Solving Minimum-Cost Reach Avoid using Reinforcement Learning
Authors: Oswin So
Cheng Ge
Chuchu Fan
Venue: NeurIPS 2024 poster (2024)
Keywords: Reinforcement Learning
Optimal Control
Reachability Analysis
Primary area: reinforcement_learning
TL;DR: We propose a new RL method for solving the minimum-cost reach-avoid problem, inspired by reachability analysis.

Abstract: Current reinforcement-learning methods are unable to directly learn policies that solve the minimum cost reach-avoid problem to minimize cumulative costs subject to the constraints of reaching the goal and avoiding unsafe states, as the structure of this new optimization problem is incompatible with current methods. Instead, a surrogate problem is solved where all objectives are combined with a weighted sum. However, this surrogate objective results in suboptimal policies that do not directly minimize the cumulative cost. In this work, we propose RC-PPO, a reinforcement-learning-based method for solving the minimum-cost reach-avoid problem by using connections to Hamilton-Jacobi reachability. Empirical results demonstrate that RC-PPO learns policies with comparable goal-reaching rates to while achieving up to 57% lower cumulative costs compared to existing methods on a suite of minimum-cost reach-avoid benchmarks on the Mujoco simulator. The project page can be found at https://oswinso.xyz/rcppo.

Solving Minimum-Cost Reach Avoid using Reinforcement Learning
Oswin So*
Cheng Ge Department of Aeronautics and Astronautics
Department of Aeronautics and Astronautics
MIT
MIT
oswinsošmit.ent edu
gec_mikelmit.eduu
Chuchu Fan
Department of Acronautics and Astronautics
MIT
chuchu@mit.edi
Abstract
Current reinforcement-leaming methods are unable to directly learn policies that solve the minimum cost reach-avoid problem to minimize cumulative costs subject to the constraints of reaching the goal and avoiding unsafe states, as the structure of this new optimization problem is incompatible with current methods. Instead, a surrogate problem solved where all objectives are combined with a weighted sum. However, this surrogate objective results in suboptimal policies that do not directly minimize the cumulative cost. In this work, we propose RC-PPO, a reinforcement-lerr leatt-lernnnngg-iee based method for solving the minimum-cost reach-avoid problem by using connections to Hamilton-Jacoh reachability. Empirical results demonstrate that RC-PPO learns policies with comparable goal-reaching rates while achieving up to 57% lower cumulative costs compared to existing methods suite of minimum-cosi reach-avoid benchmarks on the Mujoco simulator. The project page can be found at https://oswinso..y//yya
Introduction
Many real-world tasks can be framed constrained optimization problem where reaching goal at the terminal state and ensuring safety (i.e., reach-avoid) is desired while minimizing some cumulative cost as objective function, which we term the minimum-cost reach-avoid problem.
The cumulative cost, which differentiates this from the traditional reach-avoid problem, can be used to model desirable aspects of a task such as minimizing energy consumption, maximizing smoothness, or any other pseudo-energy function, and allows for choosing the most desirable policy among many policies that can satisfy the reach-avoid requirements. For example, energy eefegy-efficient autonomous driving 2 can be seen as task where the vehicle must reach a destination, follow traffic rules, and minimize fuel consumption. Minimizing fuel use is also major concern for low-thrust or energy-limites systems such as spacecraft
[ and quadrotors 4 Quadrotors often have to choose limited battery life to meet the payload capacity. Hence, minimizing their energy consumption, which can be done by taking advantage of wind patterns, is crucial for keeping them airborne to complete more tasks. Other use-cases important for climate change include plasma fusion (reach desired current, minimize the total risk of plasma disruption) [5] and voltage control (reach desired voltage level, minimize the load shedding amount) [6].
These authors contributed equally this work
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

If only a single control trajectory is desired, this class of problems can be solved using numerical trajectory optimization by either optimizing the timestep between knot points or bilevel opti- mization approach that adjusts the number of knot points in an outer loop g g 10 However, in this setting, the dynamics are assumed to be known, and only a single trajectory is obtained. Therefore, the computation will needs to be repeated when started from a different initial state. The computational complexity of trajectory optimization prevents it from being used in real time. Moreover, the use of nonlinear numerical optimization may result in poor solutions that lie in suboptimal local minim (Л].
Alternatively, to obtain a control policy, reinforcement learning (RL) can be used. However, existing methods are unable to directly solve the minimum-com reach- problem. Although RL has been used solve many tasks where reaching a goal is desired, goal-reaching is encouraged as a reward instead of as a constraint via the use of either a sparse reward at the goal [22 13 14], or a surrogate dense reward 14 15 However, posing the reach constraint as a reward then makes it difficult to optimize for the cumulative cost at the same time. In many cases, this is done via weighted sum However, the optimal policy of this new surrogate objective may not necessarily be the optimal policy of the original problem. Another method of handling this is to treat the cumulative cost as a constraint and solve for policy that maximizes the reward while keeping the cumulative cost under some fixed threshold, resulting in a new constrained optimization problem that can be solved as a constrained Markov decision process (CMDP) (21). However, the choice of this fixed threshold becomes key: too small and the problem is not feasible, destabilizing the training process. Too large, and the resulting policy will simply ignore the cumulative cost.
of the two terms [8
19 20
To tackle this issue, we propose Reach Constrained Proximal Policy OpptiizattionRC-PPO) a new algorithm that targets the minimum-cost reach-avoid problem. We first convert the reach-avoid problem to a reach problem on an augmented system and use the corresponding reach value function to compute the optimal policy. Next, we use a novel two-step PPO-based RL-based framework to learn this value function and the corresponding optimal policy. The first step uses a PPO-inspired algorithm to solve for the optimal value function and policy, conditioned on the cost upper bound. The second step fine-tunes the value function and solves for the least upper bound on the cumulative cost to obtain the final optimal policy. Our main contributions are summarized below:
We prove that the minimum-cost reach-avoid problem can be solved by defining set of augmented dynamics and a simplified constrained optimization problem.
We propose RC-PPO, a novel algorithm based on PPO that targets the minimum-cost reach-avoid problem, and prove that our algorithm converges a locally optimal policy.
Simulation experiments show that RC-PPO achieves reach rates comparable with the baseline method with the highest reach rate while achieving significantly lower cumulative costs.
2 Related Works
Carminal-horizon state-constrained optimization Terminal state constraints are quite common in the dynamic optimization literature. For the finite-horizon case, for example, one method of guaranteeing the stability of model predictive control (MPC) is with the use of terminal state constraint [22. Since MPC is implemented as a discrete-time unite-horizon numerical optimization problem, the terminal state constraints can be easily implemented in an optimization program as normal state constraint. The case of a mexible-horizon constrained optimization not as common but can still be found. For example, one method of time-optimal control is to treat the integration timestep as a control variable while imposing state constraints on the initial and final knot points 77. Another method is to consider bilevel optimization problem, where the number of knot points is optimized for in the outer loop 10].
Goal-conditioned Reinforcement Learning There have been many works on goal-conditioned reinforcement learning. These works mainly focus on the challenges of tackling sparse rewards even learning without rewards completely, either via representation learning
12
14
23
15
objectives 24
25 26
27
28
29
30
31
32
33 or by using contrastive learning to learn reward
functions 34 35
36
37
38
39
42
43 often in imitation learning settings [44] 45). However,
'I' the dense reward is not specified correctly, however, it can lead to unwanted local minima [4] that optimize the reward function in an undesirable manner, ie., reward hacking [16 17

---

the manner in which these goals are reached is not considered, and it is difficult to extend these works additionally minimize some cumulative cost.
Constrained Reinforcement Learning One way of using existing techniques to approximately lackle the minimum-cost reach-avoid problem is flip the role of the cumulative-cost objective and the goal-reaching constraint by treating the goal- goal-reaching constraint as an objective via a (sparse or dense) reward and the cumulative-cost objective as constraint with a cost threshold, turning the problem into a CMDP (2 In recent year, there has been significant interest in deep RL methods for solving CMDPs 46 47 48). While these methods are effective at solving the transformed CMDP problem, the optimal policy to the CMDP may not be the optimal policy to the original minimum-coss reach-constrained problem, depending on the choice of the cost constraint.
State Augmentation in Constrained Reinforcement Learning To improve reward structures in constrained reinforcement learning, especially in safety-critical systems, one effective approach is state augmentation. This technique integrates constraints, such as safety or energy costs, into the augmented state representation, allowing for more effective constraint management through the reward mechanism 49 [1].. While these methods enhance the reward structure for solving the transformed CMDP problems, they still face the inherent limitation of the CMDP framework: the optimal policy for the transformed CMDP may not always correspond to the optimal solution for the original problem.
Reachability Analysis Reachability analysis looks for solutions to the reach-avoid problem. That is, solve for the of initial conditions and an appropriate control policy drive a system to a desired goal set while avoiding undesireable states. Hamilton-Jacobi (HJ) reachability analysis the solution of partial differential equation (PDE) and is conventionally solved via numerical PDE techniques that use state-space discretization [54]. This has been extended recently to the case of discrete-time dynamics and solved using off off-policy [57 58) and on-policy [59] 60) reinforcement
[52 [53 54 (55 (6) provides a methodology for the case of dynamics in continuous-timg
learning. While reachability analysis concerns itself with the reach-avoid problem, we are instead
interested in solutions to the minimum-cost reach-avoid problem.
3 Problem Formulation
In this paper, we consider a class of minimum-cost reach-avoid problems defined by the tuple M = U, f, g, ht.. Here, X' C R= is the state space and U C 1 is the action space. The system states 2f E evolves under the deterministic discrete dynamics X x U + X' as
F++1 = f u4).
(1)
The control objective for the system states x; is to reach the goal region 9 and avoid the unsafe set F while minimizing the cumulative cost Σ c(x,, t (xx)) under control input " = a <xxx) for designed control policy X + U. Here, T denotes the first timestep that the agent reaches the goal G. The sets G and J are given as the 0-sublevel and strict O-superlevel sets g + and h: X + IR respectively, i.c.,
G = {x g(z) 0}. F= X h(x) > 0}
(2)
This can be formulated formally finding policy that solves the following constrained flexible final-time optimization problem for given initial state rn:
Ed ((())
min n,
(3a)
T
1=0
s.t.
IT E G,
(3b)
It $ F Vt E (O....,T).
(3c)
Jt+1 = (())))
(3d)
Note that as opposed to either traditional finite-horizon constrained optimization problems where T is fixed or infinite-horizon problems where T co, the time horizon 7' is also decision variable. Moreover, the goal constraint (3b) only enforced at the terminal timestep T. These two differences prevent the straightforward application of existing RL methods solve 33)
3

---

