Vulnerability-Aware Poisoning Mechanism for Online RL with Unknown Dynamics
Authors: Yanchao Sun
Da Huo
Furong Huang
Venue: ICLR 2021 Poster (2021)
Keywords: poisoning attack
policy gradient
vulnerability of RL
deep RL

Abstract: Poisoning attacks on Reinforcement Learning (RL) systems could take advantage of RL algorithm’s vulnerabilities and cause failure of the learning. However, prior works on poisoning RL usually either unrealistically assume the attacker knows the underlying Markov Decision Process (MDP), or directly apply the poisoning methods in supervised learning to RL. In this work, we build a generic poisoning framework for online RL via a comprehensive investigation of heterogeneous poisoning models in RL. Without any prior knowledge of the MDP, we propose a strategic poisoning algorithm called Vulnerability-Aware Adversarial Critic Poison (VA2C-P), which works for on-policy deep RL agents, closing the gap that no poisoning method exists for policy-based RL agents. VA2C-P uses a novel metric, stability radius in RL, that measures the vulnerability of RL algorithms. Experiments on multiple deep RL agents and multiple environments show that our poisoning algorithm successfully prevents agents from learning a good policy or teaches the agents to converge to a target policy, with a limited attacking budget.

Published as a conference paper at ICLR 2021
VULNERABILITY-WAAR POISONING MECHANISM FOR ONLINE RL WITH UNKNOWN DYNAMICS
Yanchao Sun'
Da Huo
Furong Huang
1.3 Department of Computer Science, University of Maryland, College Park, MD 20742, USA
2 Shanghai Jiao Tong University, China ycse edu, 2s jttuhucaas jtu. edu. en, "furongh@umd.cn
ABSTRACT
Poisoning attacks on Reinforcement Learning (RL) systems could take advantage of RL algorithm's vulnerabilities and cause failure of the learning. However, prior works on poisoming RL usually either unrealistically assume the attacker knows the underlying Markov Decision Process (MDP), or directly apply the poisoning methods in supervised learning to RL. In this work, we build a generic poison- ing framework for online RL via a comprehensive investigation of heterogeneous poisoning models in RL. Without any prior knowledge of the MDP, we propose a strategic poisoning algorithm called Vulnerability-Awan
Adversarial Critic Poi- (VA2C-P), which works for on-policy deep RL agents, closing the gap that no poisoning method exists for policy-based RL agents. VA2C-P uses a novel metric, stability radius in RI., that measures the vulnerability of RI algorithms. Experiments on multiple deep RI. agents and multiple environments show that our poisoning algorithm successfully prevents agents from learning a good policy or teaches the agents to converge to a target policy, with a limited attacking budget.
INTRODUCTION
Although reinforcement learning (RL), especially deep RL, has been successfully applied in various fields, the security RL techniques against adversarial attacks is not yet well understood. In real- world scenarios, including high-stakes ones such as autonomous driving vehicles and healthcare systems, bad decision may lead to a tragic outcome. Should we trust the decision made by an RL agent? How easy is it for adversary mislead the agent? These questions crucial to ask before deploying RL techniques in many applications.
In this paper, we focus poisoning attacks, which occur during the training and influence the learned policy. Since training RL is known to be very sample-consuming, one might have to con- stantly interact with the environment to collect data, which opens up lot of opportunities for an attacker to poison the training samples collected. Therefore, understanding poisoning mechanisms and studying the vulnerabilities in RL are erucial to provide guidance for defense methods. How- ever, existing works on adversarial attacks in RL mainly study the test-time evasion attacks (Chen al. 2019) where the attacker crafts adversarial inputs fool well-trained policy, but does not cause any change to the policy itself. Motivated by the importance of understanding RL security in the training process and the scarcity of relevant literature, this paper, we investigate how to poison RL agents and how to characterize the vulnerability of deep RL algorithms.
In general, RL is an "online" process: an agent rolls out experience from the environment with its current policy, and uses the experience to improve its policy, then uses the new policy to roll out new experience, etc. Poisoning in online RI. is significantly different from poisoning in classic supervised learning (SL), even online SL, and is more difficult due to the following challenges.
Challenge I Future Data Unavailable in Online RL. Poisoning approaches in SL et al. 2017 Wang & Chaudhuri] 2018 usually require the access to the whole training dataset, so the attacker can decide the optimal poisoning strategy before the learning starts. However, in online RL, the training data (trajectories) are generated by the agent while it is learning. Although the optimal poison should work in the long run, the attacker can only access and change the data in the current iteration, since the future data not yet generated.

---

Published as a conference paper at ICLR 2021
Challenge II Data Samples No Longer i.i.d. It well-known that in RL, data samples (state-action transitions) are longer i..d., which makes learn- ing challenging, since we should consider the long- term reward rather than the immediate result. How-
0
0.1l
1000
S Agir
$2
$10
Figure 1: An example difficult poisoning.
ever, we notice that data samples being not i..d. also makes poisoning attacks challenging, For example, an attacker wants to reduce the agent's total reward in task shown as Figure | at state $1, the attacker finds that a1 is less rewarding than do: if the attacker only looks at the immediate reward, he will lure the agent into choosing d1. However, following 01 finally leads the agent to $10 which has a much higher reward.
Challenge III - Unknown Dynamics of Environment. Although Challenge and II can be partially addressed by predicting the future trajectories steps, it requires prior knowledge on the dynam- ies of the underlying MDP. Many existing poisoning RL, works (Rakhsha et al. 2020) Ma et al.) 2019) assume the attacker has perfect knowledge of the MDP, then compute the optimal poison- ing. However, in many real-world environments, knowing the dynamics of the MDP is difficult. Although the attacker could potentially interact with the environment to build an estimate of the en- vironment model, the cost of interacting with the enviromment could be unrealistically high, market making (Spooner et al., 2018) for instance. In this paper, we study more realistic scenario where the attacker does not know the underlying dynamics of MDP, and can not directly interact with the environment, either. Thus, the attacker learns the environment only based on the agent's 's experience.
In this paper, we systematically investigate poisoning in RL by considering all the aforementioned RL-specific challenges. Previous works either do not address any of the challenges or only address some of them. [Behzadan & Munir (2017) achieve policy induction attacks for deep Q networks (DQN). However, they treat output actions of DQN similarly labels in SL, and do not consider Challenge II that the current action will influence future interactions. [a et al. (2019) propose a poisoning attack for model-based RI, but they suppose the agent learns from batch of given data, not considering Challenge I. Rakhsha et al.) (2020) study poisoning for online RI., but they require perfect knowledge of the MDP dynamics, which is unrealistic as stated in Challenge III.
Summary of Contributions. (1) We propose practical poisoning algorithm called Vulnerability- Aware Adversarial Critic Poison (VA2C-P) that works for deep policy gradient learners without any prior knowledge of the environment. To the best of our knowledge, VA2C-P is the first practical (2) We introduce a novel metric, called stability radius, characterize the stability of RL. algorithms, measuring and comparing the vulner- abilities of RI. algorithms in different scenarios. (3) We conduct a series of experiments for various environments and state-of-the-ard deep policy-based RI. algorithms, which demonstrates RI. agents' vulnerabilitiis to even weaker attackers with limited knowledge and attack budget.
algorithu that poisons policy-based deep RL methods.
2 RELATED WORK
The main focus of this paper is on poisoning RL, an emerging area in the past few years. We survey related works of adversarial attacks in SL and evasion attacks in RL in Appendix A as they out of the scope of this paper.
Targeted Poisoning Attacks for RL. Most RL poisoning researches work on targeted poisoning, also called policy teaching, where the attacker leads the agent to learn a pre-defined target policy. Policy teaching can be achieved by manipulating the rewards (Zhang & Parkes 2008 Zhang al. 2009] or dynamics (Rakhsha et al. (020) of the MDP. However, they require the attackers to not only have prior knowledge the environments (e.g.. the dynamics of the MDP), but also have the ability to alter the environment (e.g. change the transition probabilities), which are often unrealistic or difficult in practice.
Poisoning RL with Omniscient Attackers. Most guaranteed poisoning RL literature (Rakhsha cet al. 2020; Ma et al. 2019) assume omniscient attackers, who not only know the learner's model, but also know the underlying MDP. However, as motivated in the introduction, the underlying MDP is usually either unknown or too complex in practice. Some works poison RL learners by changing the reward signals sent from the environment to the agent. For example, Ma et al. (201)) introduce a policy teaching framework for batch-learning model- agents; Huang & Zhu (2019) propose reward-poisoning attack model, and provide convergence analysis for Q-learning: Zhang et al.
2

---

Published as a conference paper at ICLR 2021
2020b) present an adaptive reward poisoning method for Q-learning (while it also extends to DQN) and analyze the safety thresholds RL; these papers all assume the attacker knows not only the models of the agent, but also the parameters of the underlying MDP, which could be possible in tabular MDP, but hard to realize in large environments and modern deep RI. systems.
On the contrary, we consider non-ommiscient attackers who do not know the underlying MDP or environment in this paper. The non-omniscient attackers can be further divided into two categories: white-box attackers, who know the learner's model//arameters, and black-box attackers, who do not know the learner's model/parameters. They both tap the interactions between the learner and the environment.
Black-box Poisoning for Value-based Learners. Although there are many successful black-box evasion approaches (Xinghua et al., 2020, Inkawhich et al. 2020), black-box poisoning in RL is rare. There is a black-box attacking method for a value-based learner (DQN) proposed by |Behzadan & Munir (017). which does not require the attacker know the learner's model or the underlying MDP. In this work, the attacker induces the DQN agent to output the target action by perturbing the state with Fast Gradient Sign Method (FGSM) (Goodfellow et al. 2015) in every step. However, the data-correlation problem of RL (Challenge II) is not considered, and FGSM attack does not work for policy-based methods due to their high stochasticity, as we show in experiments.
In this paper, propose new poisoning algorithm for posicy-based deep RL agents, which can achieve both non-targeted and targeted attacks. We do not require any prior knowledge of the environment. And our algorithm works not only when the attacker knows the learner's model (white- box), but also when the leaner's model is hidden (black-box).
3 PROBLEM FORMULATION FOR POISONING ONLINE RL
3.1 NOTATIONS AND PRELIMINARIES
In RI., an agent interacts with the environment by taking actions, observing states and receiving rewards. The environment is modeled by a Markov Decision Process (MDP), which is denoted by tuple M (S, A. P, R, 7, p)), where S is the state space. A is the action space, P is the transition kernel, R the reward function, 7 E (0, 1) is the discount factor, and μu is the initial generated by policy is sequence $1, a1, V1, 82, "2. where $1 ~ μa, ag ~ (a)ss)) $141 ~ P(s|st, a,) and r = R(st, at). The goal of an RL agent is to find an optimal policy X² that maximizes the expected rotal rewards 17, which is defined as (TT)) = Ee---rrirr [r()) = ".j,,,,.""u,,,,,,
state distribution. A trajectory т
We overhead check sign the attacker perturbs a reward rt. then the poisoned reward is denoted as iz. If a policy π is updated with poisoned observation, then it is denoted as म.
variable denote that the variable is poisoned. For example, if
3.2 THE PROCEDURE ONLINE LEARNING AND POISONING
Procedure of Online Learning. We consider a classical online policy-based RL setting, where the learner iteratively updates its policy æ parametrized by 0, through K iterations with the environment. For notation simplicity, we omit 0 and use T& to denote THl, the learner's policy at iteration k. The online learning process is described as below.
21
Figure 2: Online poisoning llaaning process.
At iteration k = 1,... K, (1) The agent uses the current policy mi to roll out observation O₂ = (Of, Og. OE) from envi- OF [ri, r2, .. are respectively the sequence of states, actions and rewards generated at iteration k.
1, ronment Mr. where O 52, -- 0f = [al,,a,..... az,.
(2) The agent updates its policy parameters 0 with its algorithm f. Most posecy-based algorithms perform on-policy updating, i.e., update policy only by the current observation Ok- The on-policy update can be then formalized as T&+1 = f Ox) s argmax, Ty. Ok), where is an objective function defined by algorithm e.g., the expected total reward 17(T).
3

