Rectified Robust Policy Optimization for  Model-Uncertain Constrained Reinforcement Learning without Strong Duality
Authors: Shaocong Ma
Ziyi Chen
Yi Zhou
Heng Huang
Venue: Accepted by TMLR ()

Abstract: The goal of robust constrained reinforcement learning (RL) is to optimize an agent's performance under the worst-case model uncertainty while satisfying safety or resource constraints. In this paper, we demonstrate that strong duality does not generally hold in robust constrained RL, indicating that traditional primal-dual methods may fail to find optimal feasible policies. To overcome this limitation, we propose a novel primal-only algorithm called Rectified Robust Policy Optimization (RRPO), which operates directly on the primal problem without relying on dual formulations. We provide theoretical convergence guarantees under mild regularity assumptions, showing convergence to an approximately optimal feasible policy with iteration complexity matching the best-known lower bound when the uncertainty set diameter is controlled in a specific level.  Empirical results in a grid-world environment validate the effectiveness of our approach, demonstrating that RRPO achieves robust and safe performance under model uncertainties while the non-robust method can violate the worst-case safety constraints.

Published in Transactions on Machine Learning Research (08/2025)
Rectified Robust Policy Optimization for Model-Uncertain Constrained Reinforcement Learning without Strong Duality
Shaocong Ma
scma@908@umd.edu
Deportment of Computer Science University of Moryland, College Park
Ziyi Chen
zc2860eumd. edu
Department Computer Science University of Moryland, College Park
Yi Zhou
yi.zhou Clama edu
Department of Computer Science and Engineering Texas AUM University
Heng Huang
heng@umd edu
Department of Computer Science Universily of Moryland, College Park
Reviewed on OpenReview: https: // openrevie.. net/ forum? id= 71 gAW
Abstract
The goal robust constrained reinforcement learning (RL) to optimize an agent's per- formance under the worst-case model uncertainty while satisfying safety or resource con- straints. In this paper, we demonstrate that strong duality does not generally hold in robust constrained RL, indicating that traditional primal-dual methods may fail to find optimal feasible policies. To overcome this limitation, propose novel primal-only algorithm called Rectified Robust Policy Optimization (RRPO), which operates directly on the primal problem without relying on dual formulations. We provide theoretical convergence guaran- tees under mild regularity assumptions, showing convergence to an approximately optimal feasible policy with iteration complexity matching the best-known lower bound when the uncertainty set diameter controlled in specific level. Empirical results in a grid-world environment validate the effectiveness of our approach, demonstrating that RRPO achieves robust and safe performance under model uncertainties while the non-robust method can violate the worst-case safety constraints.
1 Introduction
In many practical reinforcement learning (RL) applications, is critical for an agent to not only maximize expected cumulative rewards but also satisfy certain constraints, such as safety requirements (Yao et al.
2024
Gu al. 2024b) or resource limitations (Wang al. 2023c). However, real-world environments often
diverge from the training environment due to model mismatch (Roy et al. 2017 Viano et al. 2021 Zhai et al.
2024
Wang et al. 2024 and environment uncertainty (Lütjens et al. 2019 Wang & Zou 2021 Ma et al.
2023
Such discrepancics can lead to significant performance degradation and, more severely, violations
of constraints, which is unacceptable in safety-critical applications. For instance, an autonomous robot may encounter unforeseen transitions due to equipment aging or mechanical failures: In the environment navigation and the robust control tasks, the robot make take the action that perform better in the idcal simulated environment due to the ideal equipment condition but suffer high penalty from higher energy cost unexpected operations in the worst-case scenario.

---

Published in Transactions on Machine Learning Research (08/2025)
Despite its practical importance, robust constrained RL has been relatively underexplored in the literature. Two closely related areas are robust. RT. (Bagnell et al. 2001; Nilim & Ghaoui 2005 Tyengar 2005 and constrained RL (Altman, 1999 Wachi & Suij 2020). Robust RL focuses on optimizing performance under model uncertaintics but typically does not consider constraints. Constrained RL aims to optimize perfor- mance while satisfying certain constraints but often assumes a fixed environment without uncertainties. Scamlessly combining two fields presents inherent challenges.
To address these challenges, we propose a framework for robust constrained RL under model uncertainty. Specifically, consider Markov Decision Processes (MDPs) where the transition dynamics are not fixed but lie within an unccrtainty set, which is commonly known as the robust MDPs (Mannor et al., 2016 Ho et al.) 2018 Tamar et al., 2013 Grand-Clément & Kroer 2021). Our objective is to optimize the worst- case cumulative reward over this uncertainty set while ensuring that all constraints are also simultaneously satisfied in the worst-case scenario. This robust approach ensures that the agent's policy remains effective and safe even when the environment deviates from the nominal model.
A common approach to solving such constrained problems is the primal-dual method (Altman
1999 Pater-
nain et al. 2019 Bai et al. 2022 Liang et al. 20118 Chen & Wang] 2016 Mahadevan et al.) 2014 Chen et al, 2022), which leverages the strong duality property to efficiently find optimal policies. Strong duality allows the original constrained problem to be solved by considering its dual problem, simplifying computations and enabling convergence guarantees. However, a crucial question arises:
Q1: Does strong duality hold in robust constrained RL?
In this paper, we address this question head-on. We first demonstrate that, unfortunately, strong duality does not generally hold in robust constrained R.L. The presence of model uncertainties breaks the Fenchel-Moreau condition, the common routine of showing the strong duality in the non-robust constrained RL (Altman 1999). We construct specific counterexample where the duality gap, the difference between the optimal values of the primal and dual problems, is strictly positive. This finding indicates that traditional constrained RL algorithm may fail to be directly generalized to the robust constrained setting; we also note that the non-zero duality gap does not exclude the potential global convergence of primal-dual algorithm. Recognizing this fundamental issue, we are motivated to ask the following question:
Q2: Can we develop non-primalldual algorithm for solving robust constrained RL problems with provable convergence guarantees?
To address this question, we introduce the Rectified Robust Policy Optimization (RRPO), a primal-only algorithm adapted from the CRPO (Xu al. 2021). RRPO is specifically designed for robust constrained RL, which bypasses the issues associated with the duality gap. Our algorithm operates directly the primal problem, ensuring constraint satisfaction and robustness without relying on dual formulations or strong duality assumptions. We summarize our key contributions as follows:
1. Counterexamlle--None Non-Zero Duality Gap: In Section 3 we provide a concrete example showing that strong duality does not hold in robust constrained RL. To the best of our knowledge, this negative result is the first theoretical example showing the non-zero duality gap in the existing literature, which resolves an open problem in constrained robust RL. We emphasize that establishing such a counterexample is nontrivial and crucial for understanding the theoretical boundaries of constrained robust RI.
2. Proposed Primal-Only Algorithm-RRRee robust RL problems, we introduce RRPO, a primal-only algorithm designed to solve robust constrained RL. problems without relying on strong duality. Moreover, in Section 4 we rigorously analyze the convergence properties of RRPO. Specifically, we prove that under appropriate conditions, RRPO converges to an approximately optimal feasible policy n¹ within a specified tolerance in the worst-case scenario. When the uncertainty set is sufficiently small, our derived convergence rate and itcration complexity also recover the best-possible lower bound for non-robust constrained RL problems (Vaswani et al. 2022
Motivated by the lack of strong duality of constrained
3. Empirical Validation: We validate the effectiveness of RRPO through experiments in a grid-world environment and the classical mountain car environment. Our results show that RRPO achieves robust
2

---

Published in Transactions on Machine Learning Research (08/2025)
and safe performance under model uncertainties, outperforming the original CRPO method that may fail to maintain constraint satisfaction in the worst-case scenario.
1.1 Related Work
Robust Constrained RL Here, we mainly explore the existing literature regarding robust constrained RL. In Appendix [A.1] we provide other related work. Robust constrained RL considers the problem of optimizing performance while satisfying constraints in the worst-case scenario. Although robust RL and constrained RL have each been extensively studied, fewer works address their intersection. In Russel & Petrik (2020). the authors investigate robust constrained RL and propose a heuristic approach that estinates robust value functions and employs a standard policy gradient method (Sutton et al. 1999), substituting the nominal value function with the robust one. However, as Wang et al. (2022) points out, this approach overlooks how the worst-case transition kernel depends on the policy, resulting in updates that do not correspond to actual gradients of the robust value function and thus lack theoretical convergence guaranlees. To remedy this, Wang et al. (2022) introduces a robust primal-dual algorithm for solving robust constrained RL problems. However, this method assumes the strong duality, which we will show later, generally does not hold in robust constrained RL. Several other studies also examine the strong duality of robust constrained RL problems:
Chosh (2024) points out that the standard routine in proving the strong duality of constrained RT problems [Panaganti & Kalathil 2022) cannot hold in the robust case. ZZhang et al. (2024) proves the strong duality by considering a different policy space, which is different from the space considered in Paternain et al. (0019)
We include further discussion on it in Appendix A.2 Complementing these works, [e et al. (2025) tackle the
online distributionally robust off-dynamics setting, and present the ORBIT algorithm that attains sublinear
regret with matching upper and lower sample-complexity bounds under general f-divergence uncertainty sets.
The uncertainty set captures the discrepancy between training and deployment environments. In our work, we mainly focus on the (s, rrecccnguul uncertainty set [Lyengar 2005 Nilim & Ghaoui 2005), where the transition uncertainty is modeled independently for each state-action pair. As shown by Lu et al. (2024); Kumar et al. (2023); ; Wang et al.] (2023a); Wang & Zou (2021), this structure induced by a specific norm or divergence usually enables efficient solution methods through robust value iteration and linear programming, preserving the tractability of dynamic programming. While our work is also potential to be extended to other settings when valid robust policy evaluation algorithm presents, including:
s- s-Uncertainty Sets The s-rectangular uncertainty set (Li et al. 2022
Kumar et al. 2023 relaxes independence by allowing nature to choose transitions jointly across all actions at given state. The widely known results include the robust policy gradient formula (Li et al.) 2022 and the closed-form solution for p-norm uncertainty sets (Kunar et al. 2023 These results make it possible to solve the robust value function more efficiently.
Li & Shapiro. 2023
d- d-Uncertainty Sets More recently, the d-rectangular uncertainty set (Ma et al. 2022) has been proposed for lincar MDPs to further generalize the existing concopts of (s, a)-roctangular uncertainty sets, where the ambiguity is structured in a low-dimenssonal decision space, enabling scalable robust value ileration high- dimensional settings. Representative works include Blanchet et al. (2023); ; Liu & Xu (2024a); Liu et al.) (2024g; Liu & Xu 2025). Remarkably, this setting has also been widely explored in the offline RL setting
Tang et al.) 2024 Liu & Xu 2024b). These results make it possible to extend our results potentially to be able to handle more complicated robust MDPs with the function approximation.
Additionally, we discuss our connection to other setting in the robust reinforcement learning and constrained reinforcement learning.
Robust RL with Reward and State Uncertainty Modern robust RL fackles misspecified or learned rewards by optimizing worst-case or risk-aware returns. Early formulations blending nominal and worst-case objectives (Xu & Mannor) 2006 Delage & Mannor 20100) have been extended by coupling-aware uncortainty sets that avoid excessive conservatism (Mannor et al., 2012).. Recent work uses Bayesian reward ensembles and CVaR objectives for preference-based RL.FF settings, giving reliability under noisy learned rewards
3

---