3.1 Reachability Analysis for Reach-Avoid Problems
In discrete time, the set of initial states that can reach the goal without entering the avoid set FF can be represented by the 0-sublevel set of reach-avoid value function V (58). Given functions h describing 9 and F and a policy æ, the reach-avoid value function
5.h XX is defined as
9.h (xo) = min max
(
max h(x=)) (O,....)T
TEN
where 27 denote the system state at time t under a policy т starting from an initial state xū 2g. In the rest of the paper, we suppress the argument zo for brevity whenever clear from the context. can be shown that the reach-avoid value function satisfies the following recursive relationship via the reach-avoid Bellman equation (RABE) [58]
g.h (xf) = max [xxT), min(g(xf), V. (17+)))). V2 0.
(5)
The Bellman equation 5 can then be used in a reinforcement learning framework (e.g., via a modification of soft actor-critic 66 62 as done in [58 to solve the reach-avoid problem.
Note that existing methods solving reach-avoid problems through this formulation focus on minimizing the value function g. This is not necessary as any policy that results in Vghh S 0 solves the reach-avoid problem, albeit without any cost considerations, However, it is often the case that we
wish minimize cumulative cost (e.g.. (Ba)) on top of the reach-avoid constraints (3b)- (3c for minimum-cosi reach-avoid problem. To address this class of problems, we next present a modification
to the reach-avoid framework that additionally enables the minimization of the cumulative cost.
3.2 Reachability Analysis for Minimum-cost Reach-Avoid Problems
We now provide a new framework to solve the minimum-coss reach-avoid by lifting the original system higher dimensional space and designing a of augmented dynamics that allow to convert the original problem into a reachability problem on the augmented system.
Let I denote the shifted indicator function defined as
TEEB = +1
be B,
b b B.
Define the augmented state as ê (s,, 2) C & X' (x11==,1)xll We now define corresponding augmented dynamics function f' X 11 + +x8aa &'s as
f (are: Ut. 2t, uz) (f(x)), max
((x))F, ((x))) ve), 2, c(21, uz)):
where yo = LA.EF. Note that y/
if the state has entered the avoid set F at some timestep from 0
to and is unsafe, and y/ = 0 if the state has not entered the avoid set at any timestep from 0 to t and is safe. Moreover, 2, is equal 2g minus the cost-to-come, i.c., for state trajectory zo. and action trajectory uo:t i.e.,
2+41
20
cla,, uz).
(8)
Under the augmented dynamics, we now define the following augmented goal function 9 E' + R as ((x, y, 2) == max( Cy, -2},
(9)
where C an arbitrary constant defined as
With this definition of ÿ, an augmented goal region 9 can be
g= ( (()) < 0} v.) x e g, y= = 10.2201 0}.
(10)
In other words, starting from initial condition 2.- (zo, yo. Zu). reaching the goal on the augmented system êτ E 9 timestep T implies that 1) the goal is reached at 2T for the original system, 2) the state trajectory remains safe and does not enter the avoid set F, and 3) z0 is upper-bound on
the total cost-to-come: Σ c(I,, u4) 20- We call this the upper-bound property. The above intuition on the newly defined augmented system is formalized in the following theorem, whose proof is provided in Appendix D.1
In practice C' max g(2).

---

