acceptodds
Under review as a conference paper at ICLR 2027

Sharp Safety and Critical Expectation Defects in Softmax Gradient Bandits

Abstract

Softmax gradient bandits adapt their exploration through updates driven by sampled rewards. Choosing the learning rate therefore requires understanding how these updates shape cumulative regret. Almost-sure convergence alone leaves this question unresolved, because rare trajectories can retain substantial expected loss even as typical trajectories learn the optimal arm. For IID arms with a unique optimum, a common predictable baseline, reward-residual bound , and gap floor , we identify the exact learning-rate ceiling for class-uniform logarithmic expected regret, including the endpoint. Below this ceiling, every fixed positive rate yields cumulative pulls to leading order for each suboptimal arm with gap , almost surely and in . Thus typical and expected allocations agree to leading order, with equal leading regret contributions from all suboptimal arms. At the ceiling, an explicit two-arm family with signed rewards retains logarithmic expected regret, but rare, prolonged excursions toward the suboptimal arm raise its leading coefficient above the typical-path value. A positive harmonic function quantifies this excess and its dependence on initialization. A uniform near-critical expansion for the same family connects the critical correction to polynomial expected regret above the ceiling.

Primary area:
learning theory
Keywords:
stochastic multi-armed bandits, softmax gradient bandits, policy gradient, learning-rate thresholds, regret analysis, critical phenomena

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_vQfLOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies the sampled softmax policy-gradient algorithm for finite stochastic bandits. It derives an implicit critical learning rate for a bounded residual class: below or at this threshold, expected regret is uniformly O(log T), while above it, a bounded IID instance can produce polynomial expected regret. Below the threshold, it also proves inverse-gap cumulative allocation. At the critical point, a specially constructed two-arm signed-reward family exhibits a gap between the almost-sure logarithmic regret coefficient and the expected coefficient, attributed to rare trajectories and non-uniform integrability.

Critical strengths

The endpoint analysis. The exponential-drift function, the multi-arm subset-potential argument, and the change-of-measure lower bound form a technically ambitious attempt to characterize the safety boundary rather than merely give a sufficient small-step condition. The paper also makes a useful conceptual distinction between almost-sure convergence, typical-path regret, and expected regret. The cumulative allocation result and the explicit critical harmonic correction could be valuable if the proof details and literature positioning hold up.

Critical weaknesses

The claims should nevertheless be narrowed. The “exact safe range” is exact only for a highly restricted class: fixed finite K, a positive known gap floor, bounded residuals, IID pull-indexed rewards, a common predictable scalar baseline, and no resets, projections, or arm-specific rates. The critical expectation defect is proved for one special two-arm reward family, not for the whole class. Several ingredients are imported from recent work, including the convergence theorem used in the converse, while the novelty relative to Baudry et al. and Jia–Ouyang needs a more explicit theorem-by-theorem comparison. The harmonic coefficient is defined implicitly and appears computationally expensive, and the experiments are mainly illustrative: the rare-event estimates have very low effective sample size, so they do not provide strong quantitative validation of the asymptotic constants.

The biggest problem is that there is no sufficient discussion on related works, and the contributions are not properly contextualized in the literature.

Questions for authors

N/A.

Reviewer_BS5rOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
1
Soundness
3
Read review
Paper summary

The paper studies stochastic gradient bandits, where the policy is softmax over policy parameters θt\theta_t. It provides characterization for the learning rate that allows logarithmic regret, showing that if learning rate is ≤O(ΔK)\le O(\frac{\Delta}{K}) for KK arms and minimum reward gap Δ\Delta, it achieves logarithmic expected regret and they also show that for any larger learning rate, the minimax regret becomes polynomial for large enough time horizon. When the learning rate is strictly smaller than the threshold, the paper also analyzes the convergence of number of pulls for each suboptimal arm. Lastly, for a specific family of two arm bandits, the paper characterizes the second order regret terms more tightly.

Critical strengths
  • The paper exactly characterizes the step size threshold necessary for logarithmic regret in stochastic gradient bandits, sharpening the analysis of [1] and solving its conjecture. The proofs builds on [1] but nontrivial arguments for sharper analysis are used.

[1] Baudry, Dorian, Emmeran Johnson, Simon Vary, Ciara Pike-Burke, and Patrick Rebeschini. "Does Stochastic Gradient really succeed for bandits?." Advances in Neural Information Processing Systems 38 (2026): 113544-113611.

