acceptodds
Under review as a conference paper at ICLR 2027

Average-Reward Policy Optimization via Discounting: Anytime and Global Linear Convergence

Abstract

We study average-reward policy optimization via discounting in finite Markov decision processes where every stationary policy induces one recurrent class, possibly with transient states. With a known model and exact policy evaluation, Discount-Guided Policy Gradient achieves an anytime optimality gap after policy updates, with nondecreasing average rewards, from any initialization and for any fixed positive discounted step size. The proof combines local gradient domination with an explicit bound on entry into a near-optimal region. For rational model data, Blackwell Policy Mirror Ascent achieves global R-linear convergence of the average-reward gap from every full-support initialization through a multiplicative error bound at an explicit Blackwell discount. Neither guarantee requires a finite global stationary-distribution mismatch coefficient.

Primary area:
reinforcement learning
Keywords:
Average-reward reinforcement learning, policy gradient, policy mirror ascent, global convergence, Blackwell optimality, unichain, discount-guided policy gradient

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_rJmKOpenReview ↗
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
AuthorsOpenReview ↗

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.

“could you authors clarify if these results for average reward MDPs have already been established under perhaps slightly stronger assumptions?”

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.5990.599, whereas another policy earns more than 0.6340.634 in Experiment 1 and 0.6380.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)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 11, but the best policy with clipping floor 0.010.01 earns only 1/100011/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.

“from my understanding, for discounted MDPs atleast, entropy regularisation of the objective is normally the route to exponential convergence. is this not the case?”

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.

“also how novel are the Blackwell discounting ideas presented in the proofs?”

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.

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

AuthorsOpenReview ↗

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 [0,1][0,1], however, an optimal policy may always choose 1/21/2, 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.

Reviewer_p1hTOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies average-reward policy optimization in finite MDPs under the all-policy unichain assumption, allowing transient states. The authors propose two algorithms that leverage discounted policy optimization to achieve global convergence guarantees without requiring a finite stationary-distribution mismatch coefficient. The first algorithm Discount-Guided Policy Gradient (DGPG) combines discounted policy gradient updates with monotone average-reward improvements and establishes an anytime (O(1/n)) convergence rate from arbitrary initialization. The second algorithm, Blackwell Policy Mirror Ascent (BPMA), uses a fixed Blackwell discount factor and a multiplicative discounted-to-average optimality-gap bound to establish global linear convergence. Numerical experiments on two synthetic MDPs demonstrate the advantages of the proposed approaches over direct average-reward policy gradient methods.

Critical strengths
  1. The paper is well written and logically organized. The intuition behind both algorithms is clearly explained, and each step of the theoretical development is well motivated.
  2. This work shows a meaningful extension of existing theory. The results extend global convergence guarantees for average-reward policy optimization to all-policy unichain MDPs with transient states, without requiring a finite global stationary-distribution mismatch coefficient.
  3. They proposed a reasonable algorithmic design. DGPG provides an intuitive approach that uses discounted optimization to escape suboptimal regions and direct average-reward updates to achieve faster convergence near the optimal policy set.
  4. The paper establishes explicit convergence guarantees under the gradient oracle setting
Critical weaknesses
  1. I am not very sure about the novelty relative to prior work. In particular, BPMA appears to largely combine an existing Blackwell discount bound with an established discounted policy mirror-ascent algorithm, although the multiplicative error bound provides an additional theoretical result. It would be better if the paper could better distinguish its contributions from existing discounted-to-average reductions and policy optimization results.
  2. The algorithm seems to be hard to apply to sample-based learning. (i) the discounted-candidate acceptance condition (Algorithm 1, Line 6) and (ii) the backtracking condition (Eq. 9) require accurate average-reward comparisons under noisy estimates, while (iii) discounted gradient estimation becomes difficult as (γm→1\gamma_m \to 1) (Eq. 11). Since the convergence proof relies on monotone improvement, it is unclear whether similar guarantees can be obtained in practical sample-based settings.
  3. Although DGPG achieves an (O(1/n)) rate, the dependence of key constants (e.g., H,εloc,LavH, \varepsilon_{\mathrm{loc}}, L_{\mathrm{av}}) on the MDP size and structure is unclear. The iteration complexity also excludes additional objective evaluations for backtracking and candidate acceptance. For BPMA, the explicit Blackwell discount may be very close to 1.
