Efficient Policy Optimization in Robust Constrained MDPs with Iteration Complexity Guarantees
Authors: Sourav Ganguly
Kishan Panaganti
Arnob Ghosh
Adam Wierman
Venue: NeurIPS 2025 poster ()
Keywords: Robust MDP
CMDP
Primal-dual optimization
iteration complexity
Natural Policy Gradient
Primary area: reinforcement_learning
TL;DR: We provide O(\epsilon^{-4}) iteration complexity policy optimization algorithm for robust constrained Markov Decision Processing

Abstract: Constrained decision-making is essential for designing safe policies in real-world control systems, yet simulated environments often fail to capture real-world adversities. We consider the problem of learning a policy that will maximize the cumulative reward while satisfying a constraint, even when there is a mismatch between the real model and an accessible simulator/nominal model. In particular, we consider the robust constrained Markov decision problem (RCMDP) where an agent needs to maximize the reward and satisfy the constraint against the worst possible stochastic model under the uncertainty set centered around an unknown nominal model.  Primal-dual methods, effective for standard constrained MDP (CMDP), are not applicable here because of the lack of the strong duality property. Further, one cannot apply the standard robust value-iteration based approach on the composite value function, either, as the worst-case models may be different for the reward value function and the constraint value function. We propose a novel technique that effectively minimizes the constraint value function--to satisfy the constraints; on the other hand, when all the constraints are satisfied, it can simply maximize the robust reward value function. We prove that such an algorithm finds a policy with at most $\epsilon$ sub-optimality and a feasible policy after $O(\epsilon^{-2})$ iterations. In contrast to the state-of-the-art method, we do not need to employ a binary search; thus, we reduce the computation time and achieve a better performance, especially for continuous state-space.

