Solving Minimum-Cost Reach Avoid using Reinforcement Learning

Authors: oswin  so
cheng  ge
chuchu  fan
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 08:44:55

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.

Main paper: 
 introduction: 
 Many real-world tasks can be framed as a constrained optimization problem where reaching a goal at the terminal state and ensuring safety (i.e., reach-avoid) is desired while minimizing some cumulative cost as an 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-efficient autonomous driving [1, 2] can be seen as a task where the vehicle must reach a destination, follow traffic rules, and minimize fuel consumption. Minimizing fuel use is also a major concern for low-thrust or energy-limited systems such as spacecraft [3] 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 a desired current, minimize the total risk of plasma disruption) [5] and voltage control (reach a desired voltage level, minimize the load shedding amount) [6] . 
related works: 
 Terminal-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 a terminal state constraint [22] . Since MPC is implemented as a discrete-time finite-horizon numerical optimization problem, the terminal state constraints can be easily implemented in an optimization program as a normal state constraint. The case of a flexible-horizon constrained optimization is 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 [7] . Another method is to consider a bilevel optimization problem, where the number of knot points is optimized for in the outer loop [8, 9, 10] .There have been many works on goal-conditioned reinforcement learning. These works mainly focus on the challenges of tackling sparse rewards [12, 14, 23, 15] or even learning without rewards completely, either via representation learning 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, 40, 41, 42, 43] , often in imitation learning settings [44, 45] . However, the manner in which these goals are reached is not considered, and it is difficult to extend these works to additionally minimize some cumulative cost.Constrained Reinforcement Learning One way of using existing techniques to approximately tackle the minimum-cost reach-avoid problem is to flip the role of the cumulative-cost objective and the goal-reaching constraint by treating the goal-reaching constraint as an objective via a (sparse or dense) reward and the cumulative-cost objective as a constraint with a cost threshold, turning the problem into a CMDP [21] . 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-cost reach-constrained problem, depending on the choice of the cost constraint.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, 50, 51] . 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, to solve for the set of initial conditions and an appropriate control policy to drive a system to a desired goal set while avoiding undesireable states. Hamilton-Jacobi (HJ) reachability analysis [52, 53, 54, 55, 56] provides a methodology for the case of dynamics in continuous-time via the solution of a 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-policy [57, 58] and on-policy [59, 60] reinforcement learning. While reachability analysis concerns itself with the reach-avoid problem, we are instead interested in solutions to the minimum-cost reach-avoid problem. 
problem formulation: 
 In this paper, we consider a class of minimum-cost reach-avoid problems defined by the tuple M := ⟨X , U, f, c, g, h⟩. Here, X ⊆ R n is the state space and U ⊆ R m is the action space. The system states x t ∈ X evolves under the deterministic discrete dynamics f : X × U → X asEQUATIONThe control objective for the system states x t is to reach the goal region G and avoid the unsafe set F while minimizing the cumulative cost T -1 t=0 c(x t , π(x t )) under control input u t = π(x t ) for a designed control policy π : X → U. Here, T denotes the first timestep that the agent reaches the goal G. The sets G and F are given as the 0-sublevel and strict 0-superlevel sets g : X → R and h : X → R respectively, i.e.,EQUATIONThis can be formulated formally as finding a policy π that solves the following constrained flexible final-time optimization problem for a given initial state x 0 :EQUATIONEQUATIONNote that as opposed to either traditional finite-horizon constrained optimization problems where T is fixed or infinite-horizon problems where T = ∞, the time horizon T is also a decision variable. Moreover, the goal constraint (3b) is only enforced at the terminal timestep T . These two differences prevent the straightforward application of existing RL methods to solve (3).In discrete time, the set of initial states that can reach the goal G without entering the avoid set F can be represented by the 0-sublevel set of a reach-avoid value function V π g,h [58] . Given functions g, h describing G and F and a policy π, the reach-avoid value function V π g,h : X → R is defined asEQUATIONwhere x π t denote the system state at time t under a policy π starting from an initial state x π 0 = x 0 . In the rest of the paper, we suppress the argument x 0 for brevity whenever clear from the context. It can be shown that the reach-avoid value function satisfies the following recursive relationship via the reach-avoid Bellman equation (RABE) [58] EQUATIONThe Bellman equation ( 5) can then be used in a reinforcement learning framework (e.g., via a modification of soft actor-critic [61, 62] ) as done in [58] to solve the reach-avoid problem.Note that existing methods of solving reach-avoid problems through this formulation focus on minimizing the value function V π g,h . This is not necessary as any policy that results in V π g,h ≤ 0 solves the reach-avoid problem, albeit without any cost considerations. However, it is often the case that we wish to minimize a cumulative cost (e.g., (3a)) on top of the reach-avoid constraints (3b)-(3c) for a minimum-cost 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.We now provide a new framework to solve the minimum-cost reach-avoid by lifting the original system to a higher dimensional space and designing a set of augmented dynamics that allow us to convert the original problem into a reachability problem on the augmented system.Let I denote the shifted indicator function defined asEQUATIONDefine the augmented state as x = (x, y, z) ⊆ X := X ×{-1, 1}×R. We now define a corresponding augmented dynamics functionEQUATIONwhere y 0 = I x0∈F . Note that y t = 1 if the state has entered the avoid set F at some timestep from 0 to t and is unsafe, and y t = 0 if the state has not entered the avoid set F at any timestep from 0 to t and is safe. Moreover, z t is equal to z 0 minus the cost-to-come, i.e., for state trajectory x 0:t and action trajectory u 0:t , i.e.,EQUATIONUnder the augmented dynamics, we now define the following augmented goal function ĝ : X → R asEQUATIONwhere C > 0 is an arbitrary constant. 2 With this definition of ĝ, an augmented goal region Ĝ can be defined asEQUATION) In other words, starting from initial condition x0 = (x 0 , y 0 , z 0 ), reaching the goal on the augmented system xT ∈ ĝ at timestep T implies that 1) the goal is reached at x T for the original system, 2) the state trajectory remains safe and does not enter the avoid set F, and 3) z 0 is an upper-bound on the total cost-to-come:T -1 t=0 c(x t , u t ) ≤ z 0 . 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.Theorem 1. For given initial conditions x 0 ∈ X , z 0 ∈ R and control policy π, consider the trajectory for the original system {x 0 , . . . x T } and its corresponding trajectory for the augmented system {(x 0 , y 0 , z 0 ), . . . (x T , y T , z T )} for some T > 0. Then, the reach constraint x T ∈ G (3b), avoid constraint x t ̸ ∈ F ∀t ∈ {0, 1, . . . , T } (3c) and the upper-bound property z 0 ≥ T -1 k=0 c x k , π(x k ) hold if and only if the augmented state reaches the augmented goal at time T , i.e., (x T , y T , z T ) ∈ Ĝ.With this construction, we have folded the avoid constraints x t ̸ ∈ F (3c) 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 (5) , resulting in the following definition of the reach value function Ṽĝ : X → REQUATIONSimilar to (4), the 0-sublevel set of Ṽĝ describes the set of augmented states x that can reach the augmented goal Ĝ. We can also similarly obtain a recursive definition of the reach value function Ṽĝ given by the reachability Bellman equation (RBE)EQUATIONwhose proof we provide in Appendix D.2.We now solve the minimum-cost reach-avoid problem using this augmented system. By Theorem 1, the z 0 is an upper bound on the cumulative cost to reach the goal while avoiding the unsafe set if and only if the augmented state x reaches the augmented goal. Since this upper bound is tight, the least upper bound z 0 that still reaches the augmented goal thus corresponds to the minimum-cost policy that satisfies the reach-avoid constraints. In other words, the minimum-cost reach-avoid problem for a given initial state x 0 can be reformulated as the following optimization problem.EQUATIONWe refer to Appendix B for a detailed derivation of the equivalence between the transformed Problem 13 and the original minimum-cost reach-avoid Problem 3.Remark 1 (Connections to the epigraph form in constrained optimization). The resulting optimization problem (13) can be interpreted as an epigraph reformulation [63] of the minimum-cost reach-avoid problem (3) . 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] .We first derive the state value function in a recursive form similar as [66] Proof.∇ θ Ṽ π θ ĝ (x) =∇ θ u∈U π θ (u | x) Qπ θ ĝ (x, u) = u∈U ∇ θ π θ (u | x) Qπ θ ĝ (, u) + π θ (u | x)∇ θ Qπ θ ĝ (x, u) = u∈U ∇ θ π θ (u | x) Qπ θ ĝ (x, u) + π θ (u | x)∇ θ min{ĝ(x), Ṽ π g (x ′ )} = u∈U ∇ θ π θ (u | x) Qπ θ ĝ (x, u) + π θ (u | x)1 ĝ(x)> Ṽ π θ g (x ′ ) ∇ θ Ṽ π θ g (x ′ )where x′ = f (x, u)Next, we consider unrolling Ṽ π θ g (x ′ ) under Reachability MDP in Definition 2. We define Pr(x → x † , k, π θ ) as the probability of transitioning from state x to x † in k steps under policy π θ in 2. Note that 1 ĝ(x)> Ṽ π θ g (x ′ ) is absorbed using the absorbing state in 2. Then we can get∇ θ Ṽ π θ ĝ (x) = x † ∈ X ∞ k=0 Pr x → x † , k, π u∈U ∇π θ (u | x † ) Qπ θ ĝ (x † , u) ∝ E x′ ∼d ′ π (x),u∼π θ Qπ θ (x ′ , u) ∇ θ ln π θ (u | x′ ) 
