Does Stochastic Gradient really succeed for bandits?
Authors: Dorian Baudry
Emmeran Johnson
Simon Vary
Ciara Pike-Burke
Patrick Rebeschini
Venue: NeurIPS 2025 oral ()
Keywords: bandits
policy gradient
Primary area: theory
TL;DR: We propose a novel regret analysis of a simple policy gradient algorithm for bandits, characterizing regret regimes depending on its learning rate.

Abstract: Recent works of Mei et al. (2023, 2024) have deepened the theoretical understanding of the *Stochastic Gradient Bandit* (SGB) policy, showing that using a constant learning rate guarantees asymptotic convergence to the optimal policy, and that sufficiently *small* learning rates can yield logarithmic regret. However, whether logarithmic regret holds beyond small learning rates remains unclear. In this work, we take a step towards characterizing the regret *regimes* of SGB as a function of its learning rate. For two--armed bandits, we identify a sharp threshold, scaling with the sub-optimality gap $\Delta$, below which SGB achieves *logarithmic* regret on all instances, and above which it can incur *polynomial* regret on some instances. 
This result highlights the necessity of knowing (or estimating) $\Delta$ to ensure logarithmic regret with a constant learning rate.
For general $K$-armed bandits, we further show the learning rate must scale inversely with $K$ to avoid polynomial regret. We introduce novel techniques to derive regret upper bounds for SGB, laying the groundwork for future advances in the theory of gradient-based bandit algorithms.

Does Stochastic Gradient really succeed for Bandits?
Dorian Baudry 1,2
Emmeran Johnson
Simon Vary²
Ciara Pike-Burke
Patrick Rebeschini
Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LIG, 38000 Grenoble, France 2 Department of Statisties, University of Oxford
3 Department of Mathematics, Imperial College London
Abstract
Recent works of Mei al. [1[ have deepened the theoretical understanding of the Stochastic Gradient Bandit (SGB) policy, showing that using a constant learning guarantees asymptotic convergence to the optimal policy, and that sufficiently small learning rates can yield logarithmic regret. However, whether logarithmic regret holds beyond small learning rates remains unclear. this work, take a step towards characterizing the regret regimes of SGB as function of its learning rate. For wwo-armed bandits, we identify a sharp threshold, scaling with the sub- optimality gap A, below which SGE achieves logarithmic regret on all instances, and above which can incur polynomial regret on some instances. This result highlights the necessity of knowing (or estimating) A to ensure logarithmic regret with a constant learning rate. For general K-armed bandits, we further show the learning rate must additionally scale inversely with K to avoid polynomial regret. We introduce novel techniques to derive regret upper bounds SGB, laying the groundwork for future advances in the theory of gradient- based bandit algorithms.
Introduction
K-armed bandit is sequential drcissonnmmkinng problem where, each time [T], learner chooses an action Ae E [K] and receives reward drawn independently at random from the fixed distribution VA.- The objective to select a policy æ, which at each step maps past observations H--1 = (As; [t) to a sampling probability PŘ, = P.(A, = 1: (H-11) for each arm k E [K],
in order to maximize the expected cumulative reward F |>'n rt] when actions are chosen according æ. This is equivalent minimizing the regret, defined by
T Σ
R
(A k))
with Vk,
A
max Hi SE[K]
14 and μi Eraen [r],
(1)
T
K
T Σ(- Pi.))
or equivalently
RJ = Ex
Σ
T PK
< Ex
max Ak.
(2)
KE[K]
where for convenience we assume that arm 1 is the unique optimal arm, i.e., ji > max max.e(2....KK) Pj- We further define the minimam gap A == ming:d.00 Ag- Finally, denote by F the family of reward distributions supported on [-1, 1], and assume that Vy F for all k E [K].
Notation We now detail the symbols used throughout the paper. Let (A, B) R2, then: AA B min A, B}, A B = max{ A, B}, and (A)_ = A V O. If A, B depend on the horizon T,, we use
Corresponding author: dorian baudry@inria.ff frr
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

interchangeably A B or A O() (resp. A B and A = ((B)) when there exists > 0 s.t. A I cB (resp. 2) and i independent of 'T' but can be problem-dependen. To hide poga-loga factors in T, we respectively use O and f2, for example A 2 log())) = A = (2(T). Finally, we use A x B when both A B and B S A hold.
1.1 Motivation and related work
Stochastic gradient ascent methods have been extensively studied in the context of bandits and reinforcement learning, tracing back to foundational works such as Robbins and Monro's stochastic approximation [3, the REINFORCE algorithm 4], and subsequent developments in policy gradient (PG) methods [3]. Despite the empirical success of these algorithms in modern deep reinforcement learning C TO), the theoretical understanding of their convergence and regret guarantees remains limited. This motivates closer examination of their foundational components in simpler settings. We study one such component, the Stochastic Gradient Bandit algorithm (SCB) [1] Chapter 2.8], a softmax policy gradient method for Multi-Armed Bandits (MAB).
central challenge analyzing SCB stems from the weakness its underlying optimization structure, making the analysis difficult even in the case of PG with access to exact gradient information [[2]. The optimization challenge arises from the softmax parametcrization satisfying only a non-uniform version of the Polyak-Lojasiewin
(PL) inequality [33 Lemma 3]. Consequently, if the sampling probability of the best arm becomes too small, the gradient signal vanishes and SGB may require an exponentially long time to recover, even with access exact gradients [14] 13]. Nevertheless, PG with softmax parameterization and exact gradients has been shown to converge to a globally optimal policy asymptotically [16] Theorem 5.1], and with O(1 rate [[33, although the rate of convergence depends on suitable initialization and problem dependent constants [14] [5] Convergence guarantees have also been obtained with regularization
12 or by modifying the softmax function [7].
The analysis of SGB with stochastic gradients becomes even more convoluted. Contrary to typical policies like UCB [8] or Thompson Sampling [1)], the decisions of SGB depend intricately on the order in which all past rewards were collected, and thus cannot be analyzed through simple summary statistics; see Appendix A.3 for a detailed comparison with standard bandit policies. Despite these difficulties, a number of recent works are able to show global convergence of variants of SGB (and its generalization for Markov Decision Process) [2H27]] However, these result require decaying learning rate regularization resulting in at best OL/vTT) convergence rate (20 23 Mei et al. [28] showed that natural policy gradient with oracle baselines achieves a O convergence rate. A closely related algorithm to SGB is SAMBA [29]. policy that achieves logarithmic regret for Bernoulli rewards by performing stochastic gradient ascent directly on the sampling probabilities without relying on the softmax transformation; for detailed comparison to SGB see Appendix B.2
Recently, Mei et al. I established a regret upper bound of (log(T)) for SGB with small constant learning rate 7) satisfying 7) S A K3/2 where K is the number of arms. In follow-up work, Mei et al. [2] further proved that SGB asymptotically converges to globally optimal policy for any constant learning rate. While asymptotic convergence is a desirable property, it does not guarantee favorable regret guarantees, the regret properties of SCB without the small rate constraint.
discuss in Appendix A.4] This motivates further investigation of
The goal of our work is to characterize the strengths and limitations of SGB, as principled yet simple and scalable learning rule; which is representative of algorithms that have shown empirical success in more complex, large-scale settings. Importantly, our aim is not to promote SGB over state-of-the-art bandit algorithms such as KL-UCB 30 or Thompson Sampling 31 32 work, we depart from optimization- analysis exploits a novel decomposition into a term that remains logarithmic for all learning rates, and second term capturing the probability of failure-that is, the chance that the optimal arm fails to stand out-which crucially depends on r). This enables us to determine regimes where SGB succeeds.
To achieve our goal, in this analyses of SGB and develop regret-based analysis. Our
1.2 The Stochastic Gradient Bandit policy (SGB)
Following Sutton and Barto [1] Section 2.8], we define SGB as randomized policy, with sampling probabilities at time 2 given by the softmax transform of some parameters (0v,)) E R
Vt E [T], Vk [K]
SCB Pk.t exp (0x.c)
(3)
2

---

In the following, we drop the superseript for simplicity of notation. Given fixed learning rate the parameter of each arm & E [K] initialized at σx, 0. and is updated follows,
Vt 2 1: 0..1+1 n.000,,, with 80 == (1-PP.,)-Ft-I1.
= k) Pe.t T 1 (Ae + k). (4)
For completeness, we provide the pseudo-code of SGB in Algorithm | in Appendix A. In the
remainder the paper, we use the shorthand notation [e(-] for the conditional expectation |E] [ From Equation 4 we derive the following first fundamental property of SGB,
vk E [K]. 2 1: E, [600.. = Pa,e(1 - -PE,) Pk.t Σ
Psatt = Pk.t [E. -x) (5)
jz
This equation allows to verify (see Appendix A.1 that SGB indeed performs stochastic gradient
ascent in order maximize the value of the policy at time 1, V Σ k= Pk,t" since (Ō
is unbiased estimate of V, V,5 It also shows that a parameter 0 is expected to increase only if
the gap of arm is smaller than A.] = - Py.A,, the instantancous regret of SGB. From (5)
we further obtain that if arm is the only optimal arm, the parameter of the best arm satisfies
T
T E. [ 27-B
T Σ (1. - (P,)A
B|0 = 17 E Σ
80
= E
Σ
(6)
which is an equality if all sub-optimal arms have the same gap A. This allows us to express an upper bound on the regret function of the parameter 01.T+1. Defining Amax maxxe [K] Ak, and using that (1 P1.))= (1 P1.)) + +1 pI,)),, by plugging O
into obtain that
RT S A max E
Σ
Pl.e) S
A max
[00TT++1 A max
Σ P1,))
n
Post condeereeeree
Failure regret
term
This regret decomposition, though obtained via straightforward reformulation, appears to be novel and, to the best of our knowledge, has not been exploited in prior analyses of SGB. In fact, Equation (7) provides a powerful lens through which we develop all the upper bounds in this work, as it splits the regret into two interpretable components. In Section 3 prove that the post-convergence term is bounded by (log 7) for any learning rate. Therefore, whether SGE achieves logarithmic regret or not depends entirely where we discuss an alternative formulation of Eq. 7 establishing the relation between failure regret and the sum of probabilities that Pt.r stays bounded away from The empirical study in Section further supports this decomposition: most trajectories of SGB fall into one of two distinct regimes-successfi runs, with convergence to the optimal policy rate O(--)), and failed runs, where the optimal arm remains persistently under-sampled up to horizon T.
the scaling of the failure regret. We justify this terminology in Appendix F.I
In addition to the above regret bound, we present in Appendix A.2 some other elementary properties of SGB that can be directly derived from its update rule (4) and will be useful in our analyses.
1.3 Outline and contributions
We introduced in Section 1.2 an original decomposition of the regret of SGB into post-convergence term and a failure regret. In Section 2 we build on Eq. 7 to provide a tight regret analysis for two-armed bandits when y & A (Thm. T. We then prove in Thm. 2 that the regret of SGB can be polynomial on some instances if r Z A. Hence, we characterize the regret of SGE in two-armed
bandits, except for a critical regime 77 x A that discuss in Section 2.2 In particular, knowing lower bound on the gap A is necessary and sufficient to tune 7) to guarantee logarithmic regret. We summarize our results for the two-armed bandit problem in Table below, denoting by F the class of two-armed bandits with distributions supported on [-1, 1] and gap larger than A E (0,
In Section 3 we consider a general number of arms K. Using lower bound arguments, we first prove a second necessary condition: logarithmic regret can be guaranteed only r) decreases linearly K (Thm. 3 By combining this result with Thm. 2 we conjecture that the critical tuning of might be proportional to A/K K. For the regret analysis, we establish Lemma 2 that the post-convergence term is logarithmic for any constant learning rate. Then, in Lemma derive an intermediate
3

---

"
5A-0(A3)
A
2 A + 0(A3)
VV E Fz. RT - log(T)
30 F S.L. E p1.1) _ (Conjecture from the proof' of Thm. and
341 E F 8.t.
R
RT 0 ( wi-aa
(Thm.
(Thm.)
Regime
Logarithmic
Critical
Polynomial
Table 1: Regret guarantees for SGB as function of y for two-armed bandits
upper bound on the failure regret. The upper bound contains additional terms compared to the case K 2, causing significant technical challenges that we detail, but leave their dedicated analysis for future work. Nonetheless, as a promising first complete result for K K-armed problems, we prove in Theorem that the regret of SGB is logarithmic if nee2n I K+2
24 when all arms have identical gap A.
Finally, in Section 4 we present some synthetic experiments that illustrate our theoretical findings.
2
Characterizing the regret regimes for two-armed bandits
In this section we propose tight characterization of the regret regimes of SGB when K We exhibit a separation between logarithmic and polynomial regret close to the gap A.
2.1 Regret analysis for y S - O(A2)
We directly detail the main result of this section and its complete proof.
Theorem (Regret upper bound for K = 2). For two-armed bandit instance v E F² with gap A E (0, 1). the regret of SGB tuned with a learning rate n satisfying r/C,, A is upper bounded by
log(1 AT)
A
t00
(2n)
Ro0 <
with C,
S 2n
2n
2ny - n)C)
(n + 2)!
Proof. Since 02 -t,, for all steps I, by 9 we drop the subscript 1 to simplify the notation. Starting from the regret decomposition of Equation 7.. we readily obtain that for any instance v,
E 100+1
RBBB
A
Σ (1 p+)
We start by upper bounding [00r+1). Jensen inequality provides that
B[Or+1] = E [log (e )] S 2
log (EE (0)))-)))
We then use the update rule of (0,)221 to upper bound Eie20.). From the Taylor expansion of the exponential, for any constant E IR and random variable r supported on [-1, holds that
+oo
9"
n-2
q²
Efear] = 1+ gB(r]
E
$1+ 9Errl + q²
[ +
Cw (8)
n!
n n!
2
2
Using the notation a, 2n1(1 p.) and b, 21pt, for any
2 Eq.
and 8 give that
E, [e 29.11]
20. E3 le 2n80 20: [e IA, 1] + -1 P. )E bere |A 2))
S 20, (1 + Pe (a//1 + au 0.5 Ca./2) + (1 pt) (-b, + b3 0.5 C2,12))
28. (1 2p. pt) (n 1 C)))
since V b, < 2n
Then, we use the relation 20: (1 Pt) = Pt (Eq. in Appendix A to obtain that
Vt 1, E 20:1] < 20: + + (n> + C,)
<0
EE [ 20 < 11+2 2 + +rr))) TT

---

which gives the logarithmic term in the theorem. It remains to upper bound BI (1 (1-p) For
t 2 I, we define 21 == 1-tt = E 20,, and obtain with the same arguments above that
E [r[ S xt (1 21-22pt11- (1- + 2p, (1 - p,,) = It - 2n(1 - pt)² (A (A- ()))
By taking expectation on both sides and summing over time steps, we thus obtain that
T
BiZr+1 - xi] - -2n (A - -1,)) E
Σ 11 - pr)
from which the result follows by using that B[r - IT+1] S x and that A - -r > O.
Tightness of the bound In addition to being strikingly simple, the proof of Thm. is also tight under the assumption that rewards are bounded in [-1, First, for F1 = Rad () and 1/2 = Rad(O), and ryCr, (1 -) A for some ε > O. the logarithmic (post-convergeence) term matches the asymptotic lower bound up to factor (1 -1-- (A)) (see
(see D.I for details). It thus cannot be much improved if e, A are small. For the constant term, the only possible improvement would be use higher-order moments for tighter approximation in Eq. (8). However, for Rademacher distributions we could at most replace C. by 1, so the gain would be minor for small 1) since we already have that C, S e2",
Comparison with existing results Theorem is a fully explicit regret upper bound, which sur- prisingly does not rely on any techniques from standard analyses of gradient ascent policies. For two arms, we obtain guarantees for much broader range of learning rates" than Mei et al. M. and even obtain near-optimal logarithmic scaling of the regret 1) happens to be close to A. We then compare SGB with SAMBA, another policy performing paraameee)))) gradient ascent. For two arms, SAMBA running with parameter a < A achieves regret bound of a log(T) [29] which is close to our result. We elaborate on the comparison between the two policies in Appendix B.2. While their analysis extends to K > 2, it is more involved than the proof of Thm. [] is restricted to Bernoulli rewards, and involves non-explicit and potentially large constants. Finally, we highlight that the logarithmic component of Thm. i valid for all constant 7,. Hence, for SGB restricting 7) is required only to guarantee that the failure regret converges, which is novel insight compared to (29].
Alternative moment-based condition closer examination of Eq. (8) reveals that the analysis of Thm. can be extended or sharpened under general moment assumptions on the reward distribution. For example, if one assumes that supm22 B[r?] S s2 for some s > O, then the result continues to hold by scaling the term C,C by s² when bounding the failure regret, so rjC,, < A is sufficient for logarithmic regret. Hence, SGB can be fine-tuned under higher-moment conditions, akin to how Bernstein- -type inequalities 133, Chapter 2.8] improve confidence intervals in UCB- -tyle algorithms. Such assumptions are often realistic in applications like marketing or online advertising, where reward distributions are typically bounded and the average outcomes (e.g. click rates) are small [34] (3]. In Appendix F.5 we also discuss the case of unbounded rewards, e.g. sub-Gaussian. Notably, for SGB these assumptions merely expand the admissible range of learning rates. By contrast, standard approaches would require substantial structural changes, such as tighter confidence intervals for UCB modified priors/posteriors for TS, to exploit higher-order moment information.
Knowledge of A While assuming that a lower bound on A is known remains strong requirement, we conclude this section by showing that, even without this knowledge, a learning rate that depends only on the time horizon 7' leads to meaningful regret guarantees in the two-armed bandit setting.
Corollary 1 (of Theorem 1. If A is unknown, one can set 1) V /og((T)
T which yields
log(T) 1(2 S 4) AT 1(A 2TC S vT log(T))
Yv E F22 Rr S
7
by using the upper bound from the theorem if 1 is small enough, and R S AT otherwise.
In Proposition 4 (App.
R33) we further prove that a time-varying learning rate т Vlogle V t)/l
also yields R2 Ö(v
(T). While Mei et al. [ Section 3] hint that such rate may be an appropriate
We document in Appendix B.1
potential issue with their result, and propose non-trivial fix for K 2.
5

---

tuning for SGB. it appears that comparable results to ours have only been been obtained with regularization added the policy update, as in [20 2T On the other hand, the regret upper bound of the gap-free variant of SAMBA 22 Thm.2] still involves large woobeem-depende constants, while the constants Corollary D are absolute. Hence, the time-dependent tuning of 7j that we propose stands out practical choice when no lower bound on A is available (see Appendix (.1 for experiments). For the two-armed case, we believe that these theoretical results offer a comprehensive guideline on how to choose 1y when using SGB in practice: if the learner has access to lower bound on A < A such that the gap-dependent tuning 77 z Á guarantees that log( (+44AA7) then the gap-dependent tuning should yield better performance, since we believe that the bound of the theorem is tight. Otherwise, the horizon- -iiieddee tuning that we propose can be safely used.
27 I V (T') for horizon T.
2.2 Necessary condition on fixed for logarithmic regret
In this section, we prove that the knowledge of the minimum gap necessary to tune the fixed learning rate of SCB in order to obtain logarithmic regret. The following Thm. 2.m.2ssaa shows that if larger than fixed constant that depends on the gap A and the number of arms K, there exists K-armed bandit problem with gap A for which SGB has polynomial regret. To define it, for J E [-1, 1] we denote resp. by (ad(u) and 6,. the Rademacher and Dirac distributions of mean μ.
Theorem 2 (Polynomial regret). Fix A (0.1) and consider the instance v (v*)Ke[R) with VK- do- If the learning rate of SGB satisfies
in Rad( A) and V22
1 A == K-1 log 1-A
then its regret on the instance v is lower bounded as follows,
RT B - RT=ū(rr-atebsln
Ve O,
where St hides polylogarithmic terms and constants depending on n and A.
Proof sketch. Let us assume K in the following, and introduce the main steps of the proof of the theorem. Details and supporting results can be found in Appendix [ where we directly consider general number of arms. Since only arm 1 yields non-zero rewards, we directly have
11 1, 0 01, 1 = 01, v7(1 pi..) rr. [(A,=1]
we denote by Pa++1 the sampling probability of arm 1 after its first pulls. The proof consists of identifying a scenario with linear regret, and lower bounding its probability as a function of r7-
Step 1: Let S be the event that P-- < 27. for some fixed value of n. Then, under S the probability that arm 1 is never pulled again after its n first selections is larger than 1/2, in which case the regret is larger than A(T n). It thus holds that Ri 2 0.5 A PPS)- (T (T-n))) nn)+-
Step 2: We lower bound IP(S) for well-chosen value of n ng + n11 for two integers and ni. Consider the following scenario: in preliminary phase, arm collects only -1 rewards from its first no pulls, and in next phase it collects 7, rewards with an empirical mean satisfying Pn, ~ -A, while the number of +1s received never more than the number of -1s throughout this phase. First, we derive in Lemma 6 lower bound on the probability of this scenario. Then, we prove (Lemma 7 that setting n O (Tog(T)) and ng = (log(n) r) guarantees that this scenario is included in the event S. From a high-level perspective, the preliminary phase only serves to make Png+1 small enough to reduce the impact of the ordering of the rewards in the next phase, and the scaling of the lower bound (ignoring log terms) comes from the choice of ng.
Lastly, we emphasize that the result should hold with random sub-optimal arms (further assuming that they are "lucky enough" throughout the trajectory), but constant rewards simplify the proof.
Critical regime We remark that Theorems I and do not provide explicit results about the regret of SGB when y x A, that we thus call the critical regime. However, by comparing both theorems and their proofs we conjecture that, some difficult instances, SGB satisfies E [(1 pc x #

---

Indeed, after summation this scaling makes the failure regret admit 12(T lower bound when 7 > A (see Thm. 2). If there is a smooth interpolation between the logarithmic and polynomial regime, then there might exists small range of learning rates 1) ~ A for which the failure regret could be logarithmic on difficult instances. This is supported by experiments from Section f and Appendix [ observe relatively smooth evolution of performance metrics (regret, percentage of failed runs) with the learning rate. In the experiments, the critical learning rates, such as 1j = A when K 2, provide good empirical performance.
3 Results for K >>> 2 arms
In this section, we explore the theoretical guarantees of SGB for K > We start by proving that the learning rate must decrease with the number of arms in order to guarantee logarithmic regret. Then, we provide preliminary results for upper bounding the regret of SCB by generalizing the proof of Theorem | We also provide some intuition about why this case is significantly harder than K = 2, and what we believe to be the right critical scaling for r7.
3.1 Necessary scaling of rj in K for logarithmic regret
In this part, we exhibit a necessary condition on the learning rate for logarithmic regret, depending on the number of arms K. While proved Theorem 22 by directly analyzing difficult instance, on the contrary, the proof technique of Theorem exxplots the efficiency of SCB on an easy problem instance, from which deduce the result using lower bound arguments. We start by presenting the regret upper bound leading to this conclusion.
Lemma 1 (Regret upper bound on easy instance). Let E JK be MAB defied by v1 do and 1/2 = 1/K- = Ó-A.foo for some A > Then, for any learning rate 1, SGB satisfies
1 log (1 (K 1)T
K²
(
E )
K
AA E R S
log
(1 E)N
E
Proof sketch. We present the full proof in Appendix D.2 We first show that, since rewards are deterministic, arm 1 remains the mode of the sampling distribution for all steps and Pk.,/ PP,,/Pi, non-increasing for any sub-optimal arm k. Hence, we establish that P1, 2 1 - happens in finite expected time for any threshold s E (0, 1), which gives the O(e-1) term of the bound. We then prove that, from that stage, - Pi, decreases exponentially fast with the total number of sub-optimal plays. This careful decomposition allows us to obtain logarithmic term that does not involve multiplicative factor of K In Appendix D.2 and G.3 we further discuss how this result might be tightened by a factor K-1 which we prove formally for K = 2 (Lemma 14).
K
Implication the consistency of SGB Lemma D suggests that, for fixed horizon, the regret of SGB can be arbitrarily small for large 17 in some easy bandit instances. As consequence of the well-known asymptotic regret lower bound 36 37), this must come at cost on other instances. We dedicate Appendix D.I thorough presentation of the lower bound we use in the proof (restated in Theorem. (). and other technical results needed to derive the following theorem.
Theorem 3 (Polynomial regret for 2 K-1). Let A E (0, 1) and a E (0, 1). Consider the class FK of K K-armed bandit instances with minimum gap least A. If the learning rate satisfies
r A(1 a) log
24 1-
K-1
then there exists an instance E FK such that the regret of SGB satisfies
Rr ((TT).
Proof. Setting V Tog(3 + T), Lemma 1 yields Ry 1 log(T) O( P(yTo (T)) for the instance #1 (80, S_A. ..., , 8_a} JKK for any 7, O. In contrast, Theorem 6 (adaptation of the Lai & Robbins lower bound) and Lemma IT (specialization to Dirac distributions) imply that Rr
any policy with regret Rr = O(T)) on all instances in F should satisfy lim inf (o >
(K (X-1)(1-a) log(T) on this deterministic instance v1- Combining these two results proves the theorem.
log 1og(1+,22 24
14,25)

---

Discussion The fact that the learning rate has to be inversely proportional to the number of arms might be surprising at first sight. An intuitive explanation that the update rule of f1,, agnostic to the number of arms: for any step /. 2 1, the distribution of 801. conditioned on H is the same if arm 1 faces single arm (K = 2) or a mixture of K - identical arms. Hence, in order to reduce the speed of convergence of Pi.t. and thus guarantee sufficient exploration of the K" 1 alternatives, it is necessary to make the learning rate decrease with K. contrast, standard bandit policies typically have a separate exploration mechanism for each arm, determined by their respective observations.
Conjectures Combining Thm. 2 and 3 we establish that logarithmic regret is only achievable for " S A K-11 This suggests that the critical threshold separating logarithmic from polynomial regret may depend on the ratio A/K. We explore this idea further in Appendix D.3] where we present and motivate two conjectures. Conjecture | on an "casy" instance. Conjecture considers a construction with one slightly sub-optimal arm and many very sub-optimal arms: V1 Rad(A), 12 ōo. and 1/3 the critical rate, above which SGB may suffer polynomial regret, is near K
inspired by Theorem 3 posits that regret cannot be too small
MKK 8-1. Both suggest that 2A for K-armed bandits.
3.2 Tools for upper bounding the regret
In this section we propose some tools derive upper bounds on the regret of SGB for K> 2. While our current results do not lead to a complete regret upper bound in general, we introduce promising preliminary results, with full regret bounds in some cases, showing the potential of the techniques introduced in this paper for future investigation on this problem.
Let us introduce M1 supke SuPrE|T] B[e"t.). Then, our first result of this section states that T0 is always logarithmic in T when K 2, detailed below.
Lemma 2. For any horizon T 2 1 and for any learning rate 1,, parameter 01 of SGB satisfies
E 001r+1] S log 1+ n |
112 e"
(K - 1) MM Mr. T A 11 (1-K-))(log[T) (Iog(T) +4)
2
We prove the lemma in Appendix F:2 with distinct proofs for the two bounds. The first one is based on Jensen inequality, similarly to the proof of Thm. [ For the second bound, we first prove that
the expectation of the minimum parameter TE| [[[mnn=[[]] @x,e] cannot be smaller than - log(T). We
then deduce the bound scaling with (K - 1) Iog(T) by using the linear relationship (9) between all parameters. The first bound tighter asymptotically if M1 o(T -2), which we think should hold at least for small enough 7). but proving it formally requires new techniques. Nonetheless, the potentially sub-optimal K 1 factor only appears in the upper bound, and does not translate into supplementary constraint on how to tune SGB to achieve logarithmic regret.
We now introduce upper bound on the failure regret obtained by generalizing the proof of Thm. Lemma 3. For any instance v E FK and learning rate satisfying C,C, < A, SGB satisfies
T
nHe + n" W.
)) with
K-1
E
Σ
p1,))
S K K.nl m1(A n),))
K K+E
PI.
H,- = Ex (L. - -p),))a)) and W, = -E Pi Pk..) - P1., - pI.))?
This result, proved Appendix F44 matches the upper bound on the failure regret in Thm. D for K= since H, = W;- = 0 in this scenario. Unfortunately, upper bounding the additional terms depending on H, and W, is intricate in general. However, these terms can be non-posithe non-positive under favorable scenarios, and are thus not necessarily causing regret. In Appendix F.4.1 we detail some properties and intuition about H,, and W,, that can be useful for future works. Intuitively, W. reflects how uniformly the probability - P1,t is divided among sub-optimal arms, leading to increased variance for parameter updates. Moreover, H, > O can occur in a scenario where increasing the probability of arm whose gap is lower than the expected gap of the policy might be preferable to increasing Pi..- Finally, we remark that Lemma Bddes not hint that 1) should depend on K, suggesting that the scaling found in Thm. 3 is required to further upper bound the newly introduced terms.
We finally present a complete regret upper bound when the gaps are identical among all arms, that we prove in Appendix E As expected from previous results, the main difficulty is to upper bound the
8

---

failure regret. although we can exploit the fact that H, = O in the case of identical gaps. The factor K in the tuning of the learning rate emerges from the initialization P1,1 K-
Theorem 4 (Logarithmic regret for identical gaps). Let v E FKK be a MAB instance satisfying 2 A A. for some A (0, 1). Then, the regret of SGB tuned with a learning rate n
satisfying n
2 is upper bounded as follows,
K+2
R7 (V) - [[ + 2(K -) 1)
2
log(T) + Tu for some constant T. >> 0.
"
Finally, we present Lemma 15 in Appendix D result analogous to Corollary I With a refined analysis of the constant r, we prove that a tuning yr = 1/vTT yields regret bound RT X K KVT. Thus, in this setting horizon-dependent learning rate can also be used when A is unknown.
4 Experiments
We now provide empirical support for the theoretical results presented in previous sections, focusing on the performance of SGB as a function of its learning rate 1). We present additional experiments in Appendix G where we also empirically compare SGB to some standard bandit algorithms.
To illustrate Thm. and 2 we first consider a two-armed bandit experiment with distributions 111 (0.10 and 212 Rad(O) on which we test SGB with four different learning
Experimental Setups
yields logarithmic regret (Thm. and 2 Assuming that Thm. Dis tight, and using A R A, we expect 7)s and 1/4 to suffer polynomial regret of resp. order /T and 74/5 For the second experiment, we consider K 10 arms and the instance defined by V1 Rad 1/2 dg and 1/3 = 1100 = 5-1, in order to support Thm. 3. and more precisely the conjecture that the critical learning rate 1) 2A/K K for K-armed problems. Thus, we compare the performance of SGB A A, 5A For each setup, we run 104 independent 5
rates: (Ma))
( A, 22, 5A). Among these, 7/
M22 = A is the critical threshold identified in Section
with learning rates (лK)εt( { A 24
A
K K
trajectories of SGB over horizon T 2- 104. Our results are displayed in Figures I and respectively.
The results of both experiments support the theoretical findings developed in this work. In each setting, only learning rates below the critical threshold 2A/ K (specifically, 7/2 and 77)) lead to a logarithmic average regret. For the rate just above the critical threshold (173). the additional statistics presented alongside the average regret curves highlight the fragility of this tuning. In particular, the average regret shifts closer to the 90th percentile across runs, indicating noticeable increase in failed trajectories compared to smaller learning rates. For K = 2, the table in Fig. I confirms this finding.
Results
The figures also remarkably illustrate the regret decomposition of Eq. ( particularly the right panel of Figure 2 which shows the empirical distributions of regret across trajectories at time T. These distributions are distinctly bimodal. A subset of runs exhibits post-convergence behavior, with regret concentrated around value proportional to 7) log(TT) (see Eq. 77 and Lemma 2). We highlight this by plotting dotted lines that scale the average regret of SGB tuned with 7/1 used as reference due to its negligible failure rate- by the factor 7/, /// for each E [5]. These reference lines align well with the "success" mode of their respective learning rates. At the same time, the distributions also reveal a failure mode, whose mass substantially increases with the learning rate (30% for 17s). Across all configurations, only small fraction of trajectories deviate from these two dominant modes.
Connections with related works Prior works [38 39 documented multimodal regret distributions for certain CCB-based algorithms. and derived impossibility results for the tail behavior of regret, later strengthened in [40]. Prop. 7 from 440] particularly resonates with our findings on SGE let b > 0, and æ be policy with regret Rr S (1 + A, lT) on every instance v E FKK where A, logg(T)) denotes the Lai-Robbins lower bound (Eq. (17.. letting = 0). Then, for some > O. the empirical regret Ry satisfies Pr P=(R. cT) x (1++))) (we refer to the paper for a more formal statement). This closely mirrors our theoretical and empirical observations on SGE, in particular the connection between the learning rate and the failure regret. We conjecture that the critical value of r) aligns the logarithmic regret term with the best logarithmic bound A, log(T) in some problem instances, and that the failure regret can be derived from the above polynomial-decaa bound, probably

