- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
this work establishes convergence rate for policy gradient and policy mirror descent for average reward MDPs.
Critical strengths
the paper cleverly adapts existing proof strategies to the context of average-reward policy optimization in finite MDPs satisfying the all-policy unichain condition, while allowing transient states.
Critical weaknesses
i am not sure about how much of a contribution this is, could you authors clarify if these results for average reward MDPs have already been established under perhaps slightly stronger assumptions?
Questions for authors
from my understanding, for discounted MDPs atleast, entropy regularisation of the objective is normally the route to exponential convergence. is this not the case? that is how do you arrive at exponential convergence from just the stepping scheme. also how novel are the Blackwell discounting ideas presented in the proofs?
3 comments
i thank the authors for their response. Could the authors clarify if this work could be directly extended to the continuous action space setting? If not, what is the bottleneck? Moreover, having read through Xiao et al (2022), it seems their linear convergence results for unregularized MDPs also require tabular MDPs, do their results extend to continuous action spaces too, or is entropy regularisation required to achieve the linear convergence in this setting?
Thank you
Second round to Reviewer rJmK
We thank the reviewer for the follow-up. Continuous-action MDPs are outside the scope of this paper; our claims concern finite-state, finite-action MDPs. Our contribution is global convergence for unregularized average-reward policy optimization under the all-policy unichain assumption, allowing transient states.
Could the authors clarify if this work could be directly extended to the continuous action space setting? If not, what is the bottleneck?
A direct extension requires new analysis, even in the discounted setting. For example, Xiao's KL-based bound contains the KL divergence from an optimal policy to the initial policy. With finitely many actions, this quantity is finite if initialization assigns positive probability to every action. With actions in , however, an optimal policy may always choose , whereas a uniform initial policy assigns zero probability to that exact point. The KL divergence from the optimal policy to the initial policy is then infinite, making the bound uninformative.
Our BPMA proof also uses a strictly positive minimum among nonzero discounted Bellman losses. With continuous actions, these losses can approach zero, so this proof step also needs new arguments.
do their results extend to continuous action spaces too, or is entropy regularisation required to achieve the linear convergence in this setting?
Entropy regularization is not required for Xiao's tabular result. Xiao [1] proves linear convergence for the unregularized discounted objective using geometrically increasing mirror-descent stepsizes. The KL term controls each policy update; the reward objective remains unregularized.
Entropy is not universally required for continuous actions either. Ju and Lan [2, Theorem 5] study exact policy mirror descent for continuous-action discounted MDPs. Their theorem includes linear convergence for an unregularized objective when cost action-value functions are convex in the action, subject to their other regularity assumptions. Extending our average-reward guarantees to continuous actions remains future work.
[1] Lin Xiao. On the Convergence Rates of Policy Gradient Methods. JMLR, 2022.
[2] Caleb Ju and Guanghui Lan. Policy Optimization over General State and Action Spaces. SIAM Journal on Optimization, 2026. arXiv:2211.16715.
Response to Reviewer rJmK
Thank you for the questions. Our central contribution is to obtain global optimality in unichain MDPs where direct average-reward gradient ascent can remain permanently stuck at a suboptimal policy. We clarify the difference from prior work below.
1. The assumptions in prior work exclude precisely the difficulty our paper resolves.
Kumar et al. (2025, Assumption 1) require the Markov chain induced by every stationary policy to be irreducible and aperiodic. In particular, no policy may make any state transient. This is substantially stronger than unichain, which allows transient states. Their global-convergence proof relies on this restriction.
Our paper shows why this distinction matters algorithmically. In the examples of Section 5 and Appendix D.2, a policy can stay in a moderately rewarding region while leaving a better route transient. The average-reward gradient is zero at these transient route states. Changing only their actions does not improve the current average reward, while changing the entry action alone initially reduces it.
The resulting policy is a suboptimal local maximum: starting there, every projected average-reward gradient step returns the same policy, regardless of the step size. Appendix D.2 proves this analytically. On the original reward scale, this policy earns less than 0.599, whereas another policy earns more than 0.634 in Experiment 1 and 0.638 in Experiment 2. Thus the failure is a persistent loss in reward, not merely a worse convergence constant. Figures 1–2 also show direct average-reward PG remaining suboptimal from uniform initialization.
DGPG overcomes this obstruction: discounted updates retain information about transient states and supply improving candidates, after which direct average-reward updates yield the anytime O(1/n) rate. Theorem 1 guarantees convergence to the unrestricted optimum from every initial policy under all-policy unichain. Extending Kumar et al.'s guarantee to this setting therefore requires a mechanism that overcomes the counterexample above.
Lee and Ryu (2026) do not supply the same guarantee with fixed clipping. Their clipped policy class can exclude every global maximizer. Our response to bKcZ gives a two-state unichain example where the unrestricted optimum is 1, but the best policy with clipping floor 0.01 earns only 1/10001, even after unlimited iterations. Their accuracy-dependent clipping result in Appendix E is acknowledged there. DGPG and BPMA converge to the unrestricted optimum without such a clipping floor.
2. Entropy regularization is not necessary for linear convergence.
Xiao (2022, Theorem 10) establishes linear convergence of policy mirror descent for the unregularized discounted objective, using geometrically increasing step sizes. BPMA uses this established result. The KL penalty in a mirror update controls the change from the current policy; it does not add an entropy bonus to the reward objective or change its optimum.
Our new result transfers that discounted rate to average reward. Theorem 2 gives a geometric upper bound on the difference between the globally optimal average reward and the reward of the current policy, from every full-support initialization under the additional rational-model condition.
3. The new Blackwell result controls approximately optimal policies.
Blackwell optimality and the explicit certificate of Grand-Clément and Petrik (2023) are established results. They identify discounts at which discounted-optimal policies are also average-reward optimal. However, an iterative algorithm generally produces approximately optimal policies, so identifying common optimizers alone does not establish a convergence rate.
Lemma 3 fills this gap: at one fixed Blackwell discount, average-reward suboptimality is at most a finite constant times discounted suboptimality. Thus a vanishing discounted error gives a vanishing upper bound on average-reward error, at the same geometric rate. The usual additive comparison leaves a nonzero residual at a fixed discount and cannot establish this conclusion. This quantitative result transfers Xiao's geometric rate to the unrestricted average-reward optimum. DGPG separately obtains global convergence without a Blackwell certificate or rationality assumption.