CROP: Certifying Robust Policies for Reinforcement Learning through Functional Smoothing
Authors: Fan Wu
Linyi Li
Zijian Huang
Yevgeniy Vorobeychik
Ding Zhao
Bo Li
Venue: ICLR 2022 Poster (2022)

Abstract: As reinforcement learning (RL) has achieved great success and been even adopted in safety-critical domains such as autonomous vehicles, a range of empirical studies have been conducted to improve its robustness against adversarial attacks. However, how to certify its robustness with theoretical guarantees still remains challenging. In this paper, we present the ﬁrst uniﬁed framework CROP (Certifying Robust Policies for RL) to provide robustness certiﬁcation on both action and reward levels. In particular, we propose two robustness certiﬁcation criteria: robustness of per-state actions and lower bound of cumulative rewards. We then develop a local smoothing algorithm for policies derived from Q-functions to guarantee the robustness of actions taken along the trajectory; we also develop a global smoothing algorithm for certifying the lower bound of a ﬁnite-horizon cumulative reward, as well as a novel local smoothing algorithm to perform adaptive search in order to obtain tighter reward certiﬁcation. Empirically, we apply CROP to evaluate several existing empirically robust RL algorithms, including adversarial training and different robust regularization, in four environments (two representative Atari games, Highway, and CartPole). Furthermore, by evaluating these algorithms against adversarial attacks, we demonstrate that our certiﬁcations are often tight. All experiment results are available at website https://crop-leaderboard.github.io.

