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

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 under any gradient proxy, without external regularization. Its specializations yield linear rates (with a superlinear regime in the well-conditioned case) for exact, inexact-tabular, and linear function approximation (LFA) updates. We complement these convergence results with end-to-end sample complexities of order $t_{\mathrm{mix}}^3/\varepsilon^2$ in both tabular ($|\mathcal S||\mathcal A|$-dependent) and LFA ($d$-dependent) settings. The LFA rate sharpens the prior best $t_{\mathrm{mix}}^5$ mixing dependence to $t_{\mathrm{mix}}^3$, and matching information-theoretic lower bounds establish that the $t_{\mathrm{mix}}^3/\varepsilon^2$ critic core is unimprovable in both settings.