acceptodds
Under review as a conference paper at ICLR 2027

Finite-Time Regret Bounds for REINFORCE in Tabular MDPs

Abstract

We establish finite-time expected cumulative regret bounds for REINFORCE in finite-horizon tabular MDPs with unknown transitions and bounded deterministic rewards. The central challenge is that policies at earlier stages determine which states are visited at later stages, while inaccurate policies at later stages can make optimal actions at earlier stages appear unfavorable. We tackle this challenge through two contributions. First, we bound the value errors that can reduce the probabilities of optimal actions by the regret incurred at later stages. This bound allows a geometrically weighted potential to control cumulative regret. Second, we show that reducing an action’s probability requires cumulative use of that action, yielding quantitative bounds on state visitation along the mean flow. Together with stochastic tracking and probability control, these contributions yield expected regret from zero initialization, using one trajectory per update and no explicit exploration or regularization. The step size is , with an instance-dependent scale , and remains constant within each run. A step size chosen using only the episode budget yields regret. Finally, deterministic two-action chains exhibit linear expected regret over an initial window whose length grows as an exponential tower in the horizon, under a sufficiently small uniform step-size cap.

Primary area:
reinforcement learning
Keywords:
Reinforcement learning, Policy gradient, Regret analysis, Markov decision process

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_xZ6QOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies finite-time expected cumulative regret for REINFORCE in finite-horizon tabular MDPs with unknown transitions and deterministic rewards. The authors establish an OM(log⁡2K)O_{\mathcal M}(\log^2 K) regret bound with an instance-dependent learning rate and an OM(log⁡3K)O_{\mathcal M}(\log^3 K) bound with a budget-dependent learning rate. The analysis develops a Bellman-debt decomposition and a weighted potential function to control downstream value errors, together with state-visitation arguments to handle implicit exploration. The paper also establishes lower bounds showing that REINFORCE can suffer a long initial period of linear regret.

Critical strengths
  1. The paper establishes finite-time expected cumulative regret bounds for vanilla REINFORCE in finite-horizon tabular MDPs, improving upon previous asymptotic convergence results. In particular, it achieves an OM(log⁡2K)O_{\mathcal M}(\log^2 K) regret bound without explicit exploration or regularization, providing a theoretical understanding of the learning efficiency of REINFORCE.

  2. The paper develops novel analytical techniques to address downstream value errors and implicit exploration in MDPs. The Bellman-debt decomposition and weighted potential function provide a way to control cumulative regret, while the state-visitation analysis handles the dependence between upstream policies and downstream learning. The paper also establishes lower bounds that illustrate the potentially slow learning behavior of REINFORCE.

Critical weaknesses
  1. Although the regret bound is polylogarithmic in KK, the instance-dependent constants can be extremely large. While the tower-delay lower bound shows that long delays are unavoidable in some MDPs, the upper bound appears overly conservative even in simpler settings. In particular, for an AA-action bandit (H=1H=1), the regret constant derived in Appendix F grows as exp⁡(Θ(Δmin⁡−A))\exp(\Theta(\Delta_{\min}^{-A})) for fixed AA, whereas Lattimore (2026b) establishes polynomial gap dependence for the same REINFORCE update. This raises concerns about the tightness and practical significance of the finite-time guarantee.
  • Lattimore, T. (2026). A Lyapunov Analysis of Softmax Policy Gradient for Stochastic Bandits. arXiv preprint arXiv:2603.26547.
  1. The OM(log⁡2K)O_{\mathcal M}(\log^2 K) regret bound requires an instance-dependent learning rate whose certified scale can be extremely small due to the readiness recursion in Appendix F. Although Corollary 3.3 provides a budget-only learning rate, its proof relies on an instance-dependent threshold K0K_0, potentially of order exp⁡(1/ηˉ)\exp(1/\bar\eta), before the certified condition is satisfied. For smaller budgets, the proof falls back on the trivial linear regret bound. This raises concerns about the practical usefulness of the finite-time guarantees.

  2. Although the paper provides several lower bounds, they do not fully characterize the optimal regret under general learning-rate choices. The Ω(log⁡2K)\Omega(\log^2 K) lower bound matches the upper bound when η≍1/log⁡K\eta\asymp 1/\log K, while Theorem E.5 only rules out a constant learning rate shared across all instances. Whether a suitable instance-dependent constant learning rate can achieve O(log⁡K)O(\log K) regret on a fixed MDP remains open. It also remains unclear whether the strong dependence on Δmin⁡\Delta_{\min} and pmin⁡p_{\min} in the upper bound is inherent to REINFORCE or an artifact of the analysis.

Minor weaknesses: The paper does not include experiments to illustrate the theoretical results. In particular, numerical experiments could help evaluate the effects of the learning rate and horizon on the regret and the practical significance of the derived bounds.

Questions for authors
  1. Can the instance-dependent constants be improved, particularly in the H=1H=1 bandit setting, where existing analyses provide substantially tighter gap dependence?

  2. Can the authors quantify the budget threshold K0K_0 required for the budget-only learning rate to enter the certified regime? For a simple concrete instance, how large must KK be before the regret bound becomes nontrivial?

  3. Can an instance-dependent constant learning rate achieve O(log⁡K)O(\log K) regret on a fixed MDP? Is the strong dependence on Δmin⁡\Delta_{\min} and pmin⁡p_{\min} in the current upper bound inherent to REINFORCE or mainly due to the analysis?

  4. How essential are the deterministic reward and zero-initialization assumptions? Can the analysis be extended to more general settings, such as stochastic rewards, discounted MDPs, or linear MDPs with function approximation?

6 comments
AuthorsOpenReview ↗

Response to Reviewer xZ6Q (1/4)

Response to Reviewer xZ6Q

Thank you for the detailed questions on constants, step sizes, and the scope of the lower bounds. These questions led us to reorganize the proof around the actual entry conditions of each state-stage block.

W1 / Q1. Polynomial bandit dependence

Weakness:

  1. Although the regret bound is polylogarithmic in KK, the instance-dependent constants can be extremely large. While the tower-delay lower bound shows that long delays are unavoidable in some MDPs, the upper bound appears overly conservative even in simpler settings. In particular, for an AA-action bandit (H=1H=1), the regret constant derived in Appendix F grows as exp⁡(Θ(Δmin⁡−A))\exp(\Theta(\Delta_{\min}^{-A})) for fixed AA, whereas Lattimore (2026b) establishes polynomial gap dependence for the same REINFORCE update. This raises concerns about the tightness and practical significance of the finite-time guarantee.

  • Lattimore, T. (2026). A Lyapunov Analysis of Softmax Policy Gradient for Stochastic Bandits. arXiv preprint arXiv:2603.26547.

Question:

  1. Can the instance-dependent constants be improved, particularly in the H=1H=1 bandit setting, where existing analyses provide substantially tighter gap dependence?

We have replaced the exponential bandit dependence with a polynomial bound by incorporating Lattimore's local analysis into the multistage proof. The revision combines three specific tools with a stage-by-stage entry rule.

1. The local proof uses the inverse-coordinate, relative-logit, and nonlinear-potential arguments of Lattimore (2026b). The inverse-exponential transformation in Lemma 3(ii), applied to a logit θa\theta_a through e−θae^{-\theta_a}, provides the starting point for controlling how far logits can decrease; our nonnegative-return setting supplies a pathwise version of this control. The relative-logit barrier in Lemma 4 controls excursions of θo−θi\theta_o-\theta_i below zero, where oo is an optimal action and ii a suboptimal action. Lemma 5 and the proof of Theorem 1 relate the total optimal-action probability to the sum of optimal logits and use a nonlinear Lyapunov function to bound cumulative loss. This last step exploits the improvement of the probability bound as learning progresses, rather than charging all subsequent loss using one worst-case probability floor. The revised manuscript attributes these tools in Appendix C.1 and Appendices A.2–A.3.