Questions for authors
  1. Can DGPG be potentially extended to noisy, sample-based estimates while retaining meaningful convergence guarantees?
  2. Can the authors characterize how the key constants scale with the MDP size and structure?
1 comment
AuthorsOpenReview ↗

Response to Reviewer p1hT

Our main achievement is global convergence in unichain MDPs where direct average-reward gradient ascent can remain permanently suboptimal.

1. Lemma 3 enables the global linear guarantee.

“BPMA appears to largely combine an existing Blackwell discount bound with an established discounted policy mirror-ascent algorithm”

BPMA builds on the Blackwell certificate of Grand-Clément and Petrik (2023) and discounted mirror ascent of Xiao (2022). Lemma 3 supplies the new step: at one fixed Blackwell discount, average-reward error is bounded by a finite constant times discounted error. Classical Blackwell optimality identifies common optimizers; it does not quantify the error of approximately optimal policies. The additive comparison leaves a nonzero residual at a fixed discount. Lemma 3 removes that residual and transfers Xiao's geometric bound to the unrestricted average-reward optimum.

The unichain extension also overcomes an optimization obstruction. Kumar et al. (2025, Assumption 1) require every policy to induce an irreducible, aperiodic chain, excluding transient states. Appendix D.2 constructs a unichain MDP with a suboptimal local maximum at which every projected average-reward gradient step stays fixed, regardless of the step size. That policy earns less than 0.5990.599, while another earns more than 0.6340.634 in Experiment 1 and 0.6380.638 in Experiment 2. Figures 1–2 also show direct average-reward PG remaining suboptimal from uniform initialization.

Lee and Ryu's fixed clipping can exclude every global maximizer. Our response to bKcZ gives a two-state unichain example with optimum 11, but best reward only 1/100011/10001 when the clipping floor is 0.010.01. Their accuracy-dependent clipping results are acknowledged there.

DGPG escapes suboptimal regions through discounted candidates that guarantee entry into a region of local gradient domination; monotone average-reward updates then preserve that region. The resulting anytime O(1/n)O(1/n) rate holds from every initial policy, without clipping or a prescribed accuracy.

2. A sampled extension is substantive future work.

“Can DGPG be potentially extended to noisy, sample-based estimates while retaining meaningful convergence guarantees?”

Our theorem resolves the optimization problem under exact evaluation; a full finite-sample analysis is future work. Prior sampled results have different requirements: Ganesh and Aggarwal (2025) assume uniform Fisher nondegeneracy and retain approximation-error terms; Lee and Ryu (2026, Appendix E.4) use accuracy-dependent clipping. They do not establish a sampled counterpart to DGPG's unrestricted anytime guarantee.

Suppose both reward estimates have error at most ξ\xi. Accept qq if J^(q)−J^(π)≥2ξ.\widehat J(q)-\widehat J(\pi)\ge2\xi. Otherwise retain π\pi. Acceptance preserves true monotonicity; rejection implies Jav(q)−Jav(π)<4ξJ_{\mathrm{av}}(q)-J_{\mathrm{av}}(\pi)<4\xi. Thus the retained policy loses at most 4ξ4\xi relative to the candidate. A full theorem must additionally control gradient errors, adapt backtracking to uncertainty, and quantify estimation cost as the discount approaches one.

3. Constants, evaluation overhead, and the certified discount.

“Can the authors characterize how the key constants scale with the MDP size and structure?”

“The iteration complexity also excludes additional objective evaluations for backtracking and candidate acceptance.”

Eqs. (12), (17), and (18) give

