Provably Efficient Black-Box Action Poisoning Attacks Against Reinforcement Learning
Year: 2022

Abstract:
Due to the broad range of applications of reinforcement learning (RL), understanding the effects of adversarial attacks against RL model is essential for the safe applications of this model. Prior works on adversarial attacks against RL mainly focus on either observation poisoning attacks or environment poisoning attacks. In this paper, we introduce a new class of attacks named action poisoning attacks, where an adversary can change the action signal selected by the agent. Compared with existing attack models, the attacker’s ability in the proposed action poisoning attack model is more restricted, and hence the attack model is more practical. We study the action poisoning attack in both white-box and black-box settings. We introduce an adaptive attack scheme called LCB-H, which works for most RL agents in the black-box setting. We prove that the LCB-H attack can force any efficient RL agent, whose dynamic regret scales sublinearly with the total number of steps taken, to choose actions according to a policy selected by the attacker very frequently, with only sublinear cost. In addition, we apply LCB-H attack against a popular model-free RL algorithm: UCB-H. We show that, even in the black-box setting, by spending only logarithm cost, the proposed LCB-H attack scheme can force the UCB-H agent to choose actions according to the policy selected by the attacker very frequently.

heading: 1 Introduction
text: Reinforcement learning (RL), a framework of control-theoretic problem that makes decisions over time under uncertain environment, has many applications in a variety of scenarios such as recommendation systems [Zhao et al., 2018], autonomous driving [O' Kelly et al., 2018], finance [Liu et al., 2020] and business management [Nazari et al., 2018], to name a few. As RL models are being increasingly used in safety critical and security related applications, it is critical to developing trustworthy RL systems. Understanding the effects of adversarial attacks on RL systems is the first step towards the goal of safe applications of RL models.
While there is much existing work addressing adversarial attacks on supervised learning models [Szegedy et al., 2014, Goodfellow et al., 2015, Kurakin et al., 2017, Moosavi-Dezfooli et al., 2017, Wang et al., 2018, Cohen et al., 2019, Dohmatob, 2019, Wang et al., 2019, Zhang and Zhu, 2019, Carmon et al., 2019, Pinot et al., 2019, Alayrac et al., 2019, Dasgupta et al., 2019, Cicalese et al., 2020], the understanding of adversarial attacks on RL models is less complete. Among the limited existing works on adversarial attacks against RL, they formally or experimentally considers different types of poisoning attack [Behzadan and Munir, 2017, Huang and Zhu, 2019, Ma et al., 2019, Zhang et al., 2020, Sun et al., 2021, Rakhsha et al., 2020, 2021]. [Sun et al., 2021] discusses the differences between the poisoning attacks. In the observation poisoning attack setting, the attacker is able to manipulate the observations of the agent. Before the agent receives the reward signal or the state
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
signal from the environment, the attacker is able to modify the data. In the environment poisoning setting, the attacker could directly change the underlying environment, i.e., the Markov decision process (MDP) model.
In this paper, we introduce a suite of novel attacks on RL named action poisoning attacks. In the proposed action poisoning attacks models, an attacker sits between the agent and the environment and could change the agent’s action. For example, in auto-driving systems, the attacker could implement destabilizing forces or manipulate the action signal, so as to change the brake force. Compared with the observation poisoning or environment poisoning attacks, the ability of the attacker in the action poisoning attack is more restricted, which brings some design challenges. In particular, compared with observation poisoning and environment poisoning attacks, the effects of the action poisoning attack on the change of observation is less direct. Furthermore, when the action space is discrete and finite, the ability of the action poisoning attacker is severely limited. We note that the goal of this paper is not to promote action manipulation attacks. Our goal is to understand the potential risks of action manipulation attacks. Understanding the risks of different kinds of adversarial attacks on RL is essential for the safe applications of RL model and designing robust RL systems.
In this paper, we investigate action poisoning attacks in both white-box and black-box settings. The white-box attack setting makes strong assumptions. In particular, the attacker has full information of the underlying MDP, the agent’s algorithm or the agent’s previous policy models, or all of them. While it is often unrealistic to exactly know the underlying environment or have the right to obtain the information of the agent’s model, the understanding of the white-box attacks could provide insights on how to design black-box attack schemes. In the black-box setting, the attacker has no prior information of the underlying MDP and does not know the agent’s algorithm. The only information the attacker has is observations generated from the environment when the agent interacts with the environment. The black-box setting is much more practical and is suitable for more realistic scenarios.
Contributions: Our main contributions are as follows: (1) We propose an action poisoning attack model in which the attacker aims to force the agent to learn a policy selected by the attacker (will be called target policy in the sequel) by changing the agent’s actions to other actions. We use loss and cost functions to evaluate the effects of the action poisoning attack on a RL agent. The cost is the cumulative number of times when the attacker changes the agent’s action, and the loss is the cumulative number of times when the agent does not follow the target policy. It is clearly of interest to minimize both the cost and loss functions. (2) In the white-box setting, we introduce an attack strategy named α-portion attack. We show that the α-portion attack strategy can force any sub-linear-regret RL agent to choose actions according to the target policy specified by the attacker with sub-linear cost and sub-linear loss. (3) We develop a black-box attack strategy, LCB-H, that nearly matches the performance of the white-box α-portion attack. To the best of our knowledge, LCB-H is the first black-box action poisoning attack scheme that provably works against RL agents. (4) We investigate the impact of the LCH-B attack on UCB-H [Jin et al., 2018], a popular and efficient model-free Q-learning algorithm, and show that, by spending only logarithm cost, the LCB-H attack can force the UCB-H agent to choose actions according to the target policy with logarithm loss.
Related work: Existing works on poisoning attacks against RL have studied different types of adversarial manipulations. [Ma et al., 2019] studies reward poisoning attack against batch RL in which the attacker is able to gather and modify the collected batch data. [Rakhsha et al., 2020] proposes a white-box environment poisoning model in which the attacker could manipulate the original MDP to a poisoned MDP. [Behzadan and Munir, 2017, Zhang et al., 2020] study online white-box reward poisoning attacks in which the attacker could manipulate the reward signal before the agent receives it. [Sun et al., 2021] proposes a practical black-box poisoning algorithm called VA2C-P. Their empirical results show that VA2C-P works for deep policy gradient RL agents without any prior knowledge of the environment. [Rakhsha et al., 2021] develops a black-box reward poisoning attack strategy called U2, that can provably attack any efficient RL algorithms. There are also some interesting works that focus on attacking multi-arm bandit problems. In particular, [Jun et al., 2018, Liu and Shroff, 2019] investigate reward poisoning attacks and show that the attacker can manipulate the behavior of the bandit algorithms by spending only logarithm cost. [Guan et al., 2020] considers a reward poisoning attack model where an adversary attacks with a certain probability at each round.[Liu and Lai, 2020] proposes an action poisoning attack strategy against multi-arm bandit problems. Existing work on action poisoning attacks against RL is limited. There are some empirical studies in deep RL [Pinto et al., 2017, Lee et al., 2020, Sun et al., 2021].
Potential negative societal impacts: The attack strategies discussed in this paper could potentially be used by malicious users to attack real RL systems. The goal of this paper is to understand and highlight the potential negative consequences of action manipulation attacks, with the hope to raise awareness of this issue in the research community. It is also our intention to design robust RL algorithms that can defend against such attacks in our future work.

heading: 2 Problem Formulation
text: Consider a tabular episodic MDPM = (S,A, H, P,R), where S is the state space with |S| = S, A is the action space with |A| = A, H ∈ Z+ is the number of steps in each episode, Ph : S × A × S → [0, 1] is the probability transition function which maps state-action-state pair to a probability, Rh : S × A → [0, 1] represents the reward function in the step h. In this paper, the probability transition functions and the reward functions can be different at different steps.
The agent interacts with the environment in a sequence of episodes. The total number of episodes is K. In each episode k ∈ [K] of this MDP, the initial states s1 is generated randomly by a distribution or chosen by the environment. Initial states may be different between episodes. At each step h ∈ [H] of an episode, the agent observes the state sh and chooses an action ah. After receiving the action, the environment generates a random reward rh ∈ [0, 1] derived from a distribution with mean Rh(sh, ah) and next state sh+1 which is drawn from the distribution Ph(·|sh, ah). Ph(·|s, a) represents the probability distribution over states if action a is taken for state s. The agent stops interacting with environment after H steps and starts another episode.
The policy π of the agent is expressed as a mappings π : S × [H]×A → [0, 1]. πh(a|s) represents the probability of taking action a in state s under stochastic policy π at step h. We have that∑ a∈A πh(a|s) = 1. A deterministic policy is a policy that maps each state to a particular action. For notation convenience, for a deterministic policy π, we use πh(s) to denote the action a which satisfies πh(a|s) = 1. Interacting with the environmentM, the policy induces a random trajectory {s1, a1, r1, s2, a2, r2, · · · , sH , aH , rH , sH+1}. We use V πh : S → R to denote the value function at step h under policy π. Given a policy π and step h, the value function of a state s ∈ S and theQ-functionQπh : S×A → R of a state-action pair (s, a) are defined as: V πh (s) = E [∑H h′=h rh′ |sh = s, π ] and Qπh(s, a) = E [∑H h′=h rh′ |sh = s, ah = a, π ] , which represent the expected total rewards received from step h to H , under policy π, starting from state s and state-action pair (s, a) respectively. It is well-known that the value function and Q-function satisfy the Bellman consistency equations. For notation simplicity, we denote V πH+1 = 0, QπH+1 = 0 and PhV π h+1(s, a) = Es′∼Ph(·|s,a)[V πh+1(s′)].
In this paper, we assume that the state space S and action space A are finite sets, and the planning horizonH is finite. Reward rh is bounded by [0, 1], so the value function andQ-function are bounded. Under this case, there always exists an optimal policy π∗ such that π∗ maximize the value function and Q-function: V ∗h (s) := V π∗ h (s) = supπ V π h (s) and Q ∗ h(s, a) := Q π∗ h (s, a) = supπ Q π h(s, a), for all s, a and h. We measure the performance of the agent over K episodes by the regret defined as:
Regret(K) = K∑ k=1 [V ∗1 (s k 1)− V π k 1 (s k 1)], (1)
where sk1 is the initial state and π k is the control policy followed by the agent for each episode k.
In this paper, we introduce a novel adversary setting, in which the attacker sits between the agent and the environment. The attacker can monitor the state, the actions of the agent and the reward signals from the environment. Furthermore, the attacker can introduce action poisoning attacks on RL agent. In particular, at each episode k and step h, after the agent chooses an action akh, the attacker can change it to another action ãkh ∈ A. If the attacker decides not to attack, ãkh = akh. Then the environment receives ãkh, and generates a random reward r k h with mean Rh(s k h, ã k h) and the next state skh+1 which is drawn from the distribution Ph(·|skh, ãkh). The agent and attacker receive the reward rkh and the next state s k h+1 from the environment. Note that the agent does not know the attacker’s manipulations and the presence of the attacker and hence will still view rkh as the reward and s k h+1 as the next state generated from state-action pair (skh, a k h).
The attacker has a target policy π†. We assume that the target policy π† is a deterministic policy. The attacker’s goal is to manipulate the agent into following the target policy π† to pick its actions. We measure the performance of the attack over K episodes by the total attack cost and the total number of the steps that the agent does not follow the target policy π†. By setting 1(·) as the indicator function, the attack cost function and the loss function are defined as
Cost(K,H) = K∑ k=1 H∑ h=1 1 ( ãkh 6= akh ) , Loss(K,H) = K∑ k=1 H∑ h=1 1 ( akh 6= π†(skh) ) , (2)
The attacker aims to minimize both the attack cost and the loss of attacks, or minimize one of them subject to a constraint on the one another. However, obtaining optimal solutions to these optimization problems is challenging. As the first step towards understanding the impact of action poisoning attacks, we design some specific simple yet effective attack strategies.

heading: 3 Attack Strategy and Analysis
text: In this paper, we study the black-box action poisoning attack problem. In black-box attack case, the attacker has no prior knowledge about the underlying environment and the agent’s policy. It only knows the observations, i.e., skh, a k h, and r k h, generated when the agent interacts with the environment. This makes the attack practical as the attacker only needs to hijack the communication between the environment and the agent without stealing information from or attacking the agent and the environment. To build up intuitions about the proposed black-box action poisoning attack strategy, we first consider a white-box attack model, in which the attacker knows the underlying MDP and hence it is easier to design attack schemes. Building on insights obtained from the white-box attack schemes, we then introduce our proposed black-box attack strategy and analyze its performance.

heading: 3.1 White-box Attack
text: In the white-box attack model, the attacker has full information of the underlying MDPM. Thus, the attacker is able to calculate V ∗h (s) and Q ∗ h(s, a) according to the Bellman optimality equations:
Q∗h(s, a) = Rh(s, a) + PhV ∗ h+1(s, a), V ∗ h (s) = max a∈A Q∗h(s, a). (3)
Since V πH+1 = 0 and Q π H+1 = 0, V ∗ h (s) and Q ∗ h(s, a) can be obtained from the Bellman optimality equation. The optimal policy π∗ are derived from π∗h(s) = arg maxa∈AQ ∗ h(s, a).
With the knowledge of the optimal policy, the attacker can perform an intuitive attack: exchange the optimal action and the target action. In particular, at the step h and state s, when the agent picks the optimal action a = π∗h(s), the attacker changes it to the action specified by the target policy ã = π†h(s). When the agent selects the target action a = π † h(s), the attacker changes it to the action might be taken under the optimal policy ã = π∗h(s). In addition, when the agent’s action does not follow the optimal policy or the target policy, the attacker does not attack. We name this attack scheme as the exchange attack (E-attack) strategy. From the agent’s point of view, π† becomes the optimal strategy under the E-attack strategy, as the agent does not know the presence of the attacker. If the optimal policy is singular, any RL algorithm with sub-linear regret will learn to follow the optimal strategy in his observation, i.e. π†, with a sub-linear regret. As the result, the loss will be sub-linear. However, the cost of the E-attack strategy may be up to O(T ), where T = KH is the total number of steps. The main reason is that, in the E-attack strategy, the attacker needs to change the actions whenever the agent chooses an action specified by the target policy π†, which happens most of the time as the agent views π† as the optimal policy. Furthermore, another drawback of the E-attack is that the expected reward the agent receives is not impacted.
Even though the E-attack strategy discussed above could force the agent to follow the target policy π†, the cost is too high and it does not affect the agent’s total expected rewards. In order to reduce the cost and have real impact on the agent’s total expected rewards, the attacker should avoid to attack when the agent takes an action specified by π†. This is possible if π† satisfies certain conditions to be specified in the sequel.
Before presenting the proposed attack strategy, we first discuss conditions under which such an attack is possible. If the target policy is the worst policy such that V π †
h (s) = infπ V π h (s), the attacker
can not force the agent to learn the target policy without attacking the target action. For notation simplicity, we denote V †h (s) := V π†
h (s). The combination of the attacker and the environment can be considered as a new environment to the agent. As the action poisoning attack only changes the actions, it can impact but does not have direct control of the agent’s observations. Although the action poisoning attack is widely applicable, the attacker’s ability is weaker than the attacker in the environment poisoning attack model. It is reasonable to limit the choice of the target policy. In this paper, we study a class of target policies denoted as Π†, for which each element π† ∈ Π† satisfies
V †h (s) > mina∈A Q†h(s, a), (4)
for all state s and all step h. That is π† is not the worst policy. Assumption 1. For the underlying MDPM = (S,A, H, P,R), Π† 6= ∅, and the attacker’s target policy π† satisfies π† ∈ Π†.
For a given target policy π†, as |S|, |A| and H are finite, the minimum of Q†h(s, a) subject to a ∈ A exists for all step h and state s. We define the minimum gap ∆min by
∆min = min h∈[H],s∈S ( V †h (s)−mina∈AQ † h(s, a) ) . (5)
Under Assumption 1, the minimum gap is positive, i.e. ∆min > 0. This positive gap provides a chance of efficient action poisoning attacks. All results in this paper are based on Assumption 1.
We now introduce an effective white-box attack schemes: α-portion attack. Specifically, at the step h and state s, if the agent picks the target action, i.e., a = π†h(s), the attacker does not attack, i.e. ã = a = π†h(s). If the agent picks a non-target action, i.e., a 6= π † h(s), the α-portion attack sets ã as
ã = π † h(s),with probability 1− α
arg min a∈A
Q†h(s, a),with probability α. (6)
For a given target policy π†, we define π−h (s) = arg mina∈AQ † h(s, a). We have the following result: Lemma 1. If the attacker follows the α-portion attack scheme on an RL agent, in the observation of the agent, the target policy π† is the optimal policy.
The detailed proof can be found in the Appendix B.1 of the supplementary material. Using Lemma 1, we can derive upper bounds of the loss and the cost functions of the α-portion attack scheme. Theorem 1. Assume the expected regret Regret(K) of the RL agent’s algorithm is bounded by a sub-linear boundR(T ), i.e., Regret(K) ≤ R(T ). The α-portion attack will force the agent to learn the target policy π† with the expected cost and the expected loss bounded by
E[Cost(K,H)] ≤ E[Loss(K,H)] ≤ R(T )/(α∆min), (7)

heading: In addition, with probability 1− p, the loss and the cost is bounded by
text: Cost(K,H) ≤ Loss(K,H) ≤ ( R(T ) + 2H2 √ log(1/p)R(T ) ) /(α∆min). (8)
The detailed proofs can be found in the Appendix B.2 of the supplementary material. In the white-box setting, the attacker can simply choose α = 1 to most effectively attack RL agents. Intuitively speaking, if α = 1, whenever the agent chooses a non-target action, the attacker changes it to the worst action under policy π†, so that all non-target actions become worse than the target action and the target policy becomes optimal in the observation of the agent.

heading: 3.2 Black-box Attack
text: In the black-box attack setting, the attacker has no prior information about the underlying environment and the agent’s algorithm, it only observes the samples generated when the agent interacts with the environment. Since the α-portion attack described in (6) for the white-box setting relies on the information of the underlying environment to solve π−h , the α-portion attack is not applicable in the
black-box setting. However, by collecting the observations and evaluating the Q-function Q†h(s, a), the attacker can perform an attack to approximate the α-portion attack. In the proposed attack scheme, the attacker evaluates the Q-values of the target policy π† with an important sampling (IS) estimator. Then, the attacker calculates the lower confidence bound (LCB) on theQ-values so that he can explore and exploit the worst action by the LCB method. In this paper, we use Hoeffding-type martingale concentration inequalities to build the confidence bound. Using this information, the attacker can then carry out an attack similar to the α-portion attack. We name the proposed attack strategy as LCB-H attack. The algorithm is summarized in Algorithm 1. In the following, we will show that the LCB-H attack nearly matches the performance of the α-portion attack.
Algorithm 1: LCB-H attack strategy on RL algorithm Input:
Target policy π†. 1: Initialize Lh(s, a) = −∞, Q̂†h(s, a) = 0, and Nh(s, a) = 0 for all state s ∈ S , all action a ∈ A
and all step h ∈ [H]. 2: for episode k = 1, 2, . . . ,K do 3: Receive sk1 . Initialize the set of trajectory traj = {sk1}. 4: for step h = 1, 2, . . . ,H do 5: The agent chooses an action akh. 6: if akh = π † h(s k h) then 7: The attacker does not attack, i.e. ãkh = a k h, and sets the IS weight wh = 1. 8: else
9: ãkh =  arg min a 6=π†h(s k h) Lh(s k h, a) and set wh = 0, with probability 1/H,
π†h(s k h) and set wh = H/(H − 1), with probability 1− 1/H.
10: end if 11: The environment receives action ãkh, and returns the reward r k h and the next state s k h+1. 12: Update the trajectory by plugging ãkh, r k h and s k h+1 into traj. 13: end for 14: Set the cumulative reward GH+1 = 0 and the importance ratio ρH+1:H+1 = 1. 15: for step h = H,H − 1, . . . , 1 do 16: Gh = rkh +Gh+1, ρh:H+1 = ρh+1:H+1 · wh, t = Nh(skh, ãkh)← Nh(skh, ãkh) + 1. 17: Q̂†h(s k h, ã k h)← (1− 1t )Q̂ † h(s k h, ã k h) + 1 t ( rkh +Gh+1 · ρh+1:H+1 ) . 18: Lh(skh, ã k h) = Q̂ † h(s k h, ã k h)− (e(H − h) + 1) √ 2 log(2SAT/p)/t. 19: end for 20: end for
Here, we highlight the main idea of the LCB-H attack. As discussed in Section 3.1, if the attacker has full information of the MDP and knows the worst action of any state s at any step h under policy π†, he can simply change the agent’s non-target action to the worst action. However, in the black-box setting, the attacker does not know the worst actions under policy π†. One intuitive idea is to estimate Q† and find the possible worst actions by the estimates of Q†. Once the attacker obtains esimate Q̂†, it carries out an attack similar to the α-portion attack by setting α = 1/H (the reason why we set α = 1/H will be discussed in the sequel): 1) when the agent picks a target action, the LCB-H attacker does not attack ; 2) when the agent picks a non-target action, with probability 1− 1H , the LCB-H attacker changes it to the target action, while with probability 1H , the LCB-H attacker changes it to the action that has the lowest lower confidence bound value. Here, we use the lower confidence bound value because in the black-box setting, the LCB-H attacker does not know which action is the worst, and hence uses confidence bounds to explore and exploit the worst action.
As shown in Algorithm 1, after collecting observations, the LCB-H attacker uses IS estimator to evaluate the target policy, which is an off-policy method [Precup, 2000, Thomas et al., 2015]. The IS estimator provides an unbiased estimate of the target policy π†. Suppose πk is the control policy followed by the agent at episode k and the attacker applies LCB-H attack on the agent. From Algorithm 1, the probability of an action ã chosen by the behavior policy bkh at the state s and step h
can be written as
P(ã|s, bkh) =  1 if ã = akh = π † h(s), 1/H if ã = arg min a6=π†h(s) Lkh(s, a) and a k h 6= π † h(s), 1− 1/H if ã = π†h(s) and a k h 6= π † h(s),
0 if otherwise.
(9)
Then, the trajectory at episode k, {sk1 , ãk1 , rk1 , sk2 , ãk2 , rk2 , · · · , skH , ãkH , rkH , skH+1}, is generated under the behavior policy bk. Since we assume that the target policy is a deterministic function, we have
P(ã|s, π†h) = 1(ã = π † h(s)). (10)
The importance sampling ratio ρkh:H = ∏H h′=h P(ãk h′ |s k h′ ,π †)
P(ãk h′ |s k h′ ,b
k) can be computed using (9) and (10), which is also used in Algorithm 1. Define the cumulative reward as Gkh:H = ∑H h′=h r k h. For notation simplicity, we set ρkh:H+1 = ρ k h:H and G k h:H+1 = G k h:H when 1 ≤ h ≤ H , and ρkH+1:H+1 = 1 and GkH+1:H+1 = 0. Since the trajectory is generated by following the behavior policy b k, we have that for all step h with 1 ≤ h ≤ H + 1, V bkh (s) = E[Gkh:H |skh = s] and V † h (s) = E[ρkh:HGkh:H |skh = s] = E[ρkh:H+1Gkh:H+1|skh = s].
We here explain why we set α = 1/H . The main reason is that the performance of the estimates of Q† depends on the number of the observations that follow π†. Even though IS estimator provides an unbiased estimate, the variance of the IS might be very high. By choosing α = 1/H , we can control the variance. In particular, to obtain estimate Q̂†h, by the Bellman consistency equations, we first estimate V †h+1. By setting α = 1 H , we can show that the importance ratio ρ k h+1:H+1 = ρ k h+1:H ≤
1 (1−α)H−h ≤ 1 (1−α)H−1 ≤ e when H ≥ 2 and 1 ≤ h ≤ H − 1, and ρ k H+1:H+1 = 1. As the result, ρkh+1:HG k h+1:H will be bounded, and the variance of the estimate of V † h+1 can be controlled.
We build a confidence bound to show the performance of the estimate error of Q†. The confidence bound is built based on Hoeffding inequalities and shown in the following Lemma. Lemma 2. If the attacker follows the LCB-H attack strategy on the RL agent, for any p ∈ (0, 1), with probability at least 1− p, the following confidence bound of Q̂†h holds simultaneously for all (s, a, h, k) ∈ S ×A× [H]× [k]:∣∣∣Q̂†h,k(s, a)−Q†h(s, a)∣∣∣ ≤ (e(H − h) + 1)√2 log(2SAT/p)/Nkh (s, a), (11) where Q̂†h,k(s, a) represents the attacker’s evaluation of Q-values at the step h at the beginning of the episode k, and Nkh (s, a) represents the cumulative number of attacker’s state-action pair (s, a) at the step h until the beginning of the episode k, i.e. Nkh (s, a) = ∑k−1 k′=1 1(s k′ h = s)1(ã k′ h = a) .
The detailed proof can be found in Appendix C.1 of the supplementary material. In Lemma 2, the given bound on LCB-H attacker’s estimation of the Q-values mainly based on Nkh (s, a) the number of state-action pair (s, a) at the step h. This bound is similar to the confidence bound in the UCB algorithm for the bandit problem, except for the additional H factor. Compared with the bandit problem, Q-values are the expected cumulative rewards, which bring the additional H factor.
The LCB-H attack scheme uses a LCB method to explore and exploit the worst action. Thus, when the agent picks a non-target action, the LCB-H attacker changes it to different post-attack actions in different episodes. In the observation of the agent, the environment is non-stationary, i.e., the reward functions and probability transition function may change over episodes. Following the existing works on non-stationary RL [Fei et al., 2020, Mao et al., 2020, Cheung et al., 2020], we define V k,πh (s) = E [∑H h′=h r k h′ |skh = s, π ] and define the expected dynamic regret for the agent as:
D-Regret(K) = K∑ k=1 [V k,π k,∗ 1 (s k 1)− V k,πk 1 (s k 1)], (12)
where πk,∗ is the optimal policy at episode k, i.e. V k,π k,∗
h (s) = supπ V k,π h (s).
Here we state our main theorem, whose proof is deferred to the supplementary material. Theorem 2. Assume the expected dynamic regret of the RL agent’s algorithm D-Regret(K) is bounded by a sub-linear bound R(T ), i.e., D-Regret(K) ≤ R(T ). With probability 1 − 4p, the LCB-H attack will force the agent to learn the target policy π† with the cost and loss bounded by
Cost(K,H) ≤ Loss(K,H) ≤ H ( R(T ) + 2H2 √ log(1/p)R(T ) ) ∆min + 307SAH4 log(2SAT/p) ∆2min .
From Theorem 2 we see that whenR(T ) ≤ O(SAH 3 log(2SAT/p)
∆min ), the cost and loss are bounded by
O(SAH 4 log(2SAT/p)
∆2min ), which scales as log(T ), otherwise the cost and loss are bounded by O(R(T ))
that scales linearly withR(T ). The LCB-H attack nearly matches the performance of the α-portion attack, without requiring any information of the underlying environment and the agent’s algorithm. Compared with the results of the α-portion attack, the additional part of the bound in Theorem 2, i.e. 307SAH4 log(2SAT/p)
∆2min , is from the cost of exploring the worst action. Note that we use a LCB method
to explore the worst action and the confidence bound is built by Hoeffding inequalities. The bound of the loss and cost can potentially be improved by using Bernstein-type concentration inequalities.

