{'fraction_non_alphanumeric': 0.052659574468085106, 'fraction_numerical': 0.010790273556231003, 'mean_word_length': 4.025873591751003, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 21, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 16, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Balancing detectability and performance of attacks on the control channel of Markov Decision Processes

We investigate the problem of designing optimal stealthy poisoning attacks on the control channel of Markov decision processes (MDPs). This research is motivated by the recent interest of the research community for adversarial and poisoning attacks applied to MDPs, and reinforcement learning (RL) methods. The policies resulting from these methods have been shown to be vulnerable to attacks perturbing the observations of the decision-maker. In such an attack, drawing inspiration from adversarial examples used in supervised learning, the amplitude of the adversarial perturbation is limited according to some norm, with the hope that this constraint will make the attack imperceptible. However, such constraints do not grant any level of undetectability and do not take into account the dynamic nature of the underlying Markov process. In this paper, we propose a new attack formulation, based on information-theoretical quantities, that considers the objective of minimizing the detectability of the attack as well as the performance of the controlled process. We analyze the trade-off between the efficiency of the attack and its detectability. We conclude with examples and numerical simulations illustrating this trade-off.


Introduction
The framework of Markov decision processes (MDPs) has been successful in many applications of systems control [39,43]. Thanks to its simplicity, and generality, it is capable of modeling most of the dynamical processes. For unknown processes, reinforcement learning (RL) techniques have shown great potential in controlling unknown systems. As a matter of fact, during the last decade, we have witnessed an increased surge of interest in RL, where, by exploiting modern methods in Deep Learning [26], researchers were able to reach higher performance, sometimes surpassing human performance in games such as Go, Dota, and Atari games [42,6,32,33]. This increased interest has made RL being applied more frequently in industrial applications, from temperature control in buildings [11], to health-care [51], financial trading [13] and more. However, as recently pointed out by Gartner and Microsoft [8,23] , in the next years AI cyber-attacks will leverage data poisoning, or adversarial samples, and only a small fraction of the companies have the right tools in place to secure their ML systems.
Researchers have focused on attacks that poison the data used by RL to compute the control action. Simple types of attacks can be computed by means of the Fast Gradient Sign Method (FGSM) [15,18,36], which computes a small perturbation of the data that minimizes some performance criterion. This attack has been shown to decrease the performance of RL agents when applied to observations of the state. Nonetheless, FGSM cannot compute optimal attacks. Instead, computing an optimal attack can be cast as an optimal control problem. This method of devising optimal attacks that poison the state observation has been shown in [40,53]. Similarly, some attacks directly alter the action taken by the agent, instead of the state [46,48] However, an issue of this body of work is that detectability is measured in terms of a distance metric, that is usually taken to be the 2 -norm, or the ∞ -norm, and the attack amplitude is constrained according to this metric. Unfortunately, this type of constraint does not take into account the dynamic nature of the underlying MDP, and therefore it is just an approximated way to deal with detectability.
To this aim, we propose a new attack formulation based on the idea that the adversary wants to minimize detectability as well as performance of the agent. The problem of detectability can be framed as a hypothesis testing problem, and we motivate a new attack criterion based on the theory of quickest change detection [25,4,47]. We focus our attention on attacks on the control channel of an MDP, and frame the detectability problem as a quickest change detection problem. We provide a new definition of attack detectability, and show how to compute attacks that minimize this detectability metric as well as performance. We conclude with examples and numerical simulations illustrating this trade-off.
Structure of the paper. In section 2, we present the related work, and introduce the framework of Markov decision processes. In section 3, we formulate the problem of optimally attacking the control channel of an MDP. We conclude with simulations in section 4.

Related work and preliminaries
Adversarial attacks in machine learning. Only recently researchers have started to address the problem of adversarial attacks on machine learning methods. This interest has originally sparked from an analysis [44,15] that showed how deep learning models are affected by the adversarial example phenomenon. An adversarial example is a type of perturbation that carefully alters the input data of a machine learning model with the goal of reducing the performance of the model. Technically, one aims at finding a small perturbation that if added to the data can significantly decrease the model's performance. This is usually done using an attack that relies on the gradient of the loss function of the model (check the FGSM attack for an example [15]). Many other attacks have been developed using this principle, and most of the defenses use adversarial training (i.e. the model is robustified by training on perturbed data), distilled policies or robust neural networks [24, 30,9,52,35].
Adversarial attacks in reinforcement learning. Researchers have started to also analyze the problem for reinforcement learning agents (one can refer to [10] for a brief summary). Initially, the focus has been on FGSM-like attacks on the observations of a Markov process [18, 36,5,28], or attacks that directly affect the state of the system. The latter type of attack usually studies an adversary that can directly affect the system, and the goal is to find a policy that is robust against the worst adversary by solving a minimax game where also the adversary is trying to control the MDP [34,37]. However, attacks on state observations perturb only the state measurement, but not the actual state of the system. To craft this attack using FGSM-like methods one usually uses the Q-value of a policy, since there is no loss function to consider in RL. Nonetheless, using the Q-value of a policy leads to sub-par attacks. This is due to the fact that it is equivalent to find a perturbation that minimizes the instantaneous reward, whilst optimal attacks should minimize the entire trajectory of rewards. Optimal attacks on the observations of a Markov process can be found by solving an adversarial MDP, as shown in [40,53]. Attacks on the observations lead to a partially observable model (a.k.a. POMDP), and therefore it is hard to find robust policies. Some of the defense mechanisms rely on the concept of adversarial training, policy distillation, the usage of history of data or the use of recurrent layers in neural networks [10,40].
Similarly to attacks that directly affect the state of the systems, there are attacks on the control channel of an MDP, i.e., attacks that alter the action chosen by the victim. This is in contrast with previous studies on robust MDPs, where the transition dynamics still depend on the action chosen by the victim. In this case, the adversary sits in between the victim's policy and the MDP. In [48] they analyze the case where the action is randomly perturbed by an adversary, and analyze how to robustify the agent's policy against these perturbations. To find a robust policy they frame the problem as a max-min game, but do not consider the problem of a stealthy attack. In [46] the authors consider an FGSM-like attack on the control channel, and propose adversarial training as a way to robustify the policy. In contrast, in [27] to compute an attack the authors propose to solve an optimization problem that minimizes the cumulative reward over a finite horizon, subject to budget constraints. To do so, they solve the optimization problem using a projected gradient descent method, and therefore can be considered an FGSM-like method.
Markov decision process (MDP). An MDP M is a controlled Markov chain, described by a tuple M = (S, A, P, r, p 0 ), where S and A are the state and action spaces, respectively. P : S ×A → ∆(S) denotes the conditional state transition probability distributions (∆(S) denote the set of distributions over S), i.e., P (s |s, a) is the probability to move from state s to state s given that action a is selected. We also write P (s, a) to denote the distribution over the next state given (s, a). Finally, p 0 is the initial distribution of the state and r : S × A → [0, R ] is the reward function, with R > 0. A (randomized) control policy π : S → ∆(A) determines the selected actions, and π(a|s) denotes the probability of choosing a in state s under π. Here we focus on ergodic MDPs, where any policy π generates a positive recurrent Markov chain. The discounted value of a policy π is defined as V π γ (s) = E π t≥0 γ t r(s t , a t )|s 0 = s (here a t is distributed according to π(·|s t )) for any initial state s, and discount factor γ ∈ (0, 1), whilst its ergodic reward (or average reward) is defined as

Optimal attacks on the control action
In this section, we first model the attack problem as a sequential decision-making problem. Then, we discuss two approaches to make the attack stealthy. The first approach limits the set of actions available to the adversary. The second one uses the definition of information rate to define stealthy attacks. Lastly, we conclude with the formulation of optimal stealthy attacks. Problem description. Here we describe the problem setting and how an adversarial agent attacks the control channel of a decision-maker, which we call victim in the following. First, we assume the victim uses a stationary Markov policy π, not necessarily deterministic, with the goal of maximizing the total collected reward. We then assume that the adversary is capable of measuring the state s t , and can manipulate the action taken at the input channel of the MDP. This condition implies that the adversary can change the action a t taken by the victim, and we denote the poisoned action byā t . On the other hand, the victim is not able to measure the perturbed actionā t chosen by the adversary.

Attack scheme
Additionally, we assume the reward function r is chosen by the victim (and we assume it is known by the adversary), computed according to the state-action pair (s t , a t ) in round t. This is a classical assumption in control theory, where the reward is built according to the state measurements of the system. This is in stark contrast with previous studies [48], where they considered a reward that depends on the perturbed actionā t , and not the original one a t . A consequence is that it is not possible to use the reward function as a way to detect the presence of anomalies, thus making the problem harder to solve. Nonetheless, this is not a necessary assumption, and one can relax it to take into account also the reward signal as explained later in the text.
Attack MDP. The goal of the adversary is to minimize the performance of the victim. Under these assumptions, the problem of finding an optimal attack can be cast to that of solving a Markov Decision Processes. In fact, note that for a stationary Markov policy π the system M • π can be modeled as an MDP. As a consequence, we can define an attack MDPM that the adversary wishes to control. Formally, the MDP the adversary wishes to solve isM = (S × A, A, P π ,r), where P π (s , a |s, a,ā) = π(a |s )P (s |s,ā) ∀(s,ā, a, s , a ) . The adversarial rewardr : S × A × A → R (with R being a compact closed subset of R) is chosen by the adversary, and can be simply put tor(s, a,ā) = −r(s, a) to obtain the classical zero-sum game formulation between two agents. A consequence of this formulation is that the adversary only needs to consider stationary Markov policies to optimally solve the problem. For an attack policy φ : S × A → ∆(A) we denote the overall policy of the system by φ • π : S → ∆(A). Finally, we denote respectively byV φ•π γ (s, a) = E φ•π [ t≥0γ tr (s t , a t ,ā t )|s 0 = s, a 0 = a] the discounted value of the adversarial policy for a discountγ. Similarly, for any attack φ we denote the discounted value of the attacked policy π by V φ•π γ (s) = E φ•π t≥0 γ t r(s t , a t ) s 0 = s , where s t+1 ∼ P φ (·|s t , a t ) and P φ (s |s t , a t ) = Eā ∼φ(st,at) [P (s |s t ,ā)]. Given these premises, for any attack φ we can find an upper bound of the regret of the victim, similar to the one in [53]. Proposition 1. Consider an MDP with bounded reward |r(s, a)| ≤ R . The difference of the discounted value of the policy π, and the policy under attack φ • π, is upper bounded as follows where P (·|s, a) − P (·|s,ā) T V is the total variation distance between P (·|s, a) and P (·|s,ā), and This inequality differs from the one in [40,53], where the upper bound also depends on π. Here, instead of having a total variation on the policy, we have that the bound depends solely on the transition density. Even though the bound may seem loose, the fact that we do not get a stronger dependency on π, as in [40,53], seems to suggest that the regret problem mostly depends on the underlying MDP, than the chosen policy. Then, it may not be always possible to find a robust policy. As a consequence, attack detection may be preferable. Since previous studies have not considered detectability from a statistical point of view, this leads us to study the problem of attack detectability.

Detectability constraints on the attack
In this section we study the problem of making an attack less detectable. We first consider simple constrained attacks, and argue how these attacks do not provide any stealthiness guarantee, and then proceed to study stealthy attack from a statistical point of view.
Optimal constrained attack. Stealthiness in literature has usually been defined as how close is the perturbed signal to the real signal (using a distance function d, or a norm). This assumption carries out the idea that somehow the victim is checking the goodness of the measured data. This notion of stealthiness can be easily adopted to compute an optimal constrained attack. For the discounted value (similarly also for other criterion) the attack is defined to be the optimizer of the following problem: for any (s, a) ∈ S × A,γ ∈ (0, 1) where Φ(ε; d) = {φ ∈ ∆(A) S×A : supp(φ(s, a)) ⊆Ā a (ε; d), ∀(s, a) ∈ S × A}, for ε > 0 and a metric d. The previous optimization problem results in an optimal policy φ that is deterministic, stationary and Markovian The problem can be easily solved both in the case the adversary knows the model, i.e., knows (P, π), and also in the case where the model is not known. In the former case, that we denote also as white-box, the adversary can solve the MDP by means of Value Iteration or Policy Iteration. In the latter case, that we denote as black-box case, it is possible to use RL techniques, such as Q-learning or policy-gradient based methods, to compute an optimal attack policy φ . Consequently, we omit to describe an algorithm that solves eq. (2).
However, we argue that constrained attacks are in general not stealthy. Constraining the amplitude of an attack does not necessarily imply a decrease in detectability for the following two reasons: (1) it depends on what kind of detection method the victim is using; (2) it does not consider the dynamics of the underlying process. Moreover, this notion of stealthiness tends to be useful as long as the victim can compare the measured signal with some reference signal (where the comparison is done using the metric d). However, this may not be always the case, or the adversary may not know what is the metric d. These arguments lead us to consider a different concept of stealthiness, based on statistical detectability.
Information-theoretical stealthiness We introduce a different notion of stealthiness based on information theoretical quantities. Attack detection in MDPs can be framed as a minimax quickest change detection problem (QCD), which is the problem of detecting a change point at which the statistical properties of the stochastic process undergo a change [49,47,4]. We consider minimax QCD since we do not know when the adversary attacks the system, and therefore the distribution of the change point is unknown.
The setup is as follows: we denote by ν the unknown change time at which the attack φ is applied to the MDP controlled by π. Assume the reward signal r is not provided by the MDP, but constructed directly from the observation of (s, a) (if that is not the case, we can easily change the following argument by considering (r, s, a) instead 3 ). Consequently, we consider a sequence of non-i.i.d. observations {(s t , a t )} t≥0 , and assume the conditional density of (s t , a t ) given the previous measurement is P (·|s t−1 , a t−1 ) for t < ν, and P φ (·|s t−1 , a t−1 ) otherwise.
The victim needs to decide in each round if she is under attack. Consequently, her decision takes the form of a stopping rule T (i.e., a detection rule) with respect to the filtration (F t ) t = (σ(s 0 , a 0 , . . . , s t , a t )) t . For this setup, a common criterion of performance due to Lorden and Pollak [29,38] is the worst case expected delay is taken with respect to the underlying probability measure when the change happens at time t = ν. The goal of the victim is to minimize E(T ) over all stopping rule satisfying E ∞ [T ] ≥ T , for some T > 0, when ν = ∞. The constraint, in simple words, lower bounds the expected duration to false alarm.
Having described the detection problem, we know that the following asymptotic lower bound [25] holds under some assumptions that are satisfied by ergodic Markov chains: for a constant I > 0. In brief, this lower bound characterizes the sample complexity of detecting a change in the model. Specifically, I measures the average rate of information that the victim can use to discriminate between two hypotheses. Because of this lower bound, the rate I directly affects the sample complexity of the detection problem, which increases as I decreases. Moreover. this lower bound is matched, asymptotically, by the CUSUM rule.
Therefore, the idea of the adversarial agent is to choose a policy φ that minimizes I. Consequently, detectability decreases since the detection delay of the victim increases. To proceed with this idea, we first observe that there is a clear link between I and the log-likelihood ratio (LLR). Let the LLR between the two models be z φ (s, a, s , a ) := ln P φ (s ,a |s,a) P (s ,a |s,a) . Consequently, z φ is equal to z φ (s, a, s , a ) = ln Eā ∼φ(s,a) [π(a |s )P (s |s,ā)] π(a |s )P (s |s, a) = ln P φ (s |s, a) P (s |s, a) .
Note that z φ does not depend on a and π, but solely on φ and (s, a, s ). Therefore we simply write z φ (s, a, s ) in the following. Now, we exploit the idea that for ergodic models the expected value of z φ for t ≥ ν converges to I, which, in this case, depends also on (π, φ), and we denote it by I(π, φ). Let C(π) = {(s, a) : π(a|s) > 0} be the set of possible state-action pairs, and assume that φ satisfies P φ (s, a) P (s, a), ∀(s, a) ∈ C(π). Then, it is possible to prove that for ergodic MDPs the quantity n −1 ν+n t=ν z φ (s t , a t , s t+1 ) converges to I(π, φ) as n → ∞ (see [25]). This argument motivates the following definition of stealthy attacks. Definition 2 (Information-theoretical stealthy attack). For ε ≥ 0 we define an attack policy φ to be ε-stealthy if I(π, φ) ≤ ε, where I(π, φ) is the information rate number KL(·, ·) is the KL-divergence, and µ φ•π is the on-policy distribution induced by φ and π.

Optimal information-theoretical stealthy attacks
Intuitively, definition 2 better captures the idea of a stealthy attack than definition 1 (note that the two ideas are not mutually exclusive, and can be combined together). The smaller I(π, φ) is, the harder it is for the victim to distinguish and decide between the hypothesis of being under attack or not. Based on definition 2, we can design an attack that minimizes performance as well as statistical detectability: for any (s, a) ∈ S × A,γ ∈ (0, 1), where Φ(P, π) = {φ ∈ ∆(A) S×A : P φ (s, a) P (s, a), ∀(s, a) ∈ C(π)}. Unfortunately this attack formulation can not be easily solved. A reason is that I(π, φ) is formulated in terms of the on-policy distribution, which makes eq. (5) hard to solve in presence of a discount factor. Moreover, even in case the adversary considers an ergodic reward criterion lim N →∞ , the optimization problem is still non-trivial. This is due to the dependency on φ of the KL-divergence term in I, which makes, in general, the maximization problem convex in the state-action distribution induced by the policy (i.e., φ • π) (therefore with multiple solutions attained at the boundaries of the feasible set; see also the appendix for a discussion).
Instead of solving eq. (5), we make use of the following observations: (1) first, we find an upper bound on I(π, φ) that permits us to remove the dependency on φ from the KL-divergence term; (2) secondly, we observe that we can use a discounted criterion in place of the ergodic criterion in definition 2 as long as the discount factorγ is close to 1.
Upper bounding I. The following lemma uses the log-sum inequality to upper bound I(π, φ).
P (s, a) ∧ π(a|s)φ(ā|s, a) > 0}. Then, the information value I(π, φ) can be upper bounded byĪ(π, φ) as follows Observe that the absolute continuity assumption P (s,ā) P (s, a) can be easily verified in those systems whose state is affected by some form of process noise (like exogenous stochastic disturbances of the state). We now consider the second simplification.
Discounted information rate. The second simplification permits us to consider a discounted version of definition 2. This change allows the use of discounted methods, which in turn permits to consider also the transient trajectory of the system in the information rate. Note, though, that this change is unnecessary if the adversary aims to maximize her ergodic reward, instead ofV φ•π γ . Since the result holds also for other type of problems, we state it in a general form. The key observation is that for a large discount factor we can approximate the gain of a chain with its discounted value. Proposition 2. Consider a Markov chain {x t } t over a finite space X . Consider two transition functions P 1 , P 0 over X . Assume that for t < ν the distribution of x t given x t−1 is Assume the chain is positive recurrent under P 1 , with stationary measure µ. Let γ ∈ (0, 1) and define Additionally, we also have the following proposition that bounds the error we make by considering I γ instead of the information term I. This bound can also be generalized to general state-action spaces by considering the Laurent decomposition shown in [20], Theorem 3.1. Proposition 3. Suppose the chain {x t } t is aperiodic and uniformly ergodic under P 1 , that is which converges to 0 as γ → 1.
The problem in proposition 4 can be cast as a linear program in terms of the discounted state-action discounted induced by φ • π (see the appendix for more details). Additionally, we can also determine a very useful metric, that is the hardness of detecting an attack on an MDP M controlled by π. Proposition 5. Consider any attack φ that results in an ergodic reward of the victim to be at-most ρ, with ρ ≤ E s∼µ π ,a∼π(s) [r(s, a)]. Then, the minimum achievable information rateĪ(π, φ) can be computed by solving the following linear program min The problem in eq. (10) computes the least detectable attack in the set of attacks that make the ergodic reward of the victim to be at-most ρ. The result can be used to measure the detection hardness as a function of ρ, and can help the user compare how different policies π affect detectability. Note that the optimization problem considers the ergodic reward. In case it is necessary to use a discounted reward, it is possible to prove that the problem becomes non-convex, unless one replacesĪ(π, φ) with I γ (π, φ) (see the appendix for a formulation that used a discounted reward).
Reinforcement learning approach. A consequence of proposition 4 is that deterministic policies are in general suboptimal. If RL techniques are used, then it is necessary to use a stochastic actor in order to find an optimal solution, otherwise stealthiness may not be guaranteed. The problem in proposition 4 is already formulated as a constrained MDP optimization problem [2], and therefore can be solved using constrained-policy optimization techniques, such as CPO [1] or PDO [12], where we set the constraint to be Alternatively, instead of using constrained-policy optimization techniques, it is still possible to use standard RL algorithms, like SAC [16] or PPO [41], by simply considering an augmented reward termr β that penalizes the KL-divergence with a penalty factor β > 0: where z(s, a,ā, s ) = ln P (s |s,ā) P (s |s,a) . If the likelihood ratio is not known, it is possible to use a two-time scale stochastic approximation algorithm [7] to both learn the policy φ and the likelihood ratio z, where φ is learnt at a slower pace than z.

