Provably Efficient Sample Complexity for Robust CMDP
This work addresses the challenge of safe reinforcement learning in uncertain environments, providing a foundational theoretical guarantee for sample efficiency, which is incremental as it builds on prior iteration complexity results.
The paper tackles the problem of learning policies that maximize reward while satisfying safety constraints under worst-case dynamics in robust constrained Markov decision processes (RCMDPs), achieving a sample complexity of Õ(|S||A|H^5/ε^2) with at most ε violation, which is the first such guarantee for RCMDPs.
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 $\mathcal{\tilde{O}}(|S||A|H^5/ε^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.