Primal-Dual Sample Complexity Bounds for Constrained Markov Decision Processes with Multiple Constraints
Not on the map. Why?
Abstract (arXiv)
This paper addresses the challenge of solving Constrained Markov Decision Processes (CMDPs) with d > 1 constraints when the transition dynamics are unknown, but samples can be drawn from a generative model. We propose a model-based algorithm for infinite horizon CMDPs with multiple constraints in the tabular setting, aiming to derive and prove sample complexity bounds for learning near-optimal policies. Our approach tackles both the relaxed and strict feasibility settings, where relaxed feasibility allows some constraint violations, and strict feasibility requires adherence to all constraints. The main contributions include the development of the algorithm and the derivation of sample complexity bounds for both settings. For the relaxed feasibility setting we show that our algorithm requires tildeO left( fracd |S| |A| log(1/δ)(1-γ)3ε2 right) samples to return ε-optimal policy, while in the strict feasibility setting it requires tildeO left( fracd3 |S| |A| log(1/δ)(1-γ)5ε2zetac^*2 right) samples.
Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 10 of its 17 references that are in the map. First posted on arXiv 9 Mar 2025.
Builds on
10 of 17 references.
References · 10
- 2018Reward Constrained Policy Optimizationcited by 397
- 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
- 2020CRPO: A New Approach for Safe Reinforcement Learning with Convergence Guaranteecited by 128
- 2020Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Modelcited by 108
- 2021Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Primal-Dual Approachcited by 46
- 2022Near-Optimal Sample Complexity Bounds for Constrained MDPscited by 36
- 2020Constrained episodic reinforcement learning in concave-convex and knapsack settingscited by 33
- 2023Model-based Constrained MDP for Budget Allocation in Sequential Incentive Marketingcited by 15
Built on by
Citing papers per year: 2026: 2.
2 papers.