arXiv CS open access

Toward the Optimal Regret-Instability Trade-off in Multi-Armed Bandits

2026 · arxiv_cs

arXiv CS · Papers · 2026

deep-learning machine-learning neural-networks

Conceptio Open Archive

Analyze & explore related research in Conceptio

Connect this record directly into your research workflow or AI agent. Explore citations across open repositories, query full text, and export structured proof bundles.

Explore in Search →Connect via MCP / API ↗

Toward the Optimal Regret–Instability Trade-off in Multi-Armed Bandits

arXiv:2608.17841v1 [stat.ML] 18 Aug 2026

Kaifei Wang∗

Yinyu Ye†‡

Han Zhong‡

Abstract Multi-armed bandit algorithms are evaluated by regret, yet comparable regret can coexist with different allocations across independent runs. We study the trade-off between worst-case regret RK,T and instability SK,T , defined as the largest standard deviation of a terminal pull count, for K arms and T rounds. We prove the finite-time lower bound RK,T SK,T ≥ CT 3/2 , where C is independent of K and T , under a finite-time regret condition and without the regularity assumptions imposed in the prior asymptotic analysis. We also introduce Stabilized Lower-Envelope UCB (SLE-UCB), a new tunable algorithm combining a running lower-envelope index with a decreasing pull-count stabilizer. SLE-UCB satisfies RK,T SK,T = O(T 3/2 log K), with an implicit constant independent of K and T , matching the lower bound exactly in T and within a logarithmic factor in K. To prove the instability bound, we develop a new offline top-prefix representation that removes path dependence from online decisions. Together with single-reward perturbations and the Efron–Stein inequality, this representation controls pull-count variance. Thus, regret and instability depend reciprocally on K, while their product has no polynomial dependence on K. These results resolve the open question raised in the literature concerning the sharp arm-dependent regret–instability frontier.

Introduction

Learning and decision-making often occur simultaneously. In clinical trials, online recommendation, and sequential resource allocation, each opportunity must be assigned while the rewards of the available alternatives remain unknown. The multi-armed bandit model captures these problems in its simplest form: every action produces an immediate reward while also generating information for future decisions (Li et al., 2010; Gittins et al., 2011; Villar et al., 2015). The central challenge is to balance information acquisition with immediate reward. Regret has become the standard measure of this balance, comparing the reward collected by an algorithm with that attainable if the best arm were known in advance (Lattimore and Szepesvári, 2020). Regret, however, is an average criterion. It reflects pull counts through their expectations but does not control how realized rewards and pull counts vary from one run to another. Two algorithms can therefore have similar regret while producing very different allocations across independent runs. This distinction matters because pull counts determine how many patients receive each treatment, how much traffic is assigned to each option, and how much data are available for subsequent inference. A related concern arises at the level of realized performance. For example, in discussing MOSS (Audibert and Bubeck, 2009), Lattimore and Szepesvári (2020, Section 9.2) use a carefully tuned two-arm policy to illustrate how favorable average performance can coexist with markedly different outcomes across independent runs. Subsequent work formalizes this issue through regret tails and risk-sensitive policy design (Simchi-Levi et al., 2022, 2023; Fan and Glynn, 2025; Zhu and Simchi-Levi, 2025). These studies focus on reward outcomes rather than arm allocations, but they reinforce the same message: regret alone does not control an algorithm’s behavior across independent runs. The allocation side of this issue is studied through sampling stability, rooted in Lai and Wei (1982). Broadly, stability requires the number of pulls of each arm to concentrate around a deterministic scale, thereby supporting conventional statistical inference after adaptive data collection. This property has been ∗ Peking University. Email: wkf5094@stu.pku.edu.cn.

† Stanford University. Email: yinyu-ye@stanford.edu.

‡ Shanghai Jiao Tong University. Email: han.zhong@sjtu.edu.cn.

examined for UCB (Kalvit and Zeevi, 2021; Khamaru and Zhang, 2024; Han et al., 2024; Chen and Lu, 2025; Fan et al., 2025) and Thompson sampling and its variants (Kalvit and Zeevi, 2021; Fan and Glynn, 2022; Halder et al., 2025; Han, 2026; Yan and Zhong, 2026). Related experimental-design work studies the trade-off between online performance and statistical power (Simchi-Levi and Wang, 2023). These studies make clear that predictable allocation is not an automatic consequence of low regret; it is a separate property of the algorithm. This longstanding literature raises a more structural question: can an algorithm be both regret-optimal and stable? Praharaj and Khamaru (2025) show that a broad class of minimax-optimal optimism-based algorithms fails to satisfy sampling stability. Subsequent work studies this question under complementary notions of stability. Halder et al. (2026) study stabilization through regularization under a related stability notion. Taken together, these studies reveal a general tension between regret and allocation stability. Chen and Lu (2026) provide a quantitative formulation of this question by studying the Pareto trade-off between worst-case regret and pull-count instability. Specifically, for a K-armed bandit run for T rounds, let RK,T denote its worst-case regret and let SK,T denote its worst-case instability, measured by the largest standard deviation of an arm’s terminal pull count. Formal definitions are provided in Section 2. Their lower bound applies to algorithms that treat identical arms symmetrically, pull every arm at least once in expectation, and achieve asymptotically sublinear worst-case regret. For every fixed K, their result implies that there exists a constant C0 > 0, independent of T , such that1 lim inf T →∞

RK,T SK,T > C0 . T 3/2

(1.1)

On the achievability side, they introduce UCB-f, a tunable generalization of UCB1 (Auer et al., 2002) controlled by an exploration function f (·), and establish √ T log T RK,T = OK T f (T ) , SK,T = OK . f (T ) Here OK (·) hides the dependence on K. Multiplying these bounds gives a regret–instability product of OK (T 3/2 log T ). With the dependence on K left implicit, the upper bound matches the T 3/2 polynomial dependence of the lower bound above but leaves a factor log T gap. To further understand the optimal regret–instability trade-off in K-armed bandits, three questions remain open: (i) whether the logarithmic gap in T can be closed, (ii) what the explicit and sharp dependence on K is, and (iii) whether a tunable algorithm can achieve this trade-off. Contributions. Our contributions are fourfold. • A finite-time lower bound. Building on the asymptotic lower bound of Chen and Lu (2026), we establish a finite-time counterpart under a mild condition that permits linear-in-T regret. Specifically, we prove RK,T SK,T ≥ CT 3/2 , where C > 0 is independent of T and K. Our proof adapts their argument without separately assuming symmetry, nondegenerate exploration, or asymptotic active learning. See Remark 7.3 for details. • A new stabilized UCB design. We introduce Stabilized Lower-Envelope UCB (SLE-UCB), which combines two distinctive design ingredients: a running lower-envelope UCB index and a decreasing pullcount stabilizer. The lower envelope makes the reward-dependent component of the index monotone, while the stabilizer creates a deterministic gap between different pull counts. The stabilizer strength is tunable, allowing the algorithm to trade regret for lower allocation variability. √ • A sharp √ K-dependent frontier. For SLE-UCB, we establish regret and instability bounds with K and 1/ K dependence, respectively, up to logarithmic factors. Multiplying these bounds gives RK,T (α)SK,T (α) = O T 3/2 log K . 1 Although the lower-bound construction of Chen and Lu (2026) uses only two arms, its asymptotic conclusion extends to every fixed K through the padding reduction in Remark 7.1.

SK,T √ T/ K

α=1 SLE-UCB upper bounds RK,T (α)SK,T (α) = O T 3/2 log K

increasing α excluded by the lower bound

√

Lower bound: RK,T SK,T = Ω(T 3/2 )

√

RK,T T

