Learning Barrier Certificates: Towards Safe Reinforcement Learning with Zero Training-time Violations
Year: 2022

Abstract:
Training-time safety violations have been a major concern when we deploy reinforcement learning algorithms in the real world. This paper explores the possibility of safe RL algorithms with zero training-time safety violations in the challenging setting where we are only given a safe but trivial-reward initial policy without any prior knowledge of the dynamics and additional offline data. We propose an algorithm, Co-trained Barrier Certificate for Safe RL (CRABS),which iteratively learns barrier certificates, dynamics models, and policies. The barrier certificates are learned via adversarial training and ensure the policy’s safety assuming calibrated learned dynamics. We also add a regularization term to encourage larger certified regions to enable better exploration. Empirical simulations show that zero safety violations are already challenging for a suite of simple environments with only 2-4 dimensional state space, especially if high-reward policies have to visit regions near the safety boundary. Prior methods require hundreds of violations to achieve decent rewards on these tasks, whereas our proposed algorithms incur zero violations.

heading: 1 Introduction
text: Researchers have demonstrated that reinforcement learning (RL) can solve complex tasks such as Atari games [Mnih et al., 2015], Go [Silver et al., 2017], dexterous manipulation tasks [Akkaya et al., 2019], and many more robotics tasks in simulated environments [Haarnoja et al., 2018]. However, deploying RL algorithms to real-world problems still faces the hurdle that they require many unsafe environment interactions. For example, a robot’s unsafe environment interactions include falling and hitting other objects, which incur physical damage costly to repair. Many recent deep RL works reduce the number of environment interactions significantly (e.g., see Haarnoja et al. [2018], Fujimoto et al. [2018], Janner et al. [2019], Dong et al. [2020], Luo et al. [2019], Chua et al. [2018] and reference therein), but the number of unsafe interactions is still prohibitive for safety-critical applications such as robotics, medicine, or autonomous vehicles [Berkenkamp et al., 2017].
Reducing the number of safety violations may not be sufficient for these safety-critical applications— we may have to eliminate them. This paper explores the possibility of safe RL algorithms with zero safety violations in both training time and test time. We also consider the challenging setting where we are only given a safe but trivial-reward initial policy.
A recent line of works on safe RL design novel actor-critic based algorithms under the constrained policy optimization formulation [Thananjeyan et al., 2021, Srinivasan et al., 2020, Bharadhwaj et al., 2020, Yang et al., 2020, Stooke et al., 2020]. They significantly reduce the number of training-time safety violations. However, these algorithms fundamentally learn the safety constraints by contrasting the safe and unsafe trajectories. In other words, because the safety set is only specified through the
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
safety costs that are observed postmortem, the algorithms only learn the concept of safety through seeing unsafe trajectories. Therefore, these algorithms cannot achieve zero training-time violations. For example, even for the simple 2D inverted pendulum environment, these methods still require at least 80 unsafe trajectories (see Figure 2 in Section 6).
Another line of work utilizes ideas from control theory and model-based approach [Cheng et al., 2019, Berkenkamp et al., 2017, Taylor et al., 2019, Zeng et al., 2020]. These works propose sufficient conditions involving certain Lyapunov functions or control barrier functions that can certify the safety of a subset of states or policies [Cheng et al., 2019]. These conditions assume access to calibrated dynamical models. They can, in principle, permit safety guarantees without visiting any unsafe states because, with the calibrated dynamics, we can foresee future danger. However, control barrier functions are often non-trivially handcrafted with prior knowledge of the environments [Ames et al., 2019, Nguyen and Sreenath, 2016].
This work aims to design model-based safe RL algorithms that achieve zero training-time safety violations by learning the barrier certificates iteratively. We present the algorithm Co-trained Barrier Certificate for Safe RL (CRABS), which alternates between learning barrier certificates that certify the safety of larger regions of states, optimizing the policy, collecting more data within the certified states, and refining the learned dynamics with data.
The work of Richards et al. [2018] is a closely related prior result, which learns a Lyapunov function given a fixed dynamics model via discretization of the state space. Our work significantly extends it with three algorithmic innovations. First, we use adversarial training to learn the certificates, which avoids discretizing state space and can potentially work with higher dimensional state space than the two-dimensional problems in Richards et al. [2018]. Second, we do not assume a given, globally accurate dynamics; instead, we learn the dynamics from safe explorations. We achieve this by co-learning the certificates, dynamics, and policy to iteratively grow the certified region and improve the dynamics and still maintain zero violations. Thirdly, the work Richards et al. [2018] only certifies the safety of some states and does not involve learning a policy. In contrast, our work learns a policy and tailors the certificates to the learned policies. In particular, our certificates aim to certify only states near the trajectories of the current and past policies—this allows us to not waste the expressive power of the certificate parameterization on irrelevant low-reward states.
We evaluate our algorithms on a suite of tasks, including a few where achieving high rewards requires careful exploration near the safety boundary. For example, in the Swing environment, the goal is to swing a rod with the largest possible angle under the safety constraints that the angle is less than 90◦. We show that our method reduces the number of safety violations from several hundred to zero on these tasks.