Published in Transactions on Machine Learning Research (08/2025)
[Brown et al. 2020 Newest advances address uncertainty inside the reward or state signal itself. Seeing- is- --Nootneeliving RSC-MDPs explicitly model spurious correlations in the slate and learn policies robust to such confounding (Ding et al. 2023). Mirror-Descent inverse RL adds robustness directly to the learned reward via adversarial mirror steps with O(1/T) regret (Han et al. 2022 Distributional Reward Estimation builds a reward-uncertaind, distribution whose risk-sensitive aggregal ion stabilises multi-agent training (Hul
et al. 2022). Morcover, robust MDPs cast dynamics error as zero-sum game; roctangular ambiguity sets
admit efficient robust DP with deterministic optimal policies (Lyengar 2005; Nilim & Ghaoui 2005 Follow-
ups loosen rectangularity to retain tractability while reducing pessimism (Wiesemann et al.
2013
Goyal &
Grand-Clement, 2023). Practical algorithms combine adversarial disturbances or domain randomization with
policy learning to harden policies against dynamics shifts (Pinto et al. 2017).
RL with Hard Constraints CMDP theory guarantees optimal stationary policies and LP or primal-dual solutions (Altman 1999 Borkar 2005). Deep RL implementations such as CPO (Achiam et al.) 2017 and RCPO (Tssseer et al. 2019) enforce budget safety limits during learning. Runtime shielding synthesised from temporal-logie specifications now guarantees safety even under partial observability (Carr et al. 2023
Quantile-Constrained Constrained RL enforces uutage-probabiliy bounds by constraining the cost distribution' 's tail rather than its expectation (Jung et al. 2022). Trust-Region Safe Distributional Actor- Critic simultaneously handles multiple constraints with distributional critics and provable convergence (Kim et al. 2023). Model- predictive safety filters based on learned control-barrier functions enforce hard stale constraints in unknown stochastic systems while optimizing performance (Wang al.) (023b). Together these methods wrap (or jointly train) base policies to guarantee constraint satisfaction without relying soft penaltics.
Safe RL Safe exploration confines learning to recoverable states (Moldovan & Abbeel 2012) or certified Lyapunov safe sets (Berkenkamp et al. 2017). Action-level intervention layers correct unsafe commands on the fly (Dalal et al. 2018a), while risk-sensitive criteria such as CVaR directly penalize catastrophic tails (Chow al. 2018ap. These threads, alongside recent hard-constraint and shiclding techniques above, provide complementary, constraint-respecling alternatives that our revised Related- Solkted-WWork section now covers.
Robust Constrained Multi-Agent Systems An important extension of robust constrained RL is its application to multi-agent settings. The concept of robustness has been generalized to multi-agent reinforce-
ment learning (MARL) (Zhang et al. 2020 Ma et al. 2023 Jiao & Li 2024 particularly in addressing state uncertainty (He et al. 2023a Han et al. 2024). Notably, He et al. (2023b) were the first to jointly consider robustness and constraints in real-world scenario, proposing the ROCOMA algorithm, which achieves effi- cient EV rebalancing under transition kernel uncertainty. Many topics in constrained robust MARL remains unexplored, making it promising direction with significant polential for further research.
2 Preliminaries and Problem Formulation
In this section, we formalize our problem setting in the context of online robust constrained RL, where the transition probabilities are unknown. We re-use existing robust policy evaluation algorithm to estimate the approximate value function.
2.1 Robust MDPs
A Robust Markow Decision Process (Robust MDP) is defined by the tuple (8,A,P,r,,) where S is a finite state space, A is finite action space, P represents the uncertainty set of transition probabilities with A(S) denoting the probability simplex over S, S x A + R is the reward function, E [0, 1) is the discount factor. We denote μ E A(S) as the initial state distribution.
In an robust MDP, the transition probabilities are not fixed but belong to an uncortainty set; usually, the uncertainty set P is defined as the s-rectangular set (Derman el al. 2021 Wang el al., 2023a Wiesemann
et al. 2013 Kumar al. 2023)
:= XseSPsr
4

---

Published in Transactions on Machine Learning Research (08/2025)
rectaneeaa set (Wiesemann et al
2013 Kumar et al. 2023
p A (s,.a)
Here, instead of assuming a specifie type of uncertainty set as in many existing literature (Wang & Zou 2021 Wang et al. 2022), we work on general uncertainty sets but simply assume that the robust value function over these uncertainty sel is computationally available. Notably, for many well-known uncertainty sets, such as the p-norm (Kumar et al. 2023). IPM (Zhou et al. 2024),, and R-contamination (Wang & Zou, 2021 uncertainty set, the robust value function can be efficiently calculated without hurting the sample complexity.
Let the policy - A(A) map each state to probability distribution over actions. In robust RL, the robust value function (*))) under policy ı starting from state is defined as the worst-case expected discounted cumulative reward:
(T(()) inf E PEP
Σ rr(ss, ar)
80 =
where the expectation is taken over the trajectories generated by following policy n, with a ~ x(- st) and 8++1 P( St, ae) for e P. The objective is to find optimal policy x² that maximizes the worst-case expected cumulative reward from the initial state distribution
v (n) max V (N),
where V Baa (s)]-
2.2 Robust Constrained MDPs
In many applications, is essential optimize the reward while satisfying certain constraints, even under model uncertainty. Constrained robust MDPs (Wang al.) 2022 Zhang al. 2024 Sun al. 2024 Ghosh
2024 extend the robust MDP framework by incorporating multiple constraints.
Let there be constraint reward functions S A - IR for i = 1,2,... .... The robust expected cumulative reward under policy π for constraint i is given by:
(s) = inf ET.P PEP
Σ ('rs(s), 80 =8
and = (V the robust expected cumulative cost from the initial distribution μ..
The constrained robust. MDP aims to find a policy that maximizes the worst-case reward while ensuring that each constraint is satisfied under the worst-case transition dynamics:
max (H)
(1)
s.t. (²")) d,, for = 1,2......
where Vgr (μ)) denotes the robust expected cumulative reward, and d, are the specified thresholds for the constraints. That is, a constrained robust MDP is defined by the tuple (S,A, (r) (dH(=:))) where (ri)_ and (d+) extend the original robust MDP to include these constraint reward function r; and the threshold d,.
2.3 Duality Gap of Robust Constrained MDPs
In constrained optimization, the concept of duality plays pivotal role formulating and solving problems (Boyd& & Vandenberghe, 2004; Bertsekas et al., 2003). The duality gap the difference between the optimal values of the primal problem and its dual. When this gap is zero, we say that strong duality holds, allowing the
5

---

Published in Transactions on Machine Learning Research (08/2025)
primal and dual problems to have the same optimal value. This property is instrumental in many optimization algorithms, particularly in convex optimization, where it enables efficient computation of optimal solutions via dual methods. For the constrained robust MDP defined earlier, we incorporate the constraints into the optimization objective, formulating the Lagrangian of the constrained robust RMDP. The Lagrangian combines the objective function and the constraints using Lagrange multipliers À = (A1, 22,..., ,,) 2 0:
- (1) Σ Vd
(2)
In this formulation, [(T, is the Lagrangian function, and X 2 0 are the Lagrange multipliers associated with the constraints. The primal problem is defined by maximizing over म, after minimizing the Lagrangian over X 2 0. That is,
max min A). A20
The dual problem is then obtained by minimizing the Lagrangian over À 0, after maximizing over m Specifically, the dual problem is:
min max L(T,
(4)
The duality gap F is defined as the difference between the optimal value of the primal problem and the optimal value of the dual problem.
Definition 2.1 (Duality gap of robust constrained MDPs). Let M == (S,A,P, PrAri (d:1/21 7) be robust constrained MDP. The duality gap I of M is defined as
g max min C(T, .1] A20
min max max A20
(5)
where the Lagrangian function of M defined by Equation (2)
Tt has been widely known that, in standard constrained MDPs without robustness considerations, under certain regularity conditions, strong duality holds (Altman 1999). This means that the duality gap 2 is zero, and the optimal value of the primal problem equals that of the dual problem. This properly allows to use primal-dual algorithms effectively to find optimal policies that satisfy the constraints. However, in the next section, we will show that the constrained robust MDPs may not have such nice property, which presents a significant challenge for solving coistr robust RL problems.
3 Constrained Robust RL Has Non-Zero Duality Gap
In this section, we present counterexample demonstrating that the duality gap in robust constrained MDPs (Definition 2.1 can be strictly positive.
Theorem 3.1. There erists a constrained robust MDP such that ils duality gap is strictly positive.
Here, we describe the construction of this counterexample. Then we will briefly describe the analysis of the duality gap. The full proof can be found in Appendix B
3.1 Construction of the Counterexample
Consider simple MDP with two states, so and 81, and two actions, ap and ai, depicted in Figure The MDP is defined as follows: (i) Transitions: The initial state is sp- From state $1, any action deterministically transitions back to state sp. From state so, action do deterministically remains in so- From state Sp, action 01 transitions to with probability p and to with probability 1 p. (ūi) Robustness: There is model uncertainty in the transition probability such that p E [p. pl, representing the uncertainly set. (iii) Reward: The reward function for the objective is ro(sp) = and ro(s1) = The reward function for the constraint is ri (sp) = and (s,) 1. (iv) Constraints: The goal is to maximize the expected cumulative reward of ru while ensuring that the expected cumulative reward of r1 meets specified threshold p under the worst-case transition probabilities.

---

Published in Transactions on Machine Learning Research (08/2025)
(a) Transitions under action dg
(b) Transitions under action d1
1
1
1
So
1
p
So
S
1
The transition diagram of the MDP considered in Theorem 3.1 At state 81, the agent always moves to state &p with probability 1, regardless the action taken. At state 8p, the agent has a probability of staying in the current state when taking action aj, and a probability taking action au- The uncertainty only occurs in the transition probability p; we let it vary from [p.P].
Figure 1:
of staying in state so when
3.2 Analysis of the Duality Gap
The robust control problem can be formulated as:
max V0T (8p)
(6)
s.t. (s0) 2p.
(7)
where (so) denotes the worst-case value function for reward r; starting from state sp.
The associated Lagrangian is:
7 -D) 77) 2 10 1 1 p) - -22)
C(T, A) Vo 1(p ViT) = x m1 - 2 - 72)
with A 2 where क == so))
We proceed to analyze the Lagrangian function and compute the duality gap by evaluating both the primal and dual formulations:
Primal Problem The primal optimization problem given by Equation 3 aims to find the policy æ that maximizes Vi (sv) while satisfying the constraint Here, we directly solve it and obtain
- 1 P
max min L(T,A)
1-7 1 1- 1-p(1-11) 7) p(1 -
1 1
Dual Problem The dual problem given by Equation (4 involves minimizing the Lagrangian over À 2 0 for fixed policy म, and then maximizing over æ. The lack of convexity in the robust setting leads a discrepancy between the solutions obtained from the primal and dual problems.
1- 1-p1+ (1-
min max L(=, 1-7 1 1 1 1 (1 p)7
It can be obviously observed that when the robustness is absent (i.c. == p). the primal problem presents the same value the dual problem.

---

Published in Transactions on Machine Learning Research (08/2025)
Algorithm 1: Rectified Robust Policy Optimization
Input initial policy parameters Bo, empty set No
for t == 0..... T do
// Robust Policy Evaluation (e.g. Algorithm 2
Evaluate value functions under %t == Te. (x,a) & Q (s, for == 0.......
Sample state-action pairs (sj, aj) from the nominal distribution;
Compute value estimates V. for == I
if V. 2 d, - for all i 0, .,... then // Threshold Updates
Add 0, to set No and track the feasible policy achieving the largest value Fout K55
Update dn: d/- + V
else if V. <d; - for some i 1...... then
11 Constraint Rectification
Maximize V using Equation (80
else if Vith < do 8 then
// Objective Rectification Maximize V using Equation
return: Tout
Demonstration of the Duality Gap By selecting values for the parameters (e.g., 0.5, 0.25, 0.75, 0.5, and p 1), we can compute the exact values of the duality gap:
21
max min L(T, A) min max [(x, A) 22
A20
A20
As the result, the strong duality does not generally hold for robust constrained MDPs.
Implications of a Non-Zero Duality Gap We have just presented counterexample showing that strong duality does not generally hold in robust coistrained MDPs, which resolves an open problem regarding the strong duality robust constrained RL problems, highlighting the importance of designing solution methods that do not rely solely on duality. In the subsequent sections, we address these challenges by proposing the primal-only approach, RRPO.
4 Solving Robust Constrained RL with Unknown Transition Kernel
The lack of strong duality robust constrained RL presents significant challenges for traditional primal-dual optimization methods. The presence of non-zero duality gap means that these methods may fail to find feasible and optimal policics in robust constrained settings. To overcome this obstacle, develop a primal- only algorithm specifically designed for solving robust constrained RL with unknown transition kernel, which we call RRPO.
4.1 Algorithm Design
Given the primal optimization problem:
max Vi(())
s.t. VT" 2 d;, for 1,2,..
Here, we note that all V (1=0,1, 0, represent the robust value functions; when 0, we call V the objective value function, while when + 0, we call V7 the constraint value function. The core concept of the CRPO algorithm (Xu et al. 2021 is to iteratively update the policy by taking gradients with respect

---

Published in Transactions on Machine Learning Research (08/2025)
Algorithm 2: Robust Linear Temporal Difference (Zhou et al. 2024
Input policy x, number of steps K, value function approximation V. 26.
Initialize: wo, 80; for k = O.. do
Sample action ag x(. 8k);
Sample transition batch ye++1 according to the nominal kernel Po ax);
// For IPM estimator: Zhou et al.p 2024)
Update wk+1 & we + an (ss) (n(sk) ax) + VVu, (Ux+1) 26.1 (sx) [[as)
return WK
to either the objective function or the constraints, depending on whether the current policy violates any constraints:
If the constraint V (i = 1,2,...... .). is violated, then the CRPO algorithm updates the violated constraint value function Vi",
If all constraints are not violated, then the CRPO algorithm updates the objective value function Vç
However, when constraints are near their boundarics, this method can lead oscillations, making difficult to track the performance of feasible policies and potentially resulting in unsafe policy outcomes when the model uncertainty presents. As the result, the algorithm cannot "remember" the highest objective value achieved by the feasible policy. To mitigate these limitations, our RRPO algorithm adopts a reformulated approach. Rather than following the standard CRPO routine, we leverage the constrained form of the original optimization problem to employ the CRPO algorithm as follows. We reformulate it into the following constrained maximization problem by introducing an auxiliary variable do:
max
do
do.7
s.t.
V (p) 2 do-
VT 2 di, for i = 1,2,...1.
At each iteration, the algorithm evaluates the robust value functions V for all i = 0, 1,,1,... J. Based on these evaluations, the algorithm proceeds one of three categories:
1. Threshold Updates: If the current policy satisfies all constraints within specified tolerance 8 (that is, V.a 2 de - for 0,1,...,7) I), the algorithm updates the boundary Uhreshold by setting do <- Vi"h (n).
2. Constraint Rectification: any constraint is violated beyond the tolerance (that is, there exists = I,, V.T (4) > d; - 8), the algorithm performs policy improvement steps to maximize the violated constraint, aiming to reduce constraint violation.
3. Objective Rectification: If the objective value VØ*((4) is less than the current best boundary threshold du 6, the algorithm performs policy improvement steps to recover the objective value.
This procedure ensures that the policy maintains pursuing the feasibility while making progress towards optimizing the objective function. This procedure is summarized Algorithm [
Robust Policy Evaluation Subroutine We consider the robust policy evaluation subroutine as a mod- ular component decoupled from policy optimization. This procodure estimates the Q-function used in the natural policy gradient update. At each iteration, the agent interacts with the environment under the current policy collect trajectories consisting of (s, tuples. These samples used to estimate the robust

---

Published in Transactions on Machine Learning Research (08/2025)
Q-function (s, a) for both the objective (i=00 0) and each constraint (i (i= 1,...,
For value approxima- tion, we adopt robust lemporal-difference (TD) learning methods tailored to the chosen uncertainty model (e.g., p-norm or IPM uncertainty). Specifically, given à nominal transition model and an uncertainty set, we compute the worst-case expected value using closod-form solutions or dual formulations from prior work (e.g- Kumar et al. (2023): Zhou el al. (2024); Wang Zou (202T)) These robust Q-estimates are then used guide policy updates via natural policy gradient step. The data collection procedure incorporated with
I).
this subroutine is further described in the Algorithm [
4.2 Handling Uncertainty
In our proposed algorithm design, apply the robust natural policy gradient (Lemma 2, Zhou et al. 2024
to maximize the value function. The update rule of maximizing V (4) is given by
exp (nQ, (s.a)/(1-1) (1-
(+ti(als) n,, (als)
(8)
Z.
where the normalization factor Z, is defined as Z= E.EA (aaas) exp (n (sssa)a((19))) When consider- exp(6(s,a)) it is shown by Zhou et al. (2024) that this update ing the softmax parametrization me(als) Σ. exp(0(s.a')) rule equivalent to
(s4 ((( + 70"
(9)
where 0 is taken over SXA, Throughout this paper, we will use the parametric and policy representations interchangeably. In updating the policy, accurate ovaluation of Q. a) is critical. To achieve this, we decouple the robust value function evaluation from the policy optimization step. This modular design allows integrate existing robust RL methods for value function approximation effectively.
Below, we highlight several promising approaches for approximating the robust value function:
p-norm uncertainty set Kumar et al. 20231: :: For each state-action pair (s, a), define
U(,a) = {ue ( (u, 1) = 0, |ul 33.
Let. Po be the nominal transition distribution. probabilities are given by
Then the corresponding uncertainty sets for transition
P(s.a) = (Pol s,0) + E (()))))) and P ((..))e8xAPP P((aa)
(10)
As shown in Proposition 2.3 of Kumar et al. 2023), the standard TD-learning algorithm can be applied, with adding a correction term, to compute the robust value function under this p-norm uncertainty model.
The integral probability metric (IPM) uncertainty set (Zhou et al. 2024 Let F C R|S] be function class including the zero function. The IPM is defined dz(p.9) sup {p TT... The IPM uncertainty set is defined as
P(s.a) = Psxa dy(Psa: Po(-(s, a)) S $B. and P X(sa))SxAP(ee)>
Using the robust TD-learning algorithm (Algorithm 2, Zhou et al. 2024 ), we can compute an approximate robust value function 8.T (p). By leveraging the relationship between the robust value function and the robust Q-function (Proposition 2.2, Li et al. (2022)), ), along with the analytical worst-case formulation (Proposition 1, Zhou al. (2044) ) we can derive an approximate robust Q-function.
We acknowledge that other approaches also exist for approximating the robust Q-value function, such Wang et. al. (202aa) Sun al. 2024); omit these results due to the limited pages.
10

---

Published in Transactions on Machine Learning Research (08/2025)
4.3 Global Convergence Guarantees
In this subsection, we establish the global convergence guaranlee for RRPO under certain assumptions. Specifically, we assume: (1) The robust policy evaluation provides sufficiently accurate estimates. (2) Under the worst-casc sccnario, the policy still maintains sufficient exploration.
Assumption 4.1 (Policy Evaluation Accuracy). The approximate robust value functions Q7 (s, a) satisfy Q (8, - Q (s) & capprox for all 8 E S, E A, and i 0,....,.
This assumption of sufficient accuracy in policy evaluation is mild and is widely adopted in the existing reinforcement learning literature (Wang et al.) 2019 Cayci et al., 2022] Xu et al. 2021 Hong et al. 2023). As previously noted, this condition can be readily satisfied for specific uncertainly sets. We will discuss the value of Eapprox in the appendix.
Assumption 4.2 (Worst-Case Case Exploration). For any policy π and its worst-case transition P, there exists Pmin > such that its state visitation probability satisfies (s) Z Pmin for all s E S, where d is the state visitation distribution starting from initial distribution μ under policy and transition P.
Remark 4.3. This assumption imposes a uniform lower bound for all policies n; another widely accepted assumption made on the horie-n scenario (He et al. 2025), which adopt complementary requirement that caps the relative ro-weighting between nominal and adversarial dynamics. Exploring algorithms that retain our absolute-coveragy guarantee while accommodating the ratio-based perspective of He el al. (2025) is an interesting avenue for future work.
The exploration assumption can hold under appropriate exploration mechanisms, especially with classical exploration techniques e.g. the initial state randomization; instead of fixed initial state, we may use uniform distribution over the state space, ensuring the state visitation probability is always lower bounded.
Moreover, this assumption de facto weakens some existing assumptions; for example, Theorem 2 (Chen & Huang 2024] assumes there exists Puiin > 0 such that inf,,a.s' P(s'|s, a) 2 Pmin for all uncertainty transition P. Assumption (Zhou et al. 2024) assumes that the nominal transition is supported by transitions in the given uncertainty set. If we are given the access to the robust policy evaluation oracle (Assumption 4.1 these widely used assumptions could be replaced with requiring the exploration the worst-case transition instead of cach transition in the uncertainty set.
Assumption 4.4. The diameter of the uncortainty set is given
sup sipdiv(P((ss..) Sc.
P.P.EC s.a
This bounded-diameter condition restricts the variability of transition kernels within the uncertainty set. Intuitively, it ensures that all candidate models in C' are uniformly close to each other in terms of total variation distance, so the adversarial enviromment cannot deviate arbitrarily from the nominal dynamics. Such boundedness assumptions are standard in robust RL and are used by Ma et al. (2023) serving as a mild regularity condition to ensure well-posedness of the optimization problem.
Our main theoretical result is as follows. Here, we present simplified version to highlight the most critical components, including the convergence rate and sample complexity. The detailed upper bound is provided in Appendix C
Theorem 4.5. Consider the NPG update rule Equation S with the learning rate 17 O ()) Let the constraint violation tolerance 5 0 ) ) and the approrimation error Capprox = O / Under these conditions, there erists an iteration T such that the output policy nout salisfies
1 )+((c),
([V*()) V= 0
VT
where V* = V² for the optimal feasible policy Tt and
max dd - (m)) s 6.
11

---

Published in Transactions on Machine Learning Research (08/2025)
Remark 4.6. Compared to Kitarnura et al. 2025 which achieves complexity of O(c=4) for exact conver- gence, our results establish faster rate of O(e-2), up to an additional constant error determined by the uncertainty set diameter c. Specifically, our method converges to a neighborhood of the optimal policy, with the residual value error bounded by c. When e is sufficiently small (e.g., when the uncertainty set is chosen to be small), our approach yields a strictly faster convergence rale up to an additive O(c) lerm. The full version of Theorem 4.5 and the detailed proof are provided Appendix C
Discussion on the correction from the previous version of this work In our initial submission, we did not include the dependence on the uncertainty diameter in the upper bound. This oversight was identified through the OpenReview discussion (https:// cally, the problem arose because Lemma C.5 incorrectly upper bounded the advantage function when it takes negative values. In the currett version, we have addressed this issue by introducing Assumption 4.4 Using the proposed RRPO (Algorithm D there
Specifi-
constant gap lincarly depending on the uncertainty diamcter C, and cannot be closed for any less than this tolerance. Also, as indicated by Theorem 4 (Panaganti & Kalathil 2022), if only learnt using the nominal model, one can show that the policy will incur another constant cost. Hence, the algorithm that solves CMDP (and thus, the CRPO) should have the same bound for this given constant.
4.4 Discussion
to achieve e-accuracy to the optinal feasible policy n² up to constant error term depending on the uncertainty diameter it takes at most O(e-?) iterations. Here, we use a specific uncertainty set to illustrate how the O(c-t) sample complexity is obtained. Assume we are considering the (s, a) rerettaagal uncertainty set defined by the p-norm:
As shown in Theorem 1.5
U( = fu E R| | (u, 1) = 0, /ullp S 3}.
Let Po be the nominal distribution. Then
P(s.a)= == (Po(-Is, a) +u +ul u u and p: (A
are the uncertainty set we consider. At each step f, we learn an e-accurate robust Q-function, which takes 3 samples; this complexity is guaranteed by applying its Proposition 4.7, Kumar et al. (2023 to the standard TD-lcarning algorithm. Since Algorithm [ requires T = O iterations (to obtain an approximaled optimal policy up to a O(c)-level error) and the e-accurate policy evaluation requires K = O 2) samples, the total sample complexity is given by T K = O(e-4)
Comparison with Kitamura et al. (2025) While Kitamura et al. 2025 also employs constrained- form optimization framework (called the epigraph formulation), our approach is fundamentally different. (1) Their method updates the maximum constraint violation, while we adopt the original CRPO update rule with tracking the auxiliary parameter. (2) Their algorithm requires an additional binary search step, while our method preserves the simplicity of the CRPO framework without such overhead.
5 Numerical Examples
To better illustrate the impact of model uncertainty on the algorithm performance, especially on the worst- case feasibility,, conducted experiments comparing the proposed RRPO and the CRPO (Xu et al., 2021 For all experiments, used discount factor 7 0.99 and the 2-norm uncertainty set defined by Equa- tion 10
5.1 The FrozenLake-Lite Gridworld
First, we consider specific 4 6 FrozenLake- like gridworld environment: The agent starts from the left-top corner posstatt = [1, 1] and can make four actions,
A (UP, DOWN, LEFT, RIGHT),
12

---

Published in Transactions on Machine Learning Research (08/2025)
to move the target point poStarget [2.
Figure 2: Illustaaioon of two paths to the target in the grid-world environment. The shortest, path (Teft) prioritizes efficiency but risks violating constraints in slippery conditions, whereas the longer path (Right) always ensures safety in the worst-case scenario.
We define two reward functions. The main reward function ro defined as
+1
if s' is the target
ro(s,a,8)
-1 is a brown block
0.1 otherwise
It gives +1 for reaching the target, -1 for landing on brown block, and -0.1 otherwise. The constraint reward function ri is defined as:
if 8 is out of the boundary
01 -1 if s' is a brown block
otherwise
It assigns -1 for stepping out of the boundary onto brown block, and 0 otherwise, leading to cost VVT (μ) < 0.2, ensuring the agent avoids hitting brown blocks
function c(s, a) := -Erri as),, We require V or moves out of the boundary. The training environment is deterministic, where each action leads to the intended movement with probability one unless the agent hits a boundary or a brown block. When this happens, the agent's position is not changed (if it hits the boundary) or is reset to the starting position (if it hits the brown block). The test environment introduces "slippery" dynamic, where every move has a probability p of resulting in an unintended slip. This slippery setting mimics conditions that may not have been foreseen during training, effectively representing worst-case scenario. Under this sctting, the obstacles construct two distinct paths routing to the largel, which is illustrated in Figure 2
We apply our proposed RRPO to solve this constrained robust RL problem, comparing it with the baseline CRPO mothod. As shown in Figure 3a our method successfully learns the safer path, while the non-robust algorithm converges the shortest path.
5.2 Mountain Car
We also consider the classical Mountain Car environment from Gymnasium (Towers et al. 2024 to test the performance of the proposed RRPO in the classical control problem. We use default reward function ro. which penalizes -1.0 each step and rewards the agent reaches the goal; that is,
0 if the agent reaches the goal, otherwisc.
ro(s, a.
To emphasize safety, we add constraint reward function ri s') defined as
a1 {-1
if the car's speed exceeds 0.06.
otherwise.
It returns -1.0 whenever the car's speed exceeds 0.06 and returns otherwise, which encourages the agent maintain safe speed throughout its run. We also consider its cost description c(s,a) - (ni (8, s')]
13

---

Published in Transactions on Machine Learning Research (08/2025)
CRPO RAPO
OAPO
ROPO
KOPO
4000
CITO
CAPO
0300
31TO
FIPO
RP0
5kp
2000 1000 1O0
28mp
2000 T000 TOOL
204p
(a) Illustration of two paths to the target the grid- world environment. The shortest path (Teft) prioritizes efficiency but risks violating constraints slippery con- ditions, whereas the longer path (Right) always ensures safety the wosst-case scenario.
(b) Reward and cost comparison across nominal and worst-case transitions for the mountain car environment. the nominal environment, both algorithms learn the desired strategies to reach the goal; however, in the worst- case scenario, the RRPO algorithm can learn more robust strategy to avoid exceeding the speed constraint.
Figure 3: Reward and cost trajectories for CRPO and RRPO under nominal and worst-case transitions in Grid World (Figure 3a and Mountain Car (Figure 3b environments.
Saburt PC
0.45
8:42
0.29
6.32
Alper Ahr
3.30 0.5
0.35
1.50
2.00
0.50
3.50
Figure Comparison among our proposed RRPO algorithm and other robust RL baselines in the robust HalfCheetah environment (shown in the left panel). The standard robust policy gradient algorithm achieves the highest score but violates the energy constraint shown in the right panel. Within the given constraint, RRPO outperforms the primal-dual approach shown in the middle panel.
For the environment uncertainty, we perturb the "gravity" parameter of the Mountain Car environment. In the worst-case scenario, the gravity is increased from the nominal value 0.0025 to 0.003. The experiment results are shown in Figure 3b the proposed RRPO method receives much less cost the worst-case environment.
6 Extended Experiments: Robust Control
Additionally, we compare the performance of the RRPO algorithm with other robust RL basclines, including the robust policy gradient and the robust primal-dual policy gradient methods, on the HalfChoetah-vd environment from Robust Gymnasium (Gu et al. 2025 We also conduct ablation study to evaluate the
14

---

Published in Transactions on Machine Learning Research (08/2025)
impact of our modification the original robust CRPO algorithm, demonstrating that it effectively reduces oscillations near the constraint boundary. Although the Safety MuJoCo environment (Gu et al. 2024a), also available in Robust Gymnasium, offers benchmarks with hard safety constraints, its formulation requires additional adaptation to our setting. Therefore, we employ a custom energy constraint that penalizes energy consumplion al each step. We include the experiment details and the hyper-parameter setting Appendix D.4
6.1
Comparison with Other Robust RL Algorithms
We conducted a comparative evaluation three robust RL algorithms on the HalfCheetah-v4 euvironment from Robust Gymnasium (Gu et al., 2025): (i) Robust Policy Gradient. (ii) Robust Primal-Dual Policy Gradient. (iii) Our proposed RRPO algorithm.
The agent learns to maximize forward locomotion speed while respecting energy consumption constraints. The reward function follows the standard HalfCheetah formulation:
ro(s, a) = forward velocity - 0. 0.1||a|²,
encouraging rapid forward movement while penalizing excessive control ellort. Crucially, we implement a separate energy constraint defined the squared L2 norm of the action vector
(s, ||a/|
with threshold of -0.25 (note that this threshold is applied to the value function instead of the current step cost; it does not apply to the constraint cost shown in Figure 3 We include the detailed hyper-parameter setting in Appendix D.4
6.2 Ablation: Robust CRPO Algorithm
In the ablation experiment, we compare our RRPO algorithm with the Robust version of CRPO algo- rithm (that is, we replace the value function used in the CRPO algorithm with the robust value function). The only difference presented here is the rectification mechanism used Algorithm [ where the RRPO algorithm tracks the best feasible policy as the Tout in the threshold update step. We follow the same setting described in Appendix DD.4. To compare both methods, we evaluate the variance of the primal reward of the output policy. In the RRPO algorithm, this variance primarily stems from inherent randomness in the policy and environment. In CRPO, however, additional source of variance arises from the random sampling of the output policy. As a result, CRPO exhibits substantially higher variance than RRPO.
AAPO
CRPO
llwaar Standard Desiatio
300
200
1.00
0
Step
Figure 5: Comparison of the variance of the primal reward ro of the output policy from CRPO Xu et al, 2021) and the RRPO (Algorithm 1 The CRPO method exhibits substantially higher variance than RRPO.
15

---

Published in Transactions on Machine Learning Research (08/2025)
7 Conclusion
In this paper, we investigated robust constrained RL problems and demonstrated that strong duality generally DOES NOT hold in this setting, thereby limiting the effectiveness of some methods which rely on the strong duality. To address this challenge, we introduced RRPO, a primal-only algorithm that directly optimizes the policy while rectifying constraint violations without relying on dual formulations. Our theoretical analysis, under mild boundedness and exploration assumptions, provided convergence guaranlees for RRPO, ensuring that it converges an approximately optimal policy up to a Occ)-eevl value function error that satisfies the constraints within specified tolerance under worst-case scenarios. Empirical results validate the effectiveness of our approach. We believe our work opens avenues for exploring and designing non-primal-cual approaches to solve robust constrained RL problems, and potentially leads to an interesting direction to identify when the strong duality of robust constrained RL holds.
References
Joshua Achiam, David Held, Aviv Tamar, and Pieter Abbeel. Constrained policy optimization. In Proceedings of the 34th International Conference Machine Learning (ICML), pp. 22 31, 2017.
Eitan Altman. Constrained Markov Decision Processes. CRC Press, 1999.
Kavosh Asadi, Shoham Sabach, Yao Liu, Omer Gottesman, and Rasool Fakoor. Td convergence: An opti- mization perspective. Advances in Neural Information Processing Systems, 36, 2024.
J. Andrew Bagnell, Andrew Y. Ng, and Jeff G. Schneider. Solving uncertain markov decision processes. Technical Report CMU-RI-TR-01-25, Carnegie Mellon University, 2001.
Qinbo Bai, Amrit Singh Bedi, Mridul Agarwal, Alec Koppel, and Vaneet Aggarwal. Achieving zero constraint violation for constrained reinforcement learning via primal-dual approach. In Proceedings of the AAAI Conference Artificial Intelligence, volume 36, pp. 3682 3682-3689, 2022.
Felix Berkenkamp, Matteo Turchetta, Angela P. Schoellig, and Andreas Krause. Safe model-basee rein- forcement learning with stability guarantees. In Advances Neural Information Processing Systems 30 (NIPS), pp. 908 919, 2017.
Dimitri P. Bertsokas, Angelia Nedic, and Asuman E. Ozdaglar. Conver Analysis and Optimization. Athena Scientific, Belmont, MA, 2003. ISBN 1886529450.
Jose Blanchet, Miao Lu, Tong Zhang, and Han Zhong. Double pessimism provably efficient for distribu- tionally robust offline reinforcement learning: Generic algorithm and robust partial coverage. Advances in Newral Information Processing Systems, 36:66845-66859, 2023.
Vivek S. Borkar, An actor-critic algorithm for constrained Markov decision processes. Systems & Control Letters, 54(3):207-213, 2005.
Stephen Boyd and Lieven Vandenberghe. Convez Optimization. Cambridge University Press, Cambridge, 2004. ISBN 9781316179512.
David Brandfonbrener and Joan Bruna. Geometric insights into the convergence of nonlinear td learning. arXiv preprint vrXio:1905 12185, 2019.
Daniel S. Brown, Scott Niekum, and Marek Petrik. Bayesian robust optimization for imitation learning. In Aduances in Neural Information Processing Systems 39 (NeurIPS), 2020.
Steven Carr, Nils Jansen, Sebastian Junges, and Ufuk Topcu. Safe reinforcement learning via shielding under partial observability. In Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI), 2023.
Semih Cayci, Niao He, and R Srikant. Finite-time analysis of entropy-regularizen neural natural actor-critic algorithm. Xixiv preprint ar Nix:2206.00833, 2022.
16

---

Published in Transactions on Machine Learning Research (08/2025)
Yichen Chen and Mengdi Wang. Stochastic primal-dual methods and sample complexity of reinforcement learning. ar Xrxiv preprint arXiv: 201116111111111 2016.
Ziyi Chen and Heng Huang. Accelerated policy gradient for s-rectangular robust mdps with large state spaces. In Forty-first International Conference on Machine Learning. 2024.
Ziyi Chen, Shaocong Ma, and Zhou. Finding correlated equilibrium of constrained markov game: A primal-dual approach. Advances in Neural Information Processing Systems, 85:25560-25577 2022.
Yinlam Chow, Mohammad Ghavamzadeh, Lucy Janson, and Marco Pavone. Risk-constrained reinforcement learning with percentile risk criteria. Journal of Machine Learning Research, 18:1-51, 2018a.
Yinlam Chow, Ofir Nachum, Edgar Duencz-Guzman, and Mohammad Ghavamzadeh. A lyapunov-based approach to safe reinforcement learning. In Advances in Newral Information Processing Systems, pp. 8092-8101, 2018b.
Gal Dalal, Krishnamurthy Dvijotham, Matej Vecerik, Todd Hester, Cosmin Paduraru, and Yuval Tassa. Sale exploration in continuous action spaces. In Proceedings of the AAAI Conference on Artificial Intelligence, 2018a.
Gal Dalal, Elad Gilboa, Shie Mannor, and Amnon Shashua. Safe exploration in contimuous action spaces. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pp. 2752- 2761, 2018b.
Erick Delage and Shic Mannor. Percentile optimization for Markov decision processes with paramcter un- certainly. Operalions Research, 58(1):203 213, 2010.
Esther Derman, Matthieu Geist, and Shie Mannor. Twice regularized mdps and the equivalence between robustness and regularization. Advances in Neural Information Processing Systems, 34:22274-22287 2021.
Dongsheng Ding, Shaofeng Zhang, Tianxing Zhang, and Liwei Wang. Natural policy gradient primal-dual method for constrained markov decision processes. In Advances in Neural Information Processing Systems, pp. 19138 19138-19148, 2020.
Wenhao Ding, Laixi Shi, Yuejie Chi, and Ding Zhao. Seeing is not believing: Robust reinforcement learning against spurious correlation. In Advances in Neural Information Processing Systems (NeurIPS), 2023.
Arnob Ghosh. Sample complexity for obtaining sub-optimality and violation bound for distributionally robust constrained mdp. In First Reinforcement Learning Safely Workshop, 2024.
Vineet Goyal and Julien Grand-Clement. Robust Markov decision processes: Beyond rectangularity. Moth- ematics of Operations Research, 48(1):203-22) 1208,-2222-22 2023.
Julien Grand-Clément and Christian Kroer. Scalable first-order methods for robust mdps. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 12086-12094, 2021.
Shangding Gu, Bilgehan Sel, Yuhao Ding, Wang, Qingwei Lin, Ming Jin, and Alois Knoll. Balance reward and safety optimization for safe reinforcement learning: perspective of gradient manipulation. In Proceedings of the AAAT Conference Artificial Intelligence, volume 38, pp.
2024a.
Shangding Gu, Long Yang, Yali Du, Guang Chen, Florian Walter, Jun Wang, and Alois Knoll. A review of safe reinforcement learning: Methods, thcories and applications. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2024b.
Shangding Gu, Laixi Shi, Muning Wen, Ming Jin, Eric Mazumdar, Yuejie Chi, Adam Wierman, and Costas Spanos. Robust gymnasium: unified modular benchmark for robust reinforcement learning. In The Thirteenth International Conference on Learning Representations, 2025. URL https://openrevies het:/Eorummiid222855a22444
17

---

Published in Transactions on Machine Learning Research (08/2025)
Dong-Sig Han, Hyunseo Kim, Hyundo Lee, JeHwan Ryu, and Byoung-Tak Tak Zhang. Robust imitation via mirror descent inverse reinforcement learning. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
Songyang Han, Sanbao Su, Sihong He, Shuo Han, Haizhao Yang, Shaofeng Zou, and Fei Miao. What is the solution for state-adversarial multi-agent reinforcement learning? Transactions on Machine Learning Research, 2024, ISSN 2835-8856. URL http::///pppaaoooeeeeeee/roroeoe
Sihong He, Songyang Han, Sanbao Su, Shuo Han, Shaofeng Zou, and Fei Miao. Robust multi-agent rein- forcement learning with state uncertainty. Transactions on Machine Learning Research (TMLR), 2023a. ISSN 2835-8856. URL
Sihong He, Yue Wang, Shuo Han, Shaofeng Zou, and Fei Miao. robust and constrained multi-agent rein- forcement learning electric vehicle rebalancing method in amod systems. In 2023 TEEE/RS) International Conference on Intelligent Robots and Systems (IROS), pp. 5637 5644. LEEE, 2023b.
Yiting Hc, Zhishuai Liu, Weixin Wang, and Pan Xu. Sample complexity of distributionally robust off- dynamics reinforcement learning with online interaction. In Forty-second International Conference Machine Learning, 2025. URL https://
Chin Pang Ho, Marek Petrik, and Wolfram Wiesemann. Fast bellman updates for robust mdps. In Interna- tional Conference on Machine Learning, pp. 1979 1988. PMLR, 2018
Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A two-timescale stochastic algorithm frame- work for bilevel optimization: Complexity analysis and application to actor-critic. SIAM Journal Optimization, 33(1):147-18))) 2023.
Linfang Hou, Liang Pang, Xin Hong, Yanyan Lan, Zhiming Ma, and Dawei Yin. Robust reinforcement learning with wassorstein constraint. arXie preprint arXiv:2006.00 00945, 2020.
Jifeng Hu, Yanchao Sun, Hechang Chen, Sili Huang, Haiyin Piao, Yi Chang, and Lichao Sun. Distributional reward estimation for effective agent deep reinforcement learming. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
Garud N. Tyengar. Robust dynamic programming. Mothematics of Operations Research, 30(2):257-20) 280. 2005.
Yuchon Jiao and Gen Li. Minimax-optimal multi-agent robust reinforcement learning. 2rXiv:24 12. 19873, 2024.
arXiv preprint
Whiyoung Jung, Myungsik Cho, Jongeui Park, and Youngehul Sung. Quantile constrained reinforcement learning: A framework constraining outage probability. In Advances in Newral Information Processing Systems (NeurIPS), 2022.
Dohyeong Kim, Kyungiae Lee, and Songhwai Oh. Trust region-based safe distributional reinforcement learning for multiple constraints. In Advances in Neural Information. Processing Systems (NeurIPS), 2023.
Toshinori Kitamura, Tadashi Kozuno, Wataru Kumagai, Kenta Hoshino, Yohei Hosoe, Kazumi Kasaura, Masashi Hamaya, Paavo Parmas, and Yutaka Matsuo. Near-optimal policy identification in robust con- strained markov decision processes via epigraph form. In The Thirteenth International Conference Learning Representations, 2025. URL https:// wwtp://ooummddddd5soeeaaa
Navdeep Kumar, Esther Derman, Matthieu Geist, Kfir Y Levy, and Shie Mannor. Policy gradient for rectangular robust markov decision processes. Advances in Neural Information Processing Systems, 36: 59477 59501, 2023.
Gen Li, Changxiao Cai, Yuxin Chen, Yuting Wei, and Yuejie Chi. Is q-learning minimax optimal? tight sample complexity analysis. Operations Research, 72(1):222
2222222--6--22 236, 2024.
18

---

Published in Transactions on Machine Learning Research (08/2025)
Yan Li and Alexander Shapiro. Rectangularity and duality of distributionally robust markov decision pro- cesses. orXiv preprint arXiv:2308. 1 11139, 2023.
Yan Li, Guanghui Lan, and Tuo Zhao. First-order policy oplimization for robust markov decision process. arXiv preprint (tff::200911577:0 2022.
Qingkai Liang Fanyu Que, and Eytan Modiano. Accelerated primal-dual policy optimization for safe rein- forcement learning. arXiv preprint arXiv:1802.06480 2018.
Shiau Hong Lim and Huan Xu. Reinforcement learning in robust markov decision processes. In Advances in Newral Information Processing Systems (NTPS), pp. 701-709, 2013.
Yunan Liu, Shaofeng Zhang, and Liwei Wang. Fast global convergence of policy optimization for constrained mdps. arviv preprint arXiv:2102.04 2021.
Zhishuai Liu and Pan Xu. Distributionally robust off-dynamics reinforcement learning: Provable efficiency with linear function approximation. In International Conference on Artificial Intelligence and Statistics, pp. 1719-2721 PMLR, 2024a.
Zhishuai Liu and Pan Xu. Minimax optimal and computationally efficient algorithms for distributionally robust oflline reinforcement learning. arxie preprinl urXi::2/03.09621, 2024b.
Zhishuai Liu and Pan Xu. Linear mixture distributionally robust markov decision processes. arXie preprint arXiv:2505. 18044, 2025.
Zhishuai Liu, Weixin Wang, and Pan Xu. Upper and lower bounds for distributionally robust off-dynamics reinforcement learning. arXiv preprint ArX:::2409.20 20521, 2024.
Miao Lu, Han Zhong, Tong Zhang, and Jose Blanchet. Distributionally robust reinforcement learning with interactive data collection: Fundamental hardness and near-optimal algorithm. arXiv preprint arXiv:2404.088 033578 2024.
Björn Lütjens, Michael Everett, and Jonathan How. Safe reinforcement learning with model uncertainty estimates. In 2019 International Conference on Robotics and Automation (ICRA), pp. 8662 8668. LEEE, 2019.
Shaocong Ma, Ziyi Chen, Shaofeng Zou, and Yi Zhou. Decentralized robust v-learning for solving markov games with model uncertainty. Journal of Machine Learning Research, 24(371):1-40, 2023.
Xiaoteng Ma, Zhipeng Liang, Jose Blanchet, Mingwen Liu, Li Xia, Jiheng Zhang, Qianchuan Zhao, and Zhengyuan Zhou. Distributionally robust. ofllnne reinforcement learning with linear function approximation. arXiv preprint Xio: 200.2200.0660, 2022.
Sridhar Mahadevan, Bo Liu, Philip Thomas, Will Dabney, Steve Giguere, Nicholas Jacek, Tan Gemp, and Ji Liu. Proximal reinforcement learning: A new theory of sequential decision making in primal-dual spaces. arXiv preprint 1405.1400.66 67577, 2014.
Shie Mannor, Ofir Mcbel, and Huan Xu. Lightning does not strike twice: Robust MDPs with coupled uncertainly. In Proceedings of the 29th International Conference on Machine Learning (ICML), 2012.
Shic Mannor, Ofir Mebel, and Huan Xu. Robust mdps with k-rectangular uncertainty. Mathematics of Operalions Research, 41 41(4):1484 1509, 2016.
Teodor Mihai Moldovan and Pieter Abbeel. Safe exploration in Markov decision processes. In Proceedings of the 29th International Conference on Machine Learning (ICML), 2012.
Arnab Nilim and Laurent El Ghaoui. Robust control of Markov decision processes with uncertain transition matrices. Operations Research, 53(5):780-775 2005.
Kishan Panaganti and Dileep Kalathil. Sample complexity of robust reinforcement learning with a generative model. In International Conference on Artificial Intelligence and Statistics, pp. PMLR, 2022.
19

---

Published in Transactions on Machine Learning Research (08/2025)
Santiago Paternain, Luiz Chamon, Miguel Calvo-Fullans, and Alejandro Ribeiro. Constrained reinforcement learning has vero duality gap. Advances in Neural Information. Processing Systems, 32, 2019.
Lerrel Pinto, James Davidson, Rahul Sukthankar, and Abhinav Gupta. Robust adversarial reinforcement learning. In Proceedings of the 34th International Conference on Machine Learning (TCML), pp. 2817- 2826, 2017.
Aurko Roy, Huan Xu, and Sebastian Pokutta. Reinforcement learning under model mismatch. Advonces in neural information processing systems, 30, 2017.
Nathan Russel and Marek Petrik. Robust musstraneed-mdps Soft-constrained robust policy optimization under model uncertainty. arXiv preprint arXiv20100048700 2020.
Jay K. Satia and Roy E. Lave Jr. Markovian decision processes with uncertain transition probabilities. Operations Research, 21(3):728-740, 1973.
Adam Stooke, Joshua Achiam, and Picter Abbecl. Responsive safety in reinforcement learning by pid lagrangian methods. International Conference on Muchine Learning, pp. 9133 9143, 2020.
Zhongchang Sun, Sihong He, Fei Miao, and Shaofeng Zou. Constrained reinforcement learning under model mismatch. In Forty-first International Conference on Machine Learning, 2024.
Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient methods for rein- forcement learning with function approximation. In Advances in Neural Information Processing Systems, volume 12, pp. 1057-1063, 1999.
Aviv Tamar, Huan Xu, and Shie Mannor. Scaling up robust mdps by reinforcement learning. arXiv preprint arXiv:1306.614 618,,689,, 2013.
Cheng Tang, Zhishuai Liu, and Pan Xu. Robust offline reinforcement learning with linearly structured f-divergence regularization. arXiv preprint 1rXiv:2411.18611 2024.
Chen Tessler, Danicl J. Mankowitz, and Shic Mannor. Reward constrained policy optimization. In Interna- tional Conference on Learning Representalions (ICLR), 2019.
Mark Towers, Ariel Kwiatkowski, Jordan Terry, John U Balis, Gianluca De Cola, Tristan Deleu, Manuel Goulão, Andreas Kallinteris, Markus Krimmel, Arjun KG, et al. Gymnasium: A standard interface for reinforcement learning environments. arXiv preprint 2rX 2024.
Sharan Vaswani, Lin Yang, and Csaba Szepesvári. Near-optimal sample complexity bounds for constrained mdps. Advances in Neural Information Processing Systems, 35:3110-3122, 2022.
Luca Viano, Yu-Ting Huang, Paramcswaran Kamalaruban, Adrian Weller, and Volkan Cevher. Robust inverse reinforcement learning under transition dynamics mismatch. Advances Neural Information Processing Systems, 34:25917 25931, 2021.
Akifumi Wachi and Yanan Sui. Safe reinforcement learning in constrained markov decision processes. In International Conference on Machine Learning, pp. 9797-9806. PMLR, 2020.
Lingxiao Wang, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural policy gradient methods: Global opti- mality and rates of convergence. arXiv preprint arXbv.999.001150, 2019.
Qiuhao Wang, Chin Pang Ho, and Marek Petrik. Policy gradient in robust mdps with global convergence guarantee. In International Conference on Machine Learning, pp.
PMTR, 2023a.
Yixuan Wang, Simon Zhan, Ruochen Jiao, Zhilu Wang, Wanxin Jin, Zhuoran Yang, Zhaoran Wang, Chao Huang, and Qi Zhu. Enforcing hard constraints with soft barriers: Safe reinforcement learning in unknown stochastic environments. In Proceedings of the 40th International Conference on Machine Learning (TCML), 2023b.
20

---

Published in Transactions on Machine Learning Research (08/2025)
Yue Wang and Shaofeng Zou. Online robust reinforcement learning with model uncertainty. Advances in Newral Information Processing Systems, $4:7193-72000 2021.
Yue Wang and Shaofeng Zou. Policy gradient method for robust reinforcement learning. In Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAT), pp. 144--440, 2022.
Yue Wang, Fei Miao, and Shaofeng Zou. Robust constrained reinforcement learning. arXiv preprint 22t.::22090066666 2022.
Yue Wang.
Zhongchang Sun, and Shaofeng Zou. A unified principle of pessimism for offline reinforcement learning under model mismatch. In The Shirty-eighhte Annual Conference on Newral Information Process- ing Systems, 2024.
Zhihai Wang, Taoxing Pan, Qi Zhou, and Jie Wang. Efficient exploration in resource-restritted reinforcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pp. (0279-1028) 2023c.
Wolfram Wiesemann, Daniel Kuhn, and Berç Rustem. Robust Markov decision processes. Mathematics of Operations Research, 38(1):153-11) 183, 2013.
Huan Xu and Shie Mannor. The robustness robustueess-erfformmace tradeoff in Markov decision processes. In Advances in Neural Information Processing Systems 19 (NIPS), pp. 1537-1544, 2006.
Tengyu Xu, Yingbin Liang, and Guanghui Lan. Crpo: new approach for safe reinforcement learning with convergence guarantee. In International Conference on Machine Learning, pp. 11480 11491. PMLR, 2021.
Lantao Yang and Chongjic Zhang. Projoction-based constrained policy optimization. In Advances Neural Informalion Processing Systems, pp. 12345- 12356, 2020.
Yihang Yao, Zuxin Liu, Zhepeng Cen, Jiacheng Zhu, Wenhao Yu, Tingnan Zhang, and Ding Zhao. Constraiin-coonditioned policy optimization for versatile safe reinforcement learning. Advonces in Neu- ral Information Processing Systems, 36, 2024.
Peng Zhai, Xiaoyi Wei, Taixian Hou, Xiaopeng Ji, Zhiyan Dong, Jiafu Yi, and Lihua Zhang, Robust proximal adversarial reinforcement learning under model mismatch. IEEE Robotics and Automation Letters, 2024.
Kaiqing Zhang, Tao Sun, Yunzhe Tao, Sahika Genc, Sunil Mallya, and Tamer Basar. Robust multi-agent reinforcement learning with model uncertainty. Advonces in neural information processing systems, 33: 10571-10583, 2020.
Zhengfei Zhang, Kishan Panaganti, Laixi Shi, Yanan Sui, Adam Wierman, and Yisong Yue. Distributionally robust constrained reinforcement learning under strong duality. Reinforcement Learning Journal, 4:1793- 1821, 2024.
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 information processing systems, 36, 2024.
A Further Discussions on Related Work
In this section, we include further discussions on existing literature include other closely related areas and clarification of existing results on the strong duality of robust constrained RL problems.
A.1 Other Related Work
In this section, further explore the two closely related areas: robust RL and constrained RI..
21

---

Published in Transactions on Machine Learning Research (08/2025)
Robust RL Robust reinforcement learning (RL) aims to develop policies that perform well under the worst-case transitions. Early works on robust RL primarily focused on model-based approaches, where the uncertainty set of transition probabilities is known or can be estimated, and robust policies are computed
using robust dynamic programming techniques [Bagnell et al.) 2001 Lyengar 2005 Nilim & Ghaoui 2005;
Satia & Lave Jr. 1973 Wiesemann et al. 2013 Lim & Xu 2013). These methods consider worst-case
scenarios over the uncertainty set to ensure robustness. In the model-free setting, robust RL algorithms have been proposed that do not require explicit knowledge of the uncertainly set but instead utilize samples to estimate robust value functions and policies (Roy et al., 2017 Wang & Zou 2021 Panaganti & Kalathil, 2022). These methods often involve solving a robust optimization problem over the estimated uncertainties. Recent theoretical advancements overcome the issues of dirrectl solving the worst-case transitions. [Wang & Zou (2022) considers the R-contaminationn model to obtain the unbiased estimator for the policy gradient method. Zhou et al. (2024) applies the double sampling method or the structure of the IPM uncertainty structure to obtain the unbiased estimation involving the worst-casc transition probability. And Kumar eet al. (2023) provides the analytical solution for the p-norm uncertainly set. These advancements allow
to directly obtain the robust policy gradient or the robut value function without estimating the worst-case transition probability,
Constrained RL Constrained reinforcement learning extends the standard RL. framework by incorporat- ing constraints into the agent's decision maaiing process, aiming to optimize performance while satisfying certain safcty, resource, or risk constraints (Altman, 1999). A widely used approach for solving constrained
RL problems is the primal-dual method (Paternain et al. 2019 Tessler el al. 2019 Liang el al. 2018: Slooke
et al., ) which leverages the strong duality property of constrained RL [Altman 1999) to formulate a Lagrangian that combines the objective function with the weighted constraints. These methods iteratively update the policy and the Lagrange multipliers, and convergence guarantees have been established under
certain conditions (Ding et al. 2020 Liu et al.) 2021). However, these methods rely on the assumption of strong duality, which may not hold in more complex settings. Alternative methods, known as primal meth- ods, enforce constraints directly by projecting policies onlo the feasible set or using safe policy improvement
techniques (Achiam et al. 2017 Chow et al.] 2018b Dalal et al.] 2018b; Xu et al.) 2021 Yang & Zhang, 2020 These methods aim to ensure constraint satisfaction without relying on dual variables.
A.2 Strong Duality in Robust Constrained RL Problems
In this section, we provide more detailed discussions in the existing literature discussing the strong duality in robust constrained RL problems.
In the existing literature, Ghosh (0024) provide an intuitive explanation for why existing primal-dual mot for non-robust. constrained RI problems could fail in robust case: In the standard routine of showing the strong duality (Paternain et al.] 2019 Altman 1999), the state visitation distribution d= is convex in the policy π,; that is, there always exists policy x such that (1 (1-a)d=::P +ad = d'',P. However, this relation obviously does not hold, which makes the strong duality of robust constrained RL problems unclear. Our counterexample offers a theoretical justification of this conjecture by providing a concrete example where the duality gap is strietly positive.
Additionally, Zhang et al. (2024) has proved the strong duality for robust constrained RL problems by employing the "randomization trick" that modifies the optimization problem's policy space. However, their results do not apply to our setting. Specifically, it doesn't consider the space of all random policies; instead, it only considers the distribution of deterministic policies. The choice of deterministic policy is made at the beginning of each round. This approach redefines the robust constrained RL problem to ensure strong duality, differing from the classical definition used in constrained RL (Altman 1999 Paternain et al. 2019 Our work, instead, aims to align with this classical definition, highlighting that without such extensions, strong duality may not hold.
As the result, existing literature has not addressed the critical question in the robust constrained RL prob- lems, which is what aim to solve in this paper.
22

---

Published in Transactions on Machine Learning Research (08/2025)
(a) Transition when taking the action do-
(b) Transition when taking the action on
1
1
1
SO
S1
p
So
S
1 1
At state S1, the agent always moves to state so with probability 1, regardless of the action taken. At state so, the agent has a probability of staying in the current state when taking action d1, and probability of of staying in state so when laking action dg- The uncertainly only occurs in the transition probability p; let il vary from [p,p].
Figure The transition diagram of the MDP considered in Theorem 3.1
Counterexample: Robust Constrained RL with Non- Zero Duality Gap
Proof. We divide the proof into three parts: (1) The construction counterexample constrained robust
MDP. (2) The evaluation of Lagrangian function. (3) The evaluation of the duality gap.
1. Construction of the constrained robust. MDP:
We consider the constrained robust MDP described in Figure (which the same as Figure I The nominal transition probability explicitly defined as follows:
P(so ag, so) 1,
P( do, 30) O,
P(so
01, 80) P,
P(81
81)80) = P.
P(sp
Qg, $1) 1,
P(s1 ag. $1) 0,
P(so 01,81) 1,
P(s1 81, 0.
Then we obtain the state transition probability induced by the policy
Ku + TiP 1 p)
p
where mo (aglss)) and (ai]so)) The action at the state doesn't make any differences. The (i, entry of p represents the probability of moving from 8j to 8; by following the policy n. We fix
the initial state to Its corresponding distribution is given by po
The reward for the objective
value function is rp
The reward for the constraint is
Here, we only consider a single
0
constraint.
Lastly, we consider the following (s, unccertiaty set defined by the Lao distance:
Vs {0), for (8, a) # (So, a1)
23

---

Published in Transactions on Machine Learning Research (08/2025)
V s0.01 {U R! (u, (ss) 0, llullo S/). Us = V3,a + P.
Given this uncertainty set, the value of p varies from p 5 to p + 6. Hcre, further assume that p is strictly less than 1, 8 < p, and p + 6 < 1. We denote p : + à and p p 6.
2. Evaluate the Lagrangian function:
Now evaluate the discounted visitation measure of the policy n.
Define the discounted visitation
[ - ( + TIP)
-7
measure as d== (I== No. Because I I-pp== =
where Ho the initial state
1T p)
distribution. Then we obtain
1 d = I - -- |
p) 1 1- [1] = 11 18-78 p=
1 (TT (1 - p)
Here, |- represent the determinant. And we choose to ensure |/P21|2 < 1. Given the discounted visitation measure, we immediately obtain the non-robust value function of each reward by using V (²*()) = =T.
Vi0 (po) 7 + ग. (7 - 72)
7T1 p)
Vi 1- 7 1 (p - -2))
From our definition of the uncertainty sct, we have p E [p.p]. Then the robust value function of each reward is:
V0 (mo) min VO (HO) 1 7 + T[ (1 (1 72)
7T (1 77)
VT (Ho) min VT((H)) 1 7 Ti - 72)
Therefore, the Lagrangian function given by
[(T,A) = v/- A(p - Vi-)
1
+ 1 - -p)(r 72))
(0
YT (1 11-17 -p)
1 1- T (1 - pp((y - 7p)
3. Evaluate the duality gap:
It suffices to evaluate both mInx max, L(T, A) and max, minx L(TT, A).
Solve mInA max, L(T, A):
We will solve 0C
an 2 to find monotone intervals of the function L(, : + L(T, A). Then we will
obtain when [(, A)
L(T, X) achieves its maxima.
0c
-(1 27 72)
- y + (1 - -p)(7 - -2)]
+ 711 +12 P) [1 7 + nι - +2]] (1 P) [11
(1 -))-(((- -3)]
[] -1-7 + (1 () ?2
-(1 - p) - 72)
(1 p) - -22)
+ )
1 7 + (1 p) 22)
[1 7 n (1 -7)(> - -
Oc Let dr
2 0. We obtain
1- P
1 1- p
11 +
+ TI - -p)r]²
24

---

Published in Transactions on Machine Learning Research (08/2025)
1 P p
1 ti (1 (1- (1-1))] [1+ (1+++(1--pp))) p)>}
p
[1 + IT (1 (1- x1
(1 ph1
1-2 2
Then we obtain
P 12 T17
p
(1- - (1 -
2)
1
1 2
It is easy to notice that when X s
1_ I-p'
the coefficien of '
(1- p) (1 2)) x
1 - p
2 0.
1 P
When A 2 1-5 the coefficient of m 1-2²
1 P (1 (1-D) - -1
V - 2
S 0.
We separately consider each case to solve the monotone intervals.
Case 1: x L.B. In this case, (1 - p)) - (1 - - 2 0. It solves:
I - +]
m S
(1-
We further consider if this upper bound is positive or negative. 2 0. It violates X A 1-p T-
b Case 1.1: A 2 1-2 In this case,
I-p"
B Case 1.2: A Therefore, in the Case 1 (A S 1 ) we always have का S 0. It indicates that C(T, A) is decreasing TT when Ti E [0,1]. The maximum achieved when setting Tı =0. That is,
T In this case,
- - 5o. 50
1 max ((,0 1-7 Xp,
where 0 0.A5 1-B T-p"
Case 2: >> In this case, (1- (1 (1- < 0. It solves:
1-E 1-
V -1 -]
T 2 7 (1-
Again, we further consider if this lower bound is positive or negative:
b. Case 2.1: X 2 1-g
- In this case, [ 2 0. It indicates that L(T, is increasing in m
when कi E [0, 1]. The maximum achieved at x = 1.
b Case 2.2: 1-7 < I-5
1-p In this case,
/ -1] :] s 0. It indicates that L(T, A) is decreasing
then increasing within Ti E 10. The maximum is either achieved at 21 1 or 21 = O. We need to decide which one is larger: When i1 1, we have
1
> Xp=
7(1 - p) 1- + (1 (1- (1-P)(7 72)
((1,))
1 1- 7 (1 (7 - 7²)
25

---

Published in Transactions on Machine Learning Research (08/2025)
or when T1
((0, 1
Xp.
1-7
By letting ((1,)) 2 A),,A), we solve the boundary is
A 1- 1--1++1 (1-D)
1 11
It means if X 2 Å, then A(1, > A), If S X, then L(1, S (().)).
Combining both Case 2.1 and Case 2.2, we obtain
((L,))) Λ
max ((T,
((0,)) 22 1
where A= 1-p 1+ (+1ー))
Now, combining both Case 1 and Case 2, we have
((L,)) A2Σ
max C(T,, A)
((0,)) $2\20'
where 2 = 1-p 1-p1+(1-p) When x = 2, the function max, [(T, -) : A + max, [(T, A) achieves its I-p 1+
minimum. That is,
1 1 1- + (1 7)7
min max ((T,
1-7 1-pl+ (1 2) P.
Solve max, min, L(T, A): We let the constraint be satisfied; that is
7 (1 -
P 7 + m (1- 22) S
Otherwise, simply letting x == to0 will lead to -00 function value. It solves
p(1 7) 7) s [1-p[( - 11 - (
Since p must be less than 1 1-7 (so, - (1 - (1- 2 0), we have
p(1 - 7)
T 2 [| p(1 - 7)17 - p)
Therefore, the maximum is achieved at π| (--p(1->))(
p(1 x1-
max min L(x,, A) max Vi¹
1
p و)- 1-p
1 7 1 p(l 1- 1-p
1-p
1
PT
1 1-7 1- -
(1 1-p
Therefore, the duality gap is given by
Φ(C) max min L(TT, A) min max C(TT, A)
1-p P PT-
1 - -1-11(11-7) p)y
1-
1 p(1 - 7) + p (1 1-
26

---

Published in Transactions on Machine Learning Research (08/2025)
When p=2: p. the duality gap turns to be exactly 0. It is because the constrained non-robust RL problem has zero duality gap. However, when we set p 0.5, p = 0.75, P 0.25, and p 1. We have the non-zero duality gap
21
9 (L) 22
C Proof of Theorem 4.5
In this scction, we provide the detailed proof of Theorem 4.5
C.1 Assumptions
In this subsection, we recap the assumptions used this proof. We additionally restrict all rewards to [0, 1]: however, this restriction is not crucial. It only affects the constant upper bound of robust value (or Q) functions V and Q" We relax this assumption to general [-Tmax: Tmax] with changing the upper and lower bound of these value functions to be Ymax
Assumption C.1 (Policy Evaluation Accuracy). The approximate robust value functions Q (8, a) satisfy (] - Q. (s, a)l S Capprox for all E S, A, and i i= I.......
Assumption C.2 (Worst-Casc Exploration). For any policy и and its worst-case transition P, there exists positive constant Pmin > 0 such that its stale visitation probability satisfies dg. 2 Pmin for all E S, where d is the state visitation distribution starting from initial distribution μ under policy æ and transition
Assumption C.3 (Bounded Rewards). For all rewards ri r A + R, it satisfies
0 r<(,) 1
for all (s, E S A.
Assumption C.4. The diameter of the uncertainty set C given
sup supdTv(P((Is,)) a), P'(ss, S P.P.CC a.a
C.2 Supporting Lemmas
We summarize all required lemmas in this subsection. These lemmas will be used to prove the main result.
The following performance difference lemma is originally developed by Zhou et al. 2024 for bounding the value function difference of two policies x' and л. Here we apply Assumption 4.2 to turn the upper and lower bound lo transition this inequality to the desired distribution needed in our convergence analysis.
Lemma C.5 (Robust performance difference lemma). Let n. n' be two policies and P be their worst-case transition kernels. Suppose that is the initial distribution over the state space S. Then
1
(1 swap p Ba (-16) (8, a)] S V (1) - (n) S
R swar' P E (1o) (8,
(11)
Proof. Equation 11 is given by Lemma 8 from Zhou el al. (2024).
Remark C.6. Moreover, we have
Vo (1) VT (14) -
E. s F. (1))
1 1-
<
E,
i E
(1)) [A (s)
(1T
E
e pe E
(1
y
27

---

Published in Transactions on Machine Learning Research (08/2025)
B
p Eu of ( (1))
7 sway
" smaf s B Barr (10) (s, +
(1 (1- drv d (dy ( c
2
Lemma C.7. Let the NPG update rule be given by
TeZ1 (als) (alss) exp (n (s, a)/ (1~1))
Zz
where the normalization factor Ze = EnEA Te(als) exp (nQ) a) -)).
Then
(s,())))= 1-7 log Ze *t+1(a|s)
Te (a(ss)
Proof. See Lemma 4 from Xu et al. 2021
The following lemma tells how much the worst-case value function of a given reward r; is im- proved by updating Te to Te+1 using its correspouding robust policy gradient. The first term J
" sua [dKL (T(+2())))l is always non-negative. The second term A, will be merged with other
errors later.
Lemma C.8. Under the NPG update rule with learning rate n, the robust value functions with an arbilvary initial distribution satisfy the following inequality:
(v) V.
(v)
E 1
a (dKz (1)))())))) A.,
where the worst-cuse cuse bransition probability of the policy me and πet1 are and P', respeclively, and the error term DS is given by
E A
[m |
Teti(a s)] (07 (s, - QT, (s,
1-7 snd
(1 7) Ean (log Ze] E [s]](s)
Em((a s) (Q (s. Q7, (s.
Egay
E
1
aEA
Proof. Let the worst-case transition probability of the policy and T++1 be P and P', respectively. Their corresponding visitation probabilities are (s)) and di dpei.. (s). Applying Lemma C.5 to the robust value function V.T (p) and Vi (v), we obtain
TT++ (V) V. (v)
E 1(P.
Σ TLi(a (s,))
aeA
E
s) (s,a) [s)(
and
acA
TT-i(a s) (s,a)
1
aEd
me s)] (s, a) - (s,a)
P P
snidy
aEA
7 sned sead Te41. V (s)).
28

---

Published in Transactions on Machine Learning Research (08/2025)
where the first equality applies the definition of the worst-case advantage function AT (=(s.a)- (*)),, and the second equality applies the decomposition of the Q-function with its approximation error. By the NPG update rule (Lemma C.7 we have
(s,a) = 1-7 log Ze
*++1(a]s) (a(as))
Then we obtain
1
1-7 log Z. (a41
V (v) - 1. (v) 2
Tt+1(a|8) 8)
srudy
Tt. (a(s)
aEd
1
E
Te+i(a s)) (,, (s,a)]
1
endd
E
[V: (s)
1 y
gndd
Tttiaa s) log Ze + log (a{s(
E
(e(als)
17
aEA
Te+i(a s)) Q7 (s,
+
erudy
aEA
E
[s)]
1
(8)
E
+ E n sud 1P log Ze
snd 14.1.0
1)
E
Σ
Teti(a s) Q7 (s)
annd
1
E
1. [V,
1 and
where (i) applies the definition of KL-divergence (T (T++((1)) Enea Teti(a () [log [es](als) )c(a|s)
By the definition of Ze, we have
(e(ass) exp exp (TQ). (s, - 7))
7. send T141 log (s)
E
E
1t log
1) sod
REA
1
te(a|s) logexp (s)
1
srud
REA
(alss) (QT) (s.
p
aEA
(als))
(Ộ (s,a) a) Q7 (s, + Q. (s,a))
?
DEA
(8)
1
E
(als)
(Q:, (s, - 0 (s,a)) + 1-
1
B
ond V (s,a),
arud
aeAA
(12)
where (i) applies the Jensen's 's inequality, and (ii) applies the relation between Q-function and value function (Proposition 2.2. from Li et. al. (2022 ). As the result, we obtain
V Tt (v) ViTT(())
2 E
44 dxL (Tees (15) + LB ")
1
n and log Ze
E 7 end
Pr pr [V (s)
1-
29

---

Published in Transactions on Machine Learning Research (08/2025)
E
ne(als) (7) (s.a)
? o
aeA
E
Te(als) Q7) (s, a) - Qu0 (s)
1
Y
soud
p
aEA
E
Tt-1(a () (8,a) (s.a)]
soud
aEd
(1)
1
E3
snd 41 pf dRL (Te+
1 '- s p'
Σ
Te-i(a F
ss] (s, - Q7 (s,a)
11
aEA
E
me(ass
(%. (8,a) Q% (s, (s.
?
snud
aEd
1(1 7)
EgNy V (s) Eyau Σ (e(aas) (0% -(((
E
Egny log Ze
aEA
where (i) we apply the change of measure to replace di
with vs (1) log (s(s) + =1
T- EoEA Teti
12) and (2) 1.
() (s, - Q. (s. a)] -"""" (+) 2 0 for all s by Equation
(8) 2 1 7-7
Therefore, we conclude that
(V) (u)
2 11 s-d c+ p drr (Te+1 (-1))][<((1ss))
+ 1-- sna
1
E
s 1 Σ
(ati [s)(Q. - (s, a)]
uEA
E
and 1.P.P Σ Teaaas)) -s,)
-
1 y
aed
(1 - 7) Ben log Ze- - Eo [V"" - EENU Σ
T<aass)
7
acA
It completes the proof.
The following lemma is the main bound that we will deal with. Lemma C.9. Under the NPG update rule with learning rate n, the robust value functions satisfy the following inequality:
V.a² ie (H) - Vi (n) < (Bany- DKL( ( (-1)) - E.- (KL( (16)
1
Bswv- Σ (a s) - -Q (s)
+
aEA
1
+
Vanti Vin
E n mnd p² DKL (KL(
(1 7)
1
E
mM Σ
Teilla s)(2 - 22 (s.
1 y
and
aEd
1 sod
Q 2% Σ Te(aas) (0) (s. aEd
E
+
where the worst-case transition probability of the worst-case optimal policy nt" and T841 are P and Pl, = dx PP' (s).
respectively, and the visitation probability of n" is vs)s :=
Proof. Let the worst-case transition probability of the worst-case optimal policy T" be p and the visitation probability of π² be
(*(s) = P
P (s).
30

---

Published in Transactions on Machine Learning Research (08/2025)
Define
1
1/4 1 γ swdd""
" PP. B (-1)) (s,a) 1-
RF snad , R (-1er (4 a)},
(13)
where Pt denotes the worst-case transition probability of IT..
Applying Lemma C.5 to the robust value function V.r and V (i 0, 0,1,,..,!!) [), we obtain
Vi (n) VV,((v (1) Esnue
Σ
x'aa
aEA
Bower Σ
(a
80 (s, Vi, +s)
?
aEA
1 B
(a 1Q (s, a)) + 1
B Σ x' s)(Q (s,a) a) - (s.aa) (s.
aEA
aEA
E Essy 1/ [s)]++
1-?
where the first equality applics the definition of the worst-case advantage function (s, (s, (*),,, and the second equality applies the decomposition of the Q-function with its approximation error.
By the NPG update rule (Lemma C.7 we have
(s) 1-2 log Ze
(+t1(al0) Ty (a(a)s)
Then we obtain
V.. (n)) - Vi (n) S
1
E Rxwey Σ (a (a|))
1- log
2: T<+((a|s)
1
17
[a(a)s)
oEA
+
E
Egny-
(a s)]0
QT (s,a))
1
acA
E Egny [V (s)]+tb
1 1-
1 Egny
(als)
log Ze +
Σ x' s) log
1
x<(a|s)
aEA
E Ennu- Σ n" s))
Q7 (s,aa)
E Egrw-
IV:" (s)]++b
(
E Eger' flog Z₁ dRL (T (-1s)]( dKl (n (-1s)
E
Egrn Σ
(a ()) (T, a)) - 1- E, E ( [x)] +s)
aEA
1 Ennyy log Ze + -E (dKL (a (-15))lm(((11)) dKl (7 ((15)]1T(41(111s)
1)
E
Egny' Σ (a s)( (s,a) QT, (s, 1 E [ (s)
aEA
where (i) applies the definition of KL-divergence. By Lemma C.8 we have
17 Eany log Z, E Earyr [V E (e(a|s) (s) (s,
7)
8 aEA
31

---

Published in Transactions on Machine Learning Research (08/2025)
< <Va Vi (v*)
"I and (
Y sou 1
E
Teti s)] QT, (s,a)
acA
E
Σ me(als) (s, (8)
? sndd
acd
Then we obtain
V (4) V/ (w) 1 (Bany- (-L((T((sss - Esnu- -Ea-o-RL (TT (11))1
1
Banu- Σ
xa (01 (s, Q.: (s.
+
aEd
1
+
V ((*)+((²)= Vú (v²)
? lE snd pr DKL ((((( (
(1
7)
1
E
Te s)) - (s,
1
andd
aEd
1 E
Σ (ulss) (s,))) Q7 (3, + aEA
7 s
which is the final upper bound after applying the last incquality. Then we omit the term containing - (=)) since it is always non-positive.
The following lemma gives the condition such that No is non-empty. Lemma C.10. Consider the NPG update rule with learning rate n and let 8 > 0 be chosen such that
8 > 1 Banw DKrt. (TT (-16)(
nL
2
(1 (1- Eapprea + (1 7)2
where Eapproz is an error term depending on the approrimation error terms, is the Lipschitz constant of the state visitation distribution d and L, is the Lipschitz constant of the robust value function V (v"), is the diameter of the uncertainty set given by Assumption
C.4 Under these conditions,
No = VL (n) - V. (w) 2 d, - for all i}
is always non-empte
Proof. When t E &&N;== = {t: Vi is sampled to update], we have i, and by the algorithm design,
V. (n) V. (1) 2 ViTh (n) de + 5 + D.m (n)) - -V, (())
28
8 - m++ (n) - vi=++1 (1)
We sum the incquality obtained from Lemma is Lipschitz in x (Wang& & Zou 2021 Zhou et al.
C.9 over f = 1, 2,...... T. Since the robust value function V (1)
2024 we have
Ln
( - V (v") D| Tell S
1 1-7
Then we obtain
V. (1) - -Vatt((4) + noT S ET DKL (-1ss( (-18) + LT
T
+ T
Tapproxx +
th
(1 7)2
32

---

This result indicates that Published in Transactions on Machine Learning Research (08/2025)
where Ve is given by Equation of Capprox which is defined as
13 and Capprox is constant upper bound (depending on Assumption 4.1
Capprox
1 Egsyy
Σ
(a [s) (s, - (5,()))))
aEA
(p) -va (u)
E ani snidet
Σ
( Q7 (s,a))
(1 7)
1-
aEA
Te(als) (o. (7. -Q7
Y an 1.P
aEA
By appropriately choosing the policy evaluation algorithm (discussed Appendix C.3 arbitrarily small. If No 0, then
Epproxx can be
12T (1 7)2 + TT capprox +1 Σ W/-
nOT S Brww
+
We further take
2
2
2l
1 (1 --
(1- sup (())
(1 (1-9) 7)2
where we apply the E-Lipschitzness of the state visitation distribution (Lemma 5, Eq. (37), Chen & Huang ).24)). Then, we let
1 ] Esny DKL( (+ (+(ss) (1 (1-7)²
nL Eapprox + 28
8>
(1 (1-11 7)2
This hyper-paramcter sctting ensures that No is non-empty.
C.3 Robust Policy Evaluation
In this section, we collect two important robust policy evaluation tochniques to discuss how use these methods to obtain the robust value function with sufficient accuracy. Though we simplified result in this subsection, these results have been extended to more general setting in original sources.
C.3.1 Option 1: The IPM Uncertainty Set
Lemma C.11 (Theorem 3, Zhou et al. (2024)). Let the value function v is parumeterized by w E RIs with the linear feature à RiST Then using the Robust Linear TD-Laarning proposed by Zhou et al. (202) with step sizes ag = (11kk) the output satisfies Ellwx - w01 = Ō( 1)
As shown by Li eiela al. 2022), the robust Q-function can be calculated using the robust value function learned by the robust TD-learning algorithm described above. That is,
((s,a)==((s) + inf (s'). PEP
The sccond term inf PEP (s') is given by Proposition from Zhou 2024). we can obtain the robust Q-function with the convergence rate VR (for the Loo-)
C.3.2 Option The p-Norm Uncertainty Set We consider the following uncertainty set:
y:= (v E R! (v, (ss) 0, ||1|| S B},
33

---

Published in Transactions on Machine Learning Research (08/2025)
u: V Po.
Let q satisfy 1. Then 0pp(.) RR18 R! is defined as:
(V)(()) = (ig'( wa (V))V - (V))
Kig (V)5-
where (V) = arg min IVV - l1lsl|le and Kn (V) = min IV - wl
Lemma C.12 (Theorem 4.2, Kumar et al. 2023 ) If the uncertainty set is defined as the p-norm () rectangular set, then the worst-case transition probability P+[-|s, a) can represented as
P+(+s,a)= Po(-|s, (V)
where B is the radius of the uncertainty set and (V) is the balanced robust value function Kuumar et al. 2023
Based on this result, apply the following TD-learning update rule:
V(s) + V(s) V(s) ta r(s, + -V0
(14)
stand. TD err. under Po
Here O-,p()) R R is an operator determined by the uncertainty set. It is easy to observe that this update rule is equivalent to the TD-lcarning over the worst-case transition probability:
Eg- (r(ss a) -
=)(8,a) 7
Σ Po(5")s,)))((aa)((())) - [
8'a
-r(s,a) + Σ
Pols'ls, ()( - -
s'aa
s'.a
ar(s,a) +1 Σ T(als) (s.)s -
s'aa
(r + Σ T((ls)) s'.a
=r(s, + F (o1)a)) (ss),,
where (i) applics the remarkable result from Theorem 4.2, Kumar et al. 2023 the worst-case transition
P+ is the rank-one perturbation of the nominal transition Pg. Therefore, by applying existing TD-lcarning
convergence analysis (Brandfonbrener & Bruna 2019 Asadi al. 2024 Li el. al. 2024). we obtain that the convergence rate is also VK*
C.4 Compact Algorithm
We also include a compact version of Algorithm in Algorithm which merges the constraint rectification and objective rectification together.
C.5 The Proof of Main Theorem
Here, we state the full version Theorem 4.5
Theorem C.13. Consider the NPG update rule with learning rale Let the constraint violation lolerance be chosen to satisfy
2 = E. Ban DEL ( (+1)))]]] +
2nL
48
8>
+ 2E 2Eapprox (1 (1-
T
(1 (1-7) 7
34

---

Published in Transactions on Machine Learning Research (08/2025)
Algorithm 3: Rectified Robust Policy Optimization
input iniiial policy parameters 8,, empty set No
for == 0, - do
Evaluate value functions under Te = To.; Q R (s, a) for i 0........
Sample state-action pairs (sy, az) from the nominal distribution
Compute value estimates V. for i O
if Vi 2 d, ò for all 0, 1...... then
// Threshold Updates
Add 0, to set No and track the feasible policy achieving the largest value Tout Wz3 Update dy: do f V
else if V, < d; for some i = 1....,,,,, then
// Constraint Rectification & Objective Rectification Maximize V using Equation
output: Tout
where & is the Lipschitz constant of the state visitation distribution dy.P, and L is the Lipschitz constant of the robust value function V (v"), Eapproz is the error caused by the robust policy evaluation step. Under these conditions, the output policy Tout satisfies:
-V) (w)) 2 Be DKL (T (+|s)[ +
2nL
48
+ 2E
(1 (1-
(1 7)2
where the constraind violation of ont guaranteed to be at most 6. Moreover, if selling
(1-7)² c
(1 7)
2L 4 -
2L 3'
< (1-2)²
the robust policy evaluation ertor Capproz
e, and the number of iteration step
2L 12
T
Eg DKL ((1))
21- 2
then the output policy satisfies the e-accuracy with constant error; that is
(p) - (F)) S E+ (1 (1-
Proof. By the update rule, the boundary value do non-decreasing. Since it is upper bounded, we conclude that { converges and we denote
df + do
as + co. More explicitly, we have
do =up V.7t < d. + +
There are only two cases for the output policy Vout:
(1) The policy is better than the optimal policy while the relaxed constraint violated; i.c.
Vi (n) V. (n) < 0.
(2) The output policy is worse than the optimal policy but upper bounded by ((+)). When (1) holds, then is desired. When (1) doesn't hold (i.e. V (M) - -V (n) > 0.), we assume Wo 2. implies Eln 2 f. Then we have
1
12
T
2 n88T < EEE (T (= +
+ 1 Eapprox +
1/
(1 - 7)
35

---

Published in Transactions on Machine Learning Research (08/2025)
LT
2f
I ny (x (15)) + (1 7)2
+ n Eapprox
(15)
(1-7)2
Here the last inequality applies the upper bound of vi (see Lemma C.10 for the full derivation and the definition of E). Then we let
2 B. . DKL (1T (+)))ll
2nL
48
26 2ppprrx
n/
(1 71-
(1 7)3
This hypeer-arameeer setting ensures that Equation does not hold. Therefore, it leads to a contradiction. We obtain [ 2 F. In this case, we have
0 S E [V (p) - Vost (N) S ET~NO (V V*
27L
Ron (xL( (+1)]= + S 1,T
+ 2 approxx +
(1 11-1) 7)2
(1 (1->) (1-
Here the non-negativity is because (p) is the largest-possible value function the feasible policy. From the construction of No and the output policy Tout; they all feasible policies.
We are interested in obtaining the complexity of the convergence to constant value function error (I-9)aC (typically, this term can be controlled by using a sufficiently small uncertainty set). To obtain the sample complexity, set all three terms to be O(e):
46
Let
24L (1-7) < 3. Then obtain
7)
n
2L 3
To make the last term 27 apprrxx S $, set the robust policy evaluation error (Assumption 4.1 to be
| - Q11 S Capprox
It leads to
1
1
1
1 1- γ
appprox +
(1 7)
fapprox + 1 Fapprox +
Fapprox
It solves approx < (1-7)2 c.
Let, 7/7 Banyy DTI( (=="(=))))+= (+18)]|T( (-1s)) S. We obtain
2
T 2
Eanr DKL( (11)((()))
1/T
2h
12
(1 - 7)2 2 Eawy DKL(# ( (1)))
In the second step, require the learning rale is not too small; that is, we let it larger than (-7)² This result indicate that the iteration complexity is T = O(E=)) with choosing an appropriate learning rate O(c) and the approximation error Capprox = (c).
" 2L 3.
Experiment Setting
This section outlines the information for replicating our experiments. Throughout our experiments, we inchude multiple independent runs and report the averaged metrics in our results. Specifically, we used three different random seeds.
36

---

Published in Transactions on Machine Learning Research (08/2025)
D.1 Hardware Specification and System Environment
We conducted our experiments computing desktop rumning Windows 10 Education, equipped with 3200MHz DDR4 DRAM memory, AMD Ryzen 7 3800X 8-Core, 16-Thread processor, and one NVIDIA GeForce RTX 2070 Super graphics cards. All experiments are executed using Python version 3.10.14.
D.2
FrozenLake-Like Gridworld Experiment
The reward function is defined as follows:
+1
if s' the target
r0(8,0,8)
-1
if s' is brown block
0.1 hthwewise
and define r(s, a) == -E ar(s,,,,, The constraint reward function is defined as:
if s is out of the boundary
-1
if s' is a brown block
0
otherwise
Here, we further define the cost function c(s, a) == -E (ri (s, a,)') s']] to better distinguish it with the rewards. In this experiment, we require the cost value function - -V (u) less than 0.2, which means that the agent should avoid hitting the brown block or move of the box.
We used a discount factor 7 0.99. The learning rates for both algorithms are set to 0.0001 and the tolerance for constraint violations is 0.01. The robustness of the environment simulated by introducing slipping probability = 0.2 in the test environment, which differs from the deterministic dynamics used during training. For both methods, we run 1M steps.
During the training, we use the neural network taking a 2-dimensional input (the position of the agent) and processes it through a single fully connected layers of size 64 followed by a ReLU activation then fed into a final linear layer that produces 4 logits (four actions: Up, Down, Left, and Right).
D.3 Mountain Car Experiment
We use the standard Mountain Car environment provided by Towers al. 2024 Once the car reaches the goal, reset the original starting point. The reward function is defined using the environment's default setting:
ro(s, (') = 0 if the agent reaches the goal,
otherwise,
and we set r(s,a) = 2, To emphasize safety, we introduce the constraint reward function:
(1 = { if the car's speed exceeds 0.06, otherwise,
and define the function c(s,a) -E. as,a, In this experiment, we account for environment uncertainty by perturbing the "gravity" parameter from its nominal value 0.0025 0.003 in the worst-case sconario. In this experiment, we set the constraint to be -4 (i.c. we require -VI (n) < 4). As shown in Figure 35 both CRPO and RRPO learn a feasible solution.
Given that the MountainCar environment has a continuous state space (i.e., the car's position and velocity), we employ radial basis function (RBF) features achieve a lincar approximation the policy. Specifically, each state first transformed into an RBF feature vector Φ(s), which then multiplied by the policy parameters 0 (one column per action) to generate logits; these logits passed through softmax function
37

---

Published in Transactions on Machine Learning Research (08/2025)
to produce the policy distribution over actions. Additionally, we incorporate e-greedy strategy with initial 0.1, decaying at rate of 0.9999, to encourage exploration in the early stages of training.
We set the 2-norm (s, reretaaggll uncertainty set defined by Equation 10 Since the state space is contin- nous, when evaluating the centered value function, we uniformly sample 100 states from the state space to es- timate the mean and the variance value of (*)s.. The radius of the p-norm uncertainty set is set to be 0.0002, This value manually tuned from preset ayper-parameter set {0.00001, 0.0001, 0.0002, 0.0003, 0.001]. When the radius value is too high, the policy tends to be too conservative; when the radius value is too small, the policy performs similar the non-robust case.
D.4 Robust Control Experiment
In this experiment, we adopt the common PPO tricks to stablize the training. Each algorithm was trained for 2 million timesteps using identical hyperparameters to ensure fair comparison: learning rate of 3 33x10 batch size of 256, discount factor with a threshold of 0.25, representing moderate constraint that provides meaningful limitations without being overly restrictive. For the constrained algorithms, Primal-Dual Policy Gradient. (Wang et al. 2022) employed a constraint learning rate of 3 x 10 with Lagrange multiplier initialization 0.1 and maximum value of 100.0. On the construction of the uncertainty set, we follow Hou et al. (2020)'s robust ector-Critic algorithm to obtain the desired robust value function approximation. The radius of the uncertainty set is set 0.001. In our experiment, ran three independent runs and reported the averaged results in the experimental section.
0.99, and PPO clip range of 0.2. We incorporated energy-based constraints
38


Reviews:
[{"review_id": "AxmgqQAcOJ", "reviewer": "Reviewer_9eGv", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- The paper provides the first concrete counterexample demonstrating a non-zero duality gap in robust constrained reinforcement learning. This is a good theoretical contribution that addresses an open problem in the field.\n- The proposed Rectified Robust Policy Optimization (RRPO) algorithm is a good solution to the duality gap issue. It avoids the limitations of primal-dual approaches and is supported by rigorous theoretical analysis with convergence guarantees.\n\nWeaknesses\n- Insufficient Motivation and Real-World Relevance: The paper merges robust RL and constrained RL but does not clearly articulate the motivation behind this integration or its importance in real-world settings. Without concrete examples or compelling use cases, it is difficult to assess the practical value of addressing this joint formulation. The experiments focus solely on toy environments, making it unclear where and how this approach would be applicable in real-world applications.\n- Incomplete Literature Review and Narrow Scope: The related work discussion appears limited, with a noticeable reliance on papers older than five years. Recent developments in both robust and constrained RL over the past three years are largely overlooked. On the robust RL side, the paper focuses exclusively on transition uncertainty, without addressing reward or state uncertainty—raising concerns about the generality of the proposed method. On the constrained RL side, the paper only considers soft constraints expressed via cumulative reward functions, ignoring formulations involving hard safety constraints. Notably, there is no discussion of alternative constraint handling mechanisms such as shielding or model-predictive shielding. As a result, the problem formulation may be too narrow and should be better scoped.\n- Limited and Simplistic Experimental Validation: The experimental environments—gridworld and mountain car—are relatively simple and may not adequately demonstrate the effectiveness of the method for complex or realistic settings. Additionally, the baseline comparisons are limited. Given the growing body of work on robust, constrained, and robust-constrained RL, it would strengthen the empirical evaluation to include more recent and competitive baselines from each of these categories.\n- Unclear Connection to Deep Reinforcement Learning: Without this counterexample, it is already known that strong duality may not hold for many recent deep reinforcement learning algorithms, particularly in nonconvex settings. This is a common issue in practice. However, the paper does not explain how the proposed RRPO algorithm can be integrated into or improve deep RL methods. Clarifying its applicability to deep RL—and demonstrating this experimentally—would significantly strengthen the paper's practical relevance and impact.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the robust constrained reinforcement learning (RL) problem, where an agent must optimize its performance under worst-case transition uncertainties while satisfying safety constraints. The authors prove that strong duality does not generally hold in robust constrained RL—a fact that undermines the efficacy of popular primal-dual algorithms. They provide a counterexample to rigorously demonstrate a non-zero duality gap. Motivated by this, the paper proposes a primal-only algorithm, Rectified Robust Policy Optimization (RRPO), that operates directly on the primal problem and avoids reliance on dual formulations.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see the weaknesses.", "broader_impact_concerns": "There is no broader impact discussion in the paper.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "ONwXZZBAWm", "reviewer": "Reviewer_F72f", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: The paper identifies a key weakness in the CRPO framework. The proposed modifications are conceptually simple and compatible with a wide range of robust RL settings and uncertainty models.\n\n\nMain weakness: The main contribution of the paper lies in the introduction of a threshold tracking mechanism (the $d_0$​ update) and a rule-based triage strategy to switch between objective and constraint optimization based on the threshold gap $\\delta$. While this design is motivated by the oscillatory behavior observed in CRPO, the paper does not provide convincing theoretical or empirical evidence that RRPO indeed mitigates this issue. The theoretical analysis only establishes that RRPO achieves the same convergence rate as CRPO. On the empirical side, while RRPO sometimes yields better rewards, the experiments are limited in scope and do not systematically measure oscillation reduction or provide broad benchmarks to support general claims of superiority.\n\nAdditionally, the claim that \"strong duality does not hold, so we cannot use primal-dual methods\" is too strong. Even when strong duality fails, there exist primal-dual approaches that can find approximate stationary points under weaker assumptions such as weak duality. The paper would benefit from a more detailed discussion of this and a clearer justification for ruling out primal-dual approaches entirely.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduce a new algorithm (RRPO) for constrained robust reinforcement learning that addresses the instability of the existing algorithms (CRPO). RRPO introduces a rectification mechanism that stabilizes learning by tracking the best feasible policy. It is shown to be compatible with various uncertainty models (e.g., p-norm and IPM-based) and leverages robust value function approximation methods. The RRPO also enjoys global convergence guarantees, matching known lower bounds for constrained RL.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1.  Add more comprehensive empirical results to substantiate the claim that RRPO improves stability near constraint boundaries. \n2.  Provide some theoretical intuition or at least a concrete example illustrating how RRPO’s rectification mechanism can reduce oscillation or improve stability.\n3. Include a more detailed comparison with existing constrained RL approaches, especially primal-dual methods.\n\nMinor changes:\n1. \"We will exchangeably using the parametric...\" -> \"We will use the parametric and policy representations interchangeably.\"", "broader_impact_concerns": "None to the best of my knowledge.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "LEkXpLOTbh", "reviewer": "Reviewer_WgLD", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The hard instance and corresponding analysis showing positive duality gap is interesting. Before section 4.2 the paper is in general clearly written. The experiments, though restricted to simple environments, show the worst case robustness and constraints compliances. However, the description of algorithm and its discussion can be more clear and rigorous. Please see questions below.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the robust constrained MDP. The authors first show strong duality does not hold in general under this setting, and thus conventional primal-dual methods for standard constrained MDP and robust MDP do not apply. A primal-only algorithm is proposed to solve the robust constrained MDP, theoretical analysis and experiments results are provided to show the effectiveness of the proposed algorithm.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I have the following questions:\n\n1. Until 4.1, the current writing gives me an impression that this work is solving a planning problem where the transition and rewards are known, because the algorithm does not involve data collection. However, the statement in section 4.2 and Appendix C.3 implies that it actually involves an online learning process for robust policy evaluation. In discussions, some results from planning papers are cited, which are used in online learning algorithms developed by existing literature. I am not saying this is wrong, but a clearer version of algorithm design would improve the current manuscript, especially the authors highlight accurate evaluation of Q-function is critical. For example, the author might provide detailed subroutine for policy evaluation, showing how the data is collected, how to estimate the Q-function, etc.\n\n2. About Alg 1, just curious if we can merge the 'Constraint Rectification' and 'Objective Rectification'.\n\n3. The authors claim that the Assumption 4.1 and 4.2 used to develop theoretical guarantee are mild. However, they somehow bypass the most difficult challenges in online DRMDPs - policy evaluation and exploration. For example, under what additional conditions/assumptions and specific estimation procedure can we expect Assumption 4.1 to hold? Assumption 4.2 assumes the visitation probability is always lower bounded under any policy $\\pi$: on the one hand this assumption is made on the visitation measure induced under the worst case env, while the exploration happens under the nominal env, right?  How does this assumption relate to exploration? How the algorithm deal with exploration-exploitation trade-off? on the other hand, when the state space is large, the lower bound $p_{\\min}$ can be extremely small. In this case, will the assumption, as well as corresponding analysis being invalid? How $p_{\\min}$ affect your bound and analysis?\n\n4. There are other works on online distributionally robust RL, for example RMDP with $(s,a)$-rectangularity: 'Distributionally robust reinforcement learning with interactive data collection: Fundamental hardness and near-optimal algorithm', and RMDP with $d$-rectangularity: 'Distributionally robust off-dynamics reinforcement learning: Provable efficiency with linear function approximation' and \n'Upper and lower bounds for distributionally robust off-dynamics reinforcement learning'. Discussion on whether the framework studied in the manuscript can incorporate these methodology would strengthen this work. Besides, the current discussion on Robust RL is limited. A relatively comprehensive summary of most recent works in this field is encouraged.\n\n-------\nOther minor issues:\n\nPage 16, section A.2 $(1−\\alpha)d^{\\pi, P}+\\alpha d^{\\pi, P}=d^{\\pi′,P}$\n\nPage 6, $\\pi_1$  used without definition.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)