A Closer Look at the Worst-case Behavior of Multi-armed Bandit Algorithms
Authors: Anand Kalvit
assaf zeevi
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: multi-armed bandits
learning algorithms
UCB
Thompson Sampling
minimax regret
diffusion approximation
distribution of arm-pulls

Abstract: One of the key drivers of complexity in the classical (stochastic) multi-armed bandit (MAB) problem is the difference between mean rewards in the top two arms, also known as the instance gap. The celebrated Upper Confidence Bound (UCB) policy is among the simplest optimism-based MAB algorithms that naturally adapts to this gap: for a horizon of play n, it achieves optimal O(log n) regret in instances with "large" gaps, and a near-optimal O(\sqrt{n log n}) minimax regret when the gap can be arbitrarily "small." This paper provides new results on the arm-sampling behavior of UCB, leading to several important insights. Among these, it is shown that arm-sampling rates under UCB are asymptotically deterministic, regardless of the problem complexity. This discovery facilitates new sharp asymptotics and a novel alternative proof for the O(\sqrt{n log n}) minimax regret of UCB. Furthermore, the paper also provides the first complete process-level characterization of the MAB problem in the conventional diffusion scaling. Among other things, the "small" gap worst-case lens adopted in this paper also reveals profound distinctions between the behavior of UCB and Thompson Sampling, such as an "incomplete learning" phenomenon characteristic of the latter.

A Closer Look at the Worst-case Behavior of Multi-armed Bandit Algorithms
Anand Kalvit' and Assaf Zeevi²
Columbia University
New York, USA
{ ('akalvit22," assaf Aagsb. col.mbia...leeeeoeooooo.o.ee. edu
Abstract
One of the key drivers of complexity the classical (stochastic) multi-armed bandit (MAB) problem is the difference between mean rewards in the top two arms, also known the instance gap. The celebrated Upper Confidence Bound (UCB) policy is among the simplest optimism-based MAB algorithms that naturally adapts to this gap: for horizon of play n, it achieves optimal O (logn) regret in instances with "large" gaps, and near-optimal O (vn log n) minimax regret when the gap can be arbitrarily "small." This paper provides new results on the arm-sampling behavior of UCB, leading several important insights. Among these, it shown that arm-sampling rates under UCB are asymptotically deterministic, regardless of the problem complexity. This discovery facilitates new sharp asymptotics and novel alternative proof for the O /n log minimax regret of UCB. Furthermore, the paper also provides the first complete process-level characterization of the MAB problem under UCB in the conventional diffusiion scaling. Among other things, the "small" gap worst-case lens adopted in this paper also reveals profound distinctions between the behavior of UCB and Thompson Sampling, such as an incomplete learning phenomenon characteristic the latter.
Introduction
Background and motivation. The MAB paradigm provides a succinct abstraction of the quintessen- tial exploration exploitation trade-offs inherent in many sequential decision making problems. This has origns in clinical trial studies dating back to 1933 [30 which gave rise to the carliest known MAB heuristic, Thompson Sampling (T. Today, the MAB problem manifests itself in various forms with applications ranging from dynamic pricing and online auctions to packet routing, scheduling, e-commerce and matching markets among others (see O for comprehensive survey of different formulations). In the canonical stochastic MAB problem, a decision maker (DM) pulls one of K arms sequentially each time t 21,2....) and receives random payoff drawn according to arm-dependent distribution. The DM, oblivious to the statistical properties of the arms, must balance exploring new and exploiting the best arm played thus far in order to maximize her cumulative payoff over the horizon of play. This objective is equivalent to minimizing the regrel relative to an oracle with perfect ex ante knowledge of the optimal arm (the one with the highest mean reward).
The classical stochastic MAB problem is fully specified by the tuple ((Pi) n). where P;
denotes the distribution of rewards associated with the 1h arm, and the horizon of play.
The statistical complexity of regret minimization the stochastic MAB problem is governed by key primitive called the gap, denoted by A, which accounts for the difference between the top two arm mean rewards in the problem. For "well-separated" or "large gap" instance, i.e., a fixed A bounded away from 0, the seminal paper
2 showed that the order of the smallest achievable regret
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

is logarithmic in the horizon. There has been plethora of subsequent work involving algorithms which can fine-tuned achieve regret arbitrarily close to the optimal rate discovered in [22] (see etc., for few notable examples). On the other hand, no algorithm can achieve an expected regret smaller than Cyn for a fixed (the constant hides dependence on the number arms) uniformly over all problem instances (also called minimax regret); see, e.g., 2 Chapter 15. The saddle-point in this minimax formulation occurs at a gap that satisfies A x 1/vn. This has a natural interpretation: approximately 1/ samples are required to distinguish between two distributions with means separated by A; at the 1/ I/sree, it becomes statistically impossible to distinguish between samples from the top arms within rounds of play. If the gap is smaller, despite the increased difficulty in the hypothesis test, the problem becomes "easier" from regret perspective. Thus, A 1/ yn is the statistically "hardest" scale for regret minimization. A number of popular algorithms achieve the vn minimax-optimal rate (modulo constants), see, e.g.. [ 2 and many more do this within poly-logarithmic factors in n. Many of these variations of the celebrated upper confidence bound algorithms, e.g.. UCB1 7 that achieve a minimax regret of (v log n)) and at the same time also deliver the logarithmic regret achievable in the mnstance-eepender setting of (22)
6
11
2
major driver of the regret performance of an algorithm is its arm-sampling characteristics. For example, in the instance-dependen (large gap) setting, optimal regret guarantees imply that the fraction of time the optimal arm(s) are played approaches in probability, as n grows large. However, this fails provide any meaningful insights as to the distribution of arm- arm-pulls for smaller gaps, e.g.. the x 1/v7 Vn "small gap" that governs the "worst-case" instance- ieannnceiddepeeeentt setting.
An illustrative numerical example involving "small gap." Consider an A/B testing problem (e.g.. a vaccine clinical trial) where the experimenter faced with two competing objectives: first, to estimate the efficacy of each alternative with the best possible precision given a budget of samples, and second, keeping the overall cost of the experiment low. This is a fundamentally hard task and algorithms incurring a low cumulative cost typically spend little time exploring sub-optimal alternatives, resulting in a degraded estimation precision (see, e.g., ( In other words, algorithms tailored for (cumulative) regret minimization may lack statistical power BI. While this trade-off is unavoidable in "well-separated" instances, numerical evidence suggests a plausible resolution in instances with "small" gaps illustrated below. For example, such situation might arise in trials conducted using two similarly efficacious vaccines (abstracted away as se 0). To illustrate the point more vividly, consider the case where A is exactly 0 (of course, this information is not known to the experimenter). This setting is numerically illustrated in Figure [ which shows the empirical distribution of N₂ (n)/n (the fraction of time arm is played until time n.) in two-armed bandit with O, under two different algorithms (UCB and Thompson Sampling), and reward configurations.
UCB1
with priors
priors
5
125-
4
4
100
3-
3
2-
2-
50-
25-
0.0
0.5
1.0
q 0.5
(b) 9 0.5
(c) 10
Figure 1: Incomplete learning under Thompson Sampling. A two-armed bandit with arms having Bernouli(g)) q) rewards each: Histograms show the empirical (probability) distribution of N₁ (n) /n for 10,000 pulls. plotted using 20,000 experiments. Algorithms: UCB1 77. TS with Beta priors M
desirable property of the outcome in this setting to have a linear allocation of the sampling budget per arm on almost every sample- patepppahhhe of the algorithm, as this leads to "complete learning:" an algorithm's 's ability to discern statistical indistinguishabilityy of the arm-means, and induce "balanced" allocation in that event. However, despite the simplicity of the zero-gap scenario, it is far from obvious whether the aforementioned property may satisfied for standard bandit algorithms such as UCB and Thompson Sampling. Indeed, Figure [ exhibits striking difference between the two. The concentration around 1/2 observable in Figure a indicates that UCB results in an approximately "balanced" sample-split, i.c., the allocation roughly n/2 per arm for large

---

(and this is observed for "most" sample-paths). In fact, we will later see that the "bell curve" in Figure () eventually collapses into the Dirac measure at 1/2 (Theorem []. On the other hand, under Thompson Sampling, the allocation of samples across arms may be arbitrarily "imbalanced" despite the arms being statistically identical, as seen in Figure lb) (see, for contrast, Figure Te), where the allocation is perfectly "balanced").. Namely, the distribution of the posterior may be such that arm I allocated anywhere from almost no sampling effort all the way to receiving almost the entire sampling budget, Figure lb)) suggests. Non-degeneracy of arm-sampling rates is observable also under the more widely used version of the algorithm that is based on Gaussian priors and Gaussian likelihoods (Algorithm 2 in (2);; see Figure 2 a). Such behavior can be detrimental for ex post causal inference in the general A/B testing context, and the vaccine testing problem referenced earlier. This is demonstrated via instructional example of two-armed bandit with one deterministic reference arm (aka the "one-armed" bandit paradigm), illustrated in Figure 2 and discussed below.
A numerical example illustrating inference implications. Consider model where arm 1 returns a constant reward of 0.5, while arm 2 yields rewards distributed as Bernoulli(O.5). In this setup, the estimate of the gap A (average treatment effect in causal inference parlance) after n rounds of play is given by Ả (m) 0.5, where X² denotes the empirical mean reward of arm 2 at time The Z statistic associated with this gap estimator given by 222 A where N2(n) the visitation count of arm 2 at time n. In the absence of any sample-adaptiviyy in the arm 2 data, results from classical statistics such the Central Limit Theorem (CLT) would posit an asymptotically Normal distribution for 2. However, since the algorithms that play the arms are adaptive in nature, e.g.. UCB and Thompson Sampling, asymptotic- normmltti-noommllty may no longer be guaranteed. Indeed, the numerical evidence in Figure strongly points to a significant departure from asymptotic-normalliy of the Z statistic associated with the gap estimator under Thompson Sampling (TS). Non-normality of the 2 statistic can be problematic for inferential tasks, e.g., it can lead to statistically unsupported inferences in the binary hypothesis test Ho A = 0 vs. Hi A F 0 performed using confidence intervals constructed as per the conventional CLT approximation. In sharp contrast, our work shows that UCB satisfies certain "balanced" sampling property (such as that in Figure I a)) in instances with "small" gaps, formally stated Theorem I that drives the Z statistic towards asymptotic- normality in the aforementioned binary hypothesis testing example (asymptotic-norna consequence of Theorem 4). Furthermore, since the /n-normalized "stochastic" regret (defined in
being a
① in 2 equals (v (N))))(AAn) Z, it follows that this too, satisfies asymptotic-normaliy under UCB (due to Theorem 4 in conjunction with Theorem D. These properties are evident in Figure - c) below, and signal reliability of ex post causal inference (under classical assumptions like validity of CLT) from "small gap" data collected by UCB vis-à-vis Thompson Sampling (TS). The reliability of inference under TS may be doubtful even in the limit of infinite data, as Figure (b) suggests.
TS
Distribution of Z statistic under TS
Distribution of Z statistic under UCB
OCT aita parc
0.7
ucB exa (1
1.00
0.3
0.3
0.75
0.2
0.2
0.25
1.0 0.0
0.0
0.5
2
-4
2
(a) Distribution of N₂ (n))m
(b) Departure from CLT
(c) Asymptotic normality per CLT
Figure 2: Failure of CLT under TS. A two-armed bandit with A = 0:: Arm returns a constant reward of 0.5, and arm 2 yields rewards distributed as Bernoull In (a), the histogram shows the empirical (probability) distribution of N (n)) /n. Algorithms: TS (Algorithm 2 in 22) and UCB (UCBI in 7 All histograms have n = 10,000 pulls, and are plotted using N 20,000 experiments.
While traditional literature on stochastic bandits is dedicated primarily to the regret minimization problem, there has been significant recent interest also in finer-grain properties of popular "adaptive" MAB algorithms such as UCB and Thompson Sampling. For example, recent line of work 27 2 29) investigates the "bias" of optimistic algorithms like UCB. The focus of our work is on understanding the distribution of arm-pulls, which as discussed earlier, has significant bearings
3