Figure 1: Schematic K-dependent regret–instability product comparison, with logarithmic factors and constants suppressed in the axis annotations. The solid blue and dashed orange curves denote the lower bound and the SLE-UCB upper bound, respectively. In the regret regime covered by Theorem 3.1, the gray region is excluded and the product bounds differ by at most a factor log K. Together with the lower bound, this provides a near-optimal characterization of the regret–instability Pareto frontier for K-armed bandits, as illustrated in Figure 1. By varying α, SLE-UCB traces this frontier, matching the lower bound exactly in T and up to a factor log K in K. This broader characterization both removes the log T gap left open by Chen and Lu (2026) and settles their open question about the K-dependence to logarithmic accuracy. • A new instability analysis. We develop an offline top-prefix representation of the online decisions made by SLE-UCB. This representation removes the path dependence created by sequential arm selection and converts a single-reward perturbation into a controlled change in terminal pull counts. Combining this perturbation argument with the Efron–Stein inequality (Efron and Stein, 1981; Boucheron et al., 2013) yields the finite-time instability bound. To the best of our knowledge, this combination has not previously been used to control terminal pull-count variance in bandit analysis. The approach may also be of independent interest for studying random sample sizes generated by other adaptive allocation rules. Organization. Section 2 introduces the bandit model and performance criteria. Section 3 presents the lower bound, the SLE-UCB algorithm, and the resulting frontier comparison. Section 4 establishes the clippingbias and concentration results. Sections 5 and 6 provide the regret and instability analyses, respectively. Section 7 proves the K-armed lower bound, and Section 8 concludes.

Model and performance metrics

Multi-armed bandits. Consider a stochastic multi-armed bandit with K ≥ 2 arms. For each arm i ∈ [K], let {Xi,n }n≥1 be an i.i.d. reward sequence with mean µi , where Xi,n is the reward revealed on the n-th pull of arm i. These reward sequences are mutually independent across arms. Let µ⋆ := maxi∈[K] µi denote the optimal mean reward, and let ν = (ν1 , . . . , νK ) denote the bandit instance, where νi is the distribution of Xi,1 . We make the following assumption on the reward distributions. Assumption 2.1 (Uniformly bounded means and sub-Gaussian rewards). There is a constant M > 0 such that µi ∈ [−M, M ] for every arm i ∈ [K] and there is a constant σ > 0 such that the reward distribution of each arm is σ-sub-Gaussian, in the sense that for all u ∈ R and i ∈ [K], 2 2 σ u . E[exp (u(Xi,1 − µi ))] ≤ exp 2 Online learning and objective. The reward distributions are unknown, and the algorithm learns online from bandit feedback. Fix a number of rounds T > K. In each round t ∈ [T ], the algorithm selects an arm

At ∈ [K] based on the past and its internal randomization, and observes only the selected arm’s reward. For every i ∈ [K] and t ∈ [T ], define Ni (t) :=

t X

1{As = i},

Ni (0) := 0.

s=1

Thus, the reward observed at time t is XAt ,NAt (t) . We evaluate an algorithm along two dimensions: regret and instability. Regret captures learning performance, whereas instability, following Chen and Lu (2026), captures the variability of pull counts. Definition 2.2 (Regret and instability). For a given instance ν and a given algorithm, regret and instability with K arms over T rounds are defined as RK,T (ν) =

T X

E [µ⋆ − µAt ] ,

SK,T (ν) = max

i∈[K]

t=1

Var[Ni (T )].

The regret RK,T (ν) measures the expected cumulative reward loss compared to the optimal arm. The instability SK,T (ν) is the largest standard deviation of an arm’s pull count across independent runs. Smaller instability therefore means that the algorithm produces more reproducible allocations across independent runs. We evaluate a bandit algorithm by its worst-case performance over the full class E of K-armed instances satisfying Assumption 2.1. Definition 2.3 (Worst-case regret and instability). For a given algorithm, the worst-case regret and instability with K arms over T rounds are defined as RK,T (E) = sup RK,T (ν),

SK,T (E) = sup SK,T (ν).

ν∈E

We henceforth omit the instance-class E and simply write RK,T and SK,T for these worst-case quantities.

Fundamental limit and Stabilized Lower-Envelope UCB

In this section, we characterize the regret–instability trade-off for K-armed bandits, including its dependence on both the number of rounds T and the number of arms K. We first establish a lower bound and then present an achievability result that matches it exactly in T and up to a logarithmic factor in K.

3.1

K-armed lower bound

While Chen and Lu (2026) establish the T 3/2 regret–instability lower bound only asymptotically, under symmetry, nondegenerate exploration, and an asymptotic active-learning condition, the following theorem holds for every K ≥ 2 and T > K. It requires the regret condition RK,T ≤ M T /8, without separately imposing any of those three conditions. Theorem 3.1 (K-armed regret–instability lower bound). Fix K ≥ 2 and T > K. Let RK,T and SK,T denote the worst-case regret and instability as in Definition 2.3. For the class of K-armed instances satisfying Assumption 2.1, every algorithm whose worst-case regret satisfies RK,T ≤ M T /8 obeys RK,T SK,T ≥ CT 3/2 . Here C = C(M, σ) > 0 depends only on the instance-class parameters (M, σ) and is independent of (T, K). Proof. See Section 7 for a detailed proof. Our proof largely follows the two-armed proof of Chen and Lu (2026) but uses a refined analysis to establish the result under weaker conditions; see Section 7 for√details. Theorem 3.1 makes the trade-off √ explicit.√At regret scale O(α KT ), instability must be Ω(T /(α K)). In particular, at the minimax regret √ rate O( KT ), attained for example by MOSS (Audibert and Bubeck, 2009), instability must be Ω(T / K). Thus, a minimax-regret policy cannot keep terminal pull counts tightly concentrated across all instances, consistent with the instability established for a broad class of minimax-optimal optimism-based algorithms by Praharaj and Khamaru (2025). We next turn to the achievability side and propose an algorithm matching this scaling up to logarithmic factors. 4

Algorithm 1 Stabilized Lower-Envelope UCB (SLE-UCB) 1: Input: number M, σ, and tuning parameter α ≥ 1. p p of rounds T , number of arms K, positive constants log(KT ), B = M + 4σι, β = 8Bι, and λ = αβ K/T . 2: Compute ι = 3: Sample a uniform random priority permutation ω ∈ SK . 4: Initialization: Pull each arm once, observe the rewards and clip them. After initialization, each arm has one pull, so Ni (K) = 1 for all i. 5: for t = K + 1, . . . , T do 6: Compute Ui (Ni (t − 1)) from (3.2) and Ii (Ni (t − 1)) from (3.3) for each arm i. 7: Choose At ∈ arg maxi∈[K] Ii (Ni (t − 1)), breaking ties by the smallest priority rank ω(i). 8: Pull At , observe the raw reward from that arm, clip it, and update the corresponding count. 9: end for

3.2

Stabilized Lower-Envelope UCB

We propose Stabilized Lower-Envelope UCB (SLE-UCB), a tunable algorithm for balancing regret and instability. It is a UCB-type algorithm with two design components: (i) replacing the standard empirical-meanplus-bonus statistic with its running lower envelope; and (ii) adding a logarithmic stabilizer that decreases with the pull count. These two components together create a stabilized index for each arm. At each time, the algorithm selects the arm with the largest stabilized index. Raw rewards are clipped before computing the index. For each arm i ∈ [K] and s ∈ [T ], define p Yi,s := min{B, max{−B, Xi,s }}, B = M + 4σι, ι = log(KT ). (3.1) When arm i is pulled for the s-th time, the algorithm uses Yi,s in place of the raw reward Xi,s . The threshold B depends only on M , σ, K, and T , and Lemma 4.1 shows that the resulting bias is negligible. Let Y = (Yi,s )i∈[K], s∈[T ] denote the full array of independent clipped rewards, revealed sequentially as the Pn arms are pulled. For n ≥ 1, define the average clipped reward by Y i (n) = ( s=1 Yi,s )/n. The lower-envelope UCB statistic is defined as β Ui (n) = min Y i (s) + √ , where β = 8Bι. (3.2) 1≤s≤n s The lower envelope is the minimum of the standard UCB statistic over all previous prefixes. Thus Ui (n) is nonincreasing in n. For a tuning parameter α ≥ 1, define the stabilized index by r K T , where λ = αβ . (3.3) Ii (n) = Ui (n) + λ log n T Since Ui (n) is nonincreasing in n and λ log(T /n) is strictly decreasing in n, the stabilized index Ii (n) is a strictly decreasing sequence in n for each arm i. During the initial period t ≤ K, SLE-UCB pulls each arm once. For t > K, it chooses an arm with the largest stabilized index and resolves ties using the sampled priority order: At ∈ arg max Ii (Ni (t − 1)). (3.4) i∈[K]

