summaries: 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. 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. 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.  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.  1. 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.  2. The paper proves an asymptotic regret lower bound for UCB **up to $(1 + o(1))$**  in two-armed bandits.  3. The paper proves that the **asymptotical empirical sum** converges to a Brownian motion for UCB in two-armed bandits. 4. The paper proves the asymptotical arm-sampling rate for Bernoulli Thompson sampling in two-armed *deterministic* bandits.  5. The authors extend their results to MAB.
abstractText: 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 p 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 p n log n minimax regret of UCB. Furthermore, the paper also provides the first complete process-level characterization of the MAB problem under UCB 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.
authors.name: Anand Kalvit
references.authors: S. AGRAWAL N. GOYAL
references.title: Analysis of thompson sampling for the multi-armed bandit problem
references.venue: In Conference on learning theory
references.authors: S. AGRAWAL N. GOYAL
references.title: Near-optimal regret bounds for thompson sampling
references.venue: Journal of the ACM (JACM) 64,
references.authors: V.F. ARAMAN R. CALDENTEY
references.title: Diffusion approximations for a class of sequential testing problems
references.venue: arXiv preprint
references.authors: AUDIBERT J.-Y S BUBECK
references.title: Minimax policies for adversarial and stochastic bandits
references.venue: In COLT (2009),
references.authors: AUDIBERT J.-Y S. BUBECK R. MUNOS
references.title: Best arm identification in multi-armed bandits
references.venue: COLT
references.authors: AUDIBERT J.-Y R. MUNOS C. SZEPESVÁRI
references.title: Exploration–exploitation tradeoff using variance estimates in multi-armed bandits
references.venue: Theoretical Computer Science 410,
references.authors: P. AUER N. CESA-BIANCHI P. FISCHER
references.title: Finite-time analysis of the multiarmed bandit problem
references.venue: Machine learning 47,
references.authors: P. BILLINGSLEY
references.title: Convergence of probability measures
references.authors: S. BUBECK N. CESA-BIANCHI
references.title: Regret analysis of stochastic and nonstochastic multiarmed bandit problems
references.venue: arXiv preprint arXiv:1204.5721
references.authors: Y. DESHPANDE L. MACKEY V. SYRGKANIS M. TADDY
references.title: Accurate inference for adaptive linear models
references.venue: arXiv preprint arXiv:1712.06695
references.authors: L. FAN P.W. GLYNN
references.title: Diffusion approximations for thompson sampling
references.venue: arXiv preprint arXiv:2105.09232
references.authors: A. GARIVIER O. CAPPÉ
references.title: The kl-ucb algorithm for bounded stochastic bandits and beyond
references.venue: In Proceedings of the 24th annual conference on learning theory
references.authors: A. GARIVIER T. LATTIMORE E. KAUFMANN
references.title: On explore-then-commit strategies
references.venue: In Advances in Neural Information Processing Systems
references.authors: P.W. GLYNN
references.title: Diffusion approximations. Handbooks in Operations research and management
references.venue: Science
references.authors: V. HADAD D.A. HIRSHBERG R. ZHAN S. WAGER S. ATHEY
references.title: Confidence intervals for policy evaluation in adaptive experiments
references.authors: W. HOEFFDING
references.title: Probability inequalities for sums of bounded random variables
references.venue: Journal of the American Statistical Association
references.authors: J. HONDA A. TAKEMURA
references.title: An asymptotically optimal bandit algorithm for bounded support models
references.venue: COLT
references.authors: C. KALKANLI A. OZGUR
references.title: Asymptotic convergence of thompson sampling
references.venue: arXiv preprint arXiv:2011.03917
references.authors: A. KALVIT A. ZEEVI
references.title: From finite to countable-armed bandits
references.venue: Advances in Neural Information Processing Systems
references.authors: E. KAUFMANN O. CAPPÉ A. GARIVIER
references.title: On the complexity of best-arm identification in multi-armed bandit models
references.venue: The Journal of Machine Learning Research 17,
references.authors: T.L. LAI H. ROBBINS
references.title: Asymptotically efficient adaptive allocation rules
references.venue: Advances in applied mathematics 6,
references.authors: T. LATTIMORE
references.title: AND SZEPESVÁRI, C. Bandit algorithms
references.authors: A. MCLENNAN
references.title: Price dispersion and incomplete learning in the long run
references.venue: Journal of Economic dynamics and control 7,
references.authors: N. MEHRABI F. MORSTATTER N. SAXENA K. LERMAN A. GALSTYAN
references.title: A survey on bias and fairness in machine learning
references.authors: M. ROTHSCHILD
references.title: A two-armed bandit theory of market pricing
references.venue: Journal of Economic Theory 9,
references.authors: J. SHIN A. RAMDAS A. RINALDO
references.title: Are sample means in multi-armed bandits positively or negatively biased
references.venue: arXiv preprint arXiv:1905.11397
references.authors: J. SHIN A. RAMDAS A. RINALDO
references.title: On the bias, risk and consistency of sample means in multi-armed bandits
references.authors: J. SHIN A. RAMDAS A. RINALDO
references.title: On conditional versus marginal bias in multi-armed bandits
references.venue: In International Conference on Machine Learning (2020),
references.authors: W.R. THOMPSON
references.title: On the likelihood that one unknown probability exceeds another in view of the evidence of two samples
references.venue: Biometrika 25,
references.authors: S.S. VILLAR J. BOWDEN J. WASON
references.title: Multi-armed bandit models for the optimal design of clinical trials: benefits and challenges
references.venue: Statistical science: a review journal of the Institute of Mathematical Statistics 30,
references.authors: WAGER S XU
references.title: Diffusion asymptotics for sequential experiments
references.venue: arXiv preprint arXiv:2101.09855
sections.text: p 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 p n log n minimax regret of UCB. Furthermore, the paper also provides the first complete process-level characterization of the MAB problem under UCB 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.
sections.heading: 1 Introduction
sections.text: Background and motivation. The MAB paradigm provides a succinct abstraction of the quintessential exploration vs. 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 earliest known MAB heuristic, Thompson Sampling [1]. 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 [9] for a comprehensive survey of different formulations). In the canonical stochastic MAB problem, a decision maker (DM) pulls one of K arms sequentially at each time t 2 {1, 2, ...}, and receives a random payoff drawn according to an arm-dependent distribution. The DM, oblivious to the statistical properties of the arms, must balance exploring new arms 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 regret 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)16i6K , n ⌘ , where Pi denotes the distribution of rewards associated with the ith arm, and n the horizon of play.
  The statistical complexity of regret minimization in the stochastic MAB problem is governed by a key primitive called the gap, denoted by , which accounts for the difference between the top two arm mean rewards in the problem. For a “well-separated” or “large gap” instance, i.e., a fixed bounded away from 0, the seminal paper [22] showed that the order of the smallest achievable regret
  35th Conference on Neural Information Processing Systems (NeurIPS 2021).
  is logarithmic in the horizon. There has been a plethora of subsequent work involving algorithms which can be fine-tuned to achieve a regret arbitrarily close to the optimal rate discovered in [22] (see [6, 14, 13, 2, 4], etc., for a few notable examples). On the other hand, no algorithm can achieve an expected regret smaller than C p n for a fixed n (the constant hides dependence on the number of arms) uniformly over all problem instances (also called minimax regret); see, e.g., [23], Chapter 15. The saddle-point in this minimax formulation occurs at a gap that satisfies ⇣ 1/ p n. This has a natural interpretation: approximately 1/ 2 samples are required to distinguish between two distributions with means separated by ; at the 1/ p n-scale, it becomes statistically impossible to distinguish between samples from the top two arms within n rounds of play. If the gap is smaller, despite the increased difficulty in the hypothesis test, the problem becomes “easier” from a regret perspective. Thus, ⇣ 1/ p n is the statistically “hardest” scale for regret minimization. A number of popular algorithms achieve the p n minimax-optimal rate (modulo constants), see, e.g., [4, 2], and many more do this within poly-logarithmic factors in n. Many of these are variations of the celebrated upper confidence bound algorithms, e.g., UCB1 [7], that achieve a minimax regret of O p n log n , and at the same time also deliver the logarithmic regret achievable in the instance-dependent setting of [22].
  A major driver of the regret performance of an algorithm is its arm-sampling characteristics. For example, in the instance-dependent (large gap) setting, optimal regret guarantees imply that the fraction of time the optimal arm(s) are played approaches 1 in probability, as n grows large. However, this fails to provide any meaningful insights as to the distribution of arm-pulls for smaller gaps, e.g., the ⇣ 1/ p n “small gap” that governs the “worst-case” instance-independent setting.
  An illustrative numerical example involving “small gap.” Consider an A/B testing problem (e.g., a vaccine clinical trial) where the experimenter is 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., [5]). In other words, algorithms tailored for (cumulative) regret minimization may lack statistical power [31]. While this trade-off is unavoidable in “well-separated” instances, numerical evidence suggests a plausible resolution in instances with “small” gaps as illustrated below. For example, such a situation might arise in trials conducted using two similarly efficacious vaccines (abstracted away as ⇡ 0). To illustrate the point more vividly, consider the case where is exactly 0 (of course, this information is not known to the experimenter). This setting is numerically illustrated in Figure 1, which shows the empirical distribution of N1(n)/n (the fraction of time arm 1 is played until time n) in a two-armed bandit with = 0, under two different algorithms (UCB and Thompson Sampling), and reward configurations.
  A desirable property of the outcome in this setting is to have a linear allocation of the sampling budget per arm on almost every sample-path of the algorithm, as this leads to “complete learning:” an algorithm’s ability to discern statistical indistinguishability of the arm-means, and induce a “balanced” allocation in that event. However, despite the simplicity of the zero-gap scenario, it is far from obvious whether the aforementioned property may be satisfied for standard bandit algorithms such as UCB and Thompson Sampling. Indeed, Figure 1 exhibits a striking difference between the two. The concentration around 1/2 observable in Figure 1(a) indicates that UCB results in an approximately “balanced” sample-split, i.e., the allocation is roughly n/2 per arm for large n
  (and this is observed for “most” sample-paths). In fact, we will later see that the “bell curve” in Figure 1(a) eventually collapses into the Dirac measure at 1/2 (Theorem 1). 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 1(b) (see, for contrast, Figure 1(c), where the allocation is perfectly “balanced”). Namely, the distribution of the posterior may be such that arm 1 is allocated anywhere from almost no sampling effort all the way to receiving almost the entire sampling budget, as Figure 1(b) 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 an instructional example of a 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 a model where arm 1 returns a constant reward of 0.5, while arm 2 yields rewards distributed as Bernoulli(0.5). In this setup, the estimate of the gap (average treatment effect in causal inference parlance) after n rounds of play is given by ̂ = X̄2(n) 0.5, where X̄2(n) denotes the empirical mean reward of arm 2 at time n. The Z statistic associated with this gap estimator is given by Z = 2 p N2(n)̂, where N2(n) is the visitation count of arm 2 at time n. In the absence of any sample-adaptivity in the arm 2 data, results from classical statistics such as the Central Limit Theorem (CLT) would posit an asymptotically Normal distribution for Z . However, since the algorithms that play the arms are adaptive in nature, e.g., UCB and Thompson Sampling, asymptotic-normality may no longer be guaranteed. Indeed, the numerical evidence in Figure 2(b) strongly points to a significant departure from asymptotic-normality of the Z statistic associated with the gap estimator under Thompson Sampling (TS). Non-normality of the Z statistic can be problematic for inferential tasks, e.g., it can lead to statistically unsupported inferences in the binary hypothesis test H0 : = 0 vs. H1 : 6= 0 performed using confidence intervals constructed as per the conventional CLT approximation. In sharp contrast, our work shows that UCB satisfies a certain “balanced” sampling property (such as that in Figure 1(a)) in instances with “small” gaps, formally stated as Theorem 1, that drives the Z statistic towards asymptoticnormality in the aforementioned binary hypothesis testing example (asymptotic-normality being a consequence of Theorem 4). Furthermore, since the p n-normalized “stochastic” regret (defined in (1) in §2) equals ⇣p N2(n)/(4n) ⌘ Z , it follows that this too, satisfies asymptotic-normality under
  UCB (due to Theorem 4, in conjunction with Theorem 1). These properties are evident in Figure 2(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 2(b) suggests.
  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, a recent line of work ([27, 28, 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 on
  ex post causal inference from data collected adaptively by bandit algorithms (see, e.g., [33, 16, 32], etc., and references therein for recent developments), algorithmic fairness in the broader context of fairness in machine learning (see [25] for a survey), as 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 under a parametric family of UCB algorithms. However, as the gap diminishes, leading to the so called small gap regime, the aforementioned bounds become vacuous. The understanding of armsampling behavior remains relatively under-studied here even for popular algorithms such as UCB and Thompson Sampling. This regime is of special interest in that it also covers the classical diffusion scaling1, where ⇣ 1/ p n, which as discussed earlier, corresponds to instances that statistically constitute the “worst-case” for hypothesis testing and regret minimization. Recently, a partial diffusion-limit characterization of the arm-sampling distribution under a version of Thompson Sampling with horizon-dependent prior variances2, was provided in [32] 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 [10, 20], 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 is bounded away from 0 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 armsampling distributions under canonical UCB (Algorithm 1) as a function of the gap (Theorem 1). 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 1, as well as a sharp dichotomy between Thompson Sampling and UCB evident therein (Theorem 2). This result earmarks an “instability” of Thompson Sampling in terms of the limiting arm-sampling distribution. As a sequel to Theorem 1, we provide the first complete characterization of the worst-case performance of canonical UCB (Theorem 3). One consequence is that the O p n log n minimax regret of UCB is strictly unimprovable in a precise sense. Moreover, our work also leads to the first process-level characterization of the two-armed bandit problem under canonical UCB in the classical diffusion limit, according to which a suitably normalized cumulative reward process converges in law to a Brownian motion with fully characterized drift and infinitesimal variance (Theorem 4). To the best of our knowledge, this is the first such characterization of UCB-type algorithms. Theorem 4 facilitates a complete distribution-level characterization of UCB’s diffusion-limit regret, thereby providing sharp insights as to the problem’s minimax complexity. Such distribution-level 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 2(c)), 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 ([6, 9, 2]), 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 is provided in §2. All theoretical propositions are stated in §3, along with a 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 §4.
sections.heading: 2 The model and notation
sections.text: 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
  1This is a standard technique for performance evaluation of stochastic systems, commonly used in the operations research and mathematics literature, see, e.g., [15].
  2Assumed to be vanishing in n; standard versions of the algorithm involve fixed (positive) prior variances.
  analyses, see, e.g., [21]. 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 limn!1 f(n)g(n) = 0. Similarly, f(n) =
  O (g(n)) or g(n) = ⌦ (f(n)) if lim supn!1 f(n)g(n) 6 C for some constant C. If f(n) = O ((g(n))) and f(n) = ⌦ ((g(n))) hold simultaneously, we say f(n) = ⇥ (g(n)), or f(n) ⇣ g(n), and we write f(n) ⇠ g(n) in the special case where limn!1 f(n)g(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, f(n) = op (g(n)) if f(n)/g(n)
  p ! 0 as n!1. Lastly, the notation ‘)’ will be used for weak convergence. The model. The arms are indexed by {1, 2}. Each arm i 2 {1, 2} is characterized by a reward distribution Pi supported on [0, 1] with mean µi. The difference between the two mean rewards, aka the gap, is given by = |µ1 µ2|; as 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,j)16j6m. The rewards are assumed to be i.i.d. in time, and independent across arms.3 The number of pulls of arm i up to (and including) time t is denoted by Ni(t). A policy ⇡ := (⇡t)t2N is an adapted sequence that prescribes pulling an arm ⇡t 2 S at time t, where S denotes the probability simplex on {1, 2}. The natural filtration at time t is given by Ft := n (⇡s)s6t , ⇣ (Xi,j)j6Ni(t) : i = 1, 2 ⌘o . The stochastic regret of policy ⇡ after n plays, denoted by R⇡n, is given by
  R⇡n := nX
  t=1
  ⇥ max (µ1, µ2) X⇡t,N⇡t (t) ⇤ . (1)
  The decision maker is interested in the problem of minimizing the expected regret, given by
  inf ⇡2⇧
  ER⇡n,
  where ⇧ is the set of policies satisfying the non-anticipation property ⇡t : Ft 1 ! S, 1 6 t 6 n, and the expectation is w.r.t. the randomness in reward realizations as well as possible randomness in the policy ⇡. In this paper, we will focus primarily on the canonical UCB policy given by Algorithm 1 below. This policy is parameterized by an exploration coefficient ⇢, which controls its arm-exploring rate. The standard UCB1 policy [7] corresponds to Algorithm 1 with ⇢ = 2; the effect of ⇢ on the expected and high-probability regret bounds of the algorithm is well-documented in [6] for problems with a “large gap.” In what follows, X̄i(t 1) denotes the empirical mean reward from arm i 2 {1, 2} at time t 1, i.e., X̄i(t 1) := PNi(t 1)
  j=1 Xi,j Ni(t 1) .
  Algorithm 1 The canonical UCB policy for two-armed bandits. 1: Input: Exploration coefficient ⇢ 2 R+. 2: At t = 1, 2, play each arm i 2 {1, 2} once. 3: for t 2 {3, 4, ...} do 4: Play arm ⇡t 2 argmaxi2{1,2} ⇣ X̄i(t 1) + q ⇢ log(t 1) Ni(t 1) ⌘ .
sections.heading: 3 Main results
sections.text: Algorithm 1 is known to achieve ER⇡n = O (log n) in the instance-dependent setting, and ER⇡n = O p n log n in the “small gap” minimax setting. The primary focus of this paper is on the distribution of arm-sampling rates, i.e., Ni(n)/n, i 2 {1, 2}. Our main results are split across two sub-sections; §3.1 examines the behavior of UCB (Algorithm 1) 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 1 under the ⇣ p (log n) /n “worst-case” gap and the ⇣ 1/ p n “diffusion-scaled” gap. 3These assumptions can be relaxed in the spirit of [7]; our results also extend to sub-Gaussian rewards.
sections.heading: 3.1 Asymptotics of arm-sampling rates
sections.text: Theorem 1 (Arm-sampling rates under UCB) Let i⇤ 2 argmax {µi : i = 1, 2} with ties broken arbitrarily. Then, the following results hold for arm i⇤ as n!1 under Algorithm 1 with ⇢ > 1:
  (I) “Large gap:” If = ! ✓q
  logn n ◆ , then Ni⇤(n)/n p ! 1.
  (II) “Small gap:” If = o ✓q
  logn n ◆ , then Ni⇤(n)/n p ! 1/2.
  (III) “Moderate gap:” If ⇠ q
  ✓ logn n for some fixed ✓ > 0, then Ni⇤(n)/n p ! ⇤⇢(✓), where the limit is the unique solution (in ) to
  1p 1
  1p =
  s ✓
  ⇢ , (2)
  and is monotone increasing in ✓, with ⇤⇢(0) = 1/2 and ⇤⇢(✓)! 1 as ✓ !1.
  Remark 1 (Permissible values of ⇢ in Algorithm 1) For ⇢ > 1, the expected regret of the policy ⇡ given by Algorithm 1 is bounded as ER⇡n 6 C⇢ ⇣ logn +
  ⇢ 1
  ⌘ for some absolute constant C > 0;
  the upper bound becomes vacuous for ⇢ 6 1 (see [6], Theorem 7). We therefore restrict Theorem 1 to ⇢ > 1 to ensure that ER⇡n remains non-trivially bounded for all .
  Discussion and intuition. Theorem 1 essentially asserts that the sampling rates Ni(n)/n, i 2 {1, 2} are asymptotically deterministic in probability under canonical UCB; only serves to determine the value of the limiting constant. The “moderate” gap regime offers a continuous interpolation from instances with zero gaps to instances with “large” gaps as ✓ sweeps over R+ in that ⇤⇢(✓) increases monotonically from 1/2 at ✓ = 0 to 1 at ✓ =1, consistent with intuition. The special case of ✓ = 0 is numerically illustrated in Figure 1(a). The tails of Ni⇤(n)/n decay polynomially fast near the end points of the interval [0, 1] with the best possible rate approaching O n 3 , occurring for ✓ = 0.
  However, as Ni⇤(n)/n approaches its limit, convergence becomes slower and is dominated by fatter ⇥ ⇣q
  log logn logn
  ⌘ tails. The behavior in this regime is regulated by the O p n log log n envelope of
  the zero-drift random walk process driving the algorithm’s regret (see proof of Theorem 1 for details).
  Proof sketch. To provide the most intuitive explanation, we pivot to the special case where the arms have identical reward distributions, and in particular, = 0. The natural candidate then for the limit of the empirical sampling rate is 1/2. On a high level, the proof relies on polynomially decaying bounds in n for ✏-deviations of the form P ⇣ N1(n)n 1 2 > ✏ ⌘
  derived using the standard trick for bounding the number of pulls of any arm on a given sample-path, to wit, for any u, n 2 N, N1(n) can be bounded above by u + Pn t=u+1 {⇡t = 1, N1(t 1) > u}, path-wise. Setting u = d(1/2 + ✏)ne in this expression, one can subsequently show via an analysis involving careful use of the policy structure together with appropriate Chernoff bounds that with high probability (approaching 1 as n ! 1), N1(n)/n 6 1/2 + "⇢ for some "⇢ 2 (0, 1/2) that depends only on ⇢. An identical result would naturally hold also for the other arm by symmetry arguments, and therefore we arrive at a meta-conclusion that Ni(n)/n > 1/2 "⇢ > 0 for both arms i 2 {1, 2} with high probability (approaching 1 as n ! 1). It is noteworthy that said conclusion cannot be arrived at for an arbitrary ✏ > 0 (in place of "⇢) since the polynomial upper bounds on P ⇣ N1(n)n 1 2 > ✏ ⌘
  derived using the aforementioned path-wise upper bound on N1(n), become vacuous if u is set “too close” to n/2, i.e., if ✏ is “near” 0. Extension to the full generality of ✏ > 0 is achieved via a refined analysis that uses the Law of the Iterated Logarithm (see [11], Theorem 8.5.2), together with the previous meta-conclusion, to obtain fatter O ⇣q log logn logn ⌘ tail bounds when ✏ is near 0. Here, it is imperative to point out that the “log n” appearing in the denominator is essentially from the p ⇢ log t optimistic bias term of UCB (see Algorithm 1), and therefore the convergence will, as such, hold also for other variations of the policy that have “less aggressive” ! (log log t) exploration functions vis-àvis log t. However, this will be achieved at the expense of the policy’s expected regret performance,
  as noted in Remark 1. We also note that the extremely slow O ⇣q
  log logn logn
  ⌘ convergence is not an
  artifact of our analysis, but in fact, supported by the numerical evidence in Figure 1(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 a deterministic limit under UCB à la Theorem 1 (see, e.g., [10] and references therein). The proof for a general in the “small” and “moderate” gap regimes is skeletally similar to that for = 0, albeit guessing a candidate limit for Ni⇤(n)/n is non-trivial; a closed-form expression for ⇤⇢(✓) is provided in Appendix A. Full details of the proof of Theorem 1 are provided in Appendix D,E,F. ... ⇤
  Remark 2 (Possible generalizations of Theorem 1) A simple extension to the K-armed setting is provided in Appendix B as Theorem 5. The behavior of UCB policies is largely governed by their optimistic bias. While Theorem 1 only covers the generic UCB policy with p ⇢ log t bias, results of the form Ni(n)/n p ! ci for some ci 2 (0, 1) continue to hold also under smaller ! p ⇢ log log t 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 [13], DMED [18], etc.
  What about Thompson Sampling? Results such as those discussed above for other popular adaptive algorithms like Thompson Sampling4 are only arable in “well-separated” instances where Ni⇤(n)/n p ! 1 as n ! 1 follows as a trivial consequence of its O ( p n) 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-studied 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 1(b) and 1(c). This result also offers an explanation for the sharp contrast with the statistical behavior of canonical UCB (Algorithm 1) à la Theorem 1, also evident from Figure 1(a). In what follows, rewards are assumed to be Bernoulli, and Si (respectively Fi) counts the number of successes/1’s (respectively failures/0’s) associated with arm i 2 {1, 2}.
  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 2 {1, 2}, (Si, Fi) = (0, 0). 2: for t 2 {1, 2, ...} do 3: Sample for each i 2 {1, 2}, Ti ⇠ Beta (Si + 1, Fi + 1). 4: Play arm ⇡t 2 argmaxi2{1,2} Ti and observe reward rt 2 {0, 1}. 5: Update success-failure counts: S⇡t S⇡t + rt, F⇡t F⇡t + 1 rt.
  Theorem 2 (Incomplete learning under Thompson Sampling) In a two-armed model where both arms yield rewards distributed as Bernoulli(q), the following holds under Algorithm 2 as n!1:
  (I) If q = 0, then N1(n)/n) 1/2.
  (II) If q = 1, then N1(n)/n) Uniform distribution on [0, 1].
  Proof sketch. The proof of Theorem 2 relies on a careful application of two subtle properties of the Beta distribution (Fact 2 and Fact 3), stated and proved in Appendix C,K. For part (I), we invoke symmetry to deduce EN1(n) = n/2, and use Fact 2 to show that the standard deviation of N1(n) is sub-linear in n, thus proving the stated assertion in (I). More elaborately, Fact 2 states for the reward configuration in (I) that the probability of playing arm 1 after it has already been played n1 times, and arm 2 n2 times, equals (n2 + 1) /(n1 +n2 +2). This probability is smaller than 1/2 if n1 > n2, which provides an intuitive explanation for the fast convergence of N1(n)/n to 1/2 observed in Figure 1(c). 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 n 2 N. Contrary to Fact 2, Fact 3 states that quite the opposite is true for the reward configuration in (II): the probability of playing arm 1 after it has already been played n1 times, and arm 2 n2 times, equals (n1 + 1) /(n1+n2+2), which is greater than 1/2 when n1 > n2. That is, the posterior distributions
  4This is the version based on Gaussian priors and Gaussian likelihoods, not the classical version based on Beta priors and Bernoulli likelihoods which has a minimax regret of O p n log n [2].
  evolve in such a 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 a perpetual “imbalance” in the sample-counts. This provides an intuitive explanation for the non-degeneracy observed in Figure 1(b) and 2(a), which additionally, also indicates that such behavior, in fact, persists also for general (non-deterministic) 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 a (1/2, 1/2) sample-split in probability (Theorem 1). On the other hand, Theorem 2 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 aforementioned claim is, in fact, borne out by the numerical evidence in Figure 1(b) and 1(c). The sampling distribution seemingly flattens rapidly from the Dirac measure at 1/2 to the Uniform 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, a uniform distribution of arm-sampling rates on [0, 1] indicates that the sample-split could be arbitrarily imbalanced along a sample-path, despite, as in the setting of Theorem 2, the two arms being statistically identical; this phenomenon is typically referred to as “incomplete learning” (see [26, 24] for the original context). Non-degeneracy in the limiting distribution is also observable numerically up to diffusion-scale gaps of O (1/ p n) 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 ⇣ 1/ p 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.5 Such a scaling, however, is not ideal from a regret standpoint and indeed, the versions of Thompson Sampling optimized for regret performance use fixed (non-vanishing) prior variances, e.g., Algorithm 2 and its Gaussian prior-based counterpart (see [2]). On a high level, [32, 12] establish that as n ! 1, the pre-limit (Ni(nt)/n)t2[0,1] under Thompson Sampling converges weakly to a “diffusion-limit” stochastic process on t 2 [0, 1]. Recall from earlier discussion that ⇣ 1/ p n is covered under the “small gap” regime; consequently, it follows from Theorem 1 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 a 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 to the nature of the distribution of Ni(n)/n as n ! 1. The asymptotic distribution of Ni(n)/n under Thompson Sampling is also investigated in [19], albeit in a significantly different setting. Cited paper considers the Bayesian setting where a prior distribution exists over problem instances, and the Thompson Sampling algorithm is “well-specified,” i.e., information about said prior is 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 2, and under the classical version of Thompson Sampling (Algorithm 2).
