Research map / Reinforcement learning / MDPs and planning

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

NeurIPS 2026 · Reinforcement learning › MDPs and planning · approach: Offline RL sample complexity · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Analyzes policy mirror descent for ergodic average-reward MDPs via a master recursion, giving linear/superlinear convergence for exact, tabular-inexact and linear-function-approximation critics, with t_mix^3/eps^2 sample complexity and matching lower bounds.

Problem

Finite-time, finite-sample convergence and sample complexity of policy mirror descent for ergodic average-reward MDPs, where discounted-to-average reductions blow up and stationary distribution mismatch is hard to control.

Approach

A single one-step Lyapunov recursion for PMD under any critic yields linear rates with growing step sizes and an asymptotic rate governed by limsup of the stationary-distribution mismatch chi; combined with truncated centered-return critics (tabular and averaged-SGD LFA) it gives t_mix^3/eps^2 sample complexity, sharpening prior LFA t_mix^5.

Key results

• Tabular inexact PMD: linear rate (1-1/chi_bar)^t up to a 2(chi_bar+1) eps_Q floor; exact PMD superlinear-type rate limsup Delta_t^{1/t} <= 1-1/chi.
• Tabular sample complexity N = O~(chi_bar^3 |S||A| t_mix^3 / eps^2) with matching Le Cam lower bound Omega(t_mix^3/eps^2) per pair.
• LFA sample complexity O~(t_mix^3 d L^4 (C+ + C*) chi_bar^3 / (eps^2 mu^2)) on a single trajectory, improving prior t_mix^5 to t_mix^3 (in expectation).

Surprising findings

• Exact PMD can converge at a rate governed by the asymptotic mismatch chi rather than the worst-case bound, with chi=1 giving superlinear convergence when the optimal policy is unique.
• Naive truncated Q estimation can be worse with larger horizon H in average reward, because centering by an estimated average cost amplifies error by H.

Limitations

• LFA guarantees hold only in expectation, not high probability.
• Assumes ergodicity (every policy irreducible and aperiodic); unichain extension is only discussed in appendix.
• Sample complexity hides polylog factors and has extra chi_bar^3 and condition-number factors.

Experimental setup

Metrics: suboptimality gap sample complexity

Baselines: Li, Wu, Lan stochastic policy mirror descent Sun et al. robust PMD Lee and Ryu alpha-clipped PMD Murthy and Srikant Kumar et al. projected policy gradient

Builds on: policy mirror descent performance difference lemma averaged SGD natural policy gradient

Closest papers by meaning

• Policy Mirror Descent with Lookahead (NeurIPS 2024 · similarity 0.91)
• Convergence of Policy Mirror Descent Beyond Compatible Function Approximation (ICML 2025 · similarity 0.90)
• Policy Gradient Algorithms in Average-Reward Multichain MDPs (NeurIPS 2026 · similarity 0.90)
• Global Convergence for Average Reward Constrained MDPs with Primal-Dual Actor Critic Algorithm (NeurIPS 2025 · similarity 0.90)
• Learning General Parameterized Policies for Infinite Horizon Average Reward Constrained MDPs via Primal-Dual Policy Gradient Algorithm (NeurIPS 2024 · similarity 0.90)
• Mirror descent actor-critic methods for entropy regularised MDPs in general spaces: stability and convergence (NeurIPS 2026 · similarity 0.90)