We impose a priority order on the arms to handle numerical ties in the index values. To avoid arm-label bias, this order is chosen at random: before starting, SLE-UCB samples an independent uniform permutation ω ∈ SK and breaks ties in favor of the arm with the smallest rank ω(i). In Section 6.1, we show that the monotonicity of Ii (n) permits an offline view of the online selection rule, which is crucial for the analysis of instability. This equivalence is formalized in Lemma 6.1. Moreover, the logarithmic stabilizer λ log(T /n) gives a deterministic lower bound on the index gap between two pull counts of the same arm. Specifically, for all 1 ≤ n1 ≤ n2 ≤ T , n2 n2 ≥ λ log ≥ 0. (3.5) Ii (n1 ) − Ii (n2 ) = Ui (n1 ) − Ui (n2 ) + λ log n1 n1 In the instability proof, this gap converts a bound on a single-reward index perturbation into a bound on the resulting change in the terminal pull count; see Section 6.3. Although the logarithmic stabilizer may influence arm selection, Section 5 shows that it only contributes a controlled additional term to regret. 5

3.3

Achievability and the Pareto frontier

The next theorem quantifies this trade-off through finite-time regret and instability bounds. Theorem 3.2 (Regret–instability guarantees for SLE-UCB). Fix 2 ≤ K < T and α ≥ 1. Recall from p (3.1) and (3.2) that ι = log(KT ), B = M + 4σι, and β = 8Bι. For SLE-UCB tuned with parameter α, let RK,T (α) and SK,T (α) denote its worst-case regret and instability as in Definition 2.3. These quantities satisfy √ n o √ √ 18 2σT √ . RK,T (α) ≤ min 2M T, 5 + α log(2K) β KT , (3.6) SK,T (α) ≤ 2 T + αβ K Consequently, for fixed M and σ, uniformly over α ≥ 1, RK,T (α)SK,T (α) = O T 3/2 log K , where the implicit constant is independent of K, T , and α. Proof. See Sections 5 and 6 for detailed proofs of the regret and instability bounds, respectively. For the product bound, applying the two branches of the regret estimate in (3.6) to the corresponding terms of the instability estimate gives √ √ 18 2σT √ RK,T (α)SK,T (α) ≤ 2 T RK,T (α) + RK,T (α) αβ K √ 5 3/2 ≤ 4M T + 18 2σ + log(2K) T 3/2 α = O T 3/2 log K , where the last equality uses α ≥ 1 and K ≥ 2. Theorem 3.2 provides finite-time guarantees for the tunable SLE-UCB algorithm over the full range α ≥ 1, and its product bound is uniform in α. Whenever RK,T (α) ≤ M T /8, this product matches the lower bound exactly in its T 3/2 dependence and within a factor log K in its dependence on the number of arms. Since the regret admits the universal bound RK,T (α) ≤ 2M T , we focus on the tuning range ! p T /K 1≤α=O , log K log(KT ) over which the tunable regret bound is at most O(T ). Because β = Θ(log(KT )) for fixed M and σ, the two guarantees take the simpler form √ T √ RK,T (α) = O α log K log(KT ) KT , SK,T (α) = O . α K log(KT ) As α increases within this range, the regret bound rises while the instability bound falls, tracing the regret– instability frontier. Compared with the OK (T 3/2 log T ) product obtained from the reported UCB-f bounds of Chen and Lu (2026), our O(T 3/2 log K) guarantee replaces the explicit log T factor with a log K factor, thereby answering their open K-dependence question up to a logarithmic factor while retaining the optimal dependence on T . For comparison, the UCB-f analysis (Chen and Lu, 2026) controls random pull counts around a deterministic fluid approximation through armwise UCB-index comparisons and concentration. The sharper K-dependence in Theorem 3.2 instead relies on the monotone lower-envelope indices and deterministic stabilizer gap of SLE-UCB, together with the offline top-prefix representation and single-reward perturbation analysis developed in Sections 6.1 and 6.3. The Efron–Stein inequality (see Efron and Stein (1981); Boucheron et al. (2013) or Lemma 6.2) then converts these perturbation bounds into variance control. See Sections 5 and 6 for details. 6

Clipping bias and concentration

In this section, we characterize the properties of the clipped reward. Lemma 4.1 (Clipping bias). Let θi = E[Yi,1 ] be the expectation of the clipped reward for arm i. For every arm i, the clipping bias of mean estimation is upper bounded by |θi − µi | ≤ σ(KT )−6 . Proof. Let Xi,1 be a reward from arm i and Yi,1 be the corresponding clipped reward. By Jensen’s inequality, we can bound the clipping bias as follows: |θi − µi | = |E[Yi,1 ] − E[Xi,1 ]| ≤ E[|Yi,1 − Xi,1 |]. As Yi,1 and Xi,1 can differ only when |Xi,1 | > B, we have |Yi,1 − Xi,1 | = |Yi,1 − Xi,1 | · 1{|Xi,1 | > B}. By Assumption 2.1, |µi | ≤ M < B. Thus, when the reward exceeds B in absolute value, the difference between the clipped reward and the raw reward can be bounded by |Yi,1 − Xi,1 | · 1{|Xi,1 | > B} ≤ |Xi,1 − µi | · 1{|Xi,1 | > B} ≤ |Xi,1 − µi | · 1{|Xi,1 − µi | > 4σι}. The second inequality holds because |Xi,1 | > B = M + 4σι and |µi | ≤ M imply |Xi,1 − µi | > 4σι. We rewrite the truncated tail expectation using the tail-integral representation: |θi − µi | ≤ E[|Xi,1 − µi |1{|Xi,1 − µi | > 4σι}] Z ∞ = 4σι P(|Xi,1 − µi | > 4σι) + P(|Xi,1 − µi | > t) dt.

(4.1)

4σι

Substituting the sub-Gaussian tail bound into (4.1) and evaluating the Gaussian tail integral, we have Z ∞ 2 t2 |θi − µi | ≤ 8σιe−8ι + 2 exp − 2 dt 2σ 4σι Z ∞ t2 1 −8ι2 t exp − 2 dt ≤ 8σιe + 2σι 4σι 2σ 2 2 1 = 8ι + σe−8ι ≤ σe−6ι = σ(KT )−6 . 2ι p √ 2 The last inequality holds since 8ι + 1/(2ι) ≤ e2ι when ι = log(KT ) ≥ log 4. According to Lemma 4.1, the gap between the expectation of the clipped reward and the true mean is negligible, so that the UCB statistic computed from the clipped rewards still reflects the performance of the arms. In the following lemma, we show the concentration of the clipped reward. Lemma 4.2 (Clipped reward concentration). Define the concentration event G by β G = Y i (n) − θi ≤ √ for all i ∈ [K], 1 ≤ n ≤ T . 2 n The event G satisfies P(G c ) ≤ 2(KT )−7 . Proof. Since the clipped rewards lie in [−B, B], Hoeffding’s inequality gives, for each fixed i and n, β β2 P Y i (n) − θi > √ ≤ 2 exp − 2 . 8B 2 n p Applying a union bound over at most KT items (i, n) and using β = 8Bι = 8B log(KT ) gives β P(G c ) ≤ KT · P Y i (n) − θi > √ ≤ 2KT · (KT )−8 = 2(KT )−7 . 2 n This finishes the proof of Lemma 4.2. 7