Published as a conference paper at ICLR 2022
CROP: CERTIFYING ROBUST POLICIES FOR RE- INFORCEMENT LEARNING THROUGH FUNCTIONAL SMOOTHING
Fan Wu-
Linyi Li University of Illinois Urbana-Champaign
Zijian Huang'
Yergeniy Vorobeychik Ding Zhao
Bo Li
Washington University in St. Louis
CCamegic Mellon University (fanwe, iny zi jianh4, cingzhac@andrewt cmu.edu
edu
yrorcbeychikkwust1.cm
ABSTRACT
As reinforcement learning (RL) has achieved great success and been even adopted in safety-critical domains such as autonomous vehicles, a range empirical studies have been conducted to improve its robustness against adversarial attacks. However, how to certify its robustness with theoretical guarantees still remains challenging. In this paper, Policies for RL) to provide robustness certification on both action and reward levels. In particular, we propose of per-state actions and lower bound of cumulative rewards. We then develop a local smoothing algorithm for policies derived from Q-functions guarantee the robustness of actions taken along the trajectory; we also develop global smoothing algorithm for certifying the lower bound of a unite-horizon cumulative reward, as well as novel local smoothing algorithm to perform adaptive search in order to obtain tighter reward certification. Empirically, we apply CROP to evaluate several existing empirically robust RL algorithms, including adversarial training and dif- ferent robust regularization, in four environments (two representative Atari games, Highway, and CartPole). Furthermore, by evaluating these algorithms against adver- sarial attacks, we demonstrate that our certifications are often tight. All experiment results are available website https: http::://rroo--eaaabboorro.oe
present the first unified framework CROP (Certifying Robust
robustness certification criteria: robustness
INTRODUCTION
Reinforcement learninnn (RL) has been widely applied to different applications, such as robotics (Kober et al., 2013 Deisenroth et al. 2013 Polydoros & Nalpantidis. 2017). autonomous driving vehi-
cles (Shalev-Shwarl et al.] 2016; Sallab et al. 2017). and trading (Deng et al. 2016 Ammadi
Yang. 2017 Ye a 2020). However, recent studies have shown that learning algorithms
vulnerable to adversarial attacks (Goodfelloow et al. 2014: Kurakin et al.) 2016) Moosavi-Dezfooli
(et al., 2016 Jia & Liang 2017 Eykholt et al. 2018). ), and range of attacks have also been proposed against the input states and trained policies of RL (Huang et al. 2017: Kos & Song 2017 Lin et al.
2017 Behzadan & Munir 2017a). As more and more safety-critical applications are being deployed in real-world (Christiano et al. 2016 Fisac et al. 2018 Cheng et al. 2019, coo)) how to test and improve their robustness before massive production is of great importance.
2019,cop),
To defend against adversarial attacks in RL, different empirical defenses have been proposed (Man
dlekar et al., 2017 BBhzzdann & Munir 201 Pattanaik al. 2018) Fischer et al. 2019 Zhang et al.
10200/Oikaring et 20.0 Donti et al.] 2000 Shen et al. 2020 Eysenbach & Levine 202 1). In
particular, adversarial training (Kos & Song. 2017 [ehhzdan & Munir [01 7b) Pattanaik et al. 201
and regularized RL algorithms by enforcing the smoothness of the trained models (Shen et al. 2020
Zhang et al. 2020 have been studied to improve the robustness of trained policies. However, several strong adaptive attacks have been proposed against these empirical defenses (Gleave et al. 2019
Hussenot et al. 2019 Russo & Proutiere 2019) and it important to provide robustness certification for given learning algorithm to end such repeated game between attackers and defenders.

---

Published as a conference paper at ICLR 2022
To provide robustness certification, several studies have been conducted on classification. For instance,
both deterministic (Ehlers) 2017] Katz
Katz et al. 2017: CCheng et al.,
2017 Tieng et al. 2017;] Weng et al.)
2018
Zhang et al. 2018: Singh et al. 2019: Gehr et al. 2018 Wong & Kolter [2018] Raghunathan
et al.
2018) and probabilistic approaches (1 (Luuyer et al. 2019 Cohen et al. 2019 Lee et al. 2019)
Salman et al. 22199] Carmon al. 2019 [eong & Shin 2020p have been explored to provide lower
bound of classification accuracy given bounded adversarial perturbation. Considering the sequential decision making property of RL, which makes it more challenging to be directly certified compared to classification, in this paper we ask: How to provide efficient and effective robustness certification for RL algorithms? What criteria should be used to certify the robustness of RL algorithms?
Different from classification which involves one-step prediction only, RL algorithms provide both action prediction and reward feedback, making what to certify and how to certify robustness of RI. challenging. In this paper we focus on Q-learning and propose two certification criteria: per-state action stability and lower bound of perturbed cumulative reward. In particular, to certify the per-state action stability, we propose the local smoothing on each input state and therefore derive the certified radius for perturbation at each state, within which the action prediction will not be altered. To certify the lower bound of cumulative reward, we propose both global smoothing over the finite trajectory to obtain the expectation or percentile bounds given trajectories smoothed with sampled noise sequences; and local smoothing calculate absolute lower bound based on our adaptive search algorithm.
We leverage our framework to test nine empirically robust RL algorithms on multiple RI. environ- ments. We show that the certified robustness depends both the algorithm and the environment properties. For instance, RadiaIRL (Oikarinen et al. (020) is the most certifiably robust method on Freeway. In addition, based on the per-state certification, we observe that for some environments such as Pong, some states are more certifiably robust and such pattern is periodic. Given the information of which states are more vulnerable, is possible to design robust algorithms to specifically focus on these vulnerable states. Based on the lower bound of perturbed cumulative reward, we show that our certification is tight by comparing our bounds with empirical results under adversarial attacks.
Technical Contributions. In this paper, we take an important step towards providing robustness certification for Q-learning. We make contributions on both theoretical and empirical fronts.
We propose a framework for certifying the robustness of Q-Jearning algorithms, which is notably the first that provides the robustness certification w.r.t. the cumulative reward.
We propose two robustness certification criteria for Q-learning algorithms, together with corre- sponding certification algorithms based on global and local smoothing strategies.
We theoretically prove the certification radius for input state and lower bound of perturbed cumula- tive reward under bounded adversarial state perturbations.
We conduct extensive experiments to provide certification for nine empirically robust RL algorithms on multiple RL environments. We provide several interesting observations which would further inspire the development of robust RL algorithms.
PRELIMINARIES
Q-learning and Deep Q-Networks (DQNs). Markov decision processes (MDPs) are at the core of RL. Our focus is on discounted discrete-time MDPs, which are defined by tuple (S,A, R, dod) where is a set of states (each with dimensionality N), A represents a set of discrete actions, R S A + IR is the reward function, and P S x A + P(S) is the transition function with P()) defining the set of probability measures, 7 E [0, 1] is the discount factor, and dg E P(S) is the distribution over the initial state. At time step f, the agent is in the state 8: E S. After choosing action a, E A. the agent transitions to the next state $1+1 ~ P(st, a:) and receives reward R(st, az). The goal is to learn a policy π: S + P(A) that maximizes the expected cumulative reward E E|E, ?'re).
Q-learning Watkins & Dayan, 1992) learns an action-value function (Q-function), Q a). which is the maximum expected cumulative reward the agent can achieve after taking ac- tion a in state s: (*)s,a) = -R(s,a) + + + ''MP(e,))
E [max, (*(s',a)) In deep Q-Networks
(DQNs) (Mnih et al., 2013). Q" is approximated using a neural network parametrized by 0, i.e. (" o; 0) ss (=) Let p E P(S x A) be the observed distribution defined over states s and actions a, the network can be trained via minimizing loss function L()) = E (s.a)=p.s~~Pss.a))
[A(s, a) + y maxa Qa (s', a';a) Q" (s. 0))]] The greedy policy π is de-
fined as taking the action with highest Q" value in each state 8: क (s) arg max.e.A Qa (s,
2

---

Published as a conference paper at ICLR 2022
Certified Robustness for Classifiers via Randomized Smoothing. Randomized smoothing (Co hen et al, 2019) has been proposed to provide probabilistic certified robustness for classification. It achieves state-of-the-art certified robustness
large-scale datasets such as ImageNet under éz- bounded constraints (Salman et al. 2019) Yang et al., 2020). In particular, given a base model and test. instance, smoothed model is constructed by outputting the most probable prediction over different Gaussian perturbed inputs.
3 ROBUSTNESS CERTIFICATION IN Q-LEARNING
In this section, we first introduce the threat model, followed by two robustness certification criteria for the Q-learning algorithm: per-state action and cumulative reward. We consider the standard adversarial setting in Q-learning (Huang al. 2017 Kos & Song 2017 Zhang et al. 2022)), where the
adversary can apply (2-bounded perturbation B {6 E l
| [o E to input state observations
of the agent during decision (test) time cause the policy select suboptimal actions. The agent
observes the perturbed state and takes action a' = π + 6). following policy х. Following the Kerckhoff's 's principle (Shannon 1949), J consider worst-case adversary who applies adversarial perturbations to every state at decision time. Our analysis and methods are generalizable to other ép
norms following (Ynng et al. 2020 Lecuyer al. 2019).
3.1 ROBUSTNESS CERTIFICATION FOR Q-LEARNING WITH DIFFERENT CRITERIA
To provide the robustness certification for Q-learning, we propose two certification criteria: per-state action robustness and lower bound of the cumulative reward.
Robustness Certification for Per-State Action. We first aim to explore the robustness (stabil- ity/consistency) of the per-state action given adversarially perturbed input states.
Definition (Certification for per-state action). Given a trained network Q with policy æ, we define the robustness certification for per-state action as the maximum perturbation magnitude E, such that for any perturbation E B the predicted action under the perturbed state will be the same as the action taken in the clean environment, i.e., π (s 5) Ts)) V5 B
Robustness Certification for Cumulative Reward. Given that the cumulative reward is important for RL, here in addition to the per-state action, we also define the robustness certification regarding the cumulative reward under input state perturbation.
Definition 2 (Cumulative reward). Let P S A - P(S) be the transition function of the environment with P.)) defining the set of probability measures. Let R, do, Q", x be the reward function, initial state distribution, discount factor, given trained Q-network, and the corresponding greedy policy introduced in ineection 2 J(xr) represents the cumulative reward and J=(T)) represents the perturbed cumulative reward under perturbations 5, E each time step t:
20 Je(m) : =(m)==Ix+ T(s, 6.)). 1-0
J(x)== = - H(s.. ((s)),
and
(I)
where 8141 ~ P(Se, ((: + 6z)), su ~ do- The randomness of ((x) arises from the environment dynamics, while that of Jg(T) includes additional randomness from the perturbations {6e}. We focus on finite horizon H in this paper, where a sufficiently large H can approximate J(T) and J=(m) ) to arbitrary precision when ? 1. Definition 3 (Robustness certification for cumulative reward). The robustness certification for cumulative reward is the lower bound of perturbed cumulative reward J such that J < Je(T) under perturbation in E {8 Rd ||ō1|2 &) applied to all time steps.
where 8141 P(st, az), So du.
We will provide details the certification of per-state action in Sectiin and the certification of cumulative reward in Section 3 based on different smoothing strategies and certification methods.
4 ROBUSTNESS CERTIFICATION STRATEGIES FOR
ACTION
In this section, we discuss the robustness certification for ptr-state action, aiming to calculate a lower bound of maximum perturbation magnitude in Definition I.
4.1
CERTIFICATION FOR PER-STATE ACTION VIA ACTION- VALUE FUNCTIONAL SMOOTHING
Let Q" be the action-value function given by the trained network Q with policy и. We derive smoothed function Q through per-state local smoothing. Specifically, at each time step t, for each action a A, we draw random noise from Gaussian distribution A (0, o² IN) smooth Q (:.a).
3

---

Published as a conference paper at ICLR 2022
E Q"(s: + a),a) Vsa S A, and (st) argmax Q" (st.a) Vsa S. ²" (st, a)) AmMA)..01N))
(2)
Lemma (Lipschitz continuity of the smoothed value function). Given the action-value function functioon Q" with smoothing parameter a is L-Lipschitz Vmmn 22/z w.r.f. the state input.
Q=: SSX x A + [Vnino V Vmax), the smoothed function
continuous with L Vema
The proof is given in Apppeddix A. Leveraging the Lipschitz continuity in Lemma I
we derive the
following theorem for certilying the robustness of per-state action.
Theorem 1. Let QF S x A + [Vmin: Vmaxx] be a trained value network, Q be the smoothed func- fion with 2 At time step with state St, we can compute the lower bound ri of maximum perturbation magnitude ((t)) (i.e., It S E(st), defined in Definition 1 for locally smoothed policy R:
Vinin
(8,, (:2) Viuin
T8 Φ-
----1
Vinax
Vinin
Vimax
Vnnin
where 4-1 is the inverse CDF function, a is the action with the highest Q value at state 8t, and 02 is the runner-up action. We name the lower bound rt as certified radius for the state St.
The proof is omitted to Appendix A.2 The theorem provides a certified radius r, for per-state action given smoothed policy: As long as the perturbation is bounded by Tr, i.e., ||x1|2 S Tr, the action does not change: (8; + ) = # (s+).. To achieve high certified robustness for per-state action. Theorem I implies a tradcoff between value function smoothness and the margin between the values top two actions: If larger smoothing parameter is applied, the action-value function would be smoother and therefore more stable; however, it would shrink the margin between the top two action values leading smaller certified radius. Thus, there exists a proper smoothing parameter balance the tradeoff, which depends on the actual environments and algorithms.
4.2 CROP-LOACT: LOCAL RANDOMIZED SMOOTHING FOR CERTIFYING PER-STATE ACTION
Next we introduce the algorithm to achieve the certification for per-state action. Given a Q" network, we apply 2 to derive a smoothed network Q At each state s,, we obtain the greedy action ãr w.r.t. Q*, and then compute the certified radius rt- We present the complete algorithm in Appendix B.
There are some additional challenges in smoothing the value function and computing the certified radius in Q-learning compared with the standard classification task (Cohen al. 2019). Challenge I: In classification, the output range of the confidence [0. 1] is known a priori; however, in Q-learning, for given QT, its range [Vmin; Vmax] is unknown. Challenge 2: In the classification task, the lower and upper bounds of the top two classes' prediction probabilities can be directly computed via the confidence interval base on multinomial proportions (Goodman) 1965). For Q-networks, the outputs are not probabilities and calculating the multinomial proportions becomes challenging.
Pre-processing. To address Challenge 1, we estimate the output range [Vmin: Vnux] of given network Q based on finite set of valid states Spub C S. In particular, we craft sufficiently large set Scub to estimate Vmin and Viaax for Q* on S, which can be used later in per-state smoothing. The details for estimating Vinin and Vmax are deferred to Appendix B.
Certification. To smooth a given state 8t, we use Monte Carlo sampling (Cohen et al., 2019) to sample noise applied to st, and then estimate the corresponding smoothed value function Q at 8 with D In particular, we sample m Gaussian noise A; ~ (N, I²IN), clip the Q-network output to ensure that it falls within the range [Vmin, Vmax), and then take the average of the output to obtain the smoothed action prediction based on Q We then employ Theorem to compute the certified radius Tt. We omit the detailed inference procedure to Appenddxx B.I] To address Challenge 2, we leverage Hoeffding's 's inequality (Hoeffding 1994) to compute a lower bound of Q (s,, ai) and an upper bound of Q (st, a12) with one-sided confidence level parameter given the top two actions aj and ag- When the former is higher than the latter, we can certify a positive radius for the given state 8,-
5 ROBUSTNESS CERTIFICATION STRATEGIES FOR THE CUMULATIVE REWARD
In this section, we present robustness certification strategies for the cumulative reward. The goal is to provide the lower bounds for the perturbed cumulative reward in Defeinitionn In particular, propose both global smoothing and local smoothing strategies to certify the perturbed cumulative reward. In the global smoothing, view the whole state trajectory as function to smooth, which
4

---

Published as a conference paper at ICLR 2022
would lead to relatively loose certification bound. We then propose the local smoothing by smoothing each state individually to obtain the absolute lower bound.
5.1 CERTIFICATION OF CUMULATIVE REWARD BASED ON GLOBBL SMOOTHING
In contrast to Secctonnn 4 where we perform per-state smoothing to achieve the certification for per-state action, here, we aim perform global smoothing on the state trajectory by viewing the entire trajectory as function. In particular, we first derive the expectation bound of the cumulative reward based on global smoothing by estimating the Lipschitz constant for the cumulative reward w.r.t. the trajectories. Since the Lipschitz estimation in the expectation bound is algorithm agnostic and could lead to loose estimation bound, we subsequently propose a more practical and tighter percentile bound.
Definition 4 (ø-randomized trajectory and o-randomized policy), Given state trajectory (so, $1..... :......,.:11)) of length H where St+1 ~ P(s,, (s:)), so ~ do. with ı the greedy policy of the action-valie function Q²,, we derive o-randomized trajectory as (5/g ,', -HH where 5/41 P(s',, As)) A, (00, IN), and 6/ so dg- We correspondingly define o-randomized policy n' based on ı in the following form: T' T'()) == ((+ + At) where A, ~ ~N((0,0"
Let the operator @ concatenates given input states or noise that added to each state. The sampled noise sequence is denoted by A = Ac, where A, (0,
Definition 5 (Perturbed return function). Let R. Y, dg be the reward function, transition function, discount factor, and initial state distribution in Definition 2] We define a bounded perturbed return function Fx INN
+ [Jmin Jmaxl representing cumulative reward with potential perturbation 8:
Fx ( = Σ 7 M(.., (s+ + 6.)), where $141 ~ P(st, + 6.)), 80 ~ do-
(4)
We can see when there is no perturbation (6, 0), Fe 0) = J(T); when there are adversarial perturbations 5, E B at each time step, Fr (0 5)) = (T(),, i.e., perturbed cumulative reward.
Mean Smoothing: Expectation bound. Here we propose to sample noise sequences A to perform global smoothing for the entire state trajectory, and calculate the lower bound of the expected per- turbed cumulative reward EA [J=(m')] under all possible bz-bounded perturbations within magnitude e. The expectation is over the noise sequence A involved in the o o-randomized policy n' in Definition 4
Lemma (Lipschitz continuity of smoothed perturbed return function). Let F be the perturbed return /2/x-
function function defined in (4) the smoothed perturbed return function F=, is Jmin-JJim) Lipschitz continuous, where Fz (4b11116))) = -0.
Fx (# (5, + ++)).
Theorem (Expectation bound). Let JF= = Fa (0 (eH-10 0)) -LEV H. where L (Jmar Jmin) Then JE S E [T)).
2/
Proof Sketch. We first derive the equality between expected perturhed cumulative reward E [J= (T') and the smoothed perturbed return function Fr ( 6,). Thus, to lower bound the former, suffices to lower bound the latter, which can be calculated leveraging the Lipschitz continuity of F Lemma 2 (proved in Appendix A.3), noticing that the distance between @ 0 and the adversarial perturbations @ 5, is bounded by ev H. The complete proof is omitted to Appendix A.4
We obtain Mmin and Jmax in Lemma 2 from environment specifications which can be loose in practice. Thus the Lipschitz constant L estimation is coarse and mean smoothing is usually loose. We next present method that circumvents estimating the Lipschitz constant and provides tight percentile bound.
Percentile Smoothing: Percentile bound. We now propose to apply percentile smoothing to smooth the perturbed cumulative reward and obtain the lower bound of the p-th percentile of [T'r', where n' is o o-randomized policy defined in Definition 4
F ( 5.) sup, {o E 1R 1P F. (e"- (8. -i)) s v sp).
(5)
Theorem (Percentile bound). Let Jr Fe' (#/ 0), where p' +b (Φ (p) evT//). Then Jp & the p-th percentile of J=('').
The proof is provided in Appendix A.5 based on Chiang et al. 2020). There are several other advantages of percentile smoothing over mean smoothing. First, the certification given by percentile
5

---

Published as a conference paper at ICLR 2022
smoothing is among the cumulative rewards of the sampled o-randomized trajectories and is therefore achievable by a real-world policy, while the expectation bound is less likely to be achieved in practice given the loose Lipschitz bound. Second, for discrete function such perturbed return function, the output of mean smoothing is continuous w.r.t. a, while the results given by percentile smoothing re- main discrete. Thus, the percentile smoothed function preserves properties of the base function before smoothing, and shares similar interpretation, e.g., the number of rounds that the agent wins. Third, taking p 50% in percentile smoothing leads to the median smoothing which achieves additional properties such as robustness to outliers (Manikandan 2011). The detailed algorithm CROP-GRE, in- cluding the inference procedure, the estimation of Fx. the calculation of the empirical order statistics, and the configuration of algorithm parameters J Jmin Jmax are deferred to Appendix B.2
5.2
CERTIFICATION OF CUMULATIVE REWARD BASED ON LOCAL SMOOTHING
Though global smoothing provides efficient and practical bounds for the perturbed cumulative reward, such bounds are still loose as they involve smoothing the entire trajectory once. In this section, we aim to provide a tighter lower bound for Je (f) by performing local smoothing.
Given a trajectory of H time steps which is guided by the locally smoothed policy म, we can compute the certified radius at each time step according to [Theorem I, which can be denoted as Tu. ".. Recall that when the perturbation magnitude step will remain unchanged. This implies that when æ min rt. none of the actions in the entire trajectory will be changed, and therefore the lower bound of the cumulative reward when E < min has two effects. First, the total number of time steps where the action is susceptible to change will increase; second, at each time step. the action can change from the best to the runner-up or the rest. We next introduce an extension of certified radius r, to characterize the two effects.
Tr, the optimal action a at time
H-1 Tt is the return of the current trajectory in a deterministic environment. Increasing
Theorem 4. Let (r2....,77) .,. ) be a sequence of certified radii for state st at time step t, where rf denotes the radius such that if < rū, the possible action at time step t will belong to the actions corresponding to top k action values of Q at state St. The definition of Te in Theorem 1 to r, here. The radii can be computed similarly as follows:
is equivalent
r 1== ( 10
(0
(0-((1))))) VVaax- - Vmnin
Viin
(Q"(s1,ax+1) Vinin
))
(
16-1
I
Vmax - Vinin
where 01 is the action of the highest Q value at state St and ax+1 the (k + 1)-th best action. We additionally define (sx) )=)= = O, which is also compatible with the definition above.
We defer the proof in Appendix A.6 With Theorem 4 for any given E, we can compute all possible actions under perturbations in B= This allows exhaustive search traverse all trajectories satisfying that all certified radii along the trajectory are smaller than E. Then, we can conclude that (a) is lower bounded by the minimum return over all these possible trajectories.
5.2.1 LORE- LOCAL SMOOTHING FOR CERTIFIED REWARD
Given policy æ in deterministic environment, let the initial state be 8p, we propose CROP-LORE to certify the lower bound of (7). At high-level, CROP-LORE exhaustively explores new trajectories leveraging Theorem 4 with priority queue and effectively updates the lower bound of cumulative reward J by expanding a trajectory tree dynamically. The algorithm returns collection of pairs ((c,, Js,) ) sorted in ascending order of E;, where |C| is the length of the collection. For all e', let i be the largest integer such that e; S E' < Es+1, then as long as the perturbation magnitude E S E', the cumulative reward Je (+t) 2 Je.- The algorithm is shown in Algorithm 3 in Appendix B.3
Algorithm Description. The method starts from the base case: when perturbation magnitude e the lower bound of cumulative reward J is exactly the benign reward. The method then gradually increases the perturbation magnitude& e (later we will explain how a new E determined). Along the increase of e, the perturbation may cause the policy æ to take different actions at some time steps. thus resulting in new trajectories. Thanks to the local smoothing, the method leverages Theorem 4 to figure out the exhaustive list of possible actions under current perturbation magnitude and effectively explore these new trajectories by formulating them as expanded branches of a trajectory tree. Once all new trajectories are explored, the method examines all leaf nodes of the tree and figures out the minimum reward among them, which is the new lower bound cumulative reward J under this new s. To mitigate the explosion of branches, CROP-LORE proposes several optimization tricks.

---

Published as a conference paper at ICLR 2022
Sidfrein
Counsnay
Tren
SA-MPP (PGD]
SA-FPP (DV10
RedielR
No sy/le
GreNDON
1.00
Ie-1
2.50
Radia
2.00
1.50
0.53
9:50
Ie-4
120
202
752
460 500
Le-5
140
200
100
400
500
100 203
300
430 520
233
225
250
420
500
320
200
300
400
300
100
200
303
407
502
3.00
1.20
Radiux
1.00
0.75
4.00
2.00
6.50
2.00
2.00
0:25
0.00
0.00
0:00
time step
time step
time step 2
time step
time step
time step
Figure 1: Robustness certification for per-state action in terms of certified radius r at all time steps. Each column corresponds to a smoothing variance a. The shaded area represents the standard deviation which is small. RadialRL is the most certifiably robust method on Freeway, while SA-MDD (CVX) is the most robust on Pong.
In the following, we will briefly introduce the trajectory exploration and expansion and growth of periurbation magnitude steps, as well as the optimization tricks. More algorithm details are deferred to Appendix B.3, where we also provide an analysis on the time complexity of the algorithm.
In trajectory exploration and expansion, CROP-LORE organizes all possible trajectories in the form of search tree and progressively grows it. For each node (representing a state), leveraging The
|AI-1 representing the required perturbation radii for π to choose each alternative action. Suppose the current e satisfies (s) S E < (s), we can grow (i + 1) branches from current state corresponding to the original action and alternative actions since 2 (s) for 1 j S i. We expand the tree branches using depth- -frst search (Tarjan 1972). In perturbation magnitude growth, when all trajectories for perturbation magnitude e are explored, we increase e to seek certification under larger perturbations. This is achieved by preserving a priority queue (van Emde Boas 1977) of the critical e's that we will expand on. Concretely, along the trajectory, at each tree node, search for the possible actions and store actions corresponding to {s) into the priority queue, since these actions are exactly those need to explored when e grows. We repeat the procedure of periurbation magnitude growth (i.e., popping out the head element from the queue) and trajectory exploration and expansion (i.e., exhaustively expand all trajectorics given the perturbation magnitude) until the priority queue becomes empty or the perturbation magni- tude reaches the predefined threshold. Additionally, we adopt a few optimization tricks commonly used in search algorithms to reduce the complexity of the algorithm, such as pruning and the mem- orization technique (Michie 1968). More potential improvements are discussed in in[pppendix B.3]
orem 4 we compute a non-decreasing sequence (s) k==
So far, we have presented all our certification methods. In Appendix C. we further discuss the advantages, limitations, and extensions of these methods, and provide more detailed analysis to help with understanding.
EXPERIMENTS
In this section, we present evaluation for the proposed robustness certification framework CROP. Con- cretely, we apply our three certification algorithms (CROP- CROP-GRE, and CROP-LORE) to certify nine RL methods (StdTrain (Mnih et al.) 2013). GaussAug (Kos & Song 2017), Adv- Train (Behzadan & Munir 2017b), SA-MDP (PGD,CVX Zhhng al. 2020). RadiaIRL (Oikari) nenn et al. 2020). CARRL (Everett et al., 2021). NoisyNet (Fortunato et al.] 2017). and Grad- DQN Patttanakk et al. 2018) two high- -ighh-imnnsional Atari games (Pong and Freeway), one low dimensional control environment (CartPole), and an autonomous driving environment (Highway). As summary, we find that (1) SA-MDP (CVX), SA-MDP (PGD). and RadialRL achieve high certified ro- bustness in different environments: (2) Large smoothing variance can help to improve certified robust- ness significantly
Freeway, while more careful selection of the smoothing parameter is needed in Pong; (3) For methods that demonstrate high certified robustness, our certification of the cumulative re- ward is tight. We defer the detailed descriptions of the environments to Appendixx and the introduc- tion to the RL methods and implementation details to AApenddxx D.2 More interesting results and dis- cussions are omitted to to/Appendix Eland our leaderboard, including results on CartPole (Appendix E.6) and Highway (Appendix E.7). As a foundational work providing robustness certification for RL, we expect more RI. algoritmms and RI. environments will be certified under our framework future work.
6.1 EVALUATION OF ROBUSTNESS CERTIFICATION FOR PER-STATE ACTION
7

---

Published as a conference paper at ICLR 2022
Freeway
Pong
aaliv reward)
35
In this subsection, we provide the robustness certification evaluation for per-state action.
50
Scfah
15
60
Lumulahis
-10
-55
SA XDX (CV0
St. MDP
-35
Razigal)
Experimental Setup and Met- rics. We evaluate the locally
-200
Gradi-df
Se-3
16.1
56.1
7.5ml
10-3
50-3
10-3
3n-3
36.1
smoothed policy क derived in 2 We follow Theorem I and report the certified radius Y2 at each step L.
Figure Benign performance locally smoothed policy क under different smoothing variance a with clean state observations.
We additionally compute certified ratio n at radius r, representing the percentage of time steps that can be certified, formally denoted as 7/-- = 1/8 E/= [r.2r). More details are omitted to Appendix D.4
Evaluation Results of CROP-LOACT. We present the certification comparison in Figure I and the benign performance under different smoothing variances in Figure 2. we omit details of certified ratio to Appendix E.1
On Freeway, we evaluate with a large range of smoothing parameter a up to 1.0, since Freeway can tolerate large noise as shown in Figure 2 Results under even larger are deferred to Aolpppddix E.2 showing that the certified robustness can be further improved for the empirically robust methods. From Figure I] we see that RadialRL consistently achieves the highest certified radius across all a 's. This is because RadialRL explicitly optimizes over the worst-case perturbations. StdTrain, GaussAug, and Adv Train are not as robust, and increasing a will not make a difference. In Pong, SA-MDP (CVX) is the most certifiably robust, which may be due to the hardness of optimizing the worst-case pertur- bation in Pong. More interesting, all methods present similar periodic patterns for the certified radius on different states, which would inspire further robust training methods to take the "confident state" (e.g., when the ball is flying towards the paddle) into account. We illustrate the frames with varying certified radius in [pppnddxx E.3] Overall, the certified robustness of these methods largely matches empirical observations (Behzadan & Munir 2017b Oikarinen al. 2020 Zhang al. 2020).
6.2 EVALUATION OF ROBUSTNESS CERTIFICATION FOR CUMULATIVE REWARD
Here we will discuss the evaluation for the robustness certification regarding cumulative reward in Section 5 We show the evaluation results for both CROP-GRE and CROP-LORE.
Evaluation Setup and Metrics. We evaluate the a-randomized policy n' derived in Definition 4 for CROP-GRE and the locally smoothed policy म derived in (2) for CROP-LORF.. We compute the expectation bound Jg. percentile bound J/. and absolute lower bound J following Theorem The- orem 3 and Section 1. To validate the tightness of the bounds, we additionally pertorm empirical attacks. More rationales see see [Appendix D.3 The detailed parameters are omitted to Apppendix D.4
We present the certification of reward in |Figure 3]and mainly focus on analyzing percentile bound. We present the bound w.r.t. different attack magnitude e under different smoothing parameter a. For each a, there exists an upper bound of & that can be certified, which is positively correlated with a. Details see sceeAdpedii B.2 We observe similar conclusion as in the per-state action certification that RadialRL is most certifiably robust for Freeway, while SA-MDP (GD),PGD) are most robust for Pong although the highest robustness is achieved at different σ.
Evaluation of CROP-GRE.
Evaluation of CROP-LORE. In IngFigure 3] note that in Freeway, RadialRL is the most robust, followed by SA-MDP (CVX), then SA-MDP (PGD), AdvTrain, and GaussAug. As for Pong, SA- MDP (CVX) outperforms RadialRL and SA-MDP (PGD), Remaining methods are not clearly ranked.
6.3
DISCUSSION ON EVALUATION RESULTS
Impact Smoothing Parameter a. We draw similar conclusions regarding the impact of smooth- ing variance from the results given by CROP-LOACT and CROP-GRE, In Freeway, as increases, the robustness of StdTrain, GaussAug, and AdvTrain barely increases, while that of SA-MDP (PGD), SA-MDP (CVX), and RadialRL steadily increases. In Pong, a in the range 0.01-0.03 shall be suitable for almost all methods. More explanations from the perspective of benign performance and certified results will be provided in Appendix E.4 For CROP-LORE, there few different con- clusions. On Freeway, it is clear that under larger attack magnitude e, larger smoothing parameter o always secures higher lower bound J. In Pong, CROP-LORE can only achieve non-zero certification with small a under a small range of attack magnitude, implying the difficulty of establishing non- trivial certification for these methods on Pong. We defer details on the selection of to Appendix E.4
8

