Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: #### Summary:
The 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.   

#### High level comments (pros & cons):

-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.   

-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. 

-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.

-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.  

Overall, 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.  

#### More specific comments and suggestions for improvement:

-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. 

-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. 

-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. 

-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. 

-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. 

-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. 

-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.  

The paper also contains minor typos, e.g.: 
- the test-time evasion attacks Chen et al. (2019) where the attacker crafts -> citation style
-alter the environment (e.g. change the transition probabilities) ,  -> remove space before ,
-On the contrary, We consider non-omniscient attackers - 'We' should be 'we'
-'a learner gains from the environment, i.e., $O = (O^s,O^a,O^r)$' -> Is $O^a$ observed?
-Compared with Problem ( Q), -> ( Q) should be (Q)
-The solution to Problem (P) is always feasible to Problem (Q, although... -> e.g. (Q should be (Q)
etc.


#### Questions: 

a. 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? 

b. 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? 

c. 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?  

d. Which practical application would support the episodic poisoning setting described in this paper?

e. How exactly is the pseudo-learner defined in this paper (e.g., in Section 5)?
review_title: Official Blind Review #4

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summary:
This 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.

Pros:
1. It is an important question to investigate how policy-based RL algorithms can be poisoned by adversarial attacks.

2. It is novel to propose a poisoning method against policy-based RL agents, which has not been studied before.

3. The proposed poisoning framework (Problem Q) is a general formulation that covers a variety of models.

4. VA2C-P has been demonstrated to be effective in targeted and untargeted attacks, under both white-box and black-box settings.

Cons:
1. 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?

2. 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.
review_title: A novel poisoning method against policy-based RL agents

final_score: rating: 7: Good paper, accept
review_content: 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.

Compared 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.

Another 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.

The 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.

Finally 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.

One 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.

I 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.

review_title: Review for Vulnerability-Aware Poisoning Mechanism for Online RL with Unknown Dynamics

final_score: rating: 6: Marginally above acceptance threshold
review_content: 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).

However, the approach taken by this paper is too heuristic and only applies to a very limited setting where 
the 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.

At 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. 

And 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].

Some technical questions:

1. 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?

Consider 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?

2. 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.

3. 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.



[1] Xuezhou Zhang, Xiaojin Zhu, Laurent Lessard. Online Data Poisoning Attack. L4DC 2020.


review_title: A good attempt on poisoning RL in unknown environments, but the algorithm is too heuristic and limiting.

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)