(4.2)

Regret Analysis

Proof. Fix an admissible instance ν. We prove the regret bound in (3.6) and the worst-case statement then follows by taking the supremum over ν. Decompose the regret according to the concentration event G from Lemma 4.2: X K K X RK,T (ν) = E 1G (5.1) (µ⋆ − µi )Ni (T ) + E 1G c (µ⋆ − µi )Ni (T ) . i=1

i=1

}

Term (I)

Term (II)

}

Term (I) in (5.1). Let θ⋆ = maxi∈[K] θi be the largest clipped mean. By Lemma 4.1, each true mean gap PK is bounded above by the corresponding clipped mean gap plus twice the clipping-bias bound. Since i=1 Ni (T ) = T , we have X X K K ⋆ ⋆ E 1G (µ − µi )Ni (T ) ≤ E 1G (θ − θi )Ni (T ) + 2σT (KT )−6 . i=1

(5.2)

i=1

It remains to bound the first term in (5.2). We divide it into the contribution from the initial pulls and the contribution from the noninitial pulls. For the initialization phase (t ≤ K), θi ∈ [−B, B] for every arm i since the rewards are clipped, so the total is at most 2BK. Since K ≤ T and β = 8Bι > 2B, we can bound the contribution of the initialization phase as follows: K X √ (θ⋆ − θi ) ≤ 2BK ≤ β KT .

(5.3)

i=1

Now consider a noninitial time t, at which SLE-UCB pulls arm i. Let j be the arm satisfying θj = θ⋆ . According to the selection rule of SLE-UCB (3.4), we have Ii (Ni (t − 1)) ≥ Ij (Nj (t − 1)).

(5.4)

On G, we first upper bound the index of the selected arm i. Since Ui (n) is the minimum over all prefixes up to n, evaluating it at the full prefix gives T Ii (Ni (t − 1)) = Ui (Ni (t − 1)) + λ log Ni (t − 1) β T ≤ Y i (Ni (t − 1)) + p + λ log Ni (t − 1) Ni (t − 1) 3β T ≤ θi + p + λ log . (5.5) Ni (t − 1) 2 Ni (t − 1) The first inequality follows from the definition of the lower-envelope UCB statistic (3.2), and the second inequality follows from the definition of event G. Next, for the arm j satisfying θj = θ⋆ , let β √ sj ∈ arg min Y j (s) + . s 1≤s≤Nj (t−1) Then the index of arm j satisfies β T Ij (Nj (t − 1)) = Y j (sj ) + √ + λ log sj Nj (t − 1) β T ≥ θj + √ + λ log ≥ θ⋆ . 2 sj Nj (t − 1) The first inequality follows from the event G, and the last inequality uses θj = θ⋆ and Nj (t − 1) ≤ T .

(5.6)

Combining (5.4), (5.5) and (5.6), for every noninitial round t > K with At = i, 3β T ⋆ θ − θi ≤ p + λ log . Ni (t − 1) 2 Ni (t − 1)

(5.7)

Summing (5.7) over all noninitial pulls, we upper bound the noninitial contribution to Term (I) by K K X 3β X p Ni (T ) − 1 + λ (θ⋆ − θi )(Ni (T ) − 1) ≤ 2 i=1 i=1

(Ni (T ) − 1) log

i:Ni (T )>1

3β √ ≤ KT + λ(T − K) log 2

T Ni (T ) − 1

KT . T −K

(5.8) (5.9)

In (5.8), we take t in (5.7) to be the last time arm i is pulled, so that the previous pull count equals Ni (T ) − 1. PK The second inequality (5.9) uses i=1 Ni (T ) = T . The first term follows from the Cauchy–Schwarz inequality and the second term follows from the concavity of x 7→ x log(T /x). Combining the initial phase contribution (5.3) and the noninitial phase contribution (5.9), substituting p λ = αβ K/T , we have T X √ √ KT 3β √ T −K ⋆ log (θ − θAt ) ≤ β KT + KT + αβ KT · 2 T T −K t=1 √ α(T − K) T ≤ 3 + α log K + log β KT T T −K √ ≤ 3 + α log(2K) β KT .

(5.10)

The last line holds because (T − K)/T < 1 and x log(1/x) < 1/e < log 2 when x < 1. Substituting (5.10) into (5.2), Term (I) is bounded by X K √ ⋆ E 1G (µ − µi )Ni (T ) ≤ 3 + α log(2K) β KT + 2σT (KT )−6 .

(5.11)

i=1

Term (II) in (5.1). On G c , each mean gap is at most 2M , since the true means are bounded in [−M, M ]. Thus, the regret is at most 2M T . According to Lemma 4.2, the probability of G c is at most 2(KT )−7 , so Term (II) can be bounded by K X E 1G c (µ⋆ − µi )Ni (T ) ≤ 2M T · 2(KT )−7 = 4M T (KT )−7 .

(5.12)

i=1

Combining the bounds. Combining (5.11) and (5.12), we obtain √ RK,T (ν) ≤ 3 + α log(2K) β KT + 2σT (KT )−6 + 4M T (KT )−7 √ ≤ 5 + α log(2K) β KT . The last inequality uses basic algebraic manipulations. By the definitions β = 8Bι and B = √ M + 4σι, together with ι ≥√1, we have σ ≤ β and M ≤ β. Thus, for K, T ≥ 2, we have 2σT (KT )−6 ≤ β KT and 4M T (KT )−7 ≤ β KT . Taking the supremum over all admissible instances proves (3.6).

Instability Analysis

This section proves the instability bound in (3.6). Fix an admissible instance ν and an arm i ∈ [K]. Recall from Section 3.2 that Y = (Ya,m )a∈[K], m∈[T ] denotes the full array of independent clipped potential rewards. We use G(Y ) to denote the event that Y satisfies the concentration condition in (4.2). Since Ni (T ) is

(a) Offline top-prefix rule

(b) Online greedy rule

compute all Vi,n = Ii (n − 1) and rank them globally

choose an arm with the largest current value

Initialization

(1, 1)

(2, 1)

Post-initial items n=2 n=3 (1, 2)

arm 2

(2, 2)

Initialization

(1, 1)

(2, 1)

(3, 1)

Next available item from each arm t=4 t=5 t=6 t=7

n=4

n=5

(1, 4)

(1, 5)

arm 1

(1, 2)

(1, 3)

(1, 4)

(2, 3)

(2, 4)

(2, 5)

arm 2

(2, 2)

(2, 3)

(3, 3)

(3, 4)

(3, 5)

arm 3

(3, 2)

(3, 3)

arm 1

(3, 1)

t=8

(1, 3) 1

arm 3

(3, 2)

select: (2, 2), (1, 2), (3, 2), (1, 3), (2, 3)

choose arm: 2 → 1 → 3 → 1 → 2

Figure 2: Offline and online selection (K = 3, T = 8). An item (i, n) represents the n-th pull of arm i, has value Vi,n = Ii (n − 1), and is post-initial when n ≥ 2. Consider a permutation (ω(1), ω(2), ω(3)) = (2, 3, 1). Assume I2 (1) > I1 (1) > I3 (1) = I1 (2) > I2 (2) and all other indices are smaller. For offline selection, after sorting Vi,n = Ii (n−1) by decreasing value and resolving the tie using ω, the first five items in the offline postinitial order are (2, 2), (1, 2), (3, 2), (1, 3), (2, 3). For online selection, the first five choices after initialization are 2 → 1 → 3 → 1 → 2, which corresponds to the same items (2, 2), (1, 2), (3, 2), (1, 3), (2, 3) as in the offline selection. determined by the clipped reward array Y and the random tie-breaking permutation ω, we write the final count as Ni (Y, ω, T ). Applying the law of total variance gives Var(Ni (Y, ω, T )) = Varω (EY [Ni (Y, ω, T ) | ω]) + Eω [VarY (Ni (Y, ω, T ) | ω)] . {z } | {z } | Term (⋆)

