Research map / Bandits and online learning / RL theory and MDPs
Achieving $\tilde{O}(1/\epsilon)$ Sample Complexity for Constrained Markov Decision Process
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a primal LP-resolving algorithm for CMDPs with a generative model that identifies an optimal LP basis via elimination tests and then resolves the LP with adaptive remaining resources, achieving instance-dependent Õ(1/ε) sample complexity.
Problem
Sample complexity of learning near-optimal policies for tabular constrained MDPs with unknown rewards, costs and transitions under a generative model; prior worst-case bounds scale as O(1/ε²).
Approach
Characterizes instance hardness via LP basis (corner points of the occupancy-measure polytope) rather than policy gaps, identifies one optimal basis by lexicographic elimination tests on estimated LPs, and then resolves a linear system on that basis with adaptively updated remaining resource capacities (online LP style), yielding a primal-only algorithm.
Key results
- Algorithm achieves O(|S|^4|A|/((1-γ)^4 ξ Δ) · log²(1/ε)/ε) sample complexity for MDPs and a corresponding Õ(1/ε) bound for CMDPs, improving the O(1/ε²) worst-case dependence on ε.
- Numerical experiment on random 10-state, 10-action, 5-constraint CMDP shows the normalized error Err(N) decreases quickly with N.
- Sample complexity has worse dependence on |S| and (1-γ) than the best known O(|S||A|/((1-γ)^3 ε²)) bounds.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use the Adaptive-resolving Algorithm with optimal-basis identification | CMDP generative model · CMDP generative model | sample complexity: O(1/ε2) -> O( 1/(∆·ε) · log2(1/ε)) | Helped |
Surprising findings
- The O(1/ε) instance-dependent bound is consistent with the Ω(1/ε²) minimax lower bound because it depends on a problem-dependent gap Δ.
Limitations
- Results restricted to tabular settings
- Worse dependence on |S| and 1-γ than best minimax bounds
- Requires Slater condition assumption and instance-dependent gap that may be small
Experimental setup
Datasets: synthetic randomly generated CMDP instances
Benchmarks: synthetic random CMDP instance
Metrics: normalized L1 error of occupancy measure vs optimal (Err(N)) sample complexity scaling
Baselines: primal-dual CMDP methods worst-case O(1/ε²) CMDP sample complexity algorithms
Builds on: online linear programming Slater-condition LP estimation (Li and Ye style analysis) occupancy measure LP formulation (Altman CMDP)
Closest papers by meaning
- Sample-Efficient Constrained Reinforcement Learning with General Parameterization (NeurIPS 2024 · similarity 0.91)
- Near-Optimal Sample Complexity for Online Constrained MDPs (NeurIPS 2025 · similarity 0.91)
- Efficient Exploration in Average-Reward Constrained Reinforcement Learning: Achieving Near-Optimal Regret With Posterior Sampling (ICML 2024 · similarity 0.91)
- Truly No-Regret Learning in Constrained MDPs (ICML 2024 · similarity 0.91)
- Optimal Sample Complexity for Average Reward Markov Decision Processes (ICLR 2024 · similarity 0.90)
- Near-Optimal Sample Complexity for MDPs via Anchoring (ICML 2025 · similarity 0.90)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.