# Provably Efficient Sample Complexity for Robust CMDP

arXiv: https://arxiv.org/abs/2511.07486 · HTML: https://mlsanity.com/paper/2511.07486/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 37 of its 61 references that are in the map.
- First posted on arXiv 10 Nov 2025.

## Builds on (most cited first, 30 of 37)

- [Constrained Policy Optimization](https://mlsanity.com/paper/1705.10528/) (2017)
- [Reward Constrained Policy Optimization](https://mlsanity.com/paper/1805.11074/) (2018)
- [Responsive Safety in Reinforcement Learning by PID Lagrangian Methods](https://mlsanity.com/paper/2007.03964/) (2020)
- [A Lyapunov-based Approach to Safe Reinforcement Learning](https://mlsanity.com/paper/1805.07708/) (2018)
- [Safe Exploration in Continuous Action Spaces](https://mlsanity.com/paper/1801.08757/) (2018)
- [Projection-Based Constrained Policy Optimization](https://mlsanity.com/paper/2010.03152/) (2020)
- [Exploration-Exploitation in Constrained MDPs](https://mlsanity.com/paper/2003.02189/) (2020)
- [Provably Efficient Safe Exploration via Primal-Dual Policy Optimization](https://mlsanity.com/paper/2003.00534/) (2020)
- [CRPO: A New Approach for Safe Reinforcement Learning with Convergence Guarantee](https://mlsanity.com/paper/2011.05869/) (2020)
- [Online Robust Reinforcement Learning with Model Uncertainty](https://mlsanity.com/paper/2109.14523/) (2021)
- [Robust Reinforcement Learning using Offline Data](https://mlsanity.com/paper/2208.05129/) (2022)
- [Sample Complexity of Robust Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2112.01506/) (2021)
- [Safe Policies for Reinforcement Learning via Primal-Dual Methods](https://mlsanity.com/paper/1911.09101/) (2019)
- [Accelerated Primal-Dual Policy Optimization for Safe Reinforcement Learning](https://mlsanity.com/paper/1802.06480/) (2018)
- [Convergent Policy Optimization for Safe Reinforcement Learning](https://mlsanity.com/paper/1910.12156/) (2019)
- [The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2305.16589/) (2023)
- [Constrained Upper Confidence Reinforcement Learning](https://mlsanity.com/paper/2001.09377/) (2020)
- [Improved Sample Complexity Bounds for Distributionally Robust Reinforcement Learning](https://mlsanity.com/paper/2303.02783/) (2023)
- [Policy Gradient in Robust MDPs with Global Convergence Guarantee](https://mlsanity.com/paper/2212.10439/) (2022)
- [Near-Optimal Sample Complexity Bounds for Constrained MDPs](https://mlsanity.com/paper/2206.06270/) (2022)
- [A Finite Sample Complexity Bound for Distributionally Robust Q-learning](https://mlsanity.com/paper/2302.13203/) (2023)
- [A Dual Approach to Constrained Markov Decision Processes with Entropy Regularization](https://mlsanity.com/paper/2110.08923/) (2021)
- [Distributionally Robust Offline Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2209.06620/) (2022)
- [Regret Bounds for Risk-Sensitive Reinforcement Learning](https://mlsanity.com/paper/2210.05650/) (2022)
- [Policy Optimization for Constrained MDPs with Provable Fast Global Convergence](https://mlsanity.com/paper/2111.00552/) (2021)
- [Towards Minimax Optimality of Model-based Robust Reinforcement Learning](https://mlsanity.com/paper/2302.05372/) (2023)
- [Model-Free Robust Average-Reward Reinforcement Learning](https://mlsanity.com/paper/2305.10504/) (2023)
- [Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process](https://mlsanity.com/paper/2110.10351/) (2021)
- [Robust Constrained Reinforcement Learning for Continuous Control with Model Misspecification](https://mlsanity.com/paper/2010.10644/) (2020)
- [Single-Trajectory Distributionally Robust Reinforcement Learning](https://mlsanity.com/paper/2301.11721/) (2023)

## Built on by (most cited first, 1 of 1)

- [Towards Reliable, Generalizable, and Specific In-Context Knowledge Editing via Multi-Objective Reinforcement Learning](https://mlsanity.com/paper/2608.25100/) (2026)

## 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.