---

Published as a conference paper at ICLR 2021
Procedure of Online Poisoning. A poisoning attacker influences the learner in the training process by perturbing the training data. In SL, the training data consists of features and labels, and the attacker poisons the training data before the learning starts. However, the training data in RL is the trajectories a learner rolls out from the environment, i.e., observation O = (O+, Oa O*). At iteration k, the attacker eavesdrops on the interaction between the learner and the environment, obtains the observation Oz. and may poison it into OR, then send O2 to the learner before policy updating. Procedure 2 in Appendix B illustrates how the online game goes between the learner and the attacker. Figure 2
visualizes this online learning-poisonigg procedure, where we can see that learning and poisoning are convoluted and inter-dependent.
3.3
UNIFIED FORMULATION FOR POISONING ONLINE POLICY-BASED RL.
3.3.1 ATTACKER's s POISON AIM
As defined in Section 3.T] the observation is collection of trajectories, consisting of the observed states O², the executed actions Oa or the received rewards O", When poisoning the observation, the attacker may only focus on the states, or on the actions, or on the rewards. We call the quantity being altered the poison aim of the attacker, denoted by D E {O*, On "") For example, D O* means the attacker chooses to attack the states.
Distinguishing different poison aims is important, since in real- world applications different poison aims correspond to different behaviors of the attacker. For example, in an RL-based recommender system, the RL agent recommends an item (i.e., an action) for user (i.e., state), and the user may or may not choose to click on the recommended item (i.e., a reward). An adversary might manipulate the reward (poisoning D O"), e.g., blocking the user's click from the RL agent or creating a fake click. An adversary might also alter the state (poisoning DD = O*), e.g., raising a teenager user's age which could result in inappropriate recommendations. An adversary might also change the action (poisoning D = O²), e.g., inserting a fake recommendation into the agent's s list of recommendations. Under different scenarios, the feasibility of poisoning different aims may vary.
Most existing works on poisoning RL only solve one type of poison aim. Zhang et al. (2020b); Huang & Zhu (2019) propose to poison rewards, Behzadan Munir (2017) assume the attacker poison the states. However, in our paper, we provide a general solution for any of the poison aims to satisfy the needs in different scenarios. Our proposed method also supports a "hybrid" poison aim, where the attacker could switch aims at different iterations, as discussed in Section
3.3.2 A POISONING FRAMEWORK FOR RL
We focus on proposing a poisoning mechanism for the above challenging online learning scenario. We first formalize the poisoning attacking at iteration k as a sequential bilevel optimization problem Q and explain the details of the problem in the remaining of this section.
in Problem
Σx م=ر XyLA(T)+11
argmin Da. .D
((a) attacker's weighted loss) (Q)
s.t.
お = argmax, (,, (,, D,D)) SiSK
((b) imitate the learner)
K Σj11 1(D, # *D,) SC
((c) limited-budget)
U(D,, D,) s e. v
((d) limited-power)
(a) Attacker's Weighted Loss. (#) measures the attacker's loss w.r.t. poisoned policy As the definition of poisoning implies, the attacker influences or misleads the learner's policy. ARa are the weights of future attacker losses, controlling how much the attacker value the poisoning results in different iterations. The goal of the attacker is either (1) non-targeted poisoning, which minimizes the expected total rewards of the learner, i.e., TA 7/(*)), (2) targeted poisoning, which induces the learner to learn a pre-defined target policy, i.e., LA = distance (it, π where distance(f ft, r²) can be any distance measure between learned policy and a target policy न. Note that the targeted
'In this paper, we assume the attacker poisons the observation which is the most universal setting in practice. Appendix [ extends our problem formulation to more general case where the attacker can change the underlying MDP.
4

---

Published as a conference paper at ICLR 2021
poisoning objective can usually be directly computed with a prior target policy, while non-targeted objective, which is the reverse of the learner's 's objective. With- out any prior knowledge of the environment, non-targeted poisoning is usually more difficult, as the attacker needs to first learn "what is the worst way" (which is as difficult as a learning problem targeted poisoning problem, assuming leading an agent to different policies is roughly equally challenging). However, most existing poisoning work focus on targeted poisoning, which requires the attacker know pre-defined target policy. Thus in this paper, we make more efforts to solve the poisoning problem, which may deprave the policy without any prior knowledge.
poisoning has a reeardd-mnimiize
by RL agent) and then lead the learner to that way (which is as difficult
(b) Imitate the Policy-Base Learner. To confidently mislead a learner, the attacker needs to predict how the learner will behave under the poison, which can be achieved by imitating the learner using the learner's 's observation. More specifically, at the j-th iteration, the attacker estimates the learner's s policy to be á.. called imitating policy. Then, the attacker predicts the next-policy # under poisoned observation, based on the learnrr's update rule argmax,.JJaa Tj, O₂ Dj)D)), where 'D E {O+, Oa, O stands for the poison aim of the poisoning, OID denotes that O is poisoned into Ô given that poison aim D is poisoned into D. However, the imitating policy á may or may not be the same the actual learner's policy, depending
the attacker's knowledge. As introduced in Section 2 we deal with both white-box and black-box attackers, and both of them do not know the environment M. white-box attacker knows the current and past observations O I.R.. the learner's algorithm / and policy म, so it can directly copy the policy R, = Ty. Vj. A black-box attacker knows the current and past observations O1 but does not know the learner's policy æ.. In this case, the attacker has to estimate π at every iteration. Section 4.3 states how to guess т.
(c,d) Limited-budger and Limited-power. In practice, the ability of an attacker is usually restricted by some constraints. For the online poisoning problem, we consider attacker's constraints in two forms: (1) (attack budget C`) the total number of iterations that the attacker could poison does not exceed C; (2) (attack power e) in one iteration, the total change U D&) between Dj and Dr can not be larger than e. Attack power controls the amount of perturbation, as commonly used the adversarial learning literature. Attack budget considers the frequency of attack, which is similar to the constraint studied by Wang & Chaudhuri (2018).
Problem Q is generic formulation, covering variety of poisoning models, and specifies the best poison an attacker can execute. However, directly solving Problem (Q) is prohibitive, as (1) the future observations OR+1.K unknown when poisoning the k-th iteration, as the attacker has no knowledge of the underlying MDP. (2) the limited budget constraint is analogous to 4 reg- ularization, which is generally NP-hard (Nguyen et al., 2019]; and (3) minimizing attacker's loss while maximizing learner's gain is non-convex minimax optimization, which a complex prob- lem (Perolat et al., 2015).
In spite of the above difficulties, we introduce a practical method to approximately and effectively solve Problem (Q) in Section 4
VA2C-P: POISON POLICY GRADIENT LEARNERS
In this section, we propose a practical and efficient poisoning algorithm called Vulnerability-Awan Adversarial Critic Poison (VA2C-P) for policy gradient learners. Without loss of generality, we assume the loss weights > = for all j 1,...,,.......... K.
Main Idea. As discussed in Section 3.3 Problem Q is difficult mainly because of the unknown future observations and the limited budget constraint. In other words, is hard to exactly determine (1) what kind of attack benefits the future the most, and (2) which iterations are worth attacking the most. Thus, we propose to break Problem OQ) into two decisions: when to attack, and how to attack. The "when to attack" decision allocates the limited budget to iterations which are more likely to be influenced by the attacker, and the "how to attack" decision utilizes limited power to minimize the attacker's loss. We introduce two mechanisms of VA2C-P, vulnerabilit-awwreness and adversarial critic, to make these two decisions respectively.
2 There are many choices of U(.)). For example, the total effort w.r.t O² ppoiiiion can be the average l distance hetween any poisoned and unpoisoned state in O² and O+
5

---

