mlsanityData to 7 Oct 2026

Near-Optimal Sample Complexity Bounds for Constrained MDPs

arXiv 2206.06270 ↗First posted 13 Jun 2022cs.LG stat.MLcited by 36

Not on the map. Why?

Abstract (arXiv)

In contrast to the advances in characterizing the sample complexity for solving Markov decision processes (MDPs), the optimal statistical complexity for solving constrained MDPs (CMDPs) remains unknown. We resolve this question by providing minimax upper and lower bounds on the sample complexity for learning near-optimal policies in a discounted CMDP with access to a generative model (simulator). In particular, we design a model-based algorithm that addresses two settings: (i) relaxed feasibility, where small constraint violations are allowed, and (ii) strict feasibility, where the output policy is required to satisfy the constraint. For (i), we prove that our algorithm returns an ε-optimal policy with probability 1 - δ, by making tildeOleft(fracS A log(1/δ)(1 - γ)3 ε2right) queries to the generative model, thus matching the sample-complexity for unconstrained MDPs. For (ii), we show that the algorithm's sample complexity is upper-bounded by tildeO left(fracS A , log(1/δ)(1 - γ)5 , ε2 zeta2 right) where zeta is the problem-dependent Slater constant that characterizes the size of the feasible region. Finally, we prove a matching lower-bound for the strict feasibility setting, thus obtaining the first near minimax optimal bounds for discounted CMDPs. Our results show that learning CMDPs is as easy as MDPs when small constraint violations are allowed, but inherently more difficult when we demand zero constraint violation.

Key facts. Cited by 36 papers in the map (data through 7 Oct 2026). Builds on 21 of its 42 references that are in the map. First posted on arXiv 13 Jun 2022.

Builds on

21 of 42 references.

References · 21

  1. 2017Constrained Policy Optimizationcited by 928
  2. 2018Reward Constrained Policy Optimizationcited by 397
  3. 2018Sim-to-Real: Learning Agile Locomotion For Quadruped Robotscited by 277
  4. 2020Exploration-Exploitation in Constrained MDPscited by 146
  5. 2019Constrained Reinforcement Learning Has Zero Duality Gapcited by 144
  6. 2019TossingBot: Learning to Throw Arbitrary Objects with Residual Physicscited by 131
  7. 2020Provably Efficient Safe Exploration via Primal-Dual Policy Optimizationcited by 131
  8. 2020CRPO: A New Approach for Safe Reinforcement Learning with Convergence Guaranteecited by 128
  9. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 124
  10. 2020Safe Reinforcement Learning in Constrained Markov Decision Processescited by 109
  11. 2020Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Modelcited by 108
  12. 2020Constrained Upper Confidence Reinforcement Learningcited by 46
9 more
  1. 2021Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Primal-Dual Approachcited by 46
  2. 2021A Primal-Dual Approach to Constrained Markov Decision Processescited by 42
  3. 2020A Sample-Efficient Algorithm for Episodic Finite-Horizon MDP with Constraintscited by 34
  4. 2020Constrained episodic reinforcement learning in concave-convex and knapsack settingscited by 33
  5. 2021A Simple Reward-free Approach to Constrained Reinforcement Learningcited by 28
  6. 2021Provably Efficient Algorithms for Multi-Objective Competitive RLcited by 20
  7. 2021A Provably-Efficient Model-Free Algorithm for Constrained Markov Decision Processescited by 17
  8. 2022Towards Painless Policy Optimization for Constrained MDPscited by 8
  9. 2019How Does an Approximate Model Help in Reinforcement Learning?cited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 3; 2023: 8; 2024: 10; 2025: 10; 2026: 5.

36 papers.

Sort:

  1. 2022Provably Efficient Model-Free Constrained RL with Linear Function Approximationcited by 29
  2. 2023Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPscited by 27
  3. 2024ActSafe: Active Exploration with Safety Constraints for Reinforcement Learningcited by 22
  4. 2022Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Modelcited by 15
  5. 2022Safe Linear Bandits over Unknown Polytopescited by 13
  6. 2024Sample-Efficient Constrained Reinforcement Learning with General Parameterizationcited by 11
  7. 2023Pure Exploration in Bandits with Linear Constraintscited by 10
  8. 2023A safe exploration approach to constrained Markov decision processescited by 10
  9. 2023Provably Learning Nash Policies in Constrained Markov Potential Gamescited by 7
  10. 2025Provably Efficient RL for Linear MDPs under Instantaneous Safety Constraints in Non-Convex Feature Spacescited by 6
  11. 2025Efficient Policy Optimization in Robust Constrained MDPs with Iteration Complexity Guaranteescited by 6
  12. 2023Online Nonstochastic Control with Adversarial and Static Constraintscited by 5
24 more
  1. 2024A Policy Gradient Primal-Dual Algorithm for Constrained MDPs with Uniform PAC Guaranteescited by 5
  2. 2024Deterministic Policies for Constrained Reinforcement Learning in Polynomial Timecited by 5
  3. 2024Confident Natural Policy Gradient for Local Planning in qπ-realizable Constrained MDPscited by 4
  4. 2025Provably Efficient RL under Episode-Wise Safety in Constrained MDPs with Linear Function Approximationcited by 4
  5. 2025Rectified Robust Policy Optimization for Model-Uncertain Constrained Reinforcement Learning without Strong Dualitycited by 4
  6. 2023Think Before You Duel: Understanding Complexities of Preference Learning under Constrained Resourcescited by 3
  7. 2025Near-Optimal Sample Complexity Bounds for Constrained Average-Reward MDPscited by 3
  8. 2025Reinforcement Learning with Imperfect Transition Predictions: A Bellman-Jensen Approachcited by 3
  9. 2024Last-Iterate Global Convergence of Policy Gradients for Constrained Reinforcement Learningcited by 2
  10. 2025Primal-Dual Sample Complexity Bounds for Constrained Markov Decision Processes with Multiple Constraintscited by 2
  11. 2023Anytime-Competitive Reinforcement Learning with Policy Priorcited by 1
  12. 2024Structured Reinforcement Learning for Media Streaming at the Wireless Edgecited by 1
  13. 2024SaVeR: Optimal Data Collection Strategy for Safe Policy Evaluation in Tabular MDPcited by 1
  14. 2024Anytime-Constrained Equilibria in Polynomial Timecited by 1
  15. 2025Polynomial-Time Approximability of Constrained Reinforcement Learningcited by 1
  16. 2025Provably Efficient Sample Complexity for Robust CMDPcited by 1
  17. 2026Constrained Meta Reinforcement Learning with Provable Test-Time Safetycited by 1
  18. 2026Near-Optimal Sample Complexity for Online Constrained MDPscited by 1
  19. 2023Semi-Infinitely Constrained Markov Decision Processes and Efficient Reinforcement Learningcited by 0
  20. 2024Last-Iterate Convergence of General Parameterized Policies in Constrained MDPscited by 0
  21. 2025Near-Optimal Reinforcement Learning for Constrained Recurrence Objectivescited by 0
  22. 2026Sampling-Based Safe Reinforcement Learningcited by 0
  23. 2026Constrained Multi-Objective Reinforcement Learning with Max-Min Criterioncited by 0
  24. 2026Learning Chance-Constrained MDPs with Bellman Distributional Certificatescited by 0