Examples and numerical results
We now consider two significant examples: the inventory control problem, and the control of linear dynamical systems 4 . We use these two examples to demonstrate the possibility of crafting stealthy attacks capable of minimizing performance. For the inventory control problem we evaluate the efficiency of the various attack models, i.e., the constrained attack in eq. (2), the optimal stealthy randomized attack in eq. (9), and a deterministic attack computed using the rewardr β (s t , a t ,ā t ), with penalty factor β > 0, defined in the previous section. Lastly, we study how to craft stealthy attacks that minimize the average reward of a linear system.

The inventory control problem
Description. The inventory control problem is a widely known problem in literature (see, e.g., [45]), and concerns the problem of managing an inventory of fixed maximum size N in face of uncertain demand. For brevity, the details of this problem can be found in the appendix.   Fig. 2: Attack evaluation of the inventory problem. From left to right: average normalized discounted reward of the victim vs the information rate I; detection statistics c t and g t for the optimal CUSUM detector and a windowed GLR rule; difference betweenĪ and the discounted information rateĪγ for φ , which was computed according to eq. (9) using different values of (ε,γ) 4 .
Attack evaluation. In the left plot of fig. 2 are shown results for the various attacks as function of their respective parameters. For the constrained attack in eq. (2) we used a distance function d(s, s ) = |s − s |, and constrained the set of available actions to C(π ) in order to avoid that the information rate goes to infinity. We evaluated the best attack policy φ for each problem against the best policy π (s) ∈ arg max π V π γ (s), and we plotted the normalized average discounted reward of the victim's policy. Since the reward depends also on the next state, r(s, a) is an expectation that takes into account the distribution of the next state. We see that the optimal randomized attack according to eq. (9) (orange curve) achieves larger performance decrease as well as lower detectability, due to a lower value of I. On the other hand, the deterministic attack found using the rewardr β shows a discrete behavior: for values of β approximately lower than 12 we have I ≈ 0.56, and I = 0 otherwise. The fact that for decreasing β we see a decreasing reward, but constant I, is due to the fact that the attack is decreasing the detectability during the transient, and not at stationarity, since we are usingĪ γ , a discounted version of the information rate.
Attack detection. We evaluated attack detectability using the optimal CUSUM detector T c = inf{t : c t ≥ c}, with c t = (max 1≤k≤t t n=k z φ (s n , a n , s n+1 )) + , and a Generalized Likelihood Ratio (GLR) rule T g = inf{t : g t ≥ c}, with g t = (max 1≤k≤t sup P φ t n=k z φ (s n , a n , s n+1 )) + (details regarding the implementation can be found in the appendix). The threshold c in the detectors can be chosen according to the desired false alarm rate over a number of samples. For the CUSUM detector, for a probability of false alarm rate δ over m samples, with m > I −1 ln δ −1 , we have that c should satisfy 2me −c = δ to achieve the asymptotic lower bound as δ → 0 [25]. For the attacks, we have chosen values of the constraints that yield a similar decrease in performance, that is, ε = 3 in eq. (2), ε = 0.21 in eq. (9), and β = 6.2 for the deterministic attack with penalty β. The middle plot in fig. 2 depicts the statistics c t , g t for the attacks applied when the system had already converged to the stationary distribution (t = 0 denotes the round ν at which the attack starts). We see that the orange curve, which corresponds to the attack in eq. (9), is the least detectable one, and it takes roughly 3 times more to detect this attack than the one in eq. (2), even though the performance decrease is similar. Finally, the right-most plot in fig. 2 shows the goodness of approximatingĪ withĪγ, where we computed φ according to eq. (9) for different values of (ε,γ). As expected from proposition 3, for large values ofγ the two quantities coincide. Moreover, interestingly we observe thatĪγ ≤Ī for every pair (ε,γ).