(6.1)

Term (⋆⋆)

Here and throughout this section, all randomness is induced only by the clipped reward array Y and the random tie-breaking permutation ω. The subscripts on expectations and variances specify which of these two sources of randomness is being averaged over: Eω and Varω are taken only with respect to ω, while EY and VarY are taken only with respect to Y ; the other source of randomness is held fixed or conditioned on as displayed. We will bound Term (⋆) in Section 6.2 and Term (⋆⋆) in Section 6.3, respectively. The key device is an offline top-prefix representation of the SLE-UCB selection rule. Conditional on the permutation ω, the final count Ni (Y, ω, T ) is a deterministic function of the reward array Y , so the Efron–Stein inequality reduces its conditional variance to single-coordinate perturbations of Y . A direct online analysis is difficult because a single perturbation may alter all subsequent decisions. The offline representation removes this path dependence, thereby enabling the required perturbation analysis. We begin by establishing the online–offline equivalence.

6.1

Online–offline equivalence

Conditional on a reward array Y and a permutation ω, all stabilized indices are deterministic. We introduce the item set IT = {(i, n) : i ∈ [K], 1 ≤ n ≤ T } and define two selection rules on it, where (i, n) represents the n-th pull of arm i. For each item (i, n), define its value as Vi,n = Ii (n − 1), where Ii (0) = ∞. Sort all items in IT by decreasing value Vi,n , resolving ties by the smaller priority rank ω(i). For a fixed number of rounds T ≥ K, compare the following two selection rules: • Offline top-prefix rule. Select top T items in the sorted list. These consist of the K initial items {(i, 1)}i∈[K] and the top T − K post-initial items. • Online greedy rule (SLE-UCB selection rule). Select {(i, 1)}i∈[K] during the first K rounds. At each later round t > K, choose an arm with the largest current value Ii (Ni (t − 1)) and select the corresponding next item.

Figure 2 illustrates the selection processes for both rules. With the following lemma, we show that the two rules select the same items. Lemma 6.1 (Online–offline equivalence). For every reward array Y and permutation ω, the item set selected by the online greedy rule up to time T ≥ K is identical to the item set selected by the offline top-prefix rule. Proof. Both rules select {(i, 1)}i∈[K] , so it remains to compare the remaining T − K post-initial selections. Let Sroff be the first r post-initial items in the offline sorted list, and let Sron be the first r post-initial items selected by the online greedy rule. We prove by induction that Sron = Sroff ,

0 ≤ r ≤ T − K.

The claim is immediate for r = 0. Suppose it holds for some r < T − K, and let (a, n) be the next item in the offline sorted list. By the induction hypothesis, the first r post-initial items selected by the two rules form the same set. Hence, for each arm i, the offline rule has selected all items (i, j) with j ≤ Ni (K + r), and its highest-ranked unselected item from that arm is (i, Ni (K + r) + 1) because Vi,j = Ii (j − 1) is strictly decreasing in j. Consequently, (a, n) is the item with the largest value among the items (i, Ni (K + r) + 1), i ∈ [K], with ties resolved by ω. At round K + r + 1, the online greedy rule compares exactly these same items and uses the same tie-breaking rule, so it also selects (a, n). This proves the induction step. Directly under the online rule, changing the tie-breaking permutation or replacing a single reward may alter the next selected arm and thereby propagate through the entire subsequent decision trajectory, making the sensitivity of the final pull counts difficult to track. With the online–offline equivalence established, we use the offline top-prefix representation in both parts of the variance analysis. In Section 6.2, it isolates the effect of random tie-breaking and shows that changing the priority permutation can alter the final count of any arm by at most one. In Section 6.3, it converts a single-coordinate reward perturbation into a movement of the offline selection boundary, thereby avoiding a recursive analysis of subsequent online decisions.

6.2

Bound of Term (⋆) in (6.1)

Proof. Fix a clipped reward array Y , the target arm i, and two permutations ω and ω ′ . By Lemma 6.1, under either permutation the algorithm selects the initial items {(j, 1)}j∈[K] and then selects the top T − K post-initial items according to the sorted item values, with ties resolved by the permutation. Let c be the value of the last selected post-initial item. Items with value strictly larger than c are selected under both permutations, and items with value strictly smaller than c are selected under neither permutation. Thus, the permutation can affect only items whose value is exactly c. For the target arm i, according to (3.5), the sequence {Ii (n)}Tn=1 is strictly decreasing. Hence arm i has at most one post-initial item with value c, and changing the permutation can change the final count of arm i by at most one: |Ni (Y, ω, T ) − Ni (Y, ω ′ , T )| ≤ 1. With ω and ω ′ fixed, taking expectations over Y gives |EY [Ni (Y, ω, T ) | ω] − EY [Ni (Y, ω ′ , T ) | ω ′ ]| ≤ EY [|Ni (Y, ω, T ) − Ni (Y, ω ′ , T )|] ≤ 1. Therefore the conditional expectations lie in an interval of length at most one as ω varies. Since the target arm i was arbitrary, for every i ∈ [K], Varω (EY [Ni (Y, ω, T ) | ω]) ≤ 1.

(6.2)

This provides an upper bound for Term (⋆).

6.3

Bound of Term (⋆⋆) in (6.1)

We fix the permutation ω and control the sensitivity of the final count of the target arm i to a singlecoordinate perturbation of the reward array. The proof has three steps: first, we bound the change in the stabilized indices caused by replacing one clipped reward; second, we translate this index perturbation into a pull-count perturbation; third, we sum the squared influences through the Efron–Stein inequality. Proof. Consider clipped reward arrays Y, Y ′ ∈ RK×T differing only in the m-th clipped reward of arm a, ′ ′ where Ya,m is an independent copy of Ya,m . Let Y i (n), Ui′ (n), and Ii′ (n) denote the corresponding averages, lower-envelope UCB statistics, and stabilized indices computed under Y ′ . For simplicity, since ω and T are fixed in this subsection, we write Nj (Y ) = Nj (Y, ω, T ) for every arm j ∈ [K]. 11

Stabilized-index perturbation. We first bound how a single-coordinate replacement changes the stabilized indices. For every arm j ̸= a, the reward array is unchanged, so Ij′ (n) = Ij (n) for all n ≤ T . For arm a, the index is unchanged for n < m, because the replaced reward has not entered the prefix average. For n ≥ m, we define the index attaining the minimum in Ua (n) under Y as β s(n) ∈ arg min Y a (q) + √ . q 1≤q≤n Using the definition of the lower-envelope UCB statistic, we have ′ ′ |Ya,m − Ya,m | |Ya,m − Ya,m | β β ′ ≤ Y a (s(n)) + = Ua (n) + Ua′ (n) ≤ Y a (s(n)) + p +p . s(n) s(n) s(n) s(n)

We next show that the minimizer s(n) cannot be much smaller than n on the concentration event G(Y ). Since s(n) is a minimizer and G(Y ) holds, we have 3β β β β ≤ Y a (s(n)) + p ≤ Y a (n) + √ ≤ θa + √ . θa + p n 2 n 2 s(n) s(n) The first and last inequalities use the event G(Y ), and the chain implies s(n) ≥ n/9. Pull-count perturbation bound on G(Y ) ∩ G(Y ′ ). Assume that G(Y ) and G(Y ′ ) both hold. Applying s(n) ≥ n/9 to Y , and then interchanging the roles of the two arrays, gives Ia′ (n) = Ia (n)