heading: 2 Setup and Preliminaries

heading: 2.1 Problem Setup
text: We consider the standard RL setup with an infinite-horizon deterministic Markov decision process (MDP). An MDP is specified by a tuple (S,A, γ, r, µ, T ), where S is the state space, A is the action space, r : S ×A → R is the reward function, 0 ≤ γ < 1 is the discount factor, µ is the distribution of the initial state, and T : S ×A → S is the deterministic dynamics model. Let ∆(X ) denote the family of distributions over a set X . The expected discounted total reward of a policy π : S → ∆(A) is defined as
J(π) = E [ ∞∑ i=0 γir(si, ai) ] ,
where s0 ∼ µ, ai ∼ π(si), si+1 = T (si, ai) for i ≥ 0. The goal is to find a policy π which maximizes J(π).
Let Sunsafe ⊂ S be the set of unsafe states specified by the user. The user-specified safe set Ssafe is defined as S\Sunsafe. A state s is (user-specified) safe if s ∈ Ssafe. A trajectory is safe if and only if all the states in the trajectory are safe. An initial state drawn from µ is assumed to safe with probability 1. We say a deterministic policy π is safe starting from state s, if the infinite-horizon trajectory obtained by executing π starting from s is safe. We also say a policy π is safe if it is safe starting from an initial state drawn from µ with probability 1. A major challenge toward safe RL is the existence of
irrecoverable states which are currently safe but will eventually lead to unsafe states regardless of future actions. We define the notion formally as follows.
Definition 1. A state s is viable iff there exists a policy π such that π is safe starting from s, that is, executing π starting from s for infinite steps never leads to an unsafe state. A user-specified safe state that is not viable is called an irrecoverable state.
We remark that unlike Srinivasan et al. [2020], Roderick et al. [2020], we do not assume all safe states are viable. We rely on the extrapolation and calibration of the dynamics to foresee risks. A calibrated dynamics model T̂ predicts a confidence region of states T̂ (s, a) ⊆ S, such that for any state s and action a, we have T (s, a) ∈ T̂ (s, a).

heading: 2.2 Preliminaries on Barrier Certificate
text: Barrier certificates are powerful tools to certify the stability of a dynamical system. Barrier certificates are often applied to a continuous-time dynamical system, but here we describe its discrete-time version where our work is based upon. We refer the readers to Prajna and Jadbabaie [2004], Prajna and Rantzer [2005] for more information about continuous-time barrier certificates.
Given a discrete-time dynamical system st+1 = f(st) without control starting from s0, a function h : S → R is a barrier certifcate if for any s ∈ S such that h(s) ≥ 0, h(f(s)) ≥ 0. Zeng et al. [2020] considers a more restrictive requirement: For any state s ∈ S , h(f(s)) ≥ αh(s) for a constant 0 ≤ α < 1. it is easy to use a barrier certificate h to show the stability of the dynamical system. Let Ch = {s : h(s) ≥ 0} be the superlevel set of h. The requirement of barrier certificates directly translates to the requirement that if s ∈ Ch, then f(s) ∈ Ch. This property of Ch, which is known as the forward-invariant property, is especially useful in safety-critical settings: suppose a barrier certificate h such that Ch does not contain unsafe states and contains the initial state s0, then it is guaranteed that Ch contains the entire trajectory of states {st}t≥0 which are safe. Finding barrier certificates requires a known dynamics f , which often can only be approximated in practice. This issue can be resolved by using a well-calibrated dynamics model f̂ , which predicts a confidence interval containing the true output. When a calibrated dynamics model f̂ is used, we require that for any s ∈ S, mins′∈f̂(s) h(s ′) ≥ 0.
Control barrier functions [Ames et al., 2019] are extensions to barrier certificates in the control setting. That is, control barrier functions are often used to find an action to meet the safety requirement instead of certifying the stability of a closed dynamical system. In this work, we simply use barrier certificates because in Section 3, we view the policy and the calibrated dynamics model as a whole closed dynamical system whose stability we are going to certify.

