In many practical reinforcement learning (RL) applications, it 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 et al., 2024b) or resource limitations (Wang et 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 discrepancies 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 ideal simulated environment due to the ideal equipment condition but suffer high penalty from higher energy cost or unexpected operations in the worst-case scenario.
The uncertainty set captures the discrepancy between training and deployment environments. In our work, we mainly focus on the (s, a)-rectangular uncertainty set (Iyengar, 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 a valid robust policy evaluation algorithm presents, including: s-Uncertainty Sets The s-rectangular uncertainty set (Li et al., 2022;Li & Shapiro, 2023;Kumar et al., 2023) relaxes independence by allowing nature to choose transitions jointly across all actions at a 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 (Kumar et al., 2023). These results make it possible to solve the robust value function more efficiently. d-Uncertainty Sets More recently, the d-rectangular uncertainty set (Ma et al., 2022) has been proposed for linear MDPs to further generalize the existing concepts of (s, a)-rectangular uncertainty sets, where the ambiguity is structured in a low-dimensional decision space, enabling scalable robust value iteration in highdimensional settings. Representative works include Blanchet et al. (2023); Liu & Xu (2024a); Liu et al. (2024); 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 tackles 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, 2010) have been extended by coupling-aware uncertainty sets that avoid excessive conservatism (Mannor et al., 2012). Recent work uses Bayesian reward ensembles and CVaR objectives for preference-based or RLHF settings, giving reliability under noisy learned rewards (Brown et al., 2020). Newest advances address uncertainty inside the reward or state signal itself. Seeingis-Not-Believing RSC-MDPs explicitly model spurious correlations in the state 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-uncertainty distribution whose risk-sensitive aggregation stabilises multi-agent training (Hu et al., 2022). Moreover, robust MDPs cast dynamics error as a zero-sum game; rectangular ambiguity sets admit efficient robust DP with deterministic optimal policies (Iyengar, 2005;Nilim & Ghaoui, 2005). Followups 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 (Tessler et al., 2019) enforce budget or safety limits during learning. Runtime shielding synthesised from temporal-logic specifications now guarantees safety even under partial observability (Carr et al., 2023). Quantile-Constrained RL enforces outage-probability 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). Modelpredictive safety filters based on learned control-barrier functions enforce hard state constraints in unknown stochastic systems while optimizing performance (Wang et al., 2023b). Together these methods wrap (or jointly train) base policies to guarantee constraint satisfaction without relying on soft penalties.
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 et al., 2018a). These threads, alongside recent hard-constraint and shielding techniques above, provide complementary, constraint-respecting alternatives that our revised Related-Work 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 reinforcement 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 a real-world scenario, proposing the ROCOMA algorithm, which achieves efficient EV rebalancing under transition kernel uncertainty. Many topics in constrained robust MARL remains unexplored, making it a promising direction with significant potential for further research.
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 an existing robust policy evaluation algorithm to estimate the approximate value function.
A Robust Markov Decision Process (Robust MDP) is defined by the tuple (S, A, P, r, γ), where S is a finite state space, A is a finite action space, P represents the uncertainty set of transition probabilities with ∆(S) denoting the probability simplex over S, r : S × A → R is the reward function, γ ∈ [0, 1) is the discount factor. We denote µ ∈ ∆(S) as the initial state distribution.
In an robust MDP, the transition probabilities are not fixed but belong to an uncertainty set; usually, the uncertainty set P is defined as the s-rectangular set (Derman et al., 2021;Wang et al., 2023a;Wiesemann et al., 2013;Kumar et al., 2023) P := × s∈S P s , or (s, a)-rectangular set (Wiesemann et al., 2013;Kumar et al., 2023) P := × (s,a)∈S×A P (s,a) .
Here, instead of assuming a specific 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 set 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 π : S → ∆(A) map each state to a probability distribution over actions. In robust RL, the robust value function V π (s) under policy π starting from state s is defined as the worst-case expected discounted cumulative reward:
where the expectation is taken over the trajectories generated by following policy π, with a t ∼ π(• | s t ) and s t+1 ∼ P (• | s t , a t ) for P ∈ P. The objective is to find an optimal policy π * that maximizes the worst-case expected cumulative reward from the initial state distribution µ:
In many applications, it is essential to optimize the reward while satisfying certain constraints, even under model uncertainty. Constrained robust MDPs (Wang et al., 2022;Zhang et al., 2024;Sun et al., 2024;Ghosh, 2024) extend the robust MDP framework by incorporating multiple constraints.
Let there be I constraint reward functions r i : S ×A → R for i = 1, 2, . . . , I. The robust expected cumulative reward under policy π for constraint i is given by:
and
is 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:
where V π 0 (µ) denotes the robust expected cumulative reward, and d i are the specified thresholds for the constraints. That is, a constrained robust MDP is defined by the tuple (S, A, P, {r i } I i=0 , {d i } I i=1 , γ), where {r i } I i=0 and {d i } I i=1 extend the original robust MDP to include these constraint reward function r i and the threshold d i .
In constrained optimization, the concept of duality plays a pivotal role in formulating and solving problems (Boyd & Vandenberghe, 2004;Bertsekas et al., 2003). The duality gap is 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 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 λ = (λ 1 , λ 2 , . . . , λ I ) ≥ 0:
In this formulation, L(π, λ) is the Lagrangian function, and λ i ≥ 0 are the Lagrange multipliers associated with the constraints. The primal problem is defined by maximizing over π, after minimizing the Lagrangian over λ ≥ 0. That is, max
The dual problem is then obtained by minimizing the Lagrangian over λ ≥ 0, after maximizing over π. Specifically, the dual problem is:
The duality gap D 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, {r i } I i=0 , {d i } I i=1 , γ) be a robust constrained MDP. The duality gap D of M is defined as
where L is the Lagrangian function of M defined by Equation (2).
It 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 D is zero, and the optimal value of the primal problem equals that of the dual problem. This property allows us 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 constrained robust RL problems.
In this section, we present a counterexample demonstrating that the duality gap in robust constrained MDPs (Definition 2.1) can be strictly positive.
Theorem 3.1. There exists a constrained robust MDP such that its 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.
Consider a simple MDP with two states, s 0 and s 1 , and two actions, a 0 and a 1 , as depicted in Figure 1. The MDP is defined as follows: (i) Transitions: The initial state is s 0 . From state s 1 , any action deterministically transitions back to state s 0 . From state s 0 , action a 0 deterministically remains in s 0 . From state s 0 , action a 1 transitions to s 0 with probability p and to s 1 with probability 1 -p.
There is model uncertainty in the transition probability p, such that p ∈ [p, p], representing the uncertainty set. (iii) Reward: The reward function for the objective is r 0 (s 0 ) = 1 and r 0 (s 1 ) = 0. The reward function for the constraint is r 1 (s 0 ) = 0 and r 1 (s 1 ) = 1. (iv) Constraints: The goal is to maximize the expected cumulative reward of r 0 while ensuring that the expected cumulative reward of r 1 meets a specified threshold ρ under the worst-case transition probabilities.
The robust control problem can be formulated as:
where V π i (s 0 ) denotes the worst-case value function for reward r i starting from state s 0 . The associated Lagrangian is:
.
with λ ≥ 0, where π 1 := π(a 1 |s 0 ).
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 V π 0 (s 0 ) while satisfying the constraint (7). Here, we directly solve it and obtain
The dual problem given by Equation (4) involves minimizing the Lagrangian over λ ≥ 0 for a fixed policy π, and then maximizing over π. The lack of convexity in the robust setting leads to a discrepancy between the solutions obtained from the primal and dual problems.
It can be obviously observed that when the robustness is absent (i.e. p = p), the primal problem presents the same value as the dual problem.
Published in Transactions on Machine Learning Research (08/2025) Algorithm 1: Rectified Robust Policy Optimization Input : initial policy parameters θ 0 , empty set N 0 for t = 0, • • • , T -1 do // Robust Policy Evaluation (e.g. Algorithm 2) Evaluate value functions under π t := π θt : Qπt i (s, a) ≈ Q πt i (s, a) for i = 0, 1, . . . , I ; Sample state-action pairs (s j , a j ) from the nominal distribution ; Compute value estimates V πt i for i = 0, . . . , I ; if V πt i ≥ d i -δ for all i = 0, 1, . . . , I then // Threshold Updates Add θ t to set N 0 and track the feasible policy achieving the largest value π out = π t ; Update d 0 : d t+1 0 ← V πt 0 ; else if V πt i < d i -δ for some i = 1, . . . , I then // Constraint Rectification Maximize V πt i using Equation (8); else if V πt 0 < d 0 -δ then // Objective Rectification Maximize V πt 0 using Equation (8); return: π out
By selecting values for the parameters (e.g., p = 0.5, p = 0.25, p = 0.75, γ = 0.5, and ρ = 1), we can compute the exact values of the duality gap:
As the result, the strong duality does not generally hold for robust constrained MDPs.
We have just presented a counterexample showing that strong duality does not generally hold in robust constrained MDPs, which resolves an open problem regarding the strong duality of 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.
The lack of strong duality in robust constrained RL presents significant challenges for traditional primal-dual optimization methods. The presence of a non-zero duality gap means that these methods may fail to find feasible and optimal policies in robust constrained settings. To overcome this obstacle, we develop a primalonly algorithm specifically designed for solving robust constrained RL with unknown transition kernel, which we call RRPO.
Given the primal optimization problem:
Here, we note that all V π i (i = 0, 1, . . . , I) represent the robust value functions; when i = 0, we call V π 0 the objective value function, while when i ̸ = 0, we call V π i 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 Algorithm 2: Robust Linear Temporal Difference (Zhou et al., 2024) Input : policy π, number of steps K, value function approximation
Sample transition batch y k+1 according to the nominal kernel P 0 (•|s k , a k ); // For IPM estimator: (Zhou et al., 2024) Update
return w K to either the objective function or the constraints, depending on whether the current policy violates any constraints:
• If all constraints are not violated, then the CRPO algorithm updates the objective value function V π 0 .
However, when constraints are near their boundaries, this method can lead to oscillations, making it 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 d 0 :
At each iteration, the algorithm evaluates the robust value functions V πt i for all i = 0, 1, . . . , I. Based on these evaluations, the algorithm proceeds in one of three categories:
1. Threshold Updates: If the current policy satisfies all constraints within a specified tolerance δ (that is,
), the algorithm updates the boundary threshold by setting d 0 ← V πt 0 (µ).
If any constraint is violated beyond the tolerance δ (that is, there exists
, the algorithm performs policy improvement steps to maximize the violated constraint, aiming to reduce constraint violation.
If the objective value V πt 0 (µ) is less than the current best boundary threshold d 0 -δ, 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 in Algorithm 1.
We consider the robust policy evaluation subroutine as a modular component decoupled from policy optimization. This procedure estimates the Q-function used in the natural policy gradient update. At each iteration, the agent interacts with the environment under the current policy π t to collect trajectories consisting of (s, a, r, s ′ ) tuples. These samples are used to estimate the robust Published in Transactions on Machine Learning Research (08/2025) Q-function Q πt i (s, a) for both the objective (i = 0) and each constraint (i = 1, . . . , I). For value approximation, we adopt robust temporal-difference (TD) learning methods tailored to the chosen uncertainty model (e.g., p-norm or IPM uncertainty). Specifically, given a nominal transition model and an uncertainty set, we compute the worst-case expected value using closed-form solutions or dual formulations from prior work (e.g., Kumar et al. (2023); Zhou et al. (2024); Wang & Zou (2021)). These robust Q-estimates are then used to guide policy updates via a natural policy gradient step. The data collection procedure incorporated with this subroutine is further described in the Algorithm 1.
In our proposed algorithm design, we apply the robust natural policy gradient (Lemma 2, Zhou et al. ( 2024)) to maximize the value function. The update rule of maximizing V πt i (µ) is given by
where the normalization factor Z t is defined as Z t := a∈A π t (a|s) exp ηQ πt i (s, a)/(1 -γ) . When considering the softmax parametrization π θ (a|s) := exp(θ(s,a)) a ′ exp(θ(s,a ′ ) , it is shown by Zhou et al. (2024) that this update rule is equivalent to
where θ is taken over R S×A . Throughout this paper, we will use the parametric and policy representations interchangeably. In updating the policy, accurate evaluation of Q π i (s, a) is critical. To achieve this, we decouple the robust value function evaluation from the policy optimization step. This modular design allows us to 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., 2023): For each state-action pair (s, a), define
Let P 0 be the nominal transition distribution. Then the corresponding uncertainty sets for transition probabilities are given by a) , and P := × (s,a)∈S×A P (s,a) .
(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 ⊂ R |S| be a function class including the zero function. The IPM is defined as
The IPM uncertainty set is defined as 2024)), we can derive an approximate robust Q-function.
In this subsection, we establish the global convergence guarantee for RRPO under certain assumptions. Specifically, we assume: (1) The robust policy evaluation provides sufficiently accurate estimates. (2) Under the worst-case scenario, the policy still maintains sufficient exploration. 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 uncertainty sets. We will discuss the value of ϵ approx in the appendix.
Assumption 4.2 (Worst-Case Exploration). For any policy π and its worst-case transition P , there exists p min > 0 such that its state visitation probability satisfies d π,P µ (s) ≥ p min for all s ∈ S, where d π,P µ 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 π; another widely accepted assumption is made on the finite-horizon scenario (He et al., 2025), which adopt a complementary requirement that caps the relative re-weighting between nominal and adversarial dynamics. Exploring algorithms that retain our absolute-coverage guarantee while accommodating the ratio-based perspective of He et 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 a fixed initial state, we may use a 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 p min > 0 such that inf s,a,s ′ P (s ′ |s, a) ≥ p min for all uncertainty transition P . Assumption 2 (Zhou et al., 2024) assumes that the nominal transition is supported by all 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 on the worst-case transition instead of each transition in the uncertainty set. 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 environment 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 a simplified version to highlight the most critical components, including the convergence rate and sample complexity. The detailed upper bound is provided in Appendix C. ). Under these conditions, there exists an iteration T such that the output policy π out satisfies
where V * := V π * for the optimal feasible policy π * and
Remark 4.6. Compared to Kitamura et al. (2025), which achieves a complexity of O(ϵ -4 ) for exact convergence, our results establish a faster rate of O(ϵ -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 c is sufficiently small (e.g., when the uncertainty set is chosen to be small), our approach yields a strictly faster convergence rate up to an additive O(c) term. The full version of Theorem 4.5 and the detailed proof are provided in Appendix C.
In our initial submission, we did not include the dependence on the uncertainty diameter c in the upper bound. This oversight was identified through the OpenReview discussion (https://openreview.net/forum?id=7l63xwAgAW). Specifically, the problem arose because Lemma C.5 incorrectly upper bounded the advantage function when it takes negative values. In the current version, we have addressed this issue by introducing Assumption 4.4. Using the proposed RRPO (Algorithm 1), there is a constant gap linearly depending on the uncertainty diameter 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.
As shown in Theorem 4.5, to achieve ϵ-accuracy to the optimal feasible policy π * up to a constant error term depending on the uncertainty diameter c, it takes at most O(ϵ -2 ) iterations. Here, we use a specific uncertainty set to illustrate how the O(ϵ -4 ) sample complexity is obtained. Assume we are considering the (s, a)-rectangular uncertainty set defined by the p-norm:
Let P 0 be the nominal distribution. Then (2) Their algorithm requires an additional binary search step, while our method preserves the simplicity of the CRPO framework without such overhead.
To better illustrate the impact of model uncertainty on the algorithm performance, especially on the worstcase feasibility, we conducted experiments comparing the proposed RRPO and the CRPO (Xu et al., 2021).
For all experiments, we used a discount factor γ = 0.99 and the 2-norm uncertainty set defined by Equation (10).
First, we consider a specific 4 × 6 FrozenLake-like gridworld environment: The agent starts from the left-top corner pos start = [1, 1] and can make four actions, We define two reward functions. The main reward function r 0 is defined as
It gives +1 for reaching the target, -1 for landing on a brown block, and -0.1 otherwise. The constraint reward function r 1 is defined as:
It assigns -1 for stepping out of the boundary or onto a brown block, and 0 otherwise, leading to a cost function c(s, a) := -E[r 1 (s, a, s ′ )]. We require -V π 1 (µ) < 0.2, ensuring the agent avoids hitting brown blocks 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 a "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 a worst-case scenario. Under this setting, the obstacles construct two distinct paths routing to the target, which is illustrated in Figure 2.
We apply our proposed RRPO to solve this constrained robust RL problem, comparing it with the baseline CRPO method. As shown in Figure 3a, our method successfully learns the safer path, while the non-robust algorithm converges to the shortest path.
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 its default reward function r 0 , which penalizes -1.0 each step and rewards 0 if the agent reaches the goal; that is, r 0 (s, a, s ′ ) = 0 if the agent reaches the goal, -1 otherwise.
To emphasize safety, we add a constraint reward function r 1 (s, a, s ′ ) defined as r 1 (s, a, s ′ ) = -1 if the car's speed exceeds 0.06, 0 otherwise.
It returns -1.0 whenever the car's speed exceeds 0.06 and returns 0 otherwise, which encourages the agent to maintain a safe speed throughout its run. We also consider its cost description as c(s, a) 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 in the worst-case environment.
Additionally, we compare the performance of the RRPO algorithm with other robust RL baselines, including the robust policy gradient and the robust primal-dual policy gradient methods, on the HalfCheetah-v4 environment from Robust Gymnasium (Gu et al., 2025). We also conduct an ablation study to evaluate the impact of our modification to 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 fit our setting. Therefore, we employ a custom energy constraint that penalizes energy consumption at each step. We include the experiment details and the hyper-parameter setting in Appendix D.4.
We conducted a comparative evaluation of three robust RL algorithms on the HalfCheetah-v4 environment 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:
encouraging rapid forward movement while penalizing excessive control effort. Crucially, we implement a separate energy constraint defined as the squared L 2 norm of the action vector
with a 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.
In the ablation experiment, we compare our RRPO algorithm with the Robust version of CRPO algorithm (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 in Algorithm 1 where the RRPO algorithm tracks the best feasible policy as the π out in the threshold update step. We follow the same setting as described in Appendix D.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, an additional source of variance arises from the random sampling of the output policy. As a result, CRPO exhibits substantially higher variance than RRPO.
Figure 5: Comparison of the variance of the primal reward r 0 of the output policy from CRPO (Xu et al., 2021) and the RRPO (Algorithm 1). The CRPO method exhibits substantially higher variance than RRPO.
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 guarantees for RRPO, ensuring that it converges to an approximately optimal policy up to a O(c)-level value function error that satisfies the constraints within a specified tolerance under worst-case scenarios. Empirical results validate the effectiveness of our approach. We believe our work opens new avenues for exploring and designing non-primal-dual 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.
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;Iyengar, 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 uncertainty 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 directly solving the worst-case transitions. Wang & Zou (2022) considers the R-contamination 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-case transition probability. And Kumar et al. (2023) provides the analytical solution for the p-norm uncertainty set. These advancements allow us 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 incorporating constraints into the agent's decision-making process, aiming to optimize performance while satisfying certain safety, 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 et al., 2019;Liang et al., 2018;Stooke et al., 2020), 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 methods, enforce constraints directly by projecting policies onto 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.
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 (2024) provide an intuitive explanation for why existing primal-dual methods for non-robust constrained RL 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 π,P is convex in the policy π; that is, there always exists a policy π ′ such that (1 -α)d π,P + αd π,P = 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 strictly 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 problems, which is what we aim to solve in this paper.
Proof. We divide the proof into three parts: (1) The construction of counterexample constrained robust MDP.
(2) The evaluation of Lagrangian function.
(3) The evaluation of the duality gap.
We consider the constrained robust MDP described in Figure 6 (which is the same as Figure 1). The nominal transition probability is explicitly defined as follows:
Then we obtain the state transition probability induced by the policy π:
where π 0 := π(a 0 |s 0 ) and π 1 := π(a 1 |s 0 ). The action at the state s 1 doesn't make any differences. The (i, j)-th entry of P π represents the probability of moving from s j to s i by following the policy π. We fix the initial state to s 0 . Its corresponding distribution is given by µ 0 = 1 0 . The reward for the objective value function is r 0 = 1 0 . The reward for the constraint is r 1 = 0 1 . Here, we only consider a single constraint.
Lastly, we consider the following (s, a)-uncertainty set defined by the L ∞ distance:
Then we obtain
It is easy to notice that when λ ≤ 1-p 1-p , the coefficient of π 1
We separately consider each case to solve the monotone intervals.
• Case 1:
We further consider if this upper bound is positive or negative.
Again, we further consider if this lower bound is positive or negative:
The maximum is either achieved at x 1 = 1 or x 1 = 0. We need to decide which one is larger: When x 1 = 1, we have
By letting L(1, λ) ≥ L(0, λ), we solve the boundary is
Combining both Case 2.1 and Case 2.2, we obtain
1+(1-p)γ . Now, combining both Case 1 and Case 2, we have
• Solve max π min λ L(π, λ):
We let the constraint be satisfied; that is
Otherwise, simply letting λ = +∞ will lead to -∞ function value. It solves
Since ρ must be less than 1 1-γ (so, --γ)ρ ≥ 0), we have
Therefore, the maximum is achieved at
Therefore, the duality gap is given by
When p = 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 ρ = 1. We have the non-zero duality gap
C Proof of Theorem 4.5
In this section, we provide the detailed proof of Theorem 4.5.
In this subsection, we recap the assumptions used in 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 can relax this assumption to a general [-r max , r max ] with changing the upper and lower bound of these value functions to be rmax 1-γ .
for all s ∈ S, a ∈ A, and i = 0, . . . , I. Assumption C.2 (Worst-Case Exploration). For any policy π and its worst-case transition P , there exists a positive constant p min > 0 such that its state visitation probability satisfies d π,P µ (s) ≥ p min for all s ∈ S, where d π,P µ is the state visitation distribution starting from initial distribution µ under policy π and transition P .
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 π ′ and π. Here we apply Assumption 4.2 to turn the upper and lower bound to transition this inequality to the desired distribution needed in our convergence analysis.
Lemma C.5 (Robust performance difference lemma). Let π, π ′ be two policies and P, P ′ be their worst-case transition kernels. Suppose that µ is the initial distribution over the state space S. Then
Proof. Equation ( 11) is given by Lemma 8 from Zhou et al. (2024).
Remark C.6. Moreover, we have
Lemma C.7. Let the NPG update rule be given by
where the normalization factor Z t := a∈A π t (a|s) exp η Qt (s, a)/(1 -γ) . Then
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 i is improved by updating π t to π t+1 using its corresponding robust policy gradient.
The first term
] is always non-negative. The second term ∆ t will be merged with other errors later.
Lemma C.8. Under the NPG update rule with learning rate η, the robust value functions with an arbitrary initial distribution ν satisfy the following inequality:
where the worst-case transition probability of the policy π t and π t+1 are P and P ′ , respectively, and the error term ∆ t is given by
Proof. Let the worst-case transition probability of the policy π t and π t+1 be P and P ′ , respectively. Their corresponding visitation probabilities are d πt,P ν (s) and d
where the first equality applies the definition of the worst-case advantage function A π (s, a) := Q π (s, a) -V π (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
Then we obtain
where (i) applies the definition of KL-divergence d KL (π t+1 (•|s)∥π t (•|s)) = a∈A π t+1 (a | s) log πt+1(a|s) πt (a|s) . By the definition of Z t , we have
where (i) applies the Jensen'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
where (i) we apply the change of measure to replace d
] 0 for all s by Equation ( 12), and (2)
Therefore, we conclude that
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 η, the robust value functions satisfy the following inequality:
where the worst-case transition probability of the worst-case optimal policy π * and π t+1 are P * and P ′ , respectively, and the visitation probability of π * is ν * (s) := d π * ,P * µ (s).
Proof. Let the worst-case transition probability of the worst-case optimal policy π * be P * and the visitation probability of π * be ν * (s) := d π * ,P * µ (s).
Define
where P t denotes the worst-case transition probability of π t .
Applying Lemma C.5 to the robust value function V π * it and V πt it (i = 0, 1, . . . , I), we obtain
where the first equality applies the definition of the worst-case advantage function A π (s, a) := Q π (s, a) -V π (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
Then we obtain
where (i) applies the definition of KL-divergence. By Lemma C.8, we have
Then we obtain
which is the final upper bound after applying the last inequality. Then we omit the term containing -D KL (π t+1 (•|s)∥π t (•|s)) since it is always non-positive.
The following lemma gives the condition such that N 0 is non-empty.
Lemma C.10. Consider the NPG update rule with learning rate η and let δ > 0 be chosen such that
where εapprox is an error term depending on the approximation error terms, ℓ is the Lipschitz constant of the state visitation distribution d π,P ν , and L is the Lipschitz constant of the robust value function V π i (ν * ), c is the diameter of the uncertainty set given by Assumption C.4. Under these conditions,
is sampled to update}, we have i t = i and by the algorithm design,
We sum the inequality obtained from Lemma C.9 over t = 1, 2, . . . , T . Since the robust value function V π (µ) is Lipschitz in π (Wang & Zou, 2021;Zhou et al., 2024), we have
Then we obtain
where ψ t is given by Equation ( 13) and εapprox is a constant upper bound (depending on Assumption 4.1) of C approx which is defined as
By appropriately choosing the policy evaluation algorithm (discussed in Appendix C.3), can be arbitrarily small.
We further take
where we apply the ℓ-Lipschitzness of the state visitation distribution (Lemma 5, Eq. ( 37), Chen & Huang (2024)). Then, we let
This hyper-parameter setting ensures that N 0 is non-empty.
In this section, we collect two important robust policy evaluation techniques to discuss how to use these methods to obtain the robust value function with sufficient accuracy. Though we use a simplified result in this subsection, these results have been extended to more general setting in original sources.
Lemma C.11 (Theorem 3, Zhou et al. (2024)). Let the value function V π is parameterized by w ∈ R |S| with the linear feature ϕ ∈ R |S| . Then using the Robust Linear TD-Learning proposed by Zhou et al. (2024) with step sizes
As shown by Li et 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,
The second term inf P ∈P V π (s ′ ) is given by Proposition 1 from Zhou et al. (2024). This result indicates that we can obtain the robust Q-function with the convergence rate 1 √ K (for the L ∞ -norm).
We consider the following uncertainty set:
where ω q (V ) := arg min ω ∥V -ω1 |S| ∥ q and κ q (V ) := min ω ∥V -ω1 |S| ∥ q .
Lemma C.12 (Theorem 4.2, Kumar et al. (2023)). If the uncertainty set is defined as the p-norm (s, a)rectangular set, then the worst-case transition probability P + (•|s, a) can be represented as
where β is the radius of the uncertainty set and O β,p (V ) is the balanced robust value function (Kumar et al., 2023).
Based on this result, we apply the following TD-learning update rule: where (i) applies 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 P 0 . Therefore, by applying existing TD-learning convergence analysis (Brandfonbrener & Bruna, 2019;Asadi et al., 2024;Li et al., 2024), we obtain that the convergence rate is also 1 √ K .
We also include a compact version of Algorithm 1 in Algorithm 3 which merges the constraint rectification and objective rectification together.
Here, we state the full version of Theorem 4.5. ν , and L is the Lipschitz constant of the robust value function V π i (ν * ), εapprox is the error caused by the robust policy evaluation step. Under these conditions, the output policy π out satisfies:
where the constraint violation of π out is guaranteed to be at most δ. Moreover, if setting
the robust policy evaluation error ϵ approx ≤ (1-γ) 2 12 ϵ, and the number of iteration step
then the output policy satisfies the ϵ-accuracy with a constant error; that is
Proof. By the update rule, the boundary value d 0 is non-decreasing. Since it is upper bounded, we conclude that {d t 0 } converges and we denote d t 0 → d0 as t → ∞. More explicitly, we have d0 = sup{V πt 0 :
There are only two cases for the output policy π out :
(1) The policy is better than the optimal policy while the relaxed constraint is violated; i.e.
V π * i (µ) -V πt+1 i (µ) ≤ 0.
(2) The output policy is worse than the optimal policy but upper bounded by O( 1 √ T ). When (1) holds, then it is desired. When (1) doesn't hold (i.e. V π * i (µ) -V This hyper-parameter setting ensures that Equation (15) does not hold. Therefore, it leads to a contradiction. We obtain |N 0 | ≥ T 2 . In this case, we have
Here the non-negativity is because V * (µ) is the largest-possible value function over the feasible policy. From the construction of N 0 and the output policy π out , they are all feasible policies. We are interested in obtaining the complexity of the convergence up to a constant value function error 4ℓ (1-γ) 2 c (typically, this term can be controlled by using a sufficiently small uncertainty set). To obtain the sample complexity, we set all three terms to be O(ϵ):
• To make the last term 2ε approx ≤ ϵ 3 , we set the robust policy evaluation error (Assumption 4.1) to be ∥ Q -Q∥ ∞ ≤ ϵ approx .
It leads to
It solves ϵ approx ≤ (1-γ) 2 12 ϵ.
• Let 2 ηT E s∼ν * D KL (π * (•|s)∥π 1 (•|s)) ≤ ϵ 3 . We obtain T ≥ 2 ηT E s∼ν * D KL (π * (•|s)∥π 1 (•|s)) 3 ϵ ≥ 2L (1 -γ) 2 In the second step, we require the learning rate η is not too small; that is, we let it larger than (1-γ) 2 2L ϵ 3 . This result indicate that the iteration complexity is T = O(ϵ -2 ), with choosing an appropriate learning rate η = Θ(ϵ) and the approximation error ϵ approx = O(ϵ).
This section outlines the information for replicating our experiments. Throughout our experiments, we include multiple independent runs and report the averaged metrics in our results. Specifically, we used three different random seeds.
Published in Transactions on Machine LearningResearch (08/2025)