Rectified Robust Policy Optimization for Model-Uncertain Constrained Reinforcement Learning without Strong Duality

arXiv 2508.17448 ↗First posted 24 Aug 2025cs.LGcited by 4

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

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.

Key facts. Cited by 4 papers in the map (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 67 of its 96 references that are in the map. First posted on arXiv 24 Aug 2025.

Builds on

67 of 96 references.

Closest ancestors · 6

Same direction, newest first

Other references · 61

2021Convex optimizationcited by 2,515
2017Constrained Policy Optimizationcited by 983
2017Robust Adversarial Reinforcement Learningcited by 451
2018Reward Constrained Policy Optimizationcited by 417
2017Safe Model-based Reinforcement Learning with Stability Guaranteescited by 366
2015Risk-Constrained Reinforcement Learning with Percentile Risk Criteriacited by 337
2020Responsive Safety in Reinforcement Learning by PID Lagrangian Methodscited by 316
2018A Lyapunov-based Approach to Safe Reinforcement Learningcited by 297
2018Safe Exploration in Continuous Action Spacescited by 247
2020Projection-Based Constrained Policy Optimizationcited by 203
2019Neural Policy Gradient Methods: Global Optimality and Rates of Convergencecited by 159
2019Constrained Reinforcement Learning Has Zero Duality Gapcited by 151

38 more

2020A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Criticcited by 144
2020CRPO: A New Approach for Safe Reinforcement Learning with Convergence Guaranteecited by 134
2020Safe Reinforcement Learning in Constrained Markov Decision Processescited by 115
2021Online Robust Reinforcement Learning with Model Uncertaintycited by 96
2021Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysiscited by 92
2021Sample Complexity of Robust Reinforcement Learning with a Generative Modelcited by 83
2018Safe Reinforcement Learning with Model Uncertainty Estimatescited by 72
2022Policy Gradient Method For Robust Reinforcement Learningcited by 69
2018Accelerated Primal-Dual Policy Optimization for Safe Reinforcement Learningcited by 62
2022Enforcing Hard Constraints with Soft Barriers: Safe Reinforcement Learning in Unknown Stochastic Environmentscited by 60
2022Safe Reinforcement Learning via Shielding under Partial Observabilitycited by 56
2017Reinforcement Learning under Model Mismatchcited by 52
2023Double Pessimism is Provably Efficient for Distributionally Robust Offline Reinforcement Learning: Generic Algorithm and Robust Partial Coveragecited by 51
2021Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Primal-Dual Approachcited by 50
2021Twice regularized MDPs and the equivalence between robustness and regularizationcited by 47
2022Policy Gradient in Robust MDPs with Global Convergence Guaranteecited by 38
2022Near-Optimal Sample Complexity Bounds for Constrained MDPscited by 37
2023Natural Actor-Critic for Robust Reinforcement Learning with Function Approximationcited by 36
2023Robust Multi-Agent Reinforcement Learning with State Uncertaintycited by 36
2020Robust Inverse Reinforcement Learning under Transition Dynamics Mismatchcited by 33
2022Distributionally Robust Offline Reinforcement Learning with Linear Function Approximationcited by 32
2022First-order Policy Optimization for Robust Markov Decision Processcited by 32
2023Policy Gradient for Rectangular Robust Markov Decision Processescited by 31
2020Bayesian Robust Optimization for Imitation Learningcited by 28
2020Scalable First-Order Methods for Robust MDPscited by 25
2023Seeing is not Believing: Robust Reinforcement Learning against Spurious Correlationcited by 25
2020Robust Constrained-MDPs: Soft-Constrained Robust Policy Optimization under Model Uncertaintycited by 23
2022What is the Solution for State-Adversarial Multi-Agent Reinforcement Learning?cited by 22
2020Robust Reinforcement Learning with Wasserstein Constraintcited by 21
2023Trust Region-Based Safe Distributional Reinforcement Learning for Multiple Constraintscited by 21
2024Balance Reward and Safety Optimization for Safe Reinforcement Learning: A Perspective of Gradient Manipulationcited by 21
2022Finite-Time Analysis of Entropy-Regularized Neural Natural Actor-Critic Algorithmcited by 20
2014Proximal Reinforcement Learning: A New Theory of Sequential Decision Making in Primal-Dual Spacescited by 19
2023Constraint-Conditioned Policy Optimization for Versatile Safe Reinforcement Learningcited by 18
2024Minimax Optimal and Computationally Efficient Algorithms for Distributionally Robust Offline Reinforcement Learningcited by 18
2013Scaling Up Robust MDPs by Reinforcement Learningcited by 17
2023TD Convergence: An Optimization Perspectivecited by 16
2016Stochastic Primal-Dual Methods and Sample Complexity of Reinforcement Learningcited by 15

50 most cited of 61 All 61 (JSON)

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 3; 2026: 1.

4 papers.

2025Primal-Only Actor Critic Algorithm for Robust Constrained Average Cost MDPscited by 1
2025Provably Efficient Sample Complexity for Robust CMDPcited by 1
2025Robust Reinforcement Learning in Finance: Modeling Market Impact with Elliptic Uncertainty Setscited by 0
2026Optimistic Policy Learning under Pessimistic Adversaries with Regret and Violation Guaranteescited by 0

Similar, not cited

Close in wording, no citation either way