Paper deep dive
Gap Entropy and Almost Instance-Wise Optimal Best-Arm Identification
Jiarui Yao, Jiaxi Zhao, Xiangxin Zhou
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 94%
Last extracted: 9/20/2026, 3:43:22 AM
Summary
This paper resolves the gap-entropy and almost instance-wise optimality conjectures proposed by Chen and Li (2016) regarding the best-arm identification problem. The authors prove that the order-oblivious instance-wise lower bound is characterized by the gap entropy, specifically $\Theta(H(I)[\log(1/\delta) + \text{Ent}(I)])$, where $H(I)$ is the sum of inverse squared gaps and $\text{Ent}(I)$ is the entropy of normalized gap group complexities. Furthermore, they present a single $\delta$-correct algorithm that achieves an expected sample complexity matching this lower bound up to an additive two-arm term, without requiring prior knowledge of the gaps. The main theorems have been formally verified in Lean 4.
Entities (8)
Relation Signals (5)
This Paper → resolves → Gap Entropy
confidence 98% · In this paper, we resolve their gap-entropy and almost instance-wise optimality conjectures.
This Paper → formalizedin → Lean 4
confidence 95% · The main theorems have been formalized and proved in Lean 4.
Chen and Li → proposedconjecture → Gap Entropy
confidence 95% · Chen and Li [2016] conjectured that the instance-wise sample complexity of this problem is characterized by the gap entropy
H(I) → definedas → Sum of inverse squared gaps
confidence 92% · let H(I)=\sum_{i=2}^{n}\Delta_{[i]}^{-2}
Aronow et al. → alsoresolves → Gap Entropy
confidence 90% · Concurrent work by Aronow et al. (2026) also resolves both conjectures
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:In the best-arm identification problem, we are given $n$ stochastic arms with unknown means and wish to identify the arm with the largest mean with probability at least $1-\delta$, using as few samples as possible. We consider independent Gaussian rewards with unit variance and means in $[0,1]$. Chen and Li [2016] conjectured that the instance-wise sample complexity of this problem is characterized by the gap entropy, up to an additive term arising from the two-arm problem. In this paper, we resolve their gap-entropy and almost instance-wise optimality conjectures. For an instance $I$, let $\Delta_{[i]}$ be the gap between the largest and the $i$-th largest mean, let $H(I)=\sum_{i=2}^{n}\Delta_{[i]}^{-2}$, and let Ent$(I)$ denote the entropy of the normalized complexities of its dyadic gap groups. For every $0<\delta<0.1$, we show that the order-oblivious instance-wise lower bound is $ {\Theta} (H(I)[\log(1/\delta)+Ent(I)]). $ We also give a single $\delta$-correct algorithm with expected sample complexity $ O ( H(I)[\log(1/\delta)+Ent(I)] +D\log(e+\log(e+D))),D=\Delta_{[2]}^{-2}, $ without prior knowledge of the gaps. Our lower bound removes the dyadic-gap and monotonicity restrictions of previous work, and our upper bound removes the additional polylogarithmic factor multiplying the two-arm term. Thus, a single algorithm attains the instance-wise lower bound up to an additive two-arm term. The main theorems have been formalized and proved in Lean 4.
Tags
Links
- Source: https://arxiv.org/abs/2609.13703v1
- Canonical: https://arxiv.org/abs/2609.13703v1
Trouble viewing inline? Open PDF directly →
Full Text
164,646 characters extracted from source content.
Expand or collapse full text
Gap Entropy and Almost Instance-Wise Optimal Best-Arm Identification Jiarui Yao †thanks: Alphabetical order.†thanks: UIUC; e-mail: jiarui14@illinois.edu. Jiaxi Zhao11footnotemark: 1 †thanks: NUS; e-mail: jiaxi.zhao@u.nus.edu Xiangxin Zhou11footnotemark: 1 †thanks: Tencent Hunyuan; e-mail: zhouxiangxin1998@gmail.com Abstract In the best-arm identification problem, we are given n stochastic arms with unknown means and wish to identify the arm with the largest mean with probability at least 1−δ1-δ, using as few samples as possible. We consider independent Gaussian rewards with unit variance and means in [0,1][0,1]. Chen and Li (2016) conjectured that the instance-wise sample complexity of this problem is characterized by the gap entropy, up to an additive term arising from the two-arm problem. In this paper, we resolve their gap-entropy and almost instance-wise optimality conjectures. For an instance I, let Δ[i] _[i] be the gap between the largest and the i-th largest mean, let H(I)=∑i=2nΔ[i]−2H(I)= _i=2^n _[i]^-2, and let Ent(I) (I) denote the entropy of the normalized complexities of its dyadic gap groups. For every 0<δ<0.10<δ<0.1, we show that the order-oblivious instance-wise lower bound is Θ(H(I)[log(1/δ)+Ent(I)]). (H(I) [ (1/δ)+ (I) ] ). We also give a single δ-correct algorithm with expected sample complexity O(H(I)[log(1/δ)+Ent(I)]+Dlog(e+log(e+D))),D=Δ[2]−2,O (H(I) [ (1/δ)+ (I) ]+D (e+ (e+D) ) ), D= _[2]^-2, without prior knowledge of the gaps. Our lower bound removes the dyadic-gap and monotonicity restrictions of previous work, and our upper bound removes the additional polylogarithmic factor multiplying the two-arm term. Thus, a single algorithm attains the instance-wise lower bound up to an additive two-arm term. The main theorems have been formalized and proved in Lean 4. 1 Introduction In fixed-confidence best-arm identification, one procedure must identify the arm of largest mean with probability at least 1−δ1-δ on every admissible instance, deciding where to sample and when to stop (Even-Dar et al., 2006; Kaufmann et al., 2016; Garivier and Kaufmann, 2016). Its difficulty is governed by the separations between means and by the cost of discovering which separations matter (Simchowitz et al., 2017). Let i[1]i_[1] denote the best-arm label and Δi _i the gap of arm i. The instance complexity is H=∑i≠i[1]Δi−2H= _i≠ i_[1] _i^-2, and Hlog(1/δ)H (1/δ) captures the confidence requirement (Mannor and Tsitsiklis, 2004) but not the cost of discovering an unknown gap scale: even with two arms, an iterated-logarithm obstruction arises (Farrell, 1964). The order-oblivious instance-wise lower bound of Chen and Li (2016) separates these effects: at each instance it takes the infimum over δ-correct algorithms after averaging over all label permutations. They conjectured that it is characterized by the Shannon entropy of the normalized complexities of the gap groups, and that a single algorithm attains it with only the additive two-arm term. An algorithm chosen separately for each target instance may have parameters adapted to that instance while remaining correct on every input. In contrast, one algorithm satisfying the bound on all instances must work without these parameters; likewise, a lower bound on a sub-instance does not yield one on the original instance for an arbitrary algorithm. Chen et al. (2017) obtain the entropy main term with an additional polylogarithmic factor on the two-arm term, and a lower bound on a suitable sub-instance that transfers to the same instance under monotonicity. We prove both conjectures in the Gaussian model stated by Chen and Li (2016), for the measurable algorithms of Section 2 and with the explicit positive truncation of the two-arm term fixed there; Appendix H shows that the instance-wise lower bound is unchanged when algorithms may use arbitrary standard Borel internal randomness, and that algorithms specified by history-dependent probability kernels satisfy the lower bound. The proof has two main components. Concurrent work by Aronow et al. (2026) also resolves both conjectures, with substantial overlap in the lower-bound argument and different upper-bound constructions; Section 3.1 compares the results and methods. A lower bound using counts on the original instance. After symmetrization, designate a suboptimal arm and raise it to the best mean; a simultaneous change at one other arm makes the resulting distribution with two best arms independent of the designated gap. Both changes are charged, through a latent-variable coupling, to expected numbers of samples on the original instance. Choosing the largest gap among representatives with small normalized expected numbers of samples gives a common comparison distribution. Selecting disjoint stopping events under that distribution bounds the number of such groups and gives a bound on a sum of exponentials; nonnegativity of relative entropy then gives the complexity-weighted entropy term. The argument assumes no monotonicity and uses no bound on the expected number of samples on another instance. A single algorithm with an additive two-arm term. The algorithm performs successive elimination runs with geometrically increasing bounds on the total weight and number of samples, reuses one reference estimate within a scale, and retains at least the empirical upper half after every elimination. Its ordinary error allocation is proportional to the weight assigned to a call; an additional penalty, summable in the run index, applies only to calls with at most seven active arms, so its sampling cost is charged to D rather than to H. Correctness is proved by grouping outputs according to fixed nested sets of arms near the original best at the terminal scale: small budgets force many underestimation events, and large budgets are controlled by a bound based on the ordering of empirical means for a call that eliminates all but at most one arm in such a set; the grouping is summable uniformly in the number of arms and gap groups. Formal verification. The definitions of Section 2, Theorems 2.1 and 2.2 with explicit constants, and the results on the algorithm model of Appendix H have been formalized and verified in Lean 4 with Mathlib11 1 https://github.com/leanprover-community/mathlib4; Appendix I states precisely what is verified and how the formal proofs differ from the presentation here. The full Lean 4 code can be found in https://github.com/zhouxiangxin1998/GapEntropy. 2 Problem formulation and main results 2.1 Observation model and statistical objective An instance is a vector I=(μ1,…,μn)∈[0,1]nI=( _1,…, _n)∈[0,1]^n, where n≥2n≥ 2 and the maximum is unique. Write [n]=1,…,n[n]=\1,…,n\. Arm i∈[n]i∈[n] produces independent (μi,1)N( _i,1) observations. Let i[r]i_[r] be the label of the arm with the rrth largest mean, breaking ties between suboptimal arms by label, and write μ[r]=μi[r] _[r]= _i_[r]. Thus i[1]=argmaxi∈[n]μi,Δi=μ[1]−μi,Δ[r]=Δi[r]=μ[1]−μ[r].i_[1]= _i∈[n] _i, _i= _[1]- _i, _[r]= _i_[r]= _[1]- _[r]. The ordered gaps satisfy 0=Δ[1]<Δ[2]≤⋯≤Δ[n]≤10= _[1]< _[2]≤·s≤ _[n]≤ 1. An algorithm has an internal random seed, a sequence of independent standard Gaussian variables independent of all rewards. At each time it applies a measurable rule to its finite observed history (the labels sampled so far and their observations) and its seed, and either requests one observation from an arm or returns a label; a return is absorbing. Let τ be the first return time, with τ=∞τ=∞ if no label is returned, and ı the returned label. Sample complexity means the unconditional expectation TA(I)=IτT_A(I)=E_Iτ, with no computational-time requirement. An algorithm is δ-correct if ℙI(τ<∞,ı^=i[1])≥1−δP_I (τ<∞, =i_[1] )≥ 1-δ for every admissible instance at every arm count n≥2n≥ 2. An algorithm on singleton inputs simply returns the only arm. Appendix H shows that the instance-wise lower bound below is unchanged if the internal random seed is drawn from an arbitrary standard Borel probability space, and that algorithms specified by history-dependent probability kernels satisfy the lower bound; the upper-bound algorithms use no internal randomness. Time counts observations: until return, the algorithm requests one observation at each integer time, so a nonreturning path has an infinite observation stream. Let AtA_t be the label sampled at time t. Conditional on the information available before that sample, the observation has law (μAt,1)N( _A_t,1). Define Ni(t)=∑s=1t∧τAs=iN_i(t)= _s=1^t τ1\A_s=i\ and let Ni(τ)N_i(τ) denote the total count, allowing +∞+∞. Then ∑iNi(t)=t∧τ _iN_i(t)=t τ and TA(I)=∑iINi(τ)T_A(I)= _iE_IN_i(τ) by monotone convergence. Thus the complexity charges every observation, including observations on erroneous trajectories. Correctness alone does not imply finite expectation; the upper bounds establish both properties separately. 2.2 The instance-wise lower bound and the gap groups For a permutation π of the labels, let πIπ I denote the instance obtained by moving arm i to label π(i)π(i). The order-oblivious instance-wise lower bound of Chen and Li (2016, Definition 3.1) is ℒ(I,δ)=infA:A is δ-correct1n!∑π∈nTA(πI).L(I,δ)= _A:\ A is δ-correct 1n! _π∈ S_nT_A(π I). (2.1) The infimum is taken separately at each I. Algorithms in this infimum may have different fixed parameters chosen for different target instances, but each must remain correct on every admissible input. The single algorithm below takes only the arms and δ as inputs. For integers k≥0k≥ 0, define Gk=i≠i[1]:2−k≤Δi<2−k+1,Hk=∑i∈GkΔi−2,H=∑kHk,pk=Hk/H.G_k= \i≠ i_[1]:2^-k≤ _i<2^-k+1 \, H_k= _i∈ G_k _i^-2, H= _kH_k, p_k=H_k/H. (2.2) The gap 11 belongs to G0G_0. Zero-mass groups are omitted from entropy sums, and Ent(I)=∑k:pk>0pklog(1/pk) (I)= _k:p_k>0p_k (1/p_k). For any discrete distribution q, Ent(q) (q) denotes its Shannon entropy, with 0log(1/0)=00 (1/0)=0; for discrete random variables, Ent denotes the entropy of their law. Throughout, D=Δ[2]−2,L=log(1/δ),ℓ(D)=log(e+log(e+D)).D= _[2]^-2, L= (1/δ), (D)= (e+ (e+D) ). (2.3) When the instance is fixed, we suppress its argument in H=H(I)H=H(I), D=D(I)D=D(I), and the gap-group quantities. All unmarked logarithms are natural. Constants in O, Ω , and Θ are universal, independent of n, δ, and the instance. We write KL for relative entropy and kl for its Bernoulli specialization. Table 1 summarizes the notation, with nk=|Gk|n_k=|G_k| and K=maxk:Hk>0K= \k:H_k>0\. Table 1: Principal instance quantities and their roles. Notation Meaning i[r]i_[r], μ[r] _[r] Label and mean of the arm with the rrth largest mean; i[1]i_[1] is the best-arm label. Δi _i, Δ[r] _[r], D Gap of label i, gap at rank r, and inverse squared smallest positive gap. HkH_k, H Total complexity of group k and complexity of the instance. pkp_k, Ent(I) (I) Normalized group complexities and their Shannon entropy. nkn_k, K Number of suboptimal arms in group k and the largest index of a nonempty group. L, ℓ(D) (D) Logarithmic confidence term and truncated iterated logarithm. Gap entropy weights each group by its total complexity rather than its number of arms. If b groups are nonempty, then 0≤Ent(I)≤logb0≤ (I)≤ b, with the upper equality when all HkH_k are equal. A single nonempty group has zero entropy. For any integer K≥1K≥ 1, take best mean 11 and nk=4K−kn_k=4^K-k arms of gap 2−k2^-k for each 1≤k≤K1≤ k≤ K. Then Hk=4KH_k=4^K, H=K4KH=K4^K, and Ent(I)=logK (I)= K, despite the very different group sizes. This example isolates the cost of exploring several groups with comparable total complexities. These quantities describe the instance and are not supplied to the single algorithm. 2.3 Main results Theorem 2.1 (Resolution of the gap-entropy conjecture). For every instance in the model above and every 0<δ<0.10<δ<0.1, ℒ(I,δ)=Θ(H(I)[log(1/δ)+Ent(I)]).L(I,δ)= \! (H(I) [ (1/δ)+ (I) ] ). (2.4) Theorem 2.2 (A single almost instance-wise optimal algorithm). For every 0<δ<0.10<δ<0.1 there is one δ-correct algorithm whose expected stopping time is finite on every admissible instance and which satisfies TA(I)=O(H(I)[log(1/δ)+Ent(I)]+Dℓ(D)).T_A(I)=O\! (H(I) [ (1/δ)+ (I) ]+D (D) ). (2.5) It receives no estimate of any gap, H, or Ent(I) (I). Together these theorems imply TA(I)=O(ℒ(I,δ)+Dℓ(D))T_A(I)=O (L(I,δ)+D (D) ), establishing Conjectures 3.5 and 3.2 of Chen and Li (2016) for the algorithms defined above, under the following convention. The additive term of Conjecture 3.2 is written there as Δ[2]−2lnlnΔ[2]−1 _[2]^-2 _[2]^-1, which is negative for Δ[2]∈(e−1,1) _[2]∈(e^-1,1) and undefined at the admissible gap Δ[2]=1 _[2]=1; a positive convention is therefore required. We use g(Δ)=max1,loglog(1/Δ)g( )= \1, (1/ ) \ for 0<Δ<10< <1 and g(1)=1g(1)=1. For every 0<Δ≤10< ≤ 1, g(Δ)≤ℓ(Δ−2)≤7g(Δ)g( )≤ ( ^-2)≤ 7g( ) (see (H.6)), so the two positive truncations give equivalent statements; as Δ[2]→0 _[2]→ 0 both are loglog(1/Δ[2])(1+o(1)) (1/ _[2]) (1+o(1) ). A uniform O(D)O(D) comparison with the untruncated expression does not hold near Δ[2]=1 _[2]=1. Corollary H.7 makes the two regimes explicit: for Δ[2]≤e−e _[2]≤ e^-e the bound holds with the untruncated Δ[2]−2loglog(1/Δ[2]) _[2]^-2 (1/ _[2]), and for Δ[2]>e−e _[2]>e^-e the additive term is absorbed into O(ℒ(I,δ))O (L(I,δ) ). The proofs give explicit constants. Theorem B.1 shows ℒ(I,δ)≥H(I)max2kl(1−δ,δ),Ent(I)/4≥15H(I)[log(1/δ)+Ent(I)],L(I,δ)≥ H(I) \2 (1-δ,δ), (I)/4 \≥ 15H(I) [ (1/δ)+ (I) ], where kl is the binary relative entropy; the universal constants in the upper bounds are large and are not optimized. Section 4 presents both directions of Theorem 2.1; Section 5 gives the single algorithm and the key arguments for Theorem 2.2. Appendix A collects the probabilistic tools and elimination guarantees used in these proofs. Complete proofs appear in Appendices B–F. Appendix G records consequences and the normalization to general known variances, and Appendix I describes the machine-checked verification of the main statements. The instance-wise upper bound is independent of the construction of the single algorithm. 3 Related work Gap-dependent complexity and elimination. Best-arm identification separates the cost of distinguishing a fixed mean vector from the additional cost of adapting to unknown gaps. Mannor and Tsitsiklis (2004) established the classical gap-dependent lower-bound scale H(I)log(1/δ)H(I) (1/δ). The sequential-testing lower bound of Farrell (1964) supplies the iterated-logarithmic obstruction in the two-arm problem as the gap tends to zero. This is an asymptotic obstruction across gap values, rather than an additional lower bound that must hold at every fixed instance for every δ-correct algorithm. That distinction motivates the order-oblivious instance-wise lower bound and the additive allowance in Chen and Li (2016). Elimination methods provide a basic route to efficient exploration. Median elimination and action elimination (Even-Dar et al., 2002; Even-Dar et al., 2006) use confidence guarantees to progressively discard unpromising arms. Median elimination finds an ε -optimal arm using O(nε−2log(1/δ))O (n ^-2 (1/δ) ) samples; our reference-selection routine uses this principle, with its Gaussian guarantee proved in the paper. Karnin et al. (2013) and Jamieson et al. (2014) obtained bounds with iterated-logarithmic dependence on the individual gaps. The unified gap-based exploration framework of Gabillon et al. (2012) gives related sampling strategies for fixed-confidence and fixed-budget objectives; KL-based confidence intervals also sharpen subset-selection guarantees (Kaufmann and Kalyanakrishnan, 2013). These bounds explain why eliminating the cost of scale adaptation from every suboptimal arm is a substantive part of the almost instance-wise optimality question. Gap entropy and instance-wise optimality. Chen and Li (2015) improved earlier upper bounds and used a refined sign-testing lower bound to obtain best-arm lower bounds beyond the classical confidence term. Chen and Li (2016) defined gap entropy using the normalized complexity of gap groups and posed two precise conjectures. Their Conjecture 3.5 asks whether the order-oblivious instance-wise lower bound is Θ(H(I)[log(1/δ)+Ent(I)]) (H(I) [ (1/δ)+ (I) ] ). Their Conjecture 3.2 asks for one δ-correct algorithm whose expected number of samples is within a constant factor of that instance-wise lower bound plus the two-arm iterated-logarithmic term. The infimum defining the instance-wise lower bound allows a different δ-correct algorithm for each target instance, whereas the latter conjecture requires a single algorithm that adapts to all instances. The direct follow-up of Chen et al. (2017) proves both an upper bound and a restricted form of the entropy lower bound. Their Theorem 1.11 gives expected sample complexity O(H(I)[log(1/δ)+Ent(I)]+Δ[2]−2loglogΔ[2]−1polylog(n,δ−1)),O\! (H(I) [ (1/δ)+ (I) ]+ _[2]^-2 _[2]^-1polylog(n,δ^-1) ), with the customary nonnegative interpretation of the iterated logarithm. Their Theorem 1.12 states that, for every instance I whose suboptimal gaps are all of the form 2−k2^-k with k≥1k≥ 1 an integer (their discrete instances), every δ-correct algorithm with δ<0.01δ<0.01 incurs Ω(H(I)[log(1/δ)+Ent(I)]) (H(I) [ (1/δ)+ (I) ] ) samples on some sub-instance I′I obtained by deleting suboptimal arms. Their Corollary 1.13 transfers the bound to I itself for monotone algorithms, meaning algorithms whose expected number of samples cannot increase when suboptimal arms are removed. The sub-instance statement alone does not give the lower bound on the original instance for an arbitrary algorithm. For the algorithms of Section 2, the results proved here address these specific differences from Chen et al. (2017): the lower bound concerns the original instance under permutation averaging, permits arbitrary positive gaps and 0<δ<0.10<δ<0.1, and imposes no monotonicity assumption. The uniform upper bound has the entropy main term and an additive two-arm term without the displayed polylog(n,δ−1)polylog(n,δ^-1) factor, under the positive truncation convention of Section 2. Information bounds and the confidence limit. Kaufmann et al. (2014) analyze distribution-dependent complexities in two-arm testing. Kaufmann et al. (2016) develop a general change-of-measure inequality for adaptive bandit experiments and lower bounds for identifying the best arms. Garivier and Kaufmann (2016) characterize the optimal allocation through an information optimization problem and prove asymptotic optimality of Track-and-Stop as δ→0δ→ 0 for a fixed instance. This limit determines the leading confidence cost, but does not by itself control the additional dependence on unknown gaps uniformly over instances. Simchowitz et al. (2017) make the distinction between moderate confidence and the vanishing-error limit explicit: their simulator method yields adaptive-sampling lower bounds that capture costs of learning where to sample. Our lower bound likewise addresses adaptation, using the original-instance counts and the common comparison distribution described in Section 4. Degenne et al. (2019) obtain finite-confidence guarantees for more general pure-exploration problems by viewing the information optimization as a game and using no-regret learners. Top-two sampling. An alternative to elimination is to sample from a pair of candidate arms. Russo (2016) introduces Bayesian top-two allocation rules and analyzes their posterior concentration rates. Shang et al. (2020) establish fixed-confidence sample-complexity guarantees for Top-Two Thompson Sampling and a transportation-cost variant with Gaussian rewards. Jourdan et al. (2022) extend the analysis to bounded reward distributions and permit alternative choices of the leading arm. Jourdan and Degenne (2023) give nonasymptotic bounds on expected sample complexity for a UCB-based top-two algorithm, while You et al. (2023) develop information-directed selection between the two candidates and obtain asymptotic optimality for Gaussian best-arm identification. These results study how to learn effective sampling allocations; the particular target here is the gap-entropy benchmark with only an additive two-arm adaptation term. Sequential stopping and time-uniform inference. Confidence sequences provide another perspective on the iterated-logarithmic cost of sequential inference. Howard et al. (2021) construct nonasymptotic confidence sequences valid over an unbounded time horizon, including boundaries with iterated-logarithmic behavior. Kaufmann and Koolen (2021) derive time-uniform deviation bounds under adaptive bandit sampling and apply them to likelihood-ratio stopping rules. Our upper-bound proof instead allocates failure probabilities across finite elimination calls; the challenge is to make that allocation adapt to the unknown complexity of the gap groups. Fixed budgets and structured exploration. With a fixed sampling budget, the objective is to control the error of the final recommendation. Successive Rejects (Audibert et al., 2010) and Sequential Halving (Karnin et al., 2013) are central elimination methods in this setting. The lower bounds of Carpentier and Locatelli (2016) show that adaptation to an unknown instance can require a logarithmic factor in the number of arms in fixed-budget guarantees. These results concern a different performance criterion from the expected stopping time studied here. Other extensions change the structure of the identification task: Chen et al. (2014) study the selection of an optimal feasible subset, and linear-bandit methods exploit information shared across arm means (Soare et al., 2014; Tao et al., 2018; Jedra and Proutiere, 2020). Huang et al. (2017) consider actions whose values depend on noisy component observations, motivated by minimax game search; Degenne and Koolen (2019) treat pure-exploration tasks with multiple correct answers. Our theorems concern independent Gaussian arms with a unique best arm; extensions of gap entropy to these structured objectives would require additional analysis. 3.1 Concurrent resolution of the two conjectures Aronow et al. (2026), posted on September 9, 2026, also resolve the gap-entropy and almost instance-wise optimality conjectures. We briefly compare with their results here. Their Theorems 1.1–1.2 give the same orders as Theorems 2.1–2.2 on Gaussian instances; their upper bounds additionally cover independent 11-sub-Gaussian rewards. Our theorems are stated for Gaussian rewards. The opposite endpoint conventions for dyadic groups change entropy by at most log2 2: each cell of either partition intersects at most two cells of the other, so both conditional entropies are at most log2 2. Their regularized two-arm term is equivalent to Dℓ(D)D (D) up to absolute constants. These conventions therefore leave the rates unchanged. Lower bound. The central mechanism is shared: permutation symmetrization, a change of at most two arm means producing a common tied reference law, and disjoint sample-count events followed by an entropy inequality. Both arguments charge the changes to counts on the original instance. Their Section 2 uses averages within gap groups, normalized by the dyadic sampling scale. Our Appendix B instead works with exact-gap counts αd=d2td _d=d^2t_d and selects a minimizing representative in each group. Our packing step also uses the δ bound on the total reference probability of the selected return events, yielding ∑ke−4αk<10δ _ke^-4 _k<10δ. These are differences within a closely related proof strategy. Instance-wise upper bound. Their Section 3 uses mixtures of exponential supermartingales around a target-dependent threshold between the two largest means, followed by a confirmation test. Our Appendix C uses only the target’s group sizes to specify a finite elimination schedule and smoothed confidence weights. Its thresholds are estimated from the active arms, and prescribed size reductions bound every run’s cost on every input. Both constructions repeat trials and interleave a globally correct fallback to ensure termination away from the target. A single algorithm. Both methods use increasing budgets, confidence allocation proportional to sampling weights, and bounds on joint premature eliminations. Their Sections 4–6 retain the Median–Fraction–Eliminate structure of Chen et al. (2017); the fraction thresholds depend on the number of rounds remaining. Their error analysis separates hard and easy arms according to the stage budget. Our algorithm (Appendix D) reuses one reference estimate per scale, retains at least the empirical upper half, and adds a summable run-index penalty only when at most seven arms remain. Our correctness proof groups outputs by fixed nested sets of near-optimal arms and combines stochastic domination with an empirical-ordering bound (Appendix E). These features provide a different way to obtain the additive two-arm cost. Our contribution also includes an explicit measurable-policy treatment and Lean 4 verification of the main statements and policy-model extensions. Appendix I specifies the scope of that verification, including the differences between the formal witnesses and the algorithms presented here. 4 Characterizing the order-oblivious instance-wise lower bound We explain the two directions of Theorem 2.1. Throughout, I is a Gaussian instance with a unique best arm in the model of Section 2, and 0<δ<1/100<δ<1/10. Complete proofs appear in Appendices B and C. A common comparison distribution using samples from the original instance. Randomly relabeling any δ-correct algorithm makes its expected cost on I equal to its permutation average. For this symmetrized algorithm, let tdt_d be the expected number of samples from an individual arm with exact gap d, and set αd=d2td _d=d^2t_d. Permutation equivariance gives every arm with gap d the same expected count on every labeling of the target; we may assume these counts are finite, since otherwise there is nothing to prove. Let PdP_d place a gap-d arm at label 11 and uniformly label the remaining target multiset. Let QaQ_a instead give label 11 mean μ[1] _[1], with the remaining labels containing the target multiset minus one gap-a arm. Thus QaQ_a has two best arms. Correctness implies Qa(return a label other than 1)≤δQ_a(return a label other than 1)≤δ: lower its other best mean by ε , apply correctness with label 11 uniquely best, and pass first to the finite-transcript limit ε↓0 0, then to infinite time. Lowering that mean keeps the perturbation admissible even when μ[1]=1 _[1]=1; no termination assumption at the tie is needed. For a≠da≠ d, couple PdP_d to QaQ_a by raising label 11 to μ[1] _[1] and changing a uniformly selected gap-a arm to gap d. The resulting background is uniformly labeled, including when gaps have multiplicities. The second change restores the gap multiplicity lost at label 11. Uniform labeling makes the comparison law depend only on a, so different source scales can share it. Keep the source assignment and selected label latent, with the same prior in both experiments. Stop each transcript at return or after m total observations, denoting its law by a superscript (m)(m). The finite-horizon Gaussian KL bound (Lemma A.1), followed by discarding the latent variables, gives KL(Pd(m)∥Qa(m))≤12[d2td+(a−d)2ta]≤12(αd+αa),a≥d. (P_d^(m) \|Q_a^(m) )≤ 12 [d^2t_d+(a-d)^2t_a ]≤ 12( _d+ _a), a≥ d. (4.1) When a=da=d, only label 11 changes and the bound is αd/2 _d/2. Binary data processing then gives αd≥2kl(1−δ,δ)≥L _d≥ 2 (1-δ,δ)≥ L. The hidden selection is independent of observations conditional on the source assignment. Consequently all costs in (4.1) are measured on the original target, without a monotonicity assumption or a transfer of expected sample complexity between different instances. Disjoint stopping events imply the entropy lower bound. We adapt the stopping-event argument of Chen et al. (2017, Appendices D.2–D.3) to the comparison above. In each nonempty group choose a gap minimizing αd _d, and denote the minimum by αk _k. Among representatives with αk≤x _k≤ x, choose the largest gap a, whenever this set is nonempty. Lemma B.4 gives corresponding stopping events EdE_d with Qa(Ed)≥e−2x/4Q_a(E_d)≥ e^-2x/4 under this common reference distribution. Selecting disjoint sample-count windows and using Qa(return a label other than 1)≤δQ_a(return a label other than 1)≤δ bounds the number of these representatives. Integrating that bound yields Z:=∑ke−4αk<10δ<1.Z:= _ke^-4 _k<10δ<1. (4.2) The reference gap depends on x; Appendix B gives the window selection and integration. Nonnegativity of relative entropy gives 4∑kpkαk≥Ent(I)−logZ≥Ent(I)4 _kp_k _k≥ (I)- Z≥ (I). The target cost is at least H∑kpkαkH _kp_k _k by groupwise minimization. Combining this with αk≥2kl(1−δ,δ) _k≥ 2 (1-δ,δ) gives the lower bound Hmax2kl(1−δ,δ),Ent(I)/4≥H[L+Ent(I)]/5H \2 (1-δ,δ), (I)/4 \≥ H [L+ (I) ]/5. An algorithm with a fixed target instance that remains δ-correct. For the upper bound, fix the group sizes of the target instance as algorithmic constants. Let n be the number of arms in that instance and K the largest index of a nonempty group. This is permitted inside the pointwise infimum defining ℒL, but correctness must still hold on every input. Use weights defined from the group sizes Wk=4k(1+∑j≥k|Gj|)W_k=4^k (1+ _j≥ k|G_j| ), for 0≤k≤K0≤ k≤ K, and qk=Wk/∑j=0KWjq_k=W_k/ _j=0^KW_j. Lemma A.5 gives total weight O(H)O(H) and normalized entropy O(1+Ent(I))O (1+ (I) ). A finite run allocates confidence proportional to qkq_k, with geometric subdivision among same-scale raw threshold-elimination calls, returning R0R_0 without enlargement. It aborts whenever a required halving fails. The group sizes determine how many arms may remain at each scale; the final call at the target’s finest scale returns only if its retained set is a singleton. At tolerance d, a call selects a reference arm by median elimination (Even-Dar et al., 2002), estimates its mean by z, and retains arms whose fresh empirical means satisfy xi≥z−d/2x_i≥ z-d/2. For s active arms and error budget α, Lemmas A.2–A.3 give a deterministic O(sd−2log(1/α))O (sd^-2 (1/α) ) sample budget and the required best-arm retention and halving guarantees. The imposed size reductions give a cost bound even after statistical failures. On every input with n arms, each run trajectory has deterministic cost BI(ε)=O(∑k=0KWklog1εqk)=O(H[log(1/ε)+Ent(I)]).B_I( )=O\! ( _k=0^KW_k 1 q_k )=O (H [ (1/ )+ (I) ] ). (4.3) The run’s incorrect-return probability is at most ε on every such input, while it succeeds with probability at least 1−ε1- on every labeling of the target. Repeat fresh runs with εt=δ2−(t+2) _t=δ 2^-(t+2) and interleave an independent δ/2δ/2-correct confidence-interval algorithm having finite expected stopping time on every input with a unique best arm. Other arm counts use the fallback alone. This fallback supplies termination even when the input differs from the target instance. Errors sum to at most δ, and interleaving costs at most a factor two. On the target, run t is reached with probability at most 2−t2^-t, so summing (4.3) gives O(H[L+Ent(I)])O (H [L+ (I) ] ) samples in expectation, uniformly over its labelings. 5 A single algorithm Theorem 2.2 requires one algorithm that works without knowing the instance’s gaps, complexity, or entropy. We describe the construction and the main proof arguments; the complete procedure, correctness proof, and analysis of the expected sample complexity are Appendices D, E, and F. The assumptions remain independent unit-variance Gaussian observations, means in [0,1][0,1], a unique best arm, and 0<δ<0.10<δ<0.1. 5.1 Sample budgets and confidence allocation Write L=log(1/δ)L= (1/δ) and γ=δ/1024γ=δ/1024. Run j=0,1,…j=0,1,… starts with all arms active and fresh observations, and has deterministic budgets hj=2j,Mj=1024hj,Qj=⌈CQhjL⌉.h_j=2^j, M_j=1024h_j, Q_j= C_Qh_jL . (5.1) The bound MjM_j controls the sum of the weights of calls, whereas QjQ_j bounds the number of samples; CQC_Q is the absolute constant C∗C_* of Appendix F, determined by the constants of Lemmas A.2 and A.3; any larger absolute constant also works. Within a run, tolerances are d=2−kd=2^-k, with k=0k=0 initially; the scale index increases only when elimination stalls. For a call on the current active set S, of size s≥2s≥ 2, define the weight w=sd−2w=sd^-2, the factor in its sample bound before the confidence logarithm. Its confidence parameter is α=γwMj(j+1)−2,2≤s≤7,1,s≥8.α=γ wM_j cases(j+1)^-2,&2≤ s≤ 7,\\ 1,&s≥ 8. cases (5.2) The size in this rule is the current active size at every call, so the branch can change after any call, including after a stall. Thus only calls with at most seven active arms incur the additional sample cost of this confidence allocation. We use standard concentration and median-elimination guarantees (Chen et al., 2017, Facts 5.1–5.2); Appendix A specifies the deterministic sample counts and the modified elimination rule. At scale entry, median elimination selects a reference arm within d/8d/8 of the active maximum, with failure probability at most α/16α/16. Independently estimate its mean by z, with accuracy d/16d/16 and failure budget βj,k=δ/[64(j+1)2(k+1)2] _j,k=δ/ [64(j+1)^2(k+1)^2 ]. At every call obtain fresh independent estimates xix_i for all active arms. The sample counts are mz=⌈512d−2log(2/βj,k)⌉,m=⌈512d−2log(128/α)⌉.m_z= 512d^-2 (2/ _j,k) , m= 512d^-2 (128/α) . (5.3) The numerical reference estimate is reused throughout the scale, even if its arm is removed, so it is paid for once per scale. The threshold retained set is R0=i:xi≥z−d/2R_0=\i:x_i≥ z-d/2\. Enlarge it by adding arms in decreasing empirical-mean order until at least ⌈s/2⌉ s/2 arms remain, so the result contains both R0R_0 and the empirical upper half. A singleton is returned only after this enlargement. If the enlarged set has size ⌈s/2⌉ s/2 , continue at the same scale; otherwise advance to the next scale. Before any sampling for a call, check its weight and its entire deterministic sample count against the remaining budgets; a failed reservation aborts the run and starts the next one. Every trajectory therefore satisfies ∑twt≤Mj _tw_t≤ M_j, ∑tαt≤γ _t _t≤γ, and Tj≤QjT_j≤ Q_j, including trajectories that eliminate the best arm. 5.2 Correctness via sets of near-optimal arms Summing a constant error allowance over infinitely many runs would not establish correctness. Our analysis instead separates errors in calls with at most seven arms from errors that require a large batch of eliminations. The key implication uses the original best mean μ[1] _[1], even after its arm has disappeared: the reference upper bound implies z−d/2≤μ[1]−7d/16z-d/2≤ _[1]-7d/16, so removing an arm with Δi≤d/8 _i≤ d/8 requires an underestimation event, xi−μi<−5d/16x_i- _i<-5d/16, whose conditional probability is at most (α/128)25(α/128)^25 by Gaussian tails. All reference-estimation failures together have probability below δ/16δ/16. Set η=γ/128η=γ/128 and p=2η25p=2η^25. Lemma E.1 couples all underestimation events in one adaptive run to independent Bernoulli indicators, one per original arm, with parameters at most p. It uses independent Poisson processes and a common clock whose predictable increments realize the exact Gaussian underestimation probabilities. The bound on the total weight limits its total elapsed clock time by p. This construction supplies independence on fixed disjoint arm sets despite adaptive sample counts. It never conditions on future reference upper bounds or on which set the algorithm ultimately selects. For calls with at most seven arms, the penalty in (5.2) gives a direct global bound: their total probability of underestimation in run j is at most 7η25(j+1)−507η^25(j+1)^-50, because ∑tαt25≤(∑tαt)25 _t _t^25≤ ( _t _t )^25, and these errors are charged once over the entire stream, for total probability at most 14η2514η^25. Outside reference failures and the charged errors in calls with at most seven arms, associate an output at its final tolerance d∗d_* with the set of near-optimal arms at that scale B=i:Δi<d∗/8,r=|B|,h=∑i∉BΔi−2,Ar=rpmax(1,r−1).B=\i: _i<d_*/8\, r=|B|, h= _i∉ B _i^-2, A_r=rp (1,r-1). (5.4) Although the final scale is random, the possible sets B form a fixed nested family determined by the instance, with at most one set of each cardinality. An incorrect singleton requires underestimation events on all but at most one arm in B, or on the original best when r=1r=1, giving probability at most ArA_r in one run. Fix B before applying the coupling and group runs according to the bound M on their total weight. For M≤h/192M≤ h/192, eliminations of arms outside B at tolerances dt≤8Δid_t≤ 8 _i, together with a possible output outside B, account for total complexity at most 64M+32M64M+32M. Arms outside B eliminated at larger tolerances therefore have total complexity at least h/2h/2. The independent Bernoulli variables for arms in B and outside B give the tail bound Ar(2ep)h/(64M)A_r(2ep)^h/(64M), which sums geometrically over these budgets. Constantly many budgets lie in h/192<M<h/192<M<h. For M≥h>0M≥ h>0, an incorrect output outside the already charged events requires a call with at least eight arms that reduces the active arms in B to at most one, or removes its sole remaining arm. Lemma E.2 handles this entire batch, which may begin with many arms in B and therefore requires a bound for their joint elimination: retaining the empirical upper half forces either underestimation of many arms in B or overestimation of many arms outside B with sufficiently large gaps, with probability at most 3η4(h/M)33η^4(h/M)^3. Taking the minimum of this bound and ArA_r gives 3Arη2(h/M)3/2 3A_rη^2(h/M)^3/2, again summable over budgets, without any independence between the underestimation events for arms in B and the elimination event. The lemma sums the conditional probabilities of elimination using the bound on the total weight of calls, so stalled scales add no union-bound factor. When h=0h=0, the retention rule makes such a large-set elimination event impossible. Finally, ∑rAr=O(p) _rA_r=O(p) and ∑rAr=O(p) _r A_r=O ( p ) make the union bound over this fixed family finite without a factor for empty scales. Together with the two global charges, the explicit constants give error probability below δ. 5.3 An unconditional expected sample complexity bound Correctness alone does not control stopping time. In a fresh run, accurate references and the usual best-arm retention and elimination events hold with probability at least 1−q01-q_0, where q0=γ+δ/16<1/2q_0=γ+δ/16<1/2. On this good event, a scale stalls only when the active size is within a constant factor of the number of arms closer than its tolerance. If ntn_t counts gaps in group t and K is the largest index of a nonempty group, the weights Wk=4k(1+∑t≥knt)W_k=4^k (1+ _t≥ kn_t ), for 0≤k≤K0≤ k≤ K, satisfy H≤∑k=0KWk<32H/3H≤ _k=0^KW_k<32H/3. Their normalized entropy is O(Ent(I)+1)O ( (I)+1 ) by Lemma A.5. Repeated halvings give the upper bound on the weights of calls wk,r≤4Wk(3/4)rw_k,r≤ 4W_k(3/4)^r, so runs on this good event with hj≥Hh_j≥ H fit the weight bound and finish by scale K. Applying the logarithmic factor in the sample bound to these weights yields baseline cost O(H[L+Ent(I)+1+log(hj/H)])O (H [L+ (I)+1+ (h_j/H) ] ). Calls with at most seven arms have total input size at most 7+4+2=137+4+2=13 per scale, so their extra confidence cost is O(4klog(j+1))O (4^k (j+1) ) at scale k and O(Dlog(j+1))O (D (j+1) ) in total. One reference estimate per scale adds O(D[L+log(j+1)+ℓ(D)])O (D [L+ (j+1)+ (D) ] ). Put Ψ=H[L+Ent(I)+1]+Dℓ(D) =H [L+ (I)+1 ]+D (D) and j∗=⌈log2(Ψ/L)⌉j_*= _2( /L) . For CQ≥C∗C_Q≥ C_*, every run j≥j∗j≥ j_* on the good event fits its entire sample budget, including each prefix and its next complete reservation. The choice is noncircular: C∗C_* bounds the declared cost of runs constrained only by the weight bound, computed without the sample budget. Independence of the fresh observations bounds the probability of reaching run j∗+tj_*+t by q0tq_0^t. Deterministic budgets control all other trajectories, hence Iτ≤∑j<j∗Qj+∑t≥0Qj∗+tq0t=O(Ψ).E_Iτ≤ _j<j_*Q_j+ _t≥ 0Q_j_*+tq_0^t=O( ). (5.5) The latter series converges because 2q0<12q_0<1. This proves finite expected stopping time, almost-sure termination, and the bound in Theorem 2.2, with no instance parameters supplied to the algorithm. 6 Conclusion For independent unit-variance Gaussian arms with means in [0,1][0,1] and the measurable algorithms of Section 2, the order-oblivious instance-wise lower bound is Θ(H[log(1/δ)+Ent(I)]) (H [ (1/δ)+ (I) ] ). A single algorithm matches this bound up to an additive O(Dlog(e+log(e+D)))O (D (e+ (e+D) ) ) term. The lower bound follows from a change of distribution to instances with two best arms whose KL divergence is bounded using expected numbers of samples on the original instance; the upper bound for a single algorithm from elimination that retains the arms with the largest empirical means and a summation over fixed sets of near-optimal arms. The proofs cover arbitrary finite instances, assume neither monotonicity nor termination at instances with two best arms, and require no prior estimates of the gaps, complexity, or gap entropy. AI use statement The main mathematical derivations and the Lean 4 formalization and verification work were carried out primarily by gpt-6-astra. The resulting mathematical arguments and formal verification work were subsequently checked by claude-fable-5.1. Generative AI tools were also used extensively in preparing the manuscript. These model-based checks are distinct from the kernel checks described in Appendix I. Appendix A Probabilistic and elimination preliminaries We collect elementary ingredients used by both upper bounds and by the lower-bound comparison. All sample blocks below are fresh. Conditional statements therefore remain valid for an adaptively chosen active set and tolerance. A.1 Gaussian tails and finite adaptive experiments For the mean X¯m X_m of m independent (μ,1)N(μ,1) observations, ℙ(X¯m−μ≥t)≤e−mt2/2,ℙ(|X¯m−μ|>t)≤2e−mt2/2(t>0).P ( X_m-μ≥ t )≤ e^-mt^2/2, ( | X_m-μ |>t )≤ 2e^-mt^2/2 (t>0). (A.1) We write kl(p,q)=plog(p/q)+(1−p)log((1−p)/(1−q)) (p,q)=p (p/q)+(1-p) ((1-p)/(1-q) ) for binary relative entropy, using the usual extended-real conventions. The following finite-horizon calculation is the Gaussian form of the adaptive change-of-measure argument used in bandit lower bounds (Kaufmann et al., 2016). We include the proof to account explicitly for internal randomness and latent mixtures. Lemma A.1 (Change of distribution for a finite adaptive Gaussian experiment). Run the same algorithm on the mean vectors μ and ν, stopping its transcript after return or after m total observations. If Pμ(m)P_μ^(m) and Pν(m)P_ν^(m) are the transcript laws and Ni(m)=Ni(m)N_i^(m)=N_i(m) is the number of observations of arm i in this transcript, using the stopped-count convention of Section 2, then KL(Pμ(m)∥Pν(m))≤12∑i(μi−νi)2μNi(m). (P_μ^(m) \|P_ν^(m) )≤ 12 _i( _i- _i)^2E_μN_i^(m). (A.2) Equality holds when the algorithm’s internal random seed is included in the transcript. The same upper bound, averaged over a common latent-variable prior, holds for mixtures of such experiments after the latent variable is discarded. Proof. Condition on the seed. Given a past transcript, the next selected arm is the same function of that history under both laws. Its conditional Gaussian divergence is (μi−νi)2/2( _i- _i)^2/2. Sampling actions and return decisions contribute no further divergence. The relative-entropy chain rule, applied for at most m observations with an absorbing state after return, proves the identity for the augmented transcript. Discarding the seed gives the inequality by data processing. For a common latent prior, apply the same chain rule after exposing the latent variable and then discard it. ∎ For any event F, data processing also gives kl(P(F),Q(F))≤KL(P∥Q) (P(F),Q(F) )≤ (P\|Q). We use Pinsker’s inequality |P(F)−Q(F)|≤KL(P∥Q)/2 |P(F)-Q(F) |≤ (P\|Q)/2 and the elementary bound kl(p,q)≥plog(1/q)−log2. (p,q)≥ p (1/q)- 2. (A.3) These comparisons will always be applied at finite horizons before taking increasing limits of return events. A.2 A median-elimination subroutine with a deterministic sample budget This subroutine follows the median-elimination principle of Even-Dar et al. (2002); Even-Dar et al. (2006); the formulation below records the deterministic budget and Gaussian guarantee needed here. Lemma A.2 (Median elimination). For a set of s arms, 0<ε≤10< ≤ 1, and 0<β<0.10<β<0.1, a procedure (S,ε,β) PAC(S, ,β) returns an arm of mean at least maxi∈Sμi−ε _i∈ S _i- with probability at least 1−β1-β. Its number of samples, denoted NPAC(s,ε,β)N_PAC(s, ,β), is deterministic and satisfies NPAC(s,ε,β)≤CPACsε−2log(8/β).N_PAC(s, ,β)≤ C_PACs ^-2 (8/β). A singleton is returned without sampling. Proof. Start with S0=S_0=S. For r=0,1,…r=0,1,…, while |Sr|≥2|S_r|≥ 2, put εr=ε8(3/4)r,βr=β2−(r+1),mr=⌈8εr−2log(8/βr)⌉. _r= 8(3/4)^r, _r=β 2^-(r+1), m_r= 8 _r^-2 (8/ _r) . Sample each arm of SrS_r exactly mrm_r times and retain the empirical upper ⌈|Sr|/2⌉ |S_r|/2 arms. These retained sizes and the stopping round are deterministic. By (A.1), the probability that a specified empirical mean exceeds its own true mean by more than εr _r, or falls below it by that amount, is at most (βr/8)4( _r/8)^4. Except with probability at most 3(βr/8)4≤βr3( _r/8)^4≤ _r, the current true best is not underestimated by εr _r, and fewer than half the current arms overestimate by εr _r. The second assertion follows by Markov’s inequality. If that best arm is discarded, every retained estimate is at least its estimate, and at least one retained arm has no upward error. The largest retained true mean is consequently within 2εr2 _r of the previous maximum. Summing the losses gives 2∑rεr=ε2 _r _r= , and summing the failure probabilities gives ∑rβr=β _r _r=β. Before termination, |Sr|≤2s2−r|S_r|≤ 2s2^-r. Thus the sample sum is bounded by a constant times sε−2∑r≥0(8/9)r[log(8/β)+r+1]=O(sε−2log(8/β)).s ^-2 _r≥ 0(8/9)^r [ (8/β)+r+1 ]=O (s ^-2 (8/β) ). The integer ceilings are absorbed by the same bound. This also specifies the exact deterministic sample count used in later reservations. ∎ A.3 Threshold elimination and retention of at least half the arms Given S, tolerance 0<d≤10<d≤ 1, and 0<α<0.10<α<0.1, choose a=(S,d/8,α/16)a= PAC(S,d/8,α/16). Independently estimate its mean with ⌈512d−2log(32/α)⌉ 512d^-2 (32/α) observations, obtaining z. Independently estimate every active arm with exactly m(S,d,α)=⌈512d−2log(128/α)⌉m(S,d,α)= 512d^-2 (128/α) (A.4) observations per arm, obtaining xix_i. Define the threshold retained set R0=i∈S:xi≥z−d/2.R_0=\i∈ S:x_i≥ z-d/2\. (A.5) The raw threshold procedure returns R0R_0. The modified procedure returns a set R consisting of R0R_0 together with the ⌈|S|/2⌉ |S|/2 arms with largest empirical means. Equivalently, add arms in decreasing empirical-mean order until at least half are retained. This equivalence holds because a threshold set is itself an upper segment of the empirical ranking. Use a fixed tie rule on the probability-zero event of equal fresh empirical means. Both procedures use the same observations and have the same sample cost. Lemma A.3 (Elimination guarantees). The raw threshold procedure above has deterministic cost at most Celim|S|d−2log(128/α)C_elim|S|d^-2 (128/α). It satisfies: 1. If a unique best arm belongs to S, it belongs to R0R_0 except with probability at most α. 2. If the unique best arm belongs to S, at most N active arms (including that best) have gap less than d from it, and s=|S|>4Ns=|S|>4N, then R0R_0 both contains the best and has size at most ⌈s/2⌉ s/2 except with probability at most α. 3. If s≤4s≤ 4, the unique best arm belongs to S, and every other active arm has gap at least d from it, then R0R_0 consists of exactly the best arm except with probability at most α. Replacing R0R_0 by the enlarged set R preserves the first two guarantees. Under the good event used to prove the third guarantee, R retains the best and has size ⌈s/2⌉ s/2 ; at most two such good calls finish from size at most four. The singleton conclusion in the third guarantee applies to R0R_0, not necessarily to R. Proof. Let μS=maxi∈Sμi _S= _i∈ S _i. Except on the PAC failure and the reference-estimation failure, each of probability at most α/16α/16, μS−3d/16≤z≤μS+d/16. _S-3d/16≤ z≤ _S+d/16. (A.6) Each active estimate has two-sided error exceeding d/16d/16 with probability at most α/64α/64. The best survives whenever its estimate is at least μS−d/16 _S-d/16. An arm with gap at least d survives threshold elimination only if it overestimates by at least 5d/165d/16, an event contained in its d/16d/16 deviation event. If s>4Ns>4N, the expected number of such far-arm deviations is at most sα/64sα/64, so the probability of at least s/4s/4 of them is at most α/16α/16. Off that event, fewer than s/4s/4 near arms and fewer than s/4s/4 far arms survive. Adding the reference and best-estimation failures proves the second assertion with slack in the constants. The first assertion uses only retention of the best arm. For s≤4s≤ 4, a union bound over all current estimates gives the third assertion. With all these estimates accurate and all gaps at least d, the best also has the largest empirical mean, so it remains in the retained empirical upper half. Lemma A.2 and the explicit sample counts prove the cost bound. ∎ Remark A.4 (Reusing a reference estimate). Suppose a reference is selected at scale entry with error budget α0/16 _0/16 and its mean estimate is separately accurate to d/16d/16 with failure probability β. If the original best is still active, (A.6) continues to hold after all later same-scale deletions, even when the reference label itself has been removed. Later calls require only fresh active-arm estimates, and their conditional estimation/progress failures are charged to their own α budgets. The PAC and reference failures are charged once at entry. For correctness after loss of the best, only the one-sided inequality z≤μ[1]+d/16z≤ _[1]+d/16 is needed. In particular, a reference satisfying the upper bound and Δi≤d/8 _i≤ d/8 imply that a removed arm satisfies xi−μi<−5d/16x_i- _i<-5d/16. Selecting a reference arm with a low mean does not invalidate this implication. The single algorithm of Appendix D estimates the reference once per scale with its own failure budget βj,k _j,k from (D.6) instead of α/16α/16; the per-call bound of Lemma A.3 is therefore not applied verbatim there, and the corresponding failure events are accounted for separately in Appendices E and F. A.4 Geometrically weighted group sizes and their entropy For an instance, put nk=|Gk|n_k=|G_k| and K=maxk:nk>0K= \k:n_k>0\. For 0≤k≤K0≤ k≤ K, define dk=2−k,Nk=1+#i≠i[1]:Δi<dk,Wk=4k(1+∑t≥knt),W=∑k=0KWk.d_k=2^-k, N_k=1+\# \i≠ i_[1]: _i<d_k \, W_k=4^k (1+ _t≥ kn_t ), W= _k=0^KW_k. (A.7) Here W0=nW_0=n, NK=1N_K=1, and Wk=4kNk−1W_k=4^kN_k-1 for k≥1k≥ 1. Lemma A.5 (Entropy of the normalized weights). Let qk=Wk/Wq_k=W_k/W. Then H≤W<323H,Ent(q)≤323Ent(I)+C0,4K≤4D,H≤ W< 323H, (q)≤ 323 (I)+C_0, 4^K≤ 4D, (A.8) where C0=log(4/3)+(4/9)log4C_0= (4/3)+(4/9) 4 is an absolute constant. Proof. Put vt=(nt+t=K)4tv_t= (n_t+1\t=K\ )4^t and st=∑l=0t4−ls_t= _l=0^t4^-l. The extra term adds one fictitious arm at the finest scale. Directly, Wk=∑t≥kvt4k−t,W=∑tvtst,1≤st≤4/3.W_k= _t≥ kv_t4^k-t, W= _tv_ts_t, 1≤ s_t≤ 4/3. Because Ht≤nt4t<4HtH_t≤ n_t4^t<4H_t on every nonempty group and 4K<4D≤4H4^K<4D≤ 4H, the total V=∑tvtV= _tv_t satisfies H≤V<8H≤ V<8H. This proves the bounds on W; the bound on 4K4^K follows from the group with largest index. Sample J with probabilities rt=vtst/Wr_t=v_ts_t/W. Conditional on J=tJ=t, sample Z∈0,…,tZ∈\0,…,t\ with probabilities 4−l/st4^-l/s_t. Then J−ZJ-Z has distribution q, and Ent(Z∣J=t)=logst+log4[Z∣J=t]≤log(4/3)+(4/9)log4=C0. (Z J=t)= s_t+ 4\,E[Z J=t]≤ (4/3)+(4/9) 4=C_0. Since nK≥1n_K≥ 1, one has vt<8Htv_t<8H_t on every nonempty group, and therefore rt≤(32/3)ptr_t≤(32/3)p_t. Nonnegativity of relative entropy gives Ent(r)=∑trtlog(1/pt)−KL(r∥p)≤323∑tptlog(1/pt). (r)= _tr_t (1/p_t)- (r\|p)≤ 323 _tp_t (1/p_t). Finally, entropy cannot increase upon discarding information, so Ent(q)=Ent(J−Z)≤Ent(J,Z)≤Ent(r)+C0. (q)= (J-Z)≤ (J,Z)≤ (r)+C_0. ∎ Appendix B A gap-entropy lower bound on the original instance We prove the lower-bound direction of Theorem 2.1 for every δ-correct algorithm of Section 2; Appendix H extends it to algorithms with arbitrary standard Borel internal randomness and to history-dependent probability kernels. The argument compares several labelings of the original instance with one experiment with two best arms. Every expected number of samples in the comparison is evaluated on the original instance. Theorem B.1 (Lower bound). For every instance I with n≥2n≥ 2 and every 0<δ<1/100<δ<1/10, ℒ(I,δ)≥H(I)max2kl(1−δ,δ),Ent(I)/4≥H(I)5(log(1/δ)+Ent(I)).L(I,δ)≥ H(I) \2 (1-δ,δ), (I)/4 \≥ H(I)5 ( (1/δ)+ (I) ). (B.1) B.1 Symmetrization and finite transcript experiments Fix a δ-correct algorithm. Randomly permute its input labels, run the algorithm through this relabeling, and undo the permutation on its answer. The resulting algorithm A is permutation equivariant in distribution, remains δ-correct, and its expected stopping time on I is exactly the original algorithm’s permutation-averaged expected stopping time. It therefore suffices to prove (B.1) for A on I. If its expected stopping time is infinite, there is nothing to prove. Assume henceforth that it is finite. Let D be the finite set of distinct positive gaps in I, let mdm_d be the multiplicity of d∈d , and write μ[1] _[1] for the best mean. Permutation equivariance implies that the expected number of samples of an arm of gap d is the same on every labeling of the target multiset. Denote this count by tdt_d, and set αd=d2td. _d=d^2t_d. (B.2) In particular, conditioning a uniformly labeled target instance to give one designated label a specified gap does not change the expected count of any other specified arm with a given gap. We have IτAH≥∑d∈mdd−2Hαd. E_I _AH≥ _d m_dd^-2H _d. (B.3) The inequality only discards samples from the best arm. We use finite experiments throughout changes of distribution. A transcript at horizon m∈ℕm records the realization of the algorithm’s internal random seed, chosen arms, observations, and any returned answer through at most m samples; after the algorithm returns, the transcript is extended by an absorbing symbol. The chain rule for relative entropy gives, for two fixed mean vectors μ,νμ,ν and the same algorithm, KL(Pμ(m)∥Pν(m))=12∑i=1n(μi−νi)2μNi(τA∧m). (P_μ^(m) \|P_ν^(m) )= 12 _i=1^n( _i- _i)^2E_μN_i( _A m). (B.4) Here Ni(τA∧m)N_i( _A m) counts observations from arm i in the finite experiment. To see the identity, condition successively on each past transcript. The algorithm’s conditional distribution of its next action is the same under the two experiments, so it contributes zero relative entropy. An observation from arm i contributes KL((μi,1)∥(νi,1))=(μi−νi)2/2 (N( _i,1) \|N( _i,1) )=( _i- _i)^2/2. Summing these conditional contributions proves the identity, including arbitrary dependence on the internal random seed. The same argument applies when the experiment is censored by an additional stopping rule. We never require the algorithm to terminate on an instance with tied best arms. B.2 Distributions on the original instance and instances with two best arms For d∈d , let PdP_d be the law obtained by placing a gap-d arm at label 11, uniformly assigning the remaining target multiset to labels 2,…,n2,…,n, and running A. This label is designated only in the analysis and is not identified to the algorithm. If N1N_1 is the number of samples from label 11 before a return, then PdN1=td,Pd(τA<∞,ı^≠1)≥1−δ.E_P_dN_1=t_d, P_d ( _A<∞, ≠ 1 )≥ 1-δ. (B.5) For a∈a , define QaQ_a by assigning mean μ[1] _[1] to label 11 and uniformly placing, at the remaining labels, the multiset of I with one gap-a arm removed. This comparison instance has exactly two arms of mean μ[1] _[1]. Lemma B.2 (Output probabilities when two arms are best). For every a∈a , Qa(τA<∞,ı^≠1)≤δ.Q_a ( _A<∞, ≠ 1 )≤δ. (B.6) Proof. Fix a labeled mean vector occurring in QaQ_a. Lower its other mean-μ[1] _[1] arm to μ[1]−ε _[1]- , leaving label 11 unchanged. Because I has at least two arms, a unique best arm, and means in [0,1][0,1], μ[1]>0 _[1]>0. Thus every sufficiently small ε>0 >0 gives a valid instance in which label 11 is uniquely best. This perturbation is valid also at the endpoint μ[1]=1 _[1]=1. Correctness bounds the probability of returning another label by horizon m by δ on the perturbed instance. By (B.4), the relative entropy between the unperturbed and perturbed horizon-m experiments is at most mε2/2m ^2/2. Pinsker’s inequality therefore makes their total variation tend to zero as ε↓0 0. The same error bound holds on the fixed instance with two best arms at every finite horizon. Average over the finitely many background labelings and then let m→∞m→∞. The finite-return events increase to the event in (B.6), proving the claim without a termination assumption on QaQ_a. ∎ Lemma B.3 (Changing two arm means). For every finite horizon m and a,d∈a,d with a≠da≠ d, KL(Pd(m)∥Qa(m))≤12(d2td+(a−d)2ta). (P_d^(m) \|Q_a^(m) )≤ 12 (d^2t_d+(a-d)^2t_a ). (B.7) For a=da=d, the upper bound is αd/2 _d/2. Consequently, if a≥da≥ d, KL(Pd(m)∥Qa(m))≤12(αd+αa). (P_d^(m) \|Q_a^(m) )≤ 12( _d+ _a). (B.8) Proof. Suppose first that a≠da≠ d. Draw a labeled assignment from the source experiment PdP_d, and independently of all observations and of the algorithm’s internal random seed, choose uniformly one of its mam_a gap-a arms. Raise label 11 from μ[1]−d _[1]-d to μ[1] _[1], and change the selected arm from μ[1]−a _[1]-a to μ[1]−d _[1]-d. The resulting background multiset is the original target multiset with one gap-a arm removed. We verify its uniform labeling, since a common comparison law is essential. Let MPM_P and MQM_Q count the distinct background labelings in PdP_d and QaQ_a. Their multiplicities give MQ/MP=ma/mdM_Q/M_P=m_a/m_d. Any fixed resulting background assignment has exactly mdm_d preimages among pairs of a source assignment and a selected label: choose which of its mdm_d gap-d labels was changed from gap a. Each pair has probability 1/(MPma)1/(M_Pm_a), so this background has probability md/(MPma)=1/MQm_d/(M_Pm_a)=1/M_Q. Thus the induced law is exactly QaQ_a, including all repeated-gap cases. Keep the source assignment and selected label as latent variables with the same prior in both experiments. Conditional on them, the means differ at precisely the two described coordinates. Under the source law, their expected numbers of samples are tdt_d and tat_a, respectively: the first follows from symmetry, and the second follows from the same symmetry and the independent uniform selection. More explicitly, for every fixed source assignment and every eligible selected label, the source transcript kernel is just A on that assignment, and its expected count at that label is tat_a. The hidden selection does not change this kernel. In the comparison experiment, each latent pair likewise uses A on its mapped mean vector; pairs with the same mapped vector give the same conditional transcript law. Apply (B.4) conditionally, average over the common latent prior, and bound truncated counts by their full source expectations. This gives the right-hand side of (B.7) for the joint laws including the latent variables. Discarding latent variables cannot increase relative entropy, proving the asserted marginal inequality. Neither latent variable is revealed to the algorithm. When a=da=d, raising label 11 alone already induces QdQ_d, and its KL divergence is at most d2td/2d^2t_d/2. Finally, if a≥da≥ d, then (a−d)2≤a2(a-d)^2≤ a^2, which proves (B.8). All numbers of samples used here belong to labelings of I. ∎ The a=da=d case, binary data processing for the event of returning a label other than 11 by horizon m, and then the limit m→∞m→∞ yield αd≥2kl(1−δ,δ)≥log(1/δ)>1. _d≥ 2 (1-δ,δ)≥ (1/δ)>1. (B.9) Indeed, let Fm=τA≤m,ı^≠1F_m= \ _A≤ m,\ ≠ 1 \ be the event of returning a label other than 11 by horizon m, and put pm=Pd(m)(Fm)p_m=P_d^(m)(F_m) and qm=Qd(m)(Fm)q_m=Q_d^(m)(F_m). Binary data processing gives kl(pm,qm)≤αd/2 (p_m,q_m)≤ _d/2 at every finite horizon. By Lemma B.2, qm≤δq_m≤δ, and by (B.5), pmp_m increases to Pd(τA<∞,ı^≠1)≥1−δ>δP_d ( _A<∞, ≠ 1 )≥ 1-δ>δ. Fix ε>0 >0 with 1−δ−ε>δ1-δ- >δ. For all sufficiently large m, pm≥1−δ−ε>δ≥qmp_m≥ 1-δ- >δ≥ q_m. Since q↦kl(p,q)q (p,q) is decreasing on (0,p](0,p], with kl(p,0)=+∞ (p,0)=+∞ for p>0p>0, and p↦kl(p,δ)p (p,δ) is increasing on [δ,1][δ,1], kl(1−δ−ε,δ)≤kl(pm,δ)≤kl(pm,qm)≤αd/2 (1-δ- ,δ)≤ (p_m,δ)≤ (p_m,q_m)≤ _d/2 for all such m. Letting ε↓0 0 and using the continuity of kl(⋅,δ) (·,δ) on [0,1)[0,1) gives kl(1−δ,δ)≤αd/2 (1-δ,δ)≤ _d/2. For the elementary second inequality, write kl(1−δ,δ)=(1−2δ)log((1−δ)/δ) (1-δ,δ)=(1-2δ) ((1-δ)/δ ). If L=log(1/δ)≥log10L= (1/δ)≥ 10, then 2kl(1−δ,δ)≥1.6(L+log0.9)≥L2 (1-δ,δ)≥ 1.6(L+ 0.9)≥ L. B.3 Disjoint stopping events under a common comparison distribution Set c0=1/100c_0=1/100 and define events on returned transcripts by Ed=τA<∞,ı^≠1,c0d−2≤N1≤16td.E_d= \ _A<∞,\ ≠ 1,\ c_0d^-2≤ N_1≤ 16t_d \. (B.10) These are transcript events whose endpoints depend only on the fixed target and the algorithm, not on the law under which they are evaluated. Lemma B.4 (Probabilities of the stopping events). For every d∈d , Pd(Ed)>1/2P_d(E_d)>1/2. Whenever a≥da≥ d, Qa(Ed)≥14exp(−αd−αa).Q_a(E_d)≥ 14 (- _d- _a). (B.11) Proof. By (B.9), αd>1 _d>1, so td=αdd−2>0t_d= _dd^-2>0 and the interval [c0d−2,16td] [c_0d^-2,16t_d ] is nonempty; in particular Markov’s inequality applies and gives Pd(N1>16td)≤1/16P_d(N_1>16t_d)≤ 1/16. For the lower endpoint, compare PdP_d with QdQ_d and censor both experiments immediately before a request that would take the count of label 11 above ⌈c0d−2⌉−1 c_0d^-2 -1, the largest integer strictly below c0d−2c_0d^-2. Also impose a total-sample horizon m. Every return by this horizon with N1<c0d−2N_1<c_0d^-2 is preserved by this censoring. The KL divergence is at most c0/2c_0/2, since only label 11 changes. Pinsker’s inequality gives total variation at most c0/2=0.05 c_0/2=0.05. The comparison probability of such an early return with answer different from 11 is at most δ by Lemma B.2. Letting m→∞m→∞ gives Pd(τA<∞,ı^≠1,N1<c0d−2)≤δ+0.05.P_d ( _A<∞, ≠ 1,N_1<c_0d^-2 )≤δ+0.05. Together with (B.5), this implies Pd(Ed)≥1−2δ−0.05−1/16>1/2.P_d(E_d)≥ 1-2δ-0.05-1/16>1/2. Apply (B.8) and binary data processing to Ed∩τA≤mE_d∩\ _A≤ m\, and take the increasing-event limit. If p=Pd(Ed)>1/2p=P_d(E_d)>1/2 and q=Qa(Ed)q=Q_a(E_d), then 12(αd+αa)≥kl(p,q)≥plog(1/q)−log2. 12( _d+ _a)≥ (p,q)≥ p (1/q)- 2. The last inequality follows by dropping the nonnegative term (1−p)log(1/(1−q))(1-p) (1/(1-q) ) and using that binary entropy is at most log2 2. Since p>1/2p>1/2, rearranging proves (B.11). Finite transcript bounds justify this step even if A never returns on a set of positive QaQ_a-probability. ∎ In each nonempty group choose an exact gap dkd_k minimizing αd _d, and abbreviate αk=αdk _k= _d_k. For x≥1x≥ 1 let x=k:αk≤x,N(x)=|x|.C_x=\k: _k≤ x\, N(x)=|C_x|. If xC_x is nonempty, choose its largest-gap representative a. Then a≥dka≥ d_k and αa≤x _a≤ x for every k∈xk _x. Lemma B.4 gives the simultaneous bounds under this single law QaQ_a, Qa(Edk)≥14e−2x,k∈x.Q_a(E_d_k)≥ 14e^-2x, k _x. (B.12) On the logarithmic sample-count coordinate log4(N1/c0) _4(N_1/c_0), the event for dkd_k corresponds to the interval [sk,sk+bk],sk=log4(dk−2)∈(k−1,k],bk=log4(1600αk).[s_k,s_k+b_k], s_k= _4 (d_k^-2 )∈(k-1,k], b_k= _4(1600 _k). All intervals with αk≤x _k≤ x have length at most b(x)=log4(1600x)b(x)= _4(1600x). There is at most one starting point in each cell (k−1,k](k-1,k], so any interval of length u contains at most u+2u+2 starting points. Greedily select the remaining interval with the smallest starting point, then delete every remaining interval whose start is at most its right endpoint. Each selection deletes at most b(x)+2b(x)+2 intervals, and the selected closed intervals are pairwise disjoint. We obtain at least N(x)/(b(x)+2)N(x)/ (b(x)+2 ) disjoint events, all contained in τA<∞,ı^≠1 \ _A<∞, ≠ 1 \. Equations (B.6) and (B.12) imply N(x)≤4δ[log4(1600x)+2]e2x.N(x)≤ 4δ\, [ _4(1600x)+2 ]e^2x. (B.13) If xC_x is empty the inequality is immediate. The reference gap a can depend on x: each application proves a deterministic inequality for the same counting function N. B.4 From scale counting to entropy By (B.9), N(x)=0N(x)=0 for x<1x<1. Tonelli’s theorem and (B.13) yield Z:=∑ke−4αk Z:= _ke^-4 _k =∫0∞4e−4xN(x)x = _0^∞4e^-4xN(x)\,dx ≤16δ∫1∞[log4(1600x)+2]e−2xx<10δ<1. ≤ 16δ _1^∞ [ _4(1600x)+2 ]e^-2x\,dx<10δ<1. (B.14) For an explicit verification of the inessential numerical constant, use logx≤x x≤ x for x≥1x≥ 1. The integral multiplied by 1616 is at most 16e−2[12(log1600log4+2)+34log4]<10.16e^-2 [ 12 ( 1600 4+2 )+ 34 4 ]<10. Let pk=Hk/Hp_k=H_k/H on the nonempty groups. Nonnegativity of relative entropy between (pk)(p_k) and (e−4αk/Z) (e^-4 _k/Z ) gives 4∑kpkαk≥Ent(I)−logZ≥Ent(I).4 _kp_k _k≥ (I)- Z≥ (I). (B.15) The minimizing representatives and (B.3) imply IτAH≥∑d∈mdd−2Hαd≥∑kpkαk. E_I _AH≥ _d m_dd^-2H _d≥ _kp_k _k. By (B.9) every αk _k is at least 2kl(1−δ,δ)≥L=log(1/δ)2 (1-δ,δ)≥ L= (1/δ), and so is this last sum, since the pkp_k are probability weights. Hence IτAH≥max2kl(1−δ,δ),Ent(I)/4≥maxL,Ent(I)/4≥L+Ent(I)5, E_I _AH≥ \2 (1-δ,δ), (I)/4 \≥ \L, (I)/4 \≥ L+ (I)5, where the last step bounds the maximum below by the weighted mean 15L+45⋅Ent(I)4 15L+ 45· (I)4. Undoing the initial symmetrization and taking the infimum over δ-correct algorithms proves Theorem B.1. The argument covers repeated suboptimal means, arbitrary positive gaps, the full range 0<δ<1/100<δ<1/10, and the endpoint best mean 11. Appendix C An instance-wise upper bound The upper-bound direction of Theorem 2.1 concerns a pointwise infimum over algorithms. We may therefore choose an algorithm whose fixed parameters depend on the target instance, provided it is correct on every admissible input. The following construction makes this quantifier distinction explicit. Proposition C.1 (Instance-wise upper bound). For every target instance I and every 0<δ<1/100<δ<1/10, there exists a δ-correct algorithm AI,δA_I,δ with finite expected stopping time on every instance with a unique best arm such that, uniformly over all labelings πIπ I of the target, πIτAI,δ≤CH(I)(log(1/δ)+Ent(I)).E_π I _A_I,δ≤ CH(I) ( (1/δ)+ (I) ). (C.1) Consequently ℒ(I,δ)L(I,δ) is bounded above by the right-hand side. C.1 Parameters and one finite run Fix a target instance; it has n≥2n≥ 2 arms by definition. Its group sizes nk=|Gk|n_k=|G_k|, the largest index K of a nonempty group, and the following quantities are fixed parameters of the construction: dk d_k =2−k, =2^-k, Nk N_k =1+∑j>knj, =1+ _j>kn_j, Wk W_k =4k(1+∑j≥knj), =4^k (1+ _j≥ kn_j ), W W =∑k=0KWk, = _k=0^KW_k, qk q_k =Wk/W, =W_k/W, 0≤k≤K. 0≤ k≤ K. (C.2) Here NkN_k is exactly the number of original arms whose gaps are below dkd_k, including i[1]i_[1]. In particular, W0=n,Wk=4kNk−1(k≥1),NK=1.W_0=n, W_k=4^kN_k-1\ (k≥ 1), N_K=1. Lemma A.5 gives H≤W<323H,Ent(q)=O(Ent(I)+1),4K≤4D≤4H.H≤ W< 323H, (q)=O ( (I)+1 ), 4^K≤ 4D≤ 4H. (C.3) Only the group sizes and the quantities derived from them are supplied as constants to this construction; its correctness will not assume that an input has these group sizes. For a run error parameter 0<ε<1/100< <1/10, set ηk=(ε/2)qk _k=( /2)q_k. Start with all input arms active. At scales k=0,…,Kk=0,…,K, repeatedly apply the raw threshold elimination procedure of Lemma A.3 while |S|>4Nk|S|>4N_k. On its rrth invocation at this scale, starting with r=0r=0, use tolerance dkd_k and confidence αk,r=ηk2−(r+1). _k,r= _k2^-(r+1). (C.4) If the returned set R0R_0 is empty or has size greater than ⌈|S|/2⌉ |S|/2 , abort the run. Otherwise replace S by R0R_0 and continue. After all scales, the active set has at most 4NK=44N_K=4 arms. If it is a singleton, return its member. Otherwise make one final raw threshold-elimination call at tolerance dKd_K and confidence ε/2 /2; return its arm only if R0R_0 is a singleton, and abort otherwise. Every call uses fresh samples; the construction uses no internal randomness, and ties are broken by a fixed rule. A run is always finite. Every accepted loop invocation reduces the active size geometrically, there are finitely many scales, and an invocation violating the size condition aborts immediately. Lemma C.2 (Guarantees for one run). The preceding run has the following properties. 1. On every input with n arms and a unique best arm, its probability of an incorrect return is at most ε . 2. On every labeling of the target I, it returns the correct arm with probability at least 1−ε1- . 3. On every input with n arms and every trajectory, its sample count is at most BI(ε)=CH(I)(log(1/ε)+Ent(I))B_I( )=CH(I) ( (1/ )+ (I) ) (C.5) for a sufficiently large universal constant C. Proof. For the first claim, an incorrect singleton can be returned only after the input’s original best has been removed. Conditional on its survival to a call, the best-arm retention guarantee in Lemma A.3 bounds this removal probability by that call’s confidence. The confidence sum over every possible trajectory is at most ∑k=0K∑r≥0αk,r+ε/2=∑k=0Kηk+ε/2=ε. _k=0^K _r≥ 0 _k,r+ /2= _k=0^K _k+ /2= . An abort cannot create an incorrect answer. This argument requires no agreement between the input and the fixed target instance. For the second claim, on a labeling of I the active number of arms within gap dkd_k of the original best is at most NkN_k, as long as that best remains active. Thus every loop invocation meets the halving condition in Lemma A.3. Except with its allocated error probability, it protects the best and satisfies the acceptance condition. At scale K all original suboptimal gaps are at least dKd_K. The final invocation therefore satisfies the primitive’s small-set singleton guarantee. A union bound with the same confidence sum proves target success with probability at least 1−ε1- . For the deterministic cost claim, the active size entering scale zero is n=W0n=W_0. If scale k≥1k≥ 1 is reached, its entry size is at most 4Nk−14N_k-1 by the preceding loop’s stopping condition, independently of all statistical events. Every loop call starts with at least five arms; an accepted result has at most ⌈s/2⌉≤3s/4 s/2 ≤ 3s/4 arms. Consequently, including a possible final aborting invocation, the scale’s cost is at most CWk∑r≥0(3/4)r(log(1/ηk)+(r+1)log2) CW_k _r≥ 0(3/4)^r ( (1/ _k)+(r+1) 2 ) ≤C′Wklog(1/ηk). ≤ C W_k (1/ _k). Here C absorbs CelimC_elim and the additive log128 128 in the primitive’s cost Celim|S|d−2log(128/α)C_elim|S|d^-2 (128/α), using log(1/ηk)≥log(20) (1/ _k)≥ (20). This uses the deterministic sample budget in Lemma A.3, not a cost bound conditioned on successful elimination. The final call uses at most C4Klog(2/ε)C4^K (2/ ) samples (the factor |S|≤4|S|≤ 4 and the term log256 256 of the primitive’s cost at confidence ε/2 /2 are absorbed into C). Summing and using (C.3), BI(ε) B_I( ) ≤C[∑k=0KWklog2WεWk+Hlog(2/ε)] ≤ C [ _k=0^KW_k 2W W_k+H (2/ ) ] =C[W(log(2/ε)+Ent(q))+Hlog(2/ε)] =C [W ( (2/ )+ (q) )+H (2/ ) ] ≤C′H(log(1/ε)+Ent(I)). ≤ C H ( (1/ )+ (I) ). The additive entropy constant is absorbed by log(1/ε)>log10 (1/ )> 10. These are bounds in terms of the fixed target even when the actual input has different means or gaps. ∎ C.2 A finite-expectation fallback For completeness, we specify a fallback F that is δ/2δ/2-correct and has finite expected number of samples on every input with a unique best arm. At round r=0,1,…r=0,1,…, sample each of the n arms cumulatively mr=2rm_r=2^r times and let μ^i,r μ_i,r be its empirical mean. Use confidence radius ρr=2mrlog8n(r+1)2δ. _r= 2m_r 8n(r+1)^2δ. (C.6) Stop once one interval [μ^i,r−ρr,μ^i,r+ρr] [ μ_i,r- _r, μ_i,r+ _r ] lies strictly above all the others, and return its arm. Gaussian tails give ℙ(|μ^i,r−μi|>ρr)≤δ4n(r+1)2.P ( | μ_i,r- _i |> _r )≤ δ4n(r+1)^2. The union bound over all arms and rounds is less than δ/2δ/2. When every interval contains its true mean, a returned arm must be the unique best, proving correctness. Fix now any input with smallest gap Δ[2]>0 _[2]>0. There exists a finite r0r_0 such that ρr≤Δ[2]/8 _r≤ _[2]/8 for all r≥r0r≥ r_0. If every empirical error at such a round is at most Δ[2]/8 _[2]/8, the best arm’s interval is strictly above every other interval. Therefore ℙ(F has not stopped by round r)≤2nexp(−mrΔ[2]2/128),r≥r0.P (F has not stopped by round r )≤ 2n (-m_r _[2]^2/128 ), r≥ r_0. It follows, for example by summing each next round’s sample cost times its reaching probability, that τF≤nmr0+∑r≥r0nmr+1 2nexp(−mrΔ[2]2/128)<∞.E _F≤ nm_r_0+ _r≥ r_0nm_r+1\,2n (-m_r _[2]^2/128 )<∞. No sharp instance-dependent guarantee is required of this fallback. C.3 Correctness on every instance and target expected cost Perform independent runs, indexed by t=0,1,…t=0,1,…, with εt=δ2−(t+2). _t=δ 2^-(t+2). An abort starts the next run; an answer stops the stream. In parallel, run an independent copy of F, alternating one requested sample from each stream, and return whichever stream answers first. Internal computation between sample requests does not contribute to sample complexity. On an input with a different arm count from the fixed target, run F alone. A singleton input returns immediately. This defines the algorithm on all admissible input sizes. Lemma C.2 bounds the run stream’s total error probability by ∑t≥0εt=δ/2 _t≥ 0 _t=δ/2. Together with the fallback’s bound, the combined algorithm is δ-correct. Its sample count is at most twice the hypothetical fallback sample count, up to one sample. Hence it has finite expectation and terminates almost surely on every input with a unique best arm, including instances different from the fixed target. On a labeling of I, fresh observations and Lemma C.2 imply that, conditional on reaching a run, its abort probability is at most εt _t. Thus the probability that the run-only stream reaches run t is at most ∏u<tεu≤2−t. _u<t _u≤ 2^-t. Its expected total sample count is consequently at most ∑t≥02−tBI(εt) _t≥ 02^-tB_I( _t) ≤CH∑t≥02−t(L+Ent(I)+(t+2)log2) ≤ CH _t≥ 02^-t (L+ (I)+(t+2) 2 ) =O(H[L+Ent(I)]). =O (H [L+ (I) ] ). Interleaving increases this upper bound by at most a factor two, up to one sample, because an earlier fallback return only shortens the execution. The constants are uniform over all target labelings. This proves Proposition C.1, and taking the pointwise infimum proves the upper-bound direction of Theorem 2.1. Appendix D A single algorithm We construct a single algorithm for Theorem 2.2. It is given only the arms and the confidence level; the complexity, gaps, and gap entropy enter solely into its analysis. A singleton input is returned without sampling. Throughout the construction, assume n≥2n≥ 2 and set L=log(1/δ),γ=δ/1024.L= (1/δ), γ=δ/1024. (D.1) The algorithm performs successive runs indexed by j=0,1,…j=0,1,…. The bounds on their total weight and number of samples are hj=2j,Mj=1024hj,Qj=⌈CQhjL⌉,h_j=2^j, M_j=1024h_j, Q_j= C_Qh_jL , (D.2) where CQC_Q is the absolute constant C∗C_* of (F.12), which depends only on the constants of Lemmas A.2 and A.3; any larger absolute constant also works, and the algorithm is fully specified once it is fixed. All observations in a new run are fresh; the algorithm uses no internal randomness. D.1 Sampling and confidence parameters Each run maintains an active set S, a scale k≥0k≥ 0, the cumulative weight of its calls, and its reserved number of samples. A call with s=|S|≥2s=|S|≥ 2 uses d=2−k,u=d−2=4k,w=su.d=2^-k, u=d^-2=4^k, w=su. (D.3) Here w is the factor in the sample bound before the confidence logarithm. If adding w respects the bound on the cumulative weight, the confidence parameter is α=γwMj(j+1)−2,2≤s≤7,1,s≥8.α=γ wM_j cases(j+1)^-2,&2≤ s≤ 7,\\ 1,&s≥ 8. cases (D.4) The branch is recomputed from the active-set size at every call. Each arm estimate in the call uses exactly m=⌈512ulog128α⌉m= 512u 128α (D.5) fresh samples. Only the first call at a scale selects a reference. Apply the deterministic sample-budget PAC procedure of Lemma A.2 to the active set, with accuracy d/8d/8 and error probability α/16α/16. Denote its output by a. The deterministic number of samples used by this procedure is written NPAC(s,d/8,α/16)N_PAC(s,d/8,α/16). Independently estimate μa _a using βj,k=δ64(j+1)2(k+1)2,mz=⌈512ulog2βj,k⌉ _j,k= δ64(j+1)^2(k+1)^2, m_z= 512u 2 _j,k (D.6) samples, and denote this empirical mean by z. All subsequent calls at this scale reuse the numerical value z. Reuse is allowed even if a has left the active set: no further observation from a is then taken. The PAC procedure, the estimate z, and the estimates used for elimination use mutually independent fresh data. D.2 The procedure and its reservation order Run j starts with all arms active, k=0k=0, and both counters zero. It repeats the following steps until it aborts or returns an arm. 1. Compute s,d,u,ws,d,u,w from (D.3). If the used weight plus w exceeds MjM_j, abort the run before taking any samples. Otherwise compute α and m from (D.4)–(D.5). 2. Compute the entire deterministic sample count for this call. At scale entry it is sm+mz+NPAC(s,d/8,α/16);sm+m_z+N_PAC(s,d/8,α/16); at a later call at the same scale it is smsm. If the current reserved sample count plus this quantity exceeds QjQ_j, abort before taking any samples for the call. Otherwise reserve this entire quantity and charge w to the weight counter. 3. At scale entry, select the reference and obtain z as specified above. At every call, obtain independent empirical means (xi)i∈S(x_i)_i∈ S, each from m fresh samples, and form R0=i∈S:xi≥z−d/2.R_0=\i∈ S:x_i≥ z-d/2\. (D.7) If |R0|<⌈s/2⌉|R_0|< s/2 , add arms in decreasing order of their xix_i values until the resulting set has size ⌈s/2⌉ s/2 . Call the resulting set R; if |R0|≥⌈s/2⌉|R_0|≥ s/2 , take R=R0R=R_0. 4. Replace S by R. If |R|=1|R|=1, return its arm and stop the entire algorithm. Otherwise, if |R|≤⌈s/2⌉|R|≤ s/2 , make the next call at the same scale. If |R|>⌈s/2⌉|R|> s/2 , increase k by one and make a new scale-entry call. On abort, discard the run and start run j+1j+1. A fixed arm order resolves any ties; ties between independent Gaussian estimates occur with probability zero. The retained set always contains both R0R_0 and the empirical upper ⌈s/2⌉ s/2 arms. In particular, the retained set is enlarged before testing for a singleton. A singleton output from a nontrivial input therefore occurs only after a call with s=2s=2. Same-scale continuation is an exact halving up to rounding and decreases a size of at least three by a factor at most 3/43/4. Each run makes finitely many calls: it can continue only finitely many times at one scale, and eventually 2⋅4k>Mj2· 4^k>M_j prevents another scale from being entered. The reservation order ensures, on every trajectory, including trajectories with mistaken eliminations, ∑t in run jwt≤Mj,∑t in run jαt≤γ,Tj≤Qj, _t in run jw_t≤ M_j, _t in run j _t≤γ, T_j≤ Q_j, (D.8) where TjT_j is the run’s sample count. In particular all executed calls have α≤γα≤γ. The deterministic PAC budget is needed here to reserve the complete first call before observing its data. D.3 Reference estimation and underestimation events Let i[1]i_[1] be the original best arm, μ[1]=μi[1] _[1]= _i_[1], and Δi=μ[1]−μi _i= _[1]- _i, with Δ[1]=0 _[1]=0. The one-sided Gaussian inequality ℙ(X¯−μ≥t)≤e−mt2/2,ℙ(X¯−μ≤−t)≤e−mt2/2P ( X-μ≥ t )≤ e^-mt^2/2, ( X-μ≤-t )≤ e^-mt^2/2 (D.9) holds for the mean of m unit-variance Gaussian observations. Conditional on a scale-entry history and on the selected reference arm, (D.6) implies ℙ(|z−μa|>d/16|entry history,a)≤βj,k.P (|z- _a|>d/16 |entry history,a )≤ _j,k. Let ℱzF_z be the event that any such estimate fails anywhere in the stream of runs. Adaptively visited scales satisfy the same conditional bound, so ℙ(ℱz)≤∑j,k≥0βj,k=δ64(∑m≥1m−2)2<δ16.P(F_z)≤ _j,k≥ 0 _j,k= δ64 ( _m≥ 1m^-2 )^2< δ16. (D.10) The reference upper bound is the event z≤μa+d/16z≤ _a+d/16. Since every original arm has mean at most μ[1] _[1], the reference upper bound implies, regardless of which arms remain active, z−d/2≤μ[1]−7d/16.z-d/2≤ _[1]-7d/16. (D.11) Consequently, removing an active arm with Δi≤d/8 _i≤ d/8 requires xi−μi<−5d/16.x_i- _i<-5d/16. (D.12) We call (D.12) an underestimation event, whether or not the arm is actually removed. Enlarging the retained set can only make removal harder. Writing ℋtH_t for the information before the fresh arm estimates in call t, including its reference data, gives ℙ(arm i has an underestimation event in call t|ℋt)≤(αt/128)25.P (arm i has an underestimation event in call t |H_t )≤( _t/128)^25. (D.13) Indeed, 512(5/16)2/2=25512(5/16)^2/2=25. This bound is about fresh Gaussian errors and needs no conditioning on the reference upper bound. The reference upper bound is used only to deduce that eliminating a near-optimal arm requires an underestimation event. This distinction will be essential in the correctness proof. Appendix E Correctness through sets of near-optimal arms The per-run bound ∑tαt≤γ _t _t≤γ is not by itself a correctness guarantee for infinitely many runs. We instead charge errors in calls with at most seven arms globally and control the remaining errors using a fixed nested family of sets determined by the instance. Throughout this section, put η=γ/128=δ/131072,p=2η25.η=γ/128=δ/131072, p=2η^25. (E.1) E.1 Stochastic domination for adaptive sampling Lemma E.1 (Stochastic domination by independent Bernoulli variables). For one fresh run, let FiF_i indicate that the empirical mean of original arm i satisfies (D.12) at some executed call. On an extension of the probability space there are independent Bernoulli variables (Yi)i=1n(Y_i)_i=1^n, each with parameter at most p, such that Fi≤YiF_i≤ Y_i simultaneously. Proof. Give each original arm an independent rate-one Poisson process i N_i, and run these processes on one common clock. Suppose the current clock is θ immediately before call t’s fresh arm estimates. The exact conditional probability of (D.12) is pt=Φ(−5dtmt/16),p_t= (-5d_t m_t/16 ), where Φ is the standard Gaussian distribution function. It is the same for all active arms because their centered empirical means have the same variance. The parameters dt,mtd_t,m_t are predictable. Advance the common clock by λt=−log(1−pt) _t=- (1-p_t). For each active arm i, use the event i(θ+λt)−i(θ)≥1 N_i(θ+ _t)- N_i(θ)≥ 1 as its underestimation indicator. Using additional independent random variables, generate xi−μix_i- _i from its Gaussian law conditional on the indicated event or its complement. Its unconditional law is exactly (0,1/mt)N(0,1/m_t), and the empirical means are independent across active arms conditional on the past. If desired, the individual observations can be generated from their conditional Gaussian distribution given the mean; the algorithm uses only the mean. Inactive arms receive dummy Poisson increments, which are never revealed to the algorithm. All PAC and reference observations use independent streams. This construction can be iterated adaptively. To be explicit, enlarge the natural joint Poisson filtration by the independent auxiliary randomness. Each current clock endpoint is a stopping time for this filtration. Adding a nonnegative duration measurable at that endpoint again gives a stopping time. The strong Markov property of the joint Poisson process therefore gives fresh independent increments at the next call. Conditional Gaussian generation reveals no future Poisson increments. This proves that the construction realizes precisely the law of the algorithm’s observations, despite adaptive active sets, scales, and sample counts. The conditional Gaussian-law assertions refer to the algorithm’s observed-history filtration, in which unused auxiliary variables remain fresh. The enlarged Poisson filtration is used only to justify stopping times and independent Poisson increments; it may reveal the independent auxiliary reservoir at time zero without changing those properties. By (D.13), pt≤(αt/128)25<1/2p_t≤( _t/128)^25<1/2. Hence every sample path satisfies ∑tλt _t _t ≤2∑tpt≤2∑t(αt/128)25≤2(∑tαt128)25≤2η25=p. ≤ 2 _tp_t≤ 2 _t( _t/128)^25≤ 2 ( _t _t128 )^25≤ 2η^25=p. (E.2) Set Yi=i(p)≥1Y_i=1 \ N_i(p)≥ 1 \. These variables are independent, each has probability 1−e−p≤p1-e^-p≤ p, and they dominate the indicators FiF_i, since the common clock never exceeds p. This is an unconditional coupling; in particular, no future reference upper-bound event is conditioned upon. ∎ E.2 Errors in calls with at most seven arms Let ℱsmallF_small denote the event that underestimation as in (D.12) occurs in any call with 2≤s≤72≤ s≤ 7 in the entire algorithm. The piecewise rule and weight bound give the pathwise bound ∑t:st≤7αt≤γ(j+1)−2 _t:s_t≤ 7 _t≤γ(j+1)^-2 within run j. Conditional union bounds over the arms and calls, followed by ∑tat25≤(∑tat)25 _ta_t^25≤ ( _ta_t )^25 for at≥0a_t≥ 0, therefore imply ℙ(an underestimation event at size at most seven in run j|run j is reached) (an underestimation event at size at most seven in run j |run j is reached ) ≤7∑t:st≤7(αt/128)25≤7η25(j+1)−50. 71.13188pt≤ 7E _t:s_t≤ 7( _t/128)^25≤ 7η^25(j+1)^-50. (E.3) Dropping the probability of reaching a run can only increase the sum. Since ∑m≥1m−50≤1+1/49<2 _m≥ 1m^-50≤ 1+1/49<2, ℙ(ℱsmall)≤14η25.P(F_small)≤ 14η^25. (E.4) We charge this event once and exclude it before summing over the sets defined below. This avoids a factor depending on the number of distinct sets. E.3 A deterministic family of sets of near-optimal arms Fix the original instance and form the sets Bk=i:Δi<2−k/8,k≥0.B_k= \i: _i<2^-k/8 \, k≥ 0. (E.5) Let ℬB be this family with repeated sets removed. It is nested and consists of nonempty subsets containing i[1]i_[1]. There is at most one member of ℬB of any given cardinality. In particular, long intervals of empty gap scales do not enlarge this family. For fixed B∈ℬB , write r=|B|,h=∑i∉BΔi−2,Rr=max1,r−1,Ar=rpRr.r=|B|, h= _i∉ B _i^-2, R_r= \1,r-1\, A_r=rp^R_r. (E.6) Associate an output with B when its final call is at a scale k with Bk=B_k=B. We always fix B first and analyze this output event on the original probability space; we never condition the distribution of observations on selection of B. Consider an incorrect singleton output associated with B and references satisfying the upper bound throughout its run. Every earlier tolerance is at least the final tolerance, so every removed arm in B has an underestimation event by (D.11)–(D.12). If r≥2r≥ 2, a singleton leaves at most one of the r arms in B. If r=1r=1, an incorrect output must remove i[1]i_[1]. Thus Lemma E.1 and a union bound over the possible arm in B with no underestimation event give ℙ(incorrect output associated with B in run j,all reference upper bounds hold in that run)≤Ar.P ( subarraycincorrect output associated with B in run j,\\ all reference upper bounds hold in that run subarray )≤ A_r. (E.7) For r≥2r≥ 2 this is the bound rpr−1rp^r-1; for r=1r=1 it is p. E.4 Small and intermediate weight bounds Fix B and a run with weight budget M=MjM=M_j. Suppose it has an output associated with B, at tolerance d∗d_*. Its final call begins with at least two arms and is included in the weight budget. Every outside arm has Δi≥d∗/8 _i≥ d_*/8. Therefore Dout:=maxi∉BΔi−2≤64d∗−2≤32M,D_out:= _i∉ B _i^-2≤ 64d_*^-2≤ 32M, (E.8) whenever the outside set is nonempty. Both DoutD_out and M are deterministic for this fixed B and run. If their inequality fails, no output can be associated with B; thus use of (E.8) below involves no conditional selection of a random weight bound. Consider an arm i∉Bi∉ B eliminated at tolerance dt≤8Δid_t≤ 8 _i. Its complexity satisfies Δi−2≤64dt−2 _i^-2≤ 64d_t^-2. Charge this complexity to the contribution dt−2d_t^-2 of arm i to the weight of its unique elimination call. The total complexity of all such arms is at most 64M64M. If the output is an outside arm, its complexity is at most 32M32M by (E.8). It follows that when M≤h/192,M≤ h/192, (E.9) outside arms eliminated at tolerances dt>8Δid_t>8 _i have total complexity at least h−96M≥h/2h-96M≥ h/2. Each of them has an underestimation event if its reference satisfies the upper bound. Here is the required weighted Bernoulli estimate, including its constants. Write ai=Δi−2≤32Ma_i= _i^-2≤ 32M and vi=ai/(32M)≤1v_i=a_i/(32M)≤ 1 for i∉Bi∉ B. Since eλv−1≤v(eλ−1)e^λ v-1≤ v(e^λ-1) on 0≤v≤10≤ v≤ 1, independent dominating variables satisfy exp(λ∑i∉BviYi) (λ _i∉ Bv_iY_i ) ≤exp(p∑i∉B(eλvi−1)) ≤ (p _i∉ B (e^λ v_i-1 ) ) ≤exp(ph32M(eλ−1)). ≤ ( ph32M(e^λ-1) ). Choose eλ=1/(2p)e^λ=1/(2p) and apply exponential Markov at h/(64M)h/(64M). This gives ℙ(∑i∉BaiYi≥h/2)≤exp[−h64Mlog12p+h64M]=(2ep)h/(64M).P ( _i∉ Ba_iY_i≥ h/2 )≤ [- h64M 12p+ h64M ]=(2ep)^h/(64M). (E.10) The dominating Bernoulli variables indexed by B and its complement are independent because these sets are fixed and disjoint. Intersecting the underestimation requirement with the requirement on the total complexity of outside arms therefore bounds the relevant incorrect output probability by Ar(2ep)h/(64M).A_r(2ep)^h/(64M). (E.11) Over the dyadic budgets satisfying (E.9), the exponents are at least three and double as budgets decrease. With a0=2ep<1/4a_0=2ep<1/4, their sum is bounded by ∑t≥0a03⋅2t≤a03/(1−a03)<1 _t≥ 0a_0^3· 2^t≤ a_0^3/ (1-a_0^3 )<1. Consequently all small-budget runs contribute at most ArA_r for this fixed B. The intermediate range h/192<M<h/192<M<h contains at most eight dyadic budgets. Using (E.7) at each of them gives total contribution at most 8Ar8A_r. These conclusions also hold when a range is empty or its lower endpoint lies below the first budget. E.5 A bound on eliminating near-optimal arms in one call For large budgets we need to control a call that simultaneously removes several arms in B. Each call uses the confidence parameter computed at its start; this parameter is not recomputed within the call. Lemma E.2 (Eliminating all but at most one near-optimal arm). Fix a set B containing i[1]i_[1] and write h=∑i∉BΔi−2h= _i∉ B _i^-2. Consider an adaptive run whose total weight is at most M, where M≥h>0M≥ h>0. Each call uses fresh estimates (D.5), follows the retention rule (D.7), and has αt≤γwt/M _t≤γ w_t/M. A call is eligible if s≥8s≥ 8, it has at least one active arm in B, and maxi∈BΔi≤d/8 _i∈ B _i≤ d/8. An elimination event occurs when a call retains at most one arm in B when at least two were active, or retains no arm in B when exactly one was active. The probability of any eligible elimination event whose reference satisfies the upper bound is at most 3η4(h/M)3.3η^4(h/M)^3. (E.12) If h=0h=0, an eligible elimination event is impossible. Proof. First assume h>0h>0 and expose the history of an eligible call, including any fresh reference data. Its parameters and whether the reference upper bound holds are now fixed, while its arm estimates remain independent. Set q=|S∩B|,x=w/h,ρ=α/128.q=|S∩ B|, x=w/h, ρ=α/128. On histories satisfying the reference upper bound, an elimination event requires one underestimation event if q=1q=1, and at least q−1q-1 underestimation events for arms in B if q≥2q≥ 2. Thus the conditional probability of an elimination event together with the reference upper bound is at most ρ25,q=1,qρ25(q−1),q≥2≤2ρ25. casesρ^25,&q=1,\\ qρ^25(q-1),&q≥ 2 cases≤ 2ρ^25. (E.13) The last inequality follows from ρ≤η≤1/1280ρ≤η≤ 1/1280; more generally qaq−1≤2aqa^q-1≤ 2a for q≥2q≥ 2 and 0<a≤1/20<a≤ 1/2. When the reference upper bound fails, the intersected event is empty. For a separate bound based on the ordering of empirical means, suppose x≥2x≥ 2 and define g2=s/(8h)g^2=s/(8h). At most hg2=s/8hg^2=s/8 outside arms in the entire original instance have gap below g, since each contributes more than g−2g^-2 to h. Also g2/d2=x/8≥1/4g^2/d^2=x/8≥ 1/4, so every arm in B has mean at least μ[1]−d/8≥μ[1]−g/4 _[1]-d/8≥ _[1]-g/4. The Gaussian tail bound yields ℙ(xi<μ[1]−g/2|ℋt) (x_i< _[1]-g/2 |H_t ) ≤e−mg2/32≤ρ2x, ≤ e^-mg^2/32≤ρ^2x, i∈S∩B, i∈ S∩ B, (E.14) ℙ(xi≥μ[1]−g/2|ℋt) (x_i≥ _[1]-g/2 |H_t ) ≤e−mg2/8≤ρ8x, ≤ e^-mg^2/8≤ρ^8x, i∈S∖B,Δi≥g. i∈ S B,\ _i≥ g. (E.15) The exponents follow by substituting m≥512d−2log(1/ρ)m≥ 512d^-2 (1/ρ) and g2=s/(8h)g^2=s/(8h). When q≥2q≥ 2, first consider the case in which at most one estimate of an arm in B is at least μ[1]−g/2 _[1]-g/2. At least q−1q-1 independent estimates of arms in B then satisfy (E.14). When q=1q=1, define this case instead to mean that its sole estimate is low. In either case its conditional probability is at most 2ρ2x2ρ^2x, by the same elementary inequality used in (E.13). In the complementary case, the elimination event requires omitting an arm in B whose estimate is at least μ[1]−g/2 _[1]-g/2: there are at least two such estimates of arms in B when q≥2q≥ 2, or the sole estimate of an arm in B is high when q=1q=1. Every member of the empirical upper half outranks the omitted arm. At most one member of that upper half is an arm in B, and at most s/8s/8 outside arms have true gap below g. Therefore at least ⌈s/2⌉−1−s/8≥s/4 s/2 -1-s/8≥ s/4 members of the upper half satisfy (E.15). This count is only stronger when q=1q=1, since no arm in B is retained. Let v=⌈s/4⌉v= s/4 . A union bound over v of the at most s far arms, followed by (sv)≤(es/v)v sv≤(es/v)^v, gives probability at most (4eρ8x)v≤(4eρ8x)s/4≤ρ2x.(4eρ^8x)^v≤(4eρ^8x)^s/4≤ρ^2x. Indeed 4eρ8x≤ρ4x<14eρ^8x≤ρ^4x<1 for ρ≤1/1280ρ≤ 1/1280 and x≥2x≥ 2, and s≥8s≥ 8. Combining the two cases gives the bound based on empirical means 3ρ2x3ρ^2x. Combining it with (E.13), using the latter alone for x<2x<2, proves the conditional bound ℙ(eligible elimination event,reference upper bound holds|ℋt)≤3ρmax(25,2x).P ( subarrayceligible elimination event,\\ reference upper bound holds subarray\, |\,H_t )≤ 3ρ (25,2x). (E.16) Put U=M/h≥1U=M/h≥ 1. A permitted call has 0<x≤U0<x≤ U and ρ≤ηx/Uρ≤η x/U. We claim that (ηx/U)max(25,2x)≤(η/U)4x.(η x/U) (25,2x)≤(η/U)^4x. (E.17) For x≤1x≤ 1, use η/U≤1η/U≤ 1 and x25≤x^25≤ x. For 1≤x≤25/21≤ x≤ 25/2, divide the left side by the right side and use U≥xU≥ x to obtain a ratio at most η21x3<1η^21x^3<1. For x≥25/2x≥ 25/2, the ratio is at most η2x−4x3η^2x-4x^3. Its logarithmic derivative 2logη+3/x2 η+3/x is negative, and its value at 25/225/2 is less than one. This proves (E.17) in all cases. Eligibility is determined before the call’s fresh arm estimates. A union bound using predictable conditional probabilities, followed by the pathwise weight bound, now gives ℙ(some eligible elimination event occurswith its reference upper bound holding)≤3(η/U)4∑t eligiblewth≤3(η/U)4U=3η4(h/M)3.P ( subarraycsome eligible elimination event occurs\\ with its reference upper bound holding subarray )≤ 3(η/U)^4E _t eligible w_th≤ 3(η/U)^4U=3η^4(h/M)^3. No future reference upper-bound event has been conditioned upon. Finally, when h=0h=0, the assumption of a unique best arm and positivity of every outside arm complexity imply that no outside arms exist. All active arms belong to B, and retaining the empirical upper half of a set of size s≥8s≥ 8 keeps at least four arms in B. The elimination event is therefore impossible in that case. ∎ E.6 Large weight bounds and the final error bound Exclude ℱz∪ℱsmallF_z _small, and consider an incorrect output associated with a fixed B. If r≥2r≥ 2, take the first call at which the number of active arms in B becomes at most one. If r=1r=1, take the call removing i[1]i_[1]. This is an elimination event of the type in Lemma E.2. Every arm in B has gap less than one eighth of the current tolerance, since B was defined at the final, smallest tolerance. The call must have s≥8s≥ 8: otherwise a removed arm in B would create an underestimation event in ℱsmallF_small. If h=0h=0, such an output is impossible. If h>0h>0 and M≥hM≥ h, (E.7), Lemma E.2, and min(u,v)≤uv (u,v)≤ uv bound its probability by 3Arη2(h/M)3/2. 3A_r\,η^2(h/M)^3/2. (E.18) This step requires no independence between the underestimation events for arms in B and the elimination event. Over dyadic budgets at least h, ∑j:Mj≥h3Arη2(h/Mj)3/2≤31−2−3/2η2Ar<3η2Ar. _j:M_j≥ h 3A_r\,η^2(h/M_j)^3/2≤ 31-2^-3/2η^2 A_r<3η^2 A_r. For completeness, the sums over cardinalities of the near-optimal sets have absolute bounds ∑r≥1Ar≤4p,∑r≥1Ar≤5p. _r≥ 1A_r≤ 4p, _r≥ 1 A_r≤ 5 p. (E.19) The first series equals p+(1−p)−2−1p+(1-p)^-2-1 and is at most 4p4p for p≤1/16p≤ 1/16. For the second, put t=p≤1/4t= p≤ 1/4 and use r≤r r≤ r to bound it by t+(1−t)−2−1≤5t+(1-t)^-2-1≤ 5t. Our value of p satisfies both restrictions. Since ℬB has at most one set of any given size, the small, intermediate, and large ranges together contribute at most ∑r≥1(9Ar+3η2Ar)≤36p+15η2p _r≥ 1 (9A_r+3η^2 A_r )≤ 36p+15η^2 p to the probability of an incorrect output outside the two excluded events. Each single-run bound remains valid conditional on reaching that run, since it starts with fresh data. Dropping reach probabilities justifies all sums over runs above. Adding (D.10) and (E.4), the total probability of any incorrect output is at most δ16+14η25+36p+15η2p δ16+14η^25+36p+15η^2 p =δ16+86η25+152η29/2 = δ16+86η^25+15 2\,η^29/2 <δ. <δ. (E.20) For the last inequality, 0<η<10<η<1 allows both positive powers to be replaced by η, and (86+152)η<108δ/131072(86+15 2)η<108δ/131072. This bounds the probability of an incorrect output by δ on every admissible instance. Combining (E.20) with the almost-sure termination proved in Appendix F establishes δ-correctness in the sense of Section 2: ℙI(τ<∞,ı^=i[1])≥1−δP_I (τ<∞, =i_[1] )≥ 1-δ. Appendix F Expected sample complexity without instance parameters We prove the expected sample complexity bound of Theorem 2.2. The analysis uses sample paths in a good event to show that sufficiently large runs succeed with constant probability. Deterministic sample budgets then control every other path, including paths on which the best arm is eliminated. F.1 A good event in a fresh run First consider a variant of run j that enforces only its weight budget, omitting its sample budget. All confidence and sampling rules remain unchanged. If the best arm is active at a scale entry, accurate PAC selection and an accurate reference estimate imply μ[1]−3d/16≤z≤μ[1]+d/16. _[1]-3d/16≤ z≤ _[1]+d/16. (F.1) As long as the original best remains active, this interval is suitable for every subsequent call at that scale, even if the reference arm is removed. Let N(d)=|i:Δi<d|N(d)= |\i: _i<d\ |, including the original best, so N(dk)=NkN(d_k)=N_k in the notation of Appendix A. We give explicit failure bounds for the modified elimination procedure of Lemma A.3. Given (F.1), an empirical mean of the best within d/16d/16 of its true mean protects it. By (D.9) and (D.5), the probability of failure of this sufficient condition is at most α/64α/64. Any arm with Δi≥d _i≥ d can enter the threshold set only by an upward error of at least 5d/165d/16, whose probability is at most (α/128)25≤α/64(α/128)^25≤α/64. If s>4N(d)s>4N(d) and the threshold set has more than ⌈s/2⌉ s/2 members, more than s/4s/4 far arms have such errors. Markov’s inequality bounds this event by α/16α/16. Otherwise the retention rule returns exactly ⌈s/2⌉ s/2 arms, so the call halves. When s≤4s≤ 4 and every suboptimal active gap is at least d, the sufficient best-arm retention condition and the absence of all far-arm upward errors give the threshold set exactly i[1]\i_[1]\. A union bound makes the failure probability at most α/16α/16. Thus the modified retained set contains the best arm and halves, and at most two such calls finish from size at most four. Charge a scale’s PAC failure once, at its entry call, at most α/16α/16. Charge best-arm retention and required progress failures at every call as above. Their combined conditional probability is less than α. Define jG_j by the absence of these failures and the accuracy of every visited reference estimate. The definition can be made along the successive prefixes until the first failure; the conditional bounds apply while the best is still active. The pathwise inequality ∑tαt≤γ _t _t≤γ and the reference union bound give ℙ(j)≥1−q0,q0=γ+δ/16<1/2,P(G_j)≥ 1-q_0, q_0=γ+δ/16<1/2, (F.2) uniformly for every fresh run. Here δ/16δ/16 is the global bound (D.10) on all reference-estimation failures in the whole stream, which dominates the failure probability of the reference estimates of a single run. This is a per-run sample complexity statement; we do not sum it over runs to prove correctness. F.2 Deterministic bounds on the weights of calls For analysis, let ntn_t count suboptimal gaps in [2−t,2−t+1)[2^-t,2^-t+1), for t≥0t≥ 0, and let K be the largest index of a nonempty group. Define Wk=4k(1+∑t≥knt),W=∑k=0KWk,qk=Wk/W.W_k=4^k (1+ _t≥ kn_t ), W= _k=0^KW_k, q_k=W_k/W. (F.3) Lemma A.5 states H≤W<323H,Ent(q)≤323Ent(I)+C0,4K≤4D,H≤ W< 323H, (q)≤ 323 (I)+C_0, 4^K≤ 4D, (F.4) where Ent(q) (q) is Shannon entropy and C0C_0 is universal. On jG_j, a scale can stall only if its input size is at most 4N(d)4N(d). At scale zero the entry size is n. At scale k≥1k≥ 1, the preceding scale could have ended only by such a stall, so the entry size is at most 4N(2−(k−1))=4(1+∑t≥knt).4N(2^-(k-1))=4 (1+ _t≥ kn_t ). An accepted same-scale continuation decreases its input size by at least a factor 3/43/4. If r=0,1,…r=0,1,… indexes the successive calls at scale k, this gives wk,r≤vk,r:=4Wk(3/4)r,V:=∑k=0K∑r≥0vk,r=16W<171H.w_k,r≤ v_k,r:=4W_k(3/4)^r, V:= _k=0^K _r≥ 0v_k,r=16W<171H. (F.5) At scale K, all suboptimal gaps are at least 2−K2^-K. More than four arms therefore halve, and at most four arms finish in at most two further calls. Thus a sample path in jG_j finishes by scale K, provided the weight bound permits those calls. This last proviso does not assume the conclusion: the same upper bounds apply to every executed prefix in jG_j and its prospective next call. If hj≥Hh_j≥ H, their cumulative prospective weight is below 171H<Mj=1024hj171H<M_j=1024h_j. No such prefix can abort at the weight bound. This proves both completion by scale K and the bounds on call weights for the process constrained only by the weight bound. F.3 Sample complexity on the good event Write h=hj≥Hh=h_j≥ H. By Lemma A.2, the declared arm and PAC cost of a call is at most Cwlog(128/α)Cw (128/α) for a universal constant C; assigning this cost at every call also bounds the PAC cost, which occurs only at scale entry. Temporarily omit the additional small-size term 2log(j+1)2 (j+1) in log(128/α) (128/α). The resulting baseline cost is bounded by a constant times ∑k,rwk,rlog128Mjγwk,r. _k,rw_k,r 128M_jγ w_k,r. The function f(x)=xlog(128Mj/(γx))f(x)=x (128M_j/(γ x) ) is increasing on (0,Mj](0,M_j]. Each upper bound vk,rv_k,r lies below V<171H<MjV<171H<M_j, so (F.5) permits termwise replacement of wk,rw_k,r by vk,rv_k,r. Let πr=14(3/4)r _r= 14(3/4)^r; normalizing these upper bounds gives vk,r/V=qkπrv_k,r/V=q_k _r. Hence ∑k=0K∑r≥0f(vk,r) _k=0^K _r≥ 0f(v_k,r) =V[log128MjγV+Ent(q)+Ent(π)] =V [ 128M_jγ V+ (q)+ (π) ] ≤CH[L+Ent(I)+1+log(h/H)]. ≤ CH [L+ (I)+1+ (h/H) ]. (F.6) Here 16H≤V<171H16H≤ V<171H, Mj=1024hM_j=1024h, γ=δ/1024γ=δ/1024, (F.4) holds, and the geometric distribution π has bounded entropy. Only calls with s≤7s≤ 7 incur the additional sample cost due to the factor (j+1)−2(j+1)^-2 in the confidence allocation. Their extra cost is at most 2Cs4klog(j+1)2Cs4^k (j+1) per call. At any fixed scale, once the size is at most seven, successive call sizes follow a sequence bounded by 7,4,27,4,2: a continuation halves rounded up, and a stall ends the scale. This includes the last possibly stalled call. Consequently ∑t at scale kst≤7st≤13,additional sample cost≤CDlog(j+1). _ subarrayct at scale k\\ s_t≤ 7 subarrays_t≤ 13, sample cost≤ CD (j+1). (F.7) The PAC procedure contributes this additional cost only if the entry call has at most seven arms, so it is already covered by the same bound. Calls of size at least eight incur no such additional cost. There is one reference estimate per visited scale. Its declared cost from (D.6) is at most C∑k=0K4k[L+1+log(j+1)+log(k+1)] C _k=0^K4^k [L+1+ (j+1)+ (k+1) ] ≤CD[L+log(j+1)+ℓ(D)], ≤ CD [L+ (j+1)+ (D) ], (F.8) where ℓ(D)=log(e+log(e+D)) (D)= (e+ (e+D) ). Indeed, ∑k=0K4k≤(4/3)4K≤16D/3 _k=0^K4^k≤(4/3)4^K≤ 16D/3, and K≤log4(4D)K≤ _4(4D) makes log(K+1)≤Cℓ(D) (K+1)≤ C (D). Integer ceilings in all sample counts are absorbed by these estimates: 4k≥14^k≥ 1 and all confidence logarithms exceed one. Combining (F.6)–(F.8), on jG_j, every run constrained only by the weight bound with hj≥Hh_j≥ H has total declared sample cost at most Bjgood=CgoodH[L+Ent(I)+1+log(hj/H)]+D[L+log(j+1)+ℓ(D)],B_j^good=C_good \H [L+ (I)+1+ (h_j/H) ]+D [L+ (j+1)+ (D) ] \, (F.9) for a fixed universal CgoodC_good. In particular, this bounds the sum of the complete prospective call reservations, not only samples observed before a possible sample-budget rejection. F.4 Choosing the fixed budget constant and summing all trajectories Define, for analysis only, Ψ=H[L+Ent(I)+1]+Dℓ(D),j∗=⌈log2(Ψ/L)⌉. =H [L+ (I)+1 ]+D (D), j_*= _2( /L) . (F.10) Because the means lie in [0,1][0,1] and n≥2n≥ 2, we have H≥D≥1H≥ D≥ 1. Thus j∗≥0j_*≥ 0, hj∗∈[Ψ/L,2Ψ/L]h_j_*∈[ /L,2 /L], and hj≥Hh_j≥ H for all j≥j∗j≥ j_*. For such j, set h=hjh=h_j. Then Ψ≤hL,Hlog(h/H)≤h. ≤ hL, H (h/H)≤ h. We also have the uniform estimate log(j+1)≤C+ℓ(D)+log(h/D). (j+1)≤ C+ (D)+ (h/D). (F.11) To see this, put y=log(h/D)≥0y= (h/D)≥ 0. Since j=logh/log2j= h/ 2, the quantity j+1j+1 is at most C(1+logD+y)C(1+ D+y). The inequality 1+logD+y≤(1+logD)(1+y)1+ D+y≤(1+ D)(1+y) and log(1+y)≤y (1+y)≤ y yield (F.11). Finally, Dlog(h/D)≤hD (h/D)≤ h. Substituting these estimates into (F.9), using D≤HD≤ H and L>log10L> 10, gives Bjgood≤C∗hjL(j≥j∗),B_j^good≤ C_*h_jL (j≥ j_*), (F.12) for an absolute constant C∗C_* determined only by CPACC_PAC, CelimC_elim, CgoodC_good, and the ratio γ/δ=1/1024γ/δ=1/1024; it does not depend on n, δ, or the instance. Fix once and for all CQ:=C∗C_Q:=C_*; any larger absolute constant also works. This choice is noncircular: neither the analysis with only the weight bound enforced nor C∗C_* depends on CQC_Q. Couple the run enforcing both budgets to the run enforcing only the weight budget, using the same samples. On jG_j with j≥j∗j≥ j_*, the weight bound permits completion, and its total declared sample cost fits QjQ_j by (F.12). Every complete-call reservation therefore passes. The event that run j is reached is determined by the observations of runs j′<j <j, while run j uses fresh observations independent of them; hence, conditional on being reached, run j has the law of a fresh run and the bound (F.2) applies conditionally. Conditional on being reached, each such run thus returns the correct arm with probability at least 1−q01-q_0. Reaching the next run requires failure to return, so induction gives ℙ(run j∗+t is reached)≤q0t,t≥0.P (run j_*+t is reached )≤ q_0^t, t≥ 0. (F.13) Returning an incorrect arm only decreases the probability of reaching subsequent runs, so it does not invalidate this bound. Let τ be the total sample count, allowing the value +∞+∞. Tonelli’s theorem and the deterministic budget Tj≤QjT_j≤ Q_j give Iτ _Iτ ≤∑j<j∗Qj+∑t≥0Qj∗+tq0t ≤ _j<j_*Q_j+ _t≥ 0Q_j_*+tq_0^t ≤CQj∗(1+∑t≥0(2q0)t)=O(Qj∗)=O(Ψ). ≤ CQ_j_* (1+ _t≥ 0(2q_0)^t )=O(Q_j_*)=O( ). (F.14) Here 2q0<12q_0<1, the earlier budgets form a geometric sum, and their ceilings change only the absolute constants. Each run is finite, and (F.13) also shows that the probability of infinitely many runs is zero. Thus the algorithm stops almost surely and has finite expected number of samples on every instance with a unique best arm. Finally, L>log10L> 10 absorbs the additive H in Ψ , proving Iτ≤CH[log(1/δ)+Ent(I)]+Dℓ(D).E_Iτ≤ C \H [ (1/δ)+ (I) ]+D (D) \. Together with (E.20), this completes the proof of Theorem 2.2. All quantities defining B, H, D, K, W, Ψ , and j∗j_* are used exclusively in the proof; the algorithm requires none of these quantities as input. Appendix G Consequences and normalization The normalization in our model allows a direct interpretation in physical measurement units. Suppose an observation from arm i has law (νi,σ2)N ( _i,σ^2 ), where σ>0σ>0 is known and common to all arms, observations are independent, and νi∈[a,a+σ] _i∈[a,a+σ] for a known a. Transform each observation by Y=(X−a)/σY=(X-a)/σ. This preserves the best arm and maps the experiment exactly to the model of Section 2. The transformation preserves the order i[r]i_[r] of the arm labels. Write ν[r]=νi[r] _[r]= _i_[r], gi=ν[1]−νig_i= _[1]- _i, and g[r]=gi[r]g_[r]=g_i_[r], and let Iσ=((νi−a)/σ)i=1nI_σ= (( _i-a)/σ )_i=1^n be the normalized instance. With Hσ=H(Iσ)H_σ=H(I_σ) and Dσ=D(Iσ)D_σ=D(I_σ), Theorem 2.2 gives Hσ=∑i≠i[1]σ2gi2, H_σ= _i≠ i_[1] σ^2g_i^2, Dσ=σ2g[2]2, D_σ= σ^2g_[2]^2, (G.1) τ τ =O(Hσ[log(1/δ)+Ent(Iσ)]+Dσℓ(Dσ)), =O\! (H_σ [ (1/δ)+ (I_σ) ]+D_σ (D_σ) ), Here g[2]g_[2] is the smallest positive unnormalized gap, and Ent(Iσ) (I_σ) is computed from the normalized gaps gi/σg_i/σ. Each normalized observation uses exactly one original observation, so the complexity depends on squared noise-to-gap ratios rather than on the origin or units of the reported scores. The algorithm receives no estimate of these ratios or of their distribution across scales, and its guarantee holds for every labeling of the same arms. An independent initial random permutation makes an implementation explicitly invariant to labels while preserving correctness and the sample bound. The order-oblivious instance-wise lower bound therefore measures difficulty intrinsic to the mean vector, without rewarding a favorable input order. In the normalized model, Theorems 2.1 and 2.2 give a criterion for matching the order-oblivious instance-wise lower bound: TA(I)ℒ(I,δ)=O(1+ℓ(D)(H/D)[L+Ent(I)]). T_A(I)L(I,δ)=O\! (1+ (D)(H/D) [L+ (I) ] ). (G.2) The factor H/D=∑i≠i[1](Δ[2]/Δi)2H/D= _i≠ i_[1]( _[2]/ _i)^2 is the instance complexity divided by the complexity of an arm with the smallest positive gap. Whenever (H/D)[L+Ent(I)]≥ℓ(D)(H/D) [L+ (I) ]≥ (D), the additional term is absorbed into the instance-wise lower bound. If all n−1n-1 suboptimal gaps are equal, then H=(n−1)DH=(n-1)D and Ent(I)=0 (I)=0, so the condition becomes (n−1)L≥ℓ(D)(n-1)L≥ (D): unknown-gap adaptation is absorbed by the ordinary confidence cost even though the common gap is not known to the procedure. Noisy model selection and hyperparameter comparison are covered only when their score measurements meet the same assumptions: reused validation data can create dependence between observations, losses need not be Gaussian, and configurations can differ in noise variance or measurement cost. The present theorems do not justify substituting such scores into the Gaussian procedure without an observation model and corresponding concentration arguments. Appendix H Internal randomness and the scope of the algorithm model The algorithms of Section 2 draw an internal random seed Z=(Z0,Z1,…)Z=(Z_0,Z_1,…) with law Γ=(0,1)⊗ℕ =N(0,1) , independent of all rewards, and apply a measurable rule to the seed and the finite observed history. This appendix records the scope of that model. The instance-wise lower bound (2.1) is unchanged when the seed may be drawn from an arbitrary standard Borel probability space (Proposition H.3); the algorithms of Appendices C and D use no internal randomness (Proposition H.4); algorithms with an explicit abandonment action and algorithms specified by history-dependent probability kernels are covered by the lower bound (Propositions H.5 and H.6). Appendix H.7 compares the truncated iterated logarithm ℓ of (2.3) with the untruncated expression of Chen and Li (2016). These statements are also covered by the formal development described in Appendix I. H.1 Algorithms with a standard Borel internal random seed Fix an arm count n≥2n≥ 2. Write t=([n]×ℝ)tO_t= ([n]×R )^t for the space of observation histories of length t and n=(i),(i):i∈[n]A_n= \ sample(i), return(i):i∈[n] \ for the finite decision space. Let (S,μ)(S,μ) be a standard Borel space with a probability measure. A randomized algorithm on (S,μ)(S,μ) is a family of measurable maps at:S×t→n,t≥0.a_t:S×O_t _n, t≥ 0. The seed is drawn once from μ, independently of all rewards; the algorithm receives neither the means nor the best label. A family of algorithms may choose S, μ, and the decision rules separately for each arm count and each confidence input. The model of Section 2 is the case (S,μ)=(ℝℕ,Γ)(S,μ)=(R^N, ). For an instance I, let QIQ_I be the law of the reward table r=(rt,i)t≥0,i∈[n]r=(r_t,i)_t≥ 0,i∈[n] of independent (μi,1)N( _i,1) variables. Execution uses the product law μ⊗QIμ Q_I. The state at time 00 is the empty history. At an active state h∈th _t with seed s, the decision at(s,h)=(i)a_t(s,h)= sample(i) moves to the history (h,(i,rt,i))∈t+1 (h,(i,r_t,i) ) _t+1, and at(s,h)=(i)a_t(s,h)= return(i) moves to the absorbing state (i) return(i). Write runa(s,r,t)run_a(s,r,t) for the state at time t; it is a measurable function of (s,r)(s,r). Since row t of the table is independent of the seed and of the earlier rows, the sampled entry is a fresh (μi,1)N( _i,1) observation conditional on the past, as in Section 2. Success is the event that runa(s,r,t)=(i[1])run_a(s,r,t)= return(i_[1]) for some finite t. The sample count is the number of sampling decisions, τa(s,r)=∑t≥0runa(s,r,t+1)∈t+1∈[0,∞], _a(s,r)= _t≥ 01 \run_a(s,r,t+1) _t+1 \∈[0,∞], which is the first return time of Section 2, and Ta(I)=∫τad(μ⊗QI)∈[0,∞]T_a(I)= _a\,d(μ Q_I)∈[0,∞] is its unconditional expectation. Neither almost-sure termination nor finite expectation is required separately. These definitions do not refer to the model with Gaussian random seeds or to any complexity bound. H.2 Representing internal randomness by a Gaussian seed Lemma H.1 (Randomization lemma). For every standard Borel probability space (S,μ)(S,μ) there is a measurable map fμ:ℝℕ→Sf_μ:R^N→ S with (fμ)#Γ=μ(f_μ)_\# =μ. The map depends on μ only, not on the instance. Proof. Let Φ be the distribution function of (0,1)N(0,1) and U the uniform law on [0,1][0,1]. Since Φ is continuous and strictly increasing, Φ(z0) (z_0) has law U under Γ ; it suffices to compare the measures of the lower intervals [0,u][0,u], including the endpoints u=0u=0 and u=1u=1. By the measurable representation theorem for probability measures on standard Borel spaces, there is a measurable gμ:[0,1]→Sg_μ:[0,1]→ S with (gμ)#=μ(g_μ)_\# U=μ. Put fμ(z)=gμ(Φ(z0))f_μ(z)=g_μ ( (z_0) ). The space S is nonempty because it carries a probability measure, and no atomlessness of μ is needed. ∎ The lemma concerns measurable maps only; it does not assert that fμf_μ is computable from finitely many random bits or within a prescribed running time. Lemma H.2 (Equality of sample paths under seed simulation). Let a be a randomized algorithm on (S,μ)(S,μ), let fμf_μ be as in Lemma H.1, and define the algorithm with a Gaussian random seed bt(z,h)=at(fμ(z),h)b_t(z,h)=a_t (f_μ(z),h ). For every reward table r and every t, runb(z,r,t)=runa(fμ(z),r,t).run_b(z,r,t)=run_a (f_μ(z),r,t ). (H.1) Consequently, on every instance I, b and a have the same law of the complete state sequence (run(t))t≥0 (run(t) )_t≥ 0, the same success probability, and the same expected number of samples in [0,∞][0,∞]; and b terminates almost surely if and only if a does. Proof. Each btb_t is measurable as a composition. Identity (H.1) follows by induction on t: both executions start from the empty history, a returned label is absorbing, and at an active history the two decisions agree and a sampling decision reads the same entry of r. One coupling therefore works at every time; it preserves every requested arm and the full sample count, including on erroneous and nonreturning paths. The map ψ(z,r)=(fμ(z),r)ψ(z,r)= (f_μ(z),r ) takes Γ⊗QI Q_I to μ⊗QIμ Q_I. Pushing (H.1) forward gives equality of the laws of the entire state sequences, and applying ψ to the measurable success and termination events gives the two probability statements. Finally, ∫τbd(Γ⊗QI)=∫τa∘ψd(Γ⊗QI)=∫τad(μ⊗QI) _b\,d( Q_I)= _a ψ\,d( Q_I)= _a\,d(μ Q_I) by the change-of-variables formula for nonnegative measurable functions, which needs no integrability. The same b and ψ serve for every I. ∎ H.3 Equality of the instance-wise lower bounds Let SB A_SB be the class of families A=(A(n))n≥2A=(A^(n))_n≥ 2 in which A(n)A^(n) is a randomized algorithm for n arms on a standard Borel probability space that may depend on n. Such a family is δ-correct if its success probability is at least 1−δ1-δ on every admissible instance at every arm count. Define ℒSB(I,δ)=infA∈SB:A is δ-correct1n!∑π∈nTA(πI),L_SB(I,δ)= _A∈ A_SB:\ A is δ-correct 1n! _π∈ S_nT_A(π I), (H.2) with all expectations and the infimum in [0,∞][0,∞]. The instance-wise lower bound ℒ(I,δ)L(I,δ) of (2.1) is the same infimum over the algorithm families with Gaussian random seeds of Section 2. Proposition H.3 (Equality of the instance-wise lower bounds). For every admissible instance I and every 0<δ<10<δ<1, ℒSB(I,δ)=ℒ(I,δ)L_SB(I,δ)=L(I,δ). Proof. The space ℝℕR^N is Polish and Γ is a Borel probability measure on it, so every algorithm family with Gaussian random seeds belongs to SB A_SB with the same success probabilities and costs. Hence ℒSB≤ℒL_SB . Conversely, let A∈SBA∈ A_SB be δ-correct and apply Lemma H.2 to the distribution of the internal random seed of A(n)A^(n) for each n. The resulting algorithm family with Gaussian random seeds has the same success probability on every instance, hence is δ-correct, and the same expected sample count on every relabeling πIπ I. Hence ℒ≤ℒSBL _SB. No minimizer, finite expectation, or termination assumption is used. ∎ Theorem 2.1, the consequence TA(I)=O(ℒ(I,δ)+Dℓ(D))T_A(I)=O (L(I,δ)+D (D) ) of Theorem 2.2, and Corollary H.7 below therefore hold with their stated constants when the instance-wise lower bound is taken over SB A_SB. This is an equality of instance-wise lower bounds, not merely the inclusion of the algorithms with Gaussian random seeds in a larger class. H.4 The upper-bound algorithms need no internal randomness Call an algorithm with a Gaussian random seed b seed independent if bt(z,h)=bt(z′,h)b_t(z,h)=b_t(z ,h) for all z,z′∈ℝℕz,z ^N, all h, and all t. Proposition H.4 (Deterministic algorithms). The algorithm with a fixed target instance of Appendix C and the single algorithm of Appendix D are both seed independent, at every arm count and every confidence input. Each therefore admits measurable decision functions of the observation history alone, and reinterpreting these functions as an algorithm with a Gaussian random seed gives back exactly the original algorithm. Proof. The primitives of Appendix A draw deterministic numbers of samples and compute the median-elimination output, the reference estimate, the retained set, and the fixed tie rule from the observed values alone. The run loops of both algorithms, their budgets and abort rules, the scale changes, and the fallback of Appendix C are functions of the observed values and of fixed parameters, in every parameter branch. Interleaving two seed-independent streams sample by sample is seed independent. Following the definitions of the two algorithms therefore proves seed independence of the complete families. Evaluating a seed-independent measurable algorithm at one fixed seed z0z^0 gives a measurable function of the history alone, namely a section of a jointly measurable map, and seed independence gives bt(z,h)=bt(z0,h)b_t(z,h)=b_t(z^0,h) for every z. ∎ Accordingly, both algorithms belong to SB A_SB with a one-point seed space and its Dirac law. Their correctness, almost-sure termination, finite expected number of samples, and cost bounds are those established in Appendices C and D–F; this appendix does not replace them by new procedures. The model permits arbitrary measurable dependence on a complete internal random seed, but every external action is a sampling or return decision. The statements above concern this standard Borel formulation; they are not theorems about arbitrary measurable spaces, arbitrary program syntax, or nonterminating internal computation between two external actions. H.5 Explicit abandonment One may enlarge the decision space by an action abandon: it is absorbing, requests no further sample, and does not count as a correct return. Execution, success, and τ are defined as in Appendix H.1, with the abandoned state as a second kind of terminal state. Proposition H.5 (Completion of explicit abandonment). For every measurable algorithm a with this additional action there is a measurable sample-or-return algorithm a¯ a on the same seed space, executed with the same seed and reward table, such that on every path the two executions make the same sampling requests, Ta¯(I)=Ta(I)T_ a(I)=T_a(I) on every instance, and the success probability of a¯ a is at least that of a. Proof. Let a¯t(s,h)=(1) a_t(s,h)= return(1) when at(s,h)=a_t(s,h)= abandon and a¯t(s,h)=at(s,h) a_t(s,h)=a_t(s,h) otherwise. Define θ on states by fixing every active history and every returned label and mapping the abandoned state to (1) return(1). Induction on t gives runa¯(s,r,t)=θ(runa(s,r,t))run_ a(s,r,t)=θ (run_a(s,r,t) ): the decisions agree at every active history, and both kinds of terminal state are absorbing. In particular the state is active at time t+1t+1 under a¯ a exactly when it is active under a, so τa¯=τa _ a= _a pathwise; integrating gives the cost identity. Every correct return of a is a correct return of a¯ a, and an abandoned path may in addition become a correct return, so monotonicity of measure gives the success inequality. ∎ Applied at each arm count, the completion preserves correctness and the expected sample count on every relabeling πIπ I, so Proposition H.3 extends to families with an abandonment action. It does not preserve the complete return law or the exact success probability. An explicit measurable abandonment action is also distinct from unobservable nonterminating internal computation between two external decisions; the proposition makes no claim about the latter. H.6 History-dependent probability kernels A second formulation specifies, for each t≥0t≥ 0, a probability kernel κt _t from tO_t to the finite set nA_n, that is, measurable functions h↦κt(h,d)h _t (h,\d\ ), d∈nd _n, summing to one. Its state laws are defined directly, without a sampler: ν0I _0^I is the Dirac mass at the empty history, and νt+1I _t+1^I is the image of νtI _t^I under the transition that fixes every returned label, moves an active h∈th _t to (i) return(i) with probability κt(h,(i)) _t (h, \ return(i) \ ), and with probability κt(h,(i)) _t (h, \ sample(i) \ ) appends (i,x)(i,x) with x∼(μi,1)x ( _i,1). The direct success probability and unconditional cost are pK(I)=supt≥0νtI((i[1])),TK(I)=∑t≥0νt+1I(t+1).p_K(I)= _t≥ 0 _t^I ( \ return(i_[1]) \ ), T_K(I)= _t≥ 0 _t+1^I(O_t+1). (H.3) The index t+1t+1 is essential: a sample is taken at time t exactly when the state at time t+1t+1 is active. The supremum over t of the νtI _t^I-probability of all returned labels is the total return probability; the algorithm specified by probability kernels terminates almost surely when it equals one. Proposition H.6 (Implementation of randomized decision rules). Every algorithm specified by probability kernels K=(κt)t≥0K=( _t)_t≥ 0 can be implemented by an algorithm with an internal random seed, and hence, by Lemma H.2, by an algorithm with a Gaussian seed, chosen before the instance is known. On every admissible instance it has success probability pK(I)p_K(I) and expected number of samples TK(I)T_K(I), and it terminates almost surely if and only if the total return probability of K equals one. Applied at every arm count, the implementation preserves correctness and the permutation average of the direct costs. Proof. Enumerate n=d1,…,d2nA_n=\d_1,…,d_2n\ and define Ft(h,u)=dmfor the least m with u<∑l≤mκt(h,dl),Ft(h,1)=d2n.F_t(h,u)=d_m the least $m$ with u< _l≤ m _t (h,\d_l\ ), F_t(h,1)=d_2n. Then FtF_t is jointly measurable and (u:Ft(h,u)=d)=κt(h,d) U ( \u:F_t(h,u)=d \ )= _t (h,\d\ ) for every h and d. Take the seed space [0,1]ℕ[0,1]^N with the law ⊗ℕ U and the decisions at(u,h)=Ft(h,ut)a_t(u,h)=F_t(h,u_t). The state runa(u,r,t)run_a(u,r,t) is a function of u0,…,ut−1u_0,…,u_t-1 and of the first t rows of r, so the pair (ut,rt,⋅)(u_t,r_t,·) is independent of it, and utu_t is independent of rt,⋅r_t,·. By independence and Tonelli’s theorem, the law of runa(u,r,t+1)run_a(u,r,t+1) is the image of the law of runa(u,r,t)run_a(u,r,t) under the direct transition: from an active h the decision Ft(h,ut)F_t(h,u_t) has law κt(h,⋅) _t(h,·), and given (i) sample(i) the appended value rt,ir_t,i has law (μi,1)N( _i,1). Induction gives LawI(runa(u,r,t))=νtILaw_I (run_a(u,r,t) )= _t^I for every t. The events runa(u,r,t)=(i[1]) \run_a(u,r,t)= return(i_[1]) \ increase in t because returns are absorbing, and their union is the success event; continuity from below gives the success probability pK(I)p_K(I). The sampling indicator at time t is the indicator that the state at time t+1t+1 is active, so Tonelli’s theorem gives Ta(I)=TK(I)T_a(I)=T_K(I), including the value +∞+∞. The same absorbing-event argument for all returned labels gives the termination equivalence. Since [0,1]ℕ[0,1]^N is standard Borel, Lemma H.2 transports the implementation to the model with Gaussian random seeds with the same three quantities. The construction does not depend on I, so applying it at every arm count preserves correctness and every permutation average. ∎ In particular, every δ-correct algorithm specified by K satisfies ℒ(I,δ)≤1n!∑π∈nTK(πI),L(I,δ)≤ 1n! _π∈ S_nT_K(π I), (H.4) so the lower bound of Theorem 2.1 applies to the direct costs of the probability-kernel formulation. This is the comparison direction used in this paper; it does not identify the infimum over families of probability kernels with the infimum over randomized algorithms, and no converse representation of every randomized algorithm by history-dependent probability kernels is claimed. The formal development (Appendix I) establishes the finite-time state laws and the three conclusions above, not a separate equality of measures on an independently constructed infinite trace space. H.7 The logarithmic convention The additive term of Conjecture 3.2 of Chen and Li (2016) is written there as Δ[2]−2lnlnΔ[2]−1 _[2]^-2 _[2]^-1. This expression is negative for e−1<Δ[2]<1e^-1< _[2]<1 and undefined at the admissible gap Δ[2]=1 _[2]=1, so a positive convention is needed. The paper uses ℓ(D)=log(e+log(e+D)) (D)= (e+ (e+D) ) with D=Δ[2]−2D= _[2]^-2, see (2.3); Section 2 also introduces g(Δ)=max1,loglog(1/Δ)g( )= \1, (1/ ) \ for 0<Δ<10< <1 and g(1)=1g(1)=1. Both agree with the untruncated expression to first order as the gap vanishes: with x=log(1/Δ)x= (1/ ), log(e+Δ−2)=2x+log(1+eΔ2)=2x+o(1) (e+ ^-2)=2x+ (1+e ^2)=2x+o(1), and one more logarithm gives ℓ(Δ−2)=loglog(1/Δ)+log2+o(1)(Δ→0). ( ^-2)= (1/ )+ 2+o(1) ( → 0). (H.5) Hence Δ−2ℓ(Δ−2) ^-2 ( ^-2) and Δ−2loglog(1/Δ) ^-2 (1/ ) have the same asymptotic order. On the whole admissible range the two positive conventions are equivalent up to absolute constants: g(Δ)≤ℓ(Δ−2)≤7g(Δ)(0<Δ≤1).g( )≤ ( ^-2)≤ 7g( ) (0< ≤ 1). (H.6) To prove (H.6), let x=log(1/Δ)≥0x= (1/ )≥ 0, so that D=Δ−2=e2x≥1D= ^-2=e^2x≥ 1. Since e<3De<3D, log(e+D)≤log(4D)≤3+2x (e+D)≤ (4D)≤ 3+2x, and therefore 1<ℓ(D)≤log(6+2x)1< (D)≤ (6+2x). For the lower bound, if x>0x>0 then e+log(e+D)>logD=2x>xe+ (e+D)> D=2x>x, so ℓ(D)>logx=loglog(1/Δ) (D)> x= (1/ ); together with ℓ(D)>1 (D)>1 this gives ℓ(D)≥g(Δ) (D)≥ g( ), and at Δ=1 =1 we have g(1)=1<ℓ(1)g(1)=1< (1). For the upper bound, if x≤1x≤ 1 then ℓ(D)≤log8<6≤7g(Δ) (D)≤ 8<6≤ 7g( ); if x>1x>1 then 6+2x≤8x6+2x≤ 8x, so ℓ(D)≤log8+logx≤6+logx≤7max1,logx=7g(Δ) (D)≤ 8+ x≤ 6+ x≤ 7 \1, x\=7g( ). Theorem 2.2 may therefore be stated equivalently with Dg(Δ[2])Dg( _[2]) in place of Dℓ(D)D (D). No comparison of the form Dℓ(D)≤Dloglog(1/Δ[2])+O(D)D (D)≤ D (1/ _[2])+O(D) holds uniformly, because the right-hand side tends to −∞-∞ as Δ[2]→1 _[2]→ 1. Corollary H.7 (Small gaps and gaps bounded away from zero). Let Δ=Δ[2] = _[2] and 0<δ<0.10<δ<0.1. The algorithm of Theorem 2.2 satisfies TA(I) T_A(I) =O(ℒ(I,δ)+Δ−2loglog(1/Δ)) =O (L(I,δ)+ ^-2 (1/ ) ) (0<Δ≤e−e), (0< ≤ e^-e), (H.7) TA(I) T_A(I) =O(ℒ(I,δ)) =O (L(I,δ) ) (e−e<Δ≤1). (e^-e< ≤ 1). (H.8) Proof. Put D=Δ−2D= ^-2. By Theorem 2.1, H[log(1/δ)+Ent(I)]=O(ℒ(I,δ))H [ (1/δ)+ (I) ]=O (L(I,δ) ), so Theorem 2.2 gives TA(I)=O(ℒ(I,δ)+Dℓ(D))T_A(I)=O (L(I,δ)+D (D) ). In the first regime let x=log(1/Δ)≥ex= (1/ )≥ e, so D=e2x>eD=e^2x>e. Then e+D<2De+D<2D and e+log(e+D)<e+log2+2x≤4xe+ (e+D)<e+ 2+2x≤ 4x, the last step because e+log2<2e≤2xe+ 2<2e≤ 2x. Hence ℓ(D)<log(4x)=log4+logx≤3logx (D)< (4x)= 4+ x≤ 3 x, using log4<2≤2logx 4<2≤ 2 x. Thus Dℓ(D)≤3Δ−2loglog(1/Δ)D (D)≤ 3 ^-2 (1/ ), which gives (H.7). At the endpoint Δ=e−e =e^-e the double logarithm equals one. In the second regime 1≤D<e2e1≤ D<e^2e. The function ℓ is increasing and e+e2e<2e2e+e^2e<2e^2e, so ℓ(D)≤ℓ(e2e)<log(3e+log2)<log(4e)<3 (D)≤ (e^2e)< (3e+ 2)< (4e)<3. Hence Dℓ(D)<3D≤3HD (D)<3D≤ 3H, because D is one of the summands of H. Since log(1/δ)>log10 (1/δ)> 10 and Ent(I)≥0 (I)≥ 0, H≤H[log(1/δ)+Ent(I)]/log10=O(ℒ(I,δ))H≤ H [ (1/δ)+ (I) ]/ 10=O (L(I,δ) ) by Theorem 2.1, which gives (H.8). The two-arm term is thus absorbed into the instance-wise lower bound in the final bound; it does not disappear from the intermediate cost analysis of Appendix F. ∎ Corollary H.7 states the untruncated term on an explicit small-gap range where it is at least one and asymptotically active, and the bound in terms of the instance-wise lower bound alone on the remaining bounded range. For e−e<Δ≤e−1e^-e< ≤ e^-1, (H.8) also implies (H.7) because loglog(1/Δ)≥0 (1/ )≥ 0 there. The corollary does not assert the literal untruncated display for every gap: that expression is negative for e−1<Δ<1e^-1< <1 and undefined at Δ=1 =1. By Proposition H.3, both displays hold verbatim with ℒSB(I,δ)L_SB(I,δ) in place of ℒ(I,δ)L(I,δ). Explicit conventions of this kind appear in the related literature. Jamieson et al. (2014) use in their sample complexity bound the truncated function loglog+(x) _+(x), equal to loglogx x for x≥ex≥ e and to 00 otherwise, so that it is defined and nonnegative throughout 0<Δi≤10< _i≤ 1, and Chen et al. (2017) work in a regime in which the confidence parameter and all gaps tend to zero. Section 2 states the present boundary convention explicitly; it is not attributed to the problem statement of Chen and Li (2016). Appendix I Machine-checked verification The definitions of Section 2 and the main statements of this paper have been formalized and proved in the Lean 4 proof assistant (de Moura and Ullrich, 2021) on top of the Mathlib library, whose original design is described by The mathlib community (2020). The development accompanies this manuscript. This appendix states what is verified, how the formal statements relate to the theorems as printed, and where the formal proofs deviate from the presentation in Appendices A–F. Formal model. An instance is a vector in [0,1]n[0,1]^n with n≥2n≥ 2 and a unique maximum. An algorithm is a measurable function of an internal random seed, distributed as an infinite sequence of independent standard Gaussian variables, and of the finite observation history, with values in the sample-or-return decision space; rewards form an independent Gaussian table and a sampling decision appends the requested entry to the history. Success is the event that the best label is returned at some finite time; the sample count is the sum of the sampling indicators, with value +∞+∞ on nonreturning paths; its expectation is the unconditional integral in [0,∞][0,∞]. δ-correctness quantifies over every instance of every arm count, and the instance-wise lower bound is the infimum over δ-correct algorithm families of the average over all n!n! relabelings, exactly as in (2.1). The gap groups, H, D, and Ent(I) (I) are defined as in (2.2)–(2.3). An independently written transcription of these definitions and of the target statements was checked, by definitional unfolding, to coincide with the definitions used in the proofs. Verified statements. For every 0<δ<1/100<δ<1/10 and every instance: 1. the lower bound ℒ(I,δ)≥H(I)[log(1/δ)+Ent(I)]/5L(I,δ)≥ H(I) [ (1/δ)+ (I) ]/5 of Theorem B.1 in its weaker 1/51/5 form, and the upper bound ℒ(I,δ)≤6.4⋅1013H(I)[log(1/δ)+Ent(I)]L(I,δ)≤ 6.4· 10^13\,H(I) [ (1/δ)+ (I) ] of Proposition C.1, hence Theorem 2.1; 2. one algorithm family, receiving only δ and n, that is δ-correct, terminates almost surely, has finite expected sample complexity, and satisfies TA(I)≤12(1012+1)(H(I)[log(1/δ)+Ent(I)]+Dℓ(D))T_A(I)≤ 12(10^12+1)\, (H(I) [ (1/δ)+ (I) ]+D (D) ), hence Theorem 2.2; 3. the consequence TA(I)≤C(ℒ(I,δ)+Dℓ(D))T_A(I)≤ C (L(I,δ)+D (D) ) for a universal C, both with Dℓ(D)D (D) and with Dg(Δ[2])D\,g( _[2]) for the truncation g of Section 2, the two versions being proved equivalent up to the factor 77, together with the two-regime statement of Corollary H.7; 4. the results of Appendix H: equality of the instance-wise lower bound over algorithms with arbitrary standard Borel internal randomness, the implementation of history-dependent probability kernels with identical success probability, cost, and termination, the completion of algorithms with an explicit abandonment action, and the deterministic nature of the two upper-bound algorithms. The literal untruncated expression Δ[2]−2lnlnΔ[2]−1 _[2]^-2 _[2]^-1 is stated separately in the formal development and is not proved; as explained in Section 2, it cannot hold uniformly near Δ[2]=1 _[2]=1. Relation to the printed proofs. The appendices contain complete proofs that do not depend on the formal development. The formal proofs establish the statements above, not the prose of the appendices sentence by sentence, and three deviations are deliberate. First, the formal lower bound does not construct a symmetrized algorithm as in Appendix B; it works directly with permutation-averaged numbers of samples of individual labels and with the bijection π↦(ad)∘π (a\,d) π on labelings in the change of distribution that modifies two arm means. Second, Lemma E.1 is proved in Appendix E by a pathwise coupling to independent Poisson clocks; the formal development instead proves the weaker but sufficient statement that, for every increasing family of subsets of arms, the set of arms whose empirical means satisfy (D.12) in at least one call is stochastically dominated by independent Bernoulli(p)(p) indicators, through a bound on the cumulative predictable hazard and a supermartingale argument. All uses of the lemma in Appendix E involve only increasing events. Third, the formally verified algorithms are variants of the algorithms of Appendices C and D with deterministic sample counts per run: every run of the single algorithm requests exactly its sample budget QjQ_j, padding with requests to a fixed arm after a return or an abort, and the sequence of runs reports an answer at the following block boundary; the algorithm with a fixed target instance pads each run to a deterministic budget computed from the hard-coded H(I)H(I) and Ent(I) (I). These variants only change absolute constants and are covered by the same arguments. The single algorithm is instantiated with CQ=1012C_Q=10^12, and the bound on the sum of exponentials (B.14) is proved with the slightly better constant (79/9)δ(79/9)δ. Checks performed. The development (about 195195 modules and 48004800 declarations for the main results, and 450450 declarations for Appendix H) was compiled from source against a pinned Mathlib revision in a fresh directory. A recursive audit of every declaration found only the axioms propext, Classical.choice, and Quot.sound, and no use of sorry. The complete import closure was replayed in a fresh kernel environment with the reference checker shipped with the Lean toolchain. The independently transcribed statements were compared with the proved statements using the Lean FRO comparator tool, which also checked the permitted axioms and replayed the proofs through the Lean kernel and through the independent external kernel nanoda. None of these checks verifies the informal text, and the development has not been reviewed by a person outside the project. References Aronow et al. (2026) P. M. Aronow, N. Kallus, and P. Lopatto A positive resolution of the gap-entropy conjecture. arXiv preprint arXiv:2609.10529v1. External Links: Link Cited by: §1, §3.1. Audibert et al. (2010) J. Audibert, S. Bubeck, and R. Munos Best Arm Identification in Multi-Armed Bandits. In Proceedings of the Twenty-third Conference on Learning Theory (COLT 2010), p. 41–53. External Links: Link Cited by: §3. Carpentier and Locatelli (2016) A. Carpentier and A. Locatelli Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem. In 29th Annual Conference on Learning Theory, Proceedings of Machine Learning Research, Vol. 49, p. 590–604. External Links: Link Cited by: §3. Chen et al. (2017) L. Chen, J. Li, and M. Qiao Towards Instance Optimal Bounds for Best Arm Identification. In Proceedings of the 2017 Conference on Learning Theory, Proceedings of Machine Learning Research, Vol. 65, p. 535–592. External Links: Link Cited by: §H.7, §1, §3, §3, §3.1, §4, §5.1. Chen and Li (2015) L. Chen and J. Li On the Optimal Sample Complexity for Best Arm Identification. arXiv preprint arXiv:1511.03774. External Links: Link Cited by: §3. Chen and Li (2016) L. Chen and J. Li Open Problem: Best Arm Identification: Almost Instance-Wise Optimality and the Gap Entropy Conjecture. In 29th Annual Conference on Learning Theory, Proceedings of Machine Learning Research, Vol. 49, p. 1643–1646. External Links: Link Cited by: §H.7, §H.7, Appendix H, §1, §1, §2.2, §2.3, §3, §3, Abstract. Chen et al. (2014) S. Chen, T. Lin, I. King, M. R. Lyu, and W. Chen Combinatorial Pure Exploration of Multi-Armed Bandits. In Advances in Neural Information Processing Systems, Vol. 27. External Links: Link Cited by: §3. de Moura and Ullrich (2021) L. de Moura and S. Ullrich The Lean 4 Theorem Prover and Programming Language. In Automated Deduction – CADE 28: 28th International Conference on Automated Deduction, Virtual Event, July 12–15, 2021, Proceedings, p. 625–635. External Links: Document, Link Cited by: Appendix I. Degenne et al. (2019) R. Degenne, W. M. Koolen, and P. Ménard Non-Asymptotic Pure Exploration by Solving Games. In Advances in Neural Information Processing Systems, Vol. 32. External Links: Link Cited by: §3. Degenne and Koolen (2019) R. Degenne and W. Koolen Pure Exploration with Multiple Correct Answers. In Advances in Neural Information Processing Systems, Vol. 32. External Links: Link Cited by: §3. Even-Dar et al. (2002) E. Even-Dar, S. Mannor, and Y. Mansour PAC Bounds for Multi-armed Bandit and Markov Decision Processes. In Computational Learning Theory, p. 255–270. External Links: Document, Link Cited by: §A.2, §3, §4. Even-Dar et al. (2006) E. Even-Dar, S. Mannor, and Y. Mansour Action Elimination and Stopping Conditions for the Multi-Armed Bandit and Reinforcement Learning Problems. Journal of Machine Learning Research 7 (39), p. 1079–1105. External Links: Link Cited by: §A.2, §1, §3. Farrell (1964) R. H. Farrell Asymptotic Behavior of Expected Sample Size in Certain One Sided Tests. The Annals of Mathematical Statistics 35 (1), p. 36–72. External Links: Document, Link Cited by: §1, §3. Gabillon et al. (2012) V. Gabillon, M. Ghavamzadeh, and A. Lazaric Best Arm Identification: A Unified Approach to Fixed Budget and Fixed Confidence. In Advances in Neural Information Processing Systems, Vol. 25. External Links: Link Cited by: §3. Garivier and Kaufmann (2016) A. Garivier and E. Kaufmann Optimal Best Arm Identification with Fixed Confidence. In 29th Annual Conference on Learning Theory, Proceedings of Machine Learning Research, Vol. 49, p. 998–1027. External Links: Link Cited by: §1, §3. Howard et al. (2021) S. R. Howard, A. Ramdas, J. McAuliffe, and J. Sekhon Time-uniform, nonparametric, nonasymptotic confidence sequences. The Annals of Statistics 49 (2), p. 1055–1080. External Links: Document, Link Cited by: §3. Huang et al. (2017) R. Huang, M. M. Ajallooeian, C. Szepesvári, and M. Müller Structured Best Arm Identification with Fixed Confidence. In Proceedings of the 28th International Conference on Algorithmic Learning Theory, Proceedings of Machine Learning Research, Vol. 76, p. 593–616. External Links: Link Cited by: §3. Jamieson et al. (2014) K. Jamieson, M. Malloy, R. Nowak, and S. Bubeck lil’ UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits. In Proceedings of The 27th Conference on Learning Theory, Proceedings of Machine Learning Research, Vol. 35, p. 423–439. External Links: Link Cited by: §H.7, §3. Jedra and Proutiere (2020) Y. Jedra and A. Proutiere Optimal Best-arm Identification in Linear Bandits. In Advances in Neural Information Processing Systems, Vol. 33, p. 10007–10017. External Links: Link Cited by: §3. Jourdan et al. (2022) M. Jourdan, R. Degenne, D. Baudry, R. de Heide, and E. Kaufmann Top Two Algorithms Revisited. In Advances in Neural Information Processing Systems, Vol. 35, p. 26791–26803. External Links: Document, Link Cited by: §3. Jourdan and Degenne (2023) M. Jourdan and R. Degenne Non-Asymptotic Analysis of a UCB-based Top Two Algorithm. In Advances in Neural Information Processing Systems, Vol. 36, p. 68980–69020. External Links: Document, Link Cited by: §3. Karnin et al. (2013) Z. Karnin, T. Koren, and O. Somekh Almost Optimal Exploration in Multi-Armed Bandits. In Proceedings of the 30th International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 28(3), p. 1238–1246. External Links: Link Cited by: §3, §3. Kaufmann et al. (2014) E. Kaufmann, O. Cappé, and A. Garivier On the Complexity of A/B Testing. In Proceedings of The 27th Conference on Learning Theory, Proceedings of Machine Learning Research, Vol. 35, p. 461–481. External Links: Link Cited by: §3. Kaufmann et al. (2016) E. Kaufmann, O. Cappé, and A. Garivier On the Complexity of Best-Arm Identification in Multi-Armed Bandit Models. Journal of Machine Learning Research 17 (1), p. 1–42. External Links: Link Cited by: §A.1, §1, §3. Kaufmann and Kalyanakrishnan (2013) E. Kaufmann and S. Kalyanakrishnan Information Complexity in Bandit Subset Selection. In Proceedings of the 26th Annual Conference on Learning Theory, Proceedings of Machine Learning Research, Vol. 30, p. 228–251. External Links: Link Cited by: §3. Kaufmann and Koolen (2021) E. Kaufmann and W. M. Koolen Mixture Martingales Revisited with Applications to Sequential Tests and Confidence Intervals. Journal of Machine Learning Research 22 (246), p. 1–44. External Links: Link Cited by: §3. Mannor and Tsitsiklis (2004) S. Mannor and J. N. Tsitsiklis The Sample Complexity of Exploration in the Multi-Armed Bandit Problem. Journal of Machine Learning Research 5, p. 623–648. External Links: Link Cited by: §1, §3. Russo (2016) D. Russo Simple Bayesian Algorithms for Best Arm Identification. In 29th Annual Conference on Learning Theory, Proceedings of Machine Learning Research, Vol. 49, p. 1417–1418. External Links: Link Cited by: §3. Shang et al. (2020) X. Shang, R. de Heide, P. Menard, E. Kaufmann, and M. Valko Fixed-confidence guarantees for Bayesian best-arm identification. In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, Proceedings of Machine Learning Research, Vol. 108, p. 1823–1832. External Links: Link Cited by: §3. Simchowitz et al. (2017) M. Simchowitz, K. Jamieson, and B. Recht The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime. In Proceedings of the 2017 Conference on Learning Theory, Proceedings of Machine Learning Research, Vol. 65, p. 1794–1834. External Links: Link Cited by: §1, §3. Soare et al. (2014) M. Soare, A. Lazaric, and R. Munos Best-Arm Identification in Linear Bandits. In Advances in Neural Information Processing Systems, Vol. 27. External Links: Link Cited by: §3. Tao et al. (2018) C. Tao, S. Blanco, and Y. Zhou Best Arm Identification in Linear Bandits with Linear Dimension Dependency. In Proceedings of the 35th International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 80, p. 4877–4886. External Links: Link Cited by: §3. The mathlib community (2020) The mathlib community The Lean mathematical library. In Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs, CPP 2020, New Orleans, LA, USA, January 20-21, 2020, p. 367–381. External Links: Document, Link Cited by: Appendix I. You et al. (2023) W. You, C. Qin, Z. Wang, and S. Yang Information-Directed Selection for Top-Two Algorithms. In Proceedings of Thirty Sixth Conference on Learning Theory, Proceedings of Machine Learning Research, Vol. 195, p. 2850–2851. External Links: Link Cited by: §3.