Iterative Reachability Estimation for Safe Reinforcement Learning
Authors: Milan Ganai
Zheng Gong
Chenning Yu
Sylvia Lee Herbert
Sicun Gao
Venue: NeurIPS 2023 poster (2023)
Keywords: Constraints
Safety
Hamilton Jacobi Reachability
Deep Reinforcement Learning
Robotics
TL;DR: We propose a novel Reachability Estimation for Safe Policy Optimization algorithm for stochastic safety-constrained reinforcement learning with safety guarantees and optimal convergence analysis.

Abstract: Ensuring safety is important for the practical deployment of reinforcement learning (RL). Various challenges must be addressed, such as handling stochasticity in the environments, providing rigorous guarantees of persistent state-wise safety satisfaction, and avoiding overly conservative behaviors that sacrifice performance. We propose a new framework, Reachability Estimation for Safe Policy Optimization (RESPO), for safety-constrained RL in general stochastic settings. In the feasible set where there exist violation-free policies, we optimize for rewards while maintaining persistent safety. Outside this feasible set, our optimization produces the safest behavior by guaranteeing entrance into the feasible set whenever possible with the least cumulative discounted violations. We introduce a class of algorithms using our novel reachability estimation function to optimize in our proposed framework and in similar frameworks such as those concurrently handling multiple hard and soft constraints. We theoretically establish that our algorithms almost surely converge to locally optimal policies of our safe optimization framework. We evaluate the proposed methods on a diverse suite of safe RL environments from Safety Gym, PyBullet, and MuJoCo, and show the benefits in improving both reward performance and safety compared with state-of-the-art baselines.

Iterative Reachability Estimation for Safe Reinforcement Learning
Milan Ganai
Zheng Gong UC San Diego
Chenning Yu UC San Diego chy010@ucsd. edu
UC San Diego
mganai edu
zhgongOucsd.co edu
Sylvia Herbert
Sicun Gao
UC San Diego
UC San Diego
sherbert@uced.co edu
sic sicung@ucsd.com edu
Abstract
Ensuring safety important for the practical deployment of reinforcement learning (RL). Various challenges must be addressed, such handling stochasticity in the environments, providing rigorous guarantees of persistent state-wise safety satis- faction, and avoiding overly conservative behaviors that sacrifice performance. We propose a new framework, Reachability Estimation for Safe Policy Optimization (RESPO), for safety-constrained RI. in general stochastic settings. In the feasible set where there exist violation-free policies, we optimize for rewards while main- taining persistent safety. Outside this feasible set, optimization produces the safest behavior by guarantecing entrance into the feasible set whenever possible with the least cumulative discounted violations. We introduce class of algo- rithms using our novel reachability estimation function to optimize in our proposed framework and in similar frameworks such as those concurrently handling multiple hard and soft constraints. We theoretically establish that our algorithms almost surely converge to locally optimal policies of our safe optimization framework. We evaluate the proposed methods on diverse suite of safe RL environments from Safety Gym, PyBullet, and MuloCo, and show the benefits in improving both reward performance and safety compared with state-of-the-ar baselines.
Introduction
Safety- Constrained Reinforcement Learning is important for multitude of real-world safety-critical applications [1, 2]. These situations require guaranteeing persistent safety and achieving high perfor- mance while handling environment uncertainty. Traditionally, methods have been proposed obtain optimal control by solving within the Constrained Markov Decision Process (CMDP) framework, which constrains expected cumulative violation of the constraints along trajectories be under some threshold. Trust-region approaches [3, 4, 5] follow from the Constrained Policy Optimization algorithm [6] which tries to guarantee monotonic performance improvement while satisfying the cumulative constraint requirement. However, these approaches are generally very computationally expensive, and their first or second order Taylor approximations may have repercussions on perfor- mance [2]. Several primal-dual approaches [7, 8, 9] have been proposed with better computational efficiency and use multi-timescale frameworks [10] for asymptotic convergence to a local optimum. Nonetheless, these approaches inherit CMDP's lack of crucial rigorous safety guarantees that ensure persistent safety. Particularly, maintaining cost budget for hard constraints like collision avoidance insufficient, Rather, it's crucial to prioritize obtaining safe, mininal-violation policies when possible.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

There have been a variety of proposed control theoretic functions that provide the needed guarantees on persistent safety for such hard constraints, including Control Barrier Functions (CBFs) [11] and Hamilton-Jann Jacobi (HJ) reachability analysis [12, 13]. CBFs are mnergy-based certification functions, whose zero super-level set control invariant [14, 15]. The drawbacks are the conservativeness of the feasible set and the lack of systematic way to find these functions for general nonlinear systems. Under certain assumptions, approximate energy-based certificates can be learned with sufficient samples [16, 17, 18, 19, 20, 21]. HJ reachability analysis focuses finding the set of initial states such that there exists some control to avoid and/or reach a certain region. computes a value function, whose zero sub-level set is the largest feasible set, together with the optimal control. The drawback is the well known 'curse of dimensionalityy" as HJ reachability requires solving a corresponding Hamilton- -aannitonn-acoii-BPe Jacobi-Belllmaa Partial Differential Equation (HJBPDE) on discrete grid recursively. Originally, both approaches assume the system dynamics and environment are known, and inputs are bounded by some polytopic constraints, while recent works have applied them to model-free settings [22, 23, 24). For both CBF and HJ reachability, controllers that optimize performance and guarantee safety can be synthesized in different ways online [25]. There also exist hard-constraint approaches like [26] have theoretical safety guarantees without relying on control theory; however, they require learning or having access to the cansition-function dynamics.
Consequently, it can be beneficial to combine CMDP-based approaches to find optimal control and the advantages of control-theoretic approaches to enable safety. The recent framework of Reachability Constrained Reinforcement Learning (RCRL) [27] proposed an approach that guarantees persistent safety and optimal performance when the agent is in the feasible set. However, RCRL is limited to learning deterministic policies in deterministic environments. In the general RL setting, stochasticity incurs a variety of challenges including how define membership in the feasible set since it is no longer a binary question but rather a probabilistic one. Another issue is that for states outside optimal feasible set, RCRL optimization cannot guarantee entrance into the feasible set when possible. This may have undesirable consequences including indefinitely violating constraints with no recovery.
In light of the above challenges, we propose new framework and class of algorithms called Reachability Estimation for Safe Policy Optimization (RESPO). Our main contributions are:
We introduce reachability estimation methods for general stochastic policies that predict the likelihood of constraint violations in the future. Using this estimation, a policy can be optimized such that (i) when in the feasible set, it maintains persistent safety and optimizes for reward performance, and (ii) when outside the feasible set, produces the safest behavior and enters the feasible set possible. We also demonstrate how our optimization can incorporate multiple hard and soft constraints while even prioritizing the hard constraints.
We provide a novel class of actor-critic algorithms based on learning our reachability estimation function, and prove our algorithm converges locally optimal policy of our proposed optimization.
We perform comprehensive experiments showing that our approach achieves high performance in complex, high nigh-dimensional Safety Gym. ByBuleet-based, and MuJoCo-basch environments compared to other ofte-of-thh-ar cafety-constrained approaches while achieving small or even violations. We also show our algorithm's performance in environments with multiple hard and soft constraints.
2 Related Work
2.1 Constrained Reinforcement Learning
lafety-constrained reinforcement learning has been addressed through various proposed learning mechanisms solving within an optimization framework. CMDP [28, 29] is one framework that augments MDPs with the cost function: the goal is to maximize expected reward returns while constraining cost returns below a manually chosen threshold. Trust-region methods [3, 4, 5, 6] and primal-dual based approaches [7, 9, 30, 31] are two classes of CMDP- approaches. Trust-region approaches generally follow from Constrained Policy Optimization (CPO) [6], which approximates the constraint optimization problem with surrogate functions for the reward objective and safety constraints, and then performs projection steps on the policy parameters with backtracking line search. Penalized Proximal Policy Optimization [32] improves upon past trust-region approaches via the clipping mechanism, similar to Proximal Policy Optimization's 's [33] improvement over Trust Region Policy Optimization [34]. Constraint-Rectiffe Policy Optimization [35] takes steps toward improving reward performance if constraints are currently satisfied else takes steps to minimize

---

