Efficient Policy Optimization in Robust Constrained MDPs with Iteration Complexity Guarantees

We appreciate your time and thoughtful evaluation of our paper. We recap your comment and present our detailed response as follows. We would also be happy to provide further clarifications if suitable.

Since the paper considers policy optimization, it is kind of weird to restrict the results to only the tabular case where the state space and action space is finite. Is it easy to extend to infinite state-action space setting?

• We now report results in continuous (infinite) state spaces using an actor–critic variant on CartPole. Specifically, we extend our method to a Robust Constrained Actor–Critic (RCAC) framework in which a neural‑network critic approximates Integral Probability Metric (IPM)‑based worst‑case values [A1] and the actor is updated via natural policy gradient. Training RCAC on the standard CartPole benchmark with IPM ambiguity set demonstrates that our approach scales beyond tabular settings to continuous state spaces with function approximation.

For the CartPole environment, we use the perturbation of $\delta=0.1$. We considered the cost function to be the absolute distance of the cart position from the center ($0$). Thus, in other words, the constraint function ensures that the cart remains as close to the centre as possible. The threshold for the constraint is 200. From the table, it is evident that among all the feasible approaches, our approach (RCAC) achieves the best reward. In particular, it significantly outperforms the EPIRC-PGS both in terms of reward and the wall-clock time. The main issue with EPIRC-PGS appears to be that the binary search is prone to error, particularly in the function-approximation setup, as the worst-case model might not be exact.

• Limitation. A complete theory for general function approximation lies beyond the scope of this paper. That said, the structure of IPM ambiguity sets yields closed‑form worst‑case value updates under linear function classes and a tractable surrogate in continuous (infinite) state spaces, suggesting a viable path to extend our analysis. Importantly, this extension is nontrivial: it requires (i) uniform deviation bounds for the IPM‑robust Bellman operator over rich function classes (e.g., covering‑number/Rademacher analyses), (ii) a careful bias–variance/error‑propagation analysis for an approximate worst‑case critic and its effect on natural policy‑gradient updates, (iii) the impact on the point-wise maximum over different value functions in the surrogate objective, and (iv) iteration‑complexity bounds that account for model misspecification. Our new experiments indicate that the method behaves well in practice; developing these guarantees is a substantive avenue for future work.

Is there any lower bound on the iteration complexity?

• The lower bound of iteration complexity, even for unconstrained robust MDP, remains open. Characterizing the lower bound indeed or achieving a better upper bound for RCMDP constitutes an important future research question.

It seems that the reference [10] belongs to the LP-based methods for solving the primal problem directly, instead of addressing the iteration complexity?

• The reviewer is correct. We will specify that.

[A1]. Zhou, Ruida, et al. "Natural actor-critic for robust reinforcement learning with function approximation." Advances in neural information processing systems 36 (2023): 97-133.

We appreciate your time and thoughtful evaluation of our paper. We recap your comment and present our detailed response as follows. We would also be happy to provide further clarifications if suitable.

The authors assume that the initial policy is strictly feasible, which may not be the case in many scenarios.The authors also mention that this assumption (Assumption 1) can be relaxed in Theorem 6.1 by setting \lambda = 2H/ \epsilon and the proof is easy to follow afterward. The authors mentioned that the algorithm would have an O(\epsilon^{-4}) in this case, similar to the algorithm in reference [8]. I was curious if the authors could comment on the performance of the RNPG algorithm and [8] if the algorithms are initialized with an infeasible policy.

• Thank you for pointing this out. The reviewer’s interpretation is not accurate:

• No strict‑feasibility requirement for the starting policy. Our algorithm can be initialized with an infeasible policy. For all our experiments, the initial policy is a random policy that can be both in the feasible and infeasible region. We had further experiments where the initial policies were strictly infeasible, yet the algorithms were able to quickly move to safer regions despite initially starting from the unsafe regions.

  • We ran our algorithms on the Garnet environment and the Garbage Collector environment. For the Garnet environment, our algorithm started with a policy that returned an objective value function (maximize it) of 103.12 and has a cost value function of 98.5 (which is infeasible as it needs to be above $100$). However, the final policy has an objective value function and constraint value function of 175.11 and 120.00, respectively.

  • For the Garbage collector, the Initial value function (maximize it) is 220.216, with an initial cost function (which should lie below 60) of 82.02. The final value function and constraint cost function are 170.21 and 56.15, respectively.

