mlsanityData to 14 Oct 2026

Global Convergence for Average Reward Constrained MDPs with Primal-Dual Actor Critic Algorithm

arXiv 2505.15138 ↗First posted 21 May 2025cs.LG cs.AIcited by 8

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

This paper investigates infinite-horizon average reward Constrained Markov Decision Processes (CMDPs) with general parametrization. We propose a Primal-Dual Natural Actor-Critic algorithm that adeptly manages constraints while ensuring a high convergence rate. In particular, our algorithm achieves global convergence and constraint violation rates of tildeO(1/√T) over a horizon of length T when the mixing time, τmix, is known to the learner. In absence of knowledge of τmix, the achievable rates change to tildeO(1/T0.5-ε) provided that T ≥ tildeOleft(τmix2/εright). Our results match the theoretical lower bound for Markov Decision Processes and establish a new benchmark in the theoretical exploration of average reward CMDPs.

Key facts. Cited by 8 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 32 of its 48 references that are in the map. First posted on arXiv 21 May 2025.

Builds on

32 of 48 references.

Closest ancestors · 5

Same direction, newest first

  1. 2024A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach26 Jul
  2. 2024Sample-Efficient Constrained Reinforcement Learning with General Parameterization17 May
  3. 2024Order-Optimal Regret with Novel Policy Gradient Approaches in Infinite-Horizon Average Reward MDPs2 Apr
  4. 2024Towards Global Optimality for Practical Average Reward Reinforcement Learning without Mixing Time Oracles18 Mar
  5. 2024Learning General Parameterized Policies for Infinite Horizon Average Reward Constrained MDPs via Primal-Dual Policy Gradient Algorithm3 Feb

Other references · 27

  1. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 229
  2. 2019Neural Policy Gradient Methods: Global Optimality and Rates of Convergencecited by 159
  3. 2020Exploration-Exploitation in Constrained MDPscited by 149
  4. 2020CRPO: A New Approach for Safe Reinforcement Learning with Convergence Guaranteecited by 134
  5. 2018Stochastic Variance-Reduced Policy Gradientcited by 106
  6. 2019Finite-Sample Analysis for SARSA with Linear Function Approximationcited by 85
  7. 2019Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processescited by 82
  8. 2021On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Methodcited by 70
  9. 2022An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methodscited by 68
  10. 2019Sample Efficient Policy Gradient Methods with Recursive Variance Reductioncited by 60
  11. 2019An Improved Convergence Analysis of Stochastic Variance-Reduced Policy Gradientcited by 59
  12. 2023Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policiescited by 58
15 more
  1. 2019DeepPool: Distributed Model-free Algorithm for Ride-sharing using Deep Reinforcement Learningcited by 54
  2. 2021Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Primal-Dual Approachcited by 50
  3. 2020Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Losscited by 46
  4. 2022Learning Infinite-Horizon Average-Reward Markov Decision Processes with Constraintscited by 29
  5. 2022Convergence and sample complexity of natural policy gradient primal-dual methods for constrained MDPscited by 27
  6. 2023Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision Processescited by 26
  7. 2020Deep Reinforcement Learning Based Intelligent Reflecting Surface for Secure Wireless Communicationscited by 22
  8. 2022Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Conservative Natural Policy Gradient Primal-Dual Algorithmcited by 20
  9. 2021Concave Utility Reinforcement Learning with Zero-Constraint Violationscited by 19
  10. 2023Beyond Exponentially Fast Mixing in Average-Reward Reinforcement Learning via Multi-Level Monte Carlo Actor-Criticcited by 18
  11. 2020A Distributed Model-Free Ride-Sharing Approach for Joint Matching, Pricing, and Dispatching using Deep Reinforcement Learningcited by 17
  12. 2022Option-Aware Adversarial Inverse Reinforcement Learning for Robotic Controlcited by 16
  13. 2023First Order Methods with Markovian Noise: from Acceleration to Variational Inequalitiescited by 14
  14. 2023A Best-of-Both-Worlds Algorithm for Constrained MDPs with Long-Term Constraintscited by 9
  15. 2023Cooperating Graph Neural Networks with Deep Reinforcement Learning for Vaccine Prioritizationcited by 9

Built on by

Cited by year (2026 to 14 Oct)

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

8 papers.

  1. 2025Regret Analysis of Average-Reward Unichain MDPs via an Actor-Critic Approachcited by 7
  2. 2025Efficient Q-Learning and Actor-Critic Methods for Robust Average-Reward Reinforcement Learningcited by 4
  3. 2026Regret Analysis of Unichain Average Reward Constrained MDPs with General Parameterizationcited by 4
  4. 2026Learning Weakly Communicating Average-Reward CMDPs: Strong Duality and Improved Regretcited by 2
  5. 2025Primal-Only Actor Critic Algorithm for Robust Constrained Average Cost MDPscited by 1
  6. 2026Global Convergence of Average Reward Constrained MDPs with Neural Critic and General Policy Parameterizationcited by 1
  7. 2026Bias-Controlled Primal-Dual Natural Actor-Critic: Optimal Rates for Constrained Multi-Objective Average-Reward RLcited by 0
  8. 2026Learning Infinite-Horizon Average-Reward CMDPs via State Augmentationcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024On the Global Convergence of Policy Gradient in Average Reward Markov Decision Processes
  2. 2024On the Convergence of Single-Timescale Actor-Critic
  3. 2024A Policy Gradient Primal-Dual Algorithm for Constrained MDPs with Uniform PAC Guarantees
  4. 2024Deterministic Policy Gradient Primal-Dual Methods for Continuous-Space Constrained MDPs
  5. 2024Last-Iterate Convergence of General Parameterized Policies in Constrained MDPs
  6. 2026Augmented Lagrangian Method for Last-Iterate Convergence for Constrained MDPs
  7. 2024Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPs
  8. 2025Sample Complexity Bounds for Linear Constrained MDPs with a Generative Model