HJ reachability analysis is a rigorous approach that verifies safety or reachability for dynamical systems. Given any deterministic nonlinear system and target set, it computes the viscosity solution for the HJBPDE, whose zero sub-level set is the backward reachable set (BRS), meaning there exists some control such that the states starting from this set will enter the target set in future time (or stay away from the target set for all future time). However, the curse of dimensionality and the assumption of knowing the dynamics and environment in advance restrict its application, especially in the model-free RI setting where there is no access to the entire observation space and dynamics at any given time. Decomposition [37], warm-starting [38], sampling- based reachability [39]. and Deepreach [40] have been proposed to solve the curse of dimensionality. [23, 24] proposed methods to bridge HJ analysis with RL by modifying the HJBPDE. The work of [27] takes framework into deterministic hard-constraint setting. There are additionally model-based HJ reachability approach for reinforcement learning- based controls. [41] a model-based extension of [27]. Approaches like [42, 43, 44] use traditional HJ reachability for RL control while learning or assuming access to the system dynamics model. In stochastic systems, finding the probability of reaching a target while avoiding certain obstacles are key problems. [45, 46] constructed the theoretic framework based on dynamic programming and consider finite and infinite time reach-avoid problems. [47, 48, 49] tractable manner constraint violations. PPO Lagrangian [30] is a primal- method combining Proximal Policy Optimization (PPO) [33] with lagrangian relaxation of the safety constraints and has relatively low complexity but outperforms CPO in constraint satisfaction. [7] uses a penalized reward function like PPO Lagrangian, and demonstrates convergence to an optimal policy through the multi-timescale framework, introduced in [10]. [36] proposes mapping the value function constraining problem as constraining densities of state visitation. Overall, while these algorithms provide benefits through various learning mechanisms, they inherit the problems of the CMDP framework. Specifically, they do not provide rigorous guarantees of persistent safety and so are generally unsuitable for state-wise constraint optimization problems.
2.2 Hamilton-Jacobi Reachability Analysis
propose computing the stochastic reach-avoid set together with the prohability in
to address the curse of dimensionality.
3 Preliminaries
3.1 Markoy Decision Processes
Markov Decision Processes (MDP) are defined as M P,r,,, S and A are the state and action spaces respectively. P S x A x S + [] is the transition function capturing the environment dynamics. r S A IR is the reward function associated with each state-action pair, h: S S 55 R55 is the safety loss function that maps state to non-negative real value, which is called the constraint value, or simply cost. Hmin is the minimum non-zero value of function h; Hmax is upper bound on function h. is a discount factor in the range (0, 1). Sy is initial state set, do is initial state distribution, and x [[a (s] is stochastic policy that is parameterized by the state and returns an action distribution from which an action can be sampled and affects the environment defined by the MDP. In unconstrained RI., the goal is to learn an optimal policy T² maximizing expected discounted sum of rewards, i.e. x² = arg max, Ry-do (s). where (s) == Ra P(s) / 7rr(st, ot)]- Note: TT, P(s) indicates sampling trajectory for horizon T starting from state using policy in MDP with transition model P, and St E r is the tth state in trajectory T.
3.2 Constrained Markov Decision Process
CMDP attempts to optimize the reward returns V*((s) under the constraint that the cost return is below some manually chosen threshold x. Specifically:
max
E Aredoo
[V (s)], subject to E (s)
(CMDP)
sr-do
where cost return function V (s) is often defined as VTT(s) == E(, Y 7'h(s))).
While many approaches have been proposed solve within this framework, CMDPs have several difficulties: 1. cost threshold often requires much tuning while using prior knowledge of the environment; and CMDP often permits some positive average cost which incompatible with wise hard constraint problems, since x is usually chosen to be above 0.
3

---

Stochastic Hamilton-Jacobi Reachability for Reinforcement Learning
Classic HJ reachability considers finding the largest feasible set for deterministic environments. In this section, we apply a similar definition in [45, 46] and define the stochastic reachability problem.
4.1 Persistent Safety and HJ Reachability for Stochastic Systems
The instantaneous safety can characterized by the safe set Ss, which is the zero level set of the safety loss function h S + Bgg The unsafe (i.e. violation) set S, is the complement of the safe set. Definition 1. Safe set and unsafe set: S. == {s S h(s) 03. == {s E S h(s)) > 0}.
We will write s.,, as the instantaneous violation indicator function, which is if the current state in the violation set and otherwise. Note that the safety loss function instantaneous violation indicator function since h captures the magnitude of the violation at the state.
different from the
is insufficient only consider instantaneous safery. When the environment and policy are both deterministic, we easily have unique trajectory for starting from each state (i.e. the future state is uniquely determined) under Lipschitz environment dynamics. In classic HJ reachability literature [13], for a deterministic MDP's transition model Pa and deterministic policy guarantees persistent safety captured by the zero sub-level set of the following value function:
the set of states that
Definition 2. Reachability value function V S + R is: (s)
SrrTtaa h((t)-
However, when there's a stochastic environment with transition model P(|ss, a) and policy T(-(s), the future states not uniquely determined. This means for a given initial state and policy, there may exist many possible trajectories starting from this state. In this case, instead of defining a binary function that only indicates the existence of constraint violations, we define the reachability estimation function (REF), which captures the probability of constraint violation:
Definition 3. The reachability estimation function (REF) d" S [0, 1] is defined as:
o" (s) =
E max (s1100=s,7)S..
P(s), SIET
In specific trajectory the value mäX,,er 1 (,)119==,,) will be 1 if there exist constraint violations and 0 if there exists no violation, which is binary. Taking expectation over this binary value for all the trajectories, get the desired probability. We define optimal REF based on optimally safe policy x² arg min, (=((s) (note that this policy may not be unique).
Definition 4. The optimal reachability estimation function o² S 00, 1] is: (=)== (s).
Interestingly, we can utilize the fact the instantaneous violation indicator function produces binary values learn the REF function in a bellman recursive form. The following will used later:
Theorem 1. The REF can be reduced the following recursive Bellman formulation:
max(L.ess P(T)
E 8- (s()s))
where s' I,, P(s) is sample of the immediate successive state (i.e., s' ~ P(-ss, rT-ss)) and the expectation is taken over all possible successive states. The proof can be found in the appendix.
Definition The feasible set of policy æ based on şi" (s) is defined as: S7 == {s E + (8) = 0).
Note, the feasible set for a specific policy is the set of states starting from which no violation is reached, and the safe set is the set of states at which there is no violation. We will use the phrase likelihood of being feasible to mean the likelihood of not reaching a violation, i.e. - (s).
4.2 Comparison with RCRL
The RCRL approach [27] uses reachability to optimize and maintain persistent safety in the feasible set. Note, in below formulation, S, is the optimal feasible set, i.c. that of a policy arg ming V (s). The RCRL formulation is:
max sr-do
E. [V)(s) L.es, vi((() (s) l subject Vi (s) S Ys S7 Sy
(RCRL)
The equation RCRL considers two different optimizations. When the optimal feasible set, the optimization produces persistently safe policy maximizing rewards. When outside this set, the

---

optimization produces control minimizing the maximum future violation, i.e. arg min, Vi (s). However, this does not ensure (re)entrance into the feasible set even if such a control exists.
RCRL performs constraint optimization on VA," with a neural network (NN) lagrange multiplier with state input [9]. When learning to optimize a Lagrangian dual function, the NN lagrange multiplier should converge to small values for states in the optimal feasible set and converge to large values for other states. Nonetheless, learning V/ provides weak signal during training: if there is an improvement in safery along the trajectory not affecting the maximum violation, VE remains the same for all states before the maximum violation in the trajectory. These improvements in costs can be crucial in guiding the optimization toward a safer policy. And optimizing with (s) can result in accumulating an unlimited number of violations smaller than the maximum violation. Also, major issue with this approach is that it's ss limited to deterministic MDPs and policies because its reachability value function in the Bellman formulation does not directly apply to the stochastic setting. However, in general stochastic settings, estimating feasibility cannot be binary since for a large portion of the state space, even under the optimal policy, the agent may enter the unsafe set with a non-zero probability, rendering such definition too conservative and impractical.
Iterative Reachability Estimation for Safe Reinforcement Learning
In this paper, we formulate a general optimization framework for safety-constrained RL and propose new algorithm solve our constraint optimization by using our novel reachability estimation function. We present the deterministic case in Section 5.1 and build our way to the stochastic case in Section 5.2. We present our novel algorithm to solve these optimizations, involving our new reachability estimation function, in Section 5.3. We introduce convergence analysis in Section 5.4.
5.1 Iterative Reachability Estimation for Deterministic Settings
All state transitions and policies happen with likelihood 0 or 1 for the deterministic environment. Therefore, the probability of constraint violation for policy from state i.e., (s),,. is in the set f0. 1). According to Definition 4, if there exists some policy π such that (0( = 0, we have (s) = O. Otherwise, o² (s) = 1. Notice that this captures definitive membership in the optimal feasible set x (s) 1 EEST" which is the feasible set of some safest policy म, = arg min, (s).
Now, we divide our optimization in two parts: the infeasible part and the feasible part.
For the infeasible part, want the agent to incur the least cumulative damage (discounted sum of costs) and, if possible, (re)enter the feasible set. Different from previous Reachability- RL optimizations, by using the discounted sum of costs (s) we consider both magnitude and frequency of violations, thereby improving learning signal. The infeasible portion takes the form:
max
E dr
(s).
For the feasible part, we want the policy to ensure the agent stays in the feasible set and maximize reward returns. This produces a constraint optimization where the cost value function is constrained:
max
E gruda
(s)], subject to V = 0, Vs E S₁-
(2)
The following propositions justify using V as the constraint. Both proofs are in the appendix. Proposition 1. The cost value function VT7 3) zero for state if and only if the persistent safety is guaranteed for that state under the policy n.
We define here Sy := S the feasibilty set of some safest policy. Now, the above two optimizations can be unified with the use of the feasibility function (*(s):
max E (V* (1 -0--0"(a o² (s) o² (s)], subject to (s) = 0, Vs S SyS sondo
(3)
Unlike other reachability based optimizations like RCRL, one particular advantage in Equation 3 is. with some assumptions, the guaranteed entrance back into feasible set with minimum cumulative discounted violations whenever possible control exists. More formally, assuming infinite horizon:
Proposition 2. If 3 that produces trajectory T = {(s.). E N, s₁ = .s} in deterministic MDP M starting from state 8, and 3m E N, m < αc such that 8m 57, then 3e > 0 where if discount factor 7 E (1 e, 1). then the optimal policy xt of Equation 3 will produce trajectory (()), N, $1 s), such that 3n N, < oc. 8y E ST and V (s) ming V (s).
5

---

5.2 Iterative Reachability Estimation for Stochastic Settings
In stochastic environments, for each state, there some likelihood of entering into the unsafe states under any policy. Thus, we adopt the probabilistic reachability Definitions 3 and 4. Rather than using the binary indicator the optimal feasible set to demarcate the feasibility and infeasibility optimization scenarios, we use the likelihood of infeasibility of the safest policy. In particular, for any state 8, the optimal likelihood that the policy will enter the infeasible set (*(s) from Definition 4.
We again divide the full optimization problem in stochastic settings into infeasible and feasible ones similar Equations and 2. However, we consider the infeasible formulation with likelihood the current state is in safest policy's 's infeasible state, or (s)) Similarly, we account for the feasible optimization formulation with likelihood the current state in a safest policy's feasible set, o" (s). The complete Reachability Estimation for Safe Policy Optimization (RESPO) can be rewritten as:
max E (s) (1 - (s)) V.. (s) 0- (s)), s.t. V = 0, w.p. 1 (s), Vs E S1- snida
(RESPO)
In sum, the RESPO framework provides several benefits when compared with other constrained Reinforcement Learning and reachability-based approaches. Notably, 1) it maintains persistent safety when in the feasible set unlike CMDP approaches. 2) compared with other reachability- based approaches, RESPO considers performance optimization in addition to maintaining safety, 3) it maintains the behavior of safest policy in the infeasible set and even reenters the feasible set when possible, 4) RESPO employs rigorously defined reachability definitions even in stochastic settings.
5.3 Overall Algorithm
We describe our algorithms by breaking down the novel components. Our algorithm predicts reachability membership to guide the training toward optimizing the right portion of the optimization equation (i.e., feasibility case or infeasibility case). Furthermore, it exclusively uses the discounted sum of costs as the safety value function we can avoid having to learn the reachability value function while having the benefit of exploiting the improved signal in the cost value function.
Optimization in infeasible set versus feasible set. If the agent is in the infeasible set, this is the simplest case. We want to find the optimal policy that maximizes V. (s). This would be the only term that needs to be considered in optimization.
On the other hand, if the agent is in the feasible set, we must solve the constraint optimization max, V*(8) (8) subject to (s) = 0. This could be solved via a Lagrangian-based method:
min max L( A) min max X srida
E (-V + (V)
Now what remains is obtaining the reachability estimation function o*, First, we address the problem of acquiring optimal likelihood of being feasible. It is nearly impossible to accurately know before training if a state is in a safest policy's 's infeasible set. We propose learning a function guaranteed to converge to this REF (with some discount factor for y-contraction mapping) by using the recursive Bellman formulation proved in Theorem 1.
We learn function p(s) to capture the probability d² (s). It is trained like a reachability function:
p(s) max{L - ((s')),
where S, is the violation set, 8' is the next sampled state, and y is a discount parameter 0 < << 1 to ensure convergence of p(s). Furthermore, and crucially, we ensure the learning rate of this REF is on a slower time scale than the policy and its critics but faster than the lagrange multiplier.
Bringing the concepts covered above, we present our full optimization equation:
E VVT - X V. (1 p((s)) + VT) p(s)) (4)
min max L(TT A) min max
We show the design of our algorithm RESPO in an actor-critic framework in Algorithm 1. Note that the V and V. have corresponding Q functions: VT(s) = Ea-- Q(s, a) and VTT = Egsa((-l)) Qe(s, a). The gradients' definitions are found in the appendix. We use operator Te to indicate the projection of vector f E IR" to the closest point in compact and convex set θ C R!.
Specifically, Ie arg minicc | - In is similarly defined.

---

Algorithm RESPO Actor Critic
Require: Randomly initialized policy ma's parameters Og. reward critic Q's parameters voo cost critic Qe's parameters Ko, REF p's parameters εo. Lagrange multiplier X's parameters was horizon T Require: Convex projection operators ee and [n and reward and cost critic learning rate (1 (k), policy learning rate C2 (k), REF learning rate (s()), lagrange multiplier learning rate Ç1 (1
1: for k = 0, 2. do
2: for i 2, do
3: Sample trajectories Ti {($j. aj, 8 (g.,),h,))) To
4: Rew. Update 7h++1 = 17 6 (k)k ((s at) [Q(s. 0z) (r(s), + (
5: Cost Update KK+1 = Ki V (Q.(s,, (h(s,) + +Q (4+1),
6: Policy Update OK+1
7: Te 0s (2-))(
-
Vo Volog log (a(()s)))
8: REF Update Sk+11 ε Ca(k)) - max(s))o "p(0)+))))0000000))1)))))))
9: Lagrange multiplier Update wk+1 = Tn(ws - Cu(+)) -p(ss))
10: end for
11: end for
Unsafe region
Figure I: We compare the performance of algorithm with other SOTA baselines in Safety Gym (left figures), Safety PyBullct (middle two figures), and Safety MuJaCo (right two figures).
5.4 Convergence Analysis
We provide convergence analysis of our algorithm for Finite MDPs (finite bounded state and action space sizes, maximum horizon T, reward bounded by Rmaxx and cost bounded by Hmax) under reasonable assumptions. We demonstrate our algorithm almost surely finds a locally optimal policy for our RESPO formulation, based the following assumptions:
A1 (Step size): Step sizes follow schedules {G (k)), {G2(k)), (G)(k)). (Sa(k)) where: Σ (k)) = Do and Σ (k))² < oo, Vi (1,2,3,4) 4), and ()()) = o())-1(k)) Vj E (2,3,4]
The reward returns and cost returns critic value functions must follow the fastest schedule (k)). the policy must follow the second fastest schedule (k)), the REF must follow the second slowest schedule (k)), and finally, the lagrange multiplier should follow the slowest schedule (k)).
A2 (Strict Feusibility): 3m((1:;; such that Vs E Sy where o² (s) 0, V (8) S O.
A3 (Differentiability and Lipschitz Continuity): For state-action pairs (s, a), we assume value and cost Q functions (s,, a;;)), Qe(s, (8, k),,, policy x [a]s;; s; 0), and REF p(s, a; {) are continuously differentiable 77, k. 0, respectively. Furthermore, V A and, for all state-action pairs (s, a). Ver((a 0) are Lipschitz continuous functions in and 0 respectively.
The detailed proof of the following result provided in the appendix.
Theorem 2. Given Assumptions A1-A3, the policy updates in Algorithm will almost surely converge to locally optimal policy for our proposed optimization in Equation RESPO.
Experiments
Baselines. The baselines we compare are CMDP-based or solve for hard constraints. The CMDP baselines are Lagrangian-basse -bsse Proximal Policy Optimization (PPOLag) based [7]. Constraint- Rectified Policy Optimization (CRPO) [35], Penalized Proximal Policy Optimization (P30) [32], and Projection- Based Constrained Policy Optimization (PCPO) [3]. The hard constraints baselines
are RCRL [27]. CBF with constraint in(s) и h(()) S 0, and Feasibile Actor-Critic (FAC) [9]. We classify FAC among the hard constraint approaches because we make its cost threshold x = in
order to better compare using NN lagrange multiplier with our REF approach in RESPO. We include the unconstrained Vanilla PPO [33] baseline for reference.

---

Benchmarks. We compare RESPO with the baselines in a diverse suite of safety environments. We consider high-dimensiona environments in Safety Gym [30] (namely PointButton and CarGoal), Safety PyBullet [50] (namely DroneCircle and BallRun), and Safety MuJoCo [51], (namely Safety HalfCheetah and Reacher). We also show our algorithm in a multi-drone environment with multiple hard and soft constraints. More detailed experiment explanations and evaluations are in the appendix.
6.1 Main Experiments in Safety Gym, Safety PyBullet, and MuJoCo
We compare our algorithm with SOTA benchmarks on various high-dimensional (up 76D observa- tion space), complex environments in the stochastic setting, i.e., where the environment and/or policy are stochastic. Particularly. we examine environments in Safety Gym, Safety PyBullet, and Safety MuJoCo. The environments provide reward for achieving goal behavior or location, while the cost based on tangible (e.g., avoiding quickly moving objects) and non-tangible (c.g., satisfying speed limit) constraints. Environments like PointButton require intricate behavior where specific buttons must be reached while avoiding multiple moving obstacles, stationary hazards, and wrong buttons.
Overall, RESPO achieves the best balance between optimizing reward and minimizing cost violations across all the environments. Specifically, our approach generally has the highest reward performance (see the red lines from the top row of Figure 2) among the safety-constrained al algorithms while maintaining reasonably low to 0 cost violations (like in HalfCheetah). When RESPO performs the second highest, the highest-performing than RESPO for instance, RCRL in PointButton or PPOLag Drone Cirele. Non-primal-dun CMDP approaches, namely CRPO, P30, and PCPO generally satisfy their cost threshold constraints, but their reward performances rarely exceed that of PPOLag. RCRL generally has extremes of high reward and high cost, like in BallRun, or low reward and low cost, like in CarGoal. FAC and CBF generally have conservative behavior that sacrifices reward performance to minimize cost.
safety algorithm always incurs several times more violations
Poiettuttion Curraatian Rewaards
Bs Corrraat Rowarik
Sneve tre Curvidivve Rewandk
1.0
RCH
30-
5.5
BCDM join)
DPP
1.0
0.5
0.2
-10
Contioal Curnu Caste
Nyrtbotter Curvidba Costs
Sellan Damalattes Costs
Drovid Inde Cormucttivn Coats
1.5
40-
22
1.0
1.5
3.5
16-
2
Figure 2: Comparison of RESPO with baselines in Safety Gym and PyBullet environments. The plots in the first row show performance measured in rewards (higher is better); those in second row show cost (lower is better). RESPO (red curves) achieves the best balance of maximizing reward and minimizing cost. When other methods achieve higher rewards than RESPO, they achieve much higher costs as well. E.g.. in PointButton. RCRL slightly higher rewards, but accumulates over 3x violations than RESPO. Note, Vanilla PPO is unconstrained.
6.2 Hard and Soft Constraints
We also demonstrate RESPO's performance in an environment with multiple hard and soft constraints. The environment requires controlling two drones to pass through a tunnel one at a time while respecting certain distance requirements. The reward is given for quickly reaching the goal positions. The two hard constraints involve (H1) ensuring neither drone collides into the wall and (H2) the distance between the two drones is more than 0.5 to ensure they do not collide. The soft constraint is that the two drones are within 0.8 of each other to ensure real-world communication. It preferable to prioritize hard constraint H1 over hard constraint H2, since colliding with the wall may have more serious consequences to the drones rather than violations of an overly precautious distance constraint.
Our approach, in the leftmost of Figure 3, successfully reaches the goal while avoiding the wall obstacles all time steps. We are able to prioritize this wall avoidance constraint over the second hard constraint. This can be seen particularly in between the blue to cyan time period where the higher
8

---

RESPO (ours)
PPOLag
RCRL
FAC
FA
6.
-55 -10 -35
20
65
23
15
-33 -30 -35 38
65
15
15
-35 -0
-55
16
65
13
15
-15 -6
43
03
05 16
Figure 3: Comparison of RESPO with baselines trajectories in Hard & Soft Constraints multi-Drone control. Starting at gold circles, drones must enter the tunnel one a time wall avoidance and ensuring drones are farther than 0.5 meters from each other. Soft constraint drones are within 0.8 meters of each other. Trajectory colors correspond to time, RESPO (on left) successfully controls drones to reach goals while always avoiding walls and usually respecting distance constraints. Other baselines cannot manage multiple constraints: they collide with the wall and have many distance constraint violations.
reach green stars. Hard constraints are
22
Pestiation Cuevalar Rewerds
Maro asiiti
-1.3
2.0
CWPC
-10
neacher Cumuittte Costs
-27
*ardiumn Curta STAA Costs
10
6
Figure 4: Comparison of RESPO with baselines in Mu- JoCo. Higher rewards (first row plots) and lower costs (second row plots) are better. In HalfCheetah, RESPO has highest reward among safcty baselines, with 0 viola- tions. In Reacher, RESPO has good rewards, low costs.
Figure 5: Ablation study on the learning rate of REF
Higher rewards (first row plots) are better; lower costs (sccond row plots) are better. When changing REF's learning rate to violate timescale assumptions, REF produces suboptimal feasible sets.
Drone makes way for the lower Drone to pass through but needs to make drop to make concave parabolic trajectory to the goal. Nonetheless, the hard constraints are almost always satisfied, thereby producing the behavior of allowing one drone through the tunnel at a time. The soft constraints are satisfied at the beginning and end but are violated, reasonably, in the middle the episode since only one drone can pass through the tunnel at time, thereby forcing the other drone into a standby mode.
6.3 Ablation Studies
We also perform ablation studies to experimentally confirm the design choices made based the theoretically established convergence and optimization framework. We particularly investigate the effects of changing the learning rate of reachability function well changing the optimization framework. We present the results of changing the learning rate for REF in Figure 5 while our results for the ablation studies on our optimization framework can be seen in Figure 6.
In Figure 5, we show the effects of making the learning rate of REF slower and faster than the one we use in accordance with Assumption 1. From these experiments, changing the learning rate in either direction produces poor reward performance. A fast learning rate makes the REF converge to the likelihood of infeasibility for the current policy, which can be suboptimal. But a very slow learning rate means the function takes too long to converge - the lagrange multiplier may meanwhile become very large, thus making it too difficult to optimize for reward returns. In both scenarios, the algorithm with modified learning rates produces conservative behavior that sacrifices reward performance.
In Figure 6, we compare RESPO with RCRL implemented with our REF and PPOLag in the CMDP framework with cost threshold x = to ensure hard constraint satisfaction. The difference between RESPO and the RCRL-based ablation approach is that the ablation still uses V instead of V. The ablation aproach's 's high cumulative cost can be attributed to the limitations of using V particularly, the lower sensitivity of VA to safety improvement and its lack of guarantees on feasible set (re)entrance. PPOL ag with x = 0 produces low violations but also very low reward performance that's 's close to zero. Naively using V in hard constraints framework leads to very conservative

---

Pointlutton Corcattya Rewards
Sal Candat Rowards
SreeeCrce Canvattv Revards
11
10
8.0
4.0
-20
CarGoal Cumu Costs
-27
CrancCeele Curmuative Conts
20-
15-
Figure 6: Ablation study on optimization framework. Top row plots show performance measured in reward (higher is better). Bottom row plots show cost (lower is better). RESPO (red curve) achieves best balance of maximizing reward and minimizing cost. RCRL framework implemented with our REF without V. incurs very high costs. PPOLag CMDP framework with X has very low reward performance. So, learning REF and learning V. are both crucial components in our design and work tandem to contribute to RESPO's efficacy.
behavior that sacrifices reward performance. Ultimately, this ablation study experimentally highlights the importance of learning our REF and using value function V in our algorithm's 's design.
7 Discussion and Conclusion
In summary, we proposed a new optimization formulation and a class of algorithms for safety- constrained reinforcement learning. Our framework optimizes reward performance for states in least-violation policy's ' feasible state space while maintaining persistent safety as well as providing the safest behavior in other states by ensuring entrance into the feasible set with minimal cumulative discounted costs. Using our proposed reachability estimation function, we prove our a algorithm's class of actor-critic methods converge locally optimal policy for our proposed optimization. We provide extensive experimental results on diverse suite of environments in Safety Gym, PyBullet, and MuJoCo, and an environment with multiple hard and soft constraints, demonstrate the effectiveness of our algorithm when compared with several SOTA baselines. We leave open various extensions to our work enable real-world deployment of our algorithm. These include constraining violations during training, guaranteeing safety in single-lifetime reinforcement learning, and ensuring policies don't forget feasible sets as environment tasks change. Our approach of learning the optimal REF to reduce the state space into low-dimensional likelihood representation to guide training for high-dimensional policies can have applications in other learning problems in answering binary classification likelihood-basee questions about dynamics in high-dimension feature spaces.
8 Acknowledgements
This material is based on work supported by NSF Career CCF 2047034, NSF CCF DASS 2217723, ONR YIP N00014-22-1-22999 and Amazon Research Award.
10

---

References
[1] Javier Garcfa and Fernando Fernández. A comprchensive survey on safe reinforcement learning. Journal of Machine Learning Research, 16(1):1437-1480, 2015.
[2] Shangding Gu, Long Yang, Yali Du, Guang Chen, Florian Walter, Jun Wang, Yaodong Yang, and Alois Knoll. A review of safe reinforcement learning: Methods, theory and applications. arXiv preprint arXiv:2205.10338 2022.
[3] Tsung- Yen Yang, Justinian Rosca, Karthik Narasimhan, and Peter J Ramadge. Projection- based constrained policy optimization. In International Conference on Learning Representations, 2020.
[4] Yiming Zhang, Quan Vuong, and Keith Ross. First order constrained optimization in policy space. Advances in Neural Information Processing Systems, 33:15338-15344 2020.
[5] Long Yang, Jiaming Ji, Juntao Dai, Yu Zhang, Pengfei Li, and Gang Pan. Cup: A conservative update policy algorithm for safe reinforcement learning. arXiv preprint arXiv:2202.07565. 2022.
[6] Joshua Achiam, David Held, Aviv Tamar, and Pieter Abheel. Constrained policy optimization. In International conference on machine learning, pages 22-31. PMLR, 2017.
[7] Chen Tessler, Daniel Mankowitz, and Shie Mannor. Reward constrained policy optimization. In International Conference on Learning Representations, 2019.
[8] Yinlam Chow, Mohammad Ghavamzadeh, Lucas Janson, and Marco Pavone. Risk-constrained reinforcement learning with percentile risk criteria. The Journal of Machine Learning Research, 18(1):60706622 120, 2017.
[9] Haitong Ma, Yang Guan, Shegnho Eben Li, Xiangteng Zhang, Sifa Zheng, and Jianyu Chen. Feasible actor-critic: Constrained reinforcement learning for ensuring statewise safety, arXiv preprint arXiv:2105. 2021.
[10] Vivek S Borkar. Stochastic approximation: a dynamical systems viewpoint, volume 48. Springer, 2009.
[11] A. D. Ames, S. Coogan, M. Egerstedt, G. Notomista, K. Sreenath, and P. Tabuada. Control barrier functions: Theory and applications. In European Control Conf., 2019.
[12] Jaime F Fisac, Mo Chen, Claire J Tomlin, and S Shankar Sastry. Reach-avoid problems with time-varying dynamics, targets and constraints. In Hybrid Systems: Computation and Control. ACM, 2015.
[13] S. Bansal, M. Chen, S. Herbert, and C. J. Tomlin. Hamilton-Jacob reachability: A brief overview and recent advances. In Conf. on Decision and Control, 2017.
[14] Aaron D Ames, Kevin Galloway, Koushil Sreenath, and Jessy W Grizzle. Rapidly exponentially stabilizing control Lyapunov functions and hybrid zero dynamics. Trans. on Automatic Control, 2014.
[15] Xiangru Xu, Paulo Tabuada, Jessy W. Grizzle, and Aaron D. Ames. Robustness of control barrier functions for safety critical control. Int. Federation of Automatic Control, 2015.
[16] Ya-Chien Chang, Nima Roohi, and Sicun Gao. Neural Iyapunov control. In H. Wallach, H. Larochelle, A. Beygelzimer, TTAlché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[17) Ya-Chien Chang and Sicun Gao. Stabilizing neural control using self-learned almost Цyаршnov critics. 2021 IEEE International Conference on Robotics and Automation (ICRA), pages 1803-1809, 2021.
[18] Zhizhen Qin, Tsui- Wei Weng, and Sicun Gao. Quantifying safety of learning-based self- driving control using almost-barrier functions. In 2022 IEFF/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 12903-12910, IEEE, 2022.
11

---

[19] Milan Ganai, Chiaki Hirayama, Ya-Chien Chang, and Sicun Gao. Learning stabilization control from observations by learning lyapunov- like proxy models. 2023 IEEE International Conference Robotics and Automation (ICRA), 2023.
[20] Yujie Yang, Yuxuan Jiang, Yichen Liu, Jianyu Chen, and Shengbo Eben Li. Model-free safe reinforcement learning through neural barrier certificate. IEEE Robotics and Automation Letters, 2023.
[21] Yixuan Wang, Simon Sinong Zhan, Ruochen Jiao, Zhilu Wang, Wanxin Jin, Zhuoran Yang, Zhaoran Wang, Chao Huang, and Qi Zhu. Enforcing hard constraints with soft barriers: Safe reinforcement learning in unknown stochastic environments. In International Conference on Machine Learning, pages 36593-36604. PMLR, 2023.
[22] Tamas G Molnar, Ryan K Cosner, Andrew W Singletary, Wyatt Ubellacker, and Aaron D Ames. Model-free safety-crie critiiall control for robotic systems. IEEE robotics and automation letters, 7(2):944-551, 2021.
[23] Anayo K Akametalu, Shromona Ghosh, Jaime F Fisac, and Claire J Tomlin. A minimum discounted reward hamilton-jacobi formulation for computing reachable sets, arXiv preprint arXiv:1809.00706, 2018.
[24] Jaime F Fisac, Neil F Lugovoy, Vicenç Rubies-Royo, Shromona Ghosh, and Claire J Tomlin. Bridging hamilton-jacobi safety analysis and reinforcement learning. In 2019 International Conference on Robotics and Automation (ICRA), pages 8550-8556. IEEE, 2019.
[25] A. Ames, X. Xu, J. W. Grizzle, and P. Tabuada. Control barrier function based quadratic programs for safety critical systems. Trans. on Automatic Control, 2017.
[26] Nuoya Xiong et al. Provably safe reinforcement learning with step-wise violation constraints. arXiv preprint arXiv:2302.0666 2023.
[27] Dongjie Yu, Haitong Ma, Shengbo Li, and Jianyu Chen. Reachability constrained reinforcement learning. In International Conference on Machine Learning, pages 25636-25655. PMLR, 2022.
[28] Eitan Altman. Constrained Markov decision processes: stochastic modeling. Routledge, 1999.
[29] Lukas Brunke, Melissa Greeff, Adam W Hall, Zhaocong Yuan, Siqi Zhou, Jacopo Panerati, and Angela P Schoellig. Safe learning in robotics: From learning-based control to safe reinforcement learning. Annual Review of Control, Robotics, and Autonomous Systems, 5:41 1-44,, 2022.
[30] Alex Ray, Joshua Achiam, and Dario Amodei. Benchmarking safe exploration in deep rein- forcement learning. arXiv preprint arXiv:
7(1):2, 2019.
[31] Jingliang Duan, Zhengyu Liu, Shengbo Eben Li, Qi Sun, Zhenzhong Jia, and Bo Cheng. Adaptive dynamic programming for nonaffine nonlinear optimal control problem with state constraints.
Neurocomputing. 184:128-144 2022.
[32] Linrui Zhang, Li Shen, Long Yang. Shi- Yong Chen, Bo Yuan, Xueqian Wang. and Dacheng Tao. Penalized proximal policy optimization for safe reinforcement learning. In International Joint Conference on Artificial Intelligence, 2022.
[33] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. CoRR, 0es/1707.06347, 2017.
[34] John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference on machine learning, pages 1889-1897. PMLR, 2015.
[35] Tengyu Xu, Yingbin Liang, and Guanghui Lan. Crpo: A new approach for safe reinforcement learning with convergence guarantee. In International Conference on Machine Learning, pages 1 11480-1 1491. PMLR, 2021.
[36] Zengyi Qin, Yuxiao Chen, and Chuchu Fan. Density constrained reinforcement learning. In International Conference Machine Learning, pages
PMLR, 2021.
12

---

[37] Mo Chen, Sylvia L Herbert, Mahesh S Vashishtha, Somil Bansal, and Claire Tomlin. De- composition of reachable sets and tubes for a class of nonlinear systems. Trans. on Automatic Control, 2018.
[38] Sylvia L Herbert, Somil Bansal, Shromona Ghosh, and Claire J Tomlin. Reachability- based safety guarantees using efficient initializations. In Conf. on Decision and Control, 2019.
[39] Lew, L. Janson, R. Bonalli, and M. Pavone. A simple and efficient sampling- -based algorithm for general reachability analysis. In Learning for Dynamics & Control Conference, March 2022.
[40] Somil Bansal and Claire J Tomlin. Deepreach: A deep learning approach to high- -isensinnns reachability. In 2021 IEEE International Conference on Robotics and Automation (ICRA), pages 1817-1824. IEEE, 2021.
[41] Dongjie Yu, Wenjun Zou, Yujie Yang, Haitong Ma, Shengbo Eben Li, Jingliang Duan, and Jianyu Chen. Safe model-based reinforcement learning with an uncertainty-aware reachability certificate. arXiv preprint arXiv:22 10.0055,, 2022.
[42] Niklas Kochdumper, Hanna Krasowski, Xiao Wang, Stanley Bak, and Matthias Althoff. Provably safe reinforcement learning via action projection using reachability analysis and polynomial zonotopes. IEEE Open Journal of Control Systems, 2:79-92, 2023.
[43] Shangding Gu, Guang Chen, Lijun Zhang, Jing Hou, Yingbai Hu, and Alois Knoll. Constrained reinforcement learning for vehicle motion planning with topological reachability analysis. Robotics, 1 11(4):81, 2022.
[44] Mahmoud Selim, Amr Alanwar, Shreyas Kousik, Grace Gao, Marco Pavone, and Karl H Johansson. Safe reinforcement learning using black-box reachability analysis. IEEE Robotics and Automation Letters, 7(4):10665-1067 2022.
[45] Alessandro Abate, Maria Prandini, John Lygeros, and Shankar Sastry. Probabilistic reachability and safety for controlled discrete time stochastic hybrid systems. Automatica, 44(11):
2734, 2008.
[46] Sean Summers and John Lygeros. Verification of discrete time stochastic hybrid systems: A stochastic reach-avoid decision problem. Automatica, 46(12):1951-1661 2010.
[47] Nikolaos Kariotoglou, Kostas Margellos, and John Lygeros. On the computational complexity and generalization properties of multi-stage and stage-wise coupled scenario programs. Systems & Control Letters, 94:63-69, 2016.
[48] Abraham P Vinod and Mecko MK Oishi. Stochastic reachability of a target tube: Theory and computation. Automatica, 125:109458, 2021.
[49] Margaret P Chapman, Riccardo Bonalli, Kevin M Smith, Insoon Yang, Marco Pavone, and Claire Tomlin. Risk-sensitive safety analysis using conditional value-at-risk. IEEE Transac- tions on Automatic Control, 67(12):6521-6536 2021.
[50] Sven Gronauer. Bullet-safety-gym: A framework for constrained reinforcement learning. 2022.
[51] Emanuel Todorov, Tom Erez, and Yuval Tassa Mujoco: A physics engine for model-based control. In 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 5026-5033, 2012.
[52] Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. A Bradford Book, Cambridge, MA, USA, 2018
[53] Yinlam Chow, Ofir Nachum, Aleksandra Faust, Edgar Duenez-Guzman, and Mohammad Ghavamzadeh. Lyapunov-based safe policy optimization for continuous control. arXiv preprint 1000 2019.
[54] Dimitri P Bertsekas. Nonlinear programming. Journal of the Operational Research Society, 4843):334-334, 1997.
[55] H.K. Khalil. Nonlinear Systems. Pearson Education. Prentice Hall, 2002.
13

---

[56] Charles Dawson, Sicun Gao, and Chuchu Fan. Safe control with learned certificates: A survey of neural Iyаpunov, barrier, and contraction methods for robotics and control. IEEE Transactions on Robotics, 2023.
[57] Jason J Choi, Donggun Lee, Koushil Sreenath, Claire J Tommin, and Sylvia L Herbert. Robust control barrier-value functions for saftta-critical control. In 2021 60th IEEE Conference on Decision and Control (CDC), pages 681 6-21. IEEE. 2021.
[58] Eric Yang Yu, Zhizhen Qin, Min Kyung Lee, and Sicun Gao. Policy optimization with advantage regularization for long-term fairness in decision systems, 2022.
[59] Ppo lagrangian pytorch. 2022.
[60] Jiaming Ji, Jiayi Zhou, Borong Zhang, Juntao Dai, Xuehai Pan, Ruiyang Sun, Weidong Huang, Yiran Geng, Mickel Liu, and Yaodong Yang. Omnisafe: An infrastructure for accelerating safe reinforcement learning research. arXiv preprint arXiv:2305.09300 2023.
14

---

A Notation
reward function
h
safety loss function
V
cumulative discounted reward value function
V
cumulative discounted cost value function
reachability value function
Les,
instantancous violation indicator function
d
reachability estimation function (REF) of a given policy
o²
reachability estimation function (REF) of safest policy
predicted reachability estimation function (REF) safest policy
H maxx Hmin
upper bound of function h minimum non-zere zero value of of function h maximum value clip lagrange multiplier upper bound of function r safe set unsafe set
maxx
Rmax
Sy
S.
Sf
feasible set (persistent safe set) expectation taken over possible next states expectation taken over possible trajectories expectation taken over initial distribution
Eylnor P
E E P
ByNda
Table 1: Notation used in the paper.
B Gradient estimates
The Q value losses based on the MSE between the Q networks and the respective sampled returns result in the gradients:
Vo()) V,, an:)) (1) (r(se, ( 7 ((41:)
(K) = Ve (iik) (sx, - (h(s)) + 7
Similarly the REF gradient update is:
V Vep(sLiE) (p(s;; max(1 {))]
From the policy gradient theorem in [52], we get the policy gradient loss as:
VoJz -0 (n,s,, -p)ss)((s))p(())))) -
+ a pp(st) + pe(s.)] Vo log (a((s))))
and the stochastic gradient of the multiplier is
(w) Qo(st, ar))) (Pt)))
and Au is clipped to be in range [0, Amax] (in particular, projection operator To(Aw) =
arg min e(0.AAma) P| 12))
C Proofs
C.1 Theorem with Proof
Theorem 3. The REF can be reduced the following recursive Bellman formulation:
15