Optimal attacks on linear dynamical systems
We now turn our attention to linear dynamical systems. Linear systems are of interests, since these are widely used models. Let us consider the following model x t+1 = Ax t + B(u t +ū t ) + w t , x 0 = 0 4 Results were averaged over 100 simulations, and shadowed areas indicate 99% confidence interval. where x n ∈ R n is the state at time t, u t ∈ R m is the control action,ū t ∈ R m is the attacker's action and w t is i.i.d. Gaussian noise, distributed according to N (0, Σ), Σ ∈ S n + . For simplicity, assume B is full-column rank, and assume the control policy of the victim is deterministic, of the type u t = Kx t , so that L := A + BK is Schur.
Assume thatū t is measurable with respect to the filtration σ(x 0 , . . . , x t ). We are interested in studying the adversarial problem with a penalty factor β > 0 on the value term: where T is the horizon length, and β > 0 is a penalty term that balances the trade-off between detectability and impact.
First, we note that the attack is not stealthy if the closed-loop system is unstable. This stability condition imposes some requirements on the set of possible values of β. Not surprisingly, we find that the constraint depends on the noise level Σ. Secondly, as expected, we find that random attacks are, in general, better than deterministic attacks. Finally, we also note that directly optimizing over the distribution ofū t is a hard problem to solve. Indeed, we find that the first-order condition is an integral equation that does not admit a simple closed-form solution, unless one fixes a distribution family onū t . Therefore we study the problem of finding the optimal deterministic attack, and the optimal attack distributed according to a Gaussian distribution. Theorem 1. Let J d be the solution of eq. (11) whenū t is a deterministic function of x t , and J g when u t is distributed according to a Gaussian distribution N (θ t , V t ). Then, there exists β > 0 such that for all β ∈ (0, β ) an optimal stealthy attack exists, and J g , J d are both finite, satisfying J g < J d . The optimal Gaussian attack is given by The value of β is given by β = min(β 0 , β 1 ), where β 0 = inf{β > 0 : 1 2 Σ −1 − βP ≺ 0} and β 1 = inf{β > 0 : β 2K B Σ −1 BK − I 0}, withP being the stationary solution of P t and Not surprisingly, from the theorem we have two immediate facts: (1) randomizing the attack benefits the adversary, which helps fooling the victim; (2) not all values of β are feasible. As β approaches β , the attack becomes less stealthy and more impactful. Computing the optimal attack amounts to computing a Riccati-like recursive equation in P t , which is a well-defined recursion only for β < β .
Example. Here we analyse the impact of an optimal Gaussian attack on a 2-dimensional linear system. We consider a simple system with A = 0.7 0.9 1.5 2 , B = 2 0 1 2 1 , Q = I 2 . The guarantees that the closed-loop eigenvalues λ 1 , λ 2 are approximately λ 1 ≈ 0.001 and λ 2 ≈ 0.134. In fig. 3 are shown the results of a Gaussian attack that starts after t atk = 25 rounds. We find that β ≈ 0.373, and as β approaches β the closed-loop eigenvalues converge to the boundary of the unit disk in the complex plane. This is also confirmed by the right plot of fig. 3, which depicts what is the value of E[ x 2 2 ] at stationarity. Moreover,we also have that I increases as β increases, making the attack less stealthy.