Theorem 1. For given initial conditions E X, 20 E R and control policy r,, consider the trajectory for the original system {ag.... }T] and its correspondigg trajectory for the augmented system
{(F0, yo, 20). ... (TT, UT, 2T)} for some T > 0. Then, the reach constraint JT 9 (3b). avoid constraint da $ J vt {0, .,..,, T} Bch and the upper-bound property 20 2 > Lk= c(TRR क (Tx) hold if and only if the augmented state reaches the augmented goal at time T, i.e., (FT, Ur; 2T) E G.
With this construction, we have folded the avoid constraints 2, & F (3ch into the reach specification on the augmented system. In other words, solving the reach problem on the augmented system results in a reach-avoid solution of the original system. As a result, we can simplify the value function (4) and Bellman equation resulting in the following definition of the reach value function Vg
R
V/ (ōo) = min ((
(11)
tEN
Similar 4 the 0-sublevel set of V describes the set of augmented states & that can reach the augmented goal G. We can also similarly obtain a recursive definition the reach value function V given by the reachability Bellman equation (RBE)
VJ (x7 V7 =/²) min {ő(=), vF, VJ (2 (2t+1: V 2711)}
AA 2 0,
(12)
whose proof we provide in Appendix D.2
We now solve the minimum-cost reach-avoid problem using this augmented system. By Theorem the is an upper bound on the cumulative cost to reach the goal while avoiding the unsafe set if and only if the augmented state å reaches the augmented goal. Since this upper bound is tight, the least upper bound 2g that still reaches the augmented goal thus corresponds to the minimum-cost policy that satisfies the reach-avoid constraints. other words, the minimum-coss reach-avoid problem for given initial state Ty can be reformulated the following optimization problem.
min 20 TT 20
(13a)
s.t. V (x0, IZOEF, 20) S 0.
(13b)
We refer to Appendix B for a detailed derivation of the equivalence between the transformed Problem 1 and the original minimum-cost reach-avoid Problem B
Remark [Conecctions to the epigraph form constrained optimization). The resulting optimization
problem 13 can be interpreted as an epigraph reformulation (x3 of the minimum-com reach-avoid
problem The epigraph reformulation results in a problem with linear objective but yields the same solution as the original problem [63] The construction we propose in this work can be seen as a dynamic version of this epigraph reformulation technique originally developed for static problems and is similar to recent results that also make use of the epigraph form for solving infinite-horizon constrained optimization problems [59].
4 Solving with Reinforcement Learning
In the previous section, we reformulated the minimum-com cost reach-avoid problem by constructing an augmented system and used its reach value function (TT) in a new constrained optimization problem over the cost upper-bound 20- In this section, propose Reachability Constrained Proximal
(13)
Policy Optimization (RC-PPO), a two-phase RL-based method for solving (3) (see Figure I).
4.1 Phase 1: Learn z-conditioned policy and value function
In the first step, we learn the optimal policy x and value function V/g as functions of the cost upper-bound 2g, using RL. To do so, consider the policy gradient framework (64). However, since the policy gradient requires a stochastic policy in the case of deterministic dynamics (65), we consider analog of the developments made in the previous section but for the case of a stochastic policy. To this end, redefine the reach value function V using similar Bellman equation under stochastic policy follows.
5

---

Phase one
Phase two
Original System
Fine-Tune V
Training
ST E 2i FiE (0,....77
2
Calculate
s (a, = min(s Vig v. 0)
Augmented Dynamic System
Minimize
#t+1 f(e ue) 2y E g'
Execution
[1t (t. (a,v))
Figure Summary of the RC-PPO algorithm. phase one, the original dynamic system is transformed into the augmented dynamic system defined in (7. Then RL is used to optimize value function V and learn stochastic policy In phase two, we fine-tune V deterministic version of π and compute the optimal upper-bound 2" to obtain the optimal deterministic policy π..
Definition (Stochastic Reachability Bellman Equation), Given function ğ in 9 a stochastic policy т, and initial conditions 2g E X, 20 E IR, the stochastic reach value function V is defined as the solution to the following stochastic reachability Bellman equation (SRBE):
V (2:) = Ex (min( Vg (&++1)
Vt 2 0,
(14)
where d. (ra, yo, 20) with yo ezz
For this stochastic Bellman equation, the Q function 66 defined as
Q7 (&x, u.) min (ft+1)})
(15)
We next define the dynamics our problem with stochastic policy below.
Definition 2 (Reachability Markov Decision Process). The Reachability Markov Decision Process is defined on the augmented dynamic in Equation (7) with an added absorbing state sg. We define the
transition function with the absorbing state
f(t u).
if V (.) 0(f(2, u)). (2) s g(f(2, u)).
M u)
(16)
80
Denote by d'_ (.) the stationary distribution under stochastic policy ा starting at X' EX [-1,1] XR
We now derive a policy gradient theorem for the Reachability MDP in Definition which yields an almost identical expression for the policy gradient.
Theorem (Policy Gradient Theorem) For policy mo parameterized by 0, the gradient of the policy value function = satisfies
V.V To (i) x Egraa((()) IÔ~ (f', u) V In To (u $7) 9
(17)
under the stationary distribution d, (.)) for Reachability MDP in Definition
The proof this new policy gradient theorem (Theorem 2 follows the proof of the normal policy gradient theorem [66], differing only in the expression of the stationary distribution. We provide the
proof Appendix D.3
Since the stationary distribution d'_ (f+) in Definition 2 is hard to simulate during the learning process, we instead consider the stationary distribution under the original augmented dynamic system. Note that Definition [ does not induce contraction map, which harms performance. To fix this, we apply the same trick [58 by introducing an additional discount factor y into the Bellman equation (12)
VT = (1 - (+)( + 7E (ā.+) V (+.-
(18)

---

This provides us with a contraction map (proved in [58] and we leave the discussion of choosing
in Appendix [ The Q-function corresponding to (18) then given as
(āt,, we) = (1 (ār) + min
min( (ū(xe), Vz (#t+1))-
(19)
Following proximal policy optimization (PPO) [67] we use generalized advantage estimation (GAB)
68 to compute variance-reduces advantage function Aj = Q7 V for the policy gradient
(Theorem 2 using the X-return [66]. We refer to Appendix A for the definition of 4g (GAA))
and
denote the loss function when 0 G₁ as
(0) FE
AA* (i: u
(20)
(T ②)
i)) Ag (GAB) (,, CLIP (c. (GAE) (GAB) (3, v1)
9 (i, u) max
(21)
TTO (u
We wish to obtain the optimal policy and the value function V.T conditioned on 2p. Hence, at the beginning of each rollout, we uniformly sample 20 within a user-specified range [zmin ²max] Since the optimal 2g is the cumulative cost of the policy that solves the minimum-cost reach-avoid problem, user-specified bounds the optimal cost. In particular, when the cost-function is
2min and 2max bounded and the optimal cost is non-negative, we can choose 2min to be some negative number and 2max to be the maximum possible discounted cost.
4.2 Phase 2: Solving for the optimal
In the second phase, we first compute a deterministic version n² of the stochastic policy from phase 1 by taking the mode. Next, we fine-tune V based on the now deterministic x² to obtain Vz..
Given any state the final policy is then obtained by solving for the optimal cost upper-bound = from Equation (13), which a 1D root-finding problem and can easily solved using bisection. Note that Equation (33 must be solved online for =" at each state x. Alternatively, to avoid performing bisection online, we can instead learn the map (x, y) + z offline using regression with randomly sampled (x, y) pairs and z" labels obtained from bisection offline.
We provide convergence proof of actor-critic version of our method without the GAE estimator in Appendix
Experiments
Baselines We consider two categories of RL baselines. The first is goal-conditioned reinforcement learning which focuses on goal-reaching but does not consider minimization of the cost. For this category, consider the Contrastive Reinforcement Learning (CRL) (33 method. We also compare against safe RL methods that solve CMDPs. As the minimum-com reach-avoid problem cannot be posed as CMDP, reformulate (3) into the following surrogate CMDP:
min π
Egg Re wode
Σ
[- 7T((,, u+]
(22a)
s.t.
Exg ue rer
Σ 1 IMEE Cran] S
(22b)
E uh rdd
Uz]] s Rehreshold
(22c)
where the reward r incentivies goal-reaching, Ctall is term balancing two constraint terms, and Xthreshold is hyperparameter the cumulative cost. For this category, consider the CPPO 48 and RESPO 660. Note that RESPO also incorporates reachability analysis to adapt the Lagrange multipliers for each constraint term. We implement the above CMDP- based baselines with three different choices of ? XL, Xs and XH. For RESPO, we found X'M to outperform both Xi and Xi and thus only report results for X'.
We also consider the static Lagrangian multiplier case. In this setting, the reward function becomes r(xx) - B[1 EF x Ctai + c( u.)) for constant Lagrange multiplier 3. We consider two different levels of /3 (3t, (n) in our experiments, resulting in the baselines PPO__t,, PPO_ SAC_at.
SAC 3H. More details are provided in Appendix

---

Pendulum
Safety Happer
WindFField
PointGoal
Safety HalfCheetah
FinedWWng
Figure 2: Illustrations of the benchmark tasks. In each picture, red denotes the unsafe region be avoided, while green denotes the goal region to be reached.
Reach Rate
Reach Rate
Reach
8C.000
RC.90
RC,900
88980
mT0.8
R10 55
F10
6AG
3AC
0W007u
CPRO
(MP)
C1P0
DIRO
0.0
0.4
0.8
0.0
0.4 0.6
0.8
Pendulum
Safety Hopper
WindField
Reach Rate
Reach Rate
Reach
00209
8C/10
8C410
8590
90.44
366 0
SAC
34C
(M9)
CPR)
Chi
PointGoal
Safety HalfCheetah
FizedWing
Figure 3: Reach rates under the sparse reward setting. RC-PPO consistently achieves the highest reach rates in all benchmark tasks. Error bars denote the standard error.
Benchmarks
We compare RC-PPO with baseline methods on several minimum-cost reach-avoid
environments. We consider an inverted pendulum (Pendulum), an environment from Safety Gym 69
(PointGoal) and two custom environments from MuJoCo [70), (Safety Hopper, Safety HalfCheetah) with added hazard regions and goal regions. We also consider 3D quadrotor navigation task simulated wind field for an urban environment [7] 72 (WindField) and an Fixed-Wing avoid task from (59] with an additional goal region (FixedWing). More details on the benchmark can be found in Appendix G
Evaluation Metrics Since the goal of RC-PPO is minimizing cost consumption while reaching goal without entering the unsafe region F. We evaluate algorithm performance based on (i) reach rate, (ii) cost. The reach rate is the ratio of trajectories that enter goal region & without violating safety along the trajectory. The cost denotes the cumulative cost over the trajectory Σi= c(2x, n (xx)).
5.1 Sparse Reward Setting
We first compare algorithm with other baseline algorithms under sparse reward setting (Figure 3 In all environments, the reach rate for the baseline algorithms is very low. Also, there is a general trend between the reach rate and the Lagrangian coefficient. CPPO_4,, PPO_0H and SAC_ have higher Lagrangian coefficients which lead to lower reach rate.
5.2 Comparison under Reward Shaping
Reward shaping is a common method that can be used to improve the performance RL algorithms, especially in the sparse reward setting [73] 74). To see whether the same conclusions still hold even in the presence of reward shaping, we retrain the baseline methods but with reward shaping using a distance function-based potential function (see Appendix F for more details).
The results in Figure demonstrate that RC-PPO remains competitive against the best baseline algorithms in reach rate while achieving significantly lower cumulative costs. The baseline methods (PPO_31, SAC_0m, CPPO__t,) fail to achieve a high reach rate due to the large weights placed on minimizing the cumulative cost. CRL can reach the goal for simpler environments (Pendulum) but struggles with more complex environments. However, since goal-conditioned methods do not consider minimize cumulative cost, it achieves higher cumulative cost relative to other methods.

---

Addiical Cundlttive
Acditoral Cumudativ Cout
Acditoral Curruaaivv Cast
Addiional Curudaaiv Cast
01200
nesro-
SACA
Reach
React Rate
Reach Pate
Reach Pate
10
K0
0520
00200
110
099
(990
091)
(R0
D1
60
0.2
0.4
0.5
0.5
1.0
50
02
0.4
0.5
0.0
0.0 0.2
0.4
0.5
0.0
02
1.0
Pendulum
PointGoal
Safety HalfCheetah
WindField
Figure 4: Cumulative cost (QQM) and reach rates under reward shaping four selected benchmarks. RC-PPO achieves significantly lower cumulative costs while retaining comparable reach rates even when compared with baseline methods that use reward shaping.
CMP0
Gall
RESPO
NC-PP
58.
Goal
Cunnuaative
600
CPPOOX
Comnulalive
200
CPPO
RESPO
Cost
800
RESPO
Cost
200-
RC-PPD
200
RC-PPO
400
50
Timestep
Timestep
(a) Pendulum
(b) WindField
Figure 5: Trajectory comparisons. On Pendulum, RC-PPO learns to perform an extensive energy pumping strategy to reach the goal upright position (green line), resulting in vastly lower cumulative energy. On WindField, RC-PPO takes advantage instead of fighting against the wind field, resulting in faster trajectory to the goal region (green box) that uses lower cumulative energy. The start of the trajectory is marked by
Other baselines focus more on goal-reaching tasks while putting less emphasis on the cost part. As result, they suffer from higher costs than RC-PPO. We can also observe that RESPO achieves lower cumulative cost compared to CPPO_A, which shares the same Kthreshold This is due to RESPO making use of reachability analysis to better satisfy constraints.
To see how RC-PPO achieves lower cumulative costs, we visualize the resulting trajectories for Pendulum um and WindFiell in Figure For Pendulum, we see that RC-PPO learns to perform energy pumping to reach the goal in more time but with a smaller cumulative cost. The optimal behavior is opposite in the case of WindField, which contains an additional constant term in the cost to model the energy draw of quadcopters (see Appendix G). Here, we see that RC-PPO takes advantage of the wind at the beginning by moving downwind, arriving at the goal faster and with less cumulative cost.
We also visualize the learned RC-PPO policy for different values of on the Pendulum benchmark (see Appendix (H.2). For small values of the policy leams to minimize the cost, but the expense of not reaching the goal. For large values of z, the policy reaches the goal quickly but at the expense of a large cost. The optimal Zopt found using the learned value function Fr finds the z that minimizes the cumulative cost but is still able to reach the goal.
5.3 Optimal solution of minimum-cost reach-avoid cannot be obtained using CMDP
Though the previous subsections show the performance benefits of RC-PPO over existing methods, this may be due to badly chosen hyperparameters for the baseline methods, particularly in the formulation of the surrogate CMDP (2).. We thus pose the following question: Can CMDP
methods perform well under the right parameters of the surrogate CMDP problem 22 ?

---

300
200
Additional Cumulative Cost
100
80
60
40
PPO different reward coefficients
20
RC-PPO
0-1
0.0
0.2
0.4
0.6
0.8
Reach Rate
Figure Pareto front of PPO across different reward coefficients. RC-PPO outperforms the entire Pareto front of what can be achieved by varying the reward function coefficients of the surrogate CMDP problem when solved using PPO.
Empirical Study. To answer this question, we first perform an extensive grid search over both the different coefficients in (22) and the static Lagrange multiplier for PPO (see Appendix H..) and plot the result in Figure RC-PPO outperforms the entire Pareto front formed from this grid search, providing experimental evidence that the performance improvements of RC-PPO stem from having
better problem formulation as opposed badly chosen hyperparameters for the baselines.
Theoretical Analysis on Simple Example. To complement the empirical study, we provide an exam- ple of simple minimum-cost reach-avoid problem where prove that no choice of hyperparameter leads to the optimal solution in Appendix [
5.4 Robustness to Noise
Finally, we investigate the robustness to varying levels of control noise in Appendix H.4 H.4 Even with the added noise, RC-PPO achieves the lowest cumulative cost while maintaining comparable reach rate to other methods.
6 Conclusion and Limitations
We have proposed RC-PPO, novel reinforcement learning algorithm for solving minimum-cost reach-avoid problems. We have demonstrated the strong capabilities of RC-PPO over prior methods in solving multitude of challenging benchmark problems, where RC-PPO learns policies that match the reach rates of existing methods while achieving significantly lower cumulative costs.
However, it should be noted that RC-PPO is not without limitations. First, the use of augmented dynamics enables folding the safety constraints within the goal specifications through an additional binary state variable. While this reduces the complexity of the resulting algorithm, it also means that two policies that are both unable to reach the goal can have the same value V even if one is unsafe, which can be undesirable. Next, the theoretical developments of RC-PPÓ are dependent on the assumptions of deterministic dynamics, which can be quite restrictive as it precludes the of commonly used techniques for real-world deployment such as domain randomization. We acknowledge these limitations and leave resolving these challenges as future work.
Acknowledgments and Disclosure of Funding
This work was partly supported by the National Science Foundation (NSF) CAREER Award #CCF- 2238030, the MIT Lincoln Lab, and the MIT-DSTA program. Any opinions, findings. conclusions, or recommendations expressed in this publication are those of the authors and don't 't necessarily reflect the views of the sponsors.
10

---

References
[1] Xuewei Qi, Yadan Luo, Guoyuan Wu, Kanok Boriboonsomsin, and Matthew Barth. Deep reinforcement learning enabled self-learning control for energy efficient driving. Transportation Research Part C: Emerging Technologies, 99:67-81, 2019.
[2] Ying Zhang, Tao You, Jinchao Chen, Chenglie Du, Zhaoyang Ai, and Xiaobo Qu Safe and energy-saving vehicle-followngg driving decision-making framework of autonomous vehicles. IEEE Transactions on Industrial Electronics, (111)):3399-18777 2021.
[3] Mirco Rasotto, Roberto Armellin, and Pierluigi Di Lizia. Multi-step optimization strategy for fuel-optimal orbital transfer of low-thrust spacecraft. Engineering Optimization, 48(3):519-542, 2016.
[4] Jack Langelaan. Long distance/duration trajectory optimization for small uavs. In AIAA guidance, navigation and control conference and exhibir, page 6737, 2007.
[5] Allen M Wang. Oswin So, Charles Dawson, Darren T Garnier, Cristina Rea, and Chuchu Fan. Active disruption avoidance and trajectory design for tokamak ramp-downs with neural differential equations and reinforcement learning. arXiv preprint 240.:22000009877 2024.
[6] Renke Huang, Yujiao Chen, Tianzhixi Yin, Xinya Li, Ang Li, Jie Tan, Wenhao Yu, Yuan Liu. and Qiuhua Huang. Accelerated deep reinforcement learning based load shedding for emergency voltage control. arXiv preprint arXiv:2006. 222200006.6666. 12667, 2020.
[7] Christoph Rösmann, Frank Hoffmann, and Torsten Bertram. Timed-elastic-band for time- optimal point-to to -o-potttto nonlinear model predictive control. In 2015 european control conference (ECC), pages 3352-3357. IEEE, 2015.
[8] Robin M Pinson and Ping Lu. Trajectory design employing convex optimization for landing on irregularly shaped asteroids. Journal of Guidance, Control, and Dynamics, (1(6):1243-1256 2018.
[9] Haichao Hong, Arna Maity, and Florian Holzapfel. Free final-time constrained sequential quadratic programming- based flight vehicle guidance. Journal of Guidance, Control, and Dynamics, 14119:181-18,, 2021.
[10] Kyle Stachowicz and Evangelos A Theodorou. Optimal-horizon model predictive control with differential dynamic programming. In 2022 International Conference Robotics and Automation (ICRA), pages 1440-1446. IEEE, 2022.
[11] Damien Emst, Mevludin Glavic, Florin Capitanescu, and Louis Wehenkel. Reinforcement learning versus model predictive control: a comparison a power system problem. IEEE Transactions on Systems, Man, and Cybernetics, Pari B (Cybernetics), 39())55752)39 2008.
[12] Marcin Andrychowicz. Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, OpenAl Pieter Abbeel, and Wojeiech Zaremba. Hindsight experience replay. Advances in neural information processing systems, 30, 2017.
[13] Matthias Plappert, Marcin Andrychowicz. Alex Ray, Bob McGrew, Bowen Baker, Glenn Powell, Jonas Schneider, Josh Tobin, Maciek Chociej, Peter Welinder, et al. Multi-goal reinforcement learning: Challenging robotics environments and request for research. arXiv preprint 1rXiv: 09464, 2018
[14] Alexander Trott, Stephan Zheng, Caiming Xiong, and Richard Socher. Keeping your dis- tance: Solving sparse reward tasks using self-balancing shaped rewards. Advances in Neural Information Processing Systems, 32, 2019.
[15] Minghuan Liu, Menghui Zhu, and Weinan Zhang. cond-condi reinforcement learning: Problems and solutions. arXiv preprint arXiv:2201.08200 2022.
[16] Jack Clark and Dario Amodei. Faulty reward functions the wild, 2016.
[17] Pulkit Agrawal. The task specification problem. In Conference on Robot Learning, pages 1745-1751. PMLR, 2022.

---

[18] Greg Brockman, Vicki Cheung, Ludwig Pettersson. Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym. arXiv preprint arXiv: 540, 2016.
[19]
Gabriel B Margolis, Tao Chen, Kartik Paigwar, Xiang Fu, Donghyun Kim, Sangbae Kim, and Pulkit Agrawal. Learning to jump from pixels. arXiv preprint arXiv:2/10.153:2 2021.
[20] Dhawal Gupta, Yash Chandak, Scott Jordan, Philip S Thomas, and Bruno C da Silva. Behavior alignment via reward function optimization. Advances Neural Information Processing Systems, 36, 2024.
[21] Eitan Altman. Constrained Markov decision processes. Routledge, 2004.
[22] Lorenzo Fagiano and Andrew R Teel. Generalized terminal state constraint for model predictive control. Automatica, 49(9):2622-25) 2631, 2013.
[23] Yifan Wu, George Tucker, and Ofir Nachum. The laplacian in rl: Learning representations with efficient approximations. arXiv preprint 1xXiv:8810004580, 2018.
[24] Ashvin Nair, Bob McGrew, Marcin Andrychowicz, Wojeiech Zaremba, and Pieter Abbeel. Over- coming exploration in reinforcement learning with demonstrations. In 2018 JEEE international conference on robotics and automation (ICRA), pages 6292-6299, IEEE, 2018.
[25] Dibya Ghosh, Abhishek Gupta, Ashwin Reddy, Justin Fu, Coline Devin, Benjamin Eysenbach, and Sergey Levine. Learning to reach goals via iterated supervised learning. arXiv preprint 1rXiv:1912.06085 2019.
[26] Ashvin V Nair, Vitchyr Pong, Murtaza Dalal, Shikhar Bahl, Steven Lin, and Sergey Levine. Visual reinforcement learning with imagined goals. Advances in neural information processing systems, 31, 2018.
[27] David Warde- Farley, Tom Van de Wiele, Tejas Kulkamni, Catalin Ionescu, Steven Hansen, and Volodymyr Mnih. Unsupervised control through non- con-parametric discriminative rewards. arXiv preprint
2018.
[28) Hao Sun, Zhizhong Li, Xiaotong Liu, Bolei Zhou, and Dahua Lin. Policy continuation with hindsight inverse dynamics. Advances in Neural Information Processing Systems, 32, 2019.
[29] Suraj Nair and Chelsea Finn. Hierarchical foresight: Self-supervised learning of long-horize tasks via visual subgoal generation. arXiv preprint arXiv: 1909.05829, 2019.
[30] Andres Campero, Roberta Raileanu, Heinrich Küttler, Joshua B Tenenbaum, Tim Rocktäschel, and Edward Grefenstette. Learning with amigo: Adversarially motivated intrinsic goals. arXiv preprint arXiv:2006. 2020.
[31] Suraj Nair, Silvio Savarese, and Chelsea Finn. Goal-aware prediction: Learning to model what matters. In International Conference on Machine Learning, pages 7207-7219. PMLR, 2020.
[32] Russell Mendonca, Oleh Rybkin, Kostas Daniilidis, Danijar Hafner, and Deepak Pathak. Dis- covering and achieving goals via world models. Advances in Neural Information Processing Systems, 34:24379-244 24391, 2021.
[33] Benjamin Eysenbach, Tianjun Zhang, Sergey Levine, and Russ R Salakhutdinov. Contrastive learning as goal-condiiioned reinforcement learning. Advances in Neural Information Process- ing Systems, 35:35603-356200 2022.
[34] David Fischinger, Markus Vineze, and Yun Jiang. Learning grasps for unknown objects in cluttered scenes. In 2013 IEEE international conference robotics and automation, pages 609-616. IEEE, 2013.
[35] Paul Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei. Deep reinforcement learning from human preferences. Advances in neural information processing systems, 30, 2017.
[36] Annie Xie, Avi Singh, Sergey Levine, and Chelsea Finn. Few-shot goal inference for visuomotor learning and planning. In Conference on Robot Learning, pages 40-52. PMLR, 2018.
12

---

[37] Justin Fu, Avi Singh, Dibya Ghosh, Larry Yang, and Sergey Levine. Variational inverse control with events: general framework for data-driven reward definition. Advances in neural information processing systems, 31, 2018.
[38] Daniel Brown, Wonjoon Goo, Prabhat Nagarajan, and Scott Niekum. Extrapolating beyond sub- optimal demonstrations via inverse reinforcement learning from observations. In International conference on machine learning, pages 783-792. PMLR, 2019.
[39] Ksenia Konyushkova, Konrad Zolna, Yusuf Aytar, Alexander Novikov, Scott Reed, Serkan Cabi, and Nando de Freitas Semi-supervised reward learning for offline reinforcement learning. arXiv preprint arXiv:20/2.06899 2020.
[40] Dmitry Kalashnikov, Jacob Varley, Yevgen Chebotar, Benjamin Swanson, Rico Jonschkowski, Chelsea Finn, Sergey Levine, and Karol Hausman. Mt-opt: Continuous multi-task robotic reinforcement learning at scale. arXiv preprint wxXiv:2104.08212, 2021.
[41] Danfei Xu and Misha Denil. Positive-unlabeled reward learning. In Conference on Robot Learning, pages 205-219. PMLR, 2021.
[42] Konrad ZoIna, Scott Reed, Alexander Novikov, Sergio Gomez Colmenarejo, David Budden, Serkan Cabi, Misha Denil, Nando de Freitas, and Ziyu Wang. Task-relevant adversarial imitation learning. In Conference Robot Learning, pages 247-263. PMLR, 2021.
[43] Suraj Nair, Eric Mitchell, Kevin Chen, Silvio Savarese, Chelsea Finn, et al. Learning language- conditioned robot behavior from offline data and crowd-sourced annotation. Conference on Robot Learning, pages 1303 1315. PMLR, 2022.
[44] Jonathan Ho and Stefano Ermon. Generative adversarial imitation learning. Advances in neural information processing systems, 29, 2016.
[45] Justin Fu, Katie Luo, and Sergey Levine. Learning robust rewards with adversarial inverse reinforcement learning, arXiv preprint arXiv:1710. 12248, 2017.
[46] Joshua Achiam, David Held, Aviv Tamar, and Pieter Abbeel. Constrained policy optimization. In International conference on machine learning, pages 22-31. PMLR, 2017.
[47] Chen Tessler, Daniel Mankowitz, and Shie Mannor. Reward constrained policy optimization. arXiv preprint 1.05 2018.
[48] Adam Stooke, Joshua Achiam, and Pieter Abbeel. Responsive safety in reinforcement learning by pid lagrangian methods. In International Conference on Machine Learning, pages 9133-9143, PMLR, 2020.
[49] Aivar Sootla, Alexander Cowen-Rivers, Taher Jafferjee, Ziyan Wang, David H Mguni, Jun Wang, and Haitham Ammar. Sauté rl: Almost surely safe reinforcement learning using state augmentation. In International Conference on Machine Learning, pages 20423-20443, PMLR, 2022.
[50] Hao Jiang, Tien Mai, Pradeep Varakantham, and Minh Huy Hoang. Solving richly con- strained reinforcement learning through state augmentation and reward penalties. arXiv preprint M.Xi:23001.1192 2023.
[51] Hao Jiang, Tien Mai. Pradeep Varakantham, and Huy Hoang. Reward penalties augmented states for solving richly constrained rl effectively. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 19867-19875, 2024.
[52] Claire J Tomlin, John Lygeros, and S Shankar Sastry. A game theoretic approach to controller design for hybrid systems. Proceedings of the IEEÉ, 88(7))949999)))) 9709999977779 2000.
[53] John Lygeros. On reachability and minimum cost optimal control. Automatica, 40(6):917-927, 2004.
[54] Ian M Mitchell, Alexandre M Bayen, and Claire J Tomlin. A time-dependent hamilton-jacobi formulation of reachable sets for continuous dynamic games. IEEE Transactions on automatic control, 9077):947-977 2005.
13

---

[55] Kostas Margellos and John Lygeros. Hamilton-jacobe formulation for reach avoid differential games. IEEE Transactions on automatic control, 56(8):1849- 2011.
[56] Somil Bansal, Mo Chen, Sylvia Herbert, and Claire Tomlin. Hamilton-jacobi reachability: A brief overview and recent advances. In 2017 IEEE 56th Annual Conference Decision and Control (CDC), pages 2242-222222222 2253. IEEE, 2017.
[57] 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.
[58] Kai Chieh Hsu, Vicenç hubies-Royo, Claire J Tomlin, and Jaime F Fisac. Safety and liveness guarantees through reach-avoid reinforcement learning. In 77th Robotics: Science and Systems, RSS 2021. MIT Press Journals, 2021.
[59] Oswin So and Chuchu Fan. Solving stabilize-avoid optimal control via epigraph form and deep reinforcement learning. arXiv preprint arXiv:2305. 14154, 2023.
[60] Milan Ganai, Zheng Gong, Chenning Yu, Sylvia Herbert, and Sicun Gao. Iterative reachability estimation for safe reinforcement learning. Advances in Neural Information Processing Systems, 36, 2024.
[61] Tuomas Haarnoja, Aurick Zhou, Kristian Hartikainen, George Tucker, Sehoon Ha, Jie Tan, Vikash Kumar, Henry Zhu, Abhishek Gupta, Pieter Abbeel, et al. Soft actor-critic algorithms and applications. arXiv preprint arXiv: 181.0005, 2018.
[62] Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off- policy maximum entropy deep reinforcement learning with a stochastic actor. In International conference machine learning, pages 1861-1870. PMLR, 2018
[63] Stephen P Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
[64] Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient meth- ods for reinforcement learning with function approximation. Advances in neural information processing systems, 12, 1999.
[65] David Silver, Guy Lever, Nicolas Heess, Thomas Degris, Daan Wierstra, and Martin Riedmiller. Deterministic policy gradient algorithms. In International conference on machine learning. pages 387-395. Pmir, 2014.
[66] Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
[67] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: 06347, 2017.
[68] John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Pieter Abbeel. High- dimensional continuous control using generalized advantage estimation. arXiv preprint arXiv:1506.02433. 2015.
[69] Alex Ray, Joshua Achiam, and Dario Amodei. Benchmarking safe exploration in deep rein- forcement learning, arXiv preprint arXiv: 7(1):2 2019.
[70] Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-based control. In 2012 JEEE/RSJ international conference on intelligent robots and systems, pages 6026-5033. IEEE, 2012.
[71] Steven Waslander and Carlos Wang. Wind disturbance estimation and rejection for quadrotor position control. In AIAA Infotech@ Aerospace conference and AIAA unmanned... Unlimited conference, page 1983, 2009.
[72] Sanjeeh T Bose and George Ilhwan Park. Wall-modeled large-eddy simulation for complex turbulent flows. Annual review of fluid mechanics, 50:535-561, 2018.
14

---

[73] Maja Mataric. Reward functions for accelerated learning. In Machine learning proceedings 1994, pages 181-189. Elsevier, 1994.
[74] Andrew Y Ng. Daishi Harada, and Stuart Russell. Policy invariance under reward transfor- mations: Theory and application to reward shaping. In Ieml, volume 99, pages 278-287, 1999.
[75] Dongjie Yu, Haitong Ma, Shengbo Li, and Jianyu Chen. Reachability constrained reinforcement learning. In International Conference Machine Learning, pages
PMLR, 2022.
[76] James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman-Milnn and Qiao Zhang. JAX: composable transformations of Python+NumPP programs, 2018.
15

---

A GAE estimator Definition
Note, however, that the definition of return 19 is different from the original definition and hence will result in a different equation for the GAE
To simplify the form of the GAE, we first define a "reduction" function ((()) R - that applies itself recursively to its n arguments, i.e.,
= In) x (II, (02.... (1), 22.,,,,. In)
(o2....,
where
(x, (1 (1- min v..
The k-step advantage function Ag(a) can then be written
15 (8.) (A() (.(2)).....
(82++)) Vg (2,).
We can then construct the GAE A7 (T(GA the X* -e-wgigtted Ag
the k-step advantage functions Overall, the GAE estimator can be described
A
(GAE) (ft)
x A
(fz). (Zz).
B Equivalence of Problem
3 and Problem 13
The equivalence between the transformed Problem 13 and the original minimum-com reach-avoid Problem 3 can be shown in the following sequence of optimization problems that yield the exact same solution if feasible:
T Σ caE (xx))
min
s.t ((xr) 50,,
max h(xx)) S k=
(23)
0=0
min x.T
cl2k, (2x))
s.t s(xr) 10, Imaaxao..... h(2))20)
(24)
k=0
min R,
20 s.t.
Σ c(xxk n (xx)) s zo. g(xT) S0, ( h(Ew)20) S
(25)
min 20,T,7
s.t.
max Σ
caa, m((x)) 20. g(ar), I M(a))20)
50
(26)
min 20,4,7
s.t.
g(ir)
0
(27)
min 20
z0
s.t.
min min ((iT) <
(28)
min
20 s.t.
min Vi (iT) 0
(29)
20
This shows that the minimum-cost reach-avoid Problem is equivalent to the formulation we solve in this work (29). which is Problem 13 in the paper. The formulation of RC-PPO solves (29 and thus also solves Problem because they are equivalent.
C Optimal Reach Value Function
As shown in (8)), we introduce an additional discount factor into the estimation of V/ 3 imprecision the calculation of V defined in Definition 1 In this section, show that for large enough discount factor < 1. we could reach unbiased in phase two of RC-PPO.
will incur
16

---

Theorem 3. We denote max+ef (0(2)} ( positive value where
Gmaz and maximal episode length T Tmax. If there exists
( < 0 9(3) -c.
Then for any under given policy ग leading to the extended goal region G. We have
Tmax
Gmaz for any deterministic policy π satisfies 18 If there exists a trajectory
max
i < O.
The proof for Theorem iis provided in Appendix D.4
D
Proofs
D.1
Proof for Theorem
Proof. We separately consider three elements augmented state (IT: Vr, 2r). First, note that 3b
holds if and only if 2r E G. For the second element from the definition of the augmented dynamics
7 holds that
max IZ.EF (J.....)
(30)
As a result 3c holds if and only if yr = -. For the third element z, note that 27 = 20
Eiz c( u(x))) Hence, if and only if 20 2 Ek= c(E,, u(x)))
D.2 Proof for Property
12
Proof. From Definition 1 know
(+)
min g ( = i)) rENl
min(ū(f), min g( 100 = a)) tEN
min(g((), VT (#++1))
D.3
Proof for Theorem
We first derive the state value function in recursive form similar as (66
Proof.
V
V.
=8
Σ ao( 23)27 (2,u)
nel
Σ
V Vomo(u 23) (.u) mo(u V (e: ():u)
uell
Σ
VoTo (z)2 (i,
wedd
+ To(u V min(((@)), Vi (t'))
Σ
VoTo(W T) (δ.u) u)
To(u [ p())) Va Vm (t')
17

---

where H' = 2
Next, we consider unrolling Vi (ø') under Reachability MDP in Definition
We define Pr(ă +
at, k, TD) as the probability of transitioning from state I to ff in l steps under policy Te in Note that L 1,) (81) is absorbed using the absorbing state in 2 Then we can get
Vol. (8) 9
E
Σ Pr(a +tt
Σ wEl
VTo(u i (
(it, .))
StEd
Edd med' ($) (~T0 (&', u) Ve In me (u (3)
D.4 Proof for Theorem
Proof. Consider trajectory {ēo..... .T) where 27 E G. We consider the worst-case scenario where
g(t+) = Imax for E T'. 1}.
Then
V
(1 -0) + ( (
< (1 7m (+1)
< (1 3maa + +(((1
Mimau + >V²
70 7)mmaz (=T(T(
? Amar +7Te
E
Convergence Guarantee Actor-Critic Version of Our Method
In this section, we provide the convergence proof of phase one of our method under the actor-critic framework. Notice that similar to Bellman equation (88 for V We could also derive the Bellman equation for Q3 as
(Gr u.) = (1-7) + 7. fmin Q7 (2 14+1)
Next, we show our method under the actor-critic framework without GAE estimator Algorithm
Algorithm I RC-PPO (Actor Critic)
Require: Initial policy parameter fg. Q function parameter wo. horizon T, convex projection operator
Te. and value function learning rate (k)), policy learning rate (2(k)
1: for k = 0, I.... do
2: for t= to T-1
3:
Sample trajectories : {āt, ut, 8++1}
4:
Critic update: wh+1 W/: B1 (R) Qg (6t, ue;
[Q (&e, wjww)) ((1- (ft( min ((tc), ,) Qg (8e+1 uet1i wix)))
5:
6: Actor Update: 0k+1 Te (0x (2) (fr, w(iw)) Vo log vo (ue fite)
7: end for
8: end for
9: return parameter 0,
18

---

In this algorithm, the (0) operator projects vector 0 R to the closest point in compact and convex set θ C IR* i.e. (0) = arg mingree 10/--113
Next, we provide the convergence analysis for Algorithm I under the following assumptions.
Assumption 1. (Step Sizes) The step size schedules { (k) and (32(k) have below properties:
E Bi(k) = Σ B2(k) = 00
Σ (k)) : Σ 82(k)² < oo
32(k) (k))
Assumption 2. (Differentiability and and Lipschitz Continuity) For any state and action pair (æ, u). Q2,2, w;w) and ((;; 0) are continuously differentiable in and 6, Furthermore, for any state and action pair (i, u). Qu (δ, u; w;w) and (á;; 0) are Lipschitz function in and 0.
Also, assumee that X and U finite and bounded and the horizon T is also bounded by T maxx then the cost function e can be bounded by Cmax and g can be bounded within G Gmax- We can limit the space of cost upper bound
for 2 S - Next, we could do discretization on [-G T Cmax] and cost function to make the augmented state set X finite and bounded.
[-G T Cmax] instead of I. This is due to g(2)
With the above assumptions, we provide convergence guarantee for Algocrithml ! Theorem Under Assumptions 1 and 2 a locally optimal policy.
the policy update in Algorithm converge almost surely
Proof. The proof follows from the proof of Theorem 2 in 75 differing only in whether update exists for the Lagrangian multiplier. We provide a proof sketch as
* First, prove that the critic parameter almost surely converges fixed point w",
This step guaranteed by the assumption of finite and bounded state and action set and Assumption The 7-contraction property of the following operator
B Bi (f, u)] =(1 - (+) + "R [min (i(+), Q u)}]
(31)
is also proved in Lemma B.1 in 75 to make sure the convergence of the first step.
Second, due to the fast convergence of w", we can show policy paramter 0 converge almost surely to a stationary point 0* which can further proved be a locally optimal solution.
We refer to
75 for proof details.
F
Implementation Details of Algorithms
In this section, will provide more details about CMDP based baselines (different between opti- mization goal with multiple constraints) and other hyperparameter settings like Xehreshold
F.1 CMDP-based Baselines
In this section, we will clarify the optimization target for CPPO and RESPO under CMDP formulation of both hard and soft constraints. Recall that our formulation of CMDP is
min 7T
Σ 7x((,, ut)
(32a)
s.t.
Exg
Σ
17' MzEr Craal S O,
(32b)
Exg rode
Σ
[7 (ofo( we)] S Xehroshold
(32c)
19

---

We then denote
V (xe) = ayd Σ (ns(( me)l
VJ (x1) = Exgardd E Inleer x Ccor
Ve (2+) = Eur E (n'e(2s, ue)
The optimization goal formulation for CPPO is as follows:
min max (L(=, A) V2 + A (VT Xahreshota) + X3 VJ (x))
In this formulation, the soft constraint V has the same priority as the hard constraint V7. This leads to potential imbalance between soft constraints and hard constraints. Instead, the optimization goal for RESPO is as follows:
min max L(T, A) ( V (a) Ao (V (3x) Kehreshola)
+ Xy (z)) (1 (()) + p(x) VF(x)
where p(æ) denotes the probability of entering the unsafe region start from state x. called the reachability estimation function (REF). This formulation prioritizes the satisfaction of hard constraints but still suffers from balancing soft constraints and reward terms.
F22 Hyperparameters
We first clarify how we set proper &thresbold for each environment. First, we will run our method RC-PPO and calculate the average cost, denote it as Caverage- We set Klow Saverags, Xmedium Cauerage and Knigh Caverage- For static lagrangian multiplier 3, set 310 0.1 and Ans 10. Also, we set Cfast = 20 in every environment.
Note that CRL is off- off-pooicy algorithm, while RC-PPO and other baselines are on-policy algo- rithms. We provide Table T showing hyperparameters for on-policy algorithms and Table showing hyperparameters for off- off-policy algorithm (CRL).
F.3 Implementation of the baselines
The implementation of the baseline follows their original implementations:
RESPO: httpll/wwwi.i.iiiiiiiiiiini/i/ir
(No license)
CRL: contrastive_ri] (No License)
G Experiment Details
In this section, we provide more details about the benchmarks and the choice of reward function r, g, function and Coast in each environment. Under the sparse reward setting, apply the following structure of reward design
r(I,, u4, (441) = Rgoot 12q1e9
where Ryoal is an constant. After doing reward shaping, we add extra term (0(x++1) - ((x:) and the reward becomes
r(E,, Ut, 11+1 Ryont layees v0(1241) ((xx)
where 7 denotes the discount factor.
Note that we set R Rgoal Ccost 20 in all the environments. Note that if there is a gap between max g(x) 0). we could get unbiased å during phase of RC-PPO guaranteed by Theorem To achieve better performance in phase two of RC-PPO, we set
g(x) 300
for x E G to maintain such gap. Also, we implement all the environments in 776 for better
scalability and parallelization.
20

---

Table I: Hyperparameter Settings for On-policy Algorithms
Hyperparameters for On-policy Algorithms
Values
On-policy parameters
Network Architecture
MLP
Units per Hidden Layer
256
Numbers of Hidden Layers
2
Hidden Layer Activation Function
tanh
Entropy coefficient Optimizer
Linear Decay 1e-2 0
Adam
Discount factor 7
0.99
GAE lambda parameter
0.95
Clip Ratio
0.2
Actor Learning rate
Linear Decay 3e-4 + 0
Reward/Cost Critic Learning rate
Linear Decay 3e-4
RESPO specific parameters
REF Output Layer Activation Function
sigmoid softplus
Lagrangian multiplier Output Layer Activation function
Lagrangian multiplier Learning rate
Linear Decay 5e-5 0
REF Learning Rate
Linear Decay le-4 -
CPPO specific parameters
Kp
1 le-4
Ki
KD
Table 2: Hyperparameter Settings for Off-policy Algorithms
Hyperparameters for Off-policy Algorithms
Values
Off-policy parameters
Network Architecture
MLP
Units per Hidden Layer
256
Numbers of Hidden Layers
2
Hidden Layer Activation Function
tanh
Entropy target
-2
Optimizer
Adam
Discount factor y
0.99
Actor Learning rate
Linear Decay 3e-4 - 0
Critic Learning rate
Linear Decay 3e-4 -> 0
Actor Target Entropy
0
Replay Buffer Size
1с6 transitions
Replay Batch Size
256
Train-Collect Interval
16
Target Smoothing Term
0.005
21

---

G.1
Pendulum
The Pendulum environment is taken from Gym space given by [0, 0] where - n regions and set
18 and the torque limit set be 1. The state In this task, we do not consider unsafe
8,8) 8].
g = {10,6) 0 + dt) < <
where 0.05 is the time interval during environment simulation. This is for preventing environ- ment overshooting during simulation.
In the Pendulum environment, cost function is given by
0 if | < 0.1
dae, ue, T++1) = 8||u||2
if
| 2 0.1
for better visualization of policies with different energy consumption, g is given by
[10082 if x gg
g(x) = -300 if xeg
G.2
Safety Hopper
The Safety Hopper environment is taken from Safety Mujoco, we add static obstacles in the envi- romment to increase the difficulty of the task. We use x to denote the x-axis position of the head of Hopper, y to be the y-axis position of the head of Hopper. Then the goal region can be described
= ((r,)) || [1, v)
[2.0, 1.4]] < 0.13
The unsafe set is described as
F= {(x y) 0.95 S x $ 1.05, y 2 1.3]
We use zthigh gleg gfoot to denote the angular velocity of the thigh, leg, foot hinge. The cost function is described as
c(2,, Uc, #e+1) 1(x thith ut) + 1(x, utt 1x u²)
where
if
|| bll < 0.4
l(a, b) = 0..15a b² if |a bl| > 0.4
g is given by
100 (x 2) + 100(y - 1.4) - 40 if 3 E g
g(
-300
if 2 E g
G.3 Safety HalfCheetah
The Safety HalfCheetah environment taken from Safety Mujoco, we add static obstacles in the environment to increase the difficulty of the task. We use front to denote the x-axis position of the front foot of Halfcheetah, front to the y-axis position of the back foot Halfcheetah, Thack to denote the x-axis position of the back foot of Halfcheetah, Yback to be the y-axis position of the back foot of Halfcheetah, Thead to denote the x-axis position the head of Halfcheetah, Whead be the y-axis position of the head of Halfcheetah. Then the goal region can be described
G = (Zheads Whead) [[ Yhead] [5.0, 0.0] < 0.2)
The unsafe set is described as
F = ((r Ufront)
Ufront < 00.25, 2.45 < 3. front 2.55)
U {(Dback Yback) Yback < 0.25, 2.45 < Tback < 2.55]
The cost function is described as g is given by
clTe, U4, xe+1) ||1+
/ ((Kead 2)2 + (Yhead 1.4)2 20 if igg -00
(
Teg
22

---

G.4 Fixed
FixedWing environment taken from [59] and we follow the same design F [59] We denote the PE as the eastward displacement of F16 with given state x. Then the goal region G is given by
g = {or 1975 I IPE S 2025)
The cost e is given by
c Uz F(+1) = 4 /// 11, 25, 25, 25
and y is given by
RaPE- [PPE-2000)
x E g if
((x)
300
if I E
G.S Quadrotor in Wind Field
We take quadrotor dynamics from crazyflies and wind field environments in the urban from 71 The wind field will disturb the quadrotor with extra movement on both r-axis and y-axis. There are static building obstacles in the environment and we treat them the unsafe region F. The goal for the quadrotor is to reach the mid-point of the city. We divide the whole city into four sections and train single policy on each of the sections. We use r E [-30, 30] denote the x-axis position of quadrotor, E [-30, 30] to be the y-axis position of quadrotor.
G = [(x
[ vl1l < 43
The cost e is given by
||u 12
cla, ue, F++1)
2
g is given by
10 (x Tgool + 10(y Ygoot)
40
g
g(t)
-300
x E G
G.6 PointGoal
The PointGoal environment is taken from Safety Gym 69 We implement PointGoal environments in Jax. In Safety Gym environment, do not perform reward-shapin and use the original reward defined in Safety Gym environments. this case, the distance reward is set also to be 20 in order to align* with Cyeat and Ceost- Different from sampling outside the hazard region which is implemented in Safety Gym, we allow Point to be initialized within the hazard region. We use x to denote the x-axis position of Point, y be the y-axis position of Point, Fooo to denote the x-axis position of Goal, and Yooal to denote the y-axis position of Goal. The goal region is given by
g == {(x, v) [|x vl - [Egatts Mgont] ||| S 0.3)
The cost e is given by
|| 12
clai, ue, x141)
2
g is given by
100 Rggoal? + (y ygoat) 2- 30 if r & -300
g(5)
r E g
G.7 Experiment Harware
We run our experiments on computer with CPU AMD Ryzen Threadripper 3970X 32-Core Processor and with GPUs of RTX3090. It takes at most 4 hours to train on every environment.
23

---

H
Additional Experiment Results
We put additional experiment results in this section.
H.1 Additional Cumulative Cost and Reach Rates
We show the cumulative cost and reach rates of the final converged policies for additional environ- ments (F16 and Safety Hopper) Figure
Additional Cumulative Cost
Additional Cumulative Cost
RC-PPO RESPO
RC-PPO
RESPO
PPO_8.
PPO BL" SAC BL-
SAC BL
CPPO Ax
CPPO AM
CPPO_X, CRL
CºPО_*,
80
160
240
100
200
300
400
Reach Rate
Reach Rate
RC-PPO
RC-PPO
RESPO
RESPO
PPO BL_
PPO BL
PPO_ BH
PPO BH
SAC
SAC B
SAC
SAC Bu
CPPO XL
CPPO
CPPO XM
CPPO Xx
CPPO Al
CPPO XH
CRL
0.0
0.2
0.4
0.6
0.8
0.0
0.2
0.4
0.6
0.8
1.0
(a) FixedWing
(b) Safety Hopper
Figure 7: Cumulative cost and reach rates of the final converged policies.
H.2 Visualization of learned policy for different
To obtain better intuition for how the learned policy depends on z, we rollout the policy choices of zo in the Pendulum environment and visualize the results in Figure
7ap
Zoe
Pay + 102
Tui 200
25
-59
Regt
Curnuletive
200
200
+ 100
200
0-
Regl
100
200
300
400
500
Timestep
Figure 8: Learned RC-PPO policy for different on Pendulum For a smaller cost lower-bound 2, cost minimization is prioritized at the expense of not reaching the goal. For a larger cost fower-boumd 2, the goal is reached using a large cumulative cost. Performing rootfinding solve for the optimal Zopt automatically finds the policy that minimizes cumulative costs while still reaching the goal.

---

Algorithm
Large Noise Reach Rate
Small Noise
Large Noise
RCPPO
1.00
1.00
1.00
RESPO
1.00
1.00
1.00
PPO 3r.
1.00
1.00
1.00
PPO Bиr
0.31
0.38
0.34
SAC BL
1.00
1.00
1.00
SAC 8H
0.21
0.37
0.20
CPPO Xt
0,67
0.65
0,65
CPPO XMs
1.00
1.00
1.00
CPPO Xh
1.00
1.00
0.99
CRL
1.00
1.00
1.00
Table 3: Reach rate final converged policies with different levels of noise to the output control
Algorithm
Additional Cumulative Cost
Small Noise
RCPPO RESPO
35.3
41.4
132.9
92.0
93.6
179.2
PPO BL
97.7
98.6
150.2
SAC 8L
156.3
157.6
270.5
CPPO X'M
223.2
220.5
209.0
CPPO XH
212.7
299.8
298.4
CRL
228.3
229.1
261.1
Table 4: Additional cumulative cost of final converged policies with different levels of noise the output control
H.3 Grid search
We perform an extensive grid search over different reward coefficients for the baseline PPO method and plotted the Pareto front across the reach rate and cost in Figure The reward we use is
Rgoat leeg Pyout Lzęg - -3((z, u).
and search the Cartesian product of Ryoal {1, 10, 100, 1000, 10000), = 1,
[2, 20, 200, 2000, 20000), Pgoal
H.4 Performance with external noise
We also performed additional experiments to illustrate the performance of RC-PPO under changing environment. Specifically, we add uniform noise to the output of the learned policy and see what happens in the Pendulum um environment.
We first compare the reach rates of the different methods Table 3 In this environment, we see that noise does not affect the reach rate too much
Next, look how the cumulative cost changes with noise by comparing methods with a near 100% reach rate Table Unsurprisingly, larger amounts of noise reduce the performance of almost all policies. Even with the added noise, RC-PPO uses the least cumulative cost compared to all other methods.
I Discussion on Limitation of CMDP-Based Algorithms
In this section, we will use an example to illustrate further why CMDP-based algorithms won't solve the minimum-cost reach-avoid problem optimally compared with our method. We focus two parts of CMDP formulation:
Weight coefficient assigned different objectives
Threshold assigned to each constraint
25

---

A
Pa
1 1-Pa Pa
1 -
30
G1
G2
G3
Figure 9: Minimum-cost reach-avoid example to illustrate the limitation of CMDP-balr -based formulation.
Consider the minimum-cost reach-avoid problem shown in Figure where cost. States A and B are two initial states with the same initial distribution probability. State G1+ G2, and Ga are three goal states. State is the absorbing state (non-goal). We use pa and pn to denote the policy parameter, which represents the probability of choosing left action on state A and B separately.
C to denote the
The optimal policy for this minimum-coss reach-avoid problem is to take the left action from both A and B, i... PA pB = 1, which gives expected cost of
0.5 10 + 0.5 30 20
To convert this into a multi-objective problem, we introduce reward that incentivizes reaching the goal as follows (we use R to denote reward):
G1) 10, R2), 20, R() 20, R(A,I) 0
(33)
This results in the following multi-objective optimization problem:
min
(-R,C)
(34)
PA.P
I.1
Weight assignment
We first consider solving multi-objective optimization Problem 34 by assigning weights on different objectives. We introduce 2 0, giving
min PA.PSE(0,1
-R + wC
(35)
Solving the scalarized Problem 34 gives us the following solution as a function of w:
PA - PB 1 (wS
(36)
Notice that the *true optimal solution of PA = pn 1 is NOT an optimal solution to the original minimum-cost reach-avoid problem shown in Figure g under any w.
Hence, the optimal solution the surrogate multi-objective problem can be suboptimal for the original minimum-coss reach-avoid problem under any weight coefficients.
Of course, this is just one choice of reward function where the optimal solution of the minimum-cost reach-avoid problem cannot be recovered. Given knowledge of the optimal policy, we can construct the reward such that the multi-objective optimization problem does include the optimal policy as solution. However, this is impossible to do if we do not have prior knowledge of the optimal policy, as is typically the case.
1.2 Threshold assignment
Next, we consider solving multi-ohjecciive optimizztionn Problem 34 assigning threshold X _hrthh on the cost constraint:
0.5(10p4 20(1 PA)) + 0.5(30pp) Xiresh
(37)
The optimal solution this CMDP can solved to be
X
10
PA 0, Pn
(38)
15
26

---

However, the true optimal solution of PA PB is NOT an optimal solution to the CMDP. To see this, taking X thresh 20, the real optimal solution P4 = P but the CMDP solution PA = Pm =
1 gives reward of 15,
20 13
gives R = 23.33 >> 15. Moreover, any uniform
scaling of the rewards or costs does not change the solution.
We can "fix" this problem if we choose the rewards to be high only along the optimal solution PA pB- I, but this requires knowledge of the optimal solution beforehand and is not feasible for all problems.
Another way to "fix" this problem is if consider "per-state" cost threshold, e.g..
A + 20(1 PA)- - NA. 10pB + 20(1 PB) S NB
(39)
Choosing exactly the cost of the optimal policy, i.e., X'A = 10 and X' 2 30, also recovers the optimal solution of PA Pn 1. This now requires knowing the smallest cost to reach the goal for every state, which is difficult to do beforehand and not feasible. On the other hand, RC-PPO does exactly this in the second phase when optimizing for zo. We thus interpret RC-PPO as automatically solving for the best cost threshold to use as a constraint for every initial state.
J Broader impact
Our proposed algorithm solves an important problem that is widely applicable many different real-world tasks including robotics, autonomous driving, and drone delivery. Solving this brings us one step closer to more feasible deployment of these robots in real life. However, proposed algorithm requires GPU training resources, which could contribute to increased energy usage.
27

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and precede the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No] or [NA]. .
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justificatin right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation.
While "[Yes] " is generally preferable to "[No]" ", is perfectly acceptable to answer "[No] "provided proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
general, answering
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS paper checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only the provided macros for your answers.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The main contributions of the paper are summarized the Introduction section well as in the abstract of the paper, describing the proposed method briefly well as its ad advantages compared to the existing methods.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
28

---

Justification:
Yes, we have discussed about the limitation of the work in Section 6
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "I "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model sellispecifiitiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-texi system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't "t acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: Yes. The completed proofs provided in the Appendix (see Appendix C for example)
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: Yes. We provide details on all experiments and baselines used. Moreover, we provide the code used reproduce our results.
Guidelines:
29

---

The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open- source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibilityy In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: Yes, the code used for generating the results in the paper has been provided.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
owt.ssubbbiiiooooioooooooooooiii for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https c/tpps.cc/public//uue
CodeeSumiiii wwabbbmssssiinii ssionpolicyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
30

---

Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
Yes. The full details are provided in the Appendix.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Yes, we report confidence intervals our plots. See Section
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (c.g. negative error rates).
show in tables
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Yes, all the required computational resources used for generating the results are provided with the experiment details.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
31

---

The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics httpps//neurrps... http::///.uarr...oooaaaaaccaaaaa
Answer: [Yes]
Justification: Yes, the research conducted this paper adheres to the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Yes, see Appendix D
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has socictal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses such risks.
Guidelines:
32

---

The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: The license of our baselines are mentioned Appendix F33
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. www.coo/caaa hom/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-pane se-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: include the code of the algorithm in the supplementary materials. Imple- mentation details are introduced Section and Appendix
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/codeemooell as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Question:
Answer: [NA]
33

---

Justification:
The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
34


Reviews:
[{"review_id": "MkTF1sYy3U", "reviewer": "Reviewer_186A", "summary": "This paper proposes Reach Constrained Proximal Policy Optimization which targets to solve the minimum-cost reach-avoid problem. The authors first convert the reach-avoid problem to a reach problem on an augmented system and use the corresponding reach value function to compute the optimal policy. Next, The authors use a novel two-step PPO-based RL-based framework to learn this value function and the corresponding optimal policy.", "questions": "1.What is the motivation for using two-phase PPO to solve this problem? Providing performance comparisons with other RL algorithms, such as TD3 and SAC, will significantly strengthen the rationale behind proposing this approach.\n\n2.To verify the statement in the abstract, \"which leads to suboptimal policies that do not directly minimize the cumulative cost,\" the authors should compare the performance of RC-PPO with other multi-objective optimization algorithms.", "limitations": "3. Please reconsider whether it is reasonable to reformulate the minimum-cost reach-avoid problem by constructing an augmented system, as the limitation that \"two policies that are both unable to reach the goal can have the same value even if one is unsafe\" is undesirable.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1.The studied problem is interesting\n2.This paper is easy to follow", "weaknesses": "1.What is the motivation for using two-phase PPO to solve this problem? Providing performance comparisons with other RL algorithms, such as TD3 and SAC, will significantly strengthen the rationale behind proposing this approach.\n\n2.To verify the statement in the abstract, \"which leads to suboptimal policies that do not directly minimize the cumulative cost,\" the authors should compare the performance of RC-PPO with other multi-objective optimization algorithms.\n\n\n3. Please reconsider whether it is reasonable to reformulate the minimum-cost reach-avoid problem by constructing an augmented system, as the limitation that \"two policies that are both unable to reach the goal can have the same value even if one is unsafe\" is undesirable.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> ### What is the motivation of using two-phase PPO to solve this problem?\n\n**The minimum-cost reach-avoid problem (1) cannot be *exactly* framed into problem structures that existing methods are able to solve.**\nOur two-phase method _directly_ solves the minimum-cost reach-avoid problem (1). In comparison, alternate RL methods either:\n1. _Only_ solve the reach-avoid problem without consideration of the cumulative cost.\n2. Solve _unconstrained_ problems (e.g., PPO, SAC, TD3)\n3. Solve problems with CMDP constraints that constrain the _expectation over initial states_ of the sum of some cost function (e.g., CPPO, RESPO)\n\nSince the minimum-cost reach-avoid problem (1) cannot be _exactly_ framed into any of the above problem types, this \"prevents the straightforward application of existing RL methods to solve (1)\" (L110).\n\nWe introduce a two-phase method to extend reachability analysis to \"additionally enable the minimization of the cumulative cost\" (L126) on top of solving the traditional reach-avoid problem by constructing a new constraint called the \"upper-bound property\"  (L145) which enforces that \"$z_0$ is an upper-bound on the total cost-to-come\" (L144).\n\n1. The first phase uses PPO to learn a _stochastic_ policy $\\pi$ and corresponding value function $\\tilde{V}_{\\hat{g}}^\\pi$ for different states $x$ and upper-bounds $z_0$.\n2. However, the reachability analysis relies on a deterministic policy. Hence, in the second phase, we take a deterministic version of the learned stochastic policy $\\pi$ and fine-tune the learned value function $\\tilde{V}^{\\pi}_{\\hat{g}}$ on this deterministic policy.\n3. Using the fine-tuned value function $\\tilde{V}_{\\hat{g}}^{\\pi}$, we can then find the smallest $z_0$ that satisfies the constraint (8b), which will then \"corresponds to the minimum-cost policy that satisfies the reach-avoid constraints\" (L164).\n\n---\n> ### Providing performance comparisons with other RL algorithms, such as TD3 and SAC, will significantly strengthen the rationale behind proposing this approach\n\n**Thank you for the suggestion!** Although we believe our approach to already be empirically well-motivated by the lower cumulative cost of our proposed method (Figure 4), **we have performed additional comparisons to SAC and PPO with more extensive reward shaping in the attached PDF**. The additional experiments lead to the same conclusion as in the main paper: because RC-PPO solves the original problem (1), it can achieve \"significantly lower cumulative costs\" (L265) while remaining \"competitive against the best baseline algorithms in reach rate\" (L264).\n\n---\n> ### To verify the statement that solving the surrogate problem \"leads to suboptimal policies that do not directly minimize the cumulative cost\", the authors should compare the performance of RC-PPO with other multi-objective optimization algorithms\n\nAs described in Section 5 (L231), we **already** compare RC-PPO against other methods that solve the surrogate CMDP problem (16) and find that \"RC-PPO remains competitive against the best baseline algorithms in reach rate while achieving significantly lower cumulative costs\" (L264, Figure 4). The reason why the baseline methods achieve a higher cumulative cost and are more suboptimal is _precisely_ because they are only able to solve a surrogate (16) instead of the true constrained optimization problem (1).\n\nAlthough we have compared against CPPO and RESPO, which are _single-policy_ multi-objective optimization algorithms [1,2], there also exist _multi-policy_ multi-objective optimization algorithms which aim to recover an approximation of the entire Pareto front [1,2]. We wish to emphasize that the minimum-cost reach-avoid problem does _NOT_ require solving for the entire Pareto front, as there is only a _single_ cumulative cost function albeit with multiple constraints. Even if the Pareto front was given, the optimal solution to (1) would still need to be found on the surface of the Pareto front, which is not a simple task.\n\n---\n> ### The limitation that \"two policies that are both unable to reach the goal can have the same value even if one is unsafe\" is undesirable.\n\n**While this is undesirable, this is an artifact of our problem formulation (1)** where we pose a constrained optimization problem. Since the reach and avoid components are both constraints and hence \"equal\", any candidate that does not satisfy both constraints is _infeasible_ regardless of whether it is safe or not. We are happy that you agree this is an important future direction to investigate, which we have mentioned in the limitations section (Section L293). Since this is not an issue from the perspective of our current problem formulation (1), we believe it to be out of the scope of the current work, and \"leave resolving these challenges as future work\" (L297).\n\n---\n\n[1] Policy Gradient Approaches for Multi–Objective Sequential Decision Making\\\n[2] Empirical evaluation methods for multiobjective reinforcement learning algorithms", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "NpbPpaNxZT", "reviewer": "Reviewer_zsEG", "summary": "The paper introduces RC-PPO, an RL algorithm designed to solve the minimum-cost reach-avoid problem by reformulating the optimization problem on an augmented system. The paper addresses the limitations of current RL that mostly solve surrogate problems to fit to the problem setting. Furthermore, a comprehensive analysis, including theoretical foundations, algorithmic details, and empirical validation is presented. Experimental comparison with respect to existing methods is also provided.", "questions": "In Section 5, the paper claims that RC-PPO remains competitive which is based on Figure 6. Can you either elaborate how this claim can be made from Figure 6, or maybe it should be Figure 4?", "limitations": "Limitations are briefly discussed.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper (including the appendix) provides solid theoretical foundation, including proofs and detailed explanations of the key concepts and assumptions.\nThe paper is overall well-written, definitions and theorems are formulated clearly. The main thread of the paper can be followed.\nThe presented experimental results are well illustrated and generally the claims based on the results are comprehensible. \nIn addition to solid theoretical arguments, the appendix also provides vast implementational details and further experimental results.\nThe presented idea seems to offer an elegant solution to minimum-cost reach-avoid problems. \n\nOverall a nice and insightful read.", "weaknesses": "(minor)\nThe presented experimental results are solid and illustrative, but could be extended. \nThe extra title of Figure 3 is slightly irritating.\nFigure 3 and Figure 4 use different axis labeling logic.\nAppendix G.2 is empty (- a formatting problem?).\nThere are typos, missing spaces, missing punctuation, repeated words and repeated phrases in the paper, e.g., L99, L186, L187, L193, L200, L206, L210+L225, L215, L232, L570.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> ### In Section 5, the paper claims that RC-PPO remains competitive which is based on Figure 6. Can you either elaborate how this claim can be made from Figure 6, or maybe it should be Figure 4?\n\n**You are correct, this should be Figure 4**.\n\n> ### The presented experimental results are solid and illustrative, but could be extended.\n\n**Thank you for the suggestion!** We have included additional comparisons to SAC (Figure 1 in the pdf), though the conclusions in the paper remain the same. We have also performed an extensive grid search over different reward coefficients for the baseline PPO method and plotted the Pareto front (Figure 2) across the reach rate and cost. Notably, RC-PPO vastly outperforms the entire Pareto front, demonstrating that methods that solve the surrogate problem yield suboptimal policies due to not solving for the minimum-cost reach-avoid problem _directly_.\n\nIf you have any further suggestions on how the presented experimental results could be extended, we would _love_ to hear your thoughts!\n\n---\n> #### The extra title of Figure 3 is slightly irritating. Figure 3 and Figure 4 use different axis labeling logic. Appendix G.2 is empty (- a formatting problem?). There are typos, missing spaces, missing punctuation, repeated words and repeated phrases in the paper, e.g., L99, L186, L187, L193, L200, L206, L210+L225, L215, L232, L570.\n \n**Thank you for the meticulous reading of the manuscript!** Unfortunately, NeurIPS does not allow for uploading a new version of the manuscript, but we will definitely include the changes in the final version.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "yCCsa6i6lV", "reviewer": "Reviewer_M8co", "summary": "The papers coinsiders a reach-avoid problem under cost minimization objective, where a CMDP has to be solved under the goal and avoid constraints (the final state has to be in the certain set, and the trajectories must avoid an unsafe region). The authors derive an optimal control problem under these constraints and show how to solve it in the RL setting. The results show an improvement in terms of the optimized objective in comparison with method that include the goal objective in the optimization cost.", "questions": "1. I appreciate it’s a personal preference, but I don’t see the need to formulate the optimal control problem as cost minimization. Furthermore, in safe RL the costs typically refer to constraints.\n2. Line 33 “Moreover, the use of nonlinear numerical optimization may result in poor solutions that lie in suboptimal local minima [14].” How does the paper address this issue? Wouldn’t any hard problem have the same problem?\n3. Line 38 “However, posing the reach constraint as a reward then makes it difficult to  optimize for the cumulative cost at the same time.”. I think adding a penalty for not reaching the goal will address this issue. Recall that in RL the rewards need not to be differentiable. \n4. Line 45. “However, the choice of  this fixed threshold becomes key: too small and the problem is not feasible, destabilizing the training  process. Too large, and the resulting policy will simply ignore the cumulative cost.” - I am not sure this statement is necessary. Problem statement is a bit of an art and the threshold is chosen on the problem design level. Sometimes it is simply given.", "limitations": "limitations are discussed", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The paper delivers well the proposed solution and the state augmentation technique that the authors propose seem to be crucial to the solution. The algorithm does outperform the competitors, where the goal is included in the objective.", "weaknesses": "1. The state augmentation is not a novel technique in constrained RL, (see references below) albeit the application here is different.\n1. I am not fully convinced that this is actually an important sub-problem in RL to solve. Can the authors elaborate why we should consider this problem in more detail? For instance, can we formulate safety gym benchmarks as this?\n1. Some of the design choices are not fully clear, why the authors minimize the initial state z_0 with the constraint z_t >=0. Wouldn't it be easier to track the accumulated cost and minimize the terminal state?\n1. I am not fully convinced that there are no simpler methods to solve this problem. For example, for the baselines, the authors reshape the reward by giving a modest reward for goal reaching. I’d like to see experiments with heavy penalization of not reaching the goal (for example, a scale from -10 to -10000) and different rewards for reaching the goal (not just one 20). \n\n\n* [Sootla et al 22] Sootla, Aivar, et al. \"Sauté rl: Almost surely safe reinforcement learning using state augmentation.\" International Conference on Machine Learning. PMLR, 2022.\n\n* [Jiang et al 23] Jiang, Hao, et al. \"Solving Richly Constrained Reinforcement Learning through State Augmentation and Reward Penalties.\" arXiv preprint arXiv:2301.11592 (2023).\n\n* [Jiang et al 24] Jiang, Hao, et al. \"Reward Penalties on Augmented States for Solving Richly Constrained RL Effectively.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 38. No. 18. 2024.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">## The paper considers ... where a CMDP has to be solved\n\nWe want to clarify **the minimum-cost reach-avoid problem is NOT a CMDP [1]** (e.g., as used in [2,3,4]), since it is NOT in the following form:\n$$\n\\max_\\pi \\quad \\mathbb{E}\\left[ \\sum_{k=0}^\\infty r_k \\right],\\quad \\textrm{s.t.} \\quad \\mathbb{E}\\left[ \\sum_{k=0}^\\infty d \\right] \\leq c_\\max.\n$$\n\n---\n>## State augmentation is not a novel technique, albeit the application is different.\n\n**Thank you for the references to state augmentation, we will include them and discuss the relationship with our work in the final version. We use state augmentation differently to the referenced works**. We emphasize that the novelty is in the framework for solving minimum-cost reach-avoid problems. We _DO NOT_ claim to be the first to propose the _idea_ of state augmentation. Moreover, while [2-4] use the augmented state to satisfy CMDP constraints by modifying the reward function but keeping the same value function, we use the augmented state to enforce the \"upper-bound property\" (L145) and apply it to the reachability Bellman equation (7).\n\n---\n>## Why is minimum-cost reach-avoid an important problem?\n\n**Minimum-cost reach-avoid (MCRA) is an important real-world problem, especially for \\*climate change\\*, but RL existing methods do not \\*directly\\* solve the problem.** In addition to \"energy-efficient autonomous driving\" (L20) and \"spacecraft and quadrotors\" (L23) mentioned in the introduction, we highlight the additional use cases of plasma fusion [5] (reach desired current, minimize total risk of plasma disruption) and voltage control [6] (reach voltage level, minimize load shedding amount).\n\n**Examples of MCRA in RL benchmarks:** Lunar Lander (reach goal, avoid crash, minimize thrusters), Reacher (reach goal, minimize control effort), PointGoal (reach goal, avoid unsafe region, minimize time).\n\nSince existing RL methods do not directly solve the minimum-cost reach-avoid problem, a surrogate problem needs to be manually designed. We show in Figure 4 that these methods achieve _suboptimal_ cumulative costs due to the use of this surrogate problem. This motivates us to construct a method that can solve MCRA _directly_.\n\n---\n>## Can simpler methods solve this problem with the right reward function coefficients? \n\n**Unfortunately, no choice reward function coefficients match the performance of our RC-PPO even after an extensive search over the coefficients**. As suggested, we have added a penalty for not reaching the goal and performed an _extensive_ grid search over the coefficients of the reward function.\n\n**We plot the results in Fig. 2 in the response pdf (see caption for grid search details)**. Different choices of the coefficients trade between reach rate and cost, forming a Pareto front. However, even the best point is sub-optimal compared to our RC-PPO.\n\n---\n>## Problem statement is a bit of an art. Sometimes it is simply given.\n\n**We agree that, given a minimum-cost reach-avoid problem, constructing a surrogate problem that yields a good solution to the original problem is hard.** If a (C)MDP is given then it can be solved directly. However, if a minimum-cost reach-avoid problem is given, it makes more sense to solve the problem _directly_ instead of relying on the \"art\" of reward function design to convert it to a (C)MDP. Moreover, the answer above shows that sometimes _no_ choice of coefficients gives the optimal solution.\n\n---\n>## Why minimize the z_0 with the constraint z_t >=0?\n\nWe DO NOT impose the constraint z_t >=0, as the question implies. \n\nThe challenge of solving _constrained_ optimization problems is in handling the interplay between the _objective_ and the _constraint_. If it were only the _objective_, then unconstrained optimization methods can be used. Similarly, if there were only _constraints_, then reachability can be used.\n\nOur strategy in this work belongs to the latter approach, where we convert the cumulative cost _objective_ $\\sum_{t=0}^{T-1} c$ into a cumulative-cost upper-bound _constraint_ (L145)\n$$\n\\sum_{t=0}^{T-1} c(x_t, u_t) \\leq z_0.\n$$\nThis gives us a problem with only three constraints, which we can solve using reachability. \n\nIf all constraints are satisfied (i.e., the goal is reached on the augmented system) for some $z_0$, then the cumulative cost is less than $z_0$ AND the other constraints are satisfied, which means the original constrained problem (1) can be solved with an objective of less than $z_0$. Consequently, the smallest $z_0$ that still satisfies all the constraints \"thus corresponds to the minimum-cost policy that still satisfies the reach-avoid constraints\" (L164).\n\n**Note**: As we write in Remark 1, our strategy here \"can be interpreted as an epigraph reformulation of the minimum-cost reach-avoid problem (1)\" (L168). This epigraph reformulation technique is standard optimization [7, p.134] but is not that well known.\n\n>## Would it be easier to track the accumulated cost and minimize the terminal state?\n\n**This is what we already do!** The reachability problem on the augmented system (4, 5) aims to keep the cumulative cost below $z_0$ and reach the goal at some terminal time.\n\n---\n>## “nonlinear numerical optimization may result in ... suboptimal local minima [14].” How does the paper address this issue?\n\n**We do not claim to address the local minima issue for RL**. Rather, this sentence only serves to illustrates a weakness of nonlinear trajectory optimization when compared to RL which has been well-established previously in the literature [8,9].\n\n---\n[1] Altman 1999, \"CMDP\"\\\n[2] Aivar et al 2022, \"Sauté rl...\"\\\n[3] Jiang et al 2023, \"Solving Richly...\"\\\n[4] Jiang et al 2024, \"Reward Penalties...\"\\\n[5] Wang et al 2024, \"Active Disruption Avoidance ... Tokamak ...\"\\\n[6] Huang et al 2020, \"Accelerated DeepRL ... Emergency Voltage Control\"\\\n[7] Boyd 2004, \"Convex optimization\"\\\n[8] Suh 2022, \"Do Differentiable...\"\\\n[9] Grandesso 2023, \"CACTO...\"", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their valuable comments. 

We are excited that the reviewers identified that we provide a _novel_ ($\color{#E24A33}{\textsf{M8co}}$) and _elegant_ ($\color{#348ABD}{\textsf{zsEG}}$) solution to the minimum-cost reach avoid problem that _improves upon the optimized objective_ ($\color{#988ED5}{\textsf{186A}}$) in comparison to existing methods, _addressing the limitations of current RL methods_ ($\color{#348ABD}{\textsf{zsEG}}$). Reviewers found our paper _well-written_ ($\color{#348ABD}{\textsf{zsEG}}$, $\color{#988ED5}{\textsf{186A}}$) and _easy to follow_ ($\color{#E24A33}{\textsf{M8co}}$, $\color{#348ABD}{\textsf{zsEG}}$). We believe that RC-PPO takes a significant step towards new RL algorithms that can solve minimum-cost reach-avoid problems by construction without the need for complex reward design.

---

# New Experiments

As _all_ reviewers have recognized our technical novelty, the primary criticism comes from an insufficient comparison to alternative RL methods ($\color{#E24A33}{\textsf{M8co}}$, $\color{#988ED5}{\textsf{186A}}$) and the necessity of RC-PPO for solving minimum-cost reach-avoid problems ($\color{#988ED5}{\textsf{186A}}$).
In the **attached PDF (below)**, we present
1. Additional comparisons with SAC on the six benchmark tasks in Fig 1 (as suggested by $\color{#E24A33}{\textsf{M8co}}$)
2. New comparison against an _extensive_ grid search over different reward coefficients in Fig 2 (as suggested by $\color{#988ED5}{\textsf{186A}}$).

In particular, the grid search over reward coefficients in Fig 2 forms a Pareto frontier, where different reward coefficients trade between the reach rate and the cumulative cost. **RC-PPO outperforms the _entire_ Pareto frontier, with _no single point on the Pareto frontier coming close to simultaneously achieving the high reach rates and low costs that RC-PPO achieves_**.

These results strengthen our argument that existing methods will lead to suboptimal policies since they do not _directly_ solve the minimum-cost reach-avoid problem. In contrast, RC-PPO is unique in that it solves the minimum-cost reach-avoid problem _directly_ and hence achieves lower cumulative costs.

We have tried our best to resolve all raised questions in the individual responses below. If you have any additional questions/comments/concerns, please let us know. We appreciate the reviewer's precious time in providing their valuable feedback.

---

**Please see the additional figures in the PDF below:**

Meta-review: The paper presents a method for solving Minimum-Cost Reach Avoid problems using RL. These are goal-driven sequential decision problems which include both constraints (avoiding set of states) together with minimization of cumulative cost. The authors consider the deterministic setting.

The paper is generally clearly written and easy to read.

The first proposed idea is to augment the state to include 'cumulative' information regarding the avoiding set of states (whether an avoiding state has been visited or not, so far) and the accumulated cost (actually z_0 minus the accumulated cost so far), where z_0 is some "upper bound" of the optimal cost at the initial state. Augmented state transition and goal states are also defined accordingly.

This idea is simple and it is difficult to see a priori how such a rewriting of the original problem can lead to any computational benefit. This reformulation also leads directly to the question of how to choose z_0.

The authors then derive a two-phase approach to compute a policy and approximate z_0 in this augmented problem (section 4).

For that, the 1st phase (and here is where the paper gets a bit confusing) reformulates the augmented problem as a discounted RL where a stochastic policy is used (Algorithm 1). This makes the problem amenable for using PPO and strongly relies on the results and method proposed in Hsu et al. (RSS, 2021 ref [28]). Critically, the value of z_0 is just used as ... another parameter? This is not specified in the paper. It is briefly mentioned in the first reply to Reviewer 186A, but not in clarifying detail:

- "The first phase uses PPO to learn a stochastic policy $\pi$ and corresponding value function $\tilde{V}_{\hat{g}}^\pi$ for different states $x$ and upper-bounds $z_0$."

The 2nd phase (Algorithm 2) serves two purposes: (1) making the stochastic policy obtained during the first phase deterministic, and (2) finally optimizing z_0 (a one dimensional optimization problem for a fixed policy/value function).

The method is then compared against two experimentally in a large variety of tasks showing in all of them competitive or superior performance of the proposed RC-PPO method. The baselines require some design choices that are stated in the paper but more details to guarantee reproducibility would be desirable.

I have several comments:

- A two phase approach could be better motivated/justified. It seems that authors identify RL with the tasks where PPO can be applied to.

- Any mention to z_0 in phase1 is avoided. This is a critical issue. If phase one is supposed to do policy optimization in the augmented problem, what is the value of z_0 chosen then? To me this essentially means solving a problem with the original complexity (finding an accurate optimal cost for the initial state) using RL. Wouldn't the parameter z_0 play a similar role than the threshold used in CMDPs? 

- Besides finding z_0^*, the motivation of phase 2 is to make the policy deterministic. Why not just a single phase 1 and decrease the stochasticity of the policy gradually until it becomes deterministic?

- Since the approach strongly relies on ref [28]. Why not compare experimentally with that work?

These are other minor points 

- line 192: the augmented dynamic equation is (4), not (5).

- lines 179 and 182, it seems some tildes and hats are missing in the value function.

- line 204: "get 'true'" -> "get the 'true'" and "Thus stationary" -> "Thus, the stationary"

- lines 264: it should be Figure 5 (in the main text), not Figure 6 (in the appendix).

- line 570: "baslines" -> "baselines"

-------------------
The paper was reviewed by three reviewers. 

The author's rebuttal period was very useful to clarify several issues and the discussion actually led to additional relevant results that could be used to improve the original submission. Some of the reviewers increase their scores after the clarifications. Finally, the three reviewers agreed that this was an article that should be accepted with different degrees of acceptance by each reviewer (5, 6 and 7).

I have read all the discussions in detail and I am generally satisfied with the authors' responses, including the informative counter examples provided.

I recommend acceptance of the paper. In addition to the improvements developed during the discussion, I suggest my comments above to be addressed in the revised version.
Decision: Accept (poster)