- 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 regret bound with an instance-dependent learning rate and an 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
-
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 regret bound without explicit exploration or regularization, providing a theoretical understanding of the learning efficiency of REINFORCE.
-
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
- Although the regret bound is polylogarithmic in , 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 -action bandit (), the regret constant derived in Appendix F grows as for fixed , 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.
-
The 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 , potentially of order , 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.
-
Although the paper provides several lower bounds, they do not fully characterize the optimal regret under general learning-rate choices. The lower bound matches the upper bound when , 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 regret on a fixed MDP remains open. It also remains unclear whether the strong dependence on and 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
-
Can the instance-dependent constants be improved, particularly in the bandit setting, where existing analyses provide substantially tighter gap dependence?
-
Can the authors quantify the budget threshold required for the budget-only learning rate to enter the certified regime? For a simple concrete instance, how large must be before the regret bound becomes nontrivial?
-
Can an instance-dependent constant learning rate achieve regret on a fixed MDP? Is the strong dependence on and in the current upper bound inherent to REINFORCE or mainly due to the analysis?
-
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
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:
- The 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 , potentially of order , 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:
- Can the authors quantify the budget threshold required for the budget-only learning rate to enter the certified regime? For a simple concrete instance, how large must 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 and be the smallest and largest positive gaps within that block, and define Here is the maximum remaining return; is the allowed downstream value error, which is zero at the terminal stage. Accordingly, is the guaranteed positive action-value separation after allowing for that error, and bounds the corresponding value spread. These are the quantities in equation (4). The common step is required to satisfy Here is the number of logits and is the stage- state set.
For the budget-only choice , set and . Certification is equivalent to Solving this inequality gives the following sufficient threshold: 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 is nontrivial at .
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 , state-stage blocks, two actions per state, deterministic rewards in , and a unique Bellman-optimal action at each state. Suppose each nonterminal layer has a reference probability distribution on the next-layer state set , with and , such that Here is a probability vector, and is its mass at next-layer state . The same vector is used for all states and actions in layer ; 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.
Response to Reviewer xZ6Q (3/4)
Let be the minimum positive Bellman gap and . For the original zero-initialized, return-to-go REINFORCE update, the same fixed step at every state and episode gives This is polynomial in and logarithmic in . 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 and 17 states. Root rewards are ; each later layer has two state types with rewards and . The two actions transition to the next types with probabilities and . The common reference is and , so each coordinate of either transition row lies between and . Here , and the current gaps at uniform initialization are at the root and 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 episodes, or environment steps. At episodes, or environment steps, The bound is approximately of the instance-specific worst-policy linear bound, which is itself at most . The values and 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:
- Although the paper provides several lower bounds, they do not fully characterize the optimal regret under general learning-rate choices. The lower bound matches the upper bound when , 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 regret on a fixed MDP remains open. It also remains unclear whether the strong dependence on and in the upper bound is inherent to REINFORCE or an artifact of the analysis.
Question:
- Can an instance-dependent constant learning rate achieve regret on a fixed MDP? Is the strong dependence on and 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 satisfies for constants that may depend on the fixed step but not on the budget . The MDP is independent of the choice of .
The instance offers a safe reward of at the first decision, a safe reward of at the second, and a terminal choice between rewards and . 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 , 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.
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:
Question:
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 through e−θ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 below zero, where o is an optimal action and i 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=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 r is the number of optimal actions and Δmax is the largest positive reward gap, a=2ΔmaxΔmin,b=log(1+AK(eη−1)). The common step η, fixed throughout the run, satisfies 0<η≤log(64A2K)minΔmin/5888,Δmin2/(32Δmax). Choosing the largest allowed step yields ERegK=O!(Alog(A/r)Δmin2Δmaxlog2(AK)). Thus the former exp(Θ(Δmin−A)) coefficient is replaced by polynomial action-count and gap dependence. Lattimore's Theorem 1 allows η≤Δmin2/[120Δmaxlog(AK)] and gives O(AlogAlogK/η) regret. Since Δmin≤Δmax, our step ceiling has the same gap and logarithmic-budget order up to universal numerical factors. For a unique optimal action (r=1), in Lattimore's regime K≥A, the resulting regret bounds also have the same action-count, gap, and logarithmic-budget orders. The revised bound displays the additional dependence on r when there are multiple optimal actions. This bound and its step-size condition appear in Corollary 3.2, equations (7)–(8).