Policy Smoothing for Provably Robust Reinforcement Learning
Authors: Aounon Kumar
Alexander Levine
Soheil Feizi
Venue: ICLR 2022 Poster (2022)
Keywords: Reinforcement Learning
Provable Adversarial Robustness
Randomized Smoothing

Abstract: The study of provable adversarial robustness for deep neural networks (DNNs) has mainly focused on $\textit{static}$ supervised learning tasks such as image classification. However, DNNs have been used extensively in real-world $\textit{adaptive}$ tasks such as reinforcement learning (RL), making such systems vulnerable to adversarial attacks as well. Prior works in provable robustness in RL seek to certify the behaviour of the victim policy at every time-step against a non-adaptive adversary using methods developed for the static setting. But in the real world, an RL adversary can infer the defense strategy used by the victim agent by observing the states, actions, etc. from previous time-steps and adapt itself to produce stronger attacks in future steps (e.g., by focusing more on states critical to the agent's performance). We present an efficient procedure, designed specifically to defend against an adaptive RL adversary, that can directly certify the total reward without requiring the policy to be robust at each time-step. Focusing on randomized smoothing based defenses, our main theoretical contribution is to prove an $\textit{adaptive version}$ of the Neyman-Pearson Lemma -- a key lemma for smoothing-based certificates -- where the adversarial perturbation at a particular time can be a stochastic function of current and previous observations and states as well as previous actions. Building on this result, we propose $\textit{policy smoothing}$ where the agent adds a Gaussian noise to its observation at each time-step before passing it through the policy function. Our robustness certificates guarantee that the final total reward obtained by policy smoothing remains above a certain threshold, even though the actions at intermediate time-steps may change under the attack. We show that our certificates are $\textit{tight}$ by constructing a worst-case scenario that achieves the bounds derived in our analysis. Our experiments on various environments like Cartpole, Pong, Freeway and Mountain Car show that our method can yield meaningful robustness guarantees in practice.


Published as a conference paper at ICLR 2022
POLICY SMOOTHING FOR PROVABLY ROBUST REINFORCEMENT LEARNING
Aounon Kumar, Alexander Levine, Soheil Feizi
Department of Computer Science University of Maryland College Park, USA
aounonê uudeumdde.. edu, edd,
{alevine0, s fe i z eecs umd.
ABSTRACT
The study of provable adversarial robustness for deep neural networks (DNNs) has mainly focused on static supervised learning tasks such as image classifica- tion. However, DNNs have been used extensively in real-world adaptive tasks such as reinforcement learning (RL), making such systems vulnerable to adver- sarial attacks well. Prior works in provable robustness in RI. seek to certify the behaviour of the victim policy at every time-step against a non-adaptive ad- versary using methods developed for the static setting. But in the real world, RL adversary can infer the defense strategy used by the victim agent by observ- ing the states, actions, etc. from previous time-steps and adapt itself to produce stronger attacks in future steps (e.g., by focusing more on states critical to the agent's performance). We present an efficient procedure, designed specifically defend against an adaptive RL adversary, that can directly certify the total reward without requiring the policy to be robust each time-step. Focusing on random- ized smoothing based defenses, our main theoretical contribution is to prove an adaptive version of the Neyman-Pearson Pearssn Lemma key lemma for smoothing- based certificates where the adversarial perturbation at a particular time can be a stochastic function of current and previous observations and states as well as previous actions. Building on this result, propose policy smoothing where the agent adds a Gaussian noise to its observation each time-step before passing it through the policy function. Our robustmess certificates guarantee that the fi- nal total reward obtained by policy smoothing remains above a certain threshold, even though the actions at intermediate time-steps may change under the attack. We show that our certificates are tight by constructing a worst-case scenario that achieves the bounds derived in analysis. Our experiments various environ- ments like Cartpole, Pong, Freeway and Mountain Car show that our method can yield meaningful robustness guarantees in practice.
INTRODUCTION
Deep neural networks (DNNs) have been widely employed for reinforcement learning (RL) prob- lems as they enable the learning of policies directly from raw sensory inputs, like images, with min- imal intervention from humans. From achieving super-human level performance in video-games
(Mnih et al.) 2013 Schulman et al. 2015) Mnih et al. 2016). Chess (Silver et al.) (017) and Go (iilver al. 2016 to carrying out complex worldworld tasks, such controlling a robot (Levine) et al.) (016) and driving vehicle (Bojarski et al. 2016). deep-learning based algorithms have not only established the state of the art, but also become more effortless to train. However, DNNs have been shown to be susceptible to tiny malicious perturbations of the input designed to completely alter their predictions (Szegedy et al. [2014] Madry et al. 2018 Goodfellow et al., 2015). the RL setting, an attacker may either directly corrupt the observations of an RL agent (Huang et al. 2017 Behzadan Munir 2017 Pattanaik et al. 2018) or act adversarially in the environment (Gleave et al. (020) significantly degrade the performance of the victim agent. Most of the adversarial defense literature has focused mainly on classification tasks (Kurakin et 2017 Buckman et al,
2018 Guo et al. 2018 Dhillon et al. 2018 Li& Li 2017
Grosse et al. 2017 Gong al. 2017).

---

Published as a conference paper at ICLR 2022
In this paper, study defense procedure for RL problems that is provably robust against norm- bounded adversarial perturbations of the observations of the victim agent.
Problem setup. A reinforcement learning task is commonly described as game between an agent and an environment characterized by the Markov Decision Process (MDP) M = (S, A, T, R. 7), where 5 is set of states, A is set of actions, T is the transition probability function, R is the step reward function and y E [0. 1] is the discount factor. However, as described in Section analysis applies an even more general setting than MDPs. At each time-step the agent makes an observation Or = ((x) E R which is a probabilistic function of the current state of the environment, picks an action a, E A and receives an immediate reward Re = R(s;, at). We define an adversary as an entity that can corrupt the agent's 's observations of the environment by augmenting them with a perturbation é at each time-step & which can depend on the states, actions, observations, etc., generated so far. We use (f1, <.....) to denote the entire sequence of adversarial perturbations. The goal of the adversary is to minimize the total reward obtained by the agent policy x while keeping the overall 22-norm of the perturbation within budget B. Formally, the adversary seeks to optimize the following objective:
3 our
min E
Σ
where R. = R(se, ar), ~ ((10(s)) +G)
:=
s.t. [|(e|, (2...)l2....)
S.
Note that the size of the perturbation e; each time-step & need not be the same and the adversary may choose to distribute the budget B over different time-steps in a way that allows it to produce a stronger attack. Also, our formulation accounts for cases when the agent may only partially observe the state of the environment, making M a Partially Observable Markov Decision Process (POMDP).
Objective. Our goal in provably robust RL to design a policy such that the total reward in the presence of a norm-bounded adversary is guaranteed to remain above certain threshold, i.e.,
min Ex
Σ
Y Re >
R. s.t. ||ell S B.
(1)
In other words, norm-bounded adversary can lower the expected total reward of the policy below a certain threshold. In our discussion, we restrict out focus to finite-step games that end after t time-steps. This is a reasonable approximation for infinite games with y < 1, as for sufficiently large f, of becomes negligibly small. For games where 7 = 1, Rg must become sufficiently small after a finite number of steps to keep the total reward finite.
Step-wise vs. episodic certificates. Previous works on robust RL have sought to certify the be- haviour of the policy function at each time-step of an episode, e.g., the output of Deep Q-Network (Lütjens et al. (019)) and the action taken for a given state (Zhang et al.) 2020). Ensuring that the behaviour of the policy remains unchanged in each step also certify that the final total reward remains the same under attack. However, if the per-step guarantee fails at even one of the interme- diate steps, the certificate on the total reward becomes vacuous or impractical in Appendix E of Zhang et al. (2020)). Our approach gets around this issue by directly certifying the final total reward for the entire episode without requiring the policy to be provably robust each intermediate step. Also, the threat-modes model we consider is more general as we allow the adversary to choose the size of the perturbation for each time-step. Thus, our method can defend against more sophisticated attacks that focus more on states that are crucial for the victim agent's performance.
compute (as noted
Technical contributions. In this paper, we study a defense procedure based on "randomized smoothing" (Cohen et al.) [219 Lécuyer et al.] 2019: Li et al. 2019 [Salman et al.) (019) since at least in "static" settings, its robustness guarantee scales up to high-dimensional problems and does not need to make stringent assumptions about the model. We ask: can utilize the benefits of randomized smoothing to make a general high- high-ddienssonal RL policy provably robust against ad- versarial attacks? The answer to this question turns out to be non-trivial as the adaptive nature of the adversary in the RL setting makes it difficult to apply certificates from the static setting. For exam- ple, the fz-certificate by Cohen et al. (2019) critically relies on the clean and adversarial distributions
2

---

Published as a conference paper at ICLR 2022
Statie (Classificaaion) Setting
Interactive (RL) Setting
92 0
4
Og 0o+00
9)
The standard Cohhnn et al. (2019) smoothing-based robustness certificate relies on the clean and the adversarial distributions being isometric Gaussians (panel a). However, adding noise to sequential observations in an RL setting (panels b-d) does not result in an isometric Gaussian distribution over the space of observations. In all figures, the distributions associated with clean and peterssariilly-peruuube values are shown in blue and red, respectively.
Figure I:
being isometric Gaussians (Figure aa.. However, in the RL setting, the adversarial perturbation in one step might depend on states, actions, observations, etc., of the previous steps, which could in turn depend on the random Gaussian noise samples added to the observations in these steps. Thus, the resulting adversarial distribution need not be isometric as in the static setting (Figure (b-d)). For more details on this example, see Appendix B
Our main theoretical contribution is to prove an adaptive version of the Neyman- Pearson lemma (Neyman & Pearson 1992) to produce robustness guarantees for RL. We emphasize that this is not a straightforward extension (refer to Appendix D and F for the entire proof). To prove this fundamental result, we first eliminate the effect of randomization in the adversary (Lemma [ by converting a general adversary to one where the perturbation at each time-step is a deterministic function of the previous states, actions, observations, etc., and showing that the modified adversary is as strong as the general one. Then, we prove the adaptive Neyman-Peane Pearson lemma where we show that, in the worst-case, the deterministic adversary can be converted one that uses up the entire budget B in the first coordinate of the perturbation in the first time-step (Lemma 3p. Finally, we de- rive the robustness guarantee under an isometric Gaussian smoothing distribution (Theorem [[]. In section A we establish the fightness of our certificates by constructing the worst-case environment- policy pair which attains our derived bounds. More formally, out of all the environment policy pairs that achieve certain total reward with probability p. we show worst-case environment-poliçy pair and a corresponding adversary such that the probability of achieving the same reward under the presence of the adversary is minimum. A discussion on the Neyman-Pearson lemma in the context of randomized smoothing is available in Appendix
Building these thcoretical results, propose Policy Smoothing, simple model-agnostic mandoizzed-smootee based technique that can provide certified robustness without increasing the computational complexity of the agent's policy. Our main contribution is to show that by augment- ing the policy's input by a random smoothing noise, we can achieve provable robustness guarantees on the total reward under norn-bounded adversarial attack (Section 4.2). Policy Smoothing does not need to make assumptions about the agent's 's policy function and is also oblivious to the work- ings of RL environment. Thus, this method can be applied to any RL setting without having to make restrictive assumptions on the environment or the agent. In section 3 we model the entire adversarial RL process under Policy Smoothing as sequence of interactions between a system A, which encapsulates the RI. environment and the agent, and a system B, which captures the addition of the adversarial perturbation and the smoothing noise to the observations, Our theoretical results do not require these systems to be Markovian and can thus have potential applications in real-time decision-making processes that do not necessarily satisfy the Markov property.
Empirical Results. We use four standard Reinforcement Learning benchmark tasks to evaluate the effectiveness of our defense and the significance of our theoretical results: the Atari games 'Pong' and 'Freeway' (Mnih et al. 2013) and the classical 'Cartpole' and 'Mountain Car' control environments (Barto et al. 1983] Moore 1990) see Figure 3, We find that our method provides highly nontrivial certificates. In particular, on at least two of the tasks, 'Pong' and 'cartpole", the
3

---

Published as a conference paper at ICLR 2022
provable lower bounds the average performances of the defended agents, against any adversary, exceed the observed average performances of undefended agents under practical attack.
2
PRIOR WORK
Adversarial RL. Adversarial attacks on RL systems have been extensively studied in recent years. DNN-based policies have been attacked by either directly corrupting their inputs (Huang et al.) 2017 Behzadan & Munir, 2017: Pattanaik et al.) 2018) or by making adversarial changes in the
environment (Gleave et al. 2020). Empirical defenses based on adversarial training, whereby the
dynamics of the RL system augmented with adversarial noise, have produced good results in practice (Kamalaruban et al. 2020) Vinitsky et al. 2020). Zhang al. (202T) propose training policies together with a learned adversary in an online alternating fashion to achieve robustness to perturbations of the agent's 's observations.
Robust RL. Prior work by Lütjens et al. (2019) has proposed a 'certified' defense against adversarial attacks to observations in deep reinforcement learning, particularly for Deep Q-Network agents. However, that work essentially only guarantees the stability of the network approximated Q-value at each time-step of an episode. By contrast, our method provides bound on the expected true reward of the agent under any norm-bounded adversarial attack.
Zhang al. 2020) certify that the action in each time-step remains unchanged under an adversarial perturbation of fixed budget for every time-step. This can guarantee that the final total reward obtained by the robust policy remains the same under attack. However, this approach would not be able to yield any robustness certificate if even one of the intermediate actions changed under attack. Our approach gets around this difficulty by directly certifying the total reward, letting some of the intermediate actions of the robust policy to potentially change under attack. For instance, consider an RL agent playing Atari Pong. The actions taken by the agent when the ball is close to and approaching the paddle are significantly more important than the ones when the ball is far away or retreating from the paddle. By allowing some of the intermediate actions to potentially change, our approach can certify for larger adversarial budgets and provide more iieeggained control over the desired total-reward threshold. Moreover, we study a more general threat model where the adversary may allocate different attack budgets for each time-step focusing more the steps that are crucial for the agent's 's performance, e.g., attacking a Pong agent when the ball is close to the paddle.
Provable Robustness in Static Settings: Notable provable robustness methods in static settings based on interval-bound propagation (Gowal et al. 2018: Huang et al. 2019 Dvijotham et al. 2018
Mirman et al. 2018), curvature bounds (Wong & Kolter 2018 Raghunathan al. 2018
Chiang
et al. 2020 S Singla & Feizi| 2019 [2020] (021). randomized smoothing (Cohen et al. 2019 Lécuyer
ct al.
2019
Li et al. 2019 Salman al. [201 Levine & Feizi 2021). etc. Certified robustness has
also been extended to problems with structured outputs such as images and sets (Kumar & Goldstein
2021]. Focusing on Gaussian smoothing, Cohen et al.) (2019) showed that if classifier outputs class with some probability under an isometric Gaussian noise around an input point, then it will output that class with high probability at any perturbation of the input within a particular & distance.
Kumar et al. (2020) showed how to certify the expectation of softmax scores of a neural network under Gaussian smoothing by using distributional information about the scores.
3 PRELIMINARIES AND NOTATIONS
We model the finite-step adversarial RL framework t-round communication between two sys- tems A and B (Figure System A represents the RL game. It contains the environment M and the agent, and when run independently, simulates the interactions between the two for some given policy л. At each time-step i, it generates a token from some set T, which is a tuple of the cur- rent state s; and its observation o,, the action a;- in the previous step (and potentially some other objects that we ignore in this discussion), i.e., For the first step. replace the action in Ti with some dummy element * from the action space A. System B comprises of the adversary and the smoothing distribution which generate an adversarial perturbation 6, and a smoothing noise vector 8,, respectively, at each time-step i, the sum of which is denoted by an offset d)= < 6 E Rdd.
(si, di-1, 0 ...... E S x A x Rd x
T.
4

---

Published as a conference paper at ICLR 2022
04
A
A
02
Tl. Rd
+7Kk
B
Figure 2: Adversarial robustness framework.
When both systems are run together an interactive fashion, in each round system A generates as a probabilistic function of T1, 7/ 72, .2..... Ti-1,, 1-.,,% (T x [Rd) A(T). ) is sampled from a fixed distribution. It passes т; to B, which generates E; as a probabilistic function of (Ty, M3 1/=1 and T; i..., G, (T x R=)==1 T independently from the smoothing distribution to obtain тІ. It then passes 1/ A for the next round. After running for steps, deterministic or random 0/1-function h is computed over all the tokens and offsets generated. We are interested in bounding the probability with which h outputs function of the adversarial budget B. In the RL setting, h could be function indicating whether the total reward above certain threshold or not.
(RR) and adds noise vector 6; sampled
PROVABLY ROBUST RL
4.1 ADAPTIVE SEMMAN-PEARSON LEMMA
Let X be the random variable representing the tuple 2 (T1, 1/1 T2, ........ Tt. nt) (T Rdy when there is no adversary, i.e., 6 and 77 = 6, is sampled directly form the smoothing distri- bution P. Let Y be the random variable representing the same tuple in the presence of general adversary satisfying ||e]|2 < B. Thus, if h(X) deriving lower-bound on the probability deterministic adversary dtt for which the adversarial perturbation at each step is a deterministic function the tokens and offsets of the previous steps and the token generated the current step. i.., ett (T Fd T Rd. Let d be its corresponding random variable. Then, have the following lemma that converts a probabilistic adversary into a deterministic one.
with some probability p. we are interested in f(Y) = as function of p and B. Let us now define
Lemma (Reduction to Deterministic Adversaries). For any general adversary e and an C (T Rd there exists a deterministic adversary eat such that,
dP E ET S[Y
where d is the random variable for the distribution defined by the adversary dtt
This lemma says that for any adversary (deterministic or random) and subset of the space of z, there exists a deterministic adversary which assigns a lower probability to I' than the general adversary. In the RL setting, this means that the probability with which smoothed policy achieves a certain reward value under general adversary is under a deterministic adversary. The intuition behind this lemma is that out all the possible values that the internal randomness of the adversary may assume, there exists a sequence of values that assigns the minimum probability to (over the randomness of the environment, policy, smoothing noise, etc.). We defer the proof to the appendix.
by the probability of the same
Next, we formulate an adaptive version of the Neyman-Pearson lemma for the case when the smooth- ing distribution P is isometric Gaussian (0, o² If we applied the classical Neyman-Pearson lemma on the distributions of X and ydt it will give us a characterization of the worst-case 0/1 function among the class of functions that achieve certain probability of being I under the dis- tribution of X that has the minimum probability of being under yd Let ax and py be the probability density function of X and dd respectively.
5

---

Published as a conference paper at ICLR 2022
Lemma 2 (Neyman-Pearson Lemma, 1933). fy = f2 E (T x R My (2) S qux (2)) for some q 2 0 and (()(X) = 1] P(X E Tya] then P[ = 1| ž Piy it E Pyae].
For an arbitrary element in the class of functions H = [h (X) = 1] N p), construct the set T y for an appropriate value of y for which P\X E y = p. Now, consider a function / which if its input comes from I a and 0 otherwise. Then, the above lemma says that the function h has the minimum probability of being I under ydt, i.c.,
h' argmin P[h(Y 1]. AEH,
This gives us the worst-case function that achieves the minimum probability under an adversarial distribution. However, in the adaptive setting, Ty could be very complicated set and obtain- ing an expression for P[y E Tyat might be difficult. To simplify our analysis, we construct a structured deterministic adversary ea which exhausts its entire budget in the first coordinate of the first perturbation vector, i.e., eff = (B,O.... ,0) and eç² = (0,0,.... 0) for > 1. Let ys be the corresponding random variable and My its density function. We formulate the following adaptive version of the Neyman Pearsso lemma:
Lemma). IfT = (T (x)(()) S qux qux(=)} for some q 2 0 and (X) = 1J Z PP[x E Tyn),, then P(N(Y") = 1] 2 Ply E Ty
Lemma 3 (Adaptive
The key difference from the classical version is that the worst-case we construct in this lemma is for the structured adversary and the final incquality relates the probability of h outputting under the adaptive adversary the probability that the structured adversary assigns the worst-case set. It says that for the appropriate value of g for which P[x <y = p, any function h E Hp outputs with at least the probability that y assigns to Ty... It shows that over all possible functions in Hp and over all possible adversaries the indicator function 1eeTy.. and the structured adversary capture the worst-case scenario where probability of h being I under the adversarial distribution is the minimum. Since both yst and X are just isometric Gaussian distribution with the same variance o² centered at different points on the first coordinate of m/ the set y is the set of all tuples a for which (n) J is below a certain threshold!" We use lemmas [ and 3 to derive the final bound on the probability of hYY) = 1 in the following theorem, the proof of which is deferred to the appendix.
Theorem 1 (Robustness Guarantee). For an isometric Gaussian smoothing noise with variance
o², (x)) 1] 2 p. then:
P[N(Y) 1] 2 (p) - -B/o),
where Tb is the standard normal CDF.
The above analysis can be adapted to obtain an upper-bound on P[h(Y) 1) 10000(010)) (00
4.2 POLICY SMOOTHING
Building on these results, we develop policy smoothing. a simple model-agnostic randomized- smoothing based technique that can provide certified robustness without increasing the computa- tional complexity of the agent's 's policy. Given policy we define smoothed policy æ as:
न o(s))) x |((ss) + 6t), where 8, ~ (0,
Our goal is to certify the expected sum of the rewards collected over multiple time-steps under policy म. We modify the technique developed by Kumar al. (2020) certify the expected class scores of a neural network by using the empirical cumulative distribution function (CDF) of the scores under the smoothing distribution to work for the RL setting. This approach utilizes the fact that the expected value of a random variable X' representing a class score under Gaussian (( o21) smoothing noise can be expressed using its CDF F.) as below:
1 (1 ((=F(z))dz
S F(z)dr.
E[X]
(2)
We use (m.) denote the jth coordinate of the vector m).

---

Published as a conference paper at ICLR 2022
(a) Cartpole
(b) Pong
(c) Freeway
(d) Mountain Car
Figure 3: Environments used in evaluations rendered by OpenAl Gym (Brockman et al. 2016
Given samples {a, of the random variable X. let define its empirical CDF point x, (x((x) = Kz; 2; S x//mm, as the fraction of samples that are less than or equal to a. Using produce high-confidence bounds the a, for a E (0, 1]. the true CDF F(x) is the range [.) Fx)), where F(x)= = (2) - (2(22/a) 22m and F(z) = Fm (x) + v (m(2//)) 2/222/ammmmmmm For an adversarial perturbation of fi-size B. the result of Cohen al. (2019) bounds the CDF within ($(--1((xx) B/a), (( + B/o)]. which in turn bounds F[(x] using equation (2).
(x), the
inequality
true CDF of X. says that with probability
In the RL setting. we can model the total reward as a random variable and obtain its empirical CDF by playing the game using policy æ. As above, we can bound the CDF F(z) of the total reward in range [F) F(x)] using the empirical CDF. Applying Theorem we can bound the CDF within (F(x)) ((F))))() + B/o]] for an &z adversary of size B. The function / in Theorem 1 could represent the CDF F(x) by indicating whether the total reward computed for an input 2 E (T R is below value Finally, equation ( puts bounds on the expected total
(F()) (
B/a), 1
reward under an adversarial attack.
EXPERIMENTS
5.1 ENVIRONMENTS AND SETUP
We tested on four standard environments: the classical cortrol problems 'Cartpole' and 'Mountain Car' and the Atari games 'Pong' and 'Freeway." We consider three tasks which use discrete action space ('Cartpole' and the two Atari games) as well as one task that uses a continuous action space ('Mountain Car'). For the discrete action space tasks, we use standard Deep Q-Network (DQN) MMiih et al. 2013) model, while for 'Mountain Car', we use Deep Deterministic Policy Gradient (DDPG) (Lillierap et al. 2016).
As is common in DQN and DDPG, our agents choose actions based on multiple frames of observa- tions. In order apply a realistic threat model, assume that the adversary acts each frame only once when it is first observed. The adversarial distortion is then maintained when the same frame is used in future steps. In other words, we consider the observation time step oe (discussed in Section 3 to be only the new observation at time (: this means that the adversarial/noise perturbation Me, as a fixed vector, continues be used to select the next action for several subsequent time-steps.
This is realistic model because we are assuming that the adversary can affect the agent's 's observa- tion of states, not necessarily the agent's memory of previous observations. As in other works on smoothing- -baen defenses (c.g.. Cohen et al. (2019)). we add noise during training as well as at test time. We use DQN and DDPG implementations from the popular mable-baselines? package (Rafín) et al. 2019): hyperparameters are provided in the appendix. In experiments, we report and certify for the total non-discounted (7 = 1) reward.
In 'Cartpole', the observation vector consists of four kinematic features. We use simple MLP model for the Q-network, and tested two variations: one which the agent uses five frames of observation, and one in which the agent uses only a single frame (shown in the appendix).
In order to show the effectiveness our technique on tasks involving high-dimensional state ob- servations, we chose two tasks ('Pong' and 'Freeway") from the Atari environment, where state observations are image frames, observed as 84 84 pixel greyscale images. For 'Pong', we test on "one-round" variant of the original environment. In variant, the game ends after player, either the agent or the opponent, scores a goal: the reward is then either zero or one. Note that this is not one-timestep episode: it takes typically the order of 100 timesteps for this to occur. Results

---

Published as a conference paper at ICLR 2022
(a) Cartpole
(b) Pong (One-Round)
Certited Reeerege Score
Cartified Win Itita
104
bation Budget
Necurbation Budget (d) Mountain Car
(c) Freeway (250 Frames)
0-02
Certried Averagg Score
Cartified Surconns RLata
Perturbation Budigtt
Perturbation Budget
Figure 4: Certified performance for various environments. The certified lower-bound on the mean reward is based on 95% lower confidence interval estimate of the mean reward of the smoothed model, using 10,000 episodes.
for full Pong game are presented in the appendix: explained there, we find that the certificates unfortunately do not scale with the length of the game. For the "Freeway" game, we play on 'Hard' mode and end the game after 250 timesteps.
In order to test on an environment with a continuous action space, we chose the 'Mountain Car' en- vironment. Note that previous certification results for reinforcement learning, which certify actions at individual states rather than certifying the overall reward (Zhang et al. 2020) cannot be applied continuous action state problems. this environment, the observation vector consists of two kinematic features (position and velocity), and the action is one continuous scalar (acceleration). As 'Cartpole', we use five observation frames and simple MLP policy. We use a slight variant of the original environment: we do not penalize for fuel cost so the reward is boolean representing whether or not the car reaches the destination in the time allotted (999 steps).
5.2 RESULTS
Certified lower bounds on the expected total reward, as a function of the total perturbation budget, are presented in Figure 4 For tasks with zero-one total reward ('Pong' and 'Mountain Car'), the function to be smoothed represents the total reward: /u()) R where It is equal to 1 if the agent wins the round, and 0 otherwise. To compute certificates on games with continuous scores ('Cartpole' and "Freeway"). ),
CDF smoothing (Kumar et al. 2020): see appendix for technical details.
In order to evaluate the robustness of both undefended and policy-smoothed agents, we developed an attack tailored to the threat model defined in where the adversary makes perturbation state observations which is bounded over the entire episode. For DQN agents, as in Lütjens et al. (019)) perturb the observation such that the pntuubationninducee action a' arg max, Q + Ct a)
minimizes the neework-aaprooimen conserve adversarial budget, we only attack if the gap between attacked q-value Q(o, a') and the clean q-value max, (o, a) is sufficiently large, exceeding a preset threshold Xq In practice, this allows the attacker to concentrate the attack budget only on the time-steps which are critical to the agent's 's performance. When attacking DDPG, where both a Q-value network and policy network t are trained and the action taken according to æ, we instead minimize Q(o, :( + (t)) + Al|e, ||2 where the hyperparameter À plays an analogous role in focusing perturbation budget on "important" steps, as judged by the effect on the approximated Q-value. Empirical results are presented in Figure 5 We see that the attacks are effective on the undefended agents (red, dashed lines). In fact. from comparing Figures and 5 we see that, for the Pong and Cartpole environments, the undefended performance under attack is worse than the certified lower bound on the performance of the policy-smoother agents under any possible attack: our certificates are the clearly non-vart non-vacuous for these environments. Further details the attack optimizations are provided in the appendix.
Q-value of the true observation Q(o, a'). However, in order
8

---

Published as a conference paper at ICLR 2022
(a) Cartpole
(b) Pong (One-Round)
133
Win Nate
Avarage
123
urarreddd Smeathig
Perturbation Budget
Perturbation Budget
(c) Freeway (250 Frames)
(d) Mountain Car
SuCCIAK Hutte
Undeltroed
Perturbation Budgat
Perturbation Budget
Figure 5: Empirical robustness of defended and undefended agents. Full details of attacks are presented in appendix.
We also present an attempted empirical attack on the smoothed agent, adapting techniques for at- tacking smoothed classifiers from (Salman et al.] (2019) (solid blue lines). We observed that our model was highly robust to this attack significantly more robust than guaranteed by our certificate. However, it is not clear whether this is due to looseness in the certificate to weakness of the attack: the significant practical challenges to attacking smoothed agents are also discussed in the appendix.
6 CONCLUSION
In this work, we extend randomized smoothing to design a procedure that can make any reinforce- ment learning agent provably robust against adversarial attacks without significantly increasing the complexity of the agent's policy. We show how to adapt existing theory on randomized smoothing from statie tasks such as classification, the dynamic setting of RL. By proving an adaptive version Seyyan-Peaason Lemma, we show that by adding Gaussian smoothing noise to
of the celebrated the input of the policy, can certifiably defend it against norm-bounded adversarial perturbations of its input. The policy smoothing technique and its theory covers wide range of adversaries, policies and environments. Our analysis is tight, meaning that the certificates we achieve are best possible unless restrictive assumptions about the RL game are made. In our experiments, we show that our method provides meaningful guarantees on the robustness of the defended policies and the total reward they achieve even in the worst case is higher than undefended policy. In the future, the introduction of randomized smoothing to RL could inspire the design of provable robustness techniques for control problems in dynamic real-world environments and multi-agent RL settings.
REPRODUCIBILITY
We supplement our work with accompanying code for reproducing the experimental results, as well as pre-trained models for a selection of the experiments. Details about setting syper-parameters and the environments we test are included in the appendix. Proofs for our theoretical results (lemmas and main theorem) are also provided in the appendix.
ETHICS STATEMENT
We present a method to make RL models provably robust under adversarial perturbations. We do not foresee any immediate ethical concerns associated with work.
ACKNOWLEDCEMENTS
This project was supported in part by NSF CAREER AWARD 1942230, grant from NIST 60NANB20D134, HR0011 1990006-GARD-F---O HR001 12090132, ONR YIP award N00014- 22-1-2271, Army Grant W91 IN771

---

Published as a conference paper at ICLR 2022
REFERENCES
Andrew G. Barto, Richard S. Sutton, and Charles W. Anderson. Neuronlike adaptive elements that can solve difficult learning control problems. IEEE Transactions on Systems, Man, and Cybernetics, SMC-13(5):334 846, 1983. doi:
Vahid Behzadan and Arslan Munir. Vulnerability of deep reinforcement learning to policy induction attacks. In Petra Perner (ed.). Machine Learning and Data Mining in Pattern Recognition 13th International Conference, MLDM 2017, New York, NY, USA, July 15-20, 2017, Proceedings, volume 10358 of Lecture Notes in Computer Science, pp. 262-275. Springer, 2017. doi: 10. 1007/ 978-3 978-3-319-62411-7)_J1 URL https: /t::://doo..oo org.10.00011110000 1007/ 978 313 62416-7_
19
Mariusz Bojarski, Davide Del Testa, Daniel Dworakowski, Bernhard Firner, Beat Flepp, Prasoon Goyal, Lawrence D. Jackel, Mathew Monfort, Urs Muller, Jiakai Zhang, Xin Zhang, Jake Zhao, and Karol Zieba. End to end learning for self-driving cars. CoRR, abs/ abss/6004007316 2016. URL
httt:://rxivv/ org/ abs 1604 07316
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojeiech Zaremba. Openai gym, 2016.
Jacob Buckman, Aurko Roy, Colin Raffel, and lan J. Goodfellow. Thermometer encoding: One hot way to resist adversarial examples. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings, 2018.
Ping-yeh Chiang, Renkun Ni, Ahmed Abdelkader, Chen Zhu, Christoph Studer, and Tom Gold- stein. Certified defenses for adversarial patches. In 8th International Conference Learning Representations, 2020.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 1310-1320, Long Beach, California, USA, 09-15 Jun 2019. PMLR.
Guneet S. Dhillon, Kamyar Azizzadenesheli, Zachary C. Lipton, Jeremy Bernstein, Jean Kossaifi, Aran Khanna, and Animashree Anandkumar. Stochastic activation pruning for robust adversarial defense. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings, 2018.
Krishnamurthy
Dvijotham, Sven Gowal, Robert Stanforth, Relja Arandjelovic, Brendan O' O'Donoghue, Jonathan Uesato, and Pushmeet Kohli. Training verified learners with learned ver- ifiers, 2018.
Adam Gleave Michael Dennis, Cody Wild, Neel Kant, Sergey Levine, and Stuart Russell. Adversar- ial policies: Attacking deep reinforcement learning. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL http:httt://// /ttttss::/oppereviieee wwt.ieeww.eeeeeeeeeeeeeeeeeeeeee forum? HdHHHg
Zhitao Gong, Wenlu Wang, and Wei-Shinn Ku. Adversarial and clean data are not twins. CoRR, abs/1704. 04960, 2017.
Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In 3rd International Conference on Learning Representations, ICLR 2015, San Diego CA, USA, May 7-9, 2015, Conference Track Proceedings. 2015.
Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Ue- sato, Relja Arandjelovic, Timothy Mann, and Pushmeet Kohli. On the effectiveness of interval bound propagation for training verifiably robust models, 2018.
Kathrin Grosse, Praveen Manoharan, Nicolas Papernot, Michael Backes, and Patrick D. McDaniel. On the (statistical) detection of adversarial examples. CoRR, abs/1 702.100222.8 2017.
10

---

Published as a conference paper at ICLR 2022
Chuan Guo, Mayank Rana, Moustapha Cissé, and Laurens van der Maaten. Countering adversarial images using input transformations. In 6th International Conference on Learning Representa- tions, ICLR 2018, Vancouver, BC, Canada. April 30 May 3, 2018, Conference Track Proceed- ings, 2018
Po-Sen Huang, Robert Stanforth, Johannes Welbl, Chris Dyer, Dani Yogatama, Sven Gowal, Krish- namurthy Dvijotham, and Pushmeet Kohli. Achieving verified robustness to symbol substitutions via interval bound propagation. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing, EMNLP-IJCNLP 2019, Hong Kong, China, November 3-7, 2019, pp. 4081-4091, 2019. doi: 10. 10.18653/v1/D19-11 1419. WRLphttp:://oo. org/ 18 8638/653/600 w1/p19--/111111 1419
Sandy H. Huang, Nicolas Papernot, Ian J. Goodfellow, Yan Duan, and Pieter Abbeel. Adversarial attacks on neural network policies. Sth International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Workshop Track Proceedings. OpenReview.net, 2017. BRLLhttps: pettps::/openreveee
net fortt/forumm20 rrr ryy.ryyyyy..yy
Parameswaran Kamalaruban, Yu-Ting Huang, Ya-Ping Hsich, Paul Rolland, Cheng Shi, and Volkan Cevher. Robust reinforcement learning via adversarial training with langevin dy- namics. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Ad- vances in Neural Information Processing Systems, volume 33, pp. 8127-8138 Curran Asso- ciates, Inc., 2020. URL httppppss//prrrccediiigssss neurips wwteeeirss.ccpppppeeeeeeee cctppaperr/222///illl 02266224688866633333444444433333
Aounon Kumar and Tom Goldstein. Center ron robust vector- functions. CoRR, abs/2102.09701, 2021. URI/nttps:///rvvv.orr//////
09701
Aounon Kumar, Alexander Levine, Soheil Feizi, and Tom Goldstein. Certifying confidence via ran- domized smoothing. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan- - Lin Advances in Neural Information Processing Systems 33: An- nual Conference on Neural Information Processing Systems 2020, NewrIPS 2020, December 2020, virtual, 2020. URL
wtwp:roooooeciooo......o.......e neurips ttt pc/ppaper//22//aaiti 9d431 - html
Alexey Kurakin, Ian J. Goodfellow, and Samy Bengio. Adversarial machine learning at scale. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24- 26, 2017, Conference Track Proceedings, 2017. URL URU/atpp:://opeeeeieeeeeet http://pnnneeeeeeeeeeeeee net. forrmmrrmm um? 1d=BJm4T4Kgx
Mathias Lécuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples with differential privacy. In 2019 IEFE Symposium on Security and Privacy, SP 2019, San Francisco, CA, USA, May 19-23, 2019, pp. 656 656-672, 2019.
Alexander Levine and Soheil Feizi. Improved, deterministte smoothing for L1 certified robustness. CoRR, abs/2103.10834, 2021. URL
22w..///21...m 10834
Sergey Levine, Chelsea Finn, Trevor Darrell, and Pieter Abbeel. End-to-end training of deep vi- suomotor policies. J. Mach. Learn. Res., 17:39:1-39:40, 2016. URL http:/ //mt:: jmlr. org/
papers/v17/15-52 html
Bai Li, Changyou Chen, Wenlin Wang, and Lawrence Carin. Certified adversarial robustness with additive noise. Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, 8-14 December 2019, Vancouver, BC, Canada, pp. 9459-9469, 2019.
Xin Li and Fuxin Li. Adversarial examples detection in deep networks with convolutional filter statistics. In IEEE International Conference on Computer Vision, ICCV 2017, Venice, Italy, Oc- tober 22-29, 2017, pp. 5775-5783, 2017.
Timothy P. Lillicrap, Jonathan J. Hunt, Alexander Pritzel, Nicolas Manfred Otto Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learn- ing. CoRR, abs/1 509.00000000 029771, 2016.
11

---

Published as a conference paper at ICLR 2022
Bjöm Lütjens, Michael Everett, and Jonathan P. How. Certified adversarial robustness for deep reinforcement learning. In Leslie Pack Kaelbling. Danica Kragic, and Komei Sugiura (eds.), 3rd Annual Conference Robot Learning. CoRL 2019, Osaka, Japan, October 30 November I, 2019, Proceedings, volume 100 of Proceedings of Machine Learning Research, pp. 3328-1337. PMLR, 2019.
ml press vv 00/1000 jens2aa html]
Aleksander Madry, Alcksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. To- wards deep learning models resistant to adversarial attacks. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Confer- ence Track Proceedings, 2018.
Matthew Mirman, Timon Gehr, and Martin Vechev. Differentiable abstract interpretation for prov- ably robust neural networks. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learn- ing Research, pp. 3578-3586. PMLR, 10-15 Jul 2018. URL press/ Freess/80/// mi hbmm
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, loannis Antonoglou, Daan Wierstra, and Martin A. Riedmiller. Playing atari with deep reinforcement learning. CoRR, abs/1312.5602, 2013.
5602
Volodymyr Mnih, Koray Kavukcuoglu, David Silver. Andrei A Rusu, Joel Veness, Mare G Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. nature, 51 ((7884)):5529-5555 533, 2015.
Volodymyr Mnih, Adrià Puigdomènech Badia, Mehdi Mirza, Alex Graves, Timothy P. Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In Maria-Florina Balcan and Kilian Q. Weinberger (eds.), Proceedings of the 33nd International Conference on Machine Learning, ICML 2016, New York City, NY, USA, June 19- 24, 2016, volume 48 of JMLR Workshop and Conference Proceedings, pp. 1928 1937. J.N7..ML..rrg 2016. URL http::///occeeeeeieeeeooo mlr press/pessssoccc..c v48 / miimmnnillll.lll 6. .at.al...mmmmmmmmmmm
Andrew W. Moore. Efficient memory-based learning for robot control. 1990.
J. Neyman and E. S. Pearson. On the Problem of the Most Efficient Tests of Statistical Hypotheses, pp. 73-108. Springer New York, New York, NY, 1992 ISBN 978-1-4612-0919-55 doi: 10.1 978- 978-1-4612-0919-5. URL
Anay Pattanaik, Zhenyi Tang. Shuijing Liu, Gautham Bommannan, and Girish Chowdhary. Robust deep reinforcement learning with adversarial attacks. In Elisabeth André, Sven Koenig, Mehdi Dastani, and Gita Sukthankar (eds.), Proceedings of the 17th International Conference on Au- tonomous Agents and MultiAgent Systems, AAMAS 2018, Stockholm, Sweden, July 10-15, 2018, pp. 2040-2042 International Foundation for Autonomous Agents and Multiagent Systems Rich- land, SC, USA/ ACM, 2018. URLhttp:: aan.tttt///ll..a..or//////o/// www.cm/wgg/ciaaiionnn.o.mo httpaataiiai.ccmammmmmm01a000000
Antonin Raffin
RI baselines3 Zoo.
rl-basel Seaasllnees--ae 200,
2020.
Antonin Raffin, Ashley Hill, Maximilian Ernestus, Adam Gleave, Anssi Kanervisto, and Noah Dor- mann. Stable baselines3.
com/DLR ww/ wattttabbebbbaeeeeeeee www.aaaseeess...... 2019.
Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. Semidefinite relaxations for certifying ro- bustness adversarial examples. Proceedings the 32nd International Conference on Neural Information Processing Systems, NIPS' 18, pp. 19900-10910, Red Hook, NY, USA, 2018. Curran Associates Inc.
Hadi Salman, Jerry Li. Ilya P. Razenshteyn, Pengchuan Zhang, Huan Zhang, Sébastien Bubeck, and Greg Yang. Provably robust deep learning via adversarially trained smoothed classifiers. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Informa- tion Processing Systems 2019, NeurIPS 2019, 8- 14 December 2019, Vancouver, BC, Canada, pp- 11 11289- 1300, 2019.
12

---

Published as a conference paper at ICLR 2022
John Schulman, Sergey Levine, Picter Abbeel, Michael I. Jordan, and Philipp Moritz. Trust gion policy optimization. In Francis R. Bach and David M. Blei (eds.), Proceedings of the 32nd International Conference Machine Learning, ICML 2015, Lille, France, 6-11 July 2015, vol- ume 37 of JMLR Workshop and Conference Proceedings, pp. 1889-1897. 188--1897JMMLR.oog 2015. URL ht.t:://pocceeee ngs. m1 wtt.sss....p...r...mmmmmmmmmmmme / vv7 www/sccullaalt.mm
hhtml
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George van den Driess- che, Julian Schrittwieser, Ioannis Antonoglou, Vedavyas Panneershelvam, Mare Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lilli- crap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis. Mastering the game of go with deep neural networks and tree search. Nat., 529(7587)4444-489 2016. doi: 10. 11936/ UBL.pttpee//o....rrr000000111113
David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, Timothy P. Lillicrap. Karen Simonyan, and Demis Hassabis. Mastering chess and shogi by self-play with a general reinforce- ment learning algorithm. CoRR, abs/1712.01815, 2017. URL http: org/ /bs/
1712. 01815
Sahil Singla and Soheil Feizi. Robustness certificates against adversarial examples for relu networks. CoRR, abs/1902.01233 2019.
Sahil Singla and Soheil Feizi. Second-order provable defenses against adversarial attacks, 2020.
Sahil Singla and Soheil Feizi. Skew orthogonal convolutions. CoRR, abs/2105.11417, 2021. URL
https:/ //arxi://axiv... /arxiv. wwtp://ggg/bbbb..ooo/ 11417
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfel- low, and Rob Fergus. Intriguing properties of neural networks. In 2nd International Conference Leurning Representations, ICLR 2014, Bansf, AB, Canada, April 14-16, 2014, Conference Track Proceedings, 2014.
Eugene Vinitsky, Yuqing Du, Kanaad Parvate, Kathy Jang, Pieter Abbeel, and Alexandre M. Bayen. Robust reinforreet learning using adversarial populations. CoRR, abs/2008.018 01225, 2020. URL
https://arxiv/ wwtp:///////aaoaaooooooooaa 2008 01825
Eric Wong and J. Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmüsssan Stockholm, Sweden, July 10-15, 2018, pp. 5283-5292. 2018.
Huan Zhang, Hongge Chen, Chaowei Xiao, Bo Li, Duane S. Boning, and Cho-Jui Hsich. Ro- bust deep reinforcement learning against adversarial perturbations on observations. CoRR, abs/2003.08933,, 2020. URL htttt:::s///:tiv..oom
abs wttp:/o///abb//0...3.333
Huan Zhang, Hongge Chen, Duane S Boning, and Cho-Jui Hsieh. Robust reinforcement learning on state observations with learned optimal adversary. In International Conference on Learning Representations, 2021. URL httppss////eeeeeeiee...co wttp:/ewwwwwweeeereeeeeeeeeeeeee http:///www....eeee...oe.ooooeaa
13

---

Published as a conference paper at ICLR 2022
A TIGHTNESS OF THE CERTIHICATE
Here, we present worst-case environment-pon policy pair that achieves the bound in Theorem 1 show- ing that our robustness certificate is in fact tight. For given environment M (S, A, T, R, and a policy let be lower-bound on the probability that the total reward obtained by policy under Gaussian smoothing (no adversary) with variance o² above a certain threshold v, i.e.,
R 2
V 2B
Let Hp be the class of all such environment- policy pairs that cross this reward threshold with proba- bility at least p. We construct an environment-policg, pair (M', x²) that achieves the reward threshold with probability ((6-1(p) (p) B/a) under the structured adversary et Note that, this does not mean that at is the strongest possible adversary for a general environment-policy pair. only shows that the performance of policy N' in environment M'' under the adversary e* is a lower-bound on the performance of a general environment-polian
pair under a general adversary. Consider a one-step game with environment M' = (S, A, R', ?) with deterministic observation function o of the state-space and a policy n' such that n' returns an action 01 E A if the first coordinate of o(s1) ) + vn is most {o(s))] + o -1 (p) and another action a2 A otherwise. Here (o(si)) represents the first coordinate of )( ). The environment offers a reward y if the action in the first step is a and O when it is 02 The game terminates immediately. The probability of the reward being above is equal to the probability of the action being @1. When 771 is sampled from the Gaussian distribution, this probability is equal to ((( {o(s1)} 1)/o) p. Therefore, (M', X') E Hp. Under the pres- ence of the structured adversary e defined in Section [4.1] this probability after smoothing becomes
(((w {o(s))) - Br)a)= = (( (p)-(p)) (p) B/o), which is same as the bound in Theorem 1
B STATIC Vs. ADAPTIVE SETTING
In this section, we illustrate the difference between the adversarial distributions in the static setting and the adaptive setting. Naively, one might assume that smoothing baased robustness guarantees can be applied directly to reinforcement learning, by adding noise to observations. For example, it seems plausible to use Cohen et al.'s l certificate Cohen et al. (2019), which relies on the overlap in the distributions of isometric Gaussians with different means, by simply adding Gaussian noise to each observation (Figure a However, as we demonstrate with a toy example in Figure [ (b-d), the Cohen et al. certificate cannot be applied directly to the RL setting, because adding noise to sequential observations does not result in an isometric Gaussian distribution over the space of observations. This is because the adversarial offset to later observations may be conditioned on the noise added to previous observations. In [--d), we consider a two-step episode, and for simplicity, we consider case where the ground-truth observations each step are fixed. At step 1, the noised distributions of the clean observation and the patrssarially-erruuube are both Gaussians and overlap substantially, similar to in the standard classification setting (panel b). However, we see in panel (c) that the adversarial perturbation e2 added to O2 can depend on the smoothed value of o¹.. This is because the agent may leak information about the observation that it receives after smoothing (01 + 172) to the adversary, for example through its choice of actions. After smoothing is performed on 02, the adaptive nature of the adversary causes the distribution of smoothed observations to no longer be an isometric Gaussian in the adversarial case (panel d). The standard certification results therefore cannot be applied.
observation of
C NEYMAN-PEARSON LEMMA [1993] IN SMOOTHING
In the context of randomized smoothing, the Neyman lemma produces the worst-case deci- sion boundary of a classifier based on the estimated probability of the top class under the smoothing distribution. It says that this boundary is region where the ratio of the probability density functions of the smoothing distributions at the clean input and the perturbed input is a constant. When the two distributions isometric Gaussians, boundary takes the form of a hyper-plane (see Appendix A of et al. (2019). However, in the dynamic setting of RI, the smoothing distribution after adding the adversarial perturbation may not
is the in static settings like image classification, this
14

---

Published as a conference paper at ICLR 2022
be isometric even if the smoothing noise each time-step was sampled from an isometric Gaus- sian distribution (see figure 1, section 'Technical contributions' and Appendix A). So, we formulate and prove adaptive version of the Jeyman-Pearson lemma to obtain provable robustness in RL through randomized smoothing.
D PROOF OF LEMMA I
Statement: For any general adversary and P ETxx RR),, there exists deterministic adver- sary el such that,
Py E P
where ydt is the random variable for the distribution defined by the adversary ett
J. e is deterministic function of Ti, 771, T2, 122 ........... 11 1, Tı. Let H {= 21 TI, 22 771, 23 T2, 24 1/2..... (0a....,,22.1... a₃} be the set of points whose first 2j - coordinates are fixed to an arbitrary set of values T1, 7/1 T2, 72:..... Ty In the space defined by H. É1. Ej-1 are fixed vectors in IR and e, is sampled from a fixed dis- tribution over the vectors with norm most By. Let Y be the random variable representing the distribution over points H defined by the adversary for which ej = 7 such that 1 B/. De- fine an adversary é', such that, = E, vi # j. Set ej to the vector yy that minimizes the probability that Y assigns to I' n H. i.c.,
Proof. Consider a time-step j such that
= arg min PLY ET
The adversary é' behaves as up to step j - 1. At step j. it sets e) to the y that minimizes the probability assigns H. based on the values Tı, 11. T2, 12, .... Ty. After that, mimics till the last time-step t. Therefore, for given tuple (21, 2...... 22j-1) = (71, 7, T2, :
T5),
PlY TNH P(Y ETNH)
Since both adversaries are same up to step j 1, their respective distributions over ž1, 22, 22j-1 remains same as well. Therefore, integrating both sides of the above inequality over the space of all tuples (=1, 22, .... 22j-1), we have:
/ P e rn H.pp (Z1, 2....., 22 12) dz2j-1
/ PlY E
ET Enn 22. ..... 22j d22 d22j-1
PLY' S eT).
where Y' is the random variable corresponding to e'. Thus, we have constructed an adversary where the first j adversarial perturbations a deterministic function of the 7,8 and 175S of the previous rounds. Applying the above step sufficiently many times we can construct a deterministic adversary dt represented by the random variable d such that
PP
S P|Y E 1].
E PROOF OF LEMMA 3
Lemma 3 states that the structured adversary characterises the worst-case scenario. Before proving this lemma, let first show that any deterministic adversary can be converted one that uses up the entire budget of B without increasing the probability assigns to being one in the worst-case. For each step i, let define used budget B', [|(G,, C2 ..., G-1))12 2 the norm of the perturbations of the previous steps and remaining budget B /B B² (B:) an upper-bound the norm of the perturbations of the remaining steps. Note that, B, and B, B.
Consider a version zdt of the deterministic adversary that uses up the entire available budget B by scaling up ett such that its norm is equal to B,, i.c, setting to elt Btt [le4 ||2. Let át be the random variable representing ddt_
15

---

Published as a conference paper at ICLR 2022
Lemma. Tf f (T x yd Mya (2) qux((2)) for some 0 and Plh(X) P[X Tp then P()(Yd = 1I 2 P[Y de l'aa].
2
Proof. Consider Tya = fz E (T x Rt (y - d'Hx((2) for some d' 2 0, such that, P[X E Tyai for some lower-bound (P)(XX) 11. Then, by the Peaaan-Pearoon Lemma we have that,
P[h(Y"))
Pfy E ey
Now consider space H in (T x y where all but the last element of the tuple are fixed, i.e., H = {z 21 = TI, 22 = :3 = 72,24 722, -2 T Since, edi is a deterministic adversary where each ete is a deterministic function of the previous and 7J5S, each eith is also fixed in H. Therefore, H. both μa and ju are two isometric Gaussians in the space the 7/s and the set H Hnnya is hyperplane. The probability assigned by y to H. n Ty is proportional to the distance of the center of the corresponding Gaussian. In the construction of zdlz, this distance only increase, therefore,
F[y E eya+ 2 P[ ay
Now, consider function hr h (2) which outputs one if z E I yee and zero otherwise. Construct the set Pyu = {= (T ) (y (=) S qux(=)} for some 2 such that, e p p P(Ar, y (X) 1).
Then, by the Neyman- Lemma, we have.
P(hr, (Yrl)) Pl E ppal
or, Plydi E ETya] 2 pl TTaal
(from definition of hr yay
or, Plydt Tya] 2 pl E [yal
or, P[h(Y = 1] df E paar
(from the above two incqualities)
proving the statement of the lemma.
Now, we prove lemma 3 below:
Statement: yf = {2 E (T x R2 (2) S qux(2)) for some 2 and P[h(X) = > P[X- E Ty then Pl 1] Ply T.
Proof. Construct the set I a. defined in the above lemma for q 2 0 such that PP I Tyaal P, for some lower-bound on P(N(X) 1]. Then,
P(M(Ydd)= 1] 2 Plpr ETyai
Now consider the structured adversary et in which of = (B, (,......)) and of' (0.0....,.0 0) for
i > 1. Define the set o = {2 (T x Rdy () S qux (z)} for the same as above. Then,
can show that:
1. dl dt E Tyae = Pf st e Tym], and
2. P E T = P[X E Ty-]]
which, in turn, prove the statement of the lemma.
Let Af and Ne. represent Gaussian distributions centered at origin and e; respectively. Then, we can write px and Jy as below:
mx(=)=
II
pr, (T: m.,7,, 72, . -1-1,, -
2-1
(z)((=)=
Mng (Ta Th, 72........
T-- 7/- 1NN (1s)
16

---

0). We can Published as a conference paper at ICLR 2022
where pr; is the conditional probability distribution of token T; given the previous tokens and offsets. Therefore,
Mya (2)
MN (m))
? vo
(ny
2n
1x (2)
pN(11))
i=1
1=1
pgae(z) (2)
Sq
Σ
2n ci
(c(h) s 20 Inq
px(2)
Consider a round j S L such that etth 0, Vi > j + and '++ (Bf+1, .,...,.)
always find such f we always have Et+ (B++1 0, ..,..,. 0), since B 0. Note that,
B VB B (B and in turn J+1 are functions of T1, 1/ T2, .2... and not Ty+1- =2,22 1J1 23 T2, '2,,.... 22j-1 = Ty} be the set of points whose first 2j - coordinates are fixed to an arbitrary set of values 71. 11, 72, .2......T For points in H. all 2t"t for j + are fixed and for i > variable representing the distribution of points in H defined by the adversary zdlt (corresponding random variable ÿrd).. In the space of 7/: "/t,,........................... Mr, this is an isometric Gaussian centered at (e)), S41,0,..... Therefore, I n H is given by
Let H (=
are set to zero. Let Y denote the random
Σ 20 & (2( < 20 Int
or, f2 c 11tt1 S 3
for some constant 3 dependent on 7/, zdit ..... Mijzi - 1, a and f. The probability assigned by the Gaussian random variable Yu to the half-space defined by (3) is proportional to the distance of the center the Gaussian from the hyper-plane in 3). which is equal to:
| || 11 3 (B 8
V 12 +
12 1++1l1 B
where the equality follows from:
| 112
+
-|,55 + 11/ 1,
|| 12 + B² (Bi+1)2
(from definition of B3)
||c 2 +P+B* B² - (|<<91] 1| + || I| +... + 129))1
B² -1| 1| ||
||2 11?)
B - (B = (B))²
Now, consider an adversary edا' such that हम हهه vi < - 1, zdt' = (B,, .,..,.....0 .). and
Ej
ztt 0, Vi > j. Let a be the corresponding random variable. Define Ty similar to r Ty.. Then, yyar 7 is given by
n3 (B/,0....,0) 5B
(4)
which is obtained by replacing adt with (B², 0,..,,... 0) and zdt about the origin. Define Yadr' similar to ydtt and just like yedt the distribution of &rat' is also an #t
5+1 with (0, 0)..., in inequality 3
isometric Gaussian, but centered at ((B2, 0, . 0), (0, o,.... The probability assigned by this Gaussian distribution to I yya N is proportional to the distance of its center to the hyper-plane defining the region in (4) which is equal to ((BB)² - /3//B. Therefore,
Ty NH] = PI E Tyar 0 7..
The key intuition behind this step is that, for isometric Gaussian smoothing distribution, the worst- case probability assigned by the adversarial distribution only depends on the magnitude of the per- turbation and not its direction. Figure illustrates this property for two-dimensional input space.
17

---

Published as a conference paper at ICLR 2022
|
Figure 6: General adversarial perturbation vs. perturbation aligned along the first dimension. Blue and red regions denote where the worst-case function is one and zero respectively.
Since both adversaries are same up to step j - 1, their respective distributions over 21, ....... 22j-1 remains same as well, i.e., Py (21, 22, 225-1) = Pyae (21, 22, 22..., 22)-1). Integrating over the space of all tuples (21, ................................ 22)-1), have:
22,....,,222....
f FI Tyya n HHppp (21, #2, 22 22 d22 dz25--1
= = Ply Ply E Tyae n Hlppae (#1, 22, #2j )dzıdz2 ..ddzz...ddy.. dz2z-1
PP E T PP' [Taw:
Since the distribution defined by (with no adversary) over the space of 7/88 Gaussian centered origin whose distance to both I a O H and Ty O H is the same (equal -B/ it assigns the same probability to both (3) and (4). Therefore,
P[X E Tyal P[X E Fyar].
Thus, have constructed adversary with less non-zero G, Applying, this step sufficiently many times we can obtain the adversary e such that,
df Tyaal P|y E Ty and EyX P[X E Tym]
which completes the proof.
F PROOF OF THEOREM
Statement: For an isometric Gaussian smoothing noise with variance o², P((()) = 1] 2 p
then:
P[MY) = -p)
Proof. Define L' = f= (T Rdy (2 < qux(2)) for an appropriate such that P[X e
Ty] = p. Then, by the Neyman Pearson lemma, we have P[h(Y) = 2 P Ty]. Applying lemma 1, we know that there exists a deterministic adversary dtt ydl such that,
represented by random variable
P[K(Y) 1] 2 PYY E I'y] 2 df E l'y].
(5)
Now define function bry (=) 1 {seTy) and set I y = {2 E (T Rddy (x))(=) < d'ux (=)) for appropriate > 0, such that, P(X E Ty Pi(lrr (X) 1] p. Applying the Neyman-
18

---

Published as a conference paper at ICLR 2022
Pearson lemma again, have:
PlAry (Ydt) = 1 P| E y
or, P\y {Ty] 2 P|y  E aaa
(from definition of hry
or, Plh(Y)
2 P| E [ya]
(from inequality (
Define yet (2) = 1 (xET For the structured adversary et represented by y define Ty fo E (T x )f (uyae( (2) & (=xx(2)) for an appropriate q" > O, such that, P[X E Tym* = Plhr,a (X) = 1] = Applying lemma 3, we have:
Fliry (r 1] P\y ry
Plyd E r Tya] 2 Ply E Ty
(from definition of hr, y.r
P(M 1] 2 Ply Tyu] Ty is defined as the set of points which satisfy:
(since PIA(Y) 1] 2 IP de E Ty
(y=(=)
MNiqe (11) Fx (z) S q" or,
px(n) S
Ti (B, 0,.......... ..... 0) S 3 or, for some constant B. This is the set of all tuples z where the first coordinate of m is below a certain threshold 7. Since P[[x Ty = p.
{nh S B/B
(17/0) = p = 7 o o (p).
Therefore,
P E Tyn = = (2- = ( (p) B/o).
G ADDITIONAL CARTPOLE RESULTS
We performed two additional experiment on Cartpole: we tested at larger noise levels, (o 0.6 and 0.8) and we tested a variant of the agent architecture. Specifically, in addition to the agent shown in the main text, which uses five frames of observation, we also tested an agent which uses only single frame. Unlike the Atari environment, the task is in fact solvable (in the non -on-adveraaiaal case) using only one frame: the observation vector represents the complete system state. We computed certificates for the policy-smoothed version of this model, and tested attacks on the undefended version. (We did not test attacks on the smoothed single- frame variant). As we see in Figure 7 we achieve non-vacee vacuous certificates in both settings (i.c, at large perturbation sizes, the smoothed agent guaranteed to be more robust than the empirical robustness of a non-smoothed agent). However, observe that the undefended agent in the multi-frame setting much more vulnerable adversarial attack. This is likely because the increased number of total features (20 vs. four) introduces more complexity of the Q-network, making it more vulnerable against adversarial attack.
H FULL PONG GAME
In Figure g we explore a failure case of our technique: we fail to produce non-vacuous certificates for full Pong game, where the game ends after either player scores 21 goals. In particular, while, for the one-round Pong game, the smoothed agent is provably more robust than the empirical perfor- mance of the undefended agent, this clearly not the case for the full game. To understand why our certificate is vacuous here, note that in the the "worst-case" environment that our certificate assumes, any perturbation will (maximally) affect all future rewards. However, in the multi-round Pong game, each round of the game is only loosely coupled to the previous rounds (the ball momentum but not position - as well as the paddle positions are retained). Therefore, any perturbation can only have a very limited effect on the total reward. Another way to think about this is to recall that in smoothing- based certificates, the noise added to each feature is proportional to the total perturbation budget of the adversary. In this sort of serial game, the perturbation budget required to attack the average reward scales with the (square root of the) number rounds, but the noise tolerance of the agent does not similarly scale.
19

---

Published as a conference paper at ICLR 2022
(a) Cartpole (Muitiframe)
(b) Cartpole (Single Frame)
Certified Average Score
Certifeed Average Score
350
6.
322
100
73-
60-
50-
26
25-
6.0
Perturbation Budget
Perturbation Budieet
Figure 7: Additional Cartpole results. Attacks on smoothed agents all for the multiframe agents are presented in Appendix
(a) Pong (One-Round)
(b) Pong (Full)
20.0
0.1 Uncelesded
175
Vin Rate
1.-
0.00
0.56
0.10
315
920
0.25
A0
0.55
3.40
0.58
0.5
0.38
0i3
0,22
0:93
6.55
6.00
Perturbation Budget
Perturbation Budiett
Figure 8: Results for the Full Pong game, compared to the single-round game.
I TRAINING AND CLEAN TEST RESULTS
In Figure 9 we present the clean (non-attacked) test performance for the experiments presented in the main text, as a function the smoothing noise a.
we present the clean training (i.e., validation round) performance function of the training time step and the smoothing noise a. Note that early stopping was applied: the model from the best validation round was kept, and only replaced if strictly better validation performance was recorded later.
In Figure 10
For Cartpole: logs were not kept after the first time an evaluation round had perfect average score of 200 (this is because the "best model" was saved for this evaluation, and it would impossible to beat this score, so training was not continued). However, for other tasks (i.e. mountain car) logs continued after perfect evaluation round.
we trained times at each noise level, and kept the best of all models. All 5 training curves are shown here for each noise level.
For Freeway: as mentioned in Appendix Section L
J COMPLETE ATTACK RESULTS
In Figures and 12 we report the empirical robustness under attack for all tested values of Ag: in the main text, we show only the result for the λo that represents the strongest attack. Figure 12 also shows the attacks smoothed agents for all smoothing noises. All attack results are means over 1000 episodes (except for Mountain Car results, where 250 episodes were used) and error bars represent the standard emror of the mean.
20

---

Published as a conference paper at ICLR 2022
(a) Pong (One-Round)
Cartpole
1.40
0.3
174
0.20
Clean Success Rate
190
Clean Win Rate
0.85
125
0.80
-23
0.75
22
0.70
53
0.6
23-
0.60
64
Smoothing Noise
Sioothhing Noise
(c) Freeway (250 Frames)
Mountain Car
1.2
Average Clean Score
Surcess
0.
5:00
Smoothing
Smoothing Noise
Figure Clean test performance as function of smoothing noise a.
Pong (1 round) Training Performance
Cartpole Training Performance
2w04
0.75
150
022
2004
25:4
5:1e+6
130000
200000
50300
40000
Time Stop
Freeveey Training Performanee
Mountain Training
0:75
0:25
50000
100000
100000
200000
26000
Tim
Figure 10: Clean training performance as a function of smoothing noise and training step.
21

---

Published as a conference paper at ICLR 2022
(a) Rnu-Round Pong
(b) Full Pong
Undeenned tmpprcaa1 0.3
20.3
Uedifonded Erpince::20 -00 0.2
0.8
Undelandee 2m
17.5
15.2-
Score
Score
10.2-
Undefenddd Empaicat X
5.-
undelesded Emraacat
indeeesded Emppicak J
Imparce 1
Prepaien 1
2.00
0.03
0.13
0.5
0.28
0.5
0.50
0:35
0-40
0.00
Perturbation Budget
Perturbstion Budget
(c) Cartpole, Multiframe
(d) Cartpole. Single Frame
undelanded Empatial 3,0 4D0
Undefreced Ongince: 2.0 63
ordelnnded Empaical Q.Q
Underreced Ginl cn Q
2.0
Score
GA
0.4
Perturbation Budget
Perturbation Budget
(e) Freeway
(f) Mountain Car
Undefended Drpirizat c.0
Undstended Emopaical 1_2 - 0.00
Undelevddd Ei X - 6.05
Undatanded Emipiiaal A,C 5.0021
Undelonded Engericat 1.0 6.12
Undalended Empaical: à 2e-d5
Scole
Score
0.4
02-
aic
2.0
3.0
3.5
40
Perturbation Budget
Perturbation Budget
Figure II: Empirical robustness of undefended agents on for all tested values of do (or A). The results in the main text the pointwise minima over À of these curves.
22

---

Published as a conference paper at ICLR 2022
(a) Cartpole, Multiframe
(b) Pong (One-Round)
1.
0.-
ScoPe
broeiiul 1.0
Drrpecal 1.0 DJ3
35-
Cardiied Raand 11.)
Dmppiical. 1,0
56-
Cortilies Boand 0.10
Drigeical 1
0.2
Driaticd 1.0
0.00
0.10
6:15
0:29
Budget
Perturbetion Budget
(c) Freeway (250 Frames)
(d) Mountain Car
Averea pgergge Score
Rate
Cuntikod Baure 6.05)
Curtifed Baues lo 5.11
Emzitaal A.C 0.2
Centifie Boand is 0.21
Curtfnal Bonrd is (.4)
0.2
Emprical
Emprical Ie40
0.0
0.0
Six
0.00
Perturbation Budget
Perturbation Budget
Figure 12: Empirical robustness of smoothed agents on for all tested values of and bo (or A). We also plot the associated certificate curves.
K EMPIRICAL ATTACK DETAILS
Our empirical attack on (undefended) RL observations for DQN is described in Algorithm [ To summarize, the core of the attack is a standard targeted L2 PGD attack on the Q-value function. However, because we wish to "save" our total perturbation budget B for use in later steps, some modifications are made. First, we only target actions a for which the sufficiently below (by gap given by the parameter Aq) the Q-value of the 'best' action, which would be taken in the absence of adversarial attack. Among these possible Targets, we ultimately choose whichever action will maximally decrease the Q-value, and which the agent can be successfully be induced to choose within the adversarial budget B. If no such action exists, then the original observation will be returned, and the entire budget will be saved. In order to preserve budget, the PGD optimization is stopped as soon as the "decision boundary" is crossed.
Q-value is
We use constant step size 7). In order to deal with the variable budget B, we optimize of a number of iterations which is a constant multiple of B
For most environments, there is some context used by the Q-value function (i.e, the previous frames) which is carried over from previous steps, but not directly being attacked in this round. We need both the clean version of the context, C, in order to evaluate the "ground-truth values of the Q- value function under various actions; as well as the "dirty" version of the context, C", based on the adversarial observations which have already been fed to the agent, in order to run the attack optimization.
Our attack for DDPG is described in Algorithm| Here, action a the agent will take when it observes a corrupted observation o' (with corrupted context C'), and use the Q-value function supplied by the DDPG algorithm to determine the "value" of that action on the ground-trumt observation o. Because our goal is to minimize this value, this amounts to minimizing Q(C; o, क (C': In order to ensure that large amount of L2 "budget" is only used when the Q value can be substantially minimized, we include a regularization term A| o - -
the policy to determine what
Attacks smoothed agents descrihed in Appendix M
23

---

Published as a conference paper at ICLR 2022
I-Round
Full
Multiframe Cartpole
Single-frame Cartpole 0.99
Pong
Pong
Freeway
Training discount factor
0.99
0.99
0.99
0.99
Total timesteps
10000000
10000000
500000
500000
10000000
Validation interval (steps)
T00000
100000
2000
2000
100000
Validation episodes
100
10
10
10
100
Learning Rate
0.0001
0.0001
0.0001
0.00005
0.0001
DQN Buffer Size
10000
10000
100000
100000
10000
DQN steps collected
100000
100000
1000
1000
100000
before learning
Fraction of steps
0.1
0.1
0.16
0.16
0.1
for exploration (linearly
decreasing exp. rate)
Initial exploration rate
Final exploration rate
0.01
0.01
0
0.01
DQN target update
1000
1000
10
TO
1000
interval (steps)
Batch size
32
32
1024
1024
32
Training interval (steps)
4
4
256
256
4
Gradient descent steps
128
128
Frames Used
4
5
Training Repeats
1
Architecture
CNN*
CNN
MLP
MLP
CNN
20
4x
256x
256
256x
256x
2
2
Table 1: Training Hyperparameters for DQN models. *CNN refers to the 3-layer convolutional network defined by the CNNPolicy class in stable-baselines3 (Raffin al.] (019), based the CNN architecture used for Atari games by Mnih et al. (2015). Note that hyperparameters for Atari games based hyperparameters from the stable-base 3asel- Zoo package (Raffin 2020). for slightly different (more deterministic) variant of the Pong environment.
Note that on image data (i.e.. Pong), we do not consider integrality constraints on the observations; however, we do incorporate box constraints on the pixel values. We also incorporate box constraints on the kinematic quantities when attacking Mountain Car, but not when attacking Cartpole: the distinction is that the constraints in Mountain Car represent artificial constraints on the kinematics Ii.e.. the velocity of the car is arbitrarily clipped], while the constraints in Cartpole arise naturally from the problem setup.
L ENVIRONMENT DETAILS AND HYPERPARAMETERS
For Atari games, we use the "NoFrameskip-vo"" variations of these environments with the standard "AtariPreprocessing" wrapper from the OpenAl Gym (Brockman at. 2016) package: this provides This environment also injects non-determinism into the -riginally-dttermnnstii Atari games, by adding randomized "stickiness" to the agent's choice actions without this, the state-observation robustness problem could be trivially solved by memorizing winning sequence of actions, and ignoring all observations at test-time.
Due to instability in training, for the freeway environment, trained each model five times, and selected the base model based on the performance of validation runs. See training hyperparameters, TTalles T and 2 For attack hyperparameters, Table and
24

---

Published as a conference paper at ICLR 2022
Mountain Car
Training discount factor yy
0.99
Total timesteps
300000
Validation interval (steps)
2000
Validation episodes
10
Learning Rate
0.0001
DDPG Buffer Size
1000000
DDPG steps collected
100
before learning
Batch size
100
Update coefficient т
0.005
Train frequency
per episode
Gradient steps
episode length
Training action noise
Ornstein Uhlenbeck (a 0.5) MLP x 400 x 300
Architecture
Table 2: Training Hyperparameters for DDPG models.
Hyperparameters are based on hyperpa- rameters from the stable-bascling Zoo package (Raffin 2020), for the unmodified Mountain Car environment.
I-Round Pong
Full Pong
Multiframe Cartpole 0.01 2
Single-frame Cartpole 0.01
Freeway
Attack step size
0.01
0.01
0.01
Attack step multiplier
2
2
2
2 0, .0.66... .22
Q-value thresholds λg searched
1,,3, 5
1, 55
4,6,8,10
0, ,05, .1, 1
9, 1.3, 1.7
Table 3: Attack Hyperparameters for DQN models.
Mountain Car
Attack step size
0.01
Attack steps
100
Regularization values À searched
.001, .0000001000000 .00001
Table 4: Attack Hyperparameters for DDPG models.
25

---

Published as a conference paper at ICLR 2022
Algorithm 1: Empirical Attack DQN Agents
Input:
Q-value function Q, clean prior observation context C, adversarial prior observation context C", observation o, budget B, Q-value threshold yo. step size 1/, step multiplier
Output: Attacked observation Oweest, remaining budget B'.
Qelean m O,
Targets == {a E AlQ(C;o, & Qelean A²}
Qweest Qelean
Owerst = 0
for a E Targets do :=
inner:
for in ....
wB do
if arg max, QC""; :','o''c if QC; 0, < Q worst then
then
Oworst d
woostt = (C;o,a))
end
break inner
end
D V. log (S((sttMaax((((")dd)))) nD |
o'
o'
o' 2||2 > then
= 0 + d 0oo o)
end
end end
return Owarsás v B²
Oworst o11
Algorithm 2: Empirical Attack DDPG Agents
Input: Q-value function Q, policy म, clean prior observation context C, adversarial prior
observation context C", observation o, budget B, weight parameter X, step size 7), step
count т
Output: Attacked observation Owersts remaining budget B'.
== 0
for in ... do
D = V O (C':o')) + Aljo' - [
if D < 0.001 then
break
end
o' = 0' + nD
1
0 0|12 > then
o' o 1 (o' 0)
end
end
return 0', / B 0 7
26

---

Published as a conference paper at ICLR 2022
M ATTACKS ON SMOOTHED AGENTS
In order to attack smoothed agents, we adapted Algorithms 1 and using techniques suggested by Salman et al. (2019) for attacking smoothed classifiers. In particular, whenever the Q-value function is evaluated or differentiated, we instead evaluate/differentiae the mean output under m 128 smoothing perturbations. Following(Salman
al. (2019), we use the same noise perturbation vectors at each step during the attack. In the multi-trame case, for the "dirty" context C", we include the actually-realized smoothing perturbations used by the agents for previous steps. However, when determining the "clean" Q-values Q(C; o, a), for the "clean" context C, we use the unperturbed previous state observations: we then take the average over m smoothing perturbations of both C and to determine the clean Q-values. This gives an unbiased estimate for the Q-values of an undisturbed smoothed agent in this state.
When attacking DDPG, in evaluating Q(C:o, oC"; average over smoothing perturbationn for both o and , in addition to C: this because both т and Q are trained on noisy samples. Note that we independently-sampler
noise perturbations o' and o.
Our attack does not appear to be successful, compared with the lower bound given by our certificate (Figures 12 One contributing factor may be that attacking a smoothed agent is more difficult that attacking a smoothed classifier, for the following reason: a smoothed classifier evaluates the expected output test time, while smoothed agent does not. Thus, while the average Q-value for the targeted action might be greater than the average Q-value for the clean action, the actual realization will depend on the specific realization of the random smoothing vector that the agent actually uses.
N RUNTIMES AND COMPUTATIONAL ENVIRONMENT
Each experiment is run on an NVIDIA 2080 Ti GPU. Typical training times are shown in Table Typical clean evaluation times are shown in Table 6
Typical attack times are shown in Table 7
Experiment
Time (hours)
Pong (I-round)
11.1
Pong (Full)
12.0
Cartpole (Multi-frame)
0.27
Cartpole (Single-framm
0.32
Freeway
14.2
Mountain Car
0.63
Table 5: Training times
Experiment
Time (seconds): smallest noise a
Time (seconds):
Experiment
largest noise
Pong (I-round)
0.46
0.38
Pong (Full)
3.82
4.65
Cartpole (Multi-frame)
0.20
0.13
Cartpole (Single-frame)
0.18
0.12
Freeway
1.36
1.35
Mountain Car
0.67
0.91
Table 6: Evaluation times. Note that the times reported here are per episode: in order to statistically bound the mean rewards, we performed 10,000 such episode evaluations for each environment.
O CDF SMOOTHING DETAILS
Due to the very general form of our certification result (h(-), as a 0/1 function, can represent any outcome, and bound the lower-hound the probability of this outcome), there are variety of
27

---

Published as a conference paper at ICLR 2022
Experiment
Time (seconds): smallest budget B
Time (seconds): largest budget B
Experiment
Pong (1-round)
1.01
0.68
Pong (Full)
8.84
10.2
Cartpole (Multi-frame)
0.35
0.32
Cartpole (Single-frame)
0.79
0.56
Freeway Mountain Car
2.67
2.80
44.0
19.6
Table Attack times. Note that the times reported here are per episode: in the paper, we report the mean of 1000 such episodes.
(a) Cartpole, Multiframe: Point Estimation
(b) Cartpole, Multiframe: DKW
Micyy Manariang Deriiod
Fily Wreeth ru 02)
fallcy Smoattig:: Durtieed
Palcy Stoeth rg: Centted
eally kmooningg Comiteed
Folcyy Serectingg cartfee
13%
5c0re
100
100
72
50-
25-
0
Perturbation Budget
Perturbation Budiget
Figure 13: Comparison of certified bounds on the total reward in Cartpole, using (a) point estimation, and (b) the DKW inequality to generate empirical bounds.
ways we can use the basic result to compute a certificate for an entire episode entire game. In the main text, we introduce CDF smoothing Kumar et al. (2220) as such option. In CDF smoothing for any threshold value J, we can define (-) as an indicator function for the event that the total episode reward is greater than Then, by the definition of the CDF function, the expectation of (.).)) is equal to 1 1-1 Fz)), where F-)) is the CDF function of the reward. Then our lower- on the expectation of h-r(-) under adversarial attack is in fact upper-bound on F(x): combining this with Equation 2 in the main text,
E[A] = / (1 F(x))dr (1-F(=) - L F(x)dr,
provides a lower bound on the total expectation of the reward under adversarial perturbation.
However, in order to perform this integral from empirical samples, we must bound F(x) at all points: this requires first upper-bounding the non-adversarial CDF function at all æ, before apply- ing our certificate result. Following Kumar et al. (2020), we accomplish this using the Dvoret- zky-Kiefet-Wolfowiz inequality (for the Full Pong environment.)
In the case of the Cartpole environment, we explore a different strategy: note that the reward at each timestep itself 0/1 function, we can define (-)-) simply the reward at timestep We can then apply our certificate result at each timestep independently, and take a sum. Note that this requires estimating the average reward each step independently: we use the Clopper-Peane Pearson method (following Cohen et al. (2019), and in order to certify in total to the desired 95% confidence bound, we certify each estimate to (100- 5/T)% confidence, where T the total number of timesteps per episode (= 200).
However, note that, in the particular case of the cartpole environment, h.(-) = if and only we have "survived" to time-step in other words, hz(-) is simply an indicator function for the total reward being 2 t. Therefore in this case, this independent estimation method is equivalent to CDF smoothing, just using Clopper-Pearson point-estimates of the CDF function rather than the Dvoretzky-Kictte Wolfor-ttlfoitzz inequality. In practice, we find that this produced slightly better certificates for this task. (Figure
28

---

Published as a conference paper at ICLR 2022
P ENVIRONMENT LICENSES
OpenAl Gym Brockman et al. ( is Copyright 2016 by OpenAl and provided under the MIT License. The stable-baselines3 packag<Raftin et al. 2019) is Copyright 2019 by Antonin Raflin and also provided under the MIT License.
29


Reviews:
[{"review_id": "k6aZK_oJStv", "reviewer": "Reviewer_4eym", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "Pros:\nRegularization via augmentation with noisy samples has been a major focus of research in defending against inference-time adversarial perturbations. This paper advances the state of the art by presenting tight lower-bounds on the return of policies that are trained on randomly perturbed observations, when subjected to norm-limited adversarial perturbations of observations. This work also overcomes the limitations of prior work by Zhang et al. via extending the certification to the entire trajectory, and not just step-wise experiences of the agent.\nThe theoretical treatment of the problem is sound, and clearly stated.\nCons:\nIn multiple sections of the manuscript, authors claim that the proposal of policy smoothing is a novel contribution of their work. This does not seem to be the case, as numerous works in the literature have already proposed and investigated the regularization of RL policies via training on randomly and adversarially perturbed observations. \nIn the entirety of the presented analysis, there seems to be an implicit assumption that the adversary is aware of the observations of the target agent. This assumption is expressed more clearly in Algorithms 1 and 2. Do the authors assume that in the absence of the adversary, the target agent’s observation would be the same as the state? If so, this needs to be clearly stated in both the problem setup and the threat model.\nThe empirical results seem lacking. If policy smoothing is a focus of this study, the results should also report the effect of policy smoothing at both training and test-time under normal (i.e., non-adversarial) settings. This requires more information to be presented than just the single dot on the performance curves under adversarial attacks with 0 budget. \nIn the full Pong game, the certified lower-bound seems to be very loose compared to the presented results. While the interpretation presented in the appendix seems valid, it may be best to rethink the attack methodology to show that the lower-bound is meaningful.\nMinor comments:\n\nPage 2 - below equation 1: “...end after t time steps” - perhaps would be better to use upper-case T to avoid confusion in symbols. \n\nPage 8: “an attack tailored to the threat model defined in 1”\n", "summary_of_the_paper": "The paper presents theoretical lower bounds (i.e., certified robustness guarantees) on the performance of RL policies with randomized smoothing against norm-limited adversaries. The proposal of the paper is an extension of the Neyman-Pearson Lemma to the adaptive settings. Authors present formal proofs for their proposal, and evaluate their claims in 4 RL benchmarks.", "summary_of_the_review": "I find this paper to be a valuable contribution to the field, and believe that the theoretical treatment and methodology of this paper can inform future investigations in not only test-time adversarial robustness, but also the general analyses of sequential perturbations in RL.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "dbfyZmGJw9B", "reviewer": "Reviewer_6S68", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "I am glad to see RL-verification approach that considers traces, rather than just applying static verification techniques to individual time-steps.\nWhile the resulting algorithm is a straight-forward adaption of RS, I think the conceptual and mathematical arguments on how to apply it in this setting are the key strength of the paper.\nFurther, the main paper and the technical arguments in appendices B - D are well written and mostly easy to follow. The key mathematical results seem to be correct.\n\nThat said, the results indicate that the presented approach does not provide a usable defense for sequential-decision-making yet, as none achieved score-vs-budget trade-offs seems really desirable. While not ideal, I think the paper can still benefit the community by shifting focus on trace-based certificates in sequential decision making and is further valuable for its theoretical contributions.\n\nTo conclude I have a few questions:\n- In the tightness proof (section 4.2) you suddenly assume another policy $\\pi'$. Can you elaborate as to why the argument isn't over the initial $\\pi$ and why this change is possible?\n- Do you think it would be possible to utilize multiple temporally overlapping certificates to improve upon the budget-score trade-off?\n- [1] seems to provide similar guarantees to the proposed approach. Can you briefly outline the difference in approach?\n\n[1] CROP: Certifying Robust Policies for Reinforcement Learning through Functional Smoothing; Fan Wu et al.; arXiv 2021\n", "summary_of_the_paper": "The paper discusses the extension of randomized smoothing (RS) to sequential interactive settings, on the example of reinforcement learning (RL).\nThe authors show, that in order to certify a sequence of steps in this setting it the theory from RS can not be directly utilized as it does not account for the adaptiveness of the adversary/environment.\nTo enable the application of RS, the authors propose an adaptive version of the Neyman-Pearson Lemma, which can be used to instantiate RS to this setting.\nMathematically, this works by first showing that the impact of a potentially stochastic adversary can be bounded by a deterministic adversary, which in turn can be bounded by a deterministic adversary with special structure.\n\nEquipped with this theory, the authors introduce policy smoothing, an algorithm that lower-bounds on the reward (or other functions of the trace) that an agent will obtain (with high probability) in the presence of an adversary.\nThe authors showcase the effectiveness of the approach on the Cartpole, Mountain Car, Pong and Freeway for different deep RL agents.", "summary_of_the_review": "The paper presents a novel way to show robustness to perturbations in sequential decision making in the presence of an adversary.\nWhile empirical results are not strong, the paper appears to be formally correct and would benefit the community.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Os_ATDz31Ho", "reviewer": "Reviewer_xL3X", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "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": "Strengths:\nThis paper tries to tackle an important problem: how to get certified robustness in reinforcement learning (RL) problems. The method that the authors propose brings the gap between the randomized smoothing technique and RL.\n\nWeakness:\nI think this paper needs to be better polished in order to be published. I found several places that are quite hard to follow.\nI also find that the idea is quite incremental given that randomized smoothing has been widely studied in supervised learning and the key idea in this paper is quite similar. The authors mentioned that the Adaptive Neyman-Pearson Lemma is a non-trivial result, but I found that the discussion about this lemma is quite confusing.\n\nBelow are some detailed comments.\n\nI found Figure 1 quite hard to understand. It would be helpful to explain this figure better.\n\nI found that the problem formulation is a bit inconsistent throughout the paper. In Section 1, it seems to me that the adversary can only add $\\epsilon_i$ to the observation. Then I found that in Section 3, it is mentioned that the adversary can also choose a smoothing noise $\\delta_i$. It would be useful to clarify and make the formulation consistent. Is the distribution of $\\delta_i$ chosen before the algorithm starts? Does the adversary have to add $\\delta_i$ in the perturbation? For example, if the adversary believes that the $\\epsilon_i$ perturbation is strong enough, maybe it can skip adding $\\delta_i$?\n\nLemma 1: the symbol S has already been used to denote the state space.\n\nI am a bit confused about the construction of $Y^{st}$. Does it mean that the best strategy for the adversary is to put all the perturbation budget to the first time step? Is this phenomenon observed in the experiments or is it only for theoretical purpose?\n\nSection 4.3: can the authors provide more specific expressions for \"underline F\" and \"overline F\"?\n\n===After response===\n\nThanks to the authors for the response. Now I understand that system B is not the adversary; instead it is a virtually constructed system for the purpose of the proof. This makes more sense and helped me understand the paper better. However, it should be more explicitly explained in the paper what is the actual attack system (which part the adversary is allowed to perturb) and what is the virtual system used for analysis. Currently in Figure 2 of the paper, it still seems to me that system B is just the attacker.\n\nI increased my score but overall I still feel that there is a lot of room for improvement in terms of the clarify of the paper.\n\nI also feel that I am not familiar enough with the existing proof technique for randomized smoothing so I may not be able to evaluate the correctness very well. Thus I decided to lower my confidence score as well.", "summary_of_the_paper": "This paper studies certified robustness of a policy in a reinforcement learning setting. The authors propose a method, similar to randomized smoothing in supervised learning to get certified robustness for a policy. The authors provide theoretical evidence and experimental results.", "summary_of_the_review": "Overall, I found this paper a bit hard to follow and I don't think the key messages are clearly conveyed. I recommend the authors to carefully revise this paper in order to be published.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "IOscBRa3nxd", "reviewer": "Reviewer_LDzS", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "1. In the adversarial objective defined above equation (1), it appears as if the perturbation sequence $\\epsilon_t$ is fixed regardless of what actual state $s_t$ is observed, whereas from later sections it's obvious that the paper actually allows $\\epsilon_t$ to depend on $s_t$.\n\n2. What is \\Phi in Theorem 1?\n\n3. In the experiments, what exactly is the undefended agent? It is stated that the defense applies policy smoothing during both training and testing phases. So for the construction of undefended agents, are they constructed just via standard training, i.e. with no smoothing during training either?\n\nThe result in Figure 5 seems unintuitive because I would anticipate the undefended agent to perform somewhat better than the smoothed policy when there is no adversarial perturbation, as intuitively techniques such as smoothing must deteriorate the performance in a clean environment. \n\nI'm not very familiar with the Neyman-Pearson Lemma, but it seems unintuitive to me that in Lemma 3, one can provide a robustness guarantee against an adaptive adversary from the construction of a much weaker adversary. Some remarks and background regarding the Neyman-Pearson Lemma would be helpful.\n", "summary_of_the_paper": "This paper extends the smoothing technique to the RL setting as a defense to test-time adversarial attacks. An adaptive version of the Neyman-Pearson Lemma is proposed. Empirical evaluations showcase the effectiveness of policy smoothing.", "summary_of_the_review": "Experiment results seem convincing, except for some minor issues. I'm not familiar with the prior literature to judge the significance of the new Neyman-Pearson Lemma. The exposition can certainly be improved to make the paper more self-contained and readable. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "9_ajt8UNqiH", "reviewer": "Reviewer_RqNT", "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": "> In general, I think this paper is clearly written and easy to follow. The proposed method is intuitive and the experimental results are convincing. Studies on RL robustness are still limited and many questions remain open. \n\n> A major competitor of this paper is Zhang et al, NeurIPS 2020, which reduced the significance of contribution. But I agree that the authors adequately discussed the connection and difference between their work and the related works. Also, though the philosophy is borrowed from Cohen et al, randomized policy smoothing is still a completely new approach for defending RL models.\n\n> I would also point out that the formulation of $\\bar{\\pi}$ in Section 4.3 is very similar to a POMDP and I guess that the authors did not realize this. I think it would be better if the authors can provide some discussions on this matter. Similar connections are also mentioned in Zhang, et al. \"Robust reinforcement learning on state observations with learned optimal adversary.\" ICLR 2021, which I think the authors may also need to include in the reference.", "summary_of_the_paper": "This paper proposed a method for RL agents' robustness certification for using randomized smoothing. An adaptive Neyman-Pearson Lemma is developed and a robustness guarantee in terms of the cumulative reward is obtained. This paper also gives a worst-case setting to prove the tightness of the aforementioned certification and also evaluate their certificates in two environments under adversarial attacks.", "summary_of_the_review": "This paper studies an important and novel problem with limited works in the literature: RL agents' robustness certification. The authors made strong assumptions and borrow ideas (randomized smoothing) from existing works in similar fields. The contribution is obvious, though not very significant. I am positive about this paper and recommend a weak acceptance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers appreciated the treatment of the topic of certifiable robustness done in this work and although they had a number of concerns, I feel they were adequately addressed by the authors.
Decision: Accept (Poster)