2. The revised entry rule makes the bandit improvement a specialization of the MDP theorem. Theorem 3.1 separates downstream waiting, repair of an unordered entry, and local learning after an ordered entry. Here an ordered entry means that every optimal-action logit is at least every suboptimal-action logit. The local analysis accommodates changing downstream action values and policy-dependent state visits. At the terminal stage there is no downstream waiting, and zero initialization already supplies the ordered entry because all logits are equal. Consequently, at H=1H=1 the first two costs vanish and the local nonlinear-potential bound applies from initialization.

3. The resulting dependence is explicit and polynomial. For a single-state bandit, we obtain \mathbb E\operatorname{Reg}_K \le \min\left\\{K, \frac{2e^aA(b+1)}{\eta} \log\left(1+\frac{(A-r)b}{r(b+1)}\right)+1\right\\}, where rr is the number of optimal actions and Δmax⁡\Delta_{\max} is the largest positive reward gap, a=Δmin⁡2Δmax⁡,b=log⁡(1+K(eη−1)A).a=\frac{\Delta_{\min}}{2\Delta_{\max}}, \qquad b=\log\left(1+\frac{K(e^\eta-1)}A\right). The common step η\eta, fixed throughout the run, satisfies 0<η≤min⁡Δmin⁡/5888,Δmin⁡2/(32Δmax⁡)log⁡(64A2K).0<\eta\le \frac{\min\\{\Delta_{\min}/5888,\\ \Delta_{\min}^2/(32\Delta_{\max})\\}} {\log(64A^2K)}. Choosing the largest allowed step yields EReg⁡K=O!(Alog⁡(A/r)Δmax⁡Δmin⁡2log⁡2(AK)).\mathbb E\operatorname{Reg}_K =O\\!\left(A\log(A/r)\frac{\Delta_{\max}}{\Delta_{\min}^2} \log^2(AK)\right). Thus the former exp⁡(Θ(Δmin⁡−A))\exp(\Theta(\Delta_{\min}^{-A})) coefficient is replaced by polynomial action-count and gap dependence. Lattimore's Theorem 1 allows η≤Δmin⁡2/[120Δmax⁡log⁡(AK)]\eta\le\Delta_{\min}^2/[120\Delta_{\max}\log(AK)] and gives O(Alog⁡Alog⁡K/η)O(A\log A\log K/\eta) regret. Since Δmin⁡≤Δmax⁡\Delta_{\min}\le\Delta_{\max}, our step ceiling has the same gap and logarithmic-budget order up to universal numerical factors. For a unique optimal action (r=1r=1), in Lattimore's regime K≥AK\ge A, the resulting regret bounds also have the same action-count, gap, and logarithmic-budget orders. The revised bound displays the additional dependence on rr when there are multiple optimal actions. This bound and its step-size condition appear in Corollary 3.2, equations (7)–(8).

AuthorsOpenReview ↗

Response to Reviewer xZ6Q (2/4)

These changes address the bandit conservatism identified in the question while retaining a unified multistage statement: Theorem 3.1 gives the three-cost decomposition, Corollary 3.2 its bandit specialization, and Appendix A the revised local proof. In general MDPs, downstream waiting and unordered-entry costs remain explicit contributions; the polynomial specialization identifies exactly which losses disappear at the bandit boundary.

W2 / Q2. Step-size certification and nontrivial budgets

Weakness:

  1. The OM(log⁡2K)O_{\mathcal M}(\log^2 K) regret bound requires an instance-dependent learning rate whose certified scale can be extremely small due to the readiness recursion in Appendix F. Although Corollary 3.3 provides a budget-only learning rate, its proof relies on an instance-dependent threshold K0K_0, potentially of order exp⁡(1/ηˉ)\exp(1/\bar\eta), before the certified condition is satisfied. For smaller budgets, the proof falls back on the trivial linear regret bound. This raises concerns about the practical usefulness of the finite-time guarantees.

Question:

  1. Can the authors quantify the budget threshold K0K_0 required for the budget-only learning rate to enter the certified regime? For a simple concrete instance, how large must KK be before the regret bound becomes nontrivial?

We address the two budget questions separately: first, the threshold at which the budget-only step satisfies the theorem’s condition; second, concrete budgets at which the regret guarantee improves upon a linear bound.

1. When the budget-only step enters the certified regime.

