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.
Figures & tables
Work
Update
Convergence
Sample complexity
Guarantee
Exact critic
Murthy and Srikant [23]
PMD (KL)
O(1/T)
—
—
Kumar et al. [16]
Projected PG
O(1/T)
—
—
Sun et al. [34]
PMD (Euclidean)
O((1−1/M0)T)
—
—
Ours
PMD (Bregman)
O((1−1/χˉ)T) ; limsuptΔt1/t≤1−1/χ
—
—
Tabular critic, generative model oracle
Table 1: Comparison with prior work on policy optimization for average-reward MDPs. Rates concern the unregularized objective, up to critic-error floors. Sample complexities keep each method’s rate constant ( χˉ , Cα ) and omit other instance-dependent factors (App. A ). Guarantees are with high probability (w.h.p.) or in expectation (in exp.), for the last or a uniformly random (rand.) iterate.
Figure 1: Median χt/χˉ trajectories. IQR shaded.
Appendix figures & tables4 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 2: Exact KL-PMD on the multiple-minimizer instance. (a) Suboptimality Δt with the non-asymptotic upper bound (1−1/χˉ)tΨ0 (Lemma 3.7 (i)) and asymptotic-rate reference (1−1/χ)tΨ0 (Lemma 3.7 (ii)) overlaid. (b) Mismatch χt with horizontal references at χˉ≈153.7 and the tail estimate χ≈12.5 . The observed contraction is strictly tighter than both theoretical rates.
Figure 3: Exact KL-PMD on the unique-minimizer instance ( ε=10−3 ). Same diagnostics as Figure 2 . Here χt→1 (tail χ≈1 ) so the asymptotic reference collapses to zero and is omitted from panel (a); the observed trajectory exhibits the two-phase convergence predicted by Corollary 4.3 , passing through an intermediate plateau at the tie-breaker scale before collapsing below 10−12 .
Figure 4: Inexact KL-PMD under uniform critic noise, on the unique-minimizer instance with tie-breaker ε=10−4 ; each curve is the mean of N=100 seeds. (a) Step-size independence. At fixed εQ=10−2 , three geometric schedules ( b=1.05 , η0∈{10−2,10−1,1} ) converge at very different rates but to essentially the same tail floor. (b) Floor depends on critic error. At fixed η0=10−1 , sweeping εQ∈{10−3,10−2,10−1} gives monotonically ordered tail floors.
Figure 5: Per-MDP diagnostics for the rate-gap experiment (Section F.4 ): panel (a) median Δt with the non-asymptotic rate reference (1−1/χˉ)tΨ0 (Lemma 3.7 (i)) and the asymptotic-rate reference (1−1/χ)tΨ0 (Lemma 3.7 (ii)), both at ensemble-median values, where Ψ0:=Δ0+D0⋆/(η−1χˉ) . The asymptotic reference is a limit statement plotted from t=0 , not a finite-time bound. Panel (b) median χt with horizontal references at χˉ and tail χ . IQR shaded.