mlsanityData to 14 Oct 2026

Policy Gradient Algorithms in Average-Reward Multichain MDPs

arXiv 2602.18003 ↗First posted 20 Feb 2026math.OC cs.CCcited by 3

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

Abstract (arXiv)

While there is an extensive body of research analyzing policy gradient methods for discounted cumulative-reward MDPs, prior work on policy gradient methods for average-reward MDPs has been limited, with most existing results restricted to ergodic or unichain settings. In this work, we first establish a policy gradient theorem for average-reward multichain MDPs based on the invariance of the classification of recurrent and transient states. Building on this foundation, we develop refined analyses and obtain a collection of convergence and sample-complexity results that advance the understanding of this setting. In particular, we show that the proposed α-clipped policy mirror ascent algorithm attains an ε-optimal policy with respect to positive policies.

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. Builds on 29 of its 54 references that are in the map. First posted on arXiv 20 Feb 2026.

Builds on

29 of 54 references.

Closest ancestors · 6

Same direction, newest first

  1. 2025Why Policy Gradient Algorithms Work for Undiscounted Total-Reward MDPs21 Oct
  2. 2025Regret Analysis of Average-Reward Unichain MDPs via an Actor-Critic Approach26 May
  3. 2025From Set Convergence to Pointwise Convergence: Finite-Time Guarantees for Average-Reward Q-Learning with Adaptive Stepsizes25 Apr
  4. 2024On Convergence of Average-Reward Q-Learning in Weakly Communicating Markov Decision Processes29 Aug
  5. 2024Order-Optimal Regret with Novel Policy Gradient Approaches in Infinite-Horizon Average Reward MDPs2 Apr
  6. 2024On the Global Convergence of Policy Gradient in Average Reward Markov Decision Processes11 Mar

Other references · 23

  1. 2017Proximal Policy Optimization Algorithmscited by 15,215
  2. 2015Trust Region Policy Optimizationcited by 2,580
  3. 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 264
  4. 2020Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularizationcited by 176
  5. 2019Global Optimality Guarantees For Policy Gradient Methodscited by 150
  6. 2022On the Convergence Rates of Policy Gradient Methodscited by 119
  7. 2019Adaptive Trust Region Policy Optimization: Global Convergence and Faster Rates for Regularized MDPscited by 118
  8. 2019Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processescited by 82
  9. 2013Projection onto the probability simplex: An efficient algorithm with a simple proof, and an applicationcited by 67
  10. 2019Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Functioncited by 44
  11. 2017Primal-Dual π Learning: Sample Complexity and Sublinear Run Time for Ergodic Markov Decision Problemscited by 33
  12. 2021Towards Tight Bounds on the Sample Complexity of Average-reward MDPscited by 33
11 more
  1. 2022Stochastic first-order methods for average-reward Markov decision processescited by 32
  2. 2021On-Policy Deep Reinforcement Learning for the Average-Reward Criterioncited by 30
  3. 2023Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processescited by 29
  4. 2023Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision Processescited by 26
  5. 2022Stochastic fixed-point iterations for nonexpansive maps: Convergence and error boundscited by 24
  6. 2020Average-reward model-free reinforcement learning: a systematic review and literature mappingcited by 22
  7. 2024Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPscited by 17
  8. 2024Achieving Tractable Minimax Optimal Regret in Average Reward MDPscited by 15
  9. 2025Near-Optimal Sample Complexity for MDPs via Anchoringcited by 14
  10. 2024Finding good policies in average-reward Markov Decision Processes without prior knowledgecited by 13
  11. 2025Optimal Non-Asymptotic Rates of Value Iteration for Average-Reward Markov Decision Processescited by 6

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 3.

3 papers.

  1. 2026Learning Policy from a Single Trajectory in Average-Reward Markov Decision Processcited by 3
  2. 2026Learning Weakly Communicating Average-Reward CMDPs: Strong Duality and Improved Regretcited by 2
  3. 2026Sharp Convergence and Sample Complexity of Policy Mirror Descent for Average-Reward MDPscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026Average-Reward Reinforcement Learning for Multichain MDPs: A Hierarchical Decomposition Approach
  2. 2024Provable Policy Gradient Methods for Average-Reward Markov Potential Games
  3. 2024Learning General Parameterized Policies for Infinite Horizon Average Reward Constrained MDPs via Primal-Dual Policy Gradient Algorithm
  4. 2024Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPs
  5. 2025Optimal Single-Policy Sample Complexity and Transient Coverage for Average-Reward Offline RL
  6. 2026Policy Gradient Methods for Non-Markovian Reinforcement Learning
  7. 2025Reinforcement Learning in POMDP's via Direct Gradient Ascent
  8. 2025An Online Multiobjective Policy Gradient for Long-run Average-reward Markov Decision Process