Conclusions
In this work, we have introduced a new notion of stealthiness, based on information-theoretical quantities, that can be used to compute stealthy adversarial attacks on the control channel of a Markov Decision Process. The resulting maximization problem is, in general, hard to solve, due to the concavity of the arguments. Nonetheless, the problem can be solved by considering an upper bound on the detectability metric, which results in a problem whose optimal attack policy is stationary and randomized. Finally, we tested the proposed attack on the inventory control problem and a linear dynamical system. Numerical results for both cases confirmed the efficiency of the attack in decreasing performance as well as detectability. These results indicate the need for future work to study the problem of finding ways to make attacks more detectable. An interesting venue of research would be to study the max-min problem of two competing agents that, respectively, try to maximize, and minimize, performance and detectability. Additionally, another research direction is to extend the methods presented here to the case of attacks on the observations. [27] Lee, X. Y., Ghadai, S., Tan, K. L., Hegde, C., and Sarkar, S. (2020). Spatiotemporally constrained action space attacks on deep reinforcement learning agents. In Proceedings of the AAAI Conference on Artificial Intelligence. [51] Yu, C., Liu, J., and Nemati, S. (2019). Reinforcement learning in healthcare: A survey. arXiv preprint arXiv:1908.08796.

Broader impact
Reinforcement learning has rapidly gained interest over the last years and has attracted interest from both the research community and the industry. However, reinforcement learning is still under heavy development, and more work needs to be done to understand how reinforcement learning can be deployed in real-world settings. Furthermore, the fact that in the future adversarial attacks will be one of the main ways to attack artificial intelligence systems makes the problem studied in this work even more relevant. The impact of applying reinforcement learning must then be thoroughly investigated before its deployment for real-world applications. In this paper, we considered the problem of balancing the detectability and efficiency of an attack, and quantified what is the hardness of detecting an attack for Markov Decision Processes. However, this work may have a negative impact on society, since we study the problem of making attacks less detectable. Nonetheless, it is necessary to understand this topic to come up with better detectors, and better policies. To this aim, we provided a first analysis of the detectability problem and showed how attacks can impact finite state-action space processes as well as linear dynamical systems. We believe the work presented here paves the way for many interesting research directions that will allow us to have a better understanding of how to design better policies as well as attack detectors.

