Provably Efficient Sample Complexity for Robust CMDP

2025/11/10 by S. Ganguly, Ganguly, Sourav, Ghosh, Arnob
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Adversarial Robustness in Machine Learning #FOS: Computer and information sciences #FOS: Electrical engineering #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Reinforcement Learning in Robotics #Systems and Control (eess.SY) #electronic engineering #information engineering

paper · pdf · doi:10.48550/arxiv.2511.07486

openalex publication_date 2025/11/10 · openalex created_date 2025/11/13 · openalex updated_date 2026/07/28

Abstract

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 \mathcalO(|S||A|H⁵/ε²) 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.

Citations

• Rectified Robust Policy Optimization for Model-Uncertain Constrained Reinforcement Learning without Strong Duality
• Efficient Policy Optimization in Robust Constrained MDPs with Iteration Complexity Guarantees
• Near-Optimal Policy Identification in Robust Constrained Markov Decision Processes via Epigraph Form
• Distributionally Robust Constrained Reinforcement Learning under Strong Duality
• Sample Complexity of Offline Distributionally Robust Linear Markov Decision Processes
• A Reductions Approach to Risk-Sensitive Reinforcement Learning with Optimized Certainty Equivalents
• The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Model
• Model-Free Robust Average-Reward Reinforcement Learning
• A Finite Sample Complexity Bound for Distributionally Robust Q-learning
• Towards Minimax Optimality of Model-based Robust Reinforcement Learning
• Single-Trajectory Distributionally Robust Reinforcement Learning
• Regret Bounds for Risk-Sensitive Reinforcement Learning
• Robust Constrained Reinforcement Learning
• Distributionally Robust Offline Reinforcement Learning with Linear Function Approximation
• Robust Reinforcement Learning using Offline Data
• Near-Optimal Sample Complexity Bounds for Constrained MDPs
• Sample Complexity of Robust Reinforcement Learning with a Generative\n Model
• Policy Optimization for Constrained MDPs with Provable Fast Global Convergence
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process
• A Dual Approach to Constrained Markov Decision Processes with Entropy Regularization
• Online Robust Reinforcement Learning with Model Uncertainty
• CRPO: A New Approach for Safe Reinforcement Learning with Convergence Guarantee
• Robust Constrained Reinforcement Learning for Continuous Control with Model Misspecification
• Responsive Safety in Reinforcement Learning by PID Lagrangian Methods
• Projection-Based Constrained Policy Optimization
• Exploration-Exploitation in Constrained MDPs
• Provably Efficient Safe Exploration via Primal-Dual Policy Optimization
• Constrained Upper Confidence Reinforcement Learning
• Safe Policies for Reinforcement Learning via Primal-Dual Methods
• Convergent Policy Optimization for Safe Reinforcement Learning
• Reward Constrained Policy Optimization
• A Lyapunov-based Approach to Safe Reinforcement Learning
• Accelerated Primal-Dual Policy Optimization for Safe Reinforcement Learning
• Safe Exploration in Continuous Action Spaces
• Constrained Policy Optimization
• Robust Markov Decision Processes
• Robust Dynamic Programming

Related

• Efficient Policy Optimization in Robust Constrained MDPs with Iteration Complexity Guarantees
• Sample Complexity Bounds for Linear Constrained MDPs with a Generative Model
• Near-Optimal Sample Complexity Bounds for Constrained MDPs
• Provably Efficient RL under Episode-Wise Safety in Constrained MDPs with Linear Function Approximation
• Towards Minimax Optimality of Model-based Robust Reinforcement Learning