Precise Asymptotics and Refined Regret of Variance-Aware UCB
Authors: Yingying Fan
Yuxuan Han
Jinchi Lv
Xiaocong XU
Zhengyuan Zhou
Venue: NeurIPS 2025 spotlight ()
Keywords: bandit learning; online learning; variance-aware decision making
Primary area: general_machine_learning

Abstract: In this paper, we study the behavior of the Upper Confidence Bound-Variance (UCB-V) algorithm for the Multi-Armed Bandit (MAB) problems, a variant of the canonical Upper Confidence Bound (UCB) algorithm that incorporates variance estimates into its decision-making process. More precisely, we provide an asymptotic characterization of the arm-pulling rates for UCB-V, extending recent results for the canonical UCB in Kalvit and Zeevi (2021) and Khamaru and Zhang (2024). In an interesting contrast to the canonical UCB, our analysis reveals that the behavior of UCB-V can exhibit instability, meaning that the arm-pulling rates may not always be asymptotically deterministic. Besides the asymptotic characterization, we also provide non-asymptotic bounds for the arm-pulling rates in the high probability regime, offering insights into the regret analysis. As an application of this high probability result, we establish that UCB-V can achieve a more refined regret bound, previously unknown even for more complicate and advanced variance-aware online decision-making algorithms. A matching regret lower bound is also established, demonstrating the optimality of our result.