sections.heading: 3.2 Beyond arm-sampling rates
sections.text: This part of the paper is dedicated to a more fine-grained analysis of the “stochastic” regret of UCB (defined in (1) in §2). Results are largely facilitated by insights on the sampling behavior of UCB in instances with “small” gaps, attributable to Theorem 1; however, we believe they are of interest in their own right. We commence with an application of Theorem 1 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 4.
  5The only result applicable to the case of non-vanishing prior variances is Theorem 4.2 of [12].
  Theorem 3 (Minimax regret complexity of UCB) In the “moderate gap” regime referenced in Theorem 1 where ⇠ q ✓ logn
  n , the regret of the policy ⇡ given by Algorithm 1 with ⇢ > 1 satisfies
  R⇡np n log n ) p ✓ 1 ⇤⇢(✓) =: h⇢(✓) as n!1, (3)
  where ⇤⇢(✓) is the (unique) solution to (2).
  To the best of our knowledge, this is the first algorithm-specific result (sharp asymptotic) that is distinct from the general ⌦ ( p n) information-theoretic lower bound by a horizon-dependent factor.6
  Discussion. A closed-form expression for ⇤⇢(✓) and h⇢(✓) is provided in Appendix A. The behavior of h⇢(✓) is illustrated below in Figure 3. For a fixed ⇢, the function h⇢(✓) is numerically observed to be uni-modal in ✓ and admit a global maximum at a unique ✓⇤⇢ := arg sup✓>0 h⇢(✓), bounded away from 0. Theorem 3 establishes that the worst-case (instance-independent) regret admits the sharp asymptotic R⇡n ⇠ h⇢ ✓⇤⇢ p n log n. In standard bandit parlance, this substantiates that the
  O p n log n
  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 p n log n performance bound for UCB vis-à-vis conventional minimax analyses such as [9]. Proof sketch. On a high level, note that when = p
  (✓ log n)/n, it follows from Theorem 1 that ER⇡n = p (✓ log n)/nE [n Ni⇤(n)] ⇠ h⇢(✓) p n log n (convergence in probability implies that in mean since |Ni⇤(n)/n| 6 1). That R⇡n also admits the same sharp asymptotic can be shown via a finer analysis. In other regimes of , viz., “small” and “large” gaps, we already know that R⇡n = op p n log n . This is obvious for “small” since ER⇡n 6 n = o p n log n , while for “large” , we use ER⇡n 6 C⇢ ((log n)/ + 1/(⇢ 1)) for some absolute constant C (given ⇢ > 1, 6 1) [6], followed by Markov’s inequality. Thus, the multiplicative constant sup✓>0 h⇢(✓) obtained in the “moderate” gap regime must correspond to the worst-case performance of the algorithm. ⇤ 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 [3]. Under this lens, time is accelerated linearly in n, space contracted by a factor of p n, and a sequence of systems indexed by n is considered. In our problem, the nth such system refers to an instance of the two-armed bandit with: n as the horizon of play; a gap that vanishes in the horizon as = c/ p n for some fixed c; and fixed reward variances given by 21 , 22 . 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-theoretic instances have a ⇥ (1/ p 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. A recent foray
  6Previous work establishes matching ⇥ p Kn logK
  upper and lower bounds for the minimax expected regret of the Gaussian prior-based Thompson Sampling algorithm in the K-armed problem, see [2].
  was made in [32, 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 2 {1, 2} is given by µi = µ + ✓i/ p n, where n is the horizon of play and µ, ✓1, ✓2 > 0 are fixed constants, and reward variances are 21 , 22 . Define 0 := |✓1 ✓2|. Denote the cumulative reward earned from arm i until time m by Si,m := PNi(m) j=1 Xi,j , and let S̃i,m := Si,m µNi(m). Then, the following process-level convergences hold under the policy ⇡ given by Algorithm 1 with ⇢ > 1:
  (I) S̃1,bntcp n , S̃2,bntcp n
  ! ) ✓ ✓1t
  2 + 1p 2 B1(t),
  ✓2t
  2 + 2p 2 B2(t)
  ◆ ,
  (II) R⇡bntcp
  n ) 0t 2 +
  r 21 + 2 2
  2 B̃(t),
  where the process-level convergence is over t 2 [0, 1], and B1(t) and B2(t) are independent standard Brownian motions in R, and B̃(t) := q 21
  21+ 2 2 B1(t)
  q 22
  21+ 2 2 B2(t).
  Proof sketch. Note that if the arms are played bn/2c times each independently over the horizon of play n (resulting in Ni(n) = bn/2c, i 2 {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 (N1(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 1 that for any arm i 2 {1, 2} as n ! 1, Ni(n)/n
  p ! 1/2 under UCB when ⇣ 1/ p n (diffusion-scaled gaps are covered under the “small gap” regime). This observation facilitates a standard “random time-change” argument t Ni(bntc)/n, i 2 {1, 2}, which followed upon by an application of Donsker’s Theorem, leads to the stated assertion in (I). This has the profound implication that for diffusion-scaled gaps, a two-armed bandit under UCB is, in fact, well-approximated by a classical system with independent samples (sample-interdependence 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 [8], Theorem 2.7) to (I). ⇤ Discussion. An immediate observation following Theorem 4 is that the normalized regret R⇡n/ p n is asymptotically Normal with mean 0/2 and variance 21 + 2 2 /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(c)), etc., such information provides new insights as to the problem’s minimax complexity as well. This is because ⇣ 1/ p n is known to be the information-theoretic “worst-case” for the problem; the smallest achievable regret in this regime must asymptotically be dominated by that under UCB, i.e., 0 p n/2. It is also noteworthy that while the diffusion limit in Theorem 4 does not itself depend on the exploration coefficient ⇢, the rate at which the system converges to said limit indeed depends on ⇢. Theorem 4 will continue to hold only as long as ⇢ = ! ((log log n) / log n); for smaller ⇢, the convergence of Ni(n)/n to 1/2 may no longer be true (refer to the proof of Theorem 1 in the “small” gap regime in Appendix E).
sections.heading: 4 Concluding remarks and open problems
sections.text: Our results for the two-armed problem under canonical UCB (Algorithm 1) may be generalizable to the K-armed setting, leveraging the observations and insights from Theorem 1 (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 1. We expect that similar generalizations are possible also for Theorem 3 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 1(b)) suggesting a plausibly non-degenerate distribution of arm-sampling rates for bounded rewards in [0, 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-limit performance metrics of Thompson Sampling, and elucidate its normalized minimax (stochastic) regret behavior.
  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.
title: A Closer Look at the Worst-case Behavior of Multi-armed Bandit Algorithms