heading: 3.3 Black-box attack on UCB-H
text: In this section, we use UCB-H algorithm [Jin et al., 2018] as an example to illustrate the effects of the proposed LCB-H action poisoning attack strategy. UCB-H algorithm is a model-free Q-learning algorithm equipped with a UCB-Hoeffding exploration policy. At a high level, this algorithm builds an high-probability upper bound of Q-function for every state-action pairs. Then, it greedily chooses the action according to the optimistic estimations. In this section, we derive an upper bound of the loss and the cost of the LCB-H attack against UCB-H agent. Complete proofs of Theorem 3 and its supporting lemmas are provided in Appendix D of the supplementary material. Theorem 3. For any given target policy π† ∈ Π†, with probability 1− 4p, the LCB-H attacker can successfully manipulate the UCB-H algorithm to implement the target policy π†, with the cost and the loss bounded as follow:
Cost(K,H) ≤ Loss(K) ≤ O ( H5 log(2H/p) + 1
∆min SAH4 +
1
∆2min H10SA log(2SAT/p)
) .
Theorem 3 reveals a significant security threat of efficient RL agents. It shows that by spending only logarithm cost, the LCB-H attack is able to force UCB-H agent to choose actions specified by a policy decided by the attack with only logarithm loss.
The results in Theorem 3 are consistent with the results in Theorem 2. In particular, [Yang et al., 2021] proved a gap-independence bound on UCB-H that scales as O(H
6SA ∆ log(T )), where ∆ =
minh,s,a{V ∗h (s)−Q∗h(s, a) : V ∗h (s)−Q∗h(s, a) > 0} is the sub-optimality gap. If an algorithm whose dynamic regret bound scales as O(H
6SA ∆ log(T )), the cost and loss are scale as O( H7SA ∆2 log(T )).
UCB-H is a stationary RL algorithm, while the LCB-H adaptively attacks the agent and hence the effective environment observed by the agent is non-stationary. This adds a factor to the loss and cost.