solving with reinforcement learning: 
 In the previous section, we reformulated the minimum-cost reach-avoid problem by constructing an augmented system and used its reach value function (11) in a new constrained optimization problem (13) over the cost upper-bound z 0 . In this section, we propose Reachability Constrained Proximal Policy Optimization (RC-PPO), a two-phase RL-based method for solving (13) (see Figure 1 ).In the first step, we learn the optimal policy π and value function Ṽ π ĝ , as functions of the cost upper-bound z 0 , using RL. To do so, we consider the policy gradient framework [64] . However, since the policy gradient requires a stochastic policy in the case of deterministic dynamics [65] , we consider an analog of the developments made in the previous section but for the case of a stochastic policy. To this end, we redefine the reach value function Ṽ π ĝ using a similar Bellman equation under a stochastic policy as follows. In phase one, the original dynamic system is transformed into the augmented dynamic system defined in (7) . Then RL is used to optimize value function Ṽ π ĝ and learn a stochastic policy π. In phase two, we fine-tune Ṽ π ĝ on a deterministic version of π and compute the optimal upper-bound z * to obtain the optimal deterministic policy π * . Definition 1 (Stochastic Reachability Bellman Equation). Given function ĝ in (9), a stochastic policy π, and initial conditions x 0 ∈ X , z 0 ∈ R, the stochastic reach value function Ṽ π ĝ is defined as the solution to the following stochastic reachability Bellman equation (SRBE):EQUATIONwhere x0 = (x 0 , y 0 , z 0 ) with y 0 = I x0∈F .For this stochastic Bellman equation, the Q function [66] is defined as Qπ ĝ (x t , u t ) = min{ĝ(x t ), Ṽg (x t+1 )}.We next define the dynamics of 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 s 0 . We define the transition function f ′ r with the absorbing state asEQUATIONDenote by d ′ π (x) the stationary distribution under stochastic policy π starting at x ∈ X ×{-1, 1}×R.We now derive a policy gradient theorem for the Reachability MDP in Definition 2 which yields an almost identical expression for the policy gradient. Theorem 2. (Policy Gradient Theorem) For policy π θ parameterized by θ, the gradient of the policy value function Ṽ π θ ĝ satisfiesEQUATIONunder the stationary distribution d The proof of 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 in Appendix D.3.Since the stationary distribution d ′ π (x) 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 1 does not induce a contraction map, which harms performance. To fix this, we apply the same trick as [58] by introducing an additional discount factor γ into the Bellman equation ( 12):EQUATIONThis provides us with a contraction map (proved in [58] ) and we leave the discussion of choosing γ in Appendix C. The Q-function corresponding to ( 18) is then given asEQUATIONFollowing proximal policy optimization (PPO) [67] , we use generalized advantage estimation (GAE) [68] to compute a variance-reduced advantage function Ãπ ĝ = Qπ ĝ -Ṽ π ĝ for the policy gradient (Theorem 2) using the λ-return [66] . We refer to Appendix A for the definition of Âπ(GAE) ĝ and denote the loss function when θ = θ l asEQUATIONEQUATION)We wish to obtain the optimal policy π and the value function Ṽ π θ ĝ conditioned on z 0 . Hence, at the beginning of each rollout, we uniformly sample z 0 within a user-specified range [z min , z max ]. Since the optimal z 0 is the cumulative cost of the policy that solves the minimum-cost reach-avoid problem, z min and z max are user-specified bounds on the optimal cost. In particular, when the cost-function is bounded and the optimal cost is non-negative, we can choose z min to be some negative number and z max to be the maximum possible discounted cost.In the second phase, we first compute a deterministic version π * of the stochastic policy π from phase 1 by taking the mode. Next, we fine-tune V π ĝ based on the now deterministic π * to obtain Ṽ * ĝ . Given any state x, the final policy is then obtained by solving for the optimal cost upper-bound z * from Equation ( 13), which is a 1D root-finding problem and can be easily solved using bisection. Note that Equation ( 13) must be solved online for z * 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 a convergence proof of an actor-critic version of our method without the GAE estimator in Appendix E. 
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, we consider the Contrastive Reinforcement Learning (CRL) [33] method. We also compare against safe RL methods that solve CMDPs. As the minimum-cost reach-avoid problem (3) cannot be posed as a CMDP, we reformulate (3) into the following surrogate CMDP:EQUATIONEQUATION)where the reward r incentivies goal-reaching, C fail is a term balancing two constraint terms, and X threshold is a hyperparameter on the cumulative cost. For this category, we consider the CPPO [48] and RESPO [60] . 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 X thresholds : X L , X M and X H . For RESPO, we found X M to outperform both X L and X H and thus only report results for X M .Figure 2 : Illustrations of the benchmark tasks. In each picture, red denotes the unsafe region to be avoided, while green denotes the goal region to be reached. 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 a 3D quadrotor navigation task in a simulated wind field for an urban environment [71, 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 G without violating safety along the trajectory. The cost denotes the cumulative cost over the trajectoryT k=0 c(x k , π(x k )).We first compare our algorithm with other baseline algorithms under a 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_X L , PPO_β H and SAC_β H have higher Lagrangian coefficients which lead to a lower reach rate.Reward shaping is a common method that can be used to improve the performance of 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 4 demonstrate that RC-PPO remains competitive against the best baseline algorithms in reach rate while achieving significantly lower cumulative costs. The baseline methods (PPO_β H , SAC_β H , CPPO_X L ) 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 a higher cumulative cost relative to other methods. Other baselines focus more on goal-reaching tasks while putting less emphasis on the cost part. As a result, they suffer from higher costs than RC-PPO. We can also observe that RESPO achieves lower cumulative cost compared to CPPO_X M which shares the same X threshold . 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 and WindField in Figure 5 . 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 z on the Pendulum benchmark (see Appendix H.2). For small values of z, the policy learns to minimize the cost, but at 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 z opt found using the learned value function Ṽ π θ ĝ finds the z that minimizes the cumulative cost but is still able to reach the goal.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 (22) . We thus pose the following question: Can CMDP methods perform well under the right parameters of the surrogate CMDP problem (22) ?. 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.3) and plot the result in Figure 6 . 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 a better problem formulation as opposed to badly chosen hyperparameters for the baselines.Theoretical Analysis on Simple Example. To complement the empirical study, we provide an example of a simple minimum-cost reach-avoid problem where we prove that no choice of hyperparameter leads to the optimal solution in Appendix I.Finally, we investigate the robustness to varying levels of control noise in Appendix H.4. Even with the added noise, RC-PPO achieves the lowest cumulative cost while maintaining a comparable reach rate to other methods.We take quadrotor dynamics from crazyflies and wind field environments in the urban area from [71] .The wind field will disturb the quadrotor with extra movement on both x-axis and y-axis. There are static building obstacles in the environment and we treat them as 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 x ∈ [-30, 30] to denote the x-axis position of quadrotor, y ∈ [-30, 30] to be the y-axis position of quadrotor.G := {(x, y) | ∥[x, y]∥ ≤ 4}The cost c is given byc(x t , u t , x t+1 ) = ∥u t ∥ 2 2g is given byg(x) = 10 (x -x goal ) 2 + 10(y -y goal ) 2 -40 if x ̸ ∈ G -300 if x ∈ G G.6 PointGoalThe PointGoal environment is taken from Safety Gym [69] We implement PointGoal environments in Jax. In Safety Gym environment, we do not perform reward-shaping and use the original reward defined in Safety Gym environments. In this case, the distance reward is set also to be 20 in order to align* with C goal and C cost . 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 to be the y-axis position of Point, x goal to denote the x-axis position of Goal, and y goal to denote the y-axis position of Goal. The goal region is given byG := {(x, y) | ∥[x, y] -[x goal , y goal ]∥ ≤ 0.3}The cost c is given byEQUATIONg is given byg(x) = 100 (x -x goal ) 2 + (y -y goal ) 2 -30 if x ̸ ∈ G -300 if x ∈ G G.7 Experiment HarwareWe run all our experiments on a computer with CPU AMD Ryzen Threadripper 3970X 32-Core Processor and with 4 GPUs of RTX3090. It takes at most 4 hours to train on every environment.Question: Does the paper provide open access to the data and code, with sufficient instructions 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. 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 no societal 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 not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an 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 a 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 as 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). 
conclusion and limitations: 
 We have proposed RC-PPO, a 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 a 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 Ṽ π g ′ even if one is unsafe, which can be undesirable. Next, the theoretical developments of RC-PPO are dependent on the assumptions of deterministic dynamics, which can be quite restrictive as it precludes the use of commonly used techniques for real-world deployment such as domain randomization. We acknowledge these limitations and leave resolving these challenges as future work. 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] Justification: The paper poses no such risks. Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make a 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 in Appendix F.3. Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a 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 (e.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, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-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 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: we include the code of the algorithm in the supplementary materials. Implementation details are introduced in Section 4 and Appendix F. Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of 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. • 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 as the institution conducting the review. 
 
 Appendix: 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 ϕ (n) : R n → R that applies itself recursively to its n arguments, i.e., ϕ (n) (x 1 , x 2 , . . . , x n ) := ϕ (1) x 1 , ϕ (n-1) (x 2 , . . . , x n ) where ϕ (1) (x, y) := (1 -γ)x + γ min{x, y}.Âπ(k) ĝ can then be written asÂπ(k) ĝ (x t ) = ϕ (k) ĝ(x t ), . . . , ĝ(x t+k-1 ), Ṽ π ĝ (x t+k ) -Ṽ π g (x t ).We can then construct the GAE Âπ(GAE) ĝ as the λ k -weighted sum over the k-step advantage functions Âπ(k) ĝ : Overall, the GAE estimator can be described asÂπ(GAE) ĝ (x t ) = 1 1 -λ ∞ k=1 λ k Âπ(k) ĝ (x t ).The equivalence between the transformed Problem 13 and the original minimum-cost reach-avoid Problem 3 can be shown in the following sequence of optimization problems that yield the exact same solution if feasible:EQUATIONThis shows that the minimum-cost reach-avoid Problem 3 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 3 because they are equivalent.As shown in (18) , we introduce an additional discount factor into the estimation of Ṽ π ĝ . It will incur imprecision on the calculation of Ṽ π ĝ defined in Definition 1. In this section, we show that for a large enough discount factor γ < 1, we could reach unbiased z in phase two of RC-PPO. Theorem 3. We denote max x∈ X {ĝ(x)} = G max and maximal episode length T max . If there exists a positive value ϵ where ĝ(x) < 0 ⇒ ĝ(x) < -ϵ.Then for any γ Tmax 1-γ Tmax > Gmax ϵ , for any deterministic policy π satisfies 18. If there exists a trajectory under given policy π leading to the extended goal region Ĝ. We haveṼ π ĝ (x) < 0.The proof for Theorem 3 is provided in Appendix D.4.D.1 Proof for Theorem 1Proof. We separately consider three elements in augmented state (x T , y T , z T ). First, note that 3b holds if and only if x T ∈ G. For the second element y, from the definition of the augmented dynamics 7, it holds thatEQUATIONAs a result 3c holds if and only if y T = -1. For the third element z, note that z T = z 0 -T -1 k=0 c(x k , u(x k )). Hence, z T ≥ 0 if and only if z 0 ≥ T -1 k=0 c(x k , u(x k )).Proof. From Definition 12, we knowṼ π ĝ (x) = min t∈N ĝ(x t | x0 = x) = min{ĝ(x), min t∈N + ĝ(x t | x0 = x)} = min{ĝ(x), Ṽ π g (x t+1 )} D.Proof. Consider trajectory {x 0 , . . . , xT } where xT ∈ Ĝ. We consider the worst-case scenario where ĝ(x t ) = g max for t ∈ {0, . . . , T -1}. ThenṼ π (x 0 ) = (1 -γ)ĝ(x 0 ) + γ min{ Ṽ π (x 1 ), ĝ(x 1 )} ≤ (1 -γ)g max + γ Ṽ π (x 1 ) ≤ (1 -γ)g max + γ((1 -γ)g max + γ Ṽ π (x 1 )) ≤ T -1 i=0 γ i (1 -γ)g max + γ T Ṽ π (x T ) < (1 -γ T )g max + γ T ϵ < 0In this section, we provide the convergence proof of phase one of our method under the actor-critic framework. Notice that similar to Bellman equation (18) for Ṽ π ĝ . We could also derive the Bellman equation for Qπĝ as Qπ ĝ (x t , u t ) = (1 -γ)ĝ( xt ) + γE xt+1∼τ,ut+1∼π [min{ĝ( xt ), Qπ g (x t+1 , u t+1 )}]Next, we show our method under the actor-critic framework without GAE estimator in Algorithm 1Require: Initial policy parameter θ 0 , Q function parameter ω 0 , horizon T, convex projection operator Γ Θ , and value function learning rate β 1 (k), policy learning rate β 2 (k) 1: for k = 0, 1, . . . dofor t = 0 to T-1 do Critic update:ω k+1 = ω k -β 1 (k)∇ ω Qĝ (x t , u t ; ω k ) • 5: Qĝ (x t , u t ; ω k ) -(1 -γ)ĝ(x t ) + γ min ĝ(x t ), Qĝ (x t+1 , u t+1 ; ω k ) 6:Actor Update:θ k+1 = Γ Θ θ k + β 2 (k) Qĝ (x t , u t ; ω k ) ∇ θ log π θ (u t | xt ) 7:end for 8: end for 9: return parameter θ, ωIn this algorithm, the Γ Θ (θ) operator projects a vector θ ∈ R k to the closest point in a compact and convex set Θ ⊂ R k , i.e., Γ Θ (θ) = arg min θ ′ ∈Θ ∥θ ′ -θ∥ 2 .Next, we provide the convergence analysis for Algorithm 1 under the following assumptions. Assumption 1. (Step Sizes) The step size schedules {β 1 (k)} and {β 2 (k)} have below properties:k β 1 (k) = k β 2 (k) = ∞ k β 1 (k) 2 , k β 2 (k) 2 < ∞ β 2 (k) = o(β 1 (k)) Assumption 2.(Differentiability and and Lipschitz Continuity) For any state and action pair (x, u), Qĝ (x, u; ω) and π(x; θ) are continuously differentiable in ω and θ. Furthermore, for any state and action pair (x, u), ∇ ω Qĝ (x, u; ω) and π(x; θ) are Lipschitz function in ω and θ. Also, we assume that X and U are finite and bounded and the horizon T is also bounded by T max , then the cost function c can be bounded by C max and g can be bounded within G max . We can limit the space of cost upper bound z ∈ [-G max , T • C max ] instead of R. This is due to ĝ(x) = -z for z ≤ -G max . Next, we could do discretization on [-G max , T • C max ] and cost function c to make the augmented state set X finite and bounded.With the above assumptions, we can provide a convergence guarantee for Algocrithm 1. Theorem 4. Under Assumptions 1 and 2, the policy update in Algorithm 1 converge almost surely to a locally optimal policy.Proof. The proof follows from the proof of Theorem 2 in [75] , differing only in whether an update exists for the Lagrangian multiplier. We provide a proof sketch as • First, we prove that the critic parameter almost surely converges to a fixed point ω * . This step is guaranteed by the assumption of finite and bounded state and action set and Assumption 1. The γ-contraction property of the following operatorEQUATION) 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 ω * , we can show policy paramter θ converge almost surely to a stationary point θ * which can be further proved to be a locally optimal solution.We refer to [75] for proof details.In this section, we will provide more details about CMDP-based baselines (different between optimization goal with multiple constraints) and other hyperparameter settings like X threshold .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 isEQUATIONEQUATIONWe then denoteV π r (x t ) := E xt,ut∼dπ t γ t r(x t , u t ) V π f (x t ) := E xt,ut∼dπ t γ t 1 xt∈F × C cost V π c (x t ) := E xt,ut∼dπ t γ t c(x t , u t )The optimization goal formulation for CPPO is as follows:min π max λ L(π, λ) = -V π r (x) + λ c • (V π c (x) -X threshold ) + λ f • V π f (x)In this formulation, the soft constraint V π c has the same priority as the hard constraint V π f . This leads to a potential imbalance between soft constraints and hard constraints. Instead, the optimization goal for RESPO is as follows:min π max λ L(π, λ) = -V π r (x) + λ c • (V π c (x) -X threshold ) + λ f • V π f (x) • (1 -p(x)) + p(x) • V π f (x)where p(x) denotes the probability of entering the unsafe region F start from state x. It is called the reachability estimation function (REF). This formulation prioritizes the satisfaction of hard constraints but still suffers from balancing soft constraints and reward terms.We first clarify how we set proper X threshold for each environment. First, we will run our method RC-PPO and calculate the average cost, we denote it as c average . We set X low = caverage 10, X medium = caverage 3and X high = c average . For static lagrangian multiplier β, we set β lo = 0.1 and β hi = 10. Also, we set C f ail = 20 in every environment.Note that CRL is an off-policy algorithm, while RC-PPO and other baselines are on-policy algorithms. We provide Table 1 showing hyperparameters for on-policy algorithms and Table 2 showing hyperparameters for off-policy algorithm (CRL).The implementation of the baseline follows their original implementations: In this section, we provide more details about the benchmarks and the choice of reward function r, g, cost function c and C cost in each environment. Under the sparse reward setting, we apply the following structure of reward designr(x t , u t , x t+1 ) = R goal × 1 xt+1∈Gwhere R goal is an constant. After doing reward shaping, we add an extra term γϕ(x t+1 ) -ϕ(x t ) and the reward becomesr(x t , u t , x t+1 ) = R goal × 1 xt+1∈G + γϕ(x t+1 ) -ϕ(x t )where γ denotes the discount factor.Note that we set R goal = C cost = 20 in all the environments. Note that if there is a gap between max{g(x) | g(x) < 0}, we could get unbiased z during phase two of RC-PPO guaranteed by Theorem 3. To achieve better performance in phase two of RC-PPO, we set g(x) = -300 for all x ∈ G to maintain such a gap. Also, we implement all the environments in Jax [76] for better scalability and parallelization. FixedWing environment is taken from [59] and we follow the same design of F as [59] . We denote the x P E as the eastward displacement of F16 with given state x. Then the goal region G is given byG := {x | 1975 ≤ x P E ≤ 2025}The cost c is given byc(x t , u t , x t+1 ) = 4∥u t /[1, 25, 25, 25]∥ 2and g is given byg(x) = ∥x P E -2000∥-25 4 if x ̸ ∈ G -300 if x ∈ G G.We put additional experiment results in this section.We show the cumulative cost and reach rates of the final converged policies for additional environments (F16 and Safety Hopper) in Figure 7 . To obtain better intuition for how the learned policy depends on z, we rollout the policy choices of z 0 in the Pendulum environment and visualize the results in Figure 8 . Figure 8 : Learned RC-PPO policy for different z on Pendulum. For a smaller cost lower-bound z, cost minimization is prioritized at the expense of not reaching the goal. For a larger cost lower-bound z, the goal is reached using a large cumulative cost. Performing rootfinding to solve for the optimal z opt automatically finds the policy that minimizes cumulative costs while still reaching the goal. 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 6 . The reward we use is r = R goal × 1 x∈G -P goal × 1 x̸ ∈G -βc(x, u).We also performed additional experiments to illustrate the performance of RC-PPO under a changing environment. Specifically, we add uniform noise to the output of the learned policy and see what happens in the Pendulum environment.We first compare the reach rates of the different methods in Table 3 . In this environment, we see that noise does not affect the reach rate too much.Next, we look at how the cumulative cost changes with noise by comparing methods with a near 100% reach rate in Table 4 . 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.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 on two parts of CMDP formulation:• Weight coefficient assigned to different objectives• Threshold assigned to each constraint Consider the minimum-cost reach-avoid problem shown in Figure 9 , where we use C to denote the cost. States A and B are two initial states with the same initial distribution probability. State G 1 , G 2 , and G 3 are three goal states. State I is the absorbing state (non-goal). We use p A and p B to denote the policy parameter, which represents the probability of choosing left action on state A and B separately.A G1 G2 B G3 I 𝑝𝑝 𝐴𝐴 1 -𝑝𝑝 𝐴𝐴 𝑝𝑝 𝐵𝐵 1 -𝑝𝑝 𝐵𝐵 𝐶𝐶 = 10 𝐶𝐶 = 20 𝐶𝐶 = 30 𝐶𝐶 = 0The optimal policy for this minimum-cost reach-avoid problem is to take the left action from both A and B, i.e., p A = p B = 1, which gives an expected cost of0.5 • 10 + 0.5 • 30 = 20To convert this into a multi-objective problem, we introduce a reward that incentivizes reaching the goal as follows (we use R to denote reward):EQUATIONThis results in the following multi-objective optimization problem:EQUATIONWe first consider solving multi-objective optimization Problem 34 by assigning weights on different objectives. We introduce w ≥ 0, givingEQUATIONSolving the scalarized Problem 34 gives us the following solution as a function of w:EQUATIONNotice that the *true* optimal solution of p A = p B = 1 is NOT an optimal solution to the original minimum-cost reach-avoid problem shown in Figure 9 under any w.Hence, the optimal solution of the surrogate multi-objective problem can be suboptimal for the original minimum-cost 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 a solution. However, this is impossible to do if we do not have prior knowledge of the optimal policy, as is typically the case.Next, we consider solving multi-objective optimization Problem 34 by assigning a threshold X _thresh on the cost constraint:EQUATIONThe optimal solution to this CMDP can be solved to beEQUATION• 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 a 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 a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or 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 submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. , with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.If the dense reward is not specified correctly, however, it can lead to unwanted local minima[14] that optimize the reward function in an undesirable manner, i.e., reward hacking[16,17]In practice, we use C = maxx∈X g(x). 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