Limitations of the work
This work studies the detectability problem of attacks from a theoretical point of view, and limitations are mainly due to the set of assumptions made throughout the papers. An assumption is that the reward signal depends on the poisoned actionā t , and not the original action a t . However, as pointed out in section 3, this assumption can be relaxed in the hypothesis testing problem by considering an observation (r t , s t , a t ) (instead of (s t , a t )) and by defining the corresponding conditional probabilities. Another assumption made in the text is that the underlying Markov decision process is ergodic and converges to a unique stationary distribution. However, note that this assumption is satisfied by many dynamical systems, such as stable linear systems. Moreover, the methods presented here can be extended also to the case where the process has several stationary probability measures. Finally, the proofs we provide consider finite state-action spaces and can be extended to consider general measurable spaces.

Value bound on policies under attack
In this section we provide a proof for the bound in proposition 1.
Proof of proposition 1. Let s ∈ S and write V φ•π (s) If we now consider V π (s) − V φ•π (s) it follows that we can write Now, let V π (s) = V φ•π (s) − ∆(s), and take the absolute value of the left hand-side. We can then derive the following inequalities The result follows from the last inequality, by taking γ V π − V φ•π ∞ to the left hand side and maximizing over s.

Information bounds and discounted information rate
In this section we first discuss the case where the victim uses also the reward signal to detect an attack. Next, we provide proofs for the various propositions presented section 3. Lastly, we discuss why the original problem is non-convex.