The enlarged common step-size scale is \bar\eta=\min\left\\{\frac{\Delta_{\min}}{5888H^2}, \min_{h,s}\frac{\delta_{h,s}^2}{32M_{h,s}(H-h+1)^2}\right\\}. The minimum is over reachable state–stage blocks with at least one suboptimal action. To state all quantities explicitly, let Dmin⁡,h,sD_{\min,h,s} and Dmax⁡,h,sD_{\max,h,s} be the smallest and largest positive gaps Vh⋆(s)−Qh⋆(s,a)V_h^\star(s)-Q_h^\star(s,a) within that block, and define Rh=H−h+1,εh={Δmin⁡/4,h<H,0,h=H,R_h=H-h+1,\qquad \varepsilon_h=\begin{cases}\Delta_{\min}/4,&h<H,\\\\0,&h=H,\end{cases} δh,s=Dmin⁡,h,s−εh,Mh,s=min⁡Rh,Dmax⁡,h,s+εh.\delta_{h,s}=D_{\min,h,s}-\varepsilon_h,\qquad M_{h,s}=\min\\{R_h,D_{\max,h,s}+\varepsilon_h\\}. Here RhR_h is the maximum remaining return; εh\varepsilon_h is the allowed downstream value error, which is zero at the terminal stage. Accordingly, δh,s\delta_{h,s} is the guaranteed positive action-value separation after allowing for that error, and Mh,sM_{h,s} bounds the corresponding value spread. These are the quantities in equation (4). The common step is required to satisfy η≤ηˉlog⁡(CK),C=64HAnθ.\eta\le\frac{\bar\eta}{\log(CK)},\qquad C=64HAn_\theta. Here nθ=A∑h∣Sh∣n_\theta=A\sum_h|\mathcal S_h| is the number of logits and Sh\mathcal S_h is the stage-hh state set.

For the budget-only choice η=(1+log⁡K)−2\eta=(1+\log K)^{-2}, set M=ηˉ−1M=\bar\eta^{-1} and y=log⁡Ky=\log K. Certification is equivalent to y2+(2−M)y+1−Mlog⁡C≥0.y^2+(2-M)y+1-M\log C\ge0. Solving this inequality gives the following sufficient threshold: Kcert=⌈exp⁡(M−2+M2+4M(log⁡C−1)2)⌉.K_{\mathrm{cert}}= \left\lceil\exp\left( \frac{M-2+\sqrt{M^2+4M(\log C-1)}}2 \right)\right\rceil. This answers when that particular budget-only rule enters the theorem's regime. The enlarged step-size scale appears in equation (9); Corollary 3.4, equation (11), and Appendix F.4 establish the budget-only guarantee. The explicit threshold calculation above appears in Appendix F.4, equation (F.6).

2. Concrete budgets with a non-trivial regret guarantee.

For an instance-dependent step, the displayed regret bound can be evaluated directly at each budget. The revised bandit example with rewards (1,0)(1,0) is nontrivial at K=106K=10^6.

For a multistage illustration, we use a class with polynomial constants under a common-reference transition condition, then evaluate its bound on a 17-state member. Theorem 5.2 and the numerical example appear in Section 5, with the proof in Appendix K.

Consider a layered MDP with arbitrary horizon HH, NN state-stage blocks, two actions per state, deterministic rewards in [0,1][0,1], and a unique Bellman-optimal action at each state. Suppose each nonterminal layer h<Hh<H has a reference probability distribution νh+1\nu_{h+1} on the next-layer state set Sh+1\mathcal S_{h+1}, with νh+1(x)≥0\nu_{h+1}(x)\ge0 and ∑x∈Sh+1νh+1(x)=1\sum_{x\in\mathcal S_{h+1}}\nu_{h+1}(x)=1, such that (1−ε)νh+1(x)≤Ph(x∣s,a)≤(1+ε)νh+1(x),0≤ε<3−22.(1-\varepsilon)\nu_{h+1}(x)\le P_h(x\mid s,a)\le(1+\varepsilon)\nu_{h+1}(x), \qquad 0\le\varepsilon<3-2\sqrt2. Here νh+1\nu_{h+1} is a probability vector, and νh+1(x)\nu_{h+1}(x) is its mass at next-layer state xx. The same vector is used for all states and actions in layer hh; it may vary across layers. Thus states and actions can change the transition distribution within a bounded relative distance of a common reference. Current action values may initially rank the Bellman-optimal action incorrectly.

AuthorsOpenReview ↗

Response to Reviewer xZ6Q (3/4)

Let Δmin⁡\Delta_{\min} be the minimum positive Bellman gap and κ=1−4ε/(1−ε)2\kappa=1-4\varepsilon/(1-\varepsilon)^2. For the original zero-initialized, return-to-go REINFORCE update, the same fixed step η=Δmin⁡/(8H2)\eta=\Delta_{\min}/(8H^2) at every state and episode gives EReg⁡K≤U(K):=Nηκ[1+log⁡(1+2ηHe2ηHK)].\mathbb E\operatorname{Reg}_K\le U(K):=\frac{N}{\eta\kappa} \left[1+\log\left(1+2\eta H e^{2\eta H}K\right)\right]. This is polynomial in N,H,Δmin⁡−1,κ−1N,H,\Delta_{\min}^{-1},\kappa^{-1} and logarithmic in KK. The proof combines the paper's Bellman-debt decomposition with a two-action local drift inequality: the common-reference condition bounds the aggregate downstream debt by a fixed fraction of the same-policy regret, allowing it to be absorbed after summing across stages. This supplies a structural theorem using the paper's proof tools, with no recursive readiness cost or minimum positive reference-mass parameter.

A concrete example has H=9H=9 and 17 states. Root rewards are (.035,0)(.035,0); each later layer has two state types with rewards (1,0)(1,0) and (.95,.91)(.95,.91). The two actions transition to the next types with probabilities (.55,.45)(.55,.45) and (.45,.55)(.45,.55). The common reference is νh+1=(.5,.5)\nu_{h+1}=(.5,.5) and ε=.1\varepsilon=.1, so each coordinate of either transition row lies between (1−.1)×.5=.45(1-.1)\times.5=.45 and (1+.1)×.5=.55(1+.1)\times.5=.55. Here Δmin⁡=.04\Delta_{\min}=.04, and the current gaps at uniform initialization are −.008-.008 at the root and −.003-.003 at intermediate states of the second type. The example therefore includes simultaneous value-order reversals at multiple stages.

Direct evaluation gives a nontrivial guarantee at about 1.08×1061.08\times10^6 episodes, or 9.70×1069.70\times10^6 environment steps. At K=107K=10^7 episodes, or 9×1079\times10^7 environment steps, U(K)≈5.61×106<K(V∗−Vmin⁡)≈4.08×107.U(K)\approx5.61\times10^6 < K(V^*-V^{\min})\approx4.08\times10^7. The bound is approximately 13.7513.75\\% of the instance-specific worst-policy linear bound, which is itself at most HKHK. The values V∗V^* and Vmin⁡V^{\min} are obtained by maximizing and minimizing the Bellman recursion. These figures evaluate the structural theorem; they establish a useful finite-budget guarantee for this class. Tightness and the necessity of the chosen step size are separate questions.

W3 / Q3. Constant steps and lower-bound quantifiers

Weakness:

  1. Although the paper provides several lower bounds, they do not fully characterize the optimal regret under general learning-rate choices. The Ω(log⁡2K)\Omega(\log^2 K) lower bound matches the upper bound when η≍1/log⁡K\eta\asymp1/\log K, while Theorem E.5 only rules out a constant learning rate shared across all instances. Whether a suitable instance-dependent constant learning rate can achieve O(log⁡K)O(\log K) regret on a fixed MDP remains open. It also remains unclear whether the strong dependence on Δmin⁡\Delta_{\min} and pmin⁡p_{\min} in the upper bound is inherent to REINFORCE or an artifact of the analysis.

Question:

  1. Can an instance-dependent constant learning rate achieve O(log⁡K)O(\log K) regret on a fixed MDP? Is the strong dependence on Δmin⁡\Delta_{\min} and pmin⁡p_{\min} in the current upper bound inherent to REINFORCE or mainly due to the analysis?

We address the fixed-step question with a stronger single-instance lower bound, and then explain what the current results establish about gap and reachability dependence.

1. A fixed-instance lower bound for constant step sizes.

We give the following additional fixed-instance lower bound in this response. It is not included in the current manuscript. The construction uses a single deterministic MDP with three stages, two actions per state, and five states in total. For this same MDP, every fixed η>0\eta>0 satisfies EReg⁡K≥cηK(1+log⁡K)rη,K≥1,\mathbb E\operatorname{Reg}_K \ge c_\eta\frac{K}{(1+\log K)^{r_\eta}},\qquad K\ge1, for constants cη,rη>0c_\eta,r_\eta>0 that may depend on the fixed step η\eta but not on the budget KK. The MDP is independent of the choice of η\eta.

The instance offers a safe reward of 3/43/4 at the first decision, a safe reward of 5/85/8 at the second, and a terminal choice between rewards 11 and 00. Continuing at both upstream states leads to the terminal reward; taking a safe action leads to a zero-reward tail. Thus the optimal value is 11, while early downstream policies make continuing appear less attractive.

The proof controls the tail of the first positive terminal feedback. Until that feedback arrives, upstream suppression repeatedly reduces the downstream learning opportunities. This produces the stated lower bound on expected regret from initialization.

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

The paper analyzes plain REINFORCE (one trajectory per update, no baseline or exploration bonus) on tabular finite-horizon MDPs. It bounds expected regret from the first episode: about log⁡2K\log^2 K over KK episodes with a tuned learning rate, or log⁡3K\log^3 K with a budget-only rate. Lower bounds show that very long slow-learning phases can be unavoidable.

Critical strengths
  • The paper analyzes the actual one-trajectory REINFORCE update, with no added exploration, critic, regularizer or resets. It controls the learning cost from initialization, including the transient phase, rather than only eventual behaviour. REINFORCE-style updates remain widely used, so knowing when the plain update explores well enough on its own is of broad interest.

  • the Bellman-debt argument is clean and reusable.

Critical weaknesses
  • The readiness time is exponential in A even with simple settings and certified steps seems to be very very small for usual settings.

  • Is there a nontrivial MDP class, beyond the terminal bandit, where the constants are polynomial and the bound is informative at realistic KK? Which parts of the recursion remain unavoidable there?

  • The one-stage case is covered by prior work. For H=1H=1, Lattimore (2026b) obtains log⁡2n\log^2 n regret with polynomial constants and stochastic rewards, using a step of order Δ2/log⁡n\Delta^2/\log n, i.e. essentially the same 1/log⁡1/\log tuning. Baudry et al. (2025) obtain O(log⁡T)O(\log T) with a constant step in the two-arm and identical-gap cases.

  • Can the authors add a main-text table comparing step size, rate, constants and reward model against Robertson et al., Lattimore and Baudry et al.? Is the new content of the upper bound confined to H≥2H\ge 2?

  • Can the authors claridfy if the step size 1/log⁡K1/\log K only a proof requirement? or intrinsic to REINFORCE

  • Curious: Which lemma fails for bounded noisy rewards with the same mean? the rewards are deterministic

  • Some attributions and comparision withe related works and explicit claims about what is novel is missing

e.g. The proof of Lemma A.6 (p.20) seems to follow from Lattimore (2026b, Lemma 3(ii)).

Questions for authors

see above

6 comments
AuthorsOpenReview ↗

Response to Reviewer m9Ac (1/4)

Response to Reviewer m9Ac

Thank you for emphasizing the value of analyzing the original one-trajectory update and its transient learning cost. We address the step size, bandit boundary, related work, and modeling questions in turn.

1 & 3. Common proof revisions: step size, readiness, and the bandit boundary

Comment 1:

The readiness time is exponential in A even with simple settings and certified steps seem to be very very small for usual settings.

Comment 3:

The one-stage case is covered by prior work. For H=1H=1, Lattimore (2026b) obtains log⁡2n\log^2 n regret with polynomial constants and stochastic rewards, using a step of order Δ2/log⁡n\Delta^2/\log n, i.e. essentially the same 1/log⁡1/\log tuning. Baudry et al. (2025) obtain O(log⁡T)O(\log T) with a constant step in the two-arm and identical-gap cases.

The same proof revision addresses these two concerns: it replaces long-horizon ODE tracking with direct discrete analysis and separates downstream waiting, entry repair, and local learning. This both enlarges the common step size and recovers polynomial bandit dependence at the terminal boundary.

Shared proof changes and their technical basis.

The discrete analysis builds on specific tools from Lattimore (2026b): the inverse-exponential-coordinate transformation in Lemma 3(ii), the relative-logit barrier argument in Lemma 4, and the optimal-action-mass/logit comparison and nonlinear Lyapunov argument in Lemma 5 and the proof of Theorem 1. We adapt these local tools to an MDP, where downstream values evolve and states are visited at policy-dependent rates. The visitation, recovery, and persistence arguments connect them across stages. Appendices C.1 and A.2–A.3 identify these connections explicitly.

The proof separately accounts for waiting for downstream values, repairing the current policy's entry, and learning after entry. At the terminal stage, downstream waiting is zero and zero initialization already supplies the ordered entry. This directly removes the unnecessary recovery cost at the bandit boundary.

(a) Readiness and the common step size.

The revised proof establishes visitation, recovery, and persistence directly for the discrete iterates. This removes the long-horizon ODE-tracking restriction from the common step size. Write Δh(s,a)=Vh⋆(s)−Qh⋆(s,a)\Delta_h(s,a)=V_h^\star(s)-Q_h^\star(s,a) for the Bellman gap and Δmin⁡\Delta_{\min} for its smallest positive value over reachable state–action pairs. Writing x=log⁡(64HAnθK)x=\log(64HAn_\theta K), the revised condition is \eta\le\min\left\\{ \frac{\Delta_{\min}}{5888H^2x}, \min_{h,s}\frac{\delta_{h,s}^2}{32M_{h,s}(H-h+1)^2x} \right\\}. Here nθ=A∑h∣Sh∣n_\theta=A\sum_h|\mathcal S_h| is the number of logits and Sh\mathcal S_h is the stage-hh state set. The minimum is over reachable state–stage blocks with at least one suboptimal action. To state all quantities explicitly, let Dmin⁡,h,sD_{\min,h,s} and Dmax⁡,h,sD_{\max,h,s} be the smallest and largest positive gaps Vh⋆(s)−Qh⋆(s,a)V_h^\star(s)-Q_h^\star(s,a) within that block, and define Rh=H−h+1,εh={Δmin⁡/4,h<H,0,h=H,R_h=H-h+1,\qquad \varepsilon_h=\begin{cases}\Delta_{\min}/4,&h<H,\\\\0,&h=H,\end{cases} δh,s=Dmin⁡,h,s−εh,Mh,s=min⁡Rh,Dmax⁡,h,s+εh.\delta_{h,s}=D_{\min,h,s}-\varepsilon_h,\qquad M_{h,s}=\min\\{R_h,D_{\max,h,s}+\varepsilon_h\\}. Here RhR_h is the maximum remaining return; εh\varepsilon_h is the allowed downstream value error, which is zero at the terminal stage. Accordingly, δh,s\delta_{h,s} is the guaranteed positive action-value separation after allowing for that error, and Mh,sM_{h,s} bounds the corresponding value spread. These are the quantities in equation (4). The first term controls recovery, and the second controls relative-logit fluctuations in the local regret analysis. All states and all episodes use this same constant step size. These discrete visitation, recovery, and persistence guarantees are proved in Lemma C.1 and Lemmas B.1–B.2.

(b) The bandit specialization and its relation to prior work.

In the bandit setting, Δmin⁡\Delta_{\min} and Δmax⁡\Delta_{\max} denote the smallest and largest positive reward gaps. The step-size ceiling in Corollary 3.2, equation (8), has the same gap and budget dependence as Lattimore (2026b, Theorem 1): both are of order Δmin⁡2/[Δmax⁡log⁡(AK)]\Delta_{\min}^2/[\Delta_{\max}\log(AK)]. Specifically, our ceiling is min⁡Δmin⁡/5888,Δmin⁡2/(32Δmax⁡)/log⁡(64A2K)\min\\{\Delta_{\min}/5888,\Delta_{\min}^2/(32\Delta_{\max})\\}/\log(64A^2K), while Lattimore's is Δmin⁡2/[120Δmax⁡log⁡(AK)]\Delta_{\min}^2/[120\Delta_{\max}\log(AK)]. Since Δmin⁡≤Δmax⁡\Delta_{\min}\le\Delta_{\max}, the minimum in our expression differs from Δmin⁡2/Δmax⁡\Delta_{\min}^2/\Delta_{\max} by at most universal constant factors. For two actions or comparable positive gaps, both simplify to order Δmin⁡/log⁡(AK)\Delta_{\min}/\log(AK).

AuthorsOpenReview ↗

Response to Reviewer m9Ac (2/4)

The revised bandit specialization recovers polynomial gap and action-count dependence through the same local entry rule used in the MDP proof. Writing rr for the number of optimal actions, its leading rate is O!(Alog⁡(A/r)Δmax⁡Δmin⁡2log⁡2(AK)).O\\!\left(A\log(A/r)\frac{\Delta_{\max}}{\Delta_{\min}^2}\log^2(AK)\right). For comparable positive gaps, this has the 1/Δmin⁡1/\Delta_{\min} dependence obtained by substituting the corresponding gap-ratio tuning into the bandit bound.

Baudry et al. give constant-step logarithmic results for two arms and the equal-gap setting. Robertson et al. analyze exploration and convergence in MDPs; our performance criterion is expected cumulative regret measured from initialization, which includes the transient cost.

2. Polynomial multistage class and concrete budgets

Is there a nontrivial MDP class, beyond the terminal bandit, where the constants are polynomial and the bound is informative at realistic KK? Which parts of the recursion remain unavoidable there?

We address the two parts of the question with one multistage MDP class and one concrete member of that class. First, a shared-reference-transition condition yields Theorem 5.2 with polynomial constants. Second, substituting a nine-stage, 17-state member into that same theorem gives an explicit finite-budget guarantee. The theorem and numerical example appear in Section 5, with the proof in Appendix K.

(a) A multistage class with polynomial constants.

Consider a layered MDP with arbitrary horizon HH, NN state-stage blocks, two actions per state, deterministic rewards in [0,1][0,1], and a unique Bellman-optimal action at each state. Suppose each nonterminal layer h<Hh<H has a reference probability distribution νh+1\nu_{h+1} on the next-layer state set Sh+1\mathcal S_{h+1}, with νh+1(x)≥0\nu_{h+1}(x)\ge0 and ∑x∈Sh+1νh+1(x)=1\sum_{x\in\mathcal S_{h+1}}\nu_{h+1}(x)=1, such that (1−ε)νh+1(x)≤Ph(x∣s,a)≤(1+ε)νh+1(x),0≤ε<3−22.(1-\varepsilon)\nu_{h+1}(x)\le P_h(x\mid s,a)\le(1+\varepsilon)\nu_{h+1}(x), \qquad 0\le\varepsilon<3-2\sqrt2. Here νh+1\nu_{h+1} is a probability vector, and νh+1(x)\nu_{h+1}(x) is its mass at next-layer state xx. The same vector is used for all states and actions in layer hh; it may vary across layers. Thus states and actions can change the transition distribution within a bounded relative distance of a common reference. Current action values may initially rank the Bellman-optimal action incorrectly.

Let Δmin⁡\Delta_{\min} be the minimum positive Bellman gap and κ=1−4ε/(1−ε)2\kappa=1-4\varepsilon/(1-\varepsilon)^2. For the original zero-initialized, return-to-go REINFORCE update, the same fixed step η=Δmin⁡/(8H2)\eta=\Delta_{\min}/(8H^2) at every state and episode gives EReg⁡K≤U(K):=Nηκ[1+log⁡(1+2ηHe2ηHK)].\mathbb E\operatorname{Reg}_K\le U(K):=\frac{N}{\eta\kappa} \left[1+\log\left(1+2\eta H e^{2\eta H}K\right)\right]. This is polynomial in N,H,Δmin⁡−1,κ−1N,H,\Delta_{\min}^{-1},\kappa^{-1} and logarithmic in KK. The proof combines the paper's Bellman-debt decomposition with a two-action local drift inequality: the common-reference condition bounds the aggregate downstream debt by a fixed fraction of the same-policy regret, allowing it to be absorbed after summing across stages. Under this condition, the backward readiness recursion is eliminated altogether, leaving only the stagewise Bellman-debt summation and the single-stage two-action local drift recursion.

(b) A 17-state member of this class: evaluating the same bound.

To instantiate the preceding theorem, take H=9H=9 and 17 states. Root rewards are (.035,0)(.035,0); each later layer has two state types with rewards (1,0)(1,0) and (.95,.91)(.95,.91). The two actions transition to the next types with probabilities (.55,.45)(.55,.45) and (.45,.55)(.45,.55). The common reference is νh+1=(.5,.5)\nu_{h+1}=(.5,.5) and ε=.1\varepsilon=.1, so each coordinate of either transition row lies between (1−.1)×.5=.45(1-.1)\times.5=.45 and (1+.1)×.5=.55(1+.1)\times.5=.55. Here Δmin⁡=.04\Delta_{\min}=.04, and the current gaps at uniform initialization are −.008-.008 at the root and −.003-.003 at intermediate states of the second type. The example therefore includes simultaneous value-order reversals at multiple stages.

Substituting these parameters into the theorem's U(K)U(K) gives a nontrivial guarantee at about 1.08×1061.08\times10^6 episodes, or 9.70×1069.70\times10^6 environment steps. At K=107K=10^7 episodes, or 9×1079\times10^7 environment steps, U(K)≈5.61×106<K(V∗−Vmin⁡)≈4.08×107.U(K)\approx5.61\times10^6 < K(V^*-V^{\min})\approx4.08\times10^7. The bound is approximately 13.7513.75\\% of the instance-specific worst-policy linear bound, which is itself at most HKHK. The values V∗V^* and Vmin⁡V^{\min} are obtained by maximizing and minimizing the Bellman recursion. These figures evaluate the structural theorem; they establish a useful finite-budget guarantee for this class.

4. Main-text comparison and the scope of novelty

Can the authors add a main-text table comparing step size, rate, constants and reward model against Robertson et al., Lattimore and Baudry et al.? Is the new content of the upper bound confined to H≥2H\ge2?

AuthorsOpenReview ↗

Response to Reviewer m9Ac (3/4)

The main new content of the general upper bound is the multistage coupling for H≥2H\ge2, with regret measured from initialization. To make the comparison with prior work explicit, Table 1 in Section 3.2 compares Robertson et al., Lattimore, Baudry et al., and our result in terms of setting, reward model, step-size tuning, performance criterion, and transient treatment. Corollary 3.2 states the improved bandit specialization and its parameter dependence; Corollary 3.3 gives the general-MDP rate at the largest certified step; the displayed bound supplies the constants for that specialization. The local bandit proof builds on Lattimore’s analysis, as credited in Appendices A.2–A.3 and C.1.

5. Is the 1/log⁡K1/\log K tuning intrinsic?

Can the authors clarify whether the step size 1/log⁡K1/\log K is only a proof requirement or is intrinsic to REINFORCE.

For general multi-action bandits and multistage MDPs, the available guarantees motivate budget-dependent tuning, while the exact necessity of 1/log⁡K1/\log K remains open. For stochastic bandits with unequal gaps, Lattimore (2026b, Theorem 1) proves O(Alog⁡Alog⁡K/η)O(A\log A\log K/\eta) regret under η≤Δmin⁡2/[120Δmax⁡log⁡(AK)]\eta\le\Delta_{\min}^2/[120\Delta_{\max}\log(AK)] and explicitly identifies removal of the logarithmic factor as an open question in Section 6. Our general-MDP guarantee likewise uses a budget-dependent common step, held fixed throughout each run. In our proof, 1/log⁡K1/\log K controls the probability of leaving the protected region over the full budget. The following positive results and counterexamples explain the underlying step-size trade-off.

Small constant steps suffice in special bandit classes. Baudry et al. (2025, Theorems 1 and 4) establish O(log⁡K)O(\log K) regret for two-arm and equal-positive-gap bandits with a unique optimal arm and suitably small, instance-dependent constant steps. Their reward distributions are supported on [−1,1][-1,1]. These results show that the logarithmic budget factor can be removed in those classes.

Larger constant steps can incur polynomial regret. Baudry et al. (2025, Theorem 3) provide a multi-action obstruction. As stated in Lattimore (2026b, Remark 6), if η>3log⁡(3)/(A−1)\eta>3\log(3)/(A-1), there exists a bounded stochastic-reward bandit with Δmin⁡≥1/2\Delta_{\min}\ge1/2 and regret Ω(K2/3)\Omega(K^{2/3}). Thus step-size restrictions reflect a genuine performance trade-off. This example obstructs one positive constant step uniformly over all action counts; the question of a suitably smaller instance-dependent constant step has different quantifiers.

Our multistage construction makes the obstruction explicit with deterministic rewards and transitions. Theorem E.5, equations (E.48)–(E.49), states that for every fixed η>0\eta>0 and integer action count A>max⁡2,1+2/ηA>\max\\{2,1+2/\eta\\}, there is a two-stage MDP for which zero-initialized REINFORCE satisfies, for every budget K≥1K\ge1, EReg⁡K≥K2exp⁡![−1+(2/η)log⁡(1+ηK/2)A−1]=Ωη,A!(K,1−2/[η(A−1)]).\mathbb E\operatorname{Reg}_K \ge \frac K2\exp\\!\left[ -\frac{1+(2/\eta)\log(1+\eta K/2)}{A-1} \right] =\Omega_{\eta,A}\\!\left(K^{\\,1-2/[\eta(A-1)]}\right). The exponent is positive, and the constant hidden in Ωη,A\Omega_{\eta,A} may depend on η,A\eta,A but not on KK. The instance can depend on η\eta and is then fixed for all budgets. This establishes a deterministic multistage instance-family obstruction, with quantifiers ∀η>0,∃Mη\forall\eta>0\\,\exists\mathcal M_\eta. The stronger question of a suitable constant step chosen for each fixed MDP is addressed by the fixed-instance lower bound below.

The quantitative lower bounds separate the cost of tuning from the cost of downstream learning. For the terminal two-action bandit with rewards (1,0)(1,0), Appendix E gives EReg⁡K≥log⁡(1+ηe2ηK)2ηe2η.\mathbb E\operatorname{Reg}_K \ge \frac{\log(1+\eta e^{2\eta}K)}{2\eta e^{2\eta}}. Consequently, for η=c/log⁡K\eta=c/\log K with fixed c>0c>0, the regret is Ω(log⁡2K)\Omega(\log^2 K) for sufficiently large KK. This matches the budget order of our upper bound under that tuning. Separately, Theorem E.2 gives a deterministic, two-action MDP for each H≥4H\ge4, with minimum positive Bellman gap 1/41/4, and constants UH,ηHcap>0U_H,\eta_H^{\mathrm{cap}}>0 depending only on HH. From zero initialization, any predictable scalar steps 0≤ηk≤ηmax⁡≤ηHcap0\le\eta_k\le\eta_{\max}\le\eta_H^{\mathrm{cap}} satisfy EReg⁡K≥K/8wheneverηmax⁡K≤UH/2.\mathbb E\operatorname{Reg}_K\ge K/8 \qquad\text{whenever}\qquad \eta_{\max}K\le U_H/2. Here predictable means chosen using the history before episode kk; UHU_H is the scaled delay threshold and ηHcap\eta_H^{\mathrm{cap}} is the allowed step cap. For sufficiently large HH, UHU_H is at least an exponential tower with H−O(log⁡H)H-O(\log H) levels. This result quantifies a potentially very long initial learning cost even for small steps.

Reviewer_2TmFOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies the finite-time regret of REINFORCE in finite-horizon tabular MDPs with unknown transitions, deterministic rewards, single-trajectory on-policy sampling, and zero logit initialization. It establishes an expected pseudo-regret bound of OM(log⁡2K)O_{\mathcal M}(\log^2 K) under an instance-dependent constant step size η=ηˉ/log⁡K\eta=\bar\eta/\log K, and OM(log⁡3K)O_{\mathcal M}(\log^3 K) under a budget-only step size. Technically, the paper introduces a "Bellman debt" bounded by downstream stage regrets, compensates for it via a geometrically weighted linear potential, and establishes a uniform floor on optimal-action probability through cumulative action-use constraints and occupancy propagation along the mean flow; it also constructs a deterministic chain MDP with a potentially tower-sized initial linear-regret window.

Critical strengths

[S1] Reusable analytical tools. The Bellman debt, the geometrically weighted linear potential with cross-stage compensation, and the cumulative-action-use bound on probability decay are non-trivial devices. The readiness/tracking/barrier pipeline that transfers mean-flow guarantees to stochastic iterates is carefully assembled and may be borrowed by future analyses of baseline-augmented or regularized variants.

Critical weaknesses

[W1] The main upper bound is severely weakened by its instance-dependent constant, and no K0K_0 is provided. The bound is CMlog⁡2K+2HC_{\mathcal M}\log^2 K+2H, but the authors themselves describe CMC_{\mathcal M} as potentially tower-sized in HH and pmin⁡−1p_{\min}^{-1}, arising from repeated composition of occupancy delivery maps across paths and backward stages. The paper gives no explicit or computable estimate of the threshold K0K_0 beyond which the bound improves upon the trivial HKHK bound, nor any non-trivial instance class on which CMC_{\mathcal M} is polynomial or otherwise controlled. The reader therefore cannot determine when the main theorem carries non-trivial information. For a paper whose central contribution is a finite-time regret bound, this is a serious limitation.

[W2] Limited insight beyond known qualitative mechanisms. The core qualitative conclusions—unbaselined REINFORCE has high variance, inaccurate downstream policies can give optimal upstream actions negative advantage, and occupancy suppression can recursively amplify delays—have been identified in prior work (Sutton et al., 1999; Robertson et al., 2025; Li et al., 2023). The present paper mainly re-derives these mechanisms in a more refined stochastic finite-horizon setting. While the technical execution is non-trivial, the paper does not articulate a new mechanism-level insight that follows from the analysis.

[W3] No connection to practically relevant variants. The analyzed algorithm has no baseline, no critic, no entropy regularization, and no clipping. The paper does not discuss what its Bellman-debt or occupancy-propagation tools imply for baseline-augmented REINFORCE, PPO-style methods, or group-relative variants used in LLM alignment. Given the paper's motivation from classical REINFORCE, a discussion of how the diagnosed pathology is or is not mitigated by standard variance-reduction devices would substantially increase the value of the contribution.

Questions for authors

See Weaknesses.

6 comments
AuthorsOpenReview ↗

Response to Reviewer 2TmF (1/4)

Response to Reviewer 2TmF

Thank you for highlighting the Bellman-debt decomposition and the cumulative-action-use argument. We have revised the upper-bound analysis to separate downstream waiting, recovery when optimal actions initially have smaller logits than suboptimal actions, and local learning once every optimal-action logit is at least every suboptimal-action logit. This gives a larger common step size and a polynomial bandit specialization. Below we explain how these changes address your questions.

W1. Explicit constants and nontrivial finite-time guarantees

[W1] The main upper bound is severely weakened by its instance-dependent constant, and no K0K_0 is provided. The bound is CMlog⁡2K+2HC_{\mathcal M}\log^2 K+2H, but the authors themselves describe CMC_{\mathcal M} as potentially tower-sized in HH and pmin⁡−1p_{\min}^{-1}, arising from repeated composition of occupancy delivery maps across paths and backward stages. The paper gives no explicit or computable estimate of the threshold K0K_0 beyond which the bound improves upon the trivial HKHK bound, nor any non-trivial instance class on which CMC_{\mathcal M} is polynomial or otherwise controlled. The reader therefore cannot determine when the main theorem carries non-trivial information. For a paper whose central contribution is a finite-time regret bound, this is a serious limitation.

We address when the finite-time guarantee carries non-trivial information in three parts. First, we give an explicit, nonrecursive upper bound on CMC_{\mathcal M} in terms of the MDP parameters. Second, we use this bound to give an explicit, computable sufficient threshold K0K_0 beyond which the guarantee improves upon the trivial HKHK bound. Third, we provide a non-trivial multistage instance class with polynomial constants, together with a concrete 17-state example showing the budget at which its guarantee becomes non-trivial. All three additions are included in the revised manuscript, in Section 5 and Appendix F, with the structural proof in Appendix K.

1. Explicit, nonrecursive instance-dependent constant.

The improved upper bound separates the cost of waiting for accurate downstream values, the cost of repairing an unordered entry (where an ordered entry means that every optimal-action logit is at least every suboptimal-action logit once downstream values are accurate), and the subsequent local learning cost. The same formula applies at every stage. At the terminal stage, downstream waiting is zero and initialization already supplies an ordered entry, so only the local learning cost remains. This separation is stated in revised Theorem 3.1, equations (5)–(6); the component constants are constructed in Appendix F.1, equations (F.1)–(F.5), with their dependency order in F.2.

We now give an explicit nonrecursive upper bound on the coefficient of log⁡2K\log^2 K. For H≥2H\ge2, let N=∑h∣Sh∣N=\sum_h|\mathcal S_h| be the number of state–stage blocks, Δ=Δmin⁡\Delta=\Delta_{\min} the smallest positive Bellman gap Δh(s,a)=Vh⋆(s)−Qh⋆(s,a)\Delta_h(s,a)=V_h^\star(s)-Q_h^\star(s,a) over reachable state–action pairs, and p=pmin⁡p=p_{\min} the smallest positive initial-state or transition probability over reachable states. Define δ0=min⁡1,Δ,m=H(H−1)2,B=65536AH2pδ0,Λlog⁡=1+log⁡(64HA2N)log⁡2,clog⁡=1+1log⁡2.\begin{aligned} \delta_0&=\min\\{1,\Delta\\},& m&=\frac{H(H-1)}2,& \mathfrak B&=\frac{65536AH^2}{p\delta_0},\\\\ \Lambda_{\log}&=1+\frac{\log(64HA^2N)}{\log2},& c_{\log}&=1+\frac1{\log2}. \end{aligned} Tnr=A2p[(1+2HA+64HΔ+512AH(H−1)Δ2)A−(1+2HA)A]+AH+log⁡(3,2A−1Bm(2A)H−2Hp),Unr=exp⁡∘m(Tnr),Snr=(2+64Hδ0)(1+2HUnrA).\begin{aligned} T_{\rm nr}={}&\frac{A}{2p}\left[ \left(1+\frac{2H}{A}+\frac{64H}{\Delta} +\frac{512AH(H-1)}{\Delta^2}\right)^A -\left(1+\frac{2H}{A}\right)^A \right]\\\\ &+AH+\log\left(\frac{3\\,2^{A-1}\mathfrak B^m(2A)^{H-2}}{Hp}\right),\\\\ \mathcal U_{\rm nr}={}&\exp^{\circ m}(T_{\rm nr}),\\\\ \mathcal S_{\rm nr}={}& \left(2+\frac{64H}{\delta_0}\right) \left(1+\frac{2H\mathcal U_{\rm nr}}{A}\right). \end{aligned} Here exp⁡∘m\exp^{\circ m} denotes mm successive applications of the exponential function, and all logarithms are natural. With the instance-dependent step-size tuning of Corollary 3.3, for all K≥2K\ge2, EReg⁡K≤CMlog⁡2K+H,\mathbb E\operatorname{Reg}_K\le C_{\mathcal M}\log^2K+H, where the coefficient obtained from the proof satisfies CM≤CMnr:=6000Λlog⁡H3δ02[HUnrlog⁡2+43NA2SnrA(1+log⁡Snrlog⁡2)+8e3NAclog⁡log⁡A].\begin{aligned} C_{\mathcal M}\le C_{\mathcal M}^{\rm nr}:={}& \frac{6000\Lambda_{\log}H^3}{\delta_0^2} \left[ \frac{H\mathcal U_{\rm nr}}{\log2} +\frac43NA^2\mathcal S_{\rm nr}^{A} \left(1+\frac{\log\mathcal S_{\rm nr}}{\log2}\right) +\frac{8\sqrt e}{3}NAc_{\log}\log A \right]. \end{aligned} The tower height is explicitly m=H(H−1)/2m=H(H-1)/2 in the readiness envelope Unr\mathcal U_{\rm nr}; Snr\mathcal S_{\rm nr} then controls the entry contribution. This nonrecursive envelope and its proof appear in Appendix F.5, Proposition F.1, equations (F.10)–(F.11), and Corollary 3.3 now explicitly permits CM=CMnrC_{\mathcal M}=C_{\mathcal M}^{\rm nr}.

AuthorsOpenReview ↗

Response to Reviewer 2TmF (2/4)

2. A computable budget beyond which the bound is non-trivial.

An explicit sufficient budget follows from this coefficient. Under the instance-dependent tuning ηK=ηˉ/log⁡(64HAnθK)\eta_K=\bar\eta/\log(64HAn_\theta K) of Corollary 3.3, where ηˉ\bar\eta is the instance-dependent step-size numerator specified there and nθ=ANn_\theta=AN is the number of logits, the same step is used at all states and throughout the run. Define $ B_{\mathcal M}:=\max\left\{1,\frac{2C_{\mathcal M}^{\rm nr}}H\right\}, \qquad K_{\mathrm{nontrivial}} :=\left\lceil4B_{\mathcal M}\log^2(4B_{\mathcal M})\right\rceil. $ Then every integer budget K≥KnontrivialK\ge K_{\mathrm{nontrivial}} satisfies $ \mathbb E\operatorname{Reg}_K \le C_{\mathcal M}^{\rm nr}\log^2K+H \le \frac{HK}{2}+H<HK. $ Indeed, log⁡(4BMlog⁡2(4BM))≤2log⁡(4BM)\log(4B_{\mathcal M}\log^2(4B_{\mathcal M}))\le 2\log(4B_{\mathcal M}) and log⁡2x/x\log^2x/x decreases for x≥e2x\ge e^2. This is a sufficient, fully nonrecursive threshold for the stated instance-dependent tuning; that tuning satisfies the step-size condition for every K≥2K\ge2. The coefficient is established in Appendix F.5, and this threshold calculation is now included in Appendix F.4, equations (F.7)–(F.8).

At the single-state bandit boundary, the same analysis yields polynomial dependence on the action count and gaps: EReg⁡K=O!(Alog⁡(A/r)Δmax⁡Δmin⁡2log⁡2(AK)),\mathbb E\operatorname{Reg}_K =O\\!\left(A\log(A/r)\frac{\Delta_{\max}}{\Delta_{\min}^2}\log^2(AK)\right), where rr is the number of optimal actions and Δmin⁡,Δmax⁡\Delta_{\min},\Delta_{\max} are the smallest and largest positive reward gaps. For the two-action bandit with rewards (1,0)(1,0), direct substitution in the displayed bound gives approximately 9.83×105<K9.83\times10^5<K at K=106K=10^6 with the stated tuning. The polynomial specialization is stated in Corollary 3.2, equations (7)–(8), and the concrete budget calculation appears in Appendix F.4.

3. Polynomial constants in a multistage class, with a concrete budget.

To identify a non-trivial multistage class with polynomial constants, we apply the same Bellman-debt decomposition under a common-reference transition condition. This structure allows the downstream debt to be absorbed directly into the regret bound, yielding the result below. We then evaluate that result on a 17-state MDP to give a concrete non-trivial budget. Theorem 5.2 and the numerical example appear in Section 5, with the proof in Appendix K.

Consider a layered MDP with arbitrary horizon HH, NN state-stage blocks, two actions per state, deterministic rewards in [0,1][0,1], and a unique Bellman-optimal action at each state. Suppose each nonterminal layer h<Hh<H has a reference probability distribution νh+1\nu_{h+1} on the next-layer state set Sh+1\mathcal S_{h+1} such that (1−ε)νh+1(x)≤Ph(x∣s,a)≤(1+ε)νh+1(x),0≤ε<3−22.(1-\varepsilon)\nu_{h+1}(x)\le P_h(x\mid s,a)\le(1+\varepsilon)\nu_{h+1}(x), \qquad 0\le\varepsilon<3-2\sqrt2. The same reference distribution νh+1\nu_{h+1} is used for all states and actions in layer hh; it may vary across layers. Thus states and actions can change the transition distribution within a bounded relative distance of a common reference. Current action values may initially rank the Bellman-optimal action incorrectly.

Let κ=1−4ε/(1−ε)2\kappa=1-4\varepsilon/(1-\varepsilon)^2. For the original zero-initialized, return-to-go REINFORCE update, the same fixed step η=Δmin⁡/(8H2)\eta=\Delta_{\min}/(8H^2) at every state and episode gives EReg⁡K≤U(K):=Nηκ[1+log⁡(1+2ηHe2ηHK)].\mathbb E\operatorname{Reg}_K\le U(K):=\frac{N}{\eta\kappa} \left[1+\log\left(1+2\eta H e^{2\eta H}K\right)\right]. This is polynomial in N,H,Δmin⁡−1,κ−1N,H,\Delta_{\min}^{-1},\kappa^{-1} and logarithmic in KK. The proof combines the paper's Bellman-debt decomposition with a two-action local drift inequality: the common-reference condition bounds the aggregate downstream debt by a fixed fraction of the same-policy regret, allowing it to be absorbed after summing across stages. This supplies a structural theorem using the paper's proof tools, with no recursive readiness cost or minimum positive reference-mass parameter.

A concrete example has H=9H=9 and 17 states. Root rewards are (.035,0)(.035,0); each later layer has two state types with rewards (1,0)(1,0) and (.95,.91)(.95,.91). The two actions transition to the next types with probabilities (.55,.45)(.55,.45) and (.45,.55)(.45,.55). The common reference is νh+1=(.5,.5)\nu_{h+1}=(.5,.5) and ε=.1\varepsilon=.1. Here Δmin⁡=.04\Delta_{\min}=.04, and the current gaps at uniform initialization are −.008-.008 at the root and −.003-.003 at intermediate states of the second type. The example therefore includes simultaneous value-order reversals at multiple stages.

AuthorsOpenReview ↗

Response to Reviewer 2TmF (3/4)

Direct evaluation gives a nontrivial guarantee at about 1.08×1061.08\times10^6 episodes, or 9.70×1069.70\times10^6 environment steps. At K=107K=10^7 episodes, or 9×1079\times10^7 environment steps, U(K)≈5.61×106<K(V∗−Vmin⁡)≈4.08×107.U(K)\approx5.61\times10^6 < K(V^*-V^{\min})\approx4.08\times10^7. The bound is approximately 13.7513.75\\% of the instance-specific worst-policy linear bound, which is itself at most HKHK. The values V∗V^* and Vmin⁡V^{\min} are obtained by maximizing and minimizing the Bellman recursion.

W2. What the analysis adds to the known qualitative mechanisms

[W2] Limited insight beyond known qualitative mechanisms. The core qualitative conclusions—unbaselined REINFORCE has high variance, inaccurate downstream policies can give optimal upstream actions negative advantage, and occupancy suppression can recursively amplify delays—have been identified in prior work (Sutton et al., 1999; Robertson et al., 2025; Li et al., 2023). The present paper mainly re-derives these mechanisms in a more refined stochastic finite-horizon setting. While the technical execution is non-trivial, the paper does not articulate a new mechanism-level insight that follows from the analysis.

Thank you for asking us to clarify the mechanism-level insight. The qualitative mechanisms identified in your comment have been discussed in prior work. Our contribution is to make their coupling quantitative through two relations: how downstream learning errors affect upstream progress, and how upstream suppression constrains the learning opportunities delivered downstream.

1. The adverse effect of downstream errors can be charged to regret under the same current policy. Let eh+1π=Vh+1⋆−Vh+1πe_{h+1}^{\pi}=V_{h+1}^{\star}-V_{h+1}^{\pi}, let dhπ(s)d_h^\pi(s) be the state occupancy, and let Ah⋆(s)\mathcal A_h^\star(s) be the Bellman-optimal action set. The downstream-error term deducting from the aggregate optimal-logit drift satisfies Dh(π):=∑sdhπ(s)∑o∈Ah⋆(s)πh(o∣s),Pheh+1π(s,o)≤∑j=h+1HRj(π),D_h(\pi) := \sum_s d_h^\pi(s) \sum_{o\in\mathcal A_h^\star(s)} \pi_h(o\mid s)\\,P_h e_{h+1}^\pi(s,o) \le \sum_{j=h+1}^{H}\mathcal R_j(\pi), where Phe(s,o)=∑xPh(x∣s,o)e(x)P_he(s,o)=\sum_xP_h(x\mid s,o)e(x) and Rj(π)=∑sdjπ(s)∑aπj(a∣s)Δj(s,a)\mathcal R_j(\pi)=\sum_s d_j^\pi(s)\sum_a\pi_j(a\mid s)\Delta_j(s,a) is the stage-jj regret under that same policy. This holds for every current policy, including policies that give a Bellman-optimal upstream action negative advantage.

The misleading component of an upstream update therefore has a quantitative source within the regret decomposition itself. It can be accounted for across stages, including the period before downstream learning finishes. With a positive lower bound on optimal-action probability, geometric stage weights turn this accounting into a potential whose conditional drift controls total regret. Accounting for downstream error through the loss of the policy generating the update connects policy-gradient progress to cumulative loss. This same-policy debt relation and its proof are in Section 4.1, equations (12)–(13), and Appendix A.7; Lemma 4.1 gives the weighted-potential connection.

2. Suppressing an action requires accumulated use, which supplies downstream learning opportunities. For the original REINFORCE update with nonnegative returns, consider a phase beginning at episode tt and define the step-scaled predictable occupancies Ns(n)=η∑k=tn−1dhπk(s)N_s(n)=\eta\sum_{k=t}^{n-1}d_h^{\pi_k}(s) and Ns,a(n)=η∑k=tn−1dhπk(s)πk,h(a∣s)N_{s,a}(n)=\eta\sum_{k=t}^{n-1}d_h^{\pi_k}(s)\pi_{k,h}(a\mid s). If all relevant inverse logits e−θt,h(s,a)e^{-\theta_{t,h}(s,a)} are at most CC, the discrete analysis gives Ns,a(n)≥12AHlog⁡!(1+2HNs(n)(2C)AeAH).N_{s,a}(n) \ge \frac{1}{2AH} \log\\!\left( 1+\frac{2H N_s(n)}{(2C)^A e^{AH}} \right). The bound holds on the time-uniform comparison event, under ηH≤1\eta H\le1 and ηx≤1\eta x\le1, where x>0x>0 is the concentration parameter controlling the failure probability of the comparison event. It applies before the current action values are correctly ordered.

Thus, even an action that currently appears unattractive must receive increasing cumulative use as its parent state is visited. For a positive transition to a child state, the occupancy recursion propagates this use downstream. The logarithmic transmission bound quantifies how these opportunities can become progressively slower across stages. Combined with recovery and persistence, this yields a finite-time guarantee from initialization. Section 4.3, equations (14)–(16), presents cumulative action use and its mean-flow propagation; the revision supplies the discrete transmission bound in equation (17), proved in Lemma C.1. Section 4.2 and Appendix A connect the downstream entry conditions to local regret, and Theorem 3.1 separates the resulting waiting, entry-repair, and local-learning costs.

W3. Baselines and practically used variants

Comments on the paper

1 comment
AuthorsOpenReview ↗

What the rebuttal adds

We thank the reviewers for the discussion. Our responses provide four concrete additions.

1. The exponential bandit coefficient is removed. For H=1H=1, the revised bound is

O ⁣(Alog⁡(A/r)Δmax⁡Δmin⁡2log⁡2(AK)),O\!\left(A\log(A/r)\frac{\Delta_{\max}}{\Delta_{\min}^{2}}\log^{2}(AK)\right),

where rr is the number of optimal actions. The original exponential dependence on the gaps is therefore replaced by polynomial dependence. The certified learning rate also has the same gap and budget dependence as the cited bandit analysis, up to universal constants. This corrects a looseness of our original analysis, rather than claiming that bandits themselves require exponential learning time.

2. Polynomial constants are possible beyond bandits. We give a logarithmic-regret guarantee for a class of two-action multistage MDPs whose transition distributions remain sufficiently close to a common reference distribution. Its coefficient is polynomial in the number of state-stage blocks, horizon, inverse minimum gap, and inverse structural margin. Actions can change transitions, and optimal actions can initially appear worse. In our nine-stage, 17-state example, the bound beats the instance-specific worst-policy linear bound at about 1.081.08 million episodes; at 1010 million episodes, it is 13.75%13.75\% of that bound.

3. A multistage class where misleading action rankings do not require recursive waiting costs. Our analysis bounds the harmful contribution of downstream policy errors by downstream regret under the same current policy. For the structural class above, these error terms can be absorbed into the aggregate progress bound, eliminating the recursive waiting-time cost. For general MDPs, the cumulative-action-use argument instead quantifies how learning opportunities continue to reach downstream states while their values are still inaccurate.

4. Long learning delays occur in sampled REINFORCE. On the original tower-chain construction with H=12H=12, none of 288 runs reached root value 0.90.9 within 10910^9 episodes. By contrast, at H=4H=4, all 32 runs reached that threshold for each tested rate η≤0.03\eta\le 0.03. The experiment spans four horizons, nine fixed learning rates, and 32 seeds per setting. For η=10−4\eta=10^{-4} at H=12H=12, mean regret per episode remains approximately 0.250.25 at budgets 10710^7, 10810^8, and 10910^9. The full table is in our reply to Reviewer xZ6Q. This demonstrates substantial finite-budget difficulty in actual runs, without claiming asymptotic linear regret.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.