Conservative Safety Critics for Exploration
Authors: Homanga Bharadhwaj
Aviral Kumar
Nicholas Rhinehart
Sergey Levine
Florian Shkurti
Animesh Garg
Venue: ICLR 2021 Poster (2021)
Keywords: Safe exploration
Reinforcement Learning

Abstract: Safe exploration presents a major challenge in reinforcement learning (RL): when active data collection requires deploying partially trained policies, we must ensure that these policies avoid catastrophically unsafe regions, while still enabling trial and error learning. In this paper, we target the problem of safe exploration in RL, by learning a conservative safety estimate of environment states through a critic, and provably upper bound the likelihood of catastrophic failures at every training iteration. We theoretically characterize the tradeoff between safety and policy improvement, show that the safety constraints are satisfied with high probability during training, derive provable convergence guarantees for our approach which is no worse asymptotically then standard RL, and empirically demonstrate the efficacy of the proposed approach on a suite of challenging navigation, manipulation, and locomotion tasks. Our results demonstrate that the proposed approach can achieve competitive task performance, while incurring significantly lower catastrophic failure rates during training as compared to prior methods. Videos are at this URL https://sites.google.com/view/conservative-safety-critics/

Published as a conference paper at ICLR 2021
CONSERVATIVE SAFETY CRITICS FOR EXPLORATION
Homanga Bharadhwaj'; Aviral Kumar", Nicholas Rhinchart Sergey Levine", Florian Shkurti', Animesh Garg' Univerriity of Toronto, Vector Institute Uniiveriiy of California Berkeley homangaêcs toronto.edi
ABSTRACT
Safe exploration presents major challenge in reinforcement learning (RL): when active data collection requires deploying partially trained policies, we must ensure that these policies avoid catastrophically unsafe regions, while still enabling trial and error learning. In this paper, we target the problem of safe exploration in RL by learning conservative safety estimate of environment states through critic, and provably upper bound the likelihood catastrophic failures at every train- ing iteration. We theoretically characterize the tradeoff' between safety and policy improvement, show that the safety constraints are likely to be satisfied with high probability during training, derive provable convergence bounds for our approach, which is no worse asymptotically than standard RL, and demonstrate the efficacy of the proposed approach on suite of challenging navigation, manipulation, and locomotion tasks. Empirically, we show that the proposed approach can achieve competitive task performance while incurring significantly lower catastrophic fail- ure rates during training than prior methods. Videos are at this url ht tts: / //sites. google. www/wwww//c//c//tc com//viee/conseevaaivee wows/rvatiieeeveeeooeeee safety- critics/
INTRODUCTION
Reinforcement learning (RL) is powerful framework for learning- based control because it can enable agents to learn to make decisions automatically through trial and error. However, in the real world, the cost of those trials and those errors can be quite high: quadruped learning to run as fast as possible, might fall down and crash, and then be unable to attempt further trials due extensive physical damage. However, learning complex skills without any failures at all is likely impossible. Even humans and animals regularly experience failure, but quickly learn from their mistakes and behave cautiously in risky situations. this paper, our goal to develop safe exploration methods for RL that similarly exhibit conservative behavior, erring on the side of caution particularly dangerous settings, and limiting the number of catastrophic failures.
A number of previous approaches have tackled this problem of safe exploration, often by formulating the problem as constrained Markov decision process (CMDP) (Garcia & Fernández, 2015; Altman, 1999). However, most of these approaches require additional assumptions, like assuming access to a function that can be queried to check if a state is safe (Thananjeyan et al., 2020), assuming access to default safe controller (Koller et al., 2018; Berkenkamp al., 2017), assuming knowledge of all the unsafe states (Fisac et al., 2019), and only obtaining safe policies after training converges, while being unsafe during the training process (Tessler et al., 2018; Dalal et al., 2018).
In this paper, we propose general safe RL algorithm, with bounds on the probability of failures during training. Our method only assumes access sparse (e.g., binary) indicator for catastrophic failure, in the standard RI. setting. We train a conservative safety critic that overestimates the prob- ability of catastrophic failure, building on tools the recently proposed conservative Q-learning framework (Kumar et al., 2020) for offline RL. In order to bound the likelihood of catastrophic failures at every iteration, we impose a KL-divergence constraint on successive policy updates so that the stationary distribution of states induced by the old and the new policies are not arbitrarily
Work done during HB's (virtual) visit Sergey Levine's lab UC Berkeley

---

Published as a conference paper at ICLR 2021
different. Based the safety critic's value, we consider a chance constraint denoting probability of failure, and optimize the policy through primal-dual gradient descent.
Our key contributions in this paper are designing algorithm that we refer to as Conservative Safety Critics (CSC), that learns a conservative estimate of how safe a state is, using this conservative estimate for safe-exploration and policy updates, and theoretically providing upper bounds the probability of failures throughout training. Through empirical evaluation in five separate simulated robotic control domains spanning manipulation, navigation, and locomotion, we show that CSC is able to learn effective policies while reducing the rate of catastrophic failures by up to 50% over prior safe exploration methods.
2 PRELIMINARIES
We describe the problem setting of a constrained MDP (Altman, 1999) specific to our approach and the conservative Q learning (Kumar et al., 2020) framework that we build on in our algorithm.
Constrained MDPs. We take constrained RL view of safety (Garcia & Fernández, 2015; Achiam et al., 2017), and define safe exploration as the process of ensuring the constraints of the constrained MDP (CMDP) are satisfied while exploring the environment to collect data samples. A CMDP is tuple (S,A, P. R, C). where S is the state space, A is the action space, P: P S x A x S + [0. 1] is transition kernel, R S A - R is task reward function, y E (0, 1) is discount factor, is a starting state distribution, and C = {(c; : S + {0, 1].X: X: E R)]i E Z} is a set of (safety) constraints that the agent must satisfy, with constraint functions G taking values either 0 (alive) or 1 (failure) and limits defining the maximal allowable amount of non-satisfaction, in terms of expected probability of failure. A stochastic policy π : + ((A) is mapping from states action distributions, and the set of all stationary policies is denoted by II. Without loss of generality, we can consider a single constraint, where C denotes the constraint satisfaction function C : S + {0, 1), (C' 1 { ailure}) similar to the task reward function, and an upper limit x. Note that since we assume only a sparse binary indicator of failure from the environment C(s), in purely online training, the agent must fail few times during training. and hence 0 failures is impossible. However, we will discuss how we can minimize the number of failures to a small rate, for constraint satisfaction.
We define discounted state distribution of policy π as d' (s) = (1 7) Er 7 P(ss, s/T), the state value function as V (s) = Ey [R(T][so = s]. the state-action value function as (s, a) = E [R[ = s, ag a). and the advantage function as A7 a) Q7 V We define similar quantities for the constraint function, as Vc, Qc and Ac. So, we have Va(H) = Er Er R(),,a,) and (²) denoting the average episodic failures, which can also be interpreted as expected probability of failure since (p) Ex [1[falurre] = P P(failurelu). For policy parameterized as Tg. we denote (s) as (s))). Note that although C' S {0, 1} takes on binary values in our setting, the function V (a) is continuous function of the policy π.
Ersx [E:-0 C(s))
Conservative Q Learning. CQL (Kumar al., 2020) is method for offline/batch RL (Lange et al., 2012; Levine et al., 2020) that aims to learn a Q-function such that the expected value of a policy under the learned Q function lower bounds its true value, preventing over-estimation due out-of- distribution actions as a result. In addition to training Q-functions via standard Bellman error, CQL minimizes the expected Q-values under a particular distribution of actions, p(als), and maximizes the expected Q-value under the on-policy distribution, π (a]s). CQL in and of itself might lead to unsafe exploration, whereas we will show in Section 3, how the theoretical tool introduced in CQL. can be used to devise safe RI. algorithm.
3 THE CONSERVATIVE
AAFE-EXPLORATION FRAMEWORK
In this section we describe our safe exploration framework. The safety constraint C(s) defined in Section 2 is an indicator of catastrophic failure: C(s) = 1 when a state s is unsafe and C(s) when it is not, and we ideally desire C(s) 0 Vs E S that the agent visits. Since we do not make any assumptions in the problem structure for RL (for example a known dynamics model), cannot guarantee this, but can at best reduce the probability of failure in every episode. So. formulate the constraint as V (p) = E,-x -h=1 C(,,)] I x, where x E [0, 1) denotes probability of failure. Our approach is motivated by the insight that by being "conservative" with respect to how
2

---