---

100
SGB, to 24
SGB,
11
A
A
2A
5A
T
250
Regget
200
SG6,
Bound of Th.1 for
10
0.7
2.3
7.6
19.9
104
0.2
1
5.4
17.6
130
2 10
0.06
0.5
3.6
15.5
300
% of the 10* runs with empirical regret larger than TA (regret the uniform policy)
2
Time
Figure 1: K 2, average regret and 10 90% percentiles (dashed lines) for 10 independent runs up to 7 2 10a (Leftt) and percentage of trajectories with emp. regret larger than TA (Right).
extending to negative E (-1,0) These connections suggest that the aforementioned results could be generalized further, at least for some policy classes such SGB. Finally, note that 441 studied conditions under which exponential decay of the regret distribution is possible, but unfortunately one of them is that the problem-dependent regret polynomial. Strong decay of the distribution of empirical regret is incompatible with logarithmic regret.
f 5A
SGB
5G0. Q =
SGB
Emp Begget
SG8
5GB. 0.
0000
300
2500
5030
7506
10:00
12500
19083
17520
Time
Empirical regret at
Figure 2: K 10, average regret and 10 90% percentiles on 10 independent runs up to horizon
T= 2 10 (Left), and distribution of the empirical regret at time (Right).
5
Conclusion
This work sheds light on the theoretical properties of SGB, a simple policy gradient algorithm for bandits, whose behavior is governed by learning rate In contrast to much of the existing literature, which largely adopts an optimization perspective, we approach the problem through the lens of regret analysis. For two-armed bandits, gap A is both necessary and sufficient to achieve logarithmic regret. For general K K-armed settings, results indicate that the critical learning rate threshold scales as 2A/ K, and we provide technical tools and insights that could serve as a foundation for a full regret characterization contexts. Our theoretical and empirical findings reveal fundamental trade-off in tuning SGB: while larger learning rates may enhance performance in favorable scenarios, exceeding the critical threshold is consistently
show that knowledge of lower bound on the sub-optimality
SGB in broader
significantly raises the risk of failure-thh -tht is, trajectories which the optimal under-sampled. Further understanding and managing this trade-off is essential for deploying SGE and its variants reliably and effectively, and offers compelling direction for future research.
Acknowledgments and Disclosure of Funding
D. Baudry, S. Vary, and P. Rebeschini were funded by UK Research and Innovation (UKRI) under the UK government's 's Horizon Europe funding guarantee [grant number EP/Y028333/1). Johnson is funded by EPSRC through the Modern Statistics and Statistical Machine Learning (StatML) CDT (grant no. EP/S023151/1), The authors would also like to thank the anonymous reviewers for their insights and suggestions, Tor Lattimore for directing them to relevant papers at an early stage of the project, Julien Aubert for generously sharing his insights and ideas on the topic, and Rémy Degenne and Emilie Kaufmann for a discussion that helped us improve the statement of Theorem 3,
10

---

References
The Annals of [1] Jincheng Mei, Zixin Zhong, Bo Dai, Alekh Agarwal, Csaba Szepesvári, and Dale Schuurmans. Stochastic gradient succeeds for bandits. In International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research. PMLR, 2023.
[2] Jincheng Mei, Bo Dai, Alekh Agarwal, Sharan Vaswani, Anant Raj, Csaba Szepesvári, and Dale Schuurmans. Small steps no more: Global convergence of stochastic gradient bandits for arbitrary learning rates. In Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, NeurIPS 2024, Vancouver. BC, Canada, 2024.
[3] Herbert Robbins and Sutton Monro. stochastic approximation method. Mathematical Statistics, 22(3):400 407, 1951.
[4] Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforce- ment learning. Machine Learning, 8(3-4):229-256) 1992.
[5] Richard S. Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. In Advances in Neural Information Processing Systems, volume 12, 2000.
[6] David Silver, Guy Lever, Nicolas Heess, Thomas Degris, Daan Wierstra, and Martin Riedmiller. Deterministic policy gradient algorithms. In International Conference on Machine Learning. 2014.
[7] Timothy P. Lillicrap. Jonathan J. Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. In 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, 2016.
[8] John Schulman, Sergey Levine, Philipp Moritz, Michael Jordan, and Pieter Abbeel. Trust region policy optimization. In International Conference Machine Learning, 2015.
[9] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal 2017.
policy optimization algorithms. arXiv preprint arXiv:1707.00
[10] Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off- policy maximum entropy deep reinforcement learning with stochastic actor. In International Conference on Machine Learning, 2018.
[11] Richard Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. The MIT Press, second edition, 2018
[12] Zafarali Ahmed, Nicolas Le Roux, Mohammad Norouzi, and Dale Schuurmans. Understand- ing the impact of entropy on policy optimization. In Proceedings of the 36th International Conference Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research. PMLR, 2019.
[13] Jincheng Mei, Chenjun Xiao, Csaba Szepesvári, and Dale Schuurmans. On the global con- vergence rates of softmax policy gradient methods. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020. Virtual Event, volume 119 of Proceedings of Machine Learning Research. PMLR, 2020.
[14] Jincheng Mei, Chenjun Xiao, Bo Dai. Lihong Li, Csaba Szepesvári. and Dale Schuurmans. Escaping the gravitational pull of softmax. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
[15] Gen Li, Yuting Wei, Yuejie Chi, and Yuxin Chen. Softmax policy gradient methods can take exponential time to converge. Math. Program., 201(1), 2023.

---

[16] Alekh Agarwal, Sham M. Kakade, Jason D. Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. J. Mach. Learn. Res., 22. 2021.
[17] Shivam Garg, Samuele Tosatto, Yangchen Pan, Martha White, and Rupam Mahmood. An alternate policy gradient estimator for softmax policies. In International Conference on Artificial Intelligence and Statistics, AISTATS 2022. 28-30 March 2022, Virtual Event, volume 151 11 of Proceedings of Machine Learning Research. PMLR. 2022.
[18] Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2):235-256, 2002.
[19] Shipra Agrawal and Navin Goyal. Analysis of Thompson sampling for the multi-armed bandit problem. In Proceedings of the 25th Annual Conference on Learning Theory, 2012.
[20] Kaiqing Zhang, Alec Koppel, Hao Zhu, and Tamer Basar. Global convergence of policy gradient methods to (almost) locally optimal policies. SIAM J. Control. Optim., 58(6), 2020.
[21] Yuhao Ding, Junzi Zhang, and Javad Lavaci. Beyond exact gradients: Convergence of stochastic soft-max policy gradient methods with entropy regularization. CoRR, abs/21 10. 17, 2021.
[22] Junyu Zhang, Chengzhuo Ni, Zheng Yu, Csaba Szepesvári, and Mengdi Wang. On the conver- gence and sample efficiency of variance-reduced policy gradient method. In Advances in Neural Information Processing Systems 34: Anmual Conference on Neural Information Processing Systems 2021, NeurlPS 2021, December 6414, 2021, virtual, 2021.
[23] Michael Lu, Matin Aghaei, Anant Raj, and Sharan Vaswani. Towards principled, practical policy gradient for bandits and tabular mdps. RLJ, 1, 2024.
[24] Rui Yuan, Robert M. Gower, and Alessandro Lazaric. A general sample complexity analysis of vanilla policy gradient. In International Conference Artificial Intelligence and Statistics, AISTATS 2022, 28-30 March 2022, Virtual Event, volume 151 of Proceedings of Machine Learning Research. PMLR, 2022.
[25] Simon Weissmann, Sara Klein, Waiss Azizian, and Leif Döring. Almost sure convergence rates of stochastic gradient methods under gradient domination. CoRR, abs/2405. 13592, 2024.
[26] Sara Klein, Simon Weissmann, and Leif Döring. Beyond stationarity: Convergence analysis of stochastic softmax policy gradient methods. In The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024, 2024.
[27] Sara Klein, Xiangyuan Zhang, Tamer Basar, Simon Weissmann, and Leif Döring. Structure matters: Dynamic policy gradient. CoRR, abs/2411.0499 1.0491,, 2024.
[28] Jincheng Mei, Wesley Chung, Valentin Thomas, Bo Dai, Csaba Szepesvári, and Dale Schuur- mans. The role of baselines in policy gradient optimization. In Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, 2022.
[29] Neil Walton and Denis Denisov. Regret analysis of markov policy gradient algorithm for multiarm bandits. Math. Oper. Res., 48(3):1553-1588 August 2023. ISSN 0364-765X.
[30] Olivier Cappé, Aurélien Garivier, Odalric-Ambrym Maillard, Rémi Munos, and Gilles Stoltz. Kullback-Leibler upper confidence bounds for optimal sequential allocation. Annals of Statistics, 41(3):151611411 2013.
[31] William R Thompson. On the likelihood that unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):285-29,, 1933.
[32] N. Korda, E. Kaufmann, and R. Munos. Thompson sampling for mie-dimensional exponential family bandits. In Advances in Neural Information Processing Systems, 2013.
[33] Stéphane Boucheron, Gabor Lugosi, and Pascal Massart. Concentration inequalities a non asymptotic theory of independence. Oxford University Press, 2013.
12

---

[34] Yanwu Yang and Panyu Zhai. Click-through rate prediction in online advertising; A literature review. Inf. Process. Manag., 59(2):102853, 2022.
[35] Anirban Bhattacharjee, Sushant Vijayan, and Sandeep Juneja. Best arm identification in rare events. In Proceedings of the Thirty-Ninth Conference on Uncertainty in Artificial Intelligence, volume 216 of Proceedings of Machine Learning Research, pages 163-172. PMLR, 31 Jul-04 Aug 2023.
[36] Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Ad- vances in applied mathematics, 6(1):4-22 1985.
[37] Apostolos N Burnetas and Michael N Katehakis. Optimal adaptive policies for sequential allocation problems. Advances in Applied Mathematics, 17(2):122-142, 1996.
[38] Jean-Yves Audibert, Rémi Munos, and Csaba Szepesvári. Exploration-explotttton tradeoff using variance estimates in multi-armed bandits. Theor. Comput. Sci., 410(19):1876-1902 2009.
[39] Antoine Salomon and Yves Audibert. Deviations of stochastic bandit regret. In 22nd International Conference on Algorithmic Learning Theory, 2011.
[40] Lin Fan and Peter W. Glynn. The fragility of optimized bandit algorithms, 2024.
[41] David Simchi-Levi, Zeyu Zheng, and Feng Zhu. Stochastic multi-armed bandits: Optimal trade-off among optimality, consistency, and tail risk. In Advances in Neural Information Processing Systems 36, NeurlPS 2023, 2023.
[42] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[43] Aleksandrs Slivkins. Introduction multi-armed bandits. Found. Trends Mach. Learn., 12 (1-2), 2019.
[44] Rajeev Agrawal. Sample mean based index policies with (log n) regret for the multi-armed bandit problem. Advances in Applied Probability, pages 1054-1078, 1995.
[45] Olivier Chapelle and Lihong Li. An empirical evaluation thompson sampling. In Shawe- Taylor, R. Zemel, P. Bartlett, F. Pereira, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 24. Curran Associates, Inc., 2011.
[46] Emilie Kaufmann, Nathaniel Korda, and Rémi Munos. Thompson sampling: An asymptotically optimal finite-time analysis. In Algorithmic Learning Theory- 23rd International Conference, ALT 2012, 2012.
[47] Junya Honda and Akimichi Takemura. Optimality of thompson sampling for gaussian bandits depends on priors. In Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics, AISTATS 2014, Reykjavik, Iceland, April 22-25, 2014, 2014.
[48] Charles Riou and Junya Honda. Bandit algorithms based on Thompson sampling for bounded reward distributions. In Algorithmic Learning Theory, pages 777-826. PMLR, 2020.
[49] Junya Honda and Akimichi Takemura. An asymptotically optimal policy for finite support models in the multiarmed bandit problem. Mach. Learn., 2011.
[50] Junya Honda and Akimichi Takemura. Non-asymptotic analysis of a new bandit algorithm for semi-bounded rewards. J. Mach. Learn. Res., 16:3721-3756. 2015.
[51] Craig Boutilier, Chih-wei Hsu, Branislav Kveton, Martin Mladenov, Csaba Szepesvari, and Manzil Zaheer. Differentiable meta-learning of bandit policies. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances Neural Information Processing Systems, volume 33, pages 2122-2134. Curran Associates, Inc., 2020.
[52] Jie Bian and Kwang-Sung Jun. Maillard sampling: Boltzmann exploration done optimally. In Proceedings of the 25th International Conference on Artificial Intelligence and Statistics, AISTATS 2022, 2022.
13

---