\qquad C_{\mathrm{av}}=O(S(1+L_{\mathrm{av}})^2).$$ Here $H$ is controlled by the uniform span of Poisson bias functions, and $L_{\mathrm{av}}$ by conditioning of the stationary-distribution linear system. The constant $\varepsilon_{\mathrm{loc}}$ measures objective separation outside a neighborhood of the optimal set where local gradient domination holds. These are finite, instance-dependent quantities; we do not claim dimension-only polynomial bounds. **DGPG needs none of them as inputs.** **Evaluation overhead.** Section 3.1 explicitly counts policy updates. Appendix B.1 shows that every trial step at most $1/L_{\mathrm{av}}$ passes backtracking. Starting at $1$ and halving therefore needs at most $$1+\lceil\log_2\max\lbrace 1,L_{\mathrm{av}}\rbrace\rceil$$ trial evaluations per average-reward update. Candidate comparisons occur once per epoch, hence $O(\log n)$ times through $n$ updates. **For a fixed MDP, counting these evaluations preserves the inverse-linear order**, with an additional instance-dependent factor. A runtime bound would additionally account for each policy-evaluation solve. **Certified discount.** BPMA's certified discount can be close to one. Our numerical results suggest the certificate is conservative; sharpening it is future work. The global linear rate does not claim a favorable uniform runtime bound.
Reviewer_bKcZOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes two algorithms, Discount-Guided Policy Gradient (DGPG) and Blackwell Policy Mirror Ascent (BPMA), to address existing limitations in average-reward policy optimization. The key insight is to exploit the relationship between discounted-reward and average-reward optimality gaps to establish global convergence guarantees.

Critical strengths

The theoretical analysis appears technically sound, and the proposed algorithmic constructions are interesting. In particular, leveraging discounted policy optimization to overcome the difficulties associated with transient states in average-reward MDPs is a promising approach.

Critical weaknesses

Restrictive assumptions for BPMA. The global linear convergence guarantee for BPMA relies on the additional assumption that both the transition probabilities (P) and rewards (r) are rational. This limits the generality of the result, and it is unclear whether the guarantee can be extended to arbitrary real-valued model parameters. Moreover, the explicitly chosen discount factor can be extremely close to one, potentially limiting the practical significance of the convergence guarantee.

Insufficient differentiation from closely related work. Although the paper discusses Lee and Ryu (2026), the distinction between their results and the present work could be developed further. A more detailed comparison of the assumptions, algorithmic approaches, and convergence guarantees would help clarify the novelty and significance of the proposed methods.

Questions for authors

Could the authors provide a more detailed comparison with the following closely related work?

Lee, Jongmin, and Ernest K. Ryu. Policy Gradient Algorithms in Average-Reward Multichain MDPs. arXiv preprint arXiv:2602.18003 (2026).

3 comments
AuthorsOpenReview ↗

Response to Reviewer bKcZ

Thank you for recognizing the technical soundness of our results. We would like to clarify two central points.

1. Global optimality is the main achievement; BPMA adds a linear rate under a further condition.

“The global linear convergence guarantee for BPMA relies on the additional assumption that both the transition probabilities (P) and rewards (r) are rational.”

“Moreover, the explicitly chosen discount factor can be extremely close to one, potentially limiting the practical significance of the convergence guarantee.”

To our knowledge, this is the first analysis establishing these anytime inverse-linear and global linear guarantees for tabular policy-gradient-type methods under all-policy unichain, allowing transient states and without assuming a finite global stationary-distribution mismatch coefficient.

DGPG achieves an anytime O(1/n)O(1/n) gap from every initial policy, for any fixed positive discounted step size. It requires neither rational model data nor a Blackwell threshold. BPMA further establishes global R-linear convergence from every full-support initialization under an additional rational-model condition. Both target the optimum over the full policy space, without a clipping floor or a prescribed accuracy.

This setting presents a substantive obstruction: Appendix D.2 exhibits suboptimal local maxima with zero first-order stationarity gap. Existing global gradient-domination arguments therefore cannot simply be extended by adjusting constants.

For BPMA, rationality supplies the explicit Blackwell-discount certificate. Given any fixed discount above the Blackwell threshold, the multiplicative error bound and rate-transfer proof also apply to real-valued models. The extra condition enables an explicit discount supporting the stronger geometric guarantee; it is not required for DGPG's global optimality result.