• Clarification of Assumption 1. We assume only that the optimal policy is strictly feasible. Under this condition, the algorithm produces a policy that is atmost $\epsilon$ sub-optimal and feasible within $O(\epsilon^{-2})$ iterations. No constraint is imposed on the feasibility of the initial policy.

We will revise the manuscript to emphasize this distinction and prevent further confusion.

The authors mentioned that Assumption 2 is a strict one as the Assumption assumes that the transition functions of each set have a similar probability (based on \Beta) for each successive states, which allows the authors to use Lemma B.3 in the Appendix..

• Thank you for raising this point. Relaxing Assumption 2 is indeed a key direction for future work. As the reviewer correctly notes, if the perturbed distribution assigns positive probability to an event, the nominal model should also assign positive probability to that event. Otherwise, a mismatch in supports could lead to unsampled regions and render finite‑sample bounds intractable, hence, it seems that this assumption is essential. While this assumption is essential for establishing our theoretical guarantees, we deliberately did not enforce it in the empirical study; the algorithm still performed well, suggesting that the practical impact may be less restrictive than the theory implies. A rigorous treatment of differing supports—and corresponding error bounds—remains an open and important challenge. Also, note that a similar assumption is also made for unconstrained robust MDP [A1]. Further, EPIRC-PGS also assumed that the ratio between the state-action occupancy measures on the states covered by all policies and the initial state distribution is bounded. Hence, it seems that one needs an assumption similar to Assumption 2 to achieve theoretical guarantees for robust MDP and RCMDP.

The authors used a KL-regularizer term for stability in their proofs. I was curious if the authors could comment on other regularization functions or formulations for ensuring robust feasibility. For example, I was curious if the authors could make a comparison with the set-based reachability analysis compared to using a KL-divergence term for regularization.

• Our algorithm can work with other uncertainty sets except the KL-uncertainty sets, where there are effective approaches to find the worst-case value function. For example, we have now achieved results for continuous state-space with the Integral probability metric (IPM), where we used $L_2$-norm as a regularization to train the critic network. We extend the work to a Robust Constrained Actor Critic (RCAC) paradigm, which uses Neural networks to approximate the critic and uses natural policy gradient to update the actor network. We train the RCAC algorithm on the standard Cartpole environment with the Integral Probability Metric (IPM) as the ambiguity set for the worst-case value function. The result shows that our work can be substantially scaled to a continuous state space.

For the CartPole environment, we use the perturbation of $\delta=0.1$. We considered the cost function to be the absolute distance of the cart position from the center ($0$). Thus, in other words, the constraint function ensures that the cart remains as close to the centre as possible. The threshold for the constraint is 200. From the table, it is evident that among all the feasible approaches, our approach (RCAC) achieves the best reward. In particular, it significantly outperforms the EPIRC-PGS both in terms of reward and the wall-clock time.

[A1]. Zhou, Ruida, et al. "Natural actor-critic for robust reinforcement learning with function approximation." Advances in neural information processing systems 36 (2023): 97-133.

We appreciate your time and thoughtful evaluation of our paper. We recap your comment and present our detailed response as follows. We would also be happy to provide further clarifications if suitable.

Only toy experiments are provided. It is not irrational to claim that the algorithm is more computationally efficient by providing only toy examples...

• We appreciate the concern. Our claim is about relative computational efficiency—for a fixed robust‑evaluator—and follows from RNPG’s algorithmic structure. Methods such as EPIRC‑PGS require an outer search/binary-search over the epigraph parameter, which can be significant when the worst-case value function times increase (e.g., TV/Wasserstein) or for infinite state-space where the worst-case evaluator can be noisy. In particular, EPIRC-PGS needs to find the maximum policy for each parameter $b_0$, and then needs to tune that parameter using a binary-search method; our approach does not require that. Hence, it is quite evident that our approach is efficient.

Evidence beyond small/tabular settings

