Safety
Sharp Convergence and Sample Complexity of Policy Mirror Descent for Average-Reward MDPs
arXiv:2610.04117v1 Announce Type: new 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 sett
arXiv:2610.04117v1 Announce Type: new 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 t_{mix}^3/arepsilon^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/arepsilon^2 sample complexity is unimprovable in both settings.
Related
- Fast Regularized Policy Mirror Descent with One-Step TD Updates
- Near-Optimal Sample Complexity Bounds for Constrained Average-Reward MDPs
- Achieving an O(1/N) Optimality Gap in Average-Reward Weakly-Coupled MDPs
- Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions
- Model-Free Robust Average-Reward Reinforcement Learning with Sample Complexity Analysis
Source: arXiv cs.LG | 2026-10-06