Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This work proposes a certification (CROP) attesting that a policy is robust against adversarial state perturbation. It finds its inspiration in the supervised learning literature and extends it to the sequential decision-making setting. Experiments on two Atari games test the performance of CROP.
main_review: *Originality*

This work essentially extends robustness certification methods existing in supervised learning, to reinforcement learning. Although the idea of certification is new, the essence of robustness guarantees together with function perturbation is not new in the RL literature. As such, some significant literature review on robust MDPs and robust RL is cruelly missing.

*Quality*

Essentially, the two proposed certificates are based on a state perturbation to which either the Q-function or the policy is applied. As far as I understand, this does not affect the model itself but only the ordering in either the Q-values or the policy. As a result, this discredits the certificate.
l. 47-53: the results obtained from CROP are problem-dependent. This may say something about the domain, but also about the certificate itself and how reliable it is. It is not clear which one of the two options applies.
CROP designs a certification for the robustness of other previous algorithms, but the very method is not challenged in and of itself. Instead, in Sec. 6, it is shown how robust are different methods but the reliability of CROP itself is not tested.

*Significance*

Overall, I find several problematic issues in this work. On a higher level, the fundamental RL question is not "how to certify robustness" but rather "how to attain robustness". Thus, I disagree with the leading direction of that paper and am not sure how relevant it would be for RL researchers. Also, a comprehensive RL review and robustness in RL is strongly missing.

*Clarity: Minor comments*

- l. 5 "smoothed with Gaussian noise": these are "perturbed" rather than "smoothed" ("smoothing" is used for making a function continuous or the like)
- l. 14 "RegPGD, RegCVX, RadialRL": those methods have never been described before, nor are they explained
- l. 120, 121, 131 "per-state action": you may just use "policy" instead
- l. 128 : Notation never introduced for those bounds. If these are reward bounds, then a  factor seems to be missing
- l. 113-114: I do not understand the justification for focusing on a finite horizon.
- l. 101 the maximum perturbation magnitude is uniform over the state-action space. Would not it be tiny then? How reliable would the certificate be if that radius gets close to 0? Also, a state-dependent  appears in Thm 1. This is confusing, or it should be discussed whether/when one would consider uniform VS state-dependent magnitude.
- Thm 1- Notation is confusing. It refers both to the immediate reward (l. 72) and a radius ball in Thm 1.

*English corrections*

- l. 1 "Certifying Robust Policies for reinforcement learning (CROP)" --> "Certifying Robust Policies (CROP) for reinforcement learning (RL)"
- l. 5 "which uses" --> "that uses/using"; l. 9 "which makes use" --> "that uses/using"
- l. 10 "for reward" --> "for the reward"/ "for performance"
- l. 15 "we demonstrate that ... by evaluating ..." --> "by evaluating ..., we demonstrate that ..." (revert)
- Remove "the" in l. 29, 30, 31, 38, 83, 398
- l. 25 "In particular, adversarial training ... by enforcing the smoothness of the trained models"--> "In particular, by enforcing the smoothness of the trained models, adversarial training... " (revert)
- l. 27-28 "have been proposed", "it is" - time concordance
- l. 31 "deterministic approaches" --> remove "approaches" (appears in l. 32)
- l. 32 "the lower bound" --> "a lower bound"
- l. 34 "compared with classification model" --> "compared to classification"
- l. 37 "Compared with" --> "Differently than"
- l. 37 "classification model" --> "classification"
- l. 37 "which only has one-step predictions" --> "which involves one-step prediction only"
- l. 37-38 "both ... as well as ..." --> "both ... and" or just "as well as"
- l. 39 remove "of RL"
- l. 48 "game properties" --> "the game properties"
- l. 84 "will be" --> "is"
- l. 94 "following" redundant
- l. 105, 399 "reinforcement learning" --> "RL" (use abbreviation consistently -- or never use it)
- l. 121 "to calculate the lower bound of maximum perturbation magnitude in Def 1" --> "to calculate a lower bound of the maximum perturbation magnitude from Def 1"
- l. 126 "the Gaussian distribution" --> "a Gaussian distribution"
- l. 140 "the tradeoff" --> "a tradeoff"
- l. 400-403 A 3-line section is a bit weird

*Missing references on robust RL (to name a few)*

[1] Iyengar, Garud N. "Robust dynamic programming." Mathematics of Operations Research 30.2 (2005): 257-280.

[2] Nilim, Arnab, and Laurent El Ghaoui. "Robust control of Markov decision processes with uncertain transition matrices." Operations Research 53.5 (2005): 780-798.

[3] Tessler, Chen, Yonathan Efroni, and Shie Mannor. "Action robust reinforcement learning and applications in continuous control." International Conference on Machine Learning. PMLR, 2019.
summary_of_the_review: By construction, robust policies (i.e., those that solve max-min objective in robust MDPs) provide a robustness certificate that is more general than the two criteria provided in Def. 1 and 3. As such, I see this study as a specific case of prior work.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper introduces CROP, a framework for the certification of reinforcement learning (RL) agents against (adversarial) observation/state perturbations based on randomized smoothing (RS). Formally, certificates for individual per-state decision as well as cumulative scores are distinguished.
In order to obtain a per-state certificate the authors introduce CROP-LoAct, which applies RS to the individual decision of the agent on each state.
For cumulative-score certificates two approaches are considered:
First, CROP-GRe which applies RS to the return function of a whole trajectory and obtains a bound either via mean smoothing or percentile smoothing.
Second, CROP-LoRe, which combines per-state certificates for a whole trace to obtain a score certificate. Via tree-search a lower bound for a given start state and base policy can be provided.