[53] Hao Qin. Twang-Sung Jun, and Chicheng Zhang. Kullback-leibler maillard sampling for multi-armed bandits with bounded rewards. In Advances in Neural Information Processing Systems 37: Annual Conference Neural Information Processing Systems 2023, NeurIPS 2023, 2023.
[54] Branislav Kveton, Martin Mladenov, Chih- Wei Hsu, Manzil Zaheer, Csaba Szepesvari, and Craig Boutilier. Meta-learning bandit policies by gradient ascent, 2021.
[55] Dorian Baudry, Kazuya Suzuki, and Junya Honda. A general recipe for the analysis of random- ized multi-armed bandit algorithms. CoRR, abs/2303. 00058,, 2023.
[56] Branislav Kveton, Csaba Szepesvári, Mohammad Ghavamzadeh, and Craig Boutilier. Perturbed- history exploration in stochastic multi-armed bandits. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, LJCAI 2019, 2019.
[57] Branislav Kveton, Csaba Szepesvari, Sharan Vaswani, Zheng Wen, Tor Lattimore, and Moham- mad Ghavamzadeh. Garbage in, reward out: Bootstrapping exploration in multi-armed bandits. In International Conference on Machine Learning, pages 3601-3610. PMLR, 2019.
[58] Akram Baransi, Odalric-Ambryn Maillard, and Shie Mannor. Sub-sampling for multi-armed bandits. In Proceedings of the European Conference on Machine Learning, page 13, 2014.
[59] Hock Peng Chan. The multi-armed bandit problem: An efficient nonparametric solution. The Annals of Statistics, 48(1 (8(1)3336-373, 2020.
[60] Dorian Baudry, Emilie Kaufmann, and Odalric-Ambrym Maillard. Sub-sampling for efficient non con-parametric bandit exploration. In Advances in Neural Information Processing Systems, 2020.
[61] Dorian Baudry, Yoan Russac, and Olivier Cappé. On Limited- -imited-Memory Subsampling Strategies for Bandits. In ICML 2021- International Conference on Machine Learning, Vienna / Virtual, Austria, July 2021.
[62] Dorian Baudry, Patrick Saux, and Odalric-Ambrym Maillard, From optimality to robustness: Adaptive re-sampling strategies in stochastic bandits. In Advances in Neural Information Processing Systems, 2021.
[63] Daniil Tiapkin, Denis Belomestny, Eric Moulines, Alexey Naumov, Sergey Samsonov, Yunhao Tang, Michal Valko, and Pierre Ménard. From dirichlet rubin: Optimistic exploration in RL without bonuses. In International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, 2022.
[64] Joseph Bertrand. Solution d'un probleme. CR Acad. Sei. Paris, 105(1887)3369, 1887.
[65] Marc Renault. Lost (and found) in translation: André's actual method and its application to the generalized ballot problem. The American Mathematical Monthly, 115(4):358 363, 2008. ISSN 00029890, 19300972.
[66] Herbert Robbins. A remark on stirling's formula. The American mathematical monthly, 62(1):
26-29, 1955.
[67] Emilie Kaufmann. Analysis of bayesian and frequentist strategies for sequential resource allocation. (Analyse de stratégies bayésiennes et fréquentistes pour I' l'allocation séquentielle de ressources). PhD thesis, Télécom ParisTech, France, 2014.
[68] Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet. Bounded regret stochastic multi- armed bandits. In Shai Shalev-Shwartz and Ingo Steinwart, editors, Proceedings of the 26th Annual Conference on Learning Theory, volume 30 of Proceedings of Machine Learning Research, Princeton, NJ, USA, 2013. PMLR.
[69] Dorian Baudry, Fabien Pesquerel, Rémy Degenne, and Odalric-Ambrym Maillard. Fast asymp- totically optimal algorithms for non-parametric stochastic bandits. In Advances in Neural Information Processing Systems, volume 36, 2023.
14

---

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: The scope of the paper is clearly stated in Section The contributions are clearly summarized in Section 1.3
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made 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.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
where we precisely discuss the type of guarantees that we were able to achieve with our analysis, and what we leave for future works.
Justification: The scope of our analysis is well-detailed in Section 1.3
Guidelines:
The answer NA means that the paper has 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 separate "Limitations" section in 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 on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or 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 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 in the paper. The authors should use their best 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.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
15

---

Answer: [Yes]
Justification: We present detailed proof of Theorem in the main paper, and for the other results we present proof sketch and detail the proofs in dedicated appendices, that are all referenced in the main paper.
Guidelines:
The answer NA means that the paper does 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 it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: will make our code available with the paper at the time of publication. Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is 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 novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it 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 is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all 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 new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or 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 or verifying the results.
5. Open access to data and code
16

---

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?
Question:
Answer: [Yes]
The pseudo-code is provided, and the main algorithm is very simple to implement. Code will be provided with the paper.
Justification:
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/
for more details.
While 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 NeurIPS code and data submission guidelines (https
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, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: We carefully detailed the choice of parameters each setup, since this precisely the focus of the theoretical results of the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of 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: we mainly report regret curves on a fixed number of independent runs. For each experiment, this number is sufficiently large that the average curves are smooth, and we reported 10 90%% quantiles, to compare algorithms more precisely.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoo bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
17

---

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).
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 to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
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?
Question:
Answer: [Yes]
Justification: the experiments be reproduced standard personal laptop. For the time horizons considered in the paper, each individual run is very fast (few seconds), and the execution time is purely proportional to the number of runs, the results be reproduced very fast on smaller scale.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the 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 didn't 'tttt make it into the paper).
paper (e.g., preliminary or failed experiments that
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: work is thcoretical and does not have direct ethical implications.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations 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: we discuss the impact that the work can have on the understanding of an approach at the foundation of the field of reinforcement learning, but do not discuss the impact of the field itself on society, which is arguably outside the scope of work of theoretical nature.
18

---

Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious 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 partieular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out. For example, it is legitimate to point 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 a generic algorithm for optimizing neural networks could enable people 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 MI...
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Experiments are performed on synthetic data.
Guidelines:
The answer NA means that the paper poses 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 is 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
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: Experiments are performed on synthetic data.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
19

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the datasets.paperssiii paperswi thcode. www.coo//aaaaa datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's 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:
Experiments are performed on synthetic data.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodl 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. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
No experiment involved human participants.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurlPS 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 equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
No experiment involved human participants.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
20

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
The core method development in this research does not involve LLMs as any important, original, non-standard components. LLMs were primarily used for minor rephrasing and syntax checks.
Justification:
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should not be described.
www.eeerrpp....eoeeeeeeeeeeeeeee /
21

---

A Supplementary material for Section [
A.1 Pseudo-code of SGB
We detail below the pseudo-code of SCB for a constant learning rate v)- This implementation only needs slight modification to consider a time-varying learning rate, as discussed in Section 2 an input sequence (11)221 should be provided, and should be replaced by in the parameter update.
Algorithm Stochastic Gradient Bandit (SCB)
Input: Learning rate 77 > 0
Set [0[K) (0)ke(K]
Uniform initialization
for / 2 do
For E [K]: set Ph, Σj- chi
b Compute the sampling probabilities
Pull A, pt = (FK,) collect reward r
Sample arm, collect reward
for & E [K] do
Set 0x,411 = 0x + mpr {(1 PA, = - PP. k)}; Parameter update
Verification that SGB performs stochastic gradient ascent For simplicity of notation, consider
parameters = (#x) and define = (PK) by Vk [K], ER e.y
We further
define S = => e for simplicity, and the value of the policy V Σk PRPR- Then, for any A [K]. holds that
0v
Oy
Σ
(1j
00,
00g
We then obtain that 80
dpe
2 20
Pa
(1 ps)) and, for j +
0p: 00
5
-PpPk.
Hence, by summing we obtain that
0V
Vk E [K],
= pu(1 - p4)p Ps Σ PJHj-
80k
j#k
which matches the second term of Equation (5). by adapting the notation. This verifies that the expected parameter update of SGB matches the gradient of the policy, up multiplication by the learning rate
A.2 Some elementary properties of SGB
To enhance clarity, we recall that time step t 1, the sampling probabilities of all arms for SGB are given by the softmax transform of some parameters
(On,)RE[K]
R Vk E [K]
Pk.t exp (Bx.t)
and that for a learning rate the parameter are updated as follows,
Vt 1:
Out+1 0z,1 + -7 with 80k, == (1 Pk.)) r, 1 1(A, = k) Pk.e-T 1(A, + k).
present some properties that are particularly useful for our analysis.
The parameters are linearly dependent From we can verify that
50k, rt
(1
(1- PA.) (L-PAt)
Σ
PJ.
0.
A
and as a consequence we obtain the following relation
21 1, 80 =
Vt >
>
θ 0.
22

---

This equation shows that the growth of the parameter of the best arm 01, is bound to how much the parameters of the sub-optimal arm can negative, which is crucial ingredient in the proof of Lemma 3 Furthermore, for K = 2 it holds that 0,, = - 22 which simplifies the expression of the sampling probability. For instance, for the sub-optimal arm 2 it holds that
0
201
If = 2: v2 P2.
1 t-e--t 201 Se
201, -00
(10)
e e + c
In the same setting this relation furthermore leads to
P1,t
P1.t
201,.
(11)
P1,t
P2.
The variance of updates scales with the expectation Again starting from 4 we analyze the squared variation of the parameters. For all arms & [K], it holds that
(00x,)) = r ((1 (k,)) ( (A = k) + pi. (AA k)).
using that 1(A, )2 1(A, = .) and that L(A, 1)1 k) 0. For all k [K], we now
introduce si = 18[r? Ae = k). and define 2² = maxjE(K] si. We then obtain that
E, [(00x..) S o Pa, (1 - pu.1)² p Σ of Pie jfk
that we can upper bound follows,
E, [(80x.)) S x² (1 pk.1) +r, Pt.))) = 5² pk. Pk.1)
(12)
Again, this property is essential for our analysis. For instance, it implies that
A s2 EE,((80,.)]]
E, 160,11 2 A A..1..111 - (p.()
2
Iterative formula for the sampling probabilities Lastly, inspired by standard proofs in bandits (see Chapter 11 in [42),, we can express the following recursion on the sampling probabilities, which we use in the proof of all the regret upper bounds presented in this paper.
Vk E [K], 121:
Ph,++
Σ chet
Pk.
Ej= Pse en60,..
(13)
which is direct using that Vj E [K] 02 +1 50,,1, and by dividing both the numerator and denominator by プ eii..
A.3 Detailed literature review on Multi-Arm Bandits
The multi-armed bandit (MAB) problem has inspired a vast body of research, with many algorithms proposed to balance exploration and exploitation. In this section, we introduce some of the most standard frameworks developed in the literature. particular, we focus on algorithms proposed to optimize problem-dependent regret bounds in stochastic bundits, where rewards are drawn indepen- dently at random from fixed distributions, since this the setting considered this paper. We refer to for comprehensive surveys and broader discussions, including (but not limited to) adversarial
42 43 bandits, problem-independeen independent bounds, and Bayesian regret bounds in stochastic bandits.
The classical optimism in the face of uncertainty principle underlies the popular UCB family of algorithms. The original UCBI policy 44 [8] achieves logarithmic regret under bounded or sub-Gaussian rewards. Later, the KL-UCB framework [30 was proposed, and proved to yield asymptotically optimal policies for various families of distribution (e.g. bounded distributions and lingle-paramete exponential families), in the sense that its regret upper bounds match the asymptotic lower bound of Lai and Robbins (36) (see Appendix [D. for details). These algorithms rely on carefully constructed confidence bounds, involving the information-theoretiee Kinf divergence (formally defined in Theorem 6) and thus better exploit the statistical properties of distribution classes than simpler UCB variants.
23

---

A second major class of policies is Thompson Sampling (TS), which dates back to Thompson 31 and has enjoyed renewed popularity since the empirical study of Chapelle and Li 445 Regarding frequentist analyses, its theoretical foundations were first rigorously established for Bernoulli rewards
19 46.. and further extended to Gaussian 47 single-parametri exponential families [32,, and
non-parametric bounded distributions [48] TS is inherently Bayesian, using posterior samples of arm parameters to guide exploration. In all of these settings, TS has been proved to achieve asymptotic
optimality under appropriate choice of prior distribution. For instance, for Bernoulli rewards uniform prior and Beta posterior yields such guarantees.
A third family. Minimum Empirical Divergence (MED) and its deterministic counterpart IMED aim to directly minimize regret by exploiting empirical divergence estimates [49 (50,, often inspired by the Kinf quantity like KL-UCB approaches, but do not rely on confidence bounds in the algorithm designs. Recently, this approach has been rediscovered under the name SoftElim [11] or Maillard Sampling
(MS) 12 53
and shown to perform optimally under general sub- Gaussian and bounded settings. have analyzed MED) through a volicy-gradien lens in contextual extensions. A recent work 155 proposes unified problem-dependent analysis of MED for generic distribution classes, and establishes a strong connection between MED and (a variant of) Thompson Sampling using non-informative prior, showing that the sampling probabilities of sub-optimal arms under the two policies decrease at the same rate asymptotically.
Interestingly, 54
Beyond these three canonical families, number of works have explored nonparametric randomized strategies. These include bootstrapping- basstee based methods [36 [7], sub-sampling algorithms [58 61], and variants of the nonparametric TS algorithm [48 62 63 which connects to the Bayesian bootstrap 633. While SGB could be perceived as fitting into this line of randomized, data-driven policies, these approaches rely on fundamentally different principles. Indeed, the core ingredients of SGE are gradient ascent and stochastic approximation [3], while these approaches exploit the properties of sample statistics which, in particular, requires storing the entire history of observed rewards.
Hence, it is clear that the SGB policy stands apart from the classical design principles that shape the landscape of bandit algorithms with optimal sablem-dependent regret guarantees. In the following we elaborate on why this implies that the analysis of SGB must depart from standard techniques derived in previous bandit analyses. Nonetheless, we then detail how familiarity with these standard approaches still guided our investigation of the theoretical properties of SGB
Key differences between SGB and standard policies Fix a generic time step t. It clear from (4) that the sampling probabílities of SGB depend complex, nonlinear way on the entire sequence of past rewards, across all arms, and the exact order in which they were collected. For instance, consider the ratio pa, PPp.. for two arms (k, E [K]2. Using ) we obtain
Pk.
e E. F. ((1-p, PI, =k) PA... (A, PA, ((4,7)))
30B
This expression shows that the current sampling ratio cannot be deduced from simple summary statistics such as empirical means or counts. In contrast, standard policies typically admit arm- specific exploration mechanisms, whose analyses rely on the concentration of statistics derived from each arm's 's individual history.
To illustrate this, consider first the MED algorithm, which, like SGB, is randomized policy with explicit sampling probabilities. As shown by Baudry et al. (55), MED can be abstractly described using divergence function D mapping the empirical distributions (FR,))kEJK] (distibutions of rewards collected by each arm, respectively) and the best empirical mean (²)(t) max MR,t, to positive values. Then, using the sample sizes (f)(Ee) the sampling probability ratio is given by
MED
e (NNe(t)D(FF.aae (4))
MED
(N(())(()
P,t
Under mild conditions for divergences D, with similar properties the Kinf function, this form allows the regret to be decomposed according to events involving (t) and concentration of the empirical distributions, leading complete regret analysis [55] Theorem 1].
similar arm-specific structure underpins Thompson Sampling (TS), perhaps the most well-known class of randomized policies. While TS does not admit closed-form expression for its sampling
24

---

probabilities, its analyses rely on the arm-wis wise posterior distributions. In particular, modern problem-
dependent analyses 19 46
32 exploit quantities of the form
p ( 2 1() 1p (uz, 2 F)F,,t-1), for E
or their lower-tail counterparts, where Pk,t is a sample from the posterior distribution of arm k at time t. Crucially, these events depend only on the history of arm k. This structural decoupling is entirely absent in SGB, which lacks any notion of per-arm sampling mechanism or posterior.
Finally, consider the deterministic UCB family. Given arm-specific confidence indices UCBkk, the action at time is chosen as
A argmax UCB
and the analysis focuses on events such as {UCBL. 2 μu + cAs), for some values E (0, 1). As with TS, the confidence bounds are based solely arm-specific empirical distributions and are thus fully decomposable across arms. In stark contrast, even in highly simplified environments (e.g.. when only one arm yields random non-zero rewards), deriving concentration inequalities for the parameters (Ox, (e(KK] in SGB is challenging due to their entangled dependence on the global history.
Comparison of Eq. with similar regret decompositions in the literature While have highlighted the challenges of applying classical bandit analysis techniques to SGE, we now draw parallels between approach and prior works randomized policies for MAB.
Several studies have proposed general frameworks for analyzing the regret of randomized algorithms, including Thompson Sampling [42 Thm. 36.2], MED [55] Lemma 3], and bootstrap-based strategies [57] Thm. 11. [62] Thm. 3.1]. Although these analyses differ in presentation, they typically yield a regret decomposition of the following idcalized form (using the notation of the present paper):
(+) & C lTg(T) + PPPPPp 2 =) for some constant C 2 0.
These decompositions directly inspired our derivation of Eq. 7 and our interpretation of the two terms in the regret bound. particular, Riou and Honda 48 introduced and motivated the terminology of post-convergence and pre-convergence terms to describe the first (logarithmic term) and second components, respectively. We adopt a similar language in this work: we prove that the post- convergence term in Eq. (7) is logarithmic in T (Lemma and we show in Appendix that the second term of Eq. 7 that we call failure regret, satisfies
T Σ
I
(1 - P1.))
x
Σ 1=1
P(P1. 21
In regimes where the pre-convergence term dominates the regret, this equivalence shows that the second term of Eq. (7) highlights a failure of the policy to consistently converge to the optimal action logarithmic rate. This motivates our use of the term failure regret to characterize this term.
A.4 Detailed discussion on global convergence and finite-time regret
In this section we complete the discussion from Section I.I that the global convergence properties of SGB does not preclude poor performance finite horizons.
globally convergent policy with poor regret We start by formally proving the statement that asymptotic convergence guarantees do not necessarily imply non-trivial regret guarantees.
Proposition 1. Define an e-Greedy policy as follows: for t < K sample each arm once, and compute their empirical averages. Then, for the rest of time steps 2 K + select an arm uniformly at random with probability Et. ltlog f)-1, and otherwise play the arm with best sample average.
Then, the policy π converges asymptotically to an optimal policy, but its regret satisfies Rr Z TA for any K --areed bandit problem with Bernoulli distributions of non-zero means.
log(T)
Proof. The proof below assumes that arm is the only sub-optimal arm, but the arguments easily extend to cases where multiple arms are optimal. We start by proving the convergence claim. Since
25

---

(ts((tog(()) +oo, each arm is guaranteed to be explored infinitely often. Hence, after waiting long enough, the optimal arm is guaranteed to obtain sufficiently enough samples so that its empirical average will remain, for instance, over μ* - & for the rest of the trajectory. Similarly, over-estimation of any sub-optimal arm will be corrected, either thanks to the forced exploration scheme or because the arm was played a lot by appearing optimal for some time. This establishes that the policy converges to an optimal arm almost surely.
We now prove the (almost) linear regret lower bound. We prove that E, is decaying fast enough that there is non-negligible probability that there is no exploration at all during a trajectory of length T > K. In particular, this probability is lower bounded by
T
II t=k
1
t tlog(t) ) eIT=x loa (o
1
Pno exploration
==
Σi=K (log(t)
-izk
1 20 (no(s))
(ou((1)
clgg()-1
2 E
Disx PioR(ey
2V
log(T)
Hence, if this scenario occurs and the best arm collected a reward O for its first pull, while at least one other arm received +1 reward, then a sub-optimal arm is selected for the T KK remaining steps. The probability of this specific event is e.g. lower bounded by (1 (1) max#22 MM > 0, by
TA assumption that max Pi > 0. Hence, in this setting the regret of π satisfies Rr Z log(TT)
L Linear regret on finite horizon We now formalize the intuition that, for a fixed horizon T, using a learning rate that scales with log(T) in the softmax transformation may be problematic: small number of unfavorable rewards can drastically reduce the probability of selecting arm in subsequent rounds. Since log(T") remains moderate for practical values of T', this highlights a potential fragility of SGB when large learning rates used without additional assumptions on the reward distributions.
Proposition 2 (Linear regret). Let V E FK defined by in = Rad(1/2) and 1/2 Then, for any e E (0, 1), 2 log [K Txl--)
VK" = 50-
R5 c(T-))
The proof of Proposition 2 follows directly from the more general result presented below, instantiated with 1- μ11 1.2 A. 2 for all k E {2, .2.....K) K). We highlight that the K - term in the proposition is permitted, by a slight change in the last steps of the proof the lemma, that we detail below.
Lemma 4 (Example I: optimal Rademacher vs non non-negative rewards). Let 11 be a Rademacher distribution of mean μ1 > O, and (V2, ..... 1h) be any distributions supported on [0, 1]. Then,
T 1 - - RT(1) 2
1- M1
Ve E (0,1): 17 2 log
A (T-
Proof. As in the main paper, we use the notation A = min A For this example, since the sub-optimal arms have non-negative rewards, then 50,,, I 0 if A, + 1. Let to denote the first (random) time for which A, = holds. Then, it holds that
RI 24(T - 1). (T) S 1)
2A(T - 1) (T) S 1/r = = -1).
AT 1) (T)) < 1/r,, =11 1-
2A(T - 1) 1 1- 14 (1-P P( E f2..... .) A, 11p1, S se"))
2
where the last line comes from a worst case bound for the value of to and the fact that after receiving Tt, = -1 then
P1 S
S e
= +
K-1
26

---

Indeed, since all rewards from sub-optimal arms are non non-negen non-negative, then (1) 01. S 0 fort S to. and
Pi,t remains the minimum of the sampling distribution, so 1 - Pı,t 2 K-1, and (2) from (9) at least K one sub-optimal arm has non-negative parameter and probability larger than 1/K, K, thus the bound on the denominator. We now use the union bound
P (31 E ..,
; T} A, - 1p Se S (T 1)e"
which, for any e E (0, 1), is smaller than
if 7) 2 log T-8 Note that for the proof of
Proposition 2 since sub-optimal arms does not yield non-zero rewards the sampling probabilities remain uniform until lo2 and then it holds that
9
P1
e - + (K - 1)e K 1
which by substituting in above steps allows include K term in the logarithm.
We now complement Lemma 4 by showing that choosing 7 22 KT)) leads to linear regret for broad class of reward distributions. This further demonstrates that large learning rates can be harmful in the absence of stronger assumptions on the distributional structure.
Lemma 5 (Example 2: Non-negative support). Assume that the rewards are supported on [0, 1]. Then in M PE log((K 1)(T' - 1]] then the regret is linear, and more precisely,
Ve E (0, RT
8 K
Σ
Pr Pr (r pk) 1
(
1 log MiR
(K - 1)
T
1-6
which holds for n > log((K - 1)(T 1)) directly if the rewards are Bernoulli.
Proof. For each distribution V% with & E [K]. there exists a constant qu > 0 such that gk = P(r 2 Hk A, k). Therefore, time t 1, each arm k has probability 2 of being selected and yielding a reward rı (k) 2 Mą. Conditioned on this event for arm k, the probability assigned to arm at the beginning of the next round satisfies
aLK DER
Pk.
Pk.2 S (K - 1)e-nin
(K 1)e
and arm & is played for all remaining rounds with probability larger than 1 - (T 1)((1 Pk.2). using union bound argument. In particular, this probability is larger than > 0f 2 log (K-I)T-1)). The result then comes by summing over all sub-optimal arms. Finally, the refinement for Bernoulli distributions is straightforward by replacing P by 1 in the bound on Pa.2.
B Detailed comparison with related works
In this appendix, we elaborate on the comparison between the analysis of SGB proposed in this paper and the two most closely related works ①1 (29]. Mei al. [ introduced the only existing prior regret analysis of SGB but, as we will show, suffers from certain limitations, and Walton and Denisov [29] introduced the SAMBA algorithm, another gradient ascent-based policy, for which they prove logarithmic regret for any number of arms and Bernoulli rewards, under proper gap-dependent tuning of the learning rate. As we will discuss, while SAMBA shares some similarities with SGB it also exhibits key differences that impact both its theoretical and practical behavior.
B.1 Comments on the previous analysis of SGB for small learning rates
In this appendix, we compare the results we obtained in this work with the previous guarantees derived by (1) for general number of arms K but small learning rates. We also document a potential issue in their analysis, which might invalidate the proof the main regret upper bound [ Theorem 5.5]. We propose correction (Theorem 5) that yields fully explicit logarithmic regret bound for
27

---

= (Eq. (15) under the same restriction on the learning rate as in the original paper. To do that, we used some of the results introduced this paper. more precisely from the proof of Theorem |
Unfortunately, this technique is specific to the case K = 2, and we are not aware of straightforward extension to settings with K > 2. In fact, the missing arguments appear closely related those required to complete the regret analysis in Corollary [ discussed in Section 3 For this reason, we present Section with the view that a full regret analysis of SGB in the general K-armed setting remains an open and challenging problem.
Comparison of the regret upper hounds Adopting the notation of the present paper, we can restate Theorrm 5.5 of Mei et al. 1 as follows,
2
log(T)
17
3/K
Av E
RT
E
+1, where = inf Pi.
121
Beyond the requirement that the learning rate must scale with A (as opposed to A), we observe that 2K log(T)
c² $ př, K², so the regret bound scales at least as
contrast, in the symmetric case
where A -... Ax A, Theorem 4 shows that the regret is at most 2K log(T"), for learning rates that may be large as 17 = is significant in many settings.
K+2 This improves the bound by a factor at least 80K (K+ (K+2)A
which
Based on the theoretical developments in this work, we further conjecture that the regret of SGB in the general K K-armed setting should be K-1. log(T) o(log(T)). , for learning rates that could be only required to satisfy // S 2A
K "
K. This suggests that the analysis in I may be conservative, potentially leading to a suboptimal characterization of SGB's ' regret. remains an open question whether the techniques from this work- wark-lloslly related to those used in the analysis of stochastic gradient descent in optimization and the tools introduced in the present paper can be combined obtain tighter regret bounds in the general K K-armed case.
Issue with the proof The development in Equation (282) in the proof of (1 Theorem 5.5] assumes that the random variable is independent of (0,) (using the notation of their paper where 8(0,) = (x** - ) r denotes the sub-optimality gap at the current state of the policy) which we believe does not hold. Indeed, the variable satisfies P1,t A inf P1,s s. for any including the one that defines (...). and thus it cannot be independent of c. In addition, it is clear that the correlation between and 8(O,) is in the wrong direction for Equation (282) to hold.
In order to overcome this issue, we suggest to get back to their Equation (277), and to keep the t-dependent quantity Te, (a") (or Pt, for us) instead of taking the infimum over all time steps. Then, we can adapt their Equation (281) to obtain, with their notation,
Vt 2 1, 8(0.) (,,5(0++1)) 7 no, (2
5(0,)²
2
Here, to correctly account for the dependence between 5(e)) and ne, (a*), we can use Cauchy- Schwartz inequality to obtain that
E B(6(0)) (2
E
Fo, (a"jz
As a remark, we think that taking the supremum outside the expectation makes further analysis of this term easier. From that step, result and obtain the following correction.
directly follow the proof steps of Mei et al. [I] to adapt their
Theorem 5 (Corrected version of Theorem 5.5 from 11. For any instance FKK SGB tuned with learning rate 1) admits the following regrel bound,
2
2 (lgg(T)
7
E LE[2]
sup
(14)
40K 3/2
Tag T (a+)2
7
We recall that the original proof steps could have led to a factor infeerry Elre. (ar)) which the authors rightfully treated as a positive problem-dependent constant. Indeed, since there exist some favorable
28

---

scenarios for which Te, (a*) rapidly starts converging to 1. it is clear that on can assume that there exists finite constant y (depending on and 17) such that infr Bl (a*)²) %.
Unfortunately, after correction it is non-trivial to deduce that the regret is logarithmic: proving that (a-) C for some constant C > requires much more careful analysis, since becomes necessary to consider extreme events that could make the ratio large. For instance, if Toz (a*) = (TT with probability (2(T-)) then the regret bound becomes linear in T. This scenario needs to be carefully considered, since it is typical for optimized bandit policies, like Thompson Sampling, as documented by [40].
For the case K 2, however, we can apply the techniques from the proof of Theorem 1 to show that this upper bound non-vacuous. Indeed, using our notation (and dropping the subscript), we obtain by expanding the fraction that
2
Pt Pt
E
E
pi
Pt
and from the second to last equation in the proof of Thm. [
we know that for I A the expectation [2//p.] initialized pi 1/2 decreasing and thus
27
Pt
2
Pt
E
+
+3
Pr.
Pt
Pr.
Using the notation x
L-Pt
used in the proof of Thm we have x? -9: by Eq. 11 in
Appendix A The exponential form allows to derive an equivalent bound on the expectation 2 as done for the expectation of in the proof of Thm. buut with 2n instead of r7. Consequently, we have that zi is a supermartinagele for 2n|22n I A and with œ = 1/2 its expectation is bounded as
1
(1 p1)
for K =2 2, 2n AA
E 121
<
1
Pt
pi
which yields that E[1/p2] S 4.
This condition 1) required for EE[1/p /p]] S 4 is weaker than the one 1) S A²/(40K3322) needed for
the rest of the convergence proof Theorem 5 Hence, for K = 2, Theorem 5 yields the upper bound on the regret
2
(log(T)
7 S
F2
R
+
(15)
40K3/2
We comment this result is strictly weaker than the establish in Theorem 1 which yields the following bound for the same range of learning rates,
log
+
A 25
T
+1
RSG
2nj
Notably, our result allows for learning rates that are approximately a factor 100/2 larger than the ones permitted by Thm. while still maintaining tighter regret guarantee (for a fixed learning rate).
where in the logarithm we used that v < 2
A
30-2377
100
Unfortunately, for the general K-arms case fixing the proof of Thm. 5.5 from by bounding E[1/p?,,l appears difficult, potentially requiring to derive the same tools needed to complete an independent regret analysis from the upper bounds presented in Section B
An interestingly comparison between the two regret bounds arises by noticing that Thm. yields an upper bound that multiplies a (logarithmic) term, resembling the post-convergence component of Eq. (7). by term related the failure regret (proportional to E((/p()). On the other hand our regret decomposition in is the result of adding the two components.
29

---

Comment on the small learning rate Lastly, we investigated whether the small learning rate requirement [ byproduct of some looseness some technical results or more intrinsic limitation of the policy. We found that the restriction arises from the foundational technical results used to derive the analysis. Consider the two-armed case. this paper, we showed that for small 7) A, ignoring for convenience the term Cn in the following lines, it holds that
E - Pt-1] 25 Eele -0t+1] 6 29 Bee 2n00e] 20 (1 - p+) - 2n((A 7) Pc(1 - pt)2
using that e" R + x + x² /2 and the expressions for 80, and (60,)² from Appendix A.2 This indicates that the policy improves in expectation between step / and step + 1 when 1) A holds, for any value of pt, but with an amplitude that depends on the current value of pt-
In contrast, the analysis in [1] is based on the equation stated above their Proposition 3.1, which follows from the ý S-smoothness of the current value of the policy under the softmax parametrization
[3 Lemma 2]. Specializing this equation to the case of K 2 arms yields the following bound in expectation:
Ealp: Pr+11 1] A < 21 p.
22?
172 pp pc),
where used Eq. 12) with < 1 to bound the term E, |||0 0.113)- The correctness of the scaling of all terms in the incquality above can be confirmed by comparison with Lemma 4.3 in [
However, this bound is difficult to interpret, especially when Pc(1 p.) is small, due to the mismatch in the dependence on pt between the progress (negative) and noise (positive) terms. Even assuming that both terms had the same dependence on some common factor A,, we would still obtain that the policy's ss value increases in expectation only fj S A This indicates that the overly conservative scaling of in terms of A arises from looseness in this preliminary bound, rather than from any fundamental limitation of SGB itself: the -ssooohhness property of the eettmax-parametrivvn policy does not appear to accurately capture the dynamics of the SGB update.
B.2 Detailed comparison between SGB and SAMBA
In SAMBA the gradient ascent is directly performed on the sampling probabilities, with no use of parametrization. Starting from the uniform probability, each time step > 1 SAMBA performs the following steps:
1. Define a; = argmax cE(K] Pr(a), draw a ~ Pt. collect R..
2. If ag = az. then for a' at: pe+ (a') = pr((a)) - app:(d)) R
p=(a;)
3. Else, Pt+1 (at) - (ac) + appr(a))..
R
p.(as)
4. Define Pe+1 (a;)) -oofa; (a)
is easy to verify that if < 1, the update remains within the probability simplex. Interestingly, under this scheme probability ps (a) is updated only if it was pulled or if the arm with the highest current probability was pulled. From gradient ascent perspective, this is natural approach: the arm with the highest probability serves as the current best guess for the optimal arm, making it reasonable to form importanco-weighted estimates of the gap A. relative to this reference. However, this feature introduces structural asymmetry, between the leading arm and the others, that complicates direct comparisons between SGB and SAMBA when K > 2.
For K = 2, we can compare the two methods more precisely. Consider the asymptotic regime in which arm has the highest selection probability. this setting, SAMBA updates the probability of arm 2 according to
EAAYAA
p2.++1]
P2.t ad p2..
Mcanwhile, under SGB have
2 P2,1 -260.
12
2 P2, (1 - 2p2, - P22, p2,))(( - -)()))
= P2, - -2 A - v/Cr)) 11 -P2.),
30

---

using the same steps as in the second to last equation in the proof of Thm. Hence, in the asymptotic regime where P2,t < 1, the expected update of SGB and SAMBA become approximately equivalent the learning rates are related by aA = 21y( - r)C)))
We also compare the behavior of the two policies in the transient regime where P2, 2 pı,t- In that case, the analysis of both policies is based on properties of Pi. It is therefore natural to use this quantity basis for comparison in this regime. For SGB, we showed that
ESGB
<
2n(A - (1,,)11111m
-
P1.++1
P1.
where the inequality is nearly tight when 7) small. For SAMBA, rather than relying the computa- tions of [29] which are specific to Bernoulli distributions, we propose a similar approximation to the one used for SGB, for rewards supported on 1,, Assuming P2, P1, and small a, we obtain:
SAMBA
1
1
Ex
PI.t
P2,
P1,+1
PI,t
1 + aTi,
PL. p2.t
r2,
1
ofn a (r'E(rr,))) + p2, op1,1/2 a 2... E B(r
Pl,e(1
P1,t
P2,
1
aA
+
E[ri,e]
PLe B(2,1) P2.
P1,
1
5 a(A - 2a)
P1.
This yields the sufficient condition < 2 ensure that Pi. is super-martingale when P2, > P1,t- which is a stricter requirement than the one from [29] for Bernoulli rewards. Note the above computations be made exact by using constant Da analogous C, used for second-order approximation of the exponential in the analysis of SGB
The main insight from this analysis, however, is that the term (1 p1,))² which appears naturally in the update dynamics SGB, does not appear in the approximation for SAMBA. Consequently, the elegant connection we established between E E'pn" pr I and the regret for SGB does not seem to hold for SAMBA: the two policies seem to admit different pre-convergence behavior, even for K 2.
We can finally remark that, although limited to Bernoulli distributions, the analysis of [29 yields logarithmic regret for SAMBA under the condition a < A. Notably, this requirement does not depend on K. We leave for future work the investigation of whether it is meferable-bott theoretically and empirically-44 maintain the update rule of SGB, where the parameters of all arms are updated at each step, or adopt a more selective approach in SAMBA, where non-leading arms cannot influence their respective updates, In particular, the intuitive explanation provided in Appendix [D3 regarding the necessary dependence of 1) on for SGB may no longer apply if updates are implemented through a mechanism akin to that of SAMBA, where leading arm is treated differently as the others.
C Proof of Theorem 2: polynomial regret when Z A
Roadmap Below, present the proof of Theorem 2 which re-uses the proof sketch of Section 2 but adding precise references to the technical lemmas needed for the proof. These results, Lemma and Lemma 7 are presented in the following sections of this appendix. Furthermore, the proof of Lemma 7 is quite technical and itself supported by several intermediate results, that we detail.
We start by restating the theorem.
Theorem 2 (Polynomial regret). Fix A (0,1), and consider the instance v (uk) with VK- 66. the learning rate of SGB satisfies
V1 Rad(A) A) and 12
n A = K-1 log (1+
then its regret on the instance v is lower bounded as follows,
RJ = (TT=((TT((+))))))
Ve O,
where St hides polylogarithmic terms in T and constants depending on n and A.
31

---

Proof. We follow the sketch of proof presented in Section adding the detailed computations and references to the supporting results.
Step 1: let Pn+1 be the the sampling probability of arm after its n first pulls, and $ be the event that Pn+1 2T for some value of that we will fix later. Then, under S the probability that arm is
never pulled again after its first selections is larger than (1 - --/ 2 1.2 in which case the regret larger than T n. We hence first obtain that
(T n)+
RT(1)= 2 A P(S).
2
Step 2: We lower bound P(S) for a well-chosen value of n, by identifying a scenario that leads (deterninistically) to Pn++1 I 27 Let ni. be integers to be specified later, we consider the following repartition of pulls two phases,
Phase 0 - very unlucky start: for its first no pulls, arm collects only -1 rewards. We denote this event by So.
Phase failed recovery: the following pulls of arm 1 have empirical mean satisfying Un, X - and the number of +1s received never more than the number of -1s throughout this phase. We denote this event by S1.
Since V1 is Rademacher of mean A, it is direct that P(Sp) = - denote the stream of rewards collected by arm (in the order they are received), and Bng Eistot Rg be the empirical mean of the rewards during phase 1. Let S., = Ex=tot 1 =
no For phase 1, let (Re)
2
1} be the number of ones received during this phase. We first define
2
1-
ni]
2
2
a
A
2
m1
An
so that 1-oA an integer greater than nn with a that is as close to as possible. From Lemma 6 we first obtain that
(P,, -a) P Sn,
1 1- as
2 11
2 2
1/6
exp
n1
log 1+
24
n11T
A
Then, conditioned on this event, Bertrand's Ballot theorem of always exceeds the running number of +1 with prohability
64 65
provides that the running numher
(n) - Smi) Sm
25,,
Pn, ad,
11
71
which finally gives that the probability of S1 is lower bounded by
P(S,) 2 ad
116
exp
A log
1 + 1 - A ))
24
2n,
Then, it remains to show that So ns C S for some values of no and nı. By Lemma 7 this is guaranteed for n = no + 71 by fixing
1 K
1
)
K
Kan (K 1)2 )
ng
n K-1 log
K
log
E-(K 1)
17
K -1
1og(2T/(1) - 1)) 2
and n1
K
nd(1 ())
A
By independence of the two sequences of rewards involved, it holds that PPS) > P(S)) P(S.). To obtain the scaling of the result, we combine the above results and use that no is tuned as a function of n1 Hence, we can state that there exists a function Czyy with (inverse) polynomial scaling in mi such that
IPS) 2 On, -e - log
32