Function approximation & continuous state space.
We add a Robust Constrained Actor–Critic (RCAC) with a neural critic (IPM‑based worst‑case estimator) and natural policy‑gradient actor updates. On CartPole (continuous state) with perturbations, RNPG attains feasibility and high return using mini‑batch updates and an approximate robust oracle—demonstrating that benefits are not artifacts of tabularity.

For the CartPole environment, we use the perturbation of $\delta=0.1$. The threshold for the constraint is 200. From the table, it is evident that among all the feasible approaches, our approach achieves the best reward. In particular, it significantly outperforms the EPIRC-PGS both in terms of reward and the wall-clock time.

2.Strength against EPIRC-PGS.

Also, we would urge the reviewer to see the results on sparse‑transition domains (e.g., RiverSwim variants), larger $\gamma$-values, and larger tabular MDPs with increasing state counts. As the worst-case evaluation time increases, our approach achieves a better result compared to EPIRC-PGS.

We would also like to bring to the reviewer’s attention that our supplementary paper also lists a few experiments motivated from the gymnasium or safety-gymnasium library specially designed for CMDP studies, such as the Modified frozen-lake and the Garbage collector where we consistently outperforms EPIRC-PGS.

Regarding Proof of Lemma B.3..

• We apologize for an oversight. First, there are typos in the proof of Lemma B.3. In particular, $\pi^*$,

should be replaced by $\hat{\pi}^*$ , the optimal solution of the surrogate problem in (9). As Lemma B.3 only deals with the surrogate problem.

• Second, we will explicitly mention that $\hat{\pi}^*$

is a uniform minimizer of the surrogate problem (we have removed $\lambda$ to maintain notational simplicity for Markdown)

$\min_{\pi}\max_{i}[\max_PV^{\pi,P}_{c_i}(s)] \forall s$.

We will update eq.(9) with this modification. Note that, we do not need this assumption on the $\pi^*$ of the original RCMDP. Rather, we need it for the optimal solution for the surrogate problem in (9). Note that this is similar to the Assumption made for the unconstrained setup as well [A1,A2].

• Third, using this, we can now expand in the following way, for a given $s$, $\max_{j}(\max_{p}V_{c_j}^{\pi,p}(s))-\max_{j}(\max_{p}V_{c_j}^{\hat{\pi}^*,p}(s))$

$\leq V_{c_i}^{\pi,p}(s)$ $-V_{c_i}^{\hat{\pi}^*, p}(s)$,

where we use the fact that $(p,c_i)=\arg\max_{j,p} V_{c_j}^{\pi,p}(s)$

• Fourth, we also missed $p$ in the last line of (31), in particular $Q^{\pi}$, and $V_{\pi}$ will be associated with $p$. (Also, the notation $\pi_s$, simply means $\pi(\cdot|s)$; we have used this notation in (11) as well, perhaps we will redefine it again to avoid confusion).
  Hence, in eqn (31), we apply the fact that

$V_{c_i}^{\pi,p}(s)=\max_{j,p}(V_{c_j}^{\pi,p}(s))\geq \max_{j,p}(V_{c_j}^{\hat{\pi}^*,p}(s))$

$\geq V_{c_i}^{\hat{\pi}^*,p}(s)$

because of the uniform minimizer assumption on $\hat{\pi}^*$ $\forall s$, this allows us to use Assumption 2, and use $p_0$

in place of $p$ . We then expand the second term again and complete the proof by Induction. Lemma B.3 mimics Lemma 9 in [A1] for the RCMDP. Since it is true for every atom, we can then easily show that for any initial state distribution $\rho$, concluding it for $J$ which we need to show for Lemma 4.2

I didn't further check the remaining proof as the manuscript should be fully revised to improve its readablity and correctness.

• We believe that we have taken utmost care to avoid any proof bugs. We respectfully ask the reviewer to reexamine the revised proofs; if any particular step remains unclear, we will gladly provide an even more detailed, line referenced justification in the supplement.

• To summarize, the only concern of the reviewer was the proof of Lemma B.3 because there were some typos (minor issues) and the lack of justification on $V_{c_i}^{\pi,p}(s)\geq V_{c_i}^{\hat{\pi}^*,p}$. Lemma B.3 only concerns the surrogate optimization problem, not the original optimization problem. We have now fixed the issue on the assumption of the uniform maximizer of the surrogate problem in (9) by $\min_{\pi}\max_{i}[\max_PV^{\pi,P}_{c_i}(s)] \forall s$. Crucially, this assumption is only on the surrogate problem, not on the original problem, and an Assumption that is also used in the unconstrained version [A1,A2]. Further, this fix is local and does not alter any theorems, rates, or conclusions: the statements and proofs go through verbatim after the correction, and all empirical results are unchanged. We have also strengthened our paper with new results for large state-space (CartPole).

