# Learning with Safety Constraints: Sample Complexity of Reinforcement Learning for Constrained MDPs

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

## Key facts

- Cited by 32 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Aug 2020.

## Built on by (most cited first, 30 of 32)

- [Enforcing Hard Constraints with Soft Barriers: Safe Reinforcement Learning in Unknown Stochastic Environments](https://mlsanity.com/paper/2209.15090/) (2022)
- [DOPE: Doubly Optimistic and Pessimistic Exploration for Safe Reinforcement Learning](https://mlsanity.com/paper/2112.00885/) (2021)
- [VLSA: Vision-Language-Action Models with Plug-and-Play Safety Constraint Layer](https://mlsanity.com/paper/2512.11891/) (2025)
- [A Near-Optimal Algorithm for Safe Reinforcement Learning Under Instantaneous Hard Constraints](https://mlsanity.com/paper/2302.04375/) (2023)
- [Soft Robust MDPs and Risk-Sensitive MDPs: Equivalence, Policy Gradient, and Sample Complexity](https://mlsanity.com/paper/2306.11626/) (2023)
- [RLOps: Development Life-cycle of Reinforcement Learning Aided Open RAN](https://mlsanity.com/paper/2111.06978/) (2021)
- [Reinforcement Learning with Almost Sure Constraints](https://mlsanity.com/paper/2112.05198/) (2021)
- [Near-Optimal Policy Identification in Robust Constrained Markov Decision Processes via Epigraph Form](https://mlsanity.com/paper/2408.16286/) (2024)
- [Provable Safe Reinforcement Learning with Binary Feedback](https://mlsanity.com/paper/2210.14492/) (2022)
- [Latent Safety-Constrained Policy Approach for Safe Offline Reinforcement Learning](https://mlsanity.com/paper/2412.08794/) (2024)
- [Safe Posterior Sampling for Constrained MDPs with Bounded Constraint Violation](https://mlsanity.com/paper/2301.11547/) (2023)
- [A Policy Gradient Primal-Dual Algorithm for Constrained MDPs with Uniform PAC Guarantees](https://mlsanity.com/paper/2401.17780/) (2024)
- [Provably Efficient RL under Episode-Wise Safety in Constrained MDPs with Linear Function Approximation](https://mlsanity.com/paper/2502.10138/) (2025)
- [Ablation Study of How Run Time Assurance Impacts the Training and Performance of Reinforcement Learning Agents](https://mlsanity.com/paper/2207.04117/) (2022)
- [ROSARL: Reward-Only Safe Reinforcement Learning](https://mlsanity.com/paper/2306.00035/) (2023)
- [What Are the Odds? Improving the foundations of Statistical Model Checking](https://mlsanity.com/paper/2404.05424/) (2024)
- [Deterministic Policies for Constrained Reinforcement Learning in Polynomial Time](https://mlsanity.com/paper/2405.14183/) (2024)
- [Reinforcement Learning with a Terminator](https://mlsanity.com/paper/2205.15376/) (2022)
- [Your Model Already Knows: Attention-Guided Safety Filter for Vision-Language-Action Models](https://mlsanity.com/paper/2606.09749/) (2026)
- [Provable Reset-free Reinforcement Learning by No-Regret Reduction](https://mlsanity.com/paper/2301.02389/) (2023)
- [Learning to Act Safely with Limited Exposure and Almost Sure Certainty](https://mlsanity.com/paper/2105.08748/) (2021)
- [Reinforcement Learning Under Probabilistic Spatio-Temporal Constraints with Time Windows](https://mlsanity.com/paper/2307.15910/) (2023)
- [Finite-Time Analysis of Three-Timescale Constrained Actor-Critic and Constrained Natural Actor-Critic Algorithms](https://mlsanity.com/paper/2310.16363/) (2023)
- [Finding Safe Zones of policies Markov Decision Processes](https://mlsanity.com/paper/2202.11593/) (2022)
- [Structured Reinforcement Learning for Media Streaming at the Wireless Edge](https://mlsanity.com/paper/2404.07315/) (2024)
- [Anytime-Constrained Equilibria in Polynomial Time](https://mlsanity.com/paper/2410.23637/) (2024)
- [Polynomial-Time Approximability of Constrained Reinforcement Learning](https://mlsanity.com/paper/2502.07764/) (2025)
- [Constrained Online Decision-Making: A Unified Framework](https://mlsanity.com/paper/2505.07101/) (2025)
- [Near-Optimal Sample Complexity for Online Constrained MDPs](https://mlsanity.com/paper/2602.15076/) (2026)
- [Reinforcement Learning for Finite-Horizon Restless Multi-Armed Multi-Action Bandits](https://mlsanity.com/paper/2109.09855/) (2021)

## Abstract (arXiv)

Many physical systems have underlying safety considerations that require that the policy employed ensures the satisfaction of a set of constraints. The analytical formulation usually takes the form of a Constrained Markov Decision Process (CMDP). We focus on the case where the CMDP is unknown, and RL algorithms obtain samples to discover the model and compute an optimal constrained policy. Our goal is to characterize the relationship between safety constraints and the number of samples needed to ensure a desired level of accuracy -- both objective maximization and constraint satisfaction -- in a PAC sense. We explore two classes of RL algorithms, namely, (i) a generative model based approach, wherein samples are taken initially to estimate a model, and (ii) an online approach, wherein the model is updated as samples are obtained. Our main finding is that compared to the best known bounds of the unconstrained regime, the sample complexity of constrained RL algorithms are increased by a factor that is logarithmic in the number of constraints, which suggests that the approach may be easily utilized in real systems.