---

ex post causal inference from data collected adaptively by bandit algorithms (see, e.g., + 16 32]
etc., and references therein for recent developments), algorithmic fairness in the broader context of fairness in machine learning (see 2 for a survey), well as on novel formulations of the MAB problem such as (20). Below, we discuss extant literature relevant to our line of work.
Previous work. The study of "well-separated instances, or the large gap regime, is supported by rich literature. For example. [6] provides high-probability bounds on arm-sampling rates un- der parametric l'amlly of UCB algorithms, However, as the gap diminishes, leading to the so called small gap regime, the aforemeentoned bounds become vacuous. The understanding of arm- sampling behavior remains relatively under mnder-studied here even for popular algorithms such as UCB and Thompson Sampling, This regime of special interest in that it also covers the classical diffiusion scaling" where A x 1/Vn, which as discussed earlier, corresponds to instances that statistically constitute the "worst-case" for hypothesis testing and regret minimization. Recently, a partial diffusion-lins characterization of the arm-sampling distribution under a version of Thompson Sampling with horizon- -deeeneet prior variance was provided in 2 as a solution to a certain stochastic differential equation (SDE). The numerical solution to said SDE was observed to have a non-degenerate distribution on [0, 1]. Similar numerical observations on non-degeneracy of the arm-sampling distribution also under standard versions of Thompson Sampling were reported in IC 22,, among others, albeit limited only to the special case of = 0, and absent a theoretical explanation for the aforementioned observations. Thus, outside of the so called "easy" problems, where A is bounded away from by an absolute constant, theoretical understanding of the sampling behavior of bandit algorithms remains an open area of research.
Contributions. In this paper, we provide the first complete asymptotic characterization of arm- sampling distributions under canonical UCB (Algorithm I as function of the gap A (Theorem M This gives rise to a fundamental insight: arm-sampling rates are asymptotically deterministic under UCB regardless of the hardness of the instance. We also provide the first theoretical explanation for an "incomplete learning" phenomenon under Thompson Sampling (Algorithm 2 alluded to in Figure as well as sharp dichotomy between Thompson Sampling and UCB evident therein (Theorem This result carmarks an "instability" of Thompson Sampling in terms of the limiting arm- arm-sampling distribution. As sequel to Theorem we provide the first complete characterization of the worst-case performance of canonical UCB (Theorem 3 One consequence is that the O (v log n2) minimax regret of UCB is strictly unimprovable in a precise sense. Moreover, process-level characterization of the two-armed bandit problem under canonical UCB in the classical diffusion limit, according to which suitably normalized cumulative reward process converges in law to Brownian motion with fully characterized drift and infinitesimal variance (Theorem 4p. To the best of our knowledge, this is the first such characterization of UCB-type algorithms. Theorem facilitates a complete distribution-level characterization of UCB's diffusion-limit regret, thereby providing sharp insights as to the problem's 's minimax complexity. Such distribution-leve information may also be useful for a variety of inferential tasks, e.g., construction of confidence intervals (see the binary hypothesis testing example referenced in Figure e))). among others. We believe our results may also present new design considerations, in particular, how to achieve, loosely speaking, the "best of both worlds" for Thompson Sampling. by addressing its "small gap" instability. Lastly, we note that our proof techniques are markedly different from the conventional methodology adopted in MAB literature
work also leads the first
9 ), and may be of independent interest in the study of related learning algorithms.
Organization of the paper. A formal description of the model and the canonical UCB algorithm provided in $ All theoretical propositions are stated in } along with high-level overview of their scope and proof sketch; detailed proofs and ancillary results are relegated to the supplementary material. Finally, concluding remarks and open problems are presented in s
2 The model and notation
The technical development in this paper will focus on the two-armed problem purely for expositional reasons; we provide extensions to the general K-armed setting in Appendix B The restriction to two-armed bandits has precedence also in the literature due to its tractability for sharp asymptotic
'This is a standard technique for performance evaluation stochastic systems, commonly used the operations research and mathematics literature, see, e.g., [5) Asssumed to be vanishing in n; standard versions of the algorithm involve fixed (positive) prior variances.

---

analyses, see, e.g., (2II.. This setting encapsulates the core statistical complexity of the MAB problem in the "small gap" regime, as well as concisely highlighting the key novelties in our approach. Before describing the model formally, we introduce the following asymptotic conventions.
Notation. We say f(n) = o (g(n)) or g(n)
(f(n)) if lim, 00
f(n)
0. Similarly, f(n)
g
O (g(n) or g()) = 2 (n)) if lim supn->xx
[(x)
< C for some constant C. If [(n) = O ((g(n)))
s(n)
and f(m) = Ω ((g(n))) hold simultaneously, we say [(n) - (g(n)), or s(n) = g(n), and we write f(n) g(n) in the special case where lim,-xxo g(n)
[(n) = 1. If either sequence f(n) or g(n) is
random, and one of the aforementioned ratio conditions holds in probability, we use the subscript
p with the corresponding Landau symbol. For example, (n) = Op (g(n)) if f(n)/g(n) 2 0 as + 0c. Lastly, the notation '=' will be used for weak convergence.
The model. The arms indexed by {1.2). Each arm i {1,2} is characterized by reward distribution P; supported on [0, 1] with mean f4- The difference between the two mean rewards, aka the gap, is given by A = |0n M2l; discussed earlier, this captures the hardness of an instance. The sequence of rewards associated with the first m pulls of arm i is denoted by (Xi,i) (xiss) The rewards are assumed to be i.i.d. in time, and independent across arms The number of pulls of arm i up to (and including) time t is denoted by (t)... A policy π == (Ft) is an adapted sequence that prescribes pulling an arm सe E S at time t, where S denotes the probability simplex on (1,2).
:i=1,2) The The natural filtration at time t is given by F. == a (Ta)age: (Xxx))eN.. : : 1. stochastic regret of policy after n plays, denoted by RT is given by
[max (mi, p2) X Xm..N,, (01]
The decision maker is interested in the problem of minimizing the expected regret, given by inf ER
where II is the set of policies satisfying the non non-anticipaa anticipation property Ne - 1<t< n, and the expectation is w.r.t. the randomness in reward realizations as well as possible randomness in the policy æ. this paper, we will focus primarily on the canonical UCB policy given by Algorithm D below. This policy is parameterized by an exploration coefficient p. which controls its arm-exploring rate. The standard UCB1 policy 7 corresponds to Algorithm with p = 2: the effect of p on the expected and high-probability regret bounds of the algorithm is well-documented in O for problems
with a 'large gap." In what follows, (1, 1) denotes the empirical mean reward from arm i E {1,2)
-, X
at time/ L i.e., X,(1 1)
N((1-1)
Algorithm 1 The canonical UCB policy for two-armed bandits.
1: Input: Exploration coefficient, p E RT..
2: A 1,2, play each arm i {1,2} once.
3: for E [3, .... do
4: Play arm n. E arg (a
(Xi(t= 1) +
plog(t-1) Ni(l-1)
3 Main results
Algorithm is known to achieve ERT = O (log n) in the instance-dependdntt setting, and n log ri) in the "small gap" minimax setting. The primary focus of this paper is
ER, = O (v on the distribution of arm-sampling rates, i.e., (n), E (1, Our main results are split across two sub- sobbsections: $3.1 examines the behavior of UCB (Algorithm IT) as well as another popular bandit algorithm, Thompson Sampling (specified in Algorithm 2) $3.2 is dedicated to results on the (stochastic) regret of Algorithm I under the A = (logn) n) /n "worst-case" gap and the A = 1/ / itiffusion-scaledd gap.
These assumptions be relaxed in the spirit of results also extend sub- Gaos-aussian rewards.
5

---

3.1 Asymptotics of arm-sampling rates
Theorem (Arm-sampling rates under UCB) Let i" e arg max {ug = 2] with ties broken arbitrarity. Then, the following results hold for arm i" as n + oo under Algorithm ! with >> 1:
(I) "Large gap:" " If w
logn
then No (n)/n 2 1.
(v
(II) "Small gap:" If
log
then N₂. (n)/m 3 1/2.
(III) "Moderate gap:" If limit is the unique solution (in X) to
log for some sixed 0 > O, then No (n)nn/n 2 x²(0), where the
(2)
and is monotone increasing in 0, with x²(0) 1/2 and x; 1 as 0 - xo.
Remark 1 (Permissible values of in Algorithm
1 For p 1, the expected regret of the policy
given by Algorithum| is bounded as ER, < Cp
for some absolute constant C > 0:
the upper bound becomes vacuous for p & 1 (see (0) Theorem 7). We therefore restrict Theorem > 1 to ensure that ER" remains non-trivially bounded for all A.
Discussion and intuition. Theorem D essentially asserts that the sampling rates (1))/n, i { are asymptotically deterministic in probability under canonical UCB: A only serves to determine the value of the limiting constant. The "moderate" gap regime offers continuous interpolation from instances with zero gaps to instances with "large" gaps as I sweeps over R4 in that (7) increases monotonically from 1/2 at 0 = 0 to 1 at 0 = co, consistent with intuition. The special case of 0 = 0 is numerically illustrated in Figure aa). The tails of N₂- (n1) decay polynomially fast near the end points of the interval [0, 1] with the best possible rate approaching O (n 12-3), occurring for 0 However, as Ni- (n2//n approaches its limit, convergence becomes slower and dominated by fatter
tails. The behavior in this regime is regulated by the O (Vnlog log n) the zero-drift random walk process driving the algorithm's 's regret (see proof of Theorem for details).
(v log log log n
envelope of
Proof sketch. To provide the most intuitive explanation,
pivot the special case where the
arms have identical reward distributions, and in particular, A = 0. The natural candidate then for the limit of the empirical sampling rate is 1/2. On high level, the proof relies on polynomially
[i) 1// > derived using the standard trick for bounding the number of pulls of any arm on given sample-path, to wit, for any u, E N, Nı (n) be bounded above by Ei=u+1 1 ( = 1, Ni 1) > w). path-wise. Setting [ + <) n] in this expression, one subsequently show via analysis involving careful use of the policy structure together with appropriate Chernoff bounds that with high probability (approaching
decaying bounds in for e-deviations of the form IP
a
+ oo), Ni (n)/nn < 1/2 + Ep for some Ep E (0, 1/2) that depends only on p. An identical result would naturally hold also for the other arm by symmetry arguments, and therefore arrive meta-conelusion that (n(n)/n
1/2 - Ep >> 0 for both arms E {1,2] with high probability (approaching 1 as n + 20). It is noteworthy that said conclusion cannot be arrived at for an arbitrary e (in place of ep) since the polynomial upper bounds on P ( ([)( 2 >
derived using the aforementioned path-wise upper bound on (n),,, become vacuous if u set "too close" to n/2, i.e., if is "near" 0. Extension to the full generality of e >> 0 is achieved via a refined analysis that uses the Law of the Iterated Logarithm (see [II] Theorem 8.5.2), together with the
previous conelsoon,,s,on, to obtain fatter O (V (log log
tail bounds when e near O. Here, is
log
imperative to point out that the "log 11" appearing in the denominator is essentially from the Vplog optimistic bias term of UCB (see Algorithm[l] [T. and therefore the convergence will, as such, hold also for other variations of the policy that have "less aggressive" w (log log i) exploration functions vis-à- vis log However, this will be achieved at the expense of the policy's expected regret performance,

---

as noted in Remark We also note that the extremely slow (v log log n
convergence is not an
artifact of our analysis, but in fact, supported by the numerical evidence in Figure I a), suggestive of a plausible non-convergence (to 1/2) in the limit. We believe such observations in previous works likely led to incorrect folk conjectures ruling out the existence of deterministic limit under UCB à la Theorem (see, e.g., [TC and references therein). The proof for a general A in the "small" and "moderate" gap regimes is skeletally similar that for A 0, albeit guessing a candidate limit for
Nç- (n)/n is non-trivial; a closed-form expression for X (
( is provided in Appendix A Full details
of the proof of Theorem are provided in Appendix
O
Remark 2 (Possible generalizations of Theorem I A simple extension to the K-a Kaareed setting is
provided in Appendix as Theorem 5 The behavior of UCB policies is largely governed by their optimistic bias. While Theorem only covers the generic UCB policy with Vplog I bias, results of the form /n Eg ca for some e (0.1) continue to hold also under smaller w (Vplog log bias (driven by the Law of the Iterated Logarithm). We believe this observation will be useful when examining more complicated UCB-inspired policies such as KL-UCB A13), DMED [8), etc.
What about Thompson Sampling? Results such as those discussed above for other popular adaptive algorithms like Thompson SamplingJ are only arable in "well-separated" instances where No. (n)(n)/n 2, 1 as - oo follows as a trivial consequence of its O (vn) minimax regret bound [2]. For smaller gaps, theoretical understanding of the distribution of arm-pulls under Thompson Sampling remains largely absent even for its most widely- stuuded variants. In this paper, we provide a first result in this direction: Theorem 2 formalizes a revealing observation for classical Thompson Sampling (Algorithm 2 in instances with zero gap, and elucidates its instability in view of the numerical evidence reported in Figure [b) and This result also offers an explanation for the sharp contrast with the statistical behavior of canonical UCB (Algorithm [T] à la Theorem [] also evident from Figure [a). In what follows, rewards are assumed to be Bernoulli, and S; (respectively F)) counts the number of successes/I ' (respectively failures/0's) "s) associated with arm i E (1,
Algorithm 2 Thompson Sampling for the two-armed Bernoulli bandit.
1: Initialize: Number of successes (1 's) and failures (0's) for each arm i E (1,2), (S., F.) = (0.
2: for E (1,2....) do
3: Sample for each i (1, T, ~ Beta (S; + F. 1).
4: Play arm E arg /1.2) T, and observe reward Tr E (0, 1}.
5: Update success-failure counts: Sx,, + Sx, + ru, Fs, + Fs.. + 1 T-
Theorem (Incomplete learning under Thompson Sampling) In a two-armed model where both arms yield rewards distributed as Bernoulligg) (g), the following holds under Algorithu D -> 00.
(I) If q = 0, then N1(n)/n + 1/2.
(II) l = 1, then N1 + Uniform distribution on [0, 1].
Proof sketch. The proof of Theorem relies on a careful application of two subtle properties of the Beta distribution (Fact 2 and Fact ). stated and proved in Appendix CK For part (I), we invoke symmetry to deduce E. (n) = n/2, and use Fact 2 to show that the standard deviation of N₂ (n) is sub-linear in n, thus proving the stated assertion in (I). More elaborately, Fact states for the reward configuration in (I) that the probability of playing arm after it has already been played n1 times, and arm 2 n2 times, equals (n2 + 1)/(m) + + + 2). This probability is smaller than 1/2 if n > n22 which provides an intuitive explanation for the fast convergence of N, (n)/ n to 1/2 observed in Figure Cc). In fact, we conjecture that the result in (I) holds also with probability 1 based on the aforementioned "self-balancing" property. The conclusion in part (II) hinges on an application of Fact 3 to show the stronger result: N1 (n) is uniformly distributed over {0, 1.., n for any E N. Contrary to Fact [ Fact states that quite the opposite is true for the reward configuration in (II): the probability of playing arm I after it has already been played ny times, and arm 2 n2 times, equals (n1 + 1) (n1 + n2 + 2), which is greater than 1/2 when n1 > 122. That is, the posterior distributions
'This is the version based on Gaussian priors and Gaussian likelihoods, not the classical version based on Beta priors and Bernoulli likelihoods which has minimax regret of O (Vn logn) 22.
7

---

evolve in such way that the algorithm is "deceived" into incorrectly believing one of the arms (arm 2 in this case) to be inferior. This leads to large sojourn times between successive visitations of arm 2 on such a sample-path, thereby resulting in perpetual "imbalance" in the sample-counts. This provides an intuitive explanation for the non-degeneracy observed in Figure (b) and 2 a), which additionally, also indicates that such behavior, in fact, persists also for general (non-determnnistic) reward distributions, as well as under the Gaussian prior-based version of the algorithm. Full proof of Theorem 2 is provided in Appendix G
More on "incomplete learning." " The zero-gap setting is a special case of the "small gap" regime where canonical UCB guarantees (1/2. 1/2) sample-split in probability (Theorem D. On the other hand, Theorem suggests that second order factors such as the mean signal strength (magnitude of the mean reward) could significantly affect the nature of the resulting sample-split under Thompson Sampling. Note that even though the result only presupposes deterministic 0/1 rewards, the aforemen- tioned claim is, in fact, borne out by the numerical evidence in Figure (b) and The sampling distribution seemingly flattens rapidly from the Dirac measure at 1/2 to the Unitorm distribution on [0, 1] as the mean rewards move away from 0. This uncertainty in the limiting sampling behavior has non-trivial implications for a variety of application areas of such learning algorithms. For instance, uniform distribution of arm-sampling rates on [0, 1J indicates that the sample-split could be arbi- trarily imbalanced along a sample- pathle despite, as in the setting of Theorem 2 the two arms being statistically identical; this phenomenon is typically referred to "incomplete learning" (see 126 24 for the original context). Non -on-neggny in the limiting distribution is also observable numerically up to diffusion-scale gaps of O (z)) under other versions of Thompson Sampling (see [32] for examples); our focus on the more extreme zero-gap setting simplifies the illustration of these effects.
A brief survey of Thompson Sampling. While extant literature does not provide any explicit result for Thompson Sampling characterizing its arm-sampling behavior in instances with "small" and "moderate" gaps, there has been recent work on its analysis in the A x 1/v'n regime under what is known as the diffusion approximation lens (see 32 12).. Cited works study Thompson Sampling primarily under the assumption that the prior variance associated with the mean reward of any arm vanishes in the horizon of play at an "appropriate" " rate f Such a scaling, however, is not ideal from regret standpoint and indeed, the versions of Thompson Sampling optimized for regret performance use fixed (non vanissninhing prior variances, e.g., Algorithm 2 and its Gaussian prior-based counterpart (see (2). On high level, [32 12| establish that as n co, the pre-limit (N((tt//))eej) (0 under Thompson Sampling converges weakly to a "diffusion-limit stochastic process on t E [o, 1]. Recall from earlier discussion that A x 1/v/i is covered under the "small gap" regime; consequently, it follows from Theorem I that the analogous limit for UCB is, in fact, the deterministic process t/2. In sharp contrast, the diffusion-limit process under Thompson Sampling may at best be characterizable only as a solution (possibly non-unique) to an appropriate stochastic differential equation or ordinary differential equation driven by suitably (random) time-changed Brownian motion. Consequently, the diffusion limit under Thompson Sampling is more difficult to interpret vis-â-vis UCB (see Theorem 4 and it is much harder to obtain lucid insights as the
nature of the distribution of (: /n as 71 + oc. The asymptotic distribution of Nn(n)/n under Thompson Sampling is also investigated in 191 albeit in a significantly different setting. Cited paper considers the Bayesian setting where prior distribution exists over problem instances, and the Thompson Sampling algorithm
"pecifid"""" i.e., information about said prior baked into the algorithm. Specifically, a sample path of the algorithm in their model involves a random problem instance from the instance-space. In contrast, the derivation of the asymptotic distribution of arm-pulls in our work is for specific (fixed) problem instances, viz., reward configurations (I) and (II) described in Theorem and under the classical version of Thompson Sampling (Algorithm
3.2 Beyond arm-sampling rates
This part of the paper is dedicated to a more fine- Aine-grained analysis of the "stochastic" regret of UCB (defined in ① in $ Results are largely facilitated by insights the sampling behavior of UCB in instances with "small" gaps, attributable to Theorem IT however, we believe they are of interest in their own right. We commence with an application of Theorem [ which provides the first complete characterization of the worst-case (minimax) performance of canonical UCB. A full diffusion-limit characterization of the two-armed bandit problem under UCB is provided thereafter in Theorem
'The only result applicable to the case of non vanishing prior variances is Theorem 4.2 of 12
8

---

Theorem (Minimax regret complexity of UCB) In the "moderate gap" regime referenced in
Theorem where A
lo the regret of the policy given by Algorithm with satisfies
R
VD - (1-x)(0)) =: =0)) as + 00,
(3)
vn
log
where x²(0) is the (unique) solution to
To the best of our knowledge, this is the first algorithu-specifcc result (sharp asymptotic) that is distinct from the general &t ( TV)) information theioottttcerticcc lower bound by a horizon-dependent factor
Discussion. A closed-fome form expression for (0) and (0) is provided in Appendix A The behavior of (0) is illustrated below in Figure 3 For a fixed p. the function (0) is numerically observed unique 0% == arg sup (0). bounded regret admits the
to be uni-modal in 0 and admit global maximum
away from O. Theorem Jestablishes that the worst-case
sharp asymptotic R, hp (0%) vn log n. In standard bandit parlance, this substantiates that the
0.5
0.5
0.5
0.4
044
0.4
h.00
0.00
0,00)
0.2
0.2
0
20
40
60
80
200
400
500
800
1000
2000
4000
6000
8000
10000
Figure 3: (0) vs. 0 for different values of the exploration coefficient in Algorithm ! The graphs exhibit a unique global maximizer 0r for each The (0- ht (0%)) pairs for p E {1.1, 4} in
that order are: (1.9, 0. 0.2367), (3.5, 0.3192), (5.3, 0.3909), (7, 0.4514).
O (Vnlogg ri) worst-case (minimax) performance guarantee of canonical UCB cannot be improved in terms of its horizon-dependence In addition, the result also specifies the precise asymptotic constants achievable in the worst-case setting. This can alternately be viewed as a direct approach to proving the O (Vn logn) performance bound for UCB vis-à-vis conventional minimax analyses such ?
/ [olo it follows from Theorem ER = ((0log /)/ [n N₂- (n)] ~ h (0) n log n (convergence in probability implies that 1). That HT also admits the same sharp asymptotic can be shown via a finer analysis. In other regimes of A, viz.. "small" and "large" gaps, we already know that R. = Op (vn log n). This obvious for "small" A since ER, & An ( (Vn log logn), while for "large" A, we use ER Cp ((log n) + 1/(p -11) 1)) for some absolute constant (given p > & 1) [6, followed by Markov's 's inequality. Thus, the multiplicative constant supa (0) obtained in the "moderate" gap regime must correspond to the worst-case performance of the algorithm. O
Proof sketch. On a high level, note that when
I that
in mean since |N;- (n)/nl
Towards diffusion asymptotics. Diffusion scaling is a classical stochastic analysis tecnnique widely used in the mathematics and operations research literature, see, e.g., steady-state analyses of queuing systems in (15), and a recent application to certain sequential testing problems in R. Under this lens, time is accelerated linearly n, space contracted by factor of /n, and a sequence of systems indexed by n considered. In our problem, the nthh such system refers to an instance of the two-armed bandit with: c; and fixed reward variances given by of. o3. This is a natural scaling for MAB experiments in that it "preserves" the hardness of the learning problem as n sweeps over the sequence of systems. Recall also from previous discussion that the "hardest" information-theoreti instances have a θ /n) gap; in short, the diffusion limit is an appropriate asymptotic lens for observing interesting process-level behavior in the MAB problem. However, despite the aforementioned reasons, the diffusion limit behavior of bandit algorithms remains poorly understood and largely unexplored. recent foray
the horizon of play; a gap that vanishes in the horizon A c/ /n for some fixed
'Previous work establishes matching è (VKn log K) regret of the Gaussian prior-based Thompson Sampling algorithm in the K K-areed problem, see 22]
upper and lower bounds for the minimax expected

---

was made in B2 12 however, deterministic algorithms like UCB remain outside the ambit of such analysis, on account of discontinuities. Theorem 4 provides a complete characterization of this limit.
Theorem 4 (Diffusion asymptotics for canonical UCB) Suppose that the mean reward of arm i E {1.2) given by 44 = μ + Bs/ Vn, where Tu the horizon of play and p. 0.01,0, 3 O are fixed constants, and reward variances are of 02. Define Do := |01 02). Denote the cumulative reward earned from arm i until time in by Si.m := -Lj=1 Xi.j. and let Sum == Si.m - -N.(m)) Then, the following process-level convergences hold under the policy a given by Algorithm 7 with p >>> 1:
(1)
S1
mt!
52.1me
02t
+
Ø1 1
(1),
Ozt
+
02 2 Ba(l))
Vn
Vni
2
V2
2
V2
R
[na]
Do!
o + + B(I),
+
2
2
where the process-level convergence is overt E [0, 1). and By (t) and B2(t) are independent standard Brownian motions in I, and B(t)
of of+i
B1 V 05 o (t)).
Proof sketch. Note that the arms are played [n/2] times each independently over the horizon of play n (resulting in (n) In/2]. i e {1,2)), part (I) of the stated assertion would immediately follow from Donsker's ' Theorem (see [8] Section 14). However, since the sequence of plays, and hence also the eventual allocation (n), N2 (n)), is determined adaptively by the policy, the aforementioned convergence may no longer be true. Here, the result hinges crucially on the observation from Theorem that for any arm i E {1,2} as n + oc, [,(n)/n & 1/2 under UCB when A x 1/vn (diffusion-scaled gaps are covered under the "small gap" regime). This observation facilitates a standard "random time-change" argument & <- (2(( i E (1,2), which followed upon by an application of Donsker's 's Theorem, leads to the stated assertion in (l). This has the profound implication that for diffusion-scaled gaps, a two-armed bandit under UCB is. in fact, aell-approximated by a classical system with independent samples due to the adaptive nature of the policy is washed away in the limit). The conclusion in (II) follows after a direct application of the Continuous Mapping Theorem (see [ Theorem 2.7) to (I).
Discussion. An immediate observation following Theorem 4 is that the normalized regret R is asymptotically Normal with mean 2n/2 and variance (o? oz) /2 under UCB. Apart from aiding in obvious inferential tasks like construction of (asymptotically valid) confidence intervals (see, e.g., the binary hypothesis testing example referenced in Figure 2()). etc., such information provides new insights as to the problem's 's minimax complexity as well. This is because A x 1/V7 is known "worst-case" for the problem; the smallest achievable regret in this regime must asymptotically be dominated by that under UCB, i.e., Aoynn/2 / It is also noteworthy that while the diffusion limit in Theorem ! does not itself depend on the exploration coefficient the rate which the system converges to said limit indeed depends on p. Theorem f will continue to hold only as long as w ((ogg log n) / /lgg n); for smaller P, the convergence of (n)n/n to 1 1/2 may no longer be true (refer to the proof of Theorem | in the "small" gap regime in Appendix
to be the information-thhorede
4 Concluding remarks and open problems
Our results for the two-armed problem under canonical UCB (Algorithm I may be generalizable to the K-armed setting, leveraging the observations and insights from Theorem | (a simple extension is provided in Appendix B The K-armed problem under UCB is of interest in its own right: we postulate a division of sampling effort within and across clusters of "similar" and "separated" arms, determined by their relative sub-optimality gaps in the spirit of Theorem [ We expect that similar generalizations are possible also for Theorem [ and Theorem 4 For Thompson Sampling, on the other hand, things are less obvious even in the two-armed setting. For example, in spite of compelling numerical evidence (refer, e.g., to Figure ()) suggesting a plausibly non-degenerate distribution of arm- samplinig rates for bounded rewards in [o. 1] with means away from 0, the proof of Theorem 2 relies heavily on the rewards being deterministic 0/1, and cannot be extended to the general case. In addition, similar results are conjectured also for the more widely used Gaussian prior-based version of the algorithm. Such results may, in future, shed light on several important diffusion- performance metrics of Thompson Sampling, and clucidate its normalized minimax (stochastic) regret behavior.
10

---

Acknowledgments and Disclosure of Funding
The authors sincerely thank the anonymous reviewers for their insightful remarks and constructive feedback on the initial submission, and hope that this revision satisfactorily addresses all their points. The authors declare an absence of any competing interests, financial or otherwise.
References
[1] AGRAWAL, S., AND GOYAL, N. Analysis of thompson sampling for the aulti-armed ban- dit problem. In Conference learning theory (2012), JMLR Workshop and Conference Proceedings, pp. 39-1.
[2] AGRAWAL, S., AND GOYAL, N. Near-optimal regret bounds for thompson sampling. Journal of the ACM (JACM) 64, 5 (2017), 1-24.
[3] ARAMAN, V. F., AND CALDENTEY, R. Diffusion approximations for class of sequential testing problems. arXiv preprint arXiv:2 102.07030 (2021).
[4] AUDIBERT, J.-Y., BUBECK, S., ET AL. Minimax policies for adversarial and stochastic bandits. In COLT (2009), vol. 7, pp. 1-122.
[5] AUDIBERT, J.-Y., BUBECK, S., AND MUNOS, R. Best arm identification in multi-armed bandits. In COLT (2010), pp. 41-53.
[6] AUDIBERT, J.-Y., MUNOS, R., AND SZEPESVÁRI, C. Exploration-exploitttio tradcoff using variance estimates in multi-armed bandits. Theoretical Computer Science 410, 19 (2009), 1876-1902.
[7] AUER, P.. CESA-BIANCHI, N., AND FISCHER, P. Finite-time analysis of the multiarmed bandit problem. Machine learning 47, 2-3 (2002), 235-256.
[8] BILLINGSLEY, P. Convergence of probability measures. John Wiley & Sons, 2013,
[9] BUBECK, S., AND CESA-BIANCHI, N. Regret analysis of stochastic and nonstochastic multi- armed bandit problems. arXiv preprint arXiv: 1204.572/ (2012).
[10] DESHPANDE, Y., MACKEY, L.., SYRGKANIS, V., AND TADDY, M. Accurate inference for adaptive linear models. arXiv preprint arXiv: (2017).
[11] DURRETT, R. Probability: theory and examples, vol. 49. Cambridge university press, 2019.
[12] FAN, L., AND GLYNN, P. W. Diffusion approximations for thompson sampling. arXiv preprint arXiv:2105.09232 (2021).
[13] GARIVIER, A., AND CAPPÉ, O. The kl-ucb algorithm for bounded stochastic bandits and beyond. In Proceedings of the 24th annual conference on learning theory (2011), pp. 359-376.
[14] GARIVIER, A., LATTIMORE, T., AND KAUFMANN, E. On saplore-then-comee strategies. In Advances in Neural Information Processing Systems (2016), pp. 784-792.
[15] GLYNN, P. W. Diffusion approximations. Handbooks in Operations research and management
Science 2 (1990), 198.
[16] HADAD, V., HIRSHBERG, D. A., ZIIAN, R., WAGER, S., AND ATHEY, S. Confidence intervals for policy evaluation in adaptive experiments. arXiv preprint arXiv: 1. (2019).
[17] HOEFFDING, W. Probability incqualities for sums of bounded random variables. Journal of the American Statistical Association 58, 301 (1963), 13-30.
[18] HONDA, J., AND TAKEMURA, A. An asymptotically optimal bandit algorithm for bounded support models. In COLT (2010), Citeseer, pp. 67-79.
[19] KALKANLI, C., AND OZGUR, A. Asymptotic convergence of thompson sampling. arXiv preprint arXiv:2011.0391 (2020).
[20] KALVIT, A.. AND ZEEVI, A. From finite countable-armed bandits. Advances in Neural Information Processing Systems 33 (2020), 8259-8269.
[21] KAUFMANN, F.,, CAPPÉ, O., AND GARIVTER, A. On the complexity of best-arm identification in multi-armed bandit models. The Journal of Machine Learning Research 17, I (2016). 1-42.
[22] LAI, L.., AND ROBBINS, Asymptotically efficient adaptive allocation rules. Advances in applied mathematics 6, (1985), 4-22.

---

[23] LATTIMORE, T., AND SZEPESVÁRI, C. Bandit algorithms. Cambridge University Press, 2020.
[24] McLENNAN, A. Price dispersion and incomplete learning in the long run. Journal of Economic dynamics and control 7, 3 (1984), 331-347.
[25] MEHRABI, N., MORSTATTER, F., SAXENA, N., LERMAN, K., AND GALSTYAN, A. A survey on bias and fairness in machine learning. arXiv preprini 1rXiv:1908. 1e...1908...33 (2019).
[26] ROTHSCHILD, M. A two-armed bandit theory of market pricing. Journal of Economic Theory 2 (1974), 185-202.
[27] SHIN, J., RAMDAS, A., AND RINALDO, A. Are sample means in multi-armed bandits positively or negatively biased? arXiv preprint arXiv: 1397 (2019).
[28] SHIN, J., RAMDAS, A., AND RINALDO, A. On the bias, risk and consistency of sample means in multi-armed bandits, arXiv preprint arXiv: 000::99020000 990.00746 (2019).
[29] SHIN, J., RAMDAS, A., AND RINALDO, A. On conditional versus marginal bias in multi-armed bandits. In International Conference on Machine Learning (2020), PMLR, pp. 8852-8861.
[30] THOMPSON, W. R. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika 25, 3/4 (1933), 285-294.
[3I] VILLAR, S. S., BOWDEN, J., AND WASON, J. Multi-armed bandit models for the optimal design of clinical trials: benefits and challenges. Statistical science: review journal of the Institute of Mathematical Statistics 30, 2 (2015), 199.
[32] WAGER, S., AND XU, K. Diffusion asymptotics for sequential experiments. arXiv preprint uxXiv2200.09985: (2021).
[33] ZHANG, K. W., JANSON, L., AND MURPHY, S. A. Inference for batched bandits. arXiv preprint 27X11:2002.003217 (2020).
Checklist
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] Detailed proofs are provided in the supplementary material.
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
12

---

(d) Did you discuss whether and how consent was obtained from people whose data you' re using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "pm_RS3rq2CH", "reviewer": "Reviewer_15pu", "summary": "The paper studies the arm sampling behavior of UCB and Thompson sampling algorithms. For the two-arm case, the asymptotic behavior of arm sampling is characterized for different regimes (small, large, and medium) of suboptimality gap. Using this characterization, the minimax regret of UCB is shown to O(n\\logn), where n is the time horizon. They highlight the incomplete learning phenomenon in Thomson sampling where sample-split could be arbitrarily imbalanced along a sample path even when both the arms have the same mean.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper highlights the important aspect of arm sampling distribution in the Multi-armed setting. The author nicely built the imbalances in arm sampling through examples for both UCB and Thompson sampling. The insights from the analysis highlight the 'incomplete learning' learning aspect in Thompson sampling.\n\nI have the following question for the authors: \n\nTheorem 1: The result holds aysmptotically and $\\Delta$ (problem instance) is changing with $n$. After $n$ rounds (sufficiently large), we expect UCB to have played the optimal arm exponentially more time than the sub-optimal arm. But the asymptotic result suggests that this need not be the case if $\\Delta \\rightarrow 0$ as $n \\rightarrow$. Can anything be said about the arm-sampling distribution for a fixed instance $\\Delta$. The asymptotic result is good, but since we also know finite time behavior, it is nice to connect.\n\nTheorem 2: What does the symbol $\\implies$ denote (convergence?). The statement assumes $n\\rightarrow \\infty$, but the Proof Sketch says for any $n \\in \\mathcal{N}$, which one is correct.\n\nTheorem 3: Does the result hold with weaker condition $\\Delta \\rightarrow 0$ Instead of thanking $\\Delta \\sim \\sqrt{\\frac{\\theta \\log n}{n}}$.\n\nOverall nice paper. Good insights. If authors could highlight the practical implications of their results, it could be nice. For example, is incomplete learning of Thompson Sampling good or bad. When should UCB be preferred over Thompson sampling and vice versa?\nDoes the incomplete learning aspect explain why Thompson sampling often performs better empirically in practice?\n\nI would be happy to revise the scores post rebuttal. \n-----\n\nPost rebuttal:\n\nThanks for clarifying some of my points. I have increased the score to 7.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "K8UhrYHsqZ5", "reviewer": "Reviewer_KzpM", "summary": "The authors study the asymptotic behavior of arm-sampling distributions under the UCB and the Thompson sampling. They provide an asymptotic characterization of the distributions, and show the arm sampling rates asymptotically deterministic regardless of the hardness of instances. With this characterization, focused on canonical UCB algorithm, they provides the first algorithm-specific worst case bound and the first diffusion-limit performance.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nOriginality:\nTo the best of my knowledge, this is the first work to provide algorithm-specific result (Theorem 3). Also, it is interesting that they provide another view of proving the worst-case performance of UCB using a diffusion scaling approach (Theorem 4). Although the paper is not the first work introducing the diffusion scaling to bandit problems, it can deal with more standard bandit algorithms. As for the originality of proof of Theorem 4, proof techniques seem to be similar to that of [25]. Is there any difficulty to apply a diffusion scaling technique to more standard bandit algorithms?\n\nQuality:\nThe proposed theorems seem to be technically sound. The authors honestly discuss about the strengths and weaknesses.\n\nClarity:\nThe paper is well-written and provides appropriate examples. I can easily follow the motivation. Since the diffusion scaling is a key technique of the main contribution, more descriptions about it helps us to understand the details of the contributions.\n\nSignificance:\nAs written in the originality, the provided results are the first works, which is the significant point of the paper. Since the works include some limitations that deals with two-armed bandit settings, it is an important first step to explore other bandit algorithms and settings .\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "A limitation of that paper is to deal with two-armed bandit settings, but as described in the concluding remarks in the paper, it may be generalized K-armed bandit. So, I think the contributions outweigh this drawback.\n\nI found the following researches that also consider the asymptotic regime using a diffusion approximation. It would be better to add some if possible.\n\nReferences:\n\n[i] Keisuke Hirano and Jack R Porter. Asymptotic representations for sequential experiments. Cowles Foundation Conference on Econometrics, 2021\n\n[ii] Fan, Lin, and Peter W. Glynn. \"Diffusion Approximations for Thompson Sampling.\" arXiv preprint arXiv:2105.09232 (2021).\n\n[iii] Araman, Victor F., and Rene Caldentey. \"Diffusion Approximations for a Class of Sequential Testing Problems.\" arXiv preprint arXiv:2102.07030 (2021).\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 hours"}, "extra_text": {}}, {"review_id": "Jok7EEtDcpV", "reviewer": "Reviewer_3P5t", "summary": "Classical bandit algorithms such as UCB and Thompson Sampling are well-understood in terms of their performance—for example, an upper bound on their regret—but, until recently, little attention has been given to their actual behavior—for example, the rates at which specific arms are sampled. This work seeks to address these questions by analyzing the arm sampling distribution achieved by both UCB and Thompson Sampling. They provide results characterizing these distributions asymptotically and, in addition, characterize the distribution of the rewards obtained by running UCB.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "While the regret incurred by UCB and Thompson Sampling (TS) is well-understood, this work seeks to understand the actual behavior of these algorithms. It makes several contributions in this direction, all in the two-armed bandit problem (though some of the results extend to K arms). In particular, they characterize the:\n- Asymptotic distribution of N_{I*}(n)/n achieved by UCB, where N_{I*}(n) is the number of pulls of the optimal arm up to time n, for various regimes of the gap.\n- Asymptotic distribution of N_{I*}(n)/n achieved by TS but in a restricted regime where the rewards are deterministic.\n- Precise regret incurred by UCB asymptotically, establishing that R_n -> c(\\theta)*\\sqrt{n log n} for some problem-dependent constant c(\\theta).\n- Distribution of the random process of the UCB’s reward and regret.\n\nAll results are asymptotic in nature (i.e. the number of samples n -> infinity). In addition, the authors provide several numerical examples illustrating that in practice UCB and TS can exhibit surprising behavior, and show that they are able to explain this behavior with their theoretical results.\n\nPros:\n- This is a timely work. In the last few years, a significant amount of attention has been given to understanding the asymptotically optimal regret of bandit problems (e.g. [4]), as well as properties of UCB (for example, the bias in the estimates of the arm means maintained by UCB [1]). Very recently [5] studied the asymptotic sampling distribution of Thompson Sampling but, to my knowledge, no other works on this exist, though open questions still remain.\n- The results are extensive and provide a full characterization of the behavior of the UCB algorithm, greatly deepening our understanding of its properties. The motivating examples help make clear that there are unusual and little-understood effects that occur when running UCB and TS.\n\nCons:\n- The main results only hold for a two-armed bandit model, though they are partially extended in the appendix to K armed models (the restriction to two-armed bandits has precedence in the literature though, for instance [4]). \n- The results on Thompson Sampling only holds for deterministic bandits. Furthermore, [5] studies the asymptotic distributions of the arm pulls of Thompson Sampling and should be cited and compared against. \n- There’s a line of recent work ([1]-[3]) which aims to understand the bias of optimistic bandit algorithms. While not directly comparable to this work, it is related to the theme of understanding the behavior of bandit algorithms, and should be cited.\n- Some discussion on the applications of these results would be interesting. For example, do these results motivate any improvements to UCB or other algorithms?\n\nOverall, this is a thorough study of the performance of bandit algorithms, greatly deepens our understanding of both UCB, and warrants an accept. \n\n----------------------------\n\nUpdate after rebuttal: I would like to maintain my score after reading the rebuttal. I believe this work makes fundamental, novel contributions to our understanding of bandits and deserves an accept.\n\n\n[1] Shin, Jaehyeok, Aaditya Ramdas, and Alessandro Rinaldo. \"Are sample means in multi-armed bandits positively or negatively biased?.\" arXiv preprint arXiv:1905.11397 (2019).\n[2] Shin, Jaehyeok, Aaditya Ramdas, and Alessandro Rinaldo. \"On the bias, risk and consistency of sample means in multi-armed bandits.\" arXiv preprint arXiv:1902.00746 (2019).\n[3] Shin, Jaehyeok, Aaditya Ramdas, and Alessandro Rinaldo. \"On conditional versus marginal bias in multi-armed bandits.\" International Conference on Machine Learning. PMLR, 2020.\n[4] Kaufmann, Emilie, Olivier Cappé, and Aurélien Garivier. \"On the complexity of best-arm identification in multi-armed bandit models.\" The Journal of Machine Learning Research 17.1 (2016): 1-42.\n[5] Kalkanli, Cem, and Ayfer Ozgur. \"Asymptotic Convergence of Thompson Sampling.\" arXiv preprint arXiv:2011.03917 (2020).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors do not discuss potential societal impact. However, the work is primarily theoretical so it is difficult to determine what negative societal impacts it may have. Limitations are discussed. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "-qDRi_Jh5oW", "reviewer": "Reviewer_SFdh", "summary": "The paper studies the asymptotical behaviors (with respect to the suboptimality gap $\\Delta$) of key statistics in the standard upper confidence bound (UCB) algorithm in standard multi-armed bandits (MAB). The contributions are as follows.\n\n1. The paper proves that the **asymptotical arm-sampling rate** converges to a constant, and gives its **analytical form** (Eq. 2). In particular, the paper discovers a non-trivial \"**moderate gap**\" regime for UCB. \n2. The paper proves an asymptotic regret lower bound for UCB **up to $(1 + o(1))$**  in two-armed bandits. \n3. The paper proves that the **asymptotical empirical sum** converges to a Brownian motion for UCB in two-armed bandits.\n4. The paper proves the asymptotical arm-sampling rate for Bernoulli Thompson sampling in two-armed *deterministic* bandits. \n5. The authors extend their results to MAB.", "questions": "", "limitations": "", "rating": 9, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nWhile asymptotical analyses are common in statisics and EE (e.g. mean-field asymptotics), it is not common in CS and rare in bandits literature. Asympotical analyses are important because it could help both researchers and practitioners better understand the algorithmic behaviors, because non-asymptotic analyses are usually not as exact and precise as their asymptotical counterparts. \n\nThis paper studies two-armed bandits, the classical and fundamental task in bandits literature, and analyzes UCB, the classical and fundamental algorithm in bandits literature. The most important statistics maintained by the UCB algorithm are the number of times of each arm being pulled and the empirical sum of each arm. For these two statistics, the paper provides exact asymptotical characterization under the simplest two-armed bandits case, which clearly distinguishes this paper from previous papers. The results are significant and set up seminal directions in bandits literature, and could benefit subsequent researchers, including myself. I believe the related works are cited adequately. \n\n\nThe paper is very well-written. The maths are easy to read and can be clearly verified in a step-by-step manner. I went through Appendices E and F (which contains main technical proofs) and did not find apparent errors. The authors are honest about their weakness about their results in the final section. \n\nThe paper almost completely depicts how standard UCB works in two-armed bandits. The results on other tasks such as multi-armed bandits and other algorithms such as Thompson sampling are, however, still premature. Further will be discussed in the limitations section. Nonetheless, given the novelty, quality, and clarity of this submission, I vote for a strong accept.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "\n### Limitations\n\n1. The authors' notations confuse me, in that it's not clear that *which limiting regime* the authors are discussing. It seems to me that Theorem 1 is stated for a sequence of two-armed bandits instances, i.e. for each $n$, there's an instance with parameters $(\\mu_{1, n}, \\mu_{2, n})$ such that $\\Delta_n = \\mu_{1, n} - \\mu_{2, n}$ satisfies $\\Delta_n \\asymp 1/\\sqrt{n}$, and that the $N_{i^*}(n) / n$ term in the result of Theorem 1 refers to the $N_{i^*}(n) / n$ in the $n$-th instance. The confusions exist at least for Theorem 1, 3, 4. Since asymptotical style results are not common in bandits literature, I recommend the authors to point out the asymptotical regime more clearly. \n2. The paper includes numerical experiments, so I think the section 3 in the checklist (Line 436) shall not be completed by \"N/A\", and the authors are encouraged to publish their codes, (though numerical experiments might be very simple).\n3. The paper fails to fully extend the results (Theorems 1, 3, 4) to the MAB case. The two-armed case is limited from both theoretical and practical perspective. In particular, in the two-armed case, the arm pulling rates satisfy $N_1(n) = n - N_2(n)$, which makes it possible to fully characterize the bandits by only analyzing one statistics $N_1(n)$. However, in the multi-armed case, at least two statistics need be studied. The paper did not prove the most intriguing \"moderate gap\" part in the multi-armed case.  \n4. The paper's results on Thompson sampling are quite limited, in that it only studies the deterministic case where rewards are constantly $0$ or $1$ for each arm. Although the authors somehow suggest that the results should extend to the stochastic setting by doing experiments (Fig. 1), I am still concerned about the results.  \n\n### Other Comments\n\n* Line 128: \"diffuion-limit\" should be \"diffusion-limit\"\n* Line 144-145: The sentence almost repeats the same sentence at Line 137-138, same thing at Line 149-150; the authors need not repeat the claim of first characeterization three times in the same paragraph\n\n### Societal Impact\n\nThe paper is mainly theoretical, and I don't see any potential negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This is strong paper that I would like to see accepted as a spotlight. There is a minor criticism concerning the restriction to two arms but the reviewers feel that this is not a major concern. There are some suggestions by the reviewers of how to improve the paper further and it would be good if the authors could incorporate these.  
Decision: Accept (Spotlight)