Published as a conference paper at ICLR 2021
Policy
Overestimate Qu with CQL
No
Yes
.G jeio CQk +G (COL)
Qc(s, ()
Fdute (8)
Qc(s. Se
execute
(s,
current state
env.siep(a)
Update dual A by gradient descent
Update policy & by gradient ascemt
Figure 1: CSC (Algorithm 1). enu.step(a) steps the simulator the next state s' and provides R(s, a) and C(s') values the agent. If C(s') (failure), episode terminates. Qc is the learned safety critic.
safe state is, and hence by over-estimating this probability of failure, we can effectively ensure constrained exploration.
Figure/ 1 provides overview of the approach. The key idea of our algorithm is to train servative safety critic denoted as Qc(s, a), that overestimates how unsafe a particular state is and modifies the exploration strategy appropriately account for this safety under-estimate (by overes- timating the probability of failure). During policy evaluation in the environment, we use the safety critic (c a) to reduce the chance of catastrophic failures by checking whether taking action a in state s has Qc(s, a) less than a threshold c. If not, we re-sample a from the current policy π <aass)
We now discuss our algorithm more formally. We start by discussing the procedure for learning the safety critic Qc, then discuss how we incorporate this in the policy gradient updates, and finally discuss how we perform safe exploration (Garcıa & Fernández, 2015) during policy execution in the environment.
Overall objective. Our objective learn an optimal policy x² that maximizes task rewards, while respecting the constraint on expected probability of failures.
π arg max V (H) where II = { E II: V x}
(1)
Ellle
Learning the safety critic. The safety critic Qe is used to obtain estimate of how unsafe particular state is, by providing an estimate of probability of failure, that will used to guide exploration. We desire the estimates to be "conservative", in the sense that the probability of failure should be an over-estimate while exploring. To train such a critic Qc we incorporate tools from CQL to estimate Qe through updates similar to those obtained by reversing the sign of a in Equation 2 of CQL(H) (Kumar et al., 2020). This gives denote the over-estimated advantage corresponding this safety critic Åc-
the actual probability so that the agent can err on the side of caution
upper bound on Qc instead of lower bound, ensured by CQL. We
Formally the safety critic is trained via the following objective, where the objective inside arg min called CQL(C). parameterizes Qc, and k denotes the 1hth update iteration.
Qc+ f arg min a (-BeNDens ara (ale) (ale) (Qc a)] ((..a)) (Qc(s, ()))
Qu
(aadd DewDDn (Qo(s.0)- Qt a1) 27
Here, 8 is the empirical Bellman operator discussed in section 3.1 and equation 2 of Kumar et al. (2020). a is a weight that varies the importance of the first term in equation 2, and controls the magnitude of value over-estimation, as we now highlight in red above. For states sampled from the replay buffer Denv. the first term seeks to maximize the expectation of Qc over actions sampled from the current policy, while the second term seeks to minimize the expectation of Qo over actions sampled from the replay buffer. Den. can include off-policy data, and also offline-data (if available). We interleave the gradient descent updates for training of Qc. with gradient ascent updates for policy To and gradient descent updates for Lagrange multiplier X, which we describe next.
Policy learning. Since want to learn policies that obey the constraint we set in terms of the safety critic, we can solve the objective in equation via:
max E BE-pe.a
[A as) s.t.
Es-pg S
(3)
3

---

end for Published as a conference paper at ICLR 2021
We can construct Lagrangian and solve the policy optimization problem through primal dual gra- dient descent
max min Par-pp, [A (s. a) X (Qo(s, x)]
Ty A20
We can apply vanilla policy gradients or some actor-critic style Q-function approximator for opti- mization. Here, Qe is the safety critic trained through CQL as described in equation 2. We defer specific implementation details for policy learning to the final paragraph of this section.
Algorithm CSC: safe exploration with conservative safety critics
1: Initialize V (task value fn), Q (safety critic), policy Tez X, Denus thresholds e, 6. X-
2: Set Ve (4) <-
b Ve. dold (1) denotes avg. failures in the previous epoch. b Execute actions in the environment. Collect on on-policy samples.
3: for epochs until convergence do
4: for episode in (I. M] do
5: Set <- (1 - 7x Ve a (4))
6:
Sample Taaaa (8). Execute iff (x. a) S Else, resample a.
7:
Obtain next state 8 r R(s, (llssa))c=== a= C(s').
8:
Dene f Dene U {(s,a, ((s,a,s',,) s',r, If available, Dene can be seeded with off pollcc//offlin data
9:
end for
10: Store the average episodic failures V. (1) + > Vg
11:
for step in [I...., N} do
Policy and Q function updates using Denu Gradient ascent on & and (Optionallly) add Entropy regularization (Appendix A.2)
12:
13:
Gradient updates for the Q-function Ç== Ç - V (CQT((
14:
Gradient descent step Lagrange multiplier À (Appendix A.2)
15:
end for
16:
@ntd
17:
Executing rollouts (i.e., safe exploration). Since we are interested in minimizing the number of constraint violations while exploring the environment, we do not simply execute the learned policy iterate the environment for active data collection. Rather, we query the safety critic Qc to obtain an estimate of how unsafe an action is and choose an action that is safe via rejection sampling. Formally, we sample an action a ~ Touu(() (s), and check if Qc(s, a) S
We keep ramsannling actions (s) until this condition is met, and once met, we execute that action in the environment. In practice, we execute this loop for 100 iterations, and choose the action among all actions in state for which Qc a) < and the value of Qa(s, is minimum. If no such action a is found that maintains Qc(s, a) I c, we just choose a for which Qc(s, a) is minimum (although above the threshold).
Here, is a threshold that varies across iterations and is defined as = (1 - xx Vec tutd (N))
where, V is the average episodic failures in the previous epoch, denoting a sample estimate of the true V (μ)). This value of c is theoretically obtained such that Lemma holds.
In the replay buffer Deme, we store tuples of the form (s, a, 8' .r,, c). where s is the previous state, is the action executed, s is the next state, r is the task reward from the environment, and e C(s'), the constraint value. In our setting, e is binary, with 0 denoting live agent and denoting failure.
Overall algorithm. Our overall algorithm, shown in Algorithm 1, executes policy rollouts in the environment by respecting the constraint Qc(s, a) S e, stores the observed data tuples in the replay buffer Denu. and uses the collected tuples to train a safety value function Qe using equation 2, update the policy and the dual variable À following the optimization objective equation
Implementation details. Here, we discuss the specifics of the implementation for policy optimiza- tion. We consider the surrogate policy improvement problem Sutton (2020):
A Teuid (s, a)
Pesr-posta max Ti
(4)
s.t. Esrpe [DLL (Teat (-1s) (-)))] < and (e)
Here, we have introduced a DEL constraint to ensure successive policies are close in order to help obtain bounds on the expected failures of the new policy in terms of the expected failures of the old policy in Section 4. We replace the D (Teaus (- (-))s((((ss) term by its second order Taylor expan- sion (expressed in terms of the Fisher Information Matrix F) and enforce the resulting constraint
4

---

Published as a conference paper at ICLR 2021
exactly (Schulman et al., 2015a). Following equation 22 (Appendix A.2) have, +
max PiamPora (A utd (s, a)
s.t. VC Rold (1))
1 R Raspo amay (Ac(s,a))
S
s.t. Esspoor (Toaa ( (-1s) IT (+1))] 2
(5)
We replace the true Aç by the learned over-estimated Ac, and consider the Lagrangian dual of this constrained problem, which we can solve by alternating gradient descent as shown below.
max min Bs- aamo Ne
[A
(s,a)
x
1 Ve Told (n) + 1 1- Poolo
En Poola aarty
(Ac(s [Ac(s.a))
-X
X20
; _ )ola) F(ò dold) S
s.t.
(6)
Note that although we use FIM for the updates, we can also apply vanilla policy gradients or some actor-critic style Q-function approximator optimize equation 6. Detailed derivations of the gradi- ent updates are in Appendix A.2.
4 THEORETICAL ANALYSIS
In this section, we aim theoretically analyze our approach, showing that the expected probability of failures is bounded after each policy update throughout the learning process, while ensuring that the convergence rate to the optimal solution is only mildly bottlenecked by the additional safety constraint.
Our main result, stated in Theorem 1, bounds the expected probability of failure the policy that results from Equation 5. To prove this, we first state a Lemma that shows that the constraints in Equation 5 are satisfied with high probability during the policy updates. Detailed proofs of all the Lemmas and Theorems are in Appendix A.1.
Notation. Let 6c = max, [EawTenew Ac(s, a)] and be the amount of overestimation in the expected advantage value generated from the safety eritic, Eompe arotauu [Ac a)] as per equa- tion 2, such that A Esp-po ard [Ac(s, a) Ac(s, a)}. Let Ç denote the sampling error in the estimation of Vo old (μ) by its sample estimate 1/- (n) (i.e. <= IV (μ) V otd (x)) and N be the number of samples used in the estimation of Ve. Let Rego (T) be the total cumulative failures incurred by running Algorithm I until T samples are collected from the environment. We first show that when using Algorithm 1, we can upper bound the expectation probability of failure for each policy iterate Teaia'
Lemma 1.
we follow Algorithm 1, during policy updates via Equation 5, the following is satisfied with high probability 2 21-
Ve -eaa (μ) 1- R.r-rsas -awts amo
sx+ Sx 1-
Here, Ç captures sampling error in the estimation of V (p) and we have ( S C' (oolow()/w) where C' is constant independent of w obtained from union bounds and concentration inequali- ties (Kumar al., 2020) and N is the number of samples used in the estimation of Vc-
[N]
This lemma intuitively implies that the constraint on the safety critic in equation 5 is satisfied with high probability, when we note that the RHS can be made small as N becomes large.
Lemma had bound in terms of V (μ)) for the old policy Tewas but not for the updated policy Tones We now show that the expected probability of failure for the policy T& resulting from solving equation 5, V. Tones (μ) is bounded with high probability.
Theorem 1. Consider policy updates that solve the constrained optimization problem defined in Equation 5. With high probability 2 1 - w, we have the following upper bound on expected proba- bility of failure V Veenew (1)) for Thnew during every policy update iteration:
V28yec
C' (VVoo((//)
V Vi (n) 5
where
S
(1
N
5

---

Published as a conference paper at ICLR 2021
So far we have shown that, with high probability, can satisfy the constraint in the objective during policy updates (Lemma 1) and obtain an upper bound on the expected probability of failure of the updated policy Témew (Theorem 1). The key insight from Theorem 1 is that if we execute policy To..e in the environment, the probability of failing is upper-bounded by a small number depending on the specified safety threshold X- Since the probability of failure is bounded, if we execute To...w for multiple episodes, the total number of failures is bounded as well.
We now bound the task performance in terms of policy return and show that incorporating and satís- fying safety constraints during learning does not severely affect the convergence rate to the optimal solution for task performance. Theorem 2 builds upon and relies on the assumptions in (Agarwal et al., 2019) and extends it to our constrained policy updates in equation 5.
Theorem (Convergence rate for policy gradient updates with the safety constraint). we run the policy gradient updates through equation 5, for policy Tæ, with p as the starting state distribution, with g( learning rate rj > O, and choose a as mentioned in the discussion of Theorem 1, then for all policy update iterations' T > 0 we have, with probability 2 =1- 11110 w-w,
log |A|
- 2TT + K 21=0 X
1
TT
2v20g
Vi(ln) - V (1) 5
+
where (1 + (1-7)²
T/
T/T
Since the value of the dual variables À strictly decreases during gradient descent updates (Algorithm
1), Er-1 (()) is upper-bounded So, we see that the additional term proportional to K introduced in the convergence rate (compared to (Agarwal et al., 2019)) due to the safety constraint is upper bounded, and can be made small with a high probability by choosing a appropriately. In addition, note that the safety threshold x helps tradeoff the convergence rate by modifying the magnitude of K (a low X means stricter safety threshold, and a higher value of K, implying a larger RHS and slower convergence). We discuss some practical considerations of the theoretical results in Appendix A.4.
So far we have demonstrated that the resulting policy iterates from algorithm all satisfy the desired safety constraint of the CMDP which allows for a maximum safety violation of x for every intermediate policy. While this result ensures that the probability of failures is bounded, it does not elaborate on the total failures incurred by the algorithm. In our next result, we show that the cumulative failures until a certain number of samples T of the algorithm grows sublinearly when executing Algorithm I, provided the safety threshold is set in the right way.
Theorem 3. [Number of cumulative safety failures grows sublinearly] Let x in Algorithm time- dependent such that Xt O(1/ /t). Then, the total number of cumulative safety violations until when T transition samples have been collected by Algorithm 1, Regc(T),, scales sub-linearly with T, ie., Regc(T))= O (SST)
A proof is provided in Appendix A.I. Theorem is in many ways similar to a typical regret bound for exploration (Russo, 2019; Jaksch et al., 2010), though it measures the total number of safety violations. This means that training with Algorithm will converge to a "safe" policy that incurs no failures at a quick, O(VT) rate.
5 EXPERIMENTS
Through experiments on continuous control environments of varying complexity, we aim to empir- ically evaluate the agreement between empirical performance and theoretical guidance by under- standing the following questions:
How safe is CSC in terms of constraint satisfaction during training?
How does learning of safe policies trade-off with task performance during training?
5.1 EXPERIMENTAL SETUP
Environments. In each environment, shown in Figure 2, we define a task objective that the agent must achieve and criteria for catastrophic failure. The goal is to solve the task without dying. In point agent/car navigation avoiding traps, the agent must navigate a maze while avoiding traps. The agent has a health counter that decreases every timestep that it spends within trap. When the

---

Published as a conference paper at ICLR 2021
(a) 2D nav.
(b) Car nav.
(c) Panda topple (d) Panda boundary
(e) Laikago
Figure 2: Illustrations of the five environments our experiments: (a) 2D Point agent navigation avoiding
traps. (b) Car navigation avoiding traps. (c) Panda push without toppling. (d) Panda push within boundary. (c)
Laikago walk without falling.
counter hits O, the agent gets trapped and dies. In Panda push without toppling, a 7-DoF Franka Emika Panda arm must push vertically placed block across the table to a goal location without the block toppling over. Failure defined as when the block topples. In Panda push within boundary, the Panda arm must be controlled to push block across the table block going outside a rectangular constraint region. Failure oceurs when the block center of mass ((x 3) position) move outside the constraint region. In Laikago walk without falling. an 18-DoF Laikago quadruped robot must walk without falling. The agent is rewarded for walking as fast as possible (or trotting) and failure occurs when the robot falls. Since quadruped walking is an extremely challenging task, for all the baselines, we initialize the agent's policy with a controller that has been trained to keep the agent standing, while not in motion.
goal location without the
Baselines and comparisons. We compare CSC to three prior methods: constrained policy op- timization (CPO) (Achiam et al., 2017), a standard unconstrained RL method (Schulman et al., 2015a) which we call Base (comparison with SAC (Haarnoja et al., 2018) in Appendix Figure 7), an algorithm similar to Base, called BaseShaped that modifies the reward R(s, a) as R(s, a) (C)(s) where P = 10 and C(s) is 1 when failure occurs and is 0 otherwise. We also consider a method that extends Leave No Trace (Eysenbach et al., 2017) to our setting, which we refer as Q en- sembles. This last comparison is the most similar to our approach, in that it also implements safety critic (adapted from LNT's backward critic), but instead of using our conservative updates, the safety critic uses ensemble for epistemic uncertainty estimation, as proposed by Eysenbach et al. (2017).
There other safe RL approaches which we cannot compare against, as they make multiple addi- tional assumptions, such as the availability of a function that can be queried to determine if a state is safe not Thananjeyan et al. (2020), availability of default safe policy for the task Koller et al. (2018); Berkenkamp et al. (2017), and prior knowledge of the location of unsafe states (Fisac et al., 2019). In addition to the baselines (Figure 3), analyze variants of our algorithm with different safety thresholds through ablation studies (Figure 4). We also analyze CSC and the baselines by seeding with small amount of offline data in the Appendix A.10.
5.2 EMPIRICAL RESULTS
Comparable or better performance with significantly lower failures during training. In Fig- 3, we observe that CSC has significantly lower average failures per episode, and hence lower cumulative failures during the entire training process. Although the failures are significantly lower for our method, task performance and convergence of average task rewards is comparable to or better than all prior methods, including the Base method, corresponding to an unconstrained RL algorithm. While the CPO and Q-ensembles baselines also achieve near average failures eventually, we see that CSC achieves this very early during training.
CSC trades off performance with safety constraint satisfaction, based on the safety-threshold X- In Figure 4, we plot variants of our method with different safety constraint thresholds x. Observe that: (a) when the threshold set to a lower value (stricter constraint), the number of avg. failures per episode decreases in all the environments, and (b) the convergence rate of the task reward is lower when the safety threshold stricter. These observations empirically complement our theo- retical guarantees in Theorems 1 and 2. We note that there quite a few failures even in the case where X = 0.O, which is to be expected in practice because in the initial stages of training there is high function approximation error in the learned critic Qc. However, we observe that the average episodic failures quickly drop below the specified threshold after about 500 episodes of training.
7

---

Published as a conference paper at ICLR 2021
Panda Boundary
Panda Topple
Car Navigation
Laikago
Avg. Failures Avg. Rewards
10
20
20
10
10
10
A00
1000
2000
0
1000
2000
0
1000
2000
0
10000
20000
0.5
0.5
0.3
0.3
0.2
0.2
0.0
0.0
0.0
0.0
1000
2000
0
1000
2000
1000
2000
0
10000
20000
CSC (Our method)
Q ensembles
CPO
Base
BaseShaped
Figure 3: Top row: Average task rewards (higher is better). Bottom row: Average catastrophic failures (lower better). x-axis: Number episodes (cach episode has 500 steps). Results on four the five environments we consider for our experiments. For cach environment, we plot the average task reward, the average episodic failures, and the cumulative episodic failures. The safety threshold is X 0.03 for all the basclines in all the environments. Results are four random seeds. Detailed results including plots of cumulative failures Fig. of the Appendix.
RELATED WORK
We discuss prior safe RL and safe control methods under three subheadings
Assuming prior domain knowledge of the problem structure. Prior works have attempted to solve safe exploration in the presence of structural assumptions about the environment or safety structures. For example, Koller et al. (2018); Berkenkamp et al. (2017) assume access to a safe set of environment states, and default safe policy, while in Fisac al. (2018); Dean et al. (2019), knowledge of system dynamics is assumed and (Fisac et al., 2019) assume access to a distance metric al., 2020) learns a kernel density estimate over unsafe
on the state space. SAVED (Thananjeyan states, and assumes access to a set of user demonstrations and user specified function that can be queried to determine whether a state is safe or not. In contrast these approaches, our method does not assume any prior knowledge from the user, or domain knowledge of the problem setting, except a binary signal from the environment indicating when a catastrophic failure has occurred.
Assuming continuous safety cost function. CPO (Achiam et al., 2017), and (Chow et al., 2019) assume a cost function can be queried from the environment at every time-step and the objective is to keep the cumulative costs within certain limit. This assumption limits the generality of the method in scenarios where only minimal feedback, such as binary reward feedback is provided (additional details in section A.3).
(Stooke et al., 2020) devise general modification to the Lagrangian by incorporating two additional terms in the optimization of the dual variable. SAMBA (Cowen-Rivers et al., 2020) has learned GP dynamics model and a continuous constraint cost function that encodes safety. The objective is minimize task cost function while maintaining the CVAR, of cumulative costs below a threshold. In the work of Dalal et al. (2018); Paternain et al. (2019b;a); Grbic & Risi (2020), only the optimal policy is learned to be safe, and there are no safety constraint satisfactions during training. In contrast to these approaches, we assume only a binary signal from the environment indicating when a catastrophic failure has occurred. Instead of minimizing expected costs, our constraint formulation directly seeks to constrain the expected probability of failure.
Safety through recoverability. Prior works have attempted to devise resetting mechanisms to re- cover the policy to a base configuration from (near) a potentially unsafe state. LNT (Eysenbach et al., 2017) trains both a forward policy for solving a task, and a reset goal-conditioned policy that kicks in when the agent is in an unsafe state and learns an ensemble of critics, which is substan- tially more complex than our approach a learned safety critic, which can give rise to simple but provable safe exploration algorithm. Concurrently to us. SQRL (Srinivasan et al., 2020) developed an approach also using safety critics such that during the pre- pre-traiming phase, the agent explores both safe and unsafe states in the environment for training the critic.
8

---

Published as a conference paper at ICLR 2021
Panda Boundary
Panda Topple
Car Navigation
Laikago
Failures Avg. Rewards
10
10
20
10
10
0.5
1000
2000
0.5
0
1000
2000
0.4
1000
2000
0
10000
20000
0.3
0.3
0.2
0.0
0.0
0.0
0.0
1000
2000
0
1000
2000
0
1000
2000
0
10000
20000
CSC; 0.0
CSC: 0.05
CSC; 0.1
CSC; 0.2
Figure 4: Top row: Average task rewards (higher better). Bottom row: Average catastrophic failures (lower is better). x-axis: Number of episodes (each episode has 500 steps). Results on four of the five environments we consider for our experiments. For each environment we plot the average task reward, the average episodic failures, and the cumulative episodic failures. All the plots are for our method (CSC) with different safety thresholds X, specified in the legend. From the plots is evident that our method can naturally trade-off safety for task performance depending on how striet the safety threshold is set to. Results are over four random seeds. Detailed results including plots of cumulative failures are in Fig. of the Appendix.
In control theory, a number of prior works have focused ity analysis (Bansal et al., 2017) for providing safety constraint satisfactions and obtaining control inputs for dynamical systems (Herbert et al., 2019; Bajesy et al., 2019; Leung et al., 2018). Our method does not require knowledge of the system dynamics or regularity conditions on the state- space, which are crucial for computing unsafe states using HJI reachability.
Mamiilon--acobiissiie
(HJI) reachabil-
7 DISCUSSION, LIMITATIONS, AND CONCLUSION
We introduced a safe exploration algorithm to learn a conservative safety critic that estimates the probability of failure for each candidate state-action tuple, and uses this to constrain policy evalua- tion and policy improvement. We provably demonstrated that the probability of failures is bounded throughout training and provided convergence results showing how ensuring safety does not severely bottleneck task performance. We empirically validated our theoretical results and showed that we achieve high task performance while incurring low accidents during training.
While our theoretical results demonstrated that the probability of failures is bounded with a high probability, one limitation is that we still observe non-zero failures empirically even when the thresh- old is set to O. This is primarily because of neural network function approximation error in the early stages of training the safety critic, which we cannot account for precisely in the theoretical re- sults, and also due to the fact that we bound the probability of failures, which in practice means that the number of failures also bounded, but non-zero. We also showed that if we set the constraint threshold in an appropriate vare-ng manner, training with CSC incurs cumulative failures that scales at most sub-linearly with the number of transition samples in the environment.
Although our approach bounds the probability of failure and is general in the sense that it does not assume access any user-specified constraint function, in situations where the task is difficult to solve, for example due to stability concerns of the agent, our approach will fail without additional assumptions. In such situations, some interesting future work directions would be to develop a curriculum of tasks start with simple tasks where safety is easier to achieve, and gradually move towards more difficult tasks, such that the learned knowledge from previous tasks is not forgotten.
ACKNOWLEDGEMENT
We thank Vector Institute, Toronto and the Department of Computer Science, University of Toronto for compute support. We thank Glen Berseth and Kevin Xie for helpful initial discussions about the project, Alexandra Volokhova, Arthur Allshire, Mayank Mittal, Samarth Sinha, and Irene Zhang for feedback the paper, and other members of the UofT CS Robotics Group for insightful discussions during internal presentations and reading group sessions. Finally, we are grateful to the anonymous ICLR 2021 reviewers for their feedback in helping improve the paper.

---

Published as a conference paper at ICLR 2021
REFERENCES
Joshua Achiam, David Held, Aviv Tamar, and Pieter Abbeel. Constrained policy optimization. arXiv preprint a7Oiv: 10528, 2017.
Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. Optimality and approximation with policy gradient methods in markov decision processes. arXiv preprint arXiv: 00261, 2019.
Eitan Altman. Constrained Markov decision processes, volume 7. CRC Press, 1999.
Andrea Bajesy, Somil Bansal, Eli Bronstein, Varun Tolani, and Claire Tomlin. efficient reachability-basee framework for provably safe autonomous navigation in unknown environ- ments. In 2019 IEEE 58th Conference on Decision and Control (CDC), pp. 1758-1765. IEEE, 2019.
Somil Bansal, Mo Chen, Sylvia Herbert, and Claire J Tomlin. Hamilton-jacohi reachability: brief overview and recent advances. In 2017 IEEE 56th Annual Conference on Decision and Control (CDC), pp. 2242-2253. IEEE, 2017.
Felix Berkenkamp, Matteo Turchetta, Angela Schoellig, and Andreas Krause. Safe model-based reinforcement learning with stability guarantees. In Advances in neural information processing systems, pp. 908-99 118-918,22 2017.
Yinlam Chow, Ofir Nachum, Aleksandra Faust, Edgar Duzmez-Guzman, and Mohammad Ghavamzadeh. Lyapunov-based safe policy optimization for continuous control. arXiv preprint 1rXiv:1901.10031. 2019.
Alexander Cowen-Rivers Daniel Palenicek, Vincent Moens, Mohammed Abdullah, Aivar Sootla, Jun Wang, and Haitham Ammar. Samba: Safe model-based & active reinforcement learning. arXiv preprint wxXiv:2006.09436. 2020.
Gal Dalal, Krishnamurthy Dvijotham, Matej Vecerik, Todd Hester, Cosmin Paduraru, and Yuval Tassa. Safe exploration in continuous action spaces. arXiv preprint 1.XXvv1801.0875555 2018.
Sarah Dean, Stephen Tu, Nikolai Matni, and Benjamin Recht. Safely learning to control the con- strained linear quadratic regulator. In 2019 American Control Conference (ACC), pp. 5582-5588. IEEE, 2019.
Benjamin Eysenbach, Shixiang Gu, Julian Ibarz, and Sergey Levine. Leave no trace: Learning to reset for safe and autonomous reinforcement learning. arXiv preprint arXiv:1711.06722 2017.
Jaime F Fisac, Anayo K Akametalu, Melanie N Zeilinger, Shahab Kaynama, Jeremy Gillula, and Claire Tomlin. A general safety framework for learning-based control uncertain robotic systems. IEEE Transactions Automatic Control, 64(7):2737-27522 2018.
Jaime Fisac, Neil F Lugovoy, Vicenç Lubies-Royo, Shromona Ghosh, and Claire Tomlin. Bridg- ing hamilton-jacobs safety analysis and reinforcement learning. In 2019 International Conference on Robotics and Automation (ICRA), pp. 8550-8556. IEEE, 2019.
Javier Garcia and Fernando Fernández. A comprehensive survey on safe reinforcement learning. Journal of Machine Learning Research, 16(1):1437-1480, 2015.
Djordje Grbic and Sebastian Risi. Safe reinforcement learning through meta-learned instincts. arXiv preprint arXiv:2005. 002333, 2020.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off- policy maximum entropy deep reinforcement learning with stochastic actor. arXiv preprint arXiv:1801.01299. 2018.
Sylvia L Herbert, Somil Bansal, Shromona Ghosh, and Claire J Tomlin. saachability-basee safety guarantees using efficient initializations. In 2019 IEEE 58th Conference on Decision and Control (CDC), pp. 48 4810-4816. IEFF, 2019.
10

---

Published as a conference paper at ICLR 2021
Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11).), 2010.
Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In ICML, volume 2. pp. 267-274, 2002.
Torsten Koller, Felix Berkenkamp, Matteo Turchetta, and Andreas Krause. Learning-based model predictive control for safe exploration. In 2018 IEEE Conference on Decision and Control (CDC), pp. 6059-6066. IEEE, 2018.
Aviral Kumar, Aurick Zhou, George Tucker, and Sergey Levine. Conservative q-learning for offline reinforcement learning. arXiv preprint arXiv:2006.00 047799000004779, 04779, 2020.
Sascha Lange, Thomas Gabel, and Martin Riedmiller. Batch reinforcement learning. In Reinforce- ment learning, pp. 45-73. Springer, 2012.
Karen Leung. Edward Schmerling, Mo Chen, John Talbot, J Christian Gerdes, and Marco Pavone. On infusing reachability- safety assurance within probabilistic planning frameworks for human-robot vehicle interactions. International Symposium on Experimental Robotics, pp- 561-574. Springer, 2018.
Sergey Levine. Deep reinforcement learning course, 2018. URL http://rail.eet berkeley.edu/ http://eeeeeocooooaaaaa//aaaaaaa
Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tuto- rial, review, and perspectives on open problems. arXiv preprint arXiv:2005.01643 2020.
Santiago Paternain, Miguel Calvo-Fullana, Luiz FO Chamon, and Alejandro Ribeiro. Safe policies for reinforcement learning via primal-dua methods. arXiv preprint urXiv:1911.09100 2019a.
Santiago Paternain, Luiz Chamon, Miguel Calvo-Fullana, and Alejandro Ribeiro. Constrained rein- forcement learning has zero duality gap. In Advances Neural Information Processing Systems, pp. 7555-7565, 2019b.
Xue Bin Peng, Erwin Coumans, Tingnan Zhang, Tsang- Wei Lee. Jie Tan, and Sergey Levine. Learn- ing agile robotic locomotion skills by imitating animals. arXiv preprint S4Kiv:2004.0078:5 2020.
Alex Ray, Joshua Achiam, and Dario Amodei. Benchmarking safe exploration in deep reinforcement learning. arXiv preprint 191000/000 2019.
Daniel Russo. Worst-case regret bounds for exploration via randomized value functions. In Ad- vances in Neural Information Processing Systems, pp. 14433-14443, 2019.
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference on machine learning, pp. 1889-1897, 201
John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Pieter Abbeel. High- dimensional continuous control using generalized advantage estimation. arXiv preprint 050.015500.02388. 2015b.
Krishnan Srinivasan, Benjamin Eysenbach, Sehoon Ha, Jie Tan, and Chelsea Finn. Learning to be safe: Deep rl with a safety critic. arXiv preprint arXiv:2010. 2020.
Adam Stooke, Joshua Achiam, and Pieter Abbeel. Responsive safety reinforcement learning by pid lagrangian methods. arXiv preprint arXiv:2007.03964 2020.
Rich Sutton. Reinforcement learning book, 2020. URL http::///ncommmeeeeieeee.
tbol//ELssttebbok//oddee html.
Chen Tessler, Daniel J Mankowitz, and Shie Mannor. Reward constraine policy optimization. arXiv preprint arXiv:1805.11011 2018
Brijen Thananjeyan, Ashwin Balakrishna, Ugo Rosolia, Felix Li, Rowan McAllister, Joseph E Gon- zalez, Sergey Levine, Francesco Borrelli, and Ken Goldberg. Safety augmented value estima- tion from demonstrations (saved): Safe deep model- based rl for sparse cost robotic tasks. IEEE Robotics and Automation Letters, 5(2):3612-361) 2020.

---

Published as a conference paper at ICLR 2021
Yuke Zhu, Josiah Wong, Ajay Mandlekar, and Roberto Martin-Martin robosuite: A modular simu-
lation framework and benchmark for robot learning. In arXiv preprint wxXi:2009.11293, 2020.
12

---

Published as a conference paper at ICLR 2021
A APPENDIX
A.1 PROOFS ALL THEOREMS AND LEMMAS
Note. During policy updates via Equation 5, the DKL constraint is satisfied with high probability we follow Algorithm I.
Following the steps in the Appendix A.2, we can write the gradient ascent step for e as
26
- Gold + FFFFFF1 Pata (Bold)
8 33 =
(8)
V Vosia (
FV dold J (Qooa)
F can be estimated with samples as
F Egrprsass E Bawneold
[ dota log Toala (V Oald log TT )']
(9)
Here B is the backtracking coefficient and we perform backtracking line search with exponential decay. V J is calculated as,
V Vesia (Qota) -osposa andtaaad
doota log Tosta (a) A
(10)
After every update, we check PKLlollood I 6, and if not we decay B Bi Bi,, set j t j + 1 and repeat for L steps until DKL S 8 is satisfied. If this is not satisfied after L steps, we backtrack, and do not update @ i.e. set @ &- Pold-
Lemma 1. If we we follow Algorithm 1, during policy updates via equation 5, the the following is satisfied with high probability 11
A
Ve Foold (μ) + 1-7 Earps aoway sx+
I- Here, & captures sampling error in the estimation of Ve Toaid (μ) and we have S C' is constant and N is the number of samples used in the estimation of Vc.
(oloo(1/w) [N
where
Proof. Based on line 6 of Algorithm 1, for every rollout {(s, a)}, the following holds:
Qc(s, a) s (1 - -x Ve (n])) v(s,a)
Ac(s,a) S (1 - -) - 10 a (1))) V(s.a)
Ve ((tnd())) (M) + Ac(s, a) Sx V(s,a)
(1I)
?
Ve Fodd (n)
Expposse amy [Ac(s:a)] sx
We note that we can only compute a sample estimate V-ooodd (1) instead of the true quantity Ve which can introduce sampling error in practice. In order ensure that V-Mont (1) much lesser
than V Foud (H). we can obtain a bound on their difference. Note that if VC Roold (H) 2 V v (u), the Lemma holds directly,
only need to consider the less than case.
Let T-oo (n) = Vo (n) Ç. With high probability 2 w, we can ensure < S C' (oooow(//w where C" is constant independent of (obtained from union bounds and concentration inequal- ities) and N is the number of samples used in the estimation of Vc. In addition, our estimate of Ac(s,a) is overestimate of the true Eymepo amws [Ac(s,a), and we denote
[
Ex-pe amoss
their difference by A.
So, with high probability 2 w. we have
V Roal (1) + Eg po aruTT
[Ac(s,a)] Sx
(12)
V Roald
(oold(()) (1) + Eggpe anots [Ac(s, 5x+c
1
A
13

---

Published as a conference paper at ICLR 2021
Theorem 1. Consider policy updates that solve the constrained optimization problem defined in equation S. With high probability 2 1-1u w, we have the following upper bound on expected proba- bility of failure Vo (fr Than during every policy update iteration
A
V28ycc
CVlog(I/))
Vaner (x)x
+
where
S
(13)
1-7
(1-
IN
Here, ec maxx [Bansssex (c( a)) and A is the overestimation in Es wold [Ao(s,a) due to CQL.
Proof. C(s) denotes the value of the constraint function from the environment in state This is analogous to the task reward function R(s, a). In our case C(s) is a binary indicator of whether a catastrophic failure has occurred, however the analysis we present holds even when C(s) is shaped continuous cost function.
C(s) - {o:
1 [failure)]
otherwise
Let VR (μ) denotes the discounted task rewards obtained in expectation by executing policy va for one episode, and let Vir (p) denote the corresponding constraint values.
max V (1) W
s.t.
Ve (p) S
(14)
From the TRPO (Schulman et al., 2015a) and CPO (Achiam et al., 2017) papers, following similar derivations, we obtain the following bounds
27ER ao (8, a) - Drv (Tolaaaa)
V (w) ood (1) 1-7 Es-peste amoto
(15)
Here, ARe is the advantage function corresponding to the task rewards and eR = max, BRanT ARt (8, (s) Drv is the total variation distance. We also have,
(e((u) Vo Toold ( S Es-peota arto
1
27EC A Tonld (s, a) + DDV(TTDTTTTTToto 1-7
(16)
1-7 Here, Ac Tould is the advantage function corresponding to the costs and cC max, Baann A a))- In our case, Ac is defined in terms of the safety Q function (c(s,a), and CQL can bound its expectation directly. To see this, note that, by defini- tion Exspenna Ac Alouu (s, (s.a)
Ex-eee aooTe [Qç(s,a) Here, the RHS is precisely the term in equation 2 of (Kumar et al., 2020) that is bounded by CQL. We get overstimated advantage Ac(s, a) from training the safety critic Qc through updates in equation 2. Let A denote the expected magnitude of over-estimate
Es- (Qç(s,
Ex-pens awtt AAo(saa EEmpe awos [Ac a)] + A, where A is positive. Note that replacing Ac. by its over-estimate Åc, the inequality in 16 above still holds.
Using Pinsker's inequality, we convert the bounds in terms of D instead of Drv.
Drv(pll4) S / Dxx((pl))/2
(17)
By Jensen's 's inequality,
E /VDDLL lg) /E p2)))
(18)
So, we can replace the IEDrv (pl 4)] terms in the bounds by v E[Dx becomes.
Then, inequation 16
vo (n) Vol Tolld (p) <
Egnpe Bempeay art AT (s, +
E
27cc
B Beupe aron DEL ( To [s]]
1-7
(19)
14

---

Published as a conference paper at ICLR 2021
Re Re-visiting objective in equation 5,
max E Borpo awvs [ (s, as)
8.b. Earpoase DKI DKI.(TTaa (Tori (118)][(((11)) Dar <
(20)
s.l. Ve X
From inequation 19 we note that instead of of constraining V/ (n) we can constrain an upper bound on this. Writing the constraint in terms of the current policy iterate Toata using equation 19,
max E Es-poota P anao
AR Roold
a)
T Neee
K6
s.t. Egrpears [DKL ( ((1))][T(((ss))
5
s.t. Vi (H) + 1-7 Eomporra arae
1
Agente (s. + / [DKL (Tows (+1s) TT [+(|s))]
(21)
As there is already a bound on (Tows (ms)) getting rid of the redundant term, we define the following optimization problem, which we actually optimize for
Toanw max E Perpo arao Foold (s (s.
Te
8.l. Ex-poste DxL. (T DKI (18)) S
(22)
s.t. Voru (1) + 1-9 Esuporee any A (s, s
Upper bound expected probability of failures. If Tenow is updated using equation 5, then have the following upper bound on V V.Tonew (N)
Vidnew (14) S youid (μ) 1 1-
E Exrpost aarts
[A
+ 711 Eemposty [D (Toaa))
27Cc
(23)
If we ensure V Toold (1) + B 1e have the following upper bound on Ve Tonew (1)
A (g
S x holds by following Algorithm
V20YEC 71
V Vdnew (w) sx
(24)
Here, cc = max, |E A Totd
(s, a)l-
Now, instead of Ac a), we have an over-estimated advantage estimate Ác(s, a) obtained by training the safety critic Qc through CQL as in equation 2. Let A denote the expected magnitude of over-estimate Ex Poata Ac(s, a)
Egeepsra ammgy (s, + A, where is positive.
From Lemma 1, able ensure the following with high probability 2
va Foold (μ) + 1 1-? Esmpany arots [Ac a)] S x 1-
By combining this with the upper bound on Vienew (p) from inequality 23, obtain with proba-
bility 2 1
A
V28 21
C' /lg(1//)
Ve Vinnew (x)
where 5
(25)
[N|
Since ec depends on the optimized policy To... it can't 't be calculated exactly prior to the update. As we cap Qc(s, a) be 1, therefore, the best bound we can construct for Ec: the trivial bound
ca S 2. Now, in order to have V.Twwe (p) < X. require A 2 + (1 7)ς. To guarantee 1-7
this, replacing A by the exact overestimation term from COL., we have the following condition
15

---

Published as a conference paper at ICLR 2021
a:
GeT
max Ptal
2V20 + (1 (1--))p))
Banwoota
I
1)
(26)
1 1-
|VDosia'
ge.r
Toola
Here, Ge, is constant depending on the concentration properties of the safety constraint function C(s,a) a) and the state transition operator ('s'|s a) (Kumar et al., 2020). Dota denotes the parameters
of the policy æ in the iteration before Dold- Now, with probability 1-w, have Vlog(//w) So, a is chosen as follows
[N]
207 (1 --) C² "VoR(1/w)
ge.T max 1 ?
1
Eawsoot
Toold
-1)
]
D Doss
ge,
Toood
(27)
Then with probability 2 1- w, we will have,
Vinnew (p) S
(28)
In the next theorem, we show that the convergence rate the optimal solution not severely affected due to the safety constraint satisfaction guarantee, and gets modified by addition of an extra bounded term.
Theorem 2. If we run the policy gradient updates through equation 5, for policy T with as
the starling state distribution, with (00) = 0, and learning rate >> 0, then for all policy update iterations > O we have, with probability 2 1 w.
(T) (v) Vî(n) -V
log |A|
(1 71 + (1-
1
24 (1-7)
2Ç
-t= X
TT
(1
TT
Since the value of the dual variables À strictly decreases during gradient descent updates (Algorithm 1), I-1 x() is upper-bounded.
addition, we choose a as mentioned in the discussion of 2v20g + Ç. Hence, with probability 2 - w, we can ensure that
Theorem 1, we have A >
1-7
Vū(m) 1
( z
log AAI
nf (1 (1 + K
1
T--1 -1 (
where K k (1 x)
4028
T/T
(1 (1-
Proof. Let superscript (1) denote the 1th policy update iteration. We follow the derivation in Lemma 5.2 of (Agarwal et al., 2019) but replace A(s, a) with our modified advantage estimator Á (s, a) = A (s, Ac)Ac(s, a). The quantity log (s) is defined in terms of A as
log Zs(s) log Σ ( (als) exp (n /(1 -)))
>
Σ
(" (als) log logexp nA (4) a) -7))
(29)
オ (1) (s.s)
0
We define an equivalent alternate quantity based on A()
log (.(s) log Σg (1) (als) exp (n7(0) (s, a1 (1))
log (00) (als) exp (n AA (1) (s) 1 Ac(s
Σ
π (als))ogges (n (s, (L/ 2 Σ (1) (als) log exp (n (s, a),a) - -7))
a
X 1 Σ (1) (c)s)
=0 ?
(30)
16

---

Published as a conference paper at ICLR 2021
For simplicity, consider softmax policy parameterization (equivalent results hold under the function approximation regime as shown in (Agarwal et al., 2019)), where we define the policy updates with the modified advantage function Á to take the form:
A and n (a+t) (x (xp(nn"))sss............".s.'s.p
(s. (s.
x((+1) = (0)
7 I-?
(x(8)
Here, (1))= EmEE (als) exp(nA")(s a) Note that our actual policy updates (with backtracking line search) are almost equivalent to this when is small. For the sake of notational
convenience, we will denote log (s) + y 1-y Σ. x (als)) (s, a) as Gs(s). We have G²(s) 2 0 from equation 30.
We consider the performance improvement lemma (Kakade & Langford, 2002) with respect to the task advantage function A (8, a) and express in terms of the modified advantage function A (s.a) A R (s,a) ( (c,s, a). Let μ be the starting state distribution of the MDP, and d( denote the stationary distribution of states induced by policy π in the tth iteration.
VR v((t))
(M)
E (1
n (++1) 4
1 -
E B
(141) (als) (s. 11) (
1 ?
1 sindit+1)
(al) log =(+)) (c(s)
(a(ss)
E Banditt))
x(+ (als){ (s.
y
E Ea (KL( ( + - E0td log (s)
(31)
1
E, Band(t+1) Σ (clsss) A (s)
A(0)
Exndunn log 2c(8) + I-9 ((t Σ 200 (alss) (8,
7
1
E E Gr(s)
7
Egng Gs(s)
We note that Gs(s) 2 from equation 30. We now prove result upper bounding the difference
between the optimal task value for any state distribution p and the task value at the t iteration for the same state distribution.
Sub-optimality gap. The difference between the optimal value function and the current value func- tion estimate is upper bounded.
17

---

Published as a conference paper at ICLR 2021
V (0) (p) 1-7 Bond' Σ
x (als)) + 200) Al (8)
1
Σ x (als)) log
(att)
+ 1-9 B
Bend (alass))0) (1,a)
(als)
1 Eand' ( DKL (Till
+ Σ (t|ss) log (s()
1
1
7 Band" (als)))) (s,0)
1 Eand'
- (= (DKL(T)(T!!))
+ log 21(5) + 1
1-7 ESnd' x AC (s,
1
1 -onnd
(DKL(TT](Z?)) - DKL D + Band [log 2c(s) +
1(t)
Σ
x (als) (8
"
- Eand'
1
(KL((T((T!)) - DKL (=:l|(/=)))))
1)
A(0 (9 (s.a)
Gc(s)+ + 1-7 Σ x (als))
r 10 (als)A4 (s.a)
Bond
1)
7
(32)
Using equation 31 with d' as the starting state distribution f4, we have:
Bo log Gi(s) - 1 (v(+tt(d')) - (d)
1)
which gives us a bound on Ea-a' log Gr(s).
Using the above equation and that (p) 2 (p) (as (s) 2 (s) for all states s),
we have:
V (p) V (0)
1 T
E (V (p) - -x2((())
1=0
T
T-1
1
Band (DKL(=T)] (+))) DKL (T. (T:
+
1
Σ
Bond log (s)
T
TT
1=0
(())
1(0)
Exnd'
1-7 Σ
(a(ss) (8, a)
Σ
00
(a () b) (5,a)
T
1-7
E Ex DKL (TT (T
T-1
T)- Σ
(fftt)(d)) (d' - -v(i (d))
I/T
(tt)
1
Eowd' [a((ss) (s)
-Lond (als) (s,
1
Egnd'
1-
1- 7
t=0
Eend. (KL(TT/lT
v (dt) - 1 (d*)
T-1 (0)
+2((1 +x + () A)
T/T
(1-7)T
T)T
log |A|
+ (1 (1-7)2T + +2((1-7) () A) ET-1 A
nT
(1 "TT
Here, A denotes the CQL overestimation penalty, and we have used the fact that each term of Σ.
L
E. n* (a) (s E. (c)ss as) is upper bounded by (x + 5 (1-
from Lemma so the difference is upper-bounded by 2(x + Ç -
18

---

Published as a conference paper at ICLR 2021
By choosing a as in equation 26, we have A Hence, we obtain the relation
2v282 I-q +
-1-7). So, - < 2025/
I-y - (1-7)6
We also observe that
-
(
4 [-
(1 x)
2Ç + (1 2 (TーT7)) + 2
So, we have the following result for convergence rate
Vi(()) VITT (p) log IA
2A
Σ1 A
(1 - 7) + ((1-)) (11-x)
+ +()
7/
(1 - 7)
T
Again, with probability 2 w. we can ensure 5 C' ('vloR(/w))
Overall, choosing the value of
IN
from equation 27, we have A >
2v287 (1 7).. So, A < I-y
2/20% - (1 - >)S. Hence, with
1-7
probability 2 w, we can ensure that
log [A|
ΣT- A -
Vi(u) - R
(T) (1) <
+
+ K
1,
(1 2)
1/T
where,
K $ (1 x) + 4V207
71-
So far we have demonstrated that the resulting policy iterates from our algorithm all satisfy the desired safety constraint of the CMDP which allows for a maximum safety violation of x for every intermediate policy. While this guarantee ensures that the probability of failures is bounded, it does not elaborate on the total failures incurred by the algorithm. In our next result, we show that the cumulative failures until certain number of iterations T of the algorithm grows sublinearly when executing Algorithm 1, provided the safety threshold is set in the right way.
Theorem 3. Let x in Algorithm be dime-dependent such that X OlI/V). Then, the total number of cumulative safety violations until when T transition samples have been collected by Algorithm 1, (T) scales sub-linearly with T, iee. Regc(T) = (
Proof. From Theorem with probability 2 1 w V2
C' C'V C'vlog(1) (og(1/w) 71 where s
V (n) x
(33)
[N|
Instead of using &news for ease of notation in this analysis, let us write this in terms of subscript t such that ne denotes the policy the tth iteration. We can write the bound on Ç more explicitly as,
(/w)
Egrddti aroite
Here, Ne(s, a) denotes the total number of times (s,a) is seen, (iN(s.))
and can be written as N₂ (s, a) = Ej=nn a). where (8, a) denotes total number of times (s, a) a.a N& a) denotes the total number of samples collected so far. Let is seen in episode j. T T= be the number of episodes elapsed when this happens. The safety threshold x can be varied at every iteration, such that it decreases X Vi So, we have with probability 2
A
V28ycc where S Bowd
O' Vlog(1/a)) and Xt Vt
C"
ve(()) (x) set 1 1- 7 (1-7)²
N a)
(34)
Now, we note that V denotes the expected probability of episodic failures by executing policy m (as described in section of the main paper). Let us consider that a policy is rolled out for one episode after every training iteration to collect data (exploration).
19

---

Published as a conference paper at ICLR 2021
Hence the total cumulative safety failures when T transition samples have been collected by Algo- rithm 1 is:
(T)
Σ
Ve
(p)
tml
k
A
V2decc
Σ
Xt
(()
Σ [=1
(1 7)2
t=1
C"
d (s))e((ass) (log1//w
Σ
+
Vi
t=1
1=1
s,a
C"
+ C² (Vog((1/w)
mr(s,a)
(35)
Vi
[N)
3,
S CC"Vk+ C''glt'/lo Σ (N,(s,a)
s,a
<C'VT + C² (oog(//)WVSSAAII
Σ a)(s,a)
VISVII
= =VIISIAAT
Here, we used the concavity of square root function to obtain Σ.o V Ne(s,a) V Nu(s, a) and the definition T = - (s
S
A.2 DERIVATION OF THE POLICY UPDATE EQUATIONS
Let A denote an action, S denote state, T denote a parameterized policy, r(s, a) denote reward function for the task being solved, and denote a trajectory of actions by following policy & at each state. To solve the following constrained optimization problem:
Er() s.t. ET S [failuree] =0
max TETTT
(36)
Here, is the trajectory corresponding to episode. The objective is maximize the cumulative returns while satisfying the constraint. The constraint says that the agent must never fail during every episode. 1 [failure]
if there is failure and 1 [failure) fail. The only way expectation can be 0 for this quantity is if every element is 0, so the constraint essentially is to never fail in any episode. Let's rewrite the objective, more generally as
0 if the agent does not
max V (14) s.t.
V (p) 0
(37)
Tha
We can relax the constraint slightly, by introducing tolerance parameter X 0. The objective below tolerates atmost X failures expectation. Since the agent can fail only once an episode, V- (μ4) can also be interpreted the probability of failure, and the constraint VT (μ)) S X says that the probability of failure in expectation must be bounded by X- So, our objective has a very intuitive and practical interpretation.
max
V (H) s.t. Ri
VC
(38)
We learn one state value function, VR (corresponding to the task reward), parameterized by 0 and one state-action value function Qo (corresponding to the sparse failure indicator), parameterized by Ç. We have task reward function r(s. a) from the environment which is used learn VR. For learning Qc. we get a signal from the environment indicating whether the agent is dead (1) or alive (0) i.e. 1 [failure).
20

---

Published as a conference paper at ICLR 2021
The safety critic Qe is used to get estimate of how safe particular state is, by providing an estimate of probability of failure, that will be used to guide exploration. We desire the estimates to be conservative. in the sense that the probability of failure should be over-estimate of the actual probability so that the agent can err in the side of caution while exploring. To train such a critic Qc. we incorporate theoretical insights from CQI., and estimate Qc through updates similar to those obtained by flipping the sign of a in equation 2 of the CQL paper (Kumar et al., 2020). The motivation for this is to get an upper bound on Qc instead of lower bound, as guaranteed by COL.
We also note that the CQL penalty term (the first two terms of equation 2 of the an estimate for the advantage function of the policy
CQL paper) can be expressed E Butd anvna a)). w)l.ee A(s, a) is the advantage function.
E Bend" oold a (ala) [Q(s, a)] E Band" a anmowaalas)) [Q(s,))]
E Vola amm (a (s, (ss a) (als Q(s,
(39)
E Bood votd a (a] [Q(s,) a) V(s)] = E2 gnd Bord (als) [A(s,
Hence, CQL help provide upper bound on the advantage function directly. Although the CQL class of algorithms have been proposed for batch RL, the basic bounds on the value function hold even for online training.
We denote the objective inside arg min as CQL(C), where parameterizes Qc. and & denotes the 1eth update iteration.
QCt- + arg min a
(Q a)] + (.ss.)) (Qc(s,a))
Qc
(40)
1
(Bo(s.a)-8+ QZ
2
For states sampled from the replay buffer Denu. the first term seeks to maximize the expectation of Qc over actions sampled from the current policy, while the second term seeks to minimize the expectation of Qe over actions sampled from the replay buffer. 'D Denv can include off- off-polliy data, and also offline-data (if available). Let the over-estimated advantage, corresponding to the over- estimated critic Qc. so obtained from CQL, be denoted as Ac(s, a)), where the true advantage is Ac(s, a).
Now, let (s) denote the stationary distribution states induced by policy тæ. For policy opti- mization, we have to solve constrained optimization problem described below:
max E Egrpo arro R
A A (s,
s.l. Egnpossa (Toi ( s
(41)
s.l. Ve (1)) S
This, as per equation 22 can be rewritten as
( (s.
Tenew max E
Ex-poose a awyy
s.t. Ex-pense DKL OoooToosaa (1 s 8
(42)
s.t. Ve Foold (1) + 1-7 Bomperss amao
A Foold (s, a)
Sx
Since learning over-estimate of Ac through the updates in equation 2, replace Ac by the learned Ac in the constraint above. There multiple ways solve this constrained op- timization problem, through duality. If we consider the Lagrangian dual of this, then we have the following optimization problem, which we can solve approximately by alternating gradient descent. For now, we keep the KL constraint as is, and later use its second order Taylor expansion in terms of the Fisher Information Matrix.
21

---

Published as a conference paper at ICLR 2021
1 maxmin B Boxpende ao A (s, a) - (vo (iooid (p) 1-9 xe A20
E Poota Eomponn
[Ac(s,a)
-x
s.l. Bamparrs (TT
s
(43)
We replace Vi (u) by its sample estimate Vo (p) and denote x Vigeii (n) as X'. Note that x' is independent of parameter & that is being optimized over. So, the objective becomes
ATouw (s, a) 1- Ac(s, + +
max min Pes- amat H A20
(44)
8.L. Eapepsas [PKL (ouue ( (TT (-18)]] S 6
For notational convenience let X denote the fraction T Also, in the expectation, replace T by Teaa and account for it by importance weighting of the objective.
Let us consider max,, operation and the following gradient necessary for gradient ascent of ø
(als)
arg max Powee Eawnosid
(AR (8, XAA(s,
T Told (als)
(45)
8.1. Barpostd DKI.(TT (116]| (-18)] S
Φ t arg max oass A(Dota) ( hold)
(46)
s.t. E Eemponn [DKL (Toae ( (-1s) 8
Here, using slide 20 of Lecture 9 in (Levine, 2018), and the identity VOTo = Toe V log Ts we have
To(als)
VgA(0) Eemp
Eanteold
V log (A(a)s) (A (s, X X'Ac(s, (o(ss,a))
(47)
Tobora (a|s)
Using slide 24 of Lecture in (Levine, 2018) and estimating locally at Φ = Gold
V VeatAAlooth = E Esnipeata Eawnoate
Volla log Tddia (a)s)(AA Teoi (s, a) a)) a))
(48)
We note that, Egrpeors Bantosi nal policy gradient corresponding to task rewards. So, we can write equation 48 as
V Dara log Tomie (als) as) V data sata (Pota): the origi-
V Vours ar A(dota) = Vorsa (Cota) + Es-pesta Em - X A'AA a)
(49)
In practice, we estimate A aoue through GAE (Schulman al., 2015b;a; Levine, 2018)
20
A Tols
26) D. Ar rrss,, ar) >VR(5E+1) VB(se)
(50)
Let Aoown (s.a) a) to equation 48
A Aroli (s,a)-X a) denote the modified advantage funcctin corresponding
A ( Ar r (r)),ar) >VR((=+1) -VR(ss X Ac(s),
(51)
So, rewriting equations 48 and 53 in terms of Amoola, we have
V Venle A(dota) Eerpent Eurnesse
V dola log Tosia (als)A
(52)
Vouis A(dota) = V
(53)
Substituting in equation 46, we have
arg max V taan [(Dala) (Ø Dold)
(54)
s.f. Earpons [DLL (Taus
<
As shown in slide 20 of Lecture 9 (Levine, 2018) and (Schulman et al., 2015a), we can approxi- mate DKL. in terms of the Fisher Information Matrix (this the second order term in the Taylor
22

---

Published as a conference paper at ICLR 2021
expansion of KL; note that around Pold. both the KL term and its gradient 0),
(Ki(Toond
( Dold) F F(6 Oold)
(55)
Where, F can be estimated with samples as
F Poot E Barnoord
V Volla log π Totaa (V
Ootd log TT []]
(56)
So, finally, we can write the gradient ascent step for & as (natural gradient conversion)
28
- Oold + FF J B
(57)
(oola) FF Gate (oold)
In practice, we perform backtracking line search to ensure the DKL, constraint satisfaction. So, we have the following update rule
25
- Gold + 3F-IF
V Pota (datd)
8 83
(58)
V Jonn [Qota) ( FV dotn J (Qota)
After every update, we check DKL (oll Σ 6, and if not we decay 30 fa By, y set j j +j+1 and repeat for L steps until DRL I 8 is satisfied. If this is not satisfied after L steps, backtrack, and do not update @ i.c. set Φ + Poid. For gradient descent with respect to the Lagrange multiplier Ả have (from equation 5).
1
A
- arT (Ac(s
(59)
1-7
Note that in the derivations we have ommitted E, in the outermost loop of all expectations, and subscripts (e.g. de, 8,) in order to avoid clutter in notations.
A.3 RELATION TO CPO
The CPO paper (Achiam et al., 2017) considers a very similar overall objective for policy gradient updates, with major difference. CPO approximates the Ve (n) X constraint by replacing VE (μ)) with its first order Taylor expansion and enforces the resulting simplified constraint exactly in the dual space. On the other hand, we do not make this simplification. and use primal-dual optimization to optimize an upper bound on Ve through the CQL inspired objective in equation 2. Doing this and not not making the linearity modification allows us to handle sparse (binary) failure indicators from the environment without assuming continuous safety cost function as done in CPO (Achiam et al., 2017).
A.4 PRACTICAL CONSIDERATIONS
Depending on the value of KL-constraint on successive policies 8, the RHS in Theorem 2 can either be a lower or higher rate than the corresponding problem without safety constraint. In particular, let the sampling error ( = 0, then if 8 2 (1-7)' (2=x)" the third term is negative.
872
If we set 7 0.99 and X 0.05, then for any > 1e-8, the third term in Theorem 3 will be negative. Also, if is chosen to be much greater than that in equation 26, the value of A can be arbitrarily increased in principle, and we would be overestimating the value of Qc significantly.
decrease in the upper bound of VH Vi( (n), While increasing A significantly will lead but in practice. we would no longer have a practical algorithm. This is because, when Qc is over- estimated significantly, it would be difficult to guarantce that line of Algorithm I satisfied, and policy execution will stop, resulting in infinite wall clock time for the algorithm.
In order ensure that the above does not happen, in practice we loop over line of Algorithm 1 for a maximum of 100 iterations. So, in practice the anytime safety constraint satisfaction of Theorem is violated during the early stages of training when the function approximation of Qc is incorrect. However, as we demonstrate empirically, we are able to ensure the guarantee holds during the majority of the training process.
23

---

Published as a conference paper at ICLR 2021
A.5 DETAILS ABOUT THE ENVIRONMENTS
In each environment, shown in Figure 2, we define a task objective that the agent must achieve and a criteria for calastrophic failure. The goal is to solve the task without dying. In all the environments, in addition to the task reward, the agent only receives a binary signal indicatin whether it is dead í.e. a catastrophic failure has occurred (I) or alive (0).
Point agent navigation avoiding traps. Here, a point agent with two independent actuators for turning and moving forward/backward must be controlled in a 2D plane to reach a goal (shown in green in Figure 2) while avoiding traps shown in violet circular regions. The agent has a health counter set to 25 for the episode and it decreases by 1 for every time- step that it resides in a trap. The agent is alive when the health counter positive, and catastrophic failure occurs when the counter strikes O and the agent dies.
Car agent navigation avoiding traps. Similar environment as the above but the agent is a Car with more complex dynamics. It has two independently controllable front wheels and free-rolling rear wheel. We adapt this environment from (Ray et al., 2019).
Panda push without toppling. A Franka Emika Panda arm must push vertically placed block across the table goal location without the block toppling over. The workspace di- mensions of the table are 20cmx40em and the dimensions of the block are Semx5cmx 10cm. The environment is based Robosuite Zhu et al. (2020) and we use Operational Space Control (OSC) to control the end-effevctor velocities of the robot arm. A catastrophic failure is said occur is the block topples.
Panda push within boundary. A Franka Emika Panda arm must be controlled to push block across the table to goal location without the block going outside a rectangular con- straint region. Catastrophic failure occurs when the block center of mass ((2, y) position) move outside the constraint region on the table with dimensions 15emx35em. The dimen- sions of the block are 5cmx5cmx 10cm. The environment is based Robosuite Zhu al. (2020) and we use Operational Space Control (OSC) to control the end-effector velocities of the robot arm.
Laikago walk without falling, a Laikago quadruped robot must walk without falling. The agent is rewarded for walking as fast as possible (or trotting) and failure occurs when the robot falls. Since this is an extremely challenging task, for all the baselines, the agent's s policy with a controller that has been trained to keep the agent standing, while not in motion. The environment is implemented in PyBullet and is based on (Peng al., 2020).
initialize
A.6 HYPER-PARAMERE DETAILS
We chose the learning rate 71 for the safety-critic Qe to be 2e - 4 after experimenting with 1e - and 2e- 4 and observing slightly better results with the latter. The value of discount factor 7/ is set to the usual default value 0.99, the learning rate 7)x of the dual variable is set to 4e - 2, the value of 5 for the DxL constraint policy updates is set to 0.01, and the value of to be 0.5. We experimented with three different a values 0.05, 0.5, 5 and found nearly same performance across these three values. For policy updates, the backtracking co-efficient g(0) is set to 0.7 and the max. number of line search iterations L 20. For the Q-ensembles bascline, the ensemble size is chosen to be 20 (as mentioned in the LNT paper), with the rest of the common consistent with CSC, for fair comparison results over four random seeds.
values
24

---

Published as a conference paper at ICLR 2021
A.7 COMPLETE RESULTS FOR TRADEOFF BETWEEN SAFETY AND TASK PERFORMANCE
CCC
appides Ber Sevepoont De
(a) Point 2D Nav. Rewards
(h) Point Nav. Avg. failures
(c) Point 2D Nav. Cum. failures
(d) Panda Topple Rewards
(e) Panda Topple Avg. failures
Panda Topple Cum. failures
(g) Car Rewards
(h) Car Avg. failures
(i) Car Cum. failures
(i) Panda Boundary Rewards
(k) Panda Boundary Avg. failures
(I) Panda Boundary Cum. failures
(m) Laikago Rewards
(n) Laikago Avg. failures
(0) Laikago Cum. failures
Figure 5: Results on the five environments we consider for our experiments. For cach environment we plot the average task reward, the average episodic failures, and the cumulative episodic failures. All the plots are for our method with different safety thresholds x. From the plots it is evident that our method can naturally trade-off safety for task performance depending how strict the safety threshold x is
In particular, for stricter x (i.e. lesser value), the avg. failures decreases, and the task reward plot also has a slower convergence compared to a less strict threshold.
25

---

Published as a conference paper at ICLR 2021
A.8 COMPLETE RESULTS FOR COMPARISON WITH BASELINES
sppiaees Ber Sevepoont
100
(a) Point 2D Nav. Rewards
(h) Point Nav. Avg. failures
(c) Point 2D Nav. Cum. failures
(d) Panda Topple Rewards
(e) Panda Topple Avg. failures
Panda Topple Cum. failures
conberoectttenn Each
(g) Car Rewards
(h) Car Avg. failures
(i) Car Cum. failures
Panda Boundary Rewards
(k) Panda Boundary Avg. failures
(I) Panda Boundary Cum. failures
(m) Laikago Rewards
(n) Laikago Avg. failures
(0) Laikago Cum. failures
Figure 6: Results on the five environments we consider for our experiments. For each environment we plot the average task reward, the average episodic failures, and the cumulative cpisodic failures. Since Laikago is an extremely challenging task, for all the baselines, we initialize the agent's 's policy with controller that has been trained keep the agent standing, while not in motion. The task then is to bootstrap learning that the agent to remain standing while walking as well. safety threshold x = 0.05 environments.
the baselines the
A.9 COMPARISON BETWEEN TWO UNCONSTRAINED RL ALGORITHMS
Ban SSC
(a) Point 2D Nav. Rewards
(b) Point 2D Nav. Avg. failures
(c) Point 2D Nav. Cum. failures
Figure 7: Comparison between two algorithms TRPO (Schulman et al., 2015a), SAC (Haarnoja et al., 2018) in the Point agent 2D Navigation environment. We see that TRPO has slightly faster convergence in terms of task rewards and also slightly lower average and cumulative failures, and so consider TRPO as the Base RL bascline in Figures and 4.
26

---

Published as a conference paper at ICLR 2021
A.10 SEEDING THE REPLAY BUFFER WITH VERY FEW SAMPLES
In order to investigate if we can leverage some offline user-specified data to lower the number of failures during training even further, seed the replay buffer of CSC and the baselines with 1000 tuples in the Car navigation environment. The 1000 tuples are marked as safe or unsafe depending on whether the car is inside a trap location or not in those states. our method can leverage such manually marked offline data (in small quantity as this marking procedure is not cheap), then we have a more practical method that can deployed in situations where the cost of visiting an unsafe state is significantly prohibitive. Note that this is different from the setting of offline/batch RL, where the entire training data assumed to be available offline in this experimental setting we consider very few tuples (only 1000). Figure 9 shows that our method can successfully leverage this small offline data to bootstrap the learning of the safety critic and significantly lower the average failures. We attribute this to training the safety critic conservatively through CQL, which is an effective method for handling offline data.
200
2006 13M 2000
200 230
178
201
1206 1200
2006
(a) Car Nav. Rewards
(b) Car Nav. Avg. failures
(c) Car Nav. Cum. failures
Figure 8: Results on the Car navigation environment after seeding the replay buffer with 1000 tuples. Although all the baselines improve by seeding, in terms of lower failure rates compared Figure 3, we ob- serve CSC able to particularly leverage offline seeding data and significantly lower the average and cumulative failures during training.
A.11 CAR NAVIGATION WITH TRAPS USING CONTINUOUS SAFETY SIGNAL
In this section we consider the case of a continuous safety signal to show that CSC can learn con- straints in this setting well, and minimize failures significantly The car navigation with traps provides a natural setting for this, because every time the agent enters trap region, it receive penalty (and its health counter decreases by 1), and a catastrophic failure occurs when the health counter drops to O. By training the safety critic with this continuous failure signal instead of on binary failure signals, we can capture notion of impending failure and hence aim to be more safe. Note that this setting is a strictly easier evaluation setting than what we previously considered with the binary safety signal.
compared to the baselines.
(a) Car Nav. Rewards
(b) Car Nav. Avg. failures
(c) Car Nav. Cum, failures
Figure 9: Results on the Car navigation environment using continuous safety signal.
27


Reviews:
[{"review_id": "uabc92i34mH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper introduces a method for performing safe exploration in RL. It addresses the problem of ensuring that partially-trained policies do not visit unsafe regions of the state space, while still being exploratory enough to collect useful training experiences. The proposed technique is based on learning conservative estimates of the probability of a catastrophic failure occurring at different states. Based on these, the authors show that it is possible to upper bound the likelihood of reaching an unsafe state at every training step, thereby guaranteeing that all safety constraints are satisfied with high probability. Importantly, the authors also show that (at least asymptotically), the method is no worse than standard unsafe reinforcement learning algorithms.\n\nOverall, this is a well-written paper with sound mathematical arguments. The authors present a thorough review of related work, such as constrained MDPs, and argue that the proposed method requires fewer assumptions. For example, the proposed technique assumes access only to a sparse (binary) indicator of whether entering a particular state would result in catastrophic failure. The authors formally show that it is possible to upper bound the expected probability of failure during every policy update iteration (Thm1), which is a non-trivial result. All update equations are carefully derived and discussed in the appendix. The experiments are well-designed and convincing, and include evaluations of the proposed method (CSC) in 4 different domains, including an 18-DoF quadruped robot.\n\nI believe that this paper introduces an important contribution to the RL community that is concerned with safety. It presents a principled method and introduces non-trivial bounds. In my opinion, this conference's community would benefit from having this paper accepted to its proceedings.\n\n\nI have just a few questions for the authors:\n\n1) safe exploration in RL is often expressed in terms of ensuring that, after every policy update, the new policy is no worse than the current one (or is worse by a bounded amount). In your paper, by contrast, safe exploration is related to the ability to avoid particular states. Can any of the bounds derived in this paper be used to ensure the former type of safety?\n\n2) during policy evaluation, the proposed algorithm uses the safety critic, Q_C(s,.), to estimate how unsafe a particular state is. If an action sampled by the policy is deemed unsafe, the algorithm repeatedly re-samples new actions. Is this type of rejection sampling guaranteed to always stop? What happens if all actions available in s are unsafe? What if safe actions do exist but have zero probability under the current policy? Could the algorithm get stuck and stop exploring?\n\n3) in Eq2, what is \\hat{Beta}^pi?\n\n4) the bound presented in Theorem 2 depends on an additional term K, which (so you argue) can be made small by picking alpha appropriately. How do you pick alpha, in practice, so that the algorithm trades-off convergence rate and safety?\n\n5) when deriving the upper bound on V_C^pi_new (Eq26), you point out the epsilon_C cannot be computed exactly before the update, since it depends on the new optimized policy pi_new. How loose does the upper bound on V get by placing a trivial upper bound epsilon_C (epsilon_C <= 2)? Also, given that policy updates are constrained to keep the stationary distribution of successive policies similar, could this be exploited to achieve a tighter bound on epsilon_C?\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "rsCLmqtC4cm", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "(some difficulty following all of the proofs lowered the confidence of my evaluation)\n\n## Summary\nThe authors lay out a new technique for safety-constrained exploration which reduces the likelihood of catastrophic failure. This is shown via extensive proofs providing theoretical guarantees on both convergence and the likelihood of failure as well as experimental results in a number of compelling tasks.\n\n## Quality & Clarity\nThe authors provide regular and clear comparisons of their approach to related techniques described in other works. They provide extensive proofs and experimental results justifying their technique’s advantages.\n\n## Originality & Significance\nThe work provides original techniques with both theoretical and empirical improvements over previous techniques.\n\n## Suggestions\nIn the experimental section, the positive reward is clear but what is missing is how receiving negative reward for failure might compare to this approach. A natural comparison against methods that do not utilize the safety constraint features is to include a very large negative reward for failure and see if the algorithms can avoid failure via this signal instead of the separate safety signal. The authors emphasize the value of only accessing a binary signal to signify safety from the environment, so this could easily be considered a slight modification of the baseline algorithms: they induce a large negative intrinsic reward when they receive a failure signal. The trap experiment provides an especially clear setting for negative rewards: the agents could receive a lesser negative reward each time they lose a health counter before reaching catastrophic failure.\n\nDuring policy evaluation, you resample actions when the likelihood of failure for a given action exceeds a certain threshold. I wonder how alternative approaches might perform, such as using the failure likelihood instead as a probability (perhaps scaled) of resampling; reweighting the action probabilities based on the failure likelihoods (maybe another action had a nearly identical expected return but a much lower chance of failure); or even utilizing the failure likelihood as an input to the policy (maybe in some scenarios the model stays as far away as possible from any risk but in others might choose to take a dangerous route that could lead to high reward). These alternatives also provide an answer to “what do you do when every action from a given state is above the threshold?” which is not specified in Section 3’s “Executing rollouts (i.e., safe exploration)” subsection nor in Algorithm 1.\n\nAlternative approaches to the sampling procedure could potentially improve the tradeoff between safety and convergence. Where other methods might waste time exploring dangerous parts of the space, your method might be able to focus more time on the healthier parts of the states and converge to an effective policy sooner. At least, this may be true after the initial period of learning an accurate safety classifier, which as you point out takes some time for the agent to figure out. An experiment that could add to the paper would be to pretrain a safety estimator and then restart training with a newly initialized policy--how does this affect the convergence with different thresholds?\n\nFinally, I would be interested to see how this work could be extended with non-binary safety constraints. The trap task provides a clear example of incremental danger (the agent is being “injured” before being finally destroyed) and being able to effectively utilize earlier hints signalling impending catastrophic failure would be a valuable skill.", "extra_scores": {}, "extra_text": {}}, {"review_id": "7DFZHSfcklP", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper would like to address the problem of ``\"safe exploration\" with a conservative estimation of the environment. Although the problem seems reasonable, I have the following several concerns on this paper:\n\n- Will the safety constraints be revealed to the agent? Standard RL assumes the reward is not revealed to the agent, and I feel the safety constraints cannot be revealed to the agent in prior as well.\n\n- If the safety constraints is not revealed to the agent, then how to train the safety critic? In my opinion, when the agent collect the data that fail catastrophically, then the exploration is already not safe.\n\n- I feel the derivation part in Section 3 is not so clear, as several notations have been introduced without explanation, though it is not hard to understand.\n\n- I don’t understand what Lemma 1 and Theorem 1 can indicate in practice. When we estimate V_C, we already satisfies several catastrophic failures, otherwise we will know nothing about the possible failure. This can also be seen from the traditional exploration analysis. And traditional exploration analysis also says when we have sufficient number of data, the probability that we suffer from catastrophic failure will decrease. In one word, I don’t see any significant idea of ``safe exploration’’ from Lemma 1 and Theorem 1.\n\n- Also, from the traditional exploration analysis, we have the regret lower bound, which says we must suffer from failure to get the best policy. We also have algorithms to match these regret lower bound on some simplified MDP settings, and even stronger guarantee that with high probability we will make small mistake when we have sufficient samples (see the mistake version of IPOC bound in [1]). I don’t feel the current paper present such kinds of guarantee.\n\nA summarize of point 4 & 5: to me I don’t feel the authors well-defined the `''safe exploration''  and give a rigorous analysis on the ``the safety guarantee. For me, I prefer to define the \"safe exploration\" as minimizing the total failure when finding the optimal policy, but no matter how to define it,  I feel what the authors have done is not \"safe\".\n\nI feel Theorem 2 is a straightforward adaption of the existing results in [2]. Though seems correct, the authors argue that Theorem 2 shows a tradeoff between safety and convergence, which I cannot agree. If we want the policy to converge to the global optimum, then we need to collect samples from the dangerous region (otherwise we cannot know if that’s dangerous and probably we can get some improvement at that region), how to keep \"safe\" at that time? Also, a slow convergence will need to run for a longer time and thus need more samples, which can enlarge the probability of catastrophic failure, right? \n\nOverall, though the empirical performance on some benchmark shows the proposed method is better than some of the previous methods, I don’t think the proposed methods really address the issue of the safe exploration. The authors does not formally define what is the safe exploration (and even little about exploration in fact), and the theoretical analysis also doesn’t address any of the safety issues. From my point of view, to achieve good performance, one must suffer from some failures, and our goal should be minimizing the number of failures, rather than minimizing the failure probability of each turn. Unfortunately, the authors does not characterize all of these issues I care about. I would like to say, considering the unsatisfactory of the problem description and theoretical analysis, I don’t think this paper is suitable for publication.\n\n[1] Dann, Christoph, et al. \"Policy certificates: Towards accountable reinforcement learning.\" International Conference on Machine Learning. PMLR, 2019.\n\n[2] Agarwal, Alekh, et al. \"Optimality and approximation with policy gradient methods in markov decision processes.\" arXiv preprint arXiv:1908.00261 (2019).\n\n------------------\nThe authors answers one of the most important concerns, I have raised score to 6.", "extra_scores": {}, "extra_text": {}}, {"review_id": "1BvX86TvZ0", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this submission the authors are trying to tackle the very important problem of safe RL with safety guarantees. The problem formulation is rather clear, and the paper is overall well written. The main idea is to formulate the safe RL problem as  a CMDP problem, but with worst-case bounds to ensure that the safety constrained is guaranteed throughout the learning.\n\nThe general idea is fine, albeit not new (please check/compare against recent works on robust-CMDPs), however, I do have several issues with the lack of rigor in the mathematical proofs, as well as the rather amplified statements about safety guarantees 'throughout learning'.\n\nIndeed, the CMDP problem (or its worst-case bound) is solved using a Lagrangian formulation, which is well-know as a soft constraints formulation, i.e., you do not have guaranteed safety during learning, as claimed in the Introduction (paragraph 3), and throughout the paper. In that case, the dramatic drone motivational example used in the Introduction (paragraph 1) is and exaggeration, i.e., this method will lead to a crash too.\n\nBesides, mathematically, many of your variables are not defined, not even in the appendix, e.g., in equation (2) $\\hat{B}$ is not defined; $\\alpha$ which seems a key tuning parameter in Theorem 1 is not defined, etc.\n\nMost importantly, the authors keep referring to the paper about CPO (Achiam et al 17) to support their proofs and technical derivations, whereas that paper is about continuous constraints costs. This paper on the other hand, is clearly using discontinuous constraints, not even $C^{0}$, and thus one cannot just use parts of the results in (Achiam et al 17) without further carful examination of the technical challenges introduced with a discontinuous cost function, e.g., you are using some Taylor developments throughout, while these only make sense for analytic functions, etc.\n\nFurthermore, the probability bounds proposed in Theorem 1 and 2 seem to be rater weak bounds, since $\\xi$ is bounded by a term inversely proportional to the confidence parameter $\\omega$, which means the probability of being safe is high when the safety bound is loose, i.e., $\\chi+\\xi$, for $\\xi\\rightarrow +\\infty$ . Similarly, for tight safety bound, i.e., $\\chi+\\xi$, for $\\xi\\rightarrow 0$, the safety probability drops to zero. The authors seem to minimize this point by the 'proper tuning' of $\\alpha$ which remains a mysterious parameter (even after checking the proofs in Appendix).\n\nThis is all to say that the authors have to tone down their statements about guaranteed provable safety bound, quite a bit.\n\nFinally, the numerical simulations are interesting, but only confirm my point about the fact that the obtained safety is asymptotic only, i.e., in steady state, and absolutely not during learning. This is clear from the plots in Figure 3 (bottom) where we see that in average the proposed algorithm necessitates more than 1000 iteration before reaching a truly safe behavior. One can also note that the CPO algorithm behaves almost similarly to the proposed algorithm, when tested on the car navigation example, and the laikago robot (Fig. 3, bottom number 3 and 4). One also wonders why in the first set of tests, in Fig. 3- top number 2, one can reach a performance cost of 20 with the proposed method, while it seems to plato at 10 in the second set of experiments, in Fig. 4-top number 2. Another point that is worth clarifying is that the tests in Fig. 4-top number 1, we see that the performance cost reaches 10 for the proposed method with large safety constraint bound (0.2), which is intuitively an almost unconstrained case. However, the unconstrained algorithm 'Base' in the first tests, Fig. 3-top number 1, the Base algorithm does not achieve a similar performance, could it be better tuned in that case ?\n\nIn summary, I found the paper well written, but it needs to be carefully revised for technical rigor, and toned down in terms of what is really achieved here (maybe somehow safer CMDP algorithm but definitely not safe during exploration).", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Summary: 
This paper introduces a different, interesting definition of safety in RL. The paper does a nice job of showing success with empirical results and providing bounds. I think it provides a nice contribution to the field.

Discussion:
The reviewers agree this paper should be accepted. The initial points brought up against the paper have been successfully addressed or mitigated. 
Decision: Accept (Poster)