---

Published as a conference paper at ICLR 2022
0,005
0.05
0.5
0.75
1.0
(Chotal) JE
-12
03
16-2
02
16-1
(Ginba) Jpp
1.00
55
1.0
0.00 0:25 0.50
0.75 3,00
0.0
0.5
2.8
16-4
18-1
(Luoca)
0.000
0.005
0,010
0.05
0.05 0.10
0.0
0.2
0.4
0.6
0.8
1.0
0.5
0.5
vllnck
sttnck
stack
Miack
atback
attack
(a) Freeway
0.001
0.005
0.01
0.03
0.05
0.1
-118
-12
30
16-4
14
1r-3
Le-3
20
10
(Giobal) dp
0.5
17
3.5
0.0
0.5
1.2
3.8
0.0
05
1.0
15
(Loca)
3.000
0.003
3.000
3,005
8.000
0.005
0.515
5.00
9.00
0.02
0.23
0.00
6.22
0.54
0.08
0.00
0.05
0.38
usack
uttak
attack
amack c
ottack c
Juack
(b) Pong
Figure 3: Robustness certification for cumulative reward, including expectation bound Js, percentile bound 1/ (p = 50%), and absolute lower bound J. Each column corresponds to one smoothing variance. Solid lines represent the certified reward bounds, and dashed lines show the empirical performance under PGD.
Tightness of the certification JEy Jns and J. We compare the empirical cumulative rewards achieved under PGD) attacks with certified lower bounds. First, the empirical results are consis- tently lower bounded by our certifications, validating the correctness of our bounds. Regarding the tightness, the improved Jp is much tighter than the loose Jg. supported by discussions in Section 5.1 The tightness of J can reflected by the zero gap between the certification and the empirical result under wide range of attack magnitude e. Furthermore, the certification for SA-MDP (CVX,PGD) are quite tight for Freeway under large attack magnitudes, and RadialRI. demonstrates on Freeway. Additionally, different methods may achieve the same empirical results under attack, yet their certifications differ tremendously, indicating the importance of the robustness certification.
superiority
Game Properties. The certified robustness of any method on Freeway is much higher than that on Pong, indicating that Freeway is more stable game than Pong, also shown in Mnih et al.) (2015).
7 RELATED WORK
We briefly review several RL methods that demonstrate empirical robustness, Kos & Song (017)) and Behzadan Munir (2017b) show that adversarial training can increase the agent's 's resilience. SA-
DQN (Zhang et al.) 2020) leverages regularization to encourage the top-1 action to stay unchanged under perturbation. Radial-RL (Oikarinen al. 2020) minimizes an adversarial loss function that incorporates the upper bound of the perturbed loss. CARRL (Everett et al., 2021) computes the lower bounds of Q values under perturbation for action selection, but is only suitable for low-dimensional environments. Most of these works only provide empirical robustness, with Zhang al. (2020) and Fischer et al. (2019) additionally provide robustness certificates at state level. To the best of our knowledge, this is the first work providing robustness certification for the cumulative reward of RL methods. Broader discussions and comparisons of related work are in Appendix Fj
Conclusions. To provide the robustness certification for RL methods, propose general frame- work CROP, aiming to provide certification based on two criteria. Our evaluations show that certain empirically robust RL methods certifiably robust for specific RL environments.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
This work is partially supported by the NSF grant No.1910100, NSF CNS 20-46726 CAR, Alfred P. Sloan Fellowship, and Amazon Research Award.
this paper, we prove the first framework for certifying the robustness of RL algorithms against evasion attacks. We aim certify and therefore potentially improve the trustworthiness of machine learning models, and we do not expect any ethics issues raised by our work.
Ethics Statement.
Reproducibility Statement. All theorem statements are substantiated with rigorous proofs in our Appendix. We have upload the source code as the supplementary material for reproducibility purpose.
REFERENCES
Promoting the use of trustworthy artificial intelligence in the federal goverment. http:://www.feeeeerrreeeeeeeeerp
the htgp:///ww.....ttttttttttttttttr federal--oveznment Accessed: 2021-05-20.
Ilge Akkaya, Marcin Andrychowicz, Maciek Chociej, Mateusz Litwin, Bob McGrew, Arthur Petron, Alex Paino, Matthias Plappert, Glenn Powell, Raphael Ribas, et Solving rubik's cube with robot hand. arXiv preprint arXiv: /910.07/ 13, 2019.
Saud Almahdi and Steve Y Yang. An adaptive portfolio trading system: A risk-return portfolio optimization using recurrent reinforcement learning with expected maximum drawdown. Expert Systems with Applications. 87:267-279 2017.
Vahid Behzadan and Arslan Munir. Vulnerability of deep reinforcement learning to policy induction attacks. In International Conference on Machine Learning and Data Mining in Pattern Recognition, pp. 262-275. Springer, 2017a.
Vahid Behzadan and Arslan Munir. Whatever does kill deep reinforcement learning, makes stronger. arXiv preprint arXiv:1712.09344 2017b.
Vahid Behzadan and Arslan Munir. Mitigation of policy manipulation attacks deep nenttworks with parameter-space noise. International Conference on Computer Safety, Reliability, and Security, pp. 406 417. Springer, 2018.
M. G. Bellemare, Y. Naddaf, J. Veness, and M. Bowling. The arcade learning environment: An evaluation platform for general agents. Journal of Artificial Intelligence Research, 47:253-279, jun 2013.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojeiech Zaremba. Openai gym. arXiv preprint arXiv:1606.015500 2016.
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In 2017 ieee symposium on security and privacy (sp). pp. 39-57. IEEE, 2017.
Yair Carmon, Aditi Raghunathan, Ludwig Schmidt, Percy Liang, and John C Duchi. Unlabeled data improves adversarial robustness. arXiv preprint arXiv:1905.1311 2019.
Chih-Hong Cheng, Georg Nührenberg, and Harald Ruess. Maximum resilience of artificial neural networks. In International Symposium on Automated Technology for Verification and Analysis, pp. 251-268. Springer, 2017.
Richard Cheng, Gábor Orosz, Richard M Murray, and Joel W Burdick. End-to-end safe reinforcement learning through barrier functions for the AAAI Conference Artificial Intelligence, volume 33, pp. 3387-3395, 2019.
continuous control tasks. In Proceedings of
10

---

Published as a conference paper at ICLR 2022
Ping-yeh Chiang, Michael Curry, Ahmed Abdelkader, Aoumon Kumar, John Dickerson, and Tom Goldstein. Detection as regression: Certified object detection with median smooth- ing. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Ad- vances in Neural Information Processing Systems, volume 33, pp- 1275-1286. Curran As- sociates, Inc., 2020. URL http:///prrrrceennnnnerrr......o
Ppperr
Paul Christiano, Zain Shah, Igor Mordatch, Jonas Schneider, Trevor Blackwell, Joshua Tobin, Pieter Abbeel, and Wojciech Zaremba. Transfer from simulation to real world through learning deep inverse dynamics model. arXiv preprint arXiv:1610.03516 2016.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In International Conference on Machine Learning, pp. 1310-1320. PMLR, 2019.
Mare Peter Deisenroth, Gerhard Neumann, Jan Peters, al. A survey on policy search for robotics. Foundations and trends in Robotics, 2(1-2))388-403 2013.
Yue Deng, Feng Bao, Youyong Kong, Zhiquan Ren, and Qionghai Dai. Deep direct reinforcement learning for financial signal representation and trading. IEEE transactions on neural networks and learning systems, 28(3):653-664, 2016.
Priya Donti, Melrose Roderick, Mahyar Fazlyab, and Zico Kolter. Enforcing robust control guarantees within neural network policies. arXiv preprint arXiv:201 1.001000 2020.
Ruediger Ehlers. Formal verification of piece-wise linear feed-forward neural networks. In Interna- tional Symposium on Automated Technology for Verification and Analysis, pp. 269-286. Springer, 2017.
Michael Everett, Bjöm Lütjens, and Jonathan P How. Certifiable robustness to adversarial state uncertainty in deep reinforcement learning. IEEE Transactions on Neural Networks and Learning Systems, 2021.
Kevin Eykholt, Ivan Evtimov, Earlence Fernandes, Bo Li, Amir Rahmati, Chaowei Xiao, Atul Prakash, Tadayoshi Kohno, and Dawn Song. Robust physical-world attacks on deep learning visual classification. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 1625-1634, 2018.
Benjamin Eysenbach and Sergey Levine. Maximum entropy (provably) solves some robust problems. arXiv preprint arXiv:2103.062555 2021.
Jaime F Fisac, Anayo K Akametalu, Melanie N Zeilinger, Shahab Kaynama, Jeremy Gillula, and Claire Tomlin. A general safety framework for learning- based control in uncertain robotic systems. IEEE Transactions on Automatic Control, (4(7):2737-2755) 2018
Marc Fischer, Matthew Mirman, Steven Stalder, and Martin Vechev. Online robustness training for deep reinforcement learning. arXiv preprint arXiv: 111191111087,,.1111 2019.
Meire Fortunato, Mohammad Gheshlaghi Azar, Bilal Piot, Jacob Menick, Ian Oshand, Alex Graves, Vlad Mnih, Remi Munos, Demis Hassabis, Olivier Pietquin, et al. Noisy networks for exploration. arXiv preprint arXiv: I /766. 10295, 2017.
Timon Gehr, Matthew Mirman, Dana Drachsler-Cohen Petar Tsankov, Swarat Chaudhuri, and Martin Vechev. Ai2: Safety and robustness certification of neural networks with abstract interpretation. In 2018 IEEE Symposium on Security and Privacy (SP), pp. 3-18. IEEE, 2018.
Adam Gleave, Michael Dennis, Cody Wild, Neel Kant, Sergey Levine, and Stuart Russell. Adversarial policies: Attacking deep reinforcement learning. arXiv preprint arXiv: 19909/950..... 2019.
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint arXiv: 141.66:4 2014.
Leo A Goodman. On simultancous confidence intervals for multinomial proportions. Technometrics, 7(2):247-254, 1965.
11

---

Published as a conference paper at ICLR 2022
Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Uesato, Relja Arandjelovic, Timothy Mann, and Pushmeet Kohli. On the effectivenesss interval bound propagation for training verifiably robust models. arXiv preprint arXiv: 2018.
Wassily Hoeffding. Probability inequalities for sums of bounded random variables. In The Collected Works of Wassily Hoeffding, pp. 409-426. Springer, 1994.
Sandy Huang, Nicolas Papernot, lan Goodfellow, Yan Duan, and Pieter Abbeel. Adversarial attacks on neural network policies. arXiv preprint urXiv:1702.02223 2017.
Léonard Hussenot, Matthieu Geist, and Olivier Pietquin. Copyeat: Taking control of neural policies with constant attacks. arXiv preprint arXiv:1905.12282. 2019.
Garud N Iyengar. Robust dynamic programming. Mathematics of Operations Research, 30(2): 257-280, 2005.
Jongheon Jeong and Jinwoo Shin. Consistency regularization for certified robustness of smoothed classifiers. arXiv preprint 2rXiv:2006.04062, 2020.
Robin Jia and Percy Liang. Adversarial examples for evaluating reading comprehension systems. arXiv preprint arXiv: htt::/707.0m 7707007328 2017.
Guy Katz, Clark Barrett, David Dill, Kyle Julian, and Mykel J Kochenderfer. Reluplex: An efficient smt solver for verifying deep neural networks. In International Conference Computer Aided Verification, pp. 97-117. Springer, 2017.
Jens Kober, J Andrew Bagnell, and Jan Peters. Reinforcement learning in roboties: A survey, The International Journal of Robotics Research, 32(11):1238-1274, 2013.
Jernej Kos and Dawn Song. Delving into adversarial attacks on deep policies. arXiv preprint arXiv:1705.06455, 2017.
Aounon Kumar, Alexander Levine, Soheil Feizi, and Tom Goldstein. Certifying confidence via randomized smoothing. 2020.
Aounon Kumar, Alexander Levine, and Soheil Feizi. Policy smoothing for provably robust reinforce- ment learning. arXiv preprint arXiv:2106.1 /1420, 1420, 2021.
Alexey Kurakin, Ian Goodfellow, and Samy Bengio. Adversarial machine learning at scale. arXiv preprint 1iiv:6611.002366 2016.
Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples with differential privacy. In 2019 IEEE Symposium on Security and Privacy (SP), pp. 656-672. IEEE, 2019.
Guang-He Lee, Yang Yuan, Shiyu Chang, and Tommi S Jaakkola. Tight certificates of adversarial robustness for randomly smoothed classifiers. arXiv preprint arXiv:1906.0499 2019.
Edouard Leurent. An environment for autonomous driving decision decision-making making.
https://
github.com/ e http://eeeeeettiaaaeeeeeeee
2018.
Linyi Li, Xiangyu Qi, Tao Xie, and Bo Li. Sok: Certified robustness for deep neural networks. arXiv preprint arXiv:2009.04131, 2020.
Yen-Chen Lin, Zhang- Wei Hong. Yuan-Hong Liao, Meng-Li Shih, Ming- Yu Liu, and Min Sun. Tactics of adversarial attack on deep reinforcement learning agents. arXiv preprint 1703.06748. 2017.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint 06083, 2017.
Ajay Mandlekar, Yuke Zhu, Animesh Garg, Li Fei-Fei, and Silvio Savarese. Adversarially robust policy learning: Active construction of physically-plausbbl perturbations. In 2017 IÉEE/RSJ International Conference Intelligent Robots and Systems (IROS), pp. 3932-3939. IEEE, 2017.
12

---

Published as a conference paper at ICLR 2022
S Manikandan. Measures of central tendency: Median and mode. Journal of pharmacology and pharmacotherapeettes, 2(3):11,, 2011.
Donald Michie. "memo" functions and machine learning. Nature, 218(5136):19-2) 1968.
Matthew Mirman, Timon Gehr, and Martin Vechev. Differentiable abstract interpretation for provably robust neural networks. In International Conference on Machine Learning, pp. 3578-3586. PMLR, 2018.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint arXiv:13/2.5602, 2013.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning, nature, 518(7540):529-533 2015.
Scyed-Mohsen Moosavi-Dezfooli, Alhussein Fawzi, and Pascal Frossard. Deepfool: simple and accurate method to fool deep neural networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 2574 2582, 2016.
Arnab Nilim and Laurent EI Ghaoui. Robust control of markov decision processes with uncertain transition matrices. Operations Research, 53(5):780-798, 2005.
Tuomas Oikarinen, Tsui-Wei Wei Weng, and Luca Daniel. Robust deep reinforcement learning through adversarial loss. arXiv preprint arXiv:2008. 01976, 2020.
Anay Pattanaik, Zhenyi Tang, Shuijing Liu, Gautham Bommannan, and Girish Chowdhary. Robust deep reinforcement learning with adversarial attacks. In /7th International Conference on Au- tonomous Agents and Multiagent Systems, AAMAS 2018, pp. 2040-2042 International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS), 2018.
Athanasios S Polydoros and Lazaros Nalpantidis. Survey of model-based reinforcement learning: Applications on robotics. Journal of Intelligent & Robotic Systems, 86(2):153-173, 2017.
Aditi Raghunathan, Jacob Steinhardt, and Perey Liang. Certified defenses against adversarial examples. arXiv preprint arXiv: 2018.
Alessio Russo and Alexandre Proutiere. Optimal attacks on reinforcement learning policies. arXiv preprint arXiv: 13548, 2019.
Ahmad EL Sallab, Mohammed Abdou, Etienne Perot, and Senthil Yogamani. Deep reinforcement learning framework for autonomous driving. Electronic Imaging, 2017(19):70-6,, 2017.
Hadi Salman, Jerry Li, Ilya Razenshteyn, Pengchuan Zhang, Huan Zhang, Sebastien Bubeck, and Greg Yang. Provably robust deep learning via adversarially trained smoothed classi- fiers. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Bue, E. Fox, and R. Gar- nett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Asso- ciates, Inc., 2019, URL https::: Paper.ppdi
Pappeee.
Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver. Prioritized experience replay. arXiv preprint arXiv:
2015.
Shai Shalev-Shwartz, Shaked Shammah, and Amnon Shashua. Safe, multi-agent, reinforcement learning for autonomous driving. arXiv preprint arXiv: 1610.03295 2016.
Claude E Shannon. Communication theory of secrecy systems. The Bell system technical journal, 28 (4):656-715, 1949.
Qianli Shen, Yan Li, Haoming Jiang, Zhaoran Wang, and Tuo Zhao. Deep reinforcement learning with robust and smooth policy. In International Conference on Machine Learning, pp. 8707-8715 PMLR, 2020.
13

