Efficient Reward Poisoning Attacks on Online Deep Reinforcement Learning
Authors: Yinglun Xu
Qi Zeng
Gagandeep Singh
Venue: Accepted by TMLR ()

Abstract: We study reward poisoning attacks on online deep reinforcement learning (DRL), where the attacker is oblivious to the learning algorithm used by the agent and the dynamics of the environment. We demonstrate the intrinsic vulnerability of state-of-the-art DRL algorithms by designing a general, black-box reward poisoning framework called adversarial MDP attacks. We instantiate our framework to construct two new attacks which only corrupt the rewards for a small fraction of the total training timesteps and make the agent learn a low-performing policy. We provide a theoretical analysis of the efficiency of our attack and perform an extensive empirical evaluation. Our results show that our attacks efficiently poison agents learning in several popular classical control and MuJoCo environments with a variety of state-of-the-art DRL algorithms, such as DQN, PPO, SAC, etc.

Published in Transactions on Machine Learning Research (07/2023)
Efficient Reward Poisoning Attacks on Online Deep Rein- forcement Learning
Yinglun Xu
yinglun6éérlinnis.ee
Deportment of Computer Science University of Illmois Urbana- Champaign
Qi Zeng
gizengEthllinois.co edu
Department Computer Science
University of Ilinois at Urbana- Champaain
Gagandeep Singh
ggnds ggnds@illinois. edu
Department of Computer Science University of Blinois at Urbana- Chaapanhh
Reviewed on OpenReview: //penreveeeeeeeee net/ forum? ? 25G6
Abstract
We study reward poisoning attacks online deep reinforcement learning (DRL), where the attacker is oblivious to the learning algorithm used by the agent and the dynamics of the environment. We demonstrate the intrinsic vulnerability of state-of-the-art DRL algorithms by designing general, black-box reward poisoning framework called adversarial MDP allacks. We instantiale our Iramework to const.ruct two new allacks which only corrupt the rewards for a small fraction of the total training timesteps and make the agent learn a low-performing policy. We provide thcoretical analysis of the efficiency of our attack and perform an extensive empirical evaluation. Our results show that our attacks efficiently poison agents learning in several popular classical control and MuJoCo environments with a variety of state-of-the-art DRL algorithms, such as DQN, PPO, SAC, etc.
1
Introduction
To obtain state-of-tho-art performance in many real-world environments such as robot control (Christiano et al. 2017) and recommendation systems {Afsar et al. 2021 Zheng el. al.] (2018). online deep reinforcement learning (DRL) algorithms relying on human feedback for determining rewards have been applied. The dependency human foedback introduces the threat of reward-based data poisoning during training: user can deliberately provide malicious rewards to make the DRL agent learn www-pefforming policies. Data poisoning has already been identified as the most critical security concern when employing learned models in industry (Kunar et al.) (020).. Thus, it is essential to study whether state-of-the-art DRL algorithms are vulnerable to reward poisoning attacks to discover potential security vulnerabilitios and motivate the development of robust. training algorithms.
Black-box DRL attack with limited budgets. To uncover practical vulnerabilities, is critical that the attack does not rely unrealistic assumptions about the attacker's capabilities. Therefore to ensure practically feasible attack, require that: (i) the attacker does not know the exact algorithm used by the agent and the parameters of the neural network used for training. The attack should work for different kinds of learning algorithms (e.g., policy optimization, Q learning), (ii) the altacker does not know the dynamics of the agent's environment, (iii) to ensure stealthiness, the amount of reward corruption applied by the attacker over each step, each episode, and the whole training process should be limited (see Scction 3), and (iv) the attacker does not have access significant memory or computing resourees to adjust strategy for reward perturbations during training.

---

Published in Transactions on Machine Learning Research (07 (07/)023)
Challenges in poisoning attack against DRL agents. The biggest challenge in the DRL setting compared to traditional RL settings such as bandits and tabular MDPs comes from the complexity of the DRL environment and algorithms. In attack formulations for traditional RL settings, the complexity of the attack problem and the optimality-ga of the solution scale with the number of states and actions of the environment (Rakhsha et al.) 2020; ZZhang et al., 2020b Banihashem el al. 2022p. These numbers become infinite in the DRL setting where the state and action spaces are continuous and high dimensional. The aforementioned problems become too complicated to solve, and no guarantee of optimality can be given for the solutions. Furthermore, the computational resource required by previous attacks for traditional RL settings can be as even more than that required by the learning agents themselves (Zhang et al. 2020b; Rakhsha et al.) 2021), which is not practical for Deep RL applications. Finally, the learning algorithms in the traditional RL settings are well-understood, making their vulnerabilities more explicit for the at attakeer to exploit. In the DRL settings, the theoretical understanding of the state-of-the-ar DRL algorithms is still limited.
This work: efficient poisoning attacks on DRL. To the best of our knowledge, no prior work studies the vulnerability of the DRL algorithms to reward poisoning attacks under the practical restrictions mentioned above. To overcome the challenges in designing efficient attacks and demonstrate the vulncrability of the state-of-the-art DRL algorithms, we make the following contributions:
1. We propose general, efficient, and parametric reward poisoning framework for the general RL setting, which call adversarial MDP attack, and instantiate it to generate two attack methods that apply to any kind of learning algorithms and are computationally efficient. To the best of our knowledge, our attack is the first to consider the following five key elements in the threat model at the same time: 1. Training time attack, 2. Online deep RT., 3. Reward poisoning attack, 4. Complete black box attack (no knowledge about the learning algorithm and the dynamics of the enviromment), and Limited computational budget.
2. We provide a theoretical analysis for the efficiency of our attack methods in the general RL setting under basic assumptions on the efficiency of the algorithms.
3. We provide an extensive evaluation of our attack methods for poisoning the training process of several state-of-the-a DRL algorithms, such as DQN, PPO, SAC, etc., learning in classical control and MuJoCo environments that are commonly used for developing and testing DRL algorithms. Our results show that our attack methods significantly reduce the performance of the policy learned by the agent most cases.
2 Related Work
Testing time attack on R.L Testing time attacks (evasion attack) in the deep RT, setting is popular literature (Huang et al.] [2117] Kos & Song, 2017; Lin et al.) 2017). For an already trained policy, testing time attacks find adversarial examples where the learned policy has undesired behavior. In contrast, our training time altack corrupts reward to make the agent learn low-performing policies.
Data poisoning attack on bandit and tabular RLL settings. Data poisoning attacks have been studied
in the simpler bandit Jun et al. (2018); Liu & Shroff (2019h: g Xu et al. (2021b) and tabular RL Ma et al. (2019h Rakhsha et al. (2020); [Zhang et al.] (2020b); Liu & Lai (2021); |; Xu et al. (2021a) settings. These attacks require the state and action spaces of the environment to be finite, making them not applicable to the deep RL setting.
Observation perturbation attack and defense. There is a line of work studying observation perturba- tion attacks during training time (Bchzadan & Munir 2017a b Inkawhich et al. 2019) and its corresponding defense (Zhang et al.) 2021a 2020a). The threat model here does not change the actual state or reward of the environment, but instead, it changes the learner's observation of the environment by generating adversarial examples. In contrast, for the poisoning attack as considered in our work, the attacker changes the actual reward or state of the environment. Also, the observation perturbation attack mainly utilizes the vulnera- bility of the neural network to adversarial examples, which is only possible through state poisoning attacks.
2

---

Published in Transactions on Machine Learning Research (07/2023)
In our work, we focus another vulnerability that is more related to the attack considered in reinforcement learning previously. This vulnerability is that an algorithm may not sample the environments enough under the attack and conclude a sub-optimal policy to be the optimal one by the end of training. We exploit this vulnerability through reward poisoning attacks, and in principle, both state and reward poisoning attacks can utilize such vulnerability.
Data poisoning attack on DRL. The work of Sun et al. (2020) is the only other work that considers reward poisoning attack on DRL and therefore is the closest to ours. First of all, the attack problem is different in terms of budget. In Sun et al. (2000), the attacker tries to minimize the perturbation per training batch while in our work, the attacker tries to minimize the perturbation per step and over the whole training process. In addition, there are four main limitations of their attack compared to ours (a) the atlack requires the knowledge of the learning algorithm (the update rule for learned policies) used by the agent, which is not available in the black box setting, (b) the attack only works for on-policy learning algorithms, (c) the computational resource required by their attacker is more than that required by the learning agent and (d) the atlacker receives the whole training batch before deciding perturbations. This makes the allack infeasible when the agent updates the observation at each time step, as it is impossible for the attacker to apply corruption to previous observations in a training batch. Since there is no other work we could find for our more realistic attack settings, we artificially adapt our attack to the setting in their work in order to experimentally compare our results to theirs. Our results in Appendix D show that our attack requires less computational resources and achieves better attack results.
Robust learning algorithms against data poisoning attack. Robust learning algorithms can guarantee efficient learning under the data poisoning attack. There have been studies robustness in the bandit
2018 Gupta et al. 2019). and tabular MDP settings (Chen et al.) 2021 Wu et al.) 2021; Lykouris et al.
Lykouris et al., 2021). but these results are not applicable in the more complex DRL setting. For the DRL setting, Zhang et al. (2021b) proposes a learning algorithm guaranteed to be robust in a simplified DRL sctting under strong assumptions on the environment (c.g., lincar Q function and finite action space). The algorithm is further empirically tested in actual DRL settings, but the attack method used for testing robustness, which we call reward flipping attack, is not very efficient and malicious as we show in Appendix Testing against weak attack methods can provide a false sense of security. Our work provides attack methods that are more suitable for empirically measuring the robustness of learning algorithms.
3 Background
Reinforcement learning. We consider a standard RL setting where an agent trains by interacting with an environment Sutton & Barto (2018). The interaction involves the agent observing a state representation of the environment, taking an action, and receiving a reward. Formally, an environment is represented by a stationary Markov decision process (MDP), M = (S.A. R, where is the state space, A is the action space, P: A + D(S) is the state transition function, R S x A + D(R) is the reward function, and j is the distribution of the initial states. The training process consists of multiple episodes where cach episode is initialized with state sampled from μ,, and the agent interacts with the environment in each episode until it terminates. A policy π S + D(A) is mapping from the state space to the space of probability distribution ((A) over the action space. If a policy π is deterministic, then T(5) returns a single action. A value function (s) ) is the expected reward an agent obtains by following the policy л starting at state 8 the environment. M. We denote VA= == E. Eeony (M)))) as the policy value for a policy x in M, which mcasures the performance of æ. Let II be the set of all possible policics, the goal of the RL. agent is to find the optimal policy with the highest policy value n" = arg max VM- Correspondingly, we denote V y as the performance of the optimal policy. We say policy is e-optimal if its policy value satisfies
VM= 2 V
Reward poisoning attack on RL. In this work, we consider a standard data poisoning alkack setting (Jun et al.) 2018 Rakhsha et al.) 2020) where a malicious adversary tries to manipulate the agent by poisoning the reward received by the agent from the environment during training. Formally, at round t, let state and action taken by the agent be st and at. The environment generates the instant reward yd ~ R(s", ,a)) and a²). The attacker injects perturbation A to the reward. Then the agent receives the
next state s'+1, ~ ,'s''aa).
3

