Paper deep dive
Bandits with Multiple Optimal Arms: Minimax Regret and Non-Adaptivity
Kaixuan Ji, Qiwei Di, Qingyue Zhao, Heyang Zhao, Quanquan Gu
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 93%
Last extracted: 10/2/2026, 8:46:14 AM
Summary
This paper investigates the minimax regret of multi-armed bandits (MAB) with multiple optimal arms. It establishes a sharper upper bound of O~((K-A)/sqrt(KA) * sqrt(T)) for sub-sampling algorithms, improving upon previous bounds, and provides a matching lower bound, proving near-minimax optimality. The study also demonstrates non-adaptivity, showing that knowledge of the number of optimal arms A is necessary to achieve near-optimal regret.
Entities (9)
Relation Signals (6)
Sub-sampling algorithms → achievesregretbound → O~((K-A)/sqrt(KA) * sqrt(T))
confidence 95% · establishing a O~((K-A)/sqrt(KA) * sqrt(T)) minimax regret
De Heide et al. → citedby → This Paper
confidence 95% · De Heide et al., 2021
Zhu and Nowak → citedby → This Paper
confidence 95% · Zhu and Nowak, 2020
This Paper → provideslowerbound → O~((K-A)/sqrt(KA) * sqrt(T))
confidence 95% · provide a matching lower bound up to logarithmic factors
Knowledge of A → isnecessaryfor → Near-optimal Regret
confidence 92% · knowledge of A up to O~(1) factors is necessary to achieve near-optimal regret
Sub-sampling algorithms → improvesupon → O~(sqrt(KT/A))
confidence 90% · improving the previous O~(sqrt(KT/A)) regret
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:We study multi-armed bandits (MAB) with multiple optimal arms, motivated by the fact that many practical decision making problems admit multiple correct answers. For $K$-armed bandits with $A$ optimal arms, we first provide a sharper analysis of previous sub-sampling algorithms (De Heide et al., 2021; Zhu and Nowak, 2020), establishing a $\tilde{O}\Big(\frac{K-A}{\sqrt{KA}}\sqrt{T} \Big)$ minimax regret, where $T$ is the total number of interactions and $\tilde O(\cdot)$ drops all constant and logarithmic factors, improving the previous $\tilde{O}(\sqrt{KT/A})$ regret. We then provide a matching lower bound up to logarithmic factors, indicating that our established rate is nearly minimax-optimal. We further show that the knowledge of $A$ up to $\tilde{O}(1)$ factors is necessary to achieve near-optimal regret, as near-optimal algorithms for one number of optimal arms must incur substantially larger regret than optimal regret for a smaller number. Overall, our results provide a comprehensive minimax characterization of $K$-armed bandits with $A$ over the entire range of $1 \leq A \leq K-1$.
Tags
Links
- Source: https://arxiv.org/abs/2609.38659v2
- Canonical: https://arxiv.org/abs/2609.38659v2
Trouble viewing inline? Open PDF directly →
Full Text
134,831 characters extracted from source content.
Expand or collapse full text
Bandits with Multiple Optimal Arms: Minimax Regret and Non-Adaptivity Kaixuan Ji Qiwei Di11footnotemark: 1 Qingyue Zhao11footnotemark: 1 Heyang Zhao Quanquan Gu †thanks: Equal contribution†thanks: Department of Computer Science, University of California, Los Angeles, CA 90095, USA; e-mail: kaixuanji@cs.ucla.edu†thanks: Department of Computer Science, University of California, Los Angeles, CA 90095, USA; e-mail: qiwei2000@cs.ucla.edu†thanks: Department of Computer Science, University of California, Los Angeles, CA 90095, USA; e-mail: zhaoqy24@cs.ucla.edu†thanks: Department of Computer Science, University of California, Los Angeles, CA 90095, USA; e-mail: hyzhao@cs.ucla.edu†thanks: Department of Computer Science, University of California, Los Angeles, CA 90095, USA; e-mail: qgu@cs.ucla.edu Abstract We study multi-armed bandits (MAB) with multiple optimal arms, motivated by the fact that many practical decision making problems admit multiple correct answers. For K-armed bandits with A optimal arms, we first provide a sharper analysis of previous sub-sampling algorithms (De Heide et al., 2021; Zhu and Nowak, 2020), establishing a O~(K−AKAT) O ( K-A KA T ) minimax regret, where T is the total number of interactions and O~(⋅) O(·) drops all constant and logarithmic factors, improving the previous O~(KT/A) O( KT/A) regret. We then provide a matching lower bound up to logarithmic factors, indicating that our established rate is nearly minimax-optimal. We further show that the knowledge of A up to O~(1) O(1) factors is necessary to achieve near-optimal regret, as near-optimal algorithms for one number of optimal arms must incur substantially larger regret than optimal regret for a smaller number. Overall, our results provide a comprehensive minimax characterization of K-armed bandits with A over the entire range of 1≤A≤K−11≤ A≤ K-1. 1 Introduction Multi-armed bandits (MAB) provide a basic model of sequential decision making under uncertainty, whose implication covers a wide range of practical problems (Bouneffouf et al., 2020; Pryzant et al., 2023; Panda et al., 2025). In an MAB, a learner repeatedly selects an action from an action set, observes a noisy reward, and aims at maximizing the cumulative reward via balancing exploration and exploitation. Classical results have characterized the difficulty of the problem by a worst case regret Θ(KT) ( KT) when T≥KT≥ K, where K is the number of arms and T is the total number of interactions (Auer et al., 2002; Audibert and Bubeck, 2009; Lattimore, 2018). However, in practice, many decision making problems, including code generation (Jimenez et al., 2024; Jain et al., 2025), math problem solving (Hendrycks et al., 2021) and good recommendation (Kano et al., 2019), admit multiple correct or satisfactory solutions. Such problems motivate the study of bandit learning with multiple correct answers (Degenne and Koolen, 2019), on which the benefit of the abundance of optimal arms is not captured by the classical Θ(KT) ( KT) regret. Prior work exploits this benefit through sub-sampling: select approximately K/AK/A arms and run a standard bandit algorithm on the selected subset (Zhu and Nowak, 2020; De Heide et al., 2021), yielding an expected regret of O~(KT/A) O( KT/A), where A is the number of optimal arms. However, this rate does not fully capture the benefit when A is close to K. Indeed, for A=K−1A=K-1, if we randomly sample two arms and apply any minimax-optimal bandit algorithm, with probability only O(1/K)O(1/K) one of the two arms is sub-optimal, leading to a regret of O(T/K)O( T/K). This discrepancy raises the question: What is the minimax regret of multi-armed bandit with multiple optimal arms? In this paper, we solve this question up to logarithmic factors. We provide a refined analysis of previous sub-sampling algorithms, and a novel near-matching lower bound for the regime A>K/4A>K/4 that was not covered by prior work. Formally, writing the class of K-armed bandit with A optimal arms as ΞK,A _K,A, our upper bound and lower bound together gives infsupν∈ΞK,ARegret,ν(T)=Θ~(K−AKAT), _ Alg _ν∈ _K,ARegret_ Alg,ν(T)= ( K-A KA T ), where Regret,ν(T)Regret_ Alg,ν(T) denotes expected regret under algorithm Alg and bandit instance ν. This characterization recovers the previous rate when K−A=Ω(K)K-A= (K) and sharpens the previous regret upper bound by a factor of Θ~((K−A)/K) ((K-A)/K) when K−A=o(K)K-A=o(K). The minimax characterization also raises an adaptation question that whether a learner can attain the appropriate rate without knowing A (Zhu and Nowak, 2020; De Heide et al., 2021). De Heide et al. (2021) showed that, for well separated B=o(A)B=o(A), if A+B≤KA+B≤ K, then no strategy can simultaneously achieve minimax-optimal regret on both ΞK,A _K,A and ΞK,B _K,B. In this paper, we provide a novel analysis that removes the constraint on A+B≤KA+B≤ K, showing that any strategy achieving near-optimal regret on ΞK,A _K,A must pay an additional multiplicative factor of Ω~(A/B) ( A/B) for regret on ΞK,B _K,B, thus providing a near-complete picture of non-adaptivity. Our contributions are summarized as follows • We provide a refined analysis of previous algorithms for bandit with multiple optimal arms. Together with our novel lower bound for the regime A>K/4A>K/4, we establish the minimax regret for K-armed bandit with A optimal arms, up to logarithmic factors, for all K, T≥KT≥ K and A∈[1,K−1]A∈[1,K-1]. • We show that, for any well separated A>BA>B, any strategy achieving near-optimal regret on ΞK,A _K,A will demonstrate a multiplicative loss of Ω~(A/B) ( A/B) compared to the minimax-optimal rate on ΞK,B _K,B, necessitating the knowledge of A to achieve the near-optimal regret. • Technically, standard two-point lower-bound arguments based on disjoint sets of optimal arms become ineffective when the number of optimal arms is close to K. We overcome this obstacle by considering a larger collection of symmetric instances and comparing them with a common all-equal reference instance. Together with a multiplicative change-of-measure argument, this approach enables us to establish worst-case hardness results even when the instances necessarily share optimal arms. Notation. The set A are assumed to be finite throughout the paper. For nonnegative sequences xn\x_n\ and yn\y_n\, we write xn=O(yn)x_n=O(y_n) if lim supn→∞xn/yn<∞ _n→∞x_n/y_n<∞, xn=o(yn)x_n=o(y_n) if lim supn→∞xn/yn=0 _n→∞x_n/y_n=0, yn=Ω(xn)y_n= (x_n) (interchangeably written as yn≳xny_n x_n) if xn=O(yn)x_n=O(y_n), and yn=Θ(xn)y_n= (x_n) if xn=O(yn)x_n=O(y_n) and xn=Ω(yn)x_n= (y_n). We further employ O~(⋅),Ω~(⋅) O(·), (·), and Θ~(⋅) (·) to hide polylogpolylog factors. For a pair of probability measures P≪QP Q on the same space, we use TV(ℙ,ℚ)TV(P,Q) to denote their total variation, and (P∥Q)≔∫log(dP/dQ)dP KL (P\|Q ) (\,dP/\,dQ)\,dP to denote their KL divergence. We denote [N]≔1,⋯,N[N] \1,·s,N\ for any positive integer N. Boldfaced lowercase letters, like x are reserved for vectors, whose i-th entry is represented as xix_i. 2 Related Work Bandits with Multiple Optimal Arms. MABs with multiple optimal arms has been widely investigated in both regret minimization and pure exploration settings. In the pure exploration setting, the existence of multiple correct answer largely reduces the sample complexity (De Heide et al., 2021; Katz-Samuels and Jamieson, 2020), and the asymptotical optimal instance-dependent rate for fixed confidence best arm identification was established when number of optimal arm A is unknown (Degenne and Koolen, 2019) and known (Truong, 2026). In the regret minimization setting, when restricting algorithms to be uniformly fast convergent (Garivier et al., 2019, Definition 1), the instance dependent regret grows with ∑a∈∖∗Δa−1logT _a ^* _a^-1 T asymptotically as T→∞T→∞, linearly with the number of suboptimal arms K−AK-A (Lai and Robbins, 1985; Burnetas and Katehakis, 1996). The uniform convergence requirement is relaxed in a subsequent line of work that considered bandits with large or even infinite number of arms (Chaudhuri and Kalyanakrishnan, 2017; Chaudhuri and Kalyanakrishnan, 2018; Aziz et al., 2018; De Heide et al., 2021; Zhu and Nowak, 2020). Specializing back to our setting, their results give an instance-dependent regret of KlogTlog(Δ−1)(AΔ)−1K T ( ^-1)(A )^-1 (De Heide et al., 2021) and correspondingly, O~(KT/A) O( KT/A) worst case regret, which is near-optimal when K−A=Ω(K)K-A= (K) (Zhu and Nowak, 2020), via an algorithmic sub-sampling (Wang et al., 2008; Bayati et al., 2020; Kalvit and Zeevi, 2020). Despite these advances, the minimax characterization of regret is restricted to the regime K−A=Ω(K)K-A= (K), since the standard lower bound techniques like Le Cam’s method are ineffective at K−A=o(K)K-A=o(K). In offline setting, Ji et al. (2026) provided a near-optimal characterization for all A∈(0,K)A∈(0,K), when restricting to uniform behavior policy, through a multiplicative change-of-measure appeared in Degenne and Koolen (2019); Garivier and Kaufmann (2021). However, the corresponding result in online setting is not yet clear. Adaptivity in Bandits. Adaptivity asks whether a learner can match the regret attainable when a problem parameter is known, without receiving that parameter as input. Some examples of affirmative results of adaptivity include adapting to unknown misspecification in contextual bandit (Foster et al., 2020), unknown weak corruption budgets (Wei et al., 2022; Liu et al., 2024), and unknown noise variance (Zhao et al., 2023). Despite these results, other adaptation problems demonstrate intrinsic hardness, leading to a number of hardness results. Examples in this category include adapting to unknown corruption tolerance in strong corruption (Bogunovic et al., 2021; He et al., 2022), unknown smoothness classes in continuum-armed bandit (Locatelli and Carpentier, 2018; Hadiji, 2019) and nonparametric contextual bandit (Gur et al., 2022), unknown reward range (Hadiji and Stoltz, 2023), unknown reward noise distribution (Ashutosh et al., 2021; Genalti et al., 2024), and unknown smallest realizable function class within a nested function class (Zhu and Nowak, 2022; Marinov and Zimmert, 2021). For the proportion of optimal arms that is studied in this paper, Zhu and Nowak (2020) prove non-adaptivity and characterize Pareto-optimal gap-independent rates, and De Heide et al. (2021) establish a gap-dependent non-adaptivity lower bound in the reservoir model. Compared to their proof, our hardness result also cover regimes with A+B>KA+B>K, where A and B are the respective numbers of optimal arms in two K-armed instance classes. Any two instances, one from each class, then share an optimal arm, so the earlier constructions in Zhu and Nowak (2020); De Heide et al. (2021) based on disjoint optima cannot establish non-adaptivity in this regime. 3 Problem Setup We consider K-armed multi-armed bandit (MAB) with A optimal arms and denote it with a tuple (,r,T)(A,r,T), where K:=||<∞K:=|A|<∞ is the number of actions, r:→[0,1]r:A→[0,1] is the reward function unknown to the learner, and T≥1T≥ 1 is the total number of interactions. At each round t∈[T]t∈[T], the learner selects an action at∈a_t according to some strategy, and observes a noisy reward rt=r(at)+εtr_t=r(a_t)+ _t, where εt _t is 11-sub-Gaussian (Lattimore and Szepesvári, 2020, Definition 5.2). The learner’s goal is to minimize the regret: Regret(T)=∑t=1Tr∗−∑t=1T[r(at)], (T)= _t=1^Tr^*- _t=1^TE[r(a_t)], where r∗=maxa∈r(a)r^*= _a r(a) and the expectation is taken with respect to the algorithm and the noises. In this paper, we consider the case where the set of optimal arms opt:=a∈:r(a)=maxa′∈r(a′)A^opt:=\a :r(a)= _a r(a )\ has a known cardinality A∈[1,K−1]A∈[1,K-1]. We denote sub=∖optA^sub=A A^opt. Our goal is to characterize the minimax optimality of the instance class infsupν∈ΞK,ARegret,ν(T), _ Alg _ν∈ _K,ARegret_ Alg,ν(T), (3.1) for given K,A,TK,A,T, where ΞK,A:=ν:|opt(ν)|=A _K,A:=\ν:|A^opt(ν)|=A\. 4 Algorithms and Upper Bounds In this section, we provide the algorithm for learning a K-armed bandit with A optimal arms. The core algorithm design, which first samples a portion of arms and then run a bandit algorithm on the sampled set, follows the previous algorithm design for bandit with many optimal arms (Zhu and Nowak, 2020; De Heide et al., 2021). In this paper, we provide a sharper analysis, achieving a near-optimal rate on the entire range A∈[1,K−1]A∈[1,K-1]. We first summarize the algorithm in Algorithm 1. At a high level, the algorithm first randomly samples a subset ℬ⊆B with cardinality |ℬ|=L=minK−A+1,⌈log(2T)log(K(K−A)−1)⌉if A≤K/2minK−A+1,⌈log2T+1⌉otherwise. |B|=L= cases \K-A+1, (2T) (K(K-A)^-1) \&if A≤ K/2\\ \K-A+1, _2T+1 \&otherwise cases. (4.1) Then Algorithm 1 runs a minimax-optimal algorithm on ℬB. The following theorem characterizes the regret upper bound of Algorithm 1. Theorem 4.1. The regret of Algorithm 1 with L set in (4.1) on any K-armed bandit instance with horizon T≥KT≥ K and exactly A∈[1,K−1]A∈[1,K-1] optimal arms admits an upper bound Regret(T)=O~(K−AKAT). (T)= O ( K-A KA T ). Although we analyze the same algorithmic framework as Zhu and Nowak (2020), we establish a strictly superior regret bound via a sharper theoretical analysis. Specifically, our result shaves off a factor of (K−A)/K(K-A)/K from the previous O~(KT/A) O( KT/A) bound. This improvement is particularly pronounced in bandit instances with a large proportion of optimal arms. Remark 4.2. Theorem 4.1 provides an improved guarantee solely in expectation. One may naturally ask whether this improvement can also be attained with high probability. In Appendix D, we show that such an extension is impossible. We prove that any algorithm satisfying the regret bound of Theorem 4.1 must suffer Ω~(T) ( T) regret with non-vanishing probability. This finding highlights an inherent separation between expected and high-probability regret in the setting of bandits with multiple optima. 4.1 Proof Overview of Theorem 4.1 We outline the proof of Theorem 4.1, deferring the full details to Appendix A. We distinguish three cases according to the composition of the randomly selected subset ℬB: 1. The subset ℬB contains no optimal arms, corresponding to the event ℰmiss:=ℬ∩opt=∅E_miss:=\B∩A^opt= \. In this case, we use the trivial regret bound of T. 2. The subset ℬB contains both optimal and suboptimal arms, denoted by event ℰsub:=ℬ∩sub≠∅∩ℬ∩opt≠∅E_sub:=\B∩A^sub≠ \∩\B∩A^opt≠ \. In this case, running MOSS for T rounds incurs expected regret O(LT)O( LT). 3. The subset ℬB contains only optimal arms, corresponding to the event ℰopt:=ℬ⊆optE_opt:=\B A^opt\. In this case, the regret is zero. Previous Analysis. Previously, De Heide et al. (2021); Zhu and Nowak (2020) distinguish between missing all optimal arms and including at least one. Choosing L of order K/AK/A, up to suitable logarithmic factors, makes ℙ[ℰmiss]P[E_miss] negligible. On the complementary event ℰsub∪ℰoptE_sub∪E_opt, the expected regret is bounded by O(LT)O( LT), yielding an overall bound of O~(KT/A) O( KT/A). This rate is optimal up to logarithmic factors when K−A=Ω(K)K-A= (K). Our Approach. The previous analysis is not sharp when A is close to K, because it does not exploit the zero regret incurred on ℰoptE_opt. In this regime, each sampled arm is suboptimal with probability only (K−A)/K(K-A)/K, and the subset size is L=O~(1)L= O(1). A union bound therefore gives ℙ[ℰsub]≤ℙ[ℰmiss∪ℰsub]≤LK−AK=O~(K−AK). [E_sub] [E_miss∪E_sub]≤ L K-AK= O ( K-AK ). Combining this probability bound with the conditional expected regret bound O~(T) O( T) on ℰsubE_sub yields Regret(T)≲ℙ[ℰmiss]T+ℙ[ℰsub]LT=O~(K−AKT), (T) [E_miss]T+P[E_sub] LT= O ( K-AK T ), where the contribution from ℰmissE_miss is made negligible by the choice of L. This establishes the desired rate when A is close to K. Algorithm 1 SMOSS (Zhu and Nowak, 2020; De Heide et al., 2021) 0: Action set A, number of total rounds T, number of optimal arm A if A≤K/2A≤ K/2. 1: Set L as in (4.1) and sample a subset ℬ⊆B of L distinct arms uniformly without replacement. 2: Run any minimax-optimal L-armed bandit algorithm, such as MOSS (Audibert and Bubeck, 2009), on ℬB for T rounds. 5 Lower Bounds In this section, we provide a lower bound of (3.1). We begin with the regime in which the number of optimal arms is small relative to K. The lower bound in this regime is suggested by previous work (Zhu and Nowak, 2020) and follows from a standard Le Cam two-point argument (see, e.g., Lattimore and Szepesvári 2020, Theorem 15.2). Theorem 5.1. Given any K, 1≤A≤K/41≤ A≤ K/4 and T≥(K−A)/AT≥(K-A)/A, for any algorithm, there exists a K-armed bandit with A optimal arms, on which the algorithm suffers from Ω~(A−1KT) ( A^-1KT) regret. We next consider the regime in which A is comparable to K, where the proof techniques of previous lower bounds (De Heide et al., 2021; Zhu and Nowak, 2020) is not effective. The main difficulty arises when A is close to K: the overlap between the sets of optimal arms makes a standard two-point argument ineffective. The lower bound for this regime is stated in the following theorem. Theorem 5.2. Given any K, A>K/4A>K/4 and T≥4/logKT≥ 4/ K, for any algorithm, there exists a K-armed bandit with A optimal arms, on which the algorithm suffers from Ω~((K−A)K−1T) ((K-A)K^-1 T) regret. Together, Theorems 5.1 and 5.2, combined with Theorem 4.1, yield infsupν∈ΞK,ARegret,ν(T)=Θ~(K−AKAT), _ Alg _ν∈ _K,ARegret_ Alg,ν(T)= ( K-A KA T ), for all K, 1≤A≤K−11≤ A≤ K-1 and T≥KT≥ K. This characterizes the minimax regret of K-armed bandit with A optimal arms up to logarithmic factors across the full range of A. 5.1 Proof Overview of Theorem 5.1 In this section, we provide a quick overview of the proof of Theorem 5.1 and defer the full proof to Appendix B.1. Starting from here, unless stated otherwise, we design the noise of rewards to be standard Gaussian. Fix a constant Δ>0 >0 to be specified later. We apply the Le Cam two-point method with two problem instances. For the first instance, we consider 0⊂S_0 such that |0|=A|S_0|=A and define the instance ν0 _0 whose reward given by r0(a)=1/2+Δr_0(a)=1/2+ for a∈0a∈S_0 and r0(a)=1/2r_0(a)=1/2 otherwise. For any algorithm Alg, let N(T)N_S(T) be the number of pulls within S up to time T. By the pigeonhole principle, there exists some 1⊂∖0S_1 S_0 such that |1|=A|S_1|=A and ν0,Alg[N1(T)]≤TAK−A≲TAK, _ _0, Alg[N_S_1(T)]≤ TAK-A TAK, where the expectation is taken over the distribution jointly given by instance r0r_0 and Alg. Now we construct the second instance ν1 _1 as r1(a)=1/2+2Δr_1(a)=1/2+2 for all a∈1a∈S_1 and r1(a)=r0(a)r_1(a)=r_0(a) otherwise. Under this construction, the distribution induced by the two instances is close, as the KL-divergence between the trajectory distributions ℙ0P_0 and ℙ1P_1 is given by ∑a∈0[Na(T)]KL((r0(a),1)∥(r1(a),1))≲TAKΔ2, _a E_0[N_a(T)]KL (N(r_0(a),1)\|N(r_1(a),1) ) TAK ^2, (5.1) where we adopt the shorthand ℙi:=ℙνi,AlgP_i:=P_ _i, Alg to denote the probability distributions over trajectories induced by the interaction between algorithm Alg and instances νi _i for i∈0,1i∈\0,1\. Now we pick Δ∼K/(AT) K/(AT), yielding (ℙ0∥ℙ1)=O(1) KL (P_0\|P_1 )=O(1), indicating that under algorithm Alg, it is hard to distinguish ν1 _1 from ν0 _011 1 In general, the KL-divergence (ℙ∥ℚ) KL (P\|Q ) between two distributions ℙP and ℚQ being a constant indicates that ℙP and ℚQ cannot be reliably distinguished.. However, we see that the optimal actions of ν0 _0 and ν1 _1 are disjoint. In other words, at each step, the learner incurs a regret of Δ on either ν0 _0 or ν1 _1 if the learner cannot distinguish ν0 _0 and ν1 _1. Since under our construction, the learner cannot reliably distinguish ν0 _0 and ν1 _1 until time step T, it must suffer from a regret of Ω(TΔ)=Ω(KT/A) (T )= ( KT/A) on one of the instances. 5.2 Proof Overview of Theorem 5.2 The preceding proof of Theorem 5.1 relies on two instances whose trajectory distributions are difficult to distinguish but whose sets of optimal arms are disjoint. Disjointness is essential: if the instances share an optimal arm, an algorithm can repeatedly pull that arm and incur zero regret on both instances without distinguishing between them. When A>K/2A>K/2, however, any two instances in ΞK,A _K,A share at least one optimal arm. An argument based solely on such a pair therefore cannot establish the desired lower bound. To overcome this obstacle, we consider a larger collection of instances, where each instance is given by subtracting the reward by a small gap Δ on some subset of A with cardinality K−AK-A. Formally, we state the instances as indexed by μ∈A:=∈1/2,1/2−ΔK|∑i=1K(μi=1/2)=A, μ _A:= \ μ∈\1/2,1/2- \^K | _i=1^K ( _i=1/2)=A \, where Δ=Θ~(1/T) = (1/ T). Given any μ,ν∈Aμ,ν _A, the reward distribution on any of the arms differs by only Δ , making any algorithm unable to distinguish between any individual instance among AV_A. To formally state this, we introduce an auxiliary instance θ whose reward vector is given by =(1/2,⋯,1/2)⊤∈ℝK θ=(1/2,·s,1/2) ^K, and let =A∪θV=V_A∪\θ\. We first show that, for any μ∈Aμ _A, the induced distribution is sufficiently close to θ. We do this by computing the KL-divergence between the two distribution ℙμP_μ and ℙθP_θ, induced by a fixed algorithm Alg, and μ, θ correspondingly. By the chain rule of KL-divergence, we see that (ℙθ∥ℙμ)=Δ22a∈sub(μ)[Na(T)]≤TΔ2=O(1), KL (P_θ\|P_μ )= ^22E_a∈A^sub(μ)[N_a(T)]≤ T ^2=O(1), where Na(T)N_a(T) denotes the number of pulls on arm a up to T interactions, and the inequality holds due to a∈sub(μ)[Na(T)]≤TE_a∈A^sub(μ)[N_a(T)]≤ T. Recall that, an O(1)O(1) KL-divergences indicates that ℙμP_μ and ℙθP_θ cannot be reliably distinguished. This implies that, Alg cannot behaves too distinctively on μ and θ. To characterize this, we need the following multiplicative change-of-measure proposition. See Remark B.2 for its previous applications in proving bandit lower bounds. Proposition 5.3. Let ℙP and ℚQ be probability measures satisfying ℙ≪ℚP and define the log-likelihood ratio L=log(dℙ/dℚ)L= (\,dP/\,\,dQ). Then, for every bounded random variable X∈[0,b]X∈[0,b] and every γ∈ℝγ , ℙ[X]≤eγℚ[X]+bℙ[L>γ]. _P[X]≤ e^γE_Q[X]+bP[L>γ]. (5.2) We apply Proposition 5.3 with ℚ=ℙμQ=P_μ, ℙ=ℙθP=P_θ, and γ≈(ℙθ∥ℙμ)γ≈ KL (P_θ\|P_μ ). Since θ[L]=(ℙθ∥ℙμ)E_θ[L]= KL (P_θ\|P_μ ), a careful selection of γ actually allows ℙ[L>γ]P[L>γ] negligible. The application of Proposition 5.3 results in the following change-of-measure inequality μ[X]≳θ[X]−o(TK), _μ[X] _θ[X]-o ( TK ), (5.3) for any random variable X∈[0,T]X∈[0,T]. However, since on the instance θ, the rewards on all the arms are equal, the algorithm Alg must allocate at least T(K−A)/KT(K-A)/K pulls on one of the subset ⊂S with ||=K−A|S|=K-A by symmetry. Now we consider the instance μ∈Aμ _A such that sub(μ)=A^sub(μ)=S. We transfer the behavior of Alg on θ to μ via (5.3). In particular, substitute X with Nsub(μ)(T)=∑t=1Tat∈sub(μ)N_A^sub(μ)(T)= _t=1^T \a_t∈A^sub(μ)\, we obtain μ[Nsub(μ)(T)]≳θ[Nsub(μ)(T)]−o(TK)≥K−AKT−o(TK)=Ω(K−AKT). _μ[N_A^sub(μ)(T)] _θ[N_A^sub(μ)(T)]-o ( TK )≥ K-AKT-o ( TK )= ( K-AKT ). Finally, recall that Regretμ,(T)=Δμ[Nsub(μ)(T)]Regret_μ, Alg(T)= _μ[N_A^sub(μ)(T)], we see that Regretμ,(T)≳Ω(K−AKTΔ)=Ω~(K−AKT), _μ, Alg(T) ( K-AKT )= ( K-AK T ), where the last equation is obtained from Δ=Θ(1/T) = (1/ T). This gives the desired lower bound. 6 Impossibility to Adapt to Number of Optimal Arms When A=o(K)A=o(K), Algorithm 1 requires A to know the sample size L to achieve the near-minimax rate. In this section, we show that such knowledge of the A is necessary. In particular, we show that, any algorithm cannot achieve (near)-minimax rate simultaneously on ΞK,A _K,A and ΞK,B _K,B, if at least one of A or B is o(K)o(K). From a technical perspective, we split the results into two disjoint regimes: A+B≤KA+B≤ K and A+B>KA+B>K. We first consider the simpler case B≤K−AB≤ K-A. Theorem 6.1. Let 1≤A≤K−11≤ A≤ K-1, and consider any algorithm Alg satisfying that there exists some ΓK,T=polylog(K,T) _K,T=polylog(K,T) such that for all T>0T>0, supν:|opt(ν)|=ARegretν,(T)≤ΓK,TK−AKAT. _ν:\,|A^opt(ν)|=ARegret_ν, Alg(T)≤ _K,T K-A KA T. Then ∀ B≤minA/(8ΓK,T),K−AB≤ \A/(8 _K,T),K-A\ and T≥max256B2ΓK,T2/(KA),KA/(16B2ΓK,T2)T≥ \256B^2 ^2_K,T/(KA),KA/(16B^2 _K,T^2)\, there exists a K-armed bandit instance ν with exactly B optimal arms such that Regretν,(T)≥Ω(KABΓK,TT). _ν, Alg(T)≥ ( KAB _K,T T ). (6.1) Theorem 6.1, in terms of both technique and results statement, follows De Heide et al. (2021, Theorem 3). Thus, it also admits constraints to the range of B similar to De Heide et al. (2021). The constraint B=O~(A)B= O(A) is mild, as if B=Ω~(A)B= (A), then running SMOSS with B also gives a near-optimal rate on ΞK,A _K,A up to a factor of O(A/B)=O~(1)O(A/B)= O(1). The second constraint, B≤K−AB≤ K-A, however, is intrinsic to the proof technique. Relaxing this constraint requires fundamentally different approach. We provide an overview of the proof technique of Theorem 6.1, along with its limitation, in Section 6.1. We next state the results in the regime B≥K−AB≥ K-A as follows, Theorem 6.2. Let K/2≤A≤K−1K/2≤ A≤ K-1, and consider any algorithm Alg achieving near-optimal regret on ΞK,A _K,A, that is, for all T>0T>0 and some fixed ΓK,T=polylog(K,T) _K,T=polylog(K,T) supν:|opt(ν)|=ARegretν,(T)≤ΓK,TK−AKT. _ν:\,|A^opt(ν)|=ARegret_ν, Alg(T)≤ _K,T K-AK T. Then, for any B satisfying K−A≤B≤K/2K-A≤ B≤ K/2 and Blog(32B/(K−A))≤K/(256ΓK,T)B (32B/(K-A))≤ K/(256 _K,T) and any T≥maxK2(B2ΓK,T2log(32B/(K−A)))−1,4T≥ \K^2 (B^2 _K,T^2 (32B/(K-A)) )^-1,4\, there exists a K-armed bandit instance ν with exactly B optimal arms such that Regretν,(T)≥Ω~(KABΓK,TT). _ν, Alg(T)≥ ( KAB _K,T T ). Ignoring all logarithmic factor, Theorem 6.1 and Theorem 6.2 together show that, when B=O(A)B=O(A), any algorithm that is nearly minimax-optimal on ΞK,A _K,A must suffer a regret of at least Ω~(KAT/B) ( KAT/B), which demonstrates a multiplicative loss of Ω~(A/B) ( A/B) compared to the minimax-optimal rate O~(KT/B) O( KT/B) on ΞK,B _K,B. These results indicate that, algorithm agnostic to the number of optimal arms cannot simultaneously attain the near-optimal regret on ΞK,A _K,A and ΞK,B _K,B if B=o(A)B=o(A), necessitating the knowledge of the number of optimal arms up to logarithmic factors. Remark 6.3. The tradeoff between ΞK,A _K,A and ΞK,B _K,B when B=o(A)B=o(A) motivates the notion of a Pareto-optimal algorithm (Zhu and Nowak, 2020): one for which no other algorithm achieves better performance pointwise over all 1≤A≤K−11≤ A≤ K-1. Designing a Pareto-optimal algorithm for our setting remains an interesting direction for future work. 6.1 Proof Overview of Theorem 6.1 In this section, we provide an overview of the proof of Theorem 6.1. At a high level, the proof follows De Heide et al. (2021) and considers the two-point-type instances, and then shows that algorithm cannot reliably distinguish these two instances through a TV-based change-of-measure argument. For simplicity, we constrain us to the case K−A=Ω(K)K-A= (K). At a high level, our goal is to consider two instances ν0∈ΞK,A _0∈ _K,A and ν1∈ΞK,B _1∈ _K,B, such that they are similar enough, yet any algorithm must suffer from sufficiently large regret on at least one of them. To do this, we consider partition A as follows, where 0S_0 is fixed and 1S_1 determined later =0∪1∪2,where |0|=A,|1|=B, and ,|2|=K−A−B. =S_0∪S_1∪S_2, |S_0|=A,\,|S_1|=B, and ,|S_2|=K-A-B. We use r0r_0 for the reward mean of ν0 _0 and r1r_1 for the reward of ν1 _1, which are given by r0(a)=1/2,a∈01/2−Δ,a∈11/2−Δ,a∈2,r1(a)=1/2,a∈01/2+Δ,a∈11/2−Δ,a∈2. r_0(a)= cases1/2,&a∈S_0\\ 1/2- ,&a∈S_1\\ 1/2- ,&a∈S_2 cases, r_1(a)= cases1/2,&a∈S_0\\ 1/2+ ,&a∈S_1\\ 1/2- ,&a∈S_2 cases. It is easy to verify that ν0∈ΞK,A _0∈ _K,A and ν1∈ΞK,B _1∈ _K,B. The key observation is that, since arms in 0∁S_0 is sub-optimal under ν0 _0, any algorithm Alg optimal on ΞK,A _K,A cannot allocate too many pulls on 0∁S_0 , the same for one of its subset 1S_1. In particular, fixing the algorithm and dropping the subscripts of Alg, if Regret(T)≤RARegret(T)≤ R_A, we must observe 0[N0∁(T)]≤RAΔ, _0[N_S_0 (T)]≤ R_A , where 0E_0 is a short hand for ν0E_ _0 and similar abbreviation applies to ν1 _1. By symmetry, there exist a subset ⊆0∁S S_0 such that ||=B|S|=B and 0[N(T)]≤BRA(K−A)Δ. _0[N_S(T)]≤ BR_A(K-A) . Without loss of generality, we pick 1=S_1=S. With this construction, we see that (i) since Alg does not allocate sufficient pulls on 1S_1, Alg cannot reliably distinguish ν1 _1 from ν0 _0; and (i) the optimal actions of ν0 _0 and ν1 _1 are disjoint, therefore Alg cannot be optimal simultaneously on them. Formally, we first show that Alg cannot reliably distinguish ν1 _1 from ν0 _0, through a computation of the KL-divergence between there distribution. Taking Δ=Θ((K−A)/(BRA)) = ((K-A)/(BR_A)) (ℙ0∥ℙ1)=0[N1(T)]⋅(2Δ)2=O(BRAΔK−A)=O(1). KL (P_0\|P_1 )=E_0[N_S_1(T)]·(2 )^2=O ( BR_A K-A )=O(1). In this case, the distribution ℙ0P_0 and ℙ1P_1 is close enough, therefore the random variable N1(T)N_S_1(T) behaves similarly under these two distribution. In particular, a change-of-measure leads to 1[N1(T)]≤0[N1(T)]+TTV(ℙ0,ℙ1)≤0[N1(T)]+T12(ℙ0∥ℙ1), _1[N_S_1(T)] _0[N_S_1(T)]+TTV(P_0,P_1) _0[N_S_1(T)]+T 12 KL (P_0\|P_1 ), where the last inequality holds due to Pinsker’s inequality. Plugging in Δ=Θ((K−A)/(BRA)) = ((K-A)/(BR_A)) into 0[N1(T)]≤BRA/((K−A)Δ)E_0[N_S_1(T)]≤ BR_A/((K-A) ) and (ℙ0∥ℙ1)=O(1) KL (P_0\|P_1 )=O(1) gives 1[N1(T)]≤B2RA2(K−A)2+O(T)=O~(B2(K−A)2(K−A)2TKA+T)=O~(T), _1[N_S_1(T)]≤ B^2R_A^2(K-A)^2+O(T)= O ( B^2(K-A)^2 (K-A)^2TKA+T )= O(T), where the first equation holds by plugging in the rate in Theorem 4.1. Finally, a careful selection of constants enables T−1[N1(T)]=Ω(T)T-E_1[N_S_1(T)]= (T), thus Regretν1(T)≥(T−1[N1(T)])Δ=Ω(TΔ)=Ω(T(K−A)BRA)=Ω~(KABT), _ _1(T)≥(T-E_1[N_S_1(T)]) = (T )= ( T(K-A)BR_A )= ( KAB T\ ), which gives the desired rate. 6.2 Proof Overview of Theorem 6.2 Similar to Theorem 5.1, the proof of Theorem 6.1 relies on the two-point construction that requires the two instances have disjoint sets of optimal arms. However, in the case A+B>KA+B>K, any instance ν0∈ΞK,A _0∈ _K,A and ν1∈ΞK,B _1∈ _K,B must share at least one optimal arm a∈opt(ν0)∩opt(ν1)a∈A^opt( _0)∩A^opt( _1), preventing an application in this regime. We overcome this obstacle by showing that any near-optimal algorithm must exhibit a non-uniform exploration profile akin to that of Algorithm 1, therefore ruling out algorithms that concentrate their pulls on a fixed arm or set of arms. Yet even under a fixed algorithm, different instances in ΞK,A _K,A induce different trajectory distributions, complicating a unified characterization of its behavior. We therefore characterize the algorithm’s exploration profile on a common reference instance θ, in which all arms have the same mean reward. Such uniformed characterization is enabled by the change-of-measure in Proposition 5.3, if we select the instances in ΞK,A _K,A close enough to θ. Formally, we have the following lemma. Lemma 6.4. Let A=Ω~(K)A= (K), and suppose that Alg is minimax-optimal on ΞK,A _K,A up to logarithmic factors, namely supν:|opt(ν)|=ARegretν,(T)≤ΓK,TK−AKAT, _ν:\,|A^opt(ν)|=ARegret_ν, Alg(T)≤ _K,T K-A KA T, where ΓK,T=polylog(K,T) _K,T=polylog(K,T). Let θ denote the all-equal instance. Then, ignoring logarithmic factors, for every m∈[T]m∈[T], and every ⊂S with ||=K−A|S|=K-A, ℙθ[N(T)≥m]≲O~(K−AKTm). _θ [N_S(T)≥ m ] O ( K-AK Tm ). Moreover, for any ⊆U such that ||=B≥K−A|U|=B≥ K-A, we have ℙθ[N(T)≥m]≲O~(BKTm). _θ [N_U(T)≥ m ] O ( BK Tm ). (6.2) Lemma 6.4 reveals a mismatch between the exploration profiles required for near-optimality on ΞK,A _K,A and ΞK,B _K,B in the regime K−A≤B≪K-A≤ B K. To illustrate this mismatch, suppose for simplicity that B divides K, and partition the arms of θ into K/BK/B groups of size B, treating each group as a super-arm. We compare the exploration levels that algorithms A Alg_A and B Alg_B, near-optimal on their respective instance classes, can attain with high probability on each fixed super-arm. For B Alg_B, we can prove that for every fixed ⊆U with ||=B|U|=B, there is a threshold mB=Ω~(TBK), such that N(T)≥mB, m_B= ( TBK ), such that N_U(T)≥ m_B, with high probability under θ. Thus, at the level of super-arms, B Alg_B must explore relatively uniformly: each fixed super-arm receives at least Ω~(TB/K) (TB/K) pulls with high probability22 2 See Appendix C.3 for the formal statement and proof.. In contrast, for A Alg_A, inequality (6.2) implies that one can choose a threshold mA=O~(TB2K2), for which, ℙθ,A[N(T)≥mA]≤1/2, m_A= O ( TB^2K^2 ), for which, P_θ, Alg_A[N_U(T)≥ m_A]≤ 1/2, provided this threshold lies within the horizon. Consequently, A Alg_A cannot ensure more than O~(TB2/K2) O(TB^2/K^2) pulls of any fixed super-arm with high probability. When B≪KB K, this scale is smaller than the exploration level required of B Alg_B, up to logarithmic factors. This incompatibility yields the desired non-adaptivity result: the exploration profile imposed by near-optimality on ΞK,A _K,A precludes the exploration needed to handle the hardest instances in ΞK,B _K,B. Remark 6.5. Lemma 6.4 shows that, when A is close to K, near-optimal algorithms must exhibit non-uniform exploration behavior, consistent with the sub-sampling approach in Section 4. A more precise characterization of “sub-sampling-like” behavior, and whether such behavior is necessary for near-optimality, remains an interesting direction for future work. Formally, we begin with any fixed ⊆U such that ||=B|U|=B, Lemma 6.4 shows that only an exploration of level O~(TB2/K2) O(TB^2/K^2) is guaranteed. Therefore, taking m=Θ~(TB2/K2)m= (TB^2/K^2) with properly selected constants, we can ensure that ℙθ[N(T)≥m]≲O~(BKTm)<1−Ω(1). _θ [N_U(T)≥ m ] O ( BK Tm )<1- (1). On the other side, an exploration of level O~(TB2/K2) O(TB^2/K^2) is not sufficient for identifying hard-enough instance. Particularly, we consider the instance ν with reward function rν(a)=1/2+Δ,a∈1/2,a∈∁, r_ν(a)= cases1/2+ ,&a \\ 1/2,&a cases, where Δ=Θ~(1/m) = (1/ m). Once again, under the event N(T)≤m\N_U(T)≤ m\, algorithm allocates only at most m to U, leading to (ℙθ∥ℙν)=O(1) KL (P_θ\|P_ν )=O(1), therefore the learner are not able to reliably distinguish θ and ν in this case. Formally, under the event N(T)≤m\N_U(T)≤ m\, the distribution of ℙνP_ν and ℙθP_θ is close enough, so change of measure is at a cost of only multiplicative constant: ℙν[N(T)≥m]≲ℙθ[N(T)≥m]<1−Ω(1). _ν [N_U(T)≥ m ] _θ [N_U(T)≥ m ]<1- (1). Recall that on ν, the regret is given by Δ(T−ν[N(T)]) (T-E_ν[N_U(T)] ), therefore, Regretν(T)≥ℙν[N(T)≤m](T−m)Δ=Ω(TΔ)=Ω~(KBT), _ν(T) _ν [N_U(T)≤ m ](T-m) = (T )= ( KB T ), where the last inequality holds due to Δ=Θ~(1/m)=Θ(K/(BT)) = (1/ m)= (K/(B T)). This gives the desired rate and finishes the proof. 7 Conclusion In this paper, we study regret minimization in K-armed bandits with A optimal arms. We first provide a sharper analysis of the previous sub-sampling algorithm and lower bounds for the problem. These results together establishes a Θ~(K−AKAT) ( K-A KA T ) minimax regret. We also show that near-optimality imposes exploration constraints that prevent uniform adaptation across sufficiently many different models with distinct numbers of optimal arms. Directions for future work include closing the remaining logarithmic gaps, designing Pareto optimal algorithms and determining which aspects of the exploration behavior induced by sub-sampling are necessary for minimax optimality. Appendix A Proofs of Theorems in Section 4 A.1 Proof of Theorem 4.1 Proof of Theorem 4.1. Let ℰmiss=ℬ∩opt=∅E_miss=\B∩A^opt= \ be the event that the randomly sampled subset does not contain any optimal arms, and ℰsub=ℬ∩sub≠∅∩ℬ∩opt≠∅E_sub=\B∩A^sub≠ \∩\B∩A^opt≠ \ be the event that the randomly sampled subset contains at least one sub-optimal arm and at least one optimal arm. We first bound the probability of ℰmissE_miss. First, if L=K−A+1L=K-A+1 then every subset of L arms must contain at least one optimal arm, since there are only K−AK-A suboptimal arms. Therefore, ℙ[ℰmiss]=0P[E_miss]=0. Otherwise, if A≤K/2A≤ K/2, we directly have L≤⌈log(2T)log(K/(K−A))⌉. L≤ (2T) (K/(K-A)) . In the complement case A>K/2A>K/2, we also have L=⌈log2T+1⌉≤⌈log(2T)log2⌉≤⌈log(2T)log(K/(K−A))⌉. L= _2T+1 ≤ (2T) 2 ≤ (2T) (K/(K-A)) . Since ℬB is sampled uniformly without replacement, we have ℙ[ℰmiss]=(K−AL)(KL)−1=∏i=0L−1K−A−iK−i≤(K−AK)L, [E_miss]= K-AL KL^-1= _i=0^L-1 K-A-iK-i≤ ( K-AK )^L, where the inequality holds due to (K−A−i)/(K−i)≤(K−A)/K(K-A-i)/(K-i)≤(K-A)/K for every i∈0,…,L−1i∈0,…,L-1. Plugging in the value of L, we see that ℙ[ℰmiss]≤(K−AK)L=exp(−Llog(K−A))≤exp(−log(2T))=12T. [E_miss]≤ ( K-AK )^L= (-L ( KK-A ) )≤ (- (2T) )= 12T. Combining the two cases gives ℙ[ℰmiss]≤(2T)−1P[E_miss]≤(2T)^-1. We then bound the probability of event ℰsub∪ℰmissE_sub∪E_miss. Trivially, we have ℙ[ℰsub∪ℰmiss]≤1P[E_sub∪E_miss]≤ 1. Moreover, by the fact that ℰsub∪ℰmiss=⋃a∈suba∈ℬE_sub∪E_miss= _a∈A^sub\a \ ℙ[ℰsub∪ℰmiss]≤∑a∈subℙ[a∈ℬ]≤L(K−A)K, [E_sub∪E_miss]≤ _a∈A^subP [\a \ ]≤ L(K-A)K, which gives ℙ[ℰsub∪ℰmiss]≤1∧L(K−A)K−1P[E_sub∪E_miss]≤ 1 L(K-A)K^-1 Now we are ready to bound the regret. On the event ℰopt≔(ℰmiss∪ℰsub)∁E_opt (E_miss∪E_sub ) , ℬ⊆optB A^opt, therefore no regret is incurred. On the event ℰsubE_sub, the restricted bandit instance over ℬB contains at least one globally optimal arm. Thus, the best mean reward among the arms in ℬB equals r∗r^*. By the minimax regret guarantee of MOSS, there exists a universal constant C>0C>0 such that Regretℬ(T)≤CLT. _B(T)≤ C LT. for every realization of ℬB satisfying ℰsubE_sub and T≥KT≥ K (see e.g., Lattimore and Szepesvári, 2020, Theorem 9.1 for a proof). Finally, On the event ℰmissE_miss, the per-round regret is at most 11, since all mean rewards belong to [0,1][0,1]. Therefore, the total regret is at most T. Combining the analysis gives that Regret(T) (T) =[Regret(T)(ℰopt)]+[Regret(T)(ℰsub)]+[Regret(T)(ℰmiss)] =E [Regret(T) (E_opt ) ]+E [Regret(T) (E_sub) ]+E [Regret(T) (E_miss) ] ≤CLTℙ[ℰsub∪ℰmiss]+Tℙ[ℰmiss] ≤ C LTP[E_sub∪E_miss]+TP[E_miss] ≤CLT(L(K−A)K∧1)+12. ≤ C LT ( L(K-A)K 1 )+ 12. It remains to bound L. Using the elementary inequality −log(1−x)≥x- (1-x)≥ x for all x∈[0,1)x∈[0,1), we obtain log(K/(K−A))=−log(1−A/K)≥A/K (K/(K-A))=- (1-A/K)≥ A/K, therefore L≤⌈log(2T)log(K/(K−A))⌉≤1+log(2T)log(K/(K−A))≤1+KAlog(2T)=O~(KA), L≤ (2T) (K/(K-A) ) ≤ 1+ (2T) (K/(K-A) )≤ 1+ KA (2T)= O ( KA ), where the first inequality holds due to ⌈x⌉≤x+1 x ≤ x+1. Substituting this inequality into the preceding regret bound yields Regret(T)=O~(((K−A)A∧1)KTA+12)=O~(K−AKAT). (T)= O ( ( (K-A)A 1 ) KTA+ 12 )= O ( K-A KA T ). Since this bound is achieved by a valid algorithm uniformly over all instances with exactly A optimal arms, the claimed minimax upper bound follows. ∎ Appendix B Proofs of Theorems in Section 5 B.1 Proof of Theorem 5.1 Proof of Theorem 5.1. The hard instance construction largely follows Theorem 15.2 of Lattimore and Szepesvári (2020) and a similar idea was also presented in De Heide et al. (2021). For simplicity, we define N(T):=∑a∈Na(T)N_S(T):= _a∈SN_a(T) for subset ⊆S . For any algorithm Alg, we fix an arbitrary subset 0⊆S_0 such that |0|=A|S_0|=A. For a parameter Δ∈(0,1/2] ∈(0,1/2] to be specified later, define the first bandit instance ν0 _0 by r0(a):=Δ,a∈0,0,a∈0∁. r_0(a):= cases ,&a∈S_0,\\ 0,&a∈S_0 . cases Thus, ν0 _0 has exactly A optimal arms, namely the arms in 0S_0. Let ℙ0P_0 and 0E_0 denote probability and expectation under ν0 _0 and Alg. Since ∑a∈0∁0[Na(T)]≤T _a∈S_0 E_0[N_a(T)]≤ T, there exists a subset 1⊆0∁S_1 S_0 with |1|=A|S_1|=A such that 0[N1(T)]≤ATK−A. _0[N_S_1(T)]≤ ATK-A. (B.1) Indeed, one may choose 1S_1 to consist of the A least-sampled arms in 0∁S_0 . Such a subset exists because A≤K/4A≤ K/4, and hence A<K−A<K-A. We now define a second bandit instance ν1 _1 by r1(a):=2Δ,a∈1,Δ,a∈0,0,a∈(0∪1)∁. r_1(a):= cases2 ,&a∈S_1,\\ ,&a∈S_0,\\ 0,&a∈(S_0∪S_1) . cases The instance ν1 _1 also has exactly A optimal arms, namely the arms in 1S_1. Similarly, we use ℙ1P_1 and 1E_1 to denote probability and expectation under ν1 _1 and Alg, and let Regreti(T)Regret_i(T) denote the expected regret under νi _i. Now we consider the event ℰ:=N1(T)≥T/2E:= \N_S_1(T)≥ T/2 \. Under ν0 _0, every arm in 1S_1 is suboptimal with gap Δ . Consequently, Regret0(T) _0(T) ≥Δ0[N1(T)]≥ΔT2ℙ0[ℰ]. ≥ _0[N_S_1(T)]≥ T2P_0[E]. Under ν1 _1, every arm outside 1S_1 has suboptimality gap at least Δ . Therefore, Regret1(T)≥Δ1[T−N1(T)]≥ΔT2ℙ1[ℰ∁]. _1(T)≥ _1[T-N_S_1(T)]≥ T2P_1 [E ]. Combining the preceding two inequalities gives Regret0(T)+Regret1(T)≥ΔT2(ℙ0[ℰ]+ℙ1[ℰ∁]). _0(T)+Regret_1(T)≥ T2 (P_0[E]+P_1[E ] ). (B.2) It remains to bound the right-hand-side of (B.2). First, by Lemma E.4 ℙ0[ℰ]+ℙ1[ℰ∁]≥12exp(−KL(ℙ0∥ℙ1)) _0[E]+P_1[E ]≥ 12 (-KL(P_0\|P_1) ) Since the two instances differ only on the arms in 1S_1. For every a∈1a∈S_1, the reward distribution is (0,1)N(0,1) under ν0 _0 and (2Δ,1)N(2 ,1) under ν1 _1. Using the chain rule for KL divergence under adaptive sampling (Lattimore and Szepesvári, 2020, Lemma 15.1), KL(ℙ0∥ℙ1)=∑a∈10[Na(T)]KL((0,1)∥(2Δ,1))=2Δ20[N1(T)]≤2Δ2ATK−A, (P_0\|P_1)= _a∈S_1E_0[N_a(T)]KL (N(0,1)\|N(2 ,1) )=2 ^2E_0[N_S_1(T)]≤ 2 ^2ATK-A, where the last inequality follows from (B.1). Now we choose Δ=14(K−A)(AT)−1 = 14 (K-A)(AT)^-1, which gives KL(ℙ0∥ℙ1)≤18KL(P_0\|P_1)≤ 18. As a result, ℙ0[ℰ]+ℙ1[ℰ∁]≥exp(−1/8)/2P_0[E]+P_1[E ]≥ (-1/8)/2. Substituting this inequality into (B.2) and taking the max over ν0 _0 and ν1 _1 gives maxν0,ν1Regret(T)≥e−1/88ΔT=Ω((K−A)TA)=Ω(KTA), _ _0, _1Regret(T)≥ e^-1/88 T= ( (K-A)TA )= ( KTA ), which finishes the proof. ∎ B.2 Proof of Theorem 5.2 To prove Theorem 5.2, we need the following change-of-measure argument. Proposition B.1. Let (Ω,)( ,G) be a measurable space, and let ℙP and ℚQ be probability measures on (Ω,)( ,G) satisfying ℙ≪ℚP . Define the log-likelihood ratio L=log(dℙ/dℚ)L= (\,dP/\,\,dQ). Then, for every G-measurable random variable X:Ω→[0,b]X: →[0,b] and every γ∈ℝγ , ℙ[X]≤eγℚ[X]+bℙ[L>γ]. _P[X]≤ e^γE_Q[X]+bP[L>γ]. (B.3) Equivalently, ℚ[X]≥e−γ[ℙ[X]−bℙ(L>γ)]. _Q[X]≥ e^-γ [E_P[X]-bP(L>γ) ]. (B.4) Proof of Proposition B.1. Decompose the expectation according to whether the log-likelihood ratio exceeds γ: ℙ[X] _P[X] =ℙ[XL≤γ]+ℙ[XL>γ]. =E_P [X1\L≤γ\ ]+E_P [X1\L>γ\ ]. For the first term, the change-of-measure identity gives ℙ[XL≤γ]=ℚ[XeLL≤γ]≤eγℚ[XL≤γ]≤eγℚ[X], _P [X1\L≤γ\ ]=E_Q [Xe^L1\L≤γ\ ]≤ e^γE_Q [X1\L≤γ\ ]≤ e^γE_Q[X], where the last inequality follows from X≥0X≥ 0. For the second term, since X≤bX≤ b, ℙ[XL>γ]≤bℙ(L>γ). _P [X1\L>γ\ ]≤ bP(L>γ). Combining the two bounds yields ℙ[X]≤eγℚ[X]+bℙ(L>γ), _P[X]≤ e^γE_Q[X]+bP(L>γ), which finishes the proof. ∎ Remark B.2. When specializing to X=ℰX= \E\, where ℰ∈E is any measurable event, Proposition B.1 reduces to ℙ(ℰ)≤eγℚ(ℰ)+ℙ[L>γ]P(E)≤ e^γQ(E)+P[L>γ]. This change-of-measure inequality, in its event-based form, was first introduced for establishing instance-dependent lower bounds (Degenne and Koolen, 2019; Garivier and Kaufmann, 2021), as an modification to the previous KL-contraction-based technique (Garivier and Kaufmann, 2016; Garivier et al., 2019). Recently, Ji et al. (2026) adopted this change-of-measure technique, together with subsequent combinatorial arguments, to prove the worst case lower bound in offline MABs with multiple optimal arms. Next we investigate the specific form of the likelihood ratio between two bandits μ and λ with Gaussian reward noise. Proposition B.3 (Log-likelihood ratio for Gaussian bandits). Fix a bandit algorithm and two bandit instance μ and λ with mean vectors ,∈ℝK λ, μ ^K. Define the filtration ℱ0:=∅,Ω,ℱt:=σ(a1,r1,…,at,rt),t∈[T], _0:=\ , \, _t:=σ(a_1,r_1,…,a_t,r_t), t∈[T], t+1:=σ(ℱt,at+1),t=0,…,T−1. _t+1:=σ(F_t,a_t+1), t=0,…,T-1. Then we see that, under the instance λ, rt|t∼(λat,1)r_t _t ( _a_t,1). Let ℙλP_λ and ℙμP_μ denote the trajectory distributions induced by the same algorithm under λ and μ, respectively. For every stopping time τ≤Tτ≤ T, define ℙλτ:=ℙλ|ℱτ,ℙμτ:=ℙμ|ℱτ. _λ^τ:=P_λ|_F_τ, _μ^τ:=P_μ|_F_τ. Then the log-likelihood ratio between the two stopped trajectory distributions satisfies Lλ,μ(τ) L_λ,μ(τ) :=logdℙλτdℙμτ=∑t=1τ[(λat−μat)(rt−λat)+12(λat−μat)2]. := \,dP_λ^τ\,dP_μ^τ= _t=1^τ [( _a_t- _a_t)(r_t- _a_t)+ 12( _a_t- _a_t)^2 ]. (B.5) Proof. For every t∈[T]t∈[T], let πt(⋅∣ht−1) _t(· h_t-1) denote the conditional distribution used by the algorithm to select ata_t given the history ht−1=(a1,r1,…,at−1,rt−1)h_t-1=(a_1,r_1,…,a_t-1,r_t-1). Since the same algorithm is used under both instances, the action-selection kernel πt _t is identical under ℙλP_λ and ℙμP_μ. In particular, it does not depend on the underlying bandit instance. Let ϕ(x):=(2π)−1exp(−x2/2)φ(x):=( 2π)^-1 (-x^2/2) denote the standard Gaussian density. Fix any deterministic n∈[T]n∈[T]. With respect to the product of the counting measure on actions and the Lebesgue measure on rewards, the density of the trajectory up to time n under λ and μ are pλ(hn)=∏t=1nπt(at∣ht−1)ϕ(rt−λat), p_λ(h_n)= _t=1^n _t(a_t h_t-1)φ(r_t- _a_t), pμ(hn)=∏t=1nπt(at∣ht−1)ϕ(rt−μat). p_μ(h_n)= _t=1^n _t(a_t h_t-1)φ(r_t- _a_t). Therefore, the action-selection probabilities cancel, and we obtain d(ℙλ|ℱn)d(ℙμ|ℱn) \,d (P_λ|_F_n )\,d (P_μ|_F_n ) =∏t=1nϕ(rt−λat)ϕ(rt−μat). = _t=1^n φ(r_t- _a_t)φ(r_t- _a_t). (B.6) Define the likelihood-ratio process Zn=dℙλ|ℱn/dℙμ|ℱnZ_n=\,dP_λ|_F_n/\,dP_μ|_F_n for all n∈[T]n∈[T], and set Z0:=1Z_0:=1. We next show that ZτZ_τ is the Radon–Nikodym derivative between the two trajectory distributions restricted to ℱτF_τ. Indeed, for every event E∈ℱτE _τ, we have μ[ZτE]=∑n=0Tμ[ZnE∩τ=n]=∑n=0Tℙλ(E∩τ=n)=ℙλ(E), _μ [Z_τ \E\ ]= _n=0^TE_μ [Z_n \E∩\τ=n\\ ]= _n=0^TP_λ (E∩\τ=n\ )=P_λ(E), where the second equality follows because E∩τ=n∈ℱnE∩\τ=n\ _n. Consequently, Zτ=dℙλτ/dℙμτZ_τ=\,dP_λ^τ/\,dP_μ^τ. It remains to compute the logarithm of ZτZ_τ. For every t∈[T]t∈[T], logϕ(rt−λat)ϕ(rt−μat)=12[(rt−μat)2−(rt−λat)2]=(λat−μat)(rt−λat)+12(λat−μat)2. φ(r_t- _a_t)φ(r_t- _a_t)= 12 [(r_t- _a_t)^2-(r_t- _a_t)^2 ]=( _a_t- _a_t)(r_t- _a_t)+ 12( _a_t- _a_t)^2. Taking the logarithm of (B.6) and evaluating the resulting likelihood-ratio process at τ therefore gives Lλ,μ(τ)=logdℙλτdℙμτ=∑t=1τ[(λat−μat)(rt−λat)+12(λat−μat)2], L_λ,μ(τ)= \,dP_λ^τ\,dP_μ^τ= _t=1^τ [( _a_t- _a_t)(r_t- _a_t)+ 12( _a_t- _a_t)^2 ], which proves the proposition. ∎ Now we are ready to prove Theorem 5.2. Proof of Theorem 5.2. The hard instance construction is inspired by Exercise 15.2 of Lattimore and Szepesvári (2020). We consider the multi-armed bandit class parameterized by mean vectors: μ∈A:=∈12,12−ΔK|∑i=1K(μi=1/2)=A, μ _A:= \ μ∈ \ 12, 12- \^K | _i=1^K ( _i=1/2)=A \, where Δ>0 >0 is a parameter to be determined later. We further consider an auxiliary instance θ such that =(1/2,⋯,1/2)⊤∈ℝK θ=(1/2,·s,1/2) ^K, and let =A∪θV=V_A∪\θ\. Unless stated otherwise, we assume that noise of rewards is standard Gaussian. For any μ∈μ , the corresponding instance is given by ([K],rμ,T)([K],r_μ,T) where the reward is given by rμ(i)=μir_μ(i)= _i. For any μ∈Aμ _A, we use opt(μ)A^opt(μ) to denote the set of optimal actions (those with reward 1/21/2) and sub(μ)A^sub(μ) to denote the set of sub-optimal arms. Our goal is to show that, for any algorithm Alg, there exists μ∈Aμ _A such that that Regretμ,(T)=Ω~(K−AKT). _μ, Alg(T)= ( K-AK T ). In the subsequent proof, we will drop the subscript of Alg when there is no ambiguity. Now we consider any μ∈Aμ _A and its difference between θ, in terms of the distribution of induced trajectories. Consider the random variable Xμ=∑a∈sub(μ)Na(T)X_μ= _a∈A^sub(μ)N_a(T), then we know that Regretμ(T)=μ[Xμ]Δ. _μ(T)=E_μ[X_μ] . On the other side, since Xμ≤TX_μ≤ T, Proposition B.1 tells us that for any γ>0γ>0, μ[Xμ]≥e−γ[θ[Xμ]−Tℙθ(logdℙθdℙμ>γ)]. _μ[X_μ]≥ e^-γ [E_θ[X_μ]-TP_θ ( \,dP_θ\,dP_μ>γ ) ]. (B.7) To lower bound the right hand side, we need to properly choose the threshold γ, which requires the computation of log(dℙθ/dℙμ) (\,dP_θ/\,dP_μ). Applying Proposition B.3 with τ=Tτ=T gives that logdℙθdℙμ \,dP_θ\,dP_μ =∑t=1T[(θat−μat)(rt−θat)+12(θat−μat)2] = _t=1^T [( _a_t- _a_t)(r_t- _a_t)+ 12( _a_t- _a_t)^2 ] =12∑a∈sub(μ)Na(T)(θa−μa)2⏟I1+∑t=1T(rt−12)Δat∈sub(μ)⏟I2, = 12 _a∈A^sub(μ)N_a(T)( _a- _a)^2_I_1+ _t=1^T (r_t- 12 ) \a_t∈A^sub(μ)\_I_2, Since ∑a∈sub(μ)Na(T)≤T _a∈A^sub(μ)N_a(T)≤ T, we know that I1≤TΔ2/2I_1≤ T ^2/2. For the second term, we consider Mt=∑s=1t(rs−12)Δℰs(μ),Vt=∑s=1tΔ2ℰs(μ), where ℰs(μ)=as∈sub(μ) M_t= _s=1^t (r_s- 12 ) \E_s(μ)\, V_t= _s=1^t ^2 \E_s(μ)\, where E_s(μ)=\a_s∈A^sub(μ)\ We further define Zt=exp(λMt−λ2Vt2),t=0,1,…,T. Z_t= (λ M_t- λ^2V_t2 ), t=0,1,…,T. Then under the probability distribution ℙθP_θ, we see that for any λ∈ℝλ , θ[Zt|ℱt−1]=Zt−1θ[exp(λ(rt−1/2)Δℰt(μ)−λ2Δ2ℰt(μ)2)⏟(⋆)|ℱt−1] _θ[Z_t|F_t-1]=Z_t-1E_θ [ (λ(r_t-1/2) \E_t(μ)\- λ^2 ^2 \E_t(μ)\2 )_( ) |F_t-1 ] For (⋆)( ), we first take expectation on tG_t, which gives that θ[(⋆)|t] _θ[( )|G_t] =1−ℰt(μ)+ℰt(μ)θ[exp(λ(rt−1/2)Δ−λ2Δ22)|t] =1- \E_t(μ)\+ \E_t(μ)\E_θ [ (λ(r_t-1/2) - λ^2 ^22 ) |G_t ] ≤1−ℰt(μ)+ℰt(μ) ≤ 1- \E_t(μ)\+ \E_t(μ)\ =1, =1, where the inequality holds due to that rt−1/2r_t-1/2 is 11-sub-gaussian conditioned on tG_t on ℙθP_θ. This immediately gives θ[(⋆)|ℱt−1]≤1E_θ[( )|F_t-1]≤ 1, verifying that ZtZ_t is a super-martingale for any λ. Now invoking Lemma E.1 with τ=Tτ=T, since I2=MTI_2=M_T, we see that for any β>0β>0, ℙθ(I2≥β)≤exp(−β22TΔ2). _θ(I_2≥β)≤ (- β^22T ^2 ). Now combining the estimation of I1I_1 and I2I_2 and set β=2ΔTlogKβ=2 T K, and γ=β+TΔ2/2γ=β+T ^2/2, we obtain that ℙθ(logdℙθdℙμ>γ)≤exp(−β22TΔ2)=1K2. _θ ( \,dP_θ\,dP_μ>γ )≤ (- β^22T ^2 )= 1K^2. Plugging into (B.7), we see that μ[Xμ] _μ[X_μ] ≥exp(−β−TΔ22)[θ[Xμ]−Tℙθ(logdℙθdℙμ>γ)] ≥ (-β- T ^22 ) [E_θ[X_μ]-TP_θ ( \,dP_θ\,dP_μ>γ ) ] ≥exp(−β−TΔ22)[θ[Xμ]−TK2]. ≥ (-β- T ^22 ) [E_θ[X_μ]- TK^2 ]. Now we sum up over all μ∈Aμ _A and obtains that ∑μ∈Aμ[Xμ] _μ _AE_μ[X_μ] ≥exp(−β−TΔ22)(∑μ∈Aθ[Xμ]−∑μ∈ATK2) ≥ (-β- T ^22 ) ( _μ _AE_θ[X_μ]- _μ _A TK^2 ) =exp(−β−TΔ22)(∑μ∈A∑a∈sub(μ)θ[Na(T)]−(K−A)TK2) = (-β- T ^22 ) ( _μ _A _a∈A^sub(μ)E_θ[N_a(T)]- KK-A TK^2 ) =exp(−β−TΔ22)(∑a∈∑μ:a∈sub(μ)θ[Na(T)]−(K−A)TK2) = (-β- T ^22 ) ( _a _μ:a∈A^sub(μ)E_θ[N_a(T)]- KK-A TK^2 ) =exp(−β−TΔ22)(T(K−1K−A−1)−(K−A)TK2), = (-β- T ^22 ) (T K-1K-A-1- KK-A TK^2 ), where the second equation is given by |A|=(K−A)|V_A|= KK-A and the last equation holds due to ∑a∈Na(T)=T _a N_a(T)=T and |μ:a∈sub(μ)|=(K−1K−A−1)|\μ:a∈A^sub(μ)\|= K-1K-A-1. Now take maximum over all μ∈Aμ _A and leverage the fact that maximum is larger that average, we see that supμ∈Aμ[Xμ] _μ _AE_μ[X_μ] ≥Texp(−β−TΔ22)[(K−A)−1(K−1K−A−1)−1K2] ≥ T (-β- T ^22 ) [ KK-A^-1 K-1K-A-1- 1K^2 ] ≥Texp(−β−TΔ22)(K−AK−1K2) ≥ T (-β- T ^22 ) ( K-AK- 1K^2 ) ≥(K−A)T2Kexp(−β−TΔ22). ≥ (K-A)T2K (-β- T ^22 ). Recall that Regretμ(T)=μ[Xμ]ΔRegret_μ(T)=E_μ[X_μ] , we see supμ∈ARegretμ(T)≥(K−A)TΔ2Kexp(−β−TΔ22). _μ _ARegret_μ(T)≥ (K-A)T 2K (-β- T ^22 ). Finally, recall that β=2ΔTlogKβ=2 T K. Now we select Δ=(TlogK)−1 = (T K)^-1, we see that β=2β=2 and γ=2+(2logK)−1≤3γ=2+(2 K)^-1≤ 3. This leads to supμ∈ARegretμ(T)≳(K−A)TKTlogK=Ω~(K−AKT), _μ _ARegret_μ(T) (K-A)TK T K= ( K-AK T ), for any algorithm Alg, which finishes the proof. ∎ Appendix C Proofs of Theorems in Section 6 C.1 Formal Version and Proof of Lemma 6.4 In this section, we provide the formal version of Lemma 6.4 and the proof of it. Lemma C.1. For some 1≤A<K1≤ A<K, consider an algorithm Alg satisfying supν:|opt(ν)|=ARegretν,(T)≤ΓK−AKT _ν:\,|A^opt(ν)|=ARegret_ν, Alg(T)≤ K-AK T for some Γ≥1 ≥ 1. Let θ denote the all-equal instance, then, for every m∈[T]m∈[T] and every ℓ≥1 ≥ 1, max⊆:||=K−Aℙθ[N(T)≥m] _S :\,|S|=K-AP_θ [N_S(T)≥ m ] ≥K−AK−exp(−ℓ)−8ΓK−AKmℓT ≥ K-AK- (- )-8 K-AK m T max⊆:||=K−Aℙθ[N(T)≥m] _S :\,|S|=K-AP_θ [N_S(T)≥ m ] ≤exp(−ℓ)+8ΓK−AKTℓm. ≤ (- )+8 K-AK T m. Proof of Lemma C.1. Fix any m∈[T]m∈[T] and ℓ≥1 ≥ 1, and for simplicity we write q(m):=max⊆:||=K−Aℙθ(N(T)≥m). q_ Alg(m):= _S :\,|S|=K-AP_θ (N_S(T)≥ m ). Recall that θ is the all-equal instance with mean vector =/2 θ=1/2. For every subset ⊆S with ||=K−A|S|=K-A, construct an alternative Gaussian bandit instance ν _S with mean vector ν_S given by ν,a:=1/2−Δ,a∈,1/2,a∉,Δ:=14mℓ. _S,a:= cases1/2- ,&a∈S,\\ 1/2,&a∉S, cases := 14 m . Since ||=K−A|S|=K-A, the instance ν _S has exactly A optimal arms. Moreover, Δ≤1/4 ≤ 1/4, so all its reward means belong to [0,1][0,1]. We show that, whenever the algorithm pulls only m or fewer than m times on the set S, it cannot reliably distinguish θ and ν _S. To show this, for a fixed S, we define the stopping time τ _S at which the pull count on S is exactly m H:=N(T)≥m,τ:=inft∈[T]:N(t)=m∧T. H_S:=\N_S(T)≥ m\, _S:= \t∈[T]:N_S(t)=m\ T. Then τ _S is a bounded (ℱt)t=0T(F_t)_t=0^T-stopping time, and H=N(τ)=m∈ℱτ. H_S=\N_S( _S)=m\ _ _S. (C.1) Now we show that, up to the stopping time τ _S, the distribution given by θ and ν _S is close. We once again characterize this closeness via the log-likelihood ratio. In particular, consider the trajectory distributions restricted to ℱτF_ _S by ℙθτ:=ℙθ|ℱτP_θ _S:=P_θ|_F_ _S and ℙντ:=ℙν|ℱτP_ _S _S:=P_ _S|_F_ _S. Applying Proposition B.3 gives that logdℙθτdℙντ \,dP_θ _S\,dP_ _S _S =∑t=1τ[(θat−ν,at)(rt−θat)+12(θat−ν,at)2] = _t=1 _S [( _a_t- _S,a_t)(r_t- _a_t)+ 12( _a_t- _S,a_t)^2 ] =Δ∑t=1τat∈(rt−1/2)+Δ22N(τ). = _t=1 _S \a_t∈S\(r_t-1/2)+ ^22N_S( _S). Now we denote Mt=Δ∑s=1tas∈(rs−1/2)M_t= _s=1^t \a_s∈S\(r_s-1/2) and Vt=Δ2N(t)V_t= ^2N_S(t) , then under the probability distribution ℙθP_θ, we see that for any λ∈ℝλ , θ[exp(λMt−λ2Vt2)|ℱt−1] _θ [ (λ M_t- λ^2V_t2 ) |F_t-1 ] =exp(λMt−1−λ2Vt−12)θ[exp(λ(rt−1/2)Δat∈−λ2Δ2at∈2)⏟(⋆)|ℱt−1] = (λ M_t-1- λ^2V_t-12 )E_θ [ (λ(r_t-1/2) \a_t∈S\- λ^2 ^2 \a_t∈S\2 )_( ) |F_t-1 ] For (⋆)( ), we first take expectation on tG_t, which gives that θ[(⋆)|t] _θ[( )|G_t] =1−at∈+at∈θ[exp(λ(rt−1/2)Δ−λ2Δ22)|t] =1- \a_t∈S\+ \a_t∈S\E_θ [ (λ(r_t-1/2) - λ^2 ^22 ) |G_t ] ≤1−at∈+at∈ ≤ 1- \a_t∈S\+ \a_t∈S\ =1, =1, where the inequality holds due to that rt−1/2r_t-1/2 is 11-sub-gaussian conditioned on tG_t on ℙθP_θ. This immediately gives θ[(⋆)|ℱt−1]≤1E_θ[( )|F_t-1]≤ 1, verifying that exp(λMt−λ2Vt/2) (λ M_t-λ^2V_t/2) is a super-martingale for any λ. Now invoking Lemma E.1 with x=Δ2mℓx= 2m , since Vτ≤mΔ2V_τ≤ m ^2, we have ℙθ(Mτ≥Δ2mℓ)≤exp(−2mΔ2ℓ2mΔ2)=exp(−ℓ). _θ (M_τ≥ 2m )≤ (- 2m ^2 2m ^2 )= (- ). Since Δ2N(τ)/2≤mΔ2/2 ^2N_S( _S)/2≤ m ^2/2, this immediately leads to ℙ(logdℙθτdℙντ≥Δ2mℓ+mΔ2/2)≤exp(−ℓ). ( \,dP_θ _S\,dP_ _S _S≥ 2m +m ^2/2 )≤ (- ). Recall that Δ=(4mℓ)−1 =(4 m )^-1, this means that Δ2mℓ+mΔ2/2=1/22+1/32ℓ<log2 2m +m ^2/2=1/2 2+1/32 < 2 since ℓ≥1 ≥ 1 ℙ(logdℙθτdℙντ>log2)≤exp(−ℓ). ( \,dP_θ _S\,dP_ _S _S> 2 )≤ (- ). (C.2) We now prove the upper bound on q(m)q_ Alg(m). Fix any ⊆S with ||=K−A|S|=K-A. Since H∈ℱτH_S _ _S, we may apply Proposition B.1 on the measurable space (Ω,ℱτ)( ,F_ _S) with ℙ=ℙθτP=P_θ _S, ℚ=ℙντQ=P_ _S _S, X=HX= \H_S\, b=1b=1 and γ=log2γ= 2. Using (C.2), we obtain ℙν(H)≥12[ℙθ(H)−ℙθ(L>log2)]≥12[ℙθ(H)−exp(−ℓ)]. _ _S(H_S)≥ 12 [P_θ(H_S)-P_θ(L_S> 2) ]≥ 12 [P_θ(H_S)- (- ) ]. (C.3) Every arm in S is suboptimal under ν _S with gap Δ . Hence, the assumed regret guarantee gives ΓK−AKT≥Regretν,(T)=Δν[N(T)] K-AK T _ _S, Alg(T)= _ _S[N_S(T)] ≥Δmℙν(H)≥Δm2[ℙθ(H)−exp(−ℓ)]. ≥ mP_ _S(H_S)≥ m2 [P_θ(H_S)- (- ) ]. Rearranging and substituting Δ=(4mℓ)−1 =(4 m )^-1 yields ℙθ(N(T)≥m)≤exp(−ℓ)+2Γ(K−A)TKΔm=exp(−ℓ)+8ΓK−AKTℓm. _θ (N_S(T)≥ m )≤ (- )+ 2 (K-A) TK m= (- )+8 K-AK T m. Since this holds for every ||=K−A|S|=K-A, taking maximum over all ||=K−A|S|=K-A gives the desired upper bound q(m)≤exp(−ℓ)+8ΓK−AKTℓm. q_ Alg(m)≤ (- )+8 K-AK T m. (C.4) We next prove the lower bound on q(m)q_ Alg(m). For every ⊆S with ||=K−A|S|=K-A, define Y=N(T)N(T)<m=N(T)H∁Y_S=N_S(T) \N_S(T)<m\=N_S(T) \H_S \. On H∁H_S , the stopping time satisfies τ=T _S=T, whereas on H_S both sides below vanish. Therefore, Y=N(τ)H∁Y_S=N_S( _S) \H_S \. In particular, Y_S is ℱτF_ _S-measurable and takes values in [0,T][0,T]. Once again, applying Proposition B.1 once more on (Ω,ℱτ)( ,F_ _S), now with ℙ=ℙθτP=P_θ _S, ℚ=ℙντQ=P_ _S _S, X=YX=Y_S, b=Tb=T and γ=log2γ= 2, and using (C.2), gives ν[Y]≥12[θ[Y]−Tℙθ(L>log2)]≥12[θ[Y]−Texp(−ℓ)]. _ _S[Y_S]≥ 12 [E_θ[Y_S]-TP_θ(L_S> 2) ]≥ 12 [E_θ[Y_S]-T (- ) ]. Since Y≤N(T)Y_S≤ N_S(T), we have ν[N(T)]≥ν[Y]≥12[θ[N(T)H∁]−Texp(−ℓ)]. _ _S[N_S(T)] _ _S[Y_S]≥ 12 [E_θ [N_S(T) \H_S \ ]-T (- ) ]. Moreover, as ℙθ(H)≤q(m)P_θ(H_S)≤ q_ Alg(m), it follows that ν[N(T)] _ _S[N_S(T)] ≥12[θ[N(T)H∁]−Texp(−ℓ)] ≥ 12 [E_θ [N_S(T) \H_S \ ]-T (- ) ] ≥12[θ[N(T)]−Tℙθ(H)−Texp(−ℓ)] ≥ 12 [E_θ[N_S(T)]-TP_θ(H_S)-T (- ) ] ≥12θ[N(T)]−T2q(m)−T2exp(−ℓ). ≥ 12E_θ[N_S(T)]- T2q_ Alg(m)- T2 (- ). Thus, ν[N(T)]≥12θ[N(T)]−T2q(m)−T2exp(−ℓ). _ _S[N_S(T)]≥ 12E_θ[N_S(T)]- T2q_ Alg(m)- T2 (- ). (C.5) We now average (C.5) over all subsets ⊆S with ||=K−A|S|=K-A. Since every arm belongs to (K−1K−A−1) K-1K-A-1 such subsets, 1(K−A)∑⊆:||=K−Aθ[N(T)]=(K−1K−A−1)(K−A)∑a∈θ[Na(T)]=K−AKT. 1 KK-A _S :\,|S|=K-AE_θ[N_S(T)]= K-1K-A-1 KK-A _a E_θ[N_a(T)]= K-AKT. Therefore, 1(K−A)∑⊆:||=K−Aν[N(T)]≥T2[K−AK−q(m)−exp(−ℓ)]. 1 KK-A _S :\,|S|=K-AE_ _S[N_S(T)]≥ T2 [ K-AK-q_ Alg(m)- (- ) ]. (C.6) Since Every ν _S has exactly A optimal arms, we have Regretν,(T)=Δν[N(T)]Regret_ _S, Alg(T)= _ _S[N_S(T)] . Together with (C.6), this implies that ΓK−AKT≥Δ(K−A)∑⊆:||=K−Aν[N(T)]≥ΔT2[K−AK−q(m)−exp(−ℓ)]. K-AK T≥ KK-A _S :\,|S|=K-AE_ _S[N_S(T)]≥ T2 [ K-AK-q_ Alg(m)- (- ) ]. Rearranging and substituting Δ=(4mℓ)−1 =(4 m )^-1 gives q(m) q_ Alg(m) ≥K−AK−exp(−ℓ)−2Γ(K−A)TKΔT ≥ K-AK- (- )- 2 (K-A) TK T (C.7) =K−AK−exp(−ℓ)−8ΓK−AKmℓT. = K-AK- (- )-8 K-AK m T. (C.8) Combining (C.4) and (C.8) proves K−AK−exp(−ℓ)−8ΓK−AKmℓT≤q(m)≤exp(−ℓ)+8ΓK−AKTℓm, K-AK- (- )-8 K-AK m T≤ q_ Alg(m)≤ (- )+8 K-AK T m, as desired. ∎ C.2 Tightness of Lemma C.1 In this section, we show that both inequalities in Lemma C.1 cannot be improved in general, for all m=O~(T)m= O(T) and A≥K/2A≥ K/2 and ℓ chosen to be the same order as the remaining factors in the bound. For simplicity, given any algorithm Alg, we write q(m):=max⊆:||=K−Aℙθ(N(T)≥m). q_ Alg(m):= _S :\,|S|=K-AP_θ (N_S(T)≥ m ). Then a properly chosen ℓ , together with m=O~(T)m= O(T) and A≥K/2A≥ K/2 reduces the lower envelop in Lemma C.1 to q(m)=Ω~(K−AK), q_ Alg(m)= ( K-AK ), and the upper envelop to q(m)=O~(K−AKTm). q_ Alg(m)= O ( K-AK Tm ). We will show that there exist two algorithms that attain the reduced lower and upper envelop respectively. Tightness of the Lower Envelope. We show that the lower bound is attained by the near-minimax optimal algorithm SMOSS. Recall that SMOSS first samples a subset ℬ⊆B of L arms uniformly without replacement and then runs a bandit algorithm only on the arms in ℬB for all T rounds, where L=Θ~(1)L= (1). We show that, under the all-equal instance θ, for every m≤T/Lm≤ T/L, qSMOSS(m)≤L(K−A)/Kq_SMOSS(m)≤ L(K-A)/K. Fix any ⊆S with ||=K−A|S|=K-A. Since SMOSS only pulls arms in the randomly sampled subset ℬB, the event N(T)≥mN_S(T)≥ m for any m≥1m≥ 1 implies that ℬ∩≠∅B∩S≠ . Therefore, ℙ[N(T)≥m]≤ℙ[∩≠∅]≤∑a∈ℙ[a∈]=L(K−A)K, _ θ [N_S(T)≥ m ] [U∩S≠ ]≤ _a∈SP[a ]= L(K-A)K, which gives that qSMOSS(m)≤L(K−A)K. q_SMOSS(m)≤ L(K-A)K. (C.9) Algorithm 2 Tail-Saturating Algorithm for Bandit with Multiple Optimal Arms 0: Action set A, number of total rounds T, number of optimal arms A, and threshold m≤T/2m≤ T/2. 1: Fix any subset ⊆U with ||=2(K−A)|U|=2(K-A) together with a partition =0∪1U=S_0∪S_1, where |0|=|1|=K−A|S_0|=|S_1|=K-A. 2: Set pm:=min1,K−AKTm, p_m:= \1,\, K-AK Tm \, and sample Z∼Bernoulli(pm)Z (p_m). 3: if Z=0Z=0 then 4: Run SMOSS on A for T rounds. 5: else 6: Sample a uniformly random permutation σ of the arms in U. 7: Run SMOSS on σ()σ(U) for 2m2m rounds, using K′=2(K−A)K =2(K-A) and A′=K−A =K-A as its input parameters, and map the selected actions back to U through σ−1σ^-1. 8: Restart SMOSS on the full action set A for the remaining T−2mT-2m rounds. 9: end if Tightness of the upper envelope. For every prescribed scale m≤T/2m≤ T/2, we construct a minimax-optimal algorithm satisfying q(m)=Ω~(min1,K−AKTm), q_ Alg(m)= ( \1,\, K-AK Tm \ ), which matches the upper envelope in Lemma C.1. The constructed algorithm is described in Algorithm 2, which is built on the algorithm SMOSS. We first show that Algorithm 2 is minimax-optimal. On the event Z=1Z=1, we fix any fixed subset ||=2(K−A)|U|=2(K-A). Since the original instance contains only K−AK-A suboptimal arms in total, the set U of 2(K−A)2(K-A) arms contains at least K−AK-A optimal arms. Therefore, when SMOSS is run on U with parameters K′=2(K−A)K =2(K-A) and A′=K−A =K-A, the same subsampling analysis as in Section 4 gives supν:|opt(ν)|=ARegretν,SMOSS(2m)=O~(m), _ν:\,|A^opt(ν)|=ARegret_ν,SMOSS^U(2m)= O( m), (C.10) where Regretν,SMOSS(2m)Regret_ν,SMOSS^U(2m) denotes the regret accumulated during the exploration phase on U. The remainder of Algorithm 2 simply runs SMOSS on the original problem, and hence contributes at most O~((K−A)/KT) O((K-A)/K T) regret. Consequently, supν:|opt(ν)|=ARegretν,(T)≤O~(K−AKT)+pmO~(m)=O~(K−AKT), _ν:\,|A^opt(ν)|=ARegret_ν, Alg(T)≤ O ( K-AK T )+p_m O( m)= O ( K-AK T ), where the last equality follows from pmm=minm,K−AKT≤K−AKT. p_m m= \ m,\, K-AK T \≤ K-AK T. Thus Algorithm 2 remains minimax-optimal up to logarithmic factors. It remains to characterize its pull-count tail under the all-equal instance θ. Conditional on Z=1Z=1, consider only the first 2m2m rounds. Let Y:=N0(2m)Y:=N_S_0(2m). Since every arm has the same reward distribution under θ, and we apply a uniformly random permutation to U before running the exploration algorithm, the resulting trajectory distribution is invariant under permutations of the arms in U. In particular, swapping 0S_0 and 1S_1 leaves the distribution unchanged. Moreover, every action during the first 2m2m rounds belongs to =0∪1U=S_0∪S_1. These leads to Y=2m−N1(2m)=2m−Y, Y=2m-N_S_1(2m) d=2m-Y, which immediately gives ℙθ[Y≥m∣Z=1]=1+ℙθ[Y=m∣Z=1]2≥12. _θ[Y≥ m Z=1]= 1+P_θ[Y=m Z=1]2≥ 12. Since the number of pulls of 0S_0 can only increase after the exploration phase, we obtain that q(m) q_ Alg(m) ≥ℙθ[N0(T)≥m] _θ [N_S_0(T)≥ m ] ≥ℙ[Z=1]ℙθ[N0(2m)≥m|Z=1] [Z=1]P_θ [N_S_0(2m)≥ m\, |\,Z=1 ] ≥12min1,K−AKTm. ≥ 12 \1,\, K-AK Tm \. Together with (C.9), it is indicated that both bounds in Lemma C.1 cannot be improved up to logarithmic factors. C.3 Exploration profile of Near Minimax-Optimal Algorithms In this section, we provide the formal statement and proof of the exploration lower bound for algorithms that are near-minimax optimal on ΞK,B _K,B, referenced in Section 6.2. The argument follows the same strategy as Lemma C.1, but is applied in the opposite direction: instead of showing that an algorithm near-optimal on ΞK,A _K,A rarely concentrates too many pulls on a fixed small set, we show that an algorithm near-optimal on ΞK,B _K,B cannot avoid pulling a fixed set of size B sufficiently often. Lemma C.2. Let 1≤B<K1≤ B<K, and suppose that Alg is minimax-optimal on ΞK,B _K,B up to a factor Γ≥1 ≥ 1, namely supν:|opt(ν)|=BRegretν,(T)≤ΓK−BKBT. _ν:\,|A^opt(ν)|=BRegret_ν, Alg(T)≤ K-B KB T. Let θ denote the all-equal instance. Then, for every ⊆U with ||=B|U|=B, every ℓ≥1 ≥ 1, and every integer m with 1≤m≤T/21≤ m≤ T/2, ℙθ[N(T)<m]≤exp(−ℓ)+16ΓKℓmBT. _θ [N_U(T)<m ]≤ (- )+16 K mBT. (C.11) In particular, for any δ=Θ(1)δ= (1), taking ℓ=log(2/δ) = (2/δ), sufficient large T and mB:=⌊δ2BT210Γ2Kℓ⌋=Ω~(TBK), m_B:= δ^2BT2^10 ^2K = ( TBK ), we obtain ℙθ[N(T)≥mB]≥1−δP_θ [N_U(T)≥ m_B ]≥ 1-δ. Proof of Lemma C.2. Fix ⊆U with ||=B|U|=B, ℓ≥1 ≥ 1, and an integer m≤T/2m≤ T/2, and write Δ:=(4mℓ)−1≤1/4 :=(4 m )^-1≤ 1/4. Consider the instance μ obtained from the all-equal instance θ by increasing the mean rewards on U by Δ : μa:=1/2+Δ,a∈,1/2,a∈∁. _a:= cases1/2+ ,&a ,\\ 1/2,&a . cases Since ||=B|U|=B, every arm in U is strictly better than every arm outside U, so μ has exactly B optimal arms, namely opt(μ)=A^opt(μ)=U, and hence μ∈ΞK,Bμ∈ _K,B. As in the proof of Lemma C.1, define H:=N(T)≥m,τ:=inft∈[T]:N(t)=m∧T, H:=\N_U(T)≥ m\, τ:= \t∈[T]:N_U(t)=m\ T, so that τ is a bounded (ℱt)t=0T(F_t)_t=0^T-stopping time and, since the pull count N(t)N_U(t) increases by at most one per round, H=N(τ)=m∈ℱτH=\N_U(τ)=m\ _τ. Consequently H∁=N(T)<mH =\N_U(T)<m\ also belongs to ℱτF_τ, and on H∁H we have τ=Tτ=T. We first show that, up to τ, the trajectory distributions induced by θ and μ remain close. Writing ℙθτ:=ℙθ|ℱτP_θ^τ:=P_θ|_F_τ and ℙμτ:=ℙμ|ℱτP_μ^τ:=P_μ|_F_τ, and using θa−μa=−Δa∈ _a- _a=- \a \, Proposition B.3 gives logdℙθτdℙμτ \,dP_θ^τ\,dP_μ^τ =∑t=1τ[(θat−μat)(rt−θat)+12(θat−μat)2] = _t=1^τ [( _a_t- _a_t)(r_t- _a_t)+ 12( _a_t- _a_t)^2 ] =−Δ∑t=1τat∈(rt−1/2)+Δ22N(τ). =- _t=1^τ \a_t \(r_t-1/2)+ ^22N_U(τ). Denote Mt:=−Δ∑s=1tas∈(rs−1/2)M_t:=- _s=1^t \a_s \(r_s-1/2) and Vt:=Δ2N(t)V_t:= ^2N_U(t). Exactly as in the proof of Lemma C.1, since rt−1/2r_t-1/2 is 11-sub-Gaussian conditioned on tG_t under ℙθP_θ (regardless of the sign of Δ ), exp(λMt−λ2Vt/2) (λ M_t-λ^2V_t/2) is a super-martingale under ℙθP_θ for every λ∈ℝλ . Invoking Lemma E.1 with x=Δ2mℓx= 2m , and using Vτ≤mΔ2V_τ≤ m ^2, we obtain ℙθ(Mτ≥Δ2mℓ)≤exp(−2mΔ2ℓ2mΔ2)=exp(−ℓ). _θ (M_τ≥ 2m )≤ (- 2m ^2 2m ^2 )= (- ). Since Δ2N(τ)/2≤mΔ2/2 ^2N_U(τ)/2≤ m ^2/2, this gives ℙθ(logdℙθτdℙμτ≥Δ2mℓ+mΔ2/2)≤exp(−ℓ). _θ ( \,dP_θ^τ\,dP_μ^τ≥ 2m +m ^2/2 )≤ (- ). Recalling Δ=(4mℓ)−1 =(4 m )^-1, we have Δ2mℓ+mΔ2/2=1/(22)+1/(32ℓ)<log2 2m +m ^2/2=1/(2 2)+1/(32 )< 2 since ℓ≥1 ≥ 1, so ℙθ(logdℙθτdℙμτ>log2)≤exp(−ℓ). _θ ( \,dP_θ^τ\,dP_μ^τ> 2 )≤ (- ). (C.12) We now transfer the bound on ℙθ(H∁)P_θ(H ) to μ. Since H∁∈ℱτH _τ, we apply Proposition B.1 on (Ω,ℱτ)( ,F_τ) with ℙ=ℙθτP=P_θ^τ, ℚ=ℙμτQ=P_μ^τ, X=H∁X= \H \, b=1b=1 and γ=log2γ= 2; using (C.12), this gives ℙμ(H∁)≥12[ℙθ(H∁)−exp(−ℓ)]. _μ (H )≥ 12 [P_θ (H )- (- ) ]. (C.13) It remains to bound the left-hand side of (C.13) using the regret guarantee of Alg on μ. Every arm in ∁U is suboptimal under μ with gap Δ , so Regretμ,(T)=Δμ[N∁(T)]=Δ(T−μ[N(T)]). _μ, Alg(T)= \,E_μ [N_U (T) ]= (T-E_μ[N_U(T)] ). On the event H∁=N(T)<mH =\N_U(T)<m\ we have N∁(T)>T−mN_U (T)>T-m, so, using (C.13) and m≤T/2m≤ T/2, Regretμ,(T) _μ, Alg(T) ≥Δ(T−m)ℙμ(H∁) ≥ (T-m)P_μ (H ) ≥Δ(T−m)2[ℙθ(H∁)−exp(−ℓ)] ≥ (T-m)2 [P_θ (H )- (- ) ] ≥ΔT4[ℙθ(H∁)−exp(−ℓ)]. ≥ T4 [P_θ (H )- (- ) ]. On the other hand, since μ∈ΞK,Bμ∈ _K,B, the assumed minimax-optimality of Alg on ΞK,B _K,B gives Regretμ,(T)≤ΓK−BKBT≤ΓKBT, _μ, Alg(T)≤ K-B KB T≤ KB T, where the second inequality uses K−B≤K-B≤ K. Combining the last two displays and rearranging leads to ℙθ(H∁)≤exp(−ℓ)+4ΓΔTKB=exp(−ℓ)+16ΓKℓmBT, _θ (H )≤ (- )+ 4 T KB= (- )+16 K mBT, where the equality substitutes Δ−1=4mℓ ^-1=4 m . This proves the claimed result in (C.11). ∎ C.4 Proof of Theorem 6.1 Proof of Theorem 6.1. The proof follows a Le Cam two-point argument similar to the proof of Theorem 5.1. For simplicity, for any subset ⊆S , we define N(T):=∑a∈Na(T)N_S(T):= _a N_a(T). Fix an arbitrary subset 0⊆S_0 with |0|=A|S_0|=A. For a parameter Δ∈(0,1/4] ∈(0,1/4] to be specified later, consider the reference instance ν0 _0 with reward function r0(a):=1/2,a∈0,1/2−Δ,a∈0∁. r_0(a):= cases1/2,&a _0,\\ 1/2- ,&a _0 . cases Thus, ν0 _0 has exactly A optimal arms, namely the arms in 0S_0. Let ℙ0P_0 and 0E_0 denote probability and expectation under ν0 _0 and Alg. By the assumed regret guarantee of Alg on every instance with A optimal arms, Δ0[N0∁(T)]=Regretν0,(T)≤RA:=ΓK,TK−AKAT, _0[N_S_0 (T)]=Regret_ _0, Alg(T)≤ R_A:= _K,T K-A KA T, which gives that 0[N0∁(T)]≤RA/ΔE_0[N_S_0 (T)]≤ R_A/ . Since B≤K−AB≤ K-A, we can choose a subset 1⊆0∁S_1 _0 with |1|=B|S_1|=B consisting of the B least-sampled arms in 0∁S_0 . By averaging, 0[N1(T)]≤BK−A0[N0∁(T)]≤BRA(K−A)Δ, _0[N_S_1(T)]≤ BK-AE_0[N_S_0 (T)]≤ BR_A(K-A) , (C.14) where the first inequality holds due to that 1S_1 is the least sampled set under ν0 _0. We now construct the alternative instance ν1 _1 by promoting the arms in 1S_1: r1(a):=1/2,a∈0,1/2+Δ,a∈1,1/2−Δ,a∈(0∪1)∁. r_1(a):= cases1/2,&a _0,\\ 1/2+ ,&a _1,\\ 1/2- ,&a∈(S_0 _1) . cases The instance ν1 _1 has exactly B optimal arms, namely the arms in 1S_1. Let ℙ1P_1 and 1E_1 denote probability and expectation under ν1 _1 and Alg. We next apply a change-of-measure argument. Since N1(T)∈[0,T]N_S_1(T)∈[0,T], Lemma E.2 gives 1[N1(T)]≤0[N1(T)]+TTV(ℙ0,ℙ1)≤0[N1(T)]+T12KL(ℙ0∥ℙ1), _1[N_S_1(T)] _0[N_S_1(T)]+TTV(P_0,P_1) _0[N_S_1(T)]+T 12KL(P_0\|P_1), (C.15) where the last inequality holds due to Pinsker’s inequality (Lemma E.3). To control the KL-divergence, we see that the instances ν0 _0 and ν1 _1 differ only on the arms in 1S_1. For every a∈1a _1, the reward distribution is (1/2−Δ,1)N(1/2- ,1) under ν0 _0 and (1/2+Δ,1)N(1/2+ ,1) under ν1 _1. Hence, by the KL decomposition for adaptive bandit experiments, KL(ℙ0∥ℙ1) (P_0\|P_1) =∑a∈10[Na(T)]KL((1/2−Δ,1)∥(1/2+Δ,1)) = _a _1E_0[N_a(T)]KL (N(1/2- ,1)\|N(1/2+ ,1) ) =2Δ20[N1(T)] =2 ^2E_0[N_S_1(T)] ≤2ΔBRAK−A, ≤ 2 BR_AK-A, where the last inequality follows from (C.14). Now choose Δ:=min1/4,(K−A)/(16BRA) := \1/4,\,(K-A)/(16BR_A)\. Then KL(ℙ0∥ℙ1)≤1/8KL(P_0\|P_1)≤ 1/8, and consequently we know that TV(ℙ0,ℙ1)≤1/4TV(P_0,P_1)≤ 1/4. Moreover, by (C.14), 0[N1(T)]≤BRAK−Amax4,16BRAK−A=max4BRAK−A,16B2RA2(K−A)2≤T4, _0[N_S_1(T)]≤ BR_AK-A \4, 16BR_AK-A \= \ 4BR_AK-A, 16B^2R_A^2(K-A)^2 \≤ T4, where the last inequality follows from the condition T≥max16BRA/(K−A), 64B2RA2/(K−A)2, T≥ \16BR_A/(K-A),\,64B^2R_A^2/(K-A)^2\, which can be derived directly from B≤A/(8ΓK,T)B≤ A/(8 _K,T) and T≥256B2ΓK,T2/(KA)T≥ 256B^2 ^2_K,T/(KA). Now we combine this inequality with (C.15) and TV(ℙ0,ℙ1)≤1/4TV(P_0,P_1)≤ 1/4, which leads to 1[N1(T)]≤T4+T4=T2. _1[N_S_1(T)]≤ T4+ T4= T2. Finally, under ν1 _1, every arm outside 1S_1 has suboptimality gap at least Δ . Therefore, Regretν1,(T)≥Δ1[T−N1(T)]≥ΔT2=minT8,(K−A)T32BRA. _ _1, Alg(T)≥ _1[T-N_S_1(T)]≥ T2= \ T8, [rgb]1,0,0 (K-A)T32BR_A \. Recall the condition that T≥KA(16B2ΓK,T2)−1T≥ KA(16B^2 _K,T^2)^-1, we have that T/8≥(K−A)T/(32BRA)T/8≥(K-A)T/(32BR_A), leading to Regretν1,(T)≥(K−A)T32BRA=KA32BΓK,TT. _ _1, Alg(T)≥ (K-A)T32BR_A= KA32B _K,T T. Since ν1 _1 has exactly B optimal arms, this proves the theorem. ∎ C.5 Proof of Theorem 6.2 In this section, we provide the proof of Theorem 6.2. We first need the following technical result. Lemma C.3 (Aggregation of square-root tails). Let X1,…,XqX_1,…,X_q be nonnegative integer-valued random variables, not necessarily independent. Suppose that, for some δ,c≥0δ,c≥ 0, each XiX_i satisfies ℙ[Xi≥s]≤δ+cs [X_i≥ s]≤δ+ c s for every i∈[q]i∈[q] and every integer s≥1s≥ 1. Then, for any integer m≥1m≥ 1, ℙ[∑i=1qXi>m]≤2qδ+3qcm. [ _i=1^qX_i>m ]≤ 2qδ+ 3qc m. Proof. For each i∈[q]i∈[q], define the truncated random variable X~i:=Xi∧m X_i:=X_i m. We decompose the event ∑i=1qXi>m\ _i=1^qX_i>m\ according to whether any individual random variable exceeds the truncation level m. In particular, ∑i=1qXi>m⊆maxi∈[q]Xi>m∪∑i=1qX~i>m. \ _i=1^qX_i>m \ \ _i∈[q]X_i>m \∪ \ _i=1^q X_i>m \. For the first event, by a union bound and the assumed tail bound, ℙ[maxi∈[q]Xi>m]≤∑i=1qℙ[Xi>m]≤qδ+qcm. [ _i∈[q]X_i>m ]≤ _i=1^qP[X_i>m]≤ qδ+ qc m. For the second event, since XiX_i is nonnegative and integer-valued, the tail-sum formula gives [X~i]=∑s=1mℙ[Xi≥s]≤mδ+c∑s=1m1s≤mδ+2cm, [ X_i]= _s=1^mP[X_i≥ s]≤ mδ+c _s=1^m 1 s≤ mδ+2c m, where the last inequality follows from ∑s=1m1/s≤2m _s=1^m1/ s≤ 2 m. Therefore, by Markov’s inequality, ℙ[∑i=1qX~i>m]≤1m∑i=1q[X~i]≤qδ+2qcm. [ _i=1^q X_i>m ]≤ 1m _i=1^qE[ X_i]≤ qδ+ 2qc m. Combining the two bounds yields ℙ[∑i=1qXi>m]≤2qδ+3qcm, [ _i=1^qX_i>m ]≤ 2qδ+ 3qc m, which finishes the proof. ∎ Now we are ready to prove Theorem 6.2. Proof of Theorem 6.2. For convenience, define RA:=ΓK,T(K−A)T/KR_A:= _K,T(K-A) T/K, which is the near-minimax optimal rate on ΞK,A _K,A. Fix an arbitrary subset ⊆U with ||=B|U|=B. For a parameter Δ>0 >0 to be specified later, consider the bandit instance ν with reward function rν(a):=1/2+Δ,a∈,1/2,a∈∁. r_ν(a):= cases1/2+ ,&a ,\\ 1/2,&a . cases Thus, ν has exactly B optimal arms, namely the arms in U. Recall that θ denotes the all-equal reference instance with rθ(a)=1/2r_θ(a)=1/2 for every a∈a . We use ℙνP_ν and ℙθP_θ to denote the trajectory distributions induced by Alg under ν and θ, respectively. We first show that, under the reference instance θ, the algorithm samples U only O~(q2RA2) O(q^2R_A^2) times with constant probability, where q:=⌈B/(K−A)⌉q:= B/(K-A) . Partition U into q disjoint subsets 1,…,qU_1,…,U_q such that |i|≤K−A|U_i|≤ K-A for every i∈[q]i∈[q]. For each i∈[q]i∈[q], extend iU_i to a subset i⊆S_i satisfying i⊆iU_i _i and |i|=K−A|S_i|=K-A. Then N(T)=∑i=1qNi(T)≤∑i=1qNi(T). N_U(T)= _i=1^qN_U_i(T)≤ _i=1^qN_S_i(T). Set ℓ:=log(16q) := (16q). Then, for every s∈[T]s∈[T] and every i∈[q]i∈[q], applying Lemma C.1 gives ℙθ[Ni(T)≥s]≤116q+8RAℓs. _θ [N_S_i(T)≥ s ]≤ 116q+8R_A s. Since Ni(T)≤TN_S_i(T)≤ T, the same inequality holds trivially for s>Ts>T. Therefore, applying Lemma C.3 to Xi:=Ni(T)X_i:=N_S_i(T) with δ=1/(16q)δ=1/(16q) and c=8RAℓc=8R_A gives, for every m≥1m≥ 1, ℙθ[∑i=1qNi(T)>m]≤18+24qRAℓm. _θ [ _i=1^qN_S_i(T)>m ]≤ 18+24qR_A m. Now we choose m=⌈4096q2RA2ℓ⌉m= 4096q^2R_A^2 . Then 24qRAℓ/m≤3/824qR_A /m≤ 3/8, which leads to ℙθ[∑i=1qNi(T)>m]≤12. _θ [ _i=1^qN_S_i(T)>m ]≤ 12. Since N(T)≤∑i=1qNi(T)N_U(T)≤ _i=1^qN_S_i(T), we conclude that ℙθ[N(T)≤m]≥12. _θ [N_U(T)≤ m ]≥ 12. (C.16) We now show that T≥2mT≥ 2m. Since B≥K−AB≥ K-A, we have q=⌈B/(K−A)⌉≤2B/(K−A)q= B/(K-A) ≤ 2B/(K-A). Consequently, ℓ≤log(32B/(K−A)) ≤ (32B/(K-A)). Using the definition of RAR_A, 4096q2RA2ℓ 4096q^2R_A^2 ≤16384B2(K−A)2ΓK,T2(K−A)2TK2log(32BK−A) ≤ 16384 B^2(K-A)^2 _K,T^2 (K-A)^2TK^2 ( 32BK-A ) =16384B2ΓK,T2log(32B/(K−A))K2T. =16384 B^2 _K,T^2 (32B/(K-A) )K^2T. By the assumed condition BΓK,Tlog(32BK−A)≤K256, B _K,T ( 32BK-A )≤ K256, the right-hand side is at most T/4T/4. Therefore, m=⌈4096q2RA2ℓ⌉≤4096q2RA2ℓ+1≤T4+1≤T2, m= 4096q^2R_A^2 ≤ 4096q^2R_A^2 +1≤ T4+1≤ T2, where the last inequality follows from T≥4T≥ 4. We now transfer (C.16) from the all-equal reference instance θ to the hard instance ν. Once again, we consider the stopping time ℰ:=N(T)≤m,τ:=inft∈[T]:N(t)=m+1∧T. := \N_U(T)≤ m \, τ:= \t∈[T]:N_U(t)=m+1 \ T. so that ℙθ[ℰ]≥1/2P_θ[E]≥ 1/2. Notice that ℰ∈ℱτE _τ and N(τ)≤m+1N_U(τ)≤ m+1 almost surely. Since θ and ν differ only on the arms in U, where the reward distribution is (1/2,1)N(1/2,1) under θ and (1/2+Δ,1)N(1/2+ ,1) under ν, the KL decomposition for the stopped trajectory gives KL(ℙθ|ℱτ∥ℙν|ℱτ)=Δ22θ[N(τ)]≤Δ2(m+1)2. (P_θ|_F_τ\|P_ν|_F_τ )= ^22E_θ[N_U(τ)]≤ ^2(m+1)2. Now we choose Δ:=1/(4m+1) :=1/(4 m+1). Then we see that (ℙθ|ℱτ∥ℙν|ℱτ)≤1/32 KL (P_θ|_F_τ\|P_ν|_F_τ )≤ 1/32. By Pinsker’s inequality (Lemma E.3), OPENTV(ℙθ||ℱτ,ℙν|ℱτ)≤1/8TV( P_θ||_F_τ,P_ν|_F_τ)≤ 1/8. Since ℰ∈ℱτE _τ, it follows from (C.16) that ℙν[ℰ]≥ℙθ[ℰ]−TV(ℙθ|ℱτ,ℙν|ℱτ)≥38. _ν[E] _θ[E]-TV (P_θ|_F_τ,P_ν|_F_τ )≥ 38. Recall that the arms in U are the unique optimal arms under ν, while every arm in ∁U has suboptimality gap Δ . Therefore, Regretν,(T)=Δν[T−N(T)]≥Δ(T−m)ℙν[ℰ]≥3ΔT16=3T64m+1, _ν, Alg(T)= _ν [T-N_U(T) ]≥ (T-m)P_ν[E]≥ 3 T16= 3T64 m+1, where the last inequality holds due to m≤T/2m≤ T/2. It remains to simplify this lower bound. Define ℓ¯=log(32B/(K−A)) = (32B/(K-A)). Since B/(K−A)≥1B/(K-A)≥ 1, we have ℓ=log(16q)≥log(16B/(K−A))≥(4/5)ℓ¯ = (16q)≥ (16B/(K-A))≥(4/5) . Together with the assumed horizon condition T≥K2/(B2ΓK,T2ℓ¯)T≥ K^2/(B^2 _K,T^2 ) gives q2RA2ℓ≥B2(K−A)2ΓK,T2(K−A)2TK2ℓ≥45B2ΓK,T2Tℓ¯K2≥45. q^2R_A^2 ≥ B^2(K-A)^2 _K,T^2 (K-A)^2TK^2 ≥ 45 B^2 _K,T^2T K^2≥ 45. Consequently, m+1≤4096q2RA2ℓ+2≤8192q2RA2ℓm+1≤ 4096q^2R_A^2 +2≤ 8192q^2R_A^2 . Therefore, Regretν,(T)≥3T64m+1≥381922KABΓK,Tlog(32B/(K−A))T, _ν, Alg(T)≥ 3T64 m+1≥ 38192 2 KAB _K,T (32B/(K-A)) T, where the second inequality uses q≤2B/(K−A)q≤ 2B/(K-A), K≥AK≥ A and ℓ≤log(32B/(K−A)) ≤ (32B/(K-A)). This finishes the proof. ∎ Appendix D High-probability Lower Bound As discussed in Remark 4.2, one may ask whether the O~((K−A)T/K) O((K-A) T/K) rate in Theorem 4.1 can be extended to the high-probability setting. In this section, we will show that it is impossible and there is a necessary payoff to achieve the near-optimal expected rate. In particular, let att=1T\a_t\_t=1^T be the actions selected by Alg. We write RT=∑t=1Tr∗−∑t=1Tr(at). R_T= _t=1^Tr^*- _t=1^Tr(a_t). As a result, we have [RT]=Regret(T)E[R_T]=Regret(T). Our main hardness result is summarized in the following theorem: Theorem D.1. Suppose A>K/2A>K/2, so that (K−A)/K<1/2(K-A)/K<1/2, and fix Γ≥1 ≥ 1. Define ℓ=log(16K/(K−A)) = (16K/(K-A)) and c0=13/128c_0=13/128. Suppose that Alg is a strategy satisfying for any problem instance in ΞK,A _K,A, Regret(T)≤ΓK−AKT, (T)≤ K-AK T, that is, a policy that achieves the minimax-optimal expected regret up to a factor of Γ . If T≥8Γ2ℓ/c02T≥8 ^2 /c_0^2, then there exists a problem instance μ∈ΞK,Aμ∈ _K,A such that ℙμ,(R(T)≥c082TΓℓ)≥K−A32K. _μ, Alg (R(T)≥ c_08 2 T )≥ K-A32K. (D.1) Theorem D.1 indicates that, for any near-minimax optimal algorithm Alg, there exists some instance, such that the pseudo-regret of Alg reaches Ω~(T) ( T), with probability Ω((K−A)/K) ((K-A)/K). Remark D.2. It is widely known that UCB-typed algorithm, while achieving a near-minimax-optimal rate, simultaneously achieves a O~(KTpolylog(δ−1)) O( KTpolylog(δ^-1)) high-probability upper bound. Theorem D.1 shows that, the analogue rate, O~((K−A)K−1T⋅polylog(δ−1)) O ((K-A)K^-1 T·polylog(δ^-1) ) is impossible when A=K−o(K)A=K-o(K). In particular, making O~((K−A)K−1T⋅polylog(δ−1))=O~(T) O ((K-A)K^-1 T·polylog(δ^-1) )= O( T) requires δ∼exp(−K/(K−A))≪(K−A)/Kδ (-K/(K-A)) (K-A)/K, which contradicts (D.1). Proof of Theorem D.1. Recall that ℓ=log(16K/(K−A)) = (16K/(K-A)) and c0=13/128c_0=13/128. Since T≥8Γ2ℓ/c02T≥ 8 ^2 /c_0^2, we can choose an integer m satisfying c02T8Γ2ℓ≤m≤c02T4Γ2ℓ. c_0^2T8 ^2 ≤ m≤ c_0^2T4 ^2 . (D.2) Let θ be the instance such that =/2∈ℝK θ=1/2 ^K denote the all-equal auxiliary instance. We first apply Lemma C.1 to characterize the exploration behavior of Alg under θ. By the lower bound in Lemma C.1, max⊆[K]:||=K−Aℙθ[N(T)≥m] _S [K]:\,|S|=K-AP_θ [N_S(T)≥ m ] ≥K−AK−exp(−ℓ)−8ΓK−AKmℓT ≥ K-AK- (- )-8 K-AK m T ≥K−AK−K−A16K−13(K−A)32K ≥ K-AK- K-A16K- 13(K-A)32K ≥K−A2K, ≥ K-A2K, where the second inequality follows from exp(−ℓ)=(K−A)/(16K) (- )=(K-A)/(16K) and the upper bound on m in (D.2). Therefore, there exists a subset ⊆[K]S [K] with ||=K−A|S|=K-A such that ℙθ[N(T)≥m]≥K−A2K. _θ [N_S(T)≥ m ]≥ K-A2K. (D.3) We now construct the hard instance μ by decreasing the mean rewards of the arms in S by Δ , with Δ=(4mℓ)−1 =(4 m )^-1, namely μa:=12−Δ,a∈,12,a∈∁. _a:= cases 12- ,&a∈S,\\ 12,&a∈S . cases Since ||=K−A|S|=K-A, the instance μ has exactly A optimal arms and hence belongs to ΞK,A _K,A. Now we transfer (D.3) from the auxiliary instance θ to μ. As usual, we prove that at τ, the probability distributions induced by θ and μ are still close, therefore leading to that ℙμ[H]≳(K−A)/KP_μ[H] (K-A)/K, where H and τ are defined by H:=N(T)≥m,τ:=inft∈[T]:N(t)=m∧T. H:= \N_S(T)≥ m \, τ:= \t∈[T]:N_S(t)=m \ T. In particular, consider the trajectory distributions restricted to ℱτF_τ by ℙθτ:=ℙθ|ℱτP_θ^τ:=P_θ|_F_τ and ℙμτ:=ℙμ|ℱτP_μ^τ:=P_μ|_F_τ. Applying Proposition B.3 gives that logdℙθ|ℱτdℙμ|ℱτ \,dP_θ|_F_τ\,dP_μ|_F_τ =∑t=1τ[(θat−μat)(rt−θat)+12(θat−μat)2] = _t=1^τ [( _a_t- _a_t)(r_t- _a_t)+ 12( _a_t- _a_t)^2 ] =Δ∑t=1τat∈(rt−1/2)+Δ22N(τ). = _t=1^τ \a_t∈S\(r_t-1/2)+ ^22N_S(τ). Now we denote Mt=Δ∑s=1tas∈(rs−1/2)M_t= _s=1^t \a_s∈S\(r_s-1/2) and Vt=Δ2N(t)V_t= ^2N_S(t), then the probability distribution ℙθP_θ, we see that for any λ∈ℝλ , θ[exp(λMt−λ2Vt2)|ℱt−1] _θ [ (λ M_t- λ^2V_t2 ) |F_t-1 ] =exp(λMt−1−λ2Vt−12)θ[exp(λ(rt−1/2)Δat∈−λ2Δ2at∈2)⏟(⋆)|ℱt−1] = (λ M_t-1- λ^2V_t-12 )E_θ [ (λ(r_t-1/2) \a_t∈S\- λ^2 ^2 \a_t∈S\2 )_( ) |F_t-1 ] For (⋆)( ), we first take expectation on tG_t, which gives that θ[(⋆)|t] _θ[( )|G_t] =1−at∈+at∈θ[exp(λ(rt−1/2)Δ−λ2Δ22)|t] =1- \a_t∈S\+ \a_t∈S\E_θ [ (λ(r_t-1/2) - λ^2 ^22 ) |G_t ] ≤1−at∈+at∈ ≤ 1- \a_t∈S\+ \a_t∈S\ =1, =1, where the inequality holds due to that rt−1/2r_t-1/2 is 11-sub-gaussian conditioned on tG_t on ℙθP_θ. This immediately gives θ[(⋆)|ℱt−1]≤1E_θ[( )|F_t-1]≤ 1, verifying that exp(λMt−λ2Vt/2) (λ M_t-λ^2V_t/2) is a super-martingale for any λ. Now invoking Lemma E.1 with x=Δ2mℓx= 2m , since Vτ≤mΔ2V_τ≤ m ^2, we have ℙθ(Mτ≥Δ2mℓ)≤exp(−2mΔ2ℓ2mΔ2)=exp(−ℓ). _θ (M_τ≥ 2m )≤ (- 2m ^2 2m ^2 )= (- ). Since Δ2N(τ)/2≤mΔ2/2 ^2N_S( _S)/2≤ m ^2/2, this immediately leads to ℙθ(logdℙθτdℙμτ≥Δ2mℓ+mΔ2/2)≤exp(−ℓ). _θ ( \,dP_θ^τ\,dP_μ^τ≥ 2m +m ^2/2 )≤ (- ). Recall that Δ=(4mℓ)−1 =(4 m )^-1, this means that Δ2mℓ+mΔ2/2=1/22+1/32ℓ<log2 2m +m ^2/2=1/2 2+1/32 < 2 since ℓ≥1 ≥ 1. Therefore, ℙ(logdℙθτdℙμτ>log2)≤exp(−ℓ). ( \,dP_θ^τ\,dP_μ^τ> 2 )≤ (- ). Now we apply Proposition B.1 on the measurable space (Ω,ℱτ)( ,F_ _S) with ℙ=ℙθτP=P_θ^τ, ℚ=ℙμτQ=P_μ^τ, X=HX= \H\, b=1b=1 and γ=log2γ= 2 and obtain that ℙμ(H)=ℙμτ(H)≥12[ℙθτ(H)−ℙ(logdℙθτdℙμτ>log2)]≥12[ℙθ(H)−exp(−ℓ)], _μ(H)=P_μ^τ(H)≥ 12 [P_θ^τ(H)-P ( \,dP_θ^τ\,dP_μ^τ> 2 ) ]≥ 12 [P_θ(H)- (- ) ], where the equation holds due to that H∈ℱτH _τ. Finally, every pull of an arm in S incurs regret Δ under μ. Hence, on the event H, R(T)≥Δm=m4ℓ. R(T)≥ m= m4 . Using the lower bound on m in (D.2), we obtain Δm≥14ℓc02T8Γ2ℓ=c082TΓℓ. m≥ 14 c_0^2T8 ^2 = c_08 2 T . Therefore, ℙμ(R(T)≥c082TΓℓ)≥K−A32K, _μ (R(T)≥ c_08 2 T )≥ K-A32K, which proves the desired result. ∎ Appendix E Auxiliary Lemmas The following standard stopped martingale inequality is a direct consequence of the time-uniform Chernoff bound of Howard et al. (2020, Theorem 1). Lemma E.1 (Stopped sub-Gaussian martingale inequality). Let (Mt,Vt)t=0T(M_t,V_t)_t=0^T be an adapted process with M0=V0=0M_0=V_0=0 and (Vt)t=0T(V_t)_t=0^T nondecreasing. Suppose that, for every s>0s>0, exp(sMt−s2Vt/2) (sM_t-s^2V_t/2) is a nonnegative supermartingale. Then, for any stopping time τ≤Tτ≤ T and every x,v>0x,v>0, ℙ(Mτ≥x,Vτ≤v)≤exp(−x22v). (M_τ≥ x,\,V_τ≤ v )≤ (- x^22v ). (E.1) In particular, if Vτ≤vV_τ≤ v almost surely, then ℙ(Mτ≥x)≤exp(−x22v). (M_τ≥ x)≤ (- x^22v ). The following lemma characterizes the change-of-measure under total variation, which is the core components in standard lower bound techniques like Le-Cam’s method (Yu, 1997). We refer to Tsybakov and Zaiats (2009, Lemma 2.1) for the proof. Lemma E.2. Let (Ω,ℱ)( ,F) be a measurable space, and let ℙP and ℚQ be probability measures on it. Then, for every ℱF-measurable function f:Ω→[0,T]f: →[0,T], |ℙ[f]−ℚ[f]|≤TTV(ℙ,ℚ), |E_P[f]-E_Q[f] |≤ TTV(P,Q), where TV(ℙ,ℚ):=supE∈ℱ|ℙ(E)−ℚ(E)|TV(P,Q):= _E |P(E)-Q(E) |. Lemma E.3 (Pinsker’s inequality). Let (Ω,ℱ)( ,F) be a measurable space, and let ℙP and ℚQ be probability measures on it. Then TV(ℙ,ℚ)≤12KL(ℙ∥ℚ). (P,Q)≤ 12KL(P\|Q). The following lemma is standard for proof of minimax lower bound and we refer to Lattimore and Szepesvári (2020, Theorem 14.2) for the proof. Lemma E.4 (Bretagnolle–Huber inequality). Let (Ω,ℱ)( ,F) be a measurable space, and let ℙP and ℚQ be probability measures on it. Then for every event E∈ℱE , ℙ(E)+ℚ(E∁)≥12exp(−KL(ℙ∥ℚ)). (E)+Q(E )≥ 12 (-KL(P\|Q) ). References Ashutosh et al. (2021) K. Ashutosh, J. Nair, A. Kagrecha, and K. Jagannathan Bandit algorithms: letting go of logarithmic regret for statistical robustness. In International Conference on Artificial Intelligence and Statistics, p. 622–630. Cited by: §2. Audibert and Bubeck (2009) J. Audibert and S. Bubeck Minimax policies for adversarial and stochastic bandits. In Colt, p. 217–226. Cited by: §1, 2. Auer et al. (2002) P. Auer, N. Cesa-Bianchi, and P. Fischer Finite-time analysis of the multiarmed bandit problem. Machine learning 47 (2), p. 235–256. Cited by: §1. Aziz et al. (2018) M. Aziz, J. Anderton, E. Kaufmann, and J. Aslam Pure exploration in infinitely-armed bandit models with fixed-confidence. In Algorithmic Learning Theory, p. 3–24. Cited by: §2. Bayati et al. (2020) M. Bayati, N. Hamidi, R. Johari, and K. Khosravi Unreasonable effectiveness of greedy algorithms in multi-armed bandit with many arms. Advances in Neural Information Processing Systems 33, p. 1713–1723. Cited by: §2. Bogunovic et al. (2021) I. Bogunovic, A. Losalka, A. Krause, and J. Scarlett Stochastic linear bandits robust to adversarial attacks. In International Conference on Artificial Intelligence and Statistics, p. 991–999. Cited by: §2. Bouneffouf et al. (2020) D. Bouneffouf, I. Rish, and C. Aggarwal Survey on applications of multi-armed and contextual bandits. In 2020 IEEE Congress on Evolutionary Computation (CEC), p. 1–8. Cited by: §1. Burnetas and Katehakis (1996) A. N. Burnetas and M. N. Katehakis Optimal adaptive policies for sequential allocation problems. Advances in Applied Mathematics 17 (2), p. 122–142. Cited by: §2. Chaudhuri and Kalyanakrishnan (2017) A. R. Chaudhuri and S. Kalyanakrishnan PAC identification of a bandit arm relative to a reward quantile. In Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, p. 1777–1783. Cited by: §2. Chaudhuri and Kalyanakrishnan (2018) A. R. Chaudhuri and S. Kalyanakrishnan Quantile-regret minimisation in infinitely many-armed bandits.. In UAI, p. 425–434. Cited by: §2. De Heide et al. (2021) R. De Heide, J. Cheshire, P. Ménard, and A. Carpentier Bandits with many optimal arms. Advances in Neural Information Processing Systems 34, p. 22457–22469. Cited by: §B.1, §1, §1, §2, §2, §4.1, §4, §5, §6.1, §6, Abstract, Algorithm 1. Degenne and Koolen (2019) R. Degenne and W. M. Koolen Pure exploration with multiple correct answers. Advances in Neural Information Processing Systems 32. Cited by: Remark B.2, §1, §2. Foster et al. (2020) D. J. Foster, C. Gentile, M. Mohri, and J. Zimmert Adapting to misspecification in contextual bandits. Advances in Neural Information Processing Systems 33, p. 11478–11489. Cited by: §2. Garivier and Kaufmann (2016) A. Garivier and E. Kaufmann Optimal best arm identification with fixed confidence. In Conference on Learning Theory, p. 998–1027. Cited by: Remark B.2. Garivier and Kaufmann (2021) A. Garivier and E. Kaufmann Nonasymptotic sequential tests for overlapping hypotheses applied to near-optimal arm identification in bandit models. Sequential Analysis 40 (1), p. 61–96. Cited by: Remark B.2, §2. Garivier et al. (2019) A. Garivier, P. Ménard, and G. Stoltz Explore first, exploit next: the true shape of regret in bandit problems. Mathematics of Operations Research 44 (2), p. 377–399. Cited by: Remark B.2, §2. Genalti et al. (2024) G. Genalti, L. Marsigli, N. Gatti, and A. M. Metelli (ε , U)-adaptive regret minimization in heavy-tailed bandits. In The Thirty Seventh Annual Conference on Learning Theory, p. 1882–1915. Cited by: §2. Gur et al. (2022) Y. Gur, A. Momeni, and S. Wager Smoothness-adaptive contextual bandits. Operations Research 70 (6), p. 3198–3216. Cited by: §2. Hadiji and Stoltz (2023) H. Hadiji and G. Stoltz Adaptation to the range in k-armed bandits. Journal of Machine Learning Research 24 (13), p. 1–33. Cited by: §2. Hadiji (2019) H. Hadiji Polynomial cost of adaptation for x-armed bandits. Advances in Neural Information Processing Systems 32. Cited by: §2. He et al. (2022) J. He, D. Zhou, T. Zhang, and Q. Gu Nearly optimal algorithms for linear contextual bandits with adversarial corruptions. Advances in neural information processing systems 35, p. 34614–34625. Cited by: §2. Hendrycks et al. (2021) D. Hendrycks, C. Burns, S. Kadavath, A. Arora, S. Basart, E. Tang, D. Song, and J. Steinhardt Measuring mathematical problem solving with the math dataset. In Proceedings of the Neural Information Processing Systems Track on Datasets and Benchmarks, Vol. 1. Cited by: §1. Howard et al. (2020) S. R. Howard, A. Ramdas, J. McAuliffe, and J. Sekhon Time-uniform Chernoff bounds via nonnegative supermartingales. Probability Surveys 17 (none), p. 257 – 317. External Links: Document Cited by: Appendix E. Jain et al. (2025) N. Jain, A. Gu, W. Li, F. Yan, T. Zhang, S. Wang, A. Solar-Lezama, K. Sen, and I. Stoica Livecodebench: holistic and contamination free evaluation of large language models for code. In International Conference on Learning Representations, Vol. 2025, p. 58791–58831. Cited by: §1. Ji et al. (2026) K. Ji, Q. Di, H. Zhao, Q. Zhao, and Q. Gu On the optimal sample complexity of offline multi-armed bandits with kl regularization. arXiv preprint arXiv:2605.02141. Cited by: Remark B.2, §2. Jimenez et al. (2024) C. E. Jimenez, J. Yang, A. Wettig, S. Yao, K. Pei, O. Press, and K. Narasimhan Swe-bench: can language models resolve real-world github issues?. In International Conference on Learning Representations, Vol. 2024, p. 54107–54157. Cited by: §1. Kalvit and Zeevi (2020) A. Kalvit and A. Zeevi From finite to countable-armed bandits. Advances in neural information processing systems 33, p. 8259–8269. Cited by: §2. Kano et al. (2019) H. Kano, J. Honda, K. Sakamaki, K. Matsuura, A. Nakamura, and M. Sugiyama Good arm identification via bandit feedback. Machine Learning 108 (5), p. 721–745. Cited by: §1. Katz-Samuels and Jamieson (2020) J. Katz-Samuels and K. Jamieson The true sample complexity of identifying good arms. In International Conference on Artificial Intelligence and Statistics, p. 1781–1791. Cited by: §2. Lai and Robbins (1985) T. L. Lai and H. Robbins Asymptotically efficient adaptive allocation rules. Advances in applied mathematics 6 (1), p. 4–22. Cited by: §2. Lattimore and Szepesvári (2020) T. Lattimore and C. Szepesvári Bandit algorithms. Cambridge University Press. Cited by: §A.1, §B.1, §B.1, §B.2, Appendix E, §3, §5. Lattimore (2018) T. Lattimore Refining the confidence level for optimistic bandit strategies. Journal of Machine Learning Research 19 (20), p. 1–32. Cited by: §1. Liu et al. (2024) H. Liu, A. Tajdini, A. Wagenmaker, and C. Wei Corruption-robust linear bandits: minimax optimality and gap-dependent misspecification. Advances in Neural Information Processing Systems 37, p. 24277–24325. Cited by: §2. Locatelli and Carpentier (2018) A. Locatelli and A. Carpentier Adaptivity to smoothness in x-armed bandits. In Conference on Learning Theory, p. 1463–1492. Cited by: §2. Marinov and Zimmert (2021) T. V. Marinov and J. Zimmert The pareto frontier of model selection for general contextual bandits. Advances in Neural Information Processing Systems 34, p. 17956–17967. Cited by: §2. Panda et al. (2025) P. Panda, R. Magazine, C. Devaguptapu, S. Takemori, and V. Sharma Adaptive llm routing under budget constraints.. In EMNLP (Findings), p. 23934–23949. Cited by: §1. Pryzant et al. (2023) R. Pryzant, D. Iter, J. Li, Y. Lee, C. Zhu, and M. Zeng Automatic prompt optimization with “gradient descent” and beam search. In Proceedings of the 2023 conference on empirical methods in natural language processing, p. 7957–7968. Cited by: §1. Truong (2026) L. V. Truong Optimal best-arm identification under fixed confidence with multiple optima. IEEE Transactions on Information Theory. Cited by: §2. Tsybakov and Zaiats (2009) A. B. Tsybakov and V. Zaiats Introduction to nonparametric estimation. Vol. 11, Springer. Cited by: Appendix E. Wang et al. (2008) Y. Wang, J. Audibert, and R. Munos Algorithms for infinitely many-armed bandits. Advances in Neural Information Processing Systems 21. Cited by: §2. Wei et al. (2022) C. Wei, C. Dann, and J. Zimmert A model selection approach for corruption robust reinforcement learning. In International Conference on Algorithmic Learning Theory, p. 1043–1096. Cited by: §2. Yu (1997) B. Yu Assouad, fano, and le cam. In Festschrift for Lucien Le Cam: research papers in probability and statistics, p. 423–435. Cited by: Appendix E. Zhao et al. (2023) H. Zhao, J. He, D. Zhou, T. Zhang, and Q. Gu Variance-dependent regret bounds for linear bandits and reinforcement learning: adaptivity and computational efficiency. In The Thirty Sixth Annual Conference on Learning Theory, p. 4977–5020. Cited by: §2. Zhu and Nowak (2020) Y. Zhu and R. Nowak On regret with multiple best arms. Advances in Neural Information Processing Systems 33, p. 9050–9060. Cited by: §1, §1, §2, §2, §4.1, §4, §4, §5, §5, Remark 6.3, Abstract, Algorithm 1. Zhu and Nowak (2022) Y. Zhu and R. Nowak Pareto optimal model selection in linear bandits. In International Conference on Artificial Intelligence and Statistics, p. 6793–6813. Cited by: §2.