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 Szepesvari
Dale Schuurmans
Venue: NeurIPS 2024 poster (2024)
Keywords: stochastic gradient bandit
arbitrary stepsize
global convergence
Primary area: bandits
TL;DR: stochastic gradient bandit algorithm converges to a globally optimal policy almost surely using any constant learning rate

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.

Small steps no more: Global convergence of stochastic gradient bandits for arbitrary learning rates
Jincheng Mei
Bo Dai 13
Alekh Agarwal 2
Sharan Vaswani
Anant Raj
Csaba Szepesvári
Dale Schuurmans
Google DeepMind
Google Research Georgia Institute of Technology University of Alberta
5 Simon Fraser University Indian Institute of Science
{ cmei, bodai, alekhagrwaa,,, vaswani.. sharan@gmail com anantraj@iisc. ac.
Abstract
We provide understanding of the stochastic gradient bandit algorithm by showing that it converges to a globally optimal policy almost surely using any con- stant 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 be- tween cumulative progress and noise, and extend the current understanding of how simple stochastic gradient methods behave in bandit settings.
Introduction
The stochastic gradient method has been ubiquitous in the field of machine learning for decades 4 When applied to reinforcement learning (RL), representative instantiation of stochastic gradient the well known policy gradient [32) (or REINFORCE (34) algorithm, where in each iteration online sample is gathered using the current policy, from which gradient estimate is obtained to conduct parameter updates. In the simplest setting of stochastic bandit problem [16], where decisions matter only for step, the REINFORCE policy gradient method becomes equivalent to the stochastic gradient bandit algorithm [1 Section 2.8). Compared to other statistical methods, such 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, 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 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 important question to understand the success of stochastic gradient based algorithms bandit-like settings, not only bridge the gap between theory and practice, but also 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 n > 0, the stochastic gradient bandit algorithm is guaranteed to converge to the globally optimal policy almost surely.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Since learning rate is the only tuning parameter in the stochastic gradient bandit algorithm, this result offers 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 pnpllraatio-exploittaiii
trade-off. Prior theoretical work on the stochastic gradient algorithm has primarily focused on non-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 globally optimal policy asymptotically as the number of iterations goes to infinity [. Subsequent work has demonstrated that the asymptotic rate of convergence is O(1/t) [2]. 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)
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 global optimum without careful design choices [9]. Yet in the same setting, standard Softmax PG has been shown to succeed in simplest form, provided only that sufficiently small learning constant rate E ((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 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 precise rate if noise in the gradient estimator persists. In addition appropriate learning rate control, many other techniques have been developed to control the effects of gradient noise, including regularization [3 D. variance reduction (37, and carefully considering growth conditions [36]
28 12
38
9 37
36
24 g
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 1) >> 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 use any exploration bonus, which means that new techniques are required demonstrate that adequately balances the exploration-exploiaatin trade-off.
In this paper, 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 minimal form of exploration without any further modification. This asymptotic event (as t - co) happens with probability and holds for any constant learning rate > O.
(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 - oc, with probability 1. That is. the probability of sub-optimal actions decays to O, even though some of them are taken infinitely often asymptotically.
2 Setting and Background
We consider the stochastic multi-armed bandit problem [6). specified by K actions and true mean reward vector r E R where for each action a E [K] == 2 K).
Rmace
r(a)=
_ x. Pa(x))(dd))
where Penax > is the reward range, / is finite measure over |- Rmaax Rmax), and (x 2 the probability density function with respect to u. We use R, to denote the reward distribution for

---

Algorithm Gradient bandit algorithm (without baselines)
Input:
initial parameters 01 E I²x learning rate 17 >> 0.
Output: policies Re, softmax(0,).
while t 2 do
Sample an action a, TT. (-) and observe reward Re (a+) Pax.
for all E K do
if = de then
81-1(a) t (a(a) +
To) Re(as).
else
(a-1(a) + 0z(a) 71- no, (a) Rí (wt))
end if
end for end while
action a defined by the density Pa and base measure μa. The goal is to find policy E [0, 1] to achieve high expected reward,
max Te r, BERR
(2)
where my is parameterized by 0 E R
The gradient bandit algorithm. A natural idea to optimize Eq. 2 is to use stochastic gradient ascent, which shown in Algorithm| [ and known as the gradient bandit algorithm [31 Section 2.8].
In Algorithm I in each iteration 2 1, the probability of pulling arm E [K] is given as
exp(Or(a))
Te, (a) = (s)) = E exp(O:(a'))
for all a E [K],
where Og E R is the parameter vector to be updated. The following proposition shows that Algorithm Tis an instance of stochastic gradient ascent with an unbiased gradient estimator 24]. Proposition 1 (Proposition 2.3 of (24 Algorithm
is equivalent to the following update,
d T 0++1 O0 d0, O2 17- (diag(TT.) -T. TB.) fr.
(4)
[d f. where E,
d0, d0, and [-] is defined with respect to randomness from on-policy sampling ag To.()) and reward sampling Re(as) Pat- The Jacobian of 9 + Te softmax(()) is To
diag(To) To E R and fr (a(a) [fa==ot Ra(a) for all [K] is the
no, (a) importance sampling (IS) estimator, and we set Rg (a) = for all a + az.
Known results on the convergence the gradient bandit algorithm. Since Eq. corresponds to smooth non-concave maximization problem over 9 E IRK [23]. using Algorithm with decaying learning rates is sufficient to guarantee convergence 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 a globally optimal policy have been developed for PG methods in the true gradient setting 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
stationary point (28 25
12 39 However,
36 24 [8]. 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 large learning rate in the stochastic gradient bandit algorithm is viable option. For example, it has been observed that softmax policies learn even with extremely large learning rates such as 2 11 For logistic regression on linearly separable data, the objective has exponential tail and the minimizer unbounded, yet it has been shown that gradient descent with iteration dependent learning
rate 7 E @(t) achieves accelerated O(1/t²) convergence (35). Though the objective in Eq. (2) has

---

similar properties, unlike logistic regression, the problem we are considering is non coneave, so the same techniques cannot be directly applied. The most related results are from 224, which proved that with a small problem specific constant learning rate, Algorithm [ achieves convergence to 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 inapplica- ble. Furthermore, with a large constant learning rate, it is unclear whether Algorithm | 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 since the classical optimization and stochastic approximation convergence
behavior of Algorithm [] theories are no longer applicable, explained.
3 Asymptotic Global Convergence of Gradient Bandit Algorithm
We have seen that solving the non-concave maximization problem Eq. 2 using Algorithm [ with any constant (potentially large) learning rate requires ideas beyond classical optimization theory. Here, we take a different perspective to investigate how Algorithm| [
|sampees actions. For analysis, we make the following assumption about the reward distribution.
Assumption 1 (True mean reward has no ties). For all i,j E [K),ifi j. then ( r()..
Remark 1. Removing Assumption ! remains an open question for future work, while we believe that Algorithm 7 works without Assumption [ One piece of evidence to support this conjecture that even in the exact gradient setting, the set of initializations where Softmax PG approaches non-strict one-hot policies has zero measure.
3.1 Failure Mode of Aggressive Updates
It has been observed that several accelerated PG methods in the true gradient setting. including natural PG [13 [ and normalized PG (2), obtain worse results than standard softmax PG if combined with online sampling 42 To, (.) using constant learning rates (20. The failure mode in these cases is that the update is too aggressive and commits
sub-optimal arm without sufficiently exploring all arms. This results in non-trivial probability of sampling one action forever, i.e., there exists a potentially sub-optimal action a E [K]. such that with some constant probability, a; = a for all I 2 1. Such an outcome implies that To, (a) - 1 as + do 20 Theorem 3]. Since E [K] could be a sub-optimal action with r(a) < rr(a))= ma r(a). this results lack of exploration, and consequently, methods such natural PG and normalized PG are not guaranteed to converge to the optimal action a' := arg max r(a) with probability
3.2 Stochastic Gradient Automatically Avoids Lack of Exploration
Our first key finding is that Algorithm dooes not keep sampling one action forever, no matter how large the constant learning rate is. This property avoids the problem of lack of exploration, in the sense that Algorithm will at least explore more than one action infinitely often. At first glance, this might not seem like 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 [K], for all / 1,
(a)1(a) +- (a(a)) + 1 (1 na, =o, (a)) (a)a,) - Tg, (a) (a,))
if = a, otherwise.
(5)
(6)
We define Ne(a) as the number of times action a E [K] is sampled up to iteration t 2 1, i.c.
N.(a) = Ia. = a},

---

and its asymptotic limit (a) == limm-+oo Ni)a), which could possibly be infinity. For all E [K] we have either (a) oc or (a) < oo, meaning that a E [K] sampled infinitely often or
only finitely many times asymptotically. First, we prove the following Lemma] [ which shows that if
an action a E [K] is sampled only finitely many times as t - 0o, then the parameter corresponding to action a is also finite, i.e., suPr21 [0,(a)] < co.
Lemma 1. Using Algorithm| 7 with any constant 1) E (1)), if (a) < 0o for an action [K]. then we have, almost surely,
sup (a)) co, and inf (a) > -0.
(8)
Lemma Wiil be used multiple times in the subsequent convergence arguments.
Proof sketch. Since we assume action a E [K] is sampled finitely many times, the update given in the case depicted by Eq. ( happens finitely many times. Each update is bounded since the sampled reward is in [- Rmax; Rmax] by Eq. ( and the learning rate a constant, i.e., 1) E ((1). In Algorithm [ (a) is still updated even when * a, with the corresponding update given by the case depicted by Eq. (6) Therefore, whether (a) is bounded depends on the cumulative probability Σ. Tg. (a) being summable as t + co. According to the extended Borel-Cantelli
lemma (Lemma we have, almost surely,
Σ 11
(a) = =00 = (Noo = =00
(9)
which implies (by taking complements) that E.>1 No. (a) oo if and only if No (a) < co. There- fore, if a [K] is sampled finitely often, (a) will be updated in a bounded manner (using Eqs. (5)
and (6) as & + oc, hence establishing Lemma] | Detailed proofs for this lemma, as well as for all other results in this paper can be found in the appendix.
Given Lemma I we can then establish the above-mentioned finding about the exploration effect of Algorithm I Tin Lemma[]
Lemma 2 (Avoiding lack of exploration). Using Algorithm 7 with any r7 E @(1), there exists at least a pair of distinct actions i, E [K] and + j. such that, almost surely,
(i) co, and Noo(j) = xc.
(10)
Proof sketch. The argument for the existence of one such action is straightforward, since by the pigconhole principle, if there are finitely many actions, i.e., K < co, there must be at least one action i E [K] that is sampled infinitely often as t + co.
The argument for the existence of a second such action is by contradiction. Suppose that all the other actions E [K] with # i are sampled only finitely many times as t + co. According to Lemma [ their corresponding parameters must remain finite, i.e., sup:21 [0: < oo for all j E [K] with j 전 i. Now consider (i). By assumption, the second update case for this parameter, Eq. (6). happens only finitely often, since Eq. (6) can only occur when a; # i. Therefore, the key question is whether the cumulative probability Σ
no, (o) involved in the first case of the update, Eq. (5), is summable as t -> co. Note that Σ.=1 (1 To, (1)) = E'm Ej No, (j), which indeed summable as oo, by the assumption and Eq. (9). This implies that action which is sampled infinitely often, achieves parameter magnitude, sup (1)) < oc, that remains bounded as + oo. Using the softmax parameterization Eq. (3) in the above argument, we conclude that for all a E [K] inf:21 To, (a) > 0, i.e., every action's 's probability remains bounded away from zero, and hence not summable. Using Eq. (9), this implies that every action sampled infinitely often, which contradicts the assumption that only action i is sampled infinitely often as t - xo.
Discussion. Lemma 2 jimplies that Algorithm I Tis 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., 17 E @(1). According to 20 Algorithm| to a sub-optimal action a E [K] forever, i.e.,
Theorem 7], even if we fix the sampling
a; for all /. > 1, its probability will not approach faster than ((1/l), i.e., 1 no, (a) E ((1(t). This means that there must be at least one another action a' E [K] with a' * a, such that a' will also be sampled infinitely often. A more intuitive explanation is that the (1 To. (a)) term in Eq. 5 will
5

---

be near 0, which slows the speed of committing to a deterministic policy on whenever TT, (a) is close to which encourages exploration. Such natural exploratory behavior arises in Algorithm | because of the softmax Jacobian diag(TT) T in the update shown in Proposition which determines the growth order of (,(a) for all E [K] as t - oc, making the effect of a constant learning rate v) E (1) asymptotically inconsequential.
3.3 Warm up: Global Asymptotic Convergence when K =
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 key result, that for both actions a E [K], the random sequence {0:(a) he21 follows the direction of the expected gradient for sufficiently large 2 1 almost surely. The proof uses 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 noo matter how large the learning rate is, as long as r (
0C. We now illustrate the second
Theorem 1. Let K = 2 and r(1) > r(2). Using Algorithm [ with any 1) E ( we have, almost surely, Te, (a") + as + co, where a" = arg ae r(a) (equal to Action 1 in this case).
Proof sketch. According to Lemma (1) = (2) = co. Denote the the reward gap as A == r(a")= maxaşaa r(a) O, which becomes A r(1) r(2) for two actions. Since the stochastic gradient is unbiased (Proposition D. we have, for all l 2 (detailed calculations omitted),
E, 10 (a") 0r(a") ) + - To, (a") (r(a") -
(11)
0.(aa) ) + -
To, (a*) A 001 To, (a") )) > (a(a))
(12)
A similar calculation shows that,
E2 (0++ = 8, - (2) (1 no. (2)) < (2).
(13)
which means that (a(aa) is monotonically increasing in expectation and (2) is monotonically decreasing in expectation. In other words, {0=(2)))22 is sub-martingale, while (2)(2)
is super- maptinaarin However, since 0r E R is unbounded, Doob's martingale convergence results cannot be directly applied, so we pursue a different argument. Following 19 24), given an action [K], we define (a) == E, (a)] (a) the "progress", and define (a) = (a( - Ex-1 [+-1(0,(a)) as the "noise", where (a))) = (a) + Pt-1(a) + (a)) By recursion we can determine that,
0e(a) - (a) + Σ W. (a)
Σ P.(a).
(14)
i.e., (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 + co. According to the calculations Eqs. 12) and (3) we have P:(a*) > and (2) < O, both of which oc and (2) + - co as t + co, which implies that te, (a") (x*)) - (())))()))( + oo, hence ne, (aa) + 1 as t + oc.
are not summable. As result, 0, (a
m2, (2)
3.4 Global Asymptotic Convergence for all K 2 2
The illustrative two-action case shows that if TJ. r E (r(2), and if both actions are sampled infinitely often, then we have, almost surely 0z(a*)= - oo and 0, - -oo as a + oc. However, the question at the beginning of Section 3.2 remains: when > 2, 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. The answer no, which follows from our third key finding, which is based on another inttradittion-based argument that establishes almost sure convergence to globally optimal policy in the general K case.
Theorem Given K 2, using Algorithm 7 with any n E O(1), we have, almost surely, no, (a*) 1 as f + oC, where a" arg [K) r(a) ) is the optimal action.

---

Proof sketch. We consider two cases: Na"a") < oc and (a*) = oc, corresponding to whether the optimal action sampled finitely or infinitely often as t + cc. We argue that the first case oN (a*) < xc) is impossible, while for the second case (Noc (a*) = oo) we prove that 0e(a") - (a) + oc for all a E [K] with r(a) < r((a), ), which implies To, (a") -> as - oc.
First case. Suppose that (a") < co. We argue that this is impossible via contradiction. Given the assumption and Lemma 2 we know there must be least two other sub-optimal actions ر1, i2 [
i1 # i2. such that Noo (21) = Noo = oc. In particular, let i1 = arg (ej)) (a)==o r(a) and
dg = arg max [ =m)== r(a), hence r(i1) < ((2) < rr(aa) By Lemma (see Appendix) we
will also have r(ii) < _ / < r(i2) for sufficiently large t 2 1, which implies for action é1,
E, 1. (b1) = (11) + 17 -T
To. (11) (r(11) - nØ.r) < (i()))
(15)
for sufficiently large 2 1, which further implies that sup;>1 (,(11) cc. Meanwhile, for the optimal action a", the assumption and Lemma | imply that inf:2] 0+(aa) > oo. Combining these two observations gives,
To. (ii) sup exp (0c()(())) 0c(aa)) <0.
sup 121 Te. (a*) 121
(16)
On the other hand, since N (i1) SuP121 (f) - (aa)) = 0o by Lemma 5 (see Appendix), which contradicts Eq. (16).
oo and No (a") < oc (by assumption), we then have
Second case. Suppose that Noc (a") = co. We will argue that ne, (a") - a - oo almost surely.
First, according to Lemma 2 there exists at least one sub- sub-optimal action i E [K], i # a", such that Nox (1i = oC. Let in arg [igg (a))= r(a). By Lemma 6 and the definition of a",
we have r(i1) < T. < r(a") ) for all sufficiently large & 2 1. Since Noc (i1) = oc, using similar calculations to Eqs. 13 and 14p in Theorem [ we have, (11) + -00 as l + co. We also have, no, (a na, (f1)
inf:21 0(((a))) ) > 00 as + 00. Hence,
cxp) 0. (i1)) - oc as t + co.
Define Ar = ta E [K] Noc (e) bo} as the set of actions that are sampled infinitely often, and note that | 2 by Lemma
2
Sort the action indices in As according their expected reward
values in descending order, i.e.,
r(a")= > r((j1=--)) Assumption iis used here to prevent two arms from having the same reward and thus guarantee the inequalities are strict in Eq. (17p. Next, using similar calculations in Lemma we have,
((()A=l-2) > r(iz) r(i))-
(17)
T0.- - r(12) > To, (a*) [n(aa)- - r((2)
Σ (12)
To, To,(a
(f((z) (r(iz)-r(a7) r(a - (18)
(a))
where A (12) = fa E [K] r(a-) <r())) is the set of actions that have lower mean reward than ie E [K]. and note that i E A (12). Using the above definitions, we can conclude that i is the only arm A (iz) that has been sampled infinitely often. According Lemma 5 for all a E AA- (1z) as 1 oo, since Na= oc (by assumption) and Noo (a(a < oo (by Eq. 17 Therefore, for all sufficiently large I, the probability ratio in Eq. 18) So, (a")
with a= # i1, we have, na, (o,(0-)
To, (a-) + do for all a E EAT (62), which implies that, for all sufficiently large 1z 1,
T r - r((2) 0.5 Te, (a") (r(a*) - r(12)) > O.
(19)
We have thus shown that -o.r r(f2). Recall that had previously proved that -..r r(i)). Hence, we will apply this argument recursively: after this point, ig [K] will become the new "i, E [K]", and a similar inequality to Eq. (13) will then hold for is E [K] from similar calculations
to Eqs. (13 and (14 in Theorem 1 establishing (f2) - -0 + oo. This will imply that for
all sufficiently large / 121, 1,
T - riia) > 0.5 Ta, (a") (r(a*) - r(ia)) >
(20)
Continuing the recursive argument, we can conclude for all actions a E As with a # a" that To,
(o)(o) 00 as + co. Meanwhile, for all actions a & Asc. Lemma 5 also shows that no, (a)) do
Ne, (a)
as co. Combining these two results yields the conclusion that for all sub-optimal actions E [K]
with r(a) < r(aa) we have No, (a*) (a) - 00 as t + co, which implies no, (a*) + 1 as t - 0c. Thus,
we have established almost sure convergence to the globally optimal policy.
7

---

Discussion. Lemma is important to prove that the optimal arm will be sampled infinitely often.
In particular, Lemma guaranttes |A 2 2 and the existence of i Eq. (15). which can then be
used to construct the contradiction in Eq. (16). Without Lemma 2 |Abx might be equal to 1 and
the failure mode in Section 3.1 can occur, resulting Algorithm not sampling the optimal action infinitely often as > oc.
3.5 Asymptotic Rate of Convergence
According Theorem 2 almost surely, Te, (a") + as xc. Therefore, after large enough time < DC, we have Te, (a 2 1/2, which implies that the "progress" term in Eq. (14) can be lower bounded. With this, asymptotic rate of convergence
be proved follows.
Theorem 3. For a large enough T > O, for all T > T, the average sub-optimality decreases at an rate. Formally, if a² is the optimal arm, then, for a constant c,
(T) T
Σne r(a") - (Te. r)
c (ln(T)
T
T-T
4 Simulation Study
To validate and enhance the theoretical findings, we ran experiments with four action bandit environment (K = 4) with true mean reward vector of r = (0.2, 0.05. -0.1 -0.4) T E IR.. The reward distribution Pa for arm S I is Gaussian, centered at r(a) and with standard deviation 0.1. The environment is chosen to illustrate various phenomenon, which we discuss after presenting the results. The algorithm Algorithm with 0, 0 R
For comparison, assuming that the random rewards belong to the [-1,1] interval, the only result for the stochastic gradient bandit algorithm [2 Lemma 4.6) that allowed constant learning rate
required that the learning rate be less than 7/- 40 40-K3/2.R5 max 128000 0.00007, where we used A = 0.15, K = 4, and R_ax = 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 Rmax to be larger, this probability falls extremely quickly, which suggests that the above threshold is generous. For the experiments we use the learning rates E (1, 10, 100, 1000]. that are several orders of magnitudes larger than T/e For each learning rate, we plot the outcome of 10 runs, corresponding to different random seeds. Each run lasts 10 el4) iterations. The suboptiiiiyyl gaps for the 4 10 cases are shown Figures La Id where they are plotted against the logarithm of time. Additional results for K = 2 arms are shown in Appendix D Note that in this example small sub-optimality implies that the optimal arm is chosen with high probability. what follows, we discuss the results in the plots.
A²
Asymptotic convergence. For the smaller learning rates of 1 and 10, all 10 seeds rapidly and steadily converge, reaching sub-optimality of -14 or less. For 7/ = 100 and 1000, most of the runs reach even small error even faster, but does not contradict the theoretical result; nor do we suspect numerical issues. As seen for the case of 77 100, even after long phase with little to progress, run "recover" (see the grey curve). In fact, it is reasonable to expect that the price of increasing the learning rate larger variance; as seen in these plots (subplots (a) and (b) are also attesting to this). Differences between learning rates are further discussed below.
"stuck" even after 10th steps. Note that this
Non- Non-monotone objective value. Using very small learning rate guarantees monotonic improve- ment (in expectation) in the policy's expected reward [24]. Conversely, a large learning rate results in con-montoonic evolution of the expected rewards {,,, T1211 even in the final stages of convergence, as can be seen clearly for the learning rates of r) = 1 and 10 in Figures Ia and Tb] For larger 7), 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 convergence. Figures la and 16 where the log-log plot has slope of nearly 11, give some evidence that an O(1/t) asymptotic rate is achieved. In general, such rate cannot be improved
8

---

subrppiindtt
-12
160
-15
-20
(a) 17
(b) 17 10.
Log sub s.b-eptiimdlity gao
Lo2 0ub 1000-ppp-maallgg
1.0
-22
-2.0
(c) 100.
(d) 1000.
Figure 1: Log sub-outine cutt-opiimliiyy gap, log (r(a") 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 subplot correspond to 10 different random seeds. Theory predicts that essentially all seeds will lead to a curve converging to zero (-oo) in these plots). For a discussion of the results, the text.,
terms of 14] Theorem gives a weaker version of convergence rate over averaged iterates (not last iterate), which is slightly worse than O(1/t). More work is needed to verify if the asymptotic convergence rate in Theorem improvable or not.
Different learning rates. Two observations can be made from Figure regarding the effect of using different 1) values: First, during the final stage of convergence when r(a") xg, = 0, using larger 7) results in faster convergence average. As v increases, the order of log (r(a") nT,r) r) also changes from e- (17 = 1). to 20 = 100), and -200 (n 1000). We conjecture that the asymptotic rate of convergence has an (1/rn) dependence. Second, using larger learning rates can take a longer time to enter the final stage of convergence. When y) = or 10, curves quickly enter the final stage of r(a") To." = 0. However, for larger values, 1/10 runs (17 100) and 3/10 runs (1) 1000) result in r(a") - TØ," values far from even after 1 iterations. These runs take orders of magnitude more iterations to eventually achieve r(a") nz. Re These situations correspond to policy me, getting stuck near sub-optimal corners of the simplex, meaning that тe (i) & for sub-optimal action E [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 platcaus in the stochastic setting remains unclear.
Trade-off's and multi-stage chracterizations of convergence. Given the above observations, there appears exist a trade-off for 7y: larger values result faster convergence during the final stage where r(a") ) To x 0. but at the the cost of taking far longer enter this final stage of convergence. Since asymptotic convergence results are insufficient for explaining these subtleties satisfactory manner, 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. 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 77 (loo t)) accelerate convergence, rather than use constant 1j ((1). This is corroborated by our experiments: As seen in Figure I 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 [4], as well as extending results for the softmax tabular parameterization handle function approximation [I]
While this work establishes surprising asymptotic convergence result for any constant learning rate, it does not shed light on the effect of different learning rates on the convergence. Moreover, our analysis is limited to multi- aumti--rmed bandits, and does not immediately extend to the general RL setting. These aspects are the main limitations of this paper.
Limitations:
Broader impact: This is primarily theoretical work on fundamental algorithm that is used broadly in RL applications. We expect these results improve the research community's s understanding of the basic stochastic gradient bandit method.
Acknowledgments and Disclosure of Funding
Jincheng Mei would like to thank Ramki Gummadi for providing feedback on a draft of this manuscript. Csaba Szepesvári and Dale Schuurmans gratefully acknowledge funding from the Canada CIFAR AT Chairs Program, Amii and NSERC. Sharan Vaswani acknowledges the support from the NSERC Discovery Grant (RGPIN-2022-04816)
References
[1] Alekh Agarwal, Sham Kakade, Jason D Lee, and Gaurav Mahajan. On theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research, 22(98):1-76, 2021.
[2] Shipra Agrawal and Navin Goyal. Analysis of thompson sampling for the multi-armed bandit problem. In Conference on learning theory, pages 39-1. JMLR Workshop and Conference Proceedings, 2012.
[3] Peter Auer. Nicolo Cesa-Biances and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2):235-256 2002.
[4] Léon Botton. Large-scale machine learning with stochastic gradient descent. In Proceedings of COMP- 2010 19th International Conference Computational StatisticsParis France, August 22-27, 2010 Keynote, Invited and Contributed Papers, pages 177-186, Springer, 2010.
Lco Breiman. Probability. SIAM, 1992.
Shicong Cen, Chen Cheng, Yuxin Chen, Yuting Wei, and Yuejie Chi. Fast global convergence of natural policy gradient methods with entropy regularization. Operations Research, 70(4):2563 2578, 2022.
Nicolò Cesa-bianchi and Claudio Gentile. Improved risk tail bounds for on-line algorithms. In Y. Weiss, B. Schölkopf, and Platt, editors, Advances in Neural Information Processing Systems, volume 18. MIT Press, 2005.
[8] Denis Denisov and Neil Walton. Regret analysis of a markov policy gradient algorithm for multi-arm arm bandits. arXiv preprint arXiv:2007.10229, 2020.
[9] Yuhao Ding, Junzi Zhang, and Javad Lavaei. Beyond exact gradients: Convergence of stochastic soft-max policy gradient methods with entropy regularization. arXiv preprint urXiv:2110.10117 2021.
[10] David A. Freedman. On Tail Probabilities for Martingales. The Annals of Probability. 3(1):100 - 118, 1975.
10

---

[11] Shivam Garg. Samuele Tosatto, Yangchen Pan, Martha White, and A Rupam Mahmood. An alternate policy gradient estimator for softmax policies. arXiv preprini arXi:22112.11622 2021.
[12] Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4)2334-2366. 2013.
[13] Sham M Kakade. A natural policy gradient. In Advances in neural information processing systems, pages 1531-1538, 2002.
[14] Tze Leung Lai, Herbert Robbins, et al. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1):4-22, 1985.
[15] Guanghui Lan. Policy mirror descent for reinforcement learning: Linear convergence, new sampling complexity, and generalized problem classes. Mathematical programming. 198(1) 1059-116,, 2023.
[16] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[17] Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, and Yuxin Chen. Softmax policy gradient methods can take exponential time to converge. In Conference Learning Theory, pages 3107-31 10. PMLR, 2021.
[18] Michael Lu, Matin Aghaci. Anant Raj, and Sharan Vaswani. Towards principled, practical policy gradient for bandits and tabular mdps. arXiv preprint arXiv:2405. 131.6, 2024.
[19] Jincheng Mei, Wesley Chung, Valentin Thomas, Bo Dai, Csaba Szepesvari, and Dale Schuurmans. The role of baselines in policy gradient optimization. Advances in Neural Information Processing Systems, 35:175 15:17818 17830, 2022.
[20] Jincheng Mei, Bo Dai, Chenjun Xiao, Csaba Szepesvari, and Dale Schuurmans. Understanding the effect of stnchasticity in policy optimization. Advances in Neural Information Processing Systems, 34: 19339-9995555 2021.
[21] Jincheng Mci, Yue Gao, Bo Dai, Csaba Szepesvari, and Dale Schuurmans. Leveraging non-uniformity in first-order non-convex optimization. In International Conference on Machine Learning, pages 3564-7564. PMLR, 2021.
[22] Jincheng Mei, Chenjun Xiao, Bo Dai, Lihong Li, Csaba Szepesvári, and Dale Schuurmans. Escaping the gravitational pull of softmax. Advances Neural Information Processing Systems, 33:21130-21 140. 2020.
[23] Jincheng Mei, Chenjun Xiao, Csaba Szepesvari, and Dale Schuurmans. On the global convergence rates of softmax policy gradient methods. In International Conference on Machine Learning, pages 6820-6829. PMLR, 2020.
[24] Jincheng Mei, Zixin Zhong, Bo Dai, Alekh Agarwal, Csaha Szepesvari, and Dale Schuurmans. Stochastic gradient succeeds for bandits. arXiv preprint arXiv:240..17235 2024.
[25] Arkadi Nemirovski. Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic ap- proximation approach to stochastic programming. SIAM Journal on optimization, 19(4):1574-169, 2009.
[26] Long Ouyang, Jeff Wu, Xu Jiang, Diogo Almeida, Carroll I. Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, al. Training language models to follow instructions with human feedback. arXiv preprint arXiv:2203.02/55 2022.
[27] Rafael Rafailov, Archit Sharma, Eric Mitchell, Christopher D Manning, Stefano Ermon, and Chelsea Finn. Direct preference optimization: Your language model is secretly a reward model. Advances in Neurul Information Processing Syxiems, 36, 2024.
[28] Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals mathematical statistics, pages 400-407, 1951.
[29] John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference on machine learning, pages 1889-1897, 2015.
[30] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.063477 2017.
[31] Richard S Sutton and Andrew G Barto. Reinforcement Learning: An Introduction. MIT Press, 2018.

---

[32] Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. Advances in neural information processing xystems, 12, 1999.
[33] William R Thompson. On the likelihood that unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3-4):885-994, 1933.
[34] Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning Machine learning, 8:229 256, 1992.
[35] Jingfeng Wu, Peter L Bartlett Matus Telgarsky, and Bin Yu. Large stepsize gradient descent for logistic loss: Non-monotonicity of the loss improves optimization efficiency. arXiv preprint urXiv:2402.1992 2024.
[36] Rui Yuan, Robert Gower, and Alessandro Lazaric. general sample complexity analysis vanilla policy gradient. In International Conference on Artificial Intelligence and Statistics, pages 3332-3380. PMLR, 2022.
[37] Junyu Zhang. Chengzhuo Ni, Csaba Szepesvari, Mengdi Wang, et al. On the convergence and sample efficiency of variance-reduced policy gradient method. Advances in Neural Information Processing Systems, 34:2228 2240, 2021.
[38] Junzi Zhang. Jongho Kim. Brendan O' O'Donoguue, and Stephen Boyd. Sample efficient reinforcement learning with reinforce. arXiv preprint arXiv:2010. 1364, 2020.
[39] Kaiqing Zhang, Alec Koppel. Hao Zhu, and Tamer Basar. Global convergence of policy gradient methods to (almost) locally optimal policies. SIAM Journal Control and Optimization, 58(6):3586 3612, 2020.
12

---

A Asymptotic Convergence
Lemmal 1 Using Algorithm with any constant v) E ((),, (a) < oo for an action a E then we have, almost surely,
[K],
sup 0c(a) 00, and inf (,(a) > -00. 22
(21)
Proof. Suppose No (a) so for an action [K]. According Algorithm
1) (1 (0- (a)) Re(a), (4+((a) 0.(a) { -1n no. (a) Ra(()), otherwise,
(22)
and let
[1, if
I(a)=
(23)
0, otherwise.
According to Eq.
22 we have, for all 2 1,
[-1
t-1
(a(a) (1(a) Σ ((a) n (1 T0-T,, (a)) R.(a)
Σ
(1))( -(-n) (a) (as))).
(24)
Using triangle inequality, we have,
(0.(a) - (a)) S La(a) 7 (1-mo,(a)) (a)) Ra(a) + Σ
lo(a)) (-1)) (a) R (as)
(25)
S 1) Rmax
E1(a) + Ruax Σ (a)
(26)
s=1
1) Rmaxx (Ni-1(a) Σ Tg, (1))
(27)
By assumption, we have,
(a) = lim (a) < co.
(28)
10000
According to the extended Borel-Cantelli Lemma we have, almost surely,
To, (a) = lim
(a) < co.
(29)
t+000
s=1
Combining Eqs.
25
28 and
29
we have, almost surely,
sup (0)()) - (a)) < xo,
(30)
121
which implies that, almost surely,
sup (0((a) S sup (a(a) 0, (a)) + 10 (a)l <0.
Lemma (Avoiding lack of exploration). Using Algorithm 1 with any O(1), there exists least a pair of distinct actions i E [K] and i * j. such that, almost surely,
Noc (i) oo, and No. (i)
(31)
13

---

Proof. First, we have, for all t 2 1,
Ia(a)
Σ aE[K]
I((a) for all 2 21)
(32)
==1 DE[K]
Σ
Σ
Tx(a)
(33)
aE[K]
Σ
(a)a)
(34)
[E[R]
By pigeonhole principle, there exists at least one action i [K], such that, almost surely,
(i) lim (i)
(35)
We argue the existence of another action by contradiction. Suppose for all the other actions j E [K] and j * i, we have (j) < co. According to the extended Borel-Cantelli Lemma we have, almost surely,
Σ no (J) = lim Σ
no, (J) < 0o.
(36)
t1000
s=1
According to the update Eq. (22). have, for all 2 1,
t-1
0.(1) - (1) = Σ 1. no, (1) R1(
Σ (1 - [.(i)) (-n) (1) Ro(as).
(37)
By triangle inequality, we have,
(0,(1) 0,(1) S Σ 1(1) 7- mo, (1)) Ri( (1))
+ +
(l-),))) (-n) To, (1) R. (a,)
s=1
(38)
[-1
< 1) Rmax
- (1-T0, + Rmax
(1- I.)))
(39)
aml
a=1
1-1 ΣΣ 4())
= 1) Rmax
To, (1) +
(40)
==1 J#C
= T) Rmax
Te, (1) + Σ N1-
(41)
Combing Eqs.
36 and
38
and the assumption of No N)) < 00 for all j * i, we have, almost surely.
sup (0((i) s sup (i((i) (1) + (i) oc. 121
(42)
t21
Since (J) < 0o for all j # i by assumption, and according to Lemma we have, almost surely, sup (0. < co.
(43)
Combining Eqs.
42 and (43 we have, for all action E [K]. sup (+((a)) < oc,
(44)
which implies that, there exists c > and c E 0(1), such that, for all a E [K].
(a)) Eve(k (xp(),(a')]
inf Te. (a) [21
inf t21
20>0 0.
(45)
14

---

Therefore, for all action
[K],
Te (a) = lim
Te, (a)
(46)
t=1
s=1
lim
(47)
lim c t1000
(48)
xc.
(49)
According to the extended Borel-Cantelli Lemma 3 we have, almost surely, for all action a E [K]
No (a) = xC,
(50)
which is contradiction with the assumption of Noo (j) oc for all the other actions j E [K] with j f i. Therefore, there exists another action j E [K] with j + i, such that Noc (i) 00.
Theorem 1 Let K and r(1) r(2). Using Algorithm [ with any 7) E ( we have, almost surely, To, (a") + as t - oc, where a" == arg max r(a) (equal to Action 1 in this case).
Proof. The proof uses the same notations as of [24] Theorem 5.1].
According Lemma 2 we have, .N (1) and Noo (2) co, i.e., both of the two actions sampled for infinitely many times as - oc.
Let F& be the o-algebra generated by 01, (a1), a1-1, R R
F. =o=a(aan Rí (a1). ... 44- R (a:1(())))))
(51)
Note that 0, and I, (defined by Eq. (23) are F.-maauurable for all t 2 1. Let [ denote the conditional expectation with respect to F,: [x[X] B[X[FF]. Define the following notations,
Wr(a) == 0,(a) -
("noise")
(52)
P((a) E, (0 (.(a). ("progress")
(53)
For each action [K], for t 2 2, we have the following decomposition,
(a) = (a(a) + P:-1(a) ( (c-1(a))
(54)
By recursion we can determine that,
t-1
(a( = (() + Σ
W. (a) + Σ Pa(a),
(55)
8=1
while we also have,
(a(a) (a) [[0 E(0 0 (a)).
(56)
(i(a)
and [a)] accounts for potential randomness in initializing 01 E RK According to Proposition we have,
(a) = E, (0 - (a) = (0) (r(a) - _T,r)
(57)
which implies that, for all t 2 1,
Pe(a") > 0> P2(2).
(58)
Next, we show that E.= Pa(a") + as + co by contradiction. Suppose that,
Σ Pi(a*) < 00.
(59)
15

---

For the optimal action a² = 1,
Σ Ps(a") = Σ n1 To, (a') (r(a") - mTo r)
(60)
= 11 A
TB (a") (1 - Te_ (a)));
(61)
==1
where A = r((a") maxayaa r(a) r(1) r(2) 0 is the reward gap. Denote that, for all 2 1,
Vi(a") = 5
Te, (a") (1 To, (a))).
(62)
18
According to Lemma [ (using Eqs. (58 to (6)) and 62 ). we have, almost surely,
sup
[0r(a") < 00.
(63)
121
For the sub-optimal action (Action 2), we have,
Σ P2(2) Σ n To, (2) (r(2) - -xØ,r) r)
(64)
11 A Σ To, - (1 Tn, (2))
(65)
Σ Pa(a"),
(66)
and also denote, for all t 2 1,
5
(2(2)
Σ no. (2) (1 To, (2)) Vi(a*).
(67)
18
According to Lemma (using Eqs.
(58
55
(64
and 67 ), we have, almost surely,
sup 121
(2)2)
< Co.
(68)
Combining Eqs.
63 and 68
there exists
0 and E 0(1), such that, for all a E {a", 22).
(x))
inf no (a)
inf 121
E (xp'),(a')] 20>0, 0.
(69)
which implies that,
Σ 1=1
To, (a") (1 (a))) = lim
Te,
(a") (1 To, (a"))
(70)
8=1
lim
c.C
(71)
lim t t.c 1+00
(72)
xc,
(73)
which is a contradiction with the assumption of Eq. 59
Therefore, we have,
Pa(a*) - 00, as t
(74)
According to Lemma (using Eqs. (58)
60
and 74 ), we have, almost surely,
0,(a") as t D0.
(75)
16

---

Similarly, according to Lemma 10 (using Eqs. (58).
64
667
and 74
we have, almost surely,
lim (2)
(76)
1-000
Note that,
1T. (a")
TT, (a")
(77)
Tw. (2) + To, (a*)
(78)
exp(Or(2) - 0 (a)) +1
Combining Eqs.
75 to 77
we have, almost surely,
To. (a") L, as & + oc.
Theorem Under Assumption 1 given K 2 2, using Algorithm I with any v) E ((), we have, almost surely, Te, (a*) + as t 7 0o, where a" = arg [c[]] ((a) is the optimal action.
Proof. Similar to the proof of Theorem define F; to be the o-algebra generated by a1, R1 (a1). ". 0t-1, 1e-1(ax)))) (1)-1) i.c.
F a (11))) ... ,4-11 R(-((r-))))))1)
(79)
Note that Og and I, (defined by Eq. (23 F.-meauurable for all / > 1. Let E,[]] denote the conditional expectation with respect to Fi: [, [F) Define the following notations,
Wr(a) (a) E ( (0)),,,
("noise")
(80)
Pa(a) == E, [a)] - (a). ("progress")
(81)
For each action a E [K], for / 2 2, we have the following decomposition,
(a(a) (a) + Pt-1(a) + (a))
(82)
By recursion we can determine that,
[-1
(a(a) E (a)
W, (a) Σ P.(a).
(83)
while we also have,
0, (a) (a) B(0 ( (a)),
(84)
Wi(a)
and [a)] accounts for potential randomness in initializing 01 RK For an action [K],
(+ = {at + E [K] : +((at>>))))))))>>) > r(a)),
(85)
(a = {a- E [K] rraaa(a)))))))) < <(a)).
(86)
Define Ass the set of actions which sampled for infinitely many times as co, i.e.,
Aso = {a [K] (o) = zo.
(87)
First part. We show that Noo (a") = xo by contradiction.
Suppose a" & Abc i.e. Noo(a") (a") < xo. According to Lemma 2 we have, |Abol > 2. Since a" & Asc
by assumption, there must at least two other sub-optimal actions i, E [K], i1 + iz, such that,
(1,) = Noc (12) = 0c.
(88)
In particular, define
i1 == arg min r(a), Re(K), No (0)=00
(89)
12 == arg max r(a). K)(K), (a)=o
(90)
17

---

Using the update for arm 81. we know that, for all 8 2 1,
Pa(11) 77 To, (i1) (r(61) - _0.r)
991)
By definition and because of Assumption 1 have that r(i1) r((2) <((a)) Furthermore,
according to Lemma 6 we have, for sufficiently large T 2 1,
r(i1) < =g."" < r(12),
(92)
which implies that after some large enough 2 1,
Σ Pa(i1) = Σ Te, (i1) ((((1)) - TØ,
(93)
==
< 0.
(by Eq. 92
(94)
r(i1) -T.
T r
Σ Te, (a) (r(i1) - r[a)]
azin
Σ
(at -r(z))
Te, Te,
(r(i)) (((()) r(a
(E)
aTEA-(i) (i)
(95)
From Eq. 89
we have,
Ax SA (i))
(96)
which implies that, for all a (i)) we have,
(a <00.
(97)
Note that, by definition, is A+ (11), and
(12 co.
(98)
In order to bound Eq. 955 using the above relations, note that,
(a_)
Σ
En Caled!(h) (1) (a= (r(at)-r(in) (r(in) - r)
(99)
--E-((1) (b)
(a)
(r(h) r(a-))
To, (12) (r(12) r(1)))
EA (i)
(Fewer terms in the denominator)
By Lemma 5 for large enough
2 1. for all a= no, (a,
r(tz)-r(i)) -())-r(a))
Hence,
no, (1g)
(
1
r(i2) - r(11)
r(i)
r(a=)
(100)
2 [A (i)) r(11) r(a-)
r(12) r(11)
EA (41
1
(101)
2
Σ
T0, (a
(r(11) - r(a
r(a ))
1
Σ
no, (at) (r(a+)--a))) - r(11)).
(102)
2
EA (61)
atEA (b)
Combining Eqs.
94
95
and 102 we have,
Po(1) Σ n To, (fz) (r(()) nT.r)
(103)
<
7
T0, (i1)
(at) (r(at) -((h))
(104)
2
ateAt (61)
71 A
no, (i1)
Σ
To, (a+)
(105)
a+t)+(i))
18

---

where
min
[r(()
r(i) > 0.
(by Assumption T
(106)
Bounding the variance for arm i1, we have that for all large enough 7 2 1.
t-1
vi(in) =
Σ no. (i1) (1 To, (11))
(107)
18
ne, (i1)
Σ
Ta,(a))
Σ
To, (a+)
(108)
18
a EAAAA()) (11
a+EAt (i1)
Using similar calculations as for the progress term, we have,
Te. (a=
To, (o, (a")
Σ
(Fewer terms in the denominator)
En EateAt(i)) To. TT. (at)
TR. (i2)
(A)
EAE
By Lemma for large enough T 2 1, for all a
(o.
Hence,
ne, (12)
5
A
13
1
(109)
5
A
(i1)
(-EA-(M1
13
(110)
Σ
To, (a
13
Σ
Ta, (a+)
(111)
EA
(i1)
(+))
Combining Eqs. 1008) and 1111
we have that for large enough 7 2 1,
5
Vi(ii)
no, (i1) (1 no, (f1)
(112)
18
ma, (i1)
Σ
ne, (a+).
(113)
atEAt (61
According to Lemma 12 (using Eqs. (4).
105 and 113
we have, almost surely,
sup (11) < cc.
(114)
(21
Since (a) < oo by assumption, and according to Lemma 1 we have, almost surely,
inf 0,(a)) > -00.
(115)
22
Combining Eqs. [114 and (15), we have,
ne, (i1)
sup
sup (xp()(((i) 0,(a")) <0.
(116)
121 Tg. (a*)
t21
On the other hand, by Lemma we have,
sup To, (i1)
(117)
To, (a*)
which contradicts Eq. (16). Hence, the assumption that Noo < oo cannot hold. This completes the proof by contradiction, and implies that Na)(a")
19

---

Second part. With a' E Ab i.. (a*) = oo, we now argue that To, (a*) - as t + oo almost surely.
According to Lemmal 2. we have, | 2 2. Since a" E Ace by assumption, there must be at least one sub-optimal action [K] with r(61) < r(a"), such that,
No oo.
(118)
In particular, define
11 = arg min r(a). K] (a)=00
(119)
According to Lemma we have, for all sufficiently large T 2 1,
r(i)) <
(120)
Using the same arguments in the first part (except that ig in Eq. 98 is replaced with a*), both Eqs. (T05) and (133) hold.
Next, we argue that E.sr Te, (b1) Eu-at(h))) (at) + oc as t + oa by contradiction.
Suppose
0
Σ
no (11)
Σ
To, (a+) < oo.
(121)
EA (6)
According to Lemma g
(using Eqs.
94
105
113
and
121 ) we have,
sup
(i,)
< 00.
(122)
t21
Calculating the progress and variance for arm a", for t Z 1,
Pi(a") n7 Te, (a") (r(a") - n r) 2 " A no, no,(aa) (a") (1 - [1- (a")). (A (A= = (A=r(aa))
(123)
max r(a)) aza"
(124)
2.
(125)
Denote that, for all t 2 1,
[-1
5
Vi(aa)
To, (a") (1 To. (a*)).
(126)
18
According to Lemma 11 (using Eqs. 123 and (26))), we have,
inf (,(a)) -00.
(127)
Combining Eqs.
122 and (17 we have,
ne, (i1) 12
sup
supexp(0((i)) 0,(a")} 00,
(128)
To. (a*)
t21
For all 1, (4)) < and since there is at least arm (a") s.t. infazı 0((a) > -00 there exists c > 0 and c E O(1), such that,
sup To, (i1) < 1 2c. (21
(129)
According to Eq. 118
we know that Noc (i1) co and for all a E AT (A1), Noo < co.
Using Lemma we have, for all large enough 2 1,
xa, ---I| no, (b1)
To, (a
Te. (i1) +
Σ
To, (at) = - To. (ii)
> 1 - (ii) (130)
To, (ii)
atEdt(iL) (i1)
a aTEA- (i)
=
(i1) +
Σ
To, (a+)))))))))) > 21 ccc.
(131)
(t))
20

---

Combining Eqs.
129 and 131 we have, for all large enough & 2 1,
Σ
To. To.(at) 2 c,
(132)
a steA+(i))
which implies that,
To, (i1)
Σ ab)
To.(at)
2
no, To. (11)
(133)
00,
(since No (ii) oc and by Lemma 3
(134)
which contradicts the assumption of Eq. therefore, have,
121
This completes the proof by contradiction, and
Σ (i)
Te, Te,(a*) (a+) + 00, as + 20.
(135)
at (11)
According to Lemma
10 (using Eqs. TO5
and 135 ) we have, almost surely,
0, (i1)
as t -> D0.
(136)
Combining Eqs. 127 and 136), we have, almost surely,
To. (a") exp(O((a") 0c(ii)) 00, as 00.
(137)
TT, (i1)
Hence, we have proved that if (11 oo and r(4)) < प.े < r(a") for sufficiently large T 2 1, (e") then, no, (in) 00, as + co.
In order to use this argument recursively, consider sorting the action indices in Abs according to their descending expected reward values,
r(a") > r(t 1-1 r(1 r(12) r(1).
(138)
We know that,
Te.
(12)
Σ
Ta, (a) (r(a)= - r((2))
(139)
To. (a] ((())((((a))))) (r(a-) - r(i2)) +
Σ
To, (at) (r(at) r(12))
EEA--11 (1z)
(tt)+(ia))
(140)
> no. (a") (r(a*) -r(iz)) - Σ
Ta, (a ((((1)) - r)
(141)
a-EA- (12)
= (a") ((())) -
Te (a
(F(1z) - r(a r(a-))
(142)
no, (a*)
a EA -EA-Aii (iz)
According to Lemma for all a E EA-(i2) with a i1, we have,
na (a")
oc, as co.
(143)
To, (a
Combining Eqs. 137) and (143). we have, for all a- - EA-((22)
no, (a*)
xc, as + co.
(144)
no. (a
Hence, for all sufficiently large 7 > 1, for all a= E A- AT12),
To. [a [a
1
r(a") - r(2)) r(i2)
(145)
To. (a*)
2 21A-(i2)
r(aa)
21

---

Combining Eqs. 142 and 1155 we have, for all sufficiently large 2 1,
r(i2) > ne, (a") r(a") - -r(iz) > 0.
To.
(146)
Hence we have, for all sufficiently large 2 1,
r(i2) < ng. < r(a")
(147)
Comparing Eqs. (20 and 147 we can use a similar argument for is and conclude that, for To, (a" ne, (ta)
sufficiently large 1, then,
00, - co. This further implies that
r(is) ने. <r(a").
(148)
Continuing this recursive argument, we have, for all actions Aso with a + at,
na, (a*)
oo, t
(149)
T0, (a)
Meanwhile, according to Lemma 5 we have, for all actions A
no, (a*) + co, as + oc.
(150)
Te, (a)
Combining Eqs. (19 and 150 we have, for all sub-optimal actions E [K] with r(a) < r(a*),
(a)) Te, (a)
+ 00, as t - oc.
(151)
Finally, note that,
Te, (a*)
To, (a*)
(152)
Ene[K]: r(a)<r(a-) To, (a) + To, (a*)
(153)
Σee[K]: r(a)<r(a)) ne, (a*) +1
(a)
Combining Eqs. 151) and 153 we have, almost surely,
To. (a") L, as t 0o.
22

---

Vn + B Miscellaneous Extra Supporting Results
Lemma 3 (Extended Borel-Cantelli Lemma, Corollary 5.29 [5]). Let (Fa)n21 a filtration, A, E Fn. Then, almost surely,
{w An infinitely often
P(An)Fn) P(An)Fa)= =00
(154)
Lemma 4 (Freedman's inequality [0 7. Theorem C.3 of (24)
Ler X1, X2,... be sequence of
random variables, such that for all 2 1, [X,] < 1/2. Define
Sn Σ
X Xt and Vn =
Σ
X,-]].
(155)
Then, for all 8 666 O,
4
())
Pr 3n: Sn 6
Vn +
log
+ 2 2og
log3 8 (156)
8
Lemma 5. Using Algorithm 7 for any two different actions i,j [K] with i # j. if No0 (1) oo
and Noc (j) < oo, then we have, almost surely,
To. (1)
sup 21 To (j)
(157)
Proof. We prove the result by contradiction. Suppose
no, (i) sup 2i TT, (j)
oo.
(158)
According to the extended Borel-Cantelli Lemma B we have, for all [K], almost surely,
Σ (21
no, ()) = 00 (N) = =o0)
(159)
Hence, taking complements, we have,
1E <0)x))))) (Nx oo)
(160)
also holds almost surely, which implies that,
no, (1) = xc, and
(161)
To. (j) < oc.
(162)
[=1
Therefore, we have,
20
8c
30 (i)
no, (1)
no. ())
(163)
T8, (i)
Te. To.()
(164)
1=1
00;
(165)
which is contradiction with Eq. 161
23

---

Lemma 6. Using Algorithm 7 we have, almost surely, for all large enough t 2 1,
r(i1) < To r < r(i2),
(166)
where 11, d2 E [K] and i1 + 12 are the action indices defined as,
i arg min r(a), [], Noo =o)=oc
(167)
12 arg max r(a).
(168)
K]
Noo =a)=oc
Proof. Define Ax as the set of actions which are sampled for infinitely many times t 00, i.e.,
Abs = {a E [K] (a) = =0)--
(169)
According to Lemma have | 2, which implies that * i2-
Given any sub-optimal action i E [K] with r(i) < r(aa), we partition the remaining actions into two parts using r(t).
(1) = fat E [K] : r(aa)) > r()) AT = fa E [K] r(aa) r())
(170)
(171)
By definition, we have,
Asc S CAt(i) U ( and
(172)
Ax C (f2) U (12)-
(173)
First part. r(1) T..
If rf1) = [ r(a), i.e., i is the "worst action", then r(i)) nH. holds trivially. Otherwise, suppose r(61) * min r(a). We have,
-Ø. - r(ii)
Σ
To, (a+) (r(a*)- r(i)))
Σ E-EA-(11)
(a (r(i1) - r((aa)) ))-
(b)
(174)
Consider the non-empty set Aso n 11+ (ii)... Pick an action ji E Aso n (Ai),, and ignore all the other actions at A+ (11) with at * fu in the above equation. We have,
TB. r(h) > ne, (hi) (r(11) r(h))
Σ
na,
(r(i1) - r(aa))
(175)
EA
(41
To, To,(a)
= (h) r(1)) - ri(1))
Σ
(r(i1) - r(a r(a-)))
(176)
Te. (i))
EA (it)
where the first inequality is because of r(a+)))))))))))))) r(,,) > 0 for all at e (ti) by Eq. 170). Note that No (j1)
and (a < co. According to Lemma 5 we have, for all large enough 2 1,
Σ
To (a
(r(()) -((-))
Σ
(r(i1) - -((a /
To, (hi To. (a-)
(177)
To, (51)
EA (i1)
EA (h)
-(j)--(( - r(i)
Σ
(r(11) - r(a-))
(178)
[A-(i1)
r(i1) - r((a) 2
a EA (i1)
r(i) - r(i1)
(179)
2
Combining Eqs. 175 and 177 we have,
N.. r(12) > ne. (i)) r(1)) -r(1))
0.
(180)
2
24

---

where the last inequality is because ji E A (61). Second part. ~े.r < r(i2).
The arguments are similar the first part. If rii2) r(aa), i.e., i2 is the optimal action, then Tg.7 r r(i2) holds trivially. Otherwise, suppose r(i2) # r(aa). We have,
r(12) nØ.
E EA (62)
no, (a . r(a
Σ
To, To, (r(at) - r(i2)).
alEAl (is)
(181)
Consider the non-empty set Asc nA (A-())). Pick an action f2 E Age nA (12), and ignore all the other actions a E EAT (i2) with # j2 in the above equation. We have,
r(i2) पØ. 2 To, (52) (r(12) r(i2))
Σ
Te.(a") (r(a*) - ri(1))
(182)
a+)++(a)
To,(at)
= (i) r(i2) - r((z)
Σ a (+t)+
(r(at) - r(()))
(183)
To, (J2)
where the first inequality is because of r(i2) - r( 0 for all a E A (iz) by Eq. 170). Note that Noc (J2) = and (a+) < co. According to Lemma we have, for all large enough >
Ta, (a+) (r(aa)) - r(12)) =
no, (f2)
Σ
(r(at) - r(bz))
(184)
To, (iz)
(f2)
(at)
atEAt
atEA
(ia)
Σ
(r(at) - r(12))
1
r(i2) r(j2)
(185)
(12(
r(a+) - r(12)
atEAt (1z)
r(12) r(j2)
(186)
2
Combining Eqs. 182 and 184). we have,
r(i2) r(j2) 0,
r(i2) पØ.r 2 no. (f2)
(187)
where the last inequality is because ja E A A (12).
For the following lemmas, we will use the notation defined in the proofs for Theorems I and 2
Lemma 7 (Concentration of noise). Given an action a E [K]. We have, with probability at least 1- 6,
Vi(a) +1
vt
W Ws+1 (a)
< <36 17 Rinax (Vi(a) + 4/3) log log
12 1 Reuax log(1/5) + 8 17 R log 3,
(188)
where
Vi(a) =
Σ
no, (a) . (1 (1- (a));
(189)
18
and
Wi(a) 0,(a) [0.(aa)
(190)
is originally defined by Eq. 52
Proof. First, note that.
E, (. (a)) = 0, for all t 2 0.
(191)
25

---

Using the update Eq. 22 we have,
W4+1(a) = ( E, [
(192)
=0:(a) + +1 (Le(a) No. (a)) Ra(aa) - (0:(a) + no. (a) (r(a) - vo,r))
(193)
=1- (I((a) To, (a)) (a) n To, (a) (r(a) - n..,))
(194)
According to Eq. | we have,
[e+1(a)] S 3n Rmax.
(195)
The conditional variance of noise is,
VarlWe+1 == E. (.((W++(a))
(196)
s 2 [E(((a(a) na, no, (a))² R.(ax))) + 2 + No, (a)² (r(a) To,r)²
(197)
where the inequality is by (a b)2 2a² + 2b2. Next, have,
(a((I(()) (a)) [ = (a) (1 - ==(a))² r(a)² + Σ To, ==(a²² r(d))²
a'sta
(198)
S R
(T((a)) (1 - (a)))) (1 =e(a)) =e(a)?)
(199)
R2
TT, (a) . (1 - nT. (a)),
(200)
and,
(r(a)
T
Σ
To, (a)) (r(a) - r(a'))
(201)
t'
Σ To, (a') |r(a) r(a')
(202)
a'za
< 2 Rmax
Σ To. (a))
(203)
a'za
= Rmax (1 - no, (a)).
(204)
Combining Eqs. (16).. (198) and (001). we have,
[Fr Fi] n
R2 (a) (1-
(a)) (1-me((a)) 172 R Te, (1 TT. (a))2
(205)
10 12 R ne, (a) (1 To. TT. (a)).
(206)
Let (1+1(a)= = (a) 6 Runas
Then we have,
[(41(a) S 1/2, and
(207)
Var (a))
< 18 Te, (a) (1 NT. (a)).
(208)
According to Lemma
there exists event & such that Pr(E)) 2 1 - 8, and when E, holds,
Σ Xx.i(a) 5 /0//vv// (v/la)+4433)bbg
Ve(a) +1
Vt:
+ 4/3) log
+ 2 log(1/6) +
3 log (209)
which implies that,
Ve(a) +
Vt Σ (a+i(a)
< 3361 Rmax (Vi(a)+ + 4/3) log
+ 12 Rmax log(1/5) + 8 nn Rmax log 3,
(210)
where Vi(a)=
3.
E'=1 To. (a) (1 Te, (a)).
18
26

---

Lemma 8 (Bounded progress), For any action E [K] with No (a) oc, if exists e >> 0 and oc, such that, for all t 2 T,
Σ Pa(a) c Vi(a),
(211)
where Ve(a) is defined Eq.
189
and if also
Pr((a) < <00,
(212)
t=1
then have, almost surely,
sup 0c(a)] oc. (21
(213)
Proof. According Eq. (55) and triangle inequality, we have,
0.(a) s [[0 + Σ Wa(a) + Σ P. (a)
(214)
1=1
According to Lemma] have, for all & 2 r
7 there exists an event ε such that Pr(Ei) 2 and when & holds, we
VV-1(() +
Wa(a) S 36 1l Rmax (V--1(a) + 4/3) log
+ 12 v Rmax log(1/0) + 8 vn Rmaa log 3.
5
(215)
According to Eq. 212 as 1 ->
Σ
Pa(a)
$ Σ
P.(aa) < 00.
(216)
s=1
According to Eqs.
211h,
215 and 216 we have,
W, (a)
< x0.
(217)
Combining Eqs.
214). 216 and 217). we have, as t + 00,
(0(() < 00.
(218)
Take any w E E = {Noc (a) 00). Because P(E (EN&)) < P(2) & < 8 - we
have that P-almost surely for all w E E there exists 8 > 0 such that w E &n E while Eq. 215) also holds for this 5. Take such a We have, almost surely,
sup (e(aa) < cc. (21
Lemma (Unbounded positive progress). For any action a E [K] with Nao(a) -o, if there exists >> and T < 2o, such that, for all 1. T.
Pi(a) > 0, and
(219)
Σ Ps(a) 2 Vi(a),,
(220)
where Vila) is defined in Eq. 189 and if also,
x
Σ Pi(a) = x0,
(221)
then we have, almost surely,
0c(a)= + 00, ast 00.
(222)
27

---

Proof.
According to Eq. (5
- =(aa==B01 [a) (a) +
W. (a) + Σ P.(a).
(223)
8=1
s=1
According to Lemma]) 7 there exists an event & such that Pr(E1) 2 have, for all & 2 r + I,
8, and when & holds, we
(a) +
Wa(a)= 2 336/ 1) Rmax / (Vi-1(a) + 4/3)) log
- 12 r Rmax log(1/5) 888) v) Remax log 3.
6
(224)
By Eq. 221 as t + 00,
(P(a)
(225)
and the speed of 2 Pa(a) - oo is strictly faster than + oo, according to Eq. 220 This implies that (a) + oc, result of "cumulative progress" dominates "cumulative noise".
Take any w E = {No (a) )o). Because P(E (En&))) S P(2) \ &n < 6 -
we have that Plalmost surely for all w E & there exists 8 > 0 such that w E E & while Eq. 224 also
holds for this 8. Take such a We have, almost surely,
02(a) + 00, l xc.
Lemma 10 (Unbounded negative progress). For any action a E [K] with No. (a) = co, if there exists > 0 and r < co, such that, for all T.
P((a) < 0, and
(226)
Ps(a) 2 c. Vi(a),
(227)
where Ve(a) is defined in Eq.
189 and if also,
Σ P:(a) -00,
(228)
t=
then we have, almost surely,
0e(a) + -00, as + 0o.
(229)
Proof. The proof follows almost the same arguments for Lemma
Lemma (Positive progress). For any action E [K] with Noo (a) = oo, there exists e >> 0 and
< such that, for all t 2
P((a) > 0, and
(230)
Σ Pa(a) c. Vi(a),
(231)
where Vi(a) is defined in Eq. (189 then we have, almost surely.
inf Oc(a) 0c.
(232)
Proof. First case: if Dee Pa(a)= < oc, then according to Lemma we have, almost surely,
sup (a(a)) oc,
(233)
which implies Eq. (222).
Second case: if - Pr(a)= oo, then according to Lemma (z(a) - 20, oc,
9 we have, almost surely,
(234)
which also implies Eq. 232
28

---

Lemma 12 (Negative progress). For any action E [K] with (a) = oc, if exists >> 0 and oc, such that, for all t 2 T,
Pr(a) 0, and
(235)
P.(a) Vi(a),
(236)
where Va(a) is defined in Eq.
189 then we have, almost surely,
sup
(((a)
(237)
22
Proof. First case: - Pi(a) < oc, then according to Lemma we have, almost surely,
sup
(e(a)] oc, 2
(238)
which implies Eq. 237 p.
Second case: if Ei=1 Pa(a) oc, then according to Lemma 10
we have, almost surely,
(a(a) -> - -0, as oo,
(239)
which also implies Eq. 237
29

---

C Rate of Convergence
Theorem
3 For a large enough 0, for all T 7, the average sub-optimality decreases at an
0 (T)
rate. Formally, if a" is the optimal arm, then, for constant
E r(a") (TasT) T
S c (T)
T
Proof. The progress for the optimal action is,
Pi(a") 17 Te, (a") (r(a") - TT. 2 1 A no, (a*) (1 To, (a*)).
(240)
(A = r0ar((a)
max r(a)) aga"
(241)
2 0.
(242)
Since lom Ne, (a*) = 1, we have for all large enough t 2 1,
To. (a.(a)) ) 1/2.
(243)
Since Na) = (Theorem and | 2 2 (Lemma we have,
2o
20
Σ (1 ,e(a")) Σ
Te (11) co,
(244)
where (11) 2o and r(i)) < r(a"). Therefore, we have,
Pa(a")= = xc.
(245)
The variance of noise is,
5
[-1
Vi(a") =
Σ
no. (a") - (1 -a. (a'),
(246)
18
which will be dominated by sum of Pr(a*) since Vi(a*) appears under square root (Lemma 7 Therefore, for all large enough / 2
(,(a") 2 C. E (a"))
(247)
On the other hand, we argued recursively (in the proofs for Theorem 2 that for all sub-optimal action E [K] with r(a) < r(a"),
Sup0r(a) < co.
(248)
121
Therefore, we have, for all large enough 2
- -((a) 2 C. Σ (1 - (a)))),
(249)
S=
which implies that,
Σ -xp()((a)(((aa)}+ 1) 11) exp { -c. Σ (11=x((aa)) (a()'))
1
((('')) s (K-1)
(250)
a
Therefore, we have,
1 =T((a)) 5
1 1- 1-T((a")
=t(a)
S (K- 1) exp
- -C. -c- (1
1-1
=((0))) (251)
aa(aa) agaa
Te(a*)
30

---

Using Lemma 15 with En = - - -==x(aa))) > 0, 2n+1 = ='er (1-x > -0 C>
and B K I
gives us that for all f T,
Σ (1- x)-))(aa)) - + x²²
1
(252)
12C
where M max In((K 1) C)), 11- -T
Finally, we use Eq. (252 to bound the average sub-optimality, For any s 2 T and T T,
r(a") (T Σ Tr(r(a") r(a)] $ Rmax (1 Tz(a")).
(Since r(a) E -- Rmaxx Rmax))
Summing from ==
Ex r(a") (TaiT)
2 Rmax
x² In(CT+ + 13C
T-T
Lemma 13. Let {yn} be the solution to the difference equation Un+1 = yn + Be with B 2 1, c > O and yo 2 max(B, 1 In(B c)). Let { be nonnegative valued sequence such that æg S yo and xn+11 S In Be-eaa czn for all 0. Then, In I for all 2 0.
Proof. Define the function f(y) = maxf# + -e : OOSS S y Clearly, f is an increasing function of its argument.
Claim: For y 2 max(B, ln()))), f(v) = y + Be cy To prove this claim, for a IR define
giz) == Be
(253)
Function is increasing on ( In([ x)) and decreasing on (-x, In(Be)).
If < 1/a, ! (n())) < 0, hence is increasing on oo). Hence, f(v) = g(v), proving the claim.
If c 2 1/B, then 1 [i(Be) e) 2 0. Hence, g is decreasing on (0, 1/cll////ee))) and then increasing on (1/el((Be)) c)). Since 2 1 In(B c), f(v =
g(v)). Since we also have y 2 B In(Bc), g(v) (BB) B g(0) and thus fv) = 9(v), finishing the proof of the claim.
The difference equation for Un is yn+1 Yn B -yM, Since yo max(B, 1 In(Be) e)) and yı. is apply the equality from increasing, have yn mmx (B, ! In [ c)) for all Therefore, the previous claim to get
Dn+1 Vv Be -y. cy [(yn)
The sequence (xr) satisfies the inequality xn+1 S on + Be S ((x)).
Now, let us prove Vn, yn using induction. The base case is 30 S yo (given). Assume z S ye
for some & 2 0. Since f is increasing, I& S implies f(Ix) < f(w). Using the properties
Ik+1 S. fxx) and f(x) yk+1. we get 26+1 f(xx)= S f(yx) Mi+t1 By the principle of mathematical induction, In S yn for all n 2 O.
Lemma 14. Let > and B 2 1. and let {yn 1 be a sequence defined by the recurrence relation
Ynt1 = yn + Be -y.
s.t. 9o max(B, ln(Be)) Then,
1 In(on + c00n n² Vn S c
12c
Proof. Define the function:
y(t) = In(ct + t
020,
31

---

and note that it is an increasing function, Moreover, ((t)(= de de = e --((()) for any 2 0. Hence,
y(t) y/0 + cp(s) ds
t t2
Define the function:
g(z) == Be and note that g is increasing when y 2 : In(Be) c). Moreover, (0) yo and yn++1 +((a).
Since y(0) yo 1 ln(Be)) and both {un} and y(t) are increasing, V/ 2 1 In(B c) for all and v() 2 In(B for all 0.
We first prove that
y(n) yn.
0, ........
(254)
We prove Eq. (24)) by induction. The claim holds for n = 0 by construction. Now assume that (n)) S Yn holds for some 0. Let us show that that y + 1) S Vn+1 also holds. For this note that
n+
v(n + 1) = v(n) +
e
ds
(n+t e ccp(n)
S v(n)=
(t y(t is increasing)
y(n) + e ccy(n)
S y(n) + - Bcy(m) g(y(n))
(since B 2 1)
(definition of g)
S ((nn)
(induction hypothesis, g increasing for y 2 1 à [I((Be) and yn. v(n) 2 _ In( ( c)) (By definition of yn+1)
By the principle of mathematical induction, y(n) S for all 2 0.
Define An, := y/, y(n). From previous inequality, know that An 2 O. We now show that (An)n is bounded, from which the desired statement follows immediately. To show that {An h is bounded we will show that An+1 A, is summable. To show this, we start by obtaining
expression for Ant1 A, Let = eovo Let n 2 O. Direct calculation gives
1 In 1
n+
A,
cyn
on + A
Using that for all x > In(1 + x) 2 1+
we get
Aat1 On < e cyn
en + A + 2
S e -cy(n)
(from Eq. 254
en + A + 3
1
(definition of yn))
en +
en + A 5
1
2e (n + A/2) (n + A/c })
1
(Since yo 2 In(ce)), A/c B 1)
2c (n + 1)
For fixed m > 0, summing up the above inequality from n 0 to m 1,
S x²
Au S
(Since Σ 1 12 = x²²
m
2c
nn
1)2
12c
n=0
x²
A m
<
(Since Ao = 0)
12c
32

---

where π = 3.14159. Hence, it follows that for any 2 0,
π²²
π
1/1 y(n) An S v(n)
In(en + c0 +
12c
12c
Lemma 15. Ler { be nonnegative valued sequence such that In+1 S In B exn can for all
with B 2 1, C >>> 0. Then, for all n 2 0,
x²²
In S In(en + c +
12c
where M max(B, In B e)), zo)-
Proof. Let [yn} be the solution to the difference equation yn+1 Yn + By- where M/
max B, 1 In [n c)). .o Since yo 2 To and yo 2 max(B, (B, [I((Be] e)), we can use Lemma 13 to
1
conclude that for all n 2
S
Furthermore, using Lemma 14 we can conclude that,
In S _ lc( + w +
n²
12c
Combining the above inequalities completes the proof.
33

---

D
Additional simulation results
Pebsolll ofcptim action
log L4 www.-/iiallll....... a40
0.30
0.30
-10
0.25
0.00
04
04
(a) (a ). 100.
(h) rr
To.27
100.
(c) log (r(a") n6. r), 10.
Figure 2: Visualization in two-action stochastic bandit problem. Here the rewards are defined as
(-0.05, 0.255) Other details same as for Figure 1 Figures 2a Zaland are based single run,
while Figure 2c averages across 10 runs. Note that log (r(a") To, Figure
2J 10 33 at the final stages on
34

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: In our view, the abstract and introduction summarize the main results, well as the technical novelty in obtaining these results.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: See Section 5
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
35

---

Justification: We describe the setting and assumptions clearly. The main results are backed by proof sketches in the main text and detailed proofs in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Our experiments consist of simple simulations, for which all the details are included in Section 4 The algorithm studied here is remarkably simple and well-known, so the experiments should be straightforward to reproduce with these details, without any code.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
36

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions 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 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.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/
sublic/guidess
CoodeSubmsssionooll1 httpe//ggiiieee//oeubbbimisee
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
cilips.cc/publle httpe//wwlccggguddeeeeeeeeeeeeee
http:/ddeeeeoeeeSuuuaassiisooloo ssioiillscscccyyccoccooccmoc for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Please see the details Section
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: There but we provide evidence for the convergence by repeating 10 independent runs, which are presented in the plots.
comparisons for which significance needs to be demonstrated,
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
37

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [No]
Justification: Our experiments are simply run on a single laptop or Python notebook, without requiring any particular infrastructure.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification:
The research does not involve human subjects or introduces any new datasets.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g.. if there special consid- eration due to laws or regulations in their jurisdiction..
10. 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.
38

---

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 direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that 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 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 attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
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 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 challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
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 dataset.
The authors should state which version of the asset used and, possible, include 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.
39

---

If assets are released, the license, copyright information, and terms of use in the thcode has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssit
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 not available online, the authors are encouraged to reach out to the asset's s creators.
13. 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/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent 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.
14. Crowdsoureing 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 details about compensation (if any)?
Answer: [NA]
Justification:
No human subjects 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 the supplemental material is fine, but if the main contribu- tion 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.
15. 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 equivalent approval/review based the requirements of your country 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 research with human subjects.
Depending 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.
40

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere 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.
41


Reviews:
[{"review_id": "VACf40w1rQ", "reviewer": "Reviewer_RHGg", "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.", "questions": "In simulations, if the learning rate is initially set to large number and then decreased, does algorithm show fast convergence?", "limitations": "Yes, the authors address the limitations.", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "This work extends the previous convergence results of stochastic gradient bandits by generalizing from a specific constant learning rate to an arbitrary constant learning rate. The high-level idea is demonstrated, and simple simulations are conducted to validate the theoretical finding.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for taking time to review our work. We hope the following can help clarify matters.\n\n>**heavily relies on prior work [23]**\n\nThis is simply incorrect. Our analysis is significantly different from [23], which is built on smoothness and growth condition, while our results do not exploit. Please refer to the common rebuttal for a detailed explanation.\n\n>**In simulations, if the learning rate is initially set to large number and then decreased, does algorithm show fast convergence?**\n\n**First**, we ran experiments using adaptive decaying learning rates as suggested on the same example in the paper. The total number of iterations is $T = 2 \\times 10^6$. For the first $10^6$ iterations, we use a linearly decayed learning rate from $\\eta = 1000$ (or $\\eta = 100$) to $\\eta = 1$ at $t = 10^6$, i.e., $\\eta_t = \\mathbf{1000} \\times (1 - t/10^6) + t/10^6$ (or replace $\\mathbf{1000}$ with $\\mathbf{100}$) for all $t \\in [1, 10^6]$. For the second $10^6$ iterations, we decay the learning rate as $O(1/\\sqrt{t})$, i.e., $\\eta_t = 1/\\sqrt{t-10^6}$ for all $t \\in [10^6 + 1, 2 \\times 10^6]$. Please see Fig. 4 in the rebuttal pdf for results.\n\n**Second**, we believe that this decaying learning rate scheme will lead to slower convergence speeds than using constant learning rates, as suggested by the analysis carried out in the paper of Lu2024.\n\n**[Lu2024]** Towards Principled, Practical Policy Gradient for Bandits and Tabular MDPs.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ISxcNe94RC", "reviewer": "Reviewer_jZkA", "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.", "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?\n2. 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:\n- For adaptive learning rates, can one think of running the algorithm in batches, such that the learning rates are decreased systematically for consequent batches?\n- 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. \n3. Can this be extended to the contextual bandits framework?", "limitations": "Yes, limitations have been adequately addressed. Societal impact statement N/A.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The paper provides useful asymptotic insights into stochastic gradient bandits, which to the best of my knowledge are novel.  Unlike previous work, where the methodology would not work for large learning rates,  the gradient bandit algorithm proposed by the authors is proven to asymptotically converge to the globally optimal policy.\n2. The paper discusses how exploration and exploitation trade-offs are balanced without exploration bonuses. Significant insights are provided into how constant learning rates affect the algorithm’s ability to explore different actions and avoid getting stuck in sub-optimal points.\n3. The proof sketches for Theorems 1 and 2 are particularly beneficial in elucidating the intuition underpinning the proofs. The contradiction-based argument presented in the case where ( $K \\geq 2$) is especially neat and clever.", "weaknesses": "1. As the authors also acknowledge, Assumption 1 seems to be a strong one and possibly unrealistic in applications.\n2. 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.\n3. 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. \n4. 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.\n\n\n*[23] Mei, Jincheng, et al. \"Stochastic gradient succeeds for bandits.\" International Conference on Machine Learning. PMLR, 2023.*", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate that the reviewer understood and recognized the contribution of the work. We answer the questions as follows.\n\nPlease refer to the common rebuttal for questions regarding Assumption 1, rate of convergence, and comparison with [23].\n\n>**...maximizing the cumulative reward (or minimizing the expected regret). Can we apply the stochastic gradient bandit algorithm in that setting?**\n\nIn fact, if we can obtain a rate of convergence (say $O(1/t)$ as speculated in the common rebuttal), such that $\\mathbb{E}{ [ r(a^*) - \\pi_{\\theta_t}^\\top r]} \\le C/t$, then this will imply a expected regret upper bound by summing up sub-optimality gap,\n$$\\sum_{t=1}^{T}{ \\Big( r(a^*) - \\mathbb{E}{[\\pi_{\\theta_t}^\\top r]} \\Big) } \\le \\sum_{t=1}^{T}{C/t} \\le C \\cdot ( \\log{T} + 1 ),$$\nwhich means that to get such a result, it is sufficient to prove a rate of convergence result.\n\n>**adaptive learning rates...decreased systematically for consequent batches?**\n\n**First**, we ran experiments using adaptive decaying learning rates on the same example in the paper. The total number of iterations is $T = 2 \\times 10^6$. For the first $10^6$ iterations, we use a linearly decayed learning rate from $\\eta = 1000$ (or $\\eta = 100$) to $\\eta = 1$ at $t = 10^6$, i.e., $\\eta_t = \\mathbf{1000} \\times (1 - t/10^6) + t/10^6$ (or replace $\\mathbf{1000}$ with $\\mathbf{100}$) for all $t \\in [1, 10^6]$. For the second $10^6$ iterations, we decay the learning rate as $O(1/\\sqrt{t})$, i.e., $\\eta_t = 1/\\sqrt{t-10^6}$ for all $t \\in [10^6 + 1, 2 \\times 10^6]$. Please see Fig. 4 in the rebuttal pdf for results.\n\n**Second**, we believe that this decaying learning rate scheme will lead to slower convergence speeds than using constant learning rates, as suggested by the analysis carried out in the paper of Lu2024.\n\n**[Lu2024]** Towards Principled, Practical Policy Gradient for Bandits and Tabular MDPs.\n\n>**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.**\n\nThank you for pointing this out. We agree with the reviewer on their intuition and insights. \n\n**First**, we would re-emphasize that the asymptotic convergence result  is the very first result for using large learning rates in stochastic gradient bandits, which is already difficult to obtain.\n\n**Second**, asymptotic convergence result itself without any characterization of rates is not enough to tell the difference in dependence on problem difficulty. As mentioned in Line 335 in the paper, a more refined characterization of convergence behaviors is needed to reflect this dependence.\n \n>**Can this be extended to the contextual bandits framework?**\n\nThank you for asking, and we are also pursuing this interesting direction. It is doable but not immediate. Extra work needs to be done for analyzing stochastic gradients using linear features (rather than the softmax tabular parameterizaion here), which is of independent of interest.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nOmIyUti40", "reviewer": "Reviewer_E4oN", "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.", "questions": "Proof Details:\n\nCould you provide more detailed explanations for Lemma 1 and Lemma 2? Specifically, how do the assumptions ensure the boundedness of parameters?\nExperimental Results:\n\nIn 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?\nPractical Implications:\n\nHow 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?\nGeneralization:\n\nYour 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?\nAssumption 1:\n\nAssumption 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?\nConvergence Rate:\n\nWhile 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?\nLimitations and Future Work:\n\nYou 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": "no", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Theoretical Contribution: The paper provides a strong theoretical result, proving the global convergence of the stochastic gradient bandit algorithm for any constant learning rate. This is a significant advancement over existing literature that typically requires decaying or small learning rates.\n2. Novel Insights: The authors uncover interesting properties of action sampling rates and the relationship between cumulative progress and noise, contributing to a deeper understanding of exploration-exploitation trade-offs in stochastic gradient methods.\n3. Clarity and Rigor: The proofs are presented with clarity and rigor, making the paper accessible to readers with a solid background in stochastic optimization and reinforcement learning.\n4. Empirical Validation: The simulation studies support the theoretical findings, demonstrating the convergence behavior under various learning rates.", "weaknesses": "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.\n2. 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.\n3. 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.\n4. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate that the reviewer understood and recognized the contribution of the work, and we thank the reviewer for carefully reading and checking the results. The main concerns are addressed as follows.\n\n>**detailed explanations for Lemma 1 and Lemma 2**\n\nAccording to Eq. (1), the sampled reward $R_t(a_t)$ is in a bounded range of $[-R_{\\max}, R_{\\max}]$ with $R_{\\max} < \\infty$. By design, we use a constant learning rate $\\eta < \\infty$. This argument is shown in Eqs. (26) and (27) for Lemma 1 in the appendix.\n\n>**elaborate on the observed differences in convergence behavior for these learning rates**\n\nFrom the simulations, smaller $\\eta$ values such as $1$ and $10$ always enter the final stage of $\\pi_{\\theta_t}(a^*)$ being close to $1$ more quickly, while larger $\\eta$ values ($100$ and $1000$) can reduce the sub-optimality gap $r(a^*) - \\pi_{\\theta_t}^\\top r$ to much smaller values when $\\pi_{\\theta_t}$ is already in the final stage of $\\pi_{\\theta_t}(a^*) \\approx 1$. However, there is a trade off, such that larger $\\eta$ values (on average) spend a longer time entering the final stage.\n\n>**learning rates outside the tested range**\n\nWe ran experiments on the same example in the paper using $\\eta = 0.01$ and $\\eta = 0.1$, which outside the tested range of $\\{1, 10, 100, 1000\\}$ (since $1000$ is already a super large learning rate, we did not test $\\eta > 1000$). Please see Fig. 3 in the rebuttal pdf for results.\n\n>**How would you recommend practitioners choose an appropriate learning rate...Are there any heuristics or rules of thumb...?**\n\nIn deep learning, large learning rates have been applied empirically. For example, [Li2020] showed that increasing learning rates can achieve good performance for networks with BatchNorm, which is similar to what we speculated for RL (Line 345). \n\nHowever, multiple factors affect practical performance. Our heuristic is that when the optimal solution is deterministic (no entropy regularization), then stochastic policy gradient could work with large learning rates. If there is entropy regularization, then eventually the learning rate has to be decayed, since otherwise oscillation can happen (optimal solution is not deterministic, and overshooting can happen). \n\n**[Li2020]** An Exponential Learning Rate Schedule for Deep Learning, in ICLR 2020.\n\n>**What challenges do you foresee in extending these results to more general reinforcement learning settings? How might the approach change?**\n\n**First**, currently we do not know if the key properties we established for bandits (Lemmas 1 and 2) will hold in MDPs or not, which is the key challenge of extending to general reinforcement learning settings.\n\n**Second**, in general MDPs, exploration over the state space is a problem that does not exist in bandits [1], which requires the stochastic gradient methods to be modified accordingly.\n\n>**Assumption 1 ... How critical is this assumption ... how to relax this assumption in future work?**\n\n**First**, Assumption 1 is for the simplicity of our arguments. It shouldn't be critical, since one can collapse actions with the same rewards without changing the optimal expected reward / value.\n\n**Second**, regarding how to relax this assumption, please refer to the common rebuttal for a more detailed discussion.\n\n>**Could you suggest specific directions or methods for this refined analysis**\n\nWe speculate that the established asymptotic convergence of $\\pi_{\\theta_t}(a^*) \\to 1$ as $t \\to \\infty$ can be split into two phases: early and final stages, corresponding to when $\\pi_{\\theta_t}(a^*) < 1 - \\epsilon$ or $\\pi_{\\theta_t}(a^*) \\ge 1 - \\epsilon$ respectively. \n\nThe phase transition happens at the time point $t_0 < \\infty$ such that for all $t \\ge t_0$, we have $\\pi_{\\theta_t}(a^*) \\ge 1 - \\epsilon$.  Therefore, a refined analysis would be to characterize how the time $t_0$ depends on learning rates, as well as other problem specific quantities, such as reward gap and reward range.\n\n>**Could you provide more insights or conjectures about the expected rate of convergence for different learning rates?**\n\n**First**, for all learning rates, from Figs. 1(a) and 1(b) in the main paper,  $\\log{ (r(a^*) - \\pi_{\\theta_t}^\\top r) } \\approx - \\log{t} + c$ (from numerical values,  slopes are $\\approx -1$), which means that $r(a^*) - \\pi_{\\theta_t}^\\top r \\approx C/t$, i.e., the rate of convergence is about $O(1/t)$ (as mentioned in Line 315).\n\n**Second**, for different learning rates, we speculate that the time spent in early stage scales with $\\eta$, such as $O(\\eta)$, while the rate in final stage scales with $1/\\eta$, such as $O(1/(\\eta \\cdot t))$, aligned with previous observed differences in convergence behavior for different learning rates in Fig. 1 in the main paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "NQ5p6Id1Q6", "reviewer": "Reviewer_qHxg", "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.", "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?\n\nQuestion 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$.\n\nComment 1: It would be helpful to discuss the challenge when using the technique in [1] for a constant learning rate.  \n\n[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": "The authors adequately addressed the limitations and societal impact.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The proof process based on contradiction and reduction is novel. Furthermore, the analysis reveals why the stochastic gradient bandits algorithm can naturally balance exploitation and exploration, which deepens the understanding of this algorithm.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate that the reviewer understood and recognized the contribution of the work. We answer the questions as follows.\n\n>**$\\eta = 100$ and $\\eta = 1000$ do not converge. Can you discuss this phenomenon in detail?**\n\nWe ran more iterations for $\\eta = 100$ and $\\eta = 1000$, and eventually all runs converged. Please see Fig. 1 in the rebuttal pdf for results. A new observation is that those curves converge when the optimal action is sampled, i.e., $a_t = a^*$. This is aligned with theory, since the first part of Theorem 2 (Line 241) proved that the optimal action will be sampled for infinitely many times as $t \\to \\infty$.\n\n>**larger $K = 10$**\n\nWe ran experiments using $K = 10$ as suggested for learning rates $\\eta \\in \\\\{1, 10\\\\}$, extending the example in the main paper to $r = (0.2, 0.05, -0.1, -0.4, -0.5, -0.6, -0.7, -0.8, -0.9, -1.0)^\\top$. Please see Fig. 2 in the rebuttal pdf for results.\n\n>**It would be helpful to discuss the challenge when using the technique in [1] for a constant learning rate.**\n\n**First**, monotonic improvement over $\\pi_{\\theta_t}^\\top r$ cannot be established for large learning rates. In fact, for large learning rates, non-monotonicity of $\\pi_{\\theta_t}^\\top$ is observed in Fig. 1 (metioned in Line 304).\n\n**Second**, in particular, Lemma 4.6 in [1] requires very small constant learning rates ($\\eta \\le \\frac{\\Delta^2}{40 \\cdot K^{3/2} \\cdot R_{\\max}^3 }$), which follows from their Lemma 4.2 (smoothness) and Lemma 4.3 (noise growth condition). Using large learning rates makes those two lemmas not applicable, and monotonic improvement of $\\pi_{\\theta_t}^\\top r$ is no longer assured.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "uNppRB7rKw", "reviewer": "Reviewer_4TYZ", "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.", "questions": "1. Algorithm 1 is the gradient bandit algorithm without baselines. Can we also have similar results for the version with baselines?\n\n2. 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": "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.\n\n2. 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.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Theoretically, the authors prove that for any constant learning rate, the stochastic gradient bandit algorithm (REINFORCE without baselines) converges to the globally optimal policy almost surely as the number of iterations goes to infinity. The authors also avoid using non-uniform smoothness and noise growth conditions in a previous related work ([1]).\n\n2. The authors also provide some simulation results to verify their theoretical findings.\n\n\n\n[1] Stochastic gradient succeeds for bandits.", "weaknesses": "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]).\n\n2. 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.\n\n3. The code is not provided, although the experimental setting is simple.\n\n[1] Gradient Descent on Neural Networks Typically Occurs at the Edge of Stability\n\n[2] Stochastic gradient succeeds for bandits.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate that the reviewer recognized the contribution of the work. We answer the questions as follows.\n\n>**include some literature review on deep learning with large learning rates**\n\nThank you for pointing the \"edge of stability\" paper to us. We will cite this line of work in the related work discussion starting from Line 104 in the paper.\n\n>**what the exact convergence rate is**\n\nPlease find a detailed discussion in the common rebuttal, regarding why the techniques in [2] are not applicable and cannot be used here to obtain a rate.\n\n>**The code is not provided**\n\nWe will upload a link for running the simulations in the updated version of the paper.\n\n>**Can we also have similar results for the version with baselines?**\n\nThank you for asking this interesting question. \n\n**First**, our preliminary calculations show that similar results can be obtained for the version with action-independent baselines, such as $\\pi_{\\theta_t}^\\top r$.\n\n**Second**, in Algorithm 1, if we replace $R_t(a_t)$ with $R_t(a_t) - \\pi_{\\theta_t}^\\top r$ (or $R_t(a_t) - B_t$ with any other action-independent baseline $B_t \\in \\mathbb{R}$), then Lemmas 1 and 2 still hold because of $R_t(a_t) - \\pi_{\\theta_t}^\\top r$ is still bounded (by Eq. (1)). Theorem 1 will hold because of the progress is exactly the same as in Eqs. (11) and (13), according to the well known result that action-independent baselines contribute $0$ to policy gradient, meaning that Proposition 1 holds for any action-independent baselines.\n\n>**What would be the challenges of extending the current analysis to the non-asymptotic rate analysis?**\n\n**First**, the challenge is that monotonic improvement (in expectation) over $\\pi_{\\theta_t}^\\top r$ cannot be shown for large learning rates (non-monotonicity of $\\pi_{\\theta_t}^\\top$ is observed in simulations in Fig. 1 in the main paper, also as pointed in Line 304), unlike Lemma 4.6 of [23] (when learning rate is very small). Therefore, it is not clear how to quantify the progress (how much $r(a^*) - \\pi_{\\theta_t}^\\top r$ is reduced in expectation after one stochastic gradient step). Without quantifying the (expected) progress, it seems difficult to do non-asymptotic rate analysis.\n\n**Second**, there exist analyses for non-monotonic improvement over objective functions (such as Nesterov's accelerated gradient), but for convex functions. However, here we have a non-concave maximization (Line 95). \n\nPlease also find a detailed discussion in the common rebuttal.\n\n>**what would be the challenges of extending the current proof techniques to other RL algorithms like natural gradient methods?**\n\nNatural gradient methods achieve faster convergence results than standard policy gradient when using exact gradient updates. However, with stochastic on-policy sampling $a_t \\sim \\pi_{\\theta_t}(\\cdot)$, if we use constant learning rates $\\eta \\in \\Theta(1)$ for natural policy gradient method, then it can fail, by converging to sub-optimal deterministic policies with  positive probability (Theorem 3 of [19] and Proposition 1 of Chung2021).\n\n**[Chung2021]** Beyond variance reduction: Understanding the true impact of baselines on policy optimization, in ICML 2021.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their valuable comments and recognition of the contributions. This common feedback answers questions raised by multiple reviewers.

>**Comparison to [23] (Reviewers RHGg, jZkA, qHxg, 4TYZ)**

**First**, we would like to emphasize that the asymptotic convergence arguments in this paper go well beyond \emph{any existing results and techniques}. The level of difficulty is paramount, since the foundational conditions (smoothness and growth condition [23]) for most existing optimization convergence and rate analysis are not applicable (as mentioned Line 116 in the paper). We believe that achieving novel results by developing innovative new proof techniques and uncovering new properties of stochastic gradients is a substantial achievement for whole optimization community, far beyond RL. 

**Second**, the analysis in this paper provides new implications for practice of policy gradient methods. Previous results, including [23], do not cover practical choices for learning rates, yet the results in this paper can. For the example in Fig. 1 in the main paper, Lemma 4.6 of [23] gives $\eta \le \frac{\Delta^2}{40 \cdot K^{3/2} \cdot R_{\max}^3 } = 0.00007$ (Line 294), which is much smaller than any learning rate in Fig. 1, which are in the realm of the analysis in this paper.

**Third**, the analysis in [23] relies on monotonic improvement results over $\pi_{\theta_t}^\top r$ (in expectation) that \textbf{do not hold} in our setting and therefore are \textbf{not applicable}. In particular, Lemma 4.6 in [23] requires one to use very small constant learning rates ($\eta \le \frac{\Delta^2}{40 \cdot K^{3/2} \cdot R_{\max}^3 }$). Therefore, we had to develop new insights, which led to new technical, innovative results (Lemmas 1 and 2) that are distinctly different from [23], and to our knowledge completely novel. 

>**Rate of convergence (Reviewers jZkA, E4oN, 4TYZ)**

**First**, we would like to emphasize that even asymptotic convergence is a totally new result for using large learning rates with stochastic gradient, without exploiting smoothness and growth conditions. As explained, in this case there is no monotonic improvement (in expectation) over $\pi_{\theta_t}^\top r$ (unlike [23]), and whether convergence (or oscillation) will occur asymptotically is not obvious.

**Second**, we speculate that the convergence rate is $O(1/t)$. Figs. 1(a) and 1(b) in the main paper show that $\log{ (r(a^*) - \pi_{\theta_t}^\top r) } \approx - \log{t} + c$ (from numerical values, the slopes are $\approx -1$), which means that $r(a^*) - \pi_{\theta_t}^\top r \approx C/t$, i.e., the rate of convergence is about $O(1/t)$ (mentioned in Line 315).

**Third**, the key difficulty arises from the non-monotonicity of $\pi_{\theta_t}^\top r$ (observed in Fig. 1, mentioned in Line 304). 
Since Lemma 4.6 of [23] requires a very small $\eta$, which does not apply here, we cannot quantify the progress (how much $r(a^*) - \pi_{\theta}^\top r$ is reduced in expectation after one stochastic gradient update) using their techniques, which makes it unclear how to use results of [23] to obtain a rate here.

>**Assumption 1 (Reviewers jZkA, E4oN)**

**First**, we believe Algorithm 1 simply works without Assumption 1. To see intuition/evidence, consider $r = (0.9, 0.9, 0.7, 0.6, 0.6, 0.5)^\top$, which does not satisfy Assumption 1. Consider softmax PG with exact gradients, which achieves $\pi_{\theta_t}^\top r \to 0.9$ as $t \to \infty$. Now the question is if $\pi_{\theta_t}$ approaches a strict one-hot policy or not. Suppose $\theta_t(1) > \theta_t(2)$, then we have,
$$\theta_{t+1}(1) - \theta_{t+1}(2) = \theta_t(1) - \theta_t(2) + \eta \cdot (\pi_{\theta_t}(1) - \pi_{\theta_t}(2)) \cdot (0.9 - \pi_{\theta_t}^\top r) > \theta_t(1) - \theta_t(2),$$
which implies that $\theta_{t}(1) - \theta_{t}(2)$ is monotonically increasing if initially $\theta_1(1) - \theta_1(2) > 0$. As a consequence, $\pi_{\theta_t}(1) \to 1$ and $\pi_{\theta_t}(2) \to 0$, even if the two actions have the same reward $0.9$. This means except for a zero measure initialization such that $\pi_{\theta_1}(1) = \pi_{\theta_1}(2)$, the policy $\pi_{\theta_t}$ eventually goes to a strictly optimal one-hot policy (mentioned in Remark 1).

**Second**, to extend the above calculations from exact gradient to the stochastic online setting, extra work needs to be done to show that with probability $1$, only one action dominates the others, rather than they achieve an asymptotic balance to have mixed (rather than strictly one-hot) convergent policies.

Meta-review: 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.
Decision: Accept (poster)