heading: 4 Numerical Experiments
text: In this section, we empirically evaluate the performance of LCB-H attacks against three efficient RL agents, namely UCB-H [Jin et al., 2018], UCB-B [Jin et al., 2018] and UCBVI-CH [Azar et al., 2017], respectively. We perform numerical simulations on an environment represented as an MDP with ten states and five actions, i.e. S = 10 and A = 5. The environment is a periodic 1-d grid world. The action space A is given by {two steps left, one step left, stay, one step right, two steps right}. For any given state-action pair (s, a), with probability p(s, a), the agent navigates by the action; with probability 1− p(s, a), the agent’s next state is sampled randomly from the five adjacent states (include itself). For example, if the environment receives state-action pair (s, a) = (5, stay),
with probability p(5, stay), the next state is 5; with probability 1−p(5,stay)5 , the next state is 3, 4, 5, 6 or 7. By randomly generating p(s, a) with 0.5 < p(s, a) < 1, we randomly generate the transition probabilities P (s′|s, a) for all action a and state s. The mean reward of state-action pairs are randomly generated from a set of values {0.2, 0.35, 0.5, 0.65, 0.8}. In this paper, we assume the rewards are bounded by [0, 1]. Thus, we use Bernoulli distribution to randomize the reward signal. The target policy is randomly chosen by deleting the worst action, so as to satisfy Assumption 1. We set the total number of steps H = 10 and the total number of episodes K = 109.
In Figure 1, we illustrate 1H -portion white-box attack and LCB-H black-box attack against three different agents separately and compare the loss and cost of these two attack schemes. For comparison purposes, we also add the curves for the regret of three agents under no attack. In the figure, the non-optimal action pull count are defined as ∑K k=1 ∑H h=1 1(Q ∗ h(s k h, a k h) < V ∗ h (s k h)). The x-axis uses a base-10 logarithmic scale and represents the time step t with the total time step T = KH . The y-axis represents the cumulative loss, cost and regret that change over time steps. The results show that, the loss and cost of 1H -portion white-box attack and LCB-H black-box attack scale as log(T ). Furthermore the performances of our black-box attack scheme, LCB-H, nearly matches those of the 1 H -portion white-box attack scheme. In addition, the cost and loss are about H/∆min times as much as the regret. This is consistent with our analysis in Theorem 2. Each of the individual experimental runs costs about twenty hours on one physical CPU core. The type of CPU is Intel Core i7-8700. More numerical results can be found in the appendix.