if n < m,

|Ia′ (n) − Ia (n)| ≤

′ 9|Ya,m − Ya,m | n

if n ≥ m.

(6.3)

We now convert the index perturbation in (6.3) into a perturbation bound for the final pull counts. If m > Na (Y ), then Ij′ (n) = Ij (n) for all j ∈ [K] and n ≤ Nj (Y ), hence the selected item set is unchanged. Thus, for every j ∈ [K], Nj (Y ) = Nj (Y ′ ). (6.4) Similarly, if m > Na (Y ′ ), then Ij (n) = Ij′ (n) for all j ∈ [K] and n ≤ Nj (Y ′ ), which implies Nj (Y ) = Nj (Y ′ ) for every j ∈ [K]. As for the case m ≤ min{Na (Y ), Na (Y ′ )}, without loss of generality, we assume that Na (Y ) < Na (Y ′ ). By Lemma 6.1, both runs are equivalent to top-prefix selections under the same permutation. Thus, (a, Na (Y )+1) is not selected under Y , while (a, Na (Y ′ )) is selected under Y ′ . Since the total number of selected items is fixed, there exists an unchanged arm j such that the item (j, ℓ) is selected under Y and not selected under Y ′ . Hence Ia (Na (Y )) ≤ Ij (ℓ − 1) = Ij′ (ℓ − 1) ≤ Ia′ (Na (Y ′ ) − 1). (6.5) Subtracting Ia (Na (Y ′ )−1) from both sides of (6.5), applying (6.3), and using the logarithmic gap of stabilized indices (3.5), we obtain Na (Y ′ ) − 1 λ log ≤ Ia (Na (Y )) − Ia (Na (Y ′ ) − 1) Na (Y ) ≤ Ia′ (Na (Y ′ ) − 1) − Ia (Na (Y ′ ) − 1) ≤

′ 9|Ya,m − Ya,m | . Na (Y ′ ) − 1

Using log(1 + x) ≥ x/(1 + x) for x ≥ 0, we have λ·

′ 9|Ya,m − Ya,m | Na (Y ′ ) − 1 − Na (Y ) ≤ . Na (Y ′ ) − 1 Na (Y ′ ) − 1

Exchanging the roles of Y and Y ′ gives the same bound when Na (Y ) > Na (Y ′ ). Therefore, when G(Y ) and ′ G(Y ′ ) both hold, we have |Na (Y ) − Na (Y ′ )| ≤ (1 + 9|Ya,m − Ya,m |/λ)1{m≤min{Na (Y ),Na (Y ′ )}} . 12

For an unchanged arm j ̸= a, remove arm a and sort all unchanged-arm items in their common order. Conditional on the number of selected items from arm a, the selected items from the unchanged arms form a prefix of this remaining list. Hence the count change of every unchanged arm is bounded by the count change of arm a. Consequently, when G(Y ) and G(Y ′ ) both hold, for every j ∈ [K], ′ 9|Ya,m − Ya,m | |Nj (Y ) − Nj (Y ′ )|≤ 1 + 1{m≤min{Na (Y ),Na (Y ′ )}} . (6.6) λ Expectation of the pull-count perturbation. Using (6.4), (6.6), and the trivial bound |Ni (Y ) − Ni (Y ′ )| ≤ T when either G(Y ) or G(Y ′ ) fails, we obtain EY,Y ′ (Ni (Y ) − Ni (Y ′ ))2 ≤ EY,Y ′ (Ni (Y ) − Ni (Y ′ ))2 1G(Y )∩G(Y ′ ) + EY,Y ′ (Ni (Y ) − Ni (Y ′ ))2 1G(Y )c ∪G(Y ′ )c !2 # " ′ 9|Ya,m − Ya,m | P(m ≤ Na (Y )) + 4T 2 (KT )−7 (6.7) ≤ EY,Y ′ 1 + λ √ 2 9 2σ ≤ 1+ P(m ≤ Na (Y )) + 4T 2 (KT )−7 . (6.8) λ ′ ): under Y , whether The first term in (6.7) uses the independence of 1{m≤min{Na (Y ),Na (Y ′ )}} and (Ya,m , Ya,m the m-th pull of arm a is selected is determined before Ya,m is observed, and similarly for Y ′ . The second term uses the union bound and Lemma 4.2 to bound the probability of G(Y )c ∪ G(Y ′ )c . The last inequality ′ uses Minkowski’s inequality and bounds EY,Y ′ [(Ya,m − Ya,m )2 ] by twice the variance of raw rewards.

Conditional variance bound. We now apply the Efron–Stein inequality in Efron and Stein (1981), in the replacement form stated in Boucheron et al. (2013, Theorem 3.1) to the reward array and bound the conditional variance using the preceding pull-count estimate. Lemma 6.2 (Efron–Stein inequality). Let X1 , . . . , Xn be independent random variables, and let Xℓ′ be an independent copy of Xℓ for all ℓ ∈ [n]. Let F = f (X1 , . . . , Xn ) be square-integrable. For ℓ ∈ [n], define F (ℓ) = f (X1 , . . . , Xℓ−1 , Xℓ′ , Xℓ+1 , . . . , Xn ). Then we have Var(F ) ≤

n i 1X h E (F − F (ℓ) )2 . 2 ℓ=1

For a coordinate (a, m) satisfying a ∈ [K] and m ∈ [T ], let Y (a,m) be the array obtained by replacing Ya,m ′ and leaving every other coordinate unchanged. Using Lemma 6.2 and (6.8), by an independent copy Ya,m with ω fixed, the conditional variance of the fixed target count can be bounded by K T 2 1XX EY,Y (a,m) Ni (Y, ω, T ) − Ni (Y (a,m) , ω, T ) 2 a=1 m=1 √ K T (1 + 9 2 σ/λ)2 X X ≤ PY (m ≤ Na (Y, ω, T )) + 2T 2 (KT )−6 2 a=1 m=1 √ K 2 X (1 + 9 2 σ/λ) = EY [Na (Y, ω, T )] + 2T 2 (KT )−6 2 a=1 √ √ (1 + 9 2 σ/λ)2 T = + 2T 2 (KT )−6 ≤ (1 + 9 2 σ/λ)2 T 2

VarY (Ni (Y, ω, T ) | ω) ≤

(6.9)

(6.10)

(6.11)

The first inequality (6.9) applies the Efron–Stein inequality over the replacement coordinates (a, m). The second inequality (6.10) uses the single-coordinate perturbation bound in (6.8). The last line (6.11) uses √ PK 2 −6 ≤ T /2 ≤ (1 + 9 2σ/λ)2 T /2, so the second a=1 EY [Na (Y, ω, T )] = T . Since K, T ≥ 2, we have 2T (KT ) term in (6.10) is absorbed into the leading term. 13

Taking expectation over ω, we can bound Term (⋆⋆) by √ Eω [VarY (Ni (Y, ω, T ) | ω)] ≤ (1 + 9 2 σ/λ)2 T .

(6.12)

This proves the desired bound for Term (⋆⋆).

6.4

Combining the bounds

Combining the variance decomposition (6.1), the bound for Term (⋆) in (6.2), and the bound for Term (⋆⋆) in (6.12), we obtain that for every arm i ∈ [K], √ √ Var(Ni (Y, ω, T )) ≤ 1 + (1 + 9 2 σ/λ)2 T ≤ 4 (1 + 9 2 σ/λ)2 T. p The last relaxation uses T ≥ 1. Substituting λ = αβ K/T , we have √ √ 18 2σT √ . SK,T (α) ≤ 2 T + αβ K Because this bound is uniform over admissible instances ν and arms i, taking the maximum over arms and then the supremum over instances proves the instability bound in (3.6).

Proof of the K-armed lower bound