Published as a conference paper at ICLR 2021
4.1 DECISION 1: WHEN TO ATTACK- VULNERABILITY-AWANE
To answer the question of when to attack, we identify the iterations under which the learner's policy gets more depraved by the same level of attack power. Inspired by the notion of stability in learning theory, which measures how a machine learning algorithm changes due to a small perturbation of the input data, we formally investigate the stability of an RL algorithm, which is the first attempt in the existing literature to the best of our knowledge.
Stability of RL Algorithms. We first focus on single update process of an algorithm f. An update o' = f O) is stable if a Limited-power poisoning attack does not cause any difference on the output policy x'. That is, the learning algorithm produces the same result regardless of the presence of the poison. More formally, we define the concept of stability radius of one update in Definition
Definition (Stability Radius of One Update). F For the update of an RL algorithm x' = f(z O), with any poison aim D, the ö-stability radius of the update is defined as the minimum poison power needed to cause ó change in policy (called spolicy-diccrppnccy
68,D(f. n, O) inf s.t. (D) S aand d (T' [r'||=]] > 8, where #' = f Ö1D),, (I)
Policy discrepancy dmaa (T: [|x2]] max, af (1)))]] (s)] where d[-I]-] could be any measure of distribution distance.
Remarks. (1) The one-update stability radius is w.I.t the algorithm f. the old policy म, the clean
observation O and the poison aim D. (2) Poison with power under Φs. k. O) will not cause
the policy distributions to change more than 8. (3) As shown by Proposition P in Appendix D.I poison with power under @f, (f π, O) will not make the policy value drop more than 0 (
7) ma 2 (A, (s), where A is the advantage function, i... (s, (s, (s).
Stability radius measures the minimal effort needed to make the poisoned next- next-policy H' notably different from the clean next-policy n' which the learner will get if no poison is applied. Assuming max.,a (s, does not drastically change for the learner's policy during training, then an attack that causes higher policy discrepancy between n' and could cause more drop of the policy value. Therefore, the idea of vulnerability-wwar attack is to estimate the vulnerability of each update and attack the most vulnerable ones. More specifically, if the attacker finds an e-powered attack results in policy discrepancy larger than some threshold 5, then it can conclude (s æ, O) S and the current update is relatively vulnerable. In practice, we have the fixed budget C' instead of 5, so we perform the vulnerability check in an adaptive way: attacking the C iterations where e-powered attacks can trigger the highest policy discrepancies. Section introduces an algorithm to realize this idea.
4.2 DECISION 2: HOW TO ATTACK- ADVERSARIAL CRITIC
constraint, now we turn our attention to minimizing the attacker's loss while satisfying the limited-power constraint. If the attacker has already decided to poison the k-th iteration due to its high vulnerability, then the decision of how to attack should be made before the learner uses the observation to update the policy. We relax the original Problem (Q) into Problem (P) as below.
Since "when to attack" decision tackles the
argmin
IA
8.t.
#*+1 = argmax, J[T, (T, Txi Öz D2))
Da) SE
Compared with Problem
(Q). Problem (P) does not consider future losses, which require the unavail- able future observations. Instead, Problem (P) finds a greedy attack DD to minimize the loss of the immediate next iteration. The solution to Problem (P) is always feasible to Problem (Q) although
might not be optimal. Appendix F.2 provides details about the optimality of Problem QQ)
In practice, it also challenging to estimate L A (it) For targeted attacking, L = distance (#, x is directly computable with a properly defined distance metric, but for non-targeted attacking, the loss
In order to characterize the stability and robustness of RI. algorithms in principled way. provide more measures for the vulnerability of RL. in both training time and test time. See Appendix 1.2b for details.
6

---

Published as a conference paper at ICLR 2021
LA (f) not be directly computed, since स is not the behavior policy. Although can importance sampling to evaluate f)())) with the current trajectories generated by the learner's 's policy,
i... [B 1 Fe (+) ( (T)],, it may suffer from high variance (Schulman al. 2015b) when there few trajectories. To solve this challenge, we introduce another mechanism, adversarial critic.
Adversarial Critic. Under poisoning. the value network (if any) held by the learner usually fails fit the correct value of its policy, since does not observe the real trajectories generated by its policy. However, the attacker observes the real trajectories before poisoning, and is able to learn the real values make the attacking stronger. Inspired by the Actor-Critic method, we propose to let the attacker learn value function (network) VW with observations of the learner, i.e., the attacker learns a critic of the learner's current policy x. Then the attacker can use V. to design poisoned observations, directing the learner a decreasing-ve
direction, which is called Adversarial Critic. #(als)
Then, using importance sampling, the attacker's ' loss becomes Eg ( where G is the discounted future reward ET
-VV
i=t 7
4.3 POISONING ALGORITHM VA2C-P.
Algorithm 1: Vulnerability- Adversarial Critic Poison
Input: total iterations of learning K; poisoning power e: poisoning budget C; Initialize a list of policy discrepancies v = 0, the number of poisoned iterations c = 0
Initialize adversarial critic network V., and imitating policy network
for k = 1.... K do
if' C then
Break
Obtain the observation (trajectories) Og obtained by the learner
Update the adversarial critic V. with observation O₂ if White-box then
Copy the learner's policy parameters to the imitating policy of attacker: 5 + T Compute the clean next-policy n' < f O&)
10
Solve Problem (P) with power e and critic V., poison O₂ to Ö Compute the poisoned next-policy म' + f(ă, Ö²) Estimate the policy discrepancy th between and #'
11
12
13
14
Add tR to the list of policy discrepancies V
th 2 - largest element V then 15
Send the learner the poisoned observation Ö if' Black-box then Update the imitating policy as the clean next-policy: # +- n²
16
17
19
else
Send the clean observation O if Black-bar box then
21
Update the imitating policy the poisoned next-policy: +- H
Algorithm Saaiamm@illussaee Iillustrates how an attacker can poison an online RL learner with our proposed VA2C- P. which is corresponding to Line in Procedure shown in Appendix More implementation details are in Algorithm in Appendix F
In an iteration, an attacker first finds good perturbation for observation O with the current attack power then estimates how much the output policy will change by computing the policy discrep- ancy between the clean next-policy and the poisoned next-policy. Then the attacker poisons the policy discrepancy ranks high in the historical policy diserepancies. In Line 11, we projected gradient descent to solve Problem Computation details are illustrated in Appendix E
Algorithm D covers both white-box and black-box settings, both of which maintain an imitating
policy to keep track of the learner's potential status. As mentioned in Section 333] white-box attacker knows the learner's current policy, thus he directly copy the leamer's parameters to
7

---

Published as a conference paper at ICLR 2021
his imitating policy (Line 9), then predict the next-policy the learner would get under different observations. In contrast, a black-bos box attacker does not know the learner's policy, but he can update its imitating policy using the same observation as the learner uses (Line 18, 22). As claimed and verified by many black-box attacking methods (Behzadan & Munir] 2017). adversarial attacks are usually transferable, i.e., if the attack works on the imitating learner, then the attack is also likely to work for the real learner. Note that as assumed by Behzadan & Munir (2nir)(201)), the black-box attacker knows what RL algorithm the learner is using (e.g., PPO, A2C, etc), that the black-box attacker computes its estimation for the next-policy in Line 10 and Line 12.
5 EXPERIMENTS
In this section, we evaluate the performance of VA2C-P by poisoning multiple algorithms on various environments. We demonstrate that VA2C-P can effectively reduce the total reward of training agent, or force the agent to choose a specific policy with limited power and budget. Moreover, VA2C-P works for heterogeneous poison aims, and works in both white-box and black-box settings.
Experiment Setup. We choose policy-gradient learning algorithms, including Vanilla Policy Gra- dient (Sutton et al.) 2000). A2C (Mnih et al.] 2016), ACKTR (Wu et al.) (017) and PPO (Schulman ct al. 2017). And we choose Gym (Brockman et al. 2016) environments with increasing difficulty levels: CartPole, Lunarl Lander, Hopper, Walker and HalfCheetah. All results are averaged over 10 random seeds. The total effort U is calculated by the normalized fz-distance. See Appendix G. for the expression of U, as well more
settings.
(a) CartPole, A2C, D = O., c00.5
(b) LunarL.ander, A2C, D O., call1 (c) Walker2d, A2C, D -O,, c=0.5 (d) HallChetthh, A2C, D c0..
.00
129
-300
N: Naue Kanken WAYT P
Tecp!
30-
-200
20-
-10
No Puii Janten
-20
No Falus Koaken
NoRaio AC-
VAXCP
VAICP
(e) CariPule, VPG, D O,, c
Hopper, VPG, c50.
(g) Hopper, PPO, O., cah.1
Walker2d, ACKTR, e=0.3
Maan Sorepp Stroatt
Frine ACCF
Daloon AC-2
100
ACT
01 07
0.5
05
04
05
06
07
05
09
93 32
01
05 0.6 07 0. 03
61R
Figure 3: Comparison of mean per-episode reward gained by VPG, PPO. A2C, ACKTR various environ- ments, under no poisoning random poisoning. AC-P and VA2C-P.
Reward-minimizing Poisoning. Baselines. To the best of our knowledge, there is no exist- ing poisoning algorithm against deep policy-gradient algorithms. Although some evasion meth- ods (Inkawhich et al.] 2020) also work for policy-gradient gradient algorithms, evasion is substantially dif- ferent from poisoning since it does not influence the policy. Therefore, to show the effectiveness of VA2C-P, we compare it with 3 baselines: (1) the normal learning with no poison; (2) a random attacker which randomly chooses C' iterations, and perturbs the reward to an arbitrary direction by and (3) simplified version of our algorithm, called Adversarial Critic Poison (AC-P), which decides "how to attack" in the same way as VA2C-P does, but chooses "when attack" randomly.
performance of VA2C-P on all three types of poison aims, assuming the attacker knows the learner's model (white-box attack). Figure 3 shows the rewards of various learners under different kinds of poisoning methods, with different ratios of budget C' to the total number of iterations K. Compared with random poisoning, our proposed VA2C-P and the simplified version AC-P make the reward drop more significantly, demonstrating the effectiveness of our "how to attack" decisions made by the Adversarial Critic. VA2C-P further outperforms AC-P in almost all cases, which implies that our "when to attack" decisions based on Awareness AtweerbblltyyAwwenneess
Performance. We first show the
work well in practice. An interesting observation is random poisoning not only does not work well in many cases, but sometimes also facilitates the learner (Figure 3p). This
Vulnerability-
8

---

Published as a conference paper at ICLR 2021
phenomenon is mainly due to the uncertainty of the environment, pointed out by Challenge I and Thus, a good poisoning strategy is important.
Challenge II in Section [
(a) LanarLander, AZC, c-0.1
(b) CartPule, VPG, C/Ksi
(c) CartPole, A2C, C/K=1/0
(d) LumarLander, A2C, C/K=1,0
10-
122
Poraice Place Mi Ivs VASE
WEX-P =
-300
VADC- dh,
PORM -111
66-
200 1,600
Figure 4: (a) VA2C-P also works under black-box setting; (b) hybrid-aim poisoning could be better than single-aim poisoning; (c)(d) VA2C-P successfully forces the agent to choose the target policy.
Black-box Poisoning. Figure demonstrates the performance of VA2C-P when the attacker knows the learnrr' ' model. But when the learner's model is not available (black-box attack), VA2C-P could also work as shown in Figure/Ap. where one can see that black-box poisoning still effective, although worse than white-box poisoning due to the lack of knowledge.
Hybrid-aim Poisoning. The experiments shown in Figure 3 assume that the attacker poisons one of the 3 poison aims, O", Oa or O But if the attacker happens to have access to all of these poison aims, it can do better by performing a "hybrid" poisoming, i.e., at each iteration, evaluate the vulnerability of the algorithm w.r.t. each poison aim with their corresponding attacker power, then choose the one with the highest vulnerability. Figure 4 shows that adaptive attacking using hybrid poison aim could significantly outperform attacking using fixed single poison aim.
Targeted Poisoning. Baselines. Although targeted RI. poisoning is studied by many works (Huang & Zhu, 2019, Rakhsha et al.] 2020), few of them work for deep RI. Despite that no existing work focuses on deep policy-based methods, we transfer the FGSM-based targeted poisoning method proposed for DQN by Behzadan & Munir (2017) to attack policy-based learners as our baseline. The attacking method is, for each new state, adding a perturbation to such that the perturbed state is pushed across the decision boundary and towards the target action. See Appendix G.2 for details.
Performance. Figure 4 and 4 respectively show the targeted- performance comparison on CartPole and LunarLander, where the target policies are both "always going to the right". The y-axes show the proportion of target actions among all actions taken by the learner. VA2C-P successfully leads the learner to learn the target policy using all types of poison aims with relatively small attack power. In contrast, FGSM fails to let the learner select the target action in most cases, even with much larger attack power. The main reason why FGSM works for DQN Behzadan & Munir (2017) but not for policy-gradient methods is, policy-based agents generally learn stochastic policies, and even though FGSM could perturb the state such that the output probability for the target action is 0.51, the agent will still choose other actions with probability 0.49. Therefore, FGSM cannot easily perform targeted poisoning against policy-bused learners.
More experiment results are in Appendix G.3 Note that our proposed poisoning method can also be extended to off- off-policy learners, as discussed in Appendix G.4
6 CONCLUSION AND DISCUSSION
In this paper, we propose VA2C-P, the first generic poisoning algorithm for deep policy-gradient online RL methods, which incorporates heterogeneous poisoning models and does not require any prior knowledge of the environment. Although the effectiveness of VA2C-P is verified in wide range of RL algorithms and environments, we acknowledge that poisoning RL in practice is still challenging, due to the relatively high computational burden and the uncertainty of the environments. These challenges are also exciting opportunities for future work.
ACKNOWLEDGMENTS
This work is supported by National Science Foundation IIS- CRII Award 030742-00001 and NOD-DARPA-Deffnss Advanced Research Projects Agency Guaranteeing AI Robustness against Deception (GARD), and Adobe, Capital One and JP Morgan faculty fellowships.

---