heading: 5 Limitations
text: Here we highlight the assumptions and limitations of our work. Our theoretical results rely on Assumption 1 which limits the choice of the target policy. A violation of Assumption 1 may cause linear cost or loss of the proposed attack scheme. In Theorem 2, we assume the expected dynamic regret of the RL agent is bounded. Generally, the expected dynamic regret is a stronger notation than the dynamic regret. In other words, the optimal policy πk,∗ in (12) may change in each episode k, while the optimal policy πk in (1) is fixed over episodes. In this paper, we discuss the action poisoning attack in the tabular episodic MDP context. Although we are convinced that the idea of our proposed attack scheme can be carried over to RL with function approximation, the current results only apply to the tabular episodic MDP setting.

heading: 6 Conclusions and Discussion
text: In this paper, we have introduced a new class of attacks on RL: action poisoning attacks. We have proposed the α-portion white-box attack and the LCB-H black-box attack. We have shown that the α-portion white-box attack is able to attack any efficient RL agent and the LCB-H black-box attack nearly matches the performance of the α-portion attack. We have analyzed the LCB-H attack against the UCB-H algorithm and proved that the proposed attack scheme can force the agent to almost always follow a particular class of target policy with only logarithm loss and cost. In the future, we will investigate action poisoning attacks on other RL models such as multi-agent RL model. It is also of interest to investigate the defense strategy to mitigate the effects of this attack.

Review summaries:
This paper proposes a new action poisoning framework to mislead the agent to learn a target policy. In a white-box setting, the paper introduces $\alpha$-portion attack that is guaranteed to conduct a successful attack with sublinear cost. In a black-box setting, the paper proposes an adaptive attack scheme called LCB-H that nearly matches the performance guarantees of the white-box attack method. With a case study on attacking UCB-H, the authors show that the proposed attack strategy can manipulate the learner with a logarithm cost, matching the main claim of the paper.

The paper studies poisoning attacks in reinforcement learning that override an agent's actions in order to force the policy of interest (target policy). The problem of 'action poisoning' is formulated in an episodic reinforcement learning framework, where the attacker experiences the cost of poisoning actions (equal to the number of poisoned/changed actions) and the loss of not fully forcing the target policy (equal to the number of times target policy was not followed). The paper formally studies white-box and black-box poisoning, developing a principled way of performing action poisoning attacks with provable guarantees. The main algorithmic contribution of this paper is an algorithm called LCB-H that has provable bounds on the cost and loss of poisoning. The numerical experiments are conducted to demonstrate the efficacy of the proposed black box attack.