This paper relies on a very specific uncertainty set. Though it is claimed that "Our framework is not limited to KL-divergence", the explanation and the empirical analysis are not sufficiently convincing.

• As we mentioned, our contribution is not in terms of developing a policy evaluation algorithm; rather, our contribution is towards provable iteration complexity guarantee for RCMDP. It is not trivial, as, unlike the CMDP, we cannot use the traditional primal-dual-based approach because the worst-case value function is different for the objective and the constraint, rendering the robust dynamic programming approach inapplicable on the composite value function. We therefore introduce a surrogate optimization problem, prove its tight relationship to the original RCMDP, and design an algorithm that achieves provable iteration complexity for the surrogate despite the additional pointwise‑max operator that is absent in the unconstrained case. In contrast to EPIRC‑PGS, our method avoids the epigraph/binary‑search loop, leading to faster convergence in practice. Further, since the binary search loop requires an accurate evaluation of the worst-case value function, EPIRC-PGS is not suitable for a large-scale setup. While our theory is developed in the tabular/linear regime, the formulation and algorithm extend to continuous (infinite) state spaces with function approximation, unlike the EPIRC-PGS—supported by new experiments—leaving a full general‑FA theory as important future work.

The proposed methods cannot be extended to the general function approximation...

• While our theory does not yet cover general function approximation, the methodology itself extends naturally. In the revision, we add an actor–critic instantiation of RNPG, robust constrained actor-critic (RCAC) for large state spaces: the critic is trained as an IPM‑based worst‑case value estimator (approximate robust oracle) [A1] from samples, and the actor is updated with RNPG using mini‑batches. On the perturbed CartPole, this implementation attains high returns with feasibility, indicating that RNPG is practically applicable beyond the tabular setting. The comparison with the other approaches is shown below:

For the CartPole environment, we use the perturbation of $\delta=0.1$. The threshold for the constraint is 200. We considered the cost function to be the absolute distance of the cart position from the center ($0$). Thus, in other words, the constraint function ensures that the cart remains as close to the centre as possible. From the table, it is evident that among all the approaches that are feasible, our approach achieves the best reward. In particular, it significantly outperforms the EPIRC-PGS both in terms of reward and the wall-clock time.

In short, although a complete general‑FA proof is outside the present scope, our new experiments demonstrate that RNPG does extend in practice to function approximation and large state spaces, mitigating the reviewer’s concern.

[A1]. Zhou, Ruida, et al. "Natural actor-critic for robust reinforcement learning with function approximation." Advances in neural information processing systems 36 (2023): 97-133.

[A2]. Iyengar, Garud N. "Robust dynamic programming." Mathematics of Operations Research 30, no. 2 (2005): 257-280.

We appreciate your time and thoughtful evaluation of our paper. We recap your comment and present our detailed response as follows. We would also be happy to provide further clarifications if suitable.

Assumption 1 requires knowledge of $\xi$..

• The reviewer is correct. We have also pointed that out in the main text; we will point that out in the Abstract as well. Also, note that we did not use the feasibility information for our empirical results.

Convergence also needs a “positive‑density” condition on transition kernels..

• Perhaps, the reviewer is referring to Assumption 2, which states that if the perturbed distribution assigns positive probability to an event, the nominal model should also assign positive probability to that event. Otherwise, a mismatch in supports could lead to unsampled regions and render finite‑sample bounds intractable. While this assumption is essential for establishing our theoretical guarantees, we deliberately did not enforce it in the empirical study; the algorithm still performed well, suggesting that the practical impact may be less restrictive than the theory implies. Also note that such types of assumptions are common in robust unconstrained PG approaches [A1]. Note that EPIRC-PGS also assumed that the ratio between the state-action occupancy measures on the states covered by all policies and the initial state distribution is bounded.

