Rectified Robust Policy Optimization for Robust Constrained Reinforcement Learning without Strong Duality

We appreciate the reviewer's constructive suggestions. Here is our point-to-point responses:

Relation To Broader Scientific Literature:

The reviewer's suggestion on providing more application scenarios is indeed helpful. We will revise the introduction section to include these applications.

Other Strengths And Weaknesses:

1. RRPO is similar to CRPO: Given that strong duality may not hold in robust constrained RL, it is natural to explore whether existing algorithms in constrained RL can still be effective. Our contribution is not in proposing an entirely new algorithm but in demonstrating that it is possible to apply an existing classical constrained RL approach to achieve optimal sample complexity without relying on strong duality assumptions. This direction will not be less challenging than proposing a new algorithm for these reasons: (1) Many literatures in constrained RL will rely on the famous paper "Constrained Reinforcement Learning Has Zero Duality Gap". If the strong duality doesn't hold, most of these theoretical analysis will be invalid. (2) Even if the convergence analysis doesn't rely on the zero duality gap, in our empirical examples, the CRPO will still converges to the infeasible result. As the result, we successfully address these two challenges and show that it is not necessary to include additional complicated structures.

2. Assumption 4.2 violates the counterexample: We would like to clarify that Assumption 4.2 doesn't contradict the counterexample, because

   • The stationary distribution at $s_1$ is not zero unless the policy $\pi(a_1|s_0)=1$. In this case ($\pi(a_1|s_0)=1$), everytime the agent arrives the state $s_0$, it will be trapped there, which makes the state $s_1$ transient. More explicitly, if we let $\pi_0:= \pi(a_0|s_0)$ and $\pi_1:= \pi(a_1|s_0)$, we can solve the stationary distribution to check the transiency as $\mu = \begin{pmatrix} \dfrac{1}{1 + \pi_1(1-p)} \\ \dfrac{\pi_1(1-p)}{1 + \pi_1(1-p)} \end{pmatrix}$.
   • In Assumption 4.2, we are using the discounted visitation measure. This definition is slightly different from the stationary distribution. As for all ergodic Markov chain, the stationary distribution is independent with respect to the initial distribution, while the discounted visitation measure will rely on that. Therefore, we comment it under Assumption 4.2 that we can use a more uniform initial distribution to obtain a strictly positive $p\_{\min}$, which is also valid for our counterexample and will not change the absence of strong duality of robust constrained RL.

3. In Theorem 4.3, the dependency on the model mismatch is included in the Policy Evaluation Accuracy assumption. Usually, the larger the model mismatch is, the higher computation is required to achieve the desired accuracy. It could depend on the structure of uncertainty set and the the robust policy evaluation algorithm, which is out of the scope of our study.

4. We appreciate the reveiwer's valuable suggestions. We will add these baselines in our revision.

Regarding Major Issues

We deeply appreciate the reviewer's careful reading. We absolutely understand that these two concerns are critical and we truly believe they are caused by some misunderstandings from our unclear presentations. Here we make additional discussions to make it more clear and explain why they are correct:

1. Invalid telescoping: It is correct that all inequalities (Lemma C.6 and Lemma C.7) only hold when $t\in \mathcal{N}_i:=\\\{ t: V_i^{\pi_t} \text{ is sampled to update}\\\}$. However, we would like to highlight that we can always sum it over $t$ with carefully handling the mismatch in the indices. To make it more clear, we will use $i_t$ to indicate that at the $t$-th step, $V_i^{\pi_t}$ is sampled. Therefore, when we sum $V\_{i\_t}^{\pi^*}(\mu) - V\_{i\_t}^{\pi\_{t+1}}(\mu) \leq a[d(\pi^*, \pi\_t) - d(\pi^*, \pi\_{t+1})]+b$ over $t$ (as an example), it becomes $\sum\_{t=1}^T \left[ V\_{i\_t}^{\pi^*}(\mu) - V\_{i\_t}^{\pi\_{t+1}}(\mu) \right] \leq a [d(\pi^*, \pi\_1) - d(\pi^*, \pi\_{T})] + Tb.$ As the right-hand side doesn't depend on the index $i$, this summation is always valid. We spent a lot of effort to make it happen: (1) We use the Lipschitzness in $\pi$ of $V_i^\pi$ to remove the dependence on $i$ in Line 1165, (2) we replace \hat{Q}\_i^{\pi\_i} - \{Q}\_i^{\pi\_i} with the policy evaluation error (Assumption 4.1), and (3) we follow the standard NPG result to decomposite KL divergence to construct the desired crossing structure $a [d(\pi^*, \pi\_1) - d(\pi^*, \pi\_{T})]$ (Lemma C.7).

   When handling the left-hand side, we set $\delta$ to be "not too small" in Lemma C.8. Under this setting, we ensure that the set $\mathcal{N}_0$ is always non-empty; it means in the whole training process $t=1,2,\dots,T$, there always exists $t$ such that the indice $0$ is sampled. As the result, in Line 1169, we can keep this term $\sum\_{i \in \mathcal{N}_0}$ and lower bound other terms $\sum\_{i \notin \mathcal{N}_0}$ using a trivial bound obtained from Line 1157 - Line 1166.

