The paper considers ... where a CMDP has to be solved

We 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:

State augmentation is not a novel technique, albeit the application is different.

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

Why is minimum-cost reach-avoid an important problem?

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

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

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

Can simpler methods solve this problem with the right reward function coefficients?

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.

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.

Problem statement is a bit of an art. Sometimes it is simply given.

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.

Why minimize the z_0 with the constraint z_t >=0?

We DO NOT impose the constraint z_t >=0, as the question implies.

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

Our 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)

This gives us a problem with only three constraints, which we can solve using reachability.

If 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).

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.

Would it be easier to track the accumulated cost and minimize the terminal state?

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.

“nonlinear numerical optimization may result in ... suboptimal local minima [14].” How does the paper address this issue?

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

[1] Altman 1999, "CMDP"
[2] Aivar et al 2022, "Sauté rl..."
[3] Jiang et al 2023, "Solving Richly..."
[4] Jiang et al 2024, "Reward Penalties..."
[5] Wang et al 2024, "Active Disruption Avoidance ... Tokamak ..."
[6] Huang et al 2020, "Accelerated DeepRL ... Emergency Voltage Control"
[7] Boyd 2004, "Convex optimization"
[8] Suh 2022, "Do Differentiable..."
[9] Grandesso 2023, "CACTO..."

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.

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:

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.

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

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}}$:

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

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

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.

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?

You are correct, this should be Figure 4.

The presented experimental results are solid and illustrative, but could be extended.

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.

If you have any further suggestions on how the presented experimental results could be extended, we would love to hear your thoughts!

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.

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.

What is the motivation of using two-phase PPO to solve this problem?

The minimum-cost reach-avoid problem (1) cannot be exactly framed into problem structures that existing methods are able to solve. Our two-phase method directly solves the minimum-cost reach-avoid problem (1). In comparison, alternate RL methods either:

1. Only solve the reach-avoid problem without consideration of the cumulative cost.
2. Solve unconstrained problems (e.g., PPO, SAC, TD3)
3. Solve problems with CMDP constraints that constrain the expectation over initial states of the sum of some cost function (e.g., CPPO, RESPO)

Since 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).

We 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).

1. 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$.
2. 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.
3. 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).

Providing performance comparisons with other RL algorithms, such as TD3 and SAC, will significantly strengthen the rationale behind proposing this approach

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

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

As 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).

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

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.

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

[1] Policy Gradient Approaches for Multi–Objective Sequential Decision Making
[2] Empirical evaluation methods for multiobjective reinforcement learning algorithms

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

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:

To solve this multi-objective optimization problem, we employ scalarization and introduce a weight $w \geq 0$, giving

Solving the scalarized problem ($\dagger$) gives us the following solution as a function of $w$:

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.

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.