We acknowledge that the certified discount can be close to one. However, our numerical results suggest that the certificate is overly conservative: the estimated Blackwell thresholds in our two experiments are approximately 0.80930.8093 and 0.26000.2600, far below the certified discounts. These are numerical estimates, not replacement certificates. Moreover, BPMA reaches a gap below 10−310^{-3} within 22,717 updates in Experiment 1 despite the conservative worst-case bound. Having established, to our knowledge, the first global linear guarantee for tabular policy-gradient-type methods in this unichain setting without a finite global mismatch assumption, we regard sharper discount certificates and convergence bounds as important future work.

2. Fixed clipping in Lee and Ryu can leave a gap arbitrarily close to one.

“Although the paper discusses Lee and Ryu (2026), the distinction between their results and the present work could be developed further.”

Their Theorems 9–10 establish convergence of reward to the optimum over Πα={π:π(a∣s)≥α}\Pi_\alpha=\lbrace \pi:\pi(a\mid s)\ge\alpha\rbrace for fixed α>0\alpha>0. This restricted optimum can be almost maximally suboptimal even in a two-state unichain MDP with rewards in [0,1][0,1].

Consider states gg and bb, each with two actions. At gg, both actions give reward 11: action Stay returns to gg, while action Leave moves to bb. At bb, both actions give reward 00 and have identical transitions: return to gg with probability δ∈(0,1)\delta\in(0,1) and remain at bb otherwise.

Writing q=π(Leave∣g)q=\pi(\mathrm{Leave}\mid g), the induced transition matrix and stationary distribution are

\qquad d_\pi=\left(\frac{\delta}{\delta+q},\frac{q}{\delta+q}\right).$$ Every stationary policy is unichain: for $q=0$, $g$ is the unique recurrent state and $b$ is transient; for $q>0$, the chain is irreducible. Its average reward is $$J_{\mathrm{av}}(\pi)=\frac{\delta}{\delta+q}.$$ The unrestricted optimum is $J^\star=1$, attained by $q=0$. But clipping forces $q\ge\alpha$, so, for $0<\alpha<1/2$, $$J_\alpha^\star=\frac{\delta}{\delta+\alpha}, \qquad J^\star-J_\alpha^\star=\frac{\alpha}{\delta+\alpha}.$$ For any fixed positive $\alpha$, choosing $\delta\ll\alpha$ makes the clipped optimum arbitrarily close to zero and its gap arbitrarily close to one. For example, $\alpha=0.01$ and $\delta=10^{-6}$ give $J_\alpha^\star=1/10001$, versus $J^\star=1$. **No number of iterations can overcome this restriction.** The mechanism is simple: clipping forces repeated departures from the rewarding state, followed by long stays in the zero-reward state. Their Appendix E does obtain unrestricted $\varepsilon$-optimality by selecting $\alpha$ according to the target accuracy and instance. Our example does not contradict that result. It establishes that a fixed clipped run need not converge to the unrestricted optimum, whereas DGPG and BPMA do, without retuning a clipping floor as accuracy increases.

Thank you for your detailed response, the illustrative two-state example, and the helpful summary.

Comparison with Lee & Ryu (2026): I appreciate the clarification on avoiding a fixed clipping floor and achieving anytime convergence. That said, since Lee & Ryu (2026) cover more general multichain/weakly communicating MDPs as well as sample-based settings, the scope of the exact-model unichain setting here still feels somewhat limited.

BPMA limitations: I also appreciate the authors' candidness regarding the rational-model assumption and the conservative Blackwell discount factor; however, these factors still somewhat limit the practical significance of the linear convergence guarantee.

Overall, I will respectfully maintain my current rating.

AuthorsOpenReview ↗

While multichain is more general, the global is not attained by Lee and Ryu.

Thank you for the follow-up. We agree that Lee and Ryu cover broader MDP classes and provide sample-based guarantees. The distinction is what a single run can achieve. Even in a one-state ergodic MDP, a fixed clipping floor can put the global optimum out of reach. Let the two actions yield rewards 11 and 00. With a fixed floor 0<α≤1/20<\alpha\leq 1/2, every iterate assigns probability at least α\alpha to the zero-reward action. The best clipped policy therefore earns exactly 1−α1-\alpha, while the unrestricted optimum is 11. Lee and Ryu obtain ε\varepsilon-optimality by choosing α\alpha for a prescribed accuracy (Appendix E, Corollaries 28–29).