Published as a conference paper at ICLR 2021
REFERENCES
Xiaoxuan Bai, Wenjia Niu, Jiqiang Liu, Xu Gao, Yingxiao Xiang, and Jingjing Liu. Adversarial examples construction towards white-box q table variation in dqn pathfinding training. 2018 IEEE Third International Conference on Data Science in Cyberspace (DSC), pp. 781-787. IEEE, 2018.
Vahid Behzadan and Arslan Munir. Vulnerability of deep reinforcement learning policy induction attacks. In International Conference on Machine Learning and Data Mining in Pattern Recogni- fion, pp. 162-275. Springer. 2017.
Battista Biggio, Blaine Nelson, and Pavel Laskov. Poisoning attacks against support vector ma- chines. arXiv preprint urXiv:/206.63:: 2012.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojeiech Zaremba. Openai gym, 2016.
Tong Chen, Jiqiang Liu, Yingxiao Xiang, Wenjia Niu, Endong Tong, and Zhen Han. Adversarial attack and defense in reinforcement learning-frow from ai security view. Cybersecurityy 2(1):11, 2019.
Adam Gleave, Michael Dennis, Neel Kant, Cody Wild, Sergey Levine, and Stuart Russell. Adver- sarial policies: Attacking deep reinforcement learning. arXiv preprint arXiv: 10615, 2019.
Ian Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. International Conference on Learning Representations, 2015. URL http://
arxiv. arxiv.org/al... abs 1et.//112..55 6572
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine Soft actor-critic: Off- policy maximum entropy deep reinforcement learning with stochastic actor. arXiv preprint /rX1v:1801.01290 2018.
Ling Huang, Anthony D Joseph, Blaine Nelson, Benjamin IP Rubinstein, and J Doug Tygar. Ad- versarial machine learning. In Proceedings of the 4th ACM workshop on Security and artificial intelligence, pp. 43 43-58, 2011.
Sandy Huang, Nicolas Papernot, Ian Goodfellow, Yan Duan, and Pieter Abbeel. Adversarial attacks on neural network policies. arXiv preprint arXiv:1702.0228:. 2017.
Yunhan Huang and Quanyan Zhu. Deceptive reinforcement learning under adversarial manipula- tions on cost signals. In International Conference on Decision and Game Theory for Security, pp. 217-237. Springer, 2019.
Matthew Inkawhich, Yiran Chen, and Hai Li. Snooping attacks on deep reinforcement learning. In AAMAS, 2020.
Ilya Kostrikov. Pytorch implementations of reinforcement learning algorithms. github. htt..///ooootooooo//rrrrrre-eeee a2c ppo acktr- -ail] 2018.
https: //
Yen-Chen Lin, Zhang- Wei Hong, Yuan-Hong Liao, Meng-Li Shih, Ming- Liu, and Min Sun. Tac- tics of adversarial attack deep reinforcement learning agents, arXiv preprint 1783v:1703.0774 2017.
Yuzhe Ma, Xuezhou Zhang, Wen Sun, and Jerry Zhu. Policy poisoning in batch reinforcement learning and control. In Advances in Neural Information Processing Systems, pp. 14543-14553, 2019.
Shike Mei and Xiaojin Zhu. Using machine teaching to identify optimal training-set attacks on machine learners. In Twenty-Ninte AAAI Conference on Artificial Intelligence, 2015.
Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In International conference on machine learning, pp. 1928-1937, 2016.
10

---

Published as a conference paper at ICLR 2021
Luis GonzzzzG,zzzezz Battista Biggio, Ambra Demontis, Andrea Paudice, Vasin Wongrassamee, Emil C Lupu, and Fabio Roli. Towards poisoning of deep learning algorithms with back- greddent optimization. In Proceedings of the 10th ACM Workshop Artificial Intelligence and Security, pp. 27-3,, 2017.
T. T. Nguyen, C. Soussen, J. Idier, and E. Djermoune. Np-hardness of 10 minimization problems: revision and extension to the non-negative setting. In 2019 13th International conference on Sampling Theory and Applications (SampTA), pp. 1-4, 2019.
Anay Pattanaik, Zhenyi Tang, Shuijing Liu, Gautham Bommannan, and Girish Chowdhary. Robust deep reinforcement learning with adversarial attacks. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS '18, pp. 2040-2042, Rich- land, SC, 2018. International Foundation for Autonomous Agents and Multiagent Systems.
Julien Perolat, Bruno Scherrer, Bilal Piot, and Olivier Pietquin. Approximate dynamic programming for two-player zero-sum markov games. volume 37 of Proceedings of Machine Learning Re- search, pp. 1321-1329, Lille, France, 07-09 Jul 2015, PMLR. URL http:httpp//tttt http:::/pprooeee.ggss
mlr. www.:rrssssseeeee v37 wttp:///////eeeeoaalsss/s html
Lerrel Pinto, James Davidson, Rahul Sukthankar, and Abhinav Gupta. Robust adversarial reinforce- ment learning. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 2817-2826 JMLR. org. 2017.
Amin Rakhsha, Goran Radanovic, Rati Devidze, Xiaojin Zhu, and Adish Singla. Policy teaching via environment poisoning: Training-time adversarial attacks against reinforcement learning. arXiv preprint arXiv:2003. 12909, 2020.
John Schulman, Sergey Levine, Picter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference on machine learning, pp. 1889-1897, 2015a.
John Schulman, Philipp Moritz, Sergey Levine, Michael I. Jordan, and Pieter Abbeel. High- dimensional continuous control using generalized advantage estimation. CoRR, abs/1500,, 2015b.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: 2017.
Ali Shafahi, W Ronny Huang, Mahyar Najibi, Octavian Suciu, Christoph Studer, Tudor Dumitras, and Tom Goldstein. Poison frogs! targeted clean-label poisoning attacks neural networks. In Advances in Neural Information Processing Systems, pp. 1103-6113, 2018
Thomas Spooner, John Fearnley, Rahul Savani, and Andreas Koukorinis. Market making via rein- forcement learning. CoRR, abs/ hts//800404216. 2018.
Jacob Steinhardt, Pang Wei W Koh, and Percy S Liang. Certified defenses for data poisoning attacks. In Advances in neural information processing systems, pp. 3517-3529, 2017.
Richard S Sutton, David A McAllester, Satinder P Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. In Advances in neural informa- tion processing systems, pp. 1057-1063, 2000.
Yizhen Wang and Kamalika Chaudhuri. Data poisoning attacks against online learning. arXiv preprint arXiv: 188.04480..0899, 2018
Yizhen Wang, Somesh Jha, and Kamalika Chaudhuri. Analyzing the robustness of nearest neighbors to adversarial examples. arXiv preprint arXiv:1706.0333 2017.
Yuhuai Wu, Elman Mansimov, Roger B Grosse, Shun Liao, and Jimmy Ba. Scalable trust-region method for deep reinforcement learning using woonncckr--fcttoree approximation. In Advances in neural information processing systems, pp. 5279-5288 2017.
Yingxiao Xiang, Wenjia Niu, Jiqiang Liu, Tong Chen, and Zhen Han. A pca-based model to predict adversarial examples on q-lcarning of path finding. In 2018 IEEE Third International Conference Data Science in Cyberspace (DSC), pp. 773-780. IEFR, 2018

---

Published as a conference paper at ICLR 2021
Qu Xinghua, Zhu Sun, Yew Ong, Abhishek Gupta, and Pengfei Wei. Minimalistic attacks: How little takes to fool deep reinforcement learning policies. IEEE Transactions on Cognitive and Developmental Systems, PP:1-1, 02 2020. doi: 10.1 00.1109/CDDS2222229975555
Chaofei Yang, Qing Wu, Hai Li, and Yiran Chen. Generative poisoning attack method against neural networks. arXiv preprini arXiv: / 770.00134, 2017.
Haoqi Zhang and David C Parkes. Value-based policy teaching with active indirect elicitation. In AAAI, volume 8, pp. 20822022-200 214, 2008.
Haoqi Zhang, David C Parkes, and Yiling Chen. Policy teaching through reward function learning. In Proceedings of the 10th ACM conference Electronic commerce, pp. 295-304, 2009.
Huan Zhang, Hongge Chen, Chaowei Xiao, Bo Li, Duane Boning, and Cho-Jui Hsieh. Robust deep reinforcement learning against adversarial perturbations on observations. arXiv preprint WxXiv:2003.08935 2020a.
Xuezhou Zhang, Yuzhe Ma, Adish Singla, and Xiaojin Zhu. Adaptive reward-poisoning attacks against reinforcement learning. arXiv preprint arXiv: 2003. /2613, 2020b.
12

---