heading: 3 Learning Barrier Certificates via Adversarial Training
text: This section describes an algorithm that learns a barrier certificate for a fixed policy π under a calibrated dynamics model T̂ . Concretely, to certify a policy π is safe, we aim to learn a (discretetime) barrier certificate h that satisfies the following three requirements.
R.1. For s0 ∼ µ, h(s0) ≥ 0 with probability 1. R.2. For every s ∈ Sunsafe, h(s) < 0. R.3. For any s such that h(s) ≥ 0, mins′∈T̂ (s,π(s)) h(s) ≥ 0.
Requirement R.1 and R.3 guarantee that the policy π will never leave the set Ch = {s ∈ S : h(s) ≥ 0} by simple induction. Moreover, R.2 guarantees that Ch only contains safe states and therefore the policy never visits unsafe states.
In the rest of the section, we aim to design and train such a barrier certificate h = hφ parametrized by neural network φ.
hφ parametrization. The three requirements for a barrier certificate are challenging to simultaneously enforce with constrained optimization involving neural network parameterization. Instead, we will parametrize hφ with R.1 and R.2 built-in such that for any φ, hφ always satisfies R.1 and R.2.
We assume the initial state s0 is deterministic (the parameterization can be extended to multiple initial states.) To capture the known user-specified safety set, we first handcraft a continuous function Bsafe : S → R≥0 satisfying Bsafe(s) ≈ 0 for typical s ∈ Ssafe and Bsafe(s) > 1 for any s ∈ Sunsafe.1 The construction of Bsafe does not need prior knowledge of irrecoverable states, but only the userspecified safety set Ssafe. To further encode the user-specified safety set into hφ, we choose hφ to be of form hφ(s) = 1 − Softplus(fφ(s) − fφ(s0)) − Bsafe(s), where fφ is a neural network, and Softplus(x) = log(1 + ex).
Because s0 is safe and Bsafe(s0) ≈ 0, hφ(s0) ≈ 1 − Softplus(0) > 0. Therefore hh satisfies R.1. Moreover, for any s ∈ Sunsafe, we have hφ(s) < 1 − Bsafe(s) < 0, so hφ in our parametrization satisfies R.2 by design.
Training barrier certificates. We now move on to training φ to satisfy R.3. Let
U(s, a, h) := max s′∈T̂ (s,a)
−h(s′). (1)
Then, R.3 requires U(s, π(s), hφ) ≤ 0 for any s ∈ Chφ , The constraint in R.3 naturally leads up to formulate the problem as a min-max problem. Define our objective function to be
C∗(hφ, U, π) := max s∈Chφ U(s, π(s), hφ) = max s∈Chφ ,s ′∈T̂ (s,π(s)) −h(s′) , (2)
and we want to minimize C∗ w.r.t. φ:
min φ C∗(hφ, U, π) = min φ max
s∈Chφ ,s ′∈T̂ (s,π(s))
−h(s′), (3)
Our goal is to ensure the minimum value is less than 0. We use gradient descent to solve the optimization problem. We also derive the gradient of C∗(Lφ, U, π) w.r.t. φ :
∇φC∗(hφ, U, π) = ∇φU(s∗, π(s∗), hφ) + ‖∇φU(s∗, π(s∗), hφ)‖2 ‖∇φhφ(s∗)‖2 ∇φhφ(s∗), (4)
where s∗ := arg maxs:hφ(s)≤1 U(s, π(s), hφ) and we defer the derivation to Appendix A. Computing the adversarial s∗.
Equation (4) requires us to compute s∗ efficiently. Because the maximization problem with respect to s is nonconcave, there could be multiple local maxima. In practice, we find that it is more efficient and reliable to use multiple local maxima to compute∇φC∗ and then average the gradient. Solving s∗ is highly non-trivial, as it is a non-concave optimization problem with a constraint s ∈ Chφ . To deal with the constraint, we introduce a Lagrangian multiplier λ and optimize U(s, π(s), hφ)− λIs∈Chφ w.r.t. s without any constraints. However, it is still very time-consuming to solve an optimization problem independently at each time. Based on the observation that the parameters of h do not change too much by one step of gradient step, we can use the optimal solution from the last optimization problem as the initial solution for the next one, which naturally leads to the idea of maintaining a set of candidates of s∗’s during the computation of∇φC∗. We use Metropolis-adjusted Langevin algorithm (MALA) to maintain a set of candidates {s1, . . . , sm} which are supposed to sample from exp(τ(U(s, π(s), hφ) − λIs∈Chφ )). Here τ is the temperature indicating we want to focus on the samples with large U(s, π(s), hφ). Although the indicator function always have zero gradient, it is still useful in the sense that MALA will reject si 6∈ Chφ . A detailed description of MALA is given in Appendix D. We choose MALA over gradient descent because the maintained candidates are more diverse, approximate local maxima. If we use gradient descent to find s∗, then multiple runs of GD likely arrive at the same s∗, so that we lost the parallelism from simultaneously working with multiple
1The function Bsafe(s) is called a barrier function for the user-specified safe set in the optimization literature. Here we do not use this term to avoid confusion with the barrier certificate.
Algorithm 1 Learning barrier certificate hφ for a policy π w.r.t. a calibrated dynamics model T̂ . Require: Temperature τ , Lagrangian multiplier λ, and optionally a regularization function Reg.
1: Let U be defined as in Equation (1). 2: Initialize m candidates of s1, . . . , sm ∈ S randomly. 3: for n iterations do 4: for every candidate si do 5: sample si ∼ exp(τU(s, π(s), hφ)− λIs∈Ch) by MALA (Algorithm 5). 6: W ← {si : hφ(si) ≥ 0, i ∈ [m]}. 7: Train φ to minimize C∗(hφ, U, π) + Reg(φ) using all candidates in W .
Algorithm 2 CRABS: Co-trained Barrier Certificate for Safe RL (Details in Section 4) Require: An initial safe policy πinit.
1: Collected trajectories buffer D̂ ← ∅; π ← πinit. 2: for T epochs do 3: Invoke Algorithm 3 to safely collect trajectories (using π as the safeguard policy and a noisy
version of π as the πexpl). Add the trajectories to D̂. 4: Learn a calibrated dynamics T̂ with D̂. 5: Learn a barrier certificate h that certifies π w.r.t. T̂ using Algorithm 1 with regularization. 6: Optimize policy π (according to the reward), using data in D̂, with the constraint that π is
certified by h.
local maxima. MALA avoids this issue by its intrinsic stochasticity, which can also be controlled by adjusting the hyperparameter τ .
We summarize our algorithm of training barrier certificates in Algorithm 1 (which contains optional regularization that will be discussed in Section 4.2). At Line 2, the initialization of si’s is arbitrary, as long as they have a sort of stochasticity.

