Policy mirror descent shows sharp convergence for average-reward tasks
Sharp Convergence and Sample Complexity of Policy Mirror Descent for Average-Reward MDPs
Machine Learning
Summary
Many real-world control problems look for steady long-term rewards, not just immediate gains. The authors studied a method called policy mirror descent that helps computers learn the best actions in these steady scenarios. They found exact conditions when this method quickly finds good strategies and proved how many samples it needs to do so reliably. Their work also matches the best possible limits, meaning the technique is as efficient as theoretically possible.
What this means in practice
- •For control engineers: Use improved sample complexity bounds to design algorithms for long-run average performance in automated systems.
- •For reinforcement learning practitioners: Implement policy mirror descent updates with guaranteed convergence and sample efficiency in average-reward learning tasks.
A theory result. No direct application yet.
Authors
Enes Arda, Atilla Eryilmaz
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_{\mathrm{mix}}^3/\varepsilon^2$ in both tabular ($|S||A|$-dependent) and LFA ($d$-dependent) settings. Our LFA sample complexity sharpens the prior best $t_{\mathrm{mix}}^5$ mixing dependence to $t_{\mathrm{mix}}^3$, and matching information-theoretic lower bounds establish that the critic's $t_{\mathrm{mix}}^3/\varepsilon^2$ sample complexity is unimprovable in both settings.