---

Published as a conference paper at ICLR 2022
Gagandeep Singh, Timon Gehr, Markus Püschel, and Martin Vechev. An abstract domain for certifying neural networks. Proceedings of the ACM on Programming Languages, 3(POPL):1-30, 2019.
Charles Stein et al. A bound for the error in the normal approximation to the distribution of a sum dependent random variables. Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability, Volume 2: Probability Theory. The Regents of the University of Califomia, 1972.
Yanchao Sun, Ruijie Zheng, Yongyuan Liang, and Furong Huang. Who the strongest enemy? towards optimal and efficient evasion attacks in deep rl. arXiv preprint (.kiv:2/06.050000 2021.
Robert Tarjan. Depth-first search and linear graph algorithms. SIAM journal on computing, 1(2): 146-160, 1972.
Vincent Tjeng, Kai Xiao, and Russ Tedrake. Evaluating robustness of neural networks with mixed integer programming. arXiv preprint arXiv:171 2017.
Josh Tobin, Rachel Fong, Alex Ray, Jonas Schneider, Wojeiech Zaremba, and Pieter Abbeel. Domain randomization for transferring deep neural networks from simulation to the real world. In 20/7 IEEE/RSJ international conference on intelligent robots and systems (IROS), pp. 23-30. IEEE, 2017.
Peter van Emde Boas. Preserving order in a forest in less than logarithmic time and linear space. Information processing letters, 6(3):80-82, 1977.
Hado Van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double q- learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2016.
Christopher JCH Watkins and Peter Dayan. Q-learning. Machine learning, 8(3-4):279-22)) 292, 1992.
Lily Weng, Huan Zhang, Hongge Chen, Zhao Song, Cho-Jui Hsieh, Luca Daniel, Duane Boning, and Inderjit Dhillon. Towards fast computation of certified robustness for relu networks. In International Conference on Machine Learning, pp. 5276-5288 PMLR, 2018.
Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In International Conference on Machine Learning, pp. 5286-5295. PMLR, 2018.
Kaidi Xu, Zhouxing Shi, Huan Zhang, Minlie Huang, K Chang, Bhavya Kailkhura, Xue Lin, and C Hsich. Automatic perturbation analysis on general computational graphs. Technical report, Lawrence Livermore National I. (LLN(L,,,),, Livermore, CA (United States), 2020.
Greg Yang, Tony Duan, J Edward Hu, Hadi Salman, Ilya Razenshteyn, and Jerry Li. Randomized smoothing of all shapes and sizes. In International Conference on Machine Learning, pp. 10693- 10705. PMLR, 2020.
Yunan Ye, Hengzhi Pei, Boxin Wang, Pin-Yo Yu Chen, Yada Zhu, Ju Xiao, and Bo Li. Reinforcement- learning based portfolio management with augmented asset movement prediction states. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 1 1112-1119, 2020.
Huan Zhang, -sui-Wei Weng, Pin- Yu Chen, Cho-Jui Hsieh, and Luca Daniel. Efficient neural network robustness certification with general activation functions. Advances in Neural Information Processing Systems, 31:4939-4948, 2018.
Huan Zhang, Hongge Chen, Chaowei Xiao, Bo Li, Mingyan Liu, Duane Boning, and Cho-Jui Hsieh. Robust deep reinforcement learning against adversarial perturbations state obser- vations. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Ad- vances in Neural Information Processing Systems, volume 33, pp. 21037. Curran As- sociates, Inc., 2020. URL wttp:/ttee//pppeeeiggeeeeoooooos E0eb6568eal 11w.11442222990030033343300 -ap.eaa
Huan Zhang, Hongge Chen, Duane S Boning, and Cho-Jui Hsich. Robust reinforcement learning on state observations with learned optimal adversary. In International Conference on Learning Representations, 2021.
14

---

Published as a conference paper at ICLR 2022
The appendices organized as follows:
In Appendix A
we present the detailed proofs for lemmas and theorems in Section and Section 5| laying down the basis for the design of our certification strategies.
present some additional details of our three certification strategies: CROP-LOACT to certify the per-state action, and CROP-GRE and CROP-LoRE to certify the cumulative reward. We include the detailed algorithm description and the complete pseudocode for each algorithm. Our implementation is publicly available at attps://githb..co /AI AI- secure/CROP
In Appendix B
In Apppendix C we provide discussion the advantages and limitations of different certification methods, and also present several promising direct extensions for future work. We also provide more detailed analysis that help with the understanding of our algorithms.
In An/Appediix D. we show the experimental details, including the game environment, details descriptions of the RL methods we evaluate, rationales for our evaluation settings and experimental designs, detailed evaluation setup for each of our certification algorithms in the main paper, as well as the setup for new game CartPole.
In/Appendix we present additional evaluation results and discussions for the environments and algorithms evaluated in the main paper, from the perspectives of different metrics and different ranges parameters. We also provide the running time statistics and specifically illustrate the periodic patterns in the Pong game. In addition, present the evaluation results on standard control environment CartPole and another autonomous driving environment Highway.
In In/Apeedixx Fl we provide a broader discussion of the related works, spanning the evasion attacks in RL, Robust RL, as well robustness certification for RL.
A PROOFS
A.1 PROOF OF LEMMA
We recall Lemma 1
Lemma (Lipschitz continuity of the smoothed value function), Given the action-value function Q S x A + [Vmins V.uax), the smoothed function Q with smoothing parameter a is L-Lipschitz continuous with L V.na Vuin /2/a w.r.l. the state input.
Proof. To prove Lemma I (2019) in their Appendix A.
we leverage the technique in the proof for Lemma 1 of Salman al.
For each action a E A, our smoothed value function
1 Q' (s, a) A~N(U.02IN) (s (2T) Jrn Q" (x() (- (-200 l|s - e1p)) de.
1
Taking the gradient w.r.t. 8, we obtain
(t,, -t)exp (- 2 1| - e112)
(xQ"( (2a)
For any unit direction u, have
u V.Q"((,a))
Viax
Vuun o²
u(s 1) exp
20 ||s - =112) dl
N
Vmaxx Vmn
1
//s - 10-(essp exp
20 1ss - 1p)
1
o²
(2x)
2"
1
|3; 112 di
1/30
20
22
Vmax
Vnnin
Thus, TTh is T--Lipschitz continuous with I Vene Vinin / 2//= W.r.t. the state input.
15

---

