Small steps no more: Global convergence of stochastic gradient bandits for arbitrary learning rates

Authors: jincheng  mei
bo  dai
alekh  agarwal
sharan  vaswani
anant  raj
csaba  szepesvári
dale  schuurmans
google  deepmind
google  research
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 18:37:16

Abstract: We provide a new understanding of the stochastic gradient bandit algorithm by showing that it converges to a globally optimal policy almost surely using \emph{any} constant learning rate. This result demonstrates that the stochastic gradient algorithm continues to balance exploration and exploitation appropriately even in scenarios where standard smoothness and noise control assumptions break down. The proofs are based on novel findings about action sampling rates and the relationship between cumulative progress and noise, and extend the current understanding of how simple stochastic gradient methods behave in bandit settings.

Main paper: 
 introduction: 
 The stochastic gradient method has been ubiquitous in the field of machine learning for decades [4] . When applied to reinforcement learning (RL), a representative instantiation of stochastic gradient is the well known policy gradient [32] (or REINFORCE [34] ) algorithm, where in each iteration an online sample is gathered using the current policy, from which a gradient estimate is obtained to conduct parameter updates. In the simplest setting of a stochastic bandit problem [16] , where decisions matter only for one step, the REINFORCE policy gradient method becomes equivalent to the stochastic gradient bandit algorithm [31, Section 2.8] . Compared to other statistical methods, such as the upper confidence bound algorithm (UCB, [14, 3] ), and Thompson sampling (TS, [33, 2] ), the stochastic gradient bandit algorithm is conceptually simpler and more computationally efficient, as it does not calculate exploration bonuses nor posterior distributions. Moreover, the stochastic gradient method is highly scalable and naturally applicable to large scale neural networks [29, 30] .However, unlike UCB or TS, the stochastic gradient bandit algorithm does not have an equivalently well established and comprehensive theoretical footing. Given its pervasive success and widespread application in RL [30] and fine-tuning for large language models [26, 27] ), it remains an important question to understand the success of stochastic gradient based algorithms in bandit-like settings, not only to bridge the gap between theory and practice, but also to identify more effective and robust variants. In this paper, we make a significant contribution to the theoretical understanding of the stochastic gradient bandit algorithm, bringing its justification closer to that of other less scalable but theoretically well established methods. In particular, we establish the surprising result that:For any constant learning rate η > 0, the stochastic gradient bandit algorithm is guaranteed to converge to the globally optimal policy almost surely.Since learning rate is the only tuning parameter in the stochastic gradient bandit algorithm, this result offers a remarkable robustness for the method, that it converges to a near optimal policy, irrespective of the value of this hyperparameter! Analysis of this algorithm is challenging because it requires techniques for simultaneously handling non-convex optimization, stochastic approximation, and the exploration-exploitation trade-off. Prior theoretical work on the stochastic gradient algorithm has primarily focused on non-convex convex optimization and stochastic approximation, but understanding the simultaneous effect on exploration has been largely lacking.Recently, significant progress has been made in establishing global convergence results for policy gradient (PG) methods. For example, it has been shown that using exact gradients, Softmax PG converges to a globally optimal policy asymptotically as the number of iterations t goes to infinity [1] . Subsequent work has demonstrated that the asymptotic rate of convergence is O(1/t) [23] , albeit with problem and initialization dependent constants [22, 17] . The rate and constant dependence in the true gradient setting have been improved via several techniques, including entropy regularization [23] , normalization [21] , and using natural gradient (mirror descent) [1, 6, 15] .Unfortunately, in the online stochastic setting, where the policy gradient has to be estimated using the current policy to collect samples, these accelerated methods all obtain worse asymptotic results than the standard Softmax PG [20] , failing to converge to a global optimum without careful design choices [19] . Yet in the same setting, standard Softmax PG has been shown to succeed in its simplest form, provided only that a sufficiently small learning constant rate η ∈ Θ(1) is used [24] .For stochastic gradient based methods, decaying or sufficiently small learning rates are used by almost all current approaches, motivated by classical convergence analyses from stochastic optimization [28, 12, 39, 38, 9, 37, 36, 24, 8] . Stationary point convergence is guaranteed for learning rates sufficiently small with respect to the smoothness of the objective function, while also decaying to zero at a precise rate if noise in the gradient estimator persists. In addition to appropriate learning rate control, many other techniques have been developed to control the effects of gradient noise, including regularization [38, 9] , variance reduction [37] , and carefully considering growth conditions [36, 24] .The technical challenges we face in the current study can be understood in the following aspects:(1) Using an arbitrarily large constant learning rate for online stochastic gradient optimization immediately renders the smoothness and noise control techniques mentioned above inapplicable.(2) With any constant learning rate η > 0, the question of whether oscillation or convergence will ultimately occur needs to be addressed before even considering whether any convergence is to a global optimum. This additional level of complexity arises because the optimization objective is not necessarily improved monotonically in expectation. Finally, (3) The gradient bandit algorithm does not use any exploration bonus, which means that new techniques are required to demonstrate that it adequately balances the exploration-exploitation trade-off.In this paper, we resolve the above difficulties by uncovering intriguing exploration properties of stochastic gradient when using any constant learning rate. In particular, we establish the following.(i) In the stochastic online setting, with probability 1, the stochastic gradient bandit algorithm will not keep sampling any single action forever, implying that it will exhibit a minimal form of exploration without any further modification. This asymptotic event (as t → ∞) happens with probability 1 and holds for any constant learning rate η > 0. (ii) This result can then be leveraged to show that, as a consequence, given any constant learning rate, the stochastic gradient bandit algorithms will converge to the globally optimal policy as t → ∞, with probability 1. That is, the probability of sub-optimal actions decays to 0, even though some of them are taken infinitely often asymptotically. 