---

6² = max L.E..
E 0" (s')}:
P(o)
where s' ~ R, P(s) is a sample of the immediate successive state (i.e., s' ~ P(-|s, a sT-ls)) and the expectation is taken over all possible successive states.
Proof.
(5)
T(s) LATES
E
E
max (1 SES max (7Es.)
T
max L
E
max L
Pla) 9 M())
= max (1 sES
E
max s5e..
P(N,P(() P(T
= max sE
E s(m),((s)
0² (5(s')}
Note that we use the notation T ~ n,, P(s) ) to indicate a trajectory sampled from the MDP with transition probability P under policy starting from state and use the notation s' ~ P(s) to indicate the next immediate state from the MDP with transition probability under policy π starting from state 8. The third line holds because the indicator function is either 0 1, so if it's 1 then d" = P()) 1 else o (s) By P(s) max,,er\ sTes.
L
C.2 Proposition with Proof
Proposition 3.
The cost value function VT((s) (s) is zero for state if and only if the persistent safety is guaranteed for that state under the policy m
Proof. (IF) Assume for given policy म, the persistent safety is guaranteed, i.e. h(se|so holds for all 8, E for all possible trajectories T sampled from the environment with control policy æ. We then have:
(T)
=
E
hh(s
((s)
BEĒT
(ONLY IF) Assume for given policy V2T = 0. Since the image of the safety loss function h(s) non-negative real, and (T) the expectation of the sum of non non-negative real values, the only way V (s) = () is if h(s: 0, mT) O, Vs, E 7 for all possible trajectories sampled from the environment with control policy ı.
C.3 Proposition 2 with Proof
Proposition 4. If that produces trajectory 7 = {( N = } in deterministic MDP M starting from state 8, and 3m E N, m < сo such that 8m S7. then 3e >> where if discount factor 7 (1 e, 1), then the optimal policy π' of Main paper Equation will produce trajectory T'= ((4)) IN, $1 s). such that 3n N, < oc, 8 E ST and V (s) = min, V (s).
In other words the proposition is stating for some state if there is policy that enters its feasible set in finite number (m - 1) of steps, then by ensuring discount factor 7 close to 1 we can guarantee that the optimal policy πT of Main paper Equation 3 will also enter the feasible set in finite number of steps with the minimum cumulative discounted sum the costs. Note that x' will always produce trajectories with the minimum discounted sum of costs whether the state is in the feasible infeasible set of the policy by virtue its optimization which constrains V
Proof. We consider two cases: (Case m and (Case 2) >>
Case m 1: this case, there exists policy æ in which the the current state the feasible set of that policy. By definition, that means that in trajectory sampled in the MDP using that
16

---

policy, starting from state there are no future violations incurred in т. Thus (s) 0. Since T incurs the minimum cumulative violation, Vo (s) 0 trivially. Therefore, 8, the first state of the trajectory, is in the feasible set of n².
Case 2 m > 1: Since policy x produces the minimum cumulative discounted cost for a given state the core of this proof will be demonstrating that the minimum cumulative discounted cost of entering the feasible set (call this value Hx) is less than the minimum cumulative discounted cost of not entering the feasible (call this value H)), and therefore will choose the route of entering the feasible set.
The proof will proceed by deriving sufficient condition for Hg HN by establishing bounds on them.
We place an upper bound on the minimum cumulative discounted cost of entering the feasible set HE. Since 3r that enters the feasible set in m steps, entering the feasible set can be most the highest possible cost that ı incurs. Since the maximum cost at any state is Maxx, the upper bound is the discounted sum m steps violations Mmxx or
HE < Hinax (1 - -
(1 (1-7) 7)
We place a lower bound on the minimum cumulative discounted cost of not entering the feasible set N.. In this case, say the sampled trajectory, the maximum gap between any non-zero violations is w. By definition, the trajectory cannot have an infinite sequence of violation-free states since the trajectory never enters the feasible set. Therefore bound on the non-zero values of h. So the minimum cumulative discounted cost of not entering the feasible set must be least the cost of the trajectory with violation of Hmin intervals of steps. That is:
finite. Now recall Hiin the lower
(1""( (1-7w)
< HN
Now HE Hy will be true if the upper bound of H is less than the lower bound of H In other words Hg < H is true if:
H Hmax (1 - mm
#min(7"" (1 70)) (1 (1-
<
(5)
Rearranging, we get:
Hmax
(1 - 7) (7)
(6)
Huin
(1 (1- -1 1). (1 700)
Let's define the RHS of the Inequality 6 as the function v(7). Consider 7 (0, 1). It is not difficult to demonstrate that vT>) in this domain range is a continuous function and that left directional limit lim u(y) co. This suggests that there is open interval of values for (whose supremum 1) for which Hmax/ min < v(7) and so HE < H So we establish that 36 > O such that for E (1 (1-e,) e, 1), we satisfy the sufficient condition He < HN that the optimal policy will enter its feasible set.
Thus, prove that if there is policy entering its feasible set from state s, then there is range of values for that are close enough to 1 ensuring that the optimal policy of Main paper Equation 3 will enter its feasible set in finite number of steps with minimum discounted sum of costs.
C.4 Theorem with Proof
Theorem 4. Given Assumptions A1-A3 in Main paper, the policy updates in Algorithm 1 will almost surely converge to locally optimal policy for our proposed optimization in Equation RESPO.
We first provide an intuitive explanation behind why our REF learns to converge to the safest policy's REF, then proof overview, and then the full proof.
17

---

W
H'
y
Z
Spi
Snl
Si
Figure 7: The predicted feasible set converges to a safest policy's feasible set since the misclassified regions X and y are corrected over time.
C.4.1 Intuition behind REF convergence
The approach can be explained by considering what happens in the individual regions of space. Consider a deterministic enviromment for simplicity. As seen in Figure 7, there are two subsets of the initial state space: safest policy's "true" feasible set Sn and REF predicted feasible set Spt. and they create 4 regions in the initial state space S₁: W Sk n SpI, X = Shu n SpI, Z = S n Spr- Consider a point during training when the lagrange multiplier À is sufficiently large. For states in W, the set of correctly classified infeasible states, the algorithm will simply minimize cumulative violations (s), and thereby remain as safe as possible since the policy and critics learning rates are faster than that of REF X, which is the set of infeasible states that are misclassified is very small if we ensure the policy and REF are trained at much faster time scales than the multiplier and so when the agent starts true infeasible states, will by definition reach violations and therefore be labeled as infeasible. In y, the set of truly feasible states that are misclassified, the algorithm also minimizes cumulative violations, which by the definition of feasibility should be O. It will then have no violations and enter the correctly predicted feasible set Z. And when starting in states in 2, the algorithm will optimize the lagrangian, and since the multiplier À is sufficiently large, it will converge to policy that optimizes for reward while ensuring safety, i.e. no future violations, and therefore the state will stay predictably feasible in 2. this manner, REF's predicted feasible set will converge to the optimal feasible set, and the agent will be safe and have optimal performance in the feasible set and be the safest behavior outside the feasible set. Thereby, the algorithm finds locally optimal solution to the proposed optimization formulation.
Sr n Spi.
C.4.2 Proof Overview
We show our algorithm convergence to the optimal policy by utilizing the proof framework of multi-time scale presented in [8. 10, 53, 27]. Specifically, we have 4 time scales for (1) the critics, (2) policy, (3) REF function, and (4) lagrange multiplier, listed in order from fastest to slowest. The overview of each timescale proof step is as follows:
We demonstrate the almost sure convergence of the crities the corresponding fixed point optimal critic functions of the policy.
Using multi-timescale theory, we demonstrate the policy almost surely converges stationary point of a continuous time system, which we show has Lyapunov function certifying its locally asymptotic stability at the stationary point.
3 We demonstrate the almost that is safe insofar as the lagrange multiplier is sufficiently large.
convergence of the REF function to the REF of the policy
4 We demonstrate the almost sure convergence of the lagrange multiplier a stationary point similar to the proof in the policy timecale.
Finally, we demonstrate that the stationary points for the policy and lagrange multiplier form saddle point, and so by local saddle point theorem we almost surely achieve the locally optimal policy of our proposed optimization.
18

---

C.4.3 Proof Details
Proof. Step (convergence of the critics V, and VN updates): From the multi-time scale assumption, we know that and will convergence on faster time scale than the other parameters 0, and w. Therefore, we can leverage Lemma 1 of Chapter 6 of [10] to analyze the convergence properties while updating Ti and Ng by treating 8, Ç. and as fixed parameters 8k, Ek. and wk. In other words, the policy, REF, and lagrange multiplier are fixed while computing Q** (s, a) and Qa (s, (s,a). a). With the Finite MDP assumption and policy evaluation convergence results of [52], and assuming sufficiently expressive function approximator (i.e. wide enough neural networks) to ensure convergence global mininum, we can use the fact that the bellman operators B and Be which are defined as
B[Q[(s, r(s,a) +7
E
[Q(''aa))
B(Q.((s,a) - h1()) +7
ata Q0((',
E
are 7-contraction mappings, and therefore as k approaches we can be sure that Q(s, a; mk) Q(s,a;n") TTh (s, a) and Qels, a: Hi)) Qe a: xx)) Qe (s, a). So since 7) and Kk converge to 17" and x=, we prove convergence of the critics in Time scale 1.
Step 2 (convergence of the policy update): Because and updated on slower time scales than 0, we can again use Lemma
Chapter 6 of [10] and treat these parameters are fixed at &a and We respectively when updating Os. Additionally in Time scale 2, we have ||Q(s, 178) Q(s a;;"")l - and [[Qu(s, o; k2) Qc(8, a; x=)]| + 0 almost surely. Now the update of the policy 0 using the gradient from Equation 4 is:
O Tol0; - (L Ex, wk) (k)) 00=
Tel0x (2)))111 (z) PEc (st)
+ [.((s,,a))\>_{( - PEN (sx)) + Pe, (st)]] log x (urlss; 0) - Ex, 00 + 50k+1 + 60.)]
-'el0>- -
where
60 Σ PT (s)
Pe, (s+)
+ [:) - Pec (8i)) + Pe. (s:) log क (a,1s;; 1)
-1 Qy ar) Pea (3t)] + Qo or
)r) [ (1 Pe, (st)) + PEr (sx) V log (a, (rc 0) l=
and
50. = Σ (d((s))Pt)) (5t, asls))
62.00
->'1-Q as))] Ps, (s:) + Qelsi, 05 Rx) Aw
pc, (s:)) + Pea (s:)
-Volog T( s4; 0) -==
+
(8), (s), PE, (x:)
Q. Tex (si, (1
Pe. (s:)) )) + Pe. (st))
Vo log TT |8; 0) 10000
19

---

Lemma 1: We can first demonstrate that 60k+1 is square integrable. In particular,
E|| 60 Fo.x
- V Tals: 00 Aata ( 2o0) (10((s) as 111 Peu (s)ll
(1 0; |Iaulee : 1|1 Pea (s) + [IPe((())12
min min(f((|ss;// (aass > (110(5 111 Pee (s)
Vos 010
+ 11Qa(s,
| ||| Pex (s) + +Ilpe (+)11
Note that Fo.: a(mm, 80m; m I k) the filtration for 0% generated by different independent trajectories [8]. Also note that the indicator function is used because the expectation of ||60x+ Il is taken with respect to p and nd (s, also) = 0 if π (als; 0s) O. From the Assumptions on Lipschitz continuity and Finite MDPs reward and costs, can bound the values of the functions and the gradients of functions. Specifically
00 11 < K1(1 10x113))
Rmax
1 1-
Hmax
(s) 5 1
11> < Amaxi
Ps. (s) 12 S 1,
[pc. (s) S
where K2 is a Lipschitz constant. Furthermore, note that because we are sampling, (aass; 0%) will take on only a finite number of values, so its nonzero values will be bounded away from zero. Thus we can say
(als: (x)[ 0x) 0} K₂
for some large enough K2. Thus using the bounds from these conditions, we can demonstrate
11160k++11 s K1 + 110x113)) Kz( Rmax
1-7 1+ Hmax
1-7 (Amax 1 1+ 1)) < oo
Therefore 80 is square integrable.
Lemma 2: Secondly, demonstrate 50. + 0.
60, Edo( p (si, asls0) >'[(Q(s), - 17Th
Pea (s:)
81.02
1-Qe(s a(ik)) + ( (P. (s:)) + PEs (st) log (aals;
$ Σ (a(su) (si, (sss) ( ((((((()) 10 (s:)
(- Qo(si, asi kx) + Qo,s ai [)]A>[1 - (8:)) + (o (1)
$ Σ (s)) pro (st, a0) [1[ az a.: ms) Q(
(s.
+ || - (s: a; + a, a;;"" (1 Pe, (8:)) + Pe. (s:)]] lo (agls:: 0)10=
20

---

And because we have [|Q ma) Q(s, (( + 0 and ||Qe(s, - Qc(s,a;k*)l + 0 almost surely, we can therefore say 50, - 0.
Lemma 3: Finally, since (0)=(0) is a sample of (0 Ex, wn,ww))o= based on the history of sampled trajectories, we conclude that 1 [o O.
From the 3 above lemmas, the policy 0 update is stochastic approximation of a continuous system (t)) defined by [10]
i = Tel VoL(_0))
which
Te [M A
Po(0 + (M()) (0)
re())
lim OK#-0
or in other words the left directional derivative Te (0) in the direction of ((). Using the left directional derivative Tel-Vo (o, [))) in the gradient descent algorithm for learning the policy Ty ensures the gradient will point in the descent direction along the boundary θ when the update hits its boundary. Using Step 2 in Appendix A.2 from [8]. we have that dL &, w)/dt /t L w, Tel-VeL(0, E, w) < 0 and the value is non-zero if [[Te-- E, w.]l of
Now consider the continuous system (t). For some fixed and w. define Lyapunov function
(0) L( .0",...
where is local minimum point. Then there exists a ball centered at 0* with a radius p such that 4O E Bg- (p) = [01|0-001| S p}. (0) is locally positive definite function, that is (c. 2 0. Using Proposition 1.1.1 from [54]. we can show that Tel-VeL(C w.w]le=--
meaning 0 is stationary point. Since dL, //d) s O, through Lyapunov theory for asymptotically stable systems presented in Chapter of [55], we can use the above arguments to demonstrate that with any initial conditions of 0(0) E Bg- (p)(p), the continuous state trajectory of 0(t) converges to 0*. Particularly, L(0", E.W) & L(O(t), < L(B(0), for all t > O.
Using these aforementioned properties, as well as the facts that 1) VoL(O,E,w) is Lipschitz function (using Proposition 17 from [8]), 2) the step-sizes of Assumption on steps sizes, 3) 80x+1 square integrable Martingale difference sequence and 80, is vanishing error almost surely, and 4) 0g. E O, Yk implying that sup, ||0x|| < oo almost surely, we can invoke Theorem of chapter in [10] to demonstrate the sequence (0x}, 0% E θ converges almost surely to the solution of the ODE defined by Equation 7, which additionally converges almost surely to the local minimum 0" O.
Step 3 (convergence of REF Ps updates): Since w is updated on a slower time scale that &, we can again treat fixed parameter W/ when updating Ç. Furthermore, in Time scale we know that the policy has converged to a local minimum, particularly | 0 (Ex, wx)] = O. Now the bellman operator for REF is defined by
(x)) = max(1ees.:)
[p('']]
p(o)
We demonstrate this is a contraction mapping as follows:
(s)p - Bb))
maxxx 7
I P(s)
[p(s')]) max max(1 7 E
swn.p(s) [ps')]}
S hy E [p(')] -7 P(s)
E
[D(')]]
P(s)
>
(p(s') - -p(s')1
P(a),
S sup (p(s) - p(s) = 71pp - 20
So we say that p(s; Ex) will converge to p(): as k + under the same assumptions of the Finite MDP and function approximator expressiveness in Step 1. Therefore, Te. will also converge to R TT-(E" wx)) k + co. And because To is the sampling policy used to compute p(s: p Te (er (e:)))))) (s: (s).
21

---

Notice that x is a locally minimum optimal policy for the following optimization (recall A is treated as constant in this timescale):
min Sn (n))(-1s)
E
Q" (s. p1-p (s) ((L-P'(s)){) + p
and therefore also locally minimum optimal policy for optimization:
p((s)
min E
E
(s, + (s, a
(f) >0
anido awo
(1-p(s))
min E
Q: a) (s)
arvdo a)(((1)))
Since (e)
(1-p((s)) 0, and the Q functions always nonnegative, can know that x is least safe as (i.e., its expected cumulative cost is most that of) a locally optimal policy for the
optimization:
min E E
(8)
do (~()()
As A approaches Amax. which in turn approaches 0o, the local minimum optimal policies of Equation approach those of the optimization ~ arg min, Egddo Easx(11s) Qr (s, a) arg min, Bgwdg (-))) Q7 (8, a). Therefore, the feasible set of the REF pe will approach that of the REF p=
Step 4 (convergence of lagrange multiplier A update): Since A is the slowest time scale, have that |00 8² (w)ll 0. 1 g [w)]] 0, and [|Qa(s, a; Kx) Qe (s, a)ll = 0 almost surely. Furthermore, due to the continuity of V L0, we have that L(, (,w)le (a=) ex LO,, w) 10=000000 (==) (wx),w==>
almost surely. The update of the multiplier using the
gradient for Equation is:
Wk+1 = Palwx +
Tnlww (a 0r mx) p(se: V wh
= Talwx + ((.))
wen + Swk+t)l
where
own+1
Qa(se, dei Kx) ploc; En Vadoluu Σ P (st (s),)))000)) (s a;)ll pe (s:))V (w
Siias
(.)) p -
=- dFth
(si, a:l V
Sija;
+ (e az [1 p(su (0: [x)] - a. (st, at) 1 Ex)]+
Qa Thh at) p(s(p((ss)) Ew]] Q. ac) pp((s)]++
Qe 3o (st, [1 - (s:) Vo
Σ P (ss: as (slso)) 10 (st, a:)] p-- (8:)) Ver loww)
+ (Qc azs Rx) - Q. Th (st, - E()
Qe Teh (st, (t) /p (st) [+))+
Qa Th (st, at) (
Now, just as in the 0 update convergence, can demonstrate the following lemmas: Lemma 4: Swk+1
square integrable since
H Hmax
1|l|ow++1113 [ 2
1. K3(11 + 1 oc
1 1-7
22

---

for some large Lipschitz constant K3. Note that Fu,k = (w owin, m S k) is the filtration for wk generated by different independent trajectories [8].
Lemma 5: Because [|Qr(st, at; KR)) Qe ThE (st; ae)lla 0 and [|p((s)) p(s);E))ll> -> 0 and
Q² 0,]]1 pc- (+t)] V.Nolu=ws. is sample of Q (8); az][1 - pg- (st) V Vwdwwwwwe we con-
clude that E[owx+1| Fu,k] = O almost surely.
Thus, the lagrange multiplier update is a stochastic approximation of a continuous system w(t) defined by [10]
e = Tn(l-Vlvv V. (0)
(9)
with Martingale difference error of dwr and where Ta is the left direction deriva- tive defined similar to that in Time scale 2 of the convergence of 0 update. Us-
ing Step 2 in Appendix A.2 from [8], we have that dL(6 (w))s=)))) 2 and the value is non-zero
V V.,, E, (o
To( [V E, (w) # O.
For a local maximum point w", define a Lyapunov function as
((w)= L(O (w),
L(O (()
Then there exists a ball centered at w" with a radius p' such that Vo E (D') = fw|llw w*ll p') J. C(w) is locally positive definite function, that is L(w)) O. Also, dl(w(l))/d -dL(0 (w), (w), /ll S and is equal only when Yo LO, (,w))o=8-(w) (. = 0, so therefore wt is a stationary point. By leveraging Lyapunov theory for asymptotically stable systems presented in Chapter 4 of [55] we can demonstrate that for any initial conditions of w E B (p'), the continuous state trajectory of (f) converges to the locally maximum point w'.
Using these aforementioned properties, as well as the facts that 1) I ( ("),,, w) is Lips- chitz function, 2) the step-sizes of Assumption on steps sizes, 3) (wk+1) } is stochastic approximation of (t) with a Martingale difference error, and 4) convex and compact properties in projections used, we can use Theorem 2 of chapter 6 in [10] to demonstrate the sequence {ux) ) converges almost surely to locally maximum point w" almost surely, that is L(O (w), E (w))w") Z ((O" (")) (w),
From Time scales 2 and 3 we have that (w), (w)),w S L(,,E, while from Time scale 4 we have that (W), (w)) 2 L(0" (w), ("))), ww) Thus, (W() (w)), s (w)),, (w), w²) < L(0, (.)" Therefore, (0*, E", w*) is local saddle point of (0, (.),. In- voking the saddle point theorem of Proposition 5.1.6 in [54], we can conclude that π T-1::0)) is locally optimal policy for our proposed optimization formulation.
C.4.4 Remark on Bounding Lagrange Multiplier
We can say our algorithm learns an REF that is closer to an optimally safe policy's REF as we take Aunx - 0c. Nonetheless, we want to put a bound on the Amax- This Amax must be large enough so that choosing a policy that can reduce the expected cost returns by some non-zero amount is prioritized over increasing the reward returns. So any change in the reward critic terms must be less than any change in the cost critic term. If HA is the minimum non-zero difference between any two cost values, and Pmin is the minimum sampled non-zero likelihood of reaching particular state and a point the sample trajectory, then we can bound the maximum change in the reward returns and the maximum change on the weighted cost returns:
Riax
A E [v(s) S
sddg
Φ(s)
[Vo(s) (A + Φ(s)
JT Ha. Pmin (A+
< A E
(1 ((s)) )
(1 (())
souda
23

---

So we can find the bound for Amax:
A E (V(s) (1 (0(s))s)]]
< A E [V((s)
(A (1 (((s)) + +
arudo
srudo
((s)
A E [(s)] < A
E (c(s) (A + (1 (1-((s))
sndda
gr-da
Rmax
(18)
1-9 <² HA Pmin () + (1 (()))
Rmax
<x+ o(8)
(1 (1-2) TT Ha Pmin
(1-)(s))
Rmax
((s)
<
. HA. Pmiin
(1 ((s))
The second line holds since simply rearranging the comparative weightages of the reward and cost returns. Now optimization). Thus, if À (1-7)->² 2 -Ha-
d(s)
(recall that if ((s) 1, then is irrelevant in the lagrangian then minimizing the cost returns is prioritized over
(I-diss)
Ryaa
maximizing reward returns.
D
Complete Experiment Details and Analysis
D.1
Baselines
We compare our algorithm RESPO with other safety RL baselines, which can be divided CMDP class and hard constraints class, and unconstrained Vanilla PPO for reference.
CMDP Approaches
Proximal Policy Oprimization-Lagraggee PPOLag is primal-dual method using Proximal Policy Optimization [33] based off of the implementation found in [7]. The lagrange multiplier is scalar learnable parameter.
Constraint-Recteoo Rectified Policy Optimization. CRPO [35] is primal approach that switches between optimizing for rewards and minimizing constraint violations depending on whether the constraints
violated.
Penalized Proximal Policy Optimization. P30 [32] is another primal approach based on applying the technique of clipping the surrogate objectives found in PPO [33] to CMDPs.
Projection-Basse Constrained Policy Optimization. PCPO [3] is trust-region approach that takes a step in policy parameter space toward optimizing for reward and then projects this policy to the constraint set satisfying the CMDP expected cost constraints.
Hard Constraints Approaches
Reachability Constrained Reinforcement Learning. RCRL [27] is primal-dual approach where the constraint is on the reachability value function and the lagrange multiplier is represented by a neural network parameterized by state.
Control Barrier Function. This CBF-based approach inspired by the various energy-based certifi- cation approaches [56, 17, 18, 11, 57, 58). This is implemented primal-dual approach where the control barrier-based constraint h(s) P- h(s) 0 is to ensure stabilization toward the safe set.
Feasible Actor Critic. FAC [9] is another primal-dual approach similar RCRL (i.e. it uses the NN representation of the lagrange multiplier parameterized by state) except that the constraint in FAC based on the cumulative discount sum of costs lieu of the reachability value function. is important to note that FAC is originally meant for the CMDP framework (with some positive cost threshold), but we adapt to hard constraints by making the cost threshold x = 0. We do this to make a better comparison between an algorithm that relies on using the lagrange multiplier represented as NN to learn feasibility with our approach of using our proposed REF function to learn the feasibility likelihood - both approaches enforce hard constraint on the cumulative discounted costs.
24

---

D.2 Benchmarks
We compare the algorithms on a diverse suite of environments including those from the Safety Gym, PyBullet, and MuJoCo suites and a multi-constraint, multi-dron environment.
Safety Cym. In Safety Gym [30], examine CarGoal and PointButton which have 72D and 76D observation spaces that include lidar, accelerometer, gyro, magnetometer, velocimeter, joint angles, and joint velocities sensors. In the CarGoal environment, the agent has 72D observation space and is supposed to reach a goal region while avoiding both hazardous spaces and contact with fragile objects. PointButton, the point agent has 76D observation space and must press series of specified goal buttons while avoiding 1) quickly moving objects, 2) hazardous spaces, 3) hitting the wrong buttons.
Safery PyBullet. In Safety PyBullet [50], we evaluate in BallRun and DroneCircle environments. In the BallRun environment, the ball agent must move fast possible under the constraint of speed limit, and it must be within some boundaries. In DroneCircle, the agent based on the Asc Hummingbird quadrotor and is rewarded for moving clockwise in circle of fixed radius with the constraint of remaining within a safety zone demarcated by two boundaries. Note that we use this environment evaluate our algorithm and the baselines in stochastic setting. We ensure the MDP is stochastic by adding a 5% gaussian noise to the transitions per step.
Safety MuJoCo. Furthermore, we compare the algorithms in with complex dynamics in MuJoCo. Specifically, we look at HalfCheetah and Reacher safety problems. In Safety HalfCheetah, the agent must move quickly as possible in the forward direction without moving left of x -3. However, unlike the standard HalfCheetah environment, the reward is based on the absolute value of the distance traveled. In this paradigm, it is casier for the agent to learn to quickly run backward rather than forward without any directional constraints. In the Safety Reacher environment, the robotic arm must reach certain point while avoiding an unsafe region.
Multi-Drone environment. We also compare an environment with multiple hard and soft constraints. The environment requires controlling two drones to pass through tunnel one at a time while respecting certain distance requirements. The reward given for quickly reaching the goal positions. The two hard constraints involve (H1) ensuring neither drone collides into the wall and (H2) the distance between the two drones more than 0.5 to ensure they do not collide. The soft constraint is that the two drones within 0.8 of each other to ensure real-world communication. It is preferable to prioritize hard constraint H1 over hard constraint H2, since colliding with the wall may have more serious consequences the drones rather than violations of overly precautious distance constraint as we will show, our algorithm RESPO can perform this prioritization in its optimization.
25

---

D.3 HyperparametersOOhher Details
Hyperparameters for Safe RL Algorithms
Values
On-policy parameters
Network Architecture
MLP
Units per Hidden Layer
256
Numbers of Hidden Layers
2
Hidden Layer Activation Function
tanh
Actor/Critic Output Layer Activation Function
linear
Lagrange multiplier Output Layer Activation Function Optimizer
softplus
Adam
Discount factor oy
0.99
GAE lambda parameter
0.97
Clip Ratio
0.2
Target KI. divergence
0.1
Total Env Interactions
9c6
Reward/Cost Critic Learning rate
Linear Decay le-3 +
Actor Learning rate
Linear Decay 3e-44 4 - 0
Lagrange Multiplier Learning rate
Linear Decay 5 -
Number Seeds algorithm per experiment
5
RESPO specific parameters
REF Output Layer Activation Function
sigmoid 1e + 0
REF Learning rate
CBF specific parameters
0.2
RCRL/FAC Note
Lagrange Multiplier
2-Layer, MLP
(other algs just use scalar parameter)
Table Hyperparameter Settings Details
To ensure fair comparison, the primal-dual based approaches and unconstrained Vanilla PPO were implemented based off of the same code base [59]. The other three approaches were implemented based [60] with the similar corresponding hyperparameters the primal-dual approaches. We run our experiments on Intel(R) Core(TM) i7-8700 CPU @ 3.20GHz with 6 cores. For Safety Gym, PyBullet, MuJoCo, and the multi-drone environments, each algorithm, per seed, per environment, takes 4 hours to train.
26

---

D.4 Double Integrator
10.0
RESPO (ours)
RCRL
7.5
Safe set boundry
5.0
Start
Feasible Set
0.0
-25
-500
-7.5
Infeasible Set
10.0
10.0
-7.5
5.0
-2.5
0.0
2.5
5.0
7.5 10.0
Figure 8: Comparison of the trajectories in the Double Integrator Environment of an agent controlled by policies obtained by RCRL (in red) and our proposed algorithm RESPO (in green) when starting from the infeasible set (but still within the safe set). Notice how our approach actively enters the feasible set (blue region), while RCRL fails to so. The level set demarcating
feasible/ifeasihle set boundary is black. safe set (i.c. the set of states that have no violations) is the region within the dashed purple square. The infeasible set is in yellow.
We the Double Integrator environment as a motivating example to demonstrate how performing constrained optimization using solely reachability-bene value functions as in RCRL can produce nonoptimal behavior when the agent outside the feasiblity set. Double Integrator has dimensional observation space [x1, .22. dimension action space E [-0.5, 0.5). system dynamics is á [I2, a), 5. Particularly, we make the cost as 1 if [|s||oe > 5, and otherwise to emphasize the importance of capturing the frequency of violation during training.
and constraint as ||
We train an RCRL controller and RESPO controller in this environment, and the results are visualized in Figure 8. The color scheme indicates the learned reachability value across the state space while the black line demarcates the border of the zero level set. We present the behavior of the trajectories of RCRL and RESPO. Because the RCRL optimizes for reachability value function when outside the feasible set, simply minimizes the maximum violation, which as can be seen does not result in the agent reentering the feasible set since it is uniformly equal to or near 1 in the infeasible set. This is since permits many violations of magnitude same or less than that of the maximum violation. On the other hand, RESPO optimizes for cumulative damage by considering total sum of costs, thereby re-entering the feasible set.
27

---

D.5
Safety Gym Environments
CarGoal Cumulative Costs
CarGoal Cumulative Rewards
PPOLag
60
FAC
20
RESPO (ours)
CBF
10
Vanilla PPO
40
CRPO
0
-10
2
8
166
106
PointButton Cumulative Rewards
PointButton Cumulative Costs
1.5
20
1.0
10
0.5
0
0.0
0
2
4
6
0
2
6
8
Figure 9: Closer look at comparison of algorithms in Safety Gym CarGoal and PointButton Environments.
In the CarGoal Environment, our approach achieves the best performance among the safe RL algorithms while being within the acceptable range of cost violations. It is important note that our algorithm has no access to information on the cost threshold. In PointButton, RESPO achieves very high reward performance among the safety baselines while maintaining among the lowest violations.
RESPO:
PPOLag: In both Safety Gym environments, PPOLag maintains relatively high performance, albeit less than our approach. Nonetheless, always converges to the cost threshold amount of violations for the respective environments.
RCRL: RCRL has either high reward and high violations low reward and low violations. It learns very conservative behavior in CarGoal environment where the violations down but the reward performance can also be seen to be sacrificed during training. For PointButton, RCRL achieves slightly higher reward performance but has over 3x the number of violations as RESPO.
Using NN to represent the lagrange multiplier in order capture the feasible sets seems to produce very conservative behavior that sacrifices performance. In both CarGoal and PointButton the reward performance and cost violations very low. This can be explained because the average observed lagrange multiplier across the states quickly grows, even becoming 9x that of scalar learnable lagrange multiplier in RESPO.
FAC:
CBF: The CBF approach has low reward performance both the Safety Gym benchmarks and its cost violations are quite high.
CRPO, P30, & PCPO: These CMDP-based primal approaches have mediocre reward performance but, with the exception of CRPO, achieve violations within the cost threshold. CRPO, however, has high cost violations both CarGoal and PointButton.
Vanilla PPO: This unconstrained algorithm consistently has high rewards and high costs, so maxi- mizing rewards does not improve costs in these environments.
28

---

D.6
Safety PyBullet Environments
X10*
DroneCircle Cumulative Rewards
DroneCircle Cumulative Costs
1.0
PPOLag
RCRL
0.8
FAC
RESPO (ours)
30
CBF
Vanilla PPO
20
CRPO
0.4
P30
PCPO
10
0.2
2
4
2
8
1e6
106
x10?
BallRun Cumulative Rewards
x10#
BallRun Cumulative Costs
2.5
3.0
2.0
2.0
1.5
1.0
1.0
0.5
0.0
0.0
2
0
8
le6
le6
Figure 10: Closer look comparison of algorithms in Safety PyBullet DroneCircle and BallRun Environments.
In the both BallRun and DroneCircle, our approach achieves the highest or among the highest reward performance compared to the other safety baselines. Furthermore, RESPO converges to almost 0 constraint violations for both environments.
RESPO:
PPOLag: In DroneCircle, PPOLag has the best reward performance. Although its costs violations are around the cost threshold, it is much higher than RESPO. On the other hand, in BallRun, PPOLag has very low reward performance.
We again see RCRL take on behavior with extremes - has low reward and cost violations in Drone Circle and has high reward and cost violations in BallRun. Constraining the maximum violation with the reachability value function as RCRL does seems to provide poor safety in an environment with non-tangible constraints (i.e. speed limit in BallRun).
RCRL:
FAC: While BallRun, we see FAC have the same low reward and low violations behavior, DroneCircle shows an instance where FAC can achieve decently high rewards while maintaining low violations.
CBF: In DroneCircle, the CBF approach has low rewards and relatively low violations; in RallRun, has bit higher rewards compared to all the low performance algorithms with very low violations.
CRPO, P3O, & PCPO: These CMDP- based primal approaches have mediocre reward performance in DroneCircle and very low performance in BallRun. Nonetheless they achieve violations within the cost threshold.
Vanilla PPO: This unconstrained algorithm consistently has high rewards and high costs (sometimes out of the scope of the plots), so maximizing rewards does not improve costs in these environments.
29

---

D.7
Safety MuJoCo Environments
Reacher Cumulative Costs
Reacher Cumulative Rewards
-1.2
PPOLag
15
RCRL
FAC
-1.3
(ours)
Vanilla PPO
CRPO
-1.4
P30
PCPO
-1.5
6
2
8
166
166
HalfCheetah Cumulative Rewards
1.0
x10#
HalfCheetah Cumulative Costs
0.8
0.6
2.0
0.4
0.0
0.2
-2.0
0.0
8
leb
le6
Figure 11: Closer look comparison of algorithms in Safety MuloCo Reacher and HalfCheetah Environments.
Note on HalfCheetah: The rewards for HalfCheetah are based on the absolute distance traveled in each step. Without the cost metric constrain backward travel, is easy learn to run backward, as is the behavior learned in unconstrained PPO.
RESPO: Our approach achieves the highest reward performance among the safety baselines in HalfCheetah and decent reward performance in Reacher. Interestingly. RESPO also has 0 constraint violations in HalfCheetah and the second lowest constraint violations Reacher.
PPOLag: The performance in Reacher for PPOLag similar as in most of the previous environments:
decently high rewrad, cost the threshold. However, for HalfCheetah, interesting PPOLag learns to maintain the violations well below the cost threshold.
RCRL: We see yet again RCRL has high reward follow by very high constraint violations.
FAC: This approach has decent reward performance in Reacher and low reward performance in HalfCheetah. However, interestingly, FAC has high cost violations though below the cost threshold.
CBF: In Reacher, the CBF approach has conservative behavior with both low reward and low cost violations. But in HalfCheetah, has very low reward performance and very high cost violations (not in the plot since its order of magnitude larger than the visible range).
CRPO, P3O, & PCPO: These CMDP-based primal approaches have decent reward performance in Reacher while maintaining violations within cost threshold. In HalfCheetah, however, they achieve low performance and low cost violations.
Vanilla PPO: This unconstrained algorithm consistently has high rewards and high costs (sometimes of the scope of the plots), so maximizing rewards does improve costs in these environments.
30

---

D.8
Hard and Soft Constraints
RESPO (ours)
PPOLag
0.6
0.6
0.4
0.2
0.2
0.0
4012
-02
0.2
0.4
0.4
00.6
-1.5
-1.0
-0.5
0.0
0.5
1.0
1.5
-1.5
-1.0
-0.5
0.0
0.5
1.0
1.5
RCRL
FAC
0.6
0.6
0.4
0.4
0.2
6,00
0.0
0.0
Number 100
0.2
-022
-0.4
-0.6
-0.6
-15
-1.0
-0.5
0.5
1.0
-1.0 -0.5
0.5
1.0
Figure 12: Closer look at comparison of RESPO with baselines trajectories in hard & soft Constraints multi- Drone control. Starting at gold circles, drones must enter the tunnel one time and reach green star while avoiding the wall and satisfying distance constraints. The colors indicate time along the trajectories.
RESPO:
We manage multiple hard and soft Constraints by extending framework optimize the following Lagrangian:
min max [(TT,)) = E
[I-V + Aao (Vir(s) x) Anoa Viez(()) (1 - Phoz (s)
srdd
+ +Vice (hoe(s) + dhel Vie (8)] Phei (8)) -1-Phei
+ Vhoi (+) Phez
(10)
The subscripts hel indicates the first hard constraint (i.e. wall avoidance), he2 indicates the second hard constraint (i.e. drone cannot be too close), and sc indicates soft constraint (i.e. drone cannot be far) they are all based on discounted sum of costs. Recall V V*((s is reward returns. We color coded the corresponding parts of the optimization. Notice how we learn different REF for each hard constraint. Also notice that the feasible set of the first hard constraint Phc1 placed to ensure prioritization of the first hard constraint. As can be seen in the top left plot of Figure 12, our approach successfully reaches the goals and avoids the walls. To enable mobility of the top drone to pass through the tunnel with wall collision, the second hard constraint is violated temporarily in the blue to cyan time period. Furthermore to allow the bottom drone to pass through the tunnel, the soft constraint is violated during the green orange time period. Nonetheless, RESPO successfully manages the constraints and reward performance via Equation 10 optimization.
manner so as
PPOLag, RCRL, FAC: The optimization formulation for these approaches is as follows:
min max [[(T,))
V/ (s) Ase (V (z((s) (8) x) Anea Viee(8)
Abea Vhot (s)
(11)
For PPOLag and FAC, all the constraint value functions are discount sum of cost. For RCRL, (E(() is based on discount sum of costs but V (s) and (s)g(s) are based on the reachability value function. Furthermore, in PPOLag,
the lagrange multipliers are learnable scalar parameters. In FAC and RCRL all the lagrange multipliers are NN representations parameterized by state. These formulations are not able provide framework for the prioritization of the constraint satisfaction all the constraints are treated the same, weighted only on the learned lagrange multipliers. As can be seen in the other three images in Figure 12, the algorithms cannot manage the multiple constraints, and invariably collide with the wall.
31

---

D.9
Ablation - Learning Rate
CarGoal Cumulative Costs
CarGoal Cumulative Rewards
80
RESPO w/ I00.01
20
w/
RESPD
RESPO w/ 1-1
10
RESPO w/ 10000
0
20
-10
2
8
166
106
PointButton Cumulative Rewards
PointButton Cumulative Costs
100
80
60
40
-5
20
4
le6
1e6
Figure 13: Closer look at Ablation study on learning rate REF.
We performance Ablation study of varying the learning rate of the REF function to verify the importance of the tealti-timescale ussumption. Particular, we compare our algorithm's 's approach of placing the learning rate of the REF between the policy and lagrange multiplier with making the REF's learning rate in various orders of magnitudes slower and faster. Our approach with the learning rate satisfying the multi-timescale assumption experimentally appears to still have the best balance of reward optimization and constraint satisfaction. Particularly when we change the learning rate by one order of magnitude (i.e. 10 x0.1), we see the reward performance reduce by around half and while the cost violations generally don't change. But when we change the learning rates by another order of magnitude, there reward performance effective becomes zero and the cost violations generally reduce further. By increasing the learning rate of the REF function, we can no longer guarantee that the REF convergences near the optimally safe REF value. Instead, becomes the REF of the policy in question. So instead, the optimization can learn to "hack" the REF function to obtain a policy (and lagrange multiplier) that is not local optimal for the optimization formulation. On the other hand, when the learning rate is too slow, the lagrange multiplier quickly explodes, thereby creating a very conservative solution notice the similarity of the orange line in Figure 13 with learning rate 0.01 times that of standard in training behavior with PPOLag where in the ablation study on optimization.
32

---

D.10
Ablation Optimization
CarGoal Cumulative Costs
CarGoal Cumulative Rewards
35
80
15
40
-5
20
PPOLag, x
RCRL with REF
RESPO (ours)
-5
8
1e6
1e6
PointButton Cumulative Rewards
PointButton Cumulative Costs
x10*
30
1.6
20
1.2
0.8
10
0.4
0-
0.0
0
4
6
8
1e6
1e6
x30*
BallRun Cumulative Rewards
x10
BallRun Cumulative Costs
3
2.0
2
1.0
-1
0.0
le6
1e6
x10P
DroneCircle Cumulative Rewards
DroneCircle Cumulative Costs
8.0
30
6.0
4.0
10
2.0
0.0
2
4
2
8
1e6
Figure 14: Closer look Ablation study hard constraints optimization frameworks.
33

---

In this ablation study, we examine the various optimization frameworks within the context of hard constraints, Particularly, we compure our RESPO framework with RCRL and CMDP. However, for RCRL we implement using our REF function method while still keeping the reachability value function. For CMDP, we make the cost threshold X 0. These comparisons answer important questions about our design choices specifically is it sufficient to simply to just use the REF component or to just learn the cost returns alone? From this ablation study, we propose that though we have provided theoretical support for adding each of these design components individually, in practice they are both required together in our algorithm. In RCRL implemented with our REF, we generally see decently high rewards but the cost violations problems of the reachability function again if the agent starts or ever wanders into the infeasible set, there is no guarantee of (re)entrance into the feasible set. So the agent can indefinitely remain in the infeasible set, thereby incurring potentially an unlimited number of constraint violations. In PPOLag with X 0, both the reward performance and constraint violations hard constraints versions of these purely learning-baan based methods, even when using the cumulative discounted cost rather than reachability value function, the reward performance is very low because the lagrange multiplier becomes too large quickly and thereby overshadows the reward returns in the optimization. Ultimately, both the REF approach and the usage of the cumulative discounted costs are important components of our algorithm RESPO that encourage a good balance between the reward performance and safety constraint satisfaction in such stochastic settings.
always very large. This highlights the
very low. By using such
34


Reviews:
[{"review_id": "A4yBLA70GA", "reviewer": "Reviewer_yyXc", "summary": "The paper proposes a new algorithm that may handle hard and soft constraints, in which the policy optimization and Hamilton-Jacobi reachability are leveraged to ensure safety. Moreover,  experiment results on safety gym, safety PyBullet, and safety MuJoCo also show the good performance of their algorithm.", "questions": "1. Could you analyze the difference between RESPO and CRPO regarding the reward update and cost update?\n2. If the agent does not find the safe action, will it be stuck at a point?\n3. How do you define the reachable set when considering reward performance?", "limitations": "1. The balance between reward and cost is not addressed well, in the experiments, as shown in Figure 3, although RESPO can ensure safety, the trajectory is longer than other baselines, and also not smooth.\n2. Some related papers are not mentioned in the study, e.g., [Kochdumper, N., et al., 2023], [Gu, S., et al., 2022] and [Selim, M., et al., 2022].\n\n[Kochdumper, N., et al., 2023] Kochdumper, N., Krasowski, H., Wang, X., Bak, S., & Althoff, M. (2023). Provably safe reinforcement learning via action projection using reachability analysis and polynomial zonotopes. IEEE Open Journal of Control Systems, 2, 79-92.\n\n[Gu, S., et al., 2022]  Gu, S., Chen, G., Zhang, L., Hou, J., Hu, Y., & Knoll, A. (2022). Constrained reinforcement learning for vehicle motion planning with topological reachability analysis. Robotics, 11(4), 81.\n\n[Selim, M., et al., 2022] Selim, M., Alanwar, A., Kousik, S., Gao, G., Pavone, M., & Johansson, K. H. (2022). Safe reinforcement learning using black-box reachability analysis. IEEE Robotics and Automation Letters, 7(4), 10665-10672.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The convergency analysis sounds good.\n2. Comprehensive experiments are provided.\n3. Hard constraints and soft constraints are investigated.", "weaknesses": "1. Paper writing quality needs to be improved a lot, I am confused about the paper notation, e.g., V_h and V_c.\n2. The experimental results are not correct regarding some baselines, especially for CRPO, in CRPO paper, the algorithm presents better performance than PPO-Lagrangian and CPO.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comments and detailed suggestions. \n\n>Paper writing quality needs to be improved a lot, I am confused about the paper notation, e.g., $V\\_h$ and $V\\_c$.\n\nWe have provided the definitions of the notations in lines 108-165 of the main paper, as well as a summary of notation in Table 1 of the appendix. We will further revise the notation to be more clear. $V_h$ is the reachability value function defined in Definition 2 (line 145 of main paper) which describes the maximum reachable violation. $V_c$ is the cumulative discounted sum defined in the CMDP section (line 125 of main paper).\n\n>The experimental results are not correct regarding some baselines, especially for CRPO, in CRPO paper, the algorithm presents better performance than PPO-Lagrangian and CPO.\n\nWith due respect, we don't believe reviewer's claim is accurate. The experiments in the CRPO paper [Xu et al.] have not compared with either PPO-Langrangian or CPO. They compare with a different algorithm called PDO and unconstrained TRPO (page 8 of [Xu et al.]). Furthermore, CRPO compares on the Cartpole and Acrobot environments, which are different benchmarks than those presented in our paper. Our implementation of CRPO baseline is based on that found in open-source python library omnisafe. Note that CRPO still inherits the limitations of the CMDP framework, namely it cannot operate in a state-wise hard constraint framework and the cost threshold needs fine-tuning and/or prior knowledge of the environment is needed.\n\n>Could you analyze the difference between RESPO and CRPO regarding the reward update and cost update?\n\nThe optimization procedures in RESPO and CRPO use the reward and cost critics differently, though the algorithms' critic updates are similar. Particularly, our contributions are in our novel proposed reachability-based optimization framework which maintains a reward critic, cost critic, and reachability estimation function (REF). Our work addresses issues about guaranteeing as best as possible to maintain hard constraints in a stochastic environment and uses a primal-dual constraint optimization method. On the other hand, CRPO’s contribution is situated within a different optimization framework, namely Constrained Markov Decision Processes (which is not suitable for hard constraints, see CMDP section 3.2 in main paper). They propose a policy optimization technique that is primal based. \n\n>If the agent does not find the safe action, will it be stuck at a point?\n\nNo, unless staying stationary is an available safe action. Based on our RESPO optimization, if there is no action so that the agent is currently or in the future safe, that means the current state is outside the feasible set. So, our optimization will be producing a policy that chooses trajectories minimizing the cumulative discounted sum of costs starting from that state. For a visual of an experiment showing how our algorithm might handle this, we refer the reviewer to the Double Integrator example in Appendix Section 4.4 in which the agent starts outside the feasible set.\n\n> How do you define the reachable set when considering reward performance?\n\nIn definition 5 (in Section 4.1 of the main paper), we define the feasible set as the set of states from which no violation is reached under a given policy (the reachable violation set will be the complement of the feasible set). RESPO will optimize reward performance under the constraint that the cumulative cost is 0 (i.e. the agent remains in the feasible set) if the agent is in the feasible set. Furthermore it will minimize cumulative cost if the agent is not in the feasible set.\n\n>The balance between reward and cost is not addressed well, in the experiments, as shown in Figure 3, although RESPO can ensure safety, the trajectory is longer than other baselines, and also not smooth.\n\nIn lines 318-322 of main paper, we describe how Figure 3 demonstrates RESPO has a desirable balance between reward and cost: it ensures the satisfaction of the various constraints as well as reaches the goal locations closer than the other approaches, therefore maintaining high rewards. \n\nNote that RESPO’s trajectory is actually the shortest ($\\sim 75$ steps) compared to the other baselines ($\\sim 85$, $80$, and $\\sim 120$) as indicated in the bar “Trajectory Step Number” next to each plot in Figure 3.\n\nAdditionally, the RESPO trajectory is quite smooth except for a particular point in the upper drone agent, which we explain in lines 320-322 of the main paper is to satisfy the hard constraints. The upper drone provides room to permit only one drone at a time in the tunnel, which is the intended behavior. The other approaches do not create this intended behavior of one drone at a time through the tunnel.\n\n>Some related papers are not mentioned in the study, e.g., [Kochdumper, N., et al., 2023], [Gu, S., et al., 2022] and [Selim, M., et al., 2022].\n\nThank you, we will add these to our related works discussion. All these three papers rely on having access to, or recreating, the model of the system dynamics to make predictions about future environment rewards and/or response, and are therefore model-based while our approach falls within the category of model-free safe RL.\n\n[Xu et al.] Crpo: A new approach for safe reinforcement learning with convergence guarantee. In ICML. PMLR, 2021."}, {"review_id": "DOdgLEWVVK", "reviewer": "Reviewer_YH1f", "summary": "Previous approaches to safe reinforcement learning used the constrained MDP formulation where there is a constraint imposed on the cumulative sum of costs to minimise violations. This framework is not applicable very easily where there is a need for hard constraint satisfaction. The previous approach (RCRL) which leverages reachability analysis to strictly satisfy hard constraints is limited to deterministic MDP and is not suited to bringing the state back to the feasible set when already outside the feasible set. In this work, the authors minimize the expected chance and frequency of violations under stochastic transition dynamics thus resolving the two problems with the previous work. The order in which to update the Q-networks, the policy networks, the Lagrangian dual factors and the reachability estimation function is studied using an empirical approach and a theoretical convergence guarantee to a local optimum is provided for this alternating optimization. Empirical comparisons are made extensively to a wide spectrum of existing approaches.", "questions": "1) While doing the comparison to CBF methods, it is not clearly what is being compared against. CBFs/Energy functions are usually handcrafted but there is CBVF (cited by the paper) and other related work that tries to construct the optimal CBF with maximum safety set (assuming known model). With the optimal CBF, the behaviour of CBF methods is not very conservative. If stochasticity is the source of trouble for the CBF methods, some extensions such as robust CBF and learned CBF are available. Here, the authors can provide more details about which exact CBF method they are using. \n\n2) In line 155, should $V_c$ be in the expression for optimal policy? $V_c$ is previously defined differently. “We define optimal REF based on an optimally safe policy π∗” is then misleading. The policy is optimizing a different loss in line 227 and it is not clear whether we actually get the optimal REF from this process. \n\n3) Assumption A3 (Lipschitz gradients) is a rather strong assumption. Are there previous cases where RL value functions are assumed to have Lipschitz gradients?\n\n4) In figure 3, why are RCRL and FAC violating the hard constraint if they are designed to respect hard constraints?\n\n5) The variance of the red RESPO learning curves seem to be high in certain figures indicating training instabilities\n", "limitations": "Authors have adequately addressed the limitations.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Advantages of paper in relation to deterministic dynamics assumption of RCRL is clear and has merit. Empirical comparisons to previous work are quite extensive with additional explanations in the appendix. Convergence to local optimum is presented to establish rigor and soundness of the method.\n", "weaknesses": "1) In section 6, it was not very clear what to see in the figures and it looked like RESPO was achieving a different point in the trade-off curve compared to the other methods. More information was available in the appendix. More discussion on how to compare the different methods and why one method performs better in a specific metric can be written out in the main section. The motivation of the paper provides the twin advantages of getting back into the feasible set and accounting for stochasticity. The first advantage is seen in the double integrator example in the appendix. Do any of the previous methods suffer due to deterministic assumptions and is the actual MDP stochastic?\n\n2) Since there are many networks and parameters updated at the same time, the robustness and reproducibility of the training process for this method and similar previous methods seem suspect. The authors have discussed this aspect in the ablation studies and the best possible convergence is obtained in the way the authors are doing the training. This insight, though a mild weakness, could benefit the community as we are inferring new insights about alternating optimization between multiple networks tied to each other.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comments and detailed suggestions. \n\n> it looked like RESPO was achieving a different point in the trade-off curve compared to the other methods.\n\nOur approach consistently achieves higher rewards and lower costs compared to the other safety baselines. Particularly, RESPO almost always achieves the highest or second highest reward performance among the safety baselines with low cumulative costs. When RESPO achieves the second highest, the algorithm with the highest (RCRL or PPOLag) always incurs several times more cost, generally beyond the acceptable threshold for that environment. The exception to this is the Reacher environment, but still RESPO has similar performance as other performance-successful algorithms and significantly lower cost than them. We will add more discussion on this in the main paper.\n\n>  Do any of the previous methods suffer due to deterministic assumptions and is the actual MDP stochastic?\n\nWe ensured environments running with the PyBullet engine, namely DroneCircle and BallRun, were stochastic by adding some noise. We will explain more details on this in the paper. Note that the policies learned were stochastic (i.e. $\\pi(a|s)$). We can see poor performance (i.e. either low rewards and low costs or high rewards and high costs) of algorithms like RCRL that assume deterministic environments.\n\n> This insight, though a mild weakness, could benefit the community as we are inferring new insights about alternating optimization between multiple networks tied to each other.\n\nAs the reviewer noted earlier, we demonstrated via 1) ablation studies in figure 5 on varying learning rates as well as 2) the proof in Appendix section 3.4 that having a particular order of learning rate schedules for the networks satisfying Assumption A1 (main paper line 265) guarantees convergence to the local optimum of our RESPO optimization.\n\n> If stochasticity is the source of trouble for the CBF methods, some extensions such as robust CBF and learned CBF are available.\n\nAs per the reviewer's suggestion, we have run additional experiments using model-free learned CBF certificate method found in [Yang et al] and results can be seen in pdf attached to global response. We see that compared to our approach and other baselines, the learned CBF produces conservative behavior (low reward and lost cost) likely because it is difficult to obtain the optimal CBF.\n\n> the authors can provide more details about which exact CBF method they are using.\n\nMore details about the CBF method can be found in the Appendix lines 290-292. Particularly, the constraint is $(c’ - c)/dt + \\nu \\cdot c \\leq 0$ where $c$ and $c’$ are consecutive cost values in a trajectory and $dt$ is the time step. This approach was also used as the CBF baseline in the RCRL paper.\n\n>In line 155, should $V\\_c$ be in the expression for optimal policy? ... The policy is optimizing a different loss in line 227 and it is not clear whether we actually get the optimal REF from this process.\n\nYes, $V_c$ should be in the expression. The RESPO optimization we proposed in line 227 will optimize for reward (i.e. $V^{\\pi}$) while maintaining cost $V^{\\pi}\\_{c} =0$ if the state is in the feasible set and minimize the cost $V^{\\pi}\\_{c}$ if the state is in the infeasible set. Notice, this produces similar safety as $\\pi^* = \\arg \\min\\_{\\pi} V^{\\pi}\\_c (s)$ : If $ V^{\\pi} \\_c (s)=0 $ then the state is in the feasible set and the RESPO optimization maximizes reward $V^{\\pi}$ while maintaining the cost constraint of 0 violations. In the other case, $\\min\\_{\\pi} V^{\\pi}\\_c(s)$ and RESPO behavior both minimize the cumulative cost. Since in both cases RESPO ensures $V^{\\pi}\\_c(s)$ is minimum, therefore the optimal policy of RESPO is actually an optimal policy of $\\min\\_{\\pi} V^{\\pi}\\_c (s)$. And hence, we can define the optimal REF from RESPO “based on __an__ optimally safe policy $\\pi^∗$.” \n\n> Are there previous cases where RL value functions are assumed to have Lipschitz gradients?\n\nThis assumption has been made in the past in several papers including [Chow et al] and [Yu et al]. Note we only use linear, tanh, softplus, and sigmoid activation functions which have Lipschitz continuous gradients.\n\n> In figure 3, why are RCRL and FAC violating the hard constraint if they are designed to respect hard constraints?\n\nApproaches like FAC and RCRL are unable to converge to a suitable policy that manages the importance of the constraints because they treat the soft constraint and both the hard constraints all with the same priority. However, our approach can prioritize the constraints within its optimization formulation (more details on how we do it are in appendix lines 423-435). Particularly RESPO never violates the primary constraint of wall avoidance and it only rarely violates the secondary hard constraint of closeness of the drones. Please refer to Section 4.8 of the appendix for more details on the optimization formulation for RCRL and FAC (particularly line 436).\n\n>The variance of the red RESPO learning curves seem to be high in certain figures indicating training instabilities.\n\nRESPO actually demonstrates smaller instabilities compared to other baseline algorithms near the end of training. While in some environments there are instabilities in the beginning of training of RESPO, our experiments show that RESPO generally converges to a consensus later in training. The only environment where the variance is relatively high at the end of training is DroneCircle—but even still, the baseline approaches with decent reward performance in DroneCircle, like PPOLag, P3O, FAC, and CRPO, have an even higher variance than RESPO.\n\n[Yang et al.] Model-free safe reinforcement learning through Neural Barrier Certificate. IEEE Robotics and Automation Letters, 2023.\n    \n[Chow et al.]  Risk-constrained reinforcement learning with percentile risk criteria. JMLR, 2017.  \n\n[Yu et al.] Reachability constrained reinforcement learning. In ICML. PMLR, 2022. "}, {"review_id": "cYQbRzD2rD", "reviewer": "Reviewer_teXi", "summary": "This paper presents  Reachability Estimation for Safe Policy Optimization (RESPO), for safety-constrained RL in general stochastic settings. The authors extend the previous RCRL approach into stochastic settings and push the agent to (re)enter the feasible region. They formulate a safe RL problem with REF and further develop an adapted AC algorithm to solve it, with convergence analysis. They compare their approach against CMDP-based approaches with a soft constraint and RCRL with a hard constraint, showing the advantages.  ", "questions": "Please see the weakness. ", "limitations": "What are the limitations of RESPO? ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper is well-motivated and well-structured to follow. It studies a critical problem. \nBased on RCRL, this paper does have some novelties in problem formulation and proposed approach. Technically, this paper is sound to me, although I only checked part of the math proof in the appendix.  \nThe experiments are promising as they show mixed performance and safety violation improvements. \n\n", "weaknesses": "1. The writing could be further improved, especially the comparison with RCRL. The reviewer acknowledges that there is some explanation of the difference between the proposed approach and RCRL, still, it would be much better to add more and clarify it. For example, the reviewer is confused why RCRL cannot guarantee or optimize (re)entrance to the feasible set. Couldn't use the same proof of Proposition 2 to obtain the same (re)entrance proposition?  \n\n2. For the deterministic environments, my understanding is RCRL considers a harder constraint as it is per state constraint than the discounted additive constraints in your paper, why the harder constraint cannot optimize/guarantee (re)entrance to the feasible set?  \n\n3. How does the reentrance proved from the deterministic environment applied to stochastic systems? \n\n3. There are some recent safe RL papers considering hard constraints. For example, \n\n a. Wang, Y., Zhan, S. S., Jiao, R., Wang, Z., Jin, W., Yang, Z., ... & Zhu, Q. (2022). Enforcing hard constraints with soft barriers: Safe reinforcement learning in unknown stochastic environments. ICML 2023.\n\n b.  Xiong, N. (2023). Provably Safe Reinforcement Learning with Step-wise Violation Constraints. arXiv preprint arXiv:2302.06064.\nThe authors may consider talking about these recent references in the paper revision. \n\n4. what do you mean by \"almost surely\" in the convergence analysis? ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comments and detailed suggestions. \n\n> The writing could be further improved, especially the comparison with RCRL. The reviewer acknowledges that there is some explanation of the difference between the proposed approach and RCRL, still, it would be much better to add more and clarify it. \n\nWe will make further explanations along these lines. In lines 170-185, we listed several specific problems in RCRL that we aim to address, namely: 1) RCRL is limited to the deterministic setting and 2) RCRL cannot guarantee (re)entrance into the feasible set. In particular, RCRL is limited to deterministic settings because its reachability value function in the Bellman formulation does not directly apply to the stochastic setting. \n\n>Why RCRL cannot guarantee or optimize (re)entrance to the feasible set. Couldn't use the same proof of Proposition 2 to obtain the same (re)entrance proposition?\n\nRCRL cannot guarantee (re)entrance because its reachability value function permits having many (possibly infinite) violations less than or equal to the maximum violation. For a small example, consider the agent faced with two possible trajectories: trajectory A which has a violation sequence (100, 0, 100) and trajectory B which has a violation sequence (100, 0, 0). The reachability value function would assign value 100 to both trajectory A and B since 100 is the maximum violation. So a reachability value approach like RCRL would choose both paths with equal likelihood and not be guaranteed to enter the feasible set. However, by considering the cumulative violations, trajectory A will have a greater cost score than B. Therefore, an approach using cumulative cost like RESPO will optimally choose trajectory B and thereby enter the feasible set.\n\nWe proposed to utilize reachability to instead measure likelihood of violation and to use (discounted) sum of costs along a trajectory to minimize cumulative violations. As Proposition 2 indicates, the (discounted) sum of costs can guarantee (re)entrance into the feasible set whenever possible by not allowing an uncountable number of violations smaller than (or equal to) the maximum violation in the trajectory. For details on the proof, please refer to Appendix section 3.3. For experimental support for this proposition, please refer to the Double Integrator example in Appendix section 4.4 which considers the behavior under RCRL versus RESPO when the agent starts inside the safe set but outside the feasible set.\n\n>For the deterministic environments, my understanding is RCRL considers a harder constraint as it is per state constraint than the discounted additive constraints in your paper, why the harder constraint cannot optimize/guarantee (re)entrance to the feasible set?\n\nA hard, state-wise constraint approach doesn’t necessarily guarantee entrance into the feasible set when the agent begins _outside the feasible set_. RCRL is unable to (re)enter the feasible set because of the formulation of its reachability value function. Specifically, because it only minimizes the maximum violation along a trajectory, it does not consider the possibility of many (potentially infinite) violations smaller than or equal to the maximum that prevent it from entering the feasible set. \n\n> How does the reentrance proved from the deterministic environment applied to stochastic systems?\n\nThe principle of reentrance using cumulative costs can be extended to stochastic systems. The basic idea we are providing in Proposition 2 is that if there exists a way to (re)enter the feasible set, this path would have a finite cumulative cost and all trajectories that do not enter the feasible set will have infinite cost (for gamma close to 1 and very large horizons), therefore the optimization will produce a policy with minimal (i.e. finite) cost which reenters the feasible set. This principle will also be reflected in stochastic systems (consider that even if the chance of ending up in a trajectory with infinite cost is small but nonzero, the expected cumulative cost will still be infinite), which justifies the usage of a value function based on cumulative cost rather than maximum cost along a trajectory.\n\n> There are some recent safe RL papers considering hard constraints. For example, [Wang et al.] and [Xiong et al.]\n\nThank you, we will add these papers in our related works section. Both these papers are model-based while our proposed algorithm falls in the category of model-free safe RL.\n\n> what do you mean by \"almost surely\" in the convergence analysis?\n\nBy almost surely, we are using the probability theory definition that the likelihood of the event (i.e. convergence to local optimum) is 1. This definition has been used in past works including [Chow et al.] and [Borkar]. \n\n> What are the limitations of RESPO?\n\nWe refer the reviewer to main paper lines 358-360. The main limitation is that we do not guarantee minimal violations _during_ training. We leave open potential extensions that can help in applications like safety in single-lifetime reinforcement learning.\n\t\t \t \t \t\t\n\t\t\t\t\t\n[Chow et al.]  Risk-constrained reinforcement learning with percentile risk criteria. JMLR, 2017. \n\n[Borkar] Stochastic approximation: a dynamical systems viewpoint, volume 48. Springer, 2009."}, {"review_id": "i0VEjTE5lO", "reviewer": "Reviewer_hXDB", "summary": "This paper proposed an iterative reachability estimation method for safe RL. The reachability is estimated by the probability of future trajectories entering unsafe state sets. Compare to previous reachability-based methods, the proposed method could handle stochastic dynamics and also improved the performance with deterministic dynamics. The proposed algorithm also leverages more information from data which could explain the performance improvement compared to existing methods. Theoretical convergence results are provided. Experimental results well supported the claimed performance improvement and safety guarantees. \n\nThis paper has removed one significant limitation, the deterministic dynamics assumption in previous studies. Removing this limitation should be very careful, and I think the authors did it very well. The author also connected HJ reachability with CMDP, which is two important definitions in the safe RL. Therefore, I strongly suggested the paper be accepted.", "questions": "I like most of the intuitions to explain the advantages of this paper. However, I have some questions:\n\n1. (line 179 - 181, about the claimed limitations of previous work RCRL) _**These improvements in costs can be crucial in guiding the optimization toward a safer policy.** And optimizing with $V_h(s) $ can result in accumulating an unlimited number of violations smaller than the maximum violation._\n\nI roughly got the intuition. I think you mean that some policies might be too far away from the safe policy. The optimization landscape looks like $V_h(s)$ should be non-decreasing in the first few steps but finally decrease to a low value. This is indeed interesting. Because from my intuition, a good policy update should always point to the direction that $V_h(s)$ decreases.\n\nDid you observe this in the experiment? If so, could you show me this phenomenon with some experimental results? It would be super helpful for enhancing the contribution of this paper.\n\n2. (Section 5.3, about the REF and multiplier.) The REF update actually relies on the distribution density function. It seems like you did not include this paper in the references,\n> Qin, Zengyi, Yuxiao Chen, and Chuchu Fan. \"Density constrained reinforcement learning.\" International Conference on Machine Learning. PMLR, 2021.\nI think it is a good paper to further understand the relationship between density function and Lagrange multipliers in safe RL problems. You should discuss the relationship with this paper.", "limitations": "The authors have adequately addressed the limitations.", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "Originality:\nVery good. As far as I now, no paper has considered stochastic reachability with the constrained RL setup. The authors also did a good job of connecting HJ reachability and CMDP, which are two important definitions in constrained RL that used to be separately considered. This combination also removed significant limitations, the deterministic dynamics of the previous study. \n\nQuality:\nExcellent. The paper very clearly explained the relation and improvement with respect to the previous paper in both deterministic and stochastic settings and did a comprehensive comparison in the experimental section. The authors also summarized the novelty and advantages of intuitions which is very easy to understand, i.e., previous methods only consider the maximum violation, which might lose information in the whole episode.\n\nClarity:\nThe presentation of this paper is good. \n\nSignificance:\nThe safety of stochastic systems is very important and challenging. There have been many theories and studies to formulate the problem, and reachability is undoubtedly one of the most powerful methods. Handling stochastic reachability should be very careful.", "weaknesses": "I feel good about most of the paper, I only have comments on some minor problems:\n1. The problem formulation, equation (4) should be emphasized better so that the reader will know this is the proposed problem formulation. \n2. The notation system is a bit messy. The readers might get lost easily, especially those not familiar with the previous paper.\n3. Algorithm 1 actually did not provide too much useful information. You should improve it to highlight the differences between your algorithm and the previous ones, like the REF update.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comments and the detailed suggestions.\n\n>The problem formulation, equation (4) should be emphasized better... The notation system is a bit messy ... You should improve it to highlight the differences between your algorithm and the previous ones\n\nThank you, we will further emphasize the equation, clarify the notations, and include the full form of the gradient of the losses in the algorithm.\n\n> The optimization landscape looks like $V_h$ should be non-decreasing in the first few steps but finally decrease to a low value. … Did you observe this in the experiment? If so, could you show me this phenomenon with some experimental results? \n\nYes, similar to what the reviewer suggests. In the quote, we are describing that since RCRL just computes maximum cost violation, any changes in cost later on in the trajectory that remain lower than the maximum cost will not affect the RCRL value. However, with cumulative sum of costs as used in RESPO, we can gain more learning signal since any change in costs along the trajectory will affect the cumulative sum.\n\nThis phenomenon explains, in the case when the agent is outside the feasible set, why RCRL tends to remain outside the feasible set and the RCRL optimization may not point to the direction that $V_h$ strictly decreases. However, our approach, RESPO, tends to (re)enter the feasible set. \n\nFor a visual on experimental results for comparing this property of cumulative costs compared to maximum reachable cost, we implemented a Double Integrator example and compared the trajectories between RESPO and RCRL in Appendix Section 4.4. It demonstrates how when the agent begins outside the feasible set, the _trajectory from RCRL remains outside the feasible set_ while the _trajectory from RESPO enters back into the feasible set_. For more information on this behavior of (re)entrance into the feasible set, we also refer the reviewer to Proposition 2 (line 213 of main paper) and its proof in Appendix Section 3.3.   \n\n> The REF update actually relies on the distribution density function. It seems like you did not include this paper in the references\n\nThank you, we will include it in the related work. Our REF estimates likelihood of future violations and is computed through reachability bellman formulation using the max operator. On the other hand, [Qin et al.]’s density metric computes state visitation density and is defined by the discounted sum of the likelihood of visiting a particular state. We will add more discussion on the relationship and differences between RESPO and [Qin et al.] in our related works.\n\n[Qin et al.] Density constrained reinforcement learning. In ICML. PMLR, 2021."}]

Author rebuttal:
We thank the reviewers for their detailed suggestions and feedback. Our novel algorithmic contributions in this paper include 1) providing a reachability-based hard constraint satisfaction approach for stochastic and deterministic settings and 2) the ability of (re)entrance into the feasible set within our reachability-based framework. We have evaluated our proposed approach on several benchmarks and compared with various baselines. We also demonstrated our method can handle and prioritize multiple hard and soft constraints. We have provided a proof that our algorithm converges to the local optimum of our proposed optimization.

We have run additional experiments for a model-free learned CBF baseline and compared with our proposed approach and other baselines. We include figures of the results in the attached pdf.

Meta-review: The meta-reviewer has reviewed the paper, the reviews, the responses, and agrees with the majority of the reviewers that this paper meets the NeurIPS standard.
Decision: Accept (poster)