---

Published in Transactions on Machine Learning Research (07/2023)
perturbed observation (s', a, A s Next, we describe the constraints the attacker's knowledge, attack budgets, and the attack goal.
Constraints on attacker: We consider a fully black-box attack setting with limitations on computation resources as follows.
1. Oblivious to the algorithm. The attacker has no knowledge of the training algorithm including any parameters in the network used by the agent while training.
2. Oblivious to the environment. The attacker has no knowledge about the MDP M except for the state and actions spaces S and A.
3. Limited computational resources. The attacker can observe the current state, action, and reward tuple as',a',re a',,'")) r²) generated during training each timestep t. However, it does not have significant memory computing resources to store and learn based on the information from historical observations.
We believe such constraints make an attack realistic. In practice, the learning algorithm used by an agent is often private. Furthermore, in many cases, the dynamics of the environment can be unknown even to the learning agent, not to mention the attacker. Finally, the attacker may not always have access to significant computational resources for constructing the attack.
Attacker's budget: We consider two budgets for the attack that are typical and have been considered in previous works (Zhang et al. 2020b Rakhsha et al. 2020 The attacker tries to minimize the budgets during the attack.
1. Number of corrupted training steps. The number of timesteps C C= 11A4 0} corrupted by the attack.
2. Bounded per-step corruption. The maximum corruption at each timestep B = max, A
We notice that it can be even more realistic if one also considers the total corruption across an episode part of the budget. To simplify the attack model for theoretical analysis, do not consider the per-episode perturbation budget in Scction
5. and we consider it for the experiments in Section G
Attacker's goal: Let To be the best policy learned by the agent during training under atlack, the goal of the attack is to make the performance of To in the environment VM as small as possible.
In this work, we want to find a black-box attack with limitod computation resource that can achieve its goal with a limited budget. In the next section, we will formally formulate the attack problem.
4 Formulating Reward Poisoning Attack
Ideally, an optimal attacker would like to minimize the budget and the performance of no at the same time, but such an attack may not exist as an attack may achieve less performance of mo with more budget. Therefore, it is more reasonable to define the optimal attacker with respect a fixed budget. Formally, with the same amount of budget of B, C, the optimal attacker is the attack that can make the agent learn policies with the least performance. Let T be the total training steps, we have the following optimization problem for the optimal attack.
T
min
s.t.
ELTI M = V;E
1| #0 = C; AA B, e [T].
(1)
To solve the above optimization problem, one needs first to approximate the policy To learned by the agent under the attack, then find the optimal attack strategy that makes the agent learn the worst policy. Both steps are hard in our black-box setting. To approximate no, the attacker needs knowledge of the environment
4

---

Published in Transactions on Machine Learning Research (07/2023)
and agent. In our resource-constrannet black-box attack setting, such information is not available at the beginning of training, and the attacker does not have sufficient memory or computing resources to learn that information based on the interaction between the agent and the environment at each step. For the second step, even in the white-box setting where the attacker has knowledge of the environment and the agent, the problem has already been shown to be hard to solve in the labular MDP setting, not to mention when the state and action spaces are continuous in our DRL setting. Due to the above difficulties, instead of solving for the optimal or near-optimal attacks, we look for an efficient attacker that can satisfy the following conditions with small values of (V, B, C) defined as below which can still be major threat to the agent: Definition 4.1. ((V, -eefffiinn attack) We say an attack is (V, B, C)--fficciett if it satisfies Equation 2 with V, B, and C:
EIVM V; DE
Ca ( 1[ + +0]
A = B, Vt E [7].
(2)
t=1
The expectation is with respect to the learning process in the environment under the attack strategy.
Note that similar formulations have been considered for data poisoning attacks in traditional RL settings (Jun et a 2018: Liu & Shroff, 2019 To explain the technical details of our methods, we first introduce a mcasure for the distance d A
[0,1] between two actions in Definition 4.2
Definition 4.2. (distance between actions) For any two actions a1 E A, 0, E A. if the action space is discrete, then d(ai, 02) = 11 [a) * 02). If the action space continuous, then d(ai, 02) = ||a - a2/l2/L where L maxa, a.A. A ||a a2ll2 ll is the maximum L2-norm difference between any two actions. Note that in both cases E 1].
Since we work in a black-box setting where no specific knowledge about the agent's learning algorithm is available, we adopt general assumption for efficient learning during training:
Assumption 4.3. (Efficient learning algorithms) Let the total training steps be T. For any efficient learning algorithm, there exists d < 1, c & 1, and p < 1 such that given stationary environment M, the algorithm guarantecs that after training for T steps in M, the following holds with probability at least p: VM 2 D - and Σt= dia', >* (st))/T S.
Intuitively, the assumption says that with a high probability, the agent should learn a near-optimal policy in the environment and lake actions close to the optimal actions most of the time. We argue that such an assumption is reasonable. The value of represents how close the performance of the learned policy can be to that of the optimal policy with high probability near-optimal policy in the environment with a high chance, the value of ought to be small for small value of p. The value of 8 represents how close the actions taken by learning algorithm are to the optimal actions. To achieve the aforementioned learning goal efficiently, a learning algorithm needs to balance the trade-off and do a strategic exploration that explores sub-optimal actions less often, so we expect. the value of is expected to be small. In practice, the choices for exploration strategies current DRL algorithms include E-groody and adding random noise on the action to explore, and both satisly the assumption above. Note that in traditional RL settings, elficient learning algorithms are usually guaranteed to have such learning efficiency (Auer et al. 2002] Dong et al. 2019). For the DRL algorithms, we need to assume such guarantees on learning efficiency for predicting the behavior of the agent during training.
p. Since the goal of lcarning algorithm is to find
exploration-cxploitaaae
By Assumption 1.3, the learning algorithm can learn an e-optimal policy with a high probability when there is no attack, so we have the following definition for a trivial attack:
Definition 4.4. (Trivial attack) We say an attack is trivial if it is (V, B, ---efficientt with V 2 (1-p). (V* e) + p. Vmin: where Vmin is the minimal performance of policy in M. The reason is that when there no attack, an agent can already learn a policy with performance greater than V* E with probability at least 1- p and otherwise Vmin according to Assumption 4.3.
Based on Assumption 4.3 we propose the following attack framework that leverages this assumption for obtaining efficient attacks.
5

---

Published in Transactions on Machine Learning Research (07/2023)
Definition 4.5. (Adversarial MDP Attack) The attacker constructs an adversarial MDP M AS,A,P, R, p} which has a different reward function R compared to the true MDP, At time step t, let x be the true reward generated by the environment. The attack samples 8t ~ R(s" a') and injects corrup- tion as A 8³ r². In the end, the reward observed by the agent at step t is fe.
Under the adversarial MDP attack, the agent trains in the adversary environment M constructed by the attacker. Since the agent still trains in a stationary adversarial environment, Assumption w.icch is about the agent's s learning behavior in a stationary environment valid. So the general behavior of the agent is predictable under the adversarial MDP attack. Next, we will propose instances that solve equation 2 efficiently.
5 Poisoning Attack Methods
In this section, we design methods to construct adversarial MDP attacks under the (T, e, d)-eficcien learning
algorithm assumption and analyze their efficiency according to Equation 2 We assume the number of training sleps as the value of T, therefore the inequalities in Assumption 4.3 hold with < and ó << 1 after T training steps in any stationary environment. First, we define a naive baseline attack and show that it is inefficient, which motivates us to propose the principles to make an adversarial MDP attack efficient.
Uniformly random time (UR) attack. The altacker randomly corrupts the reward at a limestep with a fixed probability p and amount A regardless of the current state and action. Formally, the attack strategy of the UR attacker at time t is A' = A with probability p, otherwise A' = O. The UR attack requires very limited computation resources as it only needs to sample from a Bernoulli distribution with a fixed probability p at every training step. For the efficiency of the attack, it satisfies the attack problem Equation 2 with (V, C)) as below:
Theorem 5.1. For the UR attack parameterized with attack probability k, per-step corruption A, let L := (s) be the expected length of an episode before termination for an agent following the policy и. The optimal policy under the adversarial environment is V= = arg max, VM - L". The UR attack satisfies equation 2 with B = AA, C C= k- T, and V S (1-p) max -A--- V/n v.
The proof for all theorems and lemmas in this section can be found in the appendix. Note that L is independent of the reward function, so cannot be influenced by the attack. In the following lemma, we identify types of environments and A where the UR attack is trivial. Note that these cases are common and have been considered in related work for poisoning attacks against DRL (Sun et al. 2020).
Lemma 5.2. The UR attack is trivial if: (i) L is the some for all policies, or (ti) VM is monotonically increasing (or decreasing) with 1. and A is negalive (or posilive).
Lemma 5.2 shows that the UR attack can be trivial in some common cases, and we experimentally find that the efficiency of the UR attack is limited for attacking different learning algorithms in diverse environments. We believe the main reason making the UR attack inefficient is that the e-optimal policies in the adversarial environment constructed by the UR attack have high performance in the true environment. As a result, the agent will learn a policy of high performance under the attack. In this case, let II, = { M
V5_ S <} be M
the set of c-optimal policies the adversarial environment. Then for any Tı E I, and some T2 E II ITe, we have V VT and VM < VM- In other words, for some policies T1, T2 as described above, their relative performance is very different in the true and adversarial environment. Tn the cases given by Lemma 5.2 for any policy T1 E II, and T2 E IT II,, we have either V - - = VM - VMM or VM > VM, resulting in attack inefficiency. Beyond these cases, the UR attack is still inefficient, and we believe the reason is that the attack uniformly applics perturbation to all state-action pairs. To achieve the aforementioned conditions on N and n2, the difference in reward given by the true and adversarial enviromment E a) - R(s, a)) should be high for some state-action pairs at least. Under the UR attack, the difference in reward for every state-action pair is always E| a) R(ss, a)] = A-K = C.C Note that the difference bound by ERR((, a) R(s, a)) < B according to the definition of B. To achieve the highest possible value of E|R(s, a) R(ss, a)], the UR attack requires C T which is too large. An efficient attacker should achieve this with a much smaller requirement
.M .M
6

