Bandit Allocational Instability Yilun Chen, Jiaqi Lu Abstract When multi-armed bandit (MAB) algorithms allocate pulls among competing arms, the resulting allocation can exhibit huge variation. This is particularly harmful in modern applications such as learning-enhanced platform operations and post-bandit statistical inference. Thus motivated, we introduce a new performance metric of MAB algorithms termed allocation variability , which is the largest (over arms) standard deviation of an arm’s number of pulls. We establish a fundamental trade-off between allocation variability and regret, the canonical performance metric of reward maximization. In particular, for any algorithm, the worst-case regret ℛ T \mathcal{R}_{T} and worst-case allocation variability 𝒮 T \mathcal{S}_{T} must satisfy ℛ T ⋅ 𝒮 T = Ω ⁡ ( T 3 2 ) \mathcal{R}_{T}\cdot\mathcal{S}_{T}=\Omega(T^{\frac{3}{2}}) as T → ∞ T\rightarrow\infty , as long as ℛ T = o ⁡ ( T ) \mathcal{R}_{T}=o(T) . This indicates that any minimax regret-optimal algorithm must incur worst-case allocation variability Θ ⁡ ( T ) \Theta(T) , the largest possible scale; while any algorithm with sublinear worst-case regret must necessarily incur 𝒮 T = ω ⁡ ( T ) \mathcal{S}_{T}=\omega(\sqrt{T}) . We further show that this lower bound is essentially tight, and that any point on the Pareto frontier ℛ T ⋅ 𝒮 T = Θ ~ ​ ( T 3 / 2 ) \mathcal{R}_{T}\cdot\mathcal{S}_{T}=\tilde{\Theta}(T^{3/2}) can be achieved by a simple tunable algorithm UCB-f , a generalization of the classic UCB1 . Finally, we discuss implications for platform operations and for statistical inference, when bandit algorithms are used. As a byproduct of our result, we resolve an open question of Praharaj and Khamaru 2025 . † † runningauthor: Chen and Lu † † runningtitle: Bandit Allocational Instability † † authors: The Chinese University of Hong Kong, Shenzhen, chenyilun@cuhk.edu.cn The Chinese University of Hong Kong, Shenzhen, lujiaqi@cuhk.edu.cn † † affiliation: † † affiliation: † † affiliation: † † affiliation: 1 Introduction Multi-armed bandit (MAB) is a canonical model of sequential allocation under uncertainty ( Gittins et al. 2011 ) , with broad applications across Operations Research, Statistics, Economics, and Computer Science. In the classical formulation, a decision maker repeatedly selects one of K arms. Pulling arm i yields a random reward drawn independently from an arm-specific distribution that is unknown a priori. Over a horizon of T pulls, the decision maker must balance exploration (learning the reward distributions and identifying the most rewarding arm) and exploitation (leveraging what has been learned) in order to maximize expected cumulative reward, or equivalently, minimize the expected regret relative to the best (most rewarding) arm. This exploration–exploitation dilemma has fueled decades of research and has led to a rich theory of regret-optimal algorithms. While most bandit algorithms are designed to maximize reward, how do they allocate pulls? Somewhat surprisingly, numerical evidence shows that in certain cases, the allocation pattern of canonical bandit algorithms can be highly variable. We illustrate this in Example 1.1 with Thompson Sampling ( Thompson 1933 , Russo and Van Roy 2014 ), a popular Bayesian heuristic enjoying multiple regret-optimal guarantees. Example 1.1 Consider a two-armed bandit instance with Bernoulli( p_{i} ) arms over a horizon of T=5000 . The arms are identical with p_{1}=p_{2}=0.5 . We simulate the behavior of Thompson Sampling (with \textsf{Unif}[0,1] prior over p ) across 20000 independent trials. In each trial, we record the number of pulls of arm 1, and plot its empirical distribution across trials as the histogram in Figure 1 . Observe that the number of pulls allocated to arm 1 varies drastically across different trials, spreading essentially across the entire range from 0 to 5000 , exhibiting the maximal possible variability 1 1 1 In recent studies of Kalvit and Zeevi 2021 and Halder et al. 2025 , similar phenomena were observed under Thompson Sampling when both arms have Bernoulli(1) or Normal(0,1) rewards. . Figure 1: Allocation pattern of Thompson Sampling in Example 1.1 . We term the phenomenon in Example 1.1 allocational instability . Allocational instability highlights a distinct dimension of algorithmic behavior that is not captured by regret alone, and can be particularly harmful in modern bandit applications. For example: • On a typical content-sharing platform, users arrive sequentially to browse content that are created by competing third-party creators. Upon each arrival, the platform chooses which contents to display or recommend. The platform often uses bandit algorithms to maximize user satisfaction. In the bandit abstraction, creators correspond to “arms”, and “pulling an arm” corresponds to displaying the creator’s content to an arriving user. User’s satisfaction, often proxied by click-through rate and session length, serves as the reward. An arm’s number of pulls represents the total traffic routed to the arm (creator) by the algorithm. When the algorithm exhibits allocational instability, creators subsequently face highly volatile traffic. This can have severe consequences such as perceived unfairness, increased churn risk, reduced effort and lower content quality, which will hurt the platform’s long-term prosperity. Similar negative consequences of algorithmic allocational instability also arise in e-commerce, service platforms and other settings where agents correspond to arms. Beyond those, allocational instability can also have undesirable consequences for post-bandit statistical inference (see Section 1.2 and Section 5 for details). Thus motivated, in this work we introduce a new performance metric, termed allocation variability , that quantifies algorithmic allocational instability. In the stochastic MAB model, we define allocation variability as S_{T}\triangleq\max_{i\in[K]}\sd\!\big(N_{i,T}\big), namely, the largest (over arms) standard deviation of the number of pulls by time T . We study allocation variability alongside the standard performance metric of expected pseudo-regret, R_{T}\triangleq\sum_{i=1}^{K}\Delta_{i}\,{\mathbb{E}}\big[N_{i,T}\big], where \Delta_{i} denotes the mean-reward gap between the best arm and arm i . Adopting a minimax viewpoint, we evaluate algorithms by the worst-case (instance-independent) metrics \mathcal{S}_{T}\triangleq\sup_{\nu\in\mathfrak{P}}S_{T}(\nu) and \mathcal{R}_{T}\triangleq\sup_{\nu\in\mathfrak{P}}R_{T}(\nu) over some instance class \mathfrak{P}. We ask: Can an algorithm simultaneously achieve small worst-case regret \mathcal{R}_{T} and small worst-case allocation variability \mathcal{S}_{T} ? As the main message of this paper, we show that one cannot simultaneously do well on both fronts in a fundamental sense. In particular, we establish a trade-off between \mathcal{R}_{T} and \mathcal{S}_{T} , under which any reduction in regret necessarily comes at a commensurate price in allocation variability. We then provide a class of algorithms that attains the Pareto frontier up to polylog T factors. Our main findings and contributions are summarized below. 1.1 Contributions Fundamental regret-allocation-variability trade-off. We establish a fundamental impossibility result (Theorem 3.1 ): over Gaussian bandit instances, any algorithm that actively learns (i.e., achieves \mathcal{R}_{T}=o(T) ) must satisfy \mathcal{R}_{T}\cdot\mathcal{S}_{T}=\Omega\!\left(T^{3/2}\right)\qquad\text{as }T\to\infty. As an immediate corollary, minimax regret-optimal algorithms with \mathcal{R}_{T}=\Theta(\sqrt{T}) (cf. Lattimore and Szepesvári 2020 ) must have \mathcal{S}_{T}=\Omega(T) . Since the allocation variability is at most linear in T , this implies \mathcal{S}_{T}=\Theta(T) . In words, minimax regret-optimal learning necessarily results in the largest possible allocation variability. We further demonstrate that under minimax regret-optimal algorithms, such maximal allocation variability occurs on all instances in which \Delta_{i}=O(1/\sqrt{T}) for some arm i ( Theorem 3.5 ). Moving away from minimax optimality, our lower bound quantifies how reductions in allocation variability must be paid for by a commensurate increase in regret. Specifically, algorithms with \mathcal{S}_{T}=\Theta(T^{1-\alpha}) must incur \mathcal{R}_{T}=\Omega(T^{\frac{1}{2}+\alpha}) , \forall\alpha\in(0,\frac{1}{2}] . At the opposite end of the spectrum, we identify what we term the price of learning : any algorithm that has any intention to learn, namely, achieving sub-linear regret as T grows, must incur worst-case allocation variability \mathcal{S}_{T}=\omega(\sqrt{T}) . This is in sharp contrast to algorithms that completely give up on learning, such as round-robin or other static allocation rules, which can in principle achieve \mathcal{S}_{T}=0. Pareto frontier and the UCB-f algorithms. We show that the lower bound \mathcal{R}_{T}\cdot\mathcal{S}_{T}=\Omega\!\left(T^{3/2}\right) tightly characterizes the achievable regret-allocation-variability region for active learning algorithms, as depicted in Figure 2 . Figure 2: Pareto frontier of the two objectives of interest. In particular, we design a family of algorithms that can smoothly trade off regret and allocation variability along the boundary, up to polylog T factors ( Theorem 4.1 ). This identifies \mathcal{R}_{T}\cdot\mathcal{S}_{T}=\tilde{\Theta}(T^{3/2}) as the Pareto frontier. Our Pareto-efficient family of algorithms, termed UCB-f , generalizes the canonical UCB1 algorithm by replacing the standard exploration function (of order \sqrt{\log t} ) with a tunable f(t) . A faster increasing f(t) shifts the algorithm from aggressive exploitation towards encouraging more exploration, and correspondingly trades larger regret for reduced allocation variability. Implications. Our theoretical findings have rich implications. For learning-enhanced platform operations, we consider a platform that cares about both user satisfaction and agent (arm) utility, with minimax objective \sup_{\nu\in\mathfrak{P}}(R_{T}(\nu)+(S_{T}(\nu))^{\rho}) . The parameter \rho\geq 0 captures the agents’ risk aversion level for demand variability. Our findings then immediately imply a lower bound of (\sqrt{T}\vee(T^{\frac{3\rho}{2+2\rho}}\wedge T)) for this objective, which is attained (up to polylog T factors) by the UCB-f algorithm with an appropriate choice of f(t) when \rho\in[0,2] . If \rho>2 , i.e., the agents’ risk-aversion level is so high, then the platform should completely give up learning and deterministically split demand among the agents to avoid the superlinear loss from allocation variability. For post-bandit statistical inference, we resolve an open question (with a negative answer) raised in Praharaj and Khamaru 2025 as a byproduct of Theorem 3.1 – 3.5 . This implies that under minimax regret-optimal algorithms, the desired asymptotic normality of an arm’s sample mean reward likely fails to hold, or at least can not be established by the techniques in the recent literature; see Section 1.2 and Section 5 for more details. Novel lower bounding technique. To prove our main impossibility result, we develop a systematic approach that bridges regret and allocation variability, which may find a broader application. To convey the core intuition, consider a two-armed Gaussian bandit with rewards \mathcal{N}(0,1) and \mathcal{N}(-\Delta,1) , parameterized by the gap \Delta\geq 0 . Let g_{T}(\Delta)=\mathbb{E}[N_{2,T}] denote the expected pull counts of the inferior arm. Then the expected pseudo-regret R_{T}(\Delta)=\Delta g_{T}(\Delta) . A key observation is that the allocation variability can be related to g^{\prime}_{T} , namely, how fast g_{T}(\cdot) changes with respect to \Delta . Precisely, let \Delta^{\prime} denote \Delta+1/\sqrt{g_{T}(\Delta)} , then S_{T}(\Delta)\asymp\left|g_{T}(\Delta)-g_{T}\left(\Delta^{\prime}\right)\right| by the following intuition. Under \Delta , there are on average g_{T}(\Delta) pulls on the inferior arm and consequently, one can not effectively distinguish instances in \left(\Delta,\Delta^{\prime}\right) due to the noise in the samples. Thus under \Delta , the pull counts must “stretch” at times to behave as if the instance were \Delta^{\prime} , leading to the unavoidable variability on the order of \left|g_{T}(\Delta)-g_{T}\left(\Delta^{\prime}\right)\right| . Such an observation allows us to relate S_{T}(\Delta) to {g^{\prime}_{T}(\Delta)}/{\sqrt{g_{T}(\Delta)}} . The fundamental tension between controlling regret and reducing allocation variability then follows from the following reasoning. At \Delta=0,g_{T}(0)=\frac{T}{2} by symmetry. Starting from g_{T}(0) , a small regret requires a fast descent of g_{T}(\Delta) as \Delta increases, while a small allocation variability requires g_{T}(\Delta) to change slowly (so |g^{\prime}_{T}(\Delta)| stays in control). Explicitly solving this tension results in the desired trade-off. 1.2 Literature review Regret-minimization in MAB. In the extensive stochastic MAB literature, the primary performance criterion for an algorithm has been the expected (pseudo-)regret, defined as the expected loss in cumulative reward relative to always pulling the optimal arm. For a fixed problem instance—unknown to the algorithm—the seminal work of Lai and Robbins 1985 establishes that the minimal achievable expected regret must scale as \Theta(\log T) as T\rightarrow\infty . Complementary to this instance-dependent notion is the instance-independent, or worst-case, expected (pseudo-)regret ( Lattimore and Szepesvári 2020 ). It is well known that for stochastic MAB, the worst-case expected regret under any algorithm is lower bounded by \Theta(\sqrt{T}) ; see Auer et al. 2002 . Several classic algorithms attain near-optimal rates under both instance-dependent and worst-case criteria, such as UCB1 ( Auer et al. 2002 ), UCB-V ( Audibert et al. 2009 ), KL-UCB ( Garivier and Cappé 2011 ) and Thompson Sampling ( Agrawal and Goyal 2012 , Daniel et al. 2018 ). There are also various algorithms designed to achieve strict optimality. For example, in terms of worst-case optimal rate \Theta(\sqrt{T}) , there are KL-UCB++ ( Ménard and Garivier 2017 ), MOSS and Anytime-MOSS ( Audibert and Bubeck 2009 ), Vanilla-MOSS ( Lattimore and Szepesvári 2020 ), ADA-UCB ( Lattimore 2018 ), OC-UCB ( Lattimore 2015 ), KL-MOSS ( Praharaj and Khamaru 2025 ), KL-UCB-SWITCH and Anytime KL-UCB-SWITCH ( Garivier et al. 2022 ), MOTS ( Jin et al. 2021a ), DETC ( Jin et al. 2021b ), Tsallis-INF ( Zimmert and Seldin 2021 ), and more. Our result highlights a fundamental side effect of allocational instability for all these algorithms. Beyond-expectation analysis of regret. A recent stream of work studies bandit performance beyond expected regret. In particular, Fan and Glynn 2025 , Simchi-Levi et al. 2022 , Simchi-Levi and Wang 2023 investigate the regret tail probability \mathbb{P}(\hat{R}_{T}>a) for large a\gg\mathbb{E}[\hat{R}_{T}] , characterizing when it decays slowly, namely, exhibiting a heavy tail. In the textbook Lattimore and Szepesvári 2020 , this phenomenon is discussed informally for the MOSS algorithm. Fan and Glynn 2025 show that, in general, the regret tails of instance-dependent–optimal algorithms (achieving the Lai–Robbins lower bound) must be heavy-tailed, and can be as heavy as a truncated Cauchy (of rate \Theta(\frac{1}{T}) ) for certain distribution classes. Regret tail risk differs from allocation variability in several fundamental ways. In particular, severe power-law regret tails only arise on instances with a clearly suboptimal arm (with gap \Delta_{i}>0 independent of T ), and can be effectively eliminated with only a modest sacrifice in expected regret (e.g., by a constant or polylog factor), using tunable algorithms such as UCB-f Fan and Glynn 2025 , Simchi-Levi et al. 2023 . In contrast, allocation variability is maximized when arms are indistinguishable, and it’s far more stubborn and costly to mitigate: in general, one cannot achieve small allocation variability without a substantial sacrifice on the regret front. Beyond regret tail risk, Fan and Glynn 2022 characterize the LLN and CLT for regret under UCB1 and Thompson Sampling , while Kalvit and Zeevi 2021 , Kuang and Wager 2024 further study the corresponding pathwise dynamics under these algorithms. Post-bandit statistical inference. Recently, a stream of literature aims to understand whether the arm’s sample mean reward computed from post-bandit data exhibits asymptotic normality, so that classic CLT-based inference methods can be applied. A useful technical lens to study this question is whether the bandit algorithm satisfies sampling stability, which is defined as \frac{N_{i,T}}{n_{i,T}}\xrightarrow{p}1 for some sequence of non-random values n_{i,T} , as T\rightarrow\infty (see Lai and Wei 1982 and Praharaj and Khamaru 2025 ). Sampling stability is a key sufficient condition that guarantees the asymptotic normality of the sample mean, and it is recently frequently used to analyze existing algorithms and design new ones. Along this line, Kalvit and Zeevi 2021 show the sampling stability of UCB1 , and Chen and Lu 2025 characterize its precise convergence rate. Han 2026 prove the negative for Thompson Sampling . Subsequently, Khamaru and Zhang 2024 establish the sample mean reward’s asymptotic normality for UCB1 , and Halder et al. 2025 propose ways to tune and stabilize Thompson Sampling while only incurring an additional logarithm factor in worst-case regret. Praharaj and Khamaru 2025 prove that sampling stability does not hold for minimax regret-optimal MOSS -family algorithms. Until now, the question of whether simultaneously stable and minimax regret-optimal algorithms exist remains open (see Praharaj and Khamaru 2025 ). Our fundamental lower bound in Theorem 3.1 implies a negative answer to this question. Therefore the desired asymptotic normality of an arm’s sample mean reward likely fails to hold, or at least can not be established by the techniques in the recent literature. Economic aspects of learning algorithms. More broadly, this paper contributes to an emerging literature on the economic aspects of learning algorithms; see Hartline 2026 for an overview. This literature aims to understand the (equilibrium) outcomes of algorithmic actors as they are increasingly replacing human actors in the economy ( Foster and Vohra 1997 , Hart and Mas-Colell 2000 , Calvano et al. 2020 ). A central theme is that regret minimization serves as a tractable notion of rationality for algorithmic decision makers. Our work complements this line of research by focusing on an intrinsic property of regret-minimizing algorithms, which we term allocation variability. We show that achieving low regret must entail substantial fluctuations in induced allocations, a feature that is largely absent from existing economic analyses of no-regret dynamics. Such allocational instability is economically relevant in platform operations and market design, where fluctuations in demand or traffic allocation may trigger strategic responses by participating agents (e.g. Lee et al. 1997 , Cachon et al. 2017 ). In this sense, our results provide a new angle for understanding learning algorithms in economic systems. 1.3 Organization of the paper The remainder of the paper is organized as follows. Section 2 sets up the MAB model and the performance metric of allocation variability. Section 3 establishes the fundamental trade-off between regret and allocation variability. We then introduce a family of UCB-f algorithms in Section 4 that can achieve any point on the Pareto frontier. Section 5 discusses the implications of our results. We prove Theorem 3.1 in Section 6 . Section 7 concludes the paper. The proofs of all other results are in the appendix. 2 Preliminary Consider the classic stochastic MAB model. There are K arms. For each arm i\in[K] , let \{X^{i}_{s}\}_{s\geq 1} be an i.i.d. reward sequence with common distribution \nu_{i} . These sequences are mutually independent across arms. We refer to \nu=(\nu_{1},\dots,\nu_{K}) as a bandit instance . Over a horizon T , a bandit algorithm selects a (potentially random) arm A_{t}\in[K] at each time t\in[T] . Define N_{i,t}\triangleq\sum_{s=1}^{t}\mathds{1}\{A_{s}=i\} as the pull counts (number of pulls) of arm i up to (and include) time t , and r_{t}\triangleq X^{A_{t}}_{N_{A_{t},t}} as the reward collected at time t . Let \mathcal{H}_{t-1}\triangleq(A_{1},r_{1},\ldots,A_{t-1},r_{t-1}) be the observed history up to time t-1 . The algorithm is specified by a sequence of decision rules \{\pi_{t}\}_{t\in[T]} , where each \pi_{t}(\cdot\mid\mathcal{H}_{t-1}) is a distribution over [K] , and the action is drawn as A_{t}\sim\pi_{t}(\cdot\mid\mathcal{H}_{t-1}). The standard performance metric of a bandit algorithm is the regret. In particular, let \mu_{i} be the mean reward of arm i and \mu^{*}\triangleq\max_{i\in[K]}\mu_{i} , and define the mean reward gap \Delta_{i}\triangleq\mu^{*}-\mu_{i} . Then the (expected pseudo-)regret is given by R_{T}\triangleq\sum_{i=1}^{K}\Delta_{i}\,{\mathbb{E}}[N_{i,T}] . Minimizing R_{T} is equivalent to maximizing the expected cumulative reward \mathbb{E}\left[\sum_{t=1}^{T}r_{t}\right]. In addition to the regret, this work introduces a new performance metric that quantifies the variability of an algorithm’s pull allocation. Specifically, we define the allocation variability as the largest standard deviation of the pull counts N_{i,T} across arms. Definition 2.1 (Allocation Variability) An algorithm’s allocation variability by time T is defined as S_{T}\triangleq\max_{i\in[K]}\sd\!\big(N_{i,T}\big)=\max_{i\in[K]}\sqrt{\operatorname{Var}\big(N_{i,T}\big)}. We adopt the minimax framework, evaluating a bandit algorithm by its worst-case performance over a prescribed instance class. Formally, for an instance class \mathfrak{P} , define \mathcal{R}_{T}(\mathfrak{P})\triangleq\sup_{\nu\in\mathfrak{P}}R_{T}(\nu) and \mathcal{S}_{T}(\mathfrak{P})\triangleq\sup_{\nu\in\mathfrak{P}}S_{T}(\nu) as the worst-case (instance-independent) regret and allocation variability, respectively. Throughout, we focus on a sub-Gaussian instance class with bounded means, formalized below. Definition 2.2 (Sub-Gaussian instance class) Fix M,\sigma,\bar{K}>0 . Let \mathfrak{P}_{\mathrm{sg}}(M,\sigma,\bar{K}) denote the class of stochastic bandit instances \nu=(\nu_{1},\dots,\nu_{K}) with number of arms 2\leq K\leq\bar{K} , such that for each arm i\in[K] , the reward distribution \nu_{i} has mean \mu_{i}\in[-M,M] and is \sigma -sub-Gaussian. For brevity, we omit explicit dependence on M,\sigma and \bar{K} , and write \mathfrak{P}_{\mathrm{sg}} for the instance class, with the understanding that they are fixed constants and are typically immaterial to our T -asymptotic statements. We also suppress the dependence on \mathfrak{P}_{\mathrm{sg}} and write \mathcal{R}_{T} and \mathcal{S}_{T} for notational simplicity. We specify the class of algorithms considered. We first impose two mild regularity conditions: (i) if \nu_{i}=\nu_{j} for some i\neq j , then {\mathbb{E}}[N_{i,T}]={\mathbb{E}}[N_{j,T}] ; and (ii) each arm is in expectation pulled at least once (for T\geq K ). Both of the properties are satisfied by essentially all standard bandit algorithms of interest. Other than that, we impose the following active-learning condition that requires algorithms to have an intention to learn. Definition 2.3 (Active-learning algorithms) A bandit algorithm is active-learning (over \mathfrak{P}_{\mathrm{sg}} ) if \lim_{T\to\infty}\frac{\mathcal{R}_{T}}{T}\ =\ 0 , i.e., it achieves sublinear worst-case regret. 2.1 Additional notation To simplify exposition, we sometimes use the classic Bachmann-Landau notation. In particular, for two nonnegative sequences \{a_{T}\} and \{b_{T}\} , we write a_{T}=O(b_{T}) if there exist constants C>0 and T_{0} such that a_{T}\leq Cb_{T} for all T\geq T_{0} , and a_{T}=\Omega(b_{T}) if b_{T}=O(a_{T}) . We write a_{T}=\Theta(b_{T}) if a_{T}=O(b_{T}) and a_{T}=\Omega(b_{T}) . Moreover, a_{T}=o(b_{T}) means a_{T}/b_{T}\to 0 as T\to\infty , and a_{T}=\omega(b_{T}) means a_{T}/b_{T}\to\infty as T\to\infty . We also use \tilde{O}(\cdot) , \tilde{\Omega}(\cdot) , and \tilde{\Theta}(\cdot) to suppress factors that are polylogarithmic in T . For any positive integer M , [M] denotes \{1,2,\dots,M\} , the set of positive integers up to M. For a random variable X , \sd(X) and \operatorname{Var}(X) denote its standard deviation and variance, respectively. 3 An Impossibility Theorem We provide an impossibility theorem that characterizes the fundamental trade-off between learning efficiency (as measured by regret) and allocational stability (as measured by allocation variability). Theorem 3.1 Over the instance class \mathfrak{P}_{\mathrm{sg}} , any active-learning algorithm must satisfy \liminf_{T\to\infty}\frac{\mathcal{R}_{T}\cdot\mathcal{S}_{T}}{T^{3/2}}\;>\;C, where C>0 is a constant that depends only on \mathfrak{P}_{\mathrm{sg}} and is independent of the algorithm. We prove Theorem 3.1 in Section 6 . A few remarks are in order below. On the role of active-learning. The active-learning condition is crucial. Indeed, an algorithm that does not actively learn can trivially achieve \mathcal{S}_{T}=0 , and violates the lower bound in Theorem 3.1 . Consider, for instance, the round-robin rule (see more discussion in Section 3.1 ). The lower bound in Theorem 3.1 is asymptotic in the horizon T . Improving it to a finite-time bound necessarily requires a stronger notion of active-learning. To see this, consider a sequence of algorithms \{\pi^{(l)}\}_{l\geq 1} where \pi^{(l)} plays round-robin up to time l and then switches to an arbitrary bandit algorithm e.g. UCB1 from time l+1 onward. Each \pi^{(l)} satisfies Definition 2.3 since it eventually learns and hence has sublinear worst-case regret as T\to\infty . However, for any fixed horizon T , choosing l=T yields a policy \pi^{(T)} with \mathcal{S}_{T}=0 . Consequently, no nontrivial lower bound of the form in Theorem 3.1 can hold uniformly at every finite T unless we strengthen active learning to enforce a uniform learning rate (thereby excluding such “delayed-learning” concatenations). We do not pursue this direction in the present work. On K -dependence. Our impossibility result in Theorem 3.1 is asymptotic in T and it does not capture the dependence on the number of arms K in the spirit of the classic minimax bandit literature. Indeed, we prove our lower bound using a special family of two-armed Gaussian bandit instances with bounded mean and unit variance (see also Section 3.2 and Section 6 for a detailed description). We leave a sharp characterization of the K -dependence to future work. 3.1 A closer look at different regret-scaling regimes Theorem 3.1 imposes a lower bound on the worst allocation variability, asserting that any active-learning algorithm must satisfy \mathcal{S}_{T}=\Omega(\frac{T^{3/2}}{\mathcal{R}_{T}}) . We next zoom in on specific regret-scaling regimes and discuss the implications of Theorem 3.1 . The (near)minimax regret-optimal regime: \mathcal{R}_{T}=\tilde{O}(\sqrt{T}) . It is well known that the worst-case regret is lower bounded by \mathcal{R}_{T}=\Omega(\sqrt{T}) Lattimore and Szepesvári 2020 , and much of the bandit literature focuses on the design and analysis of algorithms achieving (near)minimax-optimal regret \mathcal{R}_{T}=\tilde{O}(\sqrt{T}) . A striking implication of Theorem 3.1 is that any such near minimax regret-optimal algorithm must incur nearly maximal allocation variability. Corollary 3.2 Any algorithm with worst-case regret \tilde{O}(\sqrt{T}) satisfies \mathcal{S}_{T}=\tilde{\Theta}(T) . In particular, minimax regret-optimal algorithms that attain \mathcal{R}_{T}=\Theta(\sqrt{T}) suffer a linear-in- T worst-case allocation variability. Corollary 3.2 follows from Theorem 3.1 and the fact that N_{i,T} is bounded by T , which immediately implies a linear-in- T upper bound on its standard deviation. Many existing algorithms are designed for achieving the minimax-optimal regret \mathcal{R}_{T}=\Theta(\sqrt{T}) (see Section 1.2 for a non-exhaustive list of such algorithms). Corollary 3.2 shows that these algorithms all must incur \Theta(T) worst-case allocation variability. Beyond exact minimax regret optimality, many popular algorithms, including Thompson Sampling ( Agrawal and Goyal 2012 ) and UCB1 ( Auer et al. 2002 ) , are well known to attain the near-minimax rate \mathcal{R}_{T}=O(\sqrt{T\log T}) . For such algorithms, Theorem 3.1 implies that, in the worst case, the pull count N_{i,T} must fluctuate on the order of at least T/\sqrt{\log T} . Relatedly, ( Kalvit and Zeevi 2021 ) study the sampling behavior of UCB1 and show that \frac{N_{i,T}}{T}\xrightarrow{p}1 . Our theorem complements and, in some sense contrasts with this result, suggesting that the convergence happens at an extremely slow rate of \Omega(1/\sqrt{\log T}) in the worst-case. Chen and Lu 2025 shows that this rate is tight. As for Thompson Sampling , the worst-case allocation variability is even larger than T/\sqrt{\log T} . Indeed, Kalvit and Zeevi 2021 and Han 2026 show that its sampling rate \frac{N_{i,T}}{T} does not converge to a constant when the optimal arm is non-unique. The weak-learning regime: \mathcal{R}_{T} is nearly linear. At the opposite end of the spectrum, we consider algorithms that barely satisfy active learning, in the sense that their worst-case regret is almost linear, e.g. \mathcal{R}_{T}=\Theta(\frac{T}{\log T}). Theorem 3.1 then implies that such algorithms must still incur worst-case allocation variability at least on the \sqrt{T} scale. Corollary 3.3 Any active learning policy must have \mathcal{S}_{T}=\omega(\sqrt{T}) . Corollary 3.3 implies that any algorithm with even a modest intention to favor the better arm, hence achieving o(T) regret, must incur worst-case allocation variability strictly larger than \sqrt{T} . This stands in stark contrast to the no-learning setting, where one can use non-adaptive allocation rules such as round-robin, for which \mathcal{S}_{T} is essentially 0 . 2 2 2 When T is not a multiple of K , one can randomize only the last few pulls; this introduces at most O(1) allocation variability, which we ignore. We term this unavoidable \sqrt{T} -scale allocation variability faced by any active-learning algorithm the price of learning . 3.2 When does the worst case occur? Theorem 3.1 does not specify the worst-case instances. In general, when should we expect an algorithm to incur large allocation variability? To obtain a clearer picture, we focus on the two-armed Gaussian bandits \nu(\Delta)=\{\mathcal{N}(0,1),\mathcal{N}(-\Delta,1)\} , parameterized by the arm’s mean reward gap \Delta\geq 0. We refer to the second arm (mean -\Delta ) the inferior arm . The next result shows that as T\to\infty , any active learning algorithm must incur large allocation variability on an instance with \Delta vanishingly small. Corollary 3.4 Consider an active learning algorithm with worst-case regret \Theta(T^{\frac{1}{2}+\alpha}) , \alpha\in[0,\frac{1}{2}) . Then there exists an absolute constant c>0 such that \displaystyle\sup_{\Delta\in[0,cT^{\alpha-1/2}]}S_{T}(\Delta)=\Omega(T^{1-\alpha})\ \ \text{as }T\rightarrow\infty. The proof of Corollary 3.4 follows directly from the argument of Theorem 3.1 , and is deferred to Appendix 8 . Corollary 3.4 is consistent with Example 1.1 : large allocation variability must happen in some instance where the mean reward gap is small. Moreover, for minimax regret-optimal algorithms, we can strengthen Corollary 3.4 and show that all instances with statistically indistinguishable arms are worst case, in the sense that they incur \Theta(T) allocation variability. Theorem 3.5 Consider minimax regret-optimal algorithms that satisfy \mathcal{R}_{T}\leq c_{0}\sqrt{T} for some c_{0}>0 . Fix any c_{1}>0 . Then for any \Delta\in\left[0,\frac{c_{1}}{\sqrt{T}}\right] , there exists a constant c_{2} that depends only on c_{0},c_{1} , such that for T sufficiently large, S_{T}(\Delta)\geq c_{2}T. The proof of Theorem 3.5 follows the same overall strategy as that of Theorem 3.1 . In particular, under a minimax regret-optimal algorithm, the expected pull count of the inferior arm must be sensitive to the gap \Delta , experiencing significant decrease from T/2 as \Delta increases from zero to O(1/\sqrt{T}) . We then apply a change-of-measure argument to show that, in this local regime, nearby instances are information-theoretically hard to distinguish. This translates into a large local change rate (sensitivity) of the expected pull count with respect to \Delta whenever \Delta=O(1/\sqrt{T}) , which in turn can be related to the large allocation variability in that range. The proof is provided in Appendix 9 . A special case covered by Theorem 3.5 is \Delta=0 , i.e., the instance with two identical arms. The theorem implies that this instance must incur maximal allocation variability under any minimax regret-optimal algorithm. Another important regime is when \Delta is strictly bounded away from 0 , particularly, \Delta\in\left[\frac{c_{3}}{\sqrt{T}},\,\frac{c_{1}}{\sqrt{T}}\right] for some 0c_{4} for constant c_{4}>0 independent of the algorithm. Furthermore, over \mathfrak{P}^{2}_{\mathrm{sg}} , UCB-f achieves \liminf_{T\rightarrow\infty}\frac{\sup_{\nu\in\mathfrak{P}^{2}_{\mathrm{sg}}}{\sd\!\big(\hat{R}_{T}(\nu)\big)}}{\sqrt{T}\log T}0 and any exploration function f(\cdot) satisfying the conditions of Theorem 4.1 . We provide the proof of Proposition 4.4 in Appendix 11 . The impossibility result follows from arguments similar to those used in the proof of Theorem 3.1 , while the achievability result immediately follows from the proof of Theorem 4.1 . We establish the achievability statement for two-armed bandits, as this suffices for illustrative and contrastive purposes. Proposition 4.4 , together with Theorem 4.1 , indicates that there is essentially no trade-off between worst-case expected regret and worst-case regret variability. Indeed, one may vary \mathcal{R}_{T} to attain any rate \tilde{\Theta}\left(T^{1/2}\,f(T)\right) by tuning f(\cdot) in UCB-f , while the worst-case regret variability remains at the order \tilde{\Theta}(\sqrt{T}) . In other words, the corresponding Pareto frontier (up to polylog T factors) is a flat horizontal line, as plotted in Figure 3 (b). This is in sharp contrast to the nontrivial Pareto frontier between \mathcal{R}_{T} and the worst-case allocation variability \mathcal{S}_{T} characterized in Corollary 4.2 and illustrated in Figure 3 (a). (a) \mathcal{R}_{T} versus allocation variability. (b) \mathcal{R}_{T} versus regret variability. Figure 3: Pareto frontiers of different objectives of interest. 5 Implications Our theoretical findings have rich implications in various domains. In this section, we discuss how bandit algorithms’ allocation variability can impact platform operations and statistical inference. Implications on platform operations. Consider a platform who dynamically allocates online arriving demand to competing third-party agents with unknown service quality. Each demand allocation at time t generates a random reward r_{t} from the corresponding agent’s reward distribution. The platform aims for a large total reward. At the same time, the platform also cares about the agents’ utility to maintain its long term growth. The agents are risk-averse and get disutility if their demand variability is large. Following the classic mean-risk formulation (e.g., Markowitz 1952 ), we express the platform’s aggregate goal as maximizing expected total reward \mathbb{E}\big[\sum_{s=1}^{T}r_{s}\big] minus the (largest among agents) agent disutility S_{T}^{\rho} due to allocation variability, where \rho\geq 0 measures the agents’ risk-aversion level (e.g., \rho=0 means the agents are risk-neutral). Equivalently, the platform aims to minimize the loss R_{T}+S_{T}^{\rho} . Suppose the platform wants to incur a small aggregate loss in all possible instances \nu . Taking the robust optimization’s minimax perspective, the platform’s objective is to find an algorithm to minimize the worst-case loss \displaystyle\sup_{\nu\in\mathfrak{P}_{\mathrm{sg}}}\left(R_{T}(\nu)+(S_{T}(\nu))^{\rho}\right). (1) The following corollary of Theorem 3.1 and Theorem 4.1 establishes the lower bound of the platform’s optimal loss, and prescribes an algorithm to achieve asymptotic near-optimality. Corollary 5.1 Consider the platform’s problem in ( 1 ) where \rho\geq 0 . Under any bandit algorithm, we have \displaystyle\liminf_{T\rightarrow\infty}\frac{\sup_{\nu\in\mathfrak{P}_{\mathrm{sg}}}\left(R_{T}(\nu)+(S_{T}(\nu))^{\rho}\right)}{\sqrt{T}\vee(T^{\frac{3\rho}{2+2\rho}}\wedge T}>c_{6} for constant c_{6}>0 independent of the algorithm. Furthermore, if \rho\in[0,2] , then the UCB-f algorithm with f(t)=t^{\left(\frac{2\rho-1}{2+2\rho}\right)^{+}}\log t achieves \displaystyle\sup_{\nu\in\mathfrak{P}_{\mathrm{sg}}}(R_{T}(\nu)+(S_{T}(\nu))^{\rho})=\tilde{\Theta}(\sqrt{T}\vee T^{\frac{3\rho}{2+2\rho}}). Corollary 5.1 states that the platform must at least incur a total loss of \Theta\left(\sqrt{T}\vee\left(T^{\frac{3\rho}{2+2\rho}}\wedge T\right)\right)) in the worst case. If \rho>2 , the agents are very risk-averse, and the loss due to allocation variability dominates regret. In this case, the platform should give up learning (e.g., conduct round-robin) to avoid the superlinear loss from \Omega(\sqrt{T}) allocation variability. If \rho<\frac{1}{2} , the agents are very insensitive to risk. This propels the platform to prioritize minimizing regret, with a minimax loss of \Theta(\sqrt{T}) dominated by the regret term. If \rho\in[\frac{1}{2},2] , i.e., the agents are median level risk-averse, then the platform should carefully balance between regret and allocation variability. Our carefully tuned UCB-f algorithm can strike this balance. For example, when \rho=1 , UCB-f with f(t)=t^{\frac{1}{4}}\log t generates \tilde{\Theta}(T^{\frac{3}{4}}) worst-case regret and \tilde{\Theta}(T^{\frac{3}{4}}) worst-case allocation variability, which achieves the minimax loss of \Theta(T^{\frac{3}{4}}) up to a polylog T factor in problem ( 1 ). The proof of Corollary 5.1 is in Section 12 . Implications for statistical inference. Our results also have direct implications for statistical inference in MAB, a topic that has received growing attention in recent years (see literature review). Here the goal is to perform inference, e.g. to estimate an arm’s mean reward, using data generated by a bandit algorithm. The central difficulty is that bandit algorithms are highly adaptive, and the data thus generated are non- i.i.d. To ensure that standard inferential guarantees (developed under the i.i.d. assumption) remain valid, a recent line of work ( Han et al. 2024 , Khamaru and Zhang 2024 , Praharaj and Khamaru 2025 ) focuses on a key sufficient condition, termed sampling stability , first introduced in Lai and Wei 1982 . It is shown that under this condition, the sample mean reward \hat{\mu}_{i,T}=\frac{1}{N_{i,T}}\sum_{s=1}^{N_{i,T}}X^{i}_{s} admits asymptotic normality ( Han et al. 2024 ) , thereby supporting CLT-based confidence intervals and hypothesis tests. We state this condition below (as in Praharaj and Khamaru 2025 ). Definition 5.2 (Sampling stability) A bandit algorithm exhibits sampling stability over an instance class \mathfrak{P} if for any instance \nu\in\mathfrak{P} and any arm i\in[K] , there exist non-random scalars n_{i,T}(\nu) such that \frac{N_{i,T}(\nu)}{n_{i,T}(\nu)}\xrightarrow{p}1 , and n_{i,T}(\nu)\to\infty , as T\to\infty. A large body of work is devoted to determining whether various bandit algorithms exhibit sampling stability, and the current understanding remains largely algorithm-specific. In particular, Praharaj and Khamaru 2025 pose the following open question: Is it possible to design bandit algorithms that achieve both sampling stability and minimax-optimal regret? Our results resolve this open question with a negative answer. Corollary 5.3 Over \mathfrak{P}_{\mathrm{sg}} , no minimax regret-optimal algorithm that satisfies \mathcal{R}_{T}\leq c_{0}\sqrt{T} for some c_{0}>0 exhibits sampling stability. The corollary follows immediately from Theorem 3.1 – 3.5 , on instances with two identical Gaussian arms, together with the fact that allocation variability on the order of \Theta(T) implies sampling instability in the sense of Definition 5.2 . We provide the proof in Section 12 . Beyond the negative result in Corollary 5.3 , even for bandit algorithms satisfying Definition 5.2 , our notion of allocation variability provides a smooth, granular quantification of how stable they are. For example, the canonical UCB1 algorithm has been shown to satisfy Definition 5.2 and is therefore deemed stable; however, Corollary 3.2 suggests that its worst-case allocation variability is \tilde{\Omega}(T) , i.e., it is nearly unstable in the worst case. Consistent with this, numerical evidence in Chen and Lu 2025 indicates a substantial difference between the distribution of \sigma_{i}\sqrt{N_{i,T}}(\hat{\mu}_{i,T}-\mu_{i}) and the standard normal even at T=10^{5} , despite the fact that the former converges to the latter asymptotically. We conjecture that the large allocation variability of UCB1 contributes to this slow CLT convergence, and we leave a precise characterization of the convergence rate as an intriguing open problem. 6 Proof of Theorem 3.1 In this section, we prove our main impossibility result, Theorem 3.1 . Our proof of Theorem 3.1 primarily focuses on the family of two-armed Gaussian bandit instances as in Section 3.2 . Recall that such an instance is \nu(\Delta)\triangleq\{\mathcal{N}(0,1),\mathcal{N}(-\Delta,1)\} , parameterized by the mean reward gap \Delta between the two arms. We adopt notations S_{T}(\Delta),R_{T}(\Delta) , whose meaning is clear from context. Denote by g_{T}(\Delta)\triangleq\mathbb{E}_{\Delta}[N_{2,T}] , i.e., the expected pull counts of the second (inferior) arm in instance \Delta . For simplicity, we assume \Delta\leq 2 . Hence \nu(\Delta)\in\mathfrak{P}_{\text{sg}}(2,1) . The generalization to arbitrary \mathfrak{P}_{\text{sg}}(M,\sigma) is straightforward and we omit. The proof relies on two key lemmas. First, for each gap \Delta , we relate the allocation variability S_{T}(\Delta) to the local sensitivity of g_{T}(\cdot) at \Delta (Lemma 6.1 ). Second, we show that g_{T}(\cdot) cannot simultaneously vary slowly everywhere and yet decrease sufficiently as \Delta grows, which is necessary to keep the expected regret \mathcal{R}_{T} small (Lemma 6.2 ). We now proceed to establish these two lemmas. Lemma 6.1 Let \Delta^{\prime}\triangleq\Delta+\frac{1}{\sqrt{g_{T}(\Delta)}}. Under any algorithm, it is true that \displaystyle\max\left\{S_{T}(\Delta),S_{T}\left(\Delta^{\prime}\right)\right\}\geq\frac{\sqrt{\frac{1}{2}e^{-\frac{1}{2}}}}{4}\cdot\left|g_{T}(\Delta)-g_{T}\left(\Delta^{\prime}\right)\right|. Intuitively, under instance \Delta , an algorithm pulls the inferior arm g_{T}(\Delta) times on average. By CLT, the algorithm (up to time T ) cannot effectively distinguish instance \Delta from an alternative instance \Delta^{\prime} satisfying |\Delta^{\prime}-\Delta|\sim\frac{1}{\sqrt{g_{T}(\Delta)}} due to noisy reward samples. Thus under \Delta , the pull counts must “stretch” at times to behave as if the instance were \Delta^{\prime} . The standard deviation of the pull counts under \Delta should thus be at least \left|g_{T}(\Delta)-g_{T}\left(\Delta^{\prime}\right)\right| . The formal proof of Lemma 6.1 utilizes the Bretagnolle-Huber inequality and the divergence decomposition. Details are provided in Section 8 . We next establish a fundamental tension between \sup_{\Delta\in[0,1]}g_{T}(\Delta)\,\Delta\qquad\text{and}\qquad\sup_{\Delta\in[0,1]}\Bigl|\,g_{T}(\Delta)-g_{T}\!\Bigl(\Delta+\tfrac{1}{\sqrt{g_{T}(\Delta)}}\Bigr)\Bigr|. To make the former small, g_{T}(\Delta) must decay rapidly as \Delta increases. In contrast, making the latter small requires g_{T}(\cdot) to vary slowly over \Delta\in[0,1] . These two requirements cannot hold simultaneously. We formalize this tension in the following lemma. Lemma 6.2 There exists an absolute constant c , such that for any active-learning algorithm \displaystyle\liminf_{T\rightarrow\infty}\frac{\left(\sup_{\Delta\in[0,1]}g_{T}(\Delta)\Delta\right)\left(\sup_{\Delta\in[0,1]}\left|g_{T}(\Delta)-g_{T}\left(\Delta+\frac{1}{\sqrt{g_{T}(\Delta)}}\right)\right|\right)}{T^{\frac{3}{2}}}>c. Proof 6.3 Proof of Lemma 6.2 For each T , define a sequence of instances with \Delta_{0,T}=0 and recursively \Delta_{m+1,T}=\Delta_{m,T}+\frac{1}{\sqrt{g_{T}(\Delta_{m,T})}},m\geq 0. By symmetry g_{T}(0)=T/2. Let \tau_{T}\triangleq\inf\{m\geq 1:g_{T}(\Delta_{m,T})<\frac{T}{4}\} be the first time in the instance sequence that the expected pull count of the inferior arm drops below T/4. Then for any m\leq\tau_{T}-1 , it holds that \frac{T}{4}\leq g_{T}(\Delta_{m,T})\leq T . This yields \frac{m}{\sqrt{T}}\leq\Delta_{m,T}\leq\frac{2m}{\sqrt{T}},\qquad 0\leq m\leq\tau_{T}. If \Delta_{\tau_{T},T}>1 , then there exists a time m\leq\tau_{T} such that \Delta_{m-1,T}<1 yet \Delta_{m,T}\geq 1 , due to monotonicity. Then \Delta_{m-1,T}=\Delta_{m,T}-\frac{1}{\sqrt{g_{T}(\Delta_{m-1,T})}}\geq 1-\frac{{2}}{\sqrt{T}}\geq\frac{1}{2} for T\geq{16} . Consequently, \Delta_{m-1,T}\cdot g_{T}\left(\Delta_{m-1,T}\right)\geq\frac{1}{2}\times\frac{T}{4}=\frac{T}{8} . Since the algorithm is active learning, this case should not occur infinitely often. Thus \Delta_{\tau_{T},T}\leq 1 for T sufficiently large. This further implies \Delta_{m,T}\leq 1 for all m\leq\tau_{T} for T sufficiently large. Next, we consider two cases. In Case 1, suppose g_{T}(\Delta_{\tau_{T},T})\leq\frac{T}{20} . Then combining with the definition of \tau_{T} , g_{T}(\Delta_{\tau_{T-1},T})-g_{T}(\Delta_{\tau_{T},T})\geq\frac{T}{4}-\frac{T}{20}=\frac{T}{5}. We thus have \sup_{\Delta\in[0,1]}\left|g_{T}(\Delta)-g_{T}\left(\Delta+\frac{1}{\sqrt{g_{T}(\Delta)}}\right)\right|\geq g_{T}(\Delta_{\tau_{T-1},T})-g_{T}(\Delta_{\tau_{T},T})\geq\frac{T}{5} for T sufficiently large. Apply the standard minimax regret lower bound for Gaussian bandits (c.f. Thm. 15.2 in Lattimore and Szepesvári 2020 ) \sup_{\Delta\in[0,1]}\Delta g_{T}(\Delta)\geq\frac{1}{27}\sqrt{T} . Put together, we have \left(\sup_{\Delta\in[0,1]}g_{T}(\Delta)\Delta\right)\left(\sup_{\Delta\in[0,1]}\left|g_{T}(\Delta)-g_{T}\left(\Delta+\frac{1}{\sqrt{g_{T}(\Delta)}}\right)\right|\right)\geq\frac{1}{135}T^{\frac{3}{2}}. Next we consider Case 2, i.e. g_{T}(\Delta_{\tau_{T},T})>\frac{T}{20} . It then must be \frac{T}{20}\frac{T}{4\tau_{T}}. Recall that \Delta_{\tau_{T},T}\geq\frac{\tau_{T}}{\sqrt{T}} . Combining with g_{T}(\Delta_{\tau_{T},T})>\frac{T}{{20}} , we conclude that \sup_{\Delta\in[0,1]}g_{T}(\Delta)\Delta\geq g_{T}(\Delta_{\tau_{T},T})\Delta_{\tau_{T},T}>\frac{\tau_{T}\sqrt{T}}{20}. Put together, we have \left(\sup_{\Delta\in[0,1]}g_{T}(\Delta)\Delta\right)\left(\sup_{\Delta\in[0,1]}\left|g_{T}(\Delta)-g_{T}\left(\Delta+\frac{1}{\sqrt{g_{T}(\Delta)}}\right)\right|\right)\geq\frac{1}{80}T^{\frac{3}{2}}. Combining the above cases then completes the proof with the explicit constant c=\frac{1}{135}. ∎ Theorem 3.1 is then immediate. Proof 6.4 Proof of Theorem 3.1 By definition and that g_{T}(\Delta)\geq 1 for T\geq 2 (since we assume the algorithm pulls each arm at least once), \mathcal{S}_{T}\geq\sup_{\Delta\in[0,2]}S_{T}(\Delta)\geq\sup_{\Delta\in[0,1]}\max\left\{S_{T}(\Delta),S_{T}\left(\Delta+\frac{1}{\sqrt{g_{T}(\Delta)}}\right)\right\}, Apply Lemma 6.1 to the above, we have \mathcal{S}_{T}\geq\frac{\sqrt{\frac{1}{2}e^{-\frac{1}{2}}}}{4}\cdot\sup_{\Delta\in[0,1]}\left|g_{T}(\Delta)-g_{T}\left(\Delta+\frac{1}{\sqrt{g_{T}(\Delta)}}\right)\right|. Meanwhile, \mathcal{R}_{T}\geq\sup_{\Delta\in[0,1]}g_{T}(\Delta)\Delta . Thus, apply Lemma 6.2 , \displaystyle\liminf_{T\rightarrow\infty}\frac{\mathcal{R}_{T}\mathcal{S}_{T}}{T^{\frac{3}{2}}} \displaystyle\geq\liminf_{T\rightarrow\infty}\frac{\frac{1}{4}\sqrt{\frac{1}{2}e^{-\frac{1}{2}}}\left(\sup_{\Delta\in[0,1]}g(\Delta)\Delta\right)\left(\sup_{\Delta\in[0,1]}\left|g(\Delta)-g\left(\Delta+\frac{1}{\sqrt{g(\Delta)}}\right)\right|\right)}{T^{\frac{3}{2}}} \displaystyle>\frac{1}{540}\sqrt{\frac{1}{2}e^{-\frac{1}{2}}}, completing the proof. ∎ 7 Concluding Remarks In this paper, we identify and study a side effect of learning: the large variability in allocation. In the stochastic multi-armed bandit model, we show that there is a fundamental trade-off between any algorithm’s allocation variability and expected regret, both evaluated in a worst-case sense, as long as the algorithm has an intention to learn. We further propose a family of UCB-f algorithms, a natural extension of UCB1 , that achieves the Pareto frontier. Several natural questions arise from our analysis, which we outline below. • The lower bound in Theorem 3.1 does not capture the dependence on the number of arms. Also the explicit K -dependence in Theorem 4.1 is likely suboptimal. It remains open how the Pareto frontier scales with K . • It is natural to ask whether other popular algorithms like Thompson Sampling can be modified to attain the full frontier. This necessary require analytical techniques different from the ones used for UCB1-f . • Although our upper and lower bounds match up to polylog factors, it remains open whether the frontier can be sharpened further to remove these factors. • It would be interesting to extend our results to contextual bandits and, more broadly, to reinforcement learning, where exploration policies determine state–action visitation frequencies. The MAB model can be viewed as a special case of contextual bandits in which contexts are orthogonal and thus admit no information sharing across actions. We believe that with richer information sharing, the regret-allocation-variability trade-off may be less severe and allocational instability could be partially mitigated. • Our findings point to intriguing connections with statistical inference under adaptive data collection. An open direction is to understand the rates at which asymptotic normality emerges for estimators based on adaptively collected samples. Concretely, one explicit question is to characterize the convergence rate of \sigma_{i}\sqrt{N_{i,T}}(\hat{\mu}_{i,T}-\mu_{i}) to the standard normal distribution as T\to\infty for algorithms deemed stable, and in particular, to determine how this rate depends on the algorithm’s allocation variability. We view these as interesting directions and leave them for future investigation. \APPENDIX This appendix collects proofs omitted from the main text. There are five sections. In Section 8 we prove Lemma 6.1 and Corollary 3.4 . Section 9 proves Theorem 3.5 . In Section 10 , we provide the analysis of the proposed UCB-f family. Section 11 presents other proofs of Section 4 . Finally, we prove Corollary 5.1 and Corollary 5.3 in Section 12 . 8 Proof of Lemma 6.1 and Corollary 3.4 We first prove Lemma 6.1 , which then completes the proof of Theorem 3.1 (see Section 6 ). Recall that we consider two-armed Gaussian bandit instances. To simplify notations, we drop the subscript T , replacing S_{T}(\cdot) by S(\cdot) (the instance-dependent allocation variability), N_{2,T}(\cdot) by N(\cdot) (the number of pulls of the inferior arm) and g_{T}(\cdot) by g(\cdot) (the expected value of N(\cdot) ). Let P_{\nu\pi} denote the probability measure induced by the T -round interconnection of the algorithm \pi and a bandit instance \nu . We sometimes omit the subscript \pi and denote by P_{\nu} when the algorithm is clear from the context. Let D_{\text{KL}}(P\|Q) denote the KL divergence between two probability measures P and Q . We then proceed with a sequence of lemmas. Lemma 8.1 For any two-armed bandit instances \nu and \nu^{\prime} and any fixed algorithm, suppose WLOG g(\nu)\geq g(\nu^{\prime}) , then \displaystyle\max\{S(\nu),S(\nu^{\prime})\}\geq\frac{g(\nu)-g(\nu^{\prime})}{4}\sqrt{P_{\nu}\left(N(\nu)<\frac{g(\nu)+g(\nu^{\prime})}{2}\right)+P_{\nu^{\prime}}\left(N(\nu^{\prime})\geq\frac{g(\nu)+g(\nu^{\prime})}{2}\right)}. Proof 8.2 Proof of Lemma 6.1 Observe that \displaystyle S(\nu) \displaystyle=\sqrt{\mathbb{E}_{\nu}[(N(\nu)-g(\nu))^{2}]} \displaystyle\geq\sqrt{\mathbb{E}_{\nu}\left[(N(\nu)-g(\nu))^{2}\mathds{1}\left\{N(\nu)<\frac{g(\nu)+g(\nu^{\prime})}{2}\right\}\right]} \displaystyle\geq\frac{g(\nu)-g(\nu^{\prime})}{2}\sqrt{P_{\nu}\left(N(\nu)<\frac{g(\nu)+g(\nu^{\prime})}{2}\right)}. Similarly, S(\nu^{\prime})\geq\frac{g(\nu)-g(\nu^{\prime})}{2}\sqrt{P_{\nu^{\prime}}\left(N(\nu^{\prime})\geq\frac{g(\nu)+g(\nu^{\prime})}{2}\right)}. Also \max\{S(\nu),S(\nu^{\prime})\}\geq\frac{S(\nu)+S(\nu^{\prime})}{2}. Apply the bounds on S(\nu),S(\nu^{\prime}) derived above, we have \displaystyle\frac{S(\nu)+S(\nu^{\prime})}{2} \displaystyle\geq\frac{g(\nu)-g(\nu^{\prime})}{4}\left(\sqrt{P_{\nu}\left(N(\nu)<\frac{g(\nu)+g(\nu^{\prime})}{2}\right)}+\sqrt{P_{\nu^{\prime}}\left(N(\nu^{\prime})\geq\frac{g(\nu)+g(\nu^{\prime})}{2}\right)}\right) \displaystyle\geq\frac{g(\nu)-g(\nu^{\prime})}{4}\sqrt{P_{\nu}\left(N(\nu)<\frac{g(\nu)+g(\nu^{\prime})}{2}\right)+P_{\nu^{\prime}}\left(N(\nu^{\prime})\geq\frac{g(\nu)+g(\nu^{\prime})}{2}\right)}. Combining the above completes the proof. ∎ We recall the Bretagnolle-Huber inequality (cf. Thm. 14.2 in Lattimore and Szepesvári 2020 ). Lemma 8.3 (Bretagnolle–Huber inequality) Let P,Q be probability measures on the same measurable space, and let A be an arbitrary event. Then, P(A)+Q(A^{c})\geq\frac{1}{2}e^{-D_{\text{KL}}(P\|Q)}. A direct application of Lemma 8.3 with P_{\nu\pi} and P_{\nu^{\prime}\pi} , and the event \left\{N<\frac{g(\nu)+g(\nu^{\prime})}{2}\right\} yields Lemma 8.4 Consider any \nu,\nu^{\prime}\in\mathcal{P} and a fixed algorithm \pi . Then we have \displaystyle P_{\nu\pi}\left(N<\frac{g(\nu)+g(\nu^{\prime})}{2}\right)+P_{\nu^{\prime}\pi}\left(N\geq\frac{g(\nu)+g(\nu^{\prime})}{2}\right)\geq\max\left\{\frac{1}{2}e^{-D_{\text{KL}}(P_{\nu\pi}\|P_{\nu^{\prime}\pi})},\frac{1}{2}e^{-D_{\text{KL}}(P_{\nu^{\prime}\pi}\|P_{\nu\pi})}\right\}. Here we remark that the two notations P_{\nu\pi}\left(N<\frac{g(\nu)+g(\nu^{\prime})}{2}\right) and P_{\nu}\left(N(\nu)<\frac{g(\nu)+g(\nu^{\prime})}{2}\right) refer to the same probability (i.e., the same event under the law induced by running algorithm \pi on instance \nu ). The next lemma follows from the divergence decomposition lemma (cf. Lemma 15.1 in Lattimore and Szepesvári 2020 ), whose proof we omit. Lemma 8.5 Consider any \nu,\nu^{\prime}\in\mathcal{P} and any algorithm \pi . WLOG assume that \mu_{1}\geq\mu_{2} and \mu_{1}^{\prime}\geq\mu_{2}^{\prime} , namely, arm 1 is the best arm. Then \displaystyle D_{\text{KL}}(P_{\nu\pi}\|P_{\nu^{\prime}\pi})=(T-g(\nu))D_{\text{KL}}(\nu_{1}\|\nu_{1}^{\prime})+g(\nu)D_{\text{KL}}(\nu_{2}\|\nu_{2}^{\prime}), \displaystyle D_{\text{KL}}(P_{\nu^{\prime}\pi}\|P_{\nu\pi})=(T-g(\nu^{\prime}))D_{\text{KL}}(\nu_{1}^{\prime}\|\nu_{1})+g(\nu^{\prime})D_{\text{KL}}(\nu_{2}^{\prime}\|\nu_{2}). Recall that for Gaussian distribution \mathcal{N}(\mu,1) and \mathcal{N}(\mu^{\prime},1) , their KL divergence is equal to \frac{1}{2}(\mu-\mu^{\prime})^{2} . Consider two Gaussian measures \nu=\{\mathcal{N}(\mu_{1},1),\mathcal{N}(\mu_{2},1)\} and \nu^{\prime}=\{\mathcal{N}(\mu_{1}^{\prime},1),\mathcal{N}(\mu_{2}^{\prime},1)\} , where \mu_{1}\geq\mu_{2} , \mu_{1}^{\prime}\geq\mu_{2}^{\prime} and \mu_{1}=\mu_{1}^{\prime} . Lemma 8.4 – Lemma 8.5 together yield the following. Lemma 8.6 Consider any algorithm \pi . For the two Gaussian measures \nu,\nu^{\prime} described above with |\mu_{2}-\mu_{2}^{\prime}|=\frac{1}{\sqrt{g(\nu)}} or |\mu_{2}-\mu_{2}^{\prime}|=\frac{1}{\sqrt{g(\nu^{\prime})}} , \displaystyle P_{\nu\pi}\left(N(\nu)<\frac{g(\nu)+g(\nu^{\prime})}{2}\right)+P_{\nu^{\prime}\pi}\left(N(\nu^{\prime})\geq\frac{g(\nu)+g(\nu^{\prime})}{2}\right)\geq\frac{1}{2}e^{-\frac{1}{2}}. We now complete the proof of Lemma 6.1 . Proof 8.7 Proof of Lemma 6.1 The lemma directly follows from Lemma 8.1 and Lemma 8.6 . ∎ We now provide the proof of Corollary 3.4 . Proof 8.8 Proof of Corollary 3.4 The proof is similar to the proof of Theorem 3.1 . In particular, Lemma 6.1 indicates that it suffices to find values of \Delta_{T}=O(T^{\alpha-\frac{1}{2}}) such that g_{T}(\Delta_{T})=\Theta(T) (so that \Delta_{T}^{\prime}=O(T^{\alpha-\frac{1}{2}}) as well) and \left|g_{T}(\Delta_{T})-g_{T}(\Delta_{T}^{\prime})\right|=\Omega(T^{1-\alpha}) . We utilize the proof of Lemma 6.2 to find this \Delta_{T} . In particular, in the proof of Lemma 6.2 , there are two cases. In the first case, let \Delta_{T}=\Delta_{\tau_{T}-1,T} . Then we have g_{T}(\Delta_{T})\geq\frac{T}{4} and \left|g_{T}(\Delta_{T})-g_{T}(\Delta_{T}^{\prime})\right|\geq\frac{T}{5} when T is sufficiently large. Also, since the worst-case regret is \Theta(T^{\frac{1}{2}+\alpha}) , it must be that \Delta_{T}=O(T^{\alpha-\frac{1}{2}}) . In the second case, from the proof, there must exist \Delta_{T}\in[0,\Delta_{\tau_{T}-1,T}] such that g_{T}(\Delta_{T})\geq\frac{T}{4} and \left|g_{T}(\Delta_{T})-g_{T}(\Delta_{T}^{\prime})\right|\geq\frac{T}{4\tau_{T}} , where \tau_{T} satisfies \frac{\tau_{T}\sqrt{T}}{20}<\sup_{\Delta\in[0,1]}g_{T}(\Delta)\Delta=\Theta(T^{\frac{1}{2}+\alpha}) . Then, it must be that \tau_{T}=O(T^{\alpha}) hence \left|g_{T}(\Delta_{T})-g_{T}(\Delta_{T}^{\prime})\right|=\Omega(T^{1-\alpha}) , and that \Delta_{T}=O(T^{\alpha-\frac{1}{2}}) since g_{T}(\Delta_{T})\geq\frac{T}{4} and the worst-case regret is \Theta(T^{\frac{1}{2}+\alpha}) . ∎ 9 Proof of Theorem 3.5 To prove Theorem 3.5 , we first introduce some additional notation. Recall that \nu_{1}(\Delta)=\mathcal{N}(0,1), \nu_{2}(\Delta)=\mathcal{N}(-\Delta,1) . Also recall that \mathbf{X}^{i}\triangleq(X^{i}_{1},\dots,X^{i}_{T}) is the rewards of the first T pulls from arm i=1,2 . Then \mathbf{X}^{i} follows i.i.d. \mathcal{N}(\mu_{i},1) with \mu_{1}=0 and \mu_{2}=-\Delta. Let \mathbf{X}=(\mathbf{X}^{1},\mathbf{X}^{2}) . The first T rounds of interaction between any algorithm and the bandits must be within \mathbf{X} . We adopt notation \mathbb{E}_{\Delta},P_{\Delta} to emphasize the underlying model \nu(\Delta) . In particular, f_{\Delta}(\cdot) denote the p.d.f. of \mathbf{X} under \nu(\Delta) . We also denote N=N_{2,T} the pull counts of the second (inferior) arm. Before proving the theorem, we first state the standard change of measure identity, the proof of which we omit. Lemma 9.1 (Change of measure) Suppose h:\mathbb{R}^{2T}\to\mathbb{R} is a measurable, bounded function that maps \mathbf{X} to a real number. Then \mathbb{E}_{\Delta}[h(\mathbf{X})]=\mathbb{E}_{\Delta^{\prime}}\left[h(\mathbf{X})\cdot\left(\frac{f_{\Delta}(\mathbf{X})}{f_{\Delta^{\prime}}(\mathbf{X})}\right)\right] We are now ready to prove Theorem 3.5 . Proof 9.2 Proof of Theorem 3.5 Recall that g_{T}(\Delta)=\mathbb{E}_{\Delta}[N] , where N is the pull count of the second arm, and we omit its dependence on the instance \Delta , since this dependence is made explicit in \mathbb{E}_{\Delta} . By definition, R_{T}\left(\frac{3c_{0}}{\sqrt{T}}\right)\leq\mathcal{R}_{T}\leq c_{0}\sqrt{T} for T sufficiently large (hence \frac{3c_{0}}{\sqrt{T}}\leq 2 ). Recall that R_{T}(\Delta)=\Delta g_{T}(\Delta) . We thus have g_{T}\left(\frac{3c_{0}}{\sqrt{T}}\right)\leq\frac{T}{3} . We also recall g_{T}(0)=T/2. Denote \frac{3c_{0}}{\sqrt{T}} by \Delta_{0}. For any \Delta , either |g_{T}(\Delta)-g_{T}(0)|\geq\frac{T}{12} or |g_{T}(\Delta)-g_{T}(\Delta_{0})|\geq\frac{T}{12} . WLOG let’s assume g_{T}(0)-g_{T}(\Delta)\geq\frac{T}{12} (in other cases the reasoning is similar and we omit). Under this condition, we derive the following bound on S_{T}(\Delta) . \displaystyle S_{T}(\Delta) \displaystyle=\sqrt{\mathbb{E}_{\Delta}[(N-g_{T}(\Delta))^{2}]} \displaystyle\geq\sqrt{\mathbb{E}_{\Delta}\left[(N-g_{T}(\Delta))^{2}\mathds{1}\left\{N>\frac{g_{T}(\Delta)+g_{T}(0)}{2}\right\}\right]} \displaystyle\geq\frac{|g_{T}(\Delta)-g_{T}(0)|}{2}\sqrt{P_{\Delta}\left(N>\frac{g_{T}(\Delta)+g_{T}(0)}{2}\right)} \displaystyle\geq\frac{1}{24}\sqrt{P_{\Delta}\left(N>\frac{g_{T}(\Delta)+g_{T}(0)}{2}\right)}\cdot T. Let \mathcal{B}=\left\{N>\frac{g_{T}(\Delta)+g_{T}(0)}{2}\right\} . It suffices to show P_{\Delta}\left(\mathcal{B}\right) is lower bounded by a constant. Importantly, under any algorithm, N=N(\mathbf{X}) is a measurable function of \mathbf{X} satisfying the bound N\leq T . Thus we may apply Lemma 9.1 with \Delta^{\prime}=0 and h(\cdot)=\mathds{1}\{\mathcal{B}\} : \displaystyle P_{\Delta}\left(\mathcal{B}\right)=\mathbb{E}_{\Delta}\left[\mathds{1}\left\{\mathcal{B}\right\}\right]=\mathbb{E}_{0}\left[\mathds{1}\left\{\mathcal{B}\right\}\cdot\left(\frac{f_{\Delta}(\mathbf{X})}{f_{0}(\mathbf{X})}\right)\right]. By definition of \nu(\Delta) , we have f_{\Delta}(\mathbf{X})=\prod_{j=1}^{T}\left(\frac{1}{2\pi}\exp\left(-\frac{(X^{1}_{j})^{2}}{2}\right)\exp\left(-\frac{(X^{2}_{j}+\Delta)^{2}}{2}\right)\right). Plugging back to get \displaystyle P_{\Delta}\left(\mathcal{B}\right) \displaystyle=\mathbb{E}_{0}\left[\mathds{1}\left\{\mathcal{B}\right\}\prod_{j=1}^{T}\exp\left(-\frac{(X^{2}_{j}+\Delta)^{2}}{2}+\frac{(X^{2}_{j})^{2}}{2}\right)\right] \displaystyle=\mathbb{E}_{0}\left[\mathds{1}\left\{\mathcal{B}\right\}\cdot\exp\left(-\frac{\Delta^{2}}{2}T-\Delta\sum_{j=1}^{T}X^{2}_{j}\right)\right]. Let \mathcal{A}=\left\{\frac{1}{\sqrt{T}}\sum_{j=1}^{T}X^{2}_{j}<3\right\} , we lower bound the above to get \displaystyle\mathbb{E}_{0}\left[\mathds{1}\left\{\mathcal{B}\right\}\cdot\exp\left(-\frac{\Delta^{2}}{2}T-\Delta\sum_{j=1}^{T}X^{2}_{j}\right)\right] \displaystyle\geq\mathbb{E}_{0}\left[\mathds{1}\left\{\mathcal{B}\right\}\cdot\exp\left(-\frac{\Delta^{2}}{2}T-\Delta\sum_{j=1}^{T}X^{2}_{j}\right)\mathds{1}\{\mathcal{A}\}\right] \displaystyle\geq\mathbb{E}_{0}\left[\mathds{1}\left\{\mathcal{B}\right\}\cdot\exp\left(-\frac{\Delta^{2}}{2}T-3\Delta\sqrt{T}\right)\mathds{1}\{\mathcal{A}\}\right] \displaystyle\geq\exp\left(-\frac{c_{1}^{2}}{2}-3c_{1}\right)\mathbb{E}_{0}\left[\mathds{1}\left\{\mathcal{B}\right\}\cdot\mathds{1}\{\mathcal{A}\}\right] \displaystyle=\exp\left(-\frac{c_{1}^{2}}{2}-3c_{1}\right)\cdot P_{0}\left(\mathcal{B}\cap\mathcal{A}\right) where the second to the last inequality follows from \Delta<\Delta_{0}=\frac{c_{1}}{\sqrt{T}}. Observe that, \displaystyle\frac{T}{2} \displaystyle=\mathbb{E}_{0}\left[N\right] \displaystyle=\mathbb{E}_{0}\left[N\mathds{1}\{\mathcal{B}\}\right]+\mathbb{E}_{0}\left[N\mathds{1}\{\mathcal{B}^{c}\}\right] \displaystyle\leq\frac{g_{T}(\Delta)+g_{T}(0)}{2}\cdot P_{0}\left(\mathcal{B}^{c}\right)+T\cdot P_{0}\left(\mathcal{B}\right) \displaystyle\leq\left(\frac{T}{2}-\frac{T}{24}\right)\cdot P_{0}\left(\mathcal{B}^{c}\right)+T\cdot P_{0}\left(\mathcal{B}\right), which yields P_{0}\left(\mathcal{B}\right)\geq\frac{1}{11}. On the other hand, under \nu(0) , \sum_{j=1}^{T}X^{2}_{j}\sim\mathcal{N}(0,T) , thus P_{0}(\mathcal{A})=\Phi(3) , where \Phi is the standard normal c.d.f. Combining the above with an additional bound: P_{0}\left(\mathcal{B}\cap\mathcal{A}\right)=P_{0}\left(\mathcal{B}\right)+P_{0}\left(\mathcal{A}\right)-P_{0}\left(\mathcal{B}\cup\mathcal{A}\right)\geq\frac{1}{11}+\Phi(3)-1>\frac{1}{16}. Plugging back to the S_{T}(\Delta) bound to get S_{T}(\Delta)\geq\frac{e^{-\frac{c_{1}^{2}}{2}-3c_{1}}}{100}T , completing the proof. ∎ 10 Proof of Theorem 4.1 We introduce some additional notation. Throughout, fix a bandit instance \nu=(\nu_{1},\dots,\nu_{K})\in\mathfrak{P}_{\text{sg}}(M,\sigma) . Let \widehat{\mu}_{i}(s)\triangleq\frac{1}{s}\sum_{t=1}^{s}X^{i}_{t} denote the empirical mean of arm i based on its first s samples. Assume without loss of generality that the arm means are in a descending order, i.e. \mu_{1}\geq\mu_{2}\geq\dots\mu_{K} . In particular, the first arm has the largest mean, i.e. \mu_{1}=\mu^{*} . Define n_{i}^{t},i=1,2,...,K , as the solution of the following fluid system of equations. \displaystyle\begin{cases}\mu_{1}+\dfrac{f(t)}{\sqrt{n_{1}^{t}}}=\mu_{i}+\dfrac{f(t)}{\sqrt{n_{i}^{t}}},&\forall i=2,\dots,K,\\[5.69054pt] \sum_{i=1}^{K}n_{i}^{t}=t.\end{cases} (2) For brevity, denote n_{i}=n_{i}^{T} and N_{i}=N_{i,T} . We state two auxiliary lemmas about f(\cdot) and n_{i}^{t} . Lemma 10.1 If the exploration function f(\cdot) satisfies both f(t) and \frac{\sqrt{t}}{f(t)} increasing in t , then for any \nu\in\mathcal{P} , both n_{i}^{t} and \frac{\sqrt{n_{i}^{t}}}{f(t)} increase in t for all i=1,2,...,K . Proof 10.2 Proof We first prove that \frac{\sqrt{n_{i}^{t}}}{f(t)} increases in t for all i . Suppose this is not true, then there exists i\in\{1,2,...,K\} and t_{1}\frac{\sqrt{n_{i}^{t_{2}}}}{f(t_{2})} . By definition, for any j\neq i , we have \displaystyle\mu_{i}+\frac{f(t_{1})}{\sqrt{n_{i}^{t_{1}}}}=\mu_{j}+\frac{f(t_{1})}{\sqrt{n_{j}^{t_{1}}}},\ \ \mu_{i}+\frac{f(t_{2})}{\sqrt{n_{i}^{t_{2}}}}=\mu_{j}+\frac{f(t_{2})}{\sqrt{n_{j}^{t_{2}}}}, hence by subtracting the above two equations, we get \displaystyle\frac{f(t_{1})}{\sqrt{n_{i}^{t_{1}}}}-\frac{f(t_{2})}{\sqrt{n_{i}^{t_{2}}}}=\frac{f(t_{1})}{\sqrt{n_{j}^{t_{1}}}}-\frac{f(t_{2})}{\sqrt{n_{j}^{t_{2}}}}<0. That is, \frac{\sqrt{n_{i}^{t_{1}}}}{f(t_{1})}>\frac{\sqrt{n_{i}^{t_{2}}}}{f(t_{2})} or equivalently \frac{n_{i}^{t_{1}}}{f(t_{1})^{2}}>\frac{n_{i}^{t_{2}}}{f(t_{2})^{2}} for all i=1,2,...,K . Sum over the inequalities for all i , we get \displaystyle\frac{t_{1}}{f(t_{1})^{2}}=\frac{\sum_{i=1}^{K}n_{i}^{t_{1}}}{f(t_{1})^{2}}>\frac{\sum_{i=1}^{K}n_{i}^{t_{2}}}{f(t_{2})^{2}}=\frac{t_{2}}{f(t_{2})^{2}}, contradicting \frac{\sqrt{t}}{f(t)} being increasing in t . The term n_{i}^{t} increases in t simply follows from the fact that both f(t) and \frac{\sqrt{n_{i}^{t}}}{f(t)} increase in t . Lemma 10.3 If the exploration function f(\cdot) satisfies both f(t) and \frac{\sqrt{t}}{f(t)} increasing in t , then \inf_{\nu\in\mathfrak{P}_{\text{sg}}}n_{i} and \inf_{\nu\in\mathfrak{P}_{\text{sg}}}\frac{n_{2}}{f(T)} both diverges as T\to\infty for any i=2,...,K . Moreover, for such f(\cdot) , \sup_{\nu\in\mathfrak{P}_{\text{sg}}}(n_{i}\Delta_{i})=O\left(T^{\frac{1}{2}}f(T)\right) for any i=2,...,K . Proof 10.4 Proof By straightforward algebra, one can get \inf_{\nu\in\mathfrak{P}_{\text{sg}}}n_{i}=\Theta(f(T)^{2}). The rest of the proof follows and is omitted. ∎ We now establish the following key lemma to prove Theorem 4.1 . Lemma 10.5 Consider UCB-f with an exploration function f(\cdot) such that both f(t)/\log t and \sqrt{t}/f(t) are non-decreasing in t . There exists a constant \underline{T}\equiv\underline{T}(M,\sigma,K,\alpha) such that, for any \nu\in\mathfrak{P}_{\mathrm{sg}} , any T\geq\underline{T} , and any i\in\{1,\dots,K\} , \displaystyle P_{\nu}\!\left(N_{i}-n_{i}>q\right) \displaystyle\leq\frac{K-1}{4q^{4}},\qquad\forall\,q\geq\frac{\log T}{f(T)}\left(n_{i}\wedge n_{2}\right), \displaystyle P_{\nu}\!\left(N_{i}-n_{i}<-q\right) \displaystyle\leq\frac{(K-1)^{6}}{4q^{4}},\qquad\forall\,q\geq\frac{(K-1)\log T}{f(T)}\,n_{2}. Proof 10.6 Proof Throughout, fix \nu\in\mathfrak{P}_{\text{sg}} and we omit the subscript \nu for brevity. By Lemma 10.1 , n_{i}^{t}\leq n_{i} and \frac{n_{i}}{f(T)}\geq\frac{n_{i}^{t}}{f(t)} for any t\leq T and i\in[K]. We first bound the right tail P(N_{i}>n_{i}+q) . Bounding P(N_{i}>n_{i}+q) . Observe that \{N_{i}>n_{i}+q\} implies that there exists time t\in[n_{i}+q+1,T] , such that N_{i,t-1}=n_{i}+q and A_{t}=i . By the allocation rule of UCB-f , at time t , the UCB index of arm i is maximal among all arms: \widehat{\mu}_{i}(n_{i}+q)+\frac{f(t)}{\sqrt{n_{i}+q}}\ \geq\ \widehat{\mu}_{j}(N_{j,t-1})+\frac{f(t)}{\sqrt{N_{j,t-1}}}\qquad\forall j\neq i. Meanwhile, N_{i,t-1}=n_{i}+q implies that \sum_{j\neq i}N_{j,t-1}\ =\ t-1-(n_{i}+q). Since n_{i}^{s}\leq n_{i} for s\leq T , it follow that \sum_{j\neq i}N_{j,t-1}\ =\ t-1-(n_{i}+q)\ \leq\ t-1-(n_{i}^{t-1}+q)\ =\ \sum_{j\neq i}n_{j}^{t-1}\ -\ q. With a pigeonhole argument, there must exist j\neq i such that N_{j,t-1}\leq n_{j}^{t-1}-\frac{q}{K-1}. Combining the above and a union bound, we have \displaystyle P(N_{i}>n_{i}+q) \displaystyle\leq\sum_{t=n_{i}+q+1}^{T}\ \sum_{j\neq i}\ \sum_{m=1}^{n_{j}^{t-1}-\frac{q}{K-1}}P\!\left(\widehat{\mu}_{i}(n_{i}+q)+\frac{f(t)}{\sqrt{n_{i}+q}}\geq\widehat{\mu}_{j}(m)+\frac{f(t)}{\sqrt{m}}\right). (3) Fix (t,j,m) in the summation above. Rearrange the index inequality by centering at the means: \big(\widehat{\mu}_{i}(n_{i}+q)-\mu_{i}\big)-\big(\widehat{\mu}_{j}(m)-\mu_{j}\big)\ \geq\ (\mu_{j}-\mu_{i})+f(t)\!\left(\frac{1}{\sqrt{m}}-\frac{1}{\sqrt{n_{i}+q}}\right). Using the defining property of n^{t} and we can rewrite the above RHS as f(t)\!\left(\frac{1}{\sqrt{n_{i}^{t}}}-\frac{1}{\sqrt{n_{i}+q}}+\frac{1}{\sqrt{m}}-\frac{1}{\sqrt{n_{j}^{t}}}\right). By Lemma 10.1 , n_{i}+q=n_{i}^{T}+q\geq n_{i}^{t}+q . Also, n_{j}^{t}\geq n_{j}^{t-1}\geq m+\frac{q}{K-1} . We derive the bound \displaystyle(\mu_{j}-\mu_{i})+f(t)\!\left(\frac{1}{\sqrt{m}}-\frac{1}{\sqrt{n_{i}+q}}\right) \displaystyle\ \geq\ f(t)\!\left(\frac{1}{\sqrt{n_{i}^{t}+q}}-\frac{1}{\sqrt{n_{i}^{t}+q+\frac{q}{K-1}}}+\frac{1}{\sqrt{m}}-\frac{1}{\sqrt{m+\frac{q}{K-1}}}\right), (4) where we used \frac{1}{\sqrt{x}}-\frac{1}{\sqrt{x+q}}\geq\frac{1}{\sqrt{x+q}}-\frac{1}{\sqrt{x+q+\frac{q}{K-1}}} for K\geq 2 with x set to n_{i}^{t} . Let Z=\big(\widehat{\mu}_{i}(n_{i}+q)-\mu_{i}\big)-\big(\widehat{\mu}_{j}(m)-\mu_{j}\big). By assumption and the property of sub-Gaussian random variables, Z is \sigma\sqrt{\frac{1}{n_{i}+q}+\frac{1}{m}} -sub-Gaussian. Particularly, P(Z\geq x)\ \leq\ \exp\!\left(-\frac{x^{2}}{2\sigma^{2}\left(\frac{1}{n_{i}+q}+\frac{1}{m}\right)}\right)\ \leq\ \exp\!\left(-\frac{x^{2}}{2\sigma^{2}\left(\frac{1}{n_{i}^{t}+q}+\frac{1}{m}\right)}\right), where we used n_{i}^{t}\leq n_{i} so \frac{1}{n_{i}+q}\leq\frac{1}{n_{i}^{t}+q} . Combining with ( 4 ) gives P\!\left(\widehat{\mu}_{i}(n_{i}+q)+\frac{f(t)}{\sqrt{n_{i}+q}}\geq\widehat{\mu}_{j}(m)+\frac{f(t)}{\sqrt{m}}\right)\ \leq\ \exp\!\left(-\frac{f(t)^{2}}{2\sigma^{2}}\cdot\frac{(A+B)^{2}}{\frac{1}{n_{i}^{t}+q}+\frac{1}{m}}\right), (5) where A=\frac{1}{\sqrt{n_{i}^{t}+q}}-\frac{1}{\sqrt{n_{i}^{t}+q+\frac{q}{K-1}}} and B=\frac{1}{\sqrt{m}}-\frac{1}{\sqrt{m+\frac{q}{K-1}}} . Next we lower bound the exponent in the above RHS. Define, for x>0 and a>0 , \phi(x,a):=x\left(\frac{1}{\sqrt{x}}-\frac{1}{\sqrt{x+a}}\right)^{2}=\left(1-\sqrt{\frac{x}{x+a}}\right)^{2}. A direct derivative check shows \phi(\cdot,a) is decreasing in x for each fixed a>0 . Note that (n_{i}^{t}+q)A^{2}=\phi\left(n_{i}^{t}+q,\frac{q}{K-1}\right) and mB^{2}=\phi\left(m,\frac{q}{K-1}\right) . Consider two cases. Case 1: m\geq n_{i}^{t}+q . Then \frac{1}{n_{i}^{t}+q}+\frac{1}{m}\leq\frac{2}{n_{i}^{t}+q} and (A+B)^{2}\geq A^{2} , hence \frac{(A+B)^{2}}{\frac{1}{n_{i}^{t}+q}+\frac{1}{m}}\ \geq\ \frac{A^{2}}{2/(n_{i}^{t}+q)}\ =\ \frac{n_{i}^{t}+q}{2}A^{2}\ =\ \frac{1}{2}\,\phi\left(n_{i}^{t}+q,\frac{q}{K-1}\right). Case 2: mn_{i}+q) \displaystyle\leq\sum_{t=n_{i}+q+1}^{T}\ \sum_{j\neq i}\ \sum_{m=1}^{n_{j}^{t-1}-\frac{q}{K-1}}t^{-6}\ \leq\ \sum_{t=n_{i}+q+1}^{T}(K-1)\cdot t\cdot t^{-6} \displaystyle=\ (K-1)\sum_{t=n_{i}+q+1}^{T}t^{-5}\ \leq\ (K-1)\int_{n_{i}+q}^{\infty}x^{-5}\,dx\ =\ \frac{K-1}{4(n_{i}+q)^{4}}\ \leq\ \frac{K-1}{4q^{4}}, where the last inequality uses n_{i}\geq 0 (which holds for all large T ). Also, by Lemma 10.3 , n_{i}=\omega(1) as T\to\infty . hence for sufficiently large T depending on M,\sigma,K , condition n_{i}\geq\underline{T} can hold uniformly over the instance class \mathfrak{P}_{\text{sg}} . This proves the right-tail bound for i\geq 2 when q\geq\frac{\log T}{f(T)}n_{i} . For i=1 , the exact same argument goes through with n_{i} replaced by n_{2} in the threshold. Here such a replacement is possible since in treating the exponent of ( 5 ), we have m\leq n_{j}^{t-1}-\frac{q}{K-1}\ \frac{1}{2}\,\phi\left(n_{2}^{t}+q,\frac{q}{K-1}\right), and the rest of the proof follows. Combining the above completes the proof of the right tail for all i\in[K] . Bounding P(N_{i}0 . We make use of the right tail above to establish a crude bound. In particular, since \sum_{k=1}^{K}N_{k}=\sum_{k=1}^{K}n_{k}=T , we have \{N_{i}q\right\}\ \subseteq\ \bigcup_{j\neq i}\left\{N_{j}-n_{j}>\frac{q}{K-1}\right\}. Therefore, P(N_{i}-n_{i}<-q)\ \leq\ \sum_{j\neq i}P\!\left(N_{j}-n_{j}>\frac{q}{K-1}\right). If q\geq\frac{(K-1)\log T}{f(T)}n_{2} , then for every j\neq i we have \frac{q}{K-1}\geq\frac{\log T}{f(T)}n_{2}\geq\frac{\log T}{f(T)}\left(n_{j}\wedge n_{2}\right) , so the right-tail bound gives P\!\left(N_{j}-n_{j}>\frac{q}{K-1}\right)\ \leq\ \frac{K-1}{4\left(\frac{q}{K-1}\right)^{4}}\ =\ \frac{(K-1)^{5}}{4q^{4}}. Summing over at most K-1 arms yields P(N_{i}-n_{i}<-q)\ \leq\ (K-1)\cdot\frac{(K-1)^{5}}{4q^{4}}\ =\ \frac{(K-1)^{6}}{4q^{4}} as claimed. This completes the proof. ∎ We are now ready to prove Theorem 4.1 . Proof 10.7 Proof of Theorem 4.1 Fix \alpha\in[0,\tfrac{1}{2}) . Recall n_{i}=n_{i}^{T} is the solution of the fluid system at horizon T , and we use N_{i}=N_{i,T} interchangeably. Allocation variability. By Lemma 10.5 , for any T\geq\underline{T} , any \nu\in\mathfrak{P}_{\text{sg}} and any i\in[K] , P\big(|N_{i}-n_{i}|>q\big)\ \leq\ \frac{(K-1)^{6}}{2q^{4}},\qquad\forall q\geq\frac{(K-1)\log T}{f(T)}n_{2}. Fix q_{0}\triangleq\frac{(K-1)\log T}{f(T)}n_{2} . Using {\mathbb{E}}[Z^{2}]=\int_{0}^{\infty}2u\,P(|Z|>u)\,du , we obtain \displaystyle{\mathbb{E}}\big[(N_{i}-n_{i})^{2}\big] \displaystyle=\int_{0}^{q_{0}}2u\,P\big(|N_{i}-n_{i}|>u\big)\,du+\int_{q_{0}}^{\infty}2u\,P\big(|N_{i}-n_{i}|>u\big)\,du \displaystyle\leq q_{0}^{2}+\int_{q_{0}}^{\infty}2u\cdot\frac{(K-1)^{6}}{2u^{4}}\,du\;=\;q_{0}^{2}+\frac{(K-1)^{6}}{2}\int_{q_{0}}^{\infty}u^{-3}\,du \displaystyle=\frac{(K-1)^{2}(\log T)^{2}n_{2}^{2}}{f(T)^{2}}+\frac{(K-1)^{4}f(T)^{2}}{4n_{2}^{2}(\log T)^{2}}. By Lemma 10.3 , \inf_{\nu\in\mathfrak{P}_{\text{sg}}}n_{2}/f(T)\to\infty as T\to\infty . Hence there exists T_{0}=T_{0}(K,\alpha) such that for all T\geq T_{0} and all \nu\in\mathfrak{P}_{\text{sg}} , \frac{(K-1)^{4}f(T)^{2}}{4n_{2}^{2}(\log T)^{2}}\ \leq\ \frac{(K-1)^{2}(\log T)^{2}n_{2}^{2}}{f(T)^{2}}. Therefore, for all T\geq\underline{\underline{T}}\triangleq\underline{T}\vee T_{0} , {\mathbb{E}}\big[(N_{i}-n_{i})^{2}\big]\ \leq\ 2\frac{(K-1)^{2}(\log T)^{2}n_{2}^{2}}{f(T)^{2}}, and hence \sqrt{\operatorname{Var}(N_{i})}\ \leq\ \sqrt{{\mathbb{E}}[(N_{i}-n_{i})^{2}]}\ \leq\ \sqrt{2}(K-1)\frac{\log T}{f(T)}n_{2}. Since n_{2}=O(T) , we obtain \mathcal{S}_{T}=\sup_{\nu\in\mathfrak{P}_{\text{sg}}}\max_{i\in[K]}\sqrt{\operatorname{Var}_{\nu}(N_{i,T})}=O\left(\frac{T\log T}{f(T)}\right). Regret. We bound {\mathbb{E}}N_{i} via the right tail. By Lemma 10.5 , for T\geq\underline{T} and any i\in[2,K] , P(N_{i}-n_{i}>q)\ \leq\ \frac{K-1}{4q^{4}},\qquad\forall q\geq\frac{\log T}{f(T)}n_{i}. Taking q=n_{i} and using {\mathbb{E}}[Y]=\int_{0}^{\infty}P(Y>u)\,du for Y\geq 0 , we get \displaystyle{\mathbb{E}}N_{i} \displaystyle\leq n_{i}+{\mathbb{E}}[(N_{i}-n_{i})_{+}]\leq n_{i}+\int_{0}^{n_{i}}1\,du+\int_{n_{i}}^{\infty}P(N_{i}-n_{i}>u)\,du \displaystyle\leq 2n_{i}+\int_{n_{i}}^{\infty}\frac{K-1}{4u^{4}}\,du\;=\;2n_{i}+\frac{K-1}{12\,n_{i}^{3}}. Since by Lemma 10.3 , \inf_{\nu\in\mathfrak{P}_{\text{sg}}}n_{i}\to\infty , there exists T_{0}^{\prime}=T_{0}^{\prime}(M,K) such that \frac{K-1}{12n_{i}^{3}}\leq 2n_{i} for all i and all \nu whenever T\geq T_{0}^{\prime} . Thus for T\geq\underline{T}\vee T_{0}^{\prime} , {\mathbb{E}}_{\nu}N_{i}\leq 4n_{i}, for all i\in[2,K] and \nu\in\mathfrak{P}_{\text{sg}} Therefore, \sup_{\nu\in\mathfrak{P}_{\text{sg}}}R_{T}(\nu)=\sup_{\nu\in\mathfrak{P}_{\text{sg}}}\sum_{i=2}^{K}\Delta_{i}\,{\mathbb{E}}_{\nu}N_{i}\leq 4\sup_{\nu\in\mathfrak{P}_{\text{sg}}}\sum_{i=2}^{K}\Delta_{i}\,n_{i}\leq 4\sum_{i=2}^{K}\sup_{\nu\in\mathfrak{P}_{\text{sg}}}(n_{i}\Delta_{i})=O\!\left(T^{\frac{1}{2}}f(T)\right), where the last step again uses Lemma 10.3 . This completes the proof. ∎ 11 Other proof of Section 4 We first prove Proposition 4.3 . Proof 11.1 Proof of Proposition 4.3 Fix \alpha\in(0,\frac{1}{2}) and \beta\in(0,\alpha] . Consider the following policy for horizon length T . At t=1,...,T-\lceil T^{\frac{1}{2}+\alpha}\rceil , apply UCB-f with exploration function f(t)=t^{\alpha-\beta}\log t . In the remaining time t=T-\lceil T^{\frac{1}{2}+\alpha}\rceil+1,...,T , play each arm round-robin. Then by Theorem 4.1 , it is straightforward to see that under this policy, \displaystyle R_{T}=\Theta(T^{\frac{1}{2}+\alpha}),\ \ S_{T}=\tilde{\Theta}(T^{1-\alpha+\beta}). We now prove Proposition 4.4 . Proof 11.2 Proof of Proposition 4.4 We first prove the lower bound. Lower bound: \sup_{\nu}\sqrt{\operatorname{Var}\hat{R}_{T}(\nu)}=\Omega\left(\frac{\sqrt{T}}{\log T}\right) . Similar to the proof of Theorem 3.1 in Section 6 and Appendix 8 , we focus on the family of instances \nu(\Delta)=\{\mathcal{N}(0,1),\mathcal{N}(-\Delta,1)\} . By Lemma 8.1 , we know that \displaystyle\sup_{\nu\in\mathfrak{P}_{\text{sg}}}\sqrt{\operatorname{Var}_{\nu}(\hat{R}_{T}(\nu))} \displaystyle\geq\sup_{\Delta\in[0,2]}\Delta S_{T}(\Delta) \displaystyle\geq\sup_{\Delta,\Delta^{\prime}\in[0,2],g_{T}(\Delta)\geq g_{T}(\Delta^{\prime})}\Bigg\{\frac{(\Delta\vee\Delta^{\prime})(g_{T}(\Delta)-g_{T}(\Delta^{\prime}))}{4} \displaystyle\qquad\qquad\qquad\cdot\sqrt{P_{\Delta}\left(N_{T}<\frac{g_{T}(\Delta)+g_{T}(\Delta^{\prime})}{2}\right)+P_{\Delta^{\prime}}\left(N_{T}\geq\frac{g_{T}(\Delta)+g_{T}(\Delta^{\prime})}{2}\right)}\Bigg\}. By Lemma 8.4 – 8.6 , \sqrt{P_{\Delta}\left(N_{T}<\frac{g_{T}(\Delta)+g_{T}(\Delta^{\prime})}{2}\right)+P_{\Delta^{\prime}}\left(N_{T}\geq\frac{g_{T}(\Delta)+g_{T}(\Delta^{\prime})}{2}\right)} is lower bounded by a constant when \Delta^{\prime}-\Delta=\frac{1}{\sqrt{g_{T}(\Delta)}} . Therefore it suffices to show \displaystyle\liminf_{T\rightarrow\infty}\frac{\sup_{\Delta\in[0,1]}\left(\Delta+\frac{1}{\sqrt{g_{T}(\Delta)}}\right)\Big|g_{T}(\Delta)-g_{T}\left(\Delta+\frac{1}{\sqrt{g_{T}(\Delta)}}\right)\Big|}{\sqrt{T}/\log T}>0. The proof is similar to that of Lemma 6.2 . In particular, define \displaystyle\xi(T):=\sup_{\Delta\geq 0}\left(\Delta+\frac{1}{\sqrt{g_{T}(\Delta)}}\right)\left|g_{T}(\Delta)-g_{T}\left(\Delta+\frac{1}{\sqrt{g_{T}(\Delta)}}\right)\right|. Then \displaystyle g_{T}(\Delta)-g_{T}\left(\Delta+\frac{1}{\sqrt{g_{T}(\Delta)}}\right)\leq\frac{\xi(T)}{\Delta+\frac{1}{\sqrt{g_{T}(\Delta)}}},\ \ \forall\Delta\geq 0. (7) Define \displaystyle\Delta_{0,T}=0,\ \ \Delta_{m+1,T}=\Delta_{m,T}+\frac{1}{\sqrt{g_{T}(\Delta_{m,T})}},\forall m\geq 0, (8) Since g_{T}(\Delta)\leq T for any \Delta\geq 0 , we have \Delta_{m,T}\geq\frac{m}{\sqrt{T}},\ \ \forall m\geq 0 . Combining this bound with ( 7 ) and telescoping, for all n\geq 1 such that \Delta_{n,T}\leq 1 \displaystyle g_{T}(0)-g_{T}(\Delta_{n,T}) \displaystyle=\sum_{m=1}^{n}(g_{T}(\Delta_{m-1,T})-g_{T}(\Delta_{m,T}))\leq\sum_{m=1}^{n}\frac{\xi(T)}{\Delta_{m,T}}\leq\xi(T)\sum_{m=1}^{n}\frac{\sqrt{T}}{m}. (9) Consider \tau_{T}=\inf\{m\geq 1:g_{T}(\Delta_{m})<\frac{T}{4}\} . Then similar as in the proof of Lemma 6.2 , we must have \Delta_{\tau_{T},T}\leq 1 for T sufficiently large, due to active learning. This also implies \tau_{T}\leq\sqrt{T}, since \Delta_{m,T}\geq\frac{m}{\sqrt{T}} . We thus apply ( 9 ) to get \displaystyle g_{T}(0)-g_{T}(\Delta_{\tau_{T},T})\leq\xi(T)\sum_{m=1}^{\tau_{T}}\frac{\sqrt{T}}{m}\leq\xi(T)\sqrt{T}\left(\log\tau_{T}+1\right)\leq\xi(T)\sqrt{T}\left(\frac{1}{2}\log T+1\right), which is further bounded by \sqrt{T}\log T for T sufficiently large. On the other hand g_{T}(0)-g_{T}(\Delta_{\tau_{T},T})\geq\frac{T}{2}-\frac{T}{4} , due to the symmetry assumption at \Delta=0 and the definition of \tau_{T} . Combining the above we conclude that \xi(T)\geq\frac{\sqrt{T}}{4\log T} for T sufficiently large, completing the proof. Achievability by UCB-f . From the proof of Theorem 4.1 , for any \nu\in\mathfrak{P}_{\text{sg}} and any i\in[K] , we have {\mathbb{E}}_{\nu}[(N_{i}-n_{i})^{2}]\leq\frac{2(K-1)^{2}(\log T)^{2}n_{2}^{2}}{f(T)} In the case of two arms (where arm 2 is the inferior arm), we have \hat{R}_{T}(\nu)=\Delta N_{2} . And, \displaystyle\sqrt{\operatorname{Var}_{\nu}(\hat{R}_{T}(\nu))}=\sqrt{\operatorname{Var}_{\nu}(\Delta N_{2})}\leq\frac{\sqrt{2}(K-1)\log T}{f(T)}\Delta n_{2}. Apply Lemma 10.3 by taking superior over all two armed instances, we thus have the worst case regret variability of UCB-f under any choice of f(t) satisfying the conditions in Theorem 4.1 is at most O(\sqrt{T}\log T) , completing the proof. ∎ 12 Proof of Section 5 We prove Corollary 5.1 and Corollary 5.3 in this appendix. Proof 12.1 Proof of Corollary 5.1 Note that \displaystyle\sup_{\nu\in\mathfrak{P}_{\mathrm{sg}}}\left(R_{T}(\nu)+(S_{T}(\nu))^{\rho}\right)\geq\mathcal{R}_{T},\ \ \sup_{\nu\in\mathfrak{P}_{\mathrm{sg}}}\left(R_{T}(\nu)+(S_{T}(\nu))^{\rho}\right)\geq\sup_{\nu\in\mathfrak{P}_{\mathrm{sg}}}(S_{T}(\nu))^{\rho}=\mathcal{S}_{T}^{\rho}. By the minimax-regret lower bound, we have \liminf_{T\rightarrow\infty}\frac{\sup_{\nu\in\mathfrak{P}_{\mathrm{sg}}}\left(R_{T}(\nu)+(S_{T}(\nu))^{\rho}\right)}{\sqrt{T}}>c_{1} for some constant c_{1}>0 . Consider an active learning policy. By Theorem 3.1 , there exists an increasting sequence of T_{1},T_{2},... with \lim_{j\rightarrow\infty}T_{j}=\infty , and a large constant J>0 such that for all j\geq J , \displaystyle\mathcal{R}_{T_{j}}\cdot\mathcal{S}_{T_{j}}>CT_{j}^{\frac{3}{2}}. (10) If \liminf_{j\rightarrow\infty}\mathcal{R}_{T_{j}}>c_{2}T_{j}^{\frac{3\rho}{2+2\rho}} for some constant c_{2}>0 , then we are done. Otherwise, for any \epsilon>0 , there must exist j_{1},j_{2},... increasing to \infty , and a constant L>0 such that \mathcal{R}_{T_{j_{l}}}<\epsilon T_{j_{l}}^{\frac{3\rho}{2+2\rho}} for all l\geq L . By ( 10 ), this implies that \mathcal{S}_{T_{j_{l}}}>\frac{C}{\epsilon}T_{j_{l}}^{\frac{3}{2+2\rho}} for all l\geq L . Equivalently, \sup_{\nu\in\mathfrak{P}_{\mathrm{sg}}}\left(R_{T}(\nu)+(S_{T}(\nu))^{\rho}\right)\geq\frac{C}{\epsilon}T_{j_{l}}^{\frac{3\rho}{2+2\rho}} . ∎ Proof 12.2 Proof of Corollary 5.3 Consider any minimax optimal algorithm that satisfies \mathcal{R}_{T}\leq c_{0}\sqrt{T} for some c_{0}>0 over instance class \mathfrak{P}_{\mathrm{sg}} . Consider the instance where both arms are \mathcal{N}(0,1) . By Theorem 3.5 , for T sufficiently large, \sqrt{\operatorname{Var}(N_{1,T})}>c_{2}T for some c_{2}>0 . Suppose the algorithm satisfies sampling stability. There must exist deterministic scalars n_{T}\to\infty such that \frac{N_{1,T}}{n_{T}}\xrightarrow{p}1. First, we claim n_{T}\leq 2T for all large T . By convergence in probability, for all large T we have P(N_{i,T}\geq n_{T}/2)\geq 1/2 . But N_{i,T}\leq T , hence n_{T}/2\leq T . Now fix any \delta\in(0,1) . By convergence in probability, for all large T , P\big(|N_{i,T}-n_{T}|\geq\delta n_{T}\big)\leq\delta. Using the bound 0\leq N_{i,T}\leq T and n_{T}\leq 2T , we obtain \displaystyle\mathbb{E}\big[(N_{i,T}-n_{T})^{2}\big] \displaystyle\leq(\delta n_{T})^{2}\;+\;(T+n_{T})^{2}\,P\big(|N_{i,T}-n_{T}|\geq\delta n_{T}\big)\leq(4\delta^{2}+9\delta)\,T^{2}. Finally, Jensen’s inequality gives (\mathbb{E}[N_{i,T}]-n_{T})^{2}\leq\mathbb{E}[(N_{i,T}-n_{T})^{2}] , so \operatorname{Var}(N_{i,T})\leq\mathbb{E}[(N_{i,T}-n_{T})^{2}]+(\mathbb{E}[N_{i,T}]-n_{T})^{2}\leq 2\,\mathbb{E}[(N_{i,T}-n_{T})^{2}]\leq 2(4\delta^{2}+9\delta)T^{2}. Because \delta>0 is arbitrary, this implies \operatorname{Var}(N_{i,T})=o(T^{2}) , a contradiction. ∎