mlsanityData to 7 Oct 2026

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

arXiv 2008.00311 ↗First posted 1 Aug 2020cs.LG stat.MLcited by 32

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 5; 2022: 5; 2023: 7; 2024: 8; 2025: 4; 2026: 3.

32 papers.

Sort:

By area:

  1. 2022Enforcing Hard Constraints with Soft Barriers: Safe Reinforcement Learning in Unknown Stochastic Environmentscited by 54
  2. 2021DOPE: Doubly Optimistic and Pessimistic Exploration for Safe Reinforcement Learningcited by 34
  3. 2025VLSA: Vision-Language-Action Models with Plug-and-Play Safety Constraint Layercited by 32
  4. 2023Soft Robust MDPs and Risk-Sensitive MDPs: Equivalence, Policy Gradient, and Sample Complexitycited by 16
  5. 2021RLOps: Development Life-cycle of Reinforcement Learning Aided Open RANcited by 15
  6. 2023A Near-Optimal Algorithm for Safe Reinforcement Learning Under Instantaneous Hard Constraintscited by 15
  7. 2021Reinforcement Learning with Almost Sure Constraintscited by 11
  8. 2024Near-Optimal Policy Identification in Robust Constrained Markov Decision Processes via Epigraph Formcited by 10
  9. 2022Provable Safe Reinforcement Learning with Binary Feedbackcited by 7
  10. 2024Latent Safety-Constrained Policy Approach for Safe Offline Reinforcement Learningcited by 7
  11. 2023Safe Posterior Sampling for Constrained MDPs with Bounded Constraint Violationcited by 6
  12. 2023ROSARL: Reward-Only Safe Reinforcement Learningcited by 5
20 more
  1. 2024A Policy Gradient Primal-Dual Algorithm for Constrained MDPs with Uniform PAC Guaranteescited by 5
  2. 2024What Are the Odds? Improving the foundations of Statistical Model Checkingcited by 5
  3. 2024Deterministic Policies for Constrained Reinforcement Learning in Polynomial Timecited by 5
  4. 2022Reinforcement Learning with a Terminatorcited by 4
  5. 2025Provably Efficient RL under Episode-Wise Safety in Constrained MDPs with Linear Function Approximationcited by 4
  6. 2023Provable Reset-free Reinforcement Learning by No-Regret Reductioncited by 3
  7. 2026Your Model Already Knows: Attention-Guided Safety Filter for Vision-Language-Action Modelscited by 3
  8. 2021Learning to Act Safely with Limited Exposure and Almost Sure Certaintycited by 2
  9. 2022Ablation Study of How Run Time Assurance Impacts the Training and Performance of Reinforcement Learning Agentscited by 2
  10. 2023Reinforcement Learning Under Probabilistic Spatio-Temporal Constraints with Time Windowscited by 2
  11. 2023Finite-Time Analysis of Three-Timescale Constrained Actor-Critic and Constrained Natural Actor-Critic Algorithmscited by 2
  12. 2022Finding Safe Zones of policies Markov Decision Processescited by 1
  13. 2024Structured Reinforcement Learning for Media Streaming at the Wireless Edgecited by 1
  14. 2024Anytime-Constrained Equilibria in Polynomial Timecited by 1
  15. 2025Polynomial-Time Approximability of Constrained Reinforcement Learningcited by 1
  16. 2026Near-Optimal Sample Complexity for Online Constrained MDPscited by 1
  17. 2021Reinforcement Learning for Finite-Horizon Restless Multi-Armed Multi-Action Banditscited by 0
  18. 2024Natural Policy Gradient and Actor Critic Methods for Constrained Multi-Task Reinforcement Learningcited by 0
  19. 2025Constrained Online Decision-Making: A Unified Frameworkcited by 0
  20. 2026LexiSafe: Offline Safe Reinforcement Learning with Lexicographic Safety-Reward Hierarchycited by 0