---

Published in Transactions on Machine Learning Research (07/2023)
of C. This can happen if the attack only perturbs the actions far from the optimal actions of the adversarial environment at every state. Since the agent will explore optimal actions for most training steps according to Assumption 4.3 the attacker does not need to apply perturbation for those training steps. As a result, the attacker only roquires a low value for C' while it perturbs the sub-optimal actions in the adversarial environment as much as possible, iee, by the value of B. In summary, we have two principles for designing efficient adversarial MDP attacks.
Efficient adversarial MDP attack principles:
1. The c-optimal policies in the adversarial environment have low performance in the true environment, and 2. The reward functions for the adversarial and true environments have the same output at every state for the actions whose distance to the actions given by the optimal policy in the adversarial environment is small.
Next, we propose ways to construct an adversarial MDP attack following the efficient attack principles and analyze their efficiency.
Action evasion (AE) attack. The high-level idea behind the AE attack is to make the agent believe that at each state some actions are not optimal. Then it will learn policy that never takes these actions in the corresponding states. In the RL setting, an agent needs to take optimal actions at every state to maximize its total reward. Failing to take optimal actions at any state will lead to a sub-optimal outcome. If the attacker arbitrarily selects a sub-set of actions to attack, then the sub-set of actions will contain the optimal action at some states with a high probability. Therefore the agent will not learn optimal actions at these states leading to sub-optimal results. In many cascs, such sub-optimality can be high. For example, in a challenging maze problem, the agent needs to find way from the entrance to the exit. There can be some crossroads where there is only one correct direction that leads to the exit. At every location in the maze, the attacker makes the agent not take random action. Then with high probability, in at least one crossroad the random action can be the correct action. As a result, the agent will learn a policy that does not select the correct direction at that crossroad so it can never reach the exit, which corresponds to the worst outcome. With this intuition, the policy learned by the agent that will never take some actions at every state can have low performance. Following this idea, the AE attack applics penalties on reward whenever the agent takes certain actions at every state. Formally, the AE attack is defined as follows.
Definition 5.3. (Action evasion altack) The attack specifies arbitrary policy nl, constant A >> 0, and radius r E (0, 1). At time f, the attack strategy is A = A (d(("",, ((((a'=='(s)) (s*))) <))
Note that for the discrete action spaces, any value of r E (0, will lead to the same attack that only applies perturbation when the action taken by the agent is the same as the one given by x². The computation resource required by the AE attack is the memory to store the policy n! and the computation power to calculate the output action of the policy for an input state at every training step. For ease of analysis, we define the distance between any two policies.
Definition 5.4. (r-Distance between two policies) For a value r E (0,1), the r-distance between two policies is defined as
(M R2) = Bswny (d((T( m2 2 r).
By definition, the value of the distance between two policies is bound by (T),) E [*). in the r-neighborhood of 11 if (m) T2) = 0, and 22 is r-far from Tı D, x2) L Also note that if (T m2) 0, then D, m O. Though in general, D, is not symmetric.
L0, We say me is
The efficiency of the AE attack satisfies the following:
Theorem 5.5. Let 4 = -arg max D, VM+ If A satisfies D* - > max (T,,)))++ VM A (L* (, r)), then the AE attack satisfies Equation 2 with V S (1 - p) V +V.V* B IA), C 5 p) min, [2( (a). (.)- T p- T. In the discrete action space case, the bound on C can be rewritten as C (1 5 T
For the AE attack, if the per-step perturbation A is sufficiently large (i.e., satisfies the constraint above). the e-optiall policies in the adversarial environment are always r-far from st. Since the actions that will
7

---

Published in Transactions on Machine Learning Research (07/2023)
be perturbed by the attacker are all sub-optimal actions that the agent will not frequently explore, the number of training steps to be corrupted by the attack is limited. Theorem 5.5 implies that the performance degradation (the gap between V and V*) induced by the AE attack depends on the highest performance of the policies that are r-far from xt. According to our discussion before, in many cases, the policies that never lake some actions in every state have low performance, then the performance degradation will be large. Though we note that there are cases where such policies have sub-optimal yet decent performance.
Consider environments where policies of high performance have very distinct behaviors. In these environ- ments, the sub-optimality in the outcome induced by taking a non-optimal action at any state is limited, one can still find a sub-optimal yet high--prffrmmng policy after taking a non-optimal action. As a result, policies failing to take optimal actions in some states do not necessarily have low performance. For example, consider a simple maze problem where there is no wall. The AE attack can make the agent believe that at each position, it should not take a particular direction. Since at each position, there are always paths that reach the exit without moving in that particular direction, the agent may still find path the exit in maze. Such a path may take more steps to reach the exit compared to the optimal path, but its sub- optimality in performance is limited compared to the paths which cannot reach the exit. To handle these cases, we proposc another adversarial MDP attack.
Action inducing (AI) attack. The high-level idea of the AT attack is to make the agent believe that some random actions at every state are optimal. Then the agent will learn a policy that always takes random actions at every state, and such random behavior usually leads to poor performance in practice. In the example of the simple maze problem where there is no wall, a policy that randomly walks around in the maze is very unlikely to reach the exit, leading to the worst performance. To achieve this, the attacker penalizes the agent whenever it takes action different from the ones suggested by the random actions. Formally, the AI attack is defined as follows.
Definition 5.6. (Action inducing attack) The attack randomly specifies policy æt, a constant A < 0, and a radius r. At time t, the attack strategy is A' = A 1 {d(aa, , (s²))) 2 r).
Note that for the discrete action spaces, any value of r E (0, 1) will lead to the same attack that only applies perturbation when the action taken by the agent is different from the one given by n!. Same as the case of the AE attack, the computation resources required by the AI attack is the memory to store the policy of and the computation power to calculate the output action of the policy for an input state at every training step. The efficiency of the AI attack satisfies:
Theorem 5.7. If A satisfies (x, Vz- max,:D,(s, )>o - -A,,,(TT T!), then adversarial optimal policy under the allack is x* = arg m (=,5')= VM- In this cuse, the Al allack sulisfies Equation
with V S (1 pp) VMM +p- V*, B= = Iا), and C S (1 - p) min, (r ((F (G)) T + p-T. In the discrete action space case, the bound on C can be rewrilien as C S (1 p) 5. T.
Basically, with high enough per-step perturbation, the e-optimal policies in the adversarial environment are always in the r-neighborhood of n!. Since the optimal actions are among the actions that the AI atlack will not perturb, the attacker only needs to perturb a limited number of steps when the agent explores sub- optimal actions. Theorem 5.7 immpliss that the performance degradation induced by the AT attack depends on the highest performance of the policies that are in the r-neighborhood of m!, which is a randomly generated policy. Such policies usually have low performance as discussed before, so the performance degradation is likely to be large. In Section D we experimentally test the performance of different attacks.
6 Experiments
We evaluate our attack methods from Section 5 for poisoning the training process with state-of-the-art DRL algorithms in both the discrete and continuous settings. We consider learning in enviromments typically used for assessing the performance of the DRL algorithms in the literature.
Learning algorithms and environments: We consider 4 common Gym environments (Brockman et al., 2016) in the discrete case: CartPole, LunarLander, MountainCar, and Acrobot, and continuous cases: HalfCheetah, Hopper, Walker2d, and Swimmer. The DRL algorithms in the discrete setting are: dueling
8

---

Published in Transactions on Machine Learning Research (07 2203))
deep Q learning (Duel) [Wang et al., 2016) and double dueling deep Q learning (Double) (Van Hasselt al, 2016) while for the continuous case we choose: deep deterministic policy gradient (DDPG), twin delayed DDPG (TD3), soft actor critic (SAC), and proximal policy optimization (PPO). The implementation of the algorithms is based on the spinningup project (Achiam 2018). The number of training steps T is set to be large enough so that the learning algorithu can converge within time steps without the attack.
Efficiency of the attacks: First, we want to show that our black-box attacks are efficient in diverse reprosentative learning scenarios, i..., they make the agent learn policies of low performance under limited budgets. As mentioned in Section | we consider an additional constraint on the total perturbation applied during an episode E. Despite this additional restriction on attack power, we show that our attacks remain efficient under limited budget of E. We study the influence of different values of E on the efficiency of the attack in Appendix [A]
To make the comparison fair, we let all the attacks share the same budget of B and put hard limits on budgets of C, and E. Then the attack that achieves a smaller value of V, the performance of the best policy learned by the agent, is more efficient. The hard limit on budgets means that the attacker cannot apply perturbation if doing according to its attack strategy will break the limit. Formally, if at time in episode e, 1+ Ei= 1[1 > 0] > C or | + Erer. | > E, then the attacker applies no corruption at that time step. The hard limit on the budget represents a more realistic atlack scenario as the attack can be easily detected if it uses budgets more than the hard limits. We next described our choices on the values of B, C, and E, attack parameters r and A, and how we measure V in our experiments.
Determing B. Let Vmax: Vuain be the highest and lowest expected reward policy can get in an episode. We note that Vinax Vmun represents the maximum environment-specffe net reward agent can get during an episode, and (Vans= Veiul represents the range of average reward at a time step for an agent. We set B Ammax to be higher than (Veas- Vmuil as a low value of B may not inffuence the learning process for any attack. A similar choice has also been considered in simpler tabular MDP settings (Zhang et al. 2020b).
Determing E. We restrict the value of E to be less than Vmaxx Vmin to ensure that the perturbation in each episode is less than the net reward.
Detorming C. We want the attack to corrupt as few training steps as possible, so we set the value of C/T < I. Since this is usually the most important budget, we test the efficiency of the attack under different values of C/T e (0.005,0.2]
Determing Attack parameters. For the choice of in the contimuus action spaces, we choose r from moderate range E [0.3, 0.75) for each learning scenario. In Appendix A we study the influence of r on the attack and show that the attack can work well within a wide range of values for r. For all attacks, we have
A = B by construction. The sign of A of AE and Al attack are given by Definition 5.3 and 5.6 For the UR attack, we test both cases with A = B, BB and show the best result. For the choice of πT, according to Definition 5.6 we randomly generate æ for the AT attack. For the AE attack, since the attack works the black-box setting, n² is also randomly generated. We study the influence of the choice of न for the AE attack in Appendix A
Measuring V. To evaluate the value of V, we test the empirical performance of the learned policy after each epoch and report the highest performance as the value of V. We repeat each experiment 10 times and report the average value. We report the variance of results in the appendix.
Results. Fig D compares the efficiency of the UR, AE, and AI attacks. We also show the performance of the agent without attack. We find that in most cases, the UR attack is the least efficient as it yields learned policies with similar performance the attacks are usually efficient in the learning scenarios we test despite few failing cases like learning in LunarLander environments with the ducling DQN algorithm. The reason can be that our assumptions for learning algorithms don't hold in this case. We further notice that in different learning scenarios, the relative efficiency of the two attacks is different. For example, in the case of learning in the HalfCheetah environment by DDPG algorithm, the AE attack is much more efficient than the Al attack; for learning
without atlack. For the AE and AT attacks, we find that
9

---

Published in Transactions on Machine Learning Research (07 (07/202) 2023)
None
UR
AE
AI
Hopper-x3-sac
Walkee26dv2-tt5
Acrobci-v1-duel
MounaiinGir-C-uuul
4300
-200
1000
4000
-120
2500
-150
Brstt LO0 on Policy
2000
9000
-20
1500
2500
2000
-900
500
1500
-20
-180
2.003
0.002
0.010
0.020
0000500070
CA0SS Comigee Staps Cn
0.0120
0.005
0.000
0.010
0.00
0.005
0.020
0.040
0.10
Lomrpted steps On
Comppeod 50035 Cr1
compted Strps UI
Hupperiv3 Id3
Walker2d v2 sec
Acrobot v1. double
Mountainnar v0 double
-75
-100
2500
1000
Palicy Vihkoo
-1000
-80
Best Lesrees Policy Valiee
-105
-85
2000
1500
3000
1000
-25
500
2000
-105
-120
0.020
0020
C.00SE
0.040
0.000
+allChhetta/---tt53
Swimmer-ss d-ddpg
CarsPolevi-ddubble
Lunar.arder.v2-dell
0000
Louemed Values
bo Vabue
402
220
402
220
8000
600
3000
:00
290
200
3000
150
:80
2000
10c
-50
llattCheetah-z--ddgg
Seimmee--3-apo
CartPole duel
LurarLander
1.00
750
Palty
1000
8000
Paicy V48l0
2.5
310
Palicy Value
402
200
225
175
0000
300
250
200
125
6000
202
100
3000
0320
8,0000
0.000
0.000
Stess
Steos
Steps
Commuatdd
Figure 1: The highest performance of the policy learned by different learning algorithms in different envi- ronments under our attack modh
10

---

Published in Transactions on Machine Learning Research (07/2023)
UR
At
Al
Acrobot-vl-duel
MountainCar-vO-duel
MountainCar-vO-duel
-120
Learned Valuue
Best Learned Policy Value
-120
-130
-15
-140
Best Policy
-150
-250
-160
-160
-350
-180
-180
-190
-450
-200
-20
-16
-8
-4
-1
12
16
0152.0
4.0 6.0 8.0
20.0
0150.0
4.0 6.0 8.0
20.0
Per-Step-Corruptinn
Per-Step-Coruppiin
Per-Step-Comuption
Acrobot-v1-double
MountainCar-vO-duel
MountainCar-v0-duel
-120
-100
Best Learned Policy Policy Value
Best Learned Policy Value
-140
Best Learned Policy
-140
-300
-160
-400
-180
-180
-200
-16
-8
20.0
6.0
20.0
De--Step-Corrption
Str.ttepCrrrptionnaa à
Figure 2: Experimental observations validating implications 1,2,4, and 6 from section
in the MountainCar environment with the dueling DQN algorithm, the Al attack is more efficient. These observations vindicate choice of proposing separate attacks to handle different cases.
Influence of A on different attacks: Next, we study the effect of the per-step corruption A on the attack efficiency. To exclude the effects of attack constraints, and the choice of on the policy performance V. we do not consider a hard limit on C or and only study discrete action spaces. Fig 2 shows our results. For the UR attack, we find that when is negative, the UR attack cannot influence the learning efficiency of the agent, which is expected by Lemma 5.2] For the AE and AI attacks, we find that when A small, the influence of the attack on V is limited. As the value of A increases, the influence on V becomes more significant. When A is large enough, the value of V does not change much as A increases. As pointed out by Theorem 5.5 5.7 such phenomenon indicates that when A is big enough, the agent will find the near-optimal policies among the ones that are far from (AE) or in the neighborhood (AI) of x!.
Verification of the efficient lcarning assumption: Here we verify one koy insight bohind the efficiency of the AE and AT attack: with sufficient values of A, the allack will not apply perturbation when the agent takes actions close the optimal actions in the adversarial environment, and this happens for most the training steps according to Assumption 4.3 This insight explains why the attack can work without requiring large budget for C. Fig 3 shows the result where run the AE and AI attacks the MountainCar environment with different learning algorithms. We observe in Fig 3 that after few initial epochs, the agent rarely takes the actions that the attack will perturb in the states, suggesting that our insight is correct in this empirical case.
7 Conclusion and Limitations
In this work, we study the security vulnerability of DRL algorithms against training time attacks. We designed general, parametric franework for reward poisoning attacks and instantiated it create several efficient attacks. We provide theoretical analysis for the efficiency of our attacks. Our detailed empirical
11

---

Published in Transactions on Machine Learning Research (07 2023)
Al
AE
MountainCar-vo-duel
MountaiinCar-vO-doubee
100
250
of corrupted rounds
* corrupted rounds
80
200
60
150
100
40
50
20
20
40
60
80
100
0
20
40
60
80
100
Epoch index
Epoch index
Figure 3: Experimental observations validating implications 3 and 5 from section
evaluation confirms the efficiency of our attack methods pointing the practical vulnerability of popular DRL algorithms. We introduce this attack in the hopes that highlights that practical attacks exist against DRL. Our goal is to spawn future work into developing more robust DRL learning methods.
Our attacks have the following limitations: (i) not applicable for other attack goals, e.g, to induce a target policy, (ii) cannot find the optimal attacks, and (iii) do not cover state poisoning attacks.
References
Joshua Achiam. Spinning Up in Deep Reinforcement Learning. 2018.
Mehdi Afsar, Trafford Crump, and Behrouz Far. Reinforcement learning based recommender systems: A survey. arXiv preprint orXi::2101.066 01.0688, 2021.
Peter Auer, Nicolo Cosa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47:235-256, 2002.
Kiarash Banihashem, Adish Singla, Jiarui Gan, and Goran Radanovic. Admissible policy teaching through reward design. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 6037-6045, 2022.
Vahid Behzadan and Arslan Munir. Vulnerability of deep reinforcement learning to policy induction attacks. International Conference on Machine Learning and Data Mining in Pattern Recognition, pp. 262-275. Springer, 2017a.
Vahid Behzadan and Arslan Munir. Whatever does not kill deep reinforcement learning, makes it stronger. arXiv preprinl Xin::: 1712 0.3344, 2017b.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym. arXie preprint orXiv:1606. 0100, 2016.
Yifang Chen, Simon Du, and Kevin Jamieson. Improved corruption robust algorithms for episodic reinforce- ment learning. In International Conference on Machine Learning, pp. 1561-1570. PMLR, 2021.
Paul F. Christiano, Jan Leike, Tom B. Brown, Miljan Martic, Shane Legg, and Dario Amodei. Deep rein- forcement learning from human preferences. In Proc. Neural Information Processing Systems (NeurIPS), pp. 1299-4307, 2017.
12

---

Published in Transactions on Machine Learning Research (07 (07/2023)
Kefan Dong, Yuanhao Wang, Xiaoyu Chen, and Liwei Wang. Q-learning with ueb exploration is sample efficient for infinite-horizon mdp. Xiv preprinl Xii:190100991 2019.
Anupam Gupta, Tomer Koren, and Kunal Talwar. Better algorithms for stochastic bandits with adversarial corruptions. In Conference on Learning Theory, pp. 1562 1578. PMLR, 2019.
Peter Henderson, Riashat Islam, Philip Bachman, Joelle Pineau, Doina Precup, and David Meger. Deep reinforcement learning that matters. In Proceedings of the AAAI conference artificial intelligence, volume 32, 2018.
Sandy Huang, Nicolas Papernot, Tan Goodfellow, Yan Duan, and Pieter Abbeel. Adversarial attacks on neural network policies. arXiv preprint arXiv:1772.00295 2017.
Matthew Inkawhich, Yiran Chen, and Hai Li. Snooping attacks on deep reinforcement learning. arXiv preprint arXie:1905 11832, 2019.
Kwang- Kwang-Sung Jun, Lihong Li, Yuzhe Ma, and Xiaojin Zhu. Adversarial attacks on stochastic bandits. arXiv preprinl Xiv: 12188, 2018.
Jernej Kos and Dawn Song. Delving into adversarial attacks on deep policies. arXiv:1705.066 064.06 2017.
ar preprinl
Ram Shankar Siva Kumar, Magnus Nyström, John Lambert, Andrew Marshall, Mario Goertzel, Andi Comis- soneru, Matt Swann, and Sharon Xia. Adversarial machine learning-industry perspectives. In 2020 IEEE Security and Privacy Workshops (SPW), pp. 69-75. IEEE, 2020.
Yen-Chen Lin, Zhang-War Wei Hong, Yuan-Hong Liao, Meng-Li Shih, Ming- Yu Liu, and Min Sun. Tactics of adversarial attack on deep reinforcement learning agents. arXiv preprint aixi 703.06748, 2017.
Fang Liu and Ness Shroff. Data poisoning attacks stochastic bandits. In International Conference Machine Learning, pp. 4042 4050. PMLR, 2019.
Guanlin Liu and Lifeng Lai. Provably efficient black-box action poisoning attacks against. reinforcement learning. Advances in Neural Information Processing Systems, 34, 2021.
Thodoris Lykouris, Vahab Mirrokni, and Renato Paes Leme Stochastic bandits robust adversarial cor- ruptions. In Proceedings of the 50th Annual ACM SIGACT Symposium Theory of Computing, pp. 114 122, 2018.
Thodoris Lykouris, Max Simchowitz, Alex Slivkins, and Wen Sun. Corruption-robust exploration in episodic reinforcement learning. In Conference on Learning Theory, pp. 3242-3245. PMLR, 2021.
Yuzhe Ma, Xuezhou Zhang, Wen Sun, and Xiaojin Zhu. Policy poisoning in batch reinforcement learning 2019.
and control. arXio preprint 1rXi::1910.000
Amin Rakhsha, Goran Radanovic, Rati Devidze, Xiaojin Zhu, and Adish Singla. Policy teaching via en- vironment poisoning: Training-tiin time adversarial attacks against reinforcement learning. In International Conference on Machine Learning, pp. 7974-7984 PMLR, 2020.
Amin Rakhsha, Xuezhou Zhang, Xiaojin Zhu, and Adish Singla. Reward poisoning reinforcement learning: Attacks against unknown learners in unknown environments. arXiv preprint arXiv:2102.08400 2021.
Yanchao Sun, Da Huo, and Furong Huang. Vulnerability-wware poisoning mechanism for online rl with unknown dynamics. arXiv preprint arXiv:2009.000 00774, 2020.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Hado Van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double q-learning. In Proceedings of the AAAI conference artificial intelligence, volume 30, 2016.
13

---

Published in Transactions on Machine Learning Research (07/2023)
Ziyu Wang, Tom Schaul, Matteo Hessel, Hado Hasselt, Mare Lanctot, and Nando Freitas. Ducling network architectures for deep reinforcement learning. In International conference on machine learning, pp. 1995- 2003. PMLR, 2016.
Tianhao Wu, Yunchang Yang, Simon Du, and Liwei Wang. On reinforcement learning with adversarial corruption and its application to block mdp. In International Conference on Machine Learning, pp. 11296-11306 PMLR, 2021.
Hang Xu, Rundong Wang, Lev Raizman, and Zinovi Rabinovich. Transferable environment poisoning: Training-time attack on reinforcement. learning. In Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems, pp. 1398 1406, 2021a.
Yinglun Xu, Bhuvesh Kumar, and Jacob D Abernethy. Observation-free attacks on stochastic bandits. Advances in Newral Information Processing Systems, 34, 2021b.
Huan Zhang, Hongge Chen, Chaowei Xiao, Bo Li, Duane Boning, and Cho-Jui Hsieh. Robust deep rein- forcement learning against adversarial perturbations observations. orXiv preprint arXiv:2008.08988 2020a.
Huan Zhang, Hongge Chen, Duane Boning, and Cho-Jui Hsieh. Robust reinforcement learning on state observations with learned optimal adversary. arXis preprint arXiv:2101. 204401000.842,, 2021a.
Xuezhou Zhang, Yuzhe Ma, Adish Singla, and Xiaojin Zhu. Adaptive sward-poisoning attacks against reinforcement learning. In International Conference on Machine Learning, pp. 11225 11234. PMLR, 2020b.
Xuezhou Zhang, Yiding Chen, Xiaojin Zhu, and Wen Sun. Robust policy gradient against strong data corruption. In International Conference on Machine Learning, pp. 12391 12401. PMLR, 2021b.
Guanjie Zheng, Fuzheng Zhang, Zihan Zheng, Yang Xiang, Nicholas Jing Yuan, Xing Xie, and Zhenhui Li. DRN: A deep reinforcement learning framework for news recommendation. In Proc. World Wide Web Conference on World Wide Web, WWW, pp. 167-176. ACM, 2018.
A Experiments details and additional experiments
Influence of n² on the AE attack: Rocall that the AE attack can make the agent believe that at cach state some actions are not optimal. such actions are associated with high future rewards, the policy learned by the agent may have even worse performance as it will never take such actions. Following this intuition, the AE attack may have higher efficiency if attacks with policy æt of higher performance compared to random policy. Note that this requires the attacker to have access to policies of high performance of the environment before agent training begins, which is not available to the black-box attack setting considered in the main paper. Therefore, to study the influence of æ on the AE attack, we remove the constraint on attacker's 's knowledge of the environment that here the attacker has access to some high performing policies in the environment. Formally, we consider two types of 1t: (1) expert policy whose performance matches the best policy an efficient learning algorithm can learn (2) medium policy whose performance is in the middle between an expert policy and random policy. With the same setup, we compare the AE attack in the three cases with a random, medium, and expert policy respectively. The results in Fig show that the AE attack with 1t of higher performance usually has much more influence on the attack with random policy in most learning scenarios.
Influence of r on attack's efficiency: Here we study the effect of the hyperparameter r on the efficiency of our attacks. Recall that for AE or AI attack with a policy nt, a reward penalty of A will be applied if the agent selocts an action at state with distance to rt(s) less than or greater than r respectively. From Theorem 5.5 under the efficient learning algorithm assumption, we know that with a sufficient value of A, the efficiency of the attack V satisfies V S maxx;.D(r.)')==>>>>>>>> VM So if the value of decreases, the set of policies satisfy т : (,, æ!) = L will increase, then the value of V will also increase, making the attack less efficient. Similarly, from theorem 5.7 the value of V for the AT attack satisfies V & max ( VM
14

---

Published in Transactions on Machine Learning Research (07 (07/2023)
None
AE
-
AE(2)
-+- AE(3)
MauntainCar--O-ddal
Acrobal-vl-duel
Hopper-v3-oe
Walker2d-v2-dd
3500
4500
Deet Leened Rolcy Rolic V0i0e
-120
-100
3300
2300
2500
3000
-200
-150
2300
-20
1000
-180
500
1000
0.005 6.020
6.100
6.005
0.000
0.010
0.100
0.001
0.010
0.200
0.00000 0020
0.0050
0.0100
Comuuced Snaps
Comuppod Steps
Comrggted C/T
Comupted staps
Mo Mo.nnaiinCar-v-ooo
Acrobat-vlddubble
Hopper-v3ttd3
Walker2d-v2 v2-serddd222ac
-100
-100
45000
Dest Leareed Polky VeMe
-120
-200
2500
4000
2000
3500
-150
1500
2000
5000
-100
-400
300
2100
-500
0.015
0.000
0.040
0.100
5.005
0.020
0.040
0.100
0.001
0.005
0.010
0.020
0.00000.000
0000
0,0020
0.0000
Comupptd Shops CIT
Comupned Steas
Comppnee Stope CIT
Comppted Steps
Figure 4: Comparison belween the AE attacks with of of different performances. H² is a random policy 'A,', medium policy in 'AE(2)', and expert policy in *AE(3)
Then if is increased, the set of policies satisfy (T, T!) will increase, the value of V will increase. Note that the above statements of r is extremely small (close to 0) or large (close to 1), this assumption may break so we only test the value of r in relatively moderate range. We test in example case that learns in the Hopper environment with TD3 algorithm. The value A is set to be 25, and there is no hard limit on C. The results in Fig verify the above statement in the example learning scenarios.
based on the assumption of the efficient learning algorithm. If the value
AE
AE(2)
AE(3)
AI
Hopper-v3-od3
Happar-v3-td3
3000
200
Roward
2500
150
2000
Dest
1500
500
Figure 5: Influence of r on different attack methods
Influence of E on attack's efficiency Recall in the experiments, to make the setting more realistic, we consider an additional constraint on the altack where its total amount of perturbation for each episode is no greater than E. Here we study what is the influence E on the efficiency of the attack experimentally. We test two example environments where the agent learns in Acrobot and Mountaincar environments with dueling DQN algorithms. The parameters and hard limits on the attack are to be the same as in Table except for the value of E. The results in Fig show that unless the value of E is too small, e.g, when
15

---

Published in Transactions on Machine Learning Research (07 (07/2023)
E is greater than the per-episode net-reward range considered in Section the efficiency V does not
change much for different values of E.
Al ......*
AE
Acrobot-v2 duel
MountainCarwO--ue
-100
-125
-140
BeSt Loareed Reward
-550
-175
-160
-200
-170
-180
-190
-275
Episode Corruption
Epr-eee Corruption
Figure 6: Influence of E. the efficiency of the attack
Detailed parameters used in the table: The hyper-parameterd for the learning algorithms can be found in the codes. The parameters for the setup of the experiments are given in Table 1 In Table 2 We provide the value of Vinis Vmaxs and Lmax for each environment we use to determine the constraints on the attack. These values are given by either the setup of the environment or empirical estimation. For example, in MorvtainCar-vO, Lmax 200 and Vmmi 200 are given by the setup of the environment directly, as an episode will be terminated after 200 steps, and the reward is -1 for each step. Vmax - 100 is empirically estimated by the highest reward given by the best policy learned by the most efficient learning algorithm.
Table 1: Parameters for experiments
ENVIRONMENT
T
B
E'
r(AE) r(AI)
CARTPOLE
80000
500
LUNARLANDER
120000
4
800
MOUNTAINCAR
80000
2.5
200
ACROBOT
80000
4
500
HALFCHEETAH
600000
42
6300
1.5
HOPPER
600000
25
2500
2
1.1
WALKER2D
600000
25
2500
2.2
1.5
SWIMMER
600000
0.8
80
2.2
1.0
Table 2: Values used to determine the constraints on attack
ENVIRONMENT
Tanax
Vnax
Vnin
Vmax
Vinin
Vuna Vunn
CARTPOLE
500
500
500
LUNARLANDER
1000
200
-1000
1200
1.2
MOUNTAINCAR
200
-100
-200
100
ACROBOT
500
-100
-500
400
0.8
HALFCHEETAH
1000
12000
12000
HOPPER
1000
4000
4000
4
WALKER2D
1000
5000
5000
SWIMMER
1000
120
120
0.12
16

---

Published in Transactions on Machine Learning Research (07 (203))
Table 3: The values in the table are the variance of the performance of the best learned policy over 10 runs in identical scttings. The values in the brackets are the corresponding average value that is reported in figure 1
Environmeet-Leerninng algorithm-Attack
0.001
C 0.005
C 0.01
C = 0.02
Hopper-sac-Ui UR
106(3468)
114 (3414)
296(3355)
90(3-192
Hopper-sac-AE
125 (3163)
165 (3335)
1131 (2220)
113 (55)
Hopper-sac-Al
107 (3397)
(1(3889)
1118(2224)
(28(1)01)
Hopper-td3-UDD
147 (3580)
212(3524)
215(3482)
1032(3021)
Hopper-td3-AB
133 (3443)
(95(2845)
286()59)
49(23)
Hopper-td3-Al
(3452)
860(3072)
206(963)
690(1501)
B Proof for theorems and lemmas
Proof for Theorem 5.1 By the definition of the attack, we have B = (A]. C== p. T. The policy value of a policy π under the adversarial environment constructed by the AE attack with A, r and at satisfies: V VM= - A- Then in the adversarial environment, an e-optimal policy satisfies Vi - L. 2 V*- -E
where V'- = max; -L
Let be the event that the agent learns an e-optimal policy in the adversarial environment. When G is true, the performance on the true environment of the policy Icarned by the agent is bound by max V.VT -A--- VMM- When G is false, the performance is bound by V* Combining both cases, we have V S max -:V3.---0 - A-22 VM-
Proof for Theorem 5.2 In the first case, 1 is the same for any policy x. Then for any two policies Ti and n2 the difference between their policy values in the true and adversarial environments are the same VM - VM = M VT Therefore, e-optimal policies are the same in both environments, so under the efficient learning assumption, with probability at least 1 p, the agent will learn a policy whose policy value is at least V Then the value of V is at least (1 - p) (V* -) + Vmin where Vnnn is the minimal performance of a policy in M. So the attack is trivial.
In the second case, the policy value V is monotonic incrcasing or decrcasing with L", and A is negative or positive. For any two policies pij and T2 such that Tं has higher policy value than u2: M V > 0, then in the adversarial environment, 31 has a even higher policy value than πे: VT V > VM VT So the coppimal policies in the adversarial environment are subset of e-optimal policies in the true environment. Then the attack is trivial for the same reason as the above case.
M
Proof for Theorem 5.5
Proof. The policy value of a policy æ under the adversarial environment constructed by the AE attack with A, and n² satisfies: V = VM= - A (I." D,(x,,")) r")). Note that for any policy that far from æt, i... (T, x!) L", its policy value is the same in both true and adversarial environments. If the following is sat- isfied: ya - > (r.))= - -A-LLL"D,,m rt)), then the adversarial optimal policy is the policy with the highest policy value among the policies far from nt: 4x arg m. V Furthermore, any policy that is in the neighborhood of œ is not c-optimal, any e-optimal policy must be far from mt. i.. (!) = 0.
Let G2 be the event where the agent learns an e-optimal policy in the adversarial environment. When G is true, the true performance of the policy learned by the agent is at most max::D, (t,a))<== VM- When G is false, the performance at most V*. By the efficient learning assumption, G is true with probability at least 1 - p, so we have V < (1 11-p) p) max VM + V*.
By the definition of attack, we have B |A].
17

---

Published in Transactions on Machine Learning Research (07/2023)
Let G2 be the event where the agent takes actions with distance to adversarial optimal actions less than ö in average. The adversarial optimal action at state 8 is 4 (*)),, and the attack will not perturb the reward for any action d(a, (s)) > r. When G2 is true, the agent will not take actions that have distance d(a, A f*(s)) > ro times. When ro = (d(= n (s)) - -r), the attack will not apply corruption if an action satisfies d(a, #" *s)) ro, so the attacker needs to apply corruption for at most To A.T many rounds. When G2 is false, the attacker applies corruption for at most T rounds. The probability of G2 to be true is
for more than
at least 1 - P, so the value of C' is bound by C S (1 p)) T P.
Proof for Theorem 5.7
Proof. The policy value of a policy л under the adversarial environment constructed by the AI attack with A, r and ot satisfies: V = VM- - A (T v.). Note that for any policy that is in the neighborhood of n1, ie. ()( = 0, its policy value the same in both true and adversarial envirouments. If the following is satisfied: (+,7)) V - max::D. V A (TT, x!), then the adversarial optimal policy is the policy with the highest policy value among the policies in the neighborhood of w!; ** = arg max m=xx: VM- Furthermore, any policy that is not in the neighborhood of æt is not e-optimal, any e-optimal policy must be in the neighborhood of x i.c (1 r!) 0.
Let G1 be the event where the agent learns an 6-optimal policy in the adversarial environment. When G1 is true, the true performance of the policy learned by the agent is at most is false, the performance at most V*. By the efficient learning assumption, G is true with probability at least 1 - p, so we have V S (1 --pp p) max (mxt)) VM P.
VM- When G
By the definition of attack, we have B = -A/.
Let G2 be the event where the agent takes actions with distance to adversarial optimal actions less than 8 in average. The adversarial optimal action at state s is f (s), and the attack will not perturb the reward for any action d(a, x (s)) < r. When G2 is true, the agent will not take actions that have distance d(a, A +s)) > to for more than 6. T. When ro = ming(r- d(f", nt (s))), the attack will not apply corruption if an action no
satisfies d(a,# A (s)) < ro, so the attacker needs to apply corruption for at most zu T many rounds. When G2 is false, the attacker applies corruption for at most T rounds. The probability of G2 to be true is at least p, so the value of C' is bound by C C
2 TT+
C Comparison to Reward Flipping Attack
Here we analyze and cmpirically examine the performance of heuristic attack that appears to be effective as believed in Zhang el al. (2021b). The strategy of the allack is to change the sign of the true reward at each time. We call such attack as reward flipping attack, and its attack strategy can be formally written as As(s", a²) = - Note that such attack also construct a stationary adversarial reward function, suggesting that it also falls in our 'adversary MDP attack' framework. Under such adversarial MDP M, since all rewards have their signs flipped, we have M - for all policy suggesting that the optimal policy
under M actually has the worst performance under the true environment M. However, the disadvantage of the attack method is that it breaks our second efficient attack principle where the perturbation for the adversarial optimal actions should be limited. The consequence is that it needs to apply corruption at every timestep, resulting in too much requirement on C. We further empirically test the efficiency of the reward flipping attack. The allacker cannot apply corruption when it runs out of budget on total corruption steps C, and we do not assume any constraint on B. We consider environment Hopper and HalfCheetah and set C 0.01 as considered in our experiments while the remaining parameters are unchanged. Our results show that the performance of the reward flipping attack is comparable the baseline UR attack as shown in the table below, suggesting that the reward flipping attack is not efficient.
18

---

Published in Transactions on Machine Learning Research (07 (07/2023)
Table 4: Performance of reward flipping attack. The values in the table are the performance of the best policy ever learned by the learning algorithm, which is the same the y axis of our main experiment results in figure !
Buvironment-Learnin algorithm
Reward flipping attack
UR attack
No attack
Hopper-td3
3157
3482
3502
Hopper-sac
3521
3355
3496
HallChootah-ddigg
7463
6622
9341
HallChoetab-td3
7603
7694
9610
D Comparison to VA2C-P attack
Here we compare the effectiveness our AE attack and the most 'black box' version of VA2C-P attack proposed in [Sun et al.] (2020) which knows the learning algorithm but does not know the parameters in its model. Note that the constraints for the two attacks different in the two papers. To make sure that are not underestimating the effectiveness of the VA2C-P attack, we let both attacks work under the same constraints used in Sun et al. (2020). The constraints here are characterized by two parameters K and e. The training process is separated into K batches of steps, and the attacker is allowed to corrupt no more than C' out of training batches. In each training batch with t time steps, let ör = (ōr1,...,
be the vt I We modify the AE attack accordingly work with such constraints. More specifically, the attack strategy is unchanged when applying corruption will not break the constraints, and we forbid the attack to apply corruption if doing so will break the constraints. To avoid anything that could cause decrease in efficiency of VA2C-P attack, we do not modify any code related to training and attacking provided by Sun et al. 2020 and implement our atlack method in their code.
injected reward corruption at each time step, then the corruption should satisfy |
Since VA2C-P has more limitations than AE attack, we only consider the scenarios where both attack are applicable. As an example, we choose Swimmer as the environment and PPO as the learning algorithm. Here we use the metric in [Snn al. (020) to measure the performance of the attack. More specifically, we measure the average reward per episode collected by the learning agent through the whole training process. We set K = 1, 1, and the length of training to be 600 episodes where each episode consists of 1000 steps. The results for different attacks are shown in table Each result is the average of 10 repeated experiment, and it is clear that our attack is much more efficient.
Table 5: Comparison between VA2C-P and AE attack
clean
VA2C-P
AE
AE-(2)
AE-(3)
30.07
25.49
14.75
7.08
-2.16
We also notice that our AE attack computes faster than VA2C-P attack. To compute the attack for 600 training episodes in the experiment, our AE attack takes 135.7 seconds, while the VA2C-P black box attack takes 7049.5 seconds. In this case, the AE attack computes 52 times faster than VA2C-P attack.
One may notice that learning efficiency of PPO algorithm here is not as good as what we show in Figure This is due to different implementation of the same algorithm in our work and Sun et al. (2020). It is a known issue that difference in implementations can lead to very different learning results Henderson et al. (0018. As mentioned before, we build our learning algorithms based on spinning up documents AAciam (008), and the learning performance of our learning algorithms match the results shown in the spinning up documents.
19

---

/* Environment generates the true feedback for Published in Transactions on Machine Learning Research (07/2023)
E Framework of Online Reinforcement Learning under Reward Poisoning Attack
Here we present detailed framework of the training process of learning agent interacting with an envi- Ho) under reward poisoning attack considered in our work. ronment M = P,,
Inputs
Environment M (8, (S,A,P, R. no), Training steps T
Initialize: t=0 while / /< T do
/* The training starts at time step = 0 */
s ~ 44 E' = False
/* A training episode is initialized at state s */ /* Environment termination signal has to be False at the beginning of
each episode */
while == Palse ALST do
Agent draws an action a' such as PPO, to determine the action to draw. */ r' RRs's aa), st+1 ~ P(s',a');
Agent can run any reinforcement learning algorithm,
instant reward and next state */
Adversary determines reward perturbation A Agent observes (s' 's',''r''+ A'', if Termination condition reached then
E Truc; /* Environment checks if the termination condition is reached for this episode. The termination condition can be whether the maximum training steps in episode is reached, the agent enters state sh+1 that satifies certain conditions. */
end end end
Our AE and AI allacks define the stralegy to determine the reward perturbation A Definition 5.3 5.6
F
Additional Discussion
Potential defense for DRL against reward poisoning attacks: Our work as well as previous RL attack works Rakhsha et al. (2020) show that a vulnerable learning algorithm fails to explore the actions of high interest enough times, resulting low learning performance. So correspondingly, one idea for building robust algorithms is to make the exploration robust to the attack. For example, for the exploration idea following optimality in the face of uncertainty principle (e.g, UCB algorithms),the corruption of data can contribute additional uncertainty to the estimation of cach action. By taking the additional uncertainty into account, the exploration strategy can explore the state and actions of high interest for enough times even if there can adversarial attacks. As a result, the learning algorithm can robust against attack. This idea has been applied building robust learning algorithms in tabular MDP settings Wu al. (2021). One can adopt similar idea for building robust DRL algorithms in the future.
How to reduce the requirement For example, one can follow the same idea of the AI attack to make the agent believe some random target actions to be optimal. In addition to decreasing the reward for non-target actions, one can also increase the reward for target actions. This can make the target policy even more appealing to the agent, so it requires policy. Correspondingly, this will also significantly increase
B: One reduce the budget B by using more budget C.
less value of B to influence the performance the requirement on C as the attack needs to corrupt more steps.
20


Reviews:
[{"review_id": "l6F4M3zWuY", "reviewer": "Reviewer_bozW", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n> I found this work well-written and easy to follow. Reward poisoning attack is not well-studied in the literature. The authors first use the uniformly random time attack as a baseline and show its weakness, then they list out the principles of a non-trivial attack. \n> Two main attack frameworks are introduced intuitively. I checked the proofs in the appendix and they seem to be correct.\n> The authors conducted extensive experiments to show the efficacy of the proposed methods.\n\n\nWeakness:\n> I found Assumption 4.3 a bit too strong, especially the claim that both $\\epsilon$ and $\\delta$ <<1. Do the authors have any intuitions or examples for the numerical values of $\\epsilon$ and $\\delta$? Also, the notation of $\\epsilon$ in this assumption overlaps with the $\\epsilon$-greedy, so I think it's better to use another Greek letter here.\n> Both AE and AI attacks are described in definitions, which may cause difficulties in understanding. I think it would be better to have a pseudo-code for how they are implemented in a typical DRL algorithm, for example, PPO. Also, for the theorem 5.5 and 5.7, it seems that $\\min_s\\{ r−d(π^∗(s),π(s)) \\}$ can be a very small number, and thus the upper bound can be very loose.\n> \n> Minor: please refrain from only using color to distinguish curves in Figures 3 and 6, as it is not friendly to readers with color blindness.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors introduce a black box framework for reward poisoning attacks in training time. Within this framework, they develop two specific attacks that manipulate the reward signals in deep RL during a small portion of the training process, leading the agent to learn a suboptimal policy. The authors provide a theoretical analysis to assess the effectiveness of their attack strategy and conduct extensive empirical evaluations. The results obtained indicate that their attacks can effectively undermine the learning capabilities of various popular DRL algorithms.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see the Weakness section above. Specifically, I think more explanation on the values of $\\epsilon$ and $\\delta$ in the assumption, and pseudocode for the algorithms are welcomed.", "broader_impact_concerns": "I don't have concerns about the ethical implications of this work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "WBxfpk8dHY", "reviewer": "Reviewer_bYVw", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\n(1). The attacker considered in this paper has more limited ability compared to prior works. First, the attacker does not know the underlying environment and the algorithm adopted by the learning agent. In this regard, a lot of prior works assume the attacker has access to a simulator of the underlying environment and the learner's algorithm, which allows the attacker to train a good poisoning strategy beforehand and then deploy the strategy in the true learning stage of the RL agent. However, this paper designs attacks that can be used on the fly during the training of an RL agent. Therefore, the attacks are more practical. Second, the paper considered budgeted reward poisoning both in terms of per-step reward perturbation and the attack frequency, which again makes the attack more stealthy in practice. Overall, the constraints on the attacker's ability makes the problem setup closer to a real world attack compared to existing methods.\n\n(2). The paper provided some theoretical analysis on the performance of the attack, although the theoretical results do not look super intriguing to me (as explained later). These theoretical results provided some insights on the attack efficiency.\n\n(3). The paper performed extensive empirical evaluations of the proposed AE and AI attacks. First, we see that the AE and AI attack are indeed very efficient. They require perturbation in less than 20% of training steps, but can significantly reduce the expected cumulative rewards of the learned policy. Second, we see that both AE and AI outperform the baseline random attack strategy. Finally, the paper also provided empirical study on different hyperparameters of attack, e.g., the per-step reward poisoning budget. The results look interesting and convincing.\n\nWeaknesses:\n\n(1). Some definitions are not clear enough. To list a few\n\nThe authors never specified clearly how the attack is performed in each time step. Assume the original reward is r_t. How does the attacker change the reward? Is it r_t+\\Delta_t or r_t-\\Delta_t? The authors seem to have used the symbol \\Delta_t for reward perturbation without introducing it beforehand.\n\nIn Definition 4.1, it's not super clear what the expectation is with respect to. I suppose the expectation is with respect to the randomness in both attack strategy and the learning process. However, this is hidden from the definition.\n\nThe authors argue that Assumption 4.3 is reasonable. However, I think there are technical flaws in this assumption. The learned policy pi_0 is often random due to that the stochasticity in state transition and reward. Therefore, we cannot firmly claim that an agent can always learn an eps-optimal policy. In other words, the assumption 4.3 only holds probabilistically and is not strictly a reasonable assumption. At least the authors need to consider restating the assumption as some high-P event.\n\n(2) While the paper derived interesting theoretical results to analyze the performance of the learned policy under attack, it seems really hard to see how much performance degradation is actually achieved under AE and AI attack. For example, in Theorem 5.5, the authors give an upper bound on V. However, it's not super clear that how far V is from original optimal value V*. Just from the theorem, it seems like V could be equal to V*, in which case the theory does not provide any guarantee in terms of the performance reduction after attack. This makes the theoretical results not super intriguing to me.\n\n(3) In the experiments, the per-step reward poisoning budget seems too high to me. It can be as large as the maximum reward gap over all possible actions. This is almost like the attacker can arbitrarily change reward within the reward space.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studied reward poisoning attacks in reinforcement learning. The authors considered the black-box attack setting, where the attacker has no information about the learner and underlying environment. Two attack strategies are proposed - Action Evasion (AE) and Action Inducing (AI) attack. The AE attack tries to mislead the learning agent to believe that the optimal action in the clean environment is not optimal, thus the agent will be refrained from selecting the optimal action under attack. In contrast, the AI attack encourages the learning agent to behave like a random policy, taking random actions in every state, which results in a low-performance learned policy. The paper performed empirical study of AE and AI attack on diverse RL environments, and showed that both attacks can significantly reduce the performance of the learned policy. The authors also showed that AE and AI outperform the baseline random attack strategy.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "(1). Please fix some definitions and notation issues. Please formally introduce the threat model and introduce symbols before using them,\n\n(2). Consider improving the current theoretical results to give a better characterization on the performance drop induced by the AE and AI attack.\n\n(3). It seems like reducing the per-step reward poisoning budget B causes the attack performance to drop quickly. How can we make the attack more effective subject to small B? Please provide some discussions on that.", "broader_impact_concerns": "The paper does not have any ethical concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "WKkA81E5jZ", "reviewer": "Reviewer_eEao", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The paper proposes a new attack framework with two attacks. The techniques are solid with certain theoretical analyses.\n2. The paper has conducted an extensive empirical evaluation on different RL environments. \n3. The paper is overall well structured and written.\n\nWeaknesses:\n1. The reward poisoning attack against RL has been extensively studied in the existing literature\n2. The paper lacks a discussion or evaluation of potential defense\n\n ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a new reward poisoning attack against online RL. It proposes a new attack framework under certain assumptions. Under this framework, it proposes two attacks. The effectiveness of the proposed attacks are justified through both theoretical analysis and empirical evaluation. \n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I would suggest the authors discuss some potential counter measures against their attacks. ", "broader_impact_concerns": "Not applied.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes two reward-poisoning attacks strategies in a general RL setting. Reviewers agree the work has novel and substantial contributions, with both theoretical and empirical supports. The revised version satisfactorily addresses major questions raised in the initial reviews, such as assumption 4.3 and a few places for greater clarity. The AE agrees with the reviewers, and has a few more suggestions:

1. The authors promised to change the line types in Figures 3 and 6. But the revised version seems to have the same plots. Can you fix them?

2. The paper highlights "deep" RL throughout. I find it puzzling, because the only connection between deep RL and this work is that the authors consider non-tabular RL settings. If so, why not just call it general RL, or RL with function approximation? Calling non-tabular settings as "deep" is a misnomer IMHO.

3. (Minor) Does it make (mathematical) sense to change equality constraints to inequality ones in (2), as well as other parts?
Decision: Accept (poster)