Provably Efficient Sample Complexity for Robust CMDP
Not on the map. Why?
Abstract (arXiv)
We study the problem of learning policies that maximize cumulative reward while satisfying safety constraints, even when the real environment differs from a simulator or nominal model. We focus on robust constrained Markov decision processes (RCMDPs), where the agent must maximize reward while ensuring cumulative utility exceeds a threshold under the worst-case dynamics within an uncertainty set. While recent works have established finite-time iteration complexity guarantees for RCMDPs using policy optimization, their sample complexity guarantees remain largely unexplored. In this paper, we first show that Markovian policies may fail to be optimal even under rectangular uncertainty sets unlike the em unconstrained robust MDP. To address this, we introduce an augmented state space that incorporates the remaining utility budget into the state representation. Building on this formulation, we propose a novel Robust constrained Value iteration (RCVI) algorithm with a sample complexity of mathcaltildeO(|S||A|H5/ε2) achieving at most ε violation using a generative model where |S| and |A| denote the sizes of the state and action spaces, respectively, and H is the episode length. To the best of our knowledge, this is the em first sample complexity guarantee for RCMDP. Empirical results further validate the effectiveness of our approach.
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 37 of its 61 references that are in the map. First posted on arXiv 10 Nov 2025.
Builds on
37 of 61 references.
References · 37
- 2017Constrained Policy Optimizationcited by 928
- 2018Reward Constrained Policy Optimizationcited by 397
- 2020Responsive Safety in Reinforcement Learning by PID Lagrangian Methodscited by 302
- 2018A Lyapunov-based Approach to Safe Reinforcement Learningcited by 278
- 2018Safe Exploration in Continuous Action Spacescited by 237
- 2020Projection-Based Constrained Policy Optimizationcited by 195
- 2020Exploration-Exploitation in Constrained MDPscited by 146
- 2020Provably Efficient Safe Exploration via Primal-Dual Policy Optimizationcited by 131
- 2020CRPO: A New Approach for Safe Reinforcement Learning with Convergence Guaranteecited by 128
- 2021Online Robust Reinforcement Learning with Model Uncertaintycited by 95
- 2022Robust Reinforcement Learning using Offline Datacited by 95
- 2021Sample Complexity of Robust Reinforcement Learning with a Generative Modelcited by 82
25 more
- 2019Safe Policies for Reinforcement Learning via Primal-Dual Methodscited by 75
- 2018Accelerated Primal-Dual Policy Optimization for Safe Reinforcement Learningcited by 61
- 2019Convergent Policy Optimization for Safe Reinforcement Learningcited by 55
- 2023The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Modelcited by 50
- 2020Constrained Upper Confidence Reinforcement Learningcited by 46
- 2023Improved Sample Complexity Bounds for Distributionally Robust Reinforcement Learningcited by 44
- 2022Near-Optimal Sample Complexity Bounds for Constrained MDPscited by 36
- 2022Policy Gradient in Robust MDPs with Global Convergence Guaranteecited by 35
- 2023A Finite Sample Complexity Bound for Distributionally Robust Q-learningcited by 35
- 2021A Dual Approach to Constrained Markov Decision Processes with Entropy Regularizationcited by 33
- 2022Distributionally Robust Offline Reinforcement Learning with Linear Function Approximationcited by 31
- 2022Regret Bounds for Risk-Sensitive Reinforcement Learningcited by 26
- 2021Policy Optimization for Constrained MDPs with Provable Fast Global Convergencecited by 22
- 2023Towards Minimax Optimality of Model-based Robust Reinforcement Learningcited by 21
- 2023Model-Free Robust Average-Reward Reinforcement Learningcited by 20
- 2021Faster Algorithm and Sharper Analysis for Constrained Markov Decision Processcited by 18
- 2020Robust Constrained Reinforcement Learning for Continuous Control with Model Misspecificationcited by 16
- 2023Single-Trajectory Distributionally Robust Reinforcement Learningcited by 15
- 2024A Reductions Approach to Risk-Sensitive Reinforcement Learning with Optimized Certainty Equivalentscited by 15
- 2024Distributionally Robust Constrained Reinforcement Learning under Strong Dualitycited by 15
- 2022Robust Constrained Reinforcement Learningcited by 14
- 2024Sample Complexity of Offline Distributionally Robust Linear Markov Decision Processescited by 12
- 2024Near-Optimal Policy Identification in Robust Constrained Markov Decision Processes via Epigraph Formcited by 10
- 2025Efficient Policy Optimization in Robust Constrained MDPs with Iteration Complexity Guaranteescited by 6
- 2025Rectified Robust Policy Optimization for Model-Uncertain Constrained Reinforcement Learning without Strong Dualitycited by 4
Built on by
Citing papers per year: 2026: 1.
1 paper.