heading: 4 CRABS: Co-trained Barrier Certificate for Safe RL
text: In this section, we present our main algorithm, Co-trained Barrier Certificate for Safe RL (CRABS), shown in Algorithm 2, to iteratively co-train barrier certificates, policy and dynamics, using the algorithm in Section 3. In addition to parametrizing h by φ, we further parametrize the policy π by θ, and parametrize calibrated dynamics model T̂ by ω. CRABS alternates between training a barrier certificate that certifies the policy πθ w.r.t. a calibrated dynamics model T̂ω (Line 5), collecting data safely using the certified policy (Line 3, details in Section 4.1), learning a calibrated dynamics model (Line 4, details in Section 4.3), and training a policy with the constraint of staying in the superlevel set of the barrier function (Line 6, details in Section 4.4). In the following subsections, we discuss how we implement each line in detail.

heading: 4.1 Safe Exploration with Certified Safeguard Policy
text: Safe exploration is challenging because it is difficult to detect irrecoverable states. The barrier certificate is designed to address this — a policy π certified by some h guarantees to stay within Ch and therefore can be used for collecting data. However, we may need more diversity in the collected data beyond what can be offered by the deterministic certified policy πsafeguard. Thanks to the contraction property R.3, we in fact know that any exploration policy πexpl within the superlevel set Ch can be made safe with πsafeguard being a safeguard policy—we can first try actions from πexpl and see if they stay within the viable subset Ch, and if none does, invoke the safeguard policy πsafeguard. Algorithm 3 describes formally this simple procedure that makes any exploration policy πexpl safe. By a simple induction, one can see that the policy defined in Algorithm 3 maintains that all the visited states lie in Ch. The safeguard policy πsafeguard is supposed to safeguard the exploration. However, activating the safeguard too often is undesirable, as it only collects data from πsafeguard so there will be little
Algorithm 3 Safe exploration with safeguard policy πsafeguard
Require: (1) A policy πsafeguard certified by barrier certificate h, (2) any proposal exploration policy πexpl. Require: A state s ∈ Chφ . 1: Sample n actions a1, . . . an from πexpl(s). 2: if there exists an ai such that U(s, ai, h) ≤ 1 then 3: return: ai 4: else 5: return: πsafeguard(s).
exploration. To mitigate this issue, we often choose πexpl to be a noisy version of πsafeguard so that πexpl will be roughly safe by itself. Moreover, the safeguard policy πsafeguard will be trained via optimizing the reward function as shown in the next subsections. Therefore, a noisy version of πsafeguard will explore the high-reward region and avoid unnecessary exploration.
Following Haarnoja et al. [2018], the policy πθ is parametrized as tanh(µθ(s)), and the proposal exploration policy πexplθ is parametrized as tanh(µθ(s) + σθ(s)ζ) for ζ ∼ N (0, I), where µθ and σθ are two neural networks. Here the tanh is applied to squash the outputs to the action set [−1, 1].