---

so that replacing n2 by its value and ignoring the Cn2 term, which we hide with the 2 sign, leads to
P(S) Z -1 log(1+ 1-)
2 (1-3 K-1 Life log x
a log(1+ 1-
(A+22 log 1+ 22)
K- L+z log [+ 12م log x
= -0 log (1
2
R ل عنا logg 1+
T
1+s log |+ 2
K
K-1
For completeness, we detail the poly-logarithmic terms coming from the expression of Cny below,
1 - A Cnl
2
aA e
1/6
2
1 (xxx)
log -
2
A
Kºn
2 0A e 1/6
T
2
(K
-1)2
# K log (
A
2
K
1 + loo (
-d
1/6
π
(K
1)²
We can further detail On by replacing ni by its value. For simplicity, we capture all the problem- dependent factors in a new constant C, and finally obtain that
E 0: CN2 2 Cn (log(T)) + ( logs log 2
Step 3: Combining the results from the first two steps, obtain that
TT no - m1)+ 2 r 11
22),
RT(p) 2 A IPS)
2
where the omitted constants depending on and A and polylog factors in T can be recovered from the above lower bound on PS)).
C.1 Anti-concentration of the empirical mean of Rademacher variables
Lemma 6. Let n be a sample size and S, be the number of ones received from n independent pulls
of Rademacher variable of mean A z
2 n. Fix a
2 [
1 m1] 2.122.n]] E
[1
An
11. then
P psS
Sn
a-
2 e
1/6
2 n
exp
(-n- A Alog 1+ 1
2A
))
Proof. Using the notation
= 1+4 2
we use the following standard formula,
P(S, s)
p0(11 p>=
log(p)+ ((n log(1-p)
c " a log( P/, 7=" was (a- -nf((())
nl (() =kk((()))))
where H(x) = -x log (1 x) log(1 x)) the Shannon entropy, and kl the Bernoulli KI.-
divergence. With 1-aA and a < 1, have
2
A 1 1 A
1 1- A
1 1 A
1+
1+ A
kl n. P) < kl
log
log
2
2
2
1 A
2
1 A
1 +
2A
A log
= A Alog
(1+
1
A
1
A
33

---

Sterling's approximation for the factorial [66] gives for any
2
2mn nz 2
1/12
Thus, for (0, such that en is integer, we obtain that n!
cn
V 2nn n=
2
(c1/12 c (c1/12 v /2 c)n (1 (l-)))loon((l-ht e
e-16
11 n-n-on-(1-ch
1 c (1 c)-cinn
2 - c)n
e 1/6
(l((
V2Te(11 - -c
Remarking that /2c(1 - c) S 1/v2 for any E (0, 1), finally obtain with en
P(S, =) 2 = c
e nkil 1 = e 1/6 e/66
2
exp -n A Alog
1 1 - A ))
24
C.2 Sufficient conditions on no and nı for So ns C
Lemma 7. Fix any (0, 1), and define no, n2 as follows:
K log E-(K - )
1
K
K log
)
nig 1j K-1
(K- 1)2
K 1 Log(2T/(1K - -1) 2
11
K nA(1 8)
Then under Sn O Si it holds that Pnot S 27
Using the same notation 1n+1, let 0n+1 be the the SGB parameter of arm after its first pulls.
Proof.
First, at the end of phase 1 Pu 2
0 the policy has received no rewards of -1 from amm 1. Therefore, since K for all n S ny, we have that
0ug+1
Σ n=1
11
Pa)
mmp-
(16)
K
Next, we show that the combination this property and the events occurring under S are sufficient to prove the desired result. Indeed, we recall that under Si, the sequence of rewards in phase 1, noton RR) 11 satisfy the following two conditions:
The total number of +1 rewards should be less than 1-o4 n2 and the total number of -1 rewards should be more than Loth inc Σ R, < aA.
There should never be more +1 rewards than rewards observed at the current time step within the phase; i.c. Erstot R, < for all < ni.
The rest of the proof is based on characterizing the sequence among all sequences satisfying the above conditions that leads to the largest value for tag +1. We call this the maximizing sequence. Then, we show that even for that sequence it holds that Pogt +1 S 1 lemma follows. We detail below the lemmas that lead us to this result.
27 from which the result the
34

---

In Lemma 8 we give general construction for the maximising sequence that applies to reward sequences satisfying the above conditions for arbitrary initial parameter. Then, in Corollary 2 we show that under the occurence of phase 0, the maximising sequence of rewards with initial parameter 8ng+1 takes a simple form: first period alternating -1 and +1 rewards followed by second period with only rewards. From this simple form, we can upper-bound + for the maximising sequence (also Corollary 2). Then, in Lemma ?
we show that the proposed tuning for no and is sufficient to get that the probability Pno+n1+: +1 is smaller than 27
From a high-level perspective, we highlight that the phase So serves mitigate the impact of the order in which rewards are received in the SGB updates, by ensuring that n remains "sufficiently" negative throughout the entire phase I (i.e. for & S n1), while the tuning (log(T") permits that a probability of 1 achieved even the identified maximizing scenario. 27
C.2.1 Maximizing reward sequence and probability under So n
In this section, we consider reward sequences under S₁ and characterize the maximizing sequence for any arbitrary parameter at the start phase 1.
Definition 1 (Constrained trajectories). Let Z (-1,1) be the subset of trajectories of rewards -1 and +1 that satisfy the conditions imposed under Sy. Let Sn be a finite trajectory of n rewards .Ri....: R E 2, the feasibility indices I and _ for the n + 1-th reward are the functions satisfying:
15().) - ................................ RR, +1} E 2), and
(S.))) -1 ..... Rn: -1] 2)
In particular, for < n1, (S,) if
the number of +1 rewards in Sn is less than 1-oA 711
the number of +1 rewards in Sn is less than the number of -1 rewards in Sn.
And (S,) if the number of rewards S,, is less than 1+a n2.
In words, the feasibility indices formalize whether a reward of +1 or -1 can complete or not sequence of rewards that should verify the constraints imposed under Sj. We now prove the following characterization of the maximising reward sequence.
Lemma 8. Fix 01 R Consider {RM 1m
defined as follows with S.M
RR
RM
1,
if V(OM K-1
log( - 1) and 1 (SM 1] 1} or 12 (2M
K
+1,
if (00 < K-1
log( K - 1) and 1 (S, 1] or 1 1
+l
otherwise (the case where 0.M K-1 log(K 1) and either fine). K
Then { [R,M) J is the maximizing sequence for the SGB parameter of arm 1, i.e. it holds that 0nf+1 2 0n, for 0n obtained from RRM nn and any 6n,+1 obtained from trajectory (Re) E 2, both starting from 01.
(RM1
Proof of Lemma 8 Assume [RaM Jt=1 is not the sequence that maximizes Onz+1. Denote the maxi- mum by @W with reward sequence (RM) E Z and corresponding 0. S.W. Since {R]) different from { [RAM I= there exists some n such that one of the conditions in the construction of RM is violated, so either
Ri
1. RW +1, @W > K-1 log(K K 1) and 12( = 1.
2. RW -1, oW
K-1 log(K K 1) and 1 ((
35

---

3. RW +1 and (S = 0.
4. RW -1 and (S 0.
The last two violations cannot oceur since { [RW) un t=1 E 2. Denote m the largest such n. Then handling the first two cases separately, we have
1. RM +1, 0w K-1 log(K 1) and (3 1. We must have RW -1. Suppose not: if Rw = +1, then since [ = 1 and 0m+1 2 dm > K-1 log 1), m would not be the largest such that condition satisfied. Now consider an alternative sequence R in defined as follows:
K
RW -1,
ni + m, m + if n = m if n +
RW
+1,
Let @W correspond to the sequence of parameters with rewards R. By Lemma 10
@w OW n-
n+2
Since RW R for all > + end up with OW @W #1+1 is the maximum.
ow m1 contradicting that
#1
2. RW = 11, 0w < - log(K - and 1 (SW = 1. We must have RW
+1. Suppose not: if RW -1, then since (S = 1 and 0m+1 S pm Kー log(K< would not be the largest such that condition 2. is satisfied. Now consider an alternative
m
sequence 12W in Z defined as follows:
RW +1,
if n + m, + if n
n m
Let @W correspond to the sequence of parameters with rewards RW By Lemma 10
@w
<
Since PW = R.W for all > m + we end up with Tw Φw a1 41 contradicting that
@W is the maximum.
In both cases, we get contradiction, therefore { RRW nh Jt= cannot be the maximizing sequence. Since
this holds for any sequence different from { [R. ===1" {RA (=1 is the maximizing sequence. We refer to the end of this section for the statement of Lemma 10 and its proof.
The next corollary characterizes the maximal possible value of parameter O Ono under event So n S, by applying Lemma under the occurrence of the event Sp.
K- Corollary 2. Assume 0, -"
K vmmo and no 2 1 K-I
K log
K n (K-1)=)
Then it holds that
(1 (1-
TM S -nnann
K- mma
K
with @M being the parameter obtained with the following reward sequence
(-1),
ift (1- aD) n1, otherwise.
R.M
-1,
36

---

The above corollary highlights the role of phase 0 in ensuring that 01 is small enough so that 0Nd
K log(K 1) for all in the trajectory despite the asymmetry of the SGB update.
Proof of Corollary
2 By Definition
| (S
0 if either
the number of +1 rewards up to time / of phase 1 is 1-oA 701
the same number of +1 and -1 rewards have been observed up to time t of phase 1.
We assumed that 01 S K-1 as 0, < K-1 the same number +1 and -1 rewards have been observed up to time t of phase 1, this leads to an alternation 1 and +1: R.M (-1)²*
K-1 log 1). From Lemma we have that long K
K mm
K log( K 1) and 12 (S ) = 1, then Rd +1. However, since 1 (S (((-1) 0 when
This alternation of 1 and +1 rewards continues until either the parameter 0g becomes greater than K-1 log(K 1) receiving rewards of stops being possible (1 0) because the number of +-1 rewards up to time of phase I-oA mi (this will oceur before n1). The former could happen because of the asymmetry of the SGB update. However, we show that if no is large enough / phase is long enough so that 0, is small enough then the asymmetry can be handled so that 0, remains negative.
Intermediate claim: If no 2
K 1 K-1
log
K (K-1)=),
then ØM 2n+11 S K
0 for all n S
1-a4 n21
We prove the intermediate claim by induction. Recall that the SGB update is 0(+1 0g + 17(1 Pc) Ri A positive reward increases the parameter value and negative reward decreases it.
Base case 0 follows from 0 0 - 0, < K-1
Inductive step: assume for all k S n 1-a0 n1. Then R. (-1)² for all S 2(n + 1) (the
alternating sequence has not stopped since n < خمي my so not all +1 rewards have been observed and the parameter has remained negative throughout). We have:
(
0M 2(n+1)+1
01
TM R.M
0, +
(1 PM)) (1 P2z }
n+1-1
0 +
P2k-1
R P2k
1=1
Note that 0.4/ 0. 02: 71 P
22 since R& -1 Therefore the sum appearing in
the above expression is positive. It stems from the asymmetry of the SGB update. The presence of phase 0 makes 0 small enough such that this asymmetry is not too significant keeping 2(x+1) of
0.
37

---

the same order as 81. Specifically, we have
1
1
P2R
P2k
1 (K -) e 22
1 (K - 1) e K-10% 22
e - 02 - xxx 2
=K
(1 + (K - 1)ee
x AN 21-1 1) + (K - -1)e "I- 26)
(K - 1)e"
K 1
1
(e (ex (0 -02 -1) 1)
1 1 (K 1)e
x 02
1 (K - 1)e কे= oz
1
K
OM 21
exp
K
S eexp (1)
by the inductive hypothesis
K -
--
(m++1)+1 S 0 + 7 + 1)
S
K
The last inequality follows from
K
K²n1
(K 1)2 n1 I mue
K3
2 17
log
K
(K - 11)2
1/11
S
1
non
(K - 1))
0s
using 01 S
K -
1
K
K²2
K
using again 0 S - K 1
mmn
81 -
01
1710
K
K
nn + 1)c 61 <
K
using that n < 1- n1
< 21 < n1 1. This completes the proof of the intermediate claim.
The claim implies that throughout the alternating sequence of -1 and +1 rewards, the parameter 0 remains negative and that observing all the +1 rewards causes the altematinn sequence to terminate. We have that R&M (-1)f lasts until we have observed at most همتل ni rewards of +1 after which 12 (M 2-1/ = for all remaining rounds and therefore the remaining rewards in the maximizing sequence are all 11
When the alternation ends, by the above claim we have that after receiving to = (1 aλ) .n
samples, it holds that 0M+1 S K < - [-1 moo There are n2 to = aaAn rounds left in
the phase, all of which have a reward of -1. Hence we have
M S Phote
1
K git
<
1
K
7M
K
K-1
K
K
K-1 omo, we have:
Fixing 80 -- e
@M 0
tot +10
0uy - 17 Σ (1- pk
k=
S -n((m1 - to) 80)
=nnann (1 60)
0 S -madn1( (1 - 60).
With the previous results at hand, we can finally obtain the sufficient condition on ni and n1 to guarantee that So n,S C S.
38

---

Lemma 9. Fix any E E (0,1), 1), and define no, n2 as follows:
1 K
K 2
no =
log
log
K -1
E- - 1)
K -
(K - 1)3
K
-1)) log(27/(1
n1 =
+ A
K
7A(1-8)
Then under So n n1, it holds that Pno+ni-1 S 27
Proof. Under Sp, we have that 2no+1
S
K-1 K
17moo and by construction,
1 K
K2n1 (K - 1)2
no 2
log
17
K -
Therefore, we apply Corollary 2 on the rewards in phase I, which gives
(1- K x
Ong Ang+ni+1 S -inanni
K
1
S <-naa(1-53 s)m1
since no 2 "
-log
E E.(K - 1)
S <-nA(1 -)m + 2 =) =)
since a > 1
An
K
2T
K K-1 1
log 1og(2T/(( (K - 1))
2
S K
log
since n4 2 K
+ A
K K-1
1A(1 -8)
Ongtnit1
ex- 8ng-njtt
Pnotni+1*
-ngtai-1 S
- 2T
(K (K-1)
Engtai-1 + (K - 1)e
We conclude this section with Lemma 10 which is the last technical result supporting the proof of Lemma 7
Lemma 10. Consider an arbitrary parameter 0,, for SGB at the n-th pull of arm (and the parameters of all other arms are the same and equal to k- 0n). Let R3 E (-1,1} be the reward for the k-th
pull. Let on+2 correspond to the case where R,, = 1, Ra+1 = -1 and 0x+2 correspond to the case where Rn, -1, R,,11 1.
If0, > K-1 K
log(K - 11), Bnt2 Unt2
1f0 k-1 log(K K - -1), Oat2 On42
If0, < K-1 log(K -1), 2nt2 0n42 K
39

---

Proof of Lemma 10
K --1 1
ant2 fn 11711 pn.) + 17(11 -Pa+1) fn n7(1 Pn)) + 11
K - 1 exp(
R
0 0
K-1
K-1
=0, 11(1 pn)) + 11 K - 1 + expl
K R- 0n 6-111(1 - pm))
K 1
nt2 = On + 17(1 Pn,) - 11(1 - Pn+1) = On + 11(1 -Pa) - 11 " K- 1
exp( K-1
K
K-1
On + 11(1 pn)) 11 K 1 + cxpl K pn + k-17(11 pnn))
K-1
K-1
= On42 - Ont2 - 21(11 - -Pn)
K
+ exp( K-10n On K-I PPa)
K
K -
11 K 16--10 + expl K-I
K 0n
カー - Pn))
Using that
Pn K- 140oppp k-
K-1
1 9n)
consider the function
27 -
n(K -1)
f(x)
K - 1 1 +xx((x)
K + exp(x x + K- K K+teepp(a)
'(K - 1)
K - 1 exp(x
K n(K-1)
K-1 -l+xxx)
Then denoting Y =exp(
o kK and 7 K 1,
K-1 K l=exp(a))
2
f(x) >0 3
K 1-1+expll
- + exp(x + K-1 K [exp((s)
KK
K - 1 1+ expl(x K-1 K K-1+exp(z)
K KK-I)
2
1
Z exp(((
Z Y exp(x)
7 y exp(x)
= 27. 27Y e0 + Y e 2020 > 27.2 7Y ye" + 27c + Ye Fole
22
2
7 - ZYe" + _ e² +20 2Ze" +Y 1
y e22
= 2Y + e x > 27Y +Y²e +e²
+ (Y 2 + +1((2 - >0)
(Y - -) e²) >0
= < log / = log K 1).
Similarly, f(x) < 0 - x. > log(K K - 1) and f(x) =
- x = log( (K - 1). Since
f( K 0n)== 0n+2 On+2, we have the stated result.
D Supporting results for the proof of Theorem
This section contains the classical lower bound results in bandits (appendix D.I and the proof of Lemma [ (appendix D.22p. The proof of Theorem B in the main paper is entirely based on the results presented in this section.
D.1 Details asymptotic lower bounds in bandits with bounded-support
We denote by KT((,.) the Kullback-Leeiblr divergence between two distributions. We first state an adaptation of the classical asymptotic lower bound in MAB, first proved by Lai and Robbins
40

---

36 for parametric families of distributions, and later extended by Burnetas and Katehakis [37] for non-parametric families. The following result is inspired by the elegant formulation and proof of this lower bound, that can be found in Emilie Kaufmann's 's thesis [67 Theorem 1.2].
Theorem 6 (Asymptotic problem-dependent regret lower bound, adapted from Theorem 1.2 of [67] E JK be a MAB instance with distributions from the same family of distributions F. Let (0,1) 1), and assume that a policy satisfies Rr (TT)) for any instance E FK Then, the number of pulls of any sub-optimal arm lo (such that As > 0) under the policy x must satisfy
lim inf [[N+(T)) T-000
a
2 (V)
10 (VE,
VEF = inf (KI((K,,)) B/):www/ [ (17)
ITg(T)
for any sub-optimal arm k; and using the notation μz maxje(K] Mj-
The above theorem holds for any generic family F, but we recall that in this paper we use the notation F for the family of distributions supported on [-1, 1]. Furthermore, Theorem we consider even more specifically the family FK for some A (0, 1), of bandit instances with bounded rewards (with support 1) and minimum gap larger than A. To prove the theorem, we derive the following result.
Lemma 11 (AC for the Dirac distributions of Lemma
2A
AA E
(0,00,1)
An (6_1. log 1+
A
Proof. We first obtain from Lemma
12 below that Ki (6-2,)) = -Kint (6_ (6_,, A). The result then
follows from Lemma 13
We first prove the relation between KL-inf quantity associated FK and the associated with F.
Lemma 12 (Modified Kint with knowledge of minimum gap). Fix A E (0, 1), and let FK denote the class of K-armed bandit instances with distributions bounded in [-1,1] and with minimal non-zero gap of A. Then, for any Us. E satisfying As 2 A, holds that
FF (vk, = Kos +
Proof. The quantity Ku (vk. n²)) reflects how far the distribution Vi. is from an alternative distri- bution 1/2 such that arm i would be optimal under this reward distribution. By assuming that the minimum gap is A, it necessary that the average of the distribution 1/1 least μ² A. Since the support of the distribution has to remain in [-1, 1], the identity is direct.
F
We then prove the remaining supporting result for the proof of Lemma 1I
Lemma 13 (FFFF for bounded distributions). Let μrn E [-1, 1] and Then,
E [-1, 1] satisfying 2
K 11) = log 1 1i
Proof. To turn the Dirac distribution of mean No into distribution of mean μr at minimum (KL-)cost while keeping its support in [-1, 1], the most efficient way is to transfer as little mass as possible in +1. We thus solve
p1
p po + (1 (1-p) = p1 -
which is the probability mass remaining in μo after the transfer. This gives the result.
We now formulate some remarks, before recalling some known properties of KI-inf divergences for bounded distributions.
41

---

Remark 1. If the support [-R, R) for R >> O, and using the notation F(- ri) for this family of distributions, we obtain
R - P40 R pi
Kinf R. (6po: (10)
so the thresholds of Theorem are trivially multiplied by R. since log(1 A) becomes log(1 + A/R) in the lower bound.
Remark 2. From Lemma we see that K (.,1e)) is infinite if pt 21 A. This reflects that, in that case, the regret does have to be logarithmic. For instance, by adapting the analysis from 168) we could verify that preceding a UCB policy by a greedy step that would play any arm with empirical mean larger than 1 A (instead of computing the UCB) would yield constant regret in the case where the best arm admits an expectation larger than A.
Since this fact is not particularly insightful to understand the theoretical behavior of SCB, and the interesting scenarios arise when À small, we chose ignore this trick in the paper.
Summary of known properties of K It well known that for bounded distributions the quantity C ("" v²) can be expressed as the solution of an optimization problem, but is also related to the KL-divergence of Bernoulli distributions and to A We now claborate on these results.
Most existing results in the literature are derived for bounded distributions of support [0, 1] ([50) 30 69]. among many others). We denote this family by F. Since the KL divergence is invariant by rescaling, it is clear that K and Ki are related, more precisely
V(K E F (-1,1) (v, (T
with z = 1+ the distribution of 1+X for random variable u, and similarly for Honda 2
2
and Takemura (50) derived the following expression,
X 11 1 sup Ex-D log 1 (1 p1 XE
((C,)) (0,1),
())
We further denote by kl the Bernoulli divergence, that can be expressed
V(Ko: p1) E [0, 1], kl (1) po log
+ - (1-1a)
140 μ4
Then, for any distribution E F of mean Ho and (4 E [Po, 1] it is established that
K (Pu. ki(uo, p1) 2 2(p1 mo0
We refer to (69 for proofs and detailed discussions on the tightness of the inequalities. In particular, the inequalities are tight for Bernoulli instances with expectation near 1/2 and small gaps. This translates into the fact that, on F, the most difficult distributions are Rademacher with means near
Hence, for problems from JKK the regret of uniformly efficient policies is expected to scale in the worst case, function of the gap A, with 2(K 1) log(T) which becomes (K-1) log(T') if A is assumed be known, i.e. Rademacher arms of mean 0 (and so μn = A). We see that the results we obtained in Theorem and Theorem verify this property, and are thus coherent with the lower bound.
FK This is nearly matched for instance with K sub-optimal
To be more precise, the asymptotic scaling of the regret upper bound of Theorem small enough learning rates, while the lower bound on the instance V1 = Rad( A), 1/2 = (O) is
log(T) for
2n
loloo(( (1 so the two bounds can be arbitrarily close for 1 Ae 22 (satisfying the condition of the theorem) and A 0.
D.2 Proof of Lemma
We start by restating the result presented in the main paper.
42

---

Lemma (Regret upper bound on an easy instance). Let E FR be a MAB defied by vi = dn and
1/2
V/K =. for some A Then, for any learning rate 1/. SGB satisfies
VEE (0, sca 1 1+ log (1 (K - 1)TmA)
K² 2..AA
(
K log
E )
(1 =)n
E
Proof. Since the probabilities are only updated when a sub-optimal arm played, we introduce the notation NNEN to denote the sampling probabilities at the N-th pull of a sub-optimal arm. We use notation N₂ = > (t),)), where we recall that, for & E [K], Nx(t) E. 1 k). Then, we can first remark that
N
11 2 1, 01,411 = 01,, +I, T)1 0 n Σ
Pl,nz
==1
On the other hand, the parameters of sub-optimal arms satisfy
Vk 2 2, 0n,441 Ou.t - 71(1 - -P.,) k) + mp, + (k, 1))
tg.t 7A. ((1 Px, = k) PR. 1(A, * (h, 1)))
Ok,t nA (I = 1:) -RR 1A, + 1))
N
= Ou.t = -nANN + +n Σ
Ph.n
n=1
Thus, we obtain that
N
4 E
01 0x.1 = (t) + 7 Σ (1... n=1
Pk.n).
(18)
We additionally prove that n 2 max Pk.n by induction: this is true at initialization because all probabilities equal. Then if the property holds for some time 2 then holds that
50n, -
Aaamx (A, + 1) < A pı, (A, + 1) 501...
(2..., K)
so 1..41 [ 03.411 therefore P1,+1 remains the maximum sampling probability at the next step. We deduce that
Ob,t =
vt 2 1, 2 2: Ph.t I 101
e AAN.00
(19)
Consider To {1 2 1: tk.t 2 8 K}. From the last bound of 19 we first obtain that
1 n
K
11 vs
(x N
log
Pk. K
Then, [ trivially upper bounded by No. K by conditional independence of the number of steps between successive pulls of arm k. Thus, it holds that
K En
K
K
T
<
log
Now, considering T UK Tha we can simply write that
K
K(K - 1) EnA
K
+ K(K 11
E[IT|-
<
E
log
We can now consider the number of sub-optimal pulls incurred for & T. We can get back to using Eq. (19). but now exploiting the penultimate inequality with
Pk.t Se- ( Eiil (PL. (A,,
< " (A(M
43

---

since by design t & T + P1, Ph, = 1 Ek= Pkr. Ph. - We denote by T the complementary of T (so T TUT [T] and T 0). and by Nr the number of sub-optimal pulls within this range, so N₁ = 1(A, #1, T). To obtain the result, we just ignore the N& (t) term in the upper bound, and use very standard proof scheme in bandits. We first define
Ni
log(1+(( -1)AA") and obtain that (1-8)nA
T
E
Σ
1(A, +1)
= E
1=1,4T
< E
Σ (A
Σ 1 NF) (ETN
[EETT[T]
$ N7 T(K 1)e -))--A((-))
log(1 + T(K - 1))n))
(K- 1)7
(1-E)mA
1+ T(K 1)mA
1 + log(1 + +TK -1)m4)
(1-E)nA
which concludes the proof since
RT(2) AE
Σ L(A, # 1) AE
Σ 1)A+
Σ 11A+11)
(=1JET
1 + log( 1 + +T(K- - 1)mA)
+ AB[[T]]]
(1-6)1)
1 + log(1 + T(K - 1)m
K
1
K
+ A + log
(1 (1)))n)
T
c
Possible improvement In the last steps of the proof of Lemma simplicity the (1) term in the following bound
1 used Eq. (19) and ignored for
Pk.t (N(N (I-)))
Intuitively, the symmetry between the arms and the fact that the rewards are deterministic strongly suggest that it should hold that (1) R N, K-I with high probability, at least when N, becomes large enough. Hence, this suggest that we could decrease N by a factor K-1 and obtain a bound K
K-1 K-1 log(T))
R S
+ A
K
7)
for some constant Ag. Proving it for general number of arms seems intricate. Furthermore, for large K the difference between the two results is minor -and our result already gives the inverse linear dependency in K- so we leave further investigation for future works. However, improved bound for = 2 to formally justify this intuition, and support the proof of Theorem 3 in the case K 2. We can further remark that the improvement is not only the 1/2 factor in front of the logarithmic term, but also is the dependency in which becomes log (!) instead of -
prove this
Lemma 14 (Improved upper bound on the easy instance for 2). Let E FK be MAB defined by ôy and 1/2 = 8-A. for some A > 0. Then, for any learning rate n, SGB satisfies
Ve E (0,1), Rr < log(1 + 27 eT - -) +
log (2)
2(1 E)11
"
Proof. The improved result comes from the fact that for K = 2, 01, = -0,, at all steps (Eq. (9) which simplifies several arguments. Let 0y denote the parameter of arm after N pulls of arms 2.
44

---

Using that inf P1,t P1.1 = 1/2. we can now prove that deterministic number of samples N₂ suffices to reach PI,N 2 E. Indeed, holds that
JAN.
- PN. S e 20NG, and ON. 2
from which deduce that choosing N₂ (og(()
is sufficient to guarantee that inf N2,, PN 2 E.
n
Let us now consider number N of selections of arm 2 after its N₂ first pulls. For N = N 2 Ne. it then holds that
HN 2 0N. + n1(1 - E
which yields - PN Se 20 S 21A(1-6)1 by definition of Ne. Using the same last steps as for the proof of Lemma and choosing N- log(1+27 ((-())))((-))))) =(1-s)nA) we then obtain that 2(1-c)1A
B[N2(T)) <
1 (A. = 2, N2(1 N + Σ
1 -
2, N2(1) > No Nc+N)
N₂ + N + Te e 2nA(1-c)N
log (t) log(1 + 22 E(1 =1 -))AA)
E.T
2(1 -8)n1
1 c(1 - e
log(1 + =7 -s)11) (1]4)+1] +1 +
log (t)
2(1 E)n
7
which gives the result.
D.3 Conjectures the critical threshold for K 2
We recall that, by combining Theorem and 3 we proved that S AAK- a necessary condition guarantee logarithmic regret for SGB. We also hinted in the main paper (Section B and experiments of Section 4 that we believe that for general K-armed problems should scale with A K, and more
precisely that the critical learning rate is 17 = 2A In this section, we formalize this conjecture, and present detailed justifications.
K
Conjecture For A consider the instance FK defined by is -o and 1/ VK Rad(- A).. Then, it holds that
2A K
K-1
log(T)
3mo
s.l. E (0, (0,
Rr
+ o(og(()))
(20)
K
n
and, as consequence, SGB can be uniformly efficient on all instances from FK only if - 24 K
The empirical results presented in Section G.3
support this conjecture, and even suggest that the logarithmic bound on the post-convergence term is the same for all problems E FK (Conjecture 3 although considering only the instance described in the conjecture is sufficient to discuss the critical threshold.
now formalize how Eq. 20 suffices to establish that the critical learning rate smaller than 24 and describe the technical results that would be necessary to prove the conjecture.
K
Intuition. Let assume that Eq. (20) holds. Then, the deduction that 17 < 24 is necessary for SGB to achieve logarithmic regret follows from the same proof steps as Theorem 3 if A is small enough, then the lower bound of Lai and Robbins 36) (Theorem 6 in Appendix D.I] establishes that the
log(T) if it is uniformly efficient on asymptotic regret of SGB cannot better than (K - 1) 23
instances. By contradiction of the lower bound, this proves the last statement of the conjecture, since some parameters 7) E K [ which non-empty, would violate the lower bound for A small enough.
45

---

Hence, to prove the conjecture it suffices to prove Eq. (20). akin to how Lemma suppooreed the proof of Theorem [] More precisely. from Equation (7) and Lemma 2 we believe that it can be proved that, for an appropriate range of learning rates, the following holds:
K K-1 log(T) ollo((T)) and C1-PI.. o(log(T))
B[0 S
We assume the first result (logarithmic scaling) because have strong intuition that the post- convergence term corresponding to a fixed instance, with random rewards, should admit the same asymptotic scaling as its deterministic counterpart (UH) Lemma in the case considered the conjecture. We furthermore include K-1 factor to conform our intuition that this is a possible improvement of the upper bound of Lemma as discussed in the main paper and Appendix D.2.
(6 ]E[[]] that we studied in
Let us now discuss the upper bound on the failure regret. By introducing do0 > 0, we anticipate that (in contrast to Lemma D] it might be necessary to restrict the learning to a bounded range to prevent large deviations for the parameters (0k.)))22. Indeed, since rewards of sub-optimal arms are random, it is possible that tr., becomes arbitrarily large for some increase would necessarily cause P2.r to be large, we would expect arm 2 to be pulled frequently, and thus 02 to decrease in reasonable time, In simpler terms, the instance chosen to state the conjecture makes it unlikely that the failure regret of SGB is large: arm 1 cannot deliver bad rewards, and any over-performance of sub-optimal arms will lead to fast correction, likely causing relatively small regret, probably upper bounded by constant (thus o[l))(T)).
2. However, since this
Conjecture I offeess direction to derive the critical threshold for 7) that is very similar to the proof of Theorem in which we derived the necessary condition with scaling K-1,
Then next conjecture, the contrary, mirrors the intuition behind the proof of Theorem by proposing a candidate difficult instance for SGB, for which scaling of the learning rate below the critical threshold would be necessary.
Conjecture 2 (Candidate difficult instance). Let K 2 3, and FK be the bandit instance defined by 11 Rad A). 1/2 ōu. and V33
VK for any μ E (0, 1). Then, 17 (K-1)112) is necessary to guarantee logarithmic regret on such instance for any number of arms K.
2A
Intuition. As discussed in the main paper after stating Theorem 3 the specificity of SGB compared to more standard bandit policies is the fact that adding some very sub-optimal arm is not "neutral" with respect to wetter-performing arms, which we illustrate by understanding some scenarios that can happen with this choice of instance.
We follow the proof of Theorem 2 to provide detailed intuition support the conjecture. We recall that, in the proof of Theorem 2, we identified a scenario under which the regret of SGB is linear, and proved that this scenario happens with probability that is too large avoid polynomial regret when y > A + O( Let us consider a similar scenario.
Phase O: unlucky start Assume that for its no first pulls arm receives reward -1, and that these
pulls happen during a (random) number of steps tp. By tuning No, we can make 02 +1 01.to arbitrarily large, and as a consequence, P2 P1 can be made very close to The pulls of arms f3...., K} can only make the gap between the two parameters grow faster, since it is clear that P2.1 2 Pı,, throughout this phase.
Phase 1: failed recovery, with a twist: We are then tempted to consider the same scenario as in the proof of Theorem 2 which in a second phase arm 1 continues receive rewards that are sufficiently bad to push its probability below 1/T2)). By following the same proof scheme, we could prove that the fact that the arms & > 3 are now very sub-optimal can only make this scenario happen faster: indeed, if the rewards in phase 1 are sufficiently bad that the gap P2. P1, s 1 from the end of phase can be maintained throughout phase then
Vt 2 11
A 4 3 = 0 01,41 62,1 02, + np (22. PL.))
46

---

Hence, the probability of arm 1 decreases not only because of its unlucky pulls, but also each time "very bad" arm drawn. This a new phenomenon compared to the instance studied in the proof of Theorem 2 We believe that this is the reason why the learning rate should depend on A/K K, as we we showed that after the n, pulls of arm in
explain in the following. In the proof of Theorem 2
phase it held that
0 to
01 Re 01 - mAn1 and Ak 2 2: Oktto f1+1
K --1
which led us choose 1hg
1og(2T) ) using the linear dependency between parameters. the ná
new instance considered here, we believe that the following holds instead,
01 RJ 01,t0+1 - mmm mp( -Tto)= with n4 Σ (A,
Hence, intuitively we can expect that lower value of nı (compared to the theorem) could lead to Pla++i+1 S 27 with large-enough probability.
The following detailed intuition about this phenomenon is speculative, but we think that from that point argue the following: since arm 1 appears "at best" distribution with gap A, while the others appear as distributions with gap - T < 0, then it should hold that P1.t/P.t Pk.t x - ttrroughuut the duration of phase 1. We formally this in Conjecture in Appendix G.3 supported by experiments. As a consequence, with non-negligible probability, should hold that th Th (K 2) a nı, by summing the sample sizes of the K 2 bad deterministic arms. Under such scenario, would then obtain that
new conjecture
11 02.t0+0111 01,to+1 0 nA(K -1)m1
from which the desired tuning nı would become ni
12g(27)
(K 11n
By plugging into the last steps of the proof of Theorem
would obtain that lower bound
the probability of linear regret is of order e (x-1)a(1- log(2T) which gives lower bound on the
24
regret of scaling T का -ス--fit=z,, polynomial if > motivate the conjecture, although a proper formalization would involve many technicalities (akin to the proof of Theorem 2 but with more involved arguments), that we leave for future work. In particular, order prove the results presented in this paper we manly had to prove upper bounds of the form Pk.t < 7A.7. while for this new result it would be necessary to further prove that
(1-1)1-A) We believe that these arguments
24
Pk.t Z ndgt with some reasonable probability, to use that p( - Th,,) = An₃ during phase is a likely scenario.
We remark that the upper bound on the critical rate suggested by Conjecture T is smaller than the upper bound suggested by Conjecture 2 but the two are relatively close when is small and K is large. Proving either one of the two results presents independent challenges, and successfully proving either would constitute significant improvement the theoretical understanding of SGB.
E Proof of Theorem
We start by restating the theorem, before detailing its proof.
Theorem 4 (Logarithmic regret for identical gaps). Let u JK be a MAB instance satisfying
A2 -Ax- for some A E 1). Then, the regret of SGB luned with a learning rate
satisfying n K+2
22 is upper bounded as follows,
2 REO0 (v) < +T 2(K - 1) llg((T) + Iv for some constant r, > 0.
Proof. Instead of using Equation directly, we use Proposition 3 (Appendix F.1 to convert it into an alternative expression depending the probabilities ΣT= P(PL. < 1/2), that is more adapted to
47

---

the arguments presented in the rest of the proof. Combined with Lemma upper bound
we obtain first regret 2
(og(() + ())((()))
I <
PL. (pL
Rr $ 2(K -IK-1) 11.
+ 22
PP
which gives the logarithmic term of the theorem, and we can remark the constant r, should be an upper bound of 8(K - 1) 1)+ - (P1. 1/2). It remains to prove that the tuning of guarantees that the latter sum is finite. To do that, we use a proof inspired by the analysis of SAMBA [29]. Indeed,
similarly to the proof of Theorem we are going to prove that EE p, 1 is decreasing, under a condition
on 77 determined by the initial stage P1.1 K Using Lemma
17 with Hr O, thanks to the identical
gaps, we obtain that, for all steps t 2 1,
K
Cr 2
Σ Ph pk..) - Pc(1 Pe)
E2
S Pt
n( n))
(1 pi)²
Pr+1
K
Pt
W.
(21)
Comparing with our analysis for two-armed bandits (Th. []. the term W, causes additional difficulty.
To overcome it, we simply use that ΣK recursion as follows,
Σk=2 Ek=2 - Pk,+)) I
1-pt
I J. so we can simplify the
4
7 Cr 8
K
E
- (
- (1 -1-p1 pp)),
Pr+1
which we can now use to complete the proof of the theorem.
in finite time, we now consider the collection of time steps To starting in t == 0, and ending at the stopping time To corresponding to the first time p. 2 holds. We use that
Step 1: reaching
within To. when pt < 1/2, it holds that x pt)² 2 4. Thus, for S it holds that
Cn
Cnn (1 +2
Ex
1
7 -A (,,) = Pt
24
(22)
Pi+1
Pt
Pt
We then use that P1 K to obtain that n,,
24 K+2 then holds that E
1 1 e, for
the constant с = 2A- - (K + 2) > 0. We deduce that Elptita S Pr ct: by induction, if [ P1 -1 = K then, after taking expectations, the right hand term of the above equation is smaller than n/C,, (K + 2) 2 < -, for some constant > Hence, by using similar proof steps as Proposition of 29 we obtain that EElt A Tol S
K
2A [K+2)
Step 2: subsequent transient phases. We now consider additional transient phases: after reaching Pro 2 1 there is a probability that Prote < happens again for some > 0. This starts new 2'
transient phase Ti, starting at some step $1 > Tu. with initial probability 2 e 22 which is due to the step-size and the fact the previous iterate is above the threshold, i.e., Ps, > 2. Similarly, we can define potential subsequent transient phases (T)) For each phase, since the update formula
(22) only depends on the probability of arm 1. we obtain with the same arguments as for To. that
2e
Vj 1, El7, 85l83 +00) S
2A CK,
Step 3: finite expected number of transient phases. For any learning rate 7), there exists p E [0, 1) that, if p. 1/2 holds, then inf,21 P++. 2 1/2. In words, after the probability of the best arm reaches 1/2 there is positive probability that it remains above 1/2 forever; Vj 2 1, P(()+1 = +00 T < +00) 2 p. By conditional independence of the phases, is then direct to see that the expected number of transient phases is upper bounded by p which leads too
+00
K
1
20
Pt <
<
+ P 2A C, K + 2)*
2A
C K + 2)
48

---

which is problem-dependent constant with explicit dependency in K, A, We now prove that the -non-explicit- constant p positive.
Step 4: proving that > O. We first prove the bound for the first transient stage, which we then extend to arbitrary stage by the Markov property. Denote 4 1 Pt and let (To be the first iterate for which we know that Qro S 3. i.c., Pro 2 1.2 Assume there is a non-zero probability p' > 0 that the
subsequent iterate 9 is strictly bounded away from 1.2 that is, 41 2
We denote do to be the first time when qt 2 1 after the time To. that is: do == min 2 2 } Consider Geno for To, which, by the developments in (22). is a supermartingale. As a result we can sufficiently upper bound E Elqeroo
91++1 1
using the Optional Stopping Theorem as
E M 91
2 E Aeron 1 <c]
= E Ito 2 Tn Pul1l < + E < aol 1oo+1 <
p (oo S 5110ro+1 < + B < oollerot1 <d]
1000
1 (oo colom0t1 < <) 2
where in the second line we split the expectation of random trajectories that hit or before t and those that do not, in the third line we use the lower bound qm, 2 2.. and in the final line, we apply the Dominated Convergence Theorem and use that the second term remains a submartingale for and converges to O as t - co. Therefore we have
IP (an < 1 1-2c 0.
To factor out the assumption that goo+1 < C, we get
(oo colano11 S 2 = (1 - +') (oo = 00/9 <
-1- (1- 8)p' p' - -2)) := p 0.
The argument can be extended to stages using the Markov property. By the Markov property we have
P (av 00/T < 21>>0
We can decompose the events as
fax-1 < no 0k-1 < xo {m < xo),
and, since IP(TT:- ύK-1 < 00 00) by the developments in (2 and the bound the stepsize, we get
P ( < 00 < oo) = P < 00/TR < 00) 2
This concludes the proof that p 0, and thus that the constant T, of the theorem finite.
We finally state and prove counterpart of Corollary i in the setting of arms with identical gaps, showing that forizon-dependee tuning can also provide robust alternative to the knowledge of A in this setting.
Lemma 15 (VT regret with = 1/VT). Assume that = 1/VT, and that the bandit instance AK as Theorem A Then the regret of SGB upper bounded by RT(V) S log(T)VT on such instance, where only absolute constants are hidden.
Jk satisfies A2
Proof. Again, the gap A is small enough so that r/C, > K#z then we can upper bound the regret by AT, which yields (r S KVT. In the alternative case, we can use the bound of the theorem. The logarithmic term gives a bound scaling with K log(T) as desired. This could be sufficient if we aimed for problem-dependent bound, by leaving the constant r,,. However, it is relatively
49

---

easy to change the analysis to obtain a problem-indepeneee bound scaling with vT. Indeed, we first
(1 v²2²
observe from
that Vt
[ E
S K
K, hence by Corollary 3 holds that
K
1 A
W
A pb)
SA
E
75 n)C,))
2
Pr
K-1
11
T
AA
+
A K+2
2
K
2 + K $ KVT,
which finalizes the proof.
Additional technical results and proofs
In this section we present the detailed computations the tools presented in Section 3 for the regret analysis of SGB when there are more than two arms, with additional discussions presenting some intuitions that we did not include in the main paper for space reasons.
F1 Alternative regret bound from Equation
In this appendix we present an alternative regret bound that can be derived from Equation 7 and that we use in the proof of Theorem
Proposition (Generic regret upper bound for SGB). For any learning rate rj 0 and for any maxkelk] A. SGB satisfies the following regret bound,
e E (0, 1), defining Ce-
(1-2)A
E[O
T
VE FK R8S0 S C.
A
Σ
Proof. We start from 7 and consider bounding the failure regret in the right-hand term. For any E (0, 1), holds that
T
E
P1.)) 2
SE
Σ (1 PL.) L( <1-E)
E
(1 PI.)) p 1(pI, 2 1
E
(pI, <1 e0)
E
(1 1p:
Σ (pI, - + +
Σ
pI
By recognizing the regret in the last term and putting it together in
we get recursive relation
JKK
3GB
<
R
max
E[0,r]
+ A Amax
Σ
P (p1, +
which by reorganizing the terms provides
T
R
SCB
Rr < (1 - A)
A Amax
-E0r,
max
Σ
(p1. < c)
1-
The proof is completed by factorizing C. out of both terms.
50

---

Additional insights from Proposition 3 provides
We recall that, with the same notations, Equation
VV E
RT (v) S Co
A E
Σ (1 (1-
(L-PLe)
7
with both regret bounds valid for any value of 77 > O, and E (0, 1) in Proposition 3 Hence, proving logarithmic regret for SGB under specific choice of r/ can be equivalently done by either proving
that E
E pi.,)? oTlog(T)).
did in the proof of Theorem 1 that
E E o (log(()), for T = {o e (T] Pi,t 51-
In words, E[TT] simply the expected number of time steps for which the probability of the best arm is below the threshold 1 - c, within trajectory of duration T.
Then, believe that the following result is interesting to interpret the regret SGB the polynomial regime. We use the notation = B to express that both A S B and B S A hold.
Corollary 3. Assume that R2y00 (((T)) for some instance JK and some > Then, holds that
808
E
E
Σ (1
PI.))
Proof. From Lemma we know that E[ is always logarithmic, and can thus be ignored when comparing the bounds when the regret is polynomial. Then, the fact that the regret upper bounded by each term comes from Proposition and Eq. It remains to show that the converse holds. We first directly obtain that
T Σ
T Σ
RJ 2
AE
(1 pI.))
2 AAE
(1
pI.))
and then that
T
T
RE VV) N
AE
Σ
p1,))
A
Σ 1 (pI, S
which gives the result since the regret thus admits the same scaling as both quantities.
We interpret this result as follows: when the regret of SGB is not logarithmic, then it scales with the number of times Pı,t smaller than any fixed threshold. This gives a way to interpret the term EL_ (1 p1.)) as the failure regret introduced in the main paper.
Non-unique optimal arm We now show that Proposition 3 and Lemma 2 can be adapted when several arms are optimal, however we kept the assumption that one arm is optimal throughout the paper to simplify the presentation.
If the optimal arm is not unique, optimal arms together. Indeed, defining f.,-- Σ 02 1AA 0) and p.,t Σ Py. (A, 0) we have that
recover expression similar by grouping the K*
RT S Rr = max A E
Σ pa.e)
kE[K]
and also that
K*
K
E[00.,] = 7)
Σ
Pi
j=1
k=1
K*
2
Σ
Pj.a(1 - 14.1)
j=l
= Pr,(1 - P..))
51

---

Remark 3. It is actually quite intuitive that the number of optimal arms appear in the regret bound, since their respective parameters will increase slower by splitring the pulls among them. We believe that our lower bound Σj ePs. 2 K* e* that generates this multiplicative factor, is tight most so we can adapt Equation 7 by replacing 01,1 by 0.,, and P1,s by Pa,t- Then, for the proof of
Lemma 2 we only need to consider the event E [max x fx,e and remark that under this event and 0,t 7t it holds that
(K-K*)
1 1 PA.
2j=1 e + (K K*)
K
2ij=1 eba.
K K"
oet R
K K*
S K
R
K
so we can adapt the result of Lemma by replacing Yr K"* log 2n k- T). "T)
log(1 (K 1)nI)) by TT
plausible scenario if large enough. For instance, if the optimal arms share the same distribution we might the parameters of all optimal arms to be relatively close to each other.
F.2 Proof of Lemmal 2 and additional discussions
We restate and prove the lemma.
Lemma 2. For any horizon T for any learning rate 1), parameter 01,7+1 of SGB satisfies
T 1 / - ( (K-1)-
TT) ^ (K - (I- (log(T)) + 4n)
E 0 S log
Proof.
We propose two independent proofs for the two components of the upper bound.
First bound: we derive this first bound, depending on M sup K] sup E [<. from Jensen inequality. The proof follows the same steps as the proof of Theorem For any A > 0, we obtain that
E 1
|log (c2)) S log (E [c(0r])
1
We now study E. [e>@r]. using that e = A0.+6660. As in the proof of Theorem we use approximations of the exponential to get a recursion formula. More precisely, here we use that for any and bounded reward of expectation it holds that
Biear] 1 + gp
+00
L nl
Bl < + qu q²
+oc
n! 11 qu +
d² eq,
that we apply in the following computations with notation a; An(11 pt) and b, Anpi
F. [e>0 = A0. Egleddn, S A0, (p. |,, = 1]+ (1 - pt E(e bei | + 1)) +(1
1 [ Pt (ai11 a et /2) + (1- - -pp) (-b, max μa + e 12)12)) /2))
k22
S 20 (1+ p1 (An + (en)2=>1122))
where in the last line we replaced az, b, by their values and used that Am(p, V V1- Pc) S An.. We can further write that
e Pc - -p)) c(1+1)6. Exze0 pr: cAA-110
(e + Σk= Cko)2
For 2, choosing X = was convenient because made this expression exactly equal to p2- In general, we unfortunately cannot make this simplification. For that reason, choose À 1 to
52

---

eliminate the term depending on 11,-- Hence, we just obtain that
T-1
S 1 +
7
+
π
E
Σ
2
t=1
S +
7 +
e
sup sup E' (
(K T
2
122
which leads the first part of the result of the lemma.
Second bound: the main intuition of the proof is that, when 01r becomes large, it must be at the expense of another parameter, that must be very small. We formalize this with the following intermediate result.
Lemma 16. For any time horizon T 1, it holds that
E
min 0k.T - log((T) - 4n kE[K]
Before proving this result, we show that it immediately leads to the second bound of Lemma 2 by
Equation (9) holds that 1,, Em = Bxt I - (K 1) minxe[R] 0R, so
E & (K 1) (log(T) + 4n)
We now prove Lemma 16
Fix 7T = log( + v). and consider 07 == minke[K] OR. 2 0. Then,
|B (0 .τ + Bl0 (07 m)) SP (T S (T) Elo 7r)
We now use the following fact: 0 2 7T, then there exists a time step a < T such that
As E
7) 0g 2 rr and 0--1 < Yr
Using that O, E [TT, .T + v). we obtain that
E I P (07 - mr) + 107 2 7r)
2 B( - 1, 2 7r)
I P (07 - m2) + Ei(rr + m) 107 2 mr) B 0,) 2 ml)
< <n + 1| [ (0) 2 mr)
< Tr +
Σ
80
1(vs 2 u: 0, m7)
From this step, we carefully handle the randomness of u and its dependence with the event E, (Ys u 0- 2 } in the remaining expectation as follows,
E
Σ 50
1(Fmw
S E
Σ (50 (50 )+ 1(FN))
Σ (88_ )+ 1(0 2 2x))
< E
T
Σ (80,) )+ 1(0 2 mmm
< E
[.0 )+ 1 01 2 mT)
Then, for any round s E [T], let m, = argmin P denote the index of the arm corresponding to the minimum parameter. Then, it either holds that m, me+1, and 80, -80 m. 1.8 or
53

---

m... Hence, in both cases we that ma # M,+1. in which case mm... S 0m.4.. so 60.- 1 -00 m
have that (60,) ) _ 100m.+1.0+1l. To conclude, it remains to remark that, by definition of m and the fact that 0=+ rr, it must hold that 0m111s S -YT 7/, pm.i 0m t0 Hence, we can finally obtain that
T Σ
E
50,
I(Bu)
S En
Σ 2pm, 1: Pm, -mm (0m) 2 TT)
S 21yTe 1 < 2n
+x
F.3
Regret upper bound for two arms with time-varying rate
We develop in this section the counterpart of Corollary with a time-varying rate 1)s = V log(())
Proposition When A is unknown, the time-varying learning rate U): = log(evt) yields a regret bound Rr S 17) VT for any two-armed bandit v F=2, where the hidden constants are absolute.
The first part of the analysis consists in adapting Eq. 7 with time varying learning rates. We remark that the sequence (1) )12) is non-increasing, hence we can write that
Proof.
mh pt(1 pp) A Anr-
T Pt(1 Po)
E E
E
E
Σ
so we can reuse Eq. by replacing 7 by frr in the first term, which first yields
E
T
RT S
E
Σ (1 (1-p:)²
Then, by following the same steps the proof of Theorem I we obtain that
T-1 Vt 2 1, 2e4e20041] & 28. + + ( A + TH. Cr.)) = E 20 11+2 Σ (n + +1C,)) S
since the sequence (M)))2) can be upper bounded by constants. We further note that (e.g. vT) bound would change the result because is used inside a logarithm. We now consider the failure regret term. We first remark that, since the learning rate converges to 0, there exists deterministic time to satisfying sup C,C, < 2 More precisely, it holds that to S log(A 1) The last part of the proof consists in using the proof steps of Theorem I for tu. and obtain that
precise
A
A A.E.
log
A Σ (1
pt)
< Ato + 21 AA
suPr210 T/e Cn
A
T/T
remains to upper bound E[.x,,) We recall from the proof of the theorem that the following relation holds, for any learning rate,
VI 2 1: [x[++1] & st 2np 2. (A -n
which holds any arbitrary sequence of learning rate since the proof considers each time step separately. Hence, even in the worst case where T)t is much larger than A, we can use that
to
to
1x[2+41] - xe S n
so
E
E
m < log(to)
x log(to)²
10
54

---

We then deduce from the fact that E, (2441] regret bound of order
24 S o7 that B[ & log(to), which finally gives
(T)
log(
A
log(A-1)
RT 2
A AT
'/T
A
/T
log( A 1-
T (Tg((T) +
A AT,
A
and yields the result by remarking that the gap-dependent term cannot itself be larger than / (TTlog(T)) the dominant term of the bound is log(T))522 VT, that comes from the term involving Bf in the regret decomposition.
Remark 4 (Improved logarithms for 1/t 1/Vt). We remark that the above regret bound can be slightly optimized by considering ÿ) = =1/ that gives
log(T)
E n
S (Tg VT.
VT
TT
which becomes the scaling of the upper bound. However, we chose to study more precisely te
V log(tve) in this section and Appendix G.1 because it directly compares the optimal horizon-
dependent rate of Corollary 7
F.4 Proof Lemma
The proof of Lemma B is direct consequence of the following technical result, after using the same
telescopic arguments as in the proof of Theorem and that Σx=2 Ph. 2 K-1
(I-P1.)²
Lemma 17. Define On as in Theorem
Then, for any v E JKK and 2 1,it holds that
nH + 22 W. 2
1
1
E
<
GU (A mmn))) +
P1.+1
P1,t
P1,t
G = (1 - p1.t) + Σk= ph
with
Hi Σk = Pk.t (E, A.. (1 pk.
W. Σ k= Pk,t (1 Phi.t) (1, pI.))
In addition, H, Of =.. AK A and W 0 K =
Proof. We define Ia = 1. and use
13 to obtain the following recursion,
pi,
pk.t 0600,,-0081..
Tt++1 Ft
n'z² 2- By linearity of the By definition of Cn, for x E [- it holds that t S 1 + 1pE + Cn expectation, we deduce that
(1
K
r2 K 2
Ex[0++1] 5 Iz
1
1
Ph. E, 160,, 501,el +
Pkae IE, [8002 - (600,)-601,;)3))
We investigate the first-order term of the approximation. Using 5). and that 801, (Eq. ) we obtain that
>K kk 50n.
Ph.t E,, 180k. 601.I] =
(1
P1. Pk.)) Pk.t EpheAs Aj) = -E. (23)
k=2
34k
55

---

We now further analyze the newly defined term E,, that we express as function of B,[AA,]
Σj= PyAj. We can naturally decompose E, into positive and negative term. First,
K
K
(1-PI,c+ PR.,) Pu, PPSrs, - -(1- (1-P),))+
K
Σ
Pi.
B. E. GG, E.[
2=2
k=2
with G2 defined in the statement of the lemma. We then obtain that
K
K
K E - Pl, + ph.t) Ph,
Σ
P1, + Pk,e) Pk,t" Σ
Dk
5=1
k=2
K (1 - PI.0 B. + Pi
So, by subtracting the two we obtain that
E. (1 (1-)).e) P1,t E. +
Σ Pk.t (Ax- E.(DA.))
(24)
K
K
= -1-11P -1. PI,t" E, P1,
Σ
ph.
A
Σ k=2
Pk.e ((1 PI,))x - EIAAD (25)
k=
K
2 P (1-p).)) +
Σ
Pkot
He
(26)
k=2
This writing allows to obtain that H; = 0 if the gaps are identical, because in that case it holds that E,[AA, (1 P..
Let us now consider the term
K V1
Σ Pk.t E. [[60x. - 501,,)
k=1
To analyze the value of the term inside the expectation, it suffices consider three cases:
A E, [600.. -00,,) Spx,1 (1 p&,t pI.))² + P1,t" (1 P1,: + Pk,,) (1 - P1,t - pk.t) (f1,: pk.,)2
(1 - Ph,t + P1.. 2 = k]
(60 - -00,,))
(1 - P1, + Pk. 2 1]
4,1,
(p1. - 2 B(r A. + A
otherwise.
K}: Vk (2....,K},
Note that this expression is exact for Rademacher distributions, for which r? 1 always holds. Let us use the notation 2 = P1, Pk, to simplify some terms, and again drop the t subscript to simplify the notation. Replacing the terms, get
E (50x 20,)2 $ pk (1 (1+2)² + (1 +1 P1 Pk) 22
Pk (1+ 2z + 2²) + (1 22 + +2) + 2² - (pi + Pk) 2²
Pkk (1+ 22) +p1 (1 11-221 22
Pk + 2x +2
+ P1 2,
Pk
56

---

From this step we can continue by plugging back the value of 2, and finally obtain that
K
K
Pk
P
E
(50s
501)²]
Pk (p& p1 -p1 ))))))
(27)
k=
k=2
K
Pk (p& - pkk) + Pi - -p1) + 2p1ps)
(28)
k=2
K
K
Σ
Pk
(1 -Pk) + (1 (1- + 2p1
pk
(29)
2=2
k==2
(1- (1-p))²
2p1
Pk
Pk (1 pk) - Pı . (1 (1-p p1)²
(30)
where in the last line we made appear a term that can be expressed similarly to E, in the above computations. Finally, we get,
(n-PIi²+ -I--P1.)2++ Epnst) phos V S 27/p11.
r7² = w
k=2
with W; Σk Pk.e(1 -k..) - Pi, -P,,)) This concludes the proof, since is immediate that W, 0 for K 2.
E4.1 Properties of the components of Lemma 17
In this section, we investigate structural properties of the terms H, and W,, which appear in Lemma 17 in the setting K > 2. These terms complicate the analysis of the failure regret compared to the simpler case K 2. We believe that understanding their behavior is crucial step toward extending the theoretical analysis of SCB to multi-armed settings.
In particular, we show that H. and W; may exhibit non-trivial behavior even when K 3, suggesting that bounding them uniformly can be challenging. Nevertheless, we also identify several natural scenarios where these terms are either small or negative, which may help control their contribution in a refined analysis.
Property 1: He can be non non-negative
Consider a setting with K = 3 arms where Aa > Ag. Then, for any round t, dropping the subscript in the sampling probabilities for notational simplicity, we obtain:
He = (2 + P343 (p2 + + P5 + Pppds - (p2 + Ps Ps)
13pp3( A3 A2) + (2) As)
= >2p2 (2) - p3)
which is non-negative and only if p2 2 p3-
In the regret bound of Lemma the above result converts into a term
T
T
S# = Σ B = [=1
Σ
E
P2.1S..
(pe. pao)] -Pa.o)
(As -A2).
P1.t
There are several intuitive reasons to believe that this term can be controlled under reasonable tuning of the learning rate. First, we interpret the fact that p2, S P3, yields H[ < 0 as follows: if the current state of SGB is "very wrong", the sense that arm 3 (the worst arm) is currently treated as the best arm by the policy, some self-correction will occur, i.e. this state is unstable. This effect is even amplified if P1,1 is very small. Moreover, for the case where P2,1 > Ps,t. then H/ is positive but scales with pš, P Even in scenarios for which P2,: we might nonetheless expect P3, to have decreased "faster" than Pi.t. especially if Ag Ag is significant. In any case, scenario where
57

---

both P2,t and Ps, are significantly larger than P1,t appears quite unlikely, and we thus believe that H: should be (at least) bounded with high probability. This is also supported by the observation that H, 0 at initialization (where P2 = Ps 1/3).
Property 2: Generalization for K arms
For K arms, assuming 2 Σ ... I
Ak, we obtain:
K
H
Σ
Pk
2
Σ Py(4 -b))
k=2
j=2
K Σ k=2
Eps(A - -s)
Σ
Pン(An A3))
Pk
J=2
K
Σ
pイ A
PEp((As 11)
j=2
K
pン(4} - AR)
P)pp( ( -Ax)
2=
j>k
k=2
K
Σ
- PP))
which we believe might be useful for future analysis of SGB starting from Lemma 3
Property 3: W, can be non-negative
We again drop the subscript for the probabilities, and consider W, - -1
Let us consider again K = 3. and use the notation W. >k p2[1 p=:). Then, using that
P3 = P1 P2 we re-write Wr as follows,
W. = (1 p2) p3 p3) = p3 - (2) p2) P1 - p2) - p2)
= (1 - pa) -1)2 p1)² 2p221 - P1) 2p (1 p1) + pēP1 + p.
3 = =PI(1 - pp - 3p1) -2p3 + 3p2p1
=Pi(1 - -11=- + P2
p1) - -3p))
= -P1(1-11) -
+ p2 3p2) (1 P2 P1).
Hence, we obtain the simple property
K=3- W, = P2,1P3, 3p1,)), so 2 0 1/3.
< 3.2 the maximum of W, achieved when pa = =3 1-p1 Furthermore, is easy to see that for pı and so:
2
W < (1 pI.)) 1 1-3p1.
4
Note that this allocation is always feasible for K 3, which provides least a lower bound on the maximum possible value of W2 in general.
Property 4: P1,t 2 2/4 We < 0
We proved this property for K 3. in fact showing that the relation is equivalence in that case, and now extend for K 3. Let assume that Pı,, 2 - Then, under the constraint Σ Ph the function p (1 pı) is increasing over all admissible values of pk- By symmetry, we deduce that the maximizer W should be achieved when m of the suboptimal probabilities are equal to 1-21 and the remaining ones are zero, for some E [K- - 1]. For a fixed m, this yields:
Pl.
(1 22)
1 P1 )
W
1
pi 11--pp p1)
m²
m
58