• Regarding practical prevalence, our experiments include sparse‑transition domains such as RiverSwim, where many transitions have very small probabilities (Figure 2). In these settings, RNPG achieves feasibility and outperforms state‑of‑the‑art baselines, indicating that the method remains effective compared to the state-of-the-art approaches. We will clarify this in the text.

All experiments use exact tabular robust evaluators; no test shows RNPG with sampled value estimates, function approximation, or large state spaces...

• We now report results in large/continuous state spaces using an actor–critic implementation with function approximation and sample‑based value estimates. The robust evaluator is implemented as an Integral Probability Metric (IPM)‑based worst‑case critic learned from data (i.e., an approximate robust oracle) inspired by [A1], and RNPG updates are computed using mini‑batches. On benchmarks such as CartPole (and larger state‑space variants), RNPG achieves high returns while satisfying constraints under perturbations, and outperforms other approaches for RCMDP and vanilla CMDP. Further, its wall-clock time is comparable to the non-robust and robust CRPO versions. We will include architectural details, batch sizes, and training protocols in the final version. The results are in the following:

For the CartPole environment, we use the perturbation of $\delta=0.1$. The threshold for the constraint is 200. From the table, it is evident that among all the approaches that are feasible, our approach (RCAC) achieves the best reward. In particular, it significantly outperforms the EPIRC-PGS both in terms of reward and the wall-clock time. The main issue with EPIRC-PGS appears to be that the binary search is prone to error, particularly in the function-approximation setup [A2], as the worst-case model might not be exact. We will include the new result in the final version.

• Note that for IPM, there is a closed-form expression of the worst-case value function with the linear representation. We can use that result to achieve the iteration complexity result. However, the complete characterization is left for the future, and we will mention that in the final version.

Every RNPG step still solves for each cost/reward. For KL sets this is closed‑form, but for TV/Wasserstein sets it involves linear programs or iterative solvers..

• For TV/Wasserstein ambiguity sets, computing the worst‑case model/value indeed requires solving a convex program or using an iterative solver. This requirement, however, is shared by the baselines—including EPIRC‑PGS and unconstrained robust PG—so the cost of the “robust evaluator” is orthogonal to our contribution. RNPG’s advantage is that it eliminates the outer binary‑search loop, thereby reducing the number of robust‑evaluation calls per update. In other words, when the same evaluator backend is used for all methods, RNPG incurs fewer invocations of that backend and thus reduces end‑to‑end time.

• To make this point concrete, we have added large state‑space experiments where all methods use the same robust‑evaluation module (identical solver and settings). Under this like‑for‑like setup, RNPG achieves better wall‑clock time than EPIRC‑PGS while maintaining feasibility and high reward. We will include full timing tables and implementation details (solver, tolerances, batch sizes) in the revised version.

• For KL ambiguity sets the evaluator admits a closed‑form update. Moreover, for several $L_p$ error‑ball models, the worst‑case model/value also has closed‑form expressions (see [A3]), making RNPG directly applicable with low evaluator overhead.

It might have been interesting to also see a baseline of a naive Lagrange method or something like CRPO applied with worst-case values...

• Thank you for the suggestion. We have added a robust CRPO baseline that uses the same worst-case evaluator as RNPG (i.e., robust values under the chosen ambiguity set) for the constrained Garnet environment (Section 5, Figure 1). The results are in the followings:

Here, the utility needs to be above $100$ for feasibility. Again, RNPG outperforms EPIRC-PGS and Robust-CRPO in terms of reward while achieving feasibility. Further, its wall-clock time is $4\times$ smaller than the EPIRC-PGS. We will add the details in the final version.

[A1]. Zhou, Ruida, et al. "Natural actor-critic for robust reinforcement learning with function approximation." Advances in neural information processing systems 36 (2023): 97-133.

[A2]. Waeber, Rolf, Peter I. Frazier, and Shane G. Henderson. "Bisection search with noisy responses." SIAM Journal on Control and Optimization 51.3 (2013): 2261-2279.

[A3]. Kumar, Navdeep, et al. "Policy gradient for rectangular robust markov decision processes." Advances in Neural Information Processing Systems 36 (2023): 59477-59501

We are glad that our responses have resolved your questions, and we are thankful for your positive evaluation.