Detectability of stealthy attacks using the reward signal
It is possible to augment the QCD argument in section 3 by assuming that the victim is allowed to observe (r t , s t , a t ) instead of just (s t , a t ). For simplicity, we assume that the agent observes the reward r t upon selecting an action a t . Moreover, assume that r t is a random variable distributed according to q(s t , a t ), where a t it the action taken on the MDP M . Note that if the reward depends on the action taken by the victim, and not the one taken by the adversary, then it is the same setting that we studied in the main body of the paper. Consequently, we must have that the reward depends on the action executed on the MDP.
Then, we consider a sequence of non-i.i.d. observations {(r t , s t , a t )} t≥0 , and assume the conditional density of (r t , s t , a t ) given the previous measurement is F (·|r t−1 , s t−1 , a t−1 ) for t < ν, and Q(·|r t−1 , s t−1 , a t−1 ) otherwise. Observe that we have F (r t , s t , a t |r t−1 , s t−1 , a t−1 ) = π(a t |s t )q(r t |s t , a t )P (s t |s t−1 , a t−1 ), Q(r t , s t , a t |r t−1 , s t−1 , a t−1 ) = q φ (r t |s t , a t )π(a t |s t )P φ (s t |s t−1 , a t−1 ), where q φ (r|s, a) = Eā ∼φ(·|s,a) [q(r|s,ā)]. The agent needs to decide in each round if she is under attack. Consequently, her decision takes the form of a stopping time T with respect to the filtration (F t ) t = (σ(s 0 , a 0 , r 0 , . . . , s t , a t , r t )) t . The log-likelihood ratio takes the following form This last expression shows that in order to have a well-posed problem we require the rewards to be randomized, otherwise the log-likelihood ratio may not be well-defined. In simple words, attacks can be easily detected.
This new equation of the log-likelihood ratio changes the definition of stealthy attack changes as follows.
Due to the linearity of the arguments, all the reasonings in the main body of the paper can be straightforwardly extended to this case. First, it is possible to show that we can derive an upper bound on I(π, φ) similar to the one that we show in lemma 1 (see all the proofs in the next subsection): I(π, φ) ≤ E s∼µ φ•π ,a∼π(·|s),ā∼φ(·|s,a) [KL(P (s,ā), P (s, a)) + KL(q(s,ā), q(s, a))] =:Ī(π, φ).
(19) Also in this case the optimal policy is stationary, Markov and randomized (see next subsection to see how to compute it).