Precise Asymptotics and Refined Regret of Variance-Aware UCB
Yingying Fan
Yuxuan Han New York University yh60610stern nyu, edu
University of Southern California fanyingy@marshall. usc. edu
Jinchi Lv
Xiaocong Xu
University of Southern California j jinchi 1wmmarshall wwwpchaallll.s.eeemmmmmmm usc.
University of Southern California xuxiaoco@marshall. esu
Zhengyuan Zhou
New York University
zzhou@stern. nyu. edu
Abstract
In this paper, we study the behavior of the Upper Confidence VarianV (UCB-V) algorithm for the Multi-Armed Bandit (MAB) problems, variant of the canonical Upper Confidence Bound (UCB) algorithm that incorporates variance estimates into its cecision-making process. More precisely, we provide asymp- totic characterization of the arm- cam-uulling rates for UCB-V V, extending recent results for the canonical UCB in [21] and (23). In interesting contrast to the canoni- cal UCB, our analysis reveals that the behavior of UCB-V can exhibit instability, meaning that the arm-pulling rates may not always be asymptotically deterministic. Besides the asymptotic characterization, we also provide non-asymptotic bounds for the arm-pulling rates in the high probability regime, offering insights into the regret analysis. As an application of this high probability result, we establish that UCB-V can achieve more refined regret bound, previously unknown even for more complicate and advanced variance-awan aware online decision-makinn algorithms. A matching regret lower bound is also established, demonstrating the optimality of our result.
Introduction
The Multi-Armed Bandit (MAB) problem is fundamental framework capturing the exploration- exploitation trade-off in sequential decision-making, Over decades, it has been rigorously studied and widely applied across fields like dynamic pricing, clinical trials, and online advertising B2 35 27
In the classic K-armed MAB problem, learner faced with K arms, each associated with an unknown reward distribution P. for E [K], supported [0, 1] with mean μı, and variance 0². At each time step E [T]. the learner selects an arm a, and observes a reward X, drawn independently from Pay- The learner's goal is to maximize the cumulative reward by striking an optimal balance between exploration (sampling less-known arms to improve estimates) and exploitation (selecting arms with high estimated rewards). This objective is commonly framed regret minimization problem, where the regret over a time horizon T defined Reg(T) Σt= (Pa- - pa.) with a' = arg maX Ma the optimal arm with the highest expected reward.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Regime
Stability
Regret Upper Bound
Regrel Lower Bound
01 0
No*
((o2VT)
(((2vT)
22(22)
Yes
02 0(01)
(((02/01) 02VT)
2((02/01) .2VT))
Table 1:
Summary of stability and regret results for UCB-V V under different Ø1, d2 regimes. "There cxists an instance such that the arm pulling rate is unstable.
The minimax-optimal regret for the K-armed bandit problems is known be (VvKT) up to logarithmic factors. This rate is achievable by several well-established algorithms, including the Upper Confidence Bound (UCB) [) Thompson Sampling [2]. and Successive Elimination [3]. among others. Beyond the regret minimization, increasing attention has been devoted to analyzing finer properties and large-7 behaviors of several typical algorithms, including the regret tail distributions [15] [6]. diffusion approximations 14 21 24, and arm-pulling rates (21 23).
Among these works, [2] and 23 introduced the concept of stability for the canonical UCB algorithm, enabling the precise characterization of arm-pulling behaviors and facilitating statistical inference for adaptively collected data, task traditionally considered challenging for the general bandit algorithms.
In more structured settings, sharper regret bounds are achievable, particularly when arm variances small. For instance, if all arms have variance (i.e., deterministic rewards). single pull of each arm is sufficient to identify the optimal one. This observation has motivated active research into developing variance-awaid algorithms, the Upper Confidence Bound-Variance (UCB-V) algorithm 3 detailed in Algorithm []
algorithms for bandit problems [ 20
28 40
41
[3]. Among these
adapts the classic UCB algorithm by incorporating variance estimates of each arm.
While regret minimization for pariance-aware algorithms has been well-studied, their precise arm- pulling behavior remains less explored. The main challenge here is that incorporating variance information introduces a new quantity, in addition to the reward gaps A. Pa- - Pa: a E [K], that influences the arm-pulling rates. In fact, the behavior of the algorithm can differ significantly depending on whether variance information is incorporated or not. In Figures and we compare the empirical arm arm-pulling rates between UCB-V and the canonical UCB in two-armed setting. Compared to the canonical UCB, its variance-aware version exhibits significantly greater fluctuations in arm-pulling numbers the reward gap changes, and its arm-pulling distribution is more heavy- tailed. This highlights the significant differences in the variance-aware setting and introduces additional challenges.
Algorithm UCB-V Algorithm
1: Input: Arm number K, time horizon T. and exploration coefficient p.
2: Pull each of the K arms once in the first K iterations.
3: for t= K + 1 to T do
4: Compute arm pulls for
up time f by Ra,t Ex 1(A, = a),a (K].
5: Compute the empirical means and variances
Xat
Σ That sE((-1]
1(a, = a]xe, 82. That sE((-1]
Σ
laa = a - Xa,1)2
6: Compute the optimistic rewards UCB(a, 1) = =xa+= +
B.tt (pllgg
V
plog't vait
for a E [K].
Vha
7: Choose arm A given by A, arg ma UCB(a,t).
8:
end for
1.1 Our Contributions
In this work, we try to close this gap by presenting precise asymptotic analysis of UCB-V. As in (21 and (23,, our main focus on the arm-pulling numbers and stability. For clarity, we concentrate on the two-armed bandit setting, specifically K = 2, in the main part of our paper, as it effectively captures the core sxploration-explotaaiiii
trade-off while allowing a precise exposition of results 31 18 22 21. The extension to the K K-armed case is discussed in Appendix B

---

(a)
(b)
Figure The distributions of #1r for UCB-V and UCB with T 50, 000 over 5000 repetitions.
(a) 01 = 02 = 1/4, A2 (b) 01 = 0, 02 = 1/4, A2 oll/ T/T. A more detailed numerical
setting is provided in Appendix H
More precisely, by providing a general concentration result, we establish both precise asymptotic characterizations and high-probability bounds for the arm-pulling numbers of UCB-V. When 0, 02 (11), our results provide a straightfowward generalization of those obtained for the canonical UCB. In contrast, when σ1 Ø2 show that, unlike UCB, the stability result may hold for UCB-V V and that it reveals phase transition phenomenon in the optimal arm arm-uulling numbers, as illustrated Figure Finally, as an application of our sharp characterization of arm-pulling rates, present refined regret result for UCB-V that is previously unknown for any other variance-aware decision- making algorithms. We summarize our contributions in more detail below (see also Table I. For notational simplicity, we assume that the optimal arm is a = 1 and denote by A A2.
Precise asy asymptotic behavior for UCB-V. For fixed values of A, 01 d2 and T, introduce pair of deterministic equations whose unique solution {" = n (A σi, 02 ]))m112 predicts the arm-pulling numbers of UCB-V. We show that for possibly 7 l'-dependent (A, 02,
Ra.T Pg for 1, WaaT
except when < d2 and p2v T ((VT)) 1 hold simultaneously; Theorem for precise statement. This phenomenon, referred to as the stability of arm-pulling numbers, formally defined in Definition Consequently, the solutions of these deterministic equations can be used to predict the behavior of UCB-V V in the large-T regime, as illustrated in Figure 2 Our results reveal several notable differences between UCB-V and the canonical UCB, analyzed in (2 and (23] due to the incorporation variance information:
When 02.02 [1),, the optimal arm will always be pulled linear number of times. af of+0? T as A - 0. This indicates that, in the small-gap regime, the UCB-V algorithm tends to allocate more pulls to the arm with higher reward variance, generalizing the result for the canonical UCB in which both arms are pulled T/2 times in the small-A regime.
with n1,7
When 0 o( UCB-V may pull the optimal arm sublinearly in the small-A regime. In contrast, the canonical UCB pulls the optimal arm linearly in T', as illustrated in Figure 2b This behavior is governed by the ratio Ar = 02 p Pogplogg1 T (VVT A). More precisely, given S
Vplog T/T and d2 = -((1),
1. When limy- Ar < 1, we have m1.//ni, 24 with ni,r = Q(T).
2. When lim Ar 1, have M1.r/ni,7 E, with ni,r = O(VT/o2).
3. When limr Ar = 1, there exists bandit instance where, for large T. P(11T
T/VloT) A P( X VT Z 1.
The above results completely characterize the behavior of 71,7 in the prescribed regime. Notably, we establish phase transition in the optimal-arm pulling times n,T, shifting from D(VT/o2) to I(T) at the critical point Ar 1. We also note that the existence of unstable instance when AT 1 highlights stark contrast between UCB-V and the

---

canonical UCB, where, for the latter, it has been shown that the behavior of 71. for any A can be asymptotically described by a deterministic sequence {ni,r} as T - oc.
High probability bounds and confidence region for arm pulling numbers. While asymptotic theory provides the precise limiting behavior of UCB-V V, has a drawback similar to those found in [21] and [23]: the convergence rate in probability is quite slow. Specifically, the probability that the uncontrolled event occurs decays at a rate of (((logT)))) This slow rate is inadequate for providing insight or guarantees in the popular high probability regime for studying bandit algorithms, where the probability of an uncontrolled event should be in the order of ( To address this gap, we demonstrate that, starting from our unified concentration result in Proposition []] one can derive non-asymptotic bounds for the arm pulling numbers in the high probability regime. Such result provides a high probability confidence region for arm pulling numbers, as illustrated in Figure 3a in Appendix D.1
Refined regret for variance-aware decision making. As application of our high probability arm-pulling bounds, we demonstrate in Theorem that the UCB-V algorithm achieves a refined regret bound of form
T
01
02
This result improves upon the best-known regre for UCB-V 4 36 and surpasses the regrets for all known variance-aware bandit algorithms [1
which are of form ((o2v TT) in the two-armed setting. Our result is the first to reveal the effect of the optimal arm's variance: When d1 o(02), the regret matches the previously known O(o2 bound, and the optimal arm's 's variance does not affect performance; as on surpasses 02, the regret decreases as increases,
40
33
9
10,
following the form O o2 VT). Simulations presented in Figure 2 confirm our theoretical predictions, demonstrating that UCB-V V exhibits improved performance in high-o; scenarios, which was previously unknown. A matching regret lower bound is established in Theorem 3 demonstrating the optimality of our result.
Notation. For any positive integer n, denote by [n] = [ : n] set (1.....n).
n). For a, E R, v b = max(a, b) and A min (,, b). For any R. a+ max (a, 0). Throughout this paper, we regard T as our fundamental large parameter. For any possibly T T-dependent quantities a = (T)) and b = b(T), we say that a o(b) or b (a) if lim a/b O. Similarly, a Ob) or b= (aa) if limm--ss saala/bl < C for some constant C. Ifa = (b)) and a = Q(b) hold simultaneously. in the special case when limy -oo a/b 1. We write
say a ((b), or a x b, and write
Z (resp. S b) to mean a 2 Cb (resp. S Cb) for some absolute constant C > 0. If either
sequence a or b is random, we say a 0p (b) if a/b 2 0 as T 20.
2 Implicit bounds for arm-pulling numbers
Additional notations.
For p and T E N4. let aa T)
Ta
Aalp:T) p plog T
A
E [K].
VologT T
Whenever there is confusion, write T. = Ta T) and A. (p; T). We also allow da and V n 11/2/ / /T. For each fixed
A₂ depend on T. For any a 0 and N+, define ((n; a 2 0, the map p(:a) a): R2 + Rxo is monotone nonincreasing in n, and its (piecewise) inverse n(;;a) IR20 + R2o is nn or) (a² V /)//²² Consequently, studying Na,T reduces to analyzing
Fa V n,,t -1/2
Pa.t = (n ).)
a E [K], (T).
Aa,t
Here the two pieces in io match the variance-driven term (a/ (n) and the boundedness-diig driven term (1/n) in Bernstein's 's inequality, the rescalings F. and A₂ place variance and gap on the same Bernstein exploration scale used by our UCB-V V bonus.
4 does not directly provide the worst-case regret bound for UCB-V, and the best known worst-case regret bound for UCB-V is claimed as O( T' in 28 In Appendix E.2 show that the
O Eoga. ofT log T') regret for UCB-V can be derived based on results in (

---

01:04
(b)
Figure (a): The regrets of UCB-V with 02 = 7-1/4 A2 x 1/vT fixed and 01 x 7 T-1/1 1, each instance with 10 repetitions. (b): The median and 30% quantile of 11, (optimal arm-pulling count) for UCB and UCB-V, under varying Ar in the 0 = 0(02) regime, with T 1, 000, 000 over 30 repetitions for each Ag. The red dotted line is the predicted R1,7 of UCB-V using (6) A more detailed numerical setting provided in Appendix H
2.1 Implicit bounds for arm-pulling numbers
Consider Algorithm D with
We start with the following concentration result for (a,T-
Proposition 1. Recall that T. Talo; T) and A. (a; for E [2]. Fix any 6 >> 0, 1,
and any positive integer T 4 such that e E6;; p; PT)) 5(
log (log (oog(//// (T/6)/8)
128 (2g(88)) 1/2
plog
plog
200 3. Then, with probability at least 8, we have
/T 2.
1-6
of ViVLT + T(PL. + 12)²
+ A2)
1
1+8
1
and
11-) l1t
12
Ite
+1,
The proof of Proposition above is inspired by the delicate analysis of bonus terms for the canonical UCB [23] in the large-7 regime and is presented in Appendix C.T Proposition [ establishes sandwich inequality, demonstrating that as term E(6; p: T)) approaches O, the concerned ratio converges to 1. This can be viewed as nom-asympooiic and variance-awar aware extension of the results found in 21 and [23] for the canonical UCB. To incorporate variance information, we have also developed a Bernstein-type non-asymptotic law of iterated logarithm result in Lemma in Appendix G which is of independent interest. We now make several comments regarding Proposition [
Deriving the asymptotic equation. When selecting ò = (log 7 - we find that for any > 0, the log log log
E(0; T') term approaches 0 at a rate of O following probability convergence guarantee
T Under this selection, Proposition yields the
ViTT + Z + A2) TWi,
+ (1.
T(PIT A2)2
It is noteworthy that in this asymptotic result, the (1(1) term converges to 0 at relatively slow rate, both in probability and magnitude. For each T, it has a probability of at least 1 - O log T of
being bounded by O log This slow rate appears not only in our result but also in [21] and
log
23]. necessitating a considerably large to observe theoretical predictions clearly in experiments, as illustrated in Figure 2b
Permissible values of p for high probability bounds. One popular scale selection of 8 = 1/T2, where Proposition becomes high-probability guarantee widely adopted in the pure-exploration and regret analysis Titerature [5 3. With such selection, the requirement e(,; p; T) 1/2 translates to c' for some universal and sufficiently large constant c'. Thus, we have that with probability at
5

---

least 1 - O(1/T9,
8 PI.T TΦi,
( + A2) $1+ (c)-1.
1 (c)
(2)
T(PLTT A2)²
In particular, since the centered term is monotone increasing function of PI,T, this result provides a broo-bbbbbbblityy confidence region for f1.r and consequently for 71,7. as shown Figure 3a in Appendix D.I] These high probability bounds of n1,7 enable us to derive the refined regret bound for UCB-V Section
The implications outlined above will be made precise in the subsequent two sections.
3
Asymptotic characterization of arm-pulling numbers
3.1 Stability of the asymptotic equation
Consider the deterministic equation
f(g) =1 with f(()) Vip 22 (p T(p + 22)²
TG² +
(3)
Recall that 0. 0a/ oa/VPlogT and D. Ap log T) for 1.2, so the equation actually depends on both and T. For any fixed T E N4 and > 1. Proposition indicates that (1.7 satisfies ((P.T) 1 C. where Ç represents a perturbation term. Given the asymptotic equation derived in ( it is reasonable to conjecture that the behavior of 11,7 aligns with the solution of the above deterministic equation. To formally connect 1I, to the solution of (3), we conduct a perturbation analysis of this equation. Specifically, we have the following result.
Lemma 1. Fix any T E N4 and > 1. It holds that:
1. The fixed-poits equation 3 admits unique solution 4-" E (1/T,1).
2. Assume that there exist some Ç (-1/2, 1/2) and upe such that f(pc)) 1
Then
PC 6ot
-1-1 1 - 27|c| (1+
02 o VVV- 1
(4)
TA2
The proof of Lemma M above is provided in Appendix D.I Intuitively. Lemma asserts that in either the homogeneous variance case (02 X σ1) or when the ratio /2/(TA,) is bounded away from the solution (Pç of the <-perturbed equation is provably bounded by (1 = O())) p" However, when
σ1 =((2) and the ratio /²// (TA2) approaches 1, the stability guarantee of the lemma breaks down.
Although this result may seem pessimistic-as / (TT,) ~ causes the right-hand side of to diverge-it accurately reflects the behavior of the perturbed solution. This is illustrated in Figure 3b
in Appendix D.I where instability arises when /./ (T (T =
3.2 Asymptotic stability
One important consequence of the perturbation bound is the following asymptotic stability result. Theorem 1. Consider Algorithm 7 with K = 2. Assume that
o3
-1
02 A o
lim T
TA
2
V- 1/2
00.
(5)
Then for a E [2], we have na,r/nan
Lg 1, where ni is the unique solution to equation
of v(
(p( + A2)
T + T(p(n),7:7,) + A2)² and n σ2 (p(ni,r::)) 1 42)/((((() 2
(6)

---

The proof of Theorem aaove is provided in Appendix D.2 relying on Proposition ! and Lemmal [ Lemma [ ssows that the boundedness condition (5) essential for ensuring the stability of the arm-pulling process, as defined in Definition [ Specifically, when
72 1, condition (5) is always satisfied, and the asymptotic equation (6) reduces to the canonical UCB setting studied in 21 and (23), where stability is guaranteed. The key insight behind such stability in an even more general homogeneous setting 01 X 02 is that the optimal arm's 's pulling number grows linearly with T, as noted in [23 Eqn. (22)]. In the inhomogeneous case where 01 o(02), the boundedness of
(T2/ -11 1 becomes crucial for stability and appears to be novel, ensuring stability even when N1,7' grows sub-linearly in T. The instability result in the next subsection complements Theorem [ by presenting a counterexample where the boundedness condition in (5) fails. An extension to the K-armed setting is discussed in Appendix B
Asymptotic behavior arm-pulling numbers. Let us write xp = ( for simplicity. From Theorem the asymptotic behavior of 11, can be derived through ni,r. which, in turn, can be fully determined by ip", provided that the boundedness condition in (5) holds. Thus, understanding the analytical properties of yp" is sufficient to determine the asymptoti behavior of R1,7.
The function l((²') is known to be monotonic increasing in s²" and the solution to f(x²') 1 lies within the interval [0. 1). This allows us to efficiently compute the numerical behavior of 40 to predict both asymptotic and finite-time arm- arm-pulling behavior, as illustrated in Figure Balin Appendix [D.] However, due to the presence a maximum operation and the complexity of the underlying equation. obtaining closed-form solution for &o remains difficult. Below, present several extreme cases that highlight new phenomena arising from the incorporation of variance information, which differs from the classical UCB algorithm. A full analytical characterization of yo is left for future research.
Example 1. When 01, 02 = 2(1), Equ.
o simplifies to
ni.r T
σ1
T
T
2
+
1.
02
02
plogT
In the moderate gap regime A2 02v Oog'o T/T for some fixed 0 R2o, we have ni
(1+) with (0) being the unique solution equation X + [i
0llp)
-2
Moreover, we can compute the limits lime (0) and limg-oo X (0) 0-
This result recovers the asymptotic equation for the canonical UCB in (27] and (23) when σi
a2 = 1. The X" equation derived here can be viewed as an extension of those in (27). Notably, in the small-gap limit 0 + the arm-pulling allocation for UCB-V becomes proportional the variance instead of being equally divided.
Example 2. When 0n S VplogT T/T,0= = =Q(1), Eqn. 6
simplisies to
ni.T T
plogT (
T
A2
T
-2
+
= 1.
T
02
plogT
In the moderate gap regime where A 02 log T/T for some fixed 0 E Rzo \ {p}, we have ni, ni,r/" [T- T..T/TT
= (0) + +1)), with X* (0) being the unique solution to equation + (2, v elag
x v0/p) 1. Moreover, can compute the limits lime (0) and lim (0)
V++2TT++
This limit indicates a distinct behavior between UCB-V and UCB: as 0 0, the number of pulls for the optimal arm becomes sub-linear in T, specifically O(VT/a>) while for UCB, approaches T/2. Additionally, we have a more detailed description of the transition between sub-linear and linear pulling times: (i) When O < P. (0) < 1/(0z(1 - /0/P)/T) and (ūi) When 0 > p. (0) 2 1 p/O. This result indicates that the transition from ((VT) pulling time Q(T)) pulling time for the optimal arm occurs at 0 =
Inference with UCB-V. Another key implication of Theorem Dis is its relevance to the post-policy inference the UCB-V algorithm. To begin, we recall the notion of arm stability as defined 23 Definition 2.1].
7

---

Definition 1. An arm a E [K] is stable if there exists deterministic sequence na,r such that
na. E 1 with ,arr + 20,
where var may depend on T, (MoJae]K). and [oa)ae[K]
This notion of stability guarantees that, as + oc, the number of times that an arm is pulled becomes predictable, thus enabling valid statistical inference for each arm's 's reward distribution. Specifically, under the stability condition, the following Zsstatistic converges in distribution to a standard normal
Ma.
(Xa,I - pa) = (),
Ja.
This result is crucial for constructing valid hypothesis tests and confidence intervals in the adaptive sampling settings [29] 39]. For space efficiency, we provide a more detailed discussion along with simulation results in Appendix
3.3 Unstable results: closer look and hard instances
Recall that Theorem establishes the stability result, except for the case when 01 = o(02) and /3/(TA3
hold simultaneously. In this section, we provide hard instance in this setting and show the instability result. More precisely, let us consider the setting similar to Example [ with T2 = 1, 01 = 0, and gap A₂ = 22 / 0 log T/T.
In this scenario, the behavior of the solution to the asymptotic equation is described by ni,r X (0)T, where (0) solves + (Vplog T/T/>+ v0/p) 1 or equivalently,
1
plogT
10lp.
-I-X A T
To heuristically explain why 0 p (or equivalently / = 1) acts as a phase transition point
and leads to instability, we formally take the first-order expansion 1/ 1/v1 - 1+ A/2 in (9) and
multiply both sides by A. This yields quadratic equation in X, ! +1 /0/p)> / log 0.
Notably, the order of the solution in T depends crucially on the sign of 1 / 0/p. For any & > 0, by observing the analytical solution to the quadratic equation, we have
O log T when 1 v0/p 2 (((=)
A
when 1 - v0lp -
In particular, a perturbation in 0 around 0 = of magnitude with different signs can lead to fluctuation in ni.r from O(E VT'log to (ETT).
Based on the above intuition and informal argument, we can rigorously demonstrate the instability result by constructing Bernoulli bandit instance and establishing a time-uniform anti-concentration result for the Bernoulli reward process via Donsker's s principle. Intuitively, our mnti-concentration result shows that, with constant probability, 0 can be perturbed by magnitude of O 2)) -1) with different signs, which then implies instability in n1.7 even when we play UCB-V with the oracle information of the variance (i.e., with o.,- = o.). We summarize the instability result in the following proposition and provide its proof in Appendix [.3]
Proposition 2. Consider the following two-armed Bernoulli bandit instance: for p == 1/2 and A y01 p)) T/T, arm has reward + A and variance and arm has reward μ and variance y(1 - μ)) Assume that o, 's are known and let na, be computed by Algorithm 7 with
G.,t = o.. Then for sufficiently large T, there exist some constants Co, Ci such that
P(NIT S SCVT log T) A P(nIT 2 2/2 T) co.
Remark In the example above we set σ1 0 for simplicity. The instability analysis Proposition also extends cases where the optimal arm has variance σ1 11/2) since in this regime the

---

UCB-V V bonus for the optimal arm matches the 0 case. By contrast, constructing an instance with σi T for some a (0, 1/2) more delicate and appears require new ideas: the associated asymptotic equation becomes substantially more involved, and a complete analysis is currently unclear.
The existence of unstable instance at Ar 1 complements previous finding, where UCB-V V's stability was shown for Ar * 1. This result highlights a contrast between the UCB-V and canonical UCB: as shown in [2 and [23], the canonical UCB stable for all A, which corresponds to the case in our setting when environment, UCB-V V may exhibit significant fluctuations. Another implication of this instability is that, unlike the canonical UCB, the CLT for the Z-statistic may not hold for data collected by UCB-V, as shown in Figure 4b in Appendix [ This necessitates the developments of new statistical inference methods for UCB-V V collected data or new variance-award decision- Decision-mmaking algorithms with stronger stability guarantees than UCB-V V, which we leave as a valuable future direction.
Ø2 1. Our result demonstrates that, in heterogeneous variance
4 Refined regret for variance-aware decision making
In this section, we show that a refined regret can be achieved by UCB-V based on our arm-pulling number bounds presented in Section 2 given by 2
Previously, the best-known regret for UCB-V, shown in 4
Reg T S max log T A220
02 22
+2) S Tog...
(11)
As mentioned earlier, the regret (II does not account for the effect of 01, which contradicts the empirical performance of UCB-V and is conservative in the large 01, small 02 regime, shown in Figure 2a On the other hand, the derived asymptotic equation for the arm-pulling times naturally indicates dependency of n2,7 on 01, opening the possibility for refined worst-case regret bounds. More precisely, by adopting the high-probability bound in (2). we can show the following proposition.
Proposition 3. There exists some universal constant Co such that with p 2 Co and 2 3,
16
(
160g
6 ))21 2 T2
P n2,T S
A2 + p(nITT))))
A2 ((
By applying the upper bound on the number of pulls for sub-optimal arms, we are able to derive the refined worst-case regret for UCB-V.
Theorem There exists some universal constant Co such that for p 2 Co and T 2 3, we have
that with probability at least 1 - 6/T²,
1602 v /p T + plooT.
RTg(T) S 16 16(02 A
01
The proof of the above results can be found in Appendix E The regret bound in Theorem 2 above improves upon the bound in (T]) for the large 01, small 02 regime, while recovering (IT) in the small ai regime. We note that sharper bounds may be derived in special instances based Proposition 3 For example, in the Bernoulli setting where μ4 is close to 1, the variance inequality o3 < of + Ag
holds. In this case, Proposition 3 implies regret bound of the form O(11/TT log T), which matches the result established (3)
Regret results for the aaaredd setting. Since most works consider the general K-armed setting, for ease of comparison we now presenting the K K-armed extension of Theorem we leave the
Ratter than presenting equation of the form II bound on the number of times suboptimal arm is pulled:
4
established the following gap-dependent upper
oo
E E(urT) < C log T
(10)
A
Au
However, it is straightforward to show II by combining
10
with the trivial bound Reg(1') A2B((22.))

---

rigorous statements in Theorem 5 in Appendix B For a K-armed MAB problem with variances {o a (assuming again W.L.O.G. arm is optimal), we have:
K
Σ o
Reg (T) = 0 =0
Σ d aE[2:K]
σ1 VTlogg]
aE(2:K]
The best known worst-case regret of UCB-V was previously known as OVVKTloo T), as discussed in (28]. In comparison, our result shows that UCB-V V can achieve regret adaptive to both the variances of sub-optimal and optimal arms. Beyond UCB-V, for Thompson sampling algorithms, the O PVVEae/2 o log regret was proved in a Bayesian setting, where each arm's reward distribution follows known prior distribution. Especially, even when working with the Bayesian regret, the dependency on is previously unrevealed. We believe that our results for UCB-V can be extended to these posterior sampling algorithms.
Now we establish a matching lower bound to show the optimality of Theorem 2 To describe the lower bound result, consider any given distributions P1 and P2- Let (P P2) denote a 2-armed bandit instance, where P; represents the distribution of the i-th arm. To emphasize the dependency on the means μM; Ex-P, P.P.P.. [X] and variances of Varx-P, [X] of the arms, we redundantly express this instance as = (P (11,01), P2(u2, 02)).
Optimality of Theorem 2
Given any instance optimal arms under v for clarity. For any policy π and any instance v. we denote E,,u and Pxv as the expectation and probability with respect to the reward distribution induced by under v. More precisely, we establish the following regret lower bounds. The proof is deferred to Appendix E.3
the notation 2 (v). (v) to denote variances of optimal and sub-
Theorem 3. Given any sufficiently large T > 0 and 0 < o² < 1/3, consider the following class of problems with o-bounded variances:
V, {(Pi P2(p,,)))))) as 02 o, (nppppP(uu,aag c 10, E (1,2)).
Then for every policy there exists some E V such that,
Exv Reg(T) ((osu(())
(12)
Moreover, the following trade-off lower bound holds: Given any 0 < B < 1/2 and eT = Oppoly(Iog T"),, consider
1/2 = ((P (1I, P2(u2, E Va : u1 > u2, 01 T 02 01 2 T /256
and the good policy class
ETO Reg(T)
S SCrVT
I good
max veV
Then for any E &Igoodd there exists some v' E V'/ such that
Em Reg(T)) = S 22ub
(v')
T
(13)
Oppt
Theorem 3 states that, in the general scenario with obounded variances, no algorithm can achieve regret better than (u) This reveals the optimality of Theorem 2 the regime where Topt (v) < (v). Furthermore, we show that in Copt > Jsub regime, any reasonably good algorithm that performs nearly optimal in worst-case over V (i.c., the algorithms lie within II Igoood
Lh VT. In particular, the regret upper bound in Theorem doxt demonstrates that UCB-V matches such trade-off lower bound in the regime where Copt > Tsu. illustrating its optimality.
cannot achieve a regret better than
Conclusion. In this paper, we provide refined analysis of the UCB-V algorithm, including precise characterization of its asymptotic arm arm-pulling behavior and bigh-probability.. non-asymptotic bounds that lead sharper and optimal regret upper bound. Several valuable future directions remain open. First, the instability result is established only under the regime 01 of /lo ) and 2(1), while the stability condition in the more general case 01 = o(02) is not yet sharply understood. Second, as discussed Section our stability condition in the K -armed setting requires a uniform-type separation condition min, A. 2 ōa Fay(K- - 1)/T, which we believe can be further refined.
10

---

Acknowledgments. This work is generously supported by NSF CCF-2312205, ONR 13983263, and 2026 New York University Center for Global Economy and Business grant.
References
[1] Shipra Agrawal and Navin Goyal. Analysis of thompson sampling for the multi-armed bandit problem. In Conference on Learning Theory, pages 39-1. JMLR Workshop and Conference Proceedings, 2012.
[2] Victor Araman and René A Caldentey. Diffusion approximations for a class of sequential experimentation problems. Management Science, (8(8):5558-5979) 2022.
[3] Jean-Yves Audibert, Rémi Munos, and Csaba Szepesvári. Tuning bandit algorithms in stochastic environments. In International Conference on Algorithmic Learning Theory, pages 150-165. Springer, 2007.
[4] Yves Audibert, Rémi Munos, and Csaba Szepesvári. ietooration-xpploiaatiionn tradeoff using variance estimates in multi-armed bandits. Theoretical Computer Science, 410(19):1876- 1902, 2009.
[5] Peter Auer. Using confidence bounds for exploitation-exxloraiion trade-offs. Journal of Machine Learning Research, 3(Nov):397-422, 2002.
[6] Patrick Billingsley. Convergence of Probability Measures. John Wiley & Sons, 2013.
[7] Haoyu Chen, Wenbin Lu, and Rui Song. Statistical inference for online decision making: In contextual bandit setting. Journal of the American Statistical Association, 1 1166533):240-255, 2021.
[8] Xi Chen, Zehua Lai, He Li, and Yichen Zhang. Online statistical inference for contextual bandits via stochastic gradient descent. arXiv preprint arXiv:2212.14883; 2022.
[9] Yan Dai, Ruosong Wang. and Simon S Du. Variance-aware sparse linear bandits. arXiv preprint arXiv:2205.33450 2022.
[10] Qiwei Di, Tao Jin, Yue Wu, Heyang Zhao. Farzad Farnoud, and Quanquan Gu. Variance-aware regret bounds for stochastic contextual dueling bandits. arXiv preprint arXiv:2310.00m 009600 2023.
[11] Maria Dimakopoulou, Zhimei Ren, and Zhengyuan Zhou. Online multi-armed bandits with adaptive inference. Advances in Neural Information Processing Systems, 14:1999-1951, 2021.
[12] Congyuan Duan, Jingyang Li, and Dong Xia. Online policy learning and inference by matrix completion. arXiv preprint arXiv::404. 1000003990. 17398, 2024.
[13] Eyal Even-Dar, Shie Mannor, Yishay Mansour, and Sridhar Mahadevan. Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. Journal of Machine Learning Research, 7(6), 2006.
[14] Lin Fan and Peter W Glynn. Diffusion approximations for thompson sampling. arXiv preprint arXiv:2105.09232. 2021.
[15] Lin Fan and Peter W Glynn. The fragility of optimized bandit algorithms. arXiv preprint arXiv:2/09.1 13595, 2021.
[16] Lin Fan and Peter W Glynn. The typical behavior of bandit algorithms. arXiv preprint 2rXiv:2210005660 2022.
[17] Louis Faury, Mare Abeille, Clément Calauzênes, and Olivier Fercoq. Improved optimistic algorithms for logistic bandits. In International Conference on Machine Learning, pages 3052-3060. PMLR, 2020.
[18] Alexander Goldenshluger and Assaf Zeevi. linear response bandit problem. Stochastic Systems, 3(1):230-261) 2013.

---

[19] Vitor Hadad, David A Hirshberg, Ruohan Zhan, Stefan Wager, and Susan Athey. Confidence intervals for policy evaluation in adaptive experiments. Proceedings of the National Academy of Sciences, 118(1))e201460211 18, 2021.
[20] Junya Honda and Akimichi Takemura. Optimality of thompson sampling for gaussian bandits depends on priors. In Artificial Intelligence and Statistics, pages 375-383, PMLR, 2014.
[21] Anand Kalvit and Assaf Zeevi. A closer look at the worst-case behavior of algorithms. Advances in Neural Information Processing Systems, 34:8807-8819, 2021.
bandit
[22] Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier. On the complexity of best-arm identification in multi-armed bandit models. Journal of Machine Learning Research, 17(1):1-
42, 2016
[23] Koulik Khamaru and Cun-Hui Zhang. Inference with the upper confidence bound algorithm. arXiv preprint arXiv:2408,04550 2024.
[24] Xu Kuang and Stefan Wager. Weak signal asymptotics for sequentially randomized experiments. Management Science, 2023.
[25] Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Ad- vances in Applied Mathematics, ((1):4222, 1985.
[26] Tor Lattimore. Refining the confidence level for optimistic bandit strategies. Journal of Machine Learning Research, 19(20):1-32, 2018.
[27] Tor Lattimore and Csaba Szepesvári. Bandit Algorithuss. Cambridge University Press, 2020.
(28) Subhojyoti Mukherjee, KP Naveen, Nandan Sudarsanam, and Balaraman Ravindran. Efficient- ucbv: An almost optimal algorithm using variance estimates. In Proceedings of the AAAI Conference Artificial Intelligence, volume 32, 2018
[29] Xinkun Nie, Xiaoying Tian, Jonathan Taylor, and James Zou. Why adaptively collected data have negative bias and how correct for In International Conference on Artificial Intelligence and Statistics, pages 1261-1269. PMLR, 2018.
[30] Hao Qin, Kwang-Sune Jun, and Chicheng Zhang. Kullback-leibler maillard sampling for multi- armed bandits with bounded rewards. Advances in Neural Information Processing Systems, 36:60514 60526,, 2023.
[31] Philippe Rigollet and Assaf Zeevi. Nonparametric bandits with covariates. COLT2010 page 54, 2010.
[32] Daniel J Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband, Zheng Wen, et al. A tutorial on thompson sampling. Foundations and Trends@ in Machine Learning, 11(1):1-96, 2018.
[33] Aadirupa Saha and Branislav Kveton. Only pay for what is uncertain: Variance-adaptiv thompson sampling. In The Twelfth International Conference on Learning Representations, 2024.
[34] David Simchi-Levi, Zeyu Zheng, and Feng Zhu. Regret distribution in stochastic bandits: Optimal trade-off between expectation and tail risk. arXiv preprint arXiv:2304.0433 2023.
[35] Aleksandrs Slivkins et al. Introduction to multi-armed bandits. Foundations and Trends@ in Machine Learning. 12(1-2):1-28) 2019.
[36] Mohammad Sadegh Talebi and Aaaaric-Ambrmm Maillard, Variance-aware regret bounds for undiscounted reinforcement learning in mdps. In Algorithmic Learning Theory, pages 770-805. PMLR, 2018
[37] Ruit Xu, Yifei Min, and Tianhao Wang. Noise-adaptive thompson sampling for linear contex- tual bandits. Advances in Neural Information Processing Systems, 36, 2024.
12

---

[38] Ruohan Zhan, Vitor Hadad, David A Hirshberg, and Susan Athey. Off-policy evaluation via adaptive weighting with data from contextual bandits. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 2125-2135, 2021.
[39] Kelly Zhang, Lucas Janson, and Susan Murphy. Inference for batched bandits. Advances in Neural Information Processing Systems, 13:9818-9822 2020.
[40] Zihan Zhang. Jiaqi Yang. Xiangyang Ji, and Simon S Du. Improved variance-aware confidence sets for linear bandits and linear mixture mdp. Advances in Neural Information Processing Systems, 34:4342-4355, 2021.
[41] Heyang Zhao, Jiafan He, Dongruo Zhou, Tong Zhang, and Quanquan Gu. Variance-deppenenn regret bounds for linear bandits and reinforcement learning: Adaptivity and computational efficiency. In The Thirty Sixth Annual Conference on Learning Theory, pages 4977-5020 PMLR, 2023.
13

---

A Additional related works
Variance-aware decision making
In the multi-armed bandit setting, leveraging the variance information to balance the exploration- exploitation trade-off was first studied by [5] and [3,4, where the UCB-V V algorithm was proposed and analyzed. Beyond the optimistic approach, [28] examined elimination-based algorithms that
utilize variance information, while (20) and [33 focused on analyzing the performance of Thompson
sampling in variance-aware contexts.
Beyond the MAB model, variance information has been utilized in contextual bandit and Markov Decision Process settings [36] 40 41 (7]. Among these works, [40] and [41] are most relevant to our study, especially regarding the linear contextual bandits. Instead of assuming that each arm has a fixed variance da. they assumed that each round t, all arms have the same variance de depending on the time-step t. In the homogeneous case - i.e. when their settings coincides with ours, and both algorithms achieve a regret of V regret. However, in the general case, the regret results are not directly comparable.
0,0g = a for some > 0
Asymptotic behavior analysis in multi-armed bandits
Our investigation into the asymptotic behaviors of UCB-V is inspired by recent advancements in the precise characterization of arm-pulling behavior [2] 23), which focused the canonical UCB algorithm. Beyond the canonical UCB algorithm, another line of research explores the asymptotic properties of bandit algorithms within the Bayesian frameworks, particularly under diffusion scaling where reward gaps scale 1/VT. Additionally, noteworthy body of work [13 16 34
24 conducts asymptotic analyses in the regime described by 25 where the reward gaps A remain constant as I' innreesess.
14
Inference with adaptively collected data
In addition to the regret minimization, there a growing amount of interest in statistical inference for the bandit problems. A significant body of research addresses the online debiasing and adaptive 12]. but our findings are more closely related to studies focused on These works aim provide valid confidence intervals for reward-related quantities based on data collected from pre-specified adaptive policies. Among them, the most relevant works are [21] and [23]. The former addresses the inference guarantee of Z-estimators collected by UCB in the two-armed setting, while the latter extends this to the K K-armed setting. In particular, these two works assert the stability of the pulling time for the optimal arm under arbitrary gap conditions A, enabling the application of the martingale Central Limit Theorem (CLTT) to obtain an asymptotically normal estimator of μ²" However, our results point out critical regime where such stability breaks down, as shown in Figure highlighting the price of utilizing variance information enhance the regret minimization performance.
inference methods [1 7 g
the post-policy inference 29
39
19 38).
B Discussions on K K-armed setting
In this section, we extend the results in Theorem I which addresses the 2-armed setting, to the general K-armed case. Recall that a, = (p; T) and A2 = Aa(p; T) for E [K]. The formal statement of the result is given in the following theorem.
Theorem 4. Consider Algorithm ]
Assume that for any a [2:
-1
T T1
lim T-0
max DE [2:K] K
T 2
-
1)
1-2
<00
(14)
Then for a E [K]. we have
Na.T 2, 1,
n
14

---

where ni, is the unique solution to equation
oh (P(Min() + Aa)
Σ
=1
(15)
T(f(ni,7i0)) + Aa)² KE(K]
and []:
a V (p((i,)))))) Aa) nar (v("),ri01)) + A.)²
When K === 2, the condition simplifies to the stability condition for the 2-armed setting as stated
in Theorem [ While instability occurs when 44 is violated in the 2-armed case (cf. Proposition 2
there is no clear reason to expect that (4) optimal for the K-armed setting. Indeed, as indicated in
the proof, the fixed-point equation (15) may remain stable if there exists some E [K] \ {1) that
satisfies the boundedness condition in (14). However, formally characterizing such an a poses
significant challenge in itself. As such, a full generalization to the K K-ameed setting is left for future work.
Asymptotic arm-pulling characterization (moderate gap, K-armed). To build intuition for (5) consider the K-armed setting with all variances {au]ae[[K] = 91(1 and gaps in the moderate-gap regime A. / (0, log T)/T with fixed O₂ 2 In this regime the variance branches of (p:))) are active, and
01/ v ""i,r + 0a/T
(("i.r:0))
01
((ni.r:0)) +
v /ii.rvplog"
Vplog T
Plugging these into 15 and multiplying both sides by plog T yields
na,
a T(oi/ "i oa 0,/T)
Σ
T( "i, Oa 0a/T)
aE [
As 02 - 0 (shrinking gaps), the normalized pulling rates converge to
naT T
o² Eje(K] of
That is. when the gaps vanish, each arm's 's asymptotic pulling rate becomes proportional to its variance, generalizing the two-armed intuition and the homogeneous- vamoogneeous-variancce case.
Besides the stability results, the probabioyyyylity bounds for n,, in the K-armed setting, as in (2).
still hold when (6) is replaced with [15). shown in Appendix C refined regret bound in the K K-armed setting.
The following corollary provides
Theorem 5. There exists some universal constant Co > 0 such that for p 2 Co and T 2 3, we have that with probability at least 3K/T2.
RTg(T)= S 16
Σ xE(2:K]
1602
WpTTogg log T + (K V
σ1
aE[2:K]
When K 2, Theorem above aligns with Theorem A comparison with previous findings is provided at the end of the previous section. Notably, in the small 0²/01 regime, the bound in Theorem 5 grows linearly with the number of arms K. We conjecture that the result Theorem is optimal up to logarithmic factors for variance-aware meceii.nnmmking... even for more complicated algorithms beyond UCB-V. Establishing the corresponding minimax lower bound is left for future work.
15

---

C Proofs for Section
For any T' N+ and d O, we define events
p; = [Xa.t -Mal Pa, Pa,. T(d:::TT) Vt aT [K]
P: = 102
=1022 - -oal S Pa,t p;); e aT [K]
where e(6: p; PT) / 48p log I log log(log(T/))/)
128 The majority of the technical analysis this paper will be done on event (6: p. ( I. it worth noting that, as shown have (6: p: n (d;; P)) 2 3K8 for any 6 < 1/2. Although
in Proposition 7 below, the statements in Section 2 are presented for the 2-armed setting, the proof this section applies to the K-armed setting well.
C.1 Proof of Proposition 1
Recall that Pa.t = ( a.). For simplicity, denote by Pa,t sp(aatt:aat/ hat//plog'/ for a E [K] and E [T]. The following lemma provides a quantified error between Pa.z and Pa,t.
Lemma 2. On event M(0; p; 7) n V(6; p; 7), we have that for any a E [K] and E (7].
le(:: P)
Paa - Pa,rl S Fa.e" V
plog? T
Proof. By the elementary inequality that IV V8l S V x y/ for any 2. 2 0, we can derive on event Mí6; p; T) V(6; ; T) that
10a Tart
60 - Ta,el
|pat Po,e v
Pa.t Vplog T(o V motl/2)
Vplog? T Maat
Vi(lnati Ta) (:
(e(d:p:T] p plog
Pa,z
S Da,t V
Vplog T( V na, 1/2)
which completes the proof.
For any 8,p 0, let (6: p; 1 Err T) + (rr(o;p;7) with Err(o; P))p (p log T). Recall that Pa,T = T..). The following proposition provides (tight) upper and lower bounds for Pa.T.
Proposition 4. Fix any T E N+ and any d, E R4 such that (+(0;p; 0. Then event p; T), we have that for any [K],
(8: P;
Th.TT
An + P1.
1. (8:p;))
nI
(16)
I_ (5;; T))
1a,T
PA,T
1 (o:p:T)
n1,T
26 23 In the proof, we write 4+ = (6; p; T") M == (M6; T), and V V6 p: T) for simplicity. For any E [K], denote by T. the last time- step such that arm was pulled.
Proof. The proof primarily follows the framework
(Step 1). In this step, we provide an upper bound for v- By the UCB rule, we have
Xa.T, + Pa,T, plog > XI,T, pI,T. plog 2 holds on event Mn that
By Lemma
4 Pa.Ta > A. + P1.T. I..
Using further NT,T, = -aaTT 1, n1,T, ML,, and A, 2 O, we can show that
4 4. p(m,, - 1;0,) > A. + p1.)) --..
16

---

As p - 1;7,) S SP.Tnar//aaa
1), we can obtain an upper bound for Pa.T
Dg + P11T
na.T
(17)
PaoTT
Ba,T
(Step 2). In this step, we provide lower bound for Pa.T Consider the last time-step such that arm was pulled. In view of the UCB rule, holds that
Xa,7; + Pa,r, ploog T S X1,2 + 91,2, plog T. By Lemma we have that on event M.V.
La, S Aa + P1,m -4- Then by Ra,Ti I na,T 1, 11177 S B1, and Ag 0, follows that
(18)
Pa, S [ + (11,TT 1;+1)) -l+;
(19)
As (0n(((1nT--- - 1;ō1) z / (nI, - 1), we can obtain a lower bound for Pa.77
L_ D. + P1,T
B1T
(20)
4
Pa,T
11.
1
Combining 17 and 20 above concludes the proof.
Proposition 5. Fix any T E N+ and any ò, p E Rt such that (d(;p;;T) n n T), we have that for any E [K].
Then on event
4 PT: (o: na.T
na.T
1/2 Fa n a.T
1 (o:
n1T
Ja
(f1,T Ta)
po:
n1,
Proof. In the proof below, let us write 1 (0; T) for simplicity. Denote by
4
na.
1-
11. -1
Eu = I. na.T - 1 & =
4 11.
Note that for any a > 0, function ((;;0): : R4 + RR, is bijective and monotone decreasing, with its inverse map given by
v(z00): : 2 o
z² E
Starting from the sandwich inequality (16). the monotonicity of yp yields that
(cm (Aa (1,T)) na,T 2 w55 ( p1))):a.)
As CT 1 1, we have
a,7' < " + 21.T)²
5 (A + 21,T)) (A. + +1.7)
<
(A, + (1,T) v
Using further the fact that (2; 0 -1 V 0² = =2 oz we arrive at
7T V < ((A, +P.T) 2
Similar, from E,1 < we can derive that
n Vo (A., (1.T) V σ.)) 3
Combining the above two bounds completes the proof.
Lemma 3. Fix any E N4 and any ö, p.p E R, such that < 4 (5: p; ():: $ and
T >>> 2K. Then on event M(8; p; T) (66;; p; T), we have that for any E [K].
of VT
plog T
11
ag
(21)
100K
17

---

Proof. In the proof below, we write I+ = =1+(0; p: p: T) for simplicity. Let us first consider the lower bound for R1,r- Suppose by contradiction that (21) does not hold and have
10vK
11/2
1,T
(TIVT) V1/4
which implies σ 11,T
-1/2
01 (1 ' T 1/4) 00 VT-1/4 Thus, it follows that
10VK
1/2 1/2 F1,7 (क) V 1 1,T
VT
On the other hand, as [ na. = T. there must exist some E [K] a + 1 such that Na.T 2 T/K. K. For such a, have by that
na.
MAT PIT
2T
RoTT PT
naT
o,T
1/2
T K
01 R..T
1/2
2T
T1 V V
1/2
10vK
2T 2
10 K VT
2
T - K MaT
VT
T
K
VT
which then leads to contradiction. The lower bound for R1, follows.
Next, prove the lower bound for Ra,T, [2 K]. Starting from bound for n1,r in the first part that
20
we have by the lower
M1, 11T
1 1/ 10
2 p log T
na.T 2 2(D. p1r))
2
p plogT
T1/4
which proves the claim.
We are now ready prove Proposition]
Proof Proposition 7 the proof below, let us write 1 (1 p; T) and Err = Err(o: p; T) for
simplicity. It follows from Propositions and 5 that event M(0; p: T) n ((5;;;
12 - - 1)(11T 1)
No,T AA (1.T) 1
na.TR1,
Ba,TRITT
V (fi, + A.)
(Ma.T - 1)
Applying the lower bounds for narr Lemma
we can further bound the right-hand side above as
8
100K
p plogT
VT
+ Err
8
-1
7(1 (1-
100K
-1
(1 2V 2rrr)²
2 Err
p T
log
VT
1 5 100KT-1/2"
where we have used VErr 2 8/ lolg T') and the elementary inequality (1 (1=)) 2) 1 y z for Va, y, 2
- 1)
Using the same argument for the left-hand side, we can show that
- 5 - 100KT-17 1/2
To,T (Ao + PI.T) Ta (11,T 20)
(1 21+r/))))
(1+2vEr))
5 100KT-1/3
Summing over a and using the fact that EeE[K] na,T T, we can obtain that
(1 5v 100KT 1/3j2
22 V (111 + Ta)
(1 + Err)*
<
21+2vErr)
T(A, + p1.T)
(1 - 5vErr - 100KT-1/2/0
as desired.
18

---

180
130
17
(b)
Figure 3: (a): The confidence region of 11,7 under different Ar, with 0, = o(02). The dotted lines represent the exact and perturbed solutions of 33. where the perturbed curves solve [(p) = 1 + // log T. The UCB-V line shows the number of arm pulls under the UCB-V algorithm with 30% quantile, with T 10s over repetitions. (b): The ratio between the perturbed solution f(() = 1 1 log I" and the exact solution f(p) 1 is shown for T = 10 10?, 10 under different Ar. can be seen that the ratio deviates from as Ar - 1 with increasing T.
D Proofs for Section 3
D.1 Proof of Lemma
Proof of Lemmal 7
(1), First, we prove the existence and uniqueness of y*. Note that f(p) is continuously monotone decreasing on (0, oo). On the other hand, as
f(1/T) 3ी VT
33 VT A2)
JiV--1
21
T T(T-1+A2)
T-1
and
f(1) of V1 v 12)
2
T(1+ - T
<1
there must exist unique 8 E (1/T, 1) such that f(x*) proving the claim.
(2). We only show the proof for the case of > O, while the case of Ç < 0 can be handled similarly. Note by the monotonicity, have yoę $ y0" Let pp//p" 1 Ç for some Ç 2 0 depending on Ç.
Our aim is to derive upper bound for
follows from 3 that at least one of the following holds:
J.v 1 2' T(p+)z
Case 2: T v (1p A2) 1
Case 1:
T(s* + A2)² 2
Case 1: [f o9 V spt, we have of of sc.. Hence, it holds that
/7 V Pcc
Vip"" oं
1- (1-1--)) 2)² (1 - 2)2
-_((pc))((())))
TØx
T(p*)z
T(
7.
25
For the case when yp" = V ,-","" we can compute that
< - of V sc
of v T(p
1
2 1
2
1
Tip
1 - 2
By combining the above results, in Case 1, can conclude that Ç < 2ç.
Case 2: Note that this case, we have
3 v 4*
< T(
(22)
TØ*
T
19

---

On the other hand, if + = =02V('²* + +Z),, we can show that 1/(Tp") 2 1 2 1/2.
Thus, it must hold that 4* = and 5g = 0. This implies that when 4 + + = J2 V (0t +
1
1
< <= f(pc) - -((0)2 2
T(p; + A2)
T(p" + A2)
1
2
Tip
For the case when 03 = 32 V (i= + A2). using 22
and the fact that pp" 2 T- 1 we can deduce that
/
of VV**
V ?2
T(p* + 22)
T(Ø*)²
which implies that -01(10" + 22) 2 (0) 1/21/ / Hence, it follows that 02
o3
<= f(pc) - (=(()))((pp)) 1(00) 2
(23)
T(pc + A2)
T(pp* + A2)2
03((0* - 9c)
( 8- + +24₂
01 VT2
1/2
2 2((0* + A2)
T(y* + A2)²
(Pr + 42)²
20
This gives the bound corresponding to /2/ (ō1 V T 112) in 4
Next, we will derive the bound that corresponds to |o (TA/ 1111 in
4
The analysis will be
further separated into two cases: (i) 1 - / 2 and (ii) 1 - 03/
< 0.
For case (i), we can show that
{ Vf
<= f(Pc) - f(-0)(()))))))))))))))))))))--
+ Tlip + A2)3
1 - T(pt)2
o7 Ø" +
J2
1/2 1
02
2
T(pa)z
T(pp + 22)
T(pp* + A2)3
TA
2
For case (ii), let us recall from 23 that
4-¹
52 2(
1
12/p''2
+
'2/0002
1
(24)
Σ2)
6
2(1²* + A2)
Note that when 42/4²* 2 (or equivalently 40/ A0/A2 <1/2),
22
2
1 1-
3
2
2
1
1
3
0.
T(p** + A₂)
TA
A
TA
10*
TA
2
Using the condition that 1- 02//(T7))
2
<
0, we can derive that
(4')-
30
- 1)
TA
TA
As 0// + +A2)2 < T and 40" / < 1/2, we can obtain that /2/ S 9/4, which then entails
that -2 S 27/ 27/(252 (TA,) - 2). Consequently, it holds that
5-5
1 22/00>2
A2/00>2
2(12* + A2)
2 + 27
33 -1)
T32
Plugging this back to
24 yields that
2
33
6+ 27
T
By combining the above results, in Case 2, we can conclude that
E 27c (1
O2
T
11/ 1/2
The claim then follows by combining the estimates in Cases and 2 above.
20

---

D.2 Proof of Theorem
Proposition 6. For any positive sequences (ortr2ı, frrir2i and (ārirzi the following are equivalent:
1. limy- (
2. limr WT/ DT/ =
Proof. (1) - (2). First, noticing that by the elementary inequality,
aVe
1 b bvc SVV b' ba,b,c>0 0,
(25)
we can deduce from (I) that limy -o
(p(nT: -
Ør) v (p(r vof) 1. Using further the
identity n (a² V (p(m; ()m= σ) for any n. > 0, we have
x (
(
Jim g(urioT) Vo = pp V o
lim T-000 1T
Jim
x2 (NT:oT))
T-000
(2) + (I). In light of Consequently, holds that
25 we see that (2) implies limi V nr 1/22 ) V nt nT = 1.
lim p(nrooT) 7-000 ((TT;OT))
Pr
OT V nT 1/2
lim 7
lim T-
=1
nr
OT V RT
1/2
The claim follows.
We now ready prove Theorem 1
Proof of Theorem 1 Let us select ō = 1/logT. In the proof, we will write 1 = (6; p; T), M M( p: T), and V (8 T) for simplicity. We also write 4- ;(ni,n;01)) From Proposition 7 have P(MN V) 2 1 3K/ log T.
The uniqueness of 11,,, follows directly from Lemma 1) and the fact that (() is bijective. follows from Propositions 4 and 5 that event M V.
12 I
(Ma.T - 1)(mr-1))
BaTT A + (1,T) Ta V (f1, Aa)
1
Ba,T 1 (m
S
Applying Lemma and using the facts that 11, o(1) on M n V and I2 o(1), we can show that for any E [K], lom Na,T = too on M n V. Hence, the inequality in the above display implies that for any a E [K].
(PLT A.)
na,T J2 (PLr + A.)
= 1 0p()).
(26)
Using further Eee[K] Na,T 1, we can arrive at
V Aa) T(PII + A.)²
+ (1().
(27)
[E|K]
Let us consider the case when K 2. By resorting to Lemma 2)) we have that P1rl/ =
1 + (p((),, which together with Proposition 6 implies that m1.T/ mt.T/ni. /ni./ 0P(1).
For arm 2, with (66) at hand, by Proposition 6 suffices to show that
o3 V (s* + A2) (f1.T + A2)
P1, = 11 1 6
= 1 (p(1),
o2 (f1, + A2) (p* + A2)²
which is straightforward by 25
21

---

D.3 Proof of Proposition 2
We need the following lemma to prove Proposition 2
Lemma 4. Consider the Two-armed Bernoulli Bandit instance in Proposition Recall that T2 is the last time that arm was pulled. Then for sufficiently large T, there exists some constant Co > 0 such that
P B(u= =u==820 (2.n
1
1) T2,T
1
2 2
^P c
X2.1
<
Co-
2
Tii,TT
Proof. (Step 1). We first prove the following: On event Mr n Vr, there exists some constant <<c< such that
T2,TAAT 2 CT.
(28)
To this end, recalling from (18 that
2 n22.3
2VT
71777
holds on event M(1/ Io: p; T)) n /1/ log T'; p; 7) 11, 1, we can deduce that for sufficiently large T,
and using Lemma with the fact that 7,
T2T
ZT.
71,T1
Given that n2,7, = 122,7 - 1, a similar estimate applies to 12,T, we start from 28
19 which proves
(Step22 2). Let be the constant in (28) It follows from Step and Lemma 8 that for any 0. there exists some To = (e) > 0 such that for T 2 To. P(n2.T, 2 cf') 2 1 e. Using Lemma and
choosing Camti/ /2, can obtain that
F(U) 2 PP
1
n (12.7 [[T]))
2
72,T
P
Σ iE(n)
X
for
for all 2 Leri n (n2, 2 [cT]]
Canti
Canti
2
This concludes the proof for the probability estimate for U. The estimate for P(() follows a similar argument, will be omitted here avoid repetitive details.
We are now ready to prove Proposition
Proof of Proposition (1). We will first prove the upper bound for niT event U n M(1/ log'2 T; p; (11/ lo p; P)). Consider time Ti that arm was last pulled. Using (i) the definition of u and (ii) the UCB rule, can show that on event U n M(1 log p; /11 log T; p; T),
(1) + P2. plogT S X2.1 + P2, plog T
(ii S
plogT
# +
p +
+
R1,T
Rearranging the terms, holds on event 11 7 7M1(1 log p: T)
log that
plog T
22,7; plog T A
n2,2
71.7
By the facts that of u(1 n). A μ(l p)plog T/T, n2,7 n2m 11,77 71,7; and
01 + n22r = T, we can arrive at
(1+
02
R1,T
pozlog
VT
n1.
VT
22

---

Further using 1/v V n17 2 (1 + R1. (2T))/ the above inequality becomes
11,T (1+ 1+ pTz2log T
1
12 2T
1
02
po T VT
Note that the above inequality is quadratic, then solve it to obtain that
(B - A)2 + 4A(B + 1) (B A)
RI,T S
24
where for sufficiently large T,
02
A 1
pTzlog T
2T3/2
ToTlogT
02
1
B pō
VT
VTog
Thus, we can conclude on event n (MLLMMML////// log p: T) n (LL T
T; p; that
2(B 1
2(B +1)
VT
MLT (B- + 4A(B + 1)+ (B A)
A
(2). The lower bound for 7 1,7 on event M log T; p; T) (L1) To T) can be established using similar strategy. Let us consider time T2 that arm 2 was last pulled. Using (i) the definition of L and (ii) the UCB rule, we have that on event L n M(1 log T; p; T) n ((1 log T; PT
p;
plog T
11
P2,7T
plogT X2,T, + P2,7% plog T
2 M + +
/22,T2
11,77
Rearranging the terms yields that on event C n M(1 log T: p: 7) V(1 log T),
1
plogT T
P2, plog A
12,T2 n1,72
It follows from the facts that 2² = F2/TT, R1, 2 R1,T2, n2,T n2 - 1, and n1, + n22T = T
that
(1
02
02
R1.T
po log T
V T n1,T
VT
Observe that on event >n M(L/logT; TT n (1/ log T; T) ). it holds that e₁ T S +
o2T' for some constants C₁ and 02 1, cf. Lemme and 28 sufficiently large T,
Then we can derive that for
(1-
02 VT
2n1.T
32
1+
S
(29)
71,7
2 log T
(1-o2)
(1 - o2)T
where we have also used
1/ 1//1= (NI,T + 11/T S 1 + 2 (11 - -o)] Therefore, with
27
1
A =
1-
(30)
02)
T//2
poz 1o2log7 T
ToTloT
T2
1
B
(31)
pT log
VT
V
we can solve the inequality
29
obtain that
B +
B +
4A
B
T
nT.
2A
2A
Vlog T
The claim now follows from Lemma 4
23

---

E Proofs for Section 4
We would like to emphasize that, although the statements in Section 4 are presented for the 2-armed setting, the proof in this section applies to the K K-armed setting as well.
E.1
Proof of Proposition
We will work on the following events
At E M(p:T) |8a. -Mal S Pa.t logT,
Va [
- (Tp = 10a2 - oal S Pa. l LogT, At (T e [K]
The following lemma provides probability estimate for event My Vr when p large. Lemma 5, There exists some universal constant Co > 0 such that for p 2 Co and T 2 3,
P (M 2 21-3K? -K/TT
Proof. By selecting 8 1/72² in equations (52) and (3), we achieve the desired result, provided that p 2 Co with Co sufficiently large to satisfy /96Co + 256 - Co/4.
Proof of Proposition First, view of the proof for Lemma holds that on event Mr n Vr,
Pa,, Pa,1 S Pa.t22 Ya [K], 5
At time-step Ta, by the UCB rule of XaTT + Pa,t. plog T 2 X1,, + P1.r. p plog T. we have that on event My n VT.
plog T
2 P..... plog T 2 A. + pP..T plog T plog T
PPATT 4
P1, lo
4
Dividing plog on both sides and rearranging inequality, we can deduce that
A. + F1.T
An + P1,T Da,7
8 2
PaTTa
Pa.
Ba.
which then implies either narr < 1 or Pa.
Do + (,,r)) Therefore, we have
16
1602
na.T
V
A  41,T
Ag + 11,T
The claim now follows from Lemma
E.2 Proof of Theorem
2
Proof of Theorem Observe that
Reg(T) Σ na,T Aa + Σ na,T Aa
aeA1
aEAA
with A₁ = {a E [2: K] 1672 > A. + 31.T and A2 = [2: K] Ar. It follows from Proposition
that
16
1602
})
4
P E
12, <
Ag (((),T;)))
Ag + +(m,,,;;;
72'
Then for the summation on A2, we can derive on event Ey that
A
Σ Da < Σ
$ SKK - plooT.
(32)
PIr + A
aeAp
24

---

For the summation on A1, we have that, on one hand,
Σ REAA
na. Aa 1
Σ
na.
Σ
n A
aEA1
aeA:
(33)
$ 16VT.
A3 16 16
Σ
logT,
Do + P1TT)
aEA1
aeA1
and the other hand,
2560 A
2560 A a Pi,
Σ
Da 1
A + (1,T)
aEA1
aEAr
dEAr
(34)
o2
0
256
plog T
256
Σ
pf
log T.
oi
D
01
aEA1
aEA11
Combining
32
34
above concludes the proof.
Remark Using the high-probability arm-pulling bound from 4
Na.T S
A D
inequalities 32 and 33 remain valid when the definitions of Ai and A replaced with
A (a [2: K] o 2 and A22 [2: K] Ai,
respectively. This adjustment leads to regret bound of O 01 /Eofs ooT log T").
E.3
Lower bound proof's
In this section, we prove Theorem For clarity, we first present the proof for the Gaussian case in Section E.3. then extend the construction of reward distributions to the bounded support setting in Section E.3.2
E.3.1 Proof with Gaussian bandit instances
For simplicity, we present the proof with Gaussian bandit instances first and then generalize to the hard instances constructed over bounded reward distributions.
Theorem 6. Consider the following two classes of problems with any B > 0:
V/8 = (N)(,,, (1,, M2 IR 01.0 R20),
02)) E V > 12. 01 = T 22 2 7-9 9/566
Then for every policy there exists some V such that
Exp Reg(T) = (( (v)VTT
(35)
Moreover, the following trade-off lower bound holds: Given any er (poly(log 7)), consider the good policy class
E Reg(T)
I <CrVT
I1 Igoood
max wEV
Tsub (v)
then for any π Iggood there exists some o' such that
22 (2) Tppt (2))
T
E Reg(T) 22
(36)
CT
25

---

Proof. We consider the proof of (35) first. Let A will be determined later. We consider the following two instances:
[0, and 02 2 01, where the specific values
F1 = (N(...))
V2 oN(A.of).
Fix a policy и. Recall the divergence decomposition Lemma for the reward distributions Prn. PRuz (see e.g. Lemma 15.1 of (27)) have by our construction,
[L mmn (P = Emen (#1.T JKL(N(A..3)IIIIIA...
+ Env,
(L, oz))
E (#2,7 (L,
S 2T<2/00
(37)
Here, Puni denotes the distribution of jth arm instance v. Moreover, for instance V1, we have Eng, Reg(T) = A Emn n2.2 2 ATP mvs (N2.r 2 T/2)/2 and for instance V2, we have Eng, Reg(T) = A Eng, n1,7 2 ATFrR (N2,7 < <//2)/2. Combining the above estimates and applying Bretagnolle- Huber inequality,
obtain that
AT
Exv, (Tg(T") + Ess, Reg(T) 2 exp(-2221² /o3))
(38)
4
Taking A /T2 we arrive at the lower bound
02VT
ETe, Reg(T) Exe, Reg(T)
4v2e
This implies that either
T
sub (VI)VT
T2
0IVT
Subb (sub(12) VT
Eny, Reg(T)
Eny, Reg(T)
8
8 8
8v2e
8/2e
8v 2e
hold, which completes the proof of (35
Next, prove the trade-off lower bound in (36.. With slight abuse of notations, we construct the following instances: with d1 (T-9/256, 1] and A 160/r/
V1 (V(A..)).
12 (N(A, N(2A
We would like to argue that for any II good.
(u1)( 1
1/2-8
Emnny Reg( (T)
(39)
2560 (1)
CT
256cT
We will prove this claim by contradiction. Suppose
33 does not hold, we may derive that
T1-3
Exp, (12TT) = Emn
<
409601
Therefore, similar to (37). we can obtain refined upper bound for KL re, |PP,)) (instead of using the trivial upper bound N2, I T),
TI-B
1024
(L Pm [Pm)) I
40960,
T1-3
4'
Then we may proceed as
38
derive
Emg, Reg(T) + Exe, Reg(T) 2 40 401e-1/4 1/4 CTV 3010TVT.
By the upper bound of B,n, Reg(T) (hypothesis), we have
Eayy Reg(T) 2 33 VT EuT,y Reg(T)
1/22-8
TI
2 3
30
2ero VT > 2cr (V2)
256eT
CT
which implies that good a contradiction. This proves the trade-off lower bound in (36).
and therefore completes the proof of
26

---

E.3.2 Remark on Lower Bound over Bounded Distributions
In the proof of Theorem 6 we used the Gaussian distribution for notational convenience, owing to its analytical KL divergence bound. However, the upper bound result derived for bounded bandit instances, which leads to slight mismatch between the lower bound and upper bound environments. In this section, we show that the proof can be readily generalized to the hard instances constructed over bounded reward distributions.
Here we specify two-point supported variable based construction: Given any positive μ. o², we consider distributions Qu.o supported over {0, k²+o"
with
o² Qu.
( 022
122
Qu, (0) 112 02
1
1 0²
It can be seen that Ex Rx~Qu.. [X] μ and Varx Varx~Qu.
(X)=
Suppose, in addition, that μ and let Qaa denote A-modification of Qu,o for any 0 < A
# +o 2p, defined
"
112 + +
(μ + A)
Q (0)
QA
( + A)
72
1
(μ A)2 + 7
where ō 2 0 the solution
(p + A) +02 112 02
(40)
# A
1
Since m(a) (M+A)++ an increasing function in a and p- A
m(o)= 122 0²
lim m(a);
4+0000
follows that ō is well-defined and satisfies Ø > a.
Then we may compute the KL-divergence between Quo and Q as follows:
1
log
R t
log
1 40
112
G2
(n+ (u+A)²
122 o2
((+A))+77)
(J4 A 14+A)+00
40
1
11
0²
11 A
log
+
log
112 + 02
1 + A
112 + 02
0
d
|1 + A
log
log
log
n2 02
P + A
n12 + 02
1
0² 112
A
log
+
log
n o
1
0² 1
n A
2 log
1
where in the last step, we have used the fact that log(o² //2) S.. Taking / 2 A in the last inequality and using the elementary inequality log(1 + x) S x then leads to
2 < a(a -(a-A) A) 122 +
242
II -
Now we can summarize the above construction and calculation into the following lemma:
Lemma 6. Given any μl a > 0, there exists a distribution Qu.o supported on {0, =²+0²
} with
8
Ex~Qu. [ u,
Varx [X] = o?
27

---

Given any A > 0 and suppose that
a>Z2a-A, 20220-A,<04 1 +02
2u, A A
(41)
holds simultaneously. Then exists A-modification Q of Qua supported on {0, 12+0² such that
4
[X] 11+ (1+ nA), KL(QpollQp.)) Ex-oa [X]= = A, Varx=qa Rad
r²
In particular, for any O, with the selection 0 < A S 0/2 A, one can verify that (n, o, A) satisfies the condition (41) and the corresponding Qu,,r Qp.o are supported inside 3o] with variances lies in [o², 3
Based on Lemma 6 we now explain how to modify the distribution class constructed for proving 35 and (36 separately.
Proof of 112
The proof follows the same as that of 33 we highlight the differences below. Given
any 01, satisfying 2 σi 2 2A, we consider the following two instances:
V1 (Qm--1/2. A/2.0 Qos-
(Qm.-A/2.0 Qo.-
Note that with such selection, Lemma 6 eenuures that the distributions of the second arm's reward in both instances supported over [0, 30] with their variances lied in [02, 302). For the first arm, have its variance is given by of and its support is bounded by
(02 2/2) + oo I < 302
80
02 A/2
302
thus selecting d2 1/3 ensures that the constructed reward distributions supported over [0. 1].
Next, we can proceed the same analysis as section E.3. with the proof of 35p. The only difference is that the bound in 37 under our new construction turns to
KL ma P PTn))) =
Emn, (L2.r))L(Q0 - 4TA2 /02
and therefore,
38 becomes to
AT ET Reg(T)) Eus, Reg(T) N exp(
Taking A 02 (as T 2 2, must have that A (2/2), arrive at the lower bound
T2VT
Exe, Reg(T) V ETU, Reg (T) 2
4v
This implics that either
T2VT
suub (VI) Emp, Reg(T)
02VT
0IVT
(sbb(12)
Emg, Reg(T)
8/2c
8/2e
8/2e
8v2e
8//e
hold, which completes the proof of 12
Proof of 13 The proof follows the same as that (3 ; we highlight the differences below. For
any fixed 0 < 3 < 1/2 and 01 2 T 2-T8/2260 A = 16 / VT. and 02 = V we set
Qo. 00,-0/2,01 Qay-sao)) 12 (Qo,- Q0.-A/2.0 Q -202 -22-
In particular, notice that
T1/2-B
oz/2 A + T 2 5120f0r / VT + σ, 512cr
28

---

which always holds under our selection for sufficiently large T. Thus the KL divergence upper bound between A.r and Qa in Lemma still holds under our construction. Now applying the same argument in Section F.3.1 we can arrive at
Exp, (Tg Eng, (Tg 2 401e KL(Pne (P CT VT,
VI E Igoood
when suppose contradiction that
Eng, Reg(T) < Lablui (v1) T2/2 256 (v1)
71/2-8
VT E gloood.
(42)
cr
256eT
Now by Lemma 6 we have
7
5120fct
1
KL Rm ( [
10960.07
Toz
8"
Which then, together with implies
0IVT CT
Exg, (Tg(T) 40 1/8 CTVT Emnn Reg(T) 30 VT
2 22ro1 sub (V2))V
which implies that gloood contradiction. This disproves 422 and therefore completes the proof of the trade-off lower bound in [3)
F
Proofs for Section B
With slight abuse of notation, we define function f(x) for any E R20
0² v T.))
f(z) = Σ
T( + A.)
d[[K]
Let us consider the following fxed-point equation in yp
( Aa) T(p A.)
f(() = Σ
=1
(43)
[E[K]
The following lemma extends Lemma to the K-armed setting.
Lemma 7, It holds that:
1. The fixed-point equation 43 admits unique solution D* (1/T, for all T e N+.
2. Assume that there exist some 8 (-1/2,1/1) 1/2) and ys such that f((os)
Then there
exists some constant c(K) > 0 such that
88 10*
1
< cl0
max K
1+
K -1
TA
22
2
A
TA
σ²
-1 -1
T 5 V T 1/2
(44)
Proof. The proof is almost the same as that of Lemma convenience of readers.
We include the proof here for the
(1). First we prove the existence and uniqueness of s. Note that f(() is continuously monotone decreasing on (0, oo). On the other hand,
of VT
(T-
V- T-1-1 21
S(/T))
T-1
T(T-++A.)
29

---

and
VL+
K 1 T 1
1(1
Σ [E[K]
T(I + A.)2
there must exist unique 1p* E (L/T, 1) such that f(ø*) = proving the claim.
(2). We only show the proof for the case of > 0, while the case of 8 < 0 can be handled similarly. It follows from the monotonicity that 4p8 k Let pp//p" = 1 ô for some ò ö(0) z 0. Our aim is to derive an upper bound for d.
It follows from
43 that at least one of the following holds:
V' 1 T(p+)2 K'
32 V (0* +Da) Case 2: 3a [K] (1).
Case 1:
T(p + Aa)² K"
Case 1: 1 V 40, we have 37 = गी V (ps. Then it holds that
6 - f((0)) 2
of VP8 48 oी V = of T(ppt)2 (1 - 5)2
(11
(1 (1
(1-)2
8),2
2
1
5.
T T(p*)²
K"
For the case when y0" = V 4", we can compute that
8 f(p() - f((²)) N V
of V TØž T(p
1 T&at
1
2
1 1
8.
K
By combining the above results, in Case 1, we can conclude that ō < K6.
Case 2: Note that in this case, we have
V oi
S o Vip K-1
T S Tipt T(
T( S
(45)
K
This implies that when 40* + +T, 02 v (1p" + +aa).
1
1 T(yp + Ao)
8 f(ps) s(0²) N T((1 8)4p* + +aa)
0xp
T(pp" + Aa)((1 8))0* + Aa)
8T
8
2 T(p" + + + +aa) 2 K(K- - 1)
For the case when =²== = v (x* + An), using 45 and the fact that
4- > T leads to
1 1
1 oी V
T(pp +
K
k-
T(
K-1 T2
which entails that 40/ 1(x" + Aa)
N (1 1/2
(T K I). Hence, we have that
0²
0² T(pp + Aa)²
6 = f(16)) - -(())) 2
(46)
T(pps Aa)²
(P8 + 40¹ + 23aa
7 V 112
8.
T(y* + Aa)2
(4xx + )2
Klyp* + An)
K K - 10
This gives the bound that corresponds to 7 / V VT-11/2) in (44).
Next, we will derive the bound corresponding to ( ) and (1/ (1((K-1)=8?((AA))) 2)
in (44). The analysis will be further separated into two cases: (i) (/) -)A, 2 and
(ii 1 11--8 / (TA) < 0.
30

---

For case (i), notice that
3 V 40" )(
Jh (0" + +aa)
= =1
T(p* + A,)
a22
32 V (0t + An) T(p* + +a)²
2 1 (K - 1) max a²?
Let a, = arg max 222 To V (x* + (T)) + Ta)²).
Then we can show that
VV* T(
0
2 (K 1)) K-1
TA T
Thus, we can arrive at
5
V T(
8 = ((p6) - 1(0*) 2 1- d
2 (K-1) -1).
.
K
TA
th.
T
For case (ii), let us recall from 46) that
8
0-8
8 2 2(pp" + An)
13
52 +
13, 1./02222
(47)
3K
2(1p"
Da)
Observe that when A-/ > 2 (or equivalently y0* /An <//2),
72
π²
4"
72
1
3
2
1 -
3
7
-
1
S 0.
T( + x2)
TA
Da TA
TA
Using the condition that 1
/2/(TT
we can deduce that
3
T2
-1)
(1²))-13
TA
TA
As 1500/10 + Aa)² T and 40" Aa < 1/2, we can obtain that /2 (TAA)) S $9/4, which then leads
to -00))-A, < 225 (TT) - 2). Hence, it follows that
6"8 8
A2/0'>2
1 1./00022
2(pp* + Aa)
2 27
TA
Plugging this back to yields that
8
8
3K + 27
82
T
By combining the above results, in Case 2, we can conclude that
8 < (3K + 27)8 max {1 +
1 K
F T 1/2
^
aE(K]
TA
+
TA
The claim then follows by combining the estimates in Cases and 2 above.
Proof of Theorem 4 The proof of Theorem 4 cclosely mirrors that of Theorem and we spell out some of the details for the convenience of readers. We start by noticing that most of the derivations in Section D.2 hold for the K-armed setting. Specifically, from (27 we have that
V Ka) T(PI,+ A.)
=
(48)
# K
Combining (48) above with the stability result in Lemma 7 concludes the proof.
Proof of Theorem 5 See the proof of Theorem in Section E.2
31

---

G Auxiliary results
Lemma 8. Assume that X1, ...... are i..dd bounded random variables in [-1,1] with zero mean and variance o², Let Xt = Ee(()) Xz/t be the empirical mean. Then have that for any ó < 1/2,
12 log (T/()
64 Gogg(11/0)
PP |xx < <o/
LA (IST) 2 2
Proof. As in previous works, our proof relies on constructing supermartingale and applying Doob's inequality. Let Fe be the filtration generated by Xi,..., Xx, and S; = Exe(a) X,. For any E [0, 1].
Elexp(nS.)(=--I) = ((exx
I exp(nS:-1) (1 + ) & +
(49)
Here, in the first inequality above, we have used the fact that Ef(ex(nnX.)) + 17202: see, e.g. 17 Lemma 7].
With 7/ = (1 and 1): [0, 1] to be determined, let define
1, E exp (n.S - bn) i 1.
if 0,
(50)
Then in light of 449. it holds that
E
Z Fel = Σ (Elexp (n,S++1 - -tnt tnT²0²) [i] expl (pp(-n/o02)
7t exp (n.S - tn]o²) Z.,
implying that {2o is sequence of supermartingale. Note that by invoking a similar argument as in [23 Proof of Lemma 5.1].
{2: 2 1/0}
max ti exp (n:S: tnio > 1/0}
{ Xe 2 min
| log( 1
1
+ no? }
lm
87%
For any fixed d > 0, set
2 1/2 1/200-1
"log"
1/2 (+(+1)
if 2 in
1,
if i < in
where i, inf Zz1 2 o (log ((t + 1)) + log(1/5)) holds for v i).
Given these parameters, the analysis is further divided into two cases: 0a 1/VT and 0a < VT.
Case 1: For a 1/VT, it holds that
{4. 1/0) = 8, min
1 log(
) +
1
)
Imp
8rys
(V
2
log 1/2 (((+1)
X,
min 22
2/2
For those satisfying [log2 { 2 i1, we can choose
[log2 1) to obtain
log 1/2 2(log 4x)2 à
(2, 2 1/6} 5
X, 2 40
/1/2
32

---

For those t satisfying log, t < 11 1, it follows from the definition of i that t < 2 and 2 2 2
(log(éi
1)) + log 1/6)). Hence, we can deduce that
log ((++1)
1 V 2
2
min 24
+
t
11/2
2
log 1/2 (1(++11)
v2
(51)
1/2
log 1/2
(1(+t))
log 1/2 (1((+))
5
2 2lg 1)) 2 1og(1/8)
//2
t
Below we will derive an upper bound for it Let us consider functions f(x) = 2 and g(x) o a- log((((( + 1)) + (16). It is easy to show that
2x +1
2T
f (x) = 2" log 2 > 2
g(xx)
g2a(1 +1)
Then we have f'(x) > g' (a) as long as log(2I") + 1. On the other hand, for zo = 1log(1/0)
4 loog T follows from - I' that
f(xo) /() 2T (og(5log(2TT8)) log(1/6) > g(zu),
which entails that fxx) > g(x) holds for all
Thus, we have i S 4 ( (T/5) + 1.
Combining this upper bound of with 51. can obtain that
12e 2 1/83 = { 8. of
12 1og log(T/5)
64 log (11((11)))
Case 2: For a < 1/VT, we can deduce that
1
1
(2, 2 1/0} 5
X, 2 min
log(
1102
Ipps
87
1
1
X, 2
min i<h
log(
) + ?1oo
tmp
8%
log( (10) + log 2
3 log 1/0)
X
Xx
The claim follows.
As a corollary Lemma 8 we have the following results on the concentration of the empirical mean and variance: for any 8 2 0. let
lTg(T/5)
e(8:T) V 48p log T log 6
+ 128 (og(1/8).
Proposition 7. For all 1/2 and
[K], it holds that
P [xat MMal < fatt e(5;T)/2, vI sstss 21 21-6.
(52)
P 100, 03l < Pa. e(o;T), v1 < <IST)
> 1- 28.
(53)
Proof. The claim in (2) follows from direct application of Lemma 8 with the following simplifica- tion for the error bound therein
12 log (Tg()
64 log(1/)) < (Ta ni -1/2) e(d:T) e(6;T) /
Jal
Pa,t 2 Taa
Nh.11
Tha
33

---

To prove b3). we first notice that by Ia
-xa,ll 1,
[o oal =
1
Σ
((Xa, - -20) - (Ua Xo,1)²
Batt
sE(mule
(Xa,s Ma)
02 + Ma Ka,t
na, sEfma.r]
Then we can bound the second term above using 152p The first term above can be analyzed by the same argument in proving (52). upon noting that Var (Xa,e pma)² - I (B((Xo, Ma)*) o²
This concludes the proof.
Lemma Assume that {xili21 No 24 and constant Canti = Cani
1.i.d. Bernoull(1122) and fix any с > Then there exist some
(c)
> O such that for all N 2 No.
n + Vn, V[N/c] In Sns SNN N) 2
Cantis
(54)
2
X4
<
n
vū, V[N/C] Sn SnS 2 Canii
(55)
Proof. Our proof relies on Donsker's Theorem, which states the convergence (in distribution) of the random walk to the continuous time Brownian motion; see, e.g., [6] Section 14]. More precisely, for
f.ddd (Xih21 ~ Bernoulli(1/22) Donsker's Theorem states that for
Nt 2
(t) = VN
Σ
kE(LNe]]
it holds uniformly in t 1] that lim -oo (t) B(t), where Btt) represents the standard
Brownian motion. Equivalently, for any 5 > O, there exists some No E Z4 such that for all N 2 No.
sup P inf V x 2 P
inf B(I) 2 x rEfo.11
SE.
æER
[E[O,a]
Using the fact that inf [N/4 2( SEEn X; n/2)/vN infre(1/G.11 (t),), can deduce that for any x E IR,
Σ x 2
+ +VVN, /INCCI SnsN)
iE|n
2 inf (1(,)/))
V ( 2 2 inf
B(I) 2 2r E. [E[1/c.1]
(56)
As B(I c-1) d 7 + B(I) for another standard Brownian motion B(I and Z c-0,c-11 independent from Btt). we can further bound the right-hand side (RHS) of the inequality in the above display as follows. Denote by & the cumulative distribution function (CDF) the standard Gaussian distribution. Then we can show that
inf B(I) 2 2x - % - - (1) IP
RHS of (66)
sup 1E(0,11c71
B(I) < Z 2x
rEj0,1-c-11
(i))
2
sup
B(I) S <2) .P 2 3x
-
rE(0,,1 c-
) (1-
(1-
2Φ
Here, in step (i) above we have used the symmetry property of the Brownian motion, in step (ii) above have used the independence between Btt) and Z, and in step (iii) above have used the reflection principle.
Now choosing
-
(1-
1, Canti
2Φ
V1 -1-c-
Canti
finishes the proof for (54). The proof for (55) is nearly the same due to the symmetric property the Brownian motion, so will be omitted here.
D
34

---

H
Numerical simulations
This section summarizes the settings of all numerical experiments reported in the main text and specifies the reward distributions. Unless otherwise specified, we consider two-armed bandit instances and take arm be the optimal arm.
Common numerical settings for generating reward distributions. In experiments, we use a Beta(a, 3) distribution to generate rewards. Given a desired mean μ and variance a², and subject to the boundedness constraint on [0, 1], we set
H 11)
0² -1))
p o²
a
8 = (1-
Note that an implicit constraint on (14, 0²) o² S p(1 - p4); this constraint is satisfied by all reward distributions used below.
Figure T Distributions of n1,r. In both experiments that plot histograms of arm-pull counts, we set the time horizon to T 50,000 and the number of repetitions to R 5,000. The exploration hyperparameter is = for both UCB-V and UCB. The means and variances are set to //2
and 01
02 in Figure a), and to d1 0, 02 1 and A /2/(()) (log T in Figure 1 Ib).
b).
Figure 2: Regret and phase transition optimal-arm pulls. For panel (a), we set the times of repetition as 10, exploration hyper-parameter p 2. We vary σr (T-1//2 T-1144 1} while keeping 02 T-14 and 11 1 A2 = 7-1/2 M2 141 Ag fixed across curves. We plot the realized regret Reg(T) versus T and observe the trend toward ( as 01 increases. For panel (b), we set T = 1,000,000, and repetition time R = 30, 2, and fix = 0 and 02 = } We sweep Ar - 02v log/pogg771 ( (VT A2) by varying A2; for each value we plot the median and the 30% quantile of n1,r for UCB and UCB-V. The red dotted curve shows the numerical solution niar from (6). revealing transition from sublinear linear n1,7 around Ar 1.
I Further discussion inference with UCB-V
The asymptotic normality of the Z-statistic (8) is established via the martingale CLT. Due to the adaptive nature of data collection in the bandit algorithms, traditional inference techniques based on in- dependent and identically distributed (i.id.)) data cannot be applied directly. However, for stable arms, let us consider the filtration F, generated by {X1...., X,).
The sequence { [{a (a.=a)(X.-p))) R2.r )e([T] forms martingale difference sequence. Moreover, the Lindeberg condition is satisfied, and thus it holds that Exe(T) IE [[a,,a)(Xx_-) F.-1) 3. 1, which allows for the application of the martin- o2nir
gale CLT establish the asymptotic normality the 7-statistic. For detailed derivation, see 23 Section 2.1].
To illustrate the implication of our results on the reward inference, conduct a simulation study on the Z-statistic for UCB and UCB-V using the setting from Example 2 as shown in Figure I In Figure 4a the empirical distributions of the Z-statistic for both UCB and UCB-V V approximate the standard Gaussian, matching the theoretical predictions of our result in Example 2 where UCB-V V is stable in this regime. In Figure 4b] the empirical distribution of the Z-statistic noticeable bias compared to UCB. This suggests that the previously mentioned martingale CLT result no longer holds for UCB-V V when Ar 1. the subsequent section, we show that the underlying reason for this deviation from the CLT is the instability of UCB-V under condition Ay- = 1.
UCB-V shows
J Discussion on the modification of UCB-V
In our presentation of Algorithm [ there are several differences compared those proposed in In A) the UCB reward for each action a is set as
2 log
3{ log
Bat = Xat + Tasy
c
Na.t
Ma,t
35

---

0.1
01
40
10666
(a) Ar
(b) Ar
Figure 4: The empirical distributions of the Z-statistic for the sub-optimal arm for UCB and UCB-V V with 01 0, 02 = 1/4 under different År, both with = 50, 000 over 2, 000 repetitions.
where c, are tunable constants. Specifically, their regret guarantee is established with c, large enough. In our statement, to simplify the notation in our asymptotic analysis, we choose and Ç such that for some p > O, it holds that 2 30 p, replacing log with log T and modifying
plogT
plogT
to (a.
p log T nott
p plog
Ga,
nh,t
Tott
Ra,
We make such modification for notational simplicity and facilitating comparison with results for the canonical UCB [3]. By setting aa,t = instead of estimating it via the sample variance in the algorithm's ' input, our analysis shows that the asymptotic behavior of the modified algorithm becomes equivalent to that of the canonical UCB.
36

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No]. or [NA].
[NA] means either that the question Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justification right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will published with the paper.
The reviewers of your paper will be asked use the checklist as one of the factors their evaluation. While "[Yes] is generally preferable to "[No]" ", it is perfectly acceptable to answer "[No] providedd proper justification is given (e.g.. "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering binary way, we
"[No] or "[NA]" is not grounds for rejection. While the questions are phrased acknowledge that the true answer is often more nuanced, please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Contributions of the paper are accurately stated in the abstract and introduction. made in the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Potential limitations are discussed in the Sections and 4.
37

---

Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an 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 proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification:
All assumptions are stated in their respective places.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced 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 short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification:
The paper includes only simple simulations, and the settings are described in
detail.
Guidelines:
The answer NA means that the paper does not include experiments.
38

---

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 a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make 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 to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g.. with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome 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., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification: The paper includes only simple simulations, and their settings are already described in detail.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for a 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
//nips.cc/public/eee. www.ded/eeeooeuummmmccoo ssi ssionPolicy) 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. If 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).
39

---

Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification:
The simulation settings are clearly described in the text.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level detail that is necessary 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: [No]
Justification: The goal of the simulations is illustrate theoretical insights but not superior to some benchmark.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
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 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 or the standard error of the mean.
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 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 (c.g. negative еттог 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 com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [No]
Justification: The simulations in the paper are simple and can be executed on a standard laptop.
Guidelines:
The answer NA means that the paper does not include experiments.
40

---

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 compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics atttps://neur/: http://///errsss..pcibbb///bbbbe
Answer: [Yes]
Justification: This theoretical work involves no sensitive data or human subjects and fully complies with the NeurIPS Code of Ethics.
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 in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This is theoretical study of bandit algorithm, and we are not aware of any immediate societal impacts.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used 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 unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
41

---

Answer: [NA]
Justification:
The paper does not release any models or datasets that pose risk for misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere 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 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: This work does not use any existing code, data, other external assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if 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.
New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset 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
42

---

Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
This work does not involve crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing 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 as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it 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, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our L.LM policy hatoge//nearris.cc/oooffeeeeeeee for what should or should not be described.
43


Reviews:
[{"review_id": "6um6yvwJvJ", "reviewer": "Reviewer_XTVW", "summary": "This paper studies the behaviour of the Upper Confidence Bound-Variance (UCB-V) algorithm for the Multi-Armed Bandit (MAB) problems. More precisely, it provides an asymptotic characterization of the arm-pulling rates for UCB-V, extending recent results for the canonical UCB. The author establishes that UCB-V can achieve a more refined regret bound.", "questions": "The extension to the K-armed setting is mentioned but not deeply explored. Could the authors provide more intuition or empirical results for this case?", "limitations": "As I mentioned in the weaknesses and questions, this paper only considers the two-armed setting. This setup currently has no practical application because very few real-world scenarios meet the two-armed setting criteria. However, I believe it is essential to consider the two-armed setting before addressing the multi-armed setting.", "rating": 4, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n \n  - This paper provides a detailed analysis of precise asymptotic behaviour for UCB-V, like the stability of arm-pulling numbers.\n\n- This paper derives non-asymptotic bounds for the arm pulling numbers in the high probability regime, which shows high probability bounds and confidence regions for arm pulling numbers. \n\n- The authors include a refined regret for variance-aware decision making.\n\nWeaknesses:\n\n- This paper only focuses on the two-armed setting.", "was_revised": true, "final_justification": "The authors' clarification addressed my concerns. I don't have further questions. Thus I maintain my score.", "rebuttal": "Thank you for your interest in our work and for reviewing our manuscript. We greatly appreciate your feedback and address your comments below.\n\n**Question: Extension to the $K$‑armed setting**\n\nAs mentioned in our last section and Appendix B, we can derive analogous results in the $K$‑armed setting—including the asymptotic equation (15), the sufficient condition for stability (14), and the improved regret bound in Theorem 5—which all reduce to the two‑armed results presented in the main text. We would like to discuss several additional points and calculations:\n\n_1. Asymptotic arm‑pulling characterization._ To provide some intuition for (15), we can generalize Example 1 from the two‑armed setting: assume all variances $\\sigma_a=\\Omega(1)$ and the gaps $\\Delta_a$ are proportional to $\\theta_a\\sqrt{\\log(T)/T}$—the “moderate‑gap regime” of [21]. In this regime, condition (14) always holds, and (15) simplifies to\n\n$$\n\\sum_{a=1}^K \\frac{\\sigma_a^2}{T\\bigl(\\sigma_1/\\sqrt{n_{1}^\\star} + \\theta_a/\\sqrt{T}\\bigr)^2} = 1,\n\\qquad\nn_a^\\star = \\frac{\\sigma_a^2}{T\\bigl(\\sigma_1/\\sqrt{n_{1}^\\star} + \\theta_a/\\sqrt{T}\\bigr)^2}.\n$$\n\nAs $\\theta_a\\to0$, arm‑$a$’s normalized pulling rate ($n_a^\\star/T$) converges to\n\n$$\n\\frac{\\sigma_a^2}{\\sum_{j=1}^K \\sigma_j^2}.\n$$\n\nThat is, when the gaps shrink, each arm’s asymptotic pulling rate becomes proportional to its variance. This generalizes the intuition from Example 1 and the homogeneous setting in [23]. We will include this as an illustrative example in the revised manuscript.\n\nBesides this case (i.e., $\\sigma_a=\\Omega(1)$ for all $a$), we note that, unlike the two‑armed setting, our stability condition (14) may not be tight for general $K$: it is intrinsically harder to construct a counterexample as in Section 3.3 due to the increased number of parameters. In (14), we require an arm‑wise boundedness condition to guarantee convergence to the solution of (15), but we conjecture that it might be relaxed to a single, global condition over all arms.\n\n_2. Regret in the K‑armed setting._  When\n$$\n\\sqrt{\\sum_{a}\\sigma_a^2}\\lesssim \\sum_{a\\ge2}\\frac{\\sigma_a^2}{\\sigma_1},\n$$\nour regret bound in Theorem 5 reduces to\n$$\n\\widetilde O\\bigl(\\sqrt{\\sum_{a\\ge2}\\sigma_a^2 T}\\bigr),\n$$\nmatching previous variance‑aware results. However, in the regime of small $\\sigma_a$ and large $\\sigma_1$, our bound improves to\n$$\n\\sum_{a\\ge2}\\frac{\\sigma_a^2}{\\sigma_1}\\sqrt{T},\n$$\n\nwhich is near‑optimal in the two‑armed case (Theorem 3). Interestingly, for general $K$, this rate scales linearly in $K$, unlike the previous bound which scales as $\\sqrt{K}$; we conjecture that such linear dependence may be unavoidable for UCB‑V, as supported by our empirical results in the Table below (if plotted, the curve of final cumulative regret versus $K$ exhibits an approximately linear trend). Establishing matching lower bounds remains a valuable direction for future work.\n\n**Table: Regret for UCB‑V under different $K$.** \n\n_Simulation parameters:_ rewards are drawn from the beta distributions with $(\\mu_1,\\sigma_1)=(0.5,0.4)$ and $(\\mu_2, \\sigma_2) = \\ldots = (\\mu_K, \\sigma_K) = (0.1, 0.01)$; each simulation is run for  $T = 10,000$ rounds. \n|     $K$    |   2   |    5   |   10   |    20   |    30   |    40   |    50   |\n| :--------: | :---: | :----: | :----: | :-----: | :-----: | :-----: | :-----: |\n| **Regret** | 9.192 | 36.768 | 82.816 | 174.880 | 267.984 | 359.520 | 450.480 |\n\n\n\n**Limitation: Practical relevance of the two‑armed setting**\n\nWe agree that a full treatment of the $K$-armed case is both important and challenging. Nonetheless, the two-armed setting itself actually admits several concrete applications. For example,  A/B testing in web experiments or marketing campaigns naturally reduces to two arms (control vs.  treatment).\n    The analysis in the two-armed setting also provides useful insights for the eventual $K$-armed extension. We hope this explanation is helpful."}, {"review_id": "y0jYjUJMkX", "reviewer": "Reviewer_vmvf", "summary": "This paper studies the statistic performance of the UCB-V algorithm in multi-armed bandits. The authors first give a stable condition, and show that under this condition, the number of pulls on every arm is predictable. Then they show that if the stable condition does not hold, the number of pulls on arms could vary a lot in random. Based on this analysis, the authors also provide refined regret upper bounds for the UCB-V algorithm: if the optimal arm's variance is small, the proposed regret upper bound matches existing ones; however, if the optimal arm's variance is large, the proposed regret upper bound can becomes smaller than existing ones. They also use a lower bound to show the tightness of their refined regret upper bound.", "questions": "I do not have many questions. Please see \"Weaknesses\" part above.", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n- The writing is clear, and the results are easy to understand.\n- The previous regret upper bound is improved (although not a large one).\n- The stability analysis may also give insights for the analysis in other cases, as variance-adaptive algorithms are widely applied. \n\n\nWeaknesses:\n\n- My main concern is that the most technically challenging case analyzed in this paper—namely when the gap $\\Delta = \\Theta(1/\\sqrt{T})$—is rather rare in practice. Since the paper focuses heavily on this regime, the practical relevance of the results may be limited.\n\n- Some parts of the exposition could be clarified. For example, in lines 85–86, the meanings of the notations \"$\\gtrsim$\" and \"$\\lesssim$\" are not very clear. Additionally, in line 166, the use of $\\delta$ to denote a perturbation is potentially confusing, as $\\delta$ is already used as the confidence level in Proposition 1.", "was_revised": true, "final_justification": "The answer is clear, I do not have further questions. \n\nI believe the paper's technical contributions are clear and meaningful to the bandit literature. Therefore, I recommend accepting the paper.", "rebuttal": "Thank you for your interest in our work and for reviewing our manuscript! We greatly appreciate your feedback and address your comments below.\n\n**Question 1: $\\Delta \\asymp 1/\\sqrt{T}$ setting of interest**\n\nWe agree with the reviewer that $\\Delta = \\Theta(1/\\sqrt{T})$ represents a delicate “edge case” in practical applications. However, this regime plays a crucial conceptual and methodological role: by parameterizing $\\Delta \\asymp \\frac{\\theta}{\\sqrt{T}}$ and letting $\\theta\\to0$ or $\\theta\\to+\\infty$, one interpolates smoothly between the small-gap and large-gap regimes. In addition to this interpolation perspective, we borrow examples and explanations from [21] to illustrate how small-gap phenomena arise in practice:\n\n- **A/B testing and clinical trials.**  \n  With large sample budgets $T$, the minimum detectable effect at fixed significance and power satisfies \n  $T \\propto \\Delta^{-2}\n    \\Longrightarrow\n    \\Delta = \\mathcal{O}\\bigl(1/\\sqrt{T}\\bigr).$\n  Hence, web experiments and vaccine dosage trials naturally operate in this small-gap regime.\n\n- **Online allocation of homogeneous tasks.**  \n  Many platforms (ride‑hailing, crowdsourcing) route statistically indistinguishable tasks to agents, requiring fairness on each sample path. Here, true performance differences shrink to $\\mathcal{O}(1/\\sqrt{T})$, so early random fluctuations can lead to stark imbalances in task allocation.\n\nUnder such small‑gap regime, prior works [21, 23] showed that UCB algorithms can maintain low regret and balanced allocations. By contrast, our analysis reveals that incorporating variance estimates yields lower regret but the allocation depends on variances and may not be balanced. Such trade-off highlights a fundamental tension between efficiency and fairness: variance‑aware policies achieve better performance by pulling high-variance arms more often, yet this comes at the cost of an unbalanced allocation, which may be undesirable in applications.\n\n**Question 2: Notational confusions**\n\nThank you for your careful reading! We have corrected the noted notational issues in the revised version:\n\n1. In line 85, we will update the inequality to  \n$$\n\\mathbb{P}\\bigl(n_{1,T} \\lesssim \\sqrt{T}\\log T\\bigr)\n     \\wedge\n     \\mathbb{P}\\bigl(n_{2,T} \\gtrsim T/(\\sigma_2\\sqrt{\\log T})\\bigr)\n     \\gtrsim 1.\n$$\nMoreover, in the Notation section we will add: we write $a \\gtrsim b$ (resp. $a \\lesssim b$) to mean $a \\geq C b$ (resp. $a \\leq Cb $) for some absolute constant $C > 0$.\n\n2. We will replace the perturbation symbol $\\delta$ in line 166 with \n$\\zeta$ to avoid confusion."}, {"review_id": "pX4wCMfulY", "reviewer": "Reviewer_nRgh", "summary": "This paper studies the asymptotic behavior of a variance-aware MAB algorithm called UCB-V in the small gap regime, which reveals significant differences compared to the classic UCB algorithm in the variance-agnostic setting. First, when the deviation of the best arm $\\sigma_1$ and the suboptimal arm $\\sigma_2$ are of the same order, the asymptotic arm pulling fraction is proportional to the variance of each arm, instead of an equal split in UCB. Second, when $\\sigma_1$ is significantly smaller than the sub-optimal arm $\\sigma_2$, the arm pulling fraction may be unstable, depending on the ratio between $\\sigma_2$ and the reward gap $\\Delta$, where a phase transition phenomenon is also revealed. Third, a refined regret bound involving the variance of the best arm $\\sigma_1$ is developed, which is strictly better than the current known result, with a matching lower bound and numerical validation.", "questions": "The example to illustrate the instability of the arm pulling number may not be convincing enough. Since the best arm has variance $0$, and the algorithm knows it,  we do not need to construct confidence intervals for the best arm. A reasonable and natural modification to conduct in this setting is to only pull arm $1$ only once, instead of following the UCB-V algorithm itself. Then, there would not be an instability case since we only pull arm 2. Could you construct a bandit instance with positive variance to show the instability in Proposition 2?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n\n1. A solid and comprehensive theoretical investigation is conducted on the two-armed MAB setting, which reveals a significant behavior difference between UCB-V and UCB in asymptotic regimes. \n\n2. The paper characterizes the arm-pulling fraction based on the study of the asymptotic equation. An unstable regime is revealed when the best arm has low variance, and the gap is in the order of $\\sigma_2\\sqrt{\\theta \\log T/ T}$ especially when the constant $\\theta$ is close to the chosen exploration constant $\\rho$. By a perturbation analysis of the stable equation, a divergent behavior and a phase transition phenomenon are discovered, which justifies the additional effect of variance estimation.\n\n3. The influence of variances of the best arm and sub-optimal arms on the regret performance is also captured via Theorem 2, where a bound involving the best arm's variance is provided. This result (with extension to the multi-armed setting) captures the specific role of the best arm's variance in addition to sub-optimal arms, which is a nice complement to the current worst-case bandit analysis literature. A matching lower bound is also provided to characterize its fundamentality.\n\nWeaknesses:\n\n1. Overall, this paper could improve in several areas regarding presentation and elaboration: (1) I would suggest elaborating on the precise asymptotic behavior for UCB-V in the introduction and using a table to summarize the findings in different regimes; (2) The authors could use a separate section to discuss their numerical results and how it is consistent with theoretical findings. Those results are merely mentioned but not fully discussed in the current version; (3) the addition notation paragraph in section 2 could be expanded so that each new notation, such as the stability function $\\phi$, is given a physical meaning to conceptually prepare for the stability analysis; and (4) the paper is missing a conclusion section.\n\n2. Although extensions to K-armed settings are also discussed for the regret bound, it is hard to generalize the stability results to general K-armed cases. Therefore, the insight into the unstable phase transition behavior of UCB-V may be limited since the two-armed model is a very special case.", "was_revised": true, "final_justification": "Technically solid and strong paper, which, in my opinion, should be accepted. It reveals the fundamental behavior of an important bandit algorithm: UCB-V. The paper has quite a strong impact on advancing our understanding of bandit and RL problems, and is of importance to the ML community. \n\nThe two-armed setting may be restrictive, but extending the mathematical tools in this paper and previous studies to the multi-armed case is generally a very difficult problem. Therefore, the reasons to accept this paper greatly outweigh the reasons to reject.", "rebuttal": "Thanks for your interest in our work and for reviewing our manuscript. We greatly appreciate your feedback and address your comment below.\n\n\n**1. Writing suggestions**\n\nThank you for these valuable suggestions! We apologize for the roughness of some discussion sections and for omitting a conclusion due to page limitations. In the revised version, we will:\n\ni) Expand the introduction to state our UCB‑V asymptotics explicitly and include a compact table summarizing our stability results and regret rates across different regimes.\n\nii) Add a new section that consolidates all simulation results, detailing each experimental setup and explaining how each experiment aligns with our theoretical findings.\n\niii) In Section 2’s Additional Notation paragraph, explicitly define the stability function  \n$$ \\varphi\\_{a,t} = \\frac{\\bar{\\sigma}\\_a \\vee n_{a,t}^{-1/2}}{\\sqrt{n_{a,t}}}, $$\nand clarify that these two components correspond to the two error terms in Bernstein's inequality—so that the UCB‑V bonus for arm $a$ at time $t$ is taken as the larger of the variance‑based and boundedness‑based corrections.\n\n\niv) Add a Concluding section that summarizes our main contributions, acknowledges limitations, and outlines directions for future work.\n\n\n**2. Limitations in $K$ armed setting.**\n\nWe agree that our stability condition (14) may not be optimal for $K>2$, and that a full phase‑transition characterization is still lacking. The main technical challenge in extending our theory to the $K>2$ case lies in the increased number of parameters and their complex interactions. We therefore leave a tighter analysis of the $K>2$ case as an important direction for future work.\n\n\n**3. Instability example beyond zero‑variance instances**\n\nWe chose $\\sigma_1 = 0$ solely for simplicity of exposition. In fact, the instability analysis in Proposition 2 extends directly to settings where the optimal arm’s variance satisfies $\\sigma_1 = \\mathcal{O}(1 /\\sqrt{T})$, since the UCB‑V bonus term for the optimal arm is the same as in the $\\sigma_1 = 0$ case. We will generalize Proposition 2 accordingly in the revised manuscript.\n\nOn the other hand, we  would like to note that constructing an instance with $\\sigma_1 = T^{-\\alpha}$ for some $\\alpha \\in (0,1/2)$ is more challenging and requires some new ideas, as the asymptotic equation from Example 2 no longer applies.  We will acknowledge such limitation in the revised version."}, {"review_id": "vnGuA1nm6z", "reviewer": "Reviewer_1t6H", "summary": "This paper studies the UCB-V algorithm for stochatic bandit, a variant of the UCB algorithm when the standard deviation needs to be estimated. In particular, this paper studies the asymptotic arm pulls and how they depend on the gap between the suboptimality gap and the reward variances. The result shows a phase transition, as the arm pulls can be linear or sublinear based on the these parameters.", "questions": "The author focuses on a specific implementation of UCB-V. In the class of UCB algorithms, there is one variant that doesn't use $\\log T$ in the numerator in the square root but $\\log t$. See Chapter 8 of the book by Lattimore and Szepesvar. This variant is less conservative and has better empirical performance especially when $T$ is large. I wonder if (1) UCB-V has such a variant and (2) how easy/challenging is it to adapt the current analysis to the variant.", "limitations": "NA", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- This paper is a theoretical paper with heavy notation. But the authors are able to present the result and explain the intuition really well. Overall I enjoy reading it and learned a lot from the results and analyses.\n- The results are highly nontrivial and comprehensive. The asymptotic rate of the arm pulls depend on a lot of parameters, and the authors are able to analyze the dependence very thoroughly.\n- The discussion of the literature is detailed and the readers can see which analyses are inspired by which paper and how the results differ.\n\nWeakness: NA", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your interest in our work and for reviewing our manuscript! We greatly appreciate your feedback and address your comment below.\n\n\n\n**Question: Modifying current analysis to the $\\log t$ variant**\n\nThank you for raising this insightful question! \n\n(1) In [4],  UCB-V is presented in the general form \n    \\begin{align*}\n         \\mathrm{UCB}(a,t) = \\bar{X}\\_{a,t} +  \\widehat \\sigma\\_{a,t} \\cdot \\sqrt{\\frac{\\mathcal{E}\\_t}{n\\_{a,t}}}\n    +\\frac{\\mathcal{E}\\_t}{n\\_{a,t}},\n    \\end{align*}\nwhere $\\mathcal{E}_t$ is any non-decreasing function of $t$. Setting $\\mathcal{E}_t = \\log t$ recovers the ``$\\log t$'' variant you mentioned.\n\n(2) We believe extending our current analysis to the ``$\\log t$'' variant is **not** straightforward. Technically, it requires at least two major changes:\n\n- **An improved Bernstein‑type non‑asymptotic LIL result.** \n\nIn our Lemma 8, the Bernstein-type non-asymptotic LIL is stated as: with probability at least $1-\\delta$,\n    \\begin{align*}\n        \\big| \\bar{X}_t\\big| \\lesssim \\sigma\\sqrt{\\frac{\\log\\frac{\\log(T/\\delta)}{\\delta}}{t}} + \\frac{\\log(1/\\delta)}{t},  \\forall 1 \\leq t \\leq T.\n    \\end{align*}\n    To handle the ``$\\log t$'' variant, we may need to replace the fixed threshold $\\log\\frac{\\log(T/\\delta)}{\\delta}$ by a time-varying $\\log\\frac{\\log(t/\\delta)}{\\delta}$ inside the square root, i.e.,\n    \\begin{align*}\n        \\big| \\bar{X}_t\\big| \\lesssim \\sigma\\sqrt{\\frac{\\log\\frac{\\log(t/\\delta)}{\\delta}}{t}} + \\frac{\\log(1/\\delta)}{t},  \\forall 1 \\leq t \\leq T.\n    \\end{align*}\n\nAlthough obtaining such an improvement might require a more refined martingale-based analysis, we are hopeful that a stronger bound could be achievable.\n\n\n\n- **A revised UCB‑V analysis framework.**\n\n Even with the refined LIL concentration inequality we mentioned in point 1, under the ``$\\log t$'' variant our current analysis framework breaks down. Concretely, one obtains  \n\n\\begin{align*}\n        1 + \\mathfrak{o}\\_{\\mathbf{P}}(1) \\geq \\frac{\\Delta_a / \\log T_a+ \\varphi\\_{1,T} }{ \\varphi_{a,T}} ,\\quad \\frac{\\Delta_a / \\log T_1+ \\varphi\\_{1,T} }{ \\varphi\\_{a,T}} \\geq 1 -\\mathfrak{o}\\_{\\mathbf{P}}(1),\n\\end{align*}\n\nwhere $\\log T_1$ and $\\log T_a$ now differ because of the time-varying bonus. Such mismatch prevents us from collapsing to a single fixed point equation.  \n\nA similar limitation appears in the non-variance UCB analysis in [23], which also studies the \\``$\\log T$'' version of the UCB algorithm, and this may be a fundamental gap in using such a framework to conduct analysis. It is worth noting that [21] has successfully analyzed the behaviour of non-variance UCB in the \\``$\\log t$'' variant, but with a different, dedicated analysis and with results in a less complete characterization (as discussed below Theorem 3.1 of [23]). We tend to believe that this subtle limitation of the framework used by [23] and our work is a fundamental price paid for providing more complete characterization and simplifying the analysis of [21]. Given the less conservative nature and strong empirical performance of this  \\``$\\log t$'' variant algorithm, exploring it further could be a worthwhile avenue for future work."}]

Author rebuttal:

Meta-review: This paper presents a theoretical analysis of the Upper Confidence Bound-Variance (UCB-V) algorithm for multi-armed bandit problems. The reviewers unanimously praised the paper for its technical depth, clarity, and originality, recognizing it as a solid and comprehensive investigation into the behavior of an important variance-aware algorithm. While some reviewers initially raised concerns about the primary focus on the two-armed setting and its practical relevance, the authors' rebuttal effectively addressed these points by providing strong justifications for the importance of this setting in applications like A/B testing and by offering clear intuition and empirical support for the extension to the more general K-armed case. The authors also agreed to incorporate several presentation improvements suggested by the reviewers, further strengthening the manuscript. All reviewers were satisfied with the authors' responses, leading to a consensus of acceptance.
Decision: Accept (spotlight)