mlsanityData to 14 Oct 2026

Near-Optimal Sample Complexity Bounds for Constrained Average-Reward MDPs

arXiv 2509.16586 ↗First posted 20 Sep 2025cs.LG stat.MLcited by 4

Not on the map. Why?

Abstract (arXiv)

Recent advances have significantly improved our understanding of the sample complexity of learning in average-reward Markov decision processes (AMDPs) under the generative model. However, much less is known about the constrained average-reward MDP (CAMDP), where policies must satisfy long-run average constraints. In this work, we address this gap by studying the sample complexity of learning an ε-optimal policy in CAMDPs under a generative model. We propose a model-based algorithm that operates under two settings: (i) relaxed feasibility, which allows small constraint violations, and (ii) strict feasibility, where the output policy satisfies the constraint. We show that our algorithm achieves sample complexities of tildeOleft(fracS A (B+H) ε2right) and tildeO left(fracS A (B+H)ε2 zeta2 right) under the relaxed and strict feasibility settings, respectively. Here, zeta is the Slater constant indicating the size of the feasible region, H is the span bound of the bias function, and B is the transient time bound. Moreover, a matching lower bound of tildeOmegaleft(fracS A (B+H) ε2zeta2right) for the strict feasibility case is established, thus providing the first minimax-optimal bounds for CAMDPs. Our results close the theoretical gap in understanding the complexity of constrained average-reward MDPs.

Key facts. Cited by 4 papers in the map (data through 14 Oct 2026). Builds on 21 of its 41 references that are in the map. First posted on arXiv 20 Sep 2025.

Builds on

21 of 41 references.

References · 21

  1. 2022Training language models to follow instructions with human feedbackcited by 15,971
  2. 2024DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Modelscited by 9,379
  3. 2018Sim-to-Real: Learning Agile Locomotion For Quadruped Robotscited by 319
  4. 2019Constrained Reinforcement Learning Has Zero Duality Gapcited by 151
  5. 2020Exploration-Exploitation in Constrained MDPscited by 149
  6. 2019TossingBot: Learning to Throw Arbitrary Objects with Residual Physicscited by 137
  7. 2020Provably Efficient Safe Exploration via Primal-Dual Policy Optimizationcited by 134
  8. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 127
  9. 2020Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Modelcited by 109
  10. 2021Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Primal-Dual Approachcited by 50
  11. 2020Constrained Upper Confidence Reinforcement Learningcited by 46
  12. 2020Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Losscited by 46
9 more
  1. 2022Near-Optimal Sample Complexity Bounds for Constrained MDPscited by 37
  2. 2020Constrained episodic reinforcement learning in concave-convex and knapsack settingscited by 34
  3. 2020A Sample-Efficient Algorithm for Episodic Finite-Horizon MDP with Constraintscited by 34
  4. 2021A Simple Reward-free Approach to Constrained Reinforcement Learningcited by 30
  5. 2022Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDPcited by 29
  6. 2021Provably Efficient Algorithms for Multi-Objective Competitive RLcited by 22
  7. 2021A Provably-Efficient Model-Free Algorithm for Constrained Markov Decision Processescited by 17
  8. 2024Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPscited by 17
  9. 2024Learning General Parameterized Policies for Infinite Horizon Average Reward Constrained MDPs via Primal-Dual Policy Gradient Algorithmcited by 9

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 1; 2026: 3.

4 papers.

  1. 2026Near-Optimal Primal-Dual Algorithm for Learning Linear Mixture CMDPs with Adversarial Rewardscited by 2
  2. 2026Learning Weakly Communicating Average-Reward CMDPs: Strong Duality and Improved Regretcited by 2
  3. 2025Near-Optimal Reinforcement Learning for Constrained Recurrence Objectivescited by 0
  4. 2026Instance-Dependent Regret for CMDPs with Step-Wise Constraintscited by 0