setting and background: 
 We consider the stochastic multi-armed bandit problem [16] , specified by K actions and a true mean reward vector r ∈ R K , where for each action a ∈ [K] := {1, 2, . . . , K},EQUATIONwhere R max > 0 is the reward range, µ is a finite measure over [-R max , R max ], and P a (x) ≥ 0 is the probability density function with respect to µ. We use R a to denote the reward distribution for Algorithm 1 Gradient bandit algorithm (without baselines)Input: initial parameters θ 1 ∈ R K , learning rate η > 0. Output: policies π θt = softmax(θ t ). while t ≥ 1 do Sample an action a t ∼ π θt (•) and observe reward R t (a t ) ∼ P at . for all a ∈ [K] do if a = a t then θ t+1 (a) ← θ t (a) + η • (1 -π θt (a)) • R t (a t ). else θ t+1 (a) ← θ t (a) -η • π θt (a) • R t (a t). end if end for end while action a defined by the density P a and base measure µ. The goal is to find a policy π θ ∈ [0, 1] K to achieve high expected reward,EQUATIONwhere π θ is parameterized by θ ∈ R K .The gradient bandit algorithm. A natural idea to optimize Eq. ( 2) is to use stochastic gradient ascent, which is shown in Algorithm 1 and known as the gradient bandit algorithm [31, Section 2.8] .In Algorithm 1, in each iteration t ≥ 1, the probability of pulling arm a ∈ [K] is given asEQUATIONwhere θ t ∈ R K is the parameter vector to be updated. The following proposition shows that Algorithm 1 is an instance of stochastic gradient ascent with an unbiased gradient estimator [31, 24] . Proposition 1 (Proposition 2.3 of [24] ). Algorithm 1 is equivalent to the following update,EQUATIONwhereE t d π ⊤ θ t rt dθt = d π ⊤ θ t rdθt , and E t [•] is defined with respect to randomness from on-policy sampling a t ∼ π θt (•) and reward sampling R t (a t ) ∼ P at . The Jacobian of θ → π θ := softmax(θ) isd π θ dθ ⊤ = diag(π θ ) -π θ π ⊤ θ ∈ R K×K , and rt (a) := I{at=a} π θ t (a) • R t (a) for all a ∈ [K]is the importance sampling (IS) estimator, and we set R t (a) = 0 for all a ̸ = a t .Known results on the convergence of the gradient bandit algorithm. Since Eq. ( 2) corresponds to a smooth non-concave maximization problem over θ ∈ R K [23] , using Algorithm 1 with decaying learning rates is sufficient to guarantee convergence to a stationary point [28, 25, 12, 39] . However, this is insufficient to ensure the globally optimal solution of Eq. ( 2) is reached, since there exist multiple stationary points. More recently, guarantees of convergence to a globally optimal policy have been developed for PG methods in the true gradient setting [1, 23] , where the algorithm has access to exact mean rewards. These results were later extended to achieve global convergence guarantees (almost surely) in the stochastic setting [38, 9, 37, 36, 24, 18] . However, these extended results have required decaying or sufficiently small learning rates, motivated by exploiting smoothness and combating the inherent noise in stochastic gradients. Despite these previous assumptions, there exists empirical and theoretical evidence that using a large learning rate in the stochastic gradient bandit algorithm is a viable option. For example, it has been observed that softmax policies learn even with extremely large learning rates such as 2 14 [11] . For logistic regression on linearly separable data, the objective has an exponential tail and the minimizer is unbounded, yet it has been shown that gradient descent with iteration dependent learning rate η ∈ Θ(t) achieves accelerated O(1/t 2 ) convergence [35] . Though the objective in Eq. ( 2) has similar properties, unlike logistic regression, the problem we are considering is non-concave, so the same techniques cannot be directly applied. The most related results are from [24] , which proved that with a small problem specific constant learning rate, Algorithm 1 achieves convergence to a globally optimal policy almost surely. However, as mentioned, the learning rate choices in [24] rely on assumptions of (non-uniform) smoothness and noise growth conditions (their Lemmas 4.2, 4.3, and 4.6), which cannot be directly applied here for a large learning rate.Consequently, the use of large learning rates appear to render existing results and techniques inapplicable. Furthermore, with a large constant learning rate, it is unclear whether Algorithm 1 will converge to any stationary point, or the iterates will keep oscillating. If the algorithm does converge, it is also not clear what effect large step-sizes have on exploration, and whether the algorithm will converge to the optimal arm in such cases. Resolving these questions requires new results that characterize the behavior of Algorithm 1, since the classical optimization and stochastic approximation convergence theories are no longer applicable, as explained. 