Published as a conference paper at ICLR 2021
Appendix: Vulnerability-Aware Poisoning Mechanism for Online RL with Unknown Dynamics
A ADDITIONAL RELATED WORKS
Adversarial Attacks in SL. There have been many works studying adversarial attacking and de- fending in the past decade (Huang et al. 2011 Steinhardt et al., 2017). Poisoning, as an important type of adversarial attacking, has been well-studied in the field of machine learning (Biggio al.
2012 Mei & Zhu, (015). including deep learning (Muñoz-Gonzálee González et al.) 2017 Shafahi et al.
2018 Wang & Chaudhuri (2018) consider online learning, which similar ours. However, they Tocus on supervised learning, where the attacker knows all the data stream, while in our RL setting, the whole training data stream is not available to the attacker (as Challenge states).
Evasion Attacks in RL. Recently, adversarial RL is attracting more and more attention, especially evasion attacks at test-time, as summarized by [Chen et al.) (2019). Most works consider adversarial perturbations on observations, similar to adversarial examples in supervised learning. Huang et al. (2017) first show that neural network policies are vulnerable to evasion attacks on states, by gener- ating state perturbation with FGSM. [in et al. (0177) consider the data-correlation problem in RL and an attacker with limited ability, and propose a strategical attack method, which perturbs input states only under certain conditions. In addition, Gleave al. (2019) show that in multi-agent RL., choosing an adversarial policy could also negatively affect the victim agent, which is similar to per- turbing state into novel one. There are plenty of following works showing the vulnerability of deep RL policies, even against a limited-power black-box attacker Xinghua et al. (2020); Inkawhich
al. 2020), Adversarial attacks can be utilized train robust policies Pinto al. (2017) >; Pattanaik
et al. 2018)) There is also line of work focusing on adversarial examples in path-finding prob-
lems Xiang al. (2018); Bai et al. (2018). These evasion attacks are created to fool well well-trained policy, but they can not change the policy itself in training time as poisoning does.
B A POISONING FRAMEWORK FOR RL
In this section, we establish a generic framework of poisoning in online RL, systematically charac- terizing its challenges and difficulties from multiple perspectives objective of poisoning, various poison aims, and attacker's knowledge. Our in-depth comparison with the SL allows a thorough un- derstanding of the additional vulnerability of online RL systems compared with the well-understood SL systems. Our framework also provides a clear context to correctly position prior works in the literature well to compare our work with existing works. Compared to the poisoning frame- work described by |Huang & Zhu (2019), we provide a solution for unifying these poison aims in one attack model in this section.
We consider the online learning scenario, where the RL agent (the learner) does not know the dynam- ies or rewards of the underlying MDP M with state space S, action space A, transition dynamics P. rewards R and discount factor y
Settings and Notations In online RL, the learner interacts with the environment and collects obser- vations. The leameer' 's algorithm, denoted by f. iteratively searches for policy I parametrized by 8, through K interactions with the environment. Before learning starts, the learner initializes a policy At each iteration k. the learner uses its previous policy π to roll out observations O₂ from the MDP M. Ok is a concatenation of multiple trajectories, denoted as O₂ = (sk, ak. rk). where r7..r2,...11 are respectively the sequence of states, actions, and rewards in iteration k. Then, with the observations Ox, the learner updates its policy by attempting
8y [s1, 52, ".), ag [a,,a2, ag, a.....__ ..,, Tk
solve argmax, J(T, -g--1 O&), where J is the objective function. The generated policy by the learner's ' algorithm T = [ O of the objective function.
Y does not necessarily achieve the maximization
In this paper, an overhead check sign on a variable always denotes that the variable is poisoned. For example, if the attacker changes reward rt. then the poisoned reward is denoted as it
*For algorithms with experience replay, the update can he extended me++ f Ozak).
13

---

Published as a conference paper at ICLR 2021
Procedure 2: Flow of Online RI. Poisoning
Learner initializes its initial policy T0,
for k 1,.... K do
Learner rollouts observation (trajectories) Og in environment, M with current policy T
Attacker may poison the observation O₂ to O₂
Learner updates its policy: 7++1 [TTA O&) z argmax, Tk. Ox)
Poison Objective. We use LA to denote loss function of the poisoning attack, which the attacker attempts minimize. The form of La is determined by its goal, which falls into one of the two categories, non-targeted and targeted poisoning.
In non-targeted poisoning, the attack poisons policy a मे to minimize the learner's expected rewards. Therefore the poison objective LA is to minimize the learnrr's value (f()).
In targeted poisoning, the attack "teaches" the agent to learn pre-defined target policy n|, There- fore the poison objective LA is defined as distance IT, x!).
Most existing poison RL researches focus on targeted poisoning (Ma al. 2019 Rakhsha et al. 2020), and non- non-targeted poisoning, although discussed by Huang & Zhu (2019), remains relatively untouched.
poison aims. To influence the behaviors of the learner, an attacker could inject poison at multiple locations of the learner's learning process as detailed in Figure S in RL is more challenging than in SL is that it involves more poison aims of poisoning, some of which adapt with the environment, increasing the uncertainty.
Part of the reason why poisoning
De- poison
Polson Cissevvation
State S:
Oyr polson
Poison Training
Reward R2
My- polson
Paison Execulor
My
Pulci
Action
(a) supervised learning
(b) reinforcement learning
Figure 5: Different poison aims of poisoning in supervised learning and reinforcement learning.
Poison Aim I -- Poison Observation (O,, Oa). The attacker could manipulate the observation of the learner, i.e., change O into O. This may happen when the attacker is able to intercept the communication between the learner and the environment, similar to the man-in-the-midde attack in cryptography. The attacker could target the rewards, called Oy-poissning, studied by Huang & Zhu (2019;; or the states, called O₂ -poisoning investigated by Behzadan & Munir (0177).
Poison Aim Il Poison MDP (MR.Mp). An attack could directly change the MDP (environment) that the learner is interacting with, i.e., change M into M. For example, seller could influence the behaviors of customers by changing the prices of products. The poison MDP could be injected at the reward model R or the transition dynamics P. respectively denoted as MR-poisoning (studied
by Ma et al. (2019) and M Me-poisoning (studied by Rakhsha et al. (2020) The analogy of poison MDP in SL is manipulate the underlying data distribution of the training data.
Poison Aim III - Poison Executor Eq. The executor the learner could be poisoned. For example, an attacker applies force the agent, that the intended action "north" becomes "northeast". Pinto et al. (2017) train a robust RL agent against the executor poisoner. Denote this type of poi- soning Fa-poisoning. We show in the Appendix C that F. -aipooinn is equivalent to directly changing a stored in the observation O = (s,a, r, d).
'There are many ways to define the distance between two policies, for instance KI. diverrggeeee for stochastic policies (Schulman af. 2015a), and average mismatch for deterministic policies (Rakhsha et al. 2020).
14

---

Published as a conference paper at ICLR 2021
Attacker's Knowledge At the k-th iteration, what attacker can do depends on its current knowl- edge set, denoted by Kg. K& could contain the underlying MDP M, the learner's 's algorithm f. the learner's previous policy models 1 well the previous and current observations O..k-
[M, 11 Ora Most guaranteed pol- icy teaching literature (Rakhsha al., 2020: Ma et al. 2019) assume omniscient attacker. However as motivated in the introduction, it is often unrealistic to exactly know the underlying environment. We discuss two more realistic setting where the attacker only has limited knowledge as follows.
An omniscient attacker knows everything i.e. x
A monitoring attacker has some information but does not assume knowledge of the underlying MDP M, i.e., xc(M) = [S. 01x-11111 ). This is especially relevant in applications where learner's information is not secure (or even open), or an attacker hacks to steal information from the learner. Monitoring attacker is similar to the white-box attacker in supervised learning.
A tapping attacker has very limited knowledge and knows the observations only, i.c., K( (Oi*). This is widely applicable since the tapping the communication between the learner and the environment is easy. Tapping attacker is analogous to the black-box attacker in supervised learn- ing. Behzadan & Munir (2017) consider tapping attacker, which observes and manipulates the states but does not know the learner's s parameters.
C TARGET TYPES OF ATTACKING: MORE DETAILED EXPLANATION
11
(a) Poison observation (O,, O,)
(b) Poison MDP (M))
(c) Poison Executor Ea
Figure 6: The online poisoning vs learning. Blue solid lines denote the learning processes, while red dashed lines denote the poisoning processes. In iteration k the learner uses its previous policy πk-1 to roll out observations O₂ from current MDP M₁, then updates its model and policy by F = f 1, Ox) = argmax, TT--,, O). The attacker may (a) poison observations after they are generated, (b) poison MDP before the learner generates observations, or (c) poison the policy when it is used to generate observations. Among these three scenarios, O₂ is always influenced by the attack, thus denoted as Oa.
C.1 POISON OBSERVATION
Consider a deep reinforcement learning algorithm, which uses its old policy to generate a series of observations and updates its policy with the collected observations at every iteration. The observa- tions are stored in temporary buffer in the form of (s, a, d), where 8, r, d are returned by the environment, and a produced by the policy itself.
An attacker could stay in the middle between the learner and the environment and falsify s, r re- turned by the environment before the learner receives them. (It also possible to alter the terminal state flags d, but it is relatively easier for the learner to detect, and its influence to the learner is not as large as and r, so we do not discuss this attack type.) On the other hand, the attacker may also hack the observation buffer to change s, In both cases, poisoning and r called O₂ poisonnin and Oo--oiisning respectively.
Note that in the case of hacking observation buffer, the attacker also has the option to manipulate a in O. But we do not include this kind of attack in observation poisoning, because not like states and rewards, the actions are taken by the learner, it is easy for the learner detect the change of action sequence stored in the buffer. And we will show in Section C.3 that changing a in O is similar to the case of executor poisoning.
15

---

Published as a conference paper at ICLR 2021
C.2 POISON MDP
MDP poisoning can be considered as "changing the reality" for the learner. For example, an attacker decides to increase the reward for state-action pair (s, a) by A at iteration t, it then changes the parameter Rg(s, a) of the environment to R& (s, a) = R& (s, a) + A. As a result, whenever the learner visits (s, a) in the current iteration, receives R& (s, a) as reward. example is depicted in Figure 7 where we want to train a mouse to find the cheese in maze. However, if some bad man adds another piece of cheese in the training environment, the mouse is likely to be misled. Then, in the test time, the "malicious cheese" is removed, but the mouse still wants to find the malicious cheese instead the original one.
more intuitive
???
(a) training environment
(b) poisoned environment
(c) test environment
Figure An intuitive example of MDP poisoning.
Compared with observation poisoning and executor poisoning, MDP Poisoning is more powerful and more difficult to defend against. An example of MDP poisoning is given by Rakhsha et al. 2020), where the attacker can force the learner learn target policy with guarantees.
C.3 POISON EXECUTOR
In the online RL process, the learner learns by taking actions and getting feedbacks of the actions. If observation poisoning is viewed as changing the feedbacks, then executor poisoning can be viewed perturbing the actions taken by the leamner For example, for auto-driving agent, can slightly add some force to the steering wheel, so when the agent takes "steer left 90 degrees", what actually happens is "steer left 100 degrees". In this way, the trained policy is biased.
We now show that the aforementioned attack of changing a in could be converted to executor poisoning. We describe the following two scenarios respectively for these poisoning attacks and show they have equal effects. For simplicity, we only consider one step of the interaction, which can be simply extended multiple steps.
(1) Poisoning a in O. For one-step experience, the learner observes state s, takes action receives reward r; R(s, a.) and observes new state s/ ~ P(- (s, a;), then the tuple (s, a, Tis s() will be stored in the observation buffer. Now the attacker may change the action a, to aj. and the tuple becomes (s, a, rı, s)). Finally, the learner regard ri, s and the following observations caused by aj. instead of a;
(2) Poisoning Executor. In the same environment, suppose the learner observes state s, and takes action aj. then the attacker conducts executor poisoning and changes aj to a; then the reward and the next state will also change r; R(s, a;) and s P(-|s, a;). The learner does not know the falsification of action and stores (s, a, rı, sf) to the buffer. Finally, the attacker will take r sf and the future observations as caused by ay, and updates its policy accordingly.
Based on the descriptions, to a; on the executor. we assume the policy always has non-zero probability on all actions, then for any manipulation Hence, given the fact that the former attack can be trivially defended, we only discuss executor poisoning in poisoning framework.
see changing a; aj in the buffer is equivalent to changing a;
in O, it is possible to achieve the same effects by attacking the executor.
16

---

Published as a conference paper at ICLR 2021
D ROBUSTNESS AND STABILITY OF RL ALGORITHMS
D.1 MEASURING VULNERABILITY OF RL ALGORIHHM
Definition in Section 4 measures the stability of one update based on policy discrepancy. But it not obvious whether the rewards change drastically due the attacks. Proposition 2 provides guarantee on the performance of the poisoned policy #', compared with the un-poisoned new policy n².
Proposition 2. For an update of stochastic policy x' = f(t O), if its 8- staabiility radius is with the total variance measure, then any poisoning effort smaller than e on DD will cause the expected total reward drop (11(²²) r7((²) by no more than
4 maxs.0 |A (8,
26
Σ (s) max A=
(1 (1-
sES
where r is the discount factor, 9x (s) = - and the advantage function, i.e., Aa (5 (s, (s).
P(s s| s/T) ) is the discounted visitation frequency,
Proposition Seressttionnhowwwe shows that if the attack power is within the stability radius, the reward of the poisoned policy will not be influenced too much. which also explains the motivation behind our proposed vulnerability-awe aware attack. The proof in Appendix D.4
With Definition I the une-ue stability measure, we are able to formally define the stability radius of an RL algorithm w.r.t. an MDP.
Definition (Stability Radius w.r.t an MDP). The 6-stability radius of an algorithm f in an MDP M is defined as the minimal stability radius of all observations drawn,from the MDP, and all possible policies in policy space II. If f is on-policy, then Φ(J minzen,o (, (,) if f is off-policy, then $(f. M) = min off,
n,, O),, where n is the behavior policy;
D.2 ROBUSTNESS RADIUS
Different with poisoning. test-time evasion (adversarial examples) misleads the agent by manipu- lating the states only, since the agent no longer learns from interactions and feedbacks. Note that although Gleave et al. (2019) propose an attack called "adversarial policy", the perturbation does not happen in the policy, but still happens in the input states (observations) of the agent.
To study how robust trained policy is, we define the robustness radius with regard to both a single state and the whole environment.
Definition 4 (Robustness Radius of Policy w.r.t. a State). The robustness radius of a deterministic policy x on a state s defined as the minimal perturbation of s which changes the outpur action, i.e.,
p( 8) = =inf(38 =in[(3EESSBBL (. s.l. T(s) + m
Similarly, for any 0 < < 1, the 5-robustness radius of a stochastic policy ा on a state s is defined as the minimal perturbation of s which makes the output action distribution disagrees with the original T(8) with probability more than ó, iee.
p( inf E S (s) s.t. d ([T((1))(=((15)) > 88
(4)
where d(.l.) could be any distance measure between two distributions.
Remark. If we regard the policy as a classifier which "classifies" a state to an action, then the robustness radius of policy defined above is analogous the robustness radius of classifiers defined by Wang et al. (2017). with an extension to stochastic predictions.
Definition (Robustness Radius w.r.t an MDP). The (6- (o-jrobusss radius of a policy π in an MDP M is defined the maximal robustness radius of all states, i.e., M) minses P(TT, 8)
Remarks. (1) deterministic policy is robust against any state perturbation smaller than p(T.
17

---

Published as a conference paper at ICLR 2021
(2) For stochastic policy, if its 6-robustness radius in M is E, then any state perturbation within & will cause the expected total reward drop by no more than
207 7)²
+ 26) max [R(s,a)),
(5)
which is proven by Theorem 5 in Zhang et 2020a
D.3 VULNERABILITY COMPARISON: DIFFERENCE BETWEEN SL AND RL
To shed some light on understanding adversarial attacks in RL, we compare SL and RL in terms of their vulnerability poisoning and adversarial examples.
At test time, policy network receives states as input, and returns probabilities of choosing each actions as output; value network receives states (or state-action pairs) as input, and returns the corresponding value the output. Thus, test-time RL systems are very similar to SL. systems, as one can view the policy networks as classification networks, and value networks as regression networks. However, the key difference between evasion in RL and evasion in SL is, data samples are not independent in RL. single adversarial example in SL. test dataset may cause at most one misclassification instance, whereas adversarial example in RL may case drastic change of the gained rewards (e.g., by leading the agent to a "devastating" or "absorbing" state).
At training time, SL systems and RL systems are significantly different, as Figure shows. Even when the supervised learner also learns from data streams in an online manner, the training data independent with the learner's classifier. In contrast, the distribution of training data samples changes as the learner updates its policy. Poisoming attacks against an SL system could alter the decision boundary, so that the learner makes wrong decisions for certain data samples. For an RL system, poisoning attacks could (1) alter the decision boundary so that the learner chooses bad actions for certain states, and also (2) change the following observations and interactions due different selection of action.
In summary, an adversarial attacker may cause higher damages on RL systems than on SL. systems, with the same power and budget. But it does not suggests attacking RI. systems is easier than attacking SL systems. As every coin has two sides, the high uncertainty of the environment may help attack reduce the learner's reward, but may also lead the learner to gain higher reward in the future (as shown in Section 5). Therefore, more challenging to successfully attack RL systems than SL systems with specific goal.
D.4 PROOF OF PROPOSITION 2
Proof. According to the definition of ô-stability radius, for any poisoning effort within E, the poi- soned policy satisties D ["|[ S ó (assume total variance Drv is the distance measure between policy distributions). We are interested in the difference of expected rewards 17(x)) r7(*))
n((²)= + E.Es Ix EnEd # (als) (s, a). where g is the discounted state visitation frequencies, i.e.,
Define (*')
9n' (s) (s0 s/m² 7 (81 s|m') 2 (82 s|
Since D [ ||*1 < 8, follow Theorem in paper (Schulman et al. 2015a), we can get
In(#') T.p (xr) 482, max,,a |A (8, a)l
(6)
(1 7)-
So we have
402y max,, |Ar a)l
In(*') 71(TT)) Σ (s) Σ (s
(7)
(1 212)²
aES
aEd
which can be transformed to
482 max, A (s, a)
((7²) 7)²²) S
Σ
In gw((s) Σ (((alssA,,rs.)))
(8)
(1 -1-99 7)
8ES
aEA
18

---

Published as a conference paper at ICLR 2021
We upper bound the term
Eees (r EnEn (s. a) below.
Σ (s)
Σ (s(
SES
aEA
gr) -F [((als)Ar(ss.)))
SES
aeA
Σ (r((s) Σ [t(als)A, + Σ (s, - Σ (3,
SES
aEA
aEA
GEA
(9)
Eer(s) Σ
- t'(ass)))
Σ (s,.)s))rss.aa))
SES
aEA
aEA
Σ (2)
max aEA
Ag (s,
Σ (x(
SES
aEA
20
Σ
In' (s)
max Ar (s,a)l
aEd
#ES
Combining the above results, we obtain
nT-') m1(²) s 4 max,, (s, a)l
+ 26 Σe gnr (s) Ar as)
(10)
(1 71
SES
E ALGORITHM
Assume the learner's policy æ is parametrized by 0.
How to solve the projected gradient descent. To solve (P) jected gradient descent to update r by using the chain rule:
assume
8Pg
exists, one can use pro-
@m (TOe)
@mmo (Ter)
00
OF
002
OF
For Vanilla Policy Gradient (VPG) whose update rule is, O2 = Oa~1 + aV V r),, where
N
Fe- (TTT r)
V log LogTe._11 1a ((())(())))
(11)
can derive
1 N
T
V Vommo--1
(TTO)) 2
To. (a
Vo. log To, (a; 1s) (1) ))
E 2 ((0))
N
Th (a,
1m1
(12)
and
[V,0ke- Σ Vo, log Te, (aglss))*
(13)
Although 09, has closed-form expression for simple learners like VPG, analytically computing 2F how the poisoned reward influences the model is challenging for more complicated learners like PPO, whose update rule is an argmax function. Therefore, we use the Direct Gradient Method proposed by Yang et al. (2017) to approximate the gradient by
Mm., (TO.)
M= (f(TO, 1, + A)) M= ( ((TT))-,)))
(14)
07
A
19

---

Published as a conference paper at ICLR 2021
Algorithm 3: Non-targeted White-box VA2C-P with O,-Poisoning
Input:
total iterations of learning K; poisoning power с; poisoning budget C; attacker's
learning rate 3; maximum computing iterations J; distribution distance measure d Initialize policy discrepancies as an empty list V 0
Initialize the number of already poisoned iterations Initialize value network V for k = 1,... K do
c > C then
Break
Get the current observation O₁ and the learner's policy model 0x-1
Fit the value function: w f- argmin En,o, Σx= (V. Σt 2/ -
Imitate learner's update with the clean rewards 0k. +- Update (0x-1.T) Initialize F the original r in Ox
11
Set 1/o 77 do
for j = 1....
13
for i 1,..* N and - 1, , do
Copy r' <- r, and add small value A (r')6) Imitate learner's update with poisoned rewards 0', r/ + Update (0x-1,
15
16
Compute the direct gradient: (P.
-/-
A
Update the poisoned reward: * (r) (P
3
17
Imitate learner's update with poisoned rewards 8x, fi + Update (0x-1,
18
if (nz 175-1) converges then
29
Break
Compute ah = NT E,go d(TTe (Ta.)) and add 2/x to v
1
21
t/ is larger than the [(C - - k)] Itth largest element in v then
22
Attack: replace with # in O₂ and send it back to the learner
24
c
25 Procedure Update (0,r)
Perform update with the learner's algorithm 0' f(0,r)
27
Compute the attacker's ' objective
NT EnEo, Et= (a ( (1)
1 21 (s()))
1)
(a 1 (100)
20=
return 0',")
To show the concrete poisoning process, assume D O". Then Algorithm shows the detailed procedure VA2C-P with non-targeted goal and white-box attacker.
For Targeted Poisoning. In line 16, instead of computing
compute Odist(e', a
ag
(x!(")
For Black-box Poisoning. In line 7, instead of getting the learner's policy model 0x-1, train policy with the same algorithm of the learner 0x-1 + f(0-22, Ox-1).
F THEORETICAL INTERPRETATION OF THE BI-LEVEL OPTIMIZATION PROBLEM
In this section, we discuss the problem relaxation made in Section 4.2 For notation simplicity, we focus on the case D = rr.
F.1 PROBLEM FORMS
Suppose the attacker has budget C K. Then following the format of Problem equation Q could define the original Oo-poiionn optimization problem for the poisoning at the k-th iteration Problem equation] P= Note that for notation simplicity, the policy parameter 0 to denote
20

---

Published as a conference paper at ICLR 2021
the policy ne, that nn() (TTT)).
K Σ m0,))
argmin
(P*)
Pe PK
j=k
s.t.
0j =
|| - ry Se, Vj =j=k, k, ... K
Note that only optimize on F4 to rk. since previous k decisions have already been made the k-th iteration.
Although omniscient attacker is able to predict all the observations and solve Problem equa- tion P directly, for the non-omniscient attacker that we focus on, Problem equation P* is not
solvable because the unknown observations in iteration & + K, Hence, as discussed Sec- we relax equation P a multi-variable optimization problem, to (K - k - 1) sequential
tion 4
singie-variable optimization problems
argmin Pk
17(0))
(Pa)
S.t.
O2 110
|| - rxll Se
argmin n(8x+1)
(Px+1)
Fx+1
s.t.
Okt1 = 5(0x, Pk+1)
|| -K++1| S
and all the way to
argmin n((k)
(Pk)
*x
s.t.
0K = [(00-1,
||pK rkll S
where ry -j- k.....
K.
Note that Thk is already generated and known for all the above problems. When solving Problem (Py), Ty and 0j also known (determined by 0--1).
F.2 TIGHTNESS PROBLEM RELAXATION
Problem equation P* is (K - k 1)- --variablle optimization problem with (K - k: + 1) equality constraints and (K
inequality constraints. And Problem equation Ps ... equation Pk are (K k + 1) vinglevariable optimization problems respectively with 1 equality constraints and inequality constraints. The two sets of problems are naturally equivalent if .z.... 0xx as well as the constraints are independent. However, due to the online learning process (Figure (). 0k+1 and T8+1 are all dependent on O₂ and rg. which makes the relaxation not necessarily optimal.
We call the optimal solution to Problem equation P as (Fi..... Fi)) ), and the optimal solutions to Problem equation Ps to equation Px
For simplicity, we assume the environment and the policies are all deterministic. So that the value of observed reward r is deterministic function of 0,-1.
We claim that the relaxation does not change the feasibility as stated in Proposition 6 Proposition 6. (fith
feusible solution to Problem equation Ps
Proof. Note that r is known and the same for both equation P* and equation P
(1) #t is feasible to equation
P because it satisfies |/ rxll Se
21

---

Published as a conference paper at ICLR 2021
(2) For Problem equation
P*
with 0% f(0 #
rk+1 is the same with the M4+11 in Prob- # 1441 satisfies
lem 1 Since the optimal solution to equation Pk+1
a 1441 | - -T4+ll S G
is
also leasible equation
Ps
(3) By induction,
K 1a=k all satisfy the constraints in equation
P*
the same time, so
(Ft .Kk is feasible solution to Problem equation P*
Note that the environment or the policy is stochastic, then ry is a random variable sampled from some distribution defined by 03-1. In this case, the constraints for Problem equation P* should be Pr(lir, - ryl & c) 2 t. Vj = k ....... KK, where E [0, 1] is a threshold probability. Then, with appropriate t, Proposition 6 also holds.
So far we have shown that the relaxation is feasible, so that the attacker will not plan for a non- feasible poisoning with VA2C-P. Next, we discuss the optimality of the relaxation.
We first make the following assumptions.
Assumption 1: the learner's update function f(0, +) is differentiable w.r.t. / and A.
Assumption 2: the environment and the policies are all deterministic, and the reward r generated by policy Te is differentiable w.r.t. 0 (i.e. R(s, (s)s) is differentiable w.r.t. 0).
Proposition 7. If Assumption I and hold, the necessary condition for ....... .kk) being optimal solution to Problem equation P* for all = k ... K,
im((0,) 00,
K
On(0y) 00, 08 00;
30; 0r, ,
80 00,- 00; Dr, k,=
(15)
-'#+1
Proof. Consider the case K = 2 for simplicity, and the results naturally extend to a larger K.
At iteration 1, Problem equation P becomes
argmin Fi
(/:1) + n1(2))
(PO)
s.t.
01 f(0o, 11)
02 = f f(01, 12)
||A1 rı 2211 S
|| r2ll S E
where 6g and F1 are known.
The relaxed problems
argmin
(70))
(PI)
"1
s.t.
01 = f flu, r1) || rı Sc
where Og and are known, and
argmin
v)22)
(P2)
P2
s.t.
0₂ = f(0 12)
|| r2 Se
where 0, and 222 are determined by F1, the solution equation
P1
Suppose *# and ## are the optimal solutions equation P1 and equation
P2
And we discuss
the necessary condition for *# and r being optimal to equation P0
We can rewrite equation PI
argmnin
n(f(Bo. r1))
F
1 2 + y =
s.t.
22

---

Published as a conference paper at ICLR 2021
And the Lagrange function of the above problem is
L(ř1, A1, 81) = (60. r1)) + A (1 - rıl1² -2- -/
(16)
The necessary conditions for #1 being optimal are
Onj R1))
+ 0A1 - ri ril e² +vf)
(17)
dř
dr
||
Tı 112
e² + 3/ =0
(18)
11//1
= 0
(19)
for some Å and y1- Similarly, for Problem equation P2
the necessary conditions of optimality are
Om O01, +2))
0A2 (1
r2l1²
6² v2
(20)
0r
0r2
|| 12
1
6² + v/2 =0
(21)
A23/2 = 0
(22)
for some A and y2-
Since 7 and r are the optimal solutions to equation
P1 and
equation
P2
v and r satisfy
Equation equation 17 ~ equation 22
Expanding equation 17 and equation 20
we get
On 00
+ 2A1 - -mr =
(23)
00, 0r
A
On 002
002 0r
P
+ +2d2 r2) = 0
(24)
For Problem equation PO] the Lagrange is L(F1, 82M, X2 s/ 1/2) = m(S(0,, (() (1=,:(0000--1111"-"""""000011110 -022)-r2222 22112-2+++16)
(25)
And the necessary conditions for F1, i22 being optimal are Öm(f(eu, +1)) θř1
Ōm(f r2)) ax (1 r1112 2 (z112) +
0X2(1122 r2 12 e- (3/)
0
θř,
θr,
0r
(26)
On( (01,
0N6 (1 12 - =2 +162)²) 0
(27)
0r2
0rz
|| ri 1 2² + (of )2 = 0
(28)
|| 2 -- 2 + (v6)² 0
(29)
Xy/ = 0
(30)
Xa3/2 = 0
(31)
for some X1; N2. ví 1/2 (not the same with \1, A2, 21, 92).
Expanding equation 26 and equation 27
we get
On 001
+ On 002 001
00, 0ř2 001
0ř 001
00, Dr, -
00, 00, dr,
+
Dr 01 0r
1 =1
2x7 - r1) + 2X
r2)
00, Dr,
I h-
(32)
On 002
bę= + +22 - r2) =
(33)
002 0rz
23

---

Published as a conference paper at ICLR 2021
Combining equation 23
equation 24
equation 32 and equation 33
obtain
282 2 dr, == C On 001
On 2 001
(34)
00, dr
for some Ç. which the necessary condition for of and r being optimal to Problem equation PO
Intuitively, this condition implies that the gradient of 77(1) w.r.t rf (the RHS) should be aligned with the gradient of n7(2)) w.r.t / (the LHS), without considering the influence of 111 to 12. That is, although 1 influence 01. 01 influences both 0g and 12 (because 822 is generated by Te, ), LHS does not include On (90, Beg 80, which makes equation 34 computable in many cases.
70g Dog 00, DF,"
However, for the setting of our VA2C-P (monitoring attacker for online RL), the attacker at iteration k = does not know the observed reward T2 of iteration 1: 2, which prevent the agent from conducting the optimal attack. But equation [3 could help the attacker verify whether past poison likely be optimal for the iterations so far. For example, if the learner is using VPG, then iteration & = 2, the attacker can test whether its previous poison rj did a good job in minimizing m(01)= (7(2)) ( by evaluating whether (I V2 Ve, is equal Vo, (7))).
G EXPERIMENT SETTINGS AND ADDITIONAL RESULTS
G.1 DETAILED EXPERIMENT SETTINGS
Network Architecture. For all the learners, use a two-layer policy network with Taanh as the activation function, where each layer has 64 nodes. PPO, A2C and ACKTR also have an additional same-sized critic network. We implement VPG and PPO with PyTorch, and the implementation of A2C and ACKTR are modified from the project by Kostrikov (2018).
all experiments, the discount factor y set to be 0.99. We run VPG and PPO for 1000 episodes on every environment, and update the policy after every episode. For A2C and ACKTR, we use 16 processes to collect observations simultancously. and update policy every steps (i.e., each observation O has 80 (s, a, r)) tuples); learning last for 80000 steps in total.
Hlyper-parameters
Distance Measure for Perturbation The definition total effort function ('(-) plays an important role of understanding the attack power. Since states, actions and rewards in different forms and scales, we define U differently for various poison aims. Also, note that is a concatenation of iirc--action-ewaatt tuples, and its length could vary in different iterations, normalize over the length of observation.
For D O define the total effort as
VI0=
SEO*
For D = 0a, if the action space is continuous, we define the total effort as
U(O%,0a)
Σ
||a
م||2.
ViOa
aEOa
and if the action space is discrete, we define the total effort as
U'O",
Σ
I(a a).
VIOa
aEOa
For example, in CartPole, the action is either 0 1, then the attacker with 0.1 can flip up 10% the actions one iteration.
For D Or, define the total effort as
U(O",Ön)
Vlor |r F||.
24

---

Published as a conference paper at ICLR 2021
In the supplementary materials provide the code and instructions, well demo videos of poisoning A2C in the Hopper environment, where one can see under the same budget constraints, random poisoning has nearly influence the agent's behaviors, while our proposed VA2C-P suc- cessfully prevents the agent from hopping forward.
G.2 FGSM-BASED POISONING
The procedure of the FGSM-based targeted poisoning is as follows. We transfer the method pro- posed by Behzadan & Munir (017)) from attacking DQN to attacking policy-based algorithms. Although Behzadan Munir (2077) assume a black-box setring, we hereby use white-box attack (attacker knows learner's policy parameters) in order to let FGSM be stronger baseline.
For step L,
Step 1: the learner observes takes action de, the environment returns reward Tz, state 8t-15
Step 2: the attacker queries the target policy and gets Gadv = π (8(+1);
Step 3: the attacker poisons $1+1 by
it+ 8t+1 + c sign( (V set1 (Tr(a (8t+1)));
Step 4: the attacker sends 8141 814-1 the learner.
G.3 ADDITIONAL EXPERIMENT RESULTS
Figure shows additional results on various environments and RL algorithms, including both non- targeted poisoning and targeted poisoning.
25

---

Published as a conference paper at ICLR 2021
CariPole, AZC, D Oa, cmll.
CartPole, A2C, D Oi ea
CartPule, PPO, D Ca ce0.
Hopper, ACLKTR, D O.,, cm0.1
150
Noas Tann Roo
-30
100
103
143
106
200
Peice Price
AC-F
Radkes Poice
Konken KalkerRaion
100
Teaion Pricee
(c) CartPole, VPG, D O,,
CartPole, VPG, D O,, ml11
CartPole, VPG, D Ci mLL
(d) HalrChoetah,, A2C, D O., m00.1
123
No Frices Palaas
100
WASCPP
No
NoNoun Prlce
Rankes
VAZU
05 do 67
HalfChestah, ACKTR, D 0w.0
Hopper, VPG, O.,
Hopper, A2C, 10 Or. cw0.1
CartPole, VPG, D O.., 100.1
266
-00
1900
80
Price AC
Moue Ven speaee
-00
Af
300
X0-
Price
ACF
VAXCF
1.5
d6
01 o5
os
ns
os
65
0//
CIW
CartPole. A2C. D= c=0.1
CartPole, A2C, O,, cm0.1
(Targetedi CurtPit, VPG, C/K-10
(Targted Loneea C/K-10
Seam
FC...
180
-30
03-
0.5
123
No Nutet
No Datee
07-
P
VAZCO
ACP
0.
RTSM) -05
03 03 01
35
06
07
01
0.4
831
000
1.00
203
400
C1R
0//
Figure 8: Additional Experimental Results
G.4 EXTENSION TO OFF-POLICY LEARNERS
Although we focus on on-policy policy gradient learners this paper, our poisoning method is also applicable to off- off-policy learners which update their policies using sampled mini-batches from all historical observation (trajectories). If the adversary can manipulate the mini-batch the learner samples at every step. our proposed poisoning process works usual. We implement this idea and test it for one of the statc-of-the-art off-policy learning method SAC (Haarnoja et al. 2018), and the results are shown in Figure 9 where VA2C-P significantly reduces the reward gained by the learner. In the other case, if the adversary doesn't 't see which mini-batch the learner samples but has access the buffer, he can still alter or insert some samples influence learning.
26

---

Published as a conference paper at ICLR 2021
No Poison VA2C-P
400
300
Canslativ
200
100
200
Egisediss
Figure 9: Poisoning off-policy algorithm SAC with VA2C-P. Or, = =1,==00 0.6.
27


Reviews:
[{"review_id": "vpgwIE5zBJO", "reviewer": "AnonReviewer4", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "#### Summary:\nThe paper studies poisoning attacks on RL agents, in which the attacker influences the agent's learning process by changing the feedback obtained from the environment. The focus is put on attacking policy-based deep RL agents, without necessarily having access to the underlying MDP model of the environment. The paper proposes a new poisoning algorithm, called Vulnerability-Aware Adversarial Critic Poison, and experimentally demonstrates its effectiveness on 5 different RL environments.   \n\n#### High level comments (pros & cons):\n\n-The paper studies an important and interesting topic, poisoning attacks on RL agents, and develops a novel deep learning methods for designing more efficient and scalable attack strategies.   \n\n-In contrast to prior work, the proposed algorithm utilizes deep RL techniques, making it applicable to more complex environments. The experimental results indicate the usefulness of the proposed method. \n\n-The clarity of the paper could be improved, including the statement and description of the optimization problem and the algorithm. Furthermore, it is not clear how the problem formulation compares to prior work. Some claims in the paper should be stated more precisely.\n\n-The proposed algorithm is a greedy approach and does not have provable guarantees on the optimality of the derived attack strategies. This is in contrast to prior work cited in this paper, which appears to have some guarantees on the performance of the attack.  \n\nOverall, I enjoyed reading the paper, and its contributions seem novel and important for the line of work on poisoning attacks in RL. However, I also think that the paper could be improved in terms of clarity, and additional justifications and explanations could be added throughout the paper.  \n\n#### More specific comments and suggestions for improvement:\n\n-The exposition of the results could be improved, and some parts clarified and made more precise. For example, footnote 1 is confusing, since it states that this paper assumes that the attacker poisons observations. On the other hand, the paper also mentions results on 'Hybrid aim poisoning'. It is also confusing that optimization problem (Q) is defined as weighted loss, and then in the first paragraph of Section 4 we have the claim: 'Without loss of generality, we assume the loss weights $j = 1$ for all $j = 1,..., K$.'. The first sentence in Challenge II is also not clear: why is Markovian property important in 'are no longer i.i.d. due to the Markovian property'?  There are also sentences that do not seem to be precise. E.g., the sentence 'However, in complex environments such as Atari games, knowing the dynamics of the MDP is difficult.'  doesn't seem to be precise (since dynamics can be obtained from Atari simulator...).  Given that the paper motivates its setting with Atari games, it is also not clear why Atari games were not used as a test-bed. \n\n-Parts of the optimization problem (Q) are somewhat confusing. In particular, the paragraph that explains constraint (b) (imitate the learner), does not seem to precisely specify what this constraint looks like. In the white-box attack, it is written that the attacker knows the learner's policy and can directly copy it.  It is also stated for black-box attacker that it 'may know the learner’s algorithm', but does not know the learner's policy. On the other hand, in Section 2, it is written that 'white-box attackers, who know the learner’s model, and black-box attackers, who do not know the learner’s model. '.  These parts could be explained in more detail, or more precisely stated. \n\n-Constraints (c) and (d) control the attacker's influence, but the paper does not seem to indicate the practical importance of having both constraints. It might be useful add some discussion on this, as having both constraints seems to affects the algorithmic design proposed in the paper, and the complexity of the optimization problem. \n\n-The discussion in the related work section seems to put emphasis on practical importance of the proposed approach compared to some of the recent papers on poisoning attacks. However, it does not seem to elaborate on the differences in problem formulations, i.e., optimization problems and objectives. \n\n-The focus seems to be on an episodic setting in which after each episode (iteration), an RL agents updates its policy after the data is possibly poisoned. I'm wondering to what extent would these result generalize to fully online setting in which an agent can change its policy after each action taken. Moreover, it is not clear how one can poison e.g. observations only after an episode ends (since the same observations are needed to derive actions from the agent's policy). Additional discussion on this would be valuable. \n\n-The model of the black box-attack is somewhat ambiguous. It is first stated that a black-box attacker may know the learner's algorithm, but it is not specified to what extent the attacker relies on the knowledge about the learner's algorithm. Furthermore, the notion of pseudo-learner does not seem to be defined. \n\n-Minor: There are two 'Step 5' in the description of the algorithm. Furthermore, the algorithm uses variables $\\psi$ and $\\Psi$, which do not seem to be defined before section 4.3.  \n\nThe paper also contains minor typos, e.g.: \n- the test-time evasion attacks Chen et al. (2019) where the attacker crafts -> citation style\n-alter the environment (e.g. change the transition probabilities) ,  -> remove space before ,\n-On the contrary, We consider non-omniscient attackers - 'We' should be 'we'\n-'a learner gains from the environment, i.e., $O = (O^s,O^a,O^r)$' -> Is $O^a$ observed?\n-Compared with Problem ( Q), -> ( Q) should be (Q)\n-The solution to Problem (P) is always feasible to Problem (Q, although... -> e.g. (Q should be (Q)\netc.\n\n\n#### Questions: \n\na. I didn't understand footnote 1. It states that this paper assumes that the attacker poisons observations, but on the other hand, the results seem to suggest that other attacks are also considered. Could you clarify what types of attacks are considered in the paper? \n\nb. The optimization problem (Q) seems to be different from the ones studied in (Ma et al. 2019) and (Rakhsha et al. 2020). Could you elaborate on the differences between these attack formulations? How does your setting relate to the setting of (Zhang and Parkes, 2008) in terms of computational complexity? \n\nc. The budget constraint (c) in optimization problem (Q) assumes that the 'cost' of an attack is either 0 or 1, whereas the constraint (d) already limits the 'power' of the attack. Could you explain the practical importance of imposing these two constraints together?  \n\nd. Which practical application would support the episodic poisoning setting described in this paper?\n\ne. How exactly is the pseudo-learner defined in this paper (e.g., in Section 5)?", "extra_scores": {}, "extra_text": {}}, {"review_id": "muhv0PEoaJY", "reviewer": "AnonReviewer2", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies a very important problem of poisoning attack against RL when the attacker is not omniscient. This is an important next step, as most prior work assumes omniscient for the sake of a more rigorous theoretical understanding (e.g. Rakhsha et al., 2020, Zhang et al. 2020).\n\nHowever, the approach taken by this paper is too heuristic and only applies to a very limited setting where \nthe learner needs to perform **on-policy** policy gradient methods, which no STOA algorithm does due to its poor sample efficiency, so there isn't much empirical value.\n\nAt a high level, the approach this paper takes can be summarized as follows: It defines the optimal poisoning attack problem in an unknown environment as a **sequential decision making problem**, which is well-motivated and clear. It then proposed to simply use a **greedy algorithm** that only optimizes the current step's cost without caring about what happens in the future. Then, of course, the greedy attacker doesn't require the knowledge of the environment's transition. Even if the attacker does know it, it wouldn't be using it anyway, because it only cares about the current step. \n\nAnd prior work has already shown that in the online data poisoning context, the greedy strategy can be **exponentially worse** than the optimal attack strategy. See [1].\n\nSome technical questions:\n\n1. Correctness of Proposition 2: In the Remarks of section 4.1. It is mentioned that the value difference of two policies differed by at most delta in total variance distance will also be bounded by $poly(\\delta, 1/(1-\\gamma))$. I didn't check the proof thoroughly but I feel that there are counter-examples?\n\nConsider the classic \"combination lock\" MDP, where states form a chain of length H, and there are two actions in each state: the \"right\" action moves you right to the adjacent state, and the \"left\" action teleports you back to the starting state (the left-most state). All rewards are zero except for when the agent successfully arrives at the right-most state, which takes H right actions consecutively. Now, the optimal policy (always go right) will have value $1$. But a $\\delta$-perturbed policy which now has $\\delta$ probability of going left will only have value $(1-\\delta)^H$ (assuming a fixed episode length H and no discounting). So the gap seems to be exponential rather than polynomial. How does this example fit into the conclusion of proposition 2?\n\n2. About adversarial critic: What exactly is this $\\tilde V_\\omega$ estimating? Is it estimating the value of the optimal policy, the learner's current behavior policy, or the learner's current $\\hat\\pi_k$ which according to the paper is different from the behavior policy? If it was the latter two, how does the attacker keep track of the value of an ever-changing policy, and how does he use this value estimate to evaluate the value of some other potential poisoned policy? It's all very confusing.\n\n3. The estimated rank in step 6 of section 4.3 is only unbiased if the policy discrepancies $\\hat \\psi_k$ are *i.i.d.*, which they clearly are not.\n\n\n\n[1] Xuezhou Zhang, Xiaojin Zhu, Laurent Lessard. Online Data Poisoning Attack. L4DC 2020.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "fcmTIw-N-5T", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper studies poisoning attacks against online reinforcement learning agents. The attacker has the power of manipulating the training data, i.e., state-action-reward trajectories, in order to achieve some attack goal. The attack can be completely black-box, meaning that the proposed method allows an attack setting where the attacker has no knowledge of the RL algorithm used by the victim agent or the environment. In this scenario, the authors proposed that the attacker can imitate the learning procedure of the victim, and then based on the imitated policy; the attacker designs how to poison the training data. The attack is formulated as a bi-level optimization, where the lower level involves the imitated learning procedure. Due to the intractability of sequential optimization, the original formulation is simplified so that only the attack only solves the attack on the current training data. This procedure is repeated in every episode to achieve sequential attacks. Experiments on a variety of tasks demonstrate the superiority of the proposed attack.\n\nCompared to prior works, the main advantage of this paper lies in that the attack can be applied in more complicated tasks where state or action space is continuous. Furthermore, the attack takes into account the adversarial effect of the current attack on future behavior of the victim agent. Therefore, the attack achieves better overall performance (e.g. more times of target-action selection) than traditional gradient-based attack such as FGSM.\n\nAnother strength of the paper is that it provides some theoretical analysis in terms of how the relaxed optimization approximates the original complex attack optimization. This is in general a hard question to answer. Although the analysis is only about attack feasibility and how to test sub-optimality in hindsight, there is value in deriving those theoretical results.\n\nThe experimental part of the paper is also strong. The authors have shown convincing results that demonstrate the proposed VA2C-P attack outperforms existing gradient-based FGSM attacks. Moreover, there are systematic empirical investigations on how the attack constraint parameter epsilon affects the attack performance.\n\nFinally the paper is well-written and provides a nice summary of prior works, as well as why each prior work fails to achieve some desired property of attack in an ideal sequential attack scenario. Therefore, overall I think the paper is nice and makes significant contribution.\n\nOne disadvantage of the paper is that while the paper claims able to handle sequential attacks, the relaxed attack optimization seems solving only the desired manipulation on training data in the current episode. As a result, the solution is definitely sub-optimal. The authors provided a method of evaluating whether the implemented attack is sub-optimal in hindsight, specifically the proposition 7. This result, while being interesting, is not useful in that it cannot help practitioners gauge if the computed attack is optimal or not, since it’s a necessary condition. I am wondering if the authors could provide some insight on how sub-optimal is the attack in this paper, and potential ways to further improve it.\n\nI also want to point out that the attacker knowledge assumed in this paper is not strictly less than prior works such as in Zhang 2020. Both need to have access to a simulator of the MDP and victim environment, and both need to exhaust large amount of training data before obtaining a good attack policy. In this paper, the attacker needs to imitate the victim learner, and the accuracy of imitation result will depend on how many training data are available.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "Mj-5dSBKkIA", "reviewer": "AnonReviewer3", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nThis paper proposes a poisoning algorithm named Vulnerability-Aware Adversarial Critic Poison (VA2C-P) to attack policy-based deep reinforcement learning agents. The poisoning attack is formulated as a sequential bilevel optimisation problem (Problem Q), where the attacker either minimises the expected total rewards of the learner (non-targeted poisoning), or forces the learner to learn a target policy (targeted poisoning). To solve Problem Q, VA2C-P mainly makes two decision: (1) when to attack: a new metric named stability radius is proposed to decide the attack timing, (2) how to attack: a mechanism of adversarial critic is designed to solve a relaxed version of Problem Q by only considering the loss of the immediate next iteration.\n\nPros:\n1. It is an important question to investigate how policy-based RL algorithms can be poisoned by adversarial attacks.\n\n2. It is novel to propose a poisoning method against policy-based RL agents, which has not been studied before.\n\n3. The proposed poisoning framework (Problem Q) is a general formulation that covers a variety of models.\n\n4. VA2C-P has been demonstrated to be effective in targeted and untargeted attacks, under both white-box and black-box settings.\n\nCons:\n1. This paper considers a scenario where (1) “the attacker does not know the underlying dynamics of MDP, and cannot directly interact with the environment, either”; (2) the attacker is able to obtain the states observed by the agent, their actions and rewards. Is (2) a realistic setting? Especially, how is the reward accessible to the attacker?\n\n2. The black-box attack studied in the paper is closer to white-box attack than to black-box attack: the attacker can still access the past and current observations (state + action + reward), and the only limit is that the policy $\\pi$ of the target model is unknown. This type of black-box attack is unrealistic in many situations.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper focuses on adversarial attacks for RL, which is an exciting understudied research direction, and can be of interest to the community. All the reviewers are (mildly) positive about the paper and the author competently replied to the concerns expressed by the reviewers. 
Decision: Accept (Poster)