Research map / Reinforcement learning / MDPs and planning
Near-Optimal Sample Complexity for Online Constrained MDPs
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 model-based primal-dual algorithm with doubling batch updates for online tabular episodic CMDPs, achieving near-optimal sample complexity in relaxed and strict feasibility settings.
Problem
Sample-efficient, safe online reinforcement learning in tabular episodic constrained MDPs: prior CMDP methods either incur large safety violations or lack minimax-optimal sample complexity, and prior minimax results assume a generative model.
Approach
A model-based primal-dual method that mixes intermediate primal-dual iterates, uses a doubling-batch lazy update of the empirical transition model to decouple the value estimates from the model, and applies Bernstein-style optimistic reward and pessimistic cost bonuses with a discretized dual variable.
Key results
- Relaxed feasibility: an epsilon-optimal policy with epsilon violation after O~(SAH^3/eps^2) episodes, matching the unconstrained MDP lower bound.
- Strict feasibility: an epsilon-optimal zero-violation policy after O~(SAH^5/(eps^2 zeta^2)) episodes, matching the generative-model CMDP lower bound.
- Regret bound O~(sqrt(SAH^3K)) plus optimization error terms in the relaxed setting, with CV bounded by O~(sqrt(SAH^3K)) plus primal-dual error.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed model-based primal-dual algorithm for relaxed-feasibility online CMDPs | Online CMDPs · Relaxed feasibility | sample complexity (learning episodes): \tilde{O}\left(\frac{SAH^3}{\varepsilon^2}\right), matching the lower bound \Omega\left(\frac{SAH^3}{\varepsilon^2}\righ | Helped |
| Use the proposed model-based primal-dual algorithm for strict-feasibility online CMDPs | Online CMDPs · Strict feasibility | sample complexity (learning episodes): \tilde{O}\left(\frac{SAH^5}{\varepsilon^2\zeta^2}\right), matching the lower bound \Omega\left(\frac{SAH^5}{\varepsilon^ | Helped |
Limitations
- Tabular setting only; function approximation and multiple constraints are left to future work.
- Assumes known reward and cost functions and a known Slater constant zeta; the strict bound depends on zeta.
- No empirical experiments are reported; results are purely theoretical.
Experimental setup
Metrics: regret constraint violation sample complexity
Baselines: Efroni et al. 2020 primal-dual CMDP Liu et al. 2021 optimistic CMDP Wei et al. 2022 safe RL with known safe policy Zhang et al. 2024 generative-model CMDP
Builds on: Zhang et al. 2024 CMDP generative-model minimax analysis Zhang et al. 2020 / Azar et al. 2017 UCBVI-style bonuses Bernstein-style model-based RL (Zhang et al. 2021 near-optimal sample complexity Ding et al. 2021 primal-dual CMDP
Closest papers by meaning
- Achieving $\tilde{O}(1/\epsilon)$ Sample Complexity for Constrained Markov Decision Process (NeurIPS 2024 · similarity 0.91)
- Online Learning in Risk Sensitive constrained MDP (ICML 2025 · similarity 0.91)
- An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraints (ICML 2025 · similarity 0.91)
- Provably Efficient RL under Episode-Wise Safety in Constrained MDPs with Linear Function Approximation (NeurIPS 2025 · similarity 0.91)
- Online Learning in CMDPs: Handling Stochastic and Adversarial Constraints (ICML 2024 · similarity 0.91)
- Policy Optimization for CMDPs with Bandit Feedback: Learning Stochastic and Adversarial Constraints (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.