# Primal-Dual Sample Complexity Bounds for Constrained Markov Decision Processes with Multiple Constraints

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 10 of its 17 references that are in the map.
- First posted on arXiv 9 Mar 2025.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 10 of 10)

- [Reward Constrained Policy Optimization](https://mlsanity.com/paper/1805.11074/) (2018)
- [Constrained Reinforcement Learning Has Zero Duality Gap](https://mlsanity.com/paper/1910.13393/) (2019)
- [Exploration-Exploitation in Constrained MDPs](https://mlsanity.com/paper/2003.02189/) (2020)
- [Provably Efficient Safe Exploration via Primal-Dual Policy Optimization](https://mlsanity.com/paper/2003.00534/) (2020)
- [CRPO: A New Approach for Safe Reinforcement Learning with Convergence Guarantee](https://mlsanity.com/paper/2011.05869/) (2020)
- [Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2005.12900/) (2020)
- [Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Primal-Dual Approach](https://mlsanity.com/paper/2109.06332/) (2021)
- [Near-Optimal Sample Complexity Bounds for Constrained MDPs](https://mlsanity.com/paper/2206.06270/) (2022)
- [Constrained episodic reinforcement learning in concave-convex and knapsack settings](https://mlsanity.com/paper/2006.05051/) (2020)
- [Model-based Constrained MDP for Budget Allocation in Sequential Incentive Marketing](https://mlsanity.com/paper/2303.01049/) (2023)

## Built on by (most cited first, 2 of 2)

- [Global Optimality for Constrained Exploration via Penalty Regularization](https://mlsanity.com/paper/2604.28144/) (2026)
- [Learning Chance-Constrained MDPs with Bellman Distributional Certificates](https://mlsanity.com/paper/2609.30856/) (2026)

## 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.