asymptotic global convergence of gradient bandit algorithm: 
 We have seen that solving the non-concave maximization problem Eq. ( 2) using Algorithm 1 with any constant (potentially large) learning rate requires ideas beyond classical optimization theory. Here, we take a different perspective to investigate how Algorithm 1 samples actions. For analysis, we make the following assumption about the reward distribution. Assumption 1 (True mean reward has no ties). For all i, j ∈ [K], if i ̸ = j, then r(i) ̸ = r(j).Removing Assumption 1 remains an open question for future work, while we believe that Algorithm 1 works without Assumption 1. One piece of evidence to support this conjecture is that even in the exact gradient setting, the set of initializations where Softmax PG approaches non-strict one-hot policies has zero measure.It has been observed that several accelerated PG methods in the true gradient setting, including natural PG [13, 1] and normalized PG [21] , obtain worse results than standard softmax PG if combined with online sampling a t ∼ π θt (•) using constant learning rates [20] . The failure mode in these cases is that the update is too aggressive and commits to a sub-optimal arm without sufficiently exploring all arms. This results in a non-trivial probability of sampling one action forever, i.e., there exists a potentially sub-optimal action a ∈ [K], such that with some constant probability, a t = a for all t ≥ 1. Such an outcome implies that π θt (a) → 1 as t → ∞ [20, Theorem 3] . Since a ∈ [K] could be a sub-optimal action with r(a) < r(a * ) = max a∈[K] r(a), this results in a lack of exploration, and consequently, methods such as natural PG and normalized PG are not guaranteed to converge to the optimal action a * := arg max a∈[K] r(a) with probability 1.Our first key finding is that Algorithm 1 does not keep sampling one action forever, no matter how large the constant learning rate is. This property avoids the problem of a lack of exploration, in the sense that Algorithm 1 will at least explore more than one action infinitely often. At first glance, this might not seem like a strong property, since the algorithm might somehow explore only sub-optimal actions forever. However, we will argue below that this property coupled with additional arguments is sufficient to guarantee convergence to the globally optimal policy.Let us now formally prove the above property. By Algorithm 1, for all a ∈ [K], for all t ≥ 1,EQUATIONWe define N t (a) as the number of times action a ∈ [K] is sampled up to iteration t ≥ 1, i.e.,EQUATIONand its asymptotic limit N ∞ (a) := lim t→∞ N t (a), which could possibly be infinity. For all a ∈ [K],we have either N ∞ (a) = ∞ or N ∞ (a) < ∞, meaning that a ∈ [K] is sampled infinitely often or only finitely many times asymptotically. First, we prove the following Lemma 1, which shows that if an action a ∈ [K] is sampled only finitely many times as t → ∞, then the parameter corresponding to action a is also finite, i.e., sup t≥1 |θ t (a)| < ∞. Lemma 1 will be used multiple times in the subsequent convergence arguments.Proof sketch. Since we assume action a ∈ [K] is sampled finitely many times, the update given in the case depicted by Eq. ( 5) happens finitely many times. Each update is bounded since the sampled reward is in [-R max , R max ] by Eq. ( 1), and the learning rate is a constant, i.e., η ∈ Θ(1).In Algorithm 1, θ t (a) is still updated even when a t ̸ = a, with the corresponding update given by the case depicted by Eq. ( 6). Therefore, whether θ t (a) is bounded depends on the cumulative probability t s=1 π θs (a) being summable as t → ∞. According to the extended Borel-Cantelli lemma (Lemma 3), we have, almost surely,EQUATIONwhich implies (by taking complements) that t≥1 π θt (a) < ∞ if and only if N ∞ (a) < ∞. Therefore, if a ∈ [K] is sampled finitely often, θ t (a) will be updated in a bounded manner (using Eqs. ( 5) and ( 6)) as t → ∞, hence establishing Lemma 1. Detailed proofs for this lemma, as well as for all other results in this paper can be found in the appendix.Given Lemma 1, we can then establish the above-mentioned finding about the exploration effect of Algorithm 1 in Lemma 2. Lemma 2 (Avoiding a lack of exploration). Using Algorithm 1 with any η ∈ Θ(1), there exists at least a pair of distinct actions i, j ∈ [K] and i ̸ = j, such that, almost surely,EQUATION)Proof sketch. The argument for the existence of one such action is straightforward, since by the pigeonhole principle, if there are finitely many actions, i.e., K < ∞, there must be at least one action i ∈ [K] that is sampled infinitely often as t → ∞.The argument for the existence of a second such action is by contradiction. Suppose that all the other actions j ∈ [K] with j ̸ = i are sampled only finitely many times as t → ∞. According to Lemma 1, their corresponding parameters must remain finite, i.e., sup t≥1 |θ t (j)| < ∞ for all j ∈ [K] with j ̸ = i. Now consider θ t (i). By assumption, the second update case for this parameter, Eq. ( 6), happens only finitely often, since Eq. ( 6) can only occur when a t ̸ = i. Therefore, the key question is whether the cumulative probability t s=1 (1 -π θs (i)) involved in the first case of the update, Eq. ( 5), is summable as t → ∞. Note thatt s=1 (1 -π θs (i)) = t s=1j̸ =i π θs (j), which is indeed summable as t → ∞, by the assumption and Eq. ( 9). This implies that action i, which is sampled infinitely often, achieves a parameter magnitude, sup t≥1 |θ t (i)| < ∞, that remains bounded as t → ∞. Using the softmax parameterization Eq. (3) in the above argument, we conclude that for all a ∈ [K], inf t≥1 π θt (a) > 0, i.e., every action's probability remains bounded away from zero, and hence is not summable. Using Eq. ( 9), this implies that every action is sampled infinitely often, which contradicts the assumption that only action i is sampled infinitely often as t → ∞.Discussion. Lemma 2 implies that Algorithm 1 is not an aggressive method in the sense of [20] , no matter how large the learning rate is, as long as it is constant, i.e., η ∈ Θ(1). According to [20, Theorem 7] , even if we fix the sampling in Algorithm 1 to a sub-optimal action a ∈ [K] forever, i.e., a t = a for all t ≥ 1, its probability will not approach 1 faster than O(1/t), i.e., 1 -π θt (a) ∈ Ω(1/t). This means that there must be at least one another action a ′ ∈ [K] with a ′ ̸ = a, such that a ′ will also be sampled infinitely often. A more intuitive explanation is that the (1 -π θt (a)) term in Eq. ( 5) will be near 0, which slows the speed of committing to a deterministic policy on a whenever π θt (a) is close to 1, which encourages exploration. Such natural exploratory behavior arises in Algorithm 1 because of the softmax Jacobian diag(π θ ) -π θ π ⊤ θ in the update shown in Proposition 1, which determines the growth order of θ t (a) for all a ∈ [K] as t → ∞, making the effect of a constant learning rate η ∈ Θ(1) asymptotically inconsequential.We now consider the simplest case, where we have only two possible actions. According to Lemma 2, each of the two actions must be sampled infinitely often as t → ∞. We now illustrate the second key result, that for both actions a ∈ [K], the random sequence {θ t (a)} t≥1 follows the direction of the expected gradient for sufficiently large t ≥ 1 almost surely. The proof uses a technique that has been previously used in [19, 24] for small learning rates, but here we observe that the same technique continues to work for Algorithm 1 no matter how large the learning rate is, as long as η ∈ Θ(1). Theorem 1. Let K = 2 and r(1) > r (2) . Using Algorithm 1 with any η ∈ Θ(1), we have, almost surely, π θt (a * ) → 1 as t → ∞, where a * := arg max a∈[K] r(a) (equal to Action 1 in this case).Proof sketch. According to Lemma 2, N ∞ (1) = N ∞ (2) = ∞.Denote the the reward gap as ∆ := r(a * ) -max a̸ =a * r(a) > 0, which becomes ∆ = r(1) -r(2) for two actions. Since the stochastic gradient is unbiased (Proposition 1), we have, for all t ≥ 1 (detailed calculations omitted),EQUATIONA similar calculation shows that,EQUATIONwhich means that θ t (a * ) is monotonically increasing in expectation and θ t (2) is monotonically decreasing in expectation. In other words, {θ t (a * )} t≥1 is a sub-martingale, while {θ t (2)} t≥1 is a super-martingale. However, since θ t ∈ R K is unbounded, Doob's martingale convergence results cannot be directly applied, so we pursue a different argument. Following [19, 24] , given an action a ∈ [K], we define P t (a) := E t [θ t+1 (a)] -θ t (a) as the "progress", and define W t (a) := θ t (a) -E t-1 [θ t (a)] as the "noise", where θ t (a) = W t (a) + P t-1 (a) + θ t-1 (a). By recursion we can determine that,EQUATIONi.e., θ t (a) is the result of "cumulative progress" and "cumulative noise". According to [24, Theorem C.3] , the cumulative noise term can be bounded by using martingale concentration, where the order of the corresponding confidence interval is smaller than the order of the cumulative progress. Therefore, the summation will always be determined by the cumulative progress as t → ∞. According to the calculations in Eqs. ( 12) and ( 13), we have P t (a * ) > 0 and P t (2) < 0, both of which are not summable. As a result, θ t (a * ) → ∞ and θ t (2) → -∞ as t → ∞, which implies thatπ θ t (a * ) π θ t (2) = exp{θ t (a * ) -θ t (a)} → ∞, hence π θt (a * ) → 1 as t → ∞.The illustrative two-action case shows that if π ⊤ θt r ∈ (r(2), r(a * )) and if both actions are sampled infinitely often, then we have, almost surely θ t (a * ) → ∞ and θ t (2) → -∞ as t → ∞. However, the question at the beginning of Section 3.2 remains: when K > 2, if the two actions sampled infinitely often in Lemma 2 are both sub-optimal, will that result in a similar failure mode to the one described in Section 3.1? The answer is no, which follows from our third key finding, which is based on another contradiction-based argument that establishes almost sure convergence to a globally optimal policy in the general K > 2 case. Theorem 2. Given K ≥ 2, using Algorithm 1 with any η ∈ Θ(1), we have, almost surely, π θt (a * ) → 1 as t → ∞, where a * = arg max a∈[K] r(a) is the optimal action. Proof sketch. We consider two cases: N ∞ (a * ) < ∞ and N ∞ (a * ) = ∞, corresponding to whether the optimal action is sampled finitely or infinitely often as t → ∞. We argue that the first case (N ∞ (a * ) < ∞) is impossible, while for the second case (N ∞ (a * ) = ∞) we prove that θ t (a * ) -θ t (a) → ∞ for all a ∈ [K] with r(a) < r(a * ), which implies π θt (a * ) → 1 as t → ∞.First case. Suppose that N ∞ (a * ) < ∞. We argue that this is impossible via contradiction. Given the assumption and Lemma 2 we know there must be at least two other sub-optimal actions i 1 , i2 ∈ [K], i 1 ̸ = i 2 , such that N ∞ (i 1 ) = N ∞ (i 2 ) = ∞.In particular, let i 1 = arg min a∈[K],N∞(a)=∞ r(a) and i 2 = arg max a∈[K],N∞(a)=∞ r(a), hence r(i 1 ) < r(i 2 ) < r(a * ). By Lemma 6 (see Appendix) we will also have r(i 1 ) < π ⊤ θt r < r(i 2 ) for sufficiently large t ≥ 1 , which implies for action i 1 ,EQUATIONfor sufficiently large t ≥ 1, which further implies that sup t≥1 θ t (i 1 ) < ∞. Meanwhile, for the optimal action a * , the assumption and Lemma 1 imply that inf t≥1 θ t (a * ) > -∞. Combining these two observations gives,EQUATION)On the other hand, since N ∞ (i 1 ) = ∞ and N ∞ (a * ) < ∞ (by assumption), we then have sup t≥1 exp{θ t (i 1 ) -θ t (a * )} = ∞ by Lemma 5 (see Appendix), which contradicts Eq. ( 16).Second case. Suppose that N ∞ (a * ) = ∞. We will argue that π θt (a * ) → 1 as t → ∞ almost surely. First, according to Lemma 2, there exists at least one sub-optimal action i1 ∈ [K], i 1 ̸ = a * , such that N ∞ (i 1 ) = ∞. Let i 1 = arg min a∈[K],N∞(a)=∞ r(a). By Lemma 6 and the definition of a * , we have r(i 1 ) < π ⊤ θt r < r(a * ) for all sufficiently large t ≥ 1. Since N ∞ (i 1 ) = ∞, using similar calculations to Eqs. ( 13) and ( 14) in Theorem 1, we have, θ t (i 1 ) → -∞ as t → ∞. We also have,inf t≥1 θ t (a * ) > -∞ as t → ∞. Hence, π θ t (a * ) π θ t (i1) = exp{θ t (a * ) -θ t (i 1 )} → ∞ as t → ∞. Define A ∞ := {a ∈ [K] | N ∞ (a) = ∞}as the set of actions that are sampled infinitely often, and note that |A ∞ | ≥ 2 by Lemma 2. Sort the action indices in A ∞ according to their expected reward values in descending order, i.e., r(aEQUATION)Assumption 1 is used here to prevent two arms from having the same reward and thus guarantee the inequalities are strict in Eq. (17) . Next, using similar calculations as in Lemma 6, we have,EQUATIONwhereA -(i 2 ) := {a -∈ [K] : r(a -) < r(i 2 )} is the set of actions that have lower mean reward than i 2 ∈ [K], and note that i 1 ∈ A -(i 2 ). Using the above definitions, we can conclude that i 1 is the only arm in A -(i 2 ) that has been sampled infinitely often. According to Lemma 5, for all a -∈ A -(i 2 ) with a -̸ = i 1 , we have, 17)). Therefore, for all sufficiently large t, the probability ratio in Eq. ( 18)π θ t (a * ) π θ t (a -) → ∞ as t → ∞, since N ∞ (a * ) = ∞ (by assumption) and N ∞ (a -) < ∞ (by Eq. (EQUATION)We have thus shown that π ⊤ θt r > r(i 2 ). Recall that we had previously proved that π ⊤ θt r > r(i 1 ). Hence, we will apply this argument recursively: after this point, i 2 ∈ [K] will become the new "i 1 ∈ [K]", and a similar inequality to Eq. (13) will then hold for i 2 ∈ [K] from similar calculations to Eqs. ( 13) and ( 14) in Theorem 1, establishing θ t (i 2 ) → -∞ as t → ∞. This will imply that for all sufficiently large t ≥ 1,π ⊤ θt r -r(i 3 ) > 0.5 • π θt (a * ) • r(a * ) -r(i 3 ) > 0.(20) Continuing the recursive argument, we can conclude for all actions a ∈ A ∞ with a ̸ = a * that π θ t (a * ) π θ t (a) → ∞ as t → ∞. Meanwhile, for all actions a ̸ ∈ A ∞ , Lemma 5 also shows thatπ θ t (a * ) π θ t (a) → ∞ as t → ∞.Combining these two results yields the conclusion that for all sub-optimal actions a ∈ [K] with r(a) < r(a * ) we have π θ t (a * ) π θ t (a) → ∞ as t → ∞, which implies π θt (a * ) → 1 as t → ∞. Thus, we have established almost sure convergence to the globally optimal policy. Discussion. Lemma 2 is important to prove that the optimal arm will be sampled infinitely often. In particular, Lemma 2 guarantees |A ∞ | ≥ 2 and the existence of i 1 in Eq. (15) , which can then be used to construct the contradiction in Eq. ( 16). Without Lemma 2, |A ∞ | might be equal to 1 and the failure mode in Section 3.1 can occur, resulting in Algorithm 1 not sampling the optimal action infinitely often as t → ∞. 
simulation study: 
 To validate and enhance the theoretical findings, we ran experiments with a four action bandit environment (K = 4) with a true mean reward vector of r = (0.2, 0.05, -0.1, -0.4) ⊤ ∈ R 4 . The reward distribution P a for arm 1 ≤ a ≤ 4 is Gaussian, centered at r(a) and with a standard deviation of 0.1. The environment is chosen to illustrate various phenomenon, which we discuss after presenting the results. The algorithm is Algorithm 1 withθ 1 = 0 ∈ R K .For comparison, assuming that the random rewards belong to the [-1, 1] interval, the only result for the stochastic gradient bandit algorithm [24, Lemma 4.6 ] that allowed a constant learning rate required that the learning rate be less thanη c = ∆ 2 40•K 3/2 •R 3 max = 9128000 ≈ 0.00007, where we used ∆ = 0.15, K = 4, and R max = 1. While technically, the result does not apply to our case where the reward distributions have unbounded support, the probability of the reward landing outside of [-1, 1] is in the order of 10 -9 . Choosing R max to be larger, this probability falls extremely quickly, which suggests that the above threshold is generous. For the experiments we use the learning rates η ∈ {1, 10, 100, 1000}, that are several orders of magnitudes larger than η c . For each learning rate, we plot the outcome of 10 runs, corresponding to different random seeds. Each run lasts 10 6 (≈ e 14 ) iterations. The log-suboptimality gaps for the 4 × 10 cases are shown on Figures 1a-1d , where they are plotted against the logarithm of time. Additional results for K = 2 arms are shown in Appendix C. Note that in this example small sub-optimality implies that the optimal arm is chosen with high probability. In what follows, we discuss the results in the plots.Asymptotic convergence. For the smaller learning rates of η = 1 and 10, all 10 seeds rapidly and steadily converge, reaching a sub-optimality of e -14 or less. For η = 100 and 1000, most of the runs reach even small error even faster, but some runs are "stuck" even after 10 6 steps. Note that this does not contradict the theoretical result; nor do we suspect numerical issues. As seen for the case of η = 100, even after a long phase with little to no progress, a run can "recover" (see the grey curve). In fact, it is reasonable to expect that the price of increasing the learning rate is larger variance; as seen in these plots (subplots (a) and (b) are also attesting to this). Differences between learning rates are further discussed below.Non-monotone objective value. Using a very small learning rate guarantees monotonic improvement (in expectation) in the policy's expected reward [24] . Conversely, a large learning rate results in non-monotonic evolution of the expected rewards {π ⊤ θt r} t≥1 , even in the final stages of convergence, as can be seen clearly for the learning rates of η = 1 and 10 in Figures 1a and 1b . For larger η, the non-monotone behavior happens over longer periods and is less visible in the plots. This is because using large learning rates causes the policy to rapidly increase the parameters for some action, after which the gradient becomes small, limiting further progress.Rate of convergence. This work establishes almost sure convergence to the globally optimal policy as t → ∞ without giving any particular rate of convergence. Figures 1a and 1b , where the log-log plot has a slope of nearly -1, give some evidence that an O(1/t) asymptotic rate is achieved. In general, such a rate cannot be improved in terms of t [14] . However, more work is needed to rigorously quantify the asymptotic convergence rate.Different learning rates. Two observations can be made from Figure 1 regarding the effect of using different η values: First, during the final stage of convergence when r(a * ) -π ⊤ θt r ≈ 0, using larger η results in faster convergence on average. As η increases, the order of log (r(a * ) -π ⊤ θt r) also changes from e -14 (η = 1), to e -20 (η = 100), and e -200 (η = 1000). We conjecture that the asymptotic rate of convergence has an O(1/η) dependence. Second, using larger learning rates can take a longer time to enter the final stage of convergence. When η = 1 or 10, all curves quickly enter the final stage of r(a * ) -π ⊤ θt r ≈ 0. However, for larger η values, 1/10 runs (η = 100) and 3/10 runs θt r), plotted against the logarithm of time, log t, in a 4-action problem with various learning rates, η. Each subplot shows a run with a specific learning rate. The curves in a subplot correspond to 10 different random seeds. Theory predicts that essentially all seeds will lead to a curve converging to zero (-∞ in these plots). For a discussion of the results, see the text., (η = 1000) result in r(a * ) -π ⊤ θt r values far from 0 even after 10 6 iterations. These runs take orders of magnitude more iterations to eventually achieve r(a * ) -π ⊤ θt r ≈ 0. These situations correspond to the policy π θt getting stuck near sub-optimal corners of the simplex, meaning that π θt (i) ≈ 1 for a sub-optimal action i ∈ [K] with r(i) < r(a * ). In such cases, even Softmax PG with the true gradient can remain stuck on a sub-optimal plateau for an extremely long time [23] . However, the reason why larger learning rates lead to longer plateaus in the stochastic setting remains unclear.Trade-offs and multi-stage chracterizations of convergence. Given the above observations, there appears to exist a trade-off for η: larger η values result in faster convergence during the final stage where r(a * ) -π ⊤ θt r ≈ 0, but at the the cost of taking far longer to enter this final stage of convergence. Since asymptotic convergence results are insufficient for explaining these subtleties in a satisfactory manner, a more refined analysis that considers the different stages of convergence is required. 
conclusions and future directions: 
 This work refines our understanding of stochastic gradient bandit algorithms by proving that it converges to a globally optimal policy almost surely with any constant learning rate. Our new proof strategy based on the asymptotics of sample counts opens new directions for better characterizing exploration effects of stochastic gradient methods, while also suggesting interesting new questions. Immediate next steps are to characterize the asymptotic rate of convergence under large constant learning rates. Characterizing the multiple stages of convergence remains another interesting future direction. One interesting possibility is that there might exist an optimal time-dependent scheme for increasing the learning rate (such as η ∈ O(log t)) to accelerate convergence, rather than use a constant η ∈ O(1). This is corroborated by our experiments: As seen in Figure 1 , small learning rates perform better during the early stages of optimization, while larger learning rates achieve faster convergence during the final stage. Other directions include extending our bandit results to the more general RL setting [34] , as well as extending our results for the softmax tabular parameterization to handle function approximation [1] .Limitations: While this work establishes a surprising asymptotic convergence result for any constant learning rate, it does not shed light on the convergence rate, nor on the effect of different learning rates on the convergence. Moreover, our analysis is limited to multi-armed bandits, and does not immediately extend to the general RL setting. These aspects are the main limitations of this paper.Broader impact: This is primarily theoretical work on a fundamental algorithm that is used broadly in RL applications. We expect these results to improve the research community's understanding of the basic stochastic gradient bandit method. EQUATIONand letEQUATIONAccording to Eq. ( 22), we have, for all t ≥ 1,EQUATIONUsing triangle inequality, we have,EQUATIONEQUATIONEQUATIONBy assumption, we have,EQUATIONAccording to the extended Borel-Cantelli Lemma 3, we have, almost surely,EQUATIONCombining Eqs. ( 25), ( 28) and ( 29), we have, almost surely,EQUATIONwhich implies that, almost surely,sup t≥1 |θ t (a)| ≤ sup t≥1 |θ t (a) -θ 1 (a)| + |θ 1 (a)| < ∞.Lemma 2 (Avoiding lack of exploration). Using Algorithm 1 with any η ∈ Θ(1), there exists at least a pair of distinct actions i, j ∈ [K] and i ̸ = j, such that, almost surely,EQUATIONProof. First, we have, for all t ≥ 1,EQUATION=EQUATIONBy pigeonhole principle, there exists at least one action i ∈ [K], such that, almost surely,EQUATION)We argue the existence of another action by contradiction. Suppose for all the other actions j ∈ [K] and j ̸ = i, we have N ∞ (j) < ∞. According to the extended Borel-Cantelli Lemma 3, we have, almost surely,EQUATION)According to the update Eq. ( 22), we have, for all t ≥ 1,EQUATIONBy triangle inequality, we have,EQUATIONEQUATIONEQUATIONCombing Eqs. ( 36) and ( 38) and the assumption of N ∞ (j) < ∞ for all j ̸ = i, we have, almost surely,EQUATION)Since N ∞ (j) < ∞ for all j ̸ = i by assumption, and according to Lemma 1, we have, almost surely,EQUATIONCombining Eqs. ( 42) and (43), we have, for all action a ∈ [K], supEQUATIONwhich implies that, there exists c > 0 and c ∈ O(1), such that, for all aEQUATIONTherefore, for all action a ∈ [K], According to the extended Borel-Cantelli Lemma 3, we have, almost surely, for all action a ∈ [K],EQUATIONwhich is a contradiction with the assumption of N ∞ (j) < ∞ for all the other actions j ∈ [K] with j ̸ = i. Therefore, there exists another action j ∈ [K] with j ̸ = i, such that N ∞ (j) = ∞.Theorem 1. Let K = 2 and r(1) > r(2). Using Algorithm 1 with any η ∈ Θ(1), we have, almost surely, π θt (a * ) → 1 as t → ∞, where a * := arg max a∈[K] r(a) (equal to Action 1 in this case).Proof. The proof uses the same notations as of [24, Theorem 5.1].According to Lemma 2, we have, N ∞ (1) = ∞ and N ∞ (2) = ∞, i.e., both of the two actions are sampled for infinitely many times as t → ∞.Let F t be the σ-algebra generated by a 1 , R 1 (a 1 ), • • • , a t-1 , R t-1 (a t-1 ):EQUATIONNote that θ t and I t (defined by Eq. ( 23)) are F t -measurable for all t ≥ 1. Let E t [•] denote the conditional expectation with respect toF t : E t [X] = E[X|F t ]. Define the following notations, W t (a) := θ t (a) -E t-1 [θ t (a)],("noise") (52) P t (a) := E t [θ t+1 (a)] -θ t (a).("progress")For each action a ∈ [K], for t ≥ 2, we have the following decomposition,EQUATIONBy recursion we can determine that,EQUATIONwhile we also have,EQUATIONand E[θ 1 (a)] accounts for potential randomness in initializing θ 1 ∈ R K . According to Proposition 1, we have,EQUATIONwhich implies that, for all t ≥ 1,EQUATIONNext, we show that t s=1 P s (a * ) → ∞ as t → ∞ by contradiction. Suppose that,EQUATIONFor the optimal action a * = 1,EQUATIONwhere ∆ := r(a * ) -max a̸ =a * r(a) = r(1) -r(2) > 0 is the reward gap. Denote that, for all t ≥ 1,EQUATIONAccording to Lemma 8 (using Eqs. ( 58) to ( 60) and ( 62)), we have, almost surely,EQUATION)For the sub-optimal action (Action 2), we have,EQUATIONand also denote, for all t ≥ 1,EQUATIONAccording to Lemma 8 (using Eqs. (58), (59), ( 64) and ( 67)), we have, almost surely,EQUATIONCombining Eqs. ( 63) and (68), there exists c > 0 and c ∈ O(1), such that, for all a ∈ {a * , 2},EQUATIONwhich implies that,EQUATIONwhich is a contradiction with the assumption of Eq. (59). Therefore, we have,EQUATIONAccording to Lemma 9 (using Eqs. ( 58), (60), ( 62) and ( 74)), we have, almost surely,EQUATIONSimilarly, according to Lemma 10 (using Eqs. ( 58), ( 64), ( 67) and ( 74)), we have, almost surely,EQUATIONNote that,EQUATION)Combining Eqs. ( 75) to (77), we have, almost surely,π θt (a * ) → 1, as t → ∞.Theorem 2. Under Assumption 1, given K ≥ 2, using Algorithm 1 with any η ∈ Θ(1), we have, almost surely, π θt (a * ) → 1 as t → ∞, where a * = arg max a∈[K] r(a) is the optimal action.Proof. Similar to the proof of Theorem 1, we define F t to be the σ-algebra generated by a 1 , R 1 (a 1 ),EQUATIONNote that θ t and I t (defined by Eq. ( 23)) are F t -measurable for all t ≥ 1. Let E t [•] denote the conditional expectation with respect toF t : E t [X] = E[X|F t ]. Define the following notations, W t (a) := θ t (a) -E t-1 [θ t (a)], ("noise") (80) P t (a) := E t [θ t+1 (a)] -θ t (a).("progress")For each action a ∈ [K], for t ≥ 2, we have the following decomposition,EQUATIONBy recursion we can determine that,EQUATIONwhile we also have,EQUATIONand E[θ 1 (a)] accounts for potential randomness in initializing θ 1 ∈ R K . For an action a ∈ [K],EQUATIONEQUATIONDefine A ∞ as the set of actions which are sampled for infinitely many times as t → ∞, i.e.,EQUATION) First part. We show that N ∞ (a * ) = ∞ by contradiction. Suppose a * ̸ ∈ A ∞ i.e. N ∞ (a * ) < ∞. According to Lemma 2, we have, |A ∞ | ≥ 2. Since a * ̸ ∈ A ∞by assumption, there must be at least two other sub-optimal actions i 1 , iEQUATIONIn particular, define (90)EQUATIONUsing the update for arm i 1 , we know that, for all s ≥ 1,P s (i 1 ) = η • π θs (i 1 ) • (r(i 1 ) -π ⊤ θs r) (91)By definition and because of Assumption 1, we have that r(i 1 ) < r(i 2 ) < r(a * ). Furthermore, according to Lemma 6, we have, for sufficiently large τ ≥ 1,EQUATIONwhich implies that after some large enough τ ≥ 1,EQUATION< 0.(by Eq. ( 92)) ( 94)EQUATIONFrom Eq. ( 89), we have,EQUATIONwhich implies that, for all a -∈ A -(i 1 ), we have,EQUATIONNote that, by definition, i 2 ∈ A + (i 1 ), andN ∞ (i 2 ) = ∞.(98) In order to bound Eq. (95) using the above relations, note that,a -∈A -(i1) π θs (a -) a + ∈A + (i1) π θs (a + ) • (r(a + ) -r(i 1 )) • (r(i 1 ) -r(a -)) (99) < a -∈A -(i1)π θs (a -) π θs (i 2 ) • (r(i 2 ) -r(i 1 ))• (r(i 1 ) -r(a -))(Fewer terms in the denominator) By Lemma 5, for large enough τ ≥ 1, for all a -, π θs (a -)EQUATION)Combining Eqs. ( 94), ( 95) and (102), we have,EQUATIONwhere∆ := min i,j∈[K], i̸ =j |r(i) -r(j)| > 0.(by Assumption 1) (106) Bounding the variance for arm i 1 , we have that for all large enough τ ≥ 1,V t (i 1 ) := 5 18 • t-1 s=τ π θs (i 1 ) • (1 -π θs (i 1 )) (107) = 5 18 • t-1 s=τ π θs (i 1 ) •   a -∈A -(i1)π θs (a -) +EQUATIONUsing similar calculations as for the progress term, we have,a -∈A -(i1)π θs (a -)a + ∈A + (i1) π θs (a + ) < a -∈A -(i1)π θs (a -) π θs (i 2 ) (Fewer terms in the denominator) By Lemma 5, for large enough τ ≥ 1, for all a -, π θs (a -)π θs (i2) ≤ 13 5 1 |A -(i1)| . Hence, ≤ a -∈A -(i1) 13 5 • 1 |A -(i 1 )| (109) = 13 5 (110) =⇒ a -∈A -(i1)π θs (a -) ≤ 13 5EQUATIONCombining Eqs. ( 108) and ( 111), we have that for large enough τ ≥ 1,EQUATION)According to Lemma 12 (using Eqs. ( 94), ( 105) and ( 113)), we have, almost surely,EQUATION)Since N ∞ (a * ) < ∞ by assumption, and according to Lemma 1, we have, almost surely,EQUATION)Combining Eqs. ( 114) and (115), we have,EQUATION)On the other hand, by Lemma 5, we have,sup t≥1 π θt (i 1 ) π θt (a * ) = ∞ (117)which contradicts Eq. ( 116). Hence, the assumption that N ∞ (a * ) < ∞ cannot hold. This completes the proof by contradiction, and implies that N ∞ (a * ) = ∞.Second part. With a * ∈ A ∞ i.e. N ∞ (a * ) = ∞, we now argue that π θt (a * ) → 1 as t → ∞ almost surely.According to Lemma 2, we have, |A ∞ | ≥ 2. Since a * ∈ A ∞ by assumption, there must be at least one sub-optimal action i 1 ∈ [K] with r(i 1 ) < r(a * ), such that,EQUATIONIn particular, defineEQUATION)According to Lemma 6, we have, for all sufficiently large τ ≥ 1,EQUATION)Using the same arguments as in the first part (except that i 2 in Eq. ( 98) is replaced with a * ), both Eqs. ( 105) and ( 113) hold.Next, we argue thatEQUATION)According to Lemma 8 (using Eqs. ( 94), ( 105), ( 113) and ( 121)), we have,EQUATIONCalculating the progress and variance for arm a * , for t ≥ 1,EQUATIONEQUATION)Denote that, for all t ≥ 1,EQUATIONAccording to Lemma 11 (using Eqs. ( 123) and ( 126)), we have,EQUATION)Combining Eqs. ( 122) and (127), we have,EQUATIONFor all t ≥ 1, |θ t (i 1 )| < ∞ and since there is at least one arm (a * ) s.t. inf t≥1 θ t (a) > -∞, there exists ϵ > 0 and ϵ ∈ O(1), such that,EQUATION)According to Eq. ( 118), we know that N ∞ (i 1 ) = ∞ and for all a -∈ A -(i 1 ), N ∞ (a -) < ∞.Using Lemma 5, we have, for all large enough t ≥ 1,EQUATION)Combining Eqs. ( 129) and (131), we have, for all large enough t ≥ 1,EQUATIONwhich implies that, ∞ s=τ π θs (i 1 )a + ∈A + (i1) π θs (a + ) ≥ ϵ • ∞ s=τ π θs (i 1 ) (133) = ∞, (since N ∞ (i 1 ) = ∞ and by Lemma 3) (134)which contradicts the assumption of Eq. ( 121). This completes the proof by contradiction, and therefore, we have,EQUATION)According to Lemma 10 (using Eqs. ( 105), ( 113) and ( 135)), we have, almost surely,EQUATION)Combining Eqs. ( 127) and ( 136), we have, almost surely,EQUATION)Hence, we have proved that if N ∞ (i 1 ) = ∞ and r(i 1 ) < π ⊤ θt r < r(a * ) for sufficiently large τ ≥ 1, then,π θ t (a * ) π θ t (i1) → ∞, as t → ∞.In order to use this argument recursively, consider sorting the action indices in A ∞ according to their descending expected reward values,EQUATIONWe know that,EQUATIONEQUATIONAccording to Lemma 5, for all a -∈ A -(i 2 ) with a -̸ = i 1 , we have,EQUATIONCombining Eqs. ( 137) and (143), we have, for all a -∈ A -(i 2 ),EQUATIONHence, for all sufficiently large τ ≥ 1, for all a -∈ A -(i 2 ),EQUATIONCombining Eqs. ( 142) and (145), we have, for all sufficiently large t ≥ 1,EQUATIONHence we have, for all sufficiently large τ ≥ 1,EQUATIONComparing Eqs. ( 120) and (147), we can use a similar argument for i 2 and conclude that, for sufficiently large τ ≥ 1, then,π θ t (a * ) π θ t (i2) → ∞, as t → ∞.This further implies thatEQUATIONContinuing this recursive argument, we have, for all actions a ∈ A ∞ with a ̸ = a * ,EQUATIONMeanwhile, according to Lemma 5, we have, for all actions a ̸ ∈ A ∞ ,EQUATIONCombining Eqs. ( 149) and (150), we have, for all sub-optimal actions a ∈ [K] with r(a) < r(a * ),EQUATIONFinally, note that, EQUATION 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [Yes] Justification: See Section 5.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: No data or models are released.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [NA] Justification: No existing assets are used.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?Answer: [NA]Justification: The paper does not release new assets.Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing and research with human subjects: 
 Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?Answer: [NA] Justification: No human subjects or crowdsourcing is involved in this work.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 
institutional review board (irb) approvals or equivalent for research with human subjects: 
 Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?Answer: [NA] Justification: No human subjects or crowdsourcing is involved in this work.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.• We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: Lemma 3 (Extended Borel-Cantelli Lemma, Corollary 5.29 of [5] ). Let (F n ) n≥1 be a filtration, A n ∈ F n . Then, almost surely,EQUATIONLemma 4 (Freedman's inequality [10, 7] , Theorem C.3 of [24] ). Let X 1 , X 2 , . . . be a sequence of random variables, such that for all t ≥ 1,EQUATIONThen, for all δ > 0,EQUATIONLemma 5. Using Algorithm 1, for any two different actions i, j∈ [K] with i ̸ = j, if N ∞ (i) = ∞and N ∞ (j) < ∞, then we have, almost surely,EQUATIONProof. We prove the result by contradiction. SupposeEQUATIONAccording to the extended Borel-Cantelli Lemma 3, we have, for all a ∈ [K], almost surely,EQUATIONHence, taking complements, we have,EQUATIONalso holds almost surely, which implies that,EQUATIONEQUATIONTherefore, we have,EQUATIONEQUATIONwhich is a contradiction with Eq. (161).Lemma 6. Using Algorithm 1, we have, almost surely, for all large enough t ≥ 1,EQUATIONwhere i 1 , i 2 ∈ [K] and i 1 ̸ = i 2 are the action indices defined as,EQUATIONEQUATIONProof. Define A ∞ as the set of actions which are sampled for infinitely many times as t → ∞, i.e.,EQUATIONAccording to Lemma 2, we have|A ∞ | ≥ 2, which implies that i 1 ̸ = i 2 .Given any sub-optimal action i ∈ [K] with r(i) < r(a * ), we partition the remaining actions into two parts using r(i).EQUATIONEQUATIONBy definition, we have,EQUATIONEQUATIONFirst part. r(i 1 ) < π ⊤ θt r. If r(i 1 ) = min a∈[K] r(a), i.e., i 1 is the "worst action", then r(i 1 ) < π ⊤ θt r holds trivially. Otherwise, suppose r(i 1 ) ̸ = min a∈[K] r(a). We have,EQUATIONConsider the non-empty set A ∞ ∩ A + (i 1 ). Pick an action j 1 ∈ A ∞ ∩ A + (i 1 ), and ignore all the other actions a + ∈ A + (i 1 ) with a + ̸ = j 1 in the above equation. We have,EQUATIONEQUATIONwhere the first inequality is because of r(a + ) -r(i 1 ) > 0 for all a + ∈ A + (i 1 ) by Eq. ( 170). Note that N ∞ (j 1 ) = ∞ and N ∞ (a -) < ∞. According to Lemma 5, we have, for all large enough t ≥ 1,EQUATIONEQUATION)Combining Eqs. ( 175) and (177), we have,EQUATIONwhere the last inequality is because j 1 ∈ A + (i 1 ).Second part. π ⊤ θt r < r(i 2 ). The arguments are similar to the first part. If r(i 2 ) = r(a * ), i.e., i 2 is the optimal action, then π ⊤ θt r < r(i 2 ) holds trivially. Otherwise, suppose r(i 2 ) ̸ = r(a * ). We have,EQUATIONConsider the non-empty setA ∞ ∩ A -(i 2 ). Pick an action j 2 ∈ A ∞ ∩ A -(i 2 ), and ignore all the other actions a -∈ A -(i 2 ) with a -̸ = j 2 in the above equation. We have,EQUATIONwhere the first inequality is because of r(i 2 ) -r(a -) > 0 for all a -∈ A -(i 2 ) by Eq. ( 170). Note that N ∞ (j 2 ) = ∞ and N ∞ (a + ) < ∞. According to Lemma 5, we have, for all large enough t ≥ 1,EQUATIONEQUATIONCombining Eqs. ( 182) and (184), we have,EQUATIONwhere the last inequality is because j 2 ∈ A -(i 2 ).For the following lemmas, we will use the notation defined in the proofs for Theorems 1 and 2. Lemma 7 (Concentration of noise). Given an action a ∈ [K]. We have, with probability at least 1 -δ, ∀t :EQUATIONwhereEQUATIONandEQUATIONis originally defined by Eq. (52).Proof. First, note that,EQUATIONUsing the update Eq. ( 22), we have,EQUATIONAccording to Eq. ( 1), we have,EQUATIONThe conditional variance of noise is,EQUATION)where the inequality is by (a + b) 2 ≤ 2a 2 + 2b 2 . Next, we have,EQUATIONEQUATIONEQUATIONEQUATIONCombining Eqs. (196), ( 198) and (201), we have, EQUATIONEQUATIONAccording to Lemma 4, there exists an event E 1 such that Pr(E 1 ) ≥ 1 -δ, and when E 1 holds, ∀t : Lemma 8 (Bounded progress). For any action a ∈ [K] with N ∞ (a) = ∞, if there exists c > 0 and τ < ∞, such that, for all t ≥ τ ,EQUATIONwhere V t (a) is defined in Eq. (189), and if alsoEQUATIONthen we have, almost surely,EQUATIONProof. According to Eq. ( 55) and triangle inequality, we have,EQUATIONAccording to Lemma 7, there exists an event E 1 , such that Pr(E 1 ) ≥ 1 -δ, and when E 1 holds, we have, for all t ≥ τ + 1,EQUATIONAccording to Eq. ( 212), as t → ∞, Take any ω ∈ E := {N ∞ (a) = ∞}. Because P(E \ (E ∩ E 1 )) ≤ P(Ω \ E 1 ) ≤ δ → 0 as δ → 0, we have that P-almost surely for all ω ∈ E there exists δ > 0 such that ω ∈ E ∩ E 1 while Eq. ( 215) also holds for this δ. Take such a δ. We have, almost surely,sup t≥1 |θ t (a)| < ∞.Lemma 9 (Unbounded positive progress). For any action a ∈ [K] with N ∞ (a) = ∞, if there exists c > 0 and τ < ∞, such that, for all t ≥ τ , P t (a) > 0, andEQUATIONwhere V t (a) is defined in Eq. (189), and if also,EQUATIONthen we have, almost surely,EQUATION)Lemma 12 (Negative progress). For any action a ∈ [K] with N ∞ (a) = ∞, if there exists c > 0 and τ < ∞, such that, for all t ≥ τ , P t (a) < 0, and-EQUATIONwhere V t (a) is defined in Eq. (189), then we have, almost surely,EQUATIONProof. First case: if -∞ t=1 P t (a) < ∞, then according to Lemma 8, we have, almost surely, supEQUATIONwhich implies Eq. (237).Second case: if -∞ t=1 P t (a) = ∞, then according to Lemma 10, we have, almost surely,EQUATIONwhich also implies Eq. ( 237). Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [No] Justification: Given that we are doing simulations with a very classical algorithm, for which we give all simulation details and hyperparameters, we do not believe that code is necessary to reproduce the results. Our data is simulated, and hence easily reproduced, given the distribution which we explicitly describe. Guidelines:• The answer NA means that paper does not include experiments requiring code. Justification: The research does not involve human subjects or introduces any new datasets.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).38th Conference on Neural Information Processing Systems (NeurIPS 2024). 


Decision: The most common score for this work is Borderline accept, and none of those reviewers make a strong case for its acceptance. However, after reviewing the paper and the commentary of Reviewer E4oN, I believe this paper contributes some novel proof techniques that alleviate undue dependence on unrealistic assumptions present in prior art. Therefore, it clears the bar for acceptance.

Reviews: review: paper_summary: paper_summary: This paper proved that stochastic gradient bandits converge to a globally optimal policy almost surely for arbitrary constant learning rates if true mean reward has no ties.
strength_weakness: strength_weakness: This paper heavily relies on prior work [23], which established the asymptotic rate for a constant learning rate. As a follow-up study, however, I believe this paper does not present sufficiently strong results to warrant acceptance at a top conference.
questions: questions: In simulations, if the learning rate is initially set to large number and then decreased, does algorithm show fast convergence?
limitations: limitations: Yes, the authors address the limitations.
paper_summary: paper_summary: The paper reveals that the stochastic gradient bandit algorithm converges to a globally optimal policy almost surely using any constant learning rate. This result stands even when traditional smoothness and noise control assumptions are not met, showing the algorithm’s balance between exploration and exploitation.
strength_weakness: strength_weakness: 1. As the authors also acknowledge, Assumption 1 seems to be a strong one and possibly unrealistic in applications.
2. The work establishes almost sure convergence to the globally optimal policy as $t \rightarrow \infty$, which doesn't tell anything about the rate of convergence.
3. Section 5.1 in [23] appears to have similar results as the one presented in this paper. In the discussion of the natural exploratory behavior is attributed to the softmax Jacobian in the update, which is also discussed extensively in [23]. However, I understand that the main focus of  [23] is to show that the stochastic gradient bandit algorithm converges to a globally optimal policy at an $O(1/t)$ rate. I am concerned that this paper loses significance as [23] already establishes convergence rates to the globally optimal policy. 
4. Even though the main focus of the paper is theoretical, it would be nice to see how the stochastic gradient compares to other bandit algorithms such as UCB and Thompson Sampling in numerical experiments.


*[23] Mei, Jincheng, et al. "Stochastic gradient succeeds for bandits." International Conference on Machine Learning. PMLR, 2023.*
questions: questions: 1. The paper focuses on the simplest setting of the stochastic bandit problem, where decisions only matter for one step. The more common consideration in bandits literature is to maximizing the cumulative reward (or minimizing the expected regret). Can we apply the stochastic gradient bandit algorithm in that setting?
2. The numerical experiments section in the paper indicates that smaller learning rates perform better during early optimization stages, while larger rates are beneficial later. I have two related thoughts to this and was wondering if any comments could be made regarding the same:
- For adaptive learning rates, can one think of running the algorithm in batches, such that the learning rates are decreased systematically for consequent batches?
- Intuitively the right learning rate should depend on the underlying difficulty of the reward generating mechanism for different arms, however I am not sure if that is apparent from the discussion in the paper. 
3. Can this be extended to the contextual bandits framework?
limitations: limitations: Yes, limitations have been adequately addressed. Societal impact statement N/A.
paper_summary: paper_summary: The paper presents a novel theoretical analysis of the stochastic gradient bandit algorithm, showing that it converges to a globally optimal policy almost surely using any constant learning rate. This result is significant as it extends the understanding of stochastic gradient methods in bandit settings, even when standard smoothness and noise control assumptions do not hold.
strength_weakness: strength_weakness: 1. Practical Implications: While the theoretical results are robust, the practical implications, especially regarding the choice of learning rate in real-world applications, are not thoroughly discussed. It would be beneficial to include more guidance on how practitioners can leverage these findings.
2. Rate of Convergence: The paper establishes almost sure convergence but does not provide specific rates of convergence. Including more detailed analysis or conjectures about the rate would enhance the practical utility of the results.
3. Generalization: The study is limited to multi-armed bandits. Extending the results to more general reinforcement learning settings would significantly increase the impact of the work.
4. Assumption 1: The assumption that the true mean reward has no ties (Assumption 1) is restrictive. Addressing this limitation or providing more discussion on how this assumption might be relaxed in future work would strengthen the paper.
questions: questions: Proof Details:

Could you provide more detailed explanations for Lemma 1 and Lemma 2? Specifically, how do the assumptions ensure the boundedness of parameters?
Experimental Results:

In the experimental section, you use different learning rates (η). Could you elaborate on the observed differences in convergence behavior for these learning rates? How does the algorithm perform with learning rates outside the tested range?
Practical Implications:

How would you recommend practitioners choose an appropriate learning rate for real-world applications based on your findings? Are there any heuristics or rules of thumb that can be derived from your results?
Generalization:

Your results are currently limited to multi-armed bandits. What challenges do you foresee in extending these results to more general reinforcement learning settings? How might the approach change?
Assumption 1:

Assumption 1 states that the true mean reward has no ties. How critical is this assumption to your results? Do you have any ideas on how to relax this assumption in future work?
Convergence Rate:

While you have shown almost sure convergence, the specific rate of convergence is not detailed. Could you provide more insights or conjectures about the expected rate of convergence for different learning rates?
Limitations and Future Work:

You mention that a more refined analysis is needed to explain the subtleties of different stages of convergence. Could you suggest specific directions or methods for this refined analysis?
limitations: limitations: no
paper_summary: paper_summary: This work studies the asymptotic global convergence rate of the stochastic gradient bandit algorithm with an arbitrary constant learning rate and proves that this algorithm asymptotically converges to the global optimal. This work reveals how this algorithm balances exploitation and exploration and proves the results by contradiction and reduction. This work also provides simulation experiments to support their results.
strength_weakness: strength_weakness: The empirical success of a large learning rate is unclear. This work shows that softmax policies and logistic regression can be learned when using a large learning rate. However, they do not show that a large learning rate can lead to great empirical performance.
questions: questions: Question 1: As shown in Figure 1, when choosing $\eta= 100$ or $1000$, the algorithm does not converge. Can you discuss this phenomenon in detail?

Question 2: [1] consider $K=10$ in the simulation study. However, this work does simulation experiments with small arm numbers such as $K=4$ or $K=2$. It would be better to consider larger $K$ and show that the learning rate would not be influenced by $K$.

Comment 1: It would be helpful to discuss the challenge when using the technique in [1] for a constant learning rate.  

[1] Mei, J., Zhong, Z., Dai, B., Agarwal, A., Szepesvari, C., & Schuurmans, D. (2023, July). Stochastic gradient succeeds for bandits. In International Conference on Machine Learning (pp. 24325-24360). PMLR.
limitations: limitations: The authors adequately addressed the limitations and societal impact.
paper_summary: paper_summary: This paper studies stochastic gradient bandits with arbitrarily large learning rates. The authors prove an interesting result -- the learning rate of the gradient bandit algorithm (in particular, REINFORCE without baseline) can be arbitrarily large. Some numerical simulations are also provided to validate the findings.
strength_weakness: strength_weakness: 1. Optimization with large learrning rates have been studied, but the authors seem to only focus on the RL settings. It might be helpful to also include some literature review on deep learning with large learning rates (see, e.g., [1]).

2. Although it is shown that the algorithm can converge with arbitrarily large learning rates, it is still unclear what the exact convergence rate is. In contrast, a previous work [2], as also mentioned by the authors, has the finite-time convergence guarantees.

3. The code is not provided, although the experimental setting is simple.

[1] Gradient Descent on Neural Networks Typically Occurs at the Edge of Stability

[2] Stochastic gradient succeeds for bandits.
questions: questions: 1. Algorithm 1 is the gradient bandit algorithm without baselines. Can we also have similar results for the version with baselines?

2. What would be the challenges of extending the current analysis to the non-asymptotic rate analysis? Furthermore, what would be the challenges of extending the current proof techniques to other RL algorithms like natural gradient methods?
limitations: limitations: 1. The convergence results only imply asymptotic convergence without an explicit rate. Thus one direct question one may ask is, how does the learning rate affects the convergence speed. It would be interesting to study if there is an optimal learning rate.

2. The current results are only limited to REINFORCE without baselines for bandit setting, which is simpler than more complex RL settings. Hence it is unclear if it can provide any guidance to RL research in general.

Comments: title: Reply to rebuttal
Reply to the rebuttal
comment: Thank you for your rebuttal. The additional experiments and the discussion on the technique challenge address my concerns. I will keep my positive score to support this valuable work.
Thank you for your rebuttal. I have updated the score to 'borderline accept.'
I appreciate the authors' detailed response to my questions. After reading the rebuttal, I decide to maintain my initial score.
Thank you for your rebuttal. Your rebuttal addressed my questions and I would like to keep my score to vote for acceptance.