Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the problem of certifying a policy learned via an offline RL algorithm is robust to poisoning attacks. The authors propose two certification criteria: per-state action stability and lower bound of cumulative reward. Three different protocols are proposed, although they all based on ensembling / aggregation of sub-policy decisions. For the certification of cumulative reward, a tree-based search approach is given that evaluates all possible actions within a set. Experiments on Freeway and Breakout for a few different offline RL algorithms are given, showing Freeway can be certified to be robust to poisoning attacks for a large poisoning threshold, while Breakout cannot.


main_review: Generally, the paper was well-written, although there are some organisational problems I would like to see addressed. As the authors mention, although poisoning attacks are major concern in practical settings, one may argue they are under-researched compared to test-time attacks. As far as I am aware, this is the first paper that proposes methods to certify an RL algorithm is robust to poisoning attacks, and the results look convincing. I will go through each of my main concerns / questions / misunderstandings below in no particular order:


1. What is the motivation for developing three separate aggregation protocols? From the experiments, TPARL and DTPARL provide similar certification results. I would suggest the authors choose to present one protocol and defer the other two to the appendix, it would dramatically improve the readability of the work.


2. As far as I understand, the number of sub-policies, *u*,  that need to be trained needs to be *at least* as large as the number of poisoned action-states / trajectories, *K*. Given that in offline RL one has a finite dataset to learn a policy on, what is the affect of varying *u* on the quality of these learned sub-policies? The certification method is dependent on some level of agreement between sub-policies, but if *u* needs to be very large will this not increase sub-policy variance? It seems from Appendix H.1 this is not true for *u*=30, 50, but it would be useful to show the utility and certification over a larger sweep of *u*.


3. TPARL and DTPARL are based on the insight that not all states are created equal, and bottleneck / critical states are more important from a poisoning perspective. How much variance in window size is there for DPTARL? I'm interested in this because although the worst-case complexity is based on *W_max* should one not expect average certification time to be much smaller if the average window size is << *W_max*?


4. Related to (3), it is claimed that certification time complexity *per state*  "in practice adds negligible overhead compared with standard network policy inference.". Maybe I missed this but I couldn't see any empirical results that back up this claim. The complexity looks like a bottleneck to me, being quadratic in the space of actions and linear in *u*. The latter is perhaps to be expected since this essentially says that if one wants to certify a policy is robust to a large adversarial poisoning budget, it will take more time than certifying against a smaller budget.


5. The COPA-search algorithm is not clearly presented. Could the authors comment of the time-complexity of the search as I had trouble understanding this part.


6. Could the authors comment on why QR-DQN and C51 are more certifiably robust than DQN? Initially I thought this may just be because they achieve higher utility but this is not the case (according to Appendix H.1)


7.  How were the trajectory lengths chosen in Section 4.2?


8. What is the intuition behind why Breakout is less stable than Freeway? Does it contain more critical / bottleneck states? It would have been very useful to perform a deeper analysis of robustness to poisoning attacks wrt bottleneck and non-bottleneck states.

9. Could the authors comment on the relation between this work and [1]? Although the goals are different it feels like there is a surprising amount of overlap for an uncited paper: the name and organisation are similar, algorithms for per-state and cumulative reward certification are given, and are evaluated on similar datasets.

[1] Wu et al. CROP: Certifying Robust Policies for Reinforcement Learning through Functional Smoothing. 2106.09292
summary_of_the_review: Overall, I think this work represents a solid contribution to the field of robustness certification and RL, against what some may consider a more practical adversary than in evasion attack settings. There are a number of subtle algorithmic and experimental points that I would like the authors to clarify before raising my score, such as the complexity of COPA-search, and a more in-depth analysis of robustness to poisoning critical / bottleneck states over non-bottleneck states. I feel like this is a key point to address as it will provide stronger evidence of the deltas between the different aggregation protocols.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a certification method against poisoning attacks in offline reinforcement learning, where attackers can manipulate a subset of the training trajectories. It presents two certification criteria: per-state action stability and cumulative reward bound. It also introduces different aggregation protocols to train the policies and provides some bounds regarding the certification. In addition to theoretical results, it also has ablation studies to identify the implications of different parameters. 
main_review: Strengths:

1. The paper is well-written. It clearly states its main contributions and the intuition of the techniques used in  COPA.

2. The paper proposes a certification framework against poisoning attacks in deep reinforcement learning, which is non-trivial. It advocates two certification criteria: per-state action stability and lower bound of cumulative reward.

3. For each certification criteria, it provides bounds for different proposed aggregation protocols.

4. In addition to theoretical results, the paper also presents numerical results.


Weaknesses:

1. I appreciate the authors' providing numerical results and the theoretical studies. However, it is unclear to me to what extent the introduction of the proposed method degrades the training of the RL algorithms (in terms of convergence speed and policy quality).  In particular, how does the proposed method perform compared with vanilla DRL algorithms when there are no adversarial attacks?  

2. While the paper claims that "there is no robust RL method that is able to provide practically computable certified robustness against poisoning attacks,"  it might not be accurate.  There are a few related works on certified robustness in DRL.  For instance, "Certifiable Robustness to Adversarial State Uncertainty in Deep Reinforcement Learning" by Everett et al., and "CROP: Certifying Robust Policies for Reinforcement Learning through Functional Smoothing" by Wu et al..  Though the exact settings could be different, the authors might want to compare the proposed method with the existing literature. 

summary_of_the_review: Solid work with minor issues that can be fixed.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a defense method against poisoning attacks in offline RL. The authors propose a framework named COPA to certify the number of tolerable poisoned trajectories. The proposed defense includes a partitioning stage which separate the (possibly poisoned trajectories), a training stage where $u$ sub-policies are trained with $u$ partitions,  and an aggregation stage where the sub-policies are aggregated to produce the final policy. Three aggregation protocols are proposed with corresponding certification results.
main_review: Strengths:

1. The studied problem, certifiable defense against poisoning in offline RL, is important to the community. As far as I know, this is the first method in certifying both per-state action stability and cumulative reward against offline poisoning attacks in RL.
2. The problem setup is clearly stated. The authors provide analysis for 3 aggregation protocols, which could be helpful for understanding the  partition-aggregation based methods in RL.
3. The experiment compares several deep RL methods in terms of their intrinsic vulnerability, which is interesting.  

Weaknesses:

1. For writing:

(1) Many details and definitions that are essential for understanding the method are omitted to the Appendix, which makes the flow of the paper not very smooth, especially in Section 3. 

(2) I don't see the necessity of separately discussing 3 aggregation protocols in the main paper. The 3 methods do not differ by a lot. The empirical results in Figure 1 and 2 also show that they do not have significant differences. Discussing all 3 protocols separately results in the weakness mentioned above -- too many details are omitted in the main paper. I would like to see the authors focus on the most interesting one in the main paper and provide detailed explanations, then put the other two variants to the Appendix.

(3) Some notations are not very clear. For example, $K_t$ is not defined in or before Theorem 1. Does it mean the poisoning threshold such that the action in the $t$-th step does not change? What is $p$ in Theorem 1? What is the argmax operation in Equation 3 maxing over? This is the most important result in the paper, but the presentation is really confusing.

2. For the proposed algorithm:

(1) The temporal continuity assumption does not seem to be a standard one in RL literature. Can the authors justify how realistic this assumption is?

(2) I am very confused by the COPA-SEARCH algorithm. Why can the learner search in the MDP in the offline setting where the agent is only supposed to have access to a set of trajectories? For example, in Algorithm 5 Line 24, the learner directly queries the transition function P for the next state of $s_t,a$. The Input of Algorithm 5 also requires the environment $\mathcal{E}$. If the algorithm requires to query the environment arbitrarily, the algorithm does not make any sense. If you already know the MDP dynamics, the poisoning in trajectories do not matter at all. This is the biggest concern I have. Please let me know if I missed any important statement.

3. For the evaluation:

(1) The authors compute the certified poisoning threshold $\bar{K}$, but do not present the number of total trajectories. 

(2) The experiment results are not convincing. Deep RL training requires a large number of trajectories (millions of interactions), but the certified $\bar{K}$ provided by the proposed method is too small (around 10) based on Figure 1. That is, the defense method is too weak. In the cumulative certification, there is no comparison between the performance of the proposed method and the vanilla training method under practical poisoning attacks, so that we do not know how good the method is in terms of practical defending. There is only the result of the computed reward lower bound in Figure 2. More importantly, the certified lower bounds are too low, and become vacuous (lower bound=0) when $K>10$ or $K>5$. A normal DQN agent in Breakout should get >300 rewards. But the lower bound is 0~2, which does not make much sense, because the reward in Breakout is no smaller than 0.

4. Some related works are missing. For example, [1] also proposes a defense method agains poisoning attacks, although in a different setting. It is worth mentioning this work and discussing the differences between the settings of this paper and [1].

[1] Banihashem, Kiarash, Adish Singla, and Goran Radanovic. "Defense Against Reward Poisoning Attacks in Reinforcement Learning." arXiv preprint arXiv:2102.05776 (2021).
summary_of_the_review: This paper studies an interesting and important topic, and the proposed method makes intuitive sense. However there are many flaws in terms of writing, algorithm assumption, and empirical results. So I do no think this paper can be accepted before a major modification is made.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper studied how to certificate a policy when the training dataset is partially corrupted in the offline reinforcement learning scenario. Two criteria including per-state action stability certificate and cumulative reward lower bound certificate are proposed. Based on these two criteria, the paper designed the COPA, a general certificate framework, which provably achieved certain level of certificate. The COPA went through two phases during training, where in the first phase, the trajectories are split into subsets of equal size, then sub-policies are trained on each subset, and finally the sub-policies are aggregated to form a single learned policy. Experiments demonstrate the effectiveness of the proposed COPA certification framework. 
main_review: Strengths:

(1). This paper is the first to study policy certification for offline reinforcement learning. Given that "poisoning attacks in RL" is a popular recent topic, this paper is able to push the frontier of this research line even more and open potential future research questions.

(2). The paper provided a systematic theoretical study of policy certification based on two criteria --- per-state action stability and cumulative reward lower bound. Both criteria are sensible since they characterize the objective of general RL tasks. The theoretical results can provide guidance for designing robust RL algorithms in the future research.

(3). Experiments consolidated the theoretical findings in this paper.

Weaknesses:

(1). The idea of splitting the training set into subsets and then apply aggregation on sub-policies trained on each subset is not surprising, and has been studied a lot in previous works, e.g., in [1]. Therefore, the technical contribution of this paper seems a little bit weak, although it studied a new problem.

(2). The applicability of the COPA certification framework is limited in the sense that it only applies to poisoning attacks where the attacker poisons a small fraction of training trajectories. However, an attacker may be able to slightly perturb all trajectories without incurring much effort. For example, the attacker just need to change the data point of a single step (e.g. the first step) in each trajectory, and that already breaks the assumption made in this paper. With all that, I mean the attacker ability is very weak and the certification against weak attackers is not a strong certification.

(3). Another disadvantage of the paper is that the theorems involves very intensive symbols, which can be confusing to readers. The authors should consider adjusting how the results are stated to make it super clear.

(4). Very related papers are missing in the reference. To list a few, please see [2-4]. The authors should discuss them in the related work.

[1] Certified Robustness of Nearest Neighbors against Data Poisoning Attacks
[2] Policy poisoning in batch reinforcement learning and control
[3] Vulnerability-aware poisoning mechanism for online rl with unknown dynamics
[4] Deceptive reinforcement learning under adversarial manipulations on cost signals
summary_of_the_review: Overall, I think the paper studied a very important and interesting problem, but the paper needs to be improved in writing, related work, and discussions on potential weakness of the COPA framework.
review_title: null

Meta-review: The authors develop a novel framework for certifying the robustness of RL agents against data poisoning attacks. They obtain lower bounds on the cumulative reward for several benchmark tasks.

Reviewers had concerns about certain organizational and technical aspects of the paper, but these were addressed well in the discussion phase and author responses. Hence, I recommend acceptance. However, I would urge the authors to incorporate points from the discussion phase into the revised version, in particular the discussion with reviewers xuEG and RQX2.
Decision: Accept (Poster)