2. Misuse Lemma C.4 in Lemma C.6 and Lemma C.7: We hope clarify that the we are correctly using Lemma C.4. It doesn't require the initial distribution to be fixed as $\mu$; instead, it is an inequality depending on the initial distribution. When we change the initial distribution $\mu$ to another distribution $\nu$, the inequality still reads: $a E\_{d_\nu \otimes \pi'} [A^\pi(s,a)] \leq V^{\pi'}(\nu) - V^{\pi}(\nu) \leq b E\_{d_\nu \otimes \pi'} [A^\pi(s,a)].$ The difference includes: (1) The visitation measure is changing from $d_\mu$ to $d_\nu$. (2) The robust value function is changing from $V(\mu)$ to $V(\nu)$. As the result, we are using Lemma C.4 in Lemma C.6 and Lemma C.7 as follows:

   • In Lemma C.6, we use Lemmca C.4 in Line 957 - Line 958, which honestly follows the structure of Lemma C.4. In Line 1033 mentioned by the reviewer, it follows another result $d\_\nu = \frac{d\_\nu}{\nu} \nu \leq (1-\gamma) \nu$, which applies a trick of the change of measure to change the current measure $d\_\nu$ to another measure $\nu$. The Lemma C.4 is not involved here.
   • In Lemma C.7, we use Lemma C.4 in Line 1075. Here, we have defined a short-cut notation $\nu^*$ to represent $d\_\mu^{\pi^*, P^*}$ in Line 1073. As the subscript $\mu$ is aligned with the argument in $V^\pi(\mu)$ on the left-hand side, our applying Lemma C.4 here is still correct.

Regarding Other Issues

We thank the reviewer again for providing us with these constructive suggestions. We will revise our manuscript based on these valuable comments and we will clearly state that our method can only handle the uncertainty set where the efficient Q-function approximators are equipped.

We sincerely appreciate the reviewer’s detailed comments and valuable insights. Below, we provide our point-by-point responses.

Claims And Evidence:

• Primal-dual methods will fail in robust constrained RL:

  We would like to clarify that we never claimed that primal-dual methods will fail in all cases. Instead, we carefully used the phrase "may fail" to emphasize its potential limitations, motivating the need for a non-primal-dual approach. Specifically, we stated:

  "... it indicates that primal-dual methods may fail to find optimal feasible policies in robust constrained settings." (Page 2).

• Trivial experiments:

  Our experiments were carefully designed to highlight scenarios where a non-robust algorithm may violate constraints in the worst case. We also appreciate the reviewer’s suggestion to include experiments in the MoJoCo environment to demonstrate cases where the robust algorithm outperforms the non-robust one under perturbations. We will incorporate this addition in our revision.

Essential References Not Discussed:

We sincerely appreciate the reviewer for bringing these important references to our attention. We will add these missing references into our work.

Other Strengths And Weaknesses:

• RRPO is similar to CRPO: Given that strong duality may not hold in robust constrained RL, it is natural to explore whether existing primal-only algorithms can still be effective. Our contribution is not in proposing an entirely new algorithm but in demonstrating that this classical constrained RL approach can achieve optimal sample complexity without relying on strong duality assumptions, which is different from existing robust constrained RL literatures which additionally assume the strong duality.
• Solving the robust value function: Rather than proposing a specific solution method for the robust value function, we assume it can be computed with desired accuracy. In Appendix C.3, we describe two valid robust policy evaluation approaches. Additionally, a particular update rule for the p-norm $(s,a)$-rectangular set is given in Eq.(14).