Published as a conference paper at ICLR 2022
A.2 PROOF OF THEOREM
We recall Theorem
Theorem 1. Let Q 88 A [Vmin: mmax] be trained value network, Q" be the smoothed func- tion with (2). At time step with state 8t, we can compute the lower bound T of maximum perturbation magnitude E(s)) (i.e.. rt E(s,), defined in Definition 1/ for locally smoothed policy ā.
T2
④
(st,)a)
Viaax - Vinin
Vinn
----- )
(0--101(00 (QT(ss, (12)-iinnn Vinn
Viaax
Vinin
(6)
where $- is the inverse CDF function, an the action with the highest Q value at state Su and 02 is the runner-up action. We name the lower bound Tt certified radius for the state 8t.
We first present a lemma that can help in the proof of Theorem
Lemma 3. Let & be the CDF of standard normal distribution, the mapping (a(s)) (a,a) Vmnm h-1
is 1-Lipschitz continuous.
Vinax Viii
The lemma can be proved following the same technique the proof for Lemma in Appendix A. The detailed proof can be referred in the proof for Lemma of [Salman al.] (0199) in their Appendix A. We next show how to leverage Lemma to prove Theorem
Proof for Theorem 1 we have
Let the perturbation be 6,, based on the Lipschitz continuity of the mapping n.
May (8t) Aa, (8t + 52) < |6e||2,
Mag (8t + 5.) Tlag (#t) S |6
(8)
Suppose that under perturbation & the action selection would be misled in the sense that the smoothed value for the original action a is lower than that of another action d2, i.e., Q (s, 6, a1) I Qa (St + de, 02). Then, based on the monotonicity of 77, we have
Ma. (st + 6) S Ma2 (St + 6).
(9)
Summing up
8 and
9 obtain
||5.||2
2 (May (st) Mas (8+))
-1 ' (Se,
(QT((), (1),
Vmin
Φ- (Q a2) Vuuin
2
Vmax - Viain
Vmnax
Vinin
which is a lower bound of the maximum perturbation magnitude E(st) that can be tolerated at state St- Hence, when takes the value of the computed lower bound, it satisfies the condition that
T: S ((s)..
A.3 PROOF OF LEMMA 2
We recall Lemma 2
Lemma (Lipschitz continuity of smoothed perturbed return function). Let be the perturbed return
function function defined in (4), the smoothed perturbed return function Fz is (Jmax (min) Jmin) 22/=-
Lipschitz continuous, where Fr (0 (-166)) A~
E
Fr ( H-1 (5, D.)).
Proof. The proof can be done in similar fashion as the proof for Lemma in Appendix A.I Compared with the smoothed value network where the expectation is taken over the sampled states, here, similarly, the smoothed perturbed return function derived by taking the expectation over sampled o-randomized trajectories. The difference is that the output range the Q-network is [Vmins Vmax], while the output range of the perturbed return function is [Jmin, Jmax] Thus, the smoothed perturbed return function F is (Jmas Jmin) / Lipschiz continuous.
16

---

Published as a conference paper at ICLR 2022
A.4 PROOF OF THEOREM 2
We recall the definition of F7 as well as Theorem
F ( ( 5e = E
(-N(0.021MxN) [
Pa
1 (6e + Gc)
Theorem (Expectation bound). Let JE Fr (0) Le LevH, where L (Jmax-Jmin) 12/m. Then JE s E (x)))
Proof. We note the following equality
F 5c)
E Fs (0/= Go)
F.r (el=
5c
E J (T)
(10)
where (a) comes from the definition of the smoothed perturbed return function Fa, (b) is due to the definition of the o-randomized policy n', and (c) arises from the definition of the perturbed cumulative reward J Thus, the expected perturbed cumulative reward IE [J (r') is equivalent
to the smoothed perturbed return function Fs (0/"o 6t). Furthermore, since the distance between the all-zero @ 0 and the adversarial perturbations @/-0'd 6g is bounded by ev v leveraging the Lipschitz smoothness of in Lemma 2) we obtain the lower bound of the expected perturbed cumulative reward IE [ (**) as P (0)-100 - LevH.
A.5
PROOF OF THIBOREM 3
We recall the definition of Fy as well as Theorem 3
F
@ 8e sup, { R Px (e (ō. + G)) < sp]
(11)
Theorem (Percentile bound). Let Jp Fe' (0 where p' 1b (8-1(p) (p) svH/o). Then
Jp I the p-th percentile of Je Jm(').
Proof. To prove Theorem 3 we leverage the technique in the proof for Lemma of Chiang al. (2020) in their Appendix B.
For brevity, we abbreviate 5 == @ = H-11, 6, and redefine the plus operator such that 5 + := $ H-1
(6,
(t). Then, similar to Lemma 3
we have the conclusion that
(P F.. F
8
is 1-Lipschitz continuous, where < ~ 02 (2
Thus, under the perturbations 6, E 1 for f = 0... H 1, we have
F. (0) Φ- (F
Φ (P (s(()) < ,. (F/((0)) ||01|2
< < (P s Fs' (oi) + EVH
(Since ||0||2 S ev H)
- + SVTT
(By definition of F
(p)
(By definition of p'
Since + monotonically increase, this implies that P Fx () FF'(0)) p. According the definition of F2 in (1b, we see that FY' (0) < FY (5), i.e., Jp S the p-th percentile of Je(T'). Hence, the theorem is proved.
A.6 PROOF OF THIBOREM 4
We recall Theorem 4
17

---

Published as a conference paper at ICLR 2022
Theorem 4. Let (VE:-..,Ty (r(....,((A-1)) be a sequence of certified radii for state 8t at time step I, where r denotes the radius such that if= rÝ. the possible action time step will belong to the actions corresponding to top k action values of Q at state st. The definition of re in Theorem equivalent to r, here. The radii can be computed similarly as follows:
(0-100((111 (Vmax-
(21(
Vinin
Q" [81, Vinin
)) 1
④ (
-
Vinin
VIaax
Vmin
where 01 is the action of the highest Q value at state 8t and ax+1 1 the (A: + 1)-th best action. additionally define (5)) O, which is also compatible with the definition above.
Proof Replacing a2 with a++1 in the proof for Theorem in Appendix A.2 directyy leads to Theo- rem 4
B ADDITIONAL DETAILS OF CERTIFICATION STRATEGIES
In this section, we cover the concrete details regarding the implementation of our three certification strategies, as complement to the high-level ideas introduced back in Section SandtSnction
B.1 DETAILED ALGORITHM OF CROP-LOACT
Algorithm 1: CROP-LOACT: Local smoothing for certifying per-state action
Input: state 8, trained value network Q" with range [Viin, Va parameters for smoothing: sampling times smoothing variance a², one-sided confidence parameter a
D. Step 2: certification
A (Vnax Vmnn)) V 2m
P confidence interval
Output: smoothed value network Q", selected action certification indicator cert, certified radius r constant
if is 2 Q (s, + 2A then
certification success
cert + Irue
b Step 1: Generate noise samples ~ (N,0021 02 for S i m for each action E A do
smoothing
{ 1/ A-min
V Vmax min
Φ 1 - (s.00) (s.02)+4 Vmun
Vinax Vinia
clse
elipping avaraging
cortification failure
(s. + D clipp( clip(Q" a, min Vinn; max Vmax)
cert +- False r f undefined
11
41, 02 <- best action and runner-up action given by 12 return Q", 01 cert, r -
We present the concrete algorithm of CROP-LOACT in Algorithm 1 for the procedures introduced in Section 4.2 For each given state $t, we first perform Monte Carlo sampling (Cohen et al., 2019 Lecuyer et al. 2019) to achieve local smoothing. Based on the smoothed value function Q" we then compute the robustness certification for per-state action, i.e., the certified radius r; at the given state s,, following Theorem
Detailed Inference Procedure. During inference, invoke the model with m samples of Gaus- sian noise at each time step, and use the averaged Q value on these m noisy samples to obtain the greedy action selection and compute the certification. This procedure similar to PREDICT in Cohen et al. (2019), but since RI. involves multiple step decisions, we do not take the "abstain" decision as PREDICT in Cohen et al. (2019); instead, CROP-LOACT will take the greedy action all steps no matter whether the action can be certified or not.
Vmin, Vmax- Our estimate obtained via sampling the trajectories and calculating the Q values associated with the state-action pairs along these trajectories. Since we perform clipping using the obtained bounds, the certification is sound. The cost for estimating Vum and Vnax is essentially associated with the number of sampled trajectories, the number of steps in each trajectory, the number of sampled Gaussian noise m per step, and the cost of doing forward pass of the network; thus, the estimation can be done with low cost. Furthermore,
Estimation of the Algorithm Parameters
18

---

Published as a conference paper at ICLR 2022
Algorithm 2: CROP-GRE: Global smoothing for certifying cumulative reward
Input:
initial state distribution do, trained value network Q", game cumulative reward range [Jmin, Jmax] number of steps in an episode H. perturbation magnitude at each state E, percentile p. parameters for smoothing: sampling times m, smoothing variance one-sided confidence parameter a Output: Expectation bound Jg. p-th percentile bound Jp
D. Step 2.1: certifying expectation
bound
F + EE Jr
b amoothed actual reward
A coat + (Rmax Rmin) 2m
In(1/w)
b confidance interval
Alip t Rmax Rmin
2
EEVH
bound given by Lipschitz continuity
b Step 1: smoothing
Jg F Acont Alip
for 1 do
12
inigialization Generate macro-state noise & ~ ((00021) for
80 ~ do, J + 0
b Step 2.2: certifying percentile bound
0 0 << fo 0 II de argmax, ((s: + a))
k Cow.
J, < k-th smallest value in {
Execute action dr and observe reward re; and next state 8141
return Ja. J2
zake step
Jf J ret
accumulate the
reword
we can balance the trade-off between the accuracy and efficiency of the estimation, and for any configuration of Vinin and Vinax the certification will invariably be sound (reason above).
B.2 DETAILED ALGORITIM OF CROP-GRE
We present the concrete algorithm of CROP-GRE in Algorithm 2 for the procedures introduced in /Section 5.1 Similarly to CROP-LOACT, the algorithm also consists of two parts: performing smoothing and computing certification, where we compute both the expectation bound JÆ and the percentile bound Jp-
Step Global smoothing. We adopt Monte Carlo sampling (Cohen et al., 2019 Lecuyer et al.
2019) to estimate the smoothed perturbed return function by sampling multiple o-randomized trajectories via drawing noise sequences. For each noise sequence Ç (0, _ IxNN,, we apply noise Ç. to the input state s, sequentially, and obtain the sum of the reward J EE H-1 re, as the return for this o-randomized trajectory. We then aggregate the smoothed perturbed return values (J (J
via mean smoothing and percentile smoothing. Ji=1
Step 2: Certification for perturbed cumulative reward. First, we compute the expectation bound JE using Theorem 2 Since the smoothed perturbed return function F is obtained based sampled noise sequences, we use Hoeffding's ' inequality (Hoeffding 1994) to compute the lower bound of the random variable F (=#-11) 0) with a confidence level a. We then calculate the lower bound of F ( under all possible bo-bounded perturbations 6, B leveraging the smoothness of F.
We then compute the percentile bound Jn using Theorem We let J be sorted increasingly, and perform normal approximations (Stein et al. 1972) to compute the largest empirical order statistic J such that P Jp J 2 a. The empirical order statistic J then used as the proxy of Jp under a confidence level. We next provide detailed explanations for which aims to compute the order k using binomial formula plus normal approximation.
Estimation of Fx (defined in Lemma 2). bound of EA [J)(T')), intermediate step is to estimate F, (as shown in line of Algorithm 2).
For computing the expectation bound (i.e., the lower
We emphasize that the accuracy of the estimation does not influence the soundness of the lower bound calculation. The reason is given below. The number of sampled randomized trajectories controls
19

---

Published as a conference paper at ICLR 2022
the trade-off between the estimation efficiency and accuracy, well as the tightnss of the derived lower bound. Concretely, a small m would provide high efficiency, low estimation accuracy, and loose lower bound: but the lower bound is always sound, since algorithm explicitly accounts for the inaccuracy associated with m via leveraging the Hoeffding's inequality in line in Algorithm 2
Details of COMPUTEORDERSTArE
We consider the sorted sequence JfP S J .... S J Our goal is to find the largest &o such that 1 a. We evaluate the probability explicitly as follows:
We additionally set J = -0 and J
P
J
J
Je J. S
<
m =
(1
-p)m-
i=
Thus, the condition
Jp 2
2 is equivalent to J
mr (p)) - a
(12)
Given large enough m, the LHS of 12) can be approximated via a normal distribution with mean equal mp' and variance equal mp (1 p'). Concretely, we perform binary search find the largest & that satisfies the constraint.
We finally explain the upper bound of ε that can be certified for each given smoothing variance. In practical implementation, for a given sampling number m and confidence level parameter a, if is too small, then the condition (12 may not be satisfied even for i This implies that the existence of an upper bound of E that can be certified for each smoothing parameter recalling that p' (p) <vH/r).
Detailed Inference and Certification Procedures. We next provide detailed descriptions of the inference and certification procedures, respectively.
Inference procedure. We deploy the o-randomized policy n' as defined in Definition 4 Section 5.1 That is, for each observed state, we sample one time of Gaussian noise A, to add 8t, and take action according to this single randomized observation a, (T a + A,). Thus, in deployment time, the A-randomized policy x' exccutes on one rollout-ai at each step it takes one observation and chooses one action (following the procedure described above).
Certification procedure. We sample m randomized trajectories in CROP-GRE instead of sampling m noisy states per time step in CROP- For each sampled randomized trajectory, each time step in the trajectory, we invoke the model with sample Gaussian noise (as shown in (4)) Given the randomized trajectories and the cumulative reward for each of them, compute the certification using Theorem 2 and Theorem 3
The Algorithm Parameters Juin: Jmaxx We use the default values of Juins Jmax in the game specifications rather than estimate them, which are independent with the trained models. Thus there no computational cost at all for obtaining the two parameters. As mentioned under Theorem in Section 5. using these default values may induce a loose bound in practice, so we further propose the percentile smoothing that aims to eliminate the dependency of our certification on Jmin and Jmaxx thus achieving tighter bound.
B.3 DETAILED ALGORITHMS OF CROP-LORE
In the following, we will explain the trajectory exploration and expansion, the growth of perturbation magnitude, and optimization tricky in details.
Trajectory Exploration and Expansion. CROP-LORE organizes all possible trajectories in the form of search tree and progressively grows it. Each node of the tree represents state, and the depth of the node is equal to the time step of the corresponding state in the trajectory. The root node (at depth 0) represents the initial state 5g. For each node, leveraging Theorem 4] we compute non-decreasing sequence (r* (s)) 141-1 corresponding to required perturbation radii for и to choose each alternative action (the subscript is omitted for brevity). Suppose the current satisfies (s) I E < pi+1 We grow (i + 1) branches from current state corresponding the original action and alternative actions since e 2 r (s) for < j < i. For nodes on the newly expanded branch, we repeat the same
( (s).
20

---

Published as a conference paper at ICLR 2022
Algorithm 3: CROP-LORE: Adaptive search for certifying cumulative reward
Input: Eniveonment (5, A, R, do), trained value network 24
Q2 with [Vuin V Vinaai parameters for randomizeed smoothing: sampling times m. smoothing variance o², one-sided confidence parameter
Procedure ExF AND Ciin Jeur)
26
if Jeur 2 Jglabal then
L return 0
pruning
Output: map M that maps attack magnitude to the correpoondin certified lower bound of reward /
a_ GrrAcTicnn(s, Clims Sour)
i a = then
initialize global variables
Iglobal min[Jglobal Seur) return 0
P_que +
init ialive an emply priority queue
a, redius seward JI, cested by increasing
containing tuples lssate
for a E a a_fist do [(s,a) EXPAND(e' Elim R(s,
b. initialise global mininum swward A = (Viax Vinta) V 2m In
Jglobal +-
confidence bound
36 Fg do
initialize initiall state
Function CETACTIONS (s, Jour):
Exe AND (#o; Flim 0, Jeur =0) trafectery
P. expand initial
Generate noise samples 4; ~ NO( R for forisss i for each action A do
while True y_gqee then break
(=) 1 1 clip(Q"
0,, min Vmin;
Vinx)
10
argmax, (s,
pop out the first elenent (a.a, p_oue.pop()
11
Rist <-
12
each action E A do
D. examing the next first clament (., p_que.top() derive critical
13
(f L then continue
42
14
r, r
15
it (x, (s, 2A then
obtain pair of napping
r f ( (=.a")_A' Vmin
M[c] Jelobal
Vimux Vini
(e.))
expand the tree from the new mode EXPAND (T e', R(s.o))
Vinax Ventn
45
18
19
if S flim then
Lake possible actions
20
list +- a_sist U (a)
21
ebse
store impowiible actions quece ater expansion
22
p_que.pushi((s, o, reur))
23
return a_list
procedure to expand the tree with depth-first search (Tarjan 1972) until the terminal state of the game is reached or the node depth reaches H. As we expand, we keep the record of cumulative reward for each trajectory and update the lower bound J when reaching the end of the trajectory if necessary.
Perturbation Magnitude Growth. When all trajectories for perturbation magnitude e are explored, need increase seek for certification under larger perturbations. Luckily, since the action space is discrete, we do not need to examine every E R (which is infeasible) but only need to examine the next E where the chosen action some step may change. We leverage priority queue (van Emde Boas 1977) to effectively find out such next "critical" e. Concretely, along the trajectory exploration, at each tree node, we search for the possible actions and store actions corresponding to (x)(())) [AI- into the priority queue, since these actions are exactly those need to be explored when E grows. After trajectories for are fully explored, we pop the head element from the priority queue as the next node to expand and the next perturbation magnitude to grow. We repeat this process until the priority queue becomes empty or the perturbation magnitude & reaches the predefined threshold.
Additional Optimization. We adopt some additional optimization tricks to reduce the complexity of the algorithm. First, for environments with negative reward, we perform pruning to limit the tree size-ii if the cumulative reward leading to the current node already reaches the recorded lower bound, we can perform pruning, since the tree that follows will not serve to update the lower bound. This largely reduces the potential search space. We additionally adopt the memorization (Michie) 1968) technique which is commonly applied in search algorithms.
21

---

Published as a conference paper at ICLR 2022
We point out few more potential improvements. First, with more specific knowledge of the game mechanisms, the search algorithm can be further optimized. Take the Pong game as an example, given the horizontal speed of the ball, two paddles, thus reducing the computation. Second, empirical attacks may he efficiently incorporated into the algorithm framework provide upper bounds that help with pruning.
compress the time steps where the ball is flying between the
Time Complexity. The time complexity of CROP-LORE is [HH|Sxxploed x (log [Septored [A(T)), where [Sepllredd is the number of explored states throughout the search procedure, which is no larger than cardinality of state set, H is the horizon length, |A] is the cardinality of action set, and T the time complexity of performing local smoothing. The main bottleneck of the algorithm the large number of possible states, which is in the worst case exponential to state dimension. However, to provide a sound worst-case certification agnostic to game properties, exploring all possible states may be inevitable.
Detailed Inference and Certification Procedures and Important Modules in Algorithm 3 We next provide detailed descriptions of the inference and certification procedures, respectively, along with other important modules.
Inference procedure. In CROP-LORE, we deploy the locally smoothed policy स as defined in (2) in Seection 4.1] Concretely, for each observed state &t, we sample batch of Gaussian noise to add to St, and take action according to the computed mean Q value on the batch of randomized observations. (Actually, the inference procedure per step is exactly the same as in CROP-LOACT described in Appendix B.I.)
proffcccttonrrceduuuue procedure. We obtain the certification via Theorem 4aand the adaptive search algorithm, which outputs collection of pairs Je. ) sorted in ascending order of 6;, where |C| is the length of the collection. The interpretation for this collection of pairs is provided below. For all e', let i be the largest integer such that e; S E' < Ei+1, then long as the perturbation magnitude E S E', the cumulative reward (+) 2 Je.- This is supported by the fact that all certified radii associated with all nodes in the entire expanded tree compose a discrete set of finite cardinality; and the perturbation value between two adjacent certified radii in the returned collection will not lead to a different tree from the tree corresponding to the largest smaller perturbation magnitude. This actually is also the inspiration for the certification design.
Certification
Important modules. The function GE TACT ION computes the possible actions at a given state under the limit s, while the procedure EXP AND accomplishes the task of expanding upon given node/state. The main part of the algorithm involves a loop that repeatedly selects the next element from the priority queue, i.e., a node associated with an E value, to expand upon.
Additional Clarifications. We clarify that the algorithm only requires access to the environment such that it can obtain the reward and next state via interacting with the environment & (i.e., taking action a at state s and obtain next action s' and reward r), but does not require access to an oracle transition function T. We further emphasize that access to the environment that supports back-tracking is already sufficient for conducting our adaptive search algorithm.
C DISCUSSION ON THE CERTIFICATION METHODS
We discuss the advantages and limitations of our certification methods, as well as possible direct extensions. hoping to pave the way for future research along similar directions. We also provide more detailed analysis that help with the understanding of our algorithms.
The algorithm provides state-wise robustness certification in terms of the stabil- ity/consistency of the statetate action. It treats each time step independently, smooths the given state at the given time step, and provides the corresponding certification. Thus, one potential extension is to expand the time window from one time step to a consecutive sequence of several time steps, and provide certification for the sequences of actions for the given window of states.
CROP-LOACT.
CROP-GRE. Asexplained in Section the expectation bound JE is too loose to have any practical usage In comparison, percentile bound Jpp is much tighter and practical. However, one limitation of Jp is that there exists an upper bound of the attack magnitude that can be certified for each
22

---

Published as a conference paper at ICLR 2022
explained in Appendix B.2 For attack magnitudes that exceed the upper bound, we can obtain no useful information via this certification (though the upper bound is usually sufficiently large).
One limitation of CROP-GRE. Lemma 2 requires knowing the noise added to each step beforehand
so to generate randomized trajectories given the known noise sequence {d: ) Thus, it cannot be applied against an adaptive attacker. We clarify that our CROP-LOACT and CROP-LORE does not have such limitation.
The algorithm provides the absolute lower bound J of the cumulative reward for any finite- hotte-horizon trajectory with given initial state. The advantage of the algorithm is that J is an absolute lower bound that bounds the worst-case situation (apart from the exceptions due to the probabilistic confidence a),, rather than the statistical lower bounds JE and Jp that characterize the statistical properties of the random variable J..
CROP-LORE.
One potential pitfall in understanding J. What CROP-LORE certifies is the lower bound for the trajectory with a given initial state so do. rather than all possible states in do. This is because our search starts from a root node of the tree, which is set to the fixed given state So-
Confidence of CROP-LORE that we consider the independent multiple-test. Concretely, due to the independence of decision making errors, the confidence is (1 a)", where is the maximum number of possible attacked states explored by CROP-LORE, Formally,
Regarding the confidence of our probabilistic certification, we clarify
Pr[CROP-LORE certification holds]
II
Pr[not make error on s|not make error on Spre]
all a explored CROP-LORE
II
(1-
II
all attackable
all unatiackable
(1-a)
(13)
In the above equation, we can see that (i) leverages the independence which in turn gives bound of form (1 - a)x. This is because in each step, the event of "certification does not hold" is independent since sample Gaussian noise independently. Leveraging such independence, obtain a confidence lower bound of (1 a) From (ii), we see that the confidence is only related to the number of possible attacked states N. This is because for unattackable states, the certification deterministically holds since there is no attack at current step. Therefore, we only need to count the confidence intervals from all possibly attackable steps instead of all states explored. We remark that in practice, the attacker usually has the ability to perturb only limited number of steps, i.e., N is typically small. Therefore, the confidence is non-trivial
Main limitation of CROP-LORE. The main limitation is the high time complexity of the algorithm (details see see Appendix B.3). The algorithm has exponential time complexity in worst case despite the existence of several optimizations. Therefore, it is not suitable for environments with a large action set, or when the horizon length is set too long.
Extension to Polecy-based Methods. Though we specifically study the robustness certification in Q-learning in this paper, our two certification criteria and three certification strategies can be readily extended to policy-based methods. The intuition is that, instead of smoothing the value function in the Q-learning setting, we directly smooth the policy function in policy- based methods. With the smoothing module replaced and the theorems updated, other technical details in the algorithms for certifying the per-state action and the cumulative reward would then be similar.
D ADDITIONAL. EXPERIMENTAL DETAILS
D.1 DETAILS OF THE ATARI GAME ENVIRONMENT
We experiment with two Atari- environments in OpenAl Gym (Brockman et al. 2016) on top of the Arcade Learning Environment (Bellemare et al. 2013). The states in the environments are high dimensional color images (210 x 160 x 3) and the actions are discrete actions that control the agent to accomplish certain tasks. Concretely, we use the NoFramesk iip 1p-v4 version for our experiments,
23

---

Published as a conference paper at ICLR 2022
where the randomness that influences the environment dynamies can be fully controlled by setting the random seed of the environment at the beginning of an episode.
D.2 DETAILS OF THE RL METHODS
We introduce the details of the nine RL methods we evaluated. Specifically, for each method, we first discuss the algorithm, and then present the implementation details for it.
StdTrain (Mnih et al., 2 StdTrain (naturally trained DQN model) is an algorithm based on Q-learnin, in which DQN is used to reprent Q-value function and TD-loss is used to optimize DQN.
Our StdTrain model is implemented with Double DQN (Van Hasselt et al. 2016) and Prioritized
Experience Replay (Schaul al., 2015).
GaussAug (Behzadan Munir 2017b): The algorithm of Guu similar with AddTrain, in which appropriate Gaussian random noises added to states during training. As for implementation, our GaussAug model is based on the same architecture with the same set of basic training techniques of StdTrain, and adds Gaussian random noise with 0.005, which has the best testing performance under attacks compared with other o, to all the frames during training.
AdvTrain (Behzadan & Munir 201 Instead of using the original observation train Double DQN (Van Hasselt et al., 2016). AdvTTrain generates adversarial perturbations and applies the perturbations to part of or all of the frames when training. In our case, we add the perturbations generated by 5-step PGD attack to 50% of the frames to make balance between between stable training and effectiveness of adversarial training.
SA-MDP (PGD) and SA-MDP (CVX) (Zhang et al., 2020 Instead of utilizing adversarial noise to train models directly like AdvTrain, SA-MDP (PGD) and SA-MDP (CVX) regularize the loss function with the help of adversarial noise during training in order to train empirically robust RL agents. In our experiment settings, which the same as SA-MDP (PGD) and SA-MDP (CVX) (Zhang et al.. 2020), models consider adversarial noise with -nom e = 1/255 when solving the maximization for the regularizer and minimize the original TD-loss concurrently.
RadialRL (Oikarinen et al. 2020): With the similar idea of adding regularization during training of SA-MDP (PGD) and SA-MDP (CVX), RadiaIRI. compute the worst-case loss instead of regularizing of the bound of the difference of policy distribution under original states and adversarial states. In our case, the RadialRL model uses a linearly increasing perturbation magnitude e (from 0 to 1/255) to compute the adversarial loss.
CARRL (Everett et al. 2021): Unlike other methods which try to improve robustness of RL agents during training. CARRL enhances RL agents' robustness during testing time. It computes the lower bound of each action's ' Q value at each step and take the one with the highest lower bound conservatively. Given that the lower bound is derived via neural network verification methods (Gowal ct al. al. 2021 Thus, we only evaluate CARRL on CartPole and Highway, where we set the bound of the l norm of the perturbation be 0.1 and 0.05 respectively when computing the lower bound of Q value, which demonstrate the best empirical performance under noise and empirical attacks.
2018 Weng et al. 2018), CARRL can only be applied to low dimensional environments (Everett
NoisyNet (Fortunato al. 2017): Instead of the conventional exploration heuristics for DQN and Dueling agents which is e-greedy algorithms, NoisyNet adds parametric noise to DQN's weights, which is claimed to aid efficient exploration and yield higher scores than StdTrain. Concretely, our NoisyNet shares the same basic architecture with StdTrain, and samples the network weights during training and testing, where the weights are sampled from a Gaussian distribution with o 0.5.
GradDQN (Pattanakk et al. 2018); GradDQN is variation of AdvTrain, which utilizes conditional value risk (CVaR) as optimization criteria for robust control instead standard expected long term return. This method maximizes the expected return over worst percentile of returns, which can prevent the adversary from possible bad states. In our case, we generate the adversarial states with 10-step attack by calculating the direction of gradient and sampling in that direction from betal, 1 distribution in each step.
24

---

Published as a conference paper at ICLR 2022
For StdTrain, SA-MDP (PGD), SA-MDP (CVX), RadialRL, directly evaluate the trained models provided by the authors
D.3 RATIONALES FOR SETTINGS AND EXPERIMENTAL DESIGNS
Finite Horizon Setting. In this paper, we focus on finite horizon setting, mainly for the evaluation purpose- we would need to compute the (certified and empirical) cumulative rewards from finite rollouts. We clarify that our criteria, theorem, and algorithm are applicable to the infinite horizon case well.
The Role of Practical Attacks in Our Evaluation. The goal of this paper is to provide certification that comes with theoretical guarantees, and therefore following the standard certified robustness literatures (Cohen et al.] 2019 Li et al. 2020; Salman et al. 2019 Jeong & Shin 2020), there is no need to evaluate the empirical attacks, since the certification always holds long the attacks satisfy certain conditions regardless of the actual attack algorithms. The attacks we evaluated in our paper were only for the demonstration purpose and in the hope of providing example.
D.4 DETAILED EVALUATION SETUP FOR ATARI GAMES
We introduce the detailed evaluation setups for the three certification methods corresponding to the experiments in Section 6
We report results averaged over 10 episodes and set the length of the horizon = 500. At each time step, we sample m = 10, 000 noisy states for smoothing. When applying Hoeffding's 's inequality, the input state observations for the two Atari games are in image space, we rescale the input states such that each pixel falls into the range [0, 1]. When adding Gaussian noise to the rescaled states, we sample Gaussian noise of zero mean and different variances. Concretely, the standard deviation is selected among (0.001, 0.005, 0.01, 0.03, 0.05, 0.1, 0.5, 0.75, 1.0, 1.5, 2.0, 4.0). We evaluate different parameters for different environments.
Evaluation Setup for CROP-LOACT.
adopt the confidence level parameter
0.05. Since
We sample m 10, 000 g-randomized trajectories, each of which has length H = 500, and conduct experiments with the same set of smoothing parameters as in the setup of CROP-LOACT. When accumulating the reward, we set the discount factor y 1.0 with no discounting. We take a = 0.05 as the confidence level when applying Hoeffding's inequality in the expectation bound JR, and a = 0.05 as the confidence level for CCMP UT BORD TATAT the percentile bound Jp. For the validation of tightness, concretely, we carry out 10-step PGD attack with &g radius within the perturbation bound at all time steps during testing to evaluate the tightness of our certification.
Evaluation Setup for CROP-
Evalution Setup for CROP-LORE. We set the horizon length H 200 and sample 10, 000 noisy states with the same set smoothing variance as in the setup of CROP-LOACT. Similarly, adopt 7 1.0 the discount factor and 0.05 as the confidence level when applying Hoeffding's inequality. When evaluating Freeway, we modify the reward mechanism so that losing one ball incurs a zero score rather than negative score. This modification enables the pruning operation and therefore facilitates the search algorithm, yet still respects the goal of the game. We also empirically attack the policy स to validate the tightness of the certification via the same PGD attack as described above. For each set of experiments, we run the attack one time with the same initial state as used for computing the lower bound in Algorithm 3
D.5 EXPERIMENTAL SETUP FOR CARTPOLE
We additionally experiment with CartPole-vO in OpenAl Gym (Brockman et al. 2016) on top of the
Arcade Learning Environment (Bellemare et al. 2013). We introduce the experimental setup below.
The state in the CartPole game is low dimensional vector of length 4 and the action E {move right, move left). The goal of the game is to balance the rod on the cart, and one reward point earned at each timestep when the rod is upright.
Details of the CartPole Environment.
StdTrain, SA MDP (PGD), SA MDP (CVX) from Apache-2.0 T.0eee
Dgk and RadialRL from htt:ps
25

---

Published as a conference paper at ICLR 2022
Implementation Details of the RL Methods on CartPole. In addition to the eight RL Methods evaluated on Pong and Freeway as shown in infSection 6J we evaluate another RL algorithm CARRL (Ev erett et al. 202T). which is claimed to be robust in low dimensional games like CartPole. This method relies on linear bounds output by the Q network and selects the action whose lower bound of the Q value is the highest. More detailed introduction the algorithm and description of the implementation details are provided in Ampepdxx D.2]
Evaluation Setup for CROP-LOACT on CartPole. We report results averaged over 10 episodes and set the length of the horizon H = 200. At each time step, we sample m = 10, 000 noisy states for smoothing. When applying Hoeffding's 's inequality, we adopt the confidence level parameter = 0.05. We do not perform rescaling on the state observations. When adding Gaussian noise to states, we sample Gaussian noise of zero mean and different variances. Concretely, the standard deviation a is selected among {0.001, 0.005, 0.01, 0.03, 0.05, 0.1}.
Evaluation Setup for CROP-GRE on CartPole. We sample m = 10, 000 o-randomized trajec- tories, each of which has length H/ = 200, and conduct experiments with the same set of smoothing parameters as in the setup of CROP-LOACT. All other experiment settings are the same as Pong and Freeway in Appendix D.4
Evalution Setup for CROP-LORE on CartPole. Since the reward of CartPole game quite dense, set the horizon length as H 10 and sample 10, 000 noisy states with the same set of smoothing variance as the setup of CROP-LOACT, All other experiment settings are the same as Pong and Freeway in Appendix D.4
D.6 EXPERIMENTAL SETUP FOR HIGHWAY
In addition to the previous environments in OpenAl Gym (Brockman et al.) 2016) on the Arcade Learning Environment (Bellemare et al.) 2013), we also evaluate our methods in the Highway environment (Leurent 2018). Specifically, we test out algorithms in the highway-fast-ve environment.
Details of the highway Environment. matrix, where each line represents feature vectors of either the ego vehicle or other vehicles closest to the ego vehicle. The feature vector for each vehicle has the form of [z. y, ux, uy, 1]. corresponding to the two-dimensional positions and velocities and additional indicator value. The actions high-level control actions among (lane left, idle, lane right, faster, slower). The reward mechanism in this environment is associated with the status of the ego vehicle; more concretely, it gives higher reward for the vehicle when it stays at the rightmost lane, moves at high speed, and does not crash into other vehicles.
The state in the highway-fast-vl environment is 5 x
Evaluation Setup for CROP-LOACT on highway. We report results averaged over 10 episodes and set the length of the horizon H 30, which is the maximum length of an episode in the environment configuration. At each time step, we sample m = 10, 000 noisy states for smoothing. When applying Hoeffding's inequality, we adopt the confidence level parameter a 0.05. We do not perform rescaling on the state observations. When adding Gaussian noise to states, we sample Gaussian noise of zero mean and different variances. Concretely, the standard deviation is selected among {0.005, 0.05, 0.1, 0.5, 0.75, 1.0].
Evaluation Setup for CROP-GRE on highway. We sample m 10, 000 o-randomized trajec- tories (each of which has length H = 30) and conduct experiments with the same set of smoothing parameters as in the setup of CROP-LOACT. All other experiment settings are the same as Pong and Freeway in Appendix D.4
Evalution Setup for CROP-LORE on highway. Since the reward of highway game is also quite dense, we set the horizon length H 10 as in the CartPole environment and sample 10, 000 noisy states with the same set of smoothing variance as the setup of CROP-LOACT. All other experiment settings the same Pong and Freeway in Appendix D.4
26

---

Published as a conference paper at ICLR 2022
StuFain
Go ussAug
Advitain
SA-MPP (NCD)
SAMIP (CVX)
RadalRL
ew3 665
2-43
7.45
1.0075
0-14
68
#v3365
14
11
Inal
81 2F
1/1
04
10
12
mm8
Pont
2
92
90
radies
radlus
Figure 4: Robustness certification for per-state action in of certified ratio 7 certified radius Each column corresponds to one smoothing parameter σ. The shaded area represents the standard deviation.
Stdfrain
GaussAug
AdiTraiin
SA-MDP (PGD)
SA-MPP (CVX)
RadiaIRI
2.0
1.5
2.0
4.0
Rodius:
042
100 00
300
300
0.3 2.0
100 15
Eime stop
Time stop
Hine step
atlack
(a) Certified radius R; along time steps
(b) Absolute lower bound w.r.t. attack e
Figure 5: Robustness certification for (a) per-state action in terms of certified radius at all time steps, and (b) cumulative reward terms of absolute lower bound J w.r.t. the attack magnitude The results are reported under large smoothing parameter a compared with those evaluated in Figure and Figure 3 in the main paper.
E ADDITIONAL EVALUATION RESULTS AND DISCUSSIONS
E. ROBUSTNESS CERTIFICATION FOR PER-STATE ACTION CERTIFIED RATIO
We present the robustness certification for per-state action in terms of the certified ratio 7}. w.r.t the certified radius Figure 4 From the figure, we that RadiaIRL is the most certifiably robust method on Freeway, followed by SA-MDP (CVX) and SA-MDP (PGD); while on Pong, SA-MDP (CVX) is the most robust. These conclusions observed from Figure I Comparing the curves for Freeway and Pong, we note that Freeway not only achieves larger certified radius overall, it also more frequently attains large certified radius.
highly consistent with those in /Scctin 6. as
E.2 RESULTS OF FREEWAY UNDER LARGER SMOOTHING PARAMETER O
Since the robustness of the methods RadialRL., SA-MDP (CVX), and SA-MDP (PGD) on Freeway have been shown to improve with the increase of the smoothing parameter a in [Section 6 we subsequently evaluate their performance under even larger values. We present the certification results in Figure 5 and their benign performance in Figiue 6
First of all, as Figure 6 reveals, RadiaIRL, SA-MDP (CVX), and SA-MDP (PGD) can tolerate quite large noise-the benign performance of these methods does not drop even for up to 4.0. For the remaining three methods, the magnitude of noise they can tolerate is much smaller, already presented in Figure 2]in the main paper. On the other hand, although all the three methods Radi- aIRL, SA-MDP (CVX), and SA-MDP (PGD) invariably attain good benign performance as a grows, their certified robustness does not equally increase. As Figure 5) shows, the certified robustness of SA-MDP (PGD) increases the fastest, while that of RadialRI. drops little. The observa-
Freeway
Conuaaae roward
Stafian
Gausskup
Advita
SANDPR (PS0)
SANDP (CV3)
cummu
RedilL
Figure 6: Benign performance of locally smoothed policy # under a larger range of smoothing parameter a with clean state ab- servations.
27

---

Published as a conference paper at ICLR 2022
3C0M4
Periodic patterns in Pong. figure shows two periods (left and right), including the certified radius r w.r.t the time steps (above), and the selected game frames corresponding to different stages in each period (below). Different periods are highly similar.
Figure 7:
tion corresponds exactly to our discussion regarding the tradeoff between value function smoothness and the margin between the values to the top two actions Section
E.3 PERIODIC PATTERNS FOR PER-STATE ROBUSTNESS
We specifically study the periodic patterns for per-state robustness in Pong and present the results in Figure 7 In the game frames, our agent controls the green paddle on the right. Whenever the opponent (the orange paddle on the left) misses catching a ball, we earn point. We present two periods (frame 320-400 and frame 400-480) where our agent each earns a point in the figure above. The total points increase from 3, and from 3 to 4, respectively.
We note that Pong is a highly periodic game, with each period consisting of the following four game stages corresponding to distinct stages of the certified robustness: 1) A ball is initially fired and set flying towards the opponent. In this stage, the certified radius remains low, since not need to take any critical action. 2) The opponent catches the ball and reverses the direction of the ball. In this stage, the certified radius gradually increases, since the moves of our agent serve as the preparation to catch the ball. 3) The ball bounces from the ground, flies towards our agent, gets caught, and bounces back. In this stage, the certified radius increases rapidly, since every move is critical in determining whether we will be able to catch the ball, i.e., whether our point (action value) will increase. 4) The opponent misses the ball, and the ball disappears from the game view. In this stage, the certified radius drastically plummets to low value, since there is no clear signal (i.e., ball) in the game for the agent take any determined action.
agent does
The illustration not only helps us understand the semantic meaning of the certified radius, but can further provide guidance on designing empirically robust RL algorithms that leverage the information regarding the high/low certified radius of the states.
E.4 DETAILED DISCUSSIONS AND SELECTION SMOOTHING PARAMETER o
We first take Freeway as an example to concretely explain the impact of smoothing variance from the perspective of benign performance and certified results, and then introduce the guidelines for the selection of a based on different certification criteria.
On Freeway, as a increases, the benign performance of the locally smoothed policy of StdTrain, GaussAug, and Adv advTrain decrease rapidly in Figure 2) Also, the certified radius of these methods barely gets improved and remains low even as a increases. For the percentile bound Jg. these three methods similarly suffer a drastic decrease of cumulative reward not the case for SA-MDP (PGD), SA-MDP (CVX), and RadiaIRI., for which not only the benign performance do not experience much degradation for a as large as 1.0, but the certified radius even steadily increases. In addition, in terms of the percentile bound Jp. grows, even increase the attack simultaneously, Jp almost does not decrease. This indicates that larger smoothing variance can bring more robustness SA-MDP (PGD), SA-MDP (CVX), and RadiaIRI.
grows. This however
28

---

Published as a conference paper at ICLR 2022
CROP-LOACT. We discuss how to find the sweet spot that enables high benign performance and robustness simultaneuusly. As a increases, the benign performance of different methods generally decreases due to the noise added, while not all methods decrease at the same rate. On Freeway, StdTraii and GaussAug decrease the fastest, while SA-MDP (PGD), SA-MDP (CVX), and RadialRT. do not degrade much even for a large as 4.0. Referring back to Figure I Jand 5| we see that the certified radius of StdTrain and GaussAug remains low even though a increases, thus the best parameters for these two methods are both around 0.1.
For SA-MDP (PGD) and SA-MDP (CVX), their certified radius instead steadily increases as a increases 4.0, indicating that larger smoothing variance can bring more robustness to these two methods without sacrificing benign performance, offering certified radius larger than 2.0. As to RadialRL., its certified radius reaches the peak at a 1.0 and then decreases under larger a. Thus, 1.0 is the best smoothing parameter for RadialRI. which offers a certified radius of 1.6. Generally speaking, it is feasible to select an appropriate smoothing parameter a for all methods to increase their robustness, and robust methods will benefit more from this by admitting larger smoothing variances and achieving larger certified radius.
PROP-GRE. We next discuss how to leverage Figure 3 to assist with the selection of a. For given E or a known range of E, we can compare between the lower bounds corresponding to different and select the one that gives the highest lower bound. For example, if we know that is small in advance, we can go for a relatively small a which retains a quite high lower bound. If we know that e will be large, we will instead choose among the larger o's, since larger will not fall in the certifiable ranges of smaller a's. According to this guideline, we are able to obtain lower bounds of quite high value for RadiaIRL, SA-MDP (CVX), and SA-MDP (PGD) on Freeway under larger range of attack e.
CROP-LORE. Apart from the conclusion that larger smoothing parameter a often secures higher lower bound J, we point out that smaller smoothing variances may be able to lead to a higher lower bound than larger smoothing variances for a certain range of e. This is almost always true for very small & since smaller a is sufficient to deal with the weak attack without sacrificing much empirical performance, egg., in Figure 3 when e = 0.001, SA-MDP (CVX) on Freeway can achieve J at 0.005 while only J I for large o. This can also happen to robust methods at large e.g. when E = 1.2, RadialRL on Freeway achieves J = 2 at a = 0.75 while only J = at a 1.0. Another case is when a is large enough such that further increasing will not bring additional robustness. e.g. in Figure 5] when E = 1.5, RadialRL on Freeway achieves J = 1 at o = 1.5 while only J = 0
4.0.
E.5 COMPUTATIONAL COST
Our experiments are conducted on GPU machines, including GeForce RTX 3090, GeForce RTX 2080 Tí, and GeForce RTX 1080 The running time of m = 10000 forward passes with sampled states for per-state smoothing ranges from 2 seconds to 9 seconds depending on the server load. Thus, for one experiment of CROP-LOACT with trajectory length H 500 and 10 repeated runs, the running time ranges from 2.5 hours to 12.5 hours. CROP GRE is a little more time-consuming than CROP-LOACT, but the running time is still in the same magnitude. For trajectory length H = 500 and sampling number m 10000, most of our experiments finish within 3 hours. For CROP-LORE specifically, the running time depends on the eventual size of the search tree, and therefore differs tremendously for different methods and different smoothing variances, ranging from few hours to 4 to 5 days.
E.6 DISCUSSION ON EVALUATION RESULTS OF CARTPOLE
We provide the evaluation results for CROP on CartPole, comparing nine RL algorithms: the six algorithms evaluated in our main paper (StdTrain, GaussAug, AdvTrain, SA-MDP (PGD), SA-MDP (CVX), and RadialRL), as well as three additional algorithms (CARRL, NoisyNet, and GradDQN). The detailed descriptions of these algorithms are provided in Appendix D.2 We present the evaluation results in Figure 8
Impact of Smoothing Parameter a. In CartPole game, we draw similar conclusions regarding the impact of smoothing variance from the results given by CROP-LOACT, CROP-GRE and CROP-
29

---

Published as a conference paper at ICLR 2022
LORE. For small a. different methods indistinguishable. As increases, CARRL demonstrates its advantage as a increases, but AdvTrain and GradDQN tolerate large noise. One of differences when evaluating with CROP-GRE and CROP-LORE is that RadialRL can hold high performance and even sometimes can be better than CARRL.. Another one is that the lower bound for GradDQN is lower than all other methods in CROP-LORF.
Tightness of the certification JE, J, and J. In CartPole, we also compare the empirical cumula- tive rewards achieved under PGD attacks with our certified lower bounds J/g Jp and J. Demonstrated by Figure 8c first of all, the correctness of our bounds is validated because the empirical results are consistently lower bounded by our certifications. Compared with the loose expectation bound Jg, the improved percentile bound Jp is much tighter. Compared with these two methods, the absolute lower bound J is even tighter, especially noticing the zero gap between the certification and the empirical result when the attack magnitude is not too large. Finally, methods with the same empirical results under attack may achieve very different certified lower bounds Jg. Jp and J. showing the importance of certification.
Environment Properties. Different from Pong and Freeway, CartPole an environment with low dimension states, in contrast to the high dimensional Atari games evaluated in [Section 6 This gives rise to several outcomes. First, StdTrrii can tolerate noise well in CartPole. Second, CARRL demonstrates its advantage in low dimensional game, which is consistent with the empirical observations in Everett et al. (202T).
E.7 DISCUSSION EVALUATION RESULTS OF HIGHWAY
We next present the evaluation results for CROP on an autonomous driving environment Highway, whose state dimension is larger than CartPole but smaller than Atari games. We compare nine RL algorithms as introduced previously. We present the evaluation results in Figure
Impact of Smoothing Parameter a.. In highway, CARRL demonstrates its advantage when is small, which is supported by results in all three certifications CROP-LOACT, CROP-GRE, and CROP-LORF. For action certification (i.e., CROP-LOACT)), SA-MDP (PGD) can tolerate large range of meaning that the action selection of model trained with SA-MDP (PGD) algorithm is more consistent than other methods. For reward certification (i.e., CROP-GRE and CROP-LORE), we derive the conclusion that RadialRL outperforms than other methods when a is large.
Tightness of the certification JE, Jg and J. In highway, we compare the empirical cumulative rewards achieved under PGD attacks with our certified lower bounds Jg, Jp. and J. The correctness of our bounds validated because the empirical results are consistently lower bounded by our certifications, as shown in Figure 9c As for the tightness of reward certification methods, we draw similar conclusion as other environments - is the most tight, followed by Jp: and JE is much looser than Jp and Jg. We also notice the non-negligible gap between certified lower bounds and the empirical rewards demonstrated by RadialRL and CARRL under large smoothing parameters. This may imply that there exists large scopes for improving the attack method, or there is potential to further tighten the certified lower bounds.
F A BROADER DISCUSSION ON RELATED WORK
F.I EVASION ATTACKS RL
We consider the adversarial attacks on state observations, where the attacker aims to add perturbations to the state during test time, selection and minimizing the cumulative reward. We discuss the related works that fall into these two categories below.
achieve certain adversarial goals, such as misleading the action
Mislcading the Action Selection. It has been shown that different methods- random noise to simply interfere with the action selection (Kos & Song 2017). adopting adversarial attacks (e.g., FGSM (Goodfellow et al.) 2014) and CW attacks (Carlini & Wagner (01g)) to deliberately alter the probability of action selection are effective different degrees. More concretely, when manipulating the action selection probability, some works aim to reduce the probability of selecting
30

---

Published as a conference paper at ICLR 2022
Sodtrenn
SI-MPP (PGD)
SANDP
CARRI
Neteyfirr
Gredioo
CarPull
Rallus
Te-S
8:28
00
1e-2
1e-2
1e-2
8:20
6:30
2.0
100
2.20
6:20
6:00
5.0
0.00
50
300
57
100
202
200
1550
202
100
150
200
100
150
step
step
step
step
(a) Robustness certification for per-state action in terms certified radius r at all time steps. The shaded area represents the standard deviation.
CartPole
Stalhann
GoussAup
Advirain
150
SA/IDD (PCD)
MDP ICV))
100
Noisyfitt
GNazDON
1ec3
Imx2
Sen2
Im-1
(b) Benign performance of locally smoothed policy म under different smoothing variance d.
SAMO p0cc butthie
0.05
(Ciobal)
-250
-12
-100)
-200
(Gicbal) Jo.
150
180
320
120
1.9
120
140
260
220
80
80
66
85
0.5
1.0
15
0.0
05
1.0
0.0
0.5
10
15
20
10
15
20
(Lacal)
2.002 0/004 2.22 0:308
0.00 0.52
0.04
5.32
Attack C
ataakk C
attack C
ollack
asack
attack
(c) Robustness certification as cumulative reward, including expectation bound JE. percentile bound Jp (p 50%), and absolute lower bound J. Solid lines represent the certified reward bounds of different methods, and dashed lines show the empirical performance under PGD attacks.
Figure 8: Robustness certification on CartPole in terms of (a-b): robustness of per-state action and (c): lower bound of cumulative rewards. In (a) and (c), each column corresponds to one smoothing variance.
31

---

Published as a conference paper at ICLR 2022
Sidtrai
AdvThan
SA-MDP
SANDP
Racialfi
CAMIL
Neteyfl::
GradDig
0-505
0-45
a-235
highnwe
stop
step
step
step
step
(a) Robustness certification for per-state action in terms certified radius r at all time steps. The shaded area represents the standard deviation.
Highway
Stdirain
GoussAug
Advitein
20
(PGD)
15
10
CARRL
Nalsyket
GradDON
5e.3
Se-2
16:1
Se.1
7.5e.1
1.0
(b) Benign performance of locally smoothed policy मे under different smoothing variance
CLIEE Impoiia
0.005
0.05
0.1
0.5
0.75
1.0
kow8t88
(Gbbba)) J.z.
12-4
10-3
20-2
20-2
16-1
16-3
(Ciobbal) L.p.
0.0
5.5
1.5
6:30 0.25 0.50
3,65
0.0
05
1.3
1.
21
(Local) 1
$.90
3.2
9.13
0.0
sttack 5
attack
sttack
attack
Oftici 6
(c) Robustness certification as cumulative reward, including expectation bound JE, percentile bound Jp (p 50%), and absolute lower bound J. Solid lines represent the certified reward bounds different methods, and dashed lines show the empirical performance under PGD attacks.
Figure 9: Robustness certification on highway in terms of (a-b): robustness of per-state action and (c): lower bound of cumulative rewards. In (a) and (c), each column corresponds to one smoothing variance.
32

---

Published as a conference paper at ICLR 2022
the optimal action (Huang et al. 2017: Kos & Song 2017 Behzadan & Munir 2017b), while others Pattanaik et al. 2018).
try to increase the probability of selecting the worst action (Lin et al. 201 7
Minimizing the Cumulative Reward. ATLA Zhang et al. 2021 and PA-AD (Sun et al. 2021 consider an optimal adversary under the SA-MDP framework (Zhang ct al. 2020), which aims to lead to minimal value functions under bounded state perturbations. To find this optimal adversary (i.e.,
the optimal adversarial state perturbation). ATLA (Zhang et al. (2021) proposes to train an adversary whose action space is the perturbation set in the state space, while PA-AD (Sun al. 202 I) further decouples the problem of finding state perturbations into finding policy perturbations plus finding the state that achieves the lowest value policy, thus addressing the challenge of large state space.
F.2 ROBUST RL
Distributionally Robust RL. Nilim & El Ghaoui (2005) and Lyengar (005) of distributionally robust RL, where there is normally an uncertainty set with prior information regarding the distribution of the uncertain parameters. [yengar (005) directly put constraints on environmental dynamics and reward functions by assuming that they take values in an uncertainty set. Another line of research assumes the environmental dynamics and reward function as the uncertain parameters and are sampled from an uncertain distribution in the uncertain set. The uncertainty set is in general state-wise independent, Le.,, "s-rectangularity" in Nilim & El Ghaoui (2005). Both types aim to derive a policy by solving max-min problem, with the former taking the minimum directly over the parameters, while the latter taking the minimum over the distribution.
consider the problem
Empirically Robust RL against Evasion Attacks. We have briefly introduced related work on empirically robust RI. in infeectoon in the main paper. We emphasize two main differences between the contributions of these works and our CROP. First, most of these robust RL. methods only provide empirical robustness against perturbed state inputs during test time, but cannot provide theoretical guarantees for the performance of the trained models under any bounded perturbations; while our CROP framework can provide practically computable certified robustness w.r.t. two robustness certification criteria (per-state action stability and cumulative reward lower bound), i.e., for given RL algorithm, we can compute certifications for it that indicate its robustness. (We will discuss few more related work that can provide certified robustness in Apppeddix F.3) Second, most of these Robust RL methods focus on only the per-state decision, while we additionally consider the certification of trajectories obtain the lower bound of cumulative rewards. Below, we provide more comprehensive review of the categories of RL methods that demonstrate empirical robustness against evasion attacks.
Randomization methods (Tobin et al. exploration. This type of method was later systematically studied for its potential to improve model robustness. NoisyNet (Fortunato et al. 2017) adds parametric noise to the network's 's weight during training, providing better resilience to both training-time and test-time attacks (Behzadan & Munir 2018). also reducing the transfcrability of adversarial examples, and enabling quicker recovery with fewer number of transitions during phase transition.
2017] Akkaya et al. 2019) were first proposed to encourage
Under the adversarial training framework, Kos & Song (2017) and Behzadan & Munir (017b) show that re-training with random noise and FGSM perturbations increases the resilience against adversarial examples. PPtttnaik et al. (2018) leverage attacks using engineered loss function specifically designed for RL to significant increase the robustness to parameter variations. RS-DQN (Fischer al. 2019) is an imitation learning based approach that trains robust student-DQN in parallel with a standard DQN in order to incorporate the constrains such as SOTA adversarial defenses (Madry
al. 2017 Mirman et al. 2018).
SA-DQN (Zhang et al. 2020) is a regularization based method that adds regularizers to the training loss function to encourage the top-1 action stay unchanged under perturbation.
Built on top of the neural network verification algorithms (Gowal et al., 2018: Weng et al. 2018).
Radial-RL (Oikarinen et al. (2020) proposes to minimize an adversarial loss function that incorporates the upper bound of the perturbed loss, computed using certified bounds from verification algorithms. CARRL (Everett et al., 2021) aims to compute the lower bounds of action-values under potential perturbation and select actions according to the worst-case bound, but it relies on linear bounds (Weng) ct al. 2018) and is only suitable for low-dimensional environments.
33

---

Published as a conference paper at ICLR 2022
F.3 ROBUSTNESS CERTIFICATION FOR RL
Despite the abundant literature in robustness certification in supervised learning, there is almost no work robustness certification for RL, given the unclear criteria and the intrinsic difficulty of the task. In this part, we first introduce another two works that can achieve robustness certification at state-level, and then another concurrent work Kumar et al. (021)) which also aims to provide provable robustness regarding the cumulative reward for RL..
Robustness Certification State Level. Fischer et al. (219)) and Zhang al. (2020) have discussed the state level robustness certification as well, but the way they obtain the certification is different from CROP. Concretely, achieve robustness by probabilistic certification via randomized smoothing (Cohen et al. 2019). while |isccer et al. (2019) and (Zhang et al. (2020) directly achieve robustness by deterministic certification via leveraging the neural network verification techniques (Zhang et al. 2018 Xu et al., 2020 Mirman et al. 2018).
Despite these works on state-level robustness certification for RL, we are the first to provide the certification of cumulative rewards. We emphasize that the certification of lower bound of the cumulative reward in RL is more challenging than the per-state certification considering the dynamic nature of RI. Our main contribution of the paper indeed mainly focuses on providing an efficient adaptive search based algorithm CROP-LORE to certify the lower bound of the cumulative reward together with rigorous analysis of the certification.
Robustness Certification for Cumulative Rewards. We compare our robustness certification for cumulative rewards with another concurrent work Kumar et al. (2021).
In terms of the threat model, both Kumar et al. (202T) and CROP consider the type of adversary that can perturb the state observations of the agent during test time. In our CROP, we consider
perturbation budget per time step following previous works (Huang et al., 2017 Behzadan & Munir 2017b; Kos & Song. 2017 Pattanaik et al. 2018 Zhang al. (2220), while they assume a budget for the entire episode. The two perspectives are closely related.
Regarding the certification criteria, certify both per-state action stability and cumulative reward lower bound. Although they also consider the cumulative reward their certification goal, they formulate the certification a classification problem-certifflnn whether the cumulative reward is above a threshold or not, in contrast to directly certifying the lower bound as in our case.
For the certification technique, both works developed based on randomized smoothing proposed in supervised learning (Cohen et al.) (019).. We propose global smoothing technique (CROP-GRE)) as well an adaptive search algorithm coupled with local smoothing (CROP-LORE) to achieve the certification of cumulative reward; while they propose an adaptive version of the Neyman-Pearte Pearson lemma, which is similar with our global smoothing. Among the three algorithms (CROP- (CROP-GRE. CROP-LORE, and Kumar et al. (2020)), CROP-GRE cannot defend against an adaptive adversary (as concretely stated in Appendix C while the other two can; specifically, CROP-LORE is much more sophisticated and tight than the global smoothing ones, which is an important contribution in our work.
34


Reviews:
[{"review_id": "zgVgXzLXW6O", "reviewer": "Reviewer_tzpV", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "Strengths:\n\n1. This paper is well-written. The formulations are clear and easy-to-follow. The algorithm and experiment settings are discussed in detail in Appendix.\n2. The certification makes intuitive sense, and seems to be correct, although I have not checked the detailed proof.\n3. Both per-state action certification and cumulative reward certification are provided, while most related works do not discuss the reward certification.\n4. The experimental results are interesting. The author provide a leaderboard that shows the comparison of many robust RL algorithms in different settings, which could be helpful for the evaluation of robust RL methods.\n\n\nWeaknesses:\n\n1. The certifications are straightforward application of the randomized smoothing certification used in supervised learning, which is not surprisingly novel. But different from supervised learning, the certified radii in this paper involve $V_{min}, V_{max}$ and $J_{min}, J_{max}$ which can be hard to obtain in practice, and may make the bound vacuous. The authors have provided methods to address the challenge of estimating these terms, but it also seems to be expensive. \n2. The certifications on cumulative reward seem to be a little naive, and too expensive. The global smoothing method estimate the reward of many smoothed trajectories. But the noise sequence $\\zeta$ is of dimension $H\\times N$. As a result, it is hard to accurately estimate $\\tilde{F}$. For the local smoothing method, an exhaustive search is needed, which could require exponential sample and computation cost.\n3. For the cumulative reward, the \"certification\" is estimated by sampling methods. But as point 2 above states, it is sampling a very high-dimensional random vector, which may result in very inaccurate estimations. Then the certification can not serve as a strict lower bound of the cumulative reward. It is possible that a strong attack (e.g. [1]) can reduce the cumulative reward to be lower than the estimated certification. But this paper only tests the reward under a simple PGD attack.\n4. Some related works are missing. This paper claims to be the first certification work for RL, but another paper[2] also proposes a smoothing-based certification for cumulative rewards. Although [2] is a very recent paper and can be regarded as concurrent work, I would suggest the authors to mention this paper and discuss the relation and differences between two papers.\n5. Pong and Freeway are relatively simple compared to other Atari games. And the reward scales in these two games are small, thus it is hard to justify the tightness of the bound. In many literature[3], BankHeist and RoadRunner are used in addition to Pong and Freeway. So I would be happy to see more experimental results in these two games in order to better evaluate the proposed method.\n\nMinor issues that do not affect my score:\n1. The proposed certification only works for a greedy policy based on a Q-network. It will be better if the authors can provide some discussions on policy-based methods such as PPO.\n2. This paper focuses on certifying an existing policy, and does not provide a method for adversarial training.\n\n\nRefs:\n\n[1] Sun et al. \"Who Is the Strongest Enemy? Towards Optimal and Efficient Evasion Attacks in Deep RL.\" \n\n[2] Kumar et al. \"Policy Smoothing for Provably Robust Reinforcement Learning.\" \n\n[3] Zhang et al. \"Robust deep reinforcement learning against adversarial perturbations on state observations.\"", "summary_of_the_paper": "This paper proposes two robustness certification criteria for Q-learning based RL policies under adversarial state perturbations: per-state action robustness and lower bound of cumulative rewards. The certification is mainly based on the randomized smoothing technique. For certifying the cumulative reward, two smoothing methods (global smoothing and local smoothing) are presented with different lower bound formulations. With the proposed smoothing methods, the authors empirically evaluate and compare 6 robust RL approaches in 3 environments, showing the applicability of the proposed method.", "summary_of_the_review": "This paper focuses on an important problem of certifying RL policies against state perturbations. The proposed method makes intuitive sense, but as a direct application of the randomized smoothing technique, the novelty is a little limited. Although theoretical analysis of the lower bound of cumulative rewards is provided under 2 smoothing settings, the estimation of the lower bound could be either too loose or too expensive. The empirical evaluation is interesting and helpful for understanding recent robust RL works, but there is no enough evidence for the effectiveness of the proposed method (the tested environments are relatively simple). Therefore, I think this paper is around the borderline, and has the potential to be accepted. But at the current stage, I tend to reject it, unless more improvements are made (e.g. a more practical smoothing method, theoretical complexity analysis, or experiments in more complicated environments).\n\n\n---\nAfter rebuttal: the authors have provided more implementation details and experimental results, which I find interesting. So I increased my score.\n", "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": "eZjLJLGaQ8Z", "reviewer": "Reviewer_zGtv", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "The paper provides a comprehensive study of the RL robustness in the per-state setting as well as a per-trace setting. I am delighted to see interesting work beyond per-state certification in the RL setting.\nFurthermore, the mathematical parts are well written and can be followed easily.\n\nHowever, I am wondering about several aspects of the submission, which I hope the authors can clarify:\n- Can you justify the claim to be the \"first framework for certifying the robustness of Q-learning algorithms\", given works like [2,3] and others exist? ([3] is even discussed in the text.) Granted, with the exception of parallel work, this is the first paper to look at the certification of traces rather than just per-state decisions.\n- Can you elaborate on the inference/prediction procedure for the agents in all CROP settings? The text outlines only the certification. Is it sufficient to invoke the model with a single sample of Gaussian Noise at each step in inference, or is a procedure like Predict in [1] used?\n  As I understand (2), at least for CROP-LoAct this is the case.\n- I am generally confused whether CROP aims to be a testing-framework or a certified defense. Mathematically, sections 3-5 present a certified defense (e.g. something that is a applied to a base model) to obtain certifiable guarantee.\n  Yet, sentences like \"... we find that (1) RegCVX, RegPGD and RadialRL achieve high certified robustness...\" or \"As the first work providing robustness certification for RL, we expect more RL algorithms and games will be certified under our framework in future work.\" make CROP look like a testing/certification framework. This compounds with the fact that inference is not discussed (see previous question), as it seems one can just run a RadialRL model without further considerations to obtain the robustness guarantees outlined here.\n- Does CROP-LoRe account for multiple-testing? Since the individual local certificates only hold with confidence $1-\\alpha$ (which according to E.4 you choose as 0.05), a CROP-Lore certificate invoking N local certificates holds with at most confidence $1-N\\alpha$.\n- Why does CROP-LoAct not rephrase picking the action as a classification problem and directly apply the approach from [1], thus sidestepping the challenges outlined in 4.2? Is it because you rely on this form of certificate in CROP-LoRe?\n- Does CROP-LoRe need access to an oracle transition function $\\Gamma(s, a)$ which can execute the transition for a given $s$? If this is the case this seems a departure for the standard RL-setting where the environment can only be queried in a fixed temporal order. While I think this is perfectly fine for the considered purpose, such a departure from standard should be clearly indicated.\n- Does Lemma 2 hold if the adversary can arbitrarily choose $\\zeta_{t}$ based on the smoothed actions at steps $0, \\dots, t$? It seems to me the presented Lemma 2 only holds if the attacker commits to the values of $\\zeta_{t}$ beforehand.\n\nWhile I like the high-level approach and I think its a valuable area of investigation, I am not convinced by the presentation and potentially technical correctness (see questions) of the current submission. Further, it appears that recently a pre-print [4] was introduced, which concerns a similar topic. Could you briefly comment on the difference in approach. \n\nMinor:\n- There is a hyperlink (from a citation) crossing a page boundary at the end of the first page, which leads unpleasant artifacts.\n- The symbol used for smoothing noise seems to change between $\\zeta$ and $\\Delta$. If this is deliberate, I may have missed why.\n\n[1] Certified Adversarial Robustness via Randomized Smoothing, Cohen et al.; ICML 2019\n\n[2] Online Robustness Training for Deep Reinforcement Learning, Fischer et al.; arXiv 2019\n\n[3] Robust Deep Reinforcement Learning against Adversarial Perturbations on State Observations, Zhang et al., NeurIPS 2020\n\n[4] Policy Smoothing For Provably Robust Reinforcement Learning, Kumar et al., arXiv 2021", "summary_of_the_paper": "This paper introduces CROP, a framework for the certification of reinforcement learning (RL) agents against (adversarial) observation/state perturbations based on randomized smoothing (RS). Formally, certificates for individual per-state decision as well as cumulative scores are distinguished.\nIn order to obtain a per-state certificate the authors introduce CROP-LoAct, which applies RS to the individual decision of the agent on each state.\nFor cumulative-score certificates two approaches are considered:\nFirst, CROP-GRe which applies RS to the return function of a whole trajectory and obtains a bound either via mean smoothing or percentile smoothing.\nSecond, CROP-LoRe, which combines per-state certificates for a whole trace to obtain a score certificate. Via tree-search a lower bound for a given start state and base policy can be provided.\n\n", "summary_of_the_review": "A conceptually interesting approach to the verification of reinforcement learning in the per-state setting and beyond. However, the current manuscript leaves open questions about conceptual decisions and formal correctness.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "OiMoWIScAke", "reviewer": "Reviewer_PEk6", "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": "I believe works that certifies robust behaviours of a trained RL policy under adversarial perturbation to be helpful, and the ability to validate different RL-algorithms as more robust or less robust w.r.t. these perturbations (in the experimental section) is important and compelling. Overall I find the premise of the paper solid, and its empirical evidence well documented and solid.\n\nI cannot vouch for the correctness of the formal proofs, as I am not too good at analysis. However, I would like to ask a few questions:\n\n1) modeling of transition function perturbations : how would this work adapt to the setting where the adversary changes the transition function itself, rather than merely applying a noise on the current observation? for instance, imagine we train a maze-world agent on slip-free environment, and want to certify some of its properties in real-life where the world might be slippery?\n\n2) modeling structured perturbations : perturbation does not occur uniformly at random, typically there is a generative procedure which applies perturbation under some kind of distribution, allowing one to give tighter bounds if this generative procedure is modeled. for instance, in pong one might randomly generate hallucinated balls around the screen, or to fake multiple copies of the enemy paddle. how would the current approach extend to these structured perturbations?", "summary_of_the_paper": "This paper gives certification of RL models under worse-case state perturbations in two respects: 1) behaving the same way w.r.t. state-action pairs and 2) achieving similar rewards at the end of a sampled trajectory. The paper gives theoretical grounding on the proposed certifications and demonstrate empirically the certifications are sound.", "summary_of_the_review": "overall I am convinced this paper is solid based on its problem statement and empirical evidence, but I will defer to someone who can formally verify the math better.", "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": "F4vYe_63V63", "reviewer": "Reviewer_ZBtu", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "*Originality*\n\nThis work essentially extends robustness certification methods existing in supervised learning, to reinforcement learning. Although the idea of certification is new, the essence of robustness guarantees together with function perturbation is not new in the RL literature. As such, some significant literature review on robust MDPs and robust RL is cruelly missing.\n\n*Quality*\n\nEssentially, the two proposed certificates are based on a state perturbation to which either the Q-function or the policy is applied. As far as I understand, this does not affect the model itself but only the ordering in either the Q-values or the policy. As a result, this discredits the certificate.\nl. 47-53: the results obtained from CROP are problem-dependent. This may say something about the domain, but also about the certificate itself and how reliable it is. It is not clear which one of the two options applies.\nCROP designs a certification for the robustness of other previous algorithms, but the very method is not challenged in and of itself. Instead, in Sec. 6, it is shown how robust are different methods but the reliability of CROP itself is not tested.\n\n*Significance*\n\nOverall, I find several problematic issues in this work. On a higher level, the fundamental RL question is not \"how to certify robustness\" but rather \"how to attain robustness\". Thus, I disagree with the leading direction of that paper and am not sure how relevant it would be for RL researchers. Also, a comprehensive RL review and robustness in RL is strongly missing.\n\n*Clarity: Minor comments*\n\n- l. 5 \"smoothed with Gaussian noise\": these are \"perturbed\" rather than \"smoothed\" (\"smoothing\" is used for making a function continuous or the like)\n- l. 14 \"RegPGD, RegCVX, RadialRL\": those methods have never been described before, nor are they explained\n- l. 120, 121, 131 \"per-state action\": you may just use \"policy\" instead\n- l. 128 : Notation never introduced for those bounds. If these are reward bounds, then a  factor seems to be missing\n- l. 113-114: I do not understand the justification for focusing on a finite horizon.\n- l. 101 the maximum perturbation magnitude is uniform over the state-action space. Would not it be tiny then? How reliable would the certificate be if that radius gets close to 0? Also, a state-dependent  appears in Thm 1. This is confusing, or it should be discussed whether/when one would consider uniform VS state-dependent magnitude.\n- Thm 1- Notation is confusing. It refers both to the immediate reward (l. 72) and a radius ball in Thm 1.\n\n*English corrections*\n\n- l. 1 \"Certifying Robust Policies for reinforcement learning (CROP)\" --> \"Certifying Robust Policies (CROP) for reinforcement learning (RL)\"\n- l. 5 \"which uses\" --> \"that uses/using\"; l. 9 \"which makes use\" --> \"that uses/using\"\n- l. 10 \"for reward\" --> \"for the reward\"/ \"for performance\"\n- l. 15 \"we demonstrate that ... by evaluating ...\" --> \"by evaluating ..., we demonstrate that ...\" (revert)\n- Remove \"the\" in l. 29, 30, 31, 38, 83, 398\n- l. 25 \"In particular, adversarial training ... by enforcing the smoothness of the trained models\"--> \"In particular, by enforcing the smoothness of the trained models, adversarial training... \" (revert)\n- l. 27-28 \"have been proposed\", \"it is\" - time concordance\n- l. 31 \"deterministic approaches\" --> remove \"approaches\" (appears in l. 32)\n- l. 32 \"the lower bound\" --> \"a lower bound\"\n- l. 34 \"compared with classification model\" --> \"compared to classification\"\n- l. 37 \"Compared with\" --> \"Differently than\"\n- l. 37 \"classification model\" --> \"classification\"\n- l. 37 \"which only has one-step predictions\" --> \"which involves one-step prediction only\"\n- l. 37-38 \"both ... as well as ...\" --> \"both ... and\" or just \"as well as\"\n- l. 39 remove \"of RL\"\n- l. 48 \"game properties\" --> \"the game properties\"\n- l. 84 \"will be\" --> \"is\"\n- l. 94 \"following\" redundant\n- l. 105, 399 \"reinforcement learning\" --> \"RL\" (use abbreviation consistently -- or never use it)\n- l. 121 \"to calculate the lower bound of maximum perturbation magnitude in Def 1\" --> \"to calculate a lower bound of the maximum perturbation magnitude from Def 1\"\n- l. 126 \"the Gaussian distribution\" --> \"a Gaussian distribution\"\n- l. 140 \"the tradeoff\" --> \"a tradeoff\"\n- l. 400-403 A 3-line section is a bit weird\n\n*Missing references on robust RL (to name a few)*\n\n[1] Iyengar, Garud N. \"Robust dynamic programming.\" Mathematics of Operations Research 30.2 (2005): 257-280.\n\n[2] Nilim, Arnab, and Laurent El Ghaoui. \"Robust control of Markov decision processes with uncertain transition matrices.\" Operations Research 53.5 (2005): 780-798.\n\n[3] Tessler, Chen, Yonathan Efroni, and Shie Mannor. \"Action robust reinforcement learning and applications in continuous control.\" International Conference on Machine Learning. PMLR, 2019.", "summary_of_the_paper": "This work proposes a certification (CROP) attesting that a policy is robust against adversarial state perturbation. It finds its inspiration in the supervised learning literature and extends it to the sequential decision-making setting. Experiments on two Atari games test the performance of CROP.", "summary_of_the_review": "By construction, robust policies (i.e., those that solve max-min objective in robust MDPs) provide a robustness certificate that is more general than the two criteria provided in Def. 1 and 3. As such, I see this study as a specific case of prior work.  ", "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": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

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

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