To our knowledge, Theorem 1 gives the first guarantee that a single run of a tabular policy gradient method converges to the unrestricted optimal average reward under the all-policy unichain assumption. DGPG achieves an anytime O(1/n)O(1/n) gap from every initial policy. Appendix D.2 shows why every matters: there is a suboptimal policy from which every direct projected average-reward gradient step returns exactly the same policy, regardless of step size. DGPG converges to the optimal average reward from that very initialization.

For BPMA, we agree that the certified discount can be conservative. Theorem 2 establishes global linear convergence to the unrestricted optimum for rational models from any full-support initialization. Our experiments suggest room to sharpen the certificate. The certificate is needed for BPMA’s explicit rate guarantee. DGPG’s global optimality guarantee requires neither rational model data nor a Blackwell certificate.

Comments on the paper

2 comments

Dear Reviewers, Thank you for your time and valuable feedback. As the discussion deadline is about to end soon, please let us know if you still have any questions or concerns. We will be pleased to clarify.

Authors

AuthorsOpenReview ↗

Summary of Discussion for the Reviewers and Area Chair

Dear Area Chair and Reviewers,

Thank you for your careful reading and for the questions raised during the discussion. We would like to clarify what our paper establishes under the unichain assumption, how it differs from prior work, and what makes the linear rate possible.

To our knowledge, this paper is the first to establish global optimality for tabular average-reward policy gradient methods under the all-policy unichain assumption. This assumption allows transient states even though each stationary policy has a single recurrent class. Both algorithms converge to the optimum over all stationary policies in a single run. DGPG guarantees an O(1/n)O(1/n) gap after nn updates from any initial policy (Theorem 1). Under the additional assumption of rational rewards and transition probabilities, BPMA achieves a geometric rate from any initial policy that assigns positive probability to every action at every state (Theorem 2).

  1. Why transient states matter. Reviewer rJmK asked whether prior guarantees hold under "slightly stronger assumptions". Kumar et al. (2025, Assumption 1) require every policy to induce an irreducible, aperiodic chain. Appendix D.2 shows what can happen once transient states are allowed. The current policy never takes a route that could yield a higher reward. Changing actions along that route alone leaves the average reward unchanged, and entering the route before changing those actions makes the reward worse. Every projected average-reward gradient step from this suboptimal policy returns exactly the same policy, regardless of step size. DGPG uses discounted updates to generate candidate policies and compares them by their average reward. These candidates guarantee entry into a region where the average-reward gradient controls the optimality gap, and monotone updates keep the policy there.

  2. How much fixed clipping can cost. In our two-state example for bKcZ, staying in the rewarding state earns the unrestricted optimum of 11. A clipping floor of 0.010.01 forces the policy to leave that state repeatedly. With a return probability of 10−610^{-6} per step, even the best clipped policy earns only 1/100011/10001, however long the algorithm runs. Lee and Ryu (Appendix E) obtain ε\varepsilon-optimality by choosing the floor for the target accuracy and instance. Both of our guarantees hold along a single run over the unrestricted policy class.

  3. What proves the linear rate. Classical Blackwell optimality tells us that an exact optimizer at a sufficiently high discount is average-reward optimal. To prove a rate for BPMA, we must control the policies it produces at finite iterations. Lemma 3 bounds the average-reward gap of every policy by a fixed multiple of its discounted gap at the same Blackwell discount throughout the run. The geometric bound of Xiao (2022) for the discounted gap therefore gives the same geometric rate for average reward. Geometrically increasing mirror-ascent step sizes yield the discounted rate while the reward objective remains unregularized. Rationality lets us certify the discount explicitly. The certified discount can be close to one, and our experiments suggest that smaller discounts can work well. Sharpening the certificate remains open.

  4. Scope of the guarantees. The rates concern exact policy evaluation, with instance-dependent constants. For DGPG, counting backtracking evaluations and candidate comparisons preserves the inverse-linear order for a fixed MDP. A finite-sample guarantee remains future work. As we clarified in the follow-up, continuous-action MDPs are outside the scope of this paper.

The Authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.