Solving Minimum-Cost Reach Avoid using Reinforcement Learning

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.

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

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 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|| + Small Noise|| + 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|| + Small Noise|| + 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.