Near-Optimal Sample Complexity for Online Constrained MDPs
Not on the map. Why?
Abstract (arXiv)
Safety is a fundamental challenge in reinforcement learning (RL), particularly in real-world applications such as autonomous driving, robotics, and healthcare. To address this, Constrained Markov Decision Processes (CMDPs) are commonly used to enforce safety constraints while optimizing performance. However, existing methods often suffer from significant safety violations or require a high sample complexity to generate near-optimal policies. We address two settings: relaxed feasibility, where small violations are allowed, and strict feasibility, where no violation is allowed. We propose a model-based primal-dual algorithm that balances regret and bounded constraint violations, drawing on techniques from online RL and constrained optimization. For relaxed feasibility, we prove that our algorithm returns an varepsilon-optimal policy with varepsilon-bounded violation with arbitrarily high probability, requiring tildeOleft(fracSAH3varepsilon2right) learning episodes, matching the lower bound for unconstrained MDPs. For strict feasibility, we prove that our algorithm returns an varepsilon-optimal policy with zero violation with arbitrarily high probability, requiring tildeOleft(fracSAH5varepsilon2zeta2right) learning episodes, where zeta is the problem-dependent Slater constant characterizing the size of the feasible region. This result matches the lower bound for learning CMDPs with access to a generative model. Our results demonstrate that learning CMDPs in an online setting is as easy as learning with a generative model and is no more challenging than learning unconstrained MDPs when small violations are allowed.
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 28 of its 40 references that are in the map. First posted on arXiv 16 Feb 2026.
Builds on
28 of 40 references.
References · 28
- 2017Constrained Policy Optimizationcited by 928
- 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
- 2018Is Q-learning Provably Efficient?cited by 485
- 2018Reward Constrained Policy Optimizationcited by 397
- 2020Responsive Safety in Reinforcement Learning by PID Lagrangian Methodscited by 302
- 2020Exploration-Exploitation in Constrained MDPscited by 146
- 2019Constrained Reinforcement Learning Has Zero Duality Gapcited by 144
- 2020Provably Efficient Safe Exploration via Primal-Dual Policy Optimizationcited by 131
- 2016Why is Posterior Sampling Better than Optimism for Reinforcement Learning?cited by 116
- 2020Safe Reinforcement Learning in Constrained Markov Decision Processescited by 109
- 2015Sample Complexity of Episodic Fixed-Horizon Reinforcement Learningcited by 105
- 2020Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisitedcited by 104
16 more
- 2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
- 2021Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPscited by 78
- 2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 51
- 2021UCB Momentum Q-learning: Correcting the bias without forgettingcited by 45
- 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 44
- 2022Near-Optimal Sample Complexity Bounds for Constrained MDPscited by 36
- 2021DOPE: Doubly Optimistic and Pessimistic Exploration for Safe Reinforcement Learningcited by 34
- 2021Safe Reinforcement Learning with Linear Function Approximationcited by 33
- 2020Learning with Safety Constraints: Sample Complexity of Reinforcement Learning for Constrained MDPscited by 32
- 2019Online Primal-Dual Mirror Descent under Stochastic Constraintscited by 31
- 2021Efficient Local Planning with Linear Function Approximationcited by 21
- 2021Provably Efficient Algorithms for Multi-Objective Competitive RLcited by 20
- 2024Sample-Efficient Constrained Reinforcement Learning with General Parameterizationcited by 11
- 2022Towards Painless Policy Optimization for Constrained MDPscited by 8
- 2022A Near-Optimal Primal-Dual Method for Off-Policy Learning in CMDPcited by 5
- 2024Confident Natural Policy Gradient for Local Planning in qπ-realizable Constrained MDPscited by 4
Built on by
Citing papers per year: 2026: 1.
1 paper.