Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper presents a new attack framework on Reinforcement Learning systems that modifies the action taken by the agent without the agent noticing in order to make the agent learn the policy that the adversary wants with high probability.
main_review: Overall, the paper has good technical content but I have the issues stated below:

The threat model seems contrived and overly powerful - I am not sure how it would ever be possible for an attacker to completely swap out actions taken by an agent with completely different actions. In an MDP setting, it seems easy to identify that a less than optimal policy is in place (RL policies have the advantage of being able to learn even after deployment), and as mentioned later, so I am not convinced how broadly applicable the ideas are to the RL setting. 
Also, why wouldnt such an adversary sitting between the agent and the simulator also be able to modify any observation? The authors claim that modifying observations is more powerful than actions; this is stated without any evidence (mathematical or empirical); this may not be true for some problems and some prior work restrict the modification in observations.

The white box attack is very simple and could be compressed a lot in presentation.
Perhaps more standard or complex settings for tabular episodic MDPs would help us evaluate the validity of the results more effectively than the very simple synthetic set-up.

Generally the paper could read better and has language issues, some examples include (line 21 "applicants" vs. "applications", Figure 1 contains typos ("Tiem step" vs Time step).

-------Post Response-------- 
I increased my score as the threat model was well explained in response. 
limitations_and_societal_impact: Yes, but would have been good to propose at least a basic defense.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes a new action poisoning framework to mislead the agent to learn a target policy. In a white-box setting, the paper introduces $\alpha$-portion attack that is guaranteed to conduct a successful attack with sublinear cost. In a black-box setting, the paper proposes an adaptive attack scheme called LCB-H that nearly matches the performance guarantees of the white-box attack method. With a case study on attacking UCB-H, the authors show that the proposed attack strategy can manipulate the learner with a logarithm cost, matching the main claim of the paper.
main_review: The authors formally define and discuss action poisoning in multiple settings. The idea of attacking with the lower confidence bound is novel. The proposed action poisoning attack can deal with a practical black-box scenarion with log(T) cost, which is an interesting and significant contribution. The paper is in general well-written and easy to follow. The assumptions and limitations of the work are clearly stated, so it is easy to know the scope of the work.

My main concerns are: (1) how realistic are action poisoning attacks? Although the paper motivates the action attacks with auto-driving systems, the algorithm and analysis are built on a tabular case, where I find action attacks not very practical and easy to be detected. 
(2) the cost of the poisoning algorithm, although is logarithm in T, has a high dependence on H, and would be large as the target policy is closer to the worst policy. Does it suggest that the algorithm becomes impractical when the horizon is long and when the target policy is close, though not equal, to the worst policy? 
limitations_and_societal_impact: The authors have explicitly discussed the limitations of the work in Section 5, as well as some future directions in Section 6. I would be curious to see how the proposed algorithm applies to state or reward poisoning, and a large-scale environment with function approximation.
review_title: null

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

To my knowledge, this is the first paper to formally study action poisoning attacks in episodic tabular RL. That being said, [Sun et al. 2021] discuss/study different 'poisoning aims' including poisoning actions (see Section 3.3.1). In that sense, some of the claims in the paper do not seem to be precise, e.g., 'Prior works on adversarial attacks in RL mainly focus on either observation poisoning attacks or environment poisoning attacks'; the same is true for the claimed contributions. Other related work is generally covered well, but could be expanded with a few more references. For example, while the introduction mentions more than 10 references on adversarial attacks in supervised learning, test-time attacks in RL are not covered to a great extent. There are also references on poisoning attacks in RL that could be added, including some older works on policy teaching, e.g., Zhang and Parkes 'Value-Based Policy Teaching with Active Indirect Elicitation'. 

b. Quality

The paper studies an important topic and highly relevant for designing robust RL systems. The results are interesting as they provide a principled way of designing action poisoning attacks in tabular RL setting. On the other hand, it is not clear how practical the proposed approach is. I also have some concerns/questions about the modeling assumptions. 

b.1.  The paper claims that this form of poisoning attacks is more practical than other forms of poisoning attacks, and the arguments are based on 'restrictiveness' ('Compared with existing attack models, the attacker’s ability in the proposed action poisoning  attack model is more restricted, and hence the attack model is more practical. '). I don't see why 'restrictiveness' would necessarily imply that the attack is more practical. Whereas action poisoning could be prevented by increasing the security of the agent, poisoning rewards might not be since rewards can be external to the agent (e.g., feedback in the recommender systems). In this sense, action poisoning might not be practical at all in some settings since it assumes a (partial) control over the agent. 

b.2. The overall goal could be more clearly specified and ideally formulated as an optimization problem. In Section 2, we have 'The attacker aims to minimize both the attack cost and the loss of attacks, or minimize one of them subject to a constraint on the one another.'. However, it seems that the true goal is to have provable upper bounds on the cost/loss of attacks. The paper could also motivate the cost/loss function. E.g., in the car driving scenario from the introduction, why would it be more costly to manipulate the signal N times than M times? Why wouldn't we model the loss of the attacker through its own reward function?  

b.3. The proposed algorithm looks interesting and has provable guarantees on its performance.  It is less clear whether the bounds are tight and/or informative for practical purposes. For example, some of the bounds have dependency on $H^10$ (Theorem 3), which means that even for smaller values of $H$, the bounds are quite large. The arguments regarding UCB-H and Theorem 3 are somewhat unclear. Theorem 2 considers dynamic regret, whereas the arguments are based on the results from [Yang et al., 2021], which seems to consider the notion of regret similar to (4). 

b.4. Experiments are relative simple, which is not surprising given that this is a theory paper. However, the running times indicate that the proposed approach might not be scalable. It is generally hard to follow the details in Section 4: Figure 1 has typos (Tiem -> Time?), y-axis is not labelled (and represent multiple measures), and the font is too small, the text mentions three agents, but it doesn't explain which ones (presumably, these are the agents in the subtitles of Figure 1?). 

c. Clarity
 
The paper is enjoyable to read. However, there are many typos and some parts could be improved and explained in more detail. A few examples: 
- The statement of Lemma 1 is not clear: what does it mean 'in the observation of the agent'?
- In Section 4, the statements 'Ten states can be considered as a circle' and 'sampled randomly from the five adjacent states' are not clear.  
- The organization could be improved as well. For example, Assumption 1 and Eq. 4 could be a part of the setting (otherwise, it's not clear whether this assumption applies to Section 3.1 only). In Section 2, the claim is that the performance of the agent is measured with regret as defined by (2), but then in Section 3.2 we have a different notion of the regret. 
- What is $\pi_{h}^{-}$ in line 219? 
- The notion of behavior policy $b_k$ could be explained before being used in 246.  

d. Significance

In my opinion, these results will be interesting to researchers working on adversarial attack in RL, and more specifically on poisoning attacks. The work is mainly theoretical, but some of the principles presented in the paper might lead to practical solutions. Compared to prior work, the paper studies a different setting and orthogonal aspects of poisoning attacks. Overall, I believe that the paper provides a good starting point for formally analyzing action poisoning attacks.
limitations_and_societal_impact: The limitations are stated in Section 5. Potential societal impacts are discussed in the introduction.
review_title: null

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

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