---

If m were continuous, the maximizer would be m = 2 P1). Since m must be discrete, it is either m or m 1. Both cases yield W O.
This property shows that once SGB correctly identifies arm as the best arm and assigns it a sufficiently large probability, the term W, ceases to be problematic and longer contributes adversely to the dynamics of Lemma 17
Property 5: W; 0 if the sampling probabilities are uniform
We conclude this section by showing that Pı,t 2 is sufficient but necessary for W2 be small. In partieular, the uniform probability vector p ..... xK) also yields
W = (K 1)p((1 p1) ) P1 pı)² - P1 (1 p1)
0.
This indicates that W; = at the uniform initialization, and thus should remain small in the very first steps of the algorithm. This observation supports the idea that the carly-phase behavior of SGB is not negatively impacted by W,. fact, we even conjecture that, under properly small tuning of the learning rate 77, might be possible to prove that E
pi.r S
Wi
for all steps 1.
F55 Regret upper bounds for two arms under alternative assumptions on rewards
In this section we discuss how the regret upper bound of Theorem | and in particular the necessary condition on 77, can be adapted for unbounded rewards. Indeed, the boundedness of rewards is only used to derive Equation [8) where we use second order approximation of the moment- seenenttgneeraing function of rewards. By considering alternative assumptions, we can modify this equation and propagate it in the rest of the proof.
Sub-Gaussian distributions Consider the classical example a2-sub Gausssian distribution y of expectation By definition, it satisfies the following condition,
4/ E R, E,ww S eant 2"02
To adapt our results, we can thus perform second-order approximation on this inequality, and not directly on e Assume for instance that i o" then we can write that
2 Vg E [-1, Eray [e S equ+ _
S + qu +
0²0²
qu
+
-002
2 )
+ +(0gg)
2
0²
+ qu + 9²
122
+ O(9²).
2
In the rest of the example, we neglect the Ogq") term for simplicity of the computations, and present how the problem quantities appear in the results with this simplification. To use the above result, we further assume that 21) < 1. Then, it is easy to verify that we can follow the proof steps of the thcorem, and essentially replace C,2, (which is s 1 in the theorem) by oी 2 This yields
log [1+2 n n + n2 1 o0 ))) T
E [ S 2
for the logarithmic term, and the condition on 17 to guarantee that IE[(1 pc) = O(1) becomes
2A
1) S 0² + max 1
This result shows that SGB can work with unbounded sub- Gaussian rewards, properly tuned accord- ing to some additional knowledge on the variance proxy and the range of the reward expectations.
Bernstein condition This assumption is also standard (see Chapter 2.8 of Assume that all reward distributions satisfy the following moment conditions,
1 [K], Vm 2 2, E 11r 1"1 s m.
3B 0:
Ak
2
59

---

This condition is quite handy for the analysis of SGB, since we can now adapt Eq.
8 as follows,
4q E :: Eywu(ee") = 1 qu
E
m!
m==
[r
+000
+ q/
(qB)m-2
2
m==
[
1
qu
2
q
we further assume that yB < 1, From this result, if we ignore the I- term for simplicity (that is, BB < 1) then follow the proof steps of Theorem and obtain sufficient condition 1) < 3
for logarithmic regret, with 22 max Ey,ey [r2
G Supplementary experiments
In this section, present additional experiments that support the theoretical findings of the paper and complement the empirical results from Section We provide the code in the supplementary material accompanying the paper for reproducibilityy
For simplicity, all experiments use Rademacher distributions unless stated otherwise. These distri- butions are particularly well-suited for our purposes, as they maximize variance for given mean under the constraint that rewards lie [-1, 1). Intuitively, they represent the most "challenging" case within this setting.
Before presenting results, clarify key terminological choice: throughout the paper, the term regret refers to the quantity defined in expectation, as in Eq. (T). In this section, we report empirical estimates of this quantity based on multiple runs of the algorithm. Given M independent runs under a given policy, the empirical regret is computed as
M
1 M
R
R
A
(31)
M m=1
m=1
k=
where Ng (T') denotes the number of pulls of arm [K] up to horizon T' for the m-th run of the policy.
For any M E N. it directly follows that R2 E
R
In this section, as well as Section 4 in
the main paper, the term regret (or average regref) refers to this empirical estimate unless otherwise stated. Finally, references to the "regret" specific trajectories refer to the values of ( (RT) m for subset of runs indexed by M, while references to the distribution of regret pertain to the empirical distribution the values (R27)) mE[M]
G.1 Time-varying learning rate
We start by illustrating the results presented in Corollary | and Appendix F3 establishing the theoretical guarantees SGB with time-dependent learning rate. each setup, we run SGB tuned with:
the oracle gap-dependent tuning 7 =
24
K
a horizon-dependent gap-free tuning 1)
log(T) which requires to know T' in advance,
anytime tuning 1) = p K log(t)
for some clipping parameter p that we discuss.
We consider horizon T = 10 - for which it holds that log(2')
0.03.
will be turned into Github link after publication.
60

---

Two-armed bandits We evaluate two configurations, both featuring sub-optimal arm with mean In the first setup, we A 0.05 explore a regime where the initial anytime learning rate significantly exceeds the oracle tuning. In contrast, the second setup uses A = 0.5 to examine the opposite scenario, where the learning rate decays quickly relative to the gap. This allows us to highlight the algorithm's sensitivity to the relationship between the decaying learning rate and the problem difficulty.
The results, presented in Figure 3 lead to two key observations. First, the horizon-dependent tuning yields sublinear regret both setups, supporting the theoretical guarantee of Corollary II Second, the experiment with A = 0.05 highlights the critical role of the clipping parameter p in stabilizing performance under the anytime rate: while the average regret under 7) = 0.5A /log(t)/' is sublinear, significant fraction of trajectories suffer nearly linear regret. This effect is substantially mitigated by setting م 0.1 instead of 0.5. Interestingly, this improvement arises despite the fact that th drops below naturally (without clipping) after approximately 650 steps, suggesting that early iterations with an overly aggressive learning rate can severely compromise the algorithm's trajectory.
This observation echoes findings from prior work on the sensitivity of SGB initialization 14 15
In particular, as suggested by Theorem @ if SGB is run with a poor learning rate up to time lg. then with non-negligible probability it can reach a state where Pi,ta S t5", making recovery exceedingly slow.
K- K-armed bandits The insights presented for two-armor bandits extend to third experiment with K = 5 and A = 0.25, where the use a time-varying learning rate again leads to high variance in regret across trajectories, effect that only tighter clipping avoid. In this setting, it takes approximately 4000 steps for the un-clipped learning rate to fall below the oracle tuning.
Overall, these experiments emphasize that phases of substantial over-estimation of the learning rate should be avoided all costs to ensure reliable performance. no information about is available, tuning the learning rate using the final horizon 7 appears more robust, and the case where T is unknown can handled using a standard doubling trick. More generally, any use of excessively large learning rates, even briefly, can result in high variance across runs. Nonetheless, these experimental findings remain consistent with the theoretical results established in this paper, as the regret (in the sense of Eq. (I) is defined in expectation, and the sublinear guarantees for time-varyiin tine-varying learning rates apply in that sense.
302
-* f) A 0.05
f)
5- 0.5
602-
n= V
0.03
T1 0.5 Sigte
122
Emuiiical ol flggitt
302-
n: 0.1
302
Empirical
40-
002-
02-
102
2002
Time
Figure 3: Average regret and 10- 90% percentiles up to horizon T 104 N = 5 10a trajectories on bandit problem with means #1 0.05, #2 = 0 (Left), μ1 0.5, #2 (Right).
G.2 Comparison with standard bandit policies
We now benchmark the performance of SGB against several standard bandit policies. Motivated by the literature review in Appendix A..3 we include range of algorithms that exemplify different frameworks for balancing exploration and exploitation:
UCB, in its standard implementation [8] Figure 1].
Thompson Sampling ing (TS), using Beta prior/posterior setup 19 46
and a uniform prior.
MED, implemented with the Bernoulli KL-divergence
49
53
61

---

1750
7t 0.5
1500
-A 11 2
0.1
Regrot
0.007
2300
750
250
2520
Time
Figure 4: Average regret and 10 90% percentiles up to horizon = 10 N 5 10 trajectories
on the bandit with means μ 0.25, #2
M55 O.
While less standard, we include it as an alternative application of the policy gradient principle bandits.
SAMBA, as defined by Walton and Denisov 229
Since each of these policies is designed for Bernoulli rewards, rescale the Rademacher rewards to binary format before passing them to the algorithm: each reward r transformed = 0.5 (r fr++0 +). We emphasize that this transformation is not applied to SGB, which directly receives the original Rademacher rewards, r E (-1,1}.
Among the selected baselines, both MED and TS are known to be asymptotically optimal in the considered settings, in the sense that their regret upper bounds match the Lai & Robbins lower bound (36. For optimism-based algorithms, we chose UCB over KL-UCB. While KL-UCB offers better asymptotic guarantees, on par with and MED, requires solving an optimization problem every time step which significantly increases its runtime. Given the scale of our experimental evaluation, spanning many settings and runs, this choice is primarily motivated by practical considerations. Additionally, benchmarking SGB against other algorithms (like UCB) that are not explicitly tailored to the KL-divergence structure the environment offers a complementary perspective on its empirical performance.
Parameters tuning To ensure fair comparison between SGB and SAMBA, we followed a consistent rule for setting their respective learning rates. The experiments presented in Section 4 of the main paper indicate that, for both policies, the most effective strategy seems to consist in using the critical learning rate predicted by theory for each specific setup. For SGB, this leads to choose 1) 2A К which we conjecture to be the critical threshold for K > 2 (see Appendix D.3). For SAMBA, we a 3. As discussed in Appendix B.2 Walton and Denisov 29 prove logarithmic regret for Bernoulli rewards when a P1- max422 ML
The factor \/ in our tuning arises from the rescaling of rewards from the interval [] to [0, 1]. and we deliberately ignore the denominator to avoid introducing further assumptions on the mean values of the arms.
Experiments We consider four experimental setups designed illustrate the comparative perfor- mance of SGB across range of scenarios:
In Figure (Left), we consider a setting with K 5 arms, all with means close and where each sub-optimal arm has the same gap A = 0.1.
In Figure 5 (Right), we consider setting with K = 10 arms. The minimum gap is 0.2, while the other sub-optimal arms have significantly larger gaps: 0.5 for arms and 1 for five arms.
In Figure (Left), we consider K = arms with very low rewards, with -0.8.
In Figure 6 (Right), we consider K = 4 arms with high rewards, with = 0.96, and the worst arm having mean 0.9.
The first setup illustrates that, when the problem is fully aligned with the oracle information used by SGB (i.e., A known and exactly matches the gap of all sub-optimal arms), the performance of SGB closely matches that of state-of-the-an th-ttr- policies such Thompson Sampling. Although TS achieves
62

---

this without oracle knowledge, the experiment shows that, for well-specified problems, SGB can be highly competitive with proper tuning.
In contrast, the second setup highlights a limitation: when the sub-optimality gaps vary significantly, SGB becomes sub-optimal compared to optimized policies like MED and TS, which implement separate exploration mechanism for each arm. While it still performs reasonably well (e.g., better than UCB), the fixed learning rate results in over-exploration of significantly sub-optimal arms.
Finally, the last two experiments in Figure 6 demonstrate that although SGB outperforms UCB in scenarios with extreme means (close the boundaries of the [-1, 1] support), cannot compete with approaches like MED and TS, which leverage KL-divergences or tailored posterior distributions to better adapt the geometry of the problem.
In all setups, SGB compares favorably to SAMBA in terms of both average regret and the 10-90% empirical regret range. We believe the parameter tuning of both methods is fair with respect to their theoretical guarantees and the level of oracle information used. more detailed comparison with SAMBA is provided in Appendix G.4
- SGB, -- -=200.004
1200
SGB, n=
TS
T5
MED
MED
UCB
Em Emplhtiall Regret
UCB
SAMBA, = 0.05
-
SAMBA,
a #.
Empéiial
602
600
2024
200
Tim
Timc
Figure 5: Average regret and 10 90% percentiles up to horizon T 10 N 5 10a trajectories on the bandit problems with averages μl = 0.1, μ12 N3 = Ms O, and Ug = Pıo 0.5 (Right).
A4 = 0 (Left), and μr = 0.5, M2 = 0.3,
SGB, q- 0002
SGB,
( 0.02
502
TS
TS
402
UCB
Empinical Beggest
302-
UCB
SAMBA, 2=3 0.025
SAMBA,
a= 0.00
802
Empiitaal
202
Time
Time
Figure 6: Average regret and 10 90% percentiles up to horizon 10 N 5- 10 trajectories
on the bandit problems with averages μ41 -0.8, μ/2 = -0.85, /43 μ14 -0.9 = 0, 145 = 0095 (Left), and yr 0.96, l12 μa 0.92, μr = 0.9 (Right).
G.3 Asymptotic tightness of Theorem
We propose set of experiments designed to verify the tightness of the log(T) factor in the regret upper bound of Theorem for K and support the conjecture that the bound Lemma for general K might be tightened by factor K_
K
Two-armed bandits For the case K 2, we consider problem with means μ4r = and
μ22 -0.25, that A 0.25. We perform 1000 independent runs of SGB over horizon T 10 for three fixed learning rates: E {0.05, 0.1, 0.2). Each choice of r lies within the range of validity of Theorem In Figure 7 plot the empirical regret (computed as t + R.M see Eq. (31) with
63

---

= = 10") in logarithmic scale, along with the theoretical curves t + log( learning rate.
corresponding to each
To facilitate the comparison of the asymptotic slopes, we represent the r-axis in logarithmic scale, and each theoretical curve is vertically shifted to match the empirical regret at time T. That is, we plot
log(()
log(T)
t E (T)
RM
21
27
The figure confirms the tightness of the bound in Theorem values of 7,, the empirical regret closely follows the theoretical prediction as increases, thus supporting the sharpness of the logarithmic term in the regret bound.
for for this particular setup: for all three
SGB, /71 0.2
80
t log(t) ā1
Empirical Regret
2/:
60
SGB, f72 = 0.1
t log(t)
2m a2
40
SGB, n/3 = 0.05
log(t) a3
20
+ 2nz
0
-20
10
10a
102
103
104
10s
Time (logarithmic scale)
Figure Empirical regret of SGB in logarithmic scale up to horizon T 10 averaged over N 103 independent trajectories on the two-armed bandit problem with means ll 0 and μ2 -0.25. Results for three learning rates (πK)εt E {0.05, 0.1, 0.2), where the offsets (a,)ie are chosen so that each comparator curve matches the empirical regret at time T..
K-armed bandits. We now consider two experimental setups with K In the first, with K = 4 arms, we set ıt1 0 and choose sub-optimal arms with mean -0.4, so that all arms share the same sub-optimality gap. In the second setup, with K 5, we choose μl = 0.9, A = 0.65, and #3 μ4 ns = 1, so that the minimal gap is A 0.25, while some arms have significantly larger gaps.
The results, reported in Figure show that in both cases the regret appears to scale asymptotically as K-1 log(T) While this behavior can be expected in the first setup, where all sub-optimal arms K symmetric, the second case is more surprising. We refer to discussions in Appendix D.2 for additional insights. Based on these observations, we formulate the following conjecture.
Conjecture 3. For any bandit problem E JKK in the post-convergence regime, all sub-optimal arms E [K] are explored at a rate k "Ast: and thus contribute equally to the overall (asymptotic) regret, each by term nK log(T').
Note that this conjecture is stronger than the conjectures formulated in Appendix D.3 Conjecture 1 could be proved a consequence of Conjecture while the latter would considerably help in proving Conjecture 2 as discussed in Appendix D.3 Additionally,
emphasize that in such Rademacher/bounded settings, optimized policies like TS and MED typically satisfy an asymptotic exploration rate of 2 (up to some KL-divergence approximation). which matches the above rate if
2AL This coherent with the result of the first experiment presented in Section G.2 A
To further test the conjecture, we considered two additional setups, for which the results are reported in Figure 9
We considered instances with K and K 12 respectively, with arms with various
64

---

SGB, n. Pt=001
SGB, n
175
t x ligli! D2
400
( x Ingit +
Empirical Regret
150
Empirical Regret
SGB, f2
SG8, 02 0.05
125
[ loght! b2
300
( laght + 02
100
SGB, n 0.05
5GB, 0
K-1 logi!
200
t-
50
100
10"
10
10
10a
10
10a
10
102
10a
10*
10s
Time (logarithmic scale)
Time (logarithmic scale)
Figure 8: Empirical regret of SGB in logarithmic scale up to horizon T = 10 averaged over N = 103 independent trajectories on bandit problems defined by li = 0 and μl2 μa = μM -..4
(Left) and μ1 0.9, M2 0.65 and μ3 /44 145 -1 (Right). Results for three learning rates (n))et)) E ( K K J, where the offsets (b,)xe(3) and (c)) (egg are chosen so that each comparator curve matches the empirical regret at time T.
gaps. More precisely, the instances considered in the two experiments are parametrized by the following averages,
1xp.1 (0.5,022.2222000000022-----003
and /xxp.2 (0,40.4, -04, -0.4, -05,, 0.5, -0.6, 0.6, 00.8, -0.8, -0.83
We still observe the same asymptotic scaling as in previous experiments, which hints that the conjecture holds.
SGB, = 0.066
SGB, // 0.066
TH f=1 log!t 15
1000
tr x logit + 7%
Empirical Regret
SGB, 02 = 0.033
Empirical Regret
SGB, 02 0.033
600
t=* logtt! 16 SGB, m7 0.016
800
to legid)
600
//
400
t+ K
x logid)
K-1 +
400
200
200
0
10a
10
102
10a
10c
105
10"
101
102
107
10"
10a
Time (logarithmic scale)
Time (logarithmic scale)
Figure Empirical regret of SGB in logarithmic scale up to horizon T 10 averaged over N = 10 independent trajectories on the bandit problems defined by averages Mxxp.1 (Left) and averages /xp2 (Right). Results for three learning rates (11 [e]] { 2 K K ). where the offsets (d4)se[s) and (es) (rr chosen that each comparator curve matches the empirical regret at time T.
A 24
G.4 Detailed comparison with SAMBA
We now isolate SAMBA and SGB, and propose experiments with the double objective of highlighting the differences between the two approaches, and illustrating the discussion of Section regarding the tuning of the learning rate in PG methods under additional moment conditions, We mainly focus on settings with K 2, since the experiments presented in Appendix G.2) G.2] already show that SGB and SAMBA directly comparable for K in various scenarios.
In contrast with previous sections, where we considered Rademacher rewards, all problems this subsection involve Bernoulli rewards. This model choice allows discuss the performance of
65

---

SAMBA directly in the setting under which it was originally studied in [29]. Contrarily to Rademacher rewards, this setting further allows us to design problems that exhibit interesting moment conditions. for instance by specifying low average rewards, as typically encountered in online advertising [34
First, we compare SAMBA and SGB in configurations where their parameter tuning (denoted respectively by and 7) yields the same asymptotic regret bound. Indeed, while Theorem gives regret bound scaling log(T) for SGB, Theorem 1 of (29) gives a bound of Tog(T) for SAMBA. Hence, in Figure 10 2nj
we present results for two experiments where we choose tunings a = A and 1) +. While in both cases the asymptotic (logarithmic) scaling of the two policies appears to match-illustratee by parallel average regret curves in logarithmic scale-their pre-convergence behaviors differ significantly. Our results suggest that for these "equivalent" asymptotic tuning. SAMBA outperforms SGB in the settings considered.
However, while the parameter is already maximized under additional assumptions on max:22 (4g, the learning rate n of SCB could be increased further, up to A. This illustrates that even if SAMBA and SGB share comparable post-convergence dynamics under appropriate choices of learning rates, as discussed from a theoretical perspective in Appendix [8.2] their pre-convergence
behaviors differ considerably. As such, the two policies may have distinct merits and limitations. In the figure, we retain TS from the benchmark policies introduced in Section G.2 to illustrate the performance of state-of-the- bandit policy this problem.
300
-A SGB, 5.055
T5
-+- SAMBA, a= A.0.1
-+- SAMBA, a=A=0.1
Empaaicdl Begget
Ento Emo-rk-al
5-
Oogerithmic
Time (kggarthmicccomm
Figure 10: Empirical regret in logarithmic scale up to horizon T = 10 averaged over N = 10 trajectories on the bandit problems defined by la 0.6 and μ42 0.5 (Left) and μ 0.4, #2 0.1 (Right). In both cases, SGB is tuned with v 2 while SAMBA uses a = A.
Then, we illustrate how additional moment assumptions allow SAMBA and SGB to perform well with learning rates larger than A. We consider two problems with Bernoulli rewards with small average values. In first experiment, with K 2 arms, we use the same learning rate for both algorithms, 17 = a = p1
A. in a second experiment with K = 10 arms and averages μ1 = 0.05
ni but adopt 7 Kri in order to align with our analysis. We recall that the theoretical guarantees of SAMBA for this tuning of a hold for any number of arms K. thanks to careful design of the policy that updates the leading arm differently from the others. We refer to Appendix [B.2 for details. The results, presented in Figure show that the additional oracle knowledge allows the PG algorithms to achieve performance that can be comparable to Thompson Sampling. Notably, in the first experiment the regret statisties of SGB (average regret, 10-90% quantiles) closely match those of TS; and in the second experiment the average regret of both PG policies remain competitive, although SAMBA suffers larger variance across trajectories than TS. Nevertheless, we can further remark that in both cases the variance across trajectories is considerably smaller for SGB compared to SAMBA. Although the results do not suggest that PG methods should be preferred over TS even under the additional assumptions we introduced thheeeee-hhhheeeeeeeeeeeeeee fact that their performance is comparable to a policy that is optimized for the considered family of distributions is notable.
and μ22
1410 0.03, for which we still choose
We then consider a third experiment with K 10 arms, defined by the following means:
A
Mxp-3 = (0.1. 0.09, 0.09, 0.08, 0.08, 0.08, 0.05, 0.05, 0.05, 0.05). So
0.1.
f11
In this setting, several sub-optimal arms have sub-optimality gaps up to five times larger than that of the second-best arm. As illustrated in Figure 12 and in line with the discussion of the second
66

---

79-
-k-
SGB, n= =02
100
5GB,
aM 0.08
61-
==
SAMBA -0.4
Empiraal Beggee
Emuut cal Boegee
62-
-20
23-
-00
10
50
2300
5005
7500
20035
12500
15020
17503
20000
2500
5000
7500
10300
32500
25000
17530
22000
Figure 11: Empirical regret in logarithmic scale up to horizon T = 10 averaged over N = 10
trajectories on two bandit problems with small averages: μ4 = 0.05 and μ22 0.04 (Left) and K = 10, M1 0.05, 13
111 0.03 (Right). In both cases, SGB is tuned with yj Kp
2A
while SAMBA uses a
experiment in Figure 5 the performance of PG policies degrades (specifically, compared optimal policies like TS) when the learning rate is tailored with respect to the second-best arm, while larger learning rates could improve performance for arms with larger gaps. However, considering arm- dependent learning rates would require oracle knowledge of all arm means, which might be unrealistic in many applications.
SGB, 26 0.02
400
TS
Regret
200-
200
Time
Figure 12: Empirical regret in logarithmic scale up horizon T = 10 averaged N V11 trajectories on the bandit problem defined by K 10 nd μ 4xp.3. SGB is tuned with 17 = Kpp while SAMBA uses a
24
Finally, in order to further understand why SGB compares less favorably SAMBA in the experiments of Section G we investigated whether SGB could perform better when rewards are centered around 0 (Rademacher) rather than always positive, in the of Bernoulli rewards. From statistical perspective, an instance with Rademacher distributions of means (μo) is strictly equivalent to an instance with Bernoulli distributions of means (1++1)
ke kE|K] However, the experiment presented
in Figure 13 shows that the results of SGB tuned with r = 2 for Rademacher distributions are significantly better than the results SGB with 77 = for the corresponding Bernoulli distributions, which is nevertheless an "equivalent" tuning of SGB, more precisely both match the critical learning rate their respective setting. This can be understood through Theorem [ which shows that even though both algorithms Bernoulli case is twice as large as the bound the Rademacher case.
the same oracle knowledge, the logarithmic term of the bound in the
This last result suggests that the performance of SGB is optimized when the rewards cover a centered interval like [- in particular if tuned solely using that the rewards are bounded within known range. Intuitively, it is natural to expect that the full potential of the theoretical tuning from Theorem [ is achieved when the restriction on rj is tight due to upper bounding the failure regret tight, which we proved to be the case for Rademacher arms (see the paragraph "tightness of the bound"
67

---

SGB, ? 0.08, Rademacher rewards
SGB, n 0.04, Bernoulli rewards
200
150-
Empirical
50-
0 2000
4000
6000
8000
10000
Time
Figure 13:
Empirical regret up to horizon = 10 averaged over N 10 trajectories on the five-armed bandit problem defined by μ4 = 0.2 and μ22 and the corresponding Bernoulli instance.
145 for the Rademacher instance,
after Theorem D scenarios where y tuned using additional moment knowledge- instance, on the second moment an_ transformation that minimizes A would also lead to better empirical performance. For closely related discussion, centered on the properties of adding baselines in SCB 's update, we refer to Section 6 of [[].
68


Reviews:
[{"review_id": "HGMFY2rv84", "reviewer": "Reviewer_9S4k", "summary": "This paper considers the regret bounds of softmax policy gradient (SPG) for Multi-Armed bandits when using a constant learning rate that depends on the minimum reward gap of an bandit instance. Rather than analyzing the method using techniques from optimization, the authors instead consider the regret decomposition using the SPG update. As a result, the author show that depending how close the learning rate is to the reward gap, SPG either achieves logarithmic or polynomial regret. Additionally, the authors conduct experiments on simple bandit problems to support their theoretical results.", "questions": "1. This work mostly focuses on constant step-size since the objective satisfies a condition similar to the strong growth condition [1].\nHowever, is it possible to technique introduce in the paper can be extended for decreasing step-sizes (or a reason why it cannot) for $K > 2$ arms?\n\n2. Just to clarify, is not required to assume that all rewards are distinct, i.e. $\\mu(i) \\neq \\mu(j)$ for $i \\neq j$. This is a common assumption in prior work [2] and it's surprising to me that it's not not needed.\n\n3. In the proof sketch of Lemma 1, why are the rewards deterministic?\n\n\n[1] Mei, J., Zhong, Z., Dai, B., Agarwal, A., Szepesvari, C., & Schuurmans, D. (2023, July). Stochastic gradient succeeds for bandits.\n[2] Mei, J., Dai, B., Agarwal, A., Vaswani, S., Raj, A., Szepesvári, C., & Schuurmans, D. (2024). Small steps no more: Global convergence of stochastic gradient bandits for arbitrary learning rates.", "limitations": "Yes, the authors sufficiently address the limitations.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "**Strengths**\n1. Provides a throughout analysis for SGD when using constants step-sizes and obtain regret bounds that do not depend on $\\inf_{t \\geq 1} \\mathbb{E}[p_{1, t}]$ which appear frequently in prior work.\n2. The paper is well-written and motivated. The proof and proof sketches in the main paper were digestible.\n3. The empirical results support the theoretical findings. \n\n**Weaknesses**\n1. The results appear to require the rewards to have support $[-1, 1]$ which restricts common distributions such as Gaussian distributions\n2. The results for $K >2$ arms seem to be fixated for constant step-sizes depending on $\\Delta$ and does not seem to have analogous results such as Corollary 1.\n\n**Clarity**\nIt would be good to explicitly mention that the smaller dashed-lines represented the percentiles in Figures 1 & 2.\n**Originality**\nI believe this work offers a novel technique for analyzing SPG methods when using constant step-sizes and introduces different view when considering such problems.", "was_revised": true, "final_justification": "I recommend to accept this paper. My initial questions were fully addressed and am happy with the authors response. It would be nice to have an extension of Corollary 1 for $K >2 $ arms, but I believe their contributions are already sufficient for acceptance.", "rebuttal": "We thank the reviewer for their thoughtful comments and are glad that you appreciated our results. Below, we address the specific questions and concerns raised.\n\nW1. **Assumption on reward support**\n\nThroughout the paper, we assume that rewards lie in $[-1,1]$ for clarity and simplicity, following a common assumption in the literature, particularly in prior work on SGB. However, our analysis can be extended under alternative assumptions, such as sub-Gaussianity. The key step where boundedness is used is Equation (8), where we apply a second-order Taylor expansion and upper-bound the quadratic term by leveraging the boundedness of $r\\in [-1,1]$. If instead $r$ is $\\sigma$-sub-Gaussian, we can use the standard bound\n $$\\mathbb{E}[e^{qr}]\\leq  \\mathbb{E}[e^{q \\mathbb{E}[r]+\\frac{q^2 \\sigma^2}{2}}], $$\n\nand then apply a second-order expansion to this expression (e.g., assuming $|\\mathbb{E}[r]|\\leq 1$). The rest of the proof of Theorem 1 would follow similarly, yielding a slightly different condition on $\\eta$ depending on the variance proxy $\\sigma^2$ and $\\Delta$.\n\nIn summary, the boundedness assumption can be replaced by the assumption that rewards are sub-Gaussian, with means bounded in a known range (e.g. $[-1,1]$). We omitted this observation for space reasons in the submission but will include it in the final version.\n\n**Clarification on Figure 1 & 2**\n\nThank you for the suggestion, we will update the captions accordingly. \n\n1. **Decaying step-size for $K>2$**\n\nYou are right that we do not provide a counterpart to Corollary 1 for $K>2$ in the main paper. This is because completing the regret bound in the constant step-size case (specifically, bounding the second term in Lemma 3) is also essential for extending the analysis to decreasing step sizes.\n\nNevertheless, in Lemma 15 (Appendix E), we show that with a step size $\\eta=1/\\sqrt{T}$, the regret is $\\mathcal{O}(K\\sqrt{T})$ in the special case where all sub-optimal arms have the same gap. This is a promising first step, and we will highlight this result in the main text below Theorem 4 in the revised version.\n\n2. **Do we require distinct means?**\n\nOur analysis does not require all rewards to have distinct means. In fact, Theorem 4 specifically addresses the case where all sub-optimal arms share the same mean. This indeed contrasts with some prior works (e.g., [2]) and suggests that such a separation assumption may not be necessary. Moreover, in Appendix F.1 (starting at line 1718), we briefly discuss how parts of our analysis can be adapted to handle multiple optimal arms. \n\nWe believe that the general case with $K>2$  can be addressed without requiring this assumption, and plan to explore this in future work, by building on Lemma 3.\n\n3. **Why are the rewards deterministic in Lemma 1's sketch?**\n\nLemma 1 establishes a regret upper bound for *all* $\\eta>0$ on an *easy instance* with deterministic rewards. Hence, on this instance SGB admits logarithmic regret for all learning rates. We use this result in Theorem 3 to show that this regret bound is “too good” to guarantee consistent performance over all instances. Specifically, by comparing it to the Lai & Robbins (1985) lower bound, we deduce that if $\\eta>1/(K-1)$, the algorithm cannot guarantee logarithmic regret on all instances. More precisely, there exists a more difficult problem for which the regret must be polynomial. \n\nTheorems 2 and 3 provide, to our knowledge, the first necessary conditions in the literature on the constant learning rate $\\eta$ for SGB to achieve logarithmic regret. However, we emphasize that these conditions are necessary but not sufficient. In Appendix F, we formulate conjectures suggesting that the true critical threshold for $\\eta$ may in fact be $\\frac{2\\Delta}{K}$ for general $K \\geq 2$."}, {"review_id": "1476l45BV4", "reviewer": "Reviewer_SAiY", "summary": "The paper considers \"stochastic gradient bandits\", a simple instance of the stochastic policy gradient method where the actions are sampled from a softmax policy whose parameters are updated via a specific randomized estimate of the gradient of the value of the policy. This algorithm is noteworthy due to its simplicity. Recent previous work has established that any constant learning rate guarantees convergence to the optimal policy, and a small enough (but \"gap-dependent\") learning is sufficient to get an O(1/t) convergence of the policy (implying a log(t) regret bound). This paper refines these previous results in a number of ways:\n(1) It introduces a novel analysis technique that resembles potential function (or Lyapunov function) techniques used in online learning and beyond to directly analyze the regret, rather than analyzing policy convergence.\n(2) With this tool in place, for the 2-armed case, it establishes that if the constant stepsize is large compared to the size of the gap between the rewards of the two arms then the regret will be polynomial on some instances.\n(3) Also for the 2-armed case, it also establishes that for a constant stepsize that is smaller than the gap, the regret will be logarithmic.\n(4) The paper also shows that for the K-armed setting, the regret will be polynomial if the stepsize is large relative to 1/K.\n(5) Preliminary results are given for upper bounding the regret for the general K-armed setting.\n(6) Experimental results illustrate the findings (and in particular, highlight that the phenomenon exploited in the lower bound proofs are real).", "questions": "With some simplification, Theorems 1 & 2 suggest that there are two regimes for the regret.\n\nFor eta<Delta, the regret is min(Delta T,log(T)/Delta).\nFor eta>Delta, the regret is min(Delta T, T^{1- (Delta/(2eta))}).\n\nNow, if I fix some eta, compared to this there are those problems where the gap is small. This seems to be the second case above (realm of Theorem 2).\nHere, if Delta goes to zero, the minimum is always Delta T. Hence, for very small values of Delta, Theorem 2 is not relevant. \n\nSo it seems that Theorem 2 says that there is an intermediate range of values of Delta, such that regret is nontrivially large.\n\nI guess what really goes on here is that both theorems are essentially asymptotic (they only hold for T > f(1/Delta) for some increasing function f). This sorta means that Delta needs to be large anyways to use the theorems.\n\nI guess I am struggling to understand a little the implications of these results.\n\nTo formulate this as a question, what is the best way to understand what these results are telling us? Simply put, say, I use eta = 1/sqrt{T} or something like this. When should I worry about the performance of this algorithm (T is fixed)?", "limitations": "n.a.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 4, "strengths_and_weaknesses": "Strengths:\n1) New, neat analysis ideas that perhaps others can build on\n2) Nice \"characterization\" of how constant stepsize influences regret growth\n3) The paper is quite readable\n\nWeaknesses:\n1) Regret is a weaker concept than policy convergence, though I would not say this is a big problem. Yet, because the paper focuses on regret, it won't have results on policy convergence. Perhaps the price to be paid for the nice analysis\n2) Results for the K-armed case are \"unfinished\"\n\n--------\nSince there is no separate box for various miscellaneous comments, I will use this box for small comments/questions.\n\n1) How important was that the parameters are initialized at zero? (Line 79)\n2) Line 84: E_t must be standing for NOT E[.|H_t] but for E[.|H_{t-1}] from what I see.\n3) Line 107: \"fully characterize [..] except\" sounds funny at best. Consider rephrasing\n4) Displayed eqn, first line after line 134: Why is this not an equality?\n5) Line 187 Theorem 2 and proof: This feels a bit messy. The theorem should be stating something like this? \"For every eta, there exist Delta such that for all epsilon>0 and T large enough XYZ holds\". Correct? The proof sketch is also messy (though eventually what is happening is clear). Perhaps consider rephrasing these. Related to this comment, see also a question below.\n6) Line 202: \"Lemma 6)\" delete \")\".\n7) Line 247, Theorem 3: This should start with \"Fix Delta>0\"? Otherwise, can't I just use Theorem 2 to get this result by making Delta->0?\n8) The histograms reminded me of similar observations made in the UCB-Tuned paper by Audibert et al. who also observe similar bimodal regret distributions. Perhaps it would be interesting to compare/contrast to this.", "was_revised": true, "final_justification": "This paper makes an interesting contribution by changing the way policy gradient methods are analyzed. The main concern is whether the approach will be strong enough to handle the more interesting cases (eg K-armed bandits), however, I remain optimistic about that the paper will be useful for getting that done. A secondary minor concern is that the paper does not feel like a nice polished piece of work, but I trust the authors will be able to improve the paper to make it a nice contribution in the final revision.", "rebuttal": "We thank the reviewer for the detailed and thoughtful comments, as well as for highlighting the strengths of our work. Below, we respond to the specific questions and suggestions.\n\nW4. **regret vs policy convergence**\n\nWe agree that the regret perspective is complementary to the recent convergence analysis of Mei et al. (referenced as [2] by reviewer 9S4k). In that work, the authors establish that (1) SGB converges asymptotically to the optimal policy, and (2) the average suboptimality decays as $\\mathcal{O}(\\frac{\\log(T)}{T - \\tau})$ after some (random) time $\\tau$, corresponding to the moment when the policy enters (and stays in) a “nice” regime where the optimal arm is selected with high probability (Theorem 3 in their paper).\n\nOur interpretation is that proving a logarithmic regret bound essentially amounts to showing that $\\mathbb{E}[\\tau] < \\infty$, while in the polynomial regime we identify, this quantity may be infinite. Thus, our regret analysis provides a finer-grained understanding of how constant step-sizes influence the *transient* behavior of SGB, not just its asymptotic convergence.\n\n1. **initialization**\n\nInitializing the parameters at $0$ is not essential for our analysis. More generally, suppose the initial parameters are drawn from some distribution. In Theorem 1, for instance, the upper bound on the post-convergence term would simply include an additional term $\\frac{\\mathbb{E}[\\theta_{0}]}{\\eta}$. For the failure regret term, the expectation $\\mathbb{E}[x_1] = 1$ used in the bound (l. 139) would be replaced by $\\mathbb{E}\\left[\\frac{1 - p_{1}}{p_{1}}\\right]$, where $p_{1}$ depends on the distribution of the initial parameters. The other results in the paper can be adapted in a similar fashion.\n\n2. 3. 4. 6. **Typos and phrasing** \n\nThank you very much for your careful reading, we will include the corresponding corrections in the revision.\n\n5. **Theorem 2**\n\nFollowing your suggestions, we will clarify the statement of the theorem in the revision and the proof sketch. We will state the theorem as follows: \"Consider any learning rate $\\eta>0$ and minimum gap $\\Delta \\in (0,1)$. Then, if $\\eta > \\lambda_\\Delta \\coloneqq ...$, there exists a bandit instance defined by ... that for which the regret of SGB is polynomial, $R_T=\\widetilde \\Omega(...)$.\" \n\n7. **Theorem 3** \n\nYou're absolutely right, thank you for pointing out this subtlety. We will revise the statement by fixing $\\Delta$, which leads us to adjust the condition on $\\eta$ to $\\eta \\leq \\frac{\\log(1+\\Delta)}{\\Delta} \\cdot \\frac{1}{K - 1}$. This modification does not affect how we discuss or interpret the result in the rest of the paper, since the gap-dependent factor is bounded.\n\n8. **Histograms**\n\nThank you very much for pointing out this very interesting connection. We were not familiar with the paper by Audibert et al., but we did cite in appendix a recent paper by Fan & Glynn (ref. [60]) that makes a similar observation. We will add a sentence in the experimental section to highlight the connection to these works. More broadly, it appears that the bimodal distribution of regret is a feature inherent to algorithms that aim for logarithmic regret while managing a nonzero probability of failure. A similar bimodal behavior could likely be observed when running badly tuned instances of TS or UCB, e.g. for Gaussian distributions if the algorithms were tuned using underestimated variance parameters.\n\n**Question**\n\nThank you for this question. For the two-armed case, we believe that Theorem 1 and Corollary 1 offer a comprehensive guideline on how to choose $\\eta$ when using SGB in practice. In Corollary 1, we prove that a stepsize $\\eta \\leq 1/\\sqrt{T}$ yields a regret of order $\\sqrt{T}$, which provides a robust, horizon-dependent tuning of SGB.\n\nThen, Theorem 1 indicates that, if the learner has access to a bound $\\Delta$ such that the gap-dependent regret bound of Theorem 1 (essentially, $\\frac{\\log(1+4\\Delta^2T)}{2\\Delta}$) is smaller than the $\\sqrt{T}$ bound, they can opt for the gap-dependent tuning $\\eta \\approx \\Delta$, which leads to much better performance when $\\sqrt{T}$ is large compared to $\\Delta^{-1}$.\n\nSince our regret bounds are quite tight, we believe this methodology for selecting $\\eta$, guided by theoretical insights, is effective for maximizing empirical performance on finite horizons. We also expect the same approach to generalize to $K > 2$, assuming the critical learning rate is $\\eta_c = \\frac{2\\Delta}{K}$ (Conjecture 1), and that logarithmic regret scales as $\\frac{K-1}{K}\\cdot\\frac{\\log(T)}{\\eta}$ for $\\eta < \\eta_c$ (Conjecture 3, supported by experiments in Appendix G). In the revision we will also group these conjectures into a single conjecture in the main paper to help guide future research on this topic.\n\nWe will reflect this discussion in the revision by expanding the discussion following Corollary 1, building on the current final sentence of the paragraph."}, {"review_id": "oA2h6jGGfO", "reviewer": "Reviewer_ijbh", "summary": "The paper explores the Stochastic Gradient Bandit policy with a focus on the dependence of the regret on the learning rate $\\eta$. Relying on the work of Mei et al, 2023,2024, it exhibits different regret regimes depending on the positioning of $\\eta$ as compared to the reward gap $\\delta$ through a decomposition of the regret in two terms. Starting with a study of the 2-arms instance (upper bound then lower bound for larger $\\eta$), it then studies the case where $K\\geq 2$. Deepening our understanding of SGB, I believe that it is a solid theoretical contribution to the field.", "questions": "Could the authors provide a more detailed paragraph that would help to understand the (possible?) link between policy gradient algorithms for RL and SGB?\n\nIs there hope for really practical applications of SGB?", "limitations": "The paper explores a setup proposed in previous works: in that sense, it is not extremely novel.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "I appreciate the following strengths of the paper:\n- it is an interesting contribution to improve the understanding of SGB, a promising area of the bandit literature.\n- there is a **very solid** amount of theoretical work to obtain the theorems of the paper, also supported by some synthetic experiments.\n- I appreciate the fact that it starts with the 2-arms case to help the understanding before diving in the more complex theorems.\n\nOn the weaknesses side, I have the following concern:\n- the initial setup of SGB could be more clearly formulated at the beginning of the paper (even though it is mostly a matter of (re)organization).", "was_revised": true, "final_justification": "I was in favor of acceptance, which explains the score that I gave to the paper. The discussion phase with the authors and the reviewers confirmed this feeling.", "rebuttal": "We thank the reviewer for their positive and constructive feedback. We are glad that you found our theoretical contribution solid and appreciated the presentation. We address your comments and questions below.\n\n1. **Clarity of the introduction of SGB** \n\nWe agree that our introduction of SGB is a bit abrupt. We made this presentation choice because the algorithm is simple and well established in the literature (e.g., Sutton & Barto, Chapter 2.8), and we thought that providing the pseudo-code (Algorithm 1 in Appendix A.1), along with Equations (3) and (4), would suffice to understand it. To improve clarity, we will add a short derivation of the gradient in Appendix A.1 to illustrate how SGB corresponds to gradient ascent on the expected reward under a softmax parameterization, with estimated gradients. We hope this addition helps fully clarify the update rule in Equation (4).\n\n2. **Relation between SGB and policy gradient algorithms**\n\nApart from the bandit problem, policy gradient method with softmax parameterization (softmax policy gradient) is a widely used approach applied also in other settings, e.g. reinforcement learning (RL) and tabular MDPs:\n* In RL, policy gradient methods were shown to achieve effective empirical performance [1] and are successfully used in real-world applications such robotics [7] and large language models [8]. The SGB algorithm is directly comparable to using policy gradient method with softmax parameterization applied to the Markov Decision Process (MDP) with a single step, as studied more generally in [2, 3].\n* For tabular MDPs (a setting where the optimal policy is contained in the class of paramterized policies), the SGB algorithm is also comparable to the use of softmax policy gradient whose convergence has been studied in [4,5].\n\nAnother interesting point of comparison is the recent work [6], which studies softmax PG in the bandit setting (i.e. the same as the SGB algorithm in our paper), but with low-dimensional parameterization of the probability vector: $\\mathrm{softmax}(X\\theta)$, where $X\\in\\mathbb{R}^{K\\times d}$ is the feature matrix ($K$ is the number of arms, $d$ is the dimension of the feature space) and $\\theta\\in\\mathbb{R}^d$ is the low-dimensional paramterization, i.e., $d<K$.\n\n\n[1] Schulman J., Wolski F., Dhariwal P., Radford A., Klimov O., Proximal policy optimization algorithms, 2017\n\n[2] Agarwal, A., Kakade, S. M., Lee, J. D., Mahajan, G., Optimality and approximation with policy gradient methods in Markov decision processes, 2019.\n\n[3] Mei J., Xiao C., Szepesvari C., Schuurmans D., On the Global Convergence Rates of Softmax Policy Gradient Methods, 2022\n\n[4] Agarwal, A., Kakade, S. M., Lee, J. D., and Mahajan, G., On the theory of policy gradient methods: Optimality, approximation, and distribution shift, 2021.\n\n[5] Lu M., Aghai M., Raj A., Vaswani S., Towards Principled, Practical Policy Gradient for Bandits and Tabular MDPs, 2024\n\n[6] Lin M. Q., Mei J., Aghaei M., Lu M., Dai B., Agarwal A., Schuurmans D., Szepesvari C., Vaswani S., Rethinking the Global Convergence of Softmax Policy Gradient with Linear Function Approximation, 2025\n\n[7] Kober J., Bagnell J. A., Peters J., Reinforcement learning in robotics: A survey, 2013\n\n[8] Uc-Cetina V., Navarro-Guerrero N., Martin-Gonzalez A., Weber C., Wermter S., Survey on reinforcement learning for language processing, 2025\n\n\n3. **Practical relevance of SGB**\n\nWhile our focus is theoretical, we do believe that the insights from this study could have practical implications. In bandit settings, the simplicity of SGB, as a fast-to-update gradient-based policy makes it attractive, provided its limitations are well understood. Our findings can inform applications requiring quick updates and data storage constraints, such as online advertising or personalized content recommendation. The analysis characterizes conditions under which constant-step SGB can be safely used, while highlighting the risks of improper tuning. These insights could inform more robust and reliable deployments of softmax-based learning rules. Furthermore, we hope that the regret decomposition introduced in our analysis will inspire new algorithmic variants with improved empirical stability and performance."}, {"review_id": "QP9dHItpJ5", "reviewer": "Reviewer_kYCm", "summary": "The paper revisits the SGB algorithm and provides a sharp characterization of when a constant learning rate yields log regret. For two-armed bandits it establishes a threshold at which the regret transitions from logarithmic to polynomial, while for K-armed bandits it shows the step size must scale with the gap divided by K. Synthetic experiments confirm a clear phase transition that validate the theory.", "questions": "1. Could an adaptive or decaying step-size schedule dispense with explicit gap knowledge while still attaining logarithmic (or better) regret? This question is especially pertinent for large $K$, where your bounds dictate a very small constant step size.\n\n2. Does the analysis point to practical modifications, such as adding an exploration bonus (e.g., entropy regularization) or incorporating a simple variance-reduction technique, that would allow a larger step size without slipping into the polynomial-regret regime?", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "The work offers an elegant, elementary analysis that pinpoints the precise learning-rate regimes in which constant-step SGB remains efficient. A new regret decomposition isolates a “post-convergence” term that always stays logarithmic from a “failure” term that explodes if the learning rate is too large. The results are clean and tight for the two-arm case and extend to the multi-arm setting. It is an overall solid theoretical paper.", "was_revised": true, "final_justification": "The authors have addressed my questions, and I will reserve my judgment on the paper.", "rebuttal": "We thank the reviewer for their thoughtful and positive assessment of our work. We are particularly grateful for the insightful questions, which raise important directions for future research. Below we share our current intuitions regarding these points.\n\n1. **On avoiding gap-dependent tuning via adaptive or decaying step sizes**\n\nUsing a decaying or adaptive step-size schedule to bypass explicit gap-dependent tuning is a natural and appealing idea. However, it presents significant technical and conceptual challenges. Ideeed, estimating $\\Delta$ is essentially as difficult as the bandit problem itself, so it might not be possible to adapt the step size (e.g. based on empirical estimates of the gap) fast enough to preserve logarithmic regret.\n\nIn particular, the key challenge lies in controlling $\\mathbb{E}[p_{1,t}^{-1}]$ during early stages where the step size might be too large. Without this control, it is possible that the policy drifts too far from optimality, and by the time the learning rate decays, the policy is effectively \"trapped\" in a bad region, requiring a prohibitively long time to recover. This phenomenon is visible in our experiments with time-decaying learning rates (Figures 3 and 4, Appendix G.1), where a poorly tuned initial step size leads to severe regret spikes on some trajectories.\n\nOur intuition is that using an increasing step-size schedule could offer a more robust solution: one could start with a small step size (e.g., $1/\\sqrt{T}$) to avoid early failures, then gradually increase it toward a conservative estimate of the optimal learning rate (i.e. close to $\\Delta$) as information is gathered. Investigating such schedules is an interesting direction for future work.\n\n2. **On modifying the algorithm to tolerate larger step sizes**\n\n\nAs discussed in our literature review, several prior works have considered softmax-based policy gradient algorithms with modifications such as entropy regularization or variance reduction. However, to the best of our knowledge, none of these methods achieve logarithmic regret with a constant step size.\n\nWhether such modifications could simultaneously avoid gap-dependent tuning and preserve optimal logarithmic regret rates remains a fundamental open question and doesn’t directly follow from the current analysis.\n\n### _Regularization_\nEntropy regularization has been empirically observed to help with smoothing the objective function enabling policy gradient (PG) methods to escape flat regions and allowing the use of larger step-sizes [1]. Closest to the setup considered in our work is [2], which considers PG with softmax parameterized policies and adds a discounted entropy regularization w.r.t to the previous policies and proves $O(1/T^{1/2})$ convergence rate. The work of [3] introduced a more practical multi-staged algorithm based on entropy regularized PG that achieves $O(1/T^{1/3})$ convergence rate for tabular MDPs. A different line of work [4] considers stochastic cubic-regularized policy gradient that employs a 2nd order method with cubic-regularized updates and proves convergence with $O(1/T^{1/4})$ rate to a 2nd-order optimal policy .\n\n### _Variance Reduction_\n\nHaving stochastic updates with lower variance, e.g. as a result of a minibatch, is equivalent to considering an alternative problem, where we receive a reward with the same mean but decreased variance compared to the initial reward distribution. As such, since the knowledge of the second moment $s^2$ of the reward distribution can allow for more precise step-size tuning scaling as $\\Delta/s^2$ (see related discussion in Section G.4, lines 2101-2104), stochastic gradient updates with lower variance would also allow for larger step-sizes. However, the design of a practical variance-reduction SGB that achieves logarithmic regret remains an interesting open question.\n\nThe existing works can prove only polynomial convergence rate and do not achieve logarithmic regret. For example, the work of [6] develops a variance reduction method for PG that achieves provable $O(1/T^{1/2})$ convergence rate to optimal policy. Another work [5] shows convergence rate of $O(1/T^{3/5})$, i.e., an improvement of $T^{1/10}$ but with more restrictive assumptions.\n\n\n[1] Ahmed Z., Le Roux N., Norouzi M., Schuurmans D., Understanding the impact of entropy on policy optimization, 2018\n\n[2] Ding Y., Zhang J., Lee H., Lavaei J., Beyond Exact Gradients: Convergence of Stochastic Soft-Max Policy Gradient Methods with Entropy Regularization, 2024\n\n[3] Lu M., Aghai M., Raj A., Vaswani S., Towards Principled, Practical Policy Gradient for Bandits and Tabular MDPs, 2024\n\n[4] Wang P., Wang H., Zheng N., Stochastic cubic-regularized policy gradient method, 2022 \n\n[5] P. Xu, F. Gao, Q. Gu, An improved convergence analysis of stochastic variance-reduced policy gradient, 2020\n\n[6] Zhang J., Chegzhuo N., Zheng Y., Szepesvari C., Wang M., On the Convergence and Sample Eﬃciency of Variance-Reduced Policy Gradient Method, 2021"}]

Author rebuttal:

Meta-review: (a) Summary: The paper explores the stochastic gradient bandit algorithm. In two-armed case, it shows that a sharp threshold depending on the optimality gap $\Delta$ will determine whether the regret of SGD is logarithmic or polynomial. In the general $K$-armed cases, the learning rate should scale with $K$ to avoid polynomial regret. 


(b) Main reasons for decision/Pros: Novel techniques are introduced and the findings will definitely help further exploration of the popular and important SGD technique.

(c) Change during rebuttal: The author(s) provided good response to allay the concerns from reviewers, especially the concerns about Definition 2.5 and Theorem 2.6 (lower bound). Some reviewers (e.g. Reviewer 5V1N) raised the rating during rebuttal. Such explanation should be included in the camera-to-ready version.

(c) Decision: I vote for Accept (oral) as the rating is 5 from all reviewers and I do believe this work is important. The author(s) may consider to implement some discussion during rebuttal in their camera-to-ready submission.
Decision: Accept (oral)