mlsanityData to 14 Oct 2026

Sharp Convergence and Sample Complexity of Policy Mirror Descent for Average-Reward MDPs

arXiv 2610.04117 ↗First posted 2 Oct 2026cs.LG math.OCcited by 0

Not on the map. Why?

Abstract (arXiv)

Policy mirror descent (PMD) has a mature finite-time theory in discounted Markov decision processes (MDPs), but less is known in the average-reward setting, a more natural objective for many control applications. We give a finite-time, finite-sample analysis of PMD in ergodic average-reward MDPs built around a single master recursion that governs convergence for any critic, without external regularization. Its specializations yield linear rates for exact, inexact-tabular, and linear function approximation (LFA) updates, with a superlinear regime for exact PMD. We complement these convergence results with end-to-end sample complexities of order tmix3/varepsilon2 in both tabular (|S||A|-dependent) and LFA (d-dependent) settings. Our LFA sample complexity sharpens the prior best tmix5 mixing dependence to tmix3, and matching information-theoretic lower bounds establish that the critic's tmix3/varepsilon2 sample complexity is unimprovable in both settings.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 23 of its 40 references that are in the map. First posted on arXiv 2 Oct 2026.

Builds on

23 of 40 references.

References · 23

  1. 2017Proximal Policy Optimization Algorithmscited by 15,215
  2. 2015Trust Region Policy Optimizationcited by 2,580
  3. 2020Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularizationcited by 176
  4. 2021Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classescited by 156
  5. 2022On the Convergence Rates of Policy Gradient Methodscited by 119
  6. 2019Adaptive Trust Region Policy Optimization: Global Convergence and Faster Rates for Regularized MDPscited by 118
  7. 2013Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)cited by 111
  8. 2021Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergencecited by 84
  9. 2022Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policiescited by 46
  10. 2022Stochastic first-order methods for average-reward Markov decision processescited by 32
  11. 2023A Novel Framework for Policy Mirror Descent with General Parameterization and Linear Convergencecited by 30
  12. 2023Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision Processescited by 26
11 more
  1. 2023Optimal Convergence Rate for Exact Policy Mirror Descent in Discounted Markov Decision Processescited by 18
  2. 2023Optimal Sample Complexity for Average Reward Markov Decision Processescited by 15
  3. 2024A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approachcited by 15
  4. 2024Order-Optimal Regret with Novel Policy Gradient Approaches in Infinite-Horizon Average Reward MDPscited by 14
  5. 2024On the Global Convergence of Policy Gradient in Average Reward Markov Decision Processescited by 9
  6. 2019Generalization in Transfer Learningcited by 8
  7. 2023Performance Bounds for Policy-Based Average Reward Reinforcement Learning Algorithmscited by 7
  8. 2024Performance of NPG in Countable State-Space Average-Cost RLcited by 5
  9. 2026Policy Gradient Algorithms in Average-Reward Multichain MDPscited by 3
  10. 2024Deep Index Policy for Multi-Resource Restless Matching Bandit and Its Application in Multi-Channel Schedulingcited by 2
  11. 2024Convergence of Natural Policy Gradient for a Family of Infinite-State Queueing MDPscited by 1

Built on by

Not cited yet.