2.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.


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.
questions: 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.

2.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: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: (minor)
The presented experimental results are solid and illustrative, but could be extended. 
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.
questions: 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: Limitations are briefly discussed.
paper_summary: paper_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.
strength_weakness: strength_weakness: 1. The state augmentation is not a novel technique in constrained RL, (see references below) albeit the application here is different.
1. 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?
1. 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?
1. 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). 


* [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.

* [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).

* [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.
questions: 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.
2. 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?
3. 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. 
4. 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: limitations are discussed

Comments: title: Additional Clarifications
Fig 2 Clarification: Blue Star marks the performance of RC-PPO
comment: As the author-reviewer discussion phase closes, we would like to thank all the reviewers for participating in the discussion and giving timely, constructive responses! The concerns that have been brought up have helped us to _clarify the motivation_, _improve the theoretical justification_ and provide _stronger empirical evidence_ of the benefits of solving minimum-cost reach-avoid problems using RC-PPO.

---

# Author-Reviewer Discussion Summary
We summarize the _major_ developments that have happened during the discussion below. 

## New Experiments
- New comparison with SAC on all tasks (Rebuttal pdf, Fig 1)
    - SAC follows the same trends as the existing baseline methods in the paper, reaffirming our conclusions that RC-PPO outperforms other methods. 
- Extensive grid search of reward function coefficients for baseline methods (Rebuttal pdf, Fig 2)
    - RC-PPO outperforms the _entire_ Pareto frontier. This provides experimental evidence that the surrogate CMDP which prior methods solve does not yield the optimal solution the minimum-cost reach-avoid problem. In contrast, RC-PPO solves the minimum-cost reach-avoid problem directly. 
- Investigation into the robustness of the methods as noise is added into the environment (Reply to $\color{#988ED5}{\textsf{186A}}$)
    - Even with added noise, RC-PPO uses the least cumulative cost compared to all other methods. The performance of RC-PPO
degrades gracefully as more noise is added, in line with the other RL methods.

## New Theoretical Developments
- Proof that the formulation we eventually solve using reachability (8) is _equivalent_ to the minimum-cost reach-avoid problem (1). (Reply to $\color{#E24A33}{\textsf{M8co}}$)
- Proof that the CMDP formulation cannot optimally solve the minimum-cost reach-avoid problem for a wide range of setups. (Reply to $\color{#E24A33}{\textsf{M8co}}$)
- Proof that a surrogate multi-objective problem does not always optimally solve the minimum-cost reach-avoid problem. (Reply to $\color{#988ED5}{\textsf{186A}}$)

---

All developments, including clarifications in the replies to the reviewers that are not mentioned above, will be included in the final version.

**To the reviewers**: Thank you so much for participating in this productive author-reviewer discussion!
Once again, thank you for raising your score!

To answer your concerns about whether the minimum-cost reach-avoid problem can be solved using multi-objective methods, we have built a toy example to show that **our problem may not be solvable using multi-objective methods, depending on the choice of reward function**. Consequently, it is very difficult to construct surrogate reward functions that guarantee the optimality for the original minimum-cost reach-avoid problem in general.

> ## Can the minimum-cost reach-avoid problem always be optimally solved as a surrogate multi-objective problem given proper weights between the different objectives?

This is a very good question. **The optimal solution of the surrogate multi-objective problem can be suboptimal for the original minimum-cost reach-avoid problem given \*any\* choice of weights**. We illustrate this with the following example.

## Problem Setup
Consider the following minimum-cost reach-avoid problem, where we use $C$ to denote the cost.

- **Initial state distribution**: A ($p=0.5$), B ($p=0.5$)
- **Goal states**: $G_1$, $G_2$, $G_3$
- **(Non-goal) Absorbing state**: $I$
- **Policy parameters**: $p_A$, $p_B \in [0, 1]$

```
       ┌───┐       
  pA ┌─┤ A ├─┐ 1-pA
     │ └───┘ │     
C=10 ▼       ▼ C=20
   ┌──┐     ┌──┐   
   │G1│     │G2│   
   └──┘     └──┘   
       ┌───┐       
  pB ┌─┤ B ├─┐ 1-pB
     │ └───┘ │     
C=30 ▼       ▼ C=0 
   ┌──┐     ┌─┐    
   │G3│     │I│    
   └──┘     └─┘
```

The optimal policy for this minimum-cost reach-avoid problem is to take the _left_ action from both $A$ and $B$, i.e., $p_A = p_B = 1$, which gives an expected cost of
$$
0.5 \cdot 10 + 0.5 \cdot 30 = 20
$$

## Multi-objective Problem and Solution
To convert this into a multi-objective problem, we introduce a reward that incentivizes reaching the goal as follows (we use $R$ to denote reward):
```
       ┌───┐       
  pA ┌─┤ A ├─┐ 1-pA
     │ └───┘ │     
C=10 │       │ C=20
R=10 ▼       ▼ R=20
   ┌──┐     ┌──┐   
   │G1│     │G2│   
   └──┘     └──┘   
       ┌───┐       
  pB ┌─┤ B ├─┐ 1-pB
     │ └───┘ │     
C=30 │       │ C=0 
R=20 ▼       ▼ R=0 
   ┌──┐     ┌─┐    
   │G3│     │I│    
   └──┘     └─┘
```
This results in the following multi-objective optimization problem:
$$
\min_{p_A, p_B \in [0, 1]} \quad (-R, C) 
$$
To solve this multi-objective optimization problem, we employ scalarization and introduce a weight $w \geq 0$, giving
$$
\min_{p_A, p_B \in [0, 1]} \quad -R + w C  \tag{$\dagger$}
$$
Solving the scalarized problem ($\dagger$) gives us the following solution as a function of $w$:
$$
p_A = \mathbb{1}\_{(w \ge 1)}, \quad p_B = \mathbb{1}\_{(w \le \frac{2}{3})}
$$
Notice that **the \*true\* optimal solution of $p_A = p_B = 1$ is NOT an optimal solution to  ($\star$) under any $w$**. 

Hence, **the optimal solution of the surrogate multi-objective problem can be suboptimal for the original minimum-cost 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 ($\dagger$) does include the optimal policy as a solution. However, this is impossible to do if we do not have prior knowledge of the optimal policy, as is typically the case.

In contrast, RC-PPO solves the minimum-cost reach-avoid problem directly. Hence, assuming the optimization is done exactly, the true solution will be found without the need for any reward design.

---

We will include the above explanation in the final version to improve clarity.
Thank you for a detailed response and additional experiments. 
I decide to raise my score as part of my concerns have been solved.

As your statement in the abstract " 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." I intuitively believe that the problem studied by the author can be transformed into a multi-objective problem, and appropriate parameters can be constructed in the multi-objective problem, such as the weight values between different objectives. Using non reinforcement learning methods to solve surrogate objective problems can also achieve the same performance as the author. I don't know how the author can refute my point of view experimentally or theoretically.
Thank you for raising your score!

Below,
1. We provide **new experiment results** on robustness: RC-PPO degrades gracefully as noise is introduced but _remains the lowest cost method among baseline method with high reach rates_.
2. Clarify the objective weights: RC-PPO _does not require weights by construction_, unlike the baseline methods we have compared against.

**Please let us know if we have addressed all of your concerns!** We are happy to clarify any further questions you may have. All additional experiments and clarifications will be included in the final version.


---
> ## How does the algorithm perform when there are changes in the environment

Good question. Although not the focus of this work, **we have performed additional experiments to see what happens when the environment changes**. Specifically, we add uniform noise to the output of the learned policy and see what happens on the Pendulum environment.

### 1. Reach Rates

We first compare the reach rates of the different methods. On this environment, we see that the presence of noise does not affect the reach rate too much.

|   Name   |Reach Rate|&#124; + Small Noise|&#124; + Large Noise|
|----------|---------:|------------:|------------:|
|RC-PPO    |      1.00|         1.00|         1.00|
|RESPO     |      1.00|         1.00|         1.00|
|PPO $\beta_L$|      1.00|         1.00|         1.00|
|PPO $\beta_H$|      0.31|         0.38|         0.34|
|SAC $\beta_L$|      1.00|         1.00|         1.00|
|SAC $\beta_H$|      0.21|         0.37|         0.20|
|CPPO $\mathcal{X}_L$  |      0.67|         0.65|         0.65|
|CPPO $\mathcal{X}_M$  |      1.00|         1.00|         1.00|
|CPPO $\mathcal{X}_H$  |      1.00|         1.00|         0.99|
|CRL       |      1.00|         1.00|         1.00|

### 2. Cumulative Cost

Next, we look at how the cumulative cost changes with noise by _comparing methods with a near 100% reach rate_. 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.**

|   Name   |Additional Cumulative Cost|&#124; + Small Noise|&#124; + Large Noise|
|----------|-------------------------:|------------:|------------:|
|RC-PPO    |                      35.3|         41.4|        132.9|
|RESPO     |                      92.0|         93.6|        179.2|
|PPO $\beta_L$ |                      97.7|         98.6|        150.2|
|SAC $\beta_L$ |                     156.3|        157.6|        270.5|
|CPPO $\mathcal{X}_M$  |                     223.2|        220.5|        209.0|
|CPPO $\mathcal{X}_H$  |                     212.7|        299.8|        298.4|
|CRL       |                     228.3|        229.1|        261.1|


These additional experiments show that the **performance of RC-PPO degrades gracefully as more noise is added**, in line with existing RL methods.

---
> ## How does the algorithm perform when the weights assigned to reach-avoid and minimum-cost objectives vary?

**Our algorithm does NOT have any weight hyperparameters for the reach-avoid and the minimum-cost parts.** The motivation for our work is to solve the minimum-cost reach-avoid problem without the need to choose weights between the two. This is because the reach-avoid is a _constraint_ (always satisfy this), while the minimum-cost is an _objective_ (only minimize this if the reach-avoid constraint is satisfied).

In comparison, the baseline methods DO need a choice of weights, since "all objectives are combined with a weighted sum" (L5). **We have compared with baseline methods that require such choice of weights in Section 5 and in the new pdf**, where RC-PPO outperforms all baselines for any choice of weights.
> ## Why does the CMDP formulation give suboptimal results?

This is a very good question. **The optimal solution of the CMDP formulation is guaranteed to be suboptimal for the original minimum-cost reach-avoid problem for a wide range of problems**. The main culprit at play here is the fact that the cost threshold is a _fixed constant_. We illustrate this with the following example.

## Problem Setup
Consider the following minimum-cost reach-avoid problem, where we use $C$ to denote the cost.

- **Initial state distribution**: A ($p=0.5$), B ($p=0.5$)
- **Goal states**: $G_1$, $G_2$, $G_3$
- **(Non-goal) Absorbing state**: $I$
- **Policy parameters**: $p_A$, $p_B \in [0, 1]$

```
       ┌───┐       
  pA ┌─┤ A ├─┐ 1-pA
     │ └───┘ │     
C=10 ▼       ▼ C=20
   ┌──┐     ┌──┐   
   │G1│     │G2│   
   └──┘     └──┘   
       ┌───┐       
  pB ┌─┤ B ├─┐ 1-pB
     │ └───┘ │     
C=30 ▼       ▼ C=0 
   ┌──┐     ┌─┐    
   │G3│     │I│    
   └──┘     └─┘
```

The optimal policy to this minimum-cost reach-avoid problem is to take the _left_ action from both $A$ and $B$, i.e., $p_A = p_B = 1$, which gives an expected cost of
$$
0.5 \cdot 10 + 0.5 \cdot 30 = 20 \tag{$\dagger$}
$$

## CMDP Solution
To convert this to a CMDP, we introduce a reward that incentivizes reaching the goal, and add a cost constraint with threshold $\mathcal{X}\_{\text{thresh}}$:
$$
0.5(10p_A+20 (1-p_A)) + 0.5(30 p_B) \leq \mathcal{X}_{\text{thresh}}
$$
This gives the following CMDP (we use $R$ to denote reward):
```
       ┌───┐       
  pA ┌─┤ A ├─┐ 1-pA
     │ └───┘ │     
C=10 |       | C=20
R=10 ▼       ▼ R=20
   ┌──┐     ┌──┐   
   │G1│     │G2│   
   └──┘     └──┘   
       ┌───┐       
  pB ┌─┤ B ├─┐ 1-pB
     │ └───┘ │     
C=30 |       | C=0 
R=20 ▼       ▼ R=0 
   ┌──┐     ┌─┐    
   │G3│     │I│    
   └──┘     └─┘
```

The optimal solution to this CMDP can be solved to be
$$
p_A = 0, \quad p_B = \frac{\mathcal{X}_{\text{thres}} - 10}{15}. \tag{$\star$}
$$
However, **the \*true\* optimal solution of $p_A = p_B = 1$ is NOT an optimal solution to the CMDP ($\star$)**. To see this, taking $\mathcal{X}\_{\text{thresh}} = 20$ as in ($\dagger$), the real optimal solution $p_A = p_B = 1$ gives a reward of $R=15$, but the CMDP solution $p_A = 0, p_B = \frac{20 - 10}{15} = \frac{2}{3}$ in ($\star$) gives $R=23.33 > 15$. Moreover, any uniform scaling of the rewards or costs does not change the solution.

## Fixes
We can "fix" this problem if we choose the rewards to be high only along the optimal solution $p_A = p_B = 1$, but this requires knowledge of the optimal solution beforehand and is not feasible for all problems.

Another way to "fix" this problem is if we consider a "per-state" cost-threshold, e.g.,
$$
10 p_A + 20(1-p_A) \leq \mathcal{X}_A, \qquad 10 p_B + 20(1-p_B) \leq \mathcal{X}_B
$$
Choosing exactly the cost of the optimal policy, i.e., $\mathcal{X}_A = 10$ and $\mathcal{X}_B \geq 30$, also recovers the optimal solution of $p_A = p_B =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 $z_0$**. We can thus interpret RC-PPO as **automatically solving for the best cost-threshold to use as a constraint for every initial state**.

---

We will include this explanation in the final version to improve clarity.
Thank you for a detailed response and additional experiments. 
The problem studied by the authors can be transformed into a multi-objective optimization problem and solved using multi-objective algorithms. Although the authors have mathematically derived it into a problem that can be addressed using reinforcement learning and designed a reinforcement learning algorithm based on PPO, there are limitations in the mathematical tools used. Could you provide insights into the robustness and adaptability of the designed algorithm? Specifically, how does the algorithm perform when there are changes in the environment or when the weights assigned to reach-avoid and minimum-cost objectives vary?

I am raising my score.
I have read the individual rebuttals as well as the shared rebuttal and thank the authors for taking the time to answer. 
I will maintain my current rating.
I mean that the CMDP formulation, which is used as a baseline to compare, should solve the problem optimally, but the computational results imply that it doesn't. I cannot see specifically why and I am not sure that an explanation was provided.
Thank you for raising your score! Your suggested experiments have definitely helped to better show the fundamental limitations of solving the minimum-cost reach-avoid problem using a surrogate CMDP.

We are happy to clarify any further questions you may have!

---

>## I am very skeptical of the authors results since their formulations of reach-avoid problems do not solve the stated problem.

Could you clarify what you mean here?

Theoretically, **our formulation is an \*exact\* transformation of the minimum-cost reach-avoid problem (1).** This can be shown in the following sequence of optimization problems that yield the **exact same solution** if feasible:

$$
\begin{align}
&\min_{\pi,T}\quad \sum_{k=0}^T c(x_k, \pi(x_k)) \quad \text{ s.t } \quad g(x_T) \leq 0, \quad \max_{k = 0, \dots, T} h(x_k) \leq 0 \tag{1} \\\\
=& \min_{\pi,T}\quad \sum_{k=0}^T c(x_k, \pi(x_k)) \quad \text{ s.t } \quad g(x_T) \leq 0, \quad I_{(\max_{k = 0, \dots, T} h(x_k) > 0)} \leq 0 \tag{B} \\\\
=& \min_{z_0, \pi, T}\quad z_0 \quad \text{ s.t. } \quad \sum_{k=0}^T c(x_k, \pi(x_k)) \leq z_0, \quad g(x_T) \leq 0,\quad I_{(\max_{k = 0, \dots, T} h(x_k) > 0)} \leq 0 \tag{C} \\\\
=& \min_{z_0, \pi, T}\quad z_0 \quad \text{ s.t. } \quad \max\left( \sum_{k=0}^T c(x_k, \pi(x_k)) - z_0,\\; g(x_T),\\; I_{(\max_{k = 0, \dots, T} h(x_k) > 0)} \right) \leq 0 \tag{D} \\\\
=& \min_{z_0, \pi, T}\quad z_0 \quad \text{ s.t. } \quad \hat{g}(\hat{x}_T) \leq 0 \tag{E} \\\\
=& \min\_{z_0} \quad z_0 \quad \text{ s.t. } \quad \min\_\pi \min_T \hat{g}(\hat{x}_T) \leq 0 \tag{F} \\\\
=& \min\_{z_0} \quad z_0 \quad \text{ s.t. } \quad \min\_\pi \tilde{V}\_{\hat{g}}^\pi (\hat{x}_T) \leq 0 \tag{G}
\end{align}
$$

This shows that the minimum-cost reach-avoid problem (1) is **equivalent** to the formulation we solve in this work (G), which is (8) in the paper. The formulation of RC-PPO solves (G) and thus also solves (1) because they are equivalent.

This new derivation will be included in the final version to improve clarity.
Thank you for a detailed response and additional experiments. 

I still have some concerns regarding the claims. I am very skeptical of the authors results since their formulations of reach-avoid problems do not solve the stated problem. This indicates the problem with the formulation or the hyperparameters. I don't think the authors made a significant effort to investigate why this occurs. However, the choices they made for the CMDP are not unreasonable, the authors detailed the experiments and the readers can see when the alternative fail. They also followed my suggestions which also didn't work well. 

Overall, I think the formulation is interesting and the authors have convinced me that it could be better to use directly than trying to formulate a CMPD and balance all the constraints.

I am raising my score.
**Fig. 2 Clarification**: The $\textcolor{#348ABD}{\textsf{blue star}\unicode{x2605}}$ in the bottom right denotes **RC-PPO**. Each $\textcolor{#777777}{\textsf{grey point}}$ forming the Pareto front denotes one choice of reward function coefficient from the grid search.