Efficient Policy Optimization in Robust Constrained MDPs with Iteration Complexity Guarantees
Sourav Ganguly
Kishan Panaganti
Department of ECE
Department of CMS California Institute of Technology (now at Tencent AI Lab, Seattle, WA) kpb rww.erechhggaai................. com
New Jersey Institute of Technology
New Jersey, USA
sg2786enjit.cm edu
Arnob Ghosh
Adam Wierman
Department of ECE
Department of CMS
New Jersey Institute of Technology
California Institute of Technology
New Jersey, USA
California, USA adamv@caltech.. edu
arnob. hiaebbghhohhnnitte...
Abstract
Constrained decision-making is essential for designing safe policies in real-world control systems, yet simulated environments often fail capture real-world ad- versities. We consider the problem of learning a policy that will maximize the cumulative reward while satisfying constraint, even when there mismatch between the real model and an accessible simulator/nominal model. In particular, we consider the robust constrained Markov decision problem (RCMDP) where an agent needs to maximize the reward and satisfy the constraint against the worst possible stochastic model under the uncertainty set centered around an unknown nominal model. Primal-dual methods, effective for standard constrained MDP (CMDP), are not applicable here because the lack the strong duality prop- erty. Further, one cannot apply the standard robust value-iteration based approach on the composite value function either as the worst case models may be different for the reward value function and the constraint value function. We propose novel technique that effectively minimizes the constraint value function- satisfy the constraints; the other hand, when all the constraints simply maximize the robust reward value function. We prove that such an algo- rithm finds policy with at most sub-optimality and feasible policy after O(e-2) iterations. In contrast to the state-of-the-an methods, we do not need to employ a binary search, thus, reduce the computation time for larger value of discount factor (7), and achieve better performance for large state space.
satisfied, it
1 Introduction
Ensuring safety satisfying constraints is important for implementation of the RL algorithms in the real system. A poorly chosen action can lead to catastrophic consequences, making it crucial to incorporate safety constraints into the design. For instance, in self-driving cars M. a slight safety violation can result in serious harm to the system. Constrained Markov Decision Process (CMDP) can address such safety concerns where the agent aims to maximize the expected reward while keep- ing the expected constraint cost within a predefined safety boundary (2) (cf. CMDPs effectively restricted agents from violating safety limits 4 However, in many practical problems, an al- gorithm is trained using simulator which might be different from the real world. Thus, policies obtained for CMDP in simulated environment can still violate the constraint in the real environment.
To resolve the above issues, recently, researchers considered robust CMDP (RCMDP) problem where the constraint needs to be satisfied when there model-mismatch due to the sim-
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Wall-clock time comparisons (in secs)
EPIRC-PGS (> vals.)
Environment Name
RNPG (our)
0.9
0.99
0.995
CRS
48.574
190.53
228.65
290.15
Garnet
78.406
290.21
316.23
453. 14
Modified Frozenlake
160.31
453.7
561.47
620.12
Garbage collector
177.13
344.87
400.13
489.54
Table 1: Comparison of execution times averaged over multiple runs between RNPG, and EPIRC-PGS (inner
loop T 100 and outer-loop K=10) (Some more experimental results to demonstrate faster performance of our algorithms be found in appendix G
to-real gap. particular, we seek to solve the problem
RCMDP objective: minmax J s.t. max JR.P 64 PEF
bb iE (l,...., K}.
PEP
where Je., is the expected cumulative cost for the associated RCMDP cost function Cn (see Sec- (2. Here P is the uncertainty set centered around nominal (simulator) model described in (6). Note that learning the optimal policy for RCMDP are more challenging compared to the CMDP. In particular, the main challenge lies in the fact that the standard primal-dual based approaches, which achieve provable sample complexity results for the CMDP problems [3] 6 cannot achieve the same for the robust CMDP problem as the problem may not admit strong duality even when the strict fea- sibility holds 77. This is because the state occupancy measure is no longer convex as the worst-case transition probability model depends on the policy. Due to the same reason, even applying robust value iteration is not possible for the Lagrangian unlike the non-robust CMDP problem.
Recently, g proposed an epigraph approach to solve the problem in ( In particular, they consid- ered
min s1,0
bp s.t. Jr. bn S O; n E
Hence, the objective is passed on the constraint with an objective of how tight the constraint can be. [8] finds the optimal policy for each by. and then optimized by using binary search. They showed that for each bp. the iteration complexity is O(e=a) to find the optimal policy. Note that one needs to evaluate robust value function at every iteration for each bo which is costly operation especially when 7 large as is evident by T Further, the binary search method only works when the estimation is perfect [9] thus, if the robust policy evaluator is noisy which is more likely for the large state-space, the binary search method may not work as it is evident in our function approximation setup (Appendix G). Moreover, the complexity of iteration is only O which is worse than that of the CMDP 10]. We seek to answer the following:
Can we develop a computationally more efficient (without binary search) ap- proach for robust CMDP problem with faster iteration complexity bound?
Our Contributions
We propose a novel approach to address the optimization problem. Specifically, we reformulate follows:
J
min Max
max n
- bm
(3)
This formulation balances the trade-off between optimizing the objective and satisfying the con- straints. When max., [J=, 6n] > O, the focus on reducing constraint violations. Otherwise, the objective J is minimized, scaled by the factor A. Notably, this framework eliminates the need for binary search over >; solving the above problem directly yields a policy that respects the con- straints for an appropriately chosen A. We show the almost equivalence of optimal solution of (3) and (T). However, because of the point-wise maximum over the multiple objectives, it introduces additional challenges in achieving the iteration complexity, as the index of the value function of the objective now depends on the policy.
We propose an algorithm (RNPG) that gives a policy which is at most e-sub optimal and feasible after o iterations if the strict feasibility parameter & known. This is the first result to show that strict safety fcasibility can be achieved. This improves the existing iteration complexity

---

1
Ollo
achieved by EPIRC-PGS by 8 Our algorithm does not rely on binary
(1-r)e
search and uses KI. regularization instead of projected gradient descent. We also show that if we do not know Ç, we can achieve a policy that violates the constraint by most e amount while being at most c-suboptimal with O(1/c*) iteration complexity. Moreover, our dependence on the
state-space (S), and the effective horizon (i.e.,
are much better compared EPIRC-PGS.
We extend our framework to the function approximation setup by proposing a robust constrained actor-critic with integral probability metric the uncertainty metric. For the finite-state, our empirical results show that our proposed approaches achieve a feasible policy with good reward (comparable better than the one achieved by EPIRC-PGS, see Table 1T) faster wall-clock time (see Table compared to the EPIRC-PGS. From Table | it is evident that our algorithm speeds up the computation process by at-least times as compared EPIRC-PGS algorithm when y 0.9 and at-least 3 times to EPIRC-PGS when = 0.995. For the function approximation setup, our proposed approach is the only one that achieves feasibility and even better reward to the robust version of CRPO [1] during the test time for Cartpole experiment (Table T2p. Further, we outperform EPIRC-PGS significant manner for the function approximation setup both in terms of performance and the training time showing its efficacy.
1.1 Related Works
CMDP: The convex nature of the state-action occupancy measure ensures the existence of a zero duality gap between the primal and dual problem for CMDP, making them well-suited for solution via primal-dual methods 2 12 The convergence bounds and rates of convergence for these methods have been extensively studied in (20-24 25 26). Beyond primal-dual methods, LP-
based and model-based approaches have been explored to solve the primal problem directly 18
28
29
30). However, the above approaches cannot be extended the RCMDP case.
Robust MDP: For robust (unconstrained) MDPs (introduced in [31). recent studies obtain the sample complexity guarantec using robust dynamic programming approach [32 Model-free approaches are also studied [34 (774441 However, extending these methods to Robust Constrained MDPs (RCMDPs) presents additional challenges. The introduction of constraint functions com- plicates the optimization process as one needs to consider the worst value function both for the objective and the constraint.
RCMDP: Unlike non-robust CMDPs, there is limited research available on robust environments.
In [7). it was shown that the optimization function for RCMDPs is not convex, making it difficult to solve the Lagrangian formulation, unlike in standard CMDPs. Some studies have attempted to address this challenge using primal-dual approach [44] 7 without any iteration complexity guarantee. [45) proposed primal-dual approach to solve RCMDP under the strong duality by restricting to the categorical randomized policy class. However, they did not provide any iteration complexity guarantee. As we discussed,
[ reformulates the Lagrangian problem into an epigraph representation, addressing the limitations of previous methods while providing valuable theoretical insights. However, this method requires a binary search, significantly increasing computational complexity. Moreover, the binary search approach fails when the estimated robust policy value function is noisy (9)
2 Problem Formulation
CMDP:
We denote a MDP as M (S, 7) where A,A.P. : S
denote state space, action space, and probability transition function respectively. 7 E (0,1) denotes the discount factor and c S A IR, for 10, I..., K}. denotes the constraint function. Let R4 max (0, R) for any real number R and π S + A denote a policy. Let 3 S + A(S) denote the initial state distribution where A(S) denotes the probability distribution taken over space S. Let vP(:((s)) : S + R, s.t. E f0..... .O. (where co E C denote the cost for the objective) denote the value function obtained by following policy æ and the transition model P where
y P (s) C
Ep
1- 1 (als))
(4)
'The system specifications are, Processor: (OO GHz, Installed RAM 32.0 GB (31.7 GB usable).664bbl operating system, x64-based processor No GPU.
3

---

where (s, a) denotes the single step 'i" t'th-cost/reward for being at a state 's' and taking action "a" at the 't'-th instant. Without loss of generality, we assume S c((s, a) S 1 s.t. E {O..... K]. This is in consistent with the existing literature [8] We also denote J = (p. ViP.) for i E {0. K} where p is the initial state-distriuution. For notational simplicity, we denote H = 1/(1 - 7) as the maximum cost value.
The MDP M forms a constrained MDP when constraint cost functions are bounded by a threshold, leading to the following optimization problem,
(5) Note that even though we consider a cost-based environment to be consistent with the RCMDP literature (8] where the objective is to minimize the expected cumulative cost, our analysis can casily go through for reward-basee environment where the objective is to maximize the expected cumulative reward. Further, we can also consider the constraints of the form JT. 2 6;.
CMDP objective: min Ja.PP s.t. J Vi E (I.....K]. K}.
We consider that we have access to the nominal model Po. however, the true model might be different compared to the nominal model Po- Such a scenario is relevant when we train using simulator, however, the real environment might be different compared to the simulator. The state- of-the art choice for the uncertainty set is to collect all the probability distribution which are in close proximity to a nominal model Po E (S A). Thus IP-
RCMDP:
X (s.a)ESxA (s.aa such that
P(9.a) = { P (SS) : D(P, Po(s, S p).
(6)
where D(.,-) is the distance measure between two probability distribution and denotes the max- imum perturbation possible from the nominal model. Some poplar choices for D(...) are TV dis- tance, x² distance and KL-divergence [32]
Equation (6) satisfies the (s, rrctaaannnny assumption. It is important to note that our analy- sis and algorithm remain applicable as long as a robust policy evaluator, that is, max J5. is available. Therefore, we can also extend our approach to consider s-rectangular uncertainty sets. In addition, it is possible to extend this to the integral probability metric (IPM). However, without such an assumption, evaluating robust value function becomes an NP-hard problem.
The objective in constrained robust MDPs is to minimize (or maximize in a reward based setting) the worst case value function while keeping the worst case expected cost function within a thresh- old (user defined) as defined in (1. We denote maxp J.P.x = Je, as the worst possible expected cumulative cost corresponding to cost e; following the policy x.
Learning Metric: Since we do not know the model, we are in the data-driven learning setting.
Here, interested in finding the number of iterations (T) required to obtain a policy á with sub-optimality gap of at most and a feasible policy incurring no violations. That is, after T iterations, á satisfies
Gap(#) J J S and Violation (+) max b S.
n
where x' is the optimal policy of IT. Note that we do not assume any restriction on the policy class unlike in [8. In 45). the policy class increases as T increases as it is an ensemble of the learned policies up to time T. Here, II denotes any Markovian policy.
Thus, the iteration complexity measures how many iterations required obtain feasible policy with sub-optimality gap of at most 6. Iteration complexity is a standard measure for unconstrained robust MDP (38). In addition sub-optimality gap, also seek to achieve feasible policy A for RCMDP. Note that unlike in (8), where they allowed a violation of e, here, we want to find a feasible policy, stricter requirement.
Difficulty with the vanilla primal-dual method The most celebrated method to solve a constrained optimization problem is by introducing Lagrangian multiplers. Let consider À (Ai... ....A)) RN be the set of langrangian multipliers introduced to convert the primal problem eqn. I into the
dual space which is shown in eqn. 8
N A, JT.P PEF
min max max. J.
+
- bb).
(8)
#ElleER Pes 6o
111
In the CMDP problem, 446 shows that the strong duality holds when there exists a strictly feasible policy (aka Slater's condition). However, concurrent work [47] highlighted that strong duality

---

does not hold for the RCMDP problem as the occupancy measure is no longer convex as the worst transition model differs for different policies. addition to that, in 8 a strong ambiguity regarding the tractability in solving lagrangian problem is discussed. Further, even if one fixes X, one cannot apply robust value iteration approach to find the optimal policy for the Lagrangian unlike the CMDP. Hence, it is evident to look for alternative measures to find solution to the optimality problem.
3 Policy Gradient Approach for RCMDPs
In this section, we discuss our approach to solve the RCMDP problem (eqn. In what follows, we describe our policy optimization algorithm RNPG in detail.
3.1 Our Proposed Approach
In order to address the challenges of the primal-dual problem, We consider the following problem min max /A, max - bn]].-
Intuition: Note that when J S b, for all L,..., K, the second term in the objective becomes negative, and since 2 2 0, the optimization will focus on minimizing Jž, as the policy is likely to be feasible with respect to all constraints. Conversely, if there exists any i such that J > bi, then for sufficiently large X, the term J /A becomes smaller than J - b; causing the optimization to prioritize reducing the most violated constraint J
Even though we can not claim that 9 and ① are the same, we can claim that the optimal solution of 9 can only violate the constraint by at most e-amount by suitable choice of X. Hence, minimizing amounts to searching for policies that can violate at most amount. Thus, the optimal policy of can be an optimal of ( In particular, optimal policy of (9) indeed has a smaller cost compared to that of (T. We formalize this as the following result.
Proposition 1. Suppose that xt is the optimal policy of then co S J and can only violate the constraint by at most e with = 2/1/..
The key distinction from the epigraph- approach proposed in 8 is that we avoid tuning the hyperparameter by via binary search. This significantly reduces computational overhead, as also demonstrated in our empirical evaluations. Furthermore, tuning by typically requires accurate esti- mation, even an unbiased estimation would not work, which is prohibitive the state space--pcee grows estimate becomes challenging.
when a
Since our goal is to obtain feasible policy, we assume that the optimal policy is strictly feasible.
Assumption 1. We assume that max, J b, S -E. for some & 0.
The above assumption is required because we want to have feasible policy rather bounding the violation gap to e. Note that we only need to know (or, estimate) the value of ş. Of course, we do show that we achieve feasible policy
not need to know the optimal policy x². Using &, with at most c-gap in Theorem 4.1 Intuitively, if g > c, means that by choosing X = 2H/S. actually guarantee feasibility according to Proposition [ We relax this g-dependency in Theorem I. where we show that we can achieve a policy with at most e-gap and c-violation.
We consider the problem
min max max J - b, E..
(10)
Note that even though for theoretical analysis to achieve a feasible policy we assume the knowledge of E; for our empirical evaluations, we did not assume that and yet we achieved feasible policy with good reward exceeding the state-of-the-art performance. Hence, we modify the policy space to be Ç-dependent.
3.2 Policy Optimization Algorithm
We now describe our proposed robust natural policy gradient (RNPG) approach inspired from the unconstrained natural policy gradient [48). For notational simplicity, we define (T( J - b, +
for i = 1...,, K, and JO( = J / /x. The policy update is then given by-
j {J
Te-1 E arg min ( (ote,, nT) (L(T)()) rell
where arg max
-b + []
a
5

---

where KL is the usual Kullback-Leibe divergence. Note that this is a convex optimization problem, and can be optimized efficiently. If we use, &2 regularization. i.e., || TT. 1 then it becomes a robust projected policy gradient (RPPG) adapted from the unconstrained version (see Appendix D 49 38
a variant of which used in g to find optimal policy for each by- Of course, our approach also Empirically, we observe that KI.-divergence has a better performance, and provide iteration complexity for RNPG.
works for & norm which we define in Algorithm |
The complete procedure is described in Algorithm I First, we evaluate J and Va Jay using the robust policy evaluator which we describe the following.
Our algorithm assumes access to a robust policy evaluation oracle that returns the worst-case performance of a given policy, i... J maxper J This assumption is
Robust Policy Evaluator:
standard and is also adopted in both constrained S and unconstrained (38 robust MDP frameworks.
As we discussed, several efficient techniques exist for evaluating robust policies under various uncer- tainty models especially with (s, a) rectangular assumption 6 this work, we focus on the widely studied and expressive LL-divergenne-basee uncertainty set, which not only captures an infinite family of plausible transition models but also admits a closed-form robust evaluation method.
The robust value function under the KL-uncertainty set is formalized in Lemma D.1 (see Ap- pendix D). The advantage is that we obtain a closed form expression for the robust value function, and we can evaluate it by drawing samples from the nominal model only. For further background on KI. and other uncertainty sets, we refer the reader
50
Our framework is not limited to KL-ddieeggecc. Efficient robust value function evaluation tech- niques exist for other popular uncertainty models such as Total Variation (TV), Wasserstein, and x x"-divergence sets 32 51 52 33 These approaches typically leverage dual formulations to effi- ciently solve the inner maximization problem required for robust evaluation. We need our robust pol- icy evaluator to be only e-accurate. For many uncertainty sets including popular (s, a) -rectanguula perturbation (e.g., KL-divergence, TV-distance, x² uncertainty sets) this requires O(1/c²) samples
32 34. Hence, we need Te samples in those cases.
Policy Update: In order evaluate V T.. we use the following result directly adapted to setting from [8
Lemma 3.1. For any E II. transition kernel P S A A(S), for 1.... (VJL,((T)(ssa)) = d7 (7(s)07 where QT,p(s, a) Qu, and Qo r/
Consider is = arg max /x, (Ja: b, + 5)KK and pt = arg max Je, we can evaluate Je using the robust evaluator for QT (:.)) mentioned.
Hence, the natural policy update at iteration can be decomposed as multiple independent Mirror Descent updates across the states-
T1+,s = arg min (Q.. n.) ) + ( Vs.
(1I)
AA
Again, this is efficient since it is convex. We use direct parameterization and maf parameteriza- tion for the policy update (Appendix by solving the optimization problem (T.. The Algorithm outputs πミ corresponding to the minimum objective over T iterations. We characterize T, the itera- tion complexity in the next section.
Although Algorithm 0 incllude& & for theoretical analysis, we do not assume knowledge of & in our empirical evaluations. Section we discuss how we achieve a slightly weaker iteration complex- ity result without assuming the knowledge &.
4 Theoretical Results
In this section, we will discuss the results obtained for our RNPG algorithm (Algorithm T]. Before describing, the main results, we state the Assumptions. Assumption 2. There exists B E (0, 1) such that ryp(s"ls a) S (sp(s'|s, (s a) Vs', 8, and p E P.
This was a common assumption for unconstrained RMDP as well 53 Assumption 2 states that if the perturbed distribution assigns positive probability to event, the nominal model should also

---

Algorithm RRobust-Nttrrl Policy Gradient for constrained MDP (RNPG)
Input: a,A,T, V(.) (Robust Policy Evaluator, see Algorithm 2
Initialize: To = 1/|A|-
for 1. O...T- do
6 V.J 4. V(c, p) where i = [K,
Update TT+11 according to (II
end for Output policy arg min r max JTg max; b. + +
assign positive probability to that event. Otherwise. a mismatch in supports could lead unsampled regions and render fiiiteiteration bounds intractable. More importantly. Algorithm does not need to know We also did not enforce in our empirical studies. The algorithm still performed well, suggesting that the practical impact may be less restrictive than the theory implies. Also, EPIRC- PGS [8] assumed that the ratio between the state-action occupancy measures on the states covered by all policies and the initial state distribution is bounded.
We also consider a slightly stronger optimal policy for the surrogate problem.
Assumption 3. We consider #* uniform minimizer across all states of the surrogate problem in i.e., f* is a solution of min, max (Vs ( (s)/X, max,, maxp V=.P bba) for all s.
similar assumption is also considered for the unconstrained problem
1-7
Theorem 4.1. Under Assumptions
/ and 3 with À = 2H/ min 1}. 04 =0
after
VTS
log([ iterations, Algorithm returns policy â such that = 26 21 100-))---0 21 - 5) S
J J < 6, and max, - 6n, S 0.
Thus, Algorithm 1 has iteration complexity of O(E-2). Also, the policy is feasible and only at most e-sub optimal. Our result improves upon the result O(e-t) achieved in g Further, they did not guarantee feasibility of the policy (rather, only e-violation). More importantly, we do not need to employ a binary search algorithm. Thus, our algorithm is computationally more efficient. Our significantly better compared to [8] as well. Note that for the unconstrained case the iteration complexity is O(E [48]; whether we can achieve such a result for robust CMDP has been left for the future.
dependence on S, A. and (1 7)-
As we mentioned, we do not use this & for our empirical evaluations. Yet our results indicate that we can achieve feasible policy with better performance compared to EPIRC-PGS in significantly smaller time. In Section [ we also obtain the result when we relax Assumption | with slightly worse iteration complexity by simply putting & = 0, and x= =2H/e.
4.1 Proof Outline
The proof will be divided in two parts. First, we bound the iteration complexity for e-sub optimal solution of (TO). Subsequently, we show that the sub-optimality gap and violation gap using the above result.
Bounding the Iteration complexity for (00): The following result is the key to achieve the iteration complexity result of Algorithm [or the Problem (T0)
Lemma 4.2. The policy â returned by Algorithm satisfies the following property:
max(J², / max J
bn max 1 />, max bn) se/
(12)
for any policy π after O -2 7) -)- iterations under Assumptions and
Hence, the above result entails that Algorithm 4 returns policy which is at most c-suboptimal for the problem [0) after O(e 2(--2)-2). We show that using this result we bound the sub- optimalltyy and the violation gap.
Technical Challenge: The main challenge compared to the policy optimization baassatttio---eddd approaches for unconstrained RMDP is that here the objective (cf.(9)) ) is point-wise maximum of multiple value
7

---

functions for particular policy. Hence, one might be optimizing different objectives at different it- erations iy is varying across the iterations. Hence, unlike the unconstrained case. we cannot apply the robust robust performance difference Lemma as the value-function index might be different for Tt. and I.+1. Instead, we bound it using Assumption Holder's, and Pinsker's inequality.
Bounding the Sub-optimality Gap: By Assumption
J bn -.. Hence, max, J bn +
J= 0b
/ as J 2 0. Thus,
(J% )/A
I max max J - - max / max - bn s
(13)
where the last inequality follows from Lemma 4.2 By multiplying both the sides by X, we have the result.
Bounding the Violation: We now bound the violations.
max bn E) max(J bn () J 1A+H//
- max max bn} - max{ max J bn + + H/A
S + c/X
(14)
where for the first inequality, we use the fact that J /> S H/A. For the seenond inequality, we use the fact that J I bn E. Hence, max, J bn + { < J /A. Since À 2 2// thus, H/İ < 2/2. Note that e/\ = (m2) - <t/ (2H) s E/2. Hence, the above shows that max, (J b,)) S O.
Experimental Results
environments: ()) Garnet, and (ii) Constrained Riverswim (CRS). Additional experimental results are provided Appendix
We evaluate algorithm
We have fixed À 50 across the environments. This demonstrates that with the inclusion of KL regularization term over policy updates, RNPG eliminates the need for manual tuning of A. A sufficiently large fixed value (A 50) yields consistently strong performance. For detailed description of the hyperparameters used, please refer to Appendix E
The Garnet environment is a well-known RL benchmark that consists of nS states and nA actions, described in [55]. For our experiments, we consider G(15, 20) with 15 states and 20 ac- tions. The nominal probability function, reward function, and utility function are each sampled from separate normal distributions: ([a,, Ta), N σb), and N ((Je; where the means paa Hbb and Me are drawn from uniform distribution Uni (0, 100). To ensure valid probability distributions, this environment, we seek to
Garnet:
the nominal probabilities are exponentiated and then normalized. maximize the reward while ensuring that the constraint is above a threshold.
Objective function
Constraint function
Cumulative Objective reward
200
Cumulativve constraint cost
120
150
100
RNPG
RPPG
60
EPIRC
RNPG
40-
baseline
RPPG
20-
Safe region
EPIRC
Unsafe Region
0
200
400
600
800
1000
200
400
600
800
1000
Iteration
Iteration
Figure 1: Comparison of RNPG, RPPG and EPIRC-PGS on Gamet( 15,20) environment. Here, we want to maximize the objective (vf), and want the constraint (ef) to be above the baseline.
Constrained River-swim (CRS): The River-Swim environment consists of six states, each repre- senting an island water body. The swimmer begins at any island and aims reach either end
"The complete implementation is available

---

of the river to eam a reward. At each state, the swimmer has two possible actions: swim left (av) or swim right (a1). Rewards are only provided at the boundary states, while intermediate states do not offer any rewards. The leftmost state, Sg, and the rightmost state, 85, correspond to the riverbanks. As the swimmer moves from 80 85, the water depth increases, and dangerous whirlpools become more prevalent. This progression is captured by safety constraint cost, which varies across states. The safety cost is lowest at 5o and reaches its maximum at S5, reflecting the increasing risk as the swimmer ventures further downstream. Here the goal is to maximize the cumulative reward while ensuring the cumulative cost is below a threshold.
Objective function
Constraint function
Cumulative Objective reward
Cumulaatie constraint cost
50
120
45-
100
40-
RNPG
60-
EPIRC
40
RNPG
baseline
RPPG EPIRC
25
Unsafe region
Safe Region
20
6
200
400
600
800
1000
6
200
400
600
800
1000
Iteration
Iteration
Comparison of RPPG and EPIRC-PGS CRS environment. Here want to maximize the objective (vf) while constraint (ef) being below the threshold line.
Figure 2:
5.1 Analysis results
Does RNPG perform betler than EPIRC-PGS?
Performance: Our experimental results demonstrate that RNPG consistently outperforms EPIRC- PGS, in both environments. In fact, for the CRS environment (Figure RNPG is the only that produces feasible policy. EPIRC-PGS is unable to produce feasible policy there. In the Garnet environment (Figure I) RNPG finds feasible policy while achieving a better reward compared to the EPIRC-PGS. ATso, RNPG shows a better convergence property and is more stable because of the KI. regularization.
Computational Time: RNPG exhibits significant improvements in computational efficiency, achieving convergence at least 4x faster than EPIRC-PGS for 0.9, and 6x faster for 0.995 in the CRS setting (Table T]. In the Garnet environment, RNPG achieves 3x speedup over EPIRC-PGS for y 0.9, and least 5x speedup for 0.995 (Table [ The difference in runtime can be attributed to the fact that RNPG climinates the need for binary search for each by value in (2) as descrihed above, and it uses KI. regulerigzaaaee arization..
To summarize, RNPG performs better compared to EPIRC-PGS terms achieving a better reward while maintaining feasibility across the environments. Moreover, the convergence is stable across the environments, and reduces the computational time significantly compared to EPIRC- PGS theoretical result suggested.
KL regularization compared &a regularization. We also compare RNPG with RPPG (see DD. a projected robust gradient descent variant that &g regularizer instead of KL for policy update in [1]. In the CRS environment, RPPG performs slightly better than EPIRC-PGS by maintaining smaller constraint violations, though it still occasionally breaches the safety threshold. In the Garnet environment, RPPG achieves better performance compared to EPIRC-PGS while maintaining feasibility, however, achieves a smaller reward compared to RNPG. RNPG also much stable, showing that KL regularization is more effective compared to f2 regularization. We observe that RPPG (and, similar to RNPG) also has smaller computational time compared to EPIRC-PGS, which demonstrates that removing the binary search is the key, as EPIRC-PGS also uses & regularization for policy update.
Does À require extensive tuning for RNPG?
particularly notable observation from our experiments is that RNPG performs robustly across different environments using fixed value of X = 50. This highlights that RNPG does not need to set different values for different environments as theoretical result suggested. Rather, one high X-value is enough to achieves feasibility while achieving good reward.

---

6 Discussions and Limitation
Relaxing Assumption I We achieve our results in Theorem 4.1 where we assume that the optimal policy is strictly feasible and the feasibility parameter & is known. We will relax both the features of the assumption that & is known, and the optimal policy is strictly feasible in the following with a slightly worse iteration complexity while ensuring that the policy has violation of at most e, the same metric achieved by EPIRC-PGS (..
Theorem 6.1. Algorithm 7 gives a policy ā such that J - S e and max, J - bn S after O *(1 7) (1 3) log(lA[)) number of iterations when we plug X 2H/ and {
Note that since we are not assuming strict feasibility of the optimal policy, we can only bound the violation up to e. The key here to use À = 2 as we do not know ç. and then obtain an e>-close result using Lemma 4.2 This makes the iteration complexity of O(e ((c-)). Note that our dependence on S. A. and 1/(1 7) are significantly better compared to EPIRC-PGS(S) Further, we do not employ binary search. The proof is in Appendix C
6.1 Extending to Function Approximation: Robust Constrained Actor-Critic (RCAC)
We extend our framework to the function approximation setting motivated by the work of [54] for unconstrained Robust MDP problem. In particular, we consider the integral probability metric (IPM) as uncertainty set, dz(p; g) sup f q" f) where F S RlST. Many metrics such as Kantorovich metric, total variation, etc., are special cases of IPM under different function classes
[56]. We then consider the IPM-based uncertainty set, Pa.a {gld>(q, P%..) S p} around the nominal model.
Consider the linear function approximation setting where V Vwg, where V E Rll is feature matrix of b² (s) Vs as each row. We now consider the following function class F {s + (. R ||5l|2 1). Now, we can apply the Proposition 1 in [57] to achieve the worst case where normalize to let the first coordinate of (ss) = Hence, we can the following equation to compute the robust Bellman operator
",w + pl ||| 2.2/22 2.al,,, value function. In particular, we have suPpedz(axPt..) x² V G.ar = (v%.a V2,
I.p w,: = (s a) VV., + p/lee,2.d12.
(15)
with the next state s' is drawn from the nominal model. Guided by the last regularization term of the empirical robust Bellman operator in (15), when considering value function approximation by neural networks we add a similar regularization term for all the neural network parameters except for the bias parameter in the last layer. We use the expression in (15) for the robust value function for the gradient, and Je, in Algorithm estimate the Q-function we first use (15) by plugging the V-approximation, and then we use the linear regression to fit the critic for the robust Q-function. The details can be found in Appendix G
We need to estimate the robust Q function. In order to
From the empirical results in Figuregand Table 12 it is evident that our proposed approach outper- forms the state-of of- the-art approaches. More importantly, compared to the EPIRC-PGS (adapted to the function approximation setting), our approach achieves significantly better performance with small wall-clock time. Also, our proposed approach outperforms the robust version of the CRPO al- gorithm [1] 47 and achieves feasibility unlike robust CRPO. In Appendix we showed that robust CRPO may not achieve a finite time iteration complexity guarantee even for finite-state space.
Conclusions and Future Works
In this work, we present a novel algorithm that leverages the projected policy gradient and natural policy gradient techniques to find an e-suboptimal and feasible policy after O(E-2) iterations for RCMDP problem. We demonstrate the practical applicability of our algorithm by testing it on sev- eral standard reinforcement learning benchmarks. The empirical results highlight the effectiveness of RNPG, particularly in terms of reduced computation time and achieving feasibility and better reward compared to other state-of-the-ar algorithms for RCMDP.
Relaxing Assumption 2 and 3 constitute an important future research direction. Achieving a lower bound or improving the iteration complexity is also an important future research direction. Charac- terizing the results for other uncertainty sets also constitutes an important future research direction. Iteration complexity guarantee for the function approximation setting has been left for the future.
10

---

Acknowledgments
AG and SG acknowledge NJIT Startup Fund indexed 172884. SG acknowledges Neurips 2025 for awarding him with the NeurIPS 2025 Scholar Award. AW and KP acknowledge NSF grants CCF- 2326609, CNS-2146814, CPS-2136197, CNS-2106403, and NGSDI-210566 Resnick Sustainability Institute. KP also acknowledges support from the 'PIMCO Postdoctoral Fel- low in Data Science" fellowship the California Institute of Technology and the Resnick Institute.
and support from the
References
[1] Ran Emuna, Avinoam Borowsky, and Armin Biess. Deep reinforcement learning for human-like driving policies in collision avoidance tasks of self-driving cars. arXiv preprint 2xXiv:006.042//6 2020.
[2] Eitan Altman. Constrained markov decision processes with total cost criteria: Lagrangian approach and dual linear program. Mathematical methods of operations research, 48:387-
417, 1998.
[3] Shuang Qiu, Xiaohan Wei, Zhuoran Yang, Jieping Ye, and Zhaoran Wang. Upper confidence primal-dual optimization: Stochastically constrained markov decision processes with adver- sarial losses and unknown transitions. arXiv preprint arXiv:2003. 006600 2020.
[4] Sindhu Padakandla, KJ Prabuchandran, Sourav Ganguly, and Shalabh Bhatnagar. Data efficient safe reinforcement learning. In 2022 IEEE International Conference on Systems, Man, and Cybernetics (SMC), pages 1167-1172. IEEE, 2022.
[5] Sharan Vaswani, Lin F Yang, and Csaba Szepesvári. Near-optimal sample complexity bounds for constrained mdps. arXiv preprint arXiv:2206.0622 2022.
[6] Arnob Ghosh, Xingyu Zhou, and Ness Shroff. Provably efficient model-free constrained rl with linear function approximation. Advances in Neural Information Processing Systems, 35: 13303-13315, 2022.
[7] Yue Wang, Fei Miao, and Shaofeng Zou, Robust constrained reinforcement learning. arXiv preprint 22Xv:2209.006666 2022.
[8] Toshinori Kitamura, Tadashi Kozuno, Wataru Kumagai, Kenta Hoshino, Yohei Hosoe, Kazumi Kasaura, Masashi Hamaya, Paavo Parmas, and Yutaka Matsuo. Near-optimal policy identifi- cation in robust constrained markov decision processes via epigraph form. arXiv preprint a40iv:2408. /6286, 2024.
[9] Michael Horstein. Sequential transmission using noiseless feedback. IEEE Transactions Information Theory, 933) 1963.
[10] Jiashuo Jiang and Yinyu Ye. Achieving o(L/e) sample complexity for constrained markov decision process. arXiv preprint 2xXiv:2402.16324, 2024.
[11] Tengyu Xu, Yingbin Liang, and Guanghui Lan. Crpo: A new approach for safe reinforcement learning with convergence guarantee. In International Conference on Machine Learning, pages 11480-1149 PMLR, 2021.
[12] Santiago Paternain, Miguel Calvo-Fullana, Luiz FO Chamon, and Alejandro Ribeiro. Safe policies for reinforcement learning via primal-dual methods. IEEE Transactions on Automatic Control, 68(3):1321-1336, 2022.
[13] Adam Stooke, Joshua Achiam, and Pieter Abbeel. Responsive safety in reinforcement learning by pid lagrangian methods. In International Conference on Machine Learning, pages 9133- 9143. PMLR, 2020.
[14] Qingkai Liang, Fanyu Que, and Eytan Modiano. Accelerated primal-dual policy optimization for safe reinforcement learning. arXiv preprint 1802. 0008000000000,.. 2018.
[15] Chen Tessler, Daniel Mankowitz, and Shie Mannor. Reward constrained policy optimization. arXiv preprint arXiv:/805, 1074, 2018.

---

[16] Ming Yu, Zhuoran Yang, Mladen Kolar, and Zhaoran Wang. Convergent policy optimization for safe reinforcement learning. Advances in Neural Information Processing Systems, 32, 2019.
[17] Liyun Zheng and Lillian Ratliff. Constrained upper confidence reinforcement learning. In Learning for Dynamics and Control, pages 620-629. PMLR, 2020.
[18] Yonathan Efroni, Shie Mannor, and Matteo Pirotta. Exploration-exploitttion in constrained mdps. arXiv preprint arXiv:2003.02189, 2020.
[19] Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal regret bounds for reinforcement learning. Advances in neural information processing systems, 21, 2008.
[20] Dongsheng Ding, Kaiqing Zhang, Tamer Basar, and Mihailo R Jovanovic. Natural policy gradient primal-dual method for constrained markov decision processes. In NeurIPS, 2020.
[21] Tianjiao Li, Ziwei Guan, Shaofeng Zou, Tengyu Xu, Yingbin Liang, and Guanghui Lan. Faster algorithm and sharper analysis for constrained markov decision process. Operations Research Letters, 54:107107, 10700077,4000 2024.
[22] Tao Liu, Ruida Zhou, Dileep Kalathil, Kumar, and Chao Tian. Policy optimization for constrained mdps with provable fast global convergence. arXiv preprint arXiv:2111.00552, 2021.
[23] Donghao Ying, Yuhao Ding, and Javad Lavaei. A dual approach to constrained markov de- cision processes with entropy regularization. International Conference on Artificial Intelli- gence and Statistics, pages 1887-1909. PMLRR, 2022.
[24] Honghao Wei, Xin Liu, and Lei Ying. Triple-q: A model-free algorithm for constrained rein- forcement learning with sublinear regret and zero constraint violation. In International Con- ference on Artificial Intelligence and Statistics, pages 3274-3307. PMLR, 2022.
[25] Arnob Ghosh, Xingyu Zhou, and Ness Shroff. Achieving sub-linear regret in infinite horizon average reward constrained mdp with linear funetion approximation. In The Eleventh Interna- tional Conference on Learning Representations, 2022.
[26] Arnob Ghosh, Xingyu Zhou, and Ness Shroff. Towards achieving sub-linear regret and hard constraint violation in model-free In International Conference on Artificial Intelligence and Statistics, pages 1054-1062. PMLR, 2024.
[27] Joshua Achiam, David Held, Aviv Tamar, and Pieter Abbeel. Constrained policy optimization. In International conference on machine learning, pages 22-31. PMLR, 2017.
(28) Yinlam Chow, Ofir Nachum, Edgar Duenez-Guzman, and Mohammad Ghavamzadeh. A lyapunov-based approach to safe reinforcement learning. Advances in neural information pro- cessing systems, 31, 2018
[29] Gal Dalal, Krishnamurthy Dvijotham, Matej Vecerik, Todd Hester, Cosmin Paduraru, and Yu- val Tassa. Safe exploration in continuous action spaces. arXiv preprint wrXiv:1801.0875: 2018.
[30] Tsung-Yer Yen Yang, Justinian Rosca, Karthik Narasimhan, and Peter J Ramadge. Projection- based constrained policy optimization. arXiv preprint arX:v:2010.03152, 2020.
[31] Garud N Iyengar. Robust dynamic programming. Mathematics of Operations Research, 30(2): 257-280, 2005.
[32] Kishan Panaganti and Dileep Kalathil. Sample complexity of robust reinforcement learning with generative model. In International Conference Artificial Intelligence and Statistics, pages 1582-9602. PMLR, 2022.
[33] Wenhao Yang, Liangyu Zhang, and Zhihua Zhang. Toward theoretical understandings of robust markov decision processes: Sample complexity and asymptotics. The Annals of Statistics, 50 (6):323332488, 2022.
12

---

[34] Laixi Shi, Gen Li, Yuting Wei, Yuxin Chen, Matthieu Geist, and Yuejie Chi. The curious price of distributional robustmess in reinforcement learning with generative model. Advances in Neural Information Processing Systems, 36.79903-79917, 2023.
[35] Pierre Clavier, Erwan Le Pennec, and Matthieu Geist. Towards minimax optimality of model- based robust reinforcement learning. arXiv preprint www.ii::332.033222 2023.
[36] Zhengqing Zhou, Zhengyuan Zhou, Qinxun Bai, Linhai Qiu, Jose Blanchet, and Peter Glynn. Finite Finite-sample regret bound for distributionally robust offline tabular reinforcement learning- In International Conference on Artificial Intelligence and Statistics, pages 3331-3339. PMLR,
2021.
[37] Shengbo Wang, Nian Si, Jose Blanchet, and Zhengyuan Zhou. A finite sample complexity bound for distributionally robust q-learning. In International Conference on Artificial Intelli- gence and Statistics, pages 3370-3398. PMLR, 2023.
[38] Qiuhao Wang, Chin Pang Ho, and Marek Petrik. Policy gradient in robust mdps with global convergence guarantee. In International Conference on Machine Learning, pages 35763- 35797. PMLR, 2023.
[39] Yue Wang and Shaofeng Zou. Online robust reinforcement learning with model uncertainty. Advances in Neural Information Processing Systems, 34:7193-7206 2021.
[40] Yue Wang, Alvaro Velasquez, George K Atia, Ashley Prater-Bennette, and Shaofeng Zou. Model-free robust average-reward reinforcement learning. In International Conference on Machine Learning, pages 36431-36469, PMLR, 2023.
[41] Yue Wang, Jinjum Xiong, and Shaofeng Zou. Achieving minimax optimal sample complexity of offline reinforcement learning: A dro-based approach. 2023.
[42] Zhipeng Liang, Xiaoteng Ma, Jose Blanchet, Jiheng Zhang, and Zhengyuan Zhou. Single- trajectory distributionally robust reinforcement learning. arXiv preprint 1rXiv:230..17711, 2023.
[43] Zijian Liu, Qinxun Bai, Jose Blanchet, Perry Dong, Wei Xu, Zhengqing Zhou, and Zhengyuan Zhou, Distributionally robust q-learning. International Conference on Machine Learning, pages 13623-13643. PMLR, 2022.
[44] Daniel J Mankowitz. Dan A Calian, Rae Jeong, Cosmin Paduraru, Nicolas Heess, Sumanth Dathathri, Martin Riedmiller, and Timothy Mann. Robust constrained reinforcement learning for continuous control with model misspecification. arXiv preprint arXiv:2010. 10644, 2020.
[45] Zhengfei Zhang, Kishan Panaganti, Laixi Shi, Yanan Sui, Adam Wierman, and Yisong Yue. Distributionally robust constrained reinforcement learning under strong duality. In Reinforce- ment Learning Conference.
[46] Santiago Paternain, Luiz Chamon, Miguel Calvo-Fullana, and Alejandro Ribeiro. Constrained reinforcement learning has zero duality gap. Advances in Neural Information Processing Sys- tems, 32, 2019.
[47] Shaocong Ma, Ziyi Chen, Yi Zhou, and Heng Huang. Rectified robust policy optimization for model-uncertain constrained reinforcement learning without strong duality. arXiv preprint arXiv:2508. 17448, 2025.
[48] Qiuhao Wang. Shaohang Xu, Chin Pang Ho, and Marek Petrik. Policy gradient for robust markov decision processes. arXiv preprint arXiv:2410.2211 14, 2024.
[49] Lior Shani, Yonathan Efroni, and Shie Mannor. Adaptive trust region policy optimization: Global convergence and faster rates for regularized mdps. In Proceedings of the AAAI Confer- ence on Artificial Intelligence, volume 34, pages 1668-6675,4 2020.
[50] Kishan Panaganti, Zaiyan Xu, Dileep Kalathil, and Mohammad Ghavamzadeh. Robust rein- forcement learning using offline data. Advances in neural information processing systems, 35: 32211-32224, 2022.
13

---

[51] Kishan Panaganti Badrinath and Dileep Kalathil. Robust reinforcement learning using least squares policy iteration with provable performance guarantees. In International Conference on Machine Learning, pages 51 1-520. PMLR, 2021.
[52] Zaiyan Xu, Kishan Panaganti, and Dileep Kalathil. Improved sample complexity bounds for distributionally robust reinforcement learning. International Conference on Artificial Intel- ligence and Statistics, pages 7728-9754 PMLR, 2023.
[53] Aviv Tamar, Shie Mannor, and Huan Xu. Scaling up robust mdps using function approxima- tion. In International conference on machine learning, pages 181-189. PMLR, 2014.
[54] Ruida Zhou, Tao Liu, Min Cheng, Dileep Kalathil, PR Kumar, and Chao Tian. Natural actor- critic for robust reinforcement learning with function approximation. Advances in neural in- formation processing systems, 36:97-133, 2023.
[55] Yudan Wang. Model-free robust reinforcement learning with sample complexity analysis.
Master's thesis, State University of New York at Buffalo, 2024.
[56] Alfred Müller. Integral probability metrics and their generating classes of functions. Advances in applied probability, 29(2):429-444 443, 1997.
[57] Ruida Zhou, Tao Liu, Min Cheng, Dileep Kalathil, PR Kumar, and Chao Tian. Natural actor- critic for robust reinforcement learning with function approximation. Advances in neural in- formation processing systems, 36, 2024.
[58] Wenhao Yang, Han Wang, Tadashi Kozuno, Scott M. Jordan, and Zhihua Zhang. Robust markov decision processes without model estimation, 2023. BRLhhttss://arxt org/ars/ abs/
2302. 01248
[59] Mark Towers, Ariel Kwiatkowski, Jordan Terry, John U. Balis, Gianluca De Cola, Tristan Deleu, Manuel Goulão, Andreas Kallinteris, Markus Krimmel, Arjun KG, Rodrigo Perez- Vicente, Andrea Pierré, Sander Schulhoff, Jun Jet Tai, Hannah Tan, and Omar G. Younis. Gymnasium: A standard interface for reinforcement learning environments, 2024. URL
hhtpp:://arx: wwwxxivvorgg//ooo abs/ 17032
[60] Yanli Liu, Kaiqing Zhang. Tamer Basar, and Wotao Yin. An improved analysis of (variance-reduced) policy gradient and natural policy gradient methods. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural In- formation Processing Systems, volume 33, pages 7624-7636. Curran Associates, Inc., 2020. URL httpp:: neurips httpppperfillespppee///220 26678890CCc003336676622222244--4
pdf
14

---

Contents
Introduction
1.1
Related Works
2
Problem Formulation
3
Policy Gradient Approach for RCMDPs
3.1
Our Proposed Approach
3.2
Policy Optimization Algorithm
4
Theoretical Results
Proof Outline
5
Experimental Results
5.1
Analysis of results
6
Discussions and Limitation
10
6.1 Extending to Function Approximation: Robust Constrained Actor-Critic (RCAC)
10
7
Conclusions and Future Works
10
Proof of Proposition)
17
Proof of Lemma 4.2
17
B Proof of Lemma B.3
19
Proof of Theorem 6.
D Robust policy evaluator based on KL divergence
19
Experiments
21
Constrained River-swim
22
E.1.1
Environment Description
22
E.1.2
Discussions of the result
23
Garnet problem
24
E.2.1
Environment Description
24
E.2.2
Implementation details
24
E,2.3
Discussion of Results
25
Modified Frozen-lake
26
E.3.1
Environment description
26
13,2
Discussion of results
26
Garbage collection problem
27
E.4.1
Environment description
27
15

---

E.4.2
Discussion of results
28
Implementation Details of RNPG and RPPG
29
RNPG
29
F22
Robust Projected Policy Gradient (RPPG)
30
Extension to Continuous state space (Robust Constrained Actor Critie)
30
Results and discussion
31
Connection with the CRPO
33
16

---

A Proof of Proposition I
Proof. Recall that H² is the solution of (9.. For the first result, we have:
Sig / Soh / max / max bn]} max /A max - bn]}
0
(16)
where we use the fact that n² is feasible in the first inequality. For the second inequality, use the optimality of n for (
We prove the second result using contradiction. Assume that the optimal solution X* of (9 violates the constraint by We then show by contradiction that it cannot be an optimal solution of 9 Since
least one of the constraints violates by E, thus max, [J bn] 2 c. Note that since X 2H/c
therefore J S c/2 as the maximum value of J is H. Thus, we have
max J co A>, max[J b
(17)
Now, consider the optimal solution xO of I feasible thus max, J bnl S 0. Further, - /A S e/2. Hence,
max />, max - bn]} S 5/2 < max / max[Je - bnlb.
(18)
which contradicts the fact that â is optimal for 99. This proves the second result.
B Proof of Lemma 4.2
We use the following results proved in 488 in order to prove Lemma 4.2 Lemma B.1 (448) Lemma 4.1]). Let assume that in arg max JJ: b.). then,
Ole Q TtP a,de 1 - y) + (TT+ Te,s) S Bly, RT.s) - Bly, Te41.s)
(19)
where B is the Bregman's 's divergence.
The above result follows from Bregmen divergence and the policy update. our case, the KL divergence.
Lemma B.2 (48 Lemma A.3I), For any n, n', and we have
( .p) - (e, p) = 1
Σ p (() Et' - ns
(20)
The following result is direct consequence of Assumption g and has been proved in Appendix B.I Lemma B.3. For any
1
(TT +++") < 1-
E s mu [Q TT - -
(21)
where arg max (J b.), and = arg max JR.P.
Now, we ready prove Lemma
Proof. From Lemma B.3
((m)) ((*")
1
Σ dh
3
where Q is the estimated value. Consider that the worst-case evaluator is only en is close that is
IiQ S=...P Il.0 S 6g-
17

---

Hence, we have
((T))- - ((**) 5
1
Σ
dhh
20
(s)
Tr, - F2 (5,aQaaa
+
(22)
3
Applying Lemma B.1
(subtracting and adding (Q%se Te,e). we then have from (2
2 (e) (
1 1 E sru vo (Q0t Me,s me-1,) B(a", m²) 1 B(*", m++1 B(T++1, m)]] 60-
(23)
Now,
1 (T++1,, mt) $ 119... Tull ||co||Te. - #411,011 ||T s411,elf
(Q Thi - T(41,s)
a
2a
-1
2a (ail1
11 ||Te,. x141,=111² 2 + 1T
$ QTTPP e, 10
(24)
where we use the Holder's inequality for the first inequality. For the second inequality, we use the Pinsker's inequality as the KL divergence.
Hence, by summing over t, and using (4) we have from 23
1
Σ ( ((+*)) 2
E
no a 10 1
3
s
1=
+
a(1
3)
E
sndd
[B(# TT) mp)
B(# T+t1]] + Teo
T-1
1
<
as
+
E and B m0) + Ten-
(25)
3)
(1 21-
a(1 - B)
m=0
1
Here, the fact that ||Q 1o:0 I 1-
This is easy discern for i {1, {1..... K}. For
i = 0, we have QTaai bloo I
S m
1-7 as E S Hence, from
(1 ッ}ル
25
1
Σ (b(m)) - ((*')) < TaS (1 (1- a(1 - 3)
+
snad so B(** To) + Tep- (26)
(1 3)
1
(1 (1
Now, replacing m0
[ and
we have
VTS
Σ ( +f**)) <
VS VSTlog((AA)
+ Ten-
(27)
1 3
v11-))
Thus,
V (og()A))
*(+) $(**) < Σ ((T)) ((*))) < (1 B) T(1 7)²
+ Cu.
(28)
max (J max,, [T bn where we use the fact that मे = arg min
Hence, when T 0 (1 7 (1 332
S Slog(1 (log((A))(1/22)) iteration, the above is bounded by e,
6o E/2. The result now follows.
18

---

B.1
Proof of Lemma B.3
Proof. Let arg max b;}, and p = arg max J Now,
( x S J.. max J P
(29)
We now bound the right-hand side, and assume that p" = arg max _
(p) - * (0) - -²) (o)
+ En'(s'ss (s)
Eanp Ban (V) (3( +7 E Ep(6'lo,a)V
Ex 7 D1' (s(ssss. (s') Ep(s(ss.a
a BBo -o E((d(ss,)) (8) vT(
snup
where the incquality follows from the fact that p arg max E. p¹ (s' (s'). Hence,
(T( V (p)
Σ (9 -#) Bl Σ polsslls, (v)s Va (s))), (30)
where we use the fact that (T( 2 V (5') by Assumption 3 and Assumption expanding we get the result.
By recursively,
C Proof of Theorem 6.1
Proof. Here, we just consider the following objective
min max{ AA, max J bn)
(31)
since we do not know ç. here, we only use max, J bn instead max, Jr. - bn + E. We consider X 2H/c.
Sub-optimality gap: Since n² is feasible, thus, J / max, J bn. Thus,
(J+ )/2
I max Joz X, max J bn} - max(JJr /X, max J bn
< (2H,,
(32)
where the inequality follows from Lemma multiplying both the sides get the results.
4.2 with O(1/e). Now, using À = 2H/e and
Violation Gap: We now bound the violation.
max J bn
n
< max{{Jr /A max bn) max{Je, /X, max Js bn) H/>
22/(2H) + c
(33)
where we use the fact that J /A < H/X e/2. Hence, the result follows.
D Robust policy evaluator based on KL divergence
Robust Policy evaluator: Our algorithm assumes the existence robust policy evaluator oracle that evaluates maxper J for given There many evaluation techniques that are used to
19

---

efficiently evaluate a robust policy perturbed by popular uncertainty measures. In this work, we evaluate our policies using variant EPIRC-PGS algorithm g for KL uncertainty (as shown in Algorithm 2
The general robust DP equation is given by Equation (34
(ROBUST DP):
(s, cn (8,
7max PEP
Σ
D( (6))
(34)
where V On (8') = Σ T(s', a' d' (8,
P 8 (a,al
where ((s,a)= = A(S)KK [P|6(l|s a)] S CKE).
where PP satisfies (s, (..4)-eee rectanguaat assumption and KL[plg] = Eves p(s) In p(s)
for two prob-
di
ability distribution 2.9 E (SS). The KL uncertainty evaluator (see Algorithm justified by Lemma 4 and 5
8
Algorithm 2 KI. Uncertainty Evaluator
Input: policy æ, nominal probability transition function p", perturbation parameter CKL. Cj [co. Ci..... discouuu factory, p. (S), |A|
2: Q, V Robust Q-table(q,,TTp ..CL) (see Algorithm
1l|s,a,.] exp CKL
3: P"(s,a, a,
(s, ESXA
CKL
4: Tis, s'1 Σ (s,,),) (8x
aed
5: V. = (I (I-?T)-1a,
6: J = /" Σ (T(a))) (r(as))Q2 p- (T, (8,
aEd
7: d7. = (1 (1 P
8: vj = Hdp. (8) Q (8,a) v (s,a)
9: Return: J, j.
The KL uncertainty evaluator follows from Lemma D.I Algorithm we need the Robust Q- table. The compact algorithm for that is given in Algorithm 3
Lemma D.1. (Lemma 4 in (311) Let E ISS and 0 <g < A(S). The value of optimization problem
min (p,v) such that KT[plla] < CKL PEA(S)
(35)
equal to
min 00Kl + 0 ((g, exp (- (1)).) 920
(36)
Let 0* be the solution of equation
36
then the solution of
35 becomes,
p qexp (- 2
(37)
Using lemma D.I Equation 34 can be implemented
(1+1l (s, (s, + Σ
(s'
Pi
SES
Vt
where P(r,a) p (1(s, exp
(38)
(ie.))
V1 V2,())
and (T,n)) == arg min 0CKL + +0 In (p"()ss exp
020
20

---

Algorithm Roobutt.Qtabbl
1: Input: c22 k,p, CKL.P
2: Initialize: (s. = 0Vsss a) x A.ss) 0's E S, S.Q (reeo = 0 v(s,a) ex
3: =p(-),
1000, =1
4: while i < T do
5: Q (arev(s,0) (s a(s,a)
6:
T(,ss)
7:
s ((ls,a)
P (s,s,a,) exp
Vil.
8:
KK
V(s.a)
E' exp
V'a'1
CKL
9:
Q[8.a] = G a
(P*
V (T|18), (s,,))
V8 ES
11:
=
12:
if (s, a) = Qpreu(s, a) V(s,a) E S then
13:
Break out of loop
14:
end if
15:
i=i+1
16:
end while
17:
Return: Q, V
While Equation 36 is convex in nature, solving it for all p(l|s, a)v(s, a) E AS) in Equation 38 computationally extensive in practice. Rather than the exact constrained problem, [58 regularized robust DP update.
proposed
(s, a)) yaax PEAS
Σ P(s'VV (5) Ckr (1s.0))
(39)
where CKL 0 is constant. This regularized form be efficiently written as Equation 44
Q(++1) cn(s,a) +
( (5))
E PES
(40)
Ve (+)
where ((a.)) & p exp
CKE
The equivalence can be concluded from the duality since convex optimization problem. The following lemma also shows that the convergence is fast.
Lemma D.2. (Adaptation from Proposition 3.1 and Theorem 3.1
(58)) For any CKL
there
exists CKL. > O such that Equation (39) converges linearly to the fixed point of Equation 38
E Experiments
The environments where we test our algorithms are as given below (Some results are shown in the main paper under Experiments section (Section 5). Before moving the individual environ- ment, we first state the hyper-parameters that are fixed throughout the environments.
Common hyperparameters
The initial state distribution, denoted by p. is generated by sampling from standard normal dis- tribution followed by applying softmax transformation to convert the resulting values into valid probability distribution over states. In particular, for each state, random number is generated from (0 1). Then it normalized using softmax in order to avoid negative values.
The discount factor is set to 0.99 across all algorithms and environments to ensure consistency. However, in order to evaluate computational efficiency (wall-clock time), we run EPIRC_PGS with multiple discount factors: 7 0.9. 0.99, and 0.995.
21

---

EPIRC PGS follows double-loop structure, as described in [ where the outer loop uses the iter- ation index K and the inner loop uses index T. our experiments, we set K 10 and T 100, yielding total of K x T 1000 iterations. This ensures that all algorithms are compared over the same number of update steps.
Both RPPG and RNPG require an initial policy specification. For RPPG, we initialize the policy uni- formly: (a s) 1/|A| for all s S. In contrast, RNPG parameterizes the policy directly using vector 0, where 0 ~ 10, 1) and |0o) = |S| x |A|.
Both algorithms also depend on the hyperparameter A. For RNPG, À is fixed at 50 across all experi- ments. For RPPG, is treated as a variable hyperparameter, with values specified individually in the corresponding experimental sections.
The learning rate a set 10-3 for all algorithms across all environments. Another important hyperparametter is the loop control variable used in Algorithm 3 The operations inside the loop of Algorithm represent robust Bellman update. has been shown in [31] that the soft Bellman operator is contraction mapping. Therefore, setting fixed point Q(s, a), and subsequently to the corresponding value function (s)). In our experiments, we fix 7 1000. For theoretical justification, refer to Lemmas D.I and D.2 D.2
large value ensures convergence to
E.1 Constrained River-swim
The River-swim environment is widely studied benchmark in optimization theory and stochastic control. The detailed explanation of the algorithm as given below.
E.1.1 Environment Description
The environment consists of six distinct states, conceptualized as islands dispersed across a large body of water. At the start of each episode, swimmer is placed one of these landmasses.
The swimmer's objective to navigate toward one of the two terminal islands repredentpnrsnniingg the river's ss endpoints- to receive a reward. At each state, the swimmer can choose between two actions: swimming to the left or the right. Rewards are only provided upon reaching the terminal states, whereas all intermediate states yield zero reward (refer to Table 2
During the transition between states, the swimmer encounters adversarial elements, such as strong water currents and hostile tribal inhabitants residing on certain islands. These hazards are modeled as cost incurred for occupying a given state. The transition probabilities between states compactly represented in Table []]
while the immediate state-wise rewards and constraint costs are summarized in Table 3 Note that the reward is high at the extreme right-hand side as this is the best state, however, it also corresponds to high current or high cost. All the parameters including the value of CKL of the MDP are represented Table
State
Action
Probability for next state
$0
00
so so:0.9, s0.0.1
8i
E (1,
5]
ao
s,0.6,, 8 0.3, 8:41 : 0.1
84s
i E (0, ..... 4}
Q1 8,;0.6, 8: 0.1, 8:41 : 0.3 85:0.9, 84:0.1
85
d1
Table 2: Transition probability of River-swim environment
State
Reward 0.001
Constraint cost
So
0.2
0
0.035
82
O
$3
0.01
0.1
0.08
85
0.9
Table 3: The reward and constraint cost received each state
22

---

Hyperparameters
Value
6
A
Environment Parameters
pd
Table Table
Cp C1
b
42
KL Uncertainity Evaluator
0.99
(Algorithm 2
10-4
O'ile
CKL
0.1
Robust Q table
a
10 10-4
RPPG
10
Table 4: Hyperparameter used for all subroutines for CRS environment
Objective function
Constraint function
Cumulative Objective reward
Cumulative constraint cost
50
120
100
40
80
RNPG
60
35-
RPPG
EPIRC
40
30
RNPG
baseline
20
RPPG
25
Unsafe region
EPIRC
Safe Region
20
200
400
600
800
1000
200
400
600
800
1000
Iteration
Iteration
(a) Expected objective function comparison
(b) Expected cost function comparison
Figure 3: Comparison of RPPG and EPIRC-PGS CRS environment
E.1.2 Discussions of the result
The iteration-wise expected reward (value function) and expected constraint cost are illustrated in Figure From Figure Ba we observe that EPIRC_PGS. (denoted EPIRC) achieves the highest objective reward. However, as shown in Figure 3b it significantly violates the constraint threshold, failing to remain within the designated safe region. Since the agent's goal not only maximize long-term reward but also to ensure safety by satisfying the constraint, EPIRC PGS falls short in this regard.
RPPG achieves a higher value function than RNPG, as seen in Figure 3a However, closer look at Figure 3 reveals that RPPG also marginally violates the constraint boundaries. RNPG effectively captures the trade-off between reward maximization and the constraint satisfaction, navigating as close possible the constraint boundary. stops the point where further increase reward would result in constraint violations, thereby maintaining feasible and safe policy.
Our algorithm relies key hyperparameter, X. This parameter plays crucial role in balancing the objective and constraint terms during policy updates. Specifically, should be chosen to be sufficiently large such that when the constraint violation J - b, is marginal (i.e., J b, >> & for some small 0 and for any E 1,2,.... .... K), the scaled objective term J /> does not dominate the update direction.
If À is set too small, the influence of the objective term becomes large. As result, the algorithm may prioritize minimizing the objective cost (or maximizing the reward, depending on the envi- ronment setting) at the expense of constraint satisfaction. This contradicts our goal of maximizing expected objective return such that the expected constraint values are below certain threshold. To illustrate the impact of À on the performance and feasibility of RNPG, we conduct experiments using different values of with results presented Figure 4 Note that higher value of À indeed reduces the value function, but also decreases the cumulative cost. We set À 50 throughout the
23

---

Effect of lambda(RNPG)
Effect lambd
50-
Expected values vf
Expected values of
105
lambda=10
40-
lambda 30
lambda
lambda=10
1ambda=50
1ambda=30
30
baseline
1ambda=15 15
25
Unsafe region
lambda=50
Safe region
200
400
3050
Iteration
Iteration
Figure 4: Effect of À on RNPG for the CRS environment
experiment for RNPG as it corresponds to feasible solution for each environment. Hence, it shows that for RNPG, we do not need to costly hyper-paramett tuning for À relatively high value of À ensures feasibility as the Theory suggested.
Furthermore, Table 11 presents comparison of wall-clock time across the algorithms. RNPG completes the shortest time, running approximately 1.6x faster than RPPG and at least 4x faster than EPIRC PGS 7 0.9). These results demonstrate that RNPG only achieves competitive performance but also does so with significantly improved computational efficiency compared to both RPPG and EPIRC_PGS.
The results highlight RNPG's ability to consistently learn robust and safe policies while outperform- ing RPPG and EPIRC-PGS in terms both reliability and computational efficiency, even under adverse environmental dynamics.
E.2
Garnet problem
E.2.1
Environment Description
The Garnet environment is standard Markov Decision Process (MDP) framework commonly used to evaluate reinforcement learning (RL) algorithms in a controlled setting. It is characterized by a predefined number of states n.S and actions nA,, where the transition probabilities, rewards, and utility functions are randomly sampled from specified distributions. The transition dynamics in Garnet are typically sparse, meaning that each state does not transition all other states, instead has limited number of possible successor states for each action. Mathematically, the environment defined by transition probability matrix P(s' s, a), reward function R[(s, a), and, in the case of constrained RL, utility function U(s, a). These elements are often drawn from normal distributions, i.e.,
P(s' 8, ~ NNaa, Ga). R(s,a) ~ (NW,,, U(s,a) ~ ((pes
where the means Pas Mb, Pe sampled from uniform distribution Unif(O,, 100). Since the transi- tion probability matrix must be valid (i.c., each row should sum to 1), the probabilities are exponen- tiated and normalized using softmax transformation:
exp(P(s' s,)))
( s. = Enr exp(P(s" ss)a))
E.2.2 Implementation details
In this environment, both the reward and cost values are stochastic, sampled randomly rather than being deterministically assigned. The cost (or reward) values generated as follows:

---

== ~ N(us,
(41)
where μ4 ~ 0 10] and σg 1. Similarly we generate the cost function. Here, we use oo and R interchangeably because the Garnet environment is formulated as a reward-based MDP with utility-based constraint function. Unlike the Constrained River-swim environment, the objective here is to maximize the long-term expected reward while ensuring that the expected utility remains above a specified threshold.
The hyperparameters used for this environment are listed in Table S
Hyperparameters
Value
15
Environment
A
20
Parameters
90
KL Uncertainity Evaluator
0.99
(Algorithm
Olkiee
10-3
CKL
0.05
Bobust_Q_table
10 3
RPPG
X
15
Table 5: Hyperparameter used for all subroutines for Garnet environment
Objective function
Constraint function
Cumulative Objective reward
200
Cumulative constraint cost
120
150
100
80
RNPG
100
RPPG
60
EPIRC
50
RNPG
40
baseline
RPPG
20
Safe region
EPIRC
Unsafe Region
200
400
600
800
1000
200
400
600
800
1000
Iteration
Iteration
(a) Expected objective function comparison
(b) Expected cost function comparison
Figure 5: Comparison RPPG and EPIRC-PGS on Garnet(15 15,20) environment = 30
E.2.3 Discussion of Results
The results are shown in Figure 5 As previously discussed, the Garnet environment incorporates a utility function in the constraint rather than traditional cost function. Therefore, feasible optimal policy is expected to yield an expected utility (constraint) value that remains above a predefined threshold. For consistency in terminology and to avoid confusion, we refer to the utility function as the "constraint function" in Figure 5b
From Figure 5b it is evident that all three algorithms- RNPG, RPPG, and EPIRC_PGS-satee the constraint throughout training, thus producing fcasible policies at each iteration. However, Fig- ure 55 shows that RNPG achieves noticeably higher expected objective return compared to both EPIRC PGS and RPPG.
Figure provides further insight into RNPG's behavior. Initially, RNPG operates well within the safe region and progressively improves objective return. As approaches the constraint bound- ary, the algorithm detects the potential violation and adjusts its trajectory accoringly-pprorriiiiigg safety over additional reward. This contrasts with the behavior of RPPG and EPIRC PGS, which also maintain feasibility but yield comparatively lower objective returns. These results highlight the advantage of incorporating a natural policy gradient approach, which allows RNPG to balance safety and performance more effecctively.
25

---

In addition to performance, we compare the computational efficiency of the algorithms. Table [1 shows that RNPG requires computation time comparable to RPPG, but significantly outperforms EPIRC PGS in terms of speed. Specifically, RNPG is at least 5x faster than EPIRC PGS when 7 0.9, and nearly 8x faster when 7 = 0.995. The increased runtime for EPIRC_PGS at higher discount factors is attributed to the longer binary search required for constraint satisfaction as approaches 1. The key takeaway from this experiment is that RNPG demonstrates greater sensitivity to constraint boundaries and exhibits strong potential for scalability to larger state and action spaces. Notably, the Garnet environment used in this study contains 15 states and 20 actions. These results suggest that, with efficient implementation, RNPG can be effectively extended to high- dimenssinn settings.
E.3 Modified Frozen-lake
The general Frozen-lake is as special type of grid world problem. The vanilla Frozen-lake problem can be found in gymnasium library [59]. However, in this work, we create a small modification to make the problem more challenging and interesting.
E.3.1
Environment description
The Frozen Lake environment is modeled as d x d grid world, where the agent begins its journey at the top-left corner, Sq = (0, 0), and aims reach the bottom-right goal state s (d-1, 1, 1). At each time step, the agent may choose one of four primitive actions: move left, right, up, down, constrained by the grid boundaries.
The environment contains multiple types of states:
Goal state: Reaching the terminal state yields high reward.
Hole states:
If the agent steps into a hole, it falls in and receives a very low reward.
Normal states: All other transitions yield a moderate reward.
In addition to reward dynamics, the environment contains hazardous blocks, which are selected ran- domly at each iteration. These represent dynamic threats (e-g., thin ice, traps, or roaming predators) and impose a high constraint cost when visited. The stochastic nature of these threats introduces uncertainty in the agent's experience, making the problem both risky and difficult to optimize.
The agent's s objective is to learn policy that maximizes the expected cumulative reward while incurring only marginal harm. In other words, it must learn to reach the goal while minimizing the cumulative constraint cost associated with hazardous states.
We formulate this problem as Constrained Markov Decision Process (CMDP) under model un- certainty. For all experiments, we set the grid size to = 4. To map a 2D coordinate (z, y) to its corresponding ID state index, define wrapping function:
wrap(( v)) x d d
The probability distribution function shown Table 6
The rewards and cost functions are given in Table 7 In particular, if it reaches the goal state the reward is +1. If the agent hits the obstacle, the cost is 1, and and the frozen grid it 0.3. Note that the a grid is obstacle or not is decided randomly at the beginning of an episode.
We detail all the other parameters in Table
E.3.2 Diseussion of results
The results obtained of the given environment is depicted in Figure As seen in Figure 6b all the three algorithms successfully learns the feasible policies. However, observing Figure 6al we can clearly notice the dominance of RNPG by learning policies with better rewards. From Table [] that for the frozen lake environment, the computation time of RPPG and RNPG is almost comparable. However, RNPG is atleast 3x as faster as EPIRC-PGS for ? 0.9 and almost 4x faster than EPIRC-PGS for 7 0.995.
The key takeaway from this enviornment to show that even with added obstacles randomly, the agent can find feasible high objective return policy compared RPPG and EPIRC-PGS
26

---

Present state
action
Transition probabilities
0 0)
up
= 0. = 0 0
1/6 and (z. y 1) = 1/6
x = 0, + 0)
up
x 0, 1/2,(z 1, 1/
1/6 and (z, 1
(xt + 0,y 7 0)
up
(x
1,y) :1/2.1/2 1,, 1/
1/6 and (I. - 11 1/6
( = 0, 0)
left
(I 0,,=0):2/3(z+111
1/6 and (z, y 1) 1/6
x * 0, = 0)
left
(z, y
0) 1/2,(z 1,3) 1/6,
1,3) 1/6 and (2, y 1) 1/6
x 7 0,y 0)
left
(x, y
1:11/[1 1,9
1/6,
1/6 and
(x 1, 1/6
[ 3.y 3)
down
(x = 3.
3):
2/3
1.
1/6 and (z. 1) 1/6
x = -3
down
(x = 3, y): 1/2. 1,
1/6, (1
1/6 and ( y 1) =116
3.9 3)
down
(xt + 1,y) 1/2.1 1,y
1
1)=
/ and (I. y 1) 1/6
④ 3,9 3)
right
(x x== 3. 3) 2/3
1,
1/6 and (z. y 1) 1/6
x 7 3.
3)
right
(x.y = 3) 1/2 1,
1/6,
(2
1,
1/6 /6 and [z.
1/6
7 3 3)
right
(0.8-1)::1
1,
1/6,(1.6++11 1/6 and (x = 1/6
Table 6: Transition probabilities for Frozen lake environement
State
Reward
constraint cost
(x=3.y=3)
+1
(x.y) if frozen lake
0.3
(x.y) if obstacle
0.01
all other (x.y)
0.05
Table 7: State wise rewards and constraint cost for the Frozen lake environment
Objective function (Modified Frozenlake)
Constraint function (Modified Frozenlake)
Cumulative Objective reward
100
Cumulative constraint cost
300
RNPG
250
RPPG
80
EPIRC_ PGS
baseline
60
150
Safe region
Unsafe Region
40
100
20
50-
MNP RPP PSS
0-
200
400
6áo
800
1000
200
400
600
800
1000
Iteration
Iteration
(a) Expected objective function comparison
(b) Expected cost function comparison
Figure 6: Comparison of RNPG, RPPG and EPIRC-PGS on Modified Frozen-lake environment
E.4
Garbage collection problem
E.4.1
Environment description
We model a city as 4 grid, where each cell represents a city block. A garbage collection robot is deployed to navigate this grid and collect waste while minimizing operational risk and resource expenditure.
Certain blocks offer higher rewards due to significant waste accumulation (e.g., near hospitals or markets). However, urban conditions are inherently dynamic. These high-reward blocks are known in advance and are constantly changing showing the rapid changes of city areas. At each time step, 40% of the blocks are randomly designated as hazardous, representing unpredictable real-world events such as:
Sudden traffic congestion
Unreported toxic waste dumps
Temporary road closures or civil disturbances
27

---

Hyperparameterss
Value
15
Environment
A
Parameters
pd
Table Table
Cp C1
b
55
KL Uncertainity Evaluator (Algorithm
0.99
2
10-3
O'kle
CKL
0.02
Robust Q table
a
10 10-3
RPPG
50
Table 8: Hyperparameter used for all subroutines for Modified Frozen-lake environment
These hazardous blocks incur higher constraint cost if visited. Importantly, the set of hazardous blocks changes at every iteration, introducing layer real-time uncertainty the environment.
The robot must learn policy that balances the dual objectives of:
Maximizing long-term reward by collecting from high-value blocks
2. Minimizing cumulative constraint costs induced by environmental hazards
The transition probabilities are similar to the Frozenlake environment. Hence the transition proba- bilities for this environment can depicted by Table ( The reward and cost structure is given in T While the reward is fixed at the Goal location, the reward at garbage location is 0.01. Note that whether a certain grid a garbage location or not decided randomly, Similarly, the cost is at blocked grid. Again, the identities of the blocked grids are randomly decided.
State
Reward
Cost incurred
(x=3.y=3)
1
0.01
(x.y) garbage
0.01
(x.y) if blockage
(x.y) all other state
0,001
0.01
Table Reward and cost structure for Garbage collector environment
The hyperparameters for the various sub-routines are listed in Table 10
Hyperparameters
Value
15
Environment Parameters
A
nd
Table
Co, C1
Table
b
60
KI. Uncertainity Evaluator (Algorithm 2)
7
0.99
10-3
O'kle
CKL
0.02
Robust_0 -atable
10-
RPPG
50
Table 10: Hyperparameter used for all subroutines for Garbage collector environment
E.4.2 Discussion of results
In this subsection, we will present the performance of the RPPG, EPIRC PGS and our algorithm (FinG)FFigure7).. As shown in Figure due to the randomness of the environment, the algorithms have some minor fluctuations. However, in this environment, RPPG and RNPG obey the constraints for the complete duration, but, EPIRC_PGS violates the constraint. Although none of the algorithms
28

---

Objective function (
collector)
Constraint function (Garbage collector)
Cumulative Objective reward
175
300
RNPG
150
Cumulative constraint
250
RPPG
125
EPIRC_ PGS
100
200
baseline
150
Safe region
75
Unsafe Region
50
100
RMP RPG EGS
50
0-
200
400
600
800
1000
200
400
600
800
1000
Iteration
Iteration
(a) Expected objective function comparison
(b) Expected cost function comparison
Figure 7: Comparison of RNPG, RPPG and EPIRC-PGS (or, EPIRC_PGS) Garbage collector environment
Best policy objective and constraint return comparison
RPPG
RNPG
EPIRC-PGS ( vals.)
Env Nm
0.9
0.99
0.995
Vf
Cf
8f
Cf
Vf
Cf
vf
Cf
0,
Cf
CRS, b = 42.5
120.3
43.1
102.
42.2
127.2
44.8
121.2
48.1
123,4
46.4
Garnet, bj -90
90
102.6
99.55
208.1
-98.7
100.3
-12.44
100.6
-108.3
102.4
-10.2
MFL, 61 52.5
61.4
53.1
109.2
39.2
62.3
53.7
60.3
57.7
66.3
51.7
GC, bj = 52.5
161.2
49.2
172.2
22.1
131.2
52.0
142.5
55.6
138.
54.1
Table 11: Comparison of the best policy objective (vy) and constraint function (cy) values. bj indicates the threshold value. RNPG not only achieves the best value, but also gives feasible policy.
stabilize completely yet RPPG and RNPG are in the safe zone. In terms of objective return, can be seen from Figure 7a the expected return for RNPG is predominantly higher than RPPG and SEIRC_PGS While comparing the time (Table IT) for completion RPPG is the fastest in this environment marginally beating RNPG but still the speeds of both algorithms are comparable. When compared with EPIRC_ PGS, RNPG is winning fairly with a speedup of 2x compared to EPIRC.PGS when y 0.9 and speedup of nearly 3x compared EPIRC. PGS when 7 0.995.
This environment demonstrates that, even under random obstacle placement, the agent can success- fully learn feasible policy that ouiperforms RPPG and EPIRC PGS in terms of objective return.
F
Implementation Details of RNPG and RPPG
F1
RNPG
Note that in (11) mization, we also adopt a soft-max representation of the policy space. Let the policy be parameter- ized by 0, such that:
direct parameterization for policy update in RNPG. To facilitate opti-
exp (0r(s)
π
(42)
Eees exp (0])))
Using this parameterization, we reformulate the policy update as the solution to the following con- strained optimization problem:
O arg max V Jen O++1 0z) aa (II,TT,,,
(43)
e.+1
where the objective index ch is selected as:
max (J - bi)
ch = arg max
X
i=l..., K
29

---

This formulation enables us to apply the Natural Policy Gradient method by incorporating the ge- ometry of the policy space through the Fisher Information Matrix JF [60]. The resulting closed-form update rule is:
0++1 Oir
F F-
200
F.2 Robust Projected Policy Gradient (RPPG)
We also compare the Robust Projected Policy Gradient (RPPG) which uses regularization instead of the KL regularization. Here, we use direct parameterization. The policy update is given in the following.
1
T(+1 E arg min vi π - Tτ) + TEll
|| mell?
(44)
20c
where arg max L
max, (J
bn + }
Upon careful observation, we see that Equation (44) is convex. To find the optimal solution of T++1 we use projected gradient descent. Equation (44) can be updated as
Tt+1 arg min || (Te 0r V JT)
(45)
rell
This is the Euclidean projection the gradient step onto the simplex:
T++ III (T, a, (((e))
(46)
From Lemma 3.1 we get the value of n. (.Te) using the robust Q value evaluator in Algorithm 3 We finally project the resulting value into the policy space simplex, II. To perform projection,
find || [x a JI (T+)) A π E II. However, this process is cumbersome, hence we can leverage the evxpy package from Python to optimally solve the update equation.
Algorithm 4 Robust- Policy Gradient for CMDP with uncertainties (R-PPG)
1: Input: Robust Policy evaluator (Algorithm 2 by s.t. i E (1,K),
2: Initialization: (-1s)) = 1/| for all s, T.
3: for 0,
do
4: Evaluate J maxp JTP for = (co... "6o...ck] using the robust policy evaluator oracle.
5: ch = arg max((22 /A, J by + +) s.l. ie (1, K}
6:
if ch + 0 then
7:
*++1 = Projn me - 04 J }.
Cch
8:
else
9:
T+ = Projn - V
end if
11: end for
Output arg min.co....TT1 max J max, (J bb+
As shown Algorithm 4. RPPG leverages Projected Policy Gradient method reach the optimal policy. In general &a regularizer does not ensure small changes in the policies and might deviate lot from the previous policy. Thus, KL-regularizer has better performance over &g regularizer which we further demonstrate by our results in Section
G Extension to Continuous state space (Robust Constrained Actor Critic)
We present our robust constrained actor critic framework designed for the function approximation setting as discussed in Section The model comprises two critic networks- estimating the re- ward value function Jc, and other corresponding to the Constraint value function Jry Although we focus on single constraint for clarity, the framework readily generalizes to handle multiple con- straints. In addition to the critic networks, an actor network employed to generate actions based on the current state. To model distributional robustness, consider IPM as described in Section 6.1
30

---

Let us consider the critic network be parameterized by w where each layer contains d paramters including the bias (i.e, wi.d where w is assumed be the bias term in the I-th layer with / (1,2..... I.)). Overall approach is depicted in Algorithm
Algorithm Robust Constrained Actor Critic (RCAC)
1: Input: T.p.u b
2: Initialization: Wy (for objective estimation), (for constraint estimation) and 0" for actor
network parameterization
3: f T do
4: Get estimate for J, = (p, (s)) and Jo= = (p, (s))
5: ch arg maxxJJ,/X, (Je- -b) b])
6: Update Wehh using Web = Wehh + ag. w.a Mp (s)s), Jak) (Note Vi(s) is target Value
function obtained by Robust TD update (using equation [5
7: Update f using H gi- + o.E (Vo log wo (a (a)ls))(((()))) (Qhh - Va)())) (We change this
step to Natural Policy Gradient update for NCGC.
8: end for
At each step, we get the Value function estimate V, and V. from the respective Critic networks. After obtaining both, make choice to whether to update the constraint critic parameters or the objective critic parameters. For the selected critic, we find the target value function using the robust bellman operator along with guided regularization term on the last layer only [54]. We compute the robust value according to (15).
For our experiments, we chose the famous Cartpole environment, where the intial state is fixed and deterministic so p(i) is unit vector, can be extended to different distribution.)
1 {
if = otherwise
p(s)
(47)
In our study, we introduced uncertainty in the next-state transition after each action. While alter- native sources of uncertainty could be incorporated -ucch as perturbing the executed actions or simulating external disturbances (e.g., wind forces acting on the cart) focused on state tran- sition perturbations because they have a more direct and analyzable impact on value estimation. Perturbing the action space was deemed less meaningful in this environment, as the action set is dis- crete with only two possible values, making the resulting learning challenge comparatively trivial. The detailed results and observations are presented in the following subsection.
G.1 Results and discussion
In this sub-section, list the results obtained when tried our algorithm against the standard cartpole-v] environment available in gymnasium library. The cartpole-v algorithm comprises of continuous state space having 4 components and two discrete actions. We introduce uncertainity by adding noise to the next state obtained after taking an action. The noise is adding uniform value between 0 and 0. to the original next state value (s = + Un. 0.1))) and then clipped it between the predefined bounds of cartpole environment.
We divided the experiments results into two phases. The first is the training phase (depicted by Fig- ures R) and the second is during the testing phase (depicted by Figures 9. During the training phase, we only train the robust variants RCAC, RCAC with NPG, Robust CRPO, EPIRC-PGS by consid- cring 6 0.04. However, for constrained actor-critic (CAC), we do not train the robust version. During the training phase (Figure 8). apart from EPIRC-PGS, all the algorithms perform similarly in terms of reward and the cost value function (We highlight our two algorithms RCAC with NPG, and RCÁC, separately in figure r0p. EPIRC-PGS did not converge and could not complete the en- tire episode highlighting that binary search approach not possible to scale for large state-space. However, when these algorithms were tested (Figure 9) on the environment having a perturbation uniformly between and 0.04, the performance of CAC unstable and did not provide any feasi- ble policy. Only, our proposed approaches achieve feasibility while being close to the optimality. Robust CRPO also violates the constraint (slightly) while achieving less reward compared to our approaches. The performances of the algorithms is compactly represented in table T2
31

---

Algorithm
Average reward value
Average cost value
Constrained Actor Critic
495.23
294.6248
RCAC
494.81
177.8432
RCAC with NPG
495.0
197.9937
Robust CRPO
488,06930
213.473
EPIRC_PGS
114.8
53.79
Table 12: Tabular comparisons of the average value function and cost function during the testing phase. CAC although returns policies with high objective function but the actions unsafe can be inferred from the high constraint function (safety baseline is 200)
is also important to note down the wall clock time for the various algorithms. EPIRC PGS takes the highest wall clock time approximately 24029.013 2132..113 seconds which is nearly 4x of the time taken for the other algorithms namely RCAC with NPG (7175.31 seconds), CAC seconds), RCAC (5975.65 seconds) and Robust CRPO (4275.67 seconds) in decreasing order of the wall clock time requirements.
Compartson of Cost function on Cartpolo environment
Comparison of Value function on Cartpole environment
BZAC
500
502
RCAC YPG
CAC
Rebust. CMPO
EfIIIC FC5. CS
500
Safe region
Lireath
Dusid tre
Whire fuencinn
300
REAC
RCAC NYG
Dae
Robint CIPO DARC PCS CS
200
200
30000
Iterations
Iorattons
Value function comparison
(b) Cost function comparison
Figure& 8: Comparison of RCAC, RCAC.NPG, robust CRPO and other standard Constrained MDP solutions on the Cartpole problem during training phase
Comparisan Value Cartpole environmant
Comparison function environment
RCAC
CAC
500
Rozue
Sate region
region
Deuu landeen
Cost Aucetin
Basel
502
300
200
300
NCAC KCAC NPG
100-
Rolust_CPPO
20
40
100
100
Rerattos
Itaazions
Value function comparison
(b) Cost function comparison
Figure 9: Comparison between RCAC, CRPO and Vanilla Constrained Actor Critic during testing
period 5 0.04 (deflection from the nominal model)
32

---

Comparison of Value function on Cartpole environment
Comparison of Cost function on Cartpole environment
503
000
RCAC
RCAC,NRC NPC
700
Sale reglon
Unoote reiion
600
Danedinn
100
fanctio
500
400
200
RCAC RCAG
3-
4050
2050
18090
Value function comparison
(b) Cost function comparison
Figure 10: The comparison plots between our two main variants of Robust Constrained Actor Critic
variants (RCAC and RCAC.NPG)
H Connection with the CRPO
CRPO is one of the popular approach for non-robust CMDP which has been proposed in [1] In the CRPO algorithm, one minimizes the objective when all the constraints satisfied, and minimizes the constraint value if the policy violates the constraint for at least one constraint. In particular, the objective function can be represented
min J (max Jc., b, S 0) + max(Je, b,,x Je,, b, 0)-
(48)
Thus, might think that there some connections with approach and the robust CRPO. First, we provide the challenges in extending the results to the RCMDP case. [[]] they bound the difference the value function corresponding the policies between steps using the standard value difference lemma. However, the standard value difference lemma does not hold in the robust as the worst transition probabilities differ according the probabilities.
In what follows, we point out the difference of our approach and potentially robust CRPO ap- proach. In order obtain iteration complexity, seek to the smoothness property of the objective by invoking Moreu's 's envelope as done in [8]. In particular, we use a smooth function objective instead of the one in (48). It turns out the this modifi-
max(J;/ /X, max, J - b,, cation is essential for obtaining the iteration complexity. Note the difference we are not switching not satisfied, rather only minimizing those when max, J - bn becomes larger than J /A. Thus, as À becomes larger it becomes similar to CRPO. Also, note that in the asymptotic tee the sub-optimality gap anymore showing that perhaps, robust CRPO algorithm may not achieve the iteration complexity bound.
to minimize the constraint cost value functions when the constraints
as À 0o,
guaran-
33

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our main claim is addressed in two folds, (i) we reflect upon the theoretical guarantees is evident from Section 4 and also in the appendix, and (ii) check the prac- tical applicability of our algorithms on some standard finite state-action space benchmarks for standard RL shown in Section 5.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We mention the major limitations identified by us before conclusion
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asympiotic approximations only holding locally). The au- thors should reflect on how these assumptions might be violated practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the ap- proach. For example, a facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't it acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
34

---

Answer: [Yes]
We clearly state all the assumptions and the detailed proof using those as- sumptions
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear the main paper or supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple-
mented by formal proof' provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yss]
Due to page limitation, we talk about the empirical results in detail in the ap- pendices disclosing the complete details about creating the environment and corresponding code and plots to solve it.
Justification:
Guidelines:
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 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 novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data 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 sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results way produce the model (e.g., 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 thors 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 (c.g., to registered users), but it should be possible for other researchers to have some path to reproducing verifying the results.
35

---

5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification:
The complete details can be found in Section 5 and Appendix A,B and
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co cc/
for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
//nips.co cc/
wtt.cccppppullccccccc public/ weriic/guiiiiee guwdes/ Stt///ooeeSeieeieeeeee SonrdeSuumissionn. ssi ssionPolicy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We disclose all the hyperparameters necessary to replicate Appendix B and C.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
We consider a single run the confidence interval was not necessary
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
36

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We make this information available as a footnote Section
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't It make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
We declare that we read and understood and did our best to conform
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- cration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our experiments are based on some standard benchmarks and we did not use any real life experiments.
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.
37

---

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 spe- cific 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 direct path to any negative applications, the authors should point it out. For example, it is legitimate to point that 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 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 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 mitiga- tion strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (c.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: As we perform testing on some standard toy examples, it does not give way to any negative impacts
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by re- quiring that users adhere to usage guidelines or restrictions 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 require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
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?
Question:
Answer: [Yes]
Justification: We are not shipping our code with any source code or binary files from any other existing libraries, so there are no concerns over getting permission or including license.
Guidelines:
The answer NA means that the paper does 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 used and, 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.
38

---

If assets are released, the license, copyright information, and terms of use in the pack- age should be provided. For popular datasets, wwtpppppppppoooooo
com/datasets has curated licenses for some datasets. Their licensing guide can help determine the li- cense of 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 available online, the authors encouraged to reach out the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [Yes]
Justification:
We have made our code public and will create suitable readme file for its
use.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl 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.
At submission time, remember to anonymize your assets (if applicable). You can cither create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsoureing experiments and research with human subjects, does the per include the full text instructions given to participants and screenshots, applicable, well as details about compensation (if any)?
Answer: [NA]
Justification:
We do not involve in any crowdsourcing experiment
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, cura- tion, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects. and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
We are not involved in any crwod sourcing experiments.
Guidelines:
The answer NA means that the paper does involve crowdsoureing nor research with human subjects
Depending on the country in which research is conducted, IRB approval (or equiva- lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
39

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere 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.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: We do not use LLMs for the core method development, we use for grammar chack and for better appeal.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy hutgses//eaaiiigccc/ooeereeeeee for what should or should not be described.
40


Reviews:
[{"review_id": "DIfb07RF7C", "reviewer": "Reviewer_GbJz", "summary": "The paper introduces a KL‑regularized policy‑gradient method (RNPG) that compare favorably to EPIRC‑PGS in terms of computational efficiency and proves an $O(\\epsilon^{-2})$ convergence rate to zero‑violation solutions in robust CMDPs.", "questions": "- How would the results change if working with a finite state-action space but with function approximation?\n- It might have been interesting to also see a baseline of a naive Lagrange method or something like CRPO applied with worst-case values.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n\n- Reformulating RCMDP as a single max‑objective (Eq. 3) eliminates the epigraphic binary search and yields the RNPG update with a principled KL mirror step. \n- Theorem 4.1 guarantees an $\\epsilon$‑optimal feasible policy in $O(\\epsilon^{-2})$ iterations, improving the $O(\\epsilon^{-4})$ bound of Kitamura et al. 2024 ([8] in paper).\n- Experimental results show 4–8 times faster convergence than EPIRC‑PGS on Garnet and CRS tasks.\n\nWeaknesses\n- Assumption 1 requires knowing a constant $\\xi > 0$ such that the unknown optimum satisfies all constraints with margin $\\xi$. $\\xi$ is then used to set other parameters and prove zero‑violation. If $\\xi$ is unknown, Theorem 6.1 shows RNPG still converges but only guarantees an $\\epsilon$‑level violation and reverts to the same O(\\epsilon^{-4}) rate as EPIRC‑PGS. Thus, the headline $O(\\epsilon^{-2})$ benefit hinges on oracle information.\n\n- Convergence also needs a “positive‑density” condition on transition kernels, inherited from robust PG theory.\nThe paper does not quantify how large this density must be, nor test cases where it fails (e.g., sparse transitions), leaving its practical prevalence unclear.\n\n- All experiments use exact tabular robust evaluators; no test shows RNPG with\n* sampled value estimates,*\n* function approximation,* or\n* large state spaces.*\nHence we do not know how the algorithm behaves when the robust oracle is approximate or when KL updates are computed from mini‑batches.\n\n- Every RNPG step still solves $\\max_{P\\in\\mathcal P} V^\\pi_P$\nfor each cost/reward. For KL sets this is closed‑form, but for TV/Wasserstein sets it involves linear programs or iterative solvers. The paper (Alg. 2, appendix) alludes to such a “robust evaluator” but never times it or analyses its complexity; scaling to thousands of states could erase the gains from eliminating the binary search.\n\nMinor comments\n\n- It would be nice to clarify further the meaning of Assumption 2 (p.6) and its practical validity.\n- The caption is missing “RNPG” despite the fact that the RNPG curve is plotted.", "was_revised": true, "final_justification": "The authors provided a thorough response during the rebuttal, and major concerns are addressed.", "rebuttal": "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.\n\n>*Assumption 1 requires knowledge of $\\xi$..*\n\n* 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.**\n\n>*Convergence also needs a “positive‑density” condition on transition kernels..*\n\n* 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. \n\n* 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. \n\n>*All experiments use exact tabular robust evaluators; no test shows RNPG with *sampled value estimates*, *function approximation,* or *large state spaces.*..*\n\n* 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:\n\n| Algo | Avg. Reward Value | Avg. Cost-value | Wall-Clock Time(s) |\n|---|---|---|---|\n|Vanilla Constrained Actor-Critic with NPG | 323.15  | 350.12 |752.35 |\n|**Robust Constrained Actor-Critic with RNPG (RCAC)** | **298.99** | **199.2**| 770.2 |\n| CRPO | 352.42 | 370.69 |  761.56|\n|Robust CRPO | 281.24 | 179.7 | 701.1|\n|EPIRC-PGS|  114.8 | 53.79 | 1429.14|\n\nFor 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. \n\n* 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.\n\n>*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..*\n\n* 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.\n\n* 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.\n\n* 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.\n\n>*It might have been interesting to also see a baseline of a naive Lagrange method or something like CRPO applied with worst-case values...*\n\n* 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:\n\n| Algo | Avg. Reward Value | Avg. utility-value | Wall-Clock Time (s) |\n|---|---|---|---|\n|EPIRC-PGS | 108.25  | 107.33 | 390.21 |\n|**RNPG** | **170.142** | **116.55**| **99.21**|\n| RPPG | 118.54 | 107.2 | 103.21 |\n| Robust- CRPO | 142.89 | 101.05 | 101.51 |\n\nHere, 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. \n\n[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.\n\n[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.\n\n[A3]. Kumar, Navdeep, et al. \"Policy gradient for rectangular robust markov decision processes.\" Advances in Neural Information Processing Systems 36 (2023): 59477-59501"}, {"review_id": "bCIho3P24s", "reviewer": "Reviewer_Vtph", "summary": "This paper considers the setting of robust constrained MDPs, which aims to minimize the expected cumulative cost for the cost function $c_0$ and hope maintain a feasible cost for the cost function $c_i$ for $i=1,2,...,K$. An existing approach applies the epigraph approach to solve this problem but it requires to evaluate robust value function at every iteration and has $O(\\epsilon^{-4})$ iteration complexity. This paper aims to address this issue with proposing a more computationally efficient approach. The proposed method re-formulates the problem design with re-writing the objective loss in an equivalent form and this paper derives the best-known iteration complexity. The results are also validated using experiments.", "questions": "I have a few requests on improving this manuscript:\n1. Add empirical experiments on mojuco or other more common RL environments.\n2. Fully revise the proof to improve the readability and the correctness. \n3. Add experiments to validate the compatibility with neural network and considering the continuous state or action spaces.", "limitations": "NA", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 1, "significance": 2, "originality": 3, "strengths_and_weaknesses": "## Strengths\nThis paper proposes a new approach to handle the robust constrained RL problem. The re-formulated objective loss is new and has not been discussed before. To this reason, this paper is sufficiently new. Proving the equivalence between the re-formulated objective (3) and the original objective (1) also introduces a new theoretical result.\n\n## Weaknesses\n1. Only toy experiments are provided. It is not irrational to claim that the algorithm is more computationally efficient with providing only toy examples.\n2. The given Garnet and Constrained River-swim are too trivial.  The proposed method needs to be compared with more methods such as [1] in more tasks (e.g., mujoco locomotion tasks) to demonstrate its efficiency.\n\n[1] Xu, Tengyu, Yingbin Liang, and Guanghui Lan. \"Crpo: A new approach for safe reinforcement learning with convergence guarantee.\" International Conference on Machine Learning. PMLR, 2021.\n\n3. After a careful check of the proof, I found several critical issues that cannot be simply fixed during the rivision period:\n    * The whole proof doesn't specify the optimized parameter in the function, especially when using $\\max$ or $\\arg\\max$. For example, in L599, it doesn't tell what the p is. It could be taken over P, and it can also be taken over $\\pi$ (p for Pi). The context is unclear so the subscript shouldn't be omitted.\n    *  Many statements are incomplete. For example, Lemma B.3. only presents an equation without introducing the notations used in this equation. \n    *  Due to the unclear notations and incomplete statements, many steps in the proof are confusing and hard to check if it is correct or not:\n        * In Equation (30), the first inequality and the second inequality are the same. No explanation given here on why it holds.\n        * Equation (31) is not clear. The explaination \"$V(s') \\geq V^{\\pi^\\*}(s')$ as $J-J^{\\pi^\\*}\\geq 0$\" doesn't hold. Because $J$ is an expected $V^\\pi$, the non-negative expected value doesn't imply each atom is non-negative.   \n        * After Equation (31): the recursively expanding step omitts too much. First, the RHS of Lemma B.3 is missing one $\\rangle$ immediately after $\\pi^*$. Second, the RHS looks so different from Equation (31). More details are needed. \nI didn't further check the remaining proof as the manuscript should be fully revised to improve its readablity and correctness. The current version is obviously flawed.\n\n4. This paper relies on a very specific uncertainty set. Though it is claimed that \"Our framework is not limited to KL-divergence\", the explaination and the empirical analysis are not sufficiently convincing. Also, it requires to take the specific policy evaluation algorithm used in existing literature, which makes this paper lack sufficient novelty in this direction. \n\n5. The proposed methods cannot be extended to the general function approximation. The author claims this in the limitation section but it doesn't prevent it from being a major limiation of this  proposed method.", "was_revised": true, "final_justification": "I have carefully checked the revised comment provided by the author. Given the proposed fix, the proof should be correct without major alter from its original result. I still encourage the author to fully revise the proof to improve the readability.\n\nI am not completely satisfied with the experiments, but the newly added results have been partially sufficient to support the results presented in this paper.\n\nAs the result, I raise my score to 4.", "rebuttal": "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.\n\n>*Only toy experiments are provided. It is not irrational to claim that the algorithm is more computationally efficient by providing only toy examples...*\n\n* 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**.\n\n---\n\n### Evidence beyond small/tabular settings\n\n**Function approximation & continuous state space.**  \n   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. \n\n| Algo | Avg. Reward Value | Avg. Cost-value | Wall-Clock Time (s) |\n|---|---|---|---|\n|Vanilla Constrained Actor-Critic with NPG | 323.15  | 350.12 | 752.35|\n|**RCAC** | **298.99** | **199.2**|770.25|\n| CRPO | 352.42 | 370.69 |761.56  |\n|Robust CRPO | 281.24 | 179.7 | 701.1|\n|EPIRC-PGS|  114.8 | 53.79 | 1429.14|\n\nFor 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. \n\n2.**Strength against EPIRC-PGS**.\n\nAlso, 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. \n\nWe 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. \n\n>*Regarding Proof of Lemma B.3..*\n\n* We apologize for an oversight. First, there are typos in the proof of Lemma B.3. In particular, $\\pi^*$, \n\n 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. \n\n* Second, we will explicitly mention that $\\hat{\\pi}^*$  \n\nis a uniform minimizer of the surrogate problem (we have removed $\\lambda$ to maintain notational simplicity for Markdown)\n\n$\\min_{\\pi}\\max_{i}[\\max_PV^{\\pi,P}_{c_i}(s)] \\forall s$. \n\nWe 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].\n\n* 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))$\n\n$ \\leq V_{c_i}^{\\pi,p}(s)$\n$-V_{c_i}^{\\hat{\\pi}^*, p}(s)$,\n\n\nwhere we use the fact that $(p,c_i)=\\arg\\max_{j,p} V_{c_j}^{\\pi,p}(s)$\n\n\n* 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).  \nHence, in eqn (31), we apply the fact that \n\n$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))$\n\n$\\geq V_{c_i}^{\\hat{\\pi}^*,p}(s)$ \n\nbecause of the uniform minimizer assumption on  $\\hat{\\pi}^*$ $\\forall s$, this allows us to use Assumption 2, and use  $p_0$    \n\nin 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\n\n>*I didn't further check the remaining proof as the manuscript should be fully revised to improve its readablity and correctness.*\n\n* **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. \n\n* 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).\n\n>*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.*\n\n* 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.\n\n>*The proposed methods cannot be extended to the general function approximation...*\n\n*  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:\n\n| Algo | Avg. Reward Value | Avg. Cost-value | Wall-Clock Time(s) |\n|---|---|---|---|\n|Vanilla Constrained Actor-Critic with NPG | 323.15  | 350.12 | 752.35|\n|**RCAC** | **298.99** | **199.2**|770.25 |\n| CRPO | 352.42 | 370.69 |761.56  |\n|Robust CRPO | 281.24 | 179.7 | 701.1|\n|EPIRC-PGS|  114.8 | 53.79 | 1429.14|\n\nFor 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. \n\n\n**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.**\n\n[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.\n\n[A2]. Iyengar, Garud N. \"Robust dynamic programming.\" Mathematics of Operations Research 30, no. 2 (2005): 257-280."}, {"review_id": "JI0aK6x5KS", "reviewer": "Reviewer_rBgq", "summary": "The authors develop an algorithm for performing reinforcement learning in a constrained Markov decision process (MDP) setting. In regular constrained MDPs, the state-action occupancy measures of the underlying policies are convex, and the min-max problem can be solved via strong duality. On the other hand, if the underlying transition function of the MDPs is not known, the problem is no longer convex and is hard to solve. The authors develop a projected gradient method like existing constrained MDP algorithms, but rely on a KL-divergence regularization term to provide stability. Specifically, the algorithm first maximizes the reward like regular RL algorithms, but the algorithm adjusts the KL-divergence term if a constraint is violated during the training to provide safety. The algorithm is evaluated on two toy examples, and the authors show that the robust natural policy gradient (RNPG) algorithm can provide superior performance while satisfying the safety constraints.", "questions": "1- 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.\n\n2- 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 for calculating an upper bound of difference in the policy update. I do agree that this assumption is restrictive, particularly on the transition functions sharing the same support. I was curious if the authors could comment on replacing that Assumption with a weaker term such as having a bound on the expected successive states in a discrete or continuous state-action setting. I'd think that such an assumption would be more applicable in a continuous state-action setting rather than a discrete one.\n\n3- 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.", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "The strengths of the paper are providing an efficient algorithm for the robust contained MDP problem by using KL-divergence term instead of projected gradient ascent in the policy update to provide superior computation efficiency compared to existing work [8]. The algorithm improves on the existing iteration complexity O(\\epsilon^{4}) to O(\\epsilon^{2}).\n\nHowever, the authors assume that the initial policy is strictly feasible. They discuss how this assumption can be relaxed in Section 6, and provide a short proof and bound in the Appendix. However, the authors assume that the transition functions of the MDP has the same support, i.e., given a state and action, they should have the same set of successive states, which I believe is a bigger restriction compared to the finite state and action spaces.", "was_revised": true, "final_justification": "I did go through the responses of the authors to my and other reviews. I think the authors did a good job in clarifying the required assumptions, and also the added experiments to my and Reviewer Vtph's comments. Therefore, I am raising my score.", "rebuttal": "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.\n\n>*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.*\n\n*  Thank you for pointing this out. The reviewer’s interpretation is not accurate:\n\n* **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. \n  * 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.\n\n  * 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.\n\n* **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. \n\nWe will revise the manuscript to emphasize this distinction and prevent further confusion.\n\n>*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..*\n\n* 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. \n\n>*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.*\n\n* 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. \n\n| Algo | Avg. Reward Value | Avg. Cost-value | Wall-Clock Time (s) |\n|---|---|---|---|\n|Vanilla Constrained Actor-Critic with NPG | 323.15  | 350.12 | 752.35|\n|**RCAC** | **298.99** | **199.2**| 770.25 |\n| CRPO | 352.42 | 370.69 |761.56  |\n|Robust CRPO | 281.24 | 179.7 | 701.1|\n|EPIRC-PGS|  114.8 | 53.79 | 1429.14|\n\nFor 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. \nThe 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. \n\n\n[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."}, {"review_id": "aRNFLTpHfJ", "reviewer": "Reviewer_XfhM", "summary": "This paper introduces a novel approach designed for the Robust CMDP (RCMDP) problems. The authors first reformulate the optimization problem in a new way to balance the trade-off between optimizing the objective and satisfying the constraints, and then propose an algorithm PNPG which is at most $\\epsilon$ sub-optimal. This paper mainly has two contributions: one is that there is no need to perform a binary search on $\\lambda$, compared to the state-of-the-art method, and the other is that it first shows the strict feasibility can be achieved and improves the iteration complexity to $O(\\xi^{-2}\\epsilon^{-2})$ if the strict feasibility parameter $\\xi$ is known. The authors further illustrate that if $\\xi$ is unknown, the algorithm can get a policy with $O(\\epsilon^{-4})$ iteration complexity, which has a same dependence on $\\epsilon$ but a significantly better dependence on $S, A, (1-\\gamma)^{-1}$ compared to the state-of-the-art method. Finally, the authors conduct numerical experiment for their algorithm and the experiment settings and results make sense to me.", "questions": "1. 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?\n\n2. Is there any lower bound on the iteration complexity?\n\n3. It seems that the reference [10] belongs to the LP-based methods for solving the primal problem directly, instead of addressing the iteration complexity?", "limitations": "yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strength: The paper is well-written and it is an easy read for the reader to get the main idea. Also, in contrast to previous works on robust CMDP problem (EPIRC-PGS), this paper presents a computationally more efficient approach (RNPG) without binary search, achieving a faster iteration complexity bound and better dependence on the state-space. Compared to RPPG, the approach (RNPG) has better performance and more stability.\n\nWeakness 1: The paper does not consider infinite state-space which may be very different from finite state.\n\nWeakness 2: The authors do not prove the optimality for their iteration complexity lower bound. There may exist some better approaches to achieve tighter results.", "was_revised": true, "final_justification": "I maintain my positive recommendation of the paper.", "rebuttal": "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.\n\n>*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?*\n\n* 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.\n\n| Algo | Avg. Reward Value | Avg. Cost-value | Wall-Clock Time (s) |\n|---|---|---|---|\n|Vanilla Constrained Actor-Critic with NPG | 323.15  | 350.12 | 752.35|\n|**RCAC** | **298.99** | **199.2**| 770.25 |\n| CRPO | 352.42 | 370.69 |761.56  |\n|Robust CRPO | 281.24 | 179.7 | 701.1|\n|EPIRC-PGS|  114.8 | 53.79 | 1429.14|\n\nFor 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. \nThe 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.\n\n\n\n* **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.\n\n\n>*Is there any lower bound on the iteration complexity?*\n\n* 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.\n\n>*It seems that the reference [10] belongs to the LP-based methods for solving the primal problem directly, instead of addressing the iteration complexity?*\n\n* The reviewer is correct. We will specify that. \n\n[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."}]

Author rebuttal:

Meta-review: This paper presents an algorithm, Robust Natural Policy Gradient (RNPG), for solving robust constrained Markov decision processes (RCMDPs). The key innovation is a reformulation of the RCMDP objective that circumvents the need for the computationally expensive binary search, which is required by prior state-of-the-art methods. The authors provide strong theoretical guarantees. The reviewers unanimously acknowledged the significance of this contribution, highlighting the principled approach of eliminating the binary search and the improved theoretical bounds. The author's rebuttal successfully address the reviewers' initial concerns.
Decision: Accept (poster)