main_review: The paper provides a comprehensive study of the RL robustness in the per-state setting as well as a per-trace setting. I am delighted to see interesting work beyond per-state certification in the RL setting.
Furthermore, the mathematical parts are well written and can be followed easily.

However, I am wondering about several aspects of the submission, which I hope the authors can clarify:
- Can you justify the claim to be the "first framework for certifying the robustness of Q-learning algorithms", given works like [2,3] and others exist? ([3] is even discussed in the text.) Granted, with the exception of parallel work, this is the first paper to look at the certification of traces rather than just per-state decisions.
- Can you elaborate on the inference/prediction procedure for the agents in all CROP settings? The text outlines only the certification. Is it sufficient to invoke the model with a single sample of Gaussian Noise at each step in inference, or is a procedure like Predict in [1] used?
  As I understand (2), at least for CROP-LoAct this is the case.
- I am generally confused whether CROP aims to be a testing-framework or a certified defense. Mathematically, sections 3-5 present a certified defense (e.g. something that is a applied to a base model) to obtain certifiable guarantee.
  Yet, sentences like "... we find that (1) RegCVX, RegPGD and RadialRL achieve high certified robustness..." or "As the first work providing robustness certification for RL, we expect more RL algorithms and games will be certified under our framework in future work." make CROP look like a testing/certification framework. This compounds with the fact that inference is not discussed (see previous question), as it seems one can just run a RadialRL model without further considerations to obtain the robustness guarantees outlined here.
- Does CROP-LoRe account for multiple-testing? Since the individual local certificates only hold with confidence $1-\alpha$ (which according to E.4 you choose as 0.05), a CROP-Lore certificate invoking N local certificates holds with at most confidence $1-N\alpha$.
- Why does CROP-LoAct not rephrase picking the action as a classification problem and directly apply the approach from [1], thus sidestepping the challenges outlined in 4.2? Is it because you rely on this form of certificate in CROP-LoRe?
- Does CROP-LoRe need access to an oracle transition function $\Gamma(s, a)$ which can execute the transition for a given $s$? If this is the case this seems a departure for the standard RL-setting where the environment can only be queried in a fixed temporal order. While I think this is perfectly fine for the considered purpose, such a departure from standard should be clearly indicated.
- Does Lemma 2 hold if the adversary can arbitrarily choose $\zeta_{t}$ based on the smoothed actions at steps $0, \dots, t$? It seems to me the presented Lemma 2 only holds if the attacker commits to the values of $\zeta_{t}$ beforehand.

While I like the high-level approach and I think its a valuable area of investigation, I am not convinced by the presentation and potentially technical correctness (see questions) of the current submission. Further, it appears that recently a pre-print [4] was introduced, which concerns a similar topic. Could you briefly comment on the difference in approach. 

Minor:
- There is a hyperlink (from a citation) crossing a page boundary at the end of the first page, which leads unpleasant artifacts.
- The symbol used for smoothing noise seems to change between $\zeta$ and $\Delta$. If this is deliberate, I may have missed why.

[1] Certified Adversarial Robustness via Randomized Smoothing, Cohen et al.; ICML 2019

[2] Online Robustness Training for Deep Reinforcement Learning, Fischer et al.; arXiv 2019

[3] Robust Deep Reinforcement Learning against Adversarial Perturbations on State Observations, Zhang et al., NeurIPS 2020

[4] Policy Smoothing For Provably Robust Reinforcement Learning, Kumar et al., arXiv 2021
summary_of_the_review: A conceptually interesting approach to the verification of reinforcement learning in the per-state setting and beyond. However, the current manuscript leaves open questions about conceptual decisions and formal correctness.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes two robustness certification criteria for Q-learning based RL policies under adversarial state perturbations: per-state action robustness and lower bound of cumulative rewards. The certification is mainly based on the randomized smoothing technique. For certifying the cumulative reward, two smoothing methods (global smoothing and local smoothing) are presented with different lower bound formulations. With the proposed smoothing methods, the authors empirically evaluate and compare 6 robust RL approaches in 3 environments, showing the applicability of the proposed method.
main_review: Strengths:

1. This paper is well-written. The formulations are clear and easy-to-follow. The algorithm and experiment settings are discussed in detail in Appendix.
2. The certification makes intuitive sense, and seems to be correct, although I have not checked the detailed proof.
3. Both per-state action certification and cumulative reward certification are provided, while most related works do not discuss the reward certification.
4. The experimental results are interesting. The author provide a leaderboard that shows the comparison of many robust RL algorithms in different settings, which could be helpful for the evaluation of robust RL methods.


Weaknesses:

1. The certifications are straightforward application of the randomized smoothing certification used in supervised learning, which is not surprisingly novel. But different from supervised learning, the certified radii in this paper involve $V_{min}, V_{max}$ and $J_{min}, J_{max}$ which can be hard to obtain in practice, and may make the bound vacuous. The authors have provided methods to address the challenge of estimating these terms, but it also seems to be expensive. 
2. The certifications on cumulative reward seem to be a little naive, and too expensive. The global smoothing method estimate the reward of many smoothed trajectories. But the noise sequence $\zeta$ is of dimension $H\times N$. As a result, it is hard to accurately estimate $\tilde{F}$. For the local smoothing method, an exhaustive search is needed, which could require exponential sample and computation cost.
3. For the cumulative reward, the "certification" is estimated by sampling methods. But as point 2 above states, it is sampling a very high-dimensional random vector, which may result in very inaccurate estimations. Then the certification can not serve as a strict lower bound of the cumulative reward. It is possible that a strong attack (e.g. [1]) can reduce the cumulative reward to be lower than the estimated certification. But this paper only tests the reward under a simple PGD attack.
4. Some related works are missing. This paper claims to be the first certification work for RL, but another paper[2] also proposes a smoothing-based certification for cumulative rewards. Although [2] is a very recent paper and can be regarded as concurrent work, I would suggest the authors to mention this paper and discuss the relation and differences between two papers.
5. Pong and Freeway are relatively simple compared to other Atari games. And the reward scales in these two games are small, thus it is hard to justify the tightness of the bound. In many literature[3], BankHeist and RoadRunner are used in addition to Pong and Freeway. So I would be happy to see more experimental results in these two games in order to better evaluate the proposed method.

Minor issues that do not affect my score:
1. The proposed certification only works for a greedy policy based on a Q-network. It will be better if the authors can provide some discussions on policy-based methods such as PPO.
2. This paper focuses on certifying an existing policy, and does not provide a method for adversarial training.


Refs:

[1] Sun et al. "Who Is the Strongest Enemy? Towards Optimal and Efficient Evasion Attacks in Deep RL." 

[2] Kumar et al. "Policy Smoothing for Provably Robust Reinforcement Learning." 

[3] Zhang et al. "Robust deep reinforcement learning against adversarial perturbations on state observations."
summary_of_the_review: This paper focuses on an important problem of certifying RL policies against state perturbations. The proposed method makes intuitive sense, but as a direct application of the randomized smoothing technique, the novelty is a little limited. Although theoretical analysis of the lower bound of cumulative rewards is provided under 2 smoothing settings, the estimation of the lower bound could be either too loose or too expensive. The empirical evaluation is interesting and helpful for understanding recent robust RL works, but there is no enough evidence for the effectiveness of the proposed method (the tested environments are relatively simple). Therefore, I think this paper is around the borderline, and has the potential to be accepted. But at the current stage, I tend to reject it, unless more improvements are made (e.g. a more practical smoothing method, theoretical complexity analysis, or experiments in more complicated environments).


---
After rebuttal: the authors have provided more implementation details and experimental results, which I find interesting. So I increased my score.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper gives certification of RL models under worse-case state perturbations in two respects: 1) behaving the same way w.r.t. state-action pairs and 2) achieving similar rewards at the end of a sampled trajectory. The paper gives theoretical grounding on the proposed certifications and demonstrate empirically the certifications are sound.
main_review: I believe works that certifies robust behaviours of a trained RL policy under adversarial perturbation to be helpful, and the ability to validate different RL-algorithms as more robust or less robust w.r.t. these perturbations (in the experimental section) is important and compelling. Overall I find the premise of the paper solid, and its empirical evidence well documented and solid.

I cannot vouch for the correctness of the formal proofs, as I am not too good at analysis. However, I would like to ask a few questions:

1) modeling of transition function perturbations : how would this work adapt to the setting where the adversary changes the transition function itself, rather than merely applying a noise on the current observation? for instance, imagine we train a maze-world agent on slip-free environment, and want to certify some of its properties in real-life where the world might be slippery?

2) modeling structured perturbations : perturbation does not occur uniformly at random, typically there is a generative procedure which applies perturbation under some kind of distribution, allowing one to give tighter bounds if this generative procedure is modeled. for instance, in pong one might randomly generate hallucinated balls around the screen, or to fake multiple copies of the enemy paddle. how would the current approach extend to these structured perturbations?
summary_of_the_review: overall I am convinced this paper is solid based on its problem statement and empirical evidence, but I will defer to someone who can formally verify the math better.
review_title: null

Meta-review: The authors propose a framework for for the certification of reinforcement learning agents against adversarial observation/state perturbations based on randomized smoothing. They develop the theory of the framework, demonstrating that the framework can be used to certify lower bounds on the worst-case cumulative reward of an agent. They validate their theoretical bounds experimentally.

The paper is well written and reviewers were mostly in agreement that the contributions are worthy of acceptance. The technical concerns from reviewer zGtv were addressed during the discussion phase, but I strongly encourage the authors to revise the manuscript to address the points raised in the discussion.
Decision: Accept (Poster)