Remark 7.1 (Fixed-K reduction). We establish the fixed-K extension in (1.1) through the following padding reduction. Pad the instance with K − 2 independent N (−M, σ 2 ) dummy arms. A two-armed algorithm B simulates a K-armed algorithm A exactly on the first two arms. On dummy-arm requests, it alternates between the real arms from a uniformly random starting arm, discards the reward, and supplies an independent A B A dummy reward. This gives RB 2,T ≤ RK,T and S2,T ≤ SK,T + 1/2 while preserving the required conditions. 3/2 B B A > C0 for some constant C0 > 0. Since RB 2,T ≤ RK,T = o(T ), their theorem gives lim inf T →∞ R2,T S2,T /T Together with the two inequalities above, this yields the fixed-K conclusion. Proof of Theorem 3.1. Our proof largely follows the approach of Chen and Lu (2026). Fix K ≥ 2, T > K. Let A be an algorithm whose worst-case regret satisfies RK,T ≤ M T /8. Consider the all-zero Gaussian 2 instance ν(0) = (N (0, σ 2 ))K i=1 , where the reward distributions of all arms are N (0, σ ). Choose an arm attaining the smallest expected pull count under this instance and denote it by arm j. We consider the following family of instances, in which arm j is the unique optimal arm whenever ∆ > 0: ( N (0, σ 2 ), i = j, (ν(∆))i = 2 N (−∆, σ ), i ̸= j. We aggregate all suboptimal pulls. Suppressing the dependence on A, let P∆ , E∆ , and Var∆ denote probability, expectation, and variance under the interaction with ν(∆), and define X N− (T ) := Ni (T ) = T − Nj (T ), G(∆) := E∆ [N− (T )]. (7.1) i̸=j

The equal-gap construction gives RK,T (ν(∆)) = ∆ · G(∆),

G(0) = T − E0 [Nj (T )] ≥

K −1 T, K

(7.2)

The inequality for G(0) follows because arm j has the smallest expected pull count at ∆ = 0. Define a candidate gap by 8RK,T ∆⋆ := . T The regret requirement RK,T ≤ M T /8 gives ∆⋆ ≤ M , and hence ν(∆⋆ ) is admissible. We connect the all-zero instance to ν(∆⋆ ) through a sequence of nearby instances. The increments are chosen so that the KL 14

divergence between the interaction histories at consecutive gaps is at most 1/2. Set ∆0 = 0 and, recursively, define ) ( σ . (7.3) ∆ℓ+1 := min ∆⋆ , ∆ℓ + p G(∆ℓ ) At the zero instance, G(0) > 0, and hence P0 (N− (T ) > 0) > 0. Only the rewards from arms i ̸= j differ between ν(0) and ν(∆). For every finite ∆, the chain rule for KL divergence and the Gaussian KL formula therefore give DKL (P0 ∥P∆ ) = G(0)∆2 /(2σ 2 ) < ∞, so P0 ≪ P∆ . Consequently, P∆ (N− (T ) > 0) > 0, and thus G(∆) > 0. Therefore, the sequence {∆ℓ }ℓ≥0 is well defined. √ Since G(∆) ≤ T , every untruncated increment in (7.3) is at least σ/ T . Thus the sequence reaches ∆⋆ after finitely many steps. Let L be the first index at which the sequence reaches ∆⋆ , namely, L := min{ℓ ≥ 1 : ∆ℓ = ∆⋆ }. Since only the final increment can be truncated, √ ∆⋆ T 8RK,T L≤1+ =1+ √ . (7.4) σ σ T All points in the sequence belong to [0, ∆⋆ ], so all corresponding instances are admissible. We next establish an order-T gap between the endpoint values of G along this sequence. By (7.2), ∆⋆ ·G(∆⋆ ) = RK,T (ν(∆⋆ )) ≤ RK,T . The definition of ∆⋆ therefore gives G(∆⋆ ) ≤ T /8. Along this sequence, the triangle inequality implies L−1 X

|G(∆ℓ+1 ) − G(∆ℓ )| ≥ |G(∆L ) − G(∆0 )| = |G(∆⋆ ) − G(∆0 )| ≥

ℓ=0

T 3T T − = . 2 8 8

(7.5)

Hence, for some ℓ ∈ {0, . . . , L − 1}, |G(∆ℓ+1 ) − G(∆ℓ )| ≥ 3T /(8L). The following lemma is a variance-rescaled variant of Lemma 6.1 in Chen and Lu (2026), applied to the aggregate count N− (T ). It compares two nearby Gaussian instances and converts the preceding gap into an instability lower bound. p Lemma 7.2. Let 0 ≤ ∆ < ∆′ ≤ M and ∆′ ≤ ∆ + σ/ G(∆), where G(∆) is defined in (7.1). Under any algorithm, e−1/4 max {SK,T (ν(∆)), SK,T (ν(∆′ ))} ≥ √ |G(∆′ ) − G(∆)| . 4 2 See Section 7.1 for a detailed proof. Applying Lemma 7.2 to the preceding gap and using (7.4), we obtain SK,T ≥ max {SK,T (ν(∆ℓ )), SK,T (ν(∆ℓ+1 ))} 3e−1/4 T 3e−1/4 T √ √ · √ . ≥ (7.6) 32 2L 256 2 1 + RK,T /(σ T ) √ The last inequality relaxes the bound on L in (7.4) to L ≤ 8(1 + RK,T /(σ T )). Multiplying (7.6) by RK,T gives 3e−1/4 σ R √ · √ K,T RK,T SK,T ≥ · T 3/2 . (7.7) 256 2 σ T + RK,T ≥

The standard Gaussian minimax construction in Exercise 15.2 of Lattimore and Szepesvári (2020), after scaling to variance σ 2 and restricting the means to [−M, M ], gives √ σ M √ 1 M RK,T ≥ min , KT = σcM,σ KT , cM,σ := min , . (7.8) 8 4 8 4σ See Section proof. Since K√≥ 2 and √ 7.2 for a detailed √ √ x 7→ x/(1 +√x) is increasing on [0, ∞), it follows that RK,T /(σ T + RK,T ) ≥ cM,σ K/(1 + cM,σ K) ≥ 2 cM,σ /(1 + 2 cM,σ ). Substituting it into (7.7) yields the K-independent bound 3e−1/4 σcM,σ √ T 3/2 . RK,T SK,T ≥ 256 1 + 2 cM,σ

Remark 7.3 (Comparison of lower-bound conditions). Choosing an arm with the smallest expected pull count at ∆ = 0 as the optimal arm in the instance construction yields the lower bound on G(0) needed for (7.5), which Chen and Lu (2026) obtain from symmetry. Absolute continuity of the Gaussian interaction laws implies G(∆) > 0 for every finite ∆, ensuring that the recursion in (7.3) is well defined without nondegenerate exploration. Finally, under RK,T ≤ M T /8, ∆⋆ ≤ M , while the regret identity gives G(∆⋆ ) ≤ T /8. This admissible endpoint for fixed T , together with the lower bound on G(0), yields the order-T decrease in G required by (7.5), replacing the asymptotic active-learning argument of Chen and Lu (2026).

7.1

Proof of Lemma 7.2

Proof of Lemma 7.2. The claim is immediate if G(∆) = G(∆′ ). Otherwise, define an event  G(∆) + G(∆′ )  N− (T ) < , G(∆) > G(∆′ ), 2 A := ′  N (T ) ≥ G(∆) + G(∆ ) , G(∆) < G(∆′ ). − 2 On A, N− (T ) is at least |G(∆′ ) − G(∆)|/2 away from G(∆), while on Ac it is at least the same distance from G(∆′ ). Since N− (T ) = T − Nj (T ), it follows that (SK,T (ν(∆)))2 ≥ Var∆ (Nj (T )) = Var∆ (N− (T )) ≥ P∆ (A)

|G(∆′ ) − G(∆)|2 . 4

Similarly, we have (SK,T (ν(∆′ )))2 ≥ P∆′ (Ac )·|G(∆′ )−G(∆)|2 /4. Only the reward distributions of arms i ̸= j differ between the two instances. The chain rule for KL divergence and the Gaussian KL formula therefore give DKL (P∆ ∥P∆′ ) =

X i̸=j

1 (∆′ − ∆)2 ≤ . E∆ [Ni (T )]DKL N (−∆, σ 2 )∥N (−∆′ , σ 2 ) = G(∆) 2 2σ 2

The Bretagnolle–Huber inequality therefore implies P∆ (A) + P∆′ (Ac ) ≥ exp − DKL (P∆ ∥P∆′ ) /2 ≥ e−1/2 /2. Consequently, p |G(∆′ ) − G(∆)| p P∆ (A) + P∆′ (Ac ) 4 |G(∆′ ) − G(∆)| p e−1/4 ≥ P∆ (A) + P∆′ (Ac ) ≥ √ |G(∆′ ) − G(∆)|. 4 4 2

max {SK,T (ν(∆)), SK,T (ν(∆′ ))} ≥

This concludes the proof of Lemma 7.2.

7.2

Proof of (7.8)

Proof of the Gaussian minimax bound (7.8). The proof applies the Gaussian minimax construction in Exercise 15.2 of Lattimore and Szepesvári (2020), with the variance scaled to σ 2 and the means restricted to [−M, M ]. Set r 1 M K cM,σ := min , , δ := 4cM,σ σ . 8 4σ T For each i ∈ [K], consider the Gaussian instance ν (i) in which arm i has mean δ and all other arms have mean zero, with variance σ 2 throughout; let ν (0) be the all-zero instance. These instances are admissible because δ ≤ M . Writing Pν (i) , Eν (i) , Rν (i) for the corresponding probability, expectation and regret under the interaction with instance ν (i) , Pinsker’s inequality and the divergence decomposition give r 1 Eν (i) [Ni (T )] ≤ Eν (0) [Ni (T )] + T · TV(Pν (i) , Pν (0) ) ≤ Eν (0) [Ni (T )] + T DKL (Pν (0) ∥Pν (i) ) 2 p = Eν (0) [Ni (T )] + 2cM,σ KT Eν (0) [Ni (T )], 16

where TV(Pν (i) , Pν (0) ) = supA |Pν (i) (A) − Pν (0) (A)|. Summing over i and applying the Cauchy–Schwarz inequality yields K X

Eν (i) [Ni (T )] ≤ T + 2cM,σ KT.

i=1

Hence, with Rν (i) = δ(T − Eν (i) [Ni (T )]), RK,T ≥

K √ √ 1 σ M √ 1 X Rν (i) ≥ 4cM,σ σ 1 − − 2cM,σ KT ≥ cM,σ σ KT = min , KT , K i=1 K 8 4

where the last inequality uses K ≥ 2 and cM,σ ≤ 1/8.

Conclusion

We characterize the finite-time regret–instability trade-off for K-armed bandits. Our lower bound has a constant independent of K, while the tunable SLE-UCB algorithm achieves a regret–instability product of O(T 3/2 log K). These bounds match in their T 3/2 dependence and up to a logarithmic factor in K, thereby characterizing the frontier to logarithmic accuracy. In adaptive experimentation and dynamic resource allocation, the tuning parameter lets a decision maker choose how much regret to accept for more reproducible allocations, while the lower bound shows that this trade-off is unavoidable within the model. It would be interesting to investigate whether these ideas extend to contextual bandits and reinforcement learning.

References Audibert, J.-Y. and Bubeck, S. (2009). Minimax policies for adversarial and stochastic bandits. In Colt. Auer, P., Cesa-Bianchi, N. and Fischer, P. (2002). Finite-time analysis of the multiarmed bandit problem. Machine learning, 47 235–256. Boucheron, S., Lugosi, G. and Massart, P. (2013). Bounding the variance. In Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press, 52–82. Chen, Y. and Lu, J. (2025). arXiv:2503.04855.

A characterization of sample adaptivity in ucb data.

arXiv preprint

Chen, Y. and Lu, J. (2026). Bandit allocational instability. arXiv preprint arXiv:2602.07472. Efron, B. and Stein, C. (1981). The Jackknife Estimate of Variance. The Annals of Statistics, 9 586 – 596. Fan, L. and Glynn, P. W. (2022). arXiv:2210.05660.

The typical behavior of bandit algorithms.

arXiv preprint

Fan, L. and Glynn, P. W. (2025). The fragility of optimized bandit algorithms. Operations Research, 73 3173–3198. Fan, Y., Han, Y., Lv, J., Xu, X. and Zhou, Z. (2025). Precise asymptotics and refined regret of variance-aware ucb. Advances in Neural Information Processing Systems, 38 160795–160837. Gittins, J., Glazebrook, K. and Weber, R. (2011). Multi-armed bandit allocation indices. John Wiley & Sons. Halder, B., Pan, S. and Khamaru, K. (2025). Stable thompson sampling: Valid inference via variance inflation. arXiv preprint arXiv:2505.23260. Halder, B., Sengupta, I., Chowdhury, K., Praharaj, S. and Khamaru, K. (2026). Stabilizing bandits using regularization: Precise regret and a quantitative central limit theorem.

Han, Q. (2026). Thompson sampling: Precise arm-pull dynamics and adaptive inference. arXiv preprint arXiv:2601.21131. Han, Q., Khamaru, K. and Zhang, C.-H. (2024). Ucb algorithms for multi-armed bandits: Precise regret and adaptive inference. arXiv preprint arXiv:2412.06126. Kalvit, A. and Zeevi, A. (2021). A closer look at the worst-case behavior of multi-armed bandit algorithms. Advances in Neural Information Processing Systems, 34 8807–8819. Khamaru, K. and Zhang, C.-H. (2024). Inference with the upper confidence bound algorithm. arXiv preprint arXiv:2408.04595. Lai, T. L. and Wei, C. Z. (1982). Least squares estimates in stochastic regression models with applications to identification and control of dynamic systems. The Annals of Statistics 154–166. Lattimore, T. and Szepesvári, C. (2020). Bandit algorithms. Cambridge University Press. Li, L., Chu, W., Langford, J. and Schapire, R. E. (2010). A contextual-bandit approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web. Praharaj, S. and Khamaru, K. (2025). On instability of minimax optimal optimism-based bandit algorithms. arXiv preprint arXiv:2511.18750. Simchi-Levi, D. and Wang, C. (2023). Multi-armed bandit experimental design: Online decision-making and adaptive inference. In International Conference on Artificial Intelligence and Statistics. PMLR. Simchi-Levi, D., Zheng, Z. and Zhu, F. (2022). A simple and optimal policy design for online learning with safety against heavy-tailed risk. Advances in Neural Information Processing Systems, 35 33795–33805. Simchi-Levi, D., Zheng, Z. and Zhu, F. (2023). Stochastic multi-armed bandits: Optimal trade-off among optimality, consistency, and tail risk. Advances in Neural Information Processing Systems, 36 35619–35630. Villar, S. S., Bowden, J. and Wason, J. (2015). Multi-armed bandit models for the optimal design of clinical trials: benefits and challenges. Statistical science: a review journal of the Institute of Mathematical Statistics, 30 199. Yan, S. and Zhong, H. (2026). Optimism stabilizes thompson sampling for adaptive inference. arXiv preprint arXiv:2602.06014. Zhu, F. and Simchi-Levi, D. (2025). Adaptive variance inflation in thompson sampling: Efficiency, safety, robustness, and beyond. Advances in Neural Information Processing Systems, 38 50466–50484.

Toward the Optimal Regret-Instability Trade-off in Multi-Armed Bandits

Analyze & explore related research in Conceptio

Related documents