Sharp Convergence and Sample Complexity of Policy Mirror Descent for Average-Reward MDPs
Abstract
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/ε2 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/ε2 sample complexity is unimprovable in both settings.
Related
- Tight Sample Complexity Bounds for Entropic Best Policy Identification
- Randomized average block coordinate descent method with heavy-ball momentum for tensor least squares problem under the t-product
- Non-asymptotic Convergence of Average-reward Q-learning with Options
- Does Policy Mirror Descent Converge in Policy with Non-Decomposable Mirror Maps? A Counterexample
- PL conditions do not guarantee convergence of gradient descent-ascent dynamics
BibTeX
@misc{arda2026sharp,
title = {{Sharp Convergence and Sample Complexity of Policy Mirror Descent for Average-Reward MDPs}},
author = {Enes Arda and Atilla Eryilmaz},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.04117},
eprint = {2610.04117},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.04117},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Sharp Convergence and Sample Complexity of Policy Mirror Descent for Average-Reward MDPs
AU - Enes Arda
AU - Atilla Eryilmaz
PY - 2026
DA - 2026/10/02
PB - arXiv
DO - 10.48550/arxiv.2610.04117
UR - https://arxiv.org/abs/2610.04117
AB - 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 t_mix^3/ε^2 in both tabular (|S||A|-dependent) and LFA (d-dependent) settings. Our LFA sample complexity sharpens the prior best t_mix^5 mixing dependence to t_mix^3, and matching information-theoretic lower bounds establish that the critic's t_mix^3/ε^2 sample complexity is unimprovable in both settings.
ER -