{"id":"48a5a09e-5e71-44f0-a2ac-478f6f68135b","arxiv_id":"2502.07141","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The softmax gradient bandit converges almost surely to the optimal action for any constant learning rate, removing the small-learning-rate restriction of prior work.","lead":"This paper proves that a simple stochastic gradient bandit algorithm finds the best arm even when the learning rate is huge and constant. The result removes a long-standing 'small steps' restriction and helps explain why large learning rates work in reinforcement learning practice.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 5 proves only sup π_i/π_j = ∞, yet Theorem 2 and Lemma 6 repeatedly invoke the stronger limit π(a*)/π(a^-) → ∞ for finitely sampled arms; that eventual-dominance step is unproved and load-bearing.","rationale":"The reader's weakest-assumption analysis identifies exactly the load-bearing issue: Lemma 5 is repeatedly used as if it proved eventual dominance of the probability ratio, when it only proves that the supremum of the ratio is infinite. I agree with that diagnosis. The paper is clearly written, the high-level strategy is plausible, and the simulations are supportive, but the proof of the central theorem is incomplete at a specific technical point. Lemma 6, which sandwiches the expected reward between the smallest and largest infinitely sampled rewards, is established via 'for sufficiently large t' bounds that require π_t(a^-)/π_t(j) to be eventually small; Lemma 5 does not imply this. Similarly, the recursive step in Theorem 2 that lifts π⊤_θt r above r(i2), then r(i3), etc., relies on Eq. (145), which is again an eventual bound justified only by Lemma 5. These are not cosmetic oversights: without the missing limit, the recursion can stall at a suboptimal threshold, and the proof that every infinitely sampled suboptimal arm's parameter tends to -∞ does not go through. I do not conclude the theorem is false; the result may be true and repairable with an additional argument, but the submitted proof does not establish it. Therefore the reader's CONDITIONAL verdict is appropriate, and no verdict change is needed.","tokens_in":28460,"tokens_out":5450,"duration_ms":52868,"concrete_test":"Re-derive Eq. (145) in Theorem 2 using only the stated Lemma 5. Concretely, attempt to prove that for a finitely sampled a^- and infinitely sampled a*, π_t(a*)/π_t(a^-) → ∞. If this limit is not provable from Lemma 5, exhibit a softmax probability sequence with N∞(i)=∞, N∞(j)<∞, sup_t π_t(i)/π_t(j)=∞ but liminf_t π_t(i)/π_t(j)=0, and show that on the low-ratio times the bound in Eq. (145) fails. Then check whether any earlier lemma (e.g., Lemmas 7-10 or the martingale concentration in Lemma 7) supplies the missing limit. If no such argument exists, Theorem 2 is unproved as written.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof gap is the transition from Lemma 5's sup-statements to the eventual inequalities used throughout §3.4. Lemma 5 (Appendix B) shows only that if N∞(i)=∞ and N∞(j)<∞ then sup_t π_t(i)/π_t(j)=∞; its proof is a contradiction based on summability and does not show the ratio tends to infinity. However, Lemma 6's sandwich bound r(i1) < π⊤_θt r < r(i2) is established using 'for all large enough t' bounds such as Eqs. (177)-(179), and Theorem 2's recursive step uses Eq. (143), 'According to Lemma 5... π_t(a*)/π_t(a^-) → ∞', for every finitely sampled a^-; Eq. (145) then bounds π_t(a^-)/π_t(a*) by a small constant for all large t. These are exactly the eventual-dominance statements that Lemma 5 does not provide. Since Lemma 6 and Eq. (145) are the tools that make π⊤_θt r climb above each r(i_k) in the recursive argument, the proof of the central claim is incomplete as written. A softmax sequence satisfying the lemma's hypothesis could have π_j ~ 2^{-t} and π_i large only on sparse blocks: then N∞(i)=∞, sup ratio=∞, but the ratio has liminf 0, so all eventual bounds fail. Nothing in Lemma 5 or the surrounding argument rules this out.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the softmax-parameterized stochastic gradient bandit algorithm (Algorithm 1) and claims that, for any constant learning rate eta > 0, the policy converges almost surely to the globally optimal one-hot policy. The main technical contributions are: (i) a proof that the algorithm cannot sample a single action forever (Lemma 2); (ii) a proof for the two-action case (Theorem 1); (iii) a recursive contradiction argument for general K using the set of infinitely sampled actions A_infty (Theorem 2); and (iv) an averaged suboptimality rate O(log T / T) (Theorem 3). The proof is built around a progress/noise decomposition and several supporting lemmas on sampling counts and softmax ratios. The paper also presents simulations with K = 4 arms for learning rates eta in {1,10,100,1000} showing convergence in most runs, with occasional long plateaus for large eta.","tokens_in":28774,"tokens_out":4830,"duration_ms":47799,"significance":"If the main theorem is correct, it is a significant result: it removes learning-rate tuning as a requirement for asymptotic optimality of a basic stochastic gradient bandit method, in a regime where standard smoothness-based and noise-control arguments do not apply. The proof strategy based on sampling counts and cumulative progress versus cumulative noise is promising, and the paper is largely self-contained: it introduces no fitted constants or tuned parameters, relies on standard concentration inequalities (Freedman's inequality and the extended Borel-Cantelli lemma), and the K = 2 proof (Theorem 1) is a clean application of the progress/noise framework. The simulations align qualitatively with the claimed convergence, while also honestly displaying long plateaus for large learning rates. However, the general-K proof currently has a load-bearing gap: Lemma 5 is too weak for the way it is used, and the gap propagates through Lemma 6 and Theorem 2. For this reason the central claim is not established as written, although the result may well be true and fixable.","major_comments":[{"comment":"Lemma 5 proves only that sup_t pi_t(i)/pi_t(j) = infinity when N_infty(i)=infinity and N_infty(j) infinity for every a^- in A^-(i2), and Eq. (145) bounds the reciprocal by a small constant for all sufficiently large t. These claims are not consequences of Lemma 5. A softmax sequence with pi_j ~ 2^{-t} and pi_i taking large values only on sparse blocks satisfies N_infinity(i)=infinity, N_infinity(j) 2 therefore does not follow from the written proof, even though the K = 2 argument does not use Lemma 5 and appears unaffected.","section":"Appendix B, Lemma 6 and Section 3.4"},{"comment":"Theorem 3 inherits the gap in Theorem 2. Its proof begins by invoking Theorem 2 to assert that pi_t(a*) -> 1, and Eq. (251) then uses this convergence to derive the O(log T / T) averaged bound. Because Theorem 2 is not established for general K without the missing eventual-dominance lemma, the rate result is likewise conditional on the same fix. I would treat Theorem 3 as a consequence to be revisited after the main convergence proof is repaired.","section":"Appendix C, Theorem 3"}],"minor_comments":[{"comment":"The notation eta in Theta(1) is nonstandard here: the statement and proofs consider an arbitrary positive constant learning rate, not a rate that is bounded both above and below. Using 'any constant eta > 0' directly would avoid confusion.","section":"Throughout"},{"comment":"The caption says 'Figures 2a and 2a are based on a single run'; the second reference should likely be '2b', and the text around Figure 2b should be checked for consistency.","section":"Appendix D, Figure 2 caption"},{"comment":"The proofs of Lemmas 8-10 handle the confidence event E1 in a somewhat informal way, writing that for a fixed omega there exists a delta such that omega is in E1. A rigorous treatment should choose a countable sequence delta_n down to 0 and apply a union bound so that the conclusion holds almost surely on the event N_infinity(a)=infinity; this is a presentation issue rather than a substantive gap.","section":"Appendix B, Lemmas 8-10"},{"comment":"The discussion of the trade-off between large and small learning rates is useful, but the claim that larger eta gives faster final-stage convergence is based only on the displayed runs; the paper does not provide a quantitative analysis of the plateau length or the final-stage rate. Adding a few summary statistics across seeds would strengthen the empirical section.","section":"Section 4"}],"recommendation":"major_revision","confidential_remarks":"The conjecture is plausible and the K = 2 proof plus the simulation evidence give some confidence, but the missing eventual-dominance lemma is genuinely load-bearing for the main theorem. This is not a grounds-for-rejection issue; it is a repair that the authors may be able to make by strengthening Lemma 5 or by replacing its uses with a different argument that rules out sparse-block behavior. I would encourage the editor to send the paper back for a major revision rather than reject it, and to ask the authors to state explicitly in the revised version which lemma supplies the 'for all sufficiently large t' ratio bounds used in Lemma 6 and Theorem 2."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Mei, Dai, Agarwal, Vaswani, Raj, Szepesvari, Schuurmans — arXiv 2502.07141. The result is exactly what the abstract promises: for any constant learning rate, softmax gradient bandits converge to the optimal action almost surely, removing the restrictive small-rate condition of their earlier paper [24]. If true, that's a genuinely interesting finding, and their new angle — analyzing action sampling rates instead of smoothness — is worth reading. The paper is also honest about its limitations.\n\nThe proof, however, has a load-bearing gap. Lemma 5 shows only that if N∞(i)=∞ and N∞(j)<∞, then sup_t π_t(i)/π_t(j)=∞. But Lemma 6 and the second part of Theorem 2 use the stronger statement that π_t(a*)/π_t(a^-) → ∞ as t→∞, or at least that the ratio is eventually above any fixed threshold. The proof of Lemma 5 is a contradiction based on summability; it cannot produce an eventual lower bound. A softmax sequence with π_j ~ 2^{-t} and π_i large only on sparse blocks would satisfy the lemma's hypothesis while having the ratio go to 0 along a subsequence. Nothing in the surrounding argument rules that out. The same unproved strengthening appears in the inequalities (177)-(179) and in the recursive step around (143)-(145). Since those steps are exactly what pushes the mean reward above each r(i_k), Theorem 2 is not established as written. This is not a cosmetic gap; it is the mechanism that makes the recursion work.\n\nThat said, the paper has real merit. Lemma 2 — the claim that at least two actions are sampled infinitely often for any constant learning rate — is new and the proof is clean. The K=2 case is convincing and uses the progress/noise decomposition in a way that is easy to follow. The simulations are consistent with the claim and the paper does not oversell them. The reliance on the authors' own prior [24] is for standard tools and a proof skeleton, not for the target result, so I do not consider the self-citation a problem.\n\nI think this deserves a serious referee: the question is important, the approach is promising, and the gap is possibly repairable. But the paper should not be accepted until the authors either prove the eventual-dominance step or replace it. I'd send it to review with clear instructions about Lemma 5.","headline":"A plausible and clearly written extension that would be a strong result, but the central proof invokes an eventual-dominance limit that Lemma 5 does not establish; as written, the main theorem is not proven.","tokens_in":29291,"tokens_out":2009,"would_cite":false,"duration_ms":18927,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q32","62L20"],"pacs":[],"model":"deepseek-v4-flash","headline":"Any constant learning rate drives stochastic gradient bandits to the optimal arm","keywords":["stochastic gradient bandits","softmax policy gradient","constant learning rate","multi-armed bandits","almost sure convergence","exploration-exploitation","REINFORCE","non-convex optimization"],"falsifier":"Run Algorithm 1 with $K=3$, distinct rewards, and a very large constant $\\eta$ while tracking the probability ratios between an action sampled infinitely often and one sampled finitely often; a path with positive probability on which this ratio has infinite supremum but does not converge to $\\infty$ would break Lemma 6's sandwich bound and the recursive step of Theorem 2. More directly, a counterexample to the claimed strengthening of Lemma 5—two softmax sequences with $N_\\infty(i)=\\infty$, $N_\\infty(j)<\\infty$, and $\\limsup \\pi_i/\\pi_j=\\infty$ but $\\liminf$ finite—would show the proof needs an additional argument.","tokens_in":28269,"feed_emoji":"🎰","tokens_out":6504,"duration_ms":56925,"temperature":0.7,"pith_summary":"The paper proves that the stochastic gradient bandit algorithm—the softmax policy-gradient update applied to a multi-armed bandit—converges almost surely to the globally optimal policy for every constant learning rate $\\eta>0$, not just small ones. Prior theory required decaying or sufficiently small step sizes to control gradient noise and smoothness. The new argument shows the algorithm always explores in a minimal sense: with probability one it never samples a single action forever, and at least two actions are sampled infinitely often. From there, the paper proves by contradiction that the optimal arm must be sampled infinitely often and that the probabilities of all sub-optimal arms decay to zero. Because the learning rate is the only hyperparameter of the algorithm, the result means no step-size tuning is needed for asymptotic optimality.","feed_headline":"Any constant learning rate leads gradient bandits to the optimal arm","feed_subtitle":"A proof that the simple softmax policy-gradient update explores on its own, so no step-size schedule is needed.","key_machinery":"The paper's central objects are the sampling counts $N_t(a)$ and the softmax probability ratios $\\pi_t(i)/\\pi_t(j)$. The extended Borel-Cantelli lemma ties $N_\\infty(a)=\\infty$ to divergence of $\\sum_t \\pi_t(a)$, letting the authors reason about exploration through probabilities alone. A ratio-explosion lemma (Lemma 5) is then combined with a 'sandwich' lemma (Lemma 6) showing the expected reward $\\pi_{\\theta_t}^\\top r$ eventually lies between the best and worst infinitely-sampled actions. The convergence argument itself uses a progress/noise decomposition: $\\theta_t(a)$ is written as cumulative expected updates plus a martingale noise term, with Freedman's inequality controlling the noise so that cumulative progress dominates.","core_discovery":"The central claim is Theorem 2: under Assumption 1 (distinct mean rewards), Algorithm 1 with any constant learning rate $\\eta>0$ satisfies $\\pi_{\\theta_t}(a^*)\\to 1$ almost surely, where $a^*$ is the best arm. The proof first establishes Lemma 2, that at least two actions are sampled infinitely often, so the algorithm cannot permanently commit to one arm no matter how large $\\eta$ is. It then rules out the possibility that the optimal action is sampled only finitely often using a contradiction based on the ratio of probabilities between an infinitely-sampled sub-optimal action and the optimal action. Once $N_\\infty(a^*)=\\infty$ is known, the argument shows recursively that the worst infinitely-sampled sub-optimal action, then the next, and so on, drift to $-\\infty$ in parameter space while $\\theta_t(a^*)\\to\\infty$, forcing every sub-optimal probability ratio to zero. The paper also derives an $O(\\log T/T)$ bound on average sub-optimality after a burn-in time.","pith_inferences":["Beyond the paper: the distinct-mean-rewards assumption may be removable, since the authors note that in the exact-gradient setting the set of initializations approaching tied softmax policies has measure zero.","Beyond the paper: the plateau behavior seen for large learning rates suggests a time-dependent schedule that starts small and increases the learning rate later could combine fast early progress with fast final convergence; the authors raise this as an open question.","Beyond the paper: if the asymptotic rate depends on $1/\\eta$ as the simulations suggest, then very large learning rates trade longer transient plateaus for sharper final convergence, implying a two-stage analysis is needed to predict actual performance."],"forward_implications":["Any constant learning rate is asymptotically safe: no schedule, decay, or problem-specific small step size is needed for the gradient bandit to reach the optimal policy almost surely.","Large constant learning rates do not cause the failure mode seen in natural or normalized policy gradient, where the algorithm can commit to a sub-optimal arm with positive probability.","After a finite burn-in time, the averaged sub-optimality gap decays as $O(\\log T/T)$ regardless of the constant learning rate used.","The probability of sampling sub-optimal arms tends to zero even though, by Lemma 2, at least one sub-optimal arm is sampled infinitely often."],"supporting_citations":[{"why":"Supplies the extended Borel-Cantelli lemma that equates sampling an action infinitely often with divergence of its cumulative softmax probability.","marker":"[5]"},{"why":"Freedman's inequality, cited through Theorem C.3 of [24], is used to bound the cumulative noise term in the progress-noise decomposition.","marker":"[10]"},{"why":"Characterizes the aggressive-update failure mode (committing forever to one action) that Lemma 2 rules out for the gradient bandit algorithm.","marker":"[20]"},{"why":"Proves global convergence for sufficiently small constant learning rates and supplies the progress/noise machinery the current proof adapts.","marker":"[24]"},{"why":"Establishes the exact-gradient softmax policy-gradient convergence rate that motivates the asymptotic comparison.","marker":"[23]"},{"why":"Defines the gradient bandit algorithm studied in the paper.","marker":"[31]"},{"why":"Provides the softmax policy-gradient theory that frames the problem setting and its optimality properties.","marker":"[1]"}],"fun_headline_variants":["Gradient bandits: any constant step size finds optimal arm","No step-size tuning: arbitrary constant rates still converge","Stochastic gradient bandits converge for any learning rate","Small steps not required: bandit gradient converges globally","Constant learning rates guarantee global bandit convergence"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof needs the property that when one action is sampled infinitely often and another only finitely often, the ratio of their probabilities eventually grows without bound, but the stated lemma proves only that the supremum of that ratio is infinite, not that the ratio itself tends to infinity.","fun_headline_variants_meta":{"raw":{"variants":["Gradient bandits: any constant step size finds optimal arm","No step-size tuning: arbitrary constant rates still converge","Stochastic gradient bandits converge for any learning rate","Small steps not required: bandit gradient converges globally","Constant learning rates guarantee global bandit convergence"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000236,"raw_usage":{"total_tokens":1452,"prompt_tokens":842,"completion_tokens":610,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":458,"completion_tokens_details":{"reasoning_tokens":534}},"tokens_in":458,"tokens_out":610,"duration_ms":5734,"temperature":1.0,"reasoning_tokens":534,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T13:41:35.349282+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Algorithm 1 with $K=3$, distinct rewards, and a very large constant $\\eta$ while tracking the probability ratios between an action sampled infinitely often and one sampled finitely often; a path with positive probability on which this ratio has infinite supremum but does not converge to $\\infty$ would break Lemma 6's sandwich bound and the recursive step of Theorem 2. More directly, a counterexample to the claimed strengthening of Lemma 5—two softmax sequences with $N_\\infty(i)=\\infty$, $N_\\infty(j)<\\infty$, and $\\limsup \\pi_i/\\pi_j=\\infty$ but $\\liminf$ finite—would show the proof needs an additional argument.","supporting_citations":[{"cited_title":"Probability","cited_arxiv_id":null,"evidence_quote":"Supplies the extended Borel-Cantelli lemma that equates sampling an action infinitely often with divergence of its cumulative softmax probability."},{"cited_title":"Freedman","cited_arxiv_id":null,"evidence_quote":"Freedman's inequality, cited through Theorem C.3 of [24], is used to bound the cumulative noise term in the progress-noise decomposition."},{"cited_title":"Understanding the effect of stochasticity in policy optimization","cited_arxiv_id":null,"evidence_quote":"Characterizes the aggressive-update failure mode (committing forever to one action) that Lemma 2 rules out for the gradient bandit algorithm."},{"cited_title":"Stochastic Gradient Succeeds for Bandits","cited_arxiv_id":"2402.17235","evidence_quote":"Proves global convergence for sufficiently small constant learning rates and supplies the progress/noise machinery the current proof adapts."},{"cited_title":"On the global convergence rates of softmax policy gradient methods","cited_arxiv_id":null,"evidence_quote":"Establishes the exact-gradient softmax policy-gradient convergence rate that motivates the asymptotic comparison."},{"cited_title":"Reinforcement Learning: An Introduction","cited_arxiv_id":null,"evidence_quote":"Defines the gradient bandit algorithm studied in the paper."},{"cited_title":"On the theory of policy gradient methods: Optimality, approximation, and distribution shift","cited_arxiv_id":null,"evidence_quote":"Provides the softmax policy-gradient theory that frames the problem setting and its optimality properties."}],"review_version":1}