Proofs of section 3
We start by providing a proof for lemma 1. Next, we discuss proposition 2, proposition 3, proposition 4 and proposition 5.
Discounted information rate. We now give the proof of proposition 2 and proposition 3. The idea of the proofs is to consider the information rate I as the gain of a Markov reward process, and use the Laurent Decomposition due to Miller and Veinott [31] to relate I to a discounted version of the information rate.
Proof of proposition 2. The idea is to consider the Markov reward process (MRP) . Since the chain is irreducible we have two consequences: (1) it converges to a stationary measure, and (2) the gain of such chain is constant for all x ∈ X . First, observe that the gain . Due to a result of Miller and Veinott [31] (see also [39], corollary 8.2.4), if we denote by V (x) the bias of the MRP, since the rewards are bounded, we have that where e γ (x) satisfies lim γ→1 e γ (x) = 0 for all x (see [39] Theorem 8.2.3). The conclusion follows by noting that V (x) converges to 0 for γ → 1.
Proof of proposition 3. In the following we denote by I γ the |X |-dimensional vector representation of I γ (x), x ∈ X . We also denote by P 1 the |X | × |X | transition matrix for t ≥ ν. In light of proposition 2 and theorem 8.2.3 in [39] we have that where 1 is the unit vector, d is a |X |-column vector whose j-th entry is d j = KL(P 1 (x j ), P 0 (x j )), for some enumeration of the state space, and H P1 is the deviation matrix, which satisfies For recurrent and irreducible P 1 we have that P 1 = 1 ⊗ µ . Furthermore, in aperiodic Markov chains we also have that θ). Consequently, the series converges if where the r.h.s. is clearly a positive number in (0, 1). Let α = (1 − γ)/γ: it follows that the series is upper bounded by where the last term is equal to ( Optimal stealthy attacks. We now provide a proof of proposition 4. Proof of proposition 4. Let µ φ•π γ be the discounted state distribution induced by φ • π for an initial state distribution p ν (for unichain models this initial distribution can be arbitrary as long as the elements sum up to 1 [39]). Then, we begin by observing that Iγ(s, a) = 1 1 −γ s,a,ā µ φ•π γ (s)π(a|s)φ(ā|s, a)(1 −γ)KL(P (s,ā), P (s, a)), ,a∼π(·|s),ā∼φ(·|s,a) [KL(P (s,ā), P (s, a))].
For fixed π, let ξ ∈ ∆(S × A × A), and, spefically, let ξ(s, a,ā) = µ φ•π γ (s)π(a|s)φ(ā|s, a). Then, ξ represents the discounted state-action distribution induced by φ • π with discount factorγ, where the state is (s, a). Since we have the same discount factor also in the objective term we can make use of the same distribution ξ to equivalently rewrite the previous problem as (22) Thanks to theorem 8.9.6 in [39] we know there exists a solution ξ to the problem, and the optimal policy φ is stationary and randomized, satisfying φ (ā|s, a) = ξ (s, a,ā)/ ā ξ (s, a,ā) for every (s, a). In case π is deterministic, the problem can be simplified to However, in case one needs to consider the discounted reward, it is possible to consider the following problem min where we considered the discounted reward instead of the ergodic one through the discounted stationary distribution. Note, moreover, that the information rate is computed using the on-policy distribution µ φ•π . To solve the problem one can rewrite it by considering the state-action distributions ξ 0 (s, a,ā) = µ φ•π (s)π(a|s)φ(ā|s, a) and ξ 1 (s, a,ā) = µ φ•π γ (s)π(a|s)φ(ā|s, a). However, that results in a problem with non-convex constraints since the policy φ in each state (s, a) must be the same, i.e., we require ξ 0 (s, a,ā) ξ 1 (s, a) 1 = ξ 1 (s, a,ā) ξ 0 (s, a) 1 . A simple workaround is to approximateĪ usingĪ γ , as long as γ is sufficiently close to 1. This yields the following problem

The inventory control problem
Description of the example. The inventory control problem is a widely known problem in literature (see, e.g., [45]), and concerns the problem of managing an inventory of fixed maximum size N in face of uncertain demand. In each round the agent must decide the amount of items to be ordereded for the next day. The cost of purchasing a t items is k1 {at>0} + ca t , where k > 0 is a fixed cost of ordering nonzero items, and c > 0 is a fixed unitary price. Upon selling items the agent is paid an amount of p , where p > 0 is the price of a single item. Finally, there is also a cost of holding an inventory of size s > 0, that is hs, with h > 0 and p > h. The demand d t at time t is modeled according to a Poisson distribution, with demand rate λ. Then, given s t and a t , the size of the inventory the next round it s t+1 = max(0, min(N, To run the simulations, we have chosen N = 35, k = 3, c = 2, h = 2, p = 4, λ = 6. We used γ =γ = 0.95 to compute both the agent's policy and the adversary's policy. The attacks were applied after the system had already converged to the stationary distribution, after ν = 25 steps. Results were averaged over 100 simulations, and shadowed area indicate a confidence interval of 99% probability. Attack detection. We also evaluated the detectability of these attacks using the optimal CUSUM detector T c = inf{t : max 1≤k≤t t n=k z φ (s n , a n , s n+1 ) ≥ c}, and a Generalized Likelihood Ratio (GLR) rule T g = inf{t : max 1≤k≤t sup P φ t n=k z φ (s n , a n , s n+1 ) ≥ c}. To implement the GLR rule we estimate the transition kernel P φ , and used a window-limited GLR rule [25] with 38 parallel statistics, with a delay of 5 samples between each statistics. Specifically, the n-th statistic computes an estimate according to the last 5n samples.

Optimal attack on linear dynamical systems
We are interested in the following systems is full column-rank and w t ∼ N (0, Σ). We assume for simplicity that the adversarial policy φ is additive in the control action, so that a t = u t +ū t , where u t is the main agent's control action andū t is the adversarial's action. We assume u t = Kx t , where K is computed according to standard control techniques (e.g., LQR), and thatū t is a random variable measurable with respect to the sigma algebra σ(x t ) , and we can write thatū t ∼ φ(x t ) (since u t is deterministic, it suffices to consider random variables measurable with respect to σ(x t )).
We are interested in the following finite-horizon optimization problem min u0,...,ū T −1 We can rewrite the previous objective by noting that the first quantity is an expectation of KLdivergences Since the control action u t is a deterministic function of x t , we write D(Pū t (x t ), P (x t )) in the following. Letting I t = D(Pū t (x t ), P (x t )) we can write min u0,...,ū T −1 Solving the optimization problem is not straightfoward, due to the dependency of Pū on the random variableū. To show the hardness of solving such problem, we shall take a dynamic programming approach.
We also state the following simple lemma that will be useful in the calculations. Lemma 3 (Lemma 3.3 in [3]). Let x ∈ R n be a normal random variable with mean µ and covariance Σ. Then, for any n-square matrix S we have

Deterministic optimal attacks
We first consider the case whereū t is a deterministic function of x t . Consider a dynamic programming approach, and define with J T (x T ) = −βx T x T . Moreover, note that I t has the following expression for every t: I t = KL(P (x t ,ū t ), P (x t , u t )) = 1 2ū t B Σ −1 Bū t . We now prove by induction that J t (x) = −β(x P t x + p t ), with P t 0 and p t ≥ 0. At time t = T we simply have P T = I n and p T = 0.
Induction step. Then, proceeding by induction, assuming that the formula for J t holds for t + 1 we show that it holds also for t. First observe Define F t = 1 2 Σ −1 − βP t+1 . Similarly to before, by introducing y t = Bū t we obtain The solution exists and is unique if F t 0, that is, we need β ≤ 1 2 Σ 2 Pt+1 2 . Then, the solution at time t isū t = βB + F −1 t P t+1 Lx t and the cost becomes This proves the induction. Moreover, we observethat P t is positive definite if P t+1 is positive definite and β satisfies the condition β ≤ 1 2 Σ 2 Pt+1 2 for every t.
Compact expression for P t . Note that the equation of P t can be written in a compact. First, write P t = I n + L P t+1 (I n + βF −1 t+1 P t+1 )L and use the identity By setting U = I, V = β, W = P t+1 , Z = F t+1 we obtain Value of β. The dependency on β of P t does not make it clear how β should be chosen, especially when the horizon T goes to infinity. To help the analysis, we write P t,T to also highlight the dependency on the horizon.
To conduct the analysis we do the following: (1) Observe that for small values of β there exists B such that β ∈ B makes the recursion of P t,T well defined.
(2) If the recursion if well defined, then P 0,T P t,T 0 for every t, and P t,T P t,T +1 .
(1) First, note that for β → 0 then P t,T converges to the solution of the Lyapunov equation P t,T = I n + L P t+1,T L for any (t, T ). By continuity, there exists a neighborhood B of β for which P t,T exists for every β ∈ B (to show this we can also employ Theorem 6.8 in [21], which states that for a symmetric operator T (x), continuous and differentiable, also the eigenvalues are C 1 function of x.) (2) For the recursion to be well-defined we therefore need I t − βx t x t to be negative definite (otherwise the induction fails, and for β → 0 the solution P converges to a negative definite matrix, which is not possible since it converges to the Lyapunov solution of the unperturbed system). Then, if this condition is satisfied, for every β ∈ B we have P t+1,T P t,T . This follows from the simple fact that if I t+1 − βx t+1 x t+1 is negative definite then J t (x) ≤ J t+1 (x), which implies P t+1,T P t,T . Next, observe that P t,T +1 P t,T (follows easily by analyzing the recursion in the previous section).

Gaussian optimal attacks
The previous discussion on β follows from the fact that the adversary just prefers to make the system unstable for large values of β. For large values of β it is simply impossible not to be detected, therefore the adversary prefers to make the system unstable. We wonder if this can be changed by considering a random attack.
Moreover, we also wonder if random attacks are in general better than deterministic attacks.
Minimizing J t (x t ) over some distribution φ t (x t ) from whichū t is drawn from can't be easily solved, since it involves solving an integral equation. However, we can impose a parametrized distribution on φ t and solve for the parameters. We can for example impose thatū t ∼ N (θ t , V t ).
In this case I t is computed as follows Assume again that J t (x) = −βx P t x − p t , where P t 0 and p t ≥ 0. It clearly holds at time T for P T = βI, p T = 0. Finally, for simplicity, let R t = BV t B .
By induction it is possible to prove that θ t is the same asū t in the deterministic case, and V t does not depend on x t , but solely on P t+1 . The condition on β remains the same one that we found in the previous section.
Step t = T − 1. Remember that J T (x T ) = −βx T x T , then Then, at time T − 1 we have Then, the solution is clearly given θ T −1 = βB + F −1 T −1 Lx T −1 , where F t was defined in the previous section. We can find the optimal solution for R T −1 by solving the equation Therefore, we can derive the following which implies R T −1 = β 1 2 Σ −1 − βI −1 Σ. Therefore Then J T −1 (x T −1 ) = −βx T −1 (I n + L L + βL BF −1 B L)x T −1 − β Tr(Σ + R T −1 ) General solution. Iterating we can easily find that θ t is equal to the solution of the deterministic case, while the solution of R t is given by the condition Therefore, using also the symmetry of the matrices, we can derive Hence, What remains to prove is to show that −p t = −β Tr((Σ + R t )P t+1 ) + 1 2 Tr(Σ −1 R t ) − ln |I + Σ −1 R t | ≤ 0 is non-positive. Using that for square non-singular matrices A we have Tr ln A = ln |A| we find 0 ≥ − β Tr((Σ + R t )P t+1 ) + 1 2 Using the fact that R t 1 2 Σ −1 − βP t+1 − βΣP t+1 = 0 we derive Tr βΣP t+1 − βΣP t+1 − ln(I + Σ −1 R t ) = − Tr ln(I + Σ −1 R t ) ≤ 0 As required. Therefore, since P t is the same in both attacks, by comparing p t one can conclude that the value of the problem using a Gaussian attack is lower than the value of a deterministic attack. From the attacker's perspective this implies that a Gaussian attack is better than a deterministic one.