heading: 4.2 Regularizing Barrrier Certificates
text: The quality of exploration is directly related to the quality of policy optimization. In our case, the exploration is only within the learned viable set Chφ and it will be hindered if Chφ is too small or does not grow during training. To ensure a large and growing viable subset Chφ , we encourage the volume of Chφ to be large by adding a regularization term
Reg(φ; ĥ) = Es∈S [relu(ĥ(s)− hφ(s))],
Here ĥ is the barrier certificate obtained in the previous epoch. In the ideal case when Reg(φ; ĥ) = 0, we have Chφ ⊃ Cĥ, that is, the new viable subset Chφ is at least bigger than the reference set (which is the viable subset in the previous epoch.) We compute the expectation over S approximately by using the set of candidate s’s maintained by MALA.
In summary, to learn hφ in CRABS, we minimize the following objective (for a small positive constant λ) over φ as shown in Algorithm 1:
L(φ;U, πθ, ĥ) = C∗(Lφ, U, πθ) + λReg(φ; ĥ). (5)
We remark that the regularization is not the only reason why the viable set Chφ can grow. When the dynamics becomes more accurate as we collect more data, the Chφ will also grow. This is because an inaccurate dynamics will typically make the Chφ smaller—it is harder to satisfy R.3 when the confidence region T̂ (s, π(s)) in the constraint contains many possible states. Vice versa, shrinking the size of the confidence region will make it easier to certify more states.

heading: 4.3 Learning a Calibrated Dynamics Model
text: It is a challenging open question to obtain a dynamics model T̂ (or any supervised learning model) that is theoretically well-calibrated especially with domain shift [Zhao et al., 2020]. In practice, we heuristically approximate a calibrated dynamics model by learning an ensemble of probabilistic dynamics models, following common practice in RL [Yu et al., 2020, Janner et al., 2019, Chua et al., 2018]. We learn K probabilistic dynamics models fω1 , . . . , fωK using the data in the replay buffer D̂. (Interestingly, prior work shows that an ensemble of probabilistic models can still capture the error of estimating a deterministic ground-truth dynamics [Janner et al., 2019, Chua et al., 2018].) Each probabilistic dynamics model fωi outputs a Gaussian distributionN (µωi(s, a), diag(σ2ωi(s, a))) with diagonal covariances, where µωi and σωi are parameterized by neural networks. Given a replay buffer D̂, the objective for a probabilistic dynamics model fωi is to minimize the negative log-likelihood:
LT̂ (ωi) = −E(s,a,s′)∼D̂ [− log fωi(s ′|s, a)] . (6)
The only difference in the training procedure of these probabilistic models is the randomness in the initialization and mini-batches. We simply aggregate the means of all learn dynamics models as a coarse approximation of the confidence region, i.e., T̂ (s, a) = {µωi(s, a)}i∈[K].