Critical weaknesses
  • The step and horizon dependent characterization remains, the lower bound is not for a given time horizon, rather assuming constant step size for large enough horizon. As shown in [1], step size threshold scaling with 1/log⁡T1/ \log T is another sufficient condition for logarithmic regret, which can be a larger threshold depending on TT.
  • The current draft is hard to follow, and many axillary notations are used in the claims which are unnecessary. The text also contains many compressed terms which added explanation would help with its readability, Corollary 3 and Theorem 4 in particular. The final draft needs to be substantially improved in terms transitions between claims and giving more explanation.

[1] Lattimore, Tor. "A Lyapunov Analysis of Softmax Policy Gradient for Stochastic Bandits." arXiv preprint arXiv:2603.26547 (2026).

Questions for authors
  • If the step size sequence is decreasing and there is a finite step T0T_0 such that the step size after T0T_0 becomes less than the threshold ηc\eta_c. Can theorem 1 analysis be extend for such step size families? Have the authors consider the existence of a step size sequence that may achieve lower regret in terms of KK and Δ\Delta?
  • Can Theorem 4 be extended as a sharper regret upper bound for all K=2K=2 stochastic gradient bandits instead of a specific family?
Reviewer_8EWmOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
1
Soundness
2
Read review
Paper summary

Preliminary remarks

Note that the request to review this paper was received around midnight Nov 5th 2026 GMT, less than 48 hours before the Nov 5th 2026 AOE notification deadline. The paper is outside my core area of research, however I accepted the review request as I presume this must have been a last minute emergency review.

Although I have not done any external evalaution of AI use, the writing and presentation strongly suggest that the manuscript was fully written by an AI. This is consistent with the AI statement.

Due to the combination of the paper being outside my core area of expertise and very limited time was available, I have unfortunately not been able to verify the proofs. Given that an AI was likely to produce the proofs, the authors should have provided Lean certificates.

Contribution and significance

The paper considers softmax gradient bandit algorithms on a class of bandit problems with $K>$1 iid arms where arm 1 has maximum mean reward μ1\mu_1, and any other arm i>1i>1 has sub-optimal mean reward $\mu_i < \mu_1 - \Delta$ for some Δ>0\Delta > 0. Furthermore, it is assumed that ∣Y−bt∣≤M| Y- b_t | \le M a.s. for each tt, where btb_t is the chosen baseline of the algorithm and YY is the reward

The core contribution is to identify a critical learning rate ηc\eta_c, above which the algorithm ceases to have logarithmic regret. The critical rate is a function of the problem parameters MM and Δ\Delta. The critical rate ηc\eta_c is given implicitly in terms of the unique root of a function, but can be computed numerically.

To complement the theoretical analysis which is asymptotic in TT, the paper is complemented with experiments for finite TT in various settings (e.g., only two arms where the learning rate is near the critical ηc\eta_c). The experiments are consistent with the theory, and gives additional insights.

The paper leaves to future work how to choose the learning rate if the problem parameters MM and Δ\Delta are unknown.

Novelty

Lattimore (2026) showed O(log⁡(K)/η)O(\log(K)/\eta) regret in finite time TT for $\eta \le \tilde{O} (\Delta_{min}^2/\Delta_{max})$. This manuscript gives a more precise characterisation of the critical learning rate, but assuming asymptotically T→∞T\rightarrow\infty.

Soundness

As mentioned above, given the extremely short deadline and my unfamiliarity with the area, I have not been able to verify the technical soundness of the results.

However, it appears to me as the the proofs build on established techniques in the area, hence the methodological contribution is limited.

The proofs are highly compressed and provide too little detail. Most proofs are in the appendix, so the authors could have used more space. The central techniques used should be stated as lemmas so that the reader can check that the assumptions are satisfied (e.g., weighted Cesaro, clock lemma etc). Certain statements in proofs sounds as if they were written by an AI, e.g., "No expected-regret assumption or L1 upgrade was used."

Minor comments

The style of writing makes the paper challenging to read from an audience not already familiar with the area. In all parts, the paper lacks introductory sections that introduce the relevant technical aspects and cite general literature for further reading. E.g., terms such as "crossover scale" and proof techniques such as balanced clocks should be properly introduced. Please support the reader by citing relevant introductory literature.

Thm 1: rewrite "There is a finite constant depending on.." into "There is a finite constant C depending on..."

Critical strengths

The paper gives a more precise characterisation of the critical learning rate than what is currently available.

Critical weaknesses

The writing style is too condensed. See above.

Questions for authors

What can you say theoretically about regret for finite T in the bandit scenarios considered?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.