# Sample Complexity Bounds for Linear Constrained MDPs with a Generative Model

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

## Key facts

- Cited by 3 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.
- First posted on arXiv 2 Jul 2025.

## Placed in

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

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

- [Near-Optimal Primal-Dual Algorithm for Learning Linear Mixture CMDPs with Adversarial Rewards](https://mlsanity.com/paper/2603.27884/) (2026)
- [Augmented Lagrangian Method for Last-Iterate Convergence for Constrained MDPs](https://mlsanity.com/paper/2605.11694/) (2026)
- [Primal-Dual Policy Optimization for Linear CMDPs with Adversarial Losses](https://mlsanity.com/paper/2605.11535/) (2026)

## Abstract (arXiv)

We consider infinite-horizon γ-discounted (linear) constrained Markov decision processes (CMDPs) where the objective is to find a policy that maximizes the expected cumulative reward subject to expected cumulative constraints. Given access to a generative model, we propose to solve CMDPs with a primal-dual framework that can leverage any black-box unconstrained MDP solver. For linear CMDPs with feature dimension d, we instantiate the framework by using mirror descent value iteration (textttMDVI)~citepkitamura2023regularization an example MDP solver. We provide sample complexity bounds for the resulting CMDP algorithm in two cases: (i) relaxed feasibility, where small constraint violations are allowed, and (ii) strict feasibility, where the output policy is required to exactly satisfy the constraint. For (i), we prove that the algorithm can return an ε-optimal policy with high probability by using tildeOleft(fracd2(1-γ)4ε2right) samples. For (ii), we show that the algorithm requires tildeOleft(fracd2(1-γ)6ε2zeta2right) samples, where zeta is the problem-dependent Slater constant that characterizes the size of the feasible region. Furthermore, we prove a lower-bound of Omegaleft(fracd2(1-γ)5ε2zeta2right) for the strict feasibility setting. We note that our upper bounds under both settings exhibit a near-optimal dependence on d, ε, and zeta. Finally, we instantiate our framework for tabular CMDPs and show that it can be used to recover near-optimal sample complexities in this setting.