Provably Efficient Black-Box Action Poisoning Attacks Against Reinforcement Learning
Authors: Guanlin Liu
Lifeng Lai
Venue: NeurIPS 2021 Poster (2021)
Keywords: action poisoning
reinforcement learning
black-box attack.

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 theoretical works on adversarial attacks against RL mainly focus on either reward 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, which brings some design challenges. 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 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 very popular model-free RL algorithm: UCB-H. We show that, even in 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.

Provably Efficient Black-Box Action Poisoning
Attacks Against Reinforcement Learning
Guanlin Liu, Lifeng Lai
Department of Electrical and Computer Engineering University of California, Davis {gInliu, lflai) llii) @ucdavis edu
Abstract
Due to the broad range of applications of reinforcement learning (RL), understand- ing the effects of adversarial attacks against RL model is essential for the safe applications of this model. Prior works adversarial attacks against RL mainly focus on either observation poisoning attacks or environment poisoning attacks. In this paper, introduce 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 more restricted, and hence the attack model is more practical. We study the action poisoning attack 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 H attack against a popular model-free RI. algorithm: UCB-H. We show that, even in the black-box setting, by spending only logarithm cost, the proposed I.CB-H attack scheme can force the UCB-H agent choose actions according the policy selected by the attacker very frequently.
Introduction
Reinforcement learning (RL), framework of control-theoretic problem that makes decisions over time under uncertain environment, has many applications in a variety of scenarios such as recom- mendation systems [Zhao et al. (018), autonomous driving OO Kelly et al. 2018). finance [Liu al., [2200] and business management [Nazari 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-Dezfooll et al. 2017
Wang et al. 2018 Cohen et al. al.][019] Dohmatobb [0119 Wang al. [ and Zhu 2019
Carmon et al.] 2 Pinot et al. [019 Alayrac et al.) 2019 Dasgupta et al. [019 Cicalese et al.
2020], the understanding of adversarial attacks on RL models less complete. Among the limited
existing works on adversarial attacks against RI,, they formally or experimentally considers different types of poisoning attack [Behzadan and Munir [201) |uann and Zhu 2019 Ma et al.) 2019 /hang al., 2020 Sun et al. 2021 Rakhsha al. [220 [021]. [Sun et al. 2021 discusses the differences between the poisoning attacks. In the observation poisoning attack setting, the attacker 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 (NcurIPS 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 suite of novel attacks 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 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 RI. 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 '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 's model, the understanding of the white-bos 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 '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 a- a-portion attack. We show that the a-portion attack strategy can force any lib-linaar-rereet RL agent to choose actions according to the target policy specified by the attacker with sub-lincar cost and sub-linear loss. (3) We develop a black-box attack strategy, LCB-H, HH, that nearly matches the performance of the white-box a-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.
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.
Related work:
(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., [021] 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 [019] 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 limited. There are some empirical studies deep RI. (Pinto)
et al. 2017
Lee et al. 2020
Sun et al. 2021
2

---

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 the research community. It is also our intention to design robust RI. algorithms that can defend against such attacks in our future work.
2 Problem Formulation
Consider a tabular episodic MDP M = P,, where S is the state space with ||| = S. A is the action space with |A| A, H E Zz is the number of steps in each episode, Pa S x A x S > [0. 1] is the probability transition function which maps state-action-stat pair to a probability, R 8 x 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 sequence of episodes. The total number of episodes is K. each episode k E [K] of this MDP, the initial states 81 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 s), and chooses an action ag. After receiving the action, the environment generates random reward Th E [0, 1] derived from distribution with mean RA (5h, an) and next state 5h+1 which is drawn from the distribution Pr (-1s), an)). Ph (-|s, a) represents the probability distribution over states if action 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 mappings t: 8 [M] A [0, ll. T. (als) represents the probability of taking action a in state under stochastic policy и at step h. We have that Eeea (als) = 1. A deterministic policy is policy that maps each state to a particular action. For notation convenience, for a deterministic policy т, we use (s) to denote the action which satisfies nA (a]s) = 1. Interacting with the environment M, the policy induces a random trajectory {si, 01, 71, $2, 02 F2, , SH aH TH, $H+1}.
We use V/T S + R denote the value function step h under policy x. Given a policy and step h. the value function of state 8 E S and the Q-function Q7 S x + R of a state-action pair (s, a) are defined as: (s) = E E Twr |s = s, म and QT a) = E [> (wr = s, s.a, = o, which represent the expected total rewards received from step h to H, under policy x, starting from state 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 = 0. Qh+1 = 0 and PA I a) = E (-Is,a)) [V
In this paper, we assume that the state space S and action space A are finite sets, and the planning horizon H is finite. Reward rı is bounded by [0, 1]. so the value function and Q-function are bounded. Under this case, there always exists an optimal policy nT' such that x' maximize the value function and Q-function: (x) == V (s) = sup, V, (s) and (7, a) == Q (s, a) = sup, Q7 a), for all and h. We measure the performance of the agent over K episodes by the regret defined as:
Regret () (st VT (st)),
where of is the initial state and x 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 and step h, after the agent chooses an action at; the attacker can change it to another action ã E A. If the attacker decides not to attack, a ot. Then the environment receives a and generates a random reward rf with mean (s at) and the next state + which is drawn from the distribution ( at)) The agent and attacker receive the reward r and the next state s 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 r as the reward and s as the next state generated from state-action pair (s/; at).
3

---

The attacker has a target policy xt. We assume that the target policy of is deterministic policy. The attacker's goal is to manipulate the agent into following the target policy π² 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 nτ. By setting 1 (-) as the indicator function, the attack cost function and the loss function are defined as
K H
K "
Cost( H) =
Σ
1
(क + ag) Loss K, H) = 1d + (sh))
(2)
k=1k=1
k=11=1
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.
3 Attack Strategy and Analysis
In this paper, we study the black-box action poisoning attack problem. In black-box attack case, the attacker has prior knowledge about the underlying environment and the agent's 's policy. It only knows the observations, i... sf. a and r generated when the agent interacts with the environment. This makes the attack practical as the attacker only needs 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.
3.1 White-box Attack
In the white-box attack model, the attacker has full information of the underlying MDP M. Thus, the attacker is able to calculate V22 (s) and Q7 (s, a) according to the Bellman optimality equations:
(i.s a) (s, a) + (s, (s) max Q7 (s,a).
(3)
aEA
Since + = O and Q7+1 = O, V/ and Q7 (s, a) can be obtained from the Bellman optimality equation. The optimal policy x" are derived from 7, = arg max Q7, 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
T (s), the attacker changes it to the action specified by the target policy à -T.((ss) When the agent selects the target action a (s). the attacker changes it to the action might be taken under the optimal policy â = (5). In addition, when the agent's '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 's point of view, πf 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 RI algorithm with sub-linear regret will learn to follow the optimal strategy in his observation, i.e. n², 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 = KT 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 n², which happens most of the time as the agent views T/ 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 n¹, the cost is too high and it does not affect the agent's '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 attack when the agent takes an action specified by st. This is possible if or 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Ø (s) inf, VA (s), the attacker

---

can not force the agent to learn the target policy without attacking the target action. For notation simplicity, denote (s) Vir (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, 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. is reasonable to limit the choice of the target policy. In this paper, we study a class of target policies denoted as II", for which each element n E IIT satisfies
(+) min (8,
aEA
for all state and all step h. That is xt is not the worst policy.
Assumption 1. For the underlying MDP M = (8, A, H, P, R). TIt + 0, and the attacker's target policy æl satisfies Il 11I.
For given target policy n², (S] |A] and are finite, the minimum of (s a) subject to a E A exists for all step h and state s. We define the minimum gap Amin by
VV((s) - min Q% kE[H],SES
Amin
min
(5)
aEA
Under Assumption 1 the minimum gap is positive, i.e. Amin 0. This positive gap provides chance of efficient action poisoning attacks. All results in this paper are based on Assumption [
We now introduce an effective white-box attack schemes: a-portion attack. Specifically, at the step h and state s, if the agent picks the target action, i.e., T/ (s), the attacker does not attack, i.c. à a nr (s). If the agent picks a non-target action, i.c., a & क (s), the a-portion attack sets ā as
x (s), with probability
ā= =
arg min Q), (s. a), with probability a. aEA
(6)
For given target policy x², define n (s) arg min Q) (s. a). We have the following result: Lemma 1. If the attacker follows the a-portion attack scheme on 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.I of the supplementary material. Using Lemma I we can derive upper bounds the loss and the cost functions the a-portion attack scheme.
Theorem 1. Assume the expected regret Regret( (K) of the RL agent's ''s algorithm is bounded by sub-linear bound R(T), ie., Regret(K) < RT))). The o-portion altack will force the agent to learn the target policy n³ with the expected cost and the expected loss bounded by
E[Cost(K, K, H)) S E.Loss(K, (K, H)) S (R(T)/(aDmin);
In addition, with probability - p. the loss and the cost is bounded by
Cost(K, H) & Loss Loss(K, K, H) < (R(T) + 2H 2 (log(1//)))())))) / ((ammnn)
(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 a = 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.
3.2 Black-box Attack
In the black-box attack setting, the attacker has no prior information about the underlying environment and the agent's 's algorithm, it only observes the samples generated when the agent interacts with the environment. Since the a-portion attack described in (6) for the white-box setting relies on the information of the underlying environment solve n the a-portion attack is not applicable in the
5

---

black-box setting. However, by collecting the observations and evaluating the Q-function Q) (s, a), the attacker can perform an attack to approximate the a-portion attack. In the proposed attack scheme, the attacker evaluates the Q-values of the target policy x² with an important sampling (IS) estimator. Then, the attacker calculates the lower confidence bound (LCCB) on the Q-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 attack similar to the a-portion attack. We name the proposed attack strategy as LCB-H attack. The algorithm is summarized Algorithm 1. the following, we will show that the LCB-H H attack nearly matches the performance of the a-portion attack.
Algorithm 1: LCB-H attack strategy on RL algorithm
Input:
Target policy xt.
1:
Initialize La (s, a) = -o, (s,)))) 0, and N,,s a) = for all state s E S, all action a E A and all step h E [H].
2: for episode k = 1, 1,2.... ........
...,, K do
3: Receive st. Initialize the set of trajectory traj {s1)-
4: for step h 1,2.....
do 5: The agent chooses an action ax.
6:
O = (5%) then
7:
The attacker does not attack, i.c. क. = af. and sets the IS weight wy = 1.
8:
else
arg La (s a) and set w/ 0, with probability 1/H, H, (+)) m/ (sh) and wa H/ 1), with probability 1 1/
9:
10:
end if
The environment receives action aie and returns the reward r and the next state $ Update the trajectory by plugging ay r and s into traj. end for
12:
13:
14:
Set the cumulative reward G GH+1= = 0 and the importance ratio PH+1:H+1 =
15:
for step h = H, H ..... , do
16:
G = rh + Gh+1, ph:1++1 = 11:H+ Wh. == (o a + N (s + (5h a (1- 2) at) + (rh + Gh+1 Ph+1:H+1).
17:
Ln (sh a = (,, at) (e(H - + 20T
18:
19:
end for
20:
end for
Here, we highlight the main idea of the LCB-H attack. As discussed in Section 3.1] the attacker has full information of the MDP and knows the worst action of any state s any step h under policy n², he can simply change the agent's '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 Qi and find the possible worst actions by the estimates of Q" Once the attacker obtains esimate Qt, it carries out an attack similar to the a- e--portion attack by setting set a = 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 - H the LCB-H attacker changes it to the target action, while with probability H the LCB-H attacker changes it to the action that has the lowest lower contidence bound value. Here, we use the lower confidence bound value because in the black-box setting, the LCB-H H attacker does not know which action is the worst, and hence uses confidence bounds to explore and exploit the worst action.
1/H (the reason why we
As shown in Algorithm| 1 after collecting observations, the LCB H attacker uses IS estimator to evaluate the target policy, which an off-policy method (Precup] 2000 Thomas et al. 2015). The IS estimator provides an unbiased estimate of the target policy m!. Suppose n/ is the control policy followed by the agent at episode k and the attacker applies LCBBH attack on the agent. From Algorithm I the probability of an action ă chosen by the behavior policy 6% the state and step h

---

can be written as
1
ā o = (s),
1/H
if ā = arg min Li (5, a) and of + (/),,,
b() =
(,))
(9)
1 - 1/H
if = (s) and a + (s),
if otherwise.
Then, the trajectory episode ki, {sf 0i r1, 2 02 r2, the behavior policy b Since we assume that the target policy is deterministic function, we have
# "H rH +1 is generated under
P(o mT) 1(ā (s))
(10)
The importance sampling ratio Pi. II
P(a (o)) lea
can be computed using (9) and (00)
which is also used in Algorithm Define the cumulative reward as G Li'=a r For notation simplicity, set P Ph. P and 1h.H+1 G when 1 I h S H, and p = 1 and G +H+1:11+1111 0. Since the trajectory is generated by following the behavior policy 6², we have that for all step h with 1 - h S H 1, V (s) EE 1 s] and (s) Elph.. Ch 1 = BBpp Gh.H (7..h+11$55
s).
We here explain why we set a = 1/ H. The main reason is that the performance of the estimates of Qi depends on the number of the observations that follow x Even though IS estimator provides an control the variance. In particular, obtain estimate Q by the Bellman consistency equations, first estimate V/+11- By setting = H we can show that the importance ratio M = .h+ S (1-O)=-R -T- I when H 2 and 1 S h < H - 1, and p P 1. As the result, P Ph+1-H G) h+1-H will be bounded, and the variance of the estimate of V++1 can be controlled.
unbiased estimate, the variance of the IS might be very high. By choosing
I/H,
1
We build confidence bound 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 RI. agent, for any p E (0, 1), with probability at least p. the following confidence bound of Q) holds simultaneously for all (s, a h E S A [H] x [k):
(s,
- (c) 2log(2SAT//////////.o (1go-)))))1/olgg2//////////////
(11)
where (s, a) represents the attacker's evaluation of Q-values at the step h at the beginning of the episode k, and N% (s,a) a) represents the cumulative number of attacker's state-action pair (s, a) at the step until the beginning of the episode k, i.e. (1, = Eb= 1(sh = =0 a.)
The detailed proof can be found in Appendix C. of the supplementary material. In Lemma 2 the given bound on LCB-H attacker's s estimation of the Q-values mainly based on N (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 the expected cumulative rewards, which bring the additional H factor.
The LCB-H H attack scheme uses a LCB method to explore and exploit the worst action. Thus, when the agent picks 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.c., the reward functions and probability transition function may change over episodes. Following the existing works on non-stationary RL [Tei et al., 2020 Mao et al. 2020 Cheung et al., 2020], we define
ki (s)
IE
E> r 1
5, π and define the expected dynamic regret for the agent as:
D-Rerret(K)) Σ vi (st)
V.l.= (st)
(12)
7

---

where zhe the optimal policy at episode i.c. Vn V , VA (s).
(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(K3 [) is bounded by sub-linear bound R(T), i.e., D-Regren(K) S RR(T). With probability 1 Ap, the LCB-H attack will force the agent to learn the target policy π. with the cost and loss bounded by
H (R(T) + 21f log 1/D)R(T)
3075 log(2S
Cost(K, H) I Loss K, H
+
A
min
A
men
we see that when R(T) S O SAH log(2SAT/p)) ) the cost and loss are bounded by
From Theorem
Amin
O( SAH log(25 (TP))) which scales log( (T), otherwise the cost and loss are bounded by ((R(T))
A?
that scales linearly with RT). The LCB-H attack nearly matches the performance of the a a-portion attack, without requiring any information of the underlying environment and the agent's s algorithm.
Compared with the results of the a-portion attack, the additional part of the bound in Theorem 2 i.c.
3078 AH" (Rp(2SAT/p)) is from the cost of exploring the worst action. Note that we use LCB method A men
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-tye concentration inequalities.
3.3 Black-box attack on UCB-H
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 UCB-Hoeffding exploration policy. At a high level, this algorithm builds an niigh-rrobabilige upper bound of Q-function for every state-action pairs. Then, 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 of the supplementary material.
Theorem 3. For any given target policy &² E If' with probability 1 - 4p. the LCB-H H attacker can successfully manipulate the UCB-H algorithm to implement the target policy x², with the cost and the loss bounded as follow:
Cosi(K, S Loss(K)= S so
SAHH 5 (HHlog((H/))) + -SAH
Amin
A
min
Theorem 3 reveals 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 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
A log(T)), where A = a) (s) Q7 (s, a) 0} is the sub-optimality gap. If an algorithm whose dynamic regret bound scales as O SA log(T)), the cost and loss are scale as O H* log(T)). 4
am [V (s)-(), Q7
A? UCB-H is stationary RI. 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.
4 Numerical Experiments
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 [lin 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 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 (x, a), with probability p(s, a). the agent navigates by the action; with probability p(s, a), the agent's next state is sampled randomly from the five adjacent states (include itself). For example, if the environment receives sate-action pair (s, a) = (5, stay),
8

---

with probability p(5, stay), the next state is 5; with probability 1-p(5, the next state is 3, 4, 5, 6 or 7. By randomly generating p(x, a) with 0.5 < p({,a) a) < 1, we randomly generate the transition probabilities P(s'|s, a) for all action and state The mean reward of state-action pairs are randomly generated from set of values {0.2, 0.35, 0.5, 0.65, 0.8). 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 We set the total number of steps H 10 and the total number of episodes K 10
lock
107
137
(a) Attack UCB-I
(b) Attack UCB-B
(c) Attack UCBVI-CH
Figure 1: Action poisoning attacks against RL agents
In Figure 1 we illustrate #-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 > Σ uses base-10 10 logarithmic scale and represents the time step with the total time step T' = K H. The y-axis represents the cumulative loss, cost and regret that change over time steps. The results show that, the loss and cost of H portion white-box attack and LCB-H black-box attack scale as (og( Furthermore the performances of our black-box attack scheme, LCB-H, nearly matches those of the H h-portion white-box attack scheme. In addition, the cost and loss are about H/ H/Amin times much as the regret. This is consistent with our analysis in Theorem 2 Each of the individual experimental runs costs about twenty hours one physical CPU core. The type of CPU is Intel Core i7-8700. More numerical results can be found in the appendix.
1 (Q) (s af) < Vi (s The x-axis
Limitations
Here we highlight the assumptions and limitations of our work. Our theoretical results rely on Assumption T which limits the choice of the target policy. A violation of Assumption | may cause linear cost or loss of the proposed attack scheme. In Theorem we assume the expected dynamic regret of the RL. agent is bounded. Generally, the expected dynamic regret is stronger notation than the dynamic regret. In other words, the optimal policy A in (12) may change in each episode k. while the optimal policy x² in (T) 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.
Conclusions and Discussion
In this paper, we have introduced new class of attacks on RL: action poisoning attacks. We have proposed the a-portion white-box attack and the LCB-H black-box attack. We have shown that the a a-portion white-box attack is able attack any efficient RL agent and the LCB-H black-box attack nearly matches the performance of the a-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 RI. model. It also of interest to investigate the defense strategy to mitigate the effects of this attack.

---

References
Jean-Baptiste Alayrac, Jonathan Uesato, Po-Sen Huang, Alhusscin Fawzi, Robert Stanforth, and Pushmect Kohli. Are labels required for improving adversarial robustmess? Advances Neural Information Processing Systems, volume 32, 2019.
Mohammad Gheshlaghi Azar, Ian Oshand, and Rémi Munos. Minimax regret bounds for reinforcement learning. In International Conference on Machine Learning. pages 263-272. 2017.
Vahid Behzadan and Arslan Munir. Vulnerability of deep reinforcement learning to policy induction attacks. In International Conference on Machine Learning and Data Mining in Patter Recognition, pages Springer, 2017.
Yair Carmon, Aditi Raghunatham, Ludwig Schmidt, John C Duchi, and Perey $ Liang. Unlabeled data improves adversarial robustness. In Advances in Neural Information Processing Systems, volume 32, 2019.
Wang Chi Cheung, David Simchi-Levi, and Ruihao Zhu. Reinforcement learning for non-stationary markov decision processes: The blessing of (more) optimism. International Conference on Machine Learning. pages 1843-1854, 2020.
Ferdinando Cicalese, Eduardo Laber, Marco Molinaro, et al. Teaching with limited information on the learner's behaviour. In International Conference on Machine Learning, pages 2016 2026, 2020.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness randomized smoothing. In International Conference on Machine Learning, pages 1310-1320, 2019.
Sanjoy Dasgupta, Daniel Hsu, Stefanos Poulis, and Xiaojin Zhu. Teaching black-box learner. In Proceedings of the 36th International Conference on Muchine Learning. volume 97. pages 1547-1555, 2019.
Elvis Dohmatob. Generalized free lunch theorem for adversarial robustness. In Proceedings of the 36th International Conference on Machine Learning, pages 1646- 1654, 2019.
Yingjic Fei, Zhuoran Yang. Zhaoran Wang, and Qiaomin Xie. Dynamic regret of policy optimization in non-stationary environments. In Advances Neural Information Processing Systems, volume 33, pages 6743-6754, 2020.
David A Freedman. On tail probabilities for martingales. the Annals of Probubility, pages 100-118 1975.
Ian Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In International Conference on Learning Representations, 2015.
Z. Guan, K. Ji, D. Bucci, T. Hu, J. Palombo, M. Liston, and Y. Liang, Robust stochastic bandit algorithms under probabilistic unbounded adversarial attack. In Proceedings of the AAAI Conference Artificial Intelligence, pages 4036-4043, New York City, NY, Feb. 2020.
Jiafan He, Dongruo Zhou, and Quanquan Gu. Logarithmic regret for reinforcement learning with linear function approximation. arXiv preprint arXiv:2011. 2..22011111666 2020.
Yunhan Huang and Quanyan Zhu, Deceptive reinforcement learning under adversarial manipulations cost signals. In International Conference Decision and Game Theory for Security, pages 217 237. Springer, 2019.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan. Is gelaamnnn provably efficient? In Advances Neural Information Processing Systems, volume 31, 2018.
Kwang-Sung Jun. Lihong Li. Yuzhe Ma, and Jerry Zhu. Adversarial attacks on stochastic bandits. In Advances in Neural Information Processing Systems, volume 31, 2018.
Alexey Kurakin, lan J. Goodfellow, and Samy Bengio. Adversarial machine learning at scale. In International Conference on Learning Representations, 2017.
Xian Yeow Lee, Sambit Ghadai, Kai Liang Tan, Chinmay Hegde, and Soumik Sarkar. Spatiotemporally constrained action space attacks deep reinforcement learning agents. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 4577-4584, 2020.
Fang Liu and Ness Shroff. Data poisoning attacks on stochastic bandits. In International Conference Muchine Learning, pages 4042-4050. 2019.
Guanlin Liu and Lifeng Lai. Action-manipun manipulation attacks against stochastic bandits: Attacks and defense. IEEE Transactions Signal Processing, 68:5152-5146 2020.
10

---

Xiao- Yang Liu, Hongyang Yang, Qian Chen, Runjia Zhang, Liuqing Yang, Bowen Xiao, and Christina Dan Wang. Finrl: A deep reinforcement learning library for automated stock trading in quantitative finance. Deep RL Workshop, NewrlPS 2020, 2020.
Yuzhe Ma, Xuezhou Zhang. Wen Sun. and Jerry Zhu. Policy poisoning in batch reinforcement learning and control. In Advances in Neural Information Processing Systems, volume 32, 2019.
Weichao Mao, Kaiqing Zhang, Ruihao 7hu, David Simchi-Levi and Tamer Basar. model-free learning nearly optimal for non-stationary rl? arXiv preprint arXiv:2010.03161, 2020.
Seyed-Mohsen Moosavi-Dezfooli, Alhussein Fawzi, Omar Fawzi, and Pascal Frossard. Universal adversarial perturbations. Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1765-1773, 2017.
MohammadReza Nazari, Afshin Oroojlooy, Lawrence Snyder, and Martin Takac. Reinforcement learning for solving the vehicle routing problem. In Advances in Neural Information Processing Systems, volume 31, 2018.
Matthew O' Kelly, Aman Sinha, Hongseok Namkoong, Russ Tedrake, and John C Duchi. Scalable end-to-end autonomous vehicle testing via rare-event simulation. Advances Neural Information Processing Systems, volume 31, 2018.
Rafael Pinot, Laurent Meunier, Alexandre Araujo, Hisashi Kashima, Florian Yger, Cedric Gouy-Paalles and Jamal Atif. Theoretical evidence for adversarial robustness through randomization. In Advances in Neural Information Processing Systems, volume 32, 2019.
Lerrel Pinto. James Davidson, Rahul Sukthankar. and Abhinav Gupta, Robust adversarial reinforcement learning. In International Conference on Machine Leurning, pages 2817-2826, 2017.
Doina Precup. Eligibility traces for off-policy policy evaluation. Computer Science Department Faculty Publication Series, page 80, 2000.
Amin Rakhsha, Goran Radanovic, Rati Devidze, Xiaojin Zhu, and Adish Singla. Policy teaching via environment poisoning: Training-time adversarial attacks against reinforcement learning. International Conference on Machine Learning, pages 7974-7984, 2020.
Amin Rakhsha, Xuezhou Zhang, Xiaojin Zhu, and Adish Singla. Reward poisoning in reinforcement learning: Attacks against unknown learners unknown environments. arXiv preprint (ttt::1022.04492 2021.
Yanchao Sun, Da Huo, and Furong Huang. Vulnerability poisoning mechanism for online rl with unknown dynamics. In International Conference on Learning Representations, 2021.
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow. and Rob Fergus. Intriguing properties of neural networks. In International Conference on Learning Representations, 2014.
Philip Thomas, Georgios Theocharous, and Mohammad Ghavamzadch. High-confidence off-policy evaluation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 29, 2015.
Joel Tropp al. Freedman's 's inequality for matrix martingales. Electronic Communications in Probability, 16: 060.270.220 2011.
Yisen Wang, Xingjun Ma, James Bailey, Jinfeng Yi, Bowen Zhou, and Quanquan Gu. On the convergence and robustness of adversarial training. In ICML, volume 1, page 2, 2019.
Yizhen Wang, Somesh Jha, and Kamalika Chaudhuri. Analyzing the robustness nearest neighbors to 2018.
adversarial examples. In International Conference on Machine Learning, pages
Kunhe Yang, Lin Yang, and Simon Du. Q-learning with logarithmic regret. In International Conference on Artificial Intelligence and Statistics, pages 1554,1184, 2021.
Tianyuan Zhang and Zhanxing Zhu. Interpreting adversarially trained convolutional neural networks. In International Conference on Machine Learning, pages 7502-7511, 2019.
Xuezhou Zhang, Yuzhe Ma, Adish Singla, and Xiaojin Zhu. Adaptive dovard-poisoning attacks against reinforcement learning. In Proceedings of the 37th International Conference on Machine Learning, volume 119, pages -1234, 2020.
Xiangyu Zhao, Long Xia, Liang Zhang, Zhuoye Ding, Dawei Yin, and Jiliang Tang. Deep reinforcement learning for page-wise recommendations, In Proceedings of the 12th ACM Conference on Recommender Systems, page 95-103. ACM, 2018


Reviews:
[{"review_id": "lSBwQOvCy_", "reviewer": "Reviewer_AUr4", "summary": "The paper presents a new attack framework on Reinforcement Learning systems that modifies the action taken by the agent without the agent noticing in order to make the agent learn the policy that the adversary wants with high probability.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, the paper has good technical content but I have the issues stated below:\n\nThe threat model seems contrived and overly powerful - I am not sure how it would ever be possible for an attacker to completely swap out actions taken by an agent with completely different actions. In an MDP setting, it seems easy to identify that a less than optimal policy is in place (RL policies have the advantage of being able to learn even after deployment), and as mentioned later, so I am not convinced how broadly applicable the ideas are to the RL setting. \nAlso, why wouldnt such an adversary sitting between the agent and the simulator also be able to modify any observation? The authors claim that modifying observations is more powerful than actions; this is stated without any evidence (mathematical or empirical); this may not be true for some problems and some prior work restrict the modification in observations.\n\nThe white box attack is very simple and could be compressed a lot in presentation.\nPerhaps more standard or complex settings for tabular episodic MDPs would help us evaluate the validity of the results more effectively than the very simple synthetic set-up.\n\nGenerally the paper could read better and has language issues, some examples include (line 21 \"applicants\" vs. \"applications\", Figure 1 contains typos (\"Tiem step\" vs Time step).\n\n-------Post Response-------- \nI increased my score as the threat model was well explained in response. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, but would have been good to propose at least a basic defense.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "iKKQbeVc-EM", "reviewer": "Reviewer_L6CC", "summary": "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The authors formally define and discuss action poisoning in multiple settings. The idea of attacking with the lower confidence bound is novel. The proposed action poisoning attack can deal with a practical black-box scenarion with log(T) cost, which is an interesting and significant contribution. The paper is in general well-written and easy to follow. The assumptions and limitations of the work are clearly stated, so it is easy to know the scope of the work.\n\nMy main concerns are: (1) how realistic are action poisoning attacks? Although the paper motivates the action attacks with auto-driving systems, the algorithm and analysis are built on a tabular case, where I find action attacks not very practical and easy to be detected. \n(2) the cost of the poisoning algorithm, although is logarithm in T, has a high dependence on H, and would be large as the target policy is closer to the worst policy. Does it suggest that the algorithm becomes impractical when the horizon is long and when the target policy is close, though not equal, to the worst policy? ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have explicitly discussed the limitations of the work in Section 5, as well as some future directions in Section 6. I would be curious to see how the proposed algorithm applies to state or reward poisoning, and a large-scale environment with function approximation.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "3gRYSvTf5WN", "reviewer": "Reviewer_R4FA", "summary": "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. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "a. Originality\n\nTo my knowledge, this is the first paper to formally study action poisoning attacks in episodic tabular RL. That being said, [Sun et al. 2021] discuss/study different 'poisoning aims' including poisoning actions (see Section 3.3.1). In that sense, some of the claims in the paper do not seem to be precise, e.g., 'Prior works on adversarial attacks in RL mainly focus on either observation poisoning attacks or environment poisoning attacks'; the same is true for the claimed contributions. Other related work is generally covered well, but could be expanded with a few more references. For example, while the introduction mentions more than 10 references on adversarial attacks in supervised learning, test-time attacks in RL are not covered to a great extent. There are also references on poisoning attacks in RL that could be added, including some older works on policy teaching, e.g., Zhang and Parkes 'Value-Based Policy Teaching with Active Indirect Elicitation'. \n\nb. Quality\n\nThe paper studies an important topic and highly relevant for designing robust RL systems. The results are interesting as they provide a principled way of designing action poisoning attacks in tabular RL setting. On the other hand, it is not clear how practical the proposed approach is. I also have some concerns/questions about the modeling assumptions. \n\nb.1.  The paper claims that this form of poisoning attacks is more practical than other forms of poisoning attacks, and the arguments are based on 'restrictiveness' ('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. '). I don't see why 'restrictiveness' would necessarily imply that the attack is more practical. Whereas action poisoning could be prevented by increasing the security of the agent, poisoning rewards might not be since rewards can be external to the agent (e.g., feedback in the recommender systems). In this sense, action poisoning might not be practical at all in some settings since it assumes a (partial) control over the agent. \n\nb.2. The overall goal could be more clearly specified and ideally formulated as an optimization problem. In Section 2, we have '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, it seems that the true goal is to have provable upper bounds on the cost/loss of attacks. The paper could also motivate the cost/loss function. E.g., in the car driving scenario from the introduction, why would it be more costly to manipulate the signal N times than M times? Why wouldn't we model the loss of the attacker through its own reward function?  \n\nb.3. The proposed algorithm looks interesting and has provable guarantees on its performance.  It is less clear whether the bounds are tight and/or informative for practical purposes. For example, some of the bounds have dependency on $H^10$ (Theorem 3), which means that even for smaller values of $H$, the bounds are quite large. The arguments regarding UCB-H and Theorem 3 are somewhat unclear. Theorem 2 considers dynamic regret, whereas the arguments are based on the results from [Yang et al., 2021], which seems to consider the notion of regret similar to (4). \n\nb.4. Experiments are relative simple, which is not surprising given that this is a theory paper. However, the running times indicate that the proposed approach might not be scalable. It is generally hard to follow the details in Section 4: Figure 1 has typos (Tiem -> Time?), y-axis is not labelled (and represent multiple measures), and the font is too small, the text mentions three agents, but it doesn't explain which ones (presumably, these are the agents in the subtitles of Figure 1?). \n\nc. Clarity\n \nThe paper is enjoyable to read. However, there are many typos and some parts could be improved and explained in more detail. A few examples: \n- The statement of Lemma 1 is not clear: what does it mean 'in the observation of the agent'?\n- In Section 4, the statements 'Ten states can be considered as a circle' and 'sampled randomly from the five adjacent states' are not clear.  \n- The organization could be improved as well. For example, Assumption 1 and Eq. 4 could be a part of the setting (otherwise, it's not clear whether this assumption applies to Section 3.1 only). In Section 2, the claim is that the performance of the agent is measured with regret as defined by (2), but then in Section 3.2 we have a different notion of the regret. \n- What is $\\pi_{h}^{-}$ in line 219? \n- The notion of behavior policy $b_k$ could be explained before being used in 246.  \n\nd. Significance\n\nIn my opinion, these results will be interesting to researchers working on adversarial attack in RL, and more specifically on poisoning attacks. The work is mainly theoretical, but some of the principles presented in the paper might lead to practical solutions. Compared to prior work, the paper studies a different setting and orthogonal aspects of poisoning attacks. Overall, I believe that the paper provides a good starting point for formally analyzing action poisoning attacks.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations are stated in Section 5. Potential societal impacts are discussed in the introduction. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4h/5h"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a new, action poisoning based attack scheme against tabular episodic RL algorithms. The authors investigate this new attack scheme in both white-box and black-box settings. For the white-box setting, the authors propose a simple attack mechanism. For the black-box case, the authors  develop a new attack that provably approximately as good as the white-box attack. 

I agree with most reviewers that the theoretical findings of this paper are very useful to understand the limitations of RL algorithms. It is worth mentioning thought that the reviewers still have some concerns regarding the scalability of the proposed attacks to non-tabular settings, which is more realistic than the tabular one studied in this paper. Despite this concern, I can conclude that the reviewers did not find any reasons to reject this paper (and neither did I). In fact, all of us are in favour of acceptance. Hence I recommend this paper to be accepted as a poster.
Decision: Accept (Poster)