heading: 4.4 Policy Optimization
text: We describe our policy optimization algorithm in Algorithm 4 . The desiderata here are (1) the policy needs certified by the current barrier certificate h and (2) the policy has as high reward as possible. We break down our policy optimization algorithm into two components: First, we optimize the total rewards J(πθ) of the policy πθ; Second, we use adversarial training to guarantee the optimized policy can be certified by hφ. The modification of SAC is to some extent non-essential and mostly for technical convenience of making SAC somewhat compatible with the constraint set. Instead, it is the adversarial step that fundamentally guarantees that the policy is certified by the current hφ.
Adversarial training. We use adversarial training to guarantee πθ can be certified by hφ. Similar to what we’ve done in training hφ adversarially, the objective for training πθ is to minimize C∗(hφ, U, πθ). Unlike the case of φ, the gradient of C∗(hφ, U, πθ) w.r.t. θ is simply ∇θU(s∗, πθ(s∗), hφ), as the constraint hφ(s) is unrelated to πθ. We also use MALA to solve s∗ and plug it into the gradient term∇θU(s∗, πθ(s∗), hφ).
Optimizing J(πθ). We use a modified SAC [Haarnoja et al., 2018] to optimize J(πθ). As the modification is for safety concerns and is minor, we defer it to Appendix B. As a side note, although we only optimize πexplθ here, πθ is also optimized implicitly because π expl θ simply outputs the mean of πθ deterministically.

heading: 5 High-risk, High-reward Environments
text: We design four tasks, three of which are high-risk, high-reward tasks, to check the efficacy of our algorithm. Even though they are all based on inverted pendulum or cart pole, we choose the reward function to be somewhat conflicted with the safety constraints. That is, the optimal policy needs to take a trajectory that is near the safety boundary. This makes the tasks particularly challenging and suitable for stress testing our algorithm’s capability of avoiding irrecoverable states.
These tasks have state dimension dimensions between 2 to 4. We focus on the relatively low dimensional environments to avoid conflating the failure to learn accurate dynamics models from data and the failure to provide safety given a learned approximate dynamics. Indeed, we identify that the major difficulty to scale up to high-dimensional environments is that it requires significantly more data to learn a decent high-dimensional dynamics that can predict long-horizon trajectories. We remark that we aim to have zero violations. This is very difficult to achieve, even if the environment is low dimensional. As shown by Section 6, many existing algorithms fail to do so.
(a) Upright. The task is based on Pendulum-v0 in Open AI Gym [Brockman et al., 2016], as shown in Figure 1a. The agent can apply torque to control a pole. The environment involves the crucial quantity: the tilt angle θ which is defined to be the angle between the pole and a vertical line. The safety requirement is that the pole does not fall below the horizontal line. Technically, the user-specified safety set is {θ : |θ| ≤ θmax = 1.5} (note that the threshold is very close to π2 which corresponds to 90◦.) The reward function r is r(s, a) = −θ2, so the optimal policy minimizes the angle and angular speed by keeping the pole upright. The horizon is 200 and the initial state s0 = (0.3,−0.9). (b) Tilt. This action set, dynamics, and horizon, and safety set are the same as in Upright. The reward function is different: r(s, a) = −(θlimit − θ)2. The optimal policy is supposed to stay tilting near the
angle θ = θlimit where θlimit = −0.41151684 is the largest angle the pendulum can stay balanced. The challenge is during exploration, it is easy for the pole to overshoot and violate the safety constraints.
(c) Move. The task is based on a cart pole and the goal is to move a cart (the yellow block) to control the pole (with color teal), as shown in Figure 1b. The cart has an x position between −1 and 1, and the pole also has an angle θ ∈ [−π2 , π 2 ] with the same meaning as Upright and Tilt. The starting position is x = θ = 0. We design the reward function to be r(s, a) = x2. The user-specified safety set is {(x, θ) : |θ| ≤ θmax = 0.2, |x| ≤ 0.9} where 0.2 corresponds to roughly 11◦. Therefore, the optimal policy needs to move the cart and the pole slowly in one direction, preventing the pole from falling down and the cart from going too far. The horizon is set to 1000.
(d) Swing. This task is similar to Move, except for a few differences: The reward function is r(s, a) = θ2; The user-specified safety set is {(x, θ) : |θ| ≤ θmax = 1.5, |x| ≤ 0.9}. So the optimal policy will swing back and forth to some degree and needs to control the angles well so that it does not violate the safety requirement.
For all the tasks, once the safety constraint is violated, the episode will terminate immediately and the agent will receive a reward of -30 as a penalty. The number -30 is tuned by running SAC and choosing the one that SAC performs best with.

heading: 6 Experimental Results
text: In this section, we conduct experiments to answer the following question: Can CRABS learn a reasonable policy without safety violations in the designed tasks?
Baselines. We compare our algorithm CRABS against four baselines: (a) Soft Actor-Critic (SAC) [Haarnoja et al., 2018], one of the state-of-the-art RL algorithms, (b) Constrained Policy Optimization (CPO) [Achiam et al., 2017], a safe RL algorithm which builds a trust-region around the current policy and optimizes the policy in the trust-region, (c) RecoveryRL [Thananjeyan et al., 2021] which leverages offline data to pretrain a risk-sensitive Q function and also utilize two policies to achieving two goals (being safe and obtaining high rewards), and (d) SQRL [Srinivasan et al., 2020] which leverages offline data in an easier environment and fine-tunes the policy in a more difficult environment. SAC and CPO are given an initial safe policy for safe exploration, while RecoveryRL and SQRL are given offline data containing 40K steps from both mixed safe and unsafe trajectories which are free and are not counted. CRABS collects more data at each iteration in Swing than in other tasks to learn a better dynamics model T̂ . For SAC, we use the default hyperparameters because
we found they are not sensitive. For RecoveryRL and SQRL, the hyperparameters are tuned in the same way as in Thananjeyan et al. [2021] . For CPO, we tune the step size and batch size. More details of experiment setup and the implementation of baselines can be found in Appendix C.
Results. Our main results are shown in Figure 2. From the perspective of total rewards, SAC achieves the best total rewards among all of the 5 algorithms in Move and Swing. In all tasks, CRABS can achieve reasonable total rewards and learns faster at the beginning of training, and we hypothesize that this is directly due to its strong safety enforcement. RecoveryRL and SQRL learn faster than SAC in Move, but they suffer in Swing. RecoveryRL and SQRL are not capable of learning in Swing, although we observed the average return during exploration at the late stages of training can be as high as 15. CPO is quite sample-inefficient and does not achieve reasonable total rewards as well.
From the perspective of safety violations, CRABS surpasses all baselines without a single safety violation. The baseline algorithms always suffer from many safety violations. SAC, SQRL, and RecoveryRL have a similar number of unsafe trajectories in Upright, Tilt, Move, while in Swing, SAC has the fewest violations and RecoveryRL has the most violations. CPO has a lot of safety violations. We observe that for some random seeds, CPO does find a safe policy and once the policy is trained well, the safety violations become much less frequent, but for other random seeds, CPO keeps visiting unsafe trajectories before it reaches its computation budget.
Visualization of learned viable subset Chφ . We visualized the viable set Chφ in Figure 3. As shown in the figure, our algorithm CRABS succeeds in certifying more and more viable states and does not get stuck locally, which demonstrates the efficacy of the regularization at Section 4.2.
Handcrafted barrier function. To demonstrate the advantage of learning a barrier function, we also conduct experiments on a variant of CRABS, which uses a handcrafted barrier certificate by ourselves and does not train it, that is, Algorithm 2 without Line 5. Our goal for the handcrafted barrier function is to only show that it’s non-trivial to find a subset of viable states by handcrafting a region and therefore to demonstrate the necessity to learn the barrier certificates. In the experiments, we handcrafted a function g, whose superlevel set is a subset of safe states, and restricted exploration in this region (the superlevel set of g) in a similar manner as our current exploration scheme (Algorithm 3). Here only satisfies R.1 and R.2 but not necessarily R.3. Therefore, strictly speaking, the designed function g is not a barrier certificate, but only merely attempts to characterize a subset of safe states and restrict the exploration to it. More details of the handcrafted function g are available at Appendix C.
The results show that this variant does not perform well: It does not achieve high rewards, and has many safety violations. We hypothesize that the policy optimization is often burdened by adversarial training, and the safeguard policy sometimes cannot find an action to stay within the superlevel set Ch.

heading: 7 Related Work
text: Prior works about Safe RL take very different approaches. Dalal et al. [2018] adds an additional layer, which corrects the output of the policy locally. Some of them use Lagrangian methods to solve CMDP, while the Lagrangian multiplier is controlled adaptively [Tessler et al., 2018] or by a PID [Stooke et al., 2020]. Achiam et al. [2017], Yang et al. [2020] build a trust-region around the current policy. Eysenbach et al. [2017] learns a reset policy so that the policy only explores the states that can go back to the initial state. Turchetta et al. [2020] introduces a learnable teacher, which keeps the student safe and helps the student learn faster in a curriculum manner. Srinivasan et al. [2020] pre-trains a policy in a simpler environment and fine-tunes it in a more difficult environment. Bharadhwaj et al. [2020] learns conservative safety critics which underestimate how safe the policy is, and uses the conservative safety critics for safe exploration and policy optimization. Thananjeyan et al. [2021] makes use of existing offline data and co-trains a recovery policy.
Another line of work involves Lyapunov functions and barrier functions. Donti et al. [2020] constructs sets of stabilizing actions using a Lyapunov function, and project the action to the set, while Chow et al. [2019] projects action or parameters to ensure the decrease of Lyapunov function after a step. Ohnishi et al. [2019] is similar to ours but it constructs a barrier function manually instead of learning such one. Ames et al. [2019] gives an excellent overview of control barrier functions and how to design them. Perhaps the most related work to ours is Cheng et al. [2019], which also uses a barrier function to safeguard exploration and uses a reinforcement learning algorithm to learn a policy. However, the key difference is that we learn a barrier function, while Cheng et al. [2019] handcrafts one. The works on Lyapunov functions [Berkenkamp et al., 2017, Richards et al., 2018] require the discretizating the state space and thus only work for low-dimensional space.

heading: 8 Conclusion
text: In this paper, we propose a novel algorithm CRABS for training-time safe RL. The key idea is that we co-train a barrier certificate together with the policy to certify viable states, and only explore in the learned viable subset. The empirical rseults show that CRABS can learn some tasks without a single safety violation. We consider using model-based policy optimization techniques to improve the total rewards and sample efficiency as a promising future work. Another fascinating direction is how to deal with less accurate learned dynamics model in higher dimension environments.

heading: Acknowledgement
text: We thank Changliu Liu, Kefan Dong, and Garrett Thomas for their insightful comments. YL is supported by NSF, ONR, Simons Foundation, Schmidt Foundation, DARPA and SRC. TM acknowledges support of Google Faculty Award, NSF IIS 2045685, and JD.com.

Review summaries:
This paper proposes a safe reinforcement learning algorithm, CRABS, which can achieve zero training-time safety violations. The key idea is to iteratively learn the dynamic model, the policy and the barrier certificates. The barrier certificates are learned via adversarial training and can constrain the exploration of the policy in the safe set. The proposed algorithm is evaluated in four simple classical control problems (variants of inverted pendulum and cartpole). The evaluations demonstrate zero training-time violations and comparable learning performance compared to other safe learning baselines.

The paper proposes an RL algorithm that starts from an initial safe but low return policy that is iteratively improved while ensuring no safety violation occurs during the rollouts required by the training. The paper achieves this by learning barrier functions as safety certificates.  The two "simpler" barrier conditions are directly enforced in the structure of the learned function. In contrast, the "closed under a policy+environment step" condition R3 is checked heuristically on a probabilistic model of the environment with a Metropolis-adjusted Langevin algorithm.  Finally, the authors evaluate the achieved return and number of safety violations of their RL algorithm and other RL algorithms on variations of the Pendulum and CartPole gym environments.