Paper deep dive
Nearly Optimal Fixed-Confidence Best-Arm Identification with 1-Bit Feedback
Khang Luong, Dinh Thai Son, Hoang Ta, Hung The Tran, Tuan Quang Dam
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 91%
Last extracted: 10/5/2026, 6:53:08 AM
Summary
This paper addresses the fixed-confidence best-arm identification (BAI) problem under strict 1-bit feedback constraints, where learners only receive binary responses to threshold queries. The authors propose a time-uniform 1-bit mean-estimation primitive based on randomized threshold queries and a clipped tail-integral identity. They embed this primitive into two BAI algorithms: a fixed-clipping algorithm and a phased adaptive-clipping algorithm. The phased algorithm achieves gap-adaptive sample complexity. The paper proves an information-theoretic lower bound showing that the logarithmic penalty caused by finite-variance 1-bit feedback is intrinsic, matching the upper bound up to lower-order log-log factors.
Entities (8)
Relation Signals (5)
Fixed-Confidence Best-Arm Identification → hasconstraint → 1-Bit Feedback
confidence 95% · We study fixed-confidence best-arm identification under strict 1-bit feedback constraints.
RestartPhasedClip-1BitBAI → matches → Information-Theoretic Lower Bound
confidence 92% · This bound matches the leading dependence of the phased algorithm up to lower-order loglog factors.
1-Bit Mean-Estimation Primitive → isusedin → FixedClip-1BitBAI
confidence 90% · We then embed this primitive into candidate-challenger best-arm identification algorithms. A fixed-clipping algorithm gives a simple anytime (ϵ,δ)-PAC guarantee
1-Bit Mean-Estimation Primitive → isusedin → RestartPhasedClip-1BitBAI
confidence 90% · We then embed this primitive into candidate-challenger best-arm identification algorithms... a phased adaptive-clipping algorithm matches the clipping level to the current resolution
Lau and Scarlett → established → Optimal Finite-Variance 1-Bit Mean-Estimation Rate
confidence 88% · Lau and Scarlett [20] recently established order-optimal rates for this problem in the finite-variance regime
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:We study fixed-confidence best-arm identification under strict 1-bit feedback constraints. At each round, the learner selects an arm and a query set, and receives only a single bit indicating whether the sampled reward belongs to that set. We consider a distribution-free finite-variance setting with arm-wise localization, where direct empirical mean estimation is no longer available and clipping becomes unavoidable. We first formulate a time-uniform 1-bit mean-estimation primitive based on randomized threshold queries and a clipped tail-integral identity. We then embed this primitive into candidate-challenger best-arm identification algorithms. A fixed-clipping algorithm gives a simple anytime $(\epsilon,\delta)$-PAC guarantee, while a phased adaptive-clipping algorithm matches the clipping level to the current resolution and yields a gap-adaptive sample complexity. We also prove a $K$-arm worst-case information-theoretic lower bound showing that the logarithmic penalty caused by finite-variance 1-bit feedback is intrinsic. This bound matches the leading dependence of the phased algorithm up to lower-order $\log\log$ factors.
Tags
Links
- Source: https://arxiv.org/abs/2610.02771v1
- Canonical: https://arxiv.org/abs/2610.02771v1
Trouble viewing inline? Open PDF directly →
Full Text
179,940 characters extracted from source content.
Expand or collapse full text
Nearly Optimal Fixed-Confidence Best-Arm Identification with 1-Bit Feedback Khang Luong Affiliation: Hanoi University of Science and Technology Affiliation: Quantum AI & Cyber Security Institute, FPT Corporation Dinh Thai Son Affiliation: Hanoi University of Science and Technology Hoang Ta †thanks: Corresponding author: hoang.taduy@hust.edu.vn. Affiliation: Hanoi University of Science and Technology Hung The Tran Affiliation: Quantum AI & Cyber Security Institute, FPT Corporation Tuan Quang Dam Affiliation: Hanoi University of Science and Technology Abstract We study fixed-confidence best-arm identification under strict 1-bit feedback constraints. At each round, the learner selects an arm and a query set, and receives only a single bit indicating whether the sampled reward belongs to that set. We consider a distribution-free finite-variance setting with arm-wise localization, where direct empirical mean estimation is no longer available and clipping becomes unavoidable. We first formulate a time-uniform 1-bit mean-estimation primitive based on randomized threshold queries and a clipped tail-integral identity. We then embed this primitive into candidate-challenger best-arm identification algorithms. A fixed-clipping algorithm gives a simple anytime (ϵ,δ)(ε,δ)-PAC guarantee, while a phased adaptive-clipping algorithm matches the clipping level to the current resolution and yields a gap-adaptive sample complexity. We also prove a K-arm worst-case information-theoretic lower bound showing that the logarithmic penalty caused by finite-variance 1-bit feedback is intrinsic. This bound matches the leading dependence of the phased algorithm up to lower-order loglog factors. 1 Introduction Fixed-confidence best-arm identification (BAI) is the problem of identifying an optimal, or near-optimal, arm with high probability while using as few samples as possible [6, 14, 8]. Classical formulations assume that each pull reveals the reward value itself, so that empirical means and confidence intervals can be formed directly. In this paper, we study BAI under strict 1-bit feedback constraints: at each round, the learner selects an arm and a query set, and receives only a single bit indicating whether the sampled reward belongs to that set. Two concrete applications instantiate the threshold-query subclass of this model. Uplink-constrained sensing. A controller selects one of K sensing locations or configurations. A fresh scalar measurement Xk,t∼νkX_k,t _k is compared locally with a programmed threshold qtq_t, and the device sends only Yt=Xk,t≥qtY_t=1\X_k,t≥ q_t\. The controller seeks a location whose mean pollutant concentration or diagnostic score is within ε of the largest, with confidence 1−δ1-δ, before prioritizing an inspection or deploying an expensive high-resolution monitor. Quantized scalar sensing motivates this response mechanism [23]; adaptive arm selection and fixed-confidence identification are our specialization. Posted pricing. A seller selects a buyer population k, posts a price qtq_t to a fresh buyer with hidden valuation Xk,t∼νkX_k,t _k, and observes only the purchase bit Yt=Xk,t≥qtY_t=1\X_k,t≥ q_t\. This is the accept/reject mechanism of posted-price auctions [17]. Screening K populations for an ε -optimal mean valuation gives a threshold-query BAI problem. The objective here is mean valuation; revenue maximization is a different objective. In both applications, the learner chooses the threshold before the fresh sample is drawn. We constrain the response to one bit and assume the threshold can be supplied through a downlink or a programmable comparator. Thus these mechanisms support the queries used by our algorithms. We focus on distribution-free fixed-confidence BAI under a finite-variance assumption. The main challenge is that under 1-bit feedback, best-arm identification can no longer rely on direct empirical estimates of arm means. Even estimating the mean of a single arm becomes nontrivial: one must reconstruct a real-valued quantity from binary threshold queries while controlling both stochastic variance and approximation bias. Under only a second-moment assumption, this naturally leads to a clipping or truncation step [21, 20], and hence to a nontrivial bias–variance tradeoff. In the bandit setting, this difficulty is compounded by adaptivity: the learner must compare arms and decide when to stop using confidence intervals that remain valid uniformly over time, even though the number of pulls allocated to each arm is itself data-dependent. A fixed-target 1-bit mean estimator is not directly sufficient for a per-pull rule whose local sample counts are random and data-dependent. One needs either a time-uniform confidence sequence, as in Theorem 5, or an outer wrapper that invokes fixed-target estimators at prespecified checkpoints with simultaneous confidence control, as in phased successive elimination. Our approach is organized around this clipping difficulty. The clipping level controls a bias-variance tradeoff: a larger level reduces clipping bias but enlarges both the variance proxy and the almost-sure range of the 1-bit estimator. The ideal choice therefore depends on the scale at which arms must be distinguished, a scale governed by the unknown gaps. We address this through a 1-bit estimator with time-uniform validity, embedded into two complementary BAI strategies: a fixed clipping level tuned to the target accuracy, and a phased adaptive scheme that matches the clipping level to the current statistical scale. Finally, we prove a K-arm equal-gap lower bound showing that the logarithmic penalty is intrinsic to finite-variance 1-bit feedback. It matches the leading K, gap, and confidence dependence of the phased upper bound on these worst-case instances, up to lower-order loglog factors. 1.1 Problem setting We study fixed-confidence best-arm identification under 1-bit feedback. The learner is given a finite collection of arms =1,2,…,KA=\1,2,…,K\. Pulling arm k∈k produces an i.i.d. reward drawn from an unknown distribution νk _k on ℝR with mean μk:=X∼νk[X] _k:=E_X _k[X]. Throughout the paper, we assume that there is a known variance proxy σ>0σ>0 such that VarX∼νk(X)≤σ2for all k∈.Var_X _k(X)≤σ^2 all k . In addition, for each arm k we assume that we are given an anchor point ckc_k satisfying |μk−ck|≤σ.| _k-c_k|≤σ. We assume that the best arm is unique, and denote it by k⋆=argmaxk∈μk = _k _k, and μ⋆:=μk⋆μ := _k . Remark 1 (Role of assumptions). The variance bound is the basic moment assumption under which our 1-bit estimator operates. The anchor condition plays a different role: it gives a localization of each arm mean, which is exactly what allows the 1-bit estimator to work efficiently. This localization can itself be obtained by the preliminary 1-bit routine MedianEst, using at most O(KlogKλδσ)O (K Kλδσ ) threshold queries if μ∈[−λ,λ]μ∈[-λ,λ] with known λ; see Appendix A. Furthermore, while we use |μk−ck|≤σ| _k-c_k|≤σ for convenience, an anchor distance of |μk−ck|≤O(σ)| _k-c_k|≤ O(σ) is adequate and only alters the constant factors in the bounds, as detailed in the Appendix A. For every suboptimal arm k≠k⋆k≠ k , define the gap Δk:=μ⋆−μk>0 _k:=μ - _k>0, and for the optimal arm define Δk⋆:=minj≠k⋆Δj _k := _j≠ k _j. These gaps quantify the intrinsic difficulty of the instance: small gaps mean that the learner must distinguish arms with very close means, and hence must collect more information before stopping. 1-bit interaction model. The learner does not observe rewards directly. Instead, at round t, it chooses an arm kt∈k_t together with a measurable query set At⊆ℝA_t . The agent then observes a fresh reward sample Xkt,t∼νktX_k_t,t _k_t and returns only the single bit Yt=Xkt,t∈At∈0,1.Y_t=1\X_k_t,t∈ A_t\∈\0,1\. Both the arm choice and the query set may depend on the entire past history, so the interaction is fully adaptive. This is the same 1-bit set-query model used in the lower-bound construction. In the algorithmic part of the paper, we only use randomized threshold queries, which form a particularly simple subclass of measurable set queries. Objective. Fix an accuracy parameter ε>0 >0. We define the set of ε -optimal arms by Aε(ν):=k∈:μk≥μ⋆−ε.A_ (ν):=\k : _k≥μ - \. A 1-bit best-arm identification algorithm consists of an adaptive query strategy, a stopping time τ, and a recommendation k^∈ k . It is said to be (ε,δ)( ,δ)-PAC if Prν(τ<∞)=1 _ν(τ<∞)=1 and Prν(k^∉Aε(ν))≤δ _ν ( k∉ A_ (ν) )≤δ for every bandit instance ν=(ν1,…,νK)ν=( _1,…, _K) satisfying the above assumptions. Equivalently, with probability at least 1−δ1-δ, the output arm satisfies μk^≥μ⋆−ε _ k≥μ - . This ε -relaxed objective is natural in our setting. It allows the learner to stop once it has ruled out all arms that are worse than the optimum by more than ε , without spending additional samples to separate nearly tied arms. In particular, when ε<Δk⋆, < _k , the set Aε(ν)A_ (ν) reduces to k⋆\k \, and the (ε,δ)( ,δ)-PAC requirement becomes exact best-arm identification. 1.2 Contributions A time-uniform 1-bit mean-estimation primitive for adaptive BAI. In Section 2, we formulate a randomized-threshold mean-estimation primitive based on a clipped tail-integral identity (Lemma 2). The resulting estimator admits confidence sequences that are valid uniformly over time (Theorem 5), which is essential for BAI because the number of samples collected from each arm is random and data-dependent. As a standalone mean estimator, its sample complexity matches the optimal finite-variance 1-bit mean-estimation rate of Lau and Scarlett [20], up to the standard iterated-logarithmic price of time-uniform validity (Corollary 6). The contribution here is structural rather than rate-level: rather than improving the standalone mean-estimation rate, we provide a BAI-ready confidence sequence that remains valid under adaptive arm selection and stopping. Fixed-confidence BAI algorithms under 1-bit feedback. In Section 3, we show how to turn the above primitive into fixed-confidence BAI algorithms. The first algorithm, FixedClip-1BitBAI, uses a single clipping level tuned to the target accuracy ε . It is simple and fully anytime, but its sample complexity contains an additional mixed term caused by the range of the clipped 1-bit statistic (Theorem 8). The second algorithm, RestartPhasedClip-1BitBAI, uses phased adaptive clipping: it proceeds from coarse to fine resolutions and chooses the clipping level according to the current resolution. This removes the fixed-clipping mixed term and yields the main gap-adaptive upper bound of the paper (Theorem 10). Both algorithms are (ε,δ)( ,δ)-PAC, and their sample complexities are compared in Subsection 3.3. A matching information-theoretic lower bound for 1-bit BAI. In Section 4, we prove a worst-case lower bound for fixed-confidence BAI under 1-bit set queries. The construction is closely related in spirit to multiscale hard instances for finite-variance 1-bit mean estimation of Lau and Scarlett [20], but is formulated directly as a K-arm BAI lower bound and combined with a change-of-measure argument for adaptive stopping. For a K-arm instance with all suboptimal gaps equal to Δ , we show that any algorithm that is δ-correct over the instance class must have an expected stopping time of at least Ω((K−1)σ2Δ2logσΔlog1δ) ((K-1) σ^2 ^2 σ 1δ ) (Theorem 12). This demonstrates that the Θ(logσΔ) ( σ ) penalty is an unavoidable consequence of the 1-bit feedback constraint, proving that our algorithm is asymptotically optimal up to a loglog factor. Empirical validation. Section 5 evaluates our 1-bit mean estimator and best-arm identification algorithms. For standalone estimation, our randomized estimator achieves lower mean absolute error and a smaller bias floor than the finite-variance baseline of Lau and Scarlett [20]. In the tested bandit settings, phased adaptive clipping uses fewer queries than fixed clipping on instances with heterogeneous gaps. In the remainder of this paper, the main text presents and discusses our primary theoretical and numerical results, while all formal proofs, detailed algorithms, and experimental configurations are deferred to the appendix. 1.3 Related work Fixed-confidence best-arm identification. The fixed-confidence PAC framework for bandits and foundational sample-complexity lower bounds for pure exploration were developed in [6, 22]. A large subsequent literature developed gap-adaptive algorithms and instance-dependent complexity measures, including successive elimination methods [14], LUCB-style subset-selection algorithms [13], UGapE-type candidate-challenger algorithms [7], and time-uniform confidence methods such as lil’UCB [12]. Information-theoretic lower bounds and asymptotically optimal sampling rules were developed in [15, 8]. The closest algorithmic template to ours is the UGapE framework of Gabillon et al. [7], which compares a candidate arm against its strongest challenger using confidence intervals. All of these works assume direct access to the realized reward at each round, so empirical means and confidence intervals can be formed directly; our setting drops this assumption. Quantized feedback and communication-limited learning. Communication limits have motivated a broad line of work on statistical inference and learning from quantized or few-bit messages [4, 2, 3, 24]. A particularly relevant subproblem is mean estimation from compressed, distributed, or one-bit observations [16, 5, 18, 1]. In bandit problems, limited communication has been studied in regret minimization and distributed exploration settings [25, 10, 11]. Our setting differs in that the objective is fixed-confidence best-arm identification, the feedback consists of adaptive one-bit set queries, and the rewards are only assumed to have finite variance. This weak moment assumption is what forces clipping and leads to the logarithmic penalty analyzed in this paper. 1-bit mean estimation and threshold queries. The fundamental statistical task underlying our approach is estimating the mean of a real-valued distribution from binary threshold comparisons. Lau and Scarlett [20] recently established order-optimal rates for this problem in the finite-variance regime, achieving the sample complexity O((σ2/β2)log(σ/β)log(1/γ))O((σ^2/β^2) (σ/β) (1/γ)); crucially, they show that the log(σ/β) (σ/β) factor is unavoidable with only a second-moment assumption, since the distribution need not have known bounded support. Our 1-bit estimator matches this rate up to the loglog overhead of time-uniform validity, and our lower bound shows that the same log(σ/Δ) (σ/ ) penalty transfers directly to the BAI problem. In contrast to standalone mean estimation, fixed-confidence BAI requires confidence guarantees that remain valid under adaptive arm selection, elimination, and stopping. Thus, the role of our randomized-threshold primitive is not to improve the standalone mean-estimation rate, but to provide an anytime confidence sequence that can be embedded directly into candidate-challenger BAI algorithms. The 1-bit framework also connects to the quantile bandit setting [19], which uses 1-bit feedback to identify the arm with the best quantile rather than the best mean. 2 A 1-bit mean estimator We develop the 1-bit mean-estimation primitive through a three-stage construction. First, we establish a tail-integral identity that expresses the mean of a clipped variable as an integral of threshold probabilities. Second, we introduce a randomized thresholding scheme that allows us to estimate this integral using only a single bit per sample while maintaining a controlled bias-variance tradeoff. Finally, we derive a time-uniform confidence sequence for the mean, which enables the estimator to be used in adaptive, data-dependent stopping rules. We also discuss the sample complexity of the estimator in Corollary 6, and compare with the baseline of [20] in Remark 7. Fix one arm and suppress the arm index. Let X have mean μ, variance at most σ2σ^2, and let c be an anchor point satisfying |μ−c|≤σ|μ-c|≤σ. Define the centered variable W:=X−c.W:=X-c. Then [W]=μ−c,[W2]≤Var(W)+([W])2≤2σ2.E[W]=μ-c, [W^2] (W)+(E[W])^2≤ 2σ^2. Thus W has controlled second moment and is centered near zero. Our task is now to estimate [W]E[W], and hence μ, using only 1-bit threshold information. 2.1 A tail-integral identity The starting point is an identity that rewrites a clipped value in terms of tail events. For L>0L>0, define [w]L:=−L,w<−L,w,−L≤w≤L,L,w>L.[w]_L:= cases-L,&w<-L,\\ w,&-L≤ w≤ L,\\ L,&w>L. cases The point of clipping is that it separates the estimation problem into two parts: a bounded quantity, which can be estimated reliably, and a bias term, which we will control using the variance bound. Lemma 2 (Tail-integral identity). For every w∈ℝw and every L>0L>0, [w]L=∫0L(w≥t−w≤−t)dt.[w]_L= _0^L (1\w≥ t\-1\w≤-t\ )\,dt. Consequently, [[W]L]=∫0L(Pr(W≥t)−Pr(W≤−t))t.E[[W]_L]= _0^L ( (W≥ t)- (W≤-t) )\,dt. This identity is the bridge between mean estimation and 1-bit queries. It says that the clipped-variable mean can be written as an integral of differences between upper-tail and lower-tail probabilities. Since each of those probabilities can be accessed through a threshold comparison, the identity suggests that we should estimate the integral by randomizing the threshold t and asking only a single yes/no question per sample. The proof is given in Appendix B.1. 2.2 A 1-bit randomized estimator To turn the tail-integral identity into an estimator, we need a distribution over t. For L≥σL≥σ, define αL:=1+logLσ,gL(t):=1αLmaxσ,t,t∈[0,L]. _L:=1+ Lσ, g_L(t):= 1 _L \σ,t\, t∈[0,L]. Then gLg_L is a density on [0,L][0,L], since ∫0LgL(t)t=αL−1(∫0σt/σ+∫σLt/t)=1. _0^Lg_L(t)\,dt= _L^-1 ( _0^σdt/σ+ _σ^Ldt/t )=1. The shape of gLg_L is important. It places relatively more mass on small thresholds t, where the query is informative, while still assigning enough mass to larger thresholds to represent the integral up to L. Randomized query and estimator. Draw S∈+1,−1S∈\+1,-1\ uniformly, independently of everything else, and draw T∼gLT g_L. Given a fresh reward sample X, issue the 1-bit query Y=S(X−c)≥T.Y=1\S(X-c)≥ T\. Equivalently, when S=+1S=+1 we ask whether X≥c+TX≥ c+T, and when S=−1S=-1 we ask whether X≤c−TX≤ c-T. We then define Z:=2SgL(T)Y.Z:= 2Sg_L(T)\,Y. The next lemma summarizes why this construction works. Lemma 3 (Unbiasedness, variance, and range). For every L≥σL≥σ: (i) [Z]=[[W]L]E[Z]=E[[W]_L], (i) Var(Z)≤3αLσ2Var(Z)≤ 3 _Lσ^2, (i) |Z|≤2αLL|Z|≤ 2 _LL almost surely. Each part of the lemma has a different role. The first part shows that Z is exactly unbiased for the clipped-variable mean. The second part gives a variance bound of the correct scale, up to the logarithmic factor αL _L. The third part provides an almost-sure range bound. Together, the second and third parts are precisely what is needed to apply Bernstein’s inequality; the proof is given in Appendix B.2. Of course, Z is unbiased only for the clipped-variable mean [[W]L]E[[W]_L], not for [W]E[W] itself. The next lemma quantifies the price paid for clipping. Lemma 4 (Clipping bias). For every L≥σL≥σ, |[W]−[[W]L]|≤σ22L. |E[W]-E[[W]_L] |≤ σ^22L. This bound has the expected form: increasing the clipping level L reduces the bias, but making L too large will worsen the variance bound 3αLσ23 _Lσ^2 as well as the range bound 2αLL2 _LL. The estimator therefore has a standard bias-variance tradeoff, and the choice of L needs to balance the two effects. The bias proof is given in Appendix B.3. 2.3 Confidence sequence for the tail-integral estimator Let Z1,Z2,…Z_1,Z_2,… be i.i.d. copies of the above estimator, each built from an independent reward sample and independent internal randomization. Define Z¯n:=1n∑i=1nZi,μ^n:=c+Z¯n. Z_n:= 1n _i=1^nZ_i, μ_n:=c+ Z_n. Since Z¯n Z_n estimates the clipped-variable mean and c restores the shift, μ^n μ_n is our 1-bit estimate of μ. Theorem 5 (Confidence sequence for the tail-integral estimator). For every L≥σL≥σ and γ∈(0,1)γ∈(0,1), with probability at least 1−γ1-γ, |μ^n−μ|≤β(n,γ,L)| μ_n-μ|≤β(n,γ,L) for all n≥1n≥ 1, where β(n,γ,L)=σ22L+23αLσ2xn(γ)n+αLLxn(γ)n,β(n,γ,L)= σ^22L+2 3 _Lσ^2x_n(γ)n+ _LL\,x_n(γ)n, with αL=1+log(L/σ) _L=1+ (L/σ) and xn(γ):=log(π2(1+⌊log2n⌋)2/(3γ))x_n(γ):= \! (π^2(1+ _2n )^2/(3γ) ). The first term in β(n,γ,L)β(n,γ,L) is the clipping bias, the second is the main stochastic fluctuation term, and the third is the Bernstein range correction. The only price paid for time-uniformity is the stitched penalty xn(γ)x_n(γ), which is of order log(1/γ)+loglog(e+n) (1/γ)+ (e+n). The proof of Theorem 5 is in Appendix B.4, and the sample-complexity inversion below is proved in Appendix B.5. Corollary 6 (Sample complexity of the tail-integral estimator). Fix a target accuracy β∈(0,σ)β∈(0,σ) and an error probability γ∈(0,1/3)γ∈(0,1/3). By setting the clipping level L=2σ2βL= 2σ^2β, the tail-integral estimator μ^n μ_n satisfies |μ^n−μ|≤β| μ_n-μ|≤β with probability at least 1−γ1-γ for sample sizes n satisfying: n=O(σ2β2logσβ[log1γ+loglog(e+σβ)]).n=O ( σ^2β^2 σβ [ 1γ+ (e+ σβ ) ] ). Remark 7 (Comparison with [20]). In the finite-variance regime, [20] achieve the optimal rate O(σ2β2logσβlog1γ).O\! ( σ^2β^2 σβ 1γ ). Our estimator matches this rate up to the lower-order loglog factor needed for time-uniform validity. Structurally, their estimator partitions the domain into geometric regions and assigns fixed regional budgets, whereas ours samples a single randomized threshold from gLg_L and yields an anytime confidence sequence. This avoids fixed regional allocations and makes the estimator compatible with adaptive bandit sampling and stopping rules. 3 1-bit BAI algorithm and upper bound We now convert the time-uniform 1-bit mean confidence sequence from Section 2 into fixed-confidence BAI algorithms. Our algorithms follow the candidate-challenger interval logic of [7]. At each time, we construct arm-wise confidence intervals, select a candidate arm h, identify its strongest challenger ℓ , and stop once the candidate is certified to be ε -optimal. If the stopping condition is not met, the algorithm samples the more uncertain arm among h,ℓ\h, \, namely the one with the larger confidence radius. The main new difficulty, compared with the unquantized setting, is the choice of the clipping level L. A larger clipping level reduces the bias of the 1-bit mean estimator but increases both its variance factor and its range term. Thus, the clipping level must be matched to the statistical resolution at which arms are being compared. We present two approaches. The first is a fixed-clipping algorithm, which chooses a single clipping level tuned to the target accuracy ε . This algorithm is simple and fully anytime, but it pays an additional mixed term in the sample complexity; see Theorem 8. The second is a phased adaptive-clipping algorithm, which gradually decreases the statistical resolution and chooses the clipping level accordingly. This removes the mixed term and yields the main gap-adaptive upper bound of the paper; see Theorem 10. Both algorithms are (ε,δ)( ,δ)-PAC, and their sample complexities are compared in Subsection 3.3. Consider the non-trivial case 0<ε≤σ0< ≤σ; the case ε>σ >σ is trivial up to constants and can be handled by the initial phase alone. Define Δ~k:=maxΔk,ε, _k:= \ _k, \, and Δ¯k:=minΔ~k,σ. _k:= \ _k,σ\. 3.1 Fixed clipping bias The simplest implementation chooses the clipping level from the target accuracy: Lε:=2σ2ε,αε:=1+logLεσ=1+log2σε.L_ := 2σ^2 , _ :=1+ L_ σ=1+ 2σ . By Lemma 4, the clipping bias is at most ε/4 /4. The confidence radius from Theorem 5 becomes βε(n,γ)=ε4+23αεσ2xn(γ)n+2αεσ2xn(γ)nε. _ (n,γ)= 4+2 3 _ σ^2x_n(γ)n+ 2 _ σ^2x_n(γ)n . Algorithm FixedClip-1BitBAI uses this radius with γ=δ/Kγ=δ/K. At each round it forms confidence intervals [LCBk,UCBk][LCB_k,UCB_k] of μk _k, sets Bk=maxa≠kUCBa−LCBkB_k= _a≠ kUCB_a-LCB_k, lets h∈argminkBkh∈ _kB_k and ℓ∈argmaxa≠hUCBa ∈ _a≠ hUCB_a, stops if Bh≤εB_h≤ , and otherwise samples the more uncertain arm in h,ℓ\h, \ using the 1-bit tail-integral query at clipping level LεL_ . Detailed pseudocode is given in Algorithm 3 in Appendix E. From the expression of βε(n,γ) _ (n,γ), the sample requirement is no longer governed only by the usual n−1/2n^-1/2 concentration term. In addition, there is a lower-order n−1ε−1n^-1 ^-1 term coming from the Bernstein range correction. This term is a direct consequence of the clipping level LεL_ chosen so that the clipping bias is at most ε/4 /4, affecting the final sample complexity. This leads to the hardness quantity: Hfix(ε):=αε∑k=1K(σ2Δ~k2+σ2εΔ~k).H_fix( ):= _ _k=1^K ( σ^2 _k^2+ σ^2 _k ). With this hardness quantity, we can state the sample complexity upper bound. Theorem 8 (Fixed clipping upper bound). FixedClip-1BitBAI is (ε,δ)( ,δ)-PAC. With probability at least 1−δ1-δ, its needed number of 1-bit queries satisfies Nfix=O(Hfix(ε)[logKδ+loglogHfix(ε)]).N_fix=O\! (H_fix( ) [ Kδ+ H_fix( ) ] ). The proof of Theorem 8 is given in Appendix C.1. A finite deterministic query bound also holds on every realization for ε>0 >0, guaranteeing termination even outside the confidence event; together with interval correctness this establishes the PAC guarantee. The deterministic bound and proof are given in Appendix C.3.1. Remark 9 (The choice of clipping level L). The fixed choice Lε=2σ2/εL_ =2σ^2/ is simple and ensures bias at most ε/4 /4, but it is not instance-optimal, especially when ε≪Δk _k or ε=0 =0. For exact best-arm identification ε=0 =0, the natural scale is L⋆=Θ(σ2/Δk⋆)L_ = (σ^2/ _k ); more generally, the oracle arm-wise choice would be Lk=Θ(σ2/Δ~k)L_k= (σ^2/ _k), leading to the gap-adaptive hardness Hgap=∑k=1K(1+logσΔ¯k)σ2Δ¯k2.H_gap= _k=1^K (1+ σ _k ) σ^2 _k^2. The phased algorithm below obtains this behavior without knowing the gaps. 3.2 Phased adaptive clipping The intuition behind the phased algorithm is that easy arms should not be estimated at the finest accuracy scale. In FixedClip-1BitBAI, the clipping level is fixed using the target accuracy ε , so even an arm with a large gap pays the range cost associated with resolving ε -level differences. The phased algorithm instead proceeds from coarse to fine resolutions. At phase j, it uses a clipping level matched to the current resolution ρj _j and eliminates arms that are already distinguishable at that scale. Only statistically competitive arms survive to finer phases. This removes the fixed-clipping mixed term and yields a bound depending on each arm’s own effective gap. To implement this idea, schedule resolutions ρj:=2−jσ,J:=⌈log2(σ/ε)⌉,j=0,1,…,J, _j:=2^-jσ, J:= _2(σ/ ) , j=0,1,…,J, and at phase j set Lj:=32σ2/ρjL_j:=32σ^2/ _j, αj:=1+log(32σ/ρj) _j:=1+ (32σ/ _j), and rj:=ρj/16r_j:= _j/16. With γ=δ/[K(J+1)]γ=δ/[K(J+1)], βj(n)=ρj64+23αjσ2xn(γ)n+32αjσ2xn(γ)ρjn. _j(n)= _j64+2 3 _jσ^2x_n(γ)n+ 32 _jσ^2x_n(γ) _jn. The choice of LjL_j makes the clipping bias of phase j at most ρj/64 _j/64, while rj=ρj/16r_j= _j/16 is the target statistical radius at that resolution. Thus, phase j should be viewed as a test of whether the currently active arms can already be separated at scale ρj _j. If the confidence intervals are still too wide, the algorithm continues sampling; if all active arms have confidence radius at most rjr_j, then arms that are clearly suboptimal at this scale can be safely removed. Algorithm RestartPhasedClip-1BitBAI implements this idea using fresh estimators at every phase; detailed pseudocode is given in Algorithm 4 in Appendix E. Within phase j, it adaptively samples active arms until either some arm is certified to be ε -optimal or all active arms have confidence radius at most rjr_j. In the latter case, it eliminates every arm whose UCB is below the best LCB by more than ε , and then moves to the next, finer phase j+1j+1. Theorem 10 (Phased adaptive clipping upper bound). RestartPhasedClip-1BitBAI is (ε,δ)( ,δ)-PAC. With probability at least 1−δ1-δ, the needed number of 1-bit queries satisfies τ=O(Hgap[logKδ+loglogσε]),τ=O\! (H_ gap [ Kδ+ σ ] ), The proof of Theorem 10 is given in Appendix C.2. A finite deterministic query bound also holds on every realization for ε>0 >0, guaranteeing termination even outside the confidence event; together with interval correctness this establishes the PAC guarantee. The deterministic bound and proof are given in Appendix C.3.2. Remark 11 (Reuse instead of restart). The restart version is chosen for proof clarity. In practice one can reuse samples across clipping levels using [W]Lj=∑s=0j∫Is(W≥t−W≤−t)dt,I0=[0,L0],Is=(Ls−1,Ls](s≥1).[W]_L_j= _s=0^j _I_s (1\W≥ t\-1\W≤-t\ )dt, I_0=[0,L_0], I_s=(L_s-1,L_s]\ (s≥ 1). Thus, when moving from phase j−1j-1 to phase j, it suffices to introduce the new slab IjI_j and top up only those old slabs whose sample counts are still deficient for the finer phase-j target radius. Lemma 31 shows that this reuse strategy preserves the same order as Theorem 10. 3.3 Discussion of the sample complexity Fixed clipping vs Phased clipping. The fixed method is simpler and fully anytime, but it pays the mixed term σ2/(εΔ~k)σ^2/( _k) because the range of the 1-bit statistic is proportional to Lε=Θ(σ2/ε)L_ = (σ^2/ ). This term is unavoidable for a globally fixed clipping level, but it is wasteful for arms with Δk≫ε _k . The phased method matches LjL_j to the current resolution ρj _j, so the range term is balanced at the scale where the arm is actually distinguished; its cost is essentially (1+log(σ/Δ¯k))σ2/Δ¯k2(1+ (σ/ _k))σ^2/ _k^2 per arm. Compared with unquantized fixed-confidence BAI. The distribution-free hardness of unquantized BAI is ∑kσ2/Δ~k2 _kσ^2/ _k^2 ([7]), 1-bit feedback introduces the additional logarithmic factor 1+log(σ/Δ¯k)1+ (σ/ _k) in the phased bound. The lower bound in Section 4 shows that this logarithmic penalty is inevitable in the finite-variance regime. Lau–Scarlett [20] with phased successive elimination. At each resolution ρj _j, run their fixed-target estimator on each active arm with accuracy ρj/8 _j/8 and confidence 1−δ/[K(J+1)]1-δ/[K(J+1)], then retain estimates within ρj/2 _j/2 of the maximum. Simultaneous confidence control yields total cost O(Hgaplog(K(J+1)/δ))O(H_ gap (K(J+1)/δ)), matching our leading rate. Appendix C.4 gives the correctness and counting argument. Total sample complexity. If the anchors are not initially available but the means lie in [−λ,λ][-λ,λ], running MedianEst for each arm adds an additional O(K(logλσ+logKδ))O\! (K( λσ+ Kδ) ) term to the sample complexity, which does not scale with ε or the gaps Δk _k. 4 Lower bound We now establish an information-theoretic lower bound for fixed-confidence best-arm identification under 1-bit set queries. The construction is closely related in spirit to the multiscale hard instances that arise in finite-variance 1-bit mean estimation [20]: in both settings, one-bit queries cannot avoid a logarithmic loss under only a second-moment assumption. Here, we formulate this obstruction directly in the BAI setting by embedding opposite perturbations of a multiscale one-dimensional distribution into a K-arm instance and combining it with a change-of-measure argument for adaptive stopping. The construction uses a symmetric distribution P0P_0 of mean zero and perturbed distributions P−P_- and P+P_+ of means −Δ- and +Δ+ . The base instance (P0,P−,…,P−)(P_0,P_-,…,P_-) has K−1K-1 equal suboptimal gaps Δ . For each i≥2i≥ 2, changing only arm i to P+P_+ changes the best arm to i. A change of measure forces sufficient queries to each such arm under the same base instance, and summing gives the factor K−1K-1. Theorem 12 (K-arm worst-case lower bound for 1-bit BAI). Fix K≥2K≥ 2, σ>0σ>0, δ∈(0,1/4)δ∈(0,1/4), and Δ∈(0,σ/4] ∈(0,σ/4]. There exists a K-arm instance ν(0)ν^(0) with variance at most σ2σ^2 for every arm and all suboptimal gaps equal to Δ , such that every 1-bit algorithm that is δ-correct for exact BAI over the stated instance class satisfies ν(0)[τ]≥c(K−1)σ2Δ2logσΔlog1δE_ν^(0)[τ]≥ c(K-1) σ^2 ^2 σ 1δ for an absolute constant c>0c>0. The same bound holds for algorithms that are (ε,δ)( ,δ)-PAC over this class when 0<ε<Δ/20< < /2. All base and alternative distributions admit the same anchor ck=0c_k=0, so the bound persists when valid anchors are supplied. The construction, uniform one-query KL bound, and adaptive change-of-measure proof appear in Appendices D.1–D.3. On the equal-gap base instance, Hgap=K(1+log(σ/Δ))σ2/Δ2H_ gap=K(1+ (σ/ ))σ^2/ ^2. When δ≤1/Kδ≤ 1/K, log(1/δ) (1/δ) and log(K/δ) (K/δ) are equivalent up to constants. Hence the expected lower bound matches the leading K, gap, and confidence dependence of the high-probability phased upper bound, up to lower-order iterated logarithms. This worst-case comparison does not characterize the optimal expected complexity on every instance. 5 Numerical experiments 5.1 1-bit mean estimation We compare our tail-integral estimator proposed in Section 2 against the baseline of [20] in the finite-variance regime. The experiment has two goals: first, to compare the empirical mean absolute error (MAE) of the two estimators; second, to verify the qualitative behavior predicted by Theorem 5, namely that the error is governed by a decaying stochastic term together with a deterministic bias term induced by clipping/truncation. Figure 1: Mean absolute error |μ^n−μ|E| μ_n-μ| over the number of 1-bit queries n for our estimator and the estimator of [20] (mean ±σ±σ over runs). For readability, bias lines below 10−310^-3 are not shown. Detailed calibration and setup are given in Appendix F.1; Appendix F.2 compares variances of the signed estimates. Figure 1 illustrates the MAE relative to the number of 1-bit queries. While both estimators show the expected O(n−1/2)O(n^-1/2) decay in the Gaussian case, our estimator consistently achieves a lower MAE. For Student-t and exponential distributions, our method reaches a lower asymptotic error floor due to its smaller true deterministic bias at the same clipping/truncation level. Under this calibration, the bias term is practically significant and our estimator has lower MAE and clipping bias. The signed-estimate standard deviations are also smaller (Table 2); these empirical differences do not imply a rate separation. 5.2 1-bit best-arm identification We evaluate the empirical performance of our proposed 1-bit best-arm identification algorithms across three distinct experimental setups. To analyze the sample complexity and safety of each approach, the confidence parameter δ is varied from 0.010.01 to 0.50.5. We compare three variations of our 1-bit algorithm—FixedClip, RestartPhase, ReusePhase—against the full real-valued-feedback UGapE baseline of Gabillon et al. [7]. Appendix F.3 gives the full setup, query cap, and exploration tuning. The tuned implementations are assessed empirically. Figure 2: Stopping rounds of best-arm identification algorithms as a function of the confidence parameter δ (mean ±σ±σ over runs). Figure 2 illustrates the stopping round as a function of δ across the three experimental settings. The performance gap between the 1-bit algorithms and the unquantized baseline is most significant in the Bernoulli environment and relatively smaller in the Normal and Student-t settings. When gaps are uniform, as in the Bernoulli test where Δk _k is identical for all suboptimal arms, the three 1-bit algorithms perform similarly because no arms can be eliminated early at coarser resolutions. However, in the Normal and Student-t settings where Δk _k varies, the phased adaptive-clipping algorithms demonstrate a clear advantage by eliminating arms with larger gaps much earlier than the fixed-clipping approach. 6 Conclusion We introduced a fixed-confidence best-arm identification framework for finite-variance, 1-bit feedback environments. Using a novel randomized-threshold mean estimator, we developed a baseline fixed-clipping algorithm alongside a gap-adaptive phased alternative which achieves worst-case optimality up to loglog factors. Addressing current limitations offers clear avenues for future work. First, our algorithms rely on an localization assumption; developing methods that weaken or remove this requirement is an important next step. Second, our analysis currently relies on a K-arm worst-case lower bound, leaving the exact instance-dependent complexity of 1-bit BAI open. Finally, extending our time-uniform 1-bit primitive to broader pure-exploration tasks presents an exciting direction for communication-constrained learning. Acknowledgments We thank Prof. Jonathan Scarlett for his helpful comments and suggestions. References [1] P. Abdalla and J. Chen (2026) Robust mean estimation under quantization. External Links: 2601.07074, Link Cited by: §1.3. [2] J. Acharya, C. L. Canonne, and H. Tyagi (2019) Inference under information constraints: lower bounds from chi-square contraction. In Proceedings of the Thirty-Second Conference on Learning Theory, A. Beygelzimer and D. Hsu (Eds.), Proceedings of Machine Learning Research, Vol. 99, p. 3–17. External Links: Link Cited by: §1.3. [3] J. Acharya, C. L. Canonne, and H. Tyagi (2020) Inference under information constraints i: communication constraints and shared randomness. IEEE Transactions on Information Theory 66 (12), p. 7856–7877. Cited by: §1.3. [4] M. Braverman, A. Garg, T. Ma, H. L. Nguyen, and D. P. Woodruff (2016) Communication lower bounds for statistical estimation problems via a distributed data processing inequality. In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, STOC ’16, New York, NY, USA, p. 1011–1020. External Links: ISBN 9781450341325, Link, Document Cited by: §1.3. [5] T. T. Cai and H. Wei (2024) Distributed gaussian mean estimation under communication constraints: optimal rates and communication-efficient algorithms. J. Mach. Learn. Res. 25 (1). External Links: ISSN 1532-4435 Cited by: §1.3. [6] E. Even-Dar, S. Mannor, and Y. Mansour (2002) PAC bounds for multi-armed bandit and markov decision processes. In Computational Learning Theory, J. Kivinen and R. H. Sloan (Eds.), Berlin, Heidelberg, p. 255–270. External Links: ISBN 978-3-540-45435-9 Cited by: §1.3, §1. [7] V. Gabillon, M. Ghavamzadeh, and A. Lazaric (2012) Best arm identification: a unified approach to fixed budget and fixed confidence. In Advances in Neural Information Processing Systems, F. Pereira, C.J. Burges, L. Bottou, and K.Q. Weinberger (Eds.), Vol. 25. External Links: Link Cited by: §1.3, §3.3, §3, §5.2. [8] A. Garivier and E. Kaufmann (2016) Optimal best arm identification with fixed confidence. In 29th Annual Conference on Learning Theory, V. Feldman, A. Rakhlin, and O. Shamir (Eds.), Proceedings of Machine Learning Research, Vol. 49, Columbia University, New York, New York, USA, p. 998–1027. External Links: Link Cited by: §1.3, §1. [9] L. Gretta and E. Price (2024) Sharp Noisy Binary Search with Monotonic Probabilities. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024), K. Bringmann, M. Grohe, G. Puppis, and O. Svensson (Eds.), Leibniz International Proceedings in Informatics (LIPIcs), Vol. 297, Dagstuhl, Germany, p. 75:1–75:19. Note: Keywords: fine-grained algorithms, randomized/probabilistic methods, sublinear/streaming algorithms, noisy binary search External Links: ISBN 978-3-95977-322-5, ISSN 1868-8969, Link, Document Cited by: §A.2, §A.3. [10] O. A. Hanna, L. Yang, and C. Fragouli (2022) Solving multi-arm bandit using a few bits of communication. In Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, G. Camps-Valls, F. J. R. Ruiz, and I. Valera (Eds.), Proceedings of Machine Learning Research, Vol. 151, p. 11215–11236. External Links: Link Cited by: §1.3. [11] E. Hillel, Z. S. Karnin, T. Koren, R. Lempel, and O. Somekh (2013) Distributed exploration in multi-armed bandits. In Advances in Neural Information Processing Systems, C.J. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K. Weinberger (Eds.), Vol. 26. External Links: Link Cited by: §1.3. [12] K. Jamieson, M. Malloy, R. Nowak, and S. Bubeck (2014) Lil’ ucb : an optimal exploration algorithm for multi-armed bandits. In Proceedings of The 27th Conference on Learning Theory, M. F. Balcan, V. Feldman, and C. Szepesvári (Eds.), Proceedings of Machine Learning Research, Vol. 35, Barcelona, Spain, p. 423–439. External Links: Link Cited by: §1.3. [13] S. Kalyanakrishnan, A. Tewari, P. Auer, and P. Stone (2012) PAC subset selection in stochastic multi-armed bandits. In Proceedings of the 29th International Conference on Machine Learning (ICML 2012), p. 655–662. External Links: Link Cited by: §1.3. [14] Z. Karnin, T. Koren, and O. Somekh (2013) Almost optimal exploration in multi-armed bandits. In Proceedings of the 30th International Conference on Machine Learning, S. Dasgupta and D. McAllester (Eds.), Proceedings of Machine Learning Research, Vol. 28, Atlanta, Georgia, USA, p. 1238–1246. External Links: Link Cited by: §1.3, §1. [15] E. Kaufmann, O. Cappé, and A. Garivier (2016) 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: §1.3. [16] A. Kipnis and J. C. Duchi (2022) Mean estimation from one-bit measurements. IEEE Transactions on Information Theory 68 (9), p. 6276–6296. External Links: Document Cited by: §1.3. [17] R. Kleinberg and F. T. Leighton (2003) The value of knowing a demand curve: bounds on regret for online posted-price auctions. In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p. 594–605. External Links: Link Cited by: §1. [18] R. Kumar and S. Vatedka (2026) One-bit distributed mean estimation with unknown variance. Transactions on Machine Learning Research. Note: J2C Certification External Links: ISSN 2835-8856, Link Cited by: §1.3. [19] I. Lau and J. Scarlett (2025) Quantile multi-armed bandits with 1-bit feedback. In 36th International Conference on Algorithmic Learning Theory, External Links: Link Cited by: §1.3. [20] I. Lau and J. Scarlett (2026) Order-optimal sequential 1-bit mean estimation in general tail regimes. External Links: 2604.07796, Link Cited by: §C.4, Figure 3, Figure 3, §F.1, §F.1, §F.1, §F.1, §1, §1.2, §1.2, §1.2, §1.3, §2, §3.3, §4, Figure 1, Figure 1, §5.1, Remark 7, Remark 7. [21] I. Lau and J. Scarlett (2026) Sequential 1-bit mean estimation with near-optimal sample complexity. In The 29th International Conference on Artificial Intelligence and Statistics, External Links: Link Cited by: §1. [22] S. Mannor and J. N. Tsitsiklis (2004) The sample complexity of exploration in the multi-armed bandit problem. Journal of Machine Learning Research 5 (Jun), p. 623–648. External Links: Link Cited by: §1.3. [23] A. Ribeiro and G.B. Giannakis (2006) Bandwidth-constrained distributed estimation for wireless sensor networks-part i: gaussian case. IEEE Transactions on Signal Processing 54 (3), p. 1131–1143. External Links: Document Cited by: §1. [24] J. Shah, M. Cardone, C. Rush, and A. Dytso (2025) Generalized linear models with 1-bit measurements: asymptotics of the maximum likelihood estimator. In ICASSP 2025 - 2025 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), p. 1–5. External Links: Document Cited by: §1.3. [25] D. Vial, S. Shakkottai, and R. Srikant (2020) One-bit feedback is sufficient for upper confidence bound policies. CoRR abs/2012.02876. External Links: Link Cited by: §1.3. Appendix This appendix provides additional proofs, full algorithm pseudo-codes, and experimental details referenced in the main text. Unless stated otherwise, notation matches the main text. Contents Item Page Appendix A: The MedianEst routine A Appendix B: Proofs for Section 2 (A 1-bit mean estimator) B Appendix C: Proofs for Section 3 (1-bit BAI algorithm and upper bound) C Appendix D: Proofs for Section 4 (Lower bound) D Appendix E: Detailed algorithms E Appendix F: Numerical experiment details F Appendix A The MedianEst routine A.1 Bounding the mean via the median In Section 2, we assumed that for each arm k, the learner is provided with an anchor point ckc_k satisfying |μk−ck|≤σ| _k-c_k|≤σ. We can rigorously satisfy this assumption by estimating the median of the reward distribution. Let c be the true median of a random variable X with mean μ and variance bounded by σ2σ^2. By Cantelli’s inequality (the one-sided Chebyshev inequality), for any a>0a>0, we have: Pr(X−μ≥a)≤σ2σ2+a2. (X-μ≥ a)≤ σ^2σ^2+a^2. If the median is greater than the mean (c>μc>μ), we can substitute a=c−μa=c-μ to obtain: Pr(X≥c)≤σ2σ2+(c−μ)2. (X≥ c)≤ σ^2σ^2+(c-μ)^2. By the definition of the median, Pr(X≥c)≥12 (X≥ c)≥ 12. Combining these yields: 12≤σ2σ2+(c−μ)2⟹σ2+(c−μ)2≤2σ2⟹(c−μ)2≤σ2. 12≤ σ^2σ^2+(c-μ)^2 σ^2+(c-μ)^2≤ 2σ^2 (c-μ)^2≤σ^2. Taking the square root gives |c−μ|≤σ|c-μ|≤σ. A symmetric argument using Pr(X≤c) (X≤ c) applies when c<μc<μ. Therefore, finding a point close to the true median naturally provides a valid anchor point ckc_k that is guaranteed to be at most O(σ)O(σ) away from the true mean. A.2 Noisy binary search To find this median, assume we know a bounded range [−λ,λ][-λ,λ] containing the median. We discretize this interval into a uniform grid of n points x1<x2<⋯<xnx_1<x_2<…<x_n. Querying a threshold xix_i yields a 1-bit response Y=X≤xiY=1\X≤ x_i\, which is a Bernoulli random variable with success probability pi=Pr(X≤xi)p_i= (X≤ x_i). Because the cumulative distribution function is monotonic, the probabilities pip_i are non-decreasing. Our goal is to find a threshold xi∗x_i^* where the probability pi∗p_i^* crosses τ=1/2τ=1/2. This exactly matches the MonotonicNBS(τ,ε′τ, ) framework [9], where the algorithm must find an ε′ -good interval despite coins (thresholds) near the target being indistinguishable from it. As established by [9], for the median target τ=1/2τ=1/2, tolerance ε′∈(0,1/4) ∈(0,1/4), and failure probability γ∈(0,1/2)γ∈(0,1/2), the MedianEst algorithm successfully identifies a valid index ı such that the interval [Pr(X≤xı^),Pr(X≤xı^+1)][ (X≤ x_ ), (X≤ x_ +1)] intersects the target window (1/2−ε′,1/2+ε′)(1/2- ,1/2+ ) with probability at least 1−γ1-γ. To achieve this, the total number of 1-bit queries used by the algorithm is bounded by the sample complexity: M(n,ε′,γ)=O(1(ε′)2(logn+log2/3nlog1/31γ+log1γ)).M(n, ,γ)=O ( 1( )^2 ( n+ ^2/3n ^1/3 1γ+ 1γ ) ). A.3 The MedianEst algorithm The MedianEst algorithm is shown in Algorithm 1, which adapts BayesianScreeningSearch to our threshold grid. Because the iteration bound in [9] includes explicit constant factors that complicate the expression, we omit the exact loop count in Algorithm 1 to focus on the asymptotic scaling laws. Algorithm 1 MedianEst: 1-Bit Anchor Estimation 1: Uniformly discretized grid =(x1,…,xn)x=(x_1,…,x_n) with step size Δx x, tolerance ε′∈(0,1/4) ∈(0,1/4), failure probability γ∈(0,1/2)γ∈(0,1/2). 2: Initialize uniform prior: w1(i)=1n−1w_1(i)= 1n-1 for all i∈1,…,n−1i∈\1,…,n-1\. 3: Set sample budget M=M(n,ε′,γ)M=M(n, ,γ), and subsampling rate r=Θ(1/logn)r= (1/ n). 4: Initialize queried sequence list L=∅L= . 5: for t=1,…,Mt=1,…,M do 6: Compute the median index of the current posterior: jt=minj∈1,…,n−1:∑i=1jwt(i)≥12.j_t= \j∈\1,…,n-1\: _i=1^jw_t(i)≥ 12 \. 7: Append jtj_t to L. 8: Query the threshold xjtx_j_t and observe 1-bit feedback Yt=X≤xjtY_t=1\X≤ x_j_t\. 9: Compute the unnormalized posterior vtv_t by scaling weights based on YtY_t: vt(i)=wt(i)(1+2ε′(2Yt−1))if i≤jtwt(i)(1−2ε′(2Yt−1))if i>jt∀i∈1,…,n−1.v_t(i)= casesw_t(i) (1+2 (2Y_t-1) )&if i≤ j_t\\ w_t(i) (1-2 (2Y_t-1) )&if i>j_t cases ∀ i∈\1,…,n-1\. 10: Normalize the posterior: wt+1(i)=vt(i)∑k=1n−1vt(k)∀i∈1,…,n−1.w_t+1(i)= v_t(i) _k=1^n-1v_t(k) ∀ i∈\1,…,n-1\. 11: end for 12: Extract candidate set =L⌈k⋅rM⌉:k=1,2,…,⌊1/r⌋C= \L_ k· rM :k=1,2,…, 1/r \ from the history L. 13: Set verification budget N=Θ(1(ε′)2log||γ)N= ( 1( )^2 |C|γ ). 14: for each candidate index c∈c do 15: Draw N fresh samples X(1),…,X(N)X^(1),…,X^(N) to compute the empirical estimate: p^c=1N∑s=1NX(s)≤xc. p_c= 1N _s=1^N1\X^(s)≤ x_c\. 16: if |p^c−12|≤3ε′4 | p_c- 12 |≤ 3 4 then 17: return c^=xc+xc+12 c= x_c+x_c+12 ⊳ Return the midpoint of the verified interval 18: end if 19: end for A.4 Parameter selection and estimate validity Choosing the Tolerance (ε′ ). Because the sample complexity M(n,ε′,γ)M(n, ,γ) scales aggressively as O(1/(ε′)2)O(1/( )^2), we cannot afford to let ε′ shrink to 00 alongside the main BAI target accuracy ε . Instead, we fix ε′ as a moderate constant by setting ε′=0.05 =0.05. This choice avoids an exploding sample cost while maintaining a strictly bounded localization window. Choosing the Grid Density (n). Discretize the bounded domain [−λ,λ][-λ,λ] using a uniform step size Δx=κ⋅σ x=κ·σ for a small constant κ>0κ>0. This results in a grid of size n=Θ(λ/σ)n= (λ/σ). Crucially, because n appears inside a logarithm in the sample complexity M(n,ε′,γ)M(n, ,γ), this domain discretization contributes only an additive logarithmic term to the sample budget. The following lemma transforms the probability guarantees of MedianEst into rigorous bounds of the distance to the true mean. Lemma 13 (Estimate Validity via MedianEst). Let X be a random variable with mean μ∈[−λ,λ]μ∈[-λ,λ] and variance proxy σ2σ^2. Let the continuous domain [−λ,λ][-λ,λ] be discretized into a uniform grid with step size Δx=κ⋅σ x=κ·σ. If the MedianEst routine successfully identifies an ε′ -good interval [xı^,xı^+1][x_ ,x_ +1] for the target τ=1/2τ=1/2, then the returned midpoint c^=(xı^+xı^+1)/2 c=(x_ +x_ +1)/2 satisfies: |c^−μ|≤(1/2+ε′1/2−ε′+κ2)σ.| c-μ|≤ ( 1/2+ 1/2- + κ2 )σ. Proof. Because the returned interval is ε′ -good, the probability range [Pr(X≤xı^),Pr(X≤xı^+1)][ (X≤ x_ ), (X≤ x_ +1)] must intersect the target window (1/2−ε′,1/2+ε′)(1/2- ,1/2+ ). Since cumulative probabilities are non-decreasing, this intersection gives us two conditions: Pr(X≤xı^)<12+ε′andPr(X≤xı^+1)>12−ε′ (X≤ x_ )< 12+ (X≤ x_ +1)> 12- We can use these to bound the tails. The upper tail satisfies Pr(X>xı^)=1−Pr(X≤xı^)>1/2−ε′ (X>x_ )=1- (X≤ x_ )>1/2- , while the lower tail directly satisfies Pr(X≤xı^+1)>1/2−ε′ (X≤ x_ +1)>1/2- . We evaluate the distance from μ to the grid step by considering three cases: Case 1 (μ<xı^μ<x_ ): Applying Cantelli’s inequality gives Pr(X≥xı^)≤σ2σ2+(xı^−μ)2 (X≥ x_ )≤ σ^2σ^2+(x_ -μ)^2. Combining with our known tail bound, we get: 12−ε′<Pr(X>xı^)≤Pr(X≥xı^)≤σ2σ2+(xı^−μ)2 12- < (X>x_ )≤ (X≥ x_ )≤ σ^2σ^2+(x_ -μ)^2 Solving for the distance yields xı^−μ<σ1/2+ε′1/2−ε′x_ -μ<σ 1/2+ 1/2- . Because the returned estimate c c is the midpoint of the grid interval, its distance to the true mean is |c^−μ|=Δx2+(xı^−μ)<κσ2+σ1/2+ε′1/2−ε′.| c-μ|= x2+(x_ -μ)< κσ2+σ 1/2+ 1/2- . Case 2 (μ>xı^+1μ>x_ +1): Applying a symmetric Cantelli bound gives Pr(X≤xı^+1)≤σ2σ2+(μ−xı^+1)2 (X≤ x_ +1)≤ σ^2σ^2+(μ-x_ +1)^2. Combining with our lower tail condition, we have: 12−ε′<Pr(X≤xı^+1)≤σ2σ2+(μ−xı^+1)2 12- < (X≤ x_ +1)≤ σ^2σ^2+(μ-x_ +1)^2 Rearranging the inequality yields μ−xı^+1<σ1/2+ε′1/2−ε′μ-x_ +1<σ 1/2+ 1/2- . The distance from the midpoint is |c^−μ|=(μ−xı^+1)+Δx2<σ1/2+ε′1/2−ε′+κσ2.| c-μ|=(μ-x_ +1)+ x2<σ 1/2+ 1/2- + κσ2. Case 3 (xı^≤μ≤xı^+1x_ ≤μ≤ x_ +1): The true mean is inside the identified interval. The absolute maximum distance from the midpoint c c to any point inside this grid step is trivially bounded by half the step size, Δx2=κσ2 x2= κσ2. This is strictly smaller than the bounds derived in Cases 1 and 2. We conclude that in all possible scenarios, the initial estimate satisfies: |c^−μ|≤(1/2+ε′1/2−ε′+κ2)σ| c-μ|≤ ( 1/2+ 1/2- + κ2 )σ ∎ With ε′=0.05 =0.05 and κ=0.2κ=0.2, the guaranteed bound becomes |c^−μ|≤1.205σ| c-μ|≤ 1.205σ. We can, in principle, choose ε′ and κ to bring this bound arbitrarily close to σ, but doing so will negatively affect the sample complexity. Because the sample requirement of the MedianEst routine scales as O(1/(ε′)2)O(1/( )^2) and logarithmically with the grid size n∝1/κn 1/κ, shrinking these parameters heavily inflates the initialization cost. Ultimately, pushing for this precision is unnecessary; a difference of O(σ)O(σ) in the anchor’s distance from the mean will only affect the constant factors in the estimator’s time-uniform confidence sequence (Theorem 5) and the final best-arm identification sample complexity bounds (Theorem 8 and Theorem 10). Lemma 14 (Total Initialization Complexity). By applying a union bound over the K arms and allocating a failure budget of γ=δ/(2K)γ=δ/(2K) to each MedianEst instance, the total initialization burn-in phase is bounded by: Tinit=O(K(logλσ+logKδ)).T_init=O (K ( λσ+ Kδ ) ). Proof. For each of the K arms, we run the MedianEst routine. With our fixed ε′ and the grid size n=Θ(λ/σ)n= (λ/σ), the sample complexity per arm is bounded by M(n,ε′,δ/(2K))M(n, ,δ/(2K)). The additive terms in the query complexity are: O(logn+log2/3nlog1/31γ+log1γ).O ( n+ ^2/3n ^1/3 1γ+ 1γ ). By Young’s inequality, the cross term is bounded by the linear combination of the individual logarithmic terms: log2/3nlog1/31γ≤23logn+13log1γ=O(logn+log1γ). ^2/3n ^1/3 1γ≤ 23 n+ 13 1γ=O ( n+ 1γ ). Thus, the sample complexity per arm simplifies to O(logn+log(1/γ))O ( n+ (1/γ) ). Substituting n=Θ(λ/σ)n= (λ/σ) and γ=δ/(2K)γ=δ/(2K) yields O(logλσ+logKδ)O ( λσ+ Kδ ) samples per arm. Multiplying this per-arm cost by the K parallel instances gives the total bound TinitT_init. Because TinitT_init scales strictly with the number of arms K and is entirely independent of the arm gaps Δk _k, it operates as a purely additive initialization cost. ∎ Appendix B Proofs for Section 2 (A 1-bit mean estimator) Throughout all the proofs, we write a∧b:=mina,ba b:= \a,b\. B.1 Proof of Lemma 2 (Tail-integral identity) Proof. Fix w∈ℝw and L>0L>0. If w≥0w≥ 0, then w≤−t=01\w≤-t\=0 for every t≥0t≥ 0, and hence ∫0L(w≥t−w≤−t)dt=∫0Lw≥tdt=∫0w∧L1dt=w∧L=[w]L. _0^L (1\w≥ t\-1\w≤-t\ )\,dt= _0^L1\w≥ t\\,dt= _0^w L1\,dt=w L=[w]_L. If w<0w<0, then w≥t=01\w≥ t\=0 for every t≥0t≥ 0, and therefore ∫0L(w≥t−w≤−t)dt=−∫0Lw≤−tdt=−∫0(−w)∧L1dt=[w]L. _0^L (1\w≥ t\-1\w≤-t\ )\,dt=- _0^L1\w≤-t\\,dt=- _0^(-w) L1\,dt=[w]_L. This proves the pointwise identity. Taking expectations gives [[W]L]=∫0L(Pr(W≥t)−Pr(W≤−t))t,E[[W]_L]= _0^L ( (W≥ t)- (W≤-t) )\,dt, since the integrand is bounded in absolute value by 11 on a finite interval. ∎ B.2 Proof of Lemma 3 We fix L≥σL≥σ in the following proofs. Proof of (i). Condition on W=wW=w. Since S is uniform on +1,−1\+1,-1\, independent of T, and Y=S(X−c)≥T=SW≥T,Y=1\S(X-c)≥ T\=1\SW≥ T\, we have [Z∣W=w] [Z W=w] =12∫0L2gL(t)gL(t) 1w≥tdt−12∫0L2gL(t)gL(t) 1w≤−tdt = 12 _0^L 2g_L(t)\,g_L(t)\,1\w≥ t\\,dt- 12 _0^L 2g_L(t)\,g_L(t)\,1\w≤-t\\,dt =∫0L(w≥t−w≤−t)dt. = _0^L (1\w≥ t\-1\w≤-t\ )\,dt. By Lemma 2, this equals [w]L[w]_L. Therefore [Z∣W]=[W]Lalmost surely.E[Z W]=[W]_L surely. and taking expectations yields [Z]=[[W]L].E[Z]=E[[W]_L]. ∎ Proof of (i). Again condition on W=wW=w, and set u:=|w|∧L.u:=|w| L. Since Z=2SgL(T)YZ= 2Sg_L(T)Y, we have Z2=4gL(T)2YZ^2= 4g_L(T)^2Y. Hence [Z2∣W=w] [Z^2 W=w] =12∫0L4gL(t)2gL(t) 1w≥tdt+12∫0L4gL(t)2gL(t) 1w≤−tdt = 12 _0^L 4g_L(t)^2\,g_L(t)\,1\w≥ t\\,dt+ 12 _0^L 4g_L(t)^2\,g_L(t)\,1\w≤-t\\,dt =2∫0L1gL(t)(w≥t+w≤−t)dt =2 _0^L 1g_L(t) (1\w≥ t\+1\w≤-t\ )\,dt =2∫0udtgL(t). =2 _0^u dtg_L(t). Using 1gL(t)=αLmaxσ,t, 1g_L(t)= _L \σ,t\, we obtain [Z2∣W=w]=2αL∫0umaxσ,tt.E[Z^2 W=w]=2 _L _0^u \σ,t\\,dt. If u≤σu≤σ, then [Z2∣W=w]=2αLσu≤αL(σ2+u2),E[Z^2 W=w]=2 _Lσ u≤ _L(σ^2+u^2), by the inequality 2ab≤a2+b22ab≤ a^2+b^2. If u≥σu≥σ, then [Z2∣W=w] [Z^2 W=w] =2αL(∫0σt+∫σutt) =2 _L ( _0^σ\,dt+ _σ^ut\,dt ) =2αL(σ2+u2−σ22)=αL(σ2+u2). =2 _L (σ^2+ u^2-σ^22 )= _L(σ^2+u^2). Thus, in all cases, [Z2∣W=w]≤αL(σ2+(|w|∧L)2)=αL(σ2+([|w|]L)2).E[Z^2 W=w]≤ _L (σ^2+(|w| L)^2 )= _L (σ^2+([|w|]_L)^2 ). Taking expectations gives [Z2]≤αL(σ2+[([|W|]L)2]).E[Z^2]≤ _L (σ^2+E [([|W|]_L)^2 ] ). Since ([|W|]L)2≤W2([|W|]_L)^2≤ W^2 and [W2]≤2σ2E[W^2]≤ 2σ^2, we conclude that [Z2]≤αL(σ2+2σ2)=3αLσ2.E[Z^2]≤ _L(σ^2+2σ^2)=3 _Lσ^2. Therefore Var(Z)≤[Z2]≤3αLσ2.Var(Z) [Z^2]≤ 3 _Lσ^2. ∎ Proof of (i). Since Y∈0,1Y∈\0,1\, |Z|=|2SgL(T)Y|≤2gL(T)=2αLmaxσ,T≤2αLL,|Z|= | 2Sg_L(T)Y |≤ 2g_L(T)=2 _L \σ,T\≤ 2 _LL, because T∈[0,L]T∈[0,L]. ∎ B.3 Proof of Lemma 4 (Clipping bias) Proof. For every real w, |w−[w]L|=(|w|−L)+.|w-[w]_L|=(|w|-L)_+. Also, for every x≥0x≥ 0, (x−L)+≤x24L.(x-L)_+≤ x^24L. Indeed, the inequality is trivial when x≤Lx≤ L. If x>Lx>L, then x−L≤x24L⇔0≤(x−2L)2.x-L≤ x^24L 0≤(x-2L)^2. Applying this with x=|W|x=|W|, we get |W−[W]L|=(|W|−L)+≤W24L.|W-[W]_L|=(|W|-L)_+≤ W^24L. Therefore |[W]−[[W]L]|=|[W−[W]L]|≤[|W−[W]L|]≤[W2]4L≤σ22L, |E[W]-E[[W]_L] |= |E[W-[W]_L] | [\,|W-[W]_L|\, ]≤ E[W^2]4L≤ σ^22L, since [W2]≤2σ2E[W^2]≤ 2σ^2. ∎ B.4 Proof of Theorem 5 (Confidence sequence for the 1-bit estimator) We split the proof into four lemmas. The first lemma records the mean, variance, and range properties of the centered 1-bit variables. The second lemma turns these properties into an exponential supermartingale. The third lemma derives an epoch-wise Bernstein boundary by combining Ville’s inequality with an explicit optimization over the exponential parameter. The fourth lemma stitches the epoch-wise bounds into a genuine time-uniform confidence sequence for the clipped target. The theorem then follows by adding the clipping-bias term. Lemma 15 (Centered process properties). Fix L≥σL≥σ, and define θL:=[[W]L],Xi:=Zi−θL,Sn:=∑i=1nXi. _L:=E[[W]_L], X_i:=Z_i- _L, S_n:= _i=1^nX_i. Then X1,X2,…X_1,X_2,… are i.i.d. and mean-zero, and satisfy [Xi]=0,Var(Xi)≤vL,|Xi|≤bLa.s.,E[X_i]=0, (X_i)≤ v_L, |X_i|≤ b_L .s., where vL:=3αLσ2,bL:=3αLL.v_L:=3 _Lσ^2, b_L:=3 _LL. Proof. By Lemma 3(i), [Zi]=[[W]L]=θL,E[Z_i]=E[[W]_L]= _L, and therefore [Xi]=[Zi−θL]=0.E[X_i]=E[Z_i- _L]=0. Since subtracting a constant does not change the variance, Lemma 3(i) gives Var(Xi)=Var(Zi)≤3αLσ2=vL.Var(X_i)=Var(Z_i)≤ 3 _Lσ^2=v_L. It remains to prove the range bound. By Lemma 3(i), |Zi|≤2αLLa.s.|Z_i|≤ 2 _LL .s. Also, since |[W]L|≤L|[W]_L|≤ L, |θL|=|[[W]L]|≤|[W]L|≤L.| _L|=|E[[W]_L]| |[W]_L|≤ L. Hence |Xi|=|Zi−θL|≤|Zi|+|θL|≤2αLL+L≤3αLL=bL,|X_i|=|Z_i- _L|≤|Z_i|+| _L|≤ 2 _LL+L≤ 3 _LL=b_L, where we used αL≥1 _L≥ 1. This proves the claim. ∎ Lemma 16 (Bernstein supermartingale). For every λ∈[0,3/bL)λ∈[0,3/b_L), define ψL(λ):=vLλ22(1−bLλ/3),Mn(λ):=exp(λSn−nψL(λ)). _L(λ):= v_Lλ^22(1-b_Lλ/3), M_n(λ):= \! (λ S_n-n _L(λ) ). Then Mn(λ)n≥0\M_n(λ)\_n≥ 0 is a nonnegative supermartingale. Proof. Since [Xi]=0E[X_i]=0, Var(Xi)≤vLVar(X_i)≤ v_L, and |Xi|≤bL|X_i|≤ b_L by Lemma 15, the standard Bernstein mgf bound yields [eλXi]≤exp(vLλ22(1−bLλ/3))=eψL(λ)for all λ∈[0,3/bL).E[e^λ X_i]≤ \! ( v_Lλ^22(1-b_Lλ/3) )=e _L(λ) all λ∈[0,3/b_L). Therefore, conditioning on X1,…,Xn−1X_1,…,X_n-1, [Mn(λ)∣X1,…,Xn−1] [M_n(λ) X_1,…,X_n-1] =[exp(λSn−1+λXn−nψL(λ))∣X1,…,Xn−1] =E\! [ \! (λ S_n-1+λ X_n-n _L(λ) ) X_1,…,X_n-1 ] =Mn−1(λ)e−ψL(λ)[eλXn] =M_n-1(λ)\,e^- _L(λ)E[e^λ X_n] ≤Mn−1(λ). ≤ M_n-1(λ). Thus Mn(λ)n≥0\M_n(λ)\_n≥ 0 is a supermartingale. Since Mn(λ)M_n(λ) is an exponential of a real-valued random variable, it is strictly positive almost surely, hence nonnegative. ∎ Lemma 17 (Epoch-wise stitched Bernstein bound). For each integer j≥0j≥ 0, let Nj:=2j+1,xj(γ):=log(π2(j+1)23γ).N_j:=2^j+1, x_j(γ):= \! ( π^2(j+1)^23γ ). Then Pr(∃n∈2j,…,2j+1−1:Sn≥2vLnxj(γ)+bLxj(γ)3)≤e−xj(γ). \! (∃ n∈\2^j,…,2^j+1-1\:S_n≥ 2 v_Ln\,x_j(γ)+ b_Lx_j(γ)3 )≤ e^-x_j(γ). Proof. Fix j≥0j≥ 0, and write N:=Nj=2j+1,x:=xj(γ).N:=N_j=2^j+1, x:=x_j(γ). By Ville’s inequality applied to the nonnegative supermartingale Mn(λ)n≥0\M_n(λ)\_n≥ 0 from Lemma 16, for every λ∈[0,3/bL)λ∈[0,3/b_L), Pr(∃n≤N:Mn(λ)≥ex)≤e−x. \! (∃ n≤ N:M_n(λ)≥ e^x )≤ e^-x. Using the definition of Mn(λ)M_n(λ), this is equivalent to Pr(∃n≤N:λSn−nψL(λ)≥x)≤e−x. \! (∃ n≤ N:λ S_n-n _L(λ)≥ x )≤ e^-x. Now define the event Aλ:=∃n≤N:Sn≥x+NψL(λ)λ.A_λ:= \∃ n≤ N:S_n≥ x+N _L(λ)λ \. If AλA_λ occurs, then for some n≤Nn≤ N, λSn−nψL(λ)≥λ⋅x+NψL(λ)λ−NψL(λ)=x.λ S_n-n _L(λ)≥λ· x+N _L(λ)λ-N _L(λ)=x. Hence Aλ⊆∃n≤N:λSn−nψL(λ)≥x,A_λ \∃ n≤ N:λ S_n-n _L(λ)≥ x \, and therefore Pr(Aλ)≤e−x. (A_λ)≤ e^-x. Equivalently, Pr(∃n≤N:Sn≥x+NψL(λ)λ)≤e−xfor all λ∈[0,3/bL). \! (∃ n≤ N:S_n≥ x+N _L(λ)λ )≤ e^-x all λ∈[0,3/b_L). We now optimize the boundary over λ. Set cL:=bL3.c_L:= b_L3. Then x+NψL(λ)λ=xλ+NvLλ2(1−cLλ)=:g(λ),0<λ<1cL. x+N _L(λ)λ= xλ+ Nv_Lλ2(1-c_Lλ)=:g(λ), 0<λ< 1c_L. Differentiating, g′(λ)=−xλ2+NvL2(1−cLλ)2.g (λ)=- xλ^2+ Nv_L2(1-c_Lλ)^2. Setting g′(λ)=0g (λ)=0 gives xλ2=NvL2(1−cLλ)2. xλ^2= Nv_L2(1-c_Lλ)^2. Taking square roots and rearranging, xλ=NvL/21−cLλ⟺1λ=NvL2x+cL. xλ= Nv_L/21-c_Lλ 1λ= Nv_L2x+c_L. Thus the optimizer is λ∗=1NvL/(2x)+cL. _*= 1 Nv_L/(2x)+c_L. Substituting λ∗ _* into g, we obtain g(λ∗) g( _*) =x(NvL2x+cL)+NvL2NvL/(2x) =x\! ( Nv_L2x+c_L )+ Nv_L2 Nv_L/(2x) =NvLx2+NvLx2+cLx = Nv_Lx2+ Nv_Lx2+c_Lx =2vLNx+bLx3. = 2v_LNx+ b_Lx3. Therefore Pr(∃n≤N:Sn≥2vLNx+bLx3)≤e−x. \! (∃ n≤ N:S_n≥ 2v_LNx+ b_Lx3 )≤ e^-x. Recalling that N=2j+1N=2^j+1 and x=xj(γ)x=x_j(γ), we get Pr(∃n≤2j+1:Sn≥2vL2j+1xj(γ)+bLxj(γ)3)≤e−xj(γ). \! (∃ n≤ 2^j+1:S_n≥ 2v_L2^j+1x_j(γ)+ b_Lx_j(γ)3 )≤ e^-x_j(γ). Finally, if n∈2j,…,2j+1−1n∈\2^j,…,2^j+1-1\, then n≥2jn≥ 2^j, and so 2vL2j+1xj(γ)=2vL2jxj(γ)≤2vLnxj(γ). 2v_L2^j+1x_j(γ)=2 v_L2^jx_j(γ)≤ 2 v_Ln\,x_j(γ). Hence Pr(∃n∈2j,…,2j+1−1:Sn≥2vLnxj(γ)+bLxj(γ)3)≤e−xj(γ), \! (∃ n∈\2^j,…,2^j+1-1\:S_n≥ 2 v_Ln\,x_j(γ)+ b_Lx_j(γ)3 )≤ e^-x_j(γ), as claimed. ∎ Lemma 18 (Confidence sequence for the clipped target). Define xn(γ):=log(π2(⌊log2n⌋+1)23γ).x_n(γ):= \! ( π^2( _2n +1)^23γ ). Then with probability at least 1−γ1-γ, simultaneously for all n≥1n≥ 1, |Z¯n−θL|≤2vLxn(γ)n+bLxn(γ)3n.| Z_n- _L|≤ 2 v_Lx_n(γ)n+ b_Lx_n(γ)3n. Proof. For each j≥0j≥ 0, apply Lemma 17 to both SnS_n and −Sn-S_n. This yields Pr(∃n∈2j,…,2j+1−1:|Sn|≥2vLnxj(γ)+bLxj(γ)3)≤2e−xj(γ). \! (∃ n∈\2^j,…,2^j+1-1\:|S_n|≥ 2 v_Ln\,x_j(γ)+ b_Lx_j(γ)3 )≤ 2e^-x_j(γ). Now e−xj(γ)=3γπ2(j+1)2,e^-x_j(γ)= 3γπ^2(j+1)^2, and therefore ∑j=0∞2e−xj(γ)=6γπ2∑j=0∞1(j+1)2=6γπ2⋅π26=γ. _j=0^∞2e^-x_j(γ)= 6γπ^2 _j=0^∞ 1(j+1)^2= 6γπ^2· π^26=γ. Hence, by a union bound over all dyadic epochs, with probability at least 1−γ1-γ, for every j≥0j≥ 0 and every n∈2j,…,2j+1−1n∈\2^j,…,2^j+1-1\, |Sn|≤2vLnxj(γ)+bLxj(γ)3.|S_n|≤ 2 v_Ln\,x_j(γ)+ b_Lx_j(γ)3. Since j=⌊log2n⌋j= _2n on this epoch, this can be written as |Sn|≤2vLnxn(γ)+bLxn(γ)3for all n≥1.|S_n|≤ 2 v_Ln\,x_n(γ)+ b_Lx_n(γ)3 all n≥ 1. Dividing by n gives |Z¯n−θL|=|Sn|n≤2vLxn(γ)n+bLxn(γ)3nfor all n≥1,| Z_n- _L|= |S_n|n≤ 2 v_Lx_n(γ)n+ b_Lx_n(γ)3n all n≥ 1, which proves the claim. ∎ Proof of Theorem 5. By Lemma 4, |θL−[W]|≤σ22L.| _L-E[W]|≤ σ^22L. Also, μ^n=c+Z¯n,μ=c+[W]. μ_n=c+ Z_n, μ=c+E[W]. Therefore |μ^n−μ|=|Z¯n−[W]|≤|Z¯n−θL|+|θL−[W]|.| μ_n-μ|=| Z_n-E[W]|≤| Z_n- _L|+| _L-E[W]|. Combining this with Lemma 18, we conclude that with probability at least 1−γ1-γ, simultaneously for all n≥1n≥ 1, |μ^n−μ|≤σ22L+2vLxn(γ)n+bLxn(γ)3n.| μ_n-μ|≤ σ^22L+2 v_Lx_n(γ)n+ b_Lx_n(γ)3n. Finally, substituting vL=3αLσ2,bL=3αLL,v_L=3 _Lσ^2, b_L=3 _LL, gives |μ^n−μ|≤σ22L+23αLσ2xn(γ)n+αLLxn(γ)nfor all n≥1.| μ_n-μ|≤ σ^22L+2 3 _Lσ^2x_n(γ)n+ _LL\,x_n(γ)n all n≥ 1. This is exactly the claimed confidence sequence. ∎ B.5 Sample-complexity inversion Proof of Corollary 6. Let β>0β>0 be the desired accuracy. To balance the clipping bias and the variance, we choose the clipping level L=2σ2βL= 2σ^2β. By Lemma 4, this ensures the clipping bias is bounded by σ22L=β4 σ^22L= β4. From Theorem 5, with probability at least 1−γ1-γ, simultaneously for all n≥1n≥ 1: |μ^n−μ|≤β4+23αLσ2xn(γ)n+αLLxn(γ)n| μ_n-μ|≤ β4+2 3 _Lσ^2x_n(γ)n+ _LL\,x_n(γ)n where αL=1+log2σβ _L=1+ 2σβ and xn(γ)=log(π2(1+⌊log2n⌋)23γ)x_n(γ)= ( π^2(1+ _2n )^23γ ). To guarantee |μ^n−μ|≤β| μ_n-μ|≤β, we enforce that the concentration term is bounded by β2 β2 and the Bernstein range term by β4 β4. Solving these individually for n: 23αLσ2xn(γ)n≤β2 2 3 _Lσ^2x_n(γ)n≤ β2 ⟹n≥48αLσ2xn(γ)β2 n≥ 48 _Lσ^2x_n(γ)β^2 (1) αLLxn(γ)n≤β4 _LL\,x_n(γ)n≤ β4 ⟹n≥8αLσ2xn(γ)β2 n≥ 8 _Lσ^2x_n(γ)β^2 (2) Condition (1) is strictly dominant. Let us define H:=48αLσ2β2,H:= 48 _Lσ^2β^2, so that our goal is to find an integer n satisfying n≥Hxn(γ)n≥ Hx_n(γ). Choose n:=⌈CHη⌉,η:=log1γ+loglog(maxH,e),n:= CHη , η:= 1γ+ ( \H,e\), where C>0C>0 is a sufficiently large universal constant. Since η≥1η≥ 1, we have logH≤H,logη≤η. H≤ H, η≤η. Moreover, logn≤log(C+1)+logH+logη. n≤ (C+1)+ H+ η. Taking another logarithm and using log(a+b+c)≤log3+maxloga,logb,logc (a+b+c)≤ 3+ \ a, b, c\, we get loglogn≤c1+maxloglogH,logη≤c2+η n≤ c_1+ \ H, η\≤ c_2+η for universal constants c1,c2>0c_1,c_2>0, because logη≤η η≤η. Since 1+⌊log2n⌋≤c3logn1+ _2n ≤ c_3 n for some universal constant c3>0c_3>0, we have xn(γ) x_n(γ) =log(π2(1+⌊log2n⌋)23γ) = \! ( π^2 (1+ _2n )^23γ ) ≤log(c4(logn)2γ) ≤ \! ( c_4( n)^2γ ) =logc4+log(1γ)+2loglogn = c_4+ \! ( 1γ )+2 n ≤c5[log(1γ)+loglog(maxH,e)]=c5η, ≤ c_5 [ \! ( 1γ )+ ( \H,e\) ]=c_5η, for universal constants c4,c5>0c_4,c_5>0. Choosing C≥c5C≥ c_5, we obtain n≥CHη≥Hxn(γ).n≥ CHη≥ Hx_n(γ). Consequently, condition (1) is satisfied. Since αL=1+log2σβ _L=1+ 2σβ, we have H=Θ(σ2β2logσβ)H= ( σ^2β^2 σβ ), and therefore n=O(σ2β2logσβ[log1γ+loglog(e+σβ)]).n=O ( σ^2β^2 σβ [ 1γ+ (e+ σβ ) ] ). This completes the proof. ∎ Appendix C Proofs for Section 3 (1-bit BAI algorithm and upper bound) C.1 Fixed clipping: proof of Theorem 8 This subsection proves the sample complexity upper bound of the fixed-clipping algorithm. We first establish a high-probability event on which all fixed-clipping confidence intervals are valid uniformly over time (Lemma 19). On this event, the interval stopping rule can only return an ε -optimal arm (Lemma 20). It remains to control the number of samples. The key structural step is Lemma 22: whenever the algorithm samples arm k, its stochastic radius must still be larger than a constant fraction of the effective gap. Solving this inequality gives an arm-wise pull bound, and summing these bounds over arms yields the stated sample complexity (Lemma 23). Throughout this subsection, fix Lε=2σ2ε,αε=1+log2σε,γ=δK.L_ = 2σ^2 , _ =1+ 2σ , γ= δK. For the fixed-clipping algorithm, write βε(n,γ)=ε4+23αεσ2xn(γ)n+2αεσ2xn(γ)nε,rε(n,γ):=βε(n,γ)−ε4. _ (n,γ)= 4+2 3 _ σ^2x_n(γ)n+ 2 _ σ^2x_n(γ)n , r_ (n,γ):= _ (n,γ)- 4. Let Zk,1,Zk,2,…Z_k,1,Z_k,2,… be i.i.d. copies of the estimator, each built from an independent reward sample and independent internal randomization of arm k. At a generic round, let NkN_k denote the number of 1-bit queries already made to arm k, and let μ^k=ck+1Nk∑i=1NkZk,i,LCBk=μ^k−βε(Nk,γ),UCBk=μ^k+βε(Nk,γ). μ_k=c_k+ 1N_k _i=1^N_kZ_k,i, _k= μ_k- _ (N_k,γ), _k= μ_k+ _ (N_k,γ). Lemma 19 (Fixed-clipping good event). With probability at least 1−δ1-δ, ℰfix:=⋂k=1K⋂n≥1|μ^k(n)−μk|≤βε(n,δ/K)E_ fix:= _k=1^K _n≥ 1 \ | μ_k(n)- _k |≤ _ (n,δ/K) \ holds throughout FixedClip-1BitBAI. Proof. For a fixed arm k, the samples used by its tail-integral estimator are i.i.d. when indexed by the local count n, regardless of the adaptive times at which arm k is selected. Applying Theorem 5 with clipping level LεL_ and failure probability δ/Kδ/K gives Pr(∀n≥1,|μ^k(n)−μk|≤βε(n,δ/K))≥1−δK. (∀ n≥ 1, | μ_k(n)- _k |≤ _ (n,δ/K) )≥ 1- δK. Taking a union bound over k∈[K]k∈[K] yields Pr(ℰfix)≥1−∑k=1KδK=1−δ. (E_ fix)≥ 1- _k=1^K δK=1-δ. The time-uniformity over n is what makes the event valid under the adaptive sampling rule. ∎ Lemma 20 (Fixed-clipping stopping correctness). On ℰfixE_ fix, if FixedClip-1BitBAI stops and returns k k, then μk^≥μ⋆−ε. _ k≥μ - . Proof. Let h be the arm returned by the algorithm. The stopping rule gives Bh=maxℓ≠hUCBℓ−LCBh≤ε.B_h= _ ≠ hUCB_ -LCB_h≤ . Equivalently, for every ℓ≠h ≠ h, UCBℓ−LCBh≤ε.UCB_ -LCB_h≤ . On ℰfixE_ fix, all intervals are valid, so LCBj≤μj≤UCBjfor every j∈.LCB_j≤ _j _j every j . Therefore, for every ℓ≠h ≠ h, μℓ−μh≤UCBℓ−LCBh≤ε. _ - _h _ -LCB_h≤ . If h=k⋆h=k , the claim is immediate. Otherwise, choosing ℓ=k⋆ =k gives μ⋆−μh≤ε,μ - _h≤ , and hence μh≥μ⋆−ε _h≥μ - . ∎ The next lemma is the key interval comparison: an arm can be pulled only while its own confidence radius is still large enough to explain the current ambiguity. Lemma 21 (Fixed-clipping structural comparison). Assume ℰfixE_ fix holds. Consider a non-stopping round, and write Bk=maxa≠kUCBa−LCBk,h∈argmink∈Bk,ℓ∈argmaxa≠hUCBa.B_k= _a≠ kUCB_a-LCB_k, h∈ _k B_k, ∈ _a≠ hUCB_a. If the algorithm samples k∈h,ℓk∈\h, \, then Bh≤min0,−Δk+2βk+2βk,B_h≤ \0,- _k+2 _k\+2 _k, where βk:=βε(Nk,δ/K) _k:= _ (N_k,δ/K). Proof. For brevity, write Ui:=UCBi,Li:=LCBi,βi:=βε(Ni,δ/K).U_i:=UCB_i, L_i:=LCB_i, _i:= _ (N_i,δ/K). Since Ui−Li=2βiU_i-L_i=2 _i and the intervals are valid on ℰfixE_ fix, we have Li≤μi≤Ui,Ui≤μi+2βi,Li≥μi−2βifor all i∈.L_i≤ _i≤ U_i, U_i≤ _i+2 _i, L_i≥ _i-2 _i all i . (3) By definition of ℓ , Bh=maxa≠hUa−Lh=Uℓ−Lh.B_h= _a≠ hU_a-L_h=U_ -L_h. Case 1: the sampled arm is k=ℓk= . The sampling rule gives βℓ≥βh _ ≥ _h. We first show that Lℓ≤LhL_ ≤ L_h. Suppose, for contradiction, that Lℓ>LhL_ >L_h. Then Uℓ=Lℓ+2βℓ>Lh+2βh=Uh.U_ =L_ +2 _ >L_h+2 _h=U_h. Since Uℓ=maxa≠hUaU_ = _a≠ hU_a, and since Uℓ>UhU_ >U_h, we have maxa≠ℓUa≤Uℓ. _a≠ U_a≤ U_ . Hence Bℓ=maxa≠ℓUa−Lℓ<Uℓ−Lh=Bh,B_ = _a≠ U_a-L_ <U_ -L_h=B_h, contradicting the definition of h as a minimizer of BkB_k. Thus Lℓ≤LhL_ ≤ L_h, and therefore Bh=Uℓ−Lh≤Uℓ−Lℓ=2βℓ.B_h=U_ -L_h≤ U_ -L_ =2 _ . (4) We next prove Bh≤−Δℓ+4βℓ.B_h≤- _ +4 _ . If h=k⋆h=k , then ℓ≠k⋆ ≠ k . Using (3) and βh≤βℓ _h≤ _ , Bh=Uℓ−Lh≤(μℓ+2βℓ)−(μ⋆−2βh)≤−Δℓ+4βℓ.B_h=U_ -L_h≤( _ +2 _ )-(μ -2 _h)≤- _ +4 _ . Now suppose h≠k⋆h≠ k . Since k⋆≠hk ≠ h, the definition of ℓ gives Uℓ=maxa≠hUa≥Uk⋆≥μ⋆.U_ = _a≠ hU_a≥ U_k ≥μ . If ℓ≠k⋆ ≠ k , then Uℓ≤μℓ+2βℓU_ ≤ _ +2 _ , and hence 2βℓ≥μ⋆−μℓ=Δℓ.2 _ ≥μ - _ = _ . If instead ℓ=k⋆ =k , we use the comparison Lℓ≤LhL_ ≤ L_h. By (3), μ⋆−2βℓ=μℓ−2βℓ≤Lℓ≤Lh≤μh.μ -2 _ = _ -2 _ ≤ L_ ≤ L_h≤ _h. Since h≠k⋆h≠ k , we have μh=μ⋆−Δh≤μ⋆−Δk⋆. _h=μ - _h≤μ - _k . Thus μ⋆−2βℓ≤μ⋆−Δk⋆,μ -2 _ ≤μ - _k , and so 2βℓ≥Δk⋆=Δℓ.2 _ ≥ _k = _ . Therefore, in all subcases with h≠k⋆h≠ k , 2βℓ≥Δℓ.2 _ ≥ _ . Combining this with (4) yields Bh≤2βℓ≤−Δℓ+4βℓ.B_h≤ 2 _ ≤- _ +4 _ . Consequently, Bh≤min2βℓ,−Δℓ+4βℓ=min0,−Δℓ+2βℓ+2βℓ.B_h≤ \2 _ ,- _ +4 _ \= \0,- _ +2 _ \+2 _ . Case 2: the sampled arm is k=hk=h. The sampling rule gives βh≥βℓ _h≥ _ . We first show that Uℓ≤UhU_ ≤ U_h. Suppose, for contradiction, that Uℓ>UhU_ >U_h. Then Lℓ=Uℓ−2βℓ>Uh−2βℓ≥Uh−2βh=Lh.L_ =U_ -2 _ >U_h-2 _ ≥ U_h-2 _h=L_h. Since Uℓ=maxa≠hUaU_ = _a≠ hU_a, and since Uℓ>UhU_ >U_h, we have maxa≠ℓUa≤Uℓ. _a≠ U_a≤ U_ . Hence Bℓ=maxa≠ℓUa−Lℓ<Uℓ−Lh=Bh,B_ = _a≠ U_a-L_ <U_ -L_h=B_h, contradicting the minimality of h. Thus Uℓ≤UhU_ ≤ U_h, and Bh=Uℓ−Lh≤Uh−Lh=2βh.B_h=U_ -L_h≤ U_h-L_h=2 _h. (5) We next prove Bh≤−Δh+4βh.B_h≤- _h+4 _h. If h=k⋆h=k , then every a≠ha≠ h satisfies μa≤μ⋆−Δh _a≤μ - _h. In particular, Bh=Uℓ−Lh≤(μℓ+2βℓ)−(μ⋆−2βh)≤−Δh+2βℓ+2βh≤−Δh+4βh.B_h=U_ -L_h≤( _ +2 _ )-(μ -2 _h)≤- _h+2 _ +2 _h≤- _h+4 _h. If h≠k⋆h≠ k , then k⋆≠hk ≠ h, and Uℓ=maxa≠hUa≥Uk⋆≥μ⋆.U_ = _a≠ hU_a≥ U_k ≥μ . Since we already proved Uh≥UℓU_h≥ U_ , it follows that Uh≥μ⋆U_h≥μ . Combining this with Uh≤μh+2βhU_h≤ _h+2 _h gives 2βh≥μ⋆−μh=Δh.2 _h≥μ - _h= _h. Thus 2βh≤−Δh+4βh,2 _h≤- _h+4 _h, and (5) implies Bh≤−Δh+4βh.B_h≤- _h+4 _h. Therefore Bh≤min2βh,−Δh+4βh=min0,−Δh+2βh+2βh.B_h≤ \2 _h,- _h+4 _h\= \0,- _h+2 _h\+2 _h. The two cases prove the lemma. ∎ Lemma 22 (A fixed-clipping sampled arm has large stochastic radius). On ℰfixE_ fix, if FixedClip-1BitBAI samples arm k in a non-stopping round, then rε(Nk,δ/K)>Δ~k4.r_ (N_k,δ/K)> _k4. Proof. In a non-stopping round, Bh>εB_h> . By Lemma 21, for the sampled arm k, ε<min0,−Δk+2βk+2βk. < \0,- _k+2 _k\+2 _k. If 2βk≥Δk2 _k≥ _k, then the minimum is 00, so βk>ε2. _k> 2. If 2βk<Δk2 _k< _k, then the minimum is −Δk+2βk- _k+2 _k, so ε<−Δk+4βk,and henceβk>Δk+ε4. <- _k+4 _k, hence _k> _k+ 4. Combining the two cases gives βk>maxε2,Δk+ε4. _k> \ 2, _k+ 4 \. Since rε(Nk,δ/K)=βk−ε/4r_ (N_k,δ/K)= _k- /4, we obtain rε(Nk,δ/K)>maxε4,Δk4=Δ~k4.r_ (N_k,δ/K)> \ 4, _k4 \= _k4. ∎ Lemma 23 (Fixed-clipping counting bound). On ℰfixE_ fix, FixedClip-1BitBAI uses at most O(Hfix(ε)[logKδ+loglogHfix(ε)])O\! (H_ fix( ) [ Kδ+ H_ fix( ) ] ) 1-bit queries. Proof. For each arm, define Ak:=αε(σ2Δ~k2+σ2εΔ~k),Hfix(ε)=∑k=1KAk.A_k:= _ ( σ^2 _k^2+ σ^2 _k ), H_ fix( )= _k=1^KA_k. Let xn:=xn(δ/K)=log(π2(1+⌊log2n⌋)2K3δ).x_n:=x_n(δ/K)= ( π^2(1+ _2n )^2K3δ ). We first record a deterministic implication. There exists a universal constant c0>0c_0>0 such that for all x≥1x≥ 1, n≥c0Akx⟹23αεσ2xn+2αεσ2xnε≤Δ~k4.n≥ c_0A_kx 2 3 _ σ^2xn+ 2 _ σ^2xn ≤ _k4. (6) Indeed, take c0c_0 large enough. Since Ak≥αεσ2/Δ~k2A_k≥ _ σ^2/ _k^2, the first term is at most 23αεσ2xc0Akx≤23c0Δ~k,2 3 _ σ^2xc_0A_kx≤ 2 3c_0\, _k, which is at most Δ~k/8 _k/8 for large enough c0c_0. Similarly, since Ak≥αεσ2/(εΔ~k)A_k≥ _ σ^2/( _k), 2αεσ2xc0Akxε≤2c0Δ~k≤Δ~k8 2 _ σ^2xc_0A_kx ≤ 2c_0 _k≤ _k8 for large enough c0c_0. This proves (6). Fix an integer T≥1T≥ 1 and suppose, toward a contradiction, that the algorithm has not stopped by the time it has made T total queries. Consider any query made to arm k before time T. Since xnx_n is nondecreasing and the local count at that query is at most T, implication (6) with x=xTx=x_T shows that if Nk≥c0AkxTN_k≥ c_0A_kx_T, then rε(Nk,δ/K)≤Δ~k4,r_ (N_k,δ/K)≤ _k4, contradicting Lemma 22. Hence every arm k can be queried only while Nk<c0AkxT.N_k<c_0A_kx_T. Summing over arms gives T=∑k=1KNk<c0Hfix(ε)xT.T= _k=1^KN_k<c_0H_ fix( )x_T. Therefore any T satisfying T≥c0Hfix(ε)xTT≥ c_0H_ fix( )x_T forces the algorithm to have stopped by time T. Now choose T=⌈CHfix(ε)[logKδ+loglogHfix(ε)]⌉T= CH_ fix( ) [ Kδ+ H_ fix( ) ] for a sufficiently large universal constant C. For this choice, xT=O(logKδ+loglogHfix(ε)),x_T=O\! ( Kδ+ H_ fix( ) ), because xTx_T contains only log(K/δ) (K/δ) and the stitched term 2log(1+⌊log2T⌋)=O(loglogT)2 (1+ _2T )=O( T), while T is proportional to Hfix(ε)H_ fix( ) times logarithmic factors. Taking C large enough gives T≥c0Hfix(ε)xTT≥ c_0H_ fix( )x_T, proving the desired bound. ∎ Proof of Theorem 8. By Lemma 19, ℰfixE_ fix holds with probability at least 1−δ1-δ. On this event, Lemma 20 proves that any returned arm is ε -optimal, and Lemma 23 proves that the stopping time is bounded by the displayed sample complexity. Proposition 32 additionally establishes termination on every realization. Hence FixedClip-1BitBAI is (ε,δ)( ,δ)-PAC and satisfies the claimed high-probability query bound. ∎ C.2 Phased adaptive clipping: proof of Theorem 10 We now analyze the restart phased algorithm. We first construct a high-probability event on which all arm–phase confidence intervals are valid simultaneously (Lemma 24). On this event, the elimination and stopping rules never discard the best arm and can only return an ε -optimal arm (Lemma 26). The sample complexity analysis then proceeds phase by phase. Lemma 27 gives the number of samples needed to certify a phase-j interval at radius rjr_j. Lemmas 28 and 29 show that each arm is sampled only down to a resolution comparable to its capped effective gap Δ¯k _k. Summing the resulting dyadic costs over phases and arms gives the claimed bound (Lemma 30). For each phase j=0,1,…,J=⌈log2(σ/ε)⌉j=0,1,…,J= _2(σ/ ) , recall ρj=2−jσ,Lj=32σ2ρj,rj=ρj16,αj=1+logLjσ=1+log32σρj. _j=2^-jσ, L_j= 32σ^2 _j, r_j= _j16, _j=1+ L_jσ=1+ 32σ _j. With γ=δ/[K(J+1)]γ=δ/[K(J+1)], the phase-j confidence radius is βj(n)=ρj64+23αjσ2xn(γ)n+32αjσ2xn(γ)ρjn. _j(n)= _j64+2 3 _jσ^2x_n(γ)n+ 32 _jσ^2x_n(γ) _jn. The restart version uses independent fresh estimators in each arm–phase pair (k,j)(k,j). Lemma 24 (Phased good event). With probability at least 1−δ1-δ, the event ℰph:=⋂k=1K⋂j=0J⋂n≥1|μ^k,j(n)−μk|≤βj(n)E_ ph:= _k=1^K _j=0^J _n≥ 1 \ | μ_k,j(n)- _k |≤ _j(n) \ holds throughout RestartPhasedClip-1BitBAI. Proof. Fix an arm–phase pair (k,j)(k,j). During phase j, the algorithm uses clipping level LjL_j for arm k. Since σ22Lj=σ22⋅32σ2/ρj=ρj64, σ^22L_j= σ^22· 32σ^2/ _j= _j64, Theorem 5 with failure probability γ gives Pr(∀n≥1,|μ^k,j(n)−μk|≤βj(n))≥1−γ. (∀ n≥ 1, | μ_k,j(n)- _k |≤ _j(n) )≥ 1-γ. There are K(J+1)K(J+1) arm–phase pairs, so the union bound gives Pr(ℰph)≥1−K(J+1)γ=1−δ. (E_ ph)≥ 1-K(J+1)γ=1-δ. Again, the confidence sequence is uniform in the local sample count n, so adaptive sampling inside the phase is allowed. ∎ Lemma 25 (The best arm is never eliminated). On ℰphE_ ph, RestartPhasedClip-1BitBAI never eliminates k⋆k . Proof. Fix a phase j and suppose k⋆k is active when the elimination rule is applied. Let A be the active set at that moment and let m:=maxi∈ALCBi,j.m:= _i∈ ALCB_i,j. On ℰphE_ ph, for every active arm i, LCBi,j≤μi≤μ⋆.LCB_i,j≤ _i≤μ . Therefore m=maxi∈ALCBi,j≤μ⋆.m= _i∈ ALCB_i,j≤μ . Also, since k⋆k is active and its interval is valid, UCBk⋆,j≥μ⋆.UCB_k ,j≥μ . Combining the two displays gives UCBk⋆,j≥μ⋆≥m>m−ε.UCB_k ,j≥μ ≥ m>m- . Thus k⋆k cannot satisfy the elimination condition UCBk,j<m−εUCB_k,j<m- . ∎ Lemma 26 (Phased stopping and final-output correctness). On ℰphE_ ph, every arm returned by RestartPhasedClip-1BitBAI is ε -optimal. Proof. There are three possible ways the algorithm returns. Singleton return. If the active set has size one, Lemma 25 implies that the unique active arm must be k⋆k , hence the output is correct. Interval stopping. Suppose the algorithm returns an arm h in phase j because, with ℓ∈argmaxa∈A∖hUCBa,j ∈ _a∈ A \h\UCB_a,j, UCBℓ,j−LCBh,j≤ε.UCB_ ,j-LCB_h,j≤ . If h=k⋆h=k , the claim is immediate. Otherwise, Lemma 25 implies that k⋆k is still active, and since k⋆≠hk ≠ h, UCBℓ,j=maxa∈A∖hUCBa,j≥UCBk⋆,j≥μ⋆.UCB_ ,j= _a∈ A \h\UCB_a,j _k ,j≥μ . Also LCBh,j≤μhLCB_h,j≤ _h, so μ⋆−μh≤UCBℓ,j−LCBh,j≤ε.μ - _h _ ,j-LCB_h,j≤ . Thus h is ε -optimal. Final-phase return. Finally, suppose the algorithm reaches the final phase J and returns h∈argmaxk∈ALCBk,Jh∈ _k∈ ALCB_k,J after all active arms satisfy βk,J≤rJ _k,J≤ r_J. By Lemma 25, k⋆k is active. Hence LCBh,J≥LCBk⋆,J.LCB_h,J _k ,J. On ℰphE_ ph and because βk⋆,J≤rJ _k ,J≤ r_J, LCBk⋆,J=μ^k⋆,J−βk⋆,J≥μ⋆−2βk⋆,J≥μ⋆−2rJ.LCB_k ,J= μ_k ,J- _k ,J≥μ -2 _k ,J≥μ -2r_J. Similarly, μh≥LCBh,J _h _h,J. Therefore μh≥LCBh,J≥LCBk⋆,J≥μ⋆−2rJ. _h _h,J _k ,J≥μ -2r_J. Since rJ=ρJ/16r_J= _J/16 and ρJ≤ε _J≤ , we have 2rJ≤ε/8≤ε2r_J≤ /8≤ . Thus μh≥μ⋆−ε _h≥μ - . ∎ Lemma 27 (Per-phase sample requirement). For each phase j, define Γj:=logK(J+1)δ+loglog(eσρj)+loglog(eK(J+1)δ). _j:= K(J+1)δ+ (e^e σ _j )+ (e^e K(J+1)δ ). There exists a universal constant C>0C>0 such that nj∘:=⌈Cαjσ2ρj2Γj⌉n_j := C _jσ^2 _j^2 _j satisfies βj(nj∘)≤rj=ρj16. _j(n_j )≤ r_j= _j16. Consequently, in phase j, an active arm is queried at most nj∘n_j times before its phase-j radius is at most rjr_j. Proof. Recall βj(n)=ρj64+23αjσ2xn(γ)n+32αjσ2xn(γ)ρjn. _j(n)= _j64+2 3 _jσ^2x_n(γ)n+ 32 _jσ^2x_n(γ) _jn. The bias term is already ρj/64 _j/64. It remains to make each of the two stochastic terms at most ρj/64 _j/64. First we bound the stitched logarithm at nj∘n_j . Since xn(γ)=log(π2(1+⌊log2n⌋)23γ),x_n(γ)= ( π^2(1+ _2n )^23γ ), there is a universal constant c1>0c_1>0 such that for all n≥2n≥ 2, xn(γ)≤c1+log1γ+2loglog(en).x_n(γ)≤ c_1+ 1γ+2 (e^en). Here γ=δ/[K(J+1)]γ=δ/[K(J+1)], so log1γ=logK(J+1)δ. 1γ= K(J+1)δ. Moreover, nj∘≤C1αjσ2ρj2Γjn_j ≤ C_1 _jσ^2 _j^2 _j for a universal constant C1C_1 depending only on C, and αj=1+log32σρj≤C2log(eσρj). _j=1+ 32σ _j≤ C_2 (e^e σ _j ). Therefore loglog(enj∘)≤C3+loglog(eσρj)+loglog(eK(J+1)δ), (e^en_j )≤ C_3+ (e^e σ _j )+ (e^e K(J+1)δ ), where the last term absorbs the dependence on Γj _j. Hence, for a universal constant C0>0C_0>0, xnj∘(γ)≤C0Γj.x_n_j (γ)≤ C_0 _j. (7) Now choose the constant C in the definition of nj∘n_j large enough so that 23αjσ2C0Γjnj∘≤ρj642 3 _jσ^2C_0 _jn_j ≤ _j64 and 32αjσ2C0Γjρjnj∘≤ρj64. 32 _jσ^2C_0 _j _jn_j ≤ _j64. Using (7), both stochastic terms in βj(nj∘) _j(n_j ) are at most ρj/64 _j/64. Thus βj(nj∘)≤ρj64+ρj64+ρj64=3ρj64<ρj16=rj. _j(n_j )≤ _j64+ _j64+ _j64= 3 _j64< _j16=r_j. In the algorithm, once an arm has βk,j≤rj _k,j≤ r_j, it is not queried again in that phase unless all active arms already satisfy the same condition, in which case the phase ends. Therefore an arm receives at most nj∘n_j phase-j samples. ∎ Lemma 28 (Elimination at the right scale). Assume ℰphE_ ph holds. Fix a phase j. If a suboptimal active arm k≠k⋆k≠ k satisfies Δk>ε+ρj4, _k> + _j4, then by the time phase j ends, either the algorithm has already stopped or arm k has been eliminated. Proof. If the algorithm stops during phase j, there is nothing to prove. Otherwise, phase j ends only after every active arm has phase radius at most rj=ρj/16r_j= _j/16, and the elimination rule has been applied. Let A be the active set at that point and define m:=maxi∈ALCBi,j.m:= _i∈ ALCB_i,j. By Lemma 25, k⋆∈Ak ∈ A. Hence, on ℰphE_ ph, m≥LCBk⋆,j≥μ⋆−2rj.m _k ,j≥μ -2r_j. For the suboptimal arm k, UCBk,j≤μk+2rj=μ⋆−Δk+2rj.UCB_k,j≤ _k+2r_j=μ - _k+2r_j. If Δk>ε+4rj _k> +4r_j, then μ⋆−Δk+2rj<μ⋆−ε−2rj.μ - _k+2r_j<μ - -2r_j. Since 4rj=ρj/44r_j= _j/4, the condition Δk>ε+ρj/4 _k> + _j/4 is exactly Δk>ε+4rj _k> +4r_j. Combining the preceding displays, UCBk,j<μ⋆−ε−2rj≤m−ε.UCB_k,j<μ - -2r_j≤ m- . Thus k satisfies the elimination rule UCBk,j<m−εUCB_k,j<m- and is eliminated. ∎ Lemma 29 (Last relevant phase). Assume ℰphE_ ph holds. For every arm k, the resolution of the last phase in which k is sampled is bounded below by a universal constant multiple of Δ¯k:=minmaxΔk,ε,σ. _k:= \ \ _k, \,σ\. More precisely, there exists a universal constant c>0c>0 such that if ρ is the resolution of the last phase in which k is sampled, then ρ≥cΔ¯k.ρ≥ c\, _k. Proof. We first consider a suboptimal arm k≠k⋆k≠ k . Case 1: Δk≥2ε _k≥ 2 and Δk≤σ _k≤σ. Then Δ¯k=Δk _k= _k. Let jkj_k be the first phase index such that ρjk≤Δk _j_k≤ _k. By dyadicity, Δk2<ρjk≤Δk. _k2< _j_k≤ _k. Since Δk≥2ε _k≥ 2 , we have ε≤Δk/2 ≤ _k/2. Therefore ε+ρjk4≤Δk2+Δk4=3Δk4<Δk. + _j_k4≤ _k2+ _k4= 3 _k4< _k. Lemma 28 implies that arm k is eliminated by the end of phase jkj_k, unless the algorithm has already stopped. Thus k is not sampled beyond phase jkj_k, so its last sampled resolution is at least ρjk>Δ¯k/2 _j_k> _k/2. Case 2: Δk≥2ε _k≥ 2 and Δk>σ _k>σ. Then Δ¯k=σ _k=σ. At phase 00, ρ0=σ _0=σ. Since ε≤Δk/2 ≤ _k/2 and ρ0/4=σ/4<Δk/4 _0/4=σ/4< _k/4, ε+ρ04<Δk2+Δk4=3Δk4<Δk. + _04< _k2+ _k4= 3 _k4< _k. Thus Lemma 28 eliminates arm k by the end of phase 00, unless the algorithm stops. If k is sampled, its last sampled resolution is therefore σ=Δ¯kσ= _k. Case 3: Δk<2ε _k<2 . Then Δ¯k≤2ε _k≤ 2 . Also J=⌈log2(σ/ε)⌉J= _2(σ/ ) , so ρJ≤ε<2ρJ. _J≤ <2 _J. No arm is sampled after phase J. Hence the last sampled resolution satisfies ρ≥ρJ>ε/2≥Δ¯k/4ρ≥ _J> /2≥ _k/4. Now consider the optimal arm k⋆k , with Δk⋆=minj≠k⋆Δj _k = _j≠ k _j. If Δk⋆≥2ε _k ≥ 2 and Δk⋆≤σ _k ≤σ, let j⋆j_ be the first phase with ρj⋆≤Δk⋆ _j_ ≤ _k . The same calculation as in Case 1 shows that every suboptimal arm a satisfies Δa≥Δk⋆>ε+ρj⋆4, _a≥ _k > + _j_ 4, so all suboptimal arms are eliminated by the end of phase j⋆j_ , unless the algorithm has already stopped. The active set then becomes singleton and the algorithm returns, so k⋆k is not sampled beyond this phase and its last sampled resolution exceeds Δ¯k⋆/2 _k /2. If Δk⋆≥2ε _k ≥ 2 and Δk⋆>σ _k >σ, the same argument applies at phase 00, giving last sampled resolution σ=Δ¯k⋆σ= _k . If Δk⋆<2ε _k <2 , the final-phase argument in Case 3 gives last sampled resolution greater than Δ¯k⋆/4 _k /4. This proves the claim with c=1/4c=1/4. Early stopping can only increase the last sampled resolution, so no upper bound on it is needed or asserted. ∎ Lemma 30 (Phased counting bound). On ℰphE_ ph, RestartPhasedClip-1BitBAI uses at most O(∑k=1KΛ(Δ¯k)σ2Δ¯k2Γ(Δ¯k,K,J,δ))O\! ( _k=1^K ( _k) σ^2 _k^2 ( _k;K,J,δ) ) 1-bit queries, where Λ(u)=1+logσu (u)=1+ σu and Γ(u,K,J,δ)=logK(J+1)δ+loglog(eσu)+loglog(eK(J+1)δ). (u;K,J,δ)= K(J+1)δ+ (e^e σu )+ (e^e K(J+1)δ ). Proof. By Lemma 27, in phase j each active arm receives at most nj∘=O(αjσ2ρj2Γj)n_j =O\! ( _jσ^2 _j^2 _j ) queries. By Lemma 29, arm k is sampled only in phases whose resolution is at least a universal constant multiple of Δ¯k _k. Thus the total number of samples of arm k is bounded by ∑j:ρj≳Δ¯kO(αjσ2ρj2Γj). _j:\, _j _kO\! ( _jσ^2 _j^2 _j ). Let jkj_k be the last phase in this sum. Since ρj _j decreases geometrically, ∑j=0jk1ρj2=1σ2∑j=0jk4j≤431ρjk2. _j=0^j_k 1 _j^2= 1σ^2 _j=0^j_k4^j≤ 43 1 _j_k^2. Moreover, both αj _j and Γj _j are nondecreasing as ρj _j decreases, so for j≤jkj≤ j_k, αj≤αjk,Γj≤Γjk. _j≤ _j_k, _j≤ _j_k. Therefore the contribution of arm k is at most a constant times αjkσ2ρjk2Γjk. _j_k σ^2 _j_k^2 _j_k. The largest scheduled index jkj_k satisfying ρjk≳Δ¯k _j_k _k has ρjk=Θ(Δ¯k) _j_k= ( _k) by dyadicity and the final-scale cap. This index bounds the cost even if the actual last sampled phase is earlier. Hence αjk=1+log32σρjk=O(1+logσΔ¯k)=O(Λ(Δ¯k)), _j_k=1+ 32σ _j_k=O\! (1+ σ _k )=O( ( _k)), σ2ρjk2=O(σ2Δ¯k2), σ^2 _j_k^2=O\! ( σ^2 _k^2 ), and Γjk=O(Γ(Δ¯k,K,J,δ)). _j_k=O\! ( ( _k;K,J,δ) ). Thus arm k contributes at most O(Λ(Δ¯k)σ2Δ¯k2Γ(Δ¯k,K,J,δ)).O\! ( ( _k) σ^2 _k^2 ( _k;K,J,δ) ). Summing this bound over k=1,…,Kk=1,…,K proves the lemma. ∎ Proof of Theorem 10. By Lemma 24, ℰphE_ ph holds with probability at least 1−δ1-δ. On this event, Lemma 26 proves that every possible return is ε -optimal. Lemma 30 gives the stated high-probability query bound. Proposition 33 establishes termination on every realization. Hence RestartPhasedClip-1BitBAI is (ε,δ)( ,δ)-PAC and satisfies the claimed sample complexity. The displayed main-text bound follows because Δ¯k≥ε _k≥ , J+1=O(1+log(σ/ε))J+1=O(1+ (σ/ )), and the remaining iterated logarithms in Γ are absorbed into log(K/δ)+loglog(eσ/ε) (K/δ)+ (e^eσ/ ). ∎ Lemma 31 (Reusable phased clipping has the same order). Consider the phased algorithm with the same active-arm, stopping, and elimination rules as RestartPhasedClip-1BitBAI, but replace the restarted phase-j estimator by the following reusable slab estimator. Let L−1:=0L_-1:=0, let I0:=[0,L0],Is:=(Ls−1,Ls](s≥1),I_0:=[0,L_0], I_s:=(L_s-1,L_s] (s≥ 1), and define As:=∫Isdtmaxσ,t,qs(t):=1Asmaxσ,t,t∈Is.A_s:= _I_s dt \σ,t\, q_s(t):= 1A_s \σ,t\, t∈ I_s. For each arm k and slab s, draw S∼Unif−1,+1S Unif\-1,+1\, T∼qsT q_s, query Y=S(Xk−ck)≥T,Y=1\S(X_k-c_k)≥ T\, and define Zk,s:=2Sqs(T)Y.Z_k,s:= 2Sq_s(T)Y. In phase j, form μ^k,jreuse:=ck+∑s=0jZ¯k,s, μ reuse_k,j:=c_k+ _s=0^j Z_k,s, where Z¯k,s Z_k,s is the empirical average of the retained samples from slab s. For Γj:=logK(J+1)δ+loglog(eσρj)+loglog(eK(J+1)δ), _j:= K(J+1)δ+ (e^e σ _j )+ (e^e K(J+1)δ ), there is a universal constant C0>0C_0>0 such that it is enough to top up each slab s≤js≤ j to ms,j:=⌈C0Asσ2ρj2Γj⌉m_s,j:= C_0\, A_sσ^2 _j^2 _j samples in order to guarantee the phase-j radius rj=ρj/16r_j= _j/16. Consequently, on an event of probability at least 1−δ1-δ, the reusable phased algorithm uses at most O(∑k=1KΛ(Δ¯k)σ2Δ¯k2Γ(Δ¯k,K,J,δ))O\! ( _k=1^K ( _k) σ^2 _k^2 ( _k;K,J,δ) ) 1-bit queries, where Λ(u)=1+logσu (u)=1+ σu and Γ(u,K,J,δ)=logK(J+1)δ+loglog(eσu)+loglog(eK(J+1)δ). (u;K,J,δ)= K(J+1)δ+ (e^e σu )+ (e^e K(J+1)δ ). Thus reuse preserves the order of Theorem 10. Proof. Fix an arm k, and write Wk=Xk−ckW_k=X_k-c_k. First note that qsq_s is a density on IsI_s, and ∑s=0jAs=∫0Ljdtmaxσ,t=1+logLjσ=αj. _s=0^jA_s= _0^L_j dt \σ,t\=1+ L_jσ= _j. Moreover, by the same tail-integral calculation used in Lemma 2, [Zk,s]=∫Is(Pr(Wk≥t)−Pr(Wk≤−t))t.E[Z_k,s]= _I_s ( (W_k≥ t)- (W_k≤-t) )dt. Therefore ∑s=0j[Zk,s]=[[Wk]Lj], _s=0^jE[Z_k,s]=E[[W_k]_L_j], so the reusable phase-j estimator is unbiased for the clipped target ck+[[Wk]Lj]c_k+E[[W_k]_L_j]. We next establish the variance and range bounds needed for Bernstein’s inequality. Conditional on Wk=wW_k=w, [Zk,s2∣Wk=w]=2As∫Ismaxσ,t|w|≥tdt.E[Z_k,s^2 W_k=w]=2A_s _I_s \σ,t\1\|w|≥ t\\,dt. Hence, writing vk,s:=Var(Zk,s)v_k,s:=Var(Z_k,s), we have ∑s=0jvk,sAs≤∑s=0j[Zk,s2]As≤2[∫0Ljmaxσ,t|Wk|≥tdt]. _s=0^j v_k,sA_s≤ _s=0^j E[Z_k,s^2]A_s≤ 2E\! [ _0^L_j \σ,t\1\|W_k|≥ t\\,dt ]. For any x≥0x≥ 0, ∫0Ljmaxσ,tx≥tdt≤∫0xmaxσ,tdt≤σx+x22. _0^L_j \σ,t\1\x≥ t\\,dt≤ _0^x \σ,t\\,dt≤σ x+ x^22. Since [Wk2]≤2σ2E[W_k^2]≤ 2σ^2, this gives ∑s=0jvk,sAs≤Cσ2 _s=0^j v_k,sA_s≤ Cσ^2 for a universal constant C>0C>0. Also, |Zk,s|≤2qs(T)=2Asmaxσ,T≤2AsLs.|Z_k,s|≤ 2q_s(T)=2A_s \σ,T\≤ 2A_sL_s. Because As≥log2A_s≥ 2 for every s, the centered variables satisfy |Zk,s−Zk,s|≤CAsLs|Z_k,s-EZ_k,s|≤ CA_sL_s for another universal constant C>0C>0. Now fix a phase j. Suppose each slab s≤js≤ j has been topped up to ms,jm_s,j samples. Define Z¯k,s=1ms,j∑i=1ms,jZk,s,i. Z_k,s= 1m_s,j _i=1^m_s,jZ_k,s,i. The centered error of the reusable clipped estimator is ∑s=0j(Z¯k,s−Zk,s). _s=0^j ( Z_k,s-EZ_k,s ). Its Bernstein variance proxy is Vk,j:=∑s=0jvk,sms,j,V_k,j:= _s=0^j v_k,sm_s,j, and its maximum summand range is Bk,j:=maxs≤jCAsLsms,j.B_k,j:= _s≤ j CA_sL_sm_s,j. By the choice of ms,jm_s,j, Vk,j≤ρj2C0σ2Γj∑s=0jvk,sAs≤Cρj2C0Γj,V_k,j≤ _j^2C_0σ^2 _j _s=0^j v_k,sA_s≤ C _j^2C_0 _j, and Bk,j≤maxs≤jCAsLsC0Asσ2Γj/ρj2≤CLjρj2C0σ2Γj=32CρjC0Γj,B_k,j≤ _s≤ j CA_sL_sC_0A_sσ^2 _j/ _j^2≤ CL_j _j^2C_0σ^2 _j= 32C _jC_0 _j, where the last equality uses Lj=32σ2/ρjL_j=32σ^2/ _j. Bernstein’s inequality therefore gives, for a universal constant c>0c>0, Pr(|∑s=0j(Z¯k,s−Zk,s)|>2Vk,jΓj+Bk,jΓj)≤e−cΓj. ( | _s=0^j ( Z_k,s-EZ_k,s ) |>2 V_k,j _j+B_k,j _j )≤ e^-c _j. Since Γj≥log(K(J+1)/δ) _j≥ (K(J+1)/δ), a union bound over all K(J+1)K(J+1) arm–phase pairs shows that, with probability at least 1−δ1-δ, the above Bernstein bound holds simultaneously for every k and j. Taking C0C_0 sufficiently large yields 2Vk,jΓj+Bk,jΓj≤3ρj64.2 V_k,j _j+B_k,j _j≤ 3 _j64. The clipping bias at level LjL_j is |[Wk]−[[Wk]Lj]|≤σ22Lj=ρj64. |E[W_k]-E[[W_k]_L_j] |≤ σ^22L_j= _j64. Consequently, on the simultaneous event, |μ^k,jreuse−μk|≤3ρj64+ρj64=ρj16=rj | μ reuse_k,j- _k |≤ 3 _j64+ _j64= _j16=r_j whenever all slabs s≤js≤ j have been topped up to ms,jm_s,j. Thus the reusable estimator certifies the same phase-j radius as the restarted estimator. It remains to count samples. For a fixed arm k, let jkj_k be the last phase in which k is sampled by the reusable algorithm. Since samples are retained, the total number of slab samples collected for arm k is bounded by the final top-up target at phase jkj_k, namely ∑s=0jkms,jk=O(σ2ρjk2Γjk∑s=0jkAs)=O(αjkσ2ρjk2Γjk). _s=0^j_km_s,j_k=O\! ( σ^2 _j_k^2 _j_k _s=0^j_kA_s )=O\! ( _j_kσ^2 _j_k^2 _j_k ). On the same valid-interval event, the stopping and elimination arguments from Lemmas 25–29 apply verbatim, since they only use validity of the confidence intervals and the fact that each completed phase reaches radius rjr_j. Hence Lemma 29 gives ρjk≥cΔ¯k. _j_k≥ c\, _k. Therefore αjk=1+log32σρjk=O(1+logσΔ¯k)=O(Λ(Δ¯k)), _j_k=1+ 32σ _j_k=O\! (1+ σ _k )=O( ( _k)), σ2ρjk2=O(σ2Δ¯k2), σ^2 _j_k^2=O\! ( σ^2 _k^2 ), and Γjk=O(Γ(Δ¯k,K,J,δ)). _j_k=O\! ( ( _k;K,J,δ) ). Thus arm k contributes at most O(Λ(Δ¯k)σ2Δ¯k2Γ(Δ¯k,K,J,δ))O\! ( ( _k) σ^2 _k^2 ( _k;K,J,δ) ) queries. Summing over k=1,…,Kk=1,…,K proves the claimed bound. ∎ C.3 Deterministic finite query bounds The high-probability bounds above quantify gap-dependent behavior. For positive accuracy, both algorithms also have finite gap-independent query caps on every realization. These bounds establish termination without conditioning on confidence validity. We assume supplied anchors and 0<ε≤σ0< ≤σ; for larger accuracy one may run the algorithms with target σ. C.3.1 Fixed clipping Proposition 32 (Pathwise fixed-clipping cap). Let Aε=αεσ2/ε2A_ = _ σ^2/ ^2, and let mεm_ be the smallest nonnegative integer satisfying 2mε≥768Aεlog(π2K(mε+1)23δ).2^m_ ≥ 768A_ ( π^2K(m_ +1)^23δ ). Set nfix∘=2mεn_ fix =2^m_ . Then on every realization, τfix≤Knfix∘=O(KAε[logKδ+loglog(eAε)]). _ fix≤ Kn_ fix =O\! (KA_ [ Kδ+ (e^eA_ ) ] ). Proof. In any non-stopping round, if k∈h,ℓk∈\h, \ is sampled, the interval geometry alone gives Bh≤2βkB_h≤ 2 _k. To see this for k=ℓk= , the sampling rule implies βℓ≥βh _ ≥ _h. If LCBℓ>LCBhLCB_ >LCB_h, then UCBℓ>UCBhUCB_ >UCB_h and Bℓ<BhB_ <B_h, contradicting the minimality of h. Hence Bh=UCBℓ−LCBh≤2βℓB_h=UCB_ -LCB_h≤ 2 _ . For k=hk=h, the sampling rule implies βh≥βℓ _h≥ _ . If UCBℓ>UCBhUCB_ >UCB_h, then LCBℓ>LCBhLCB_ >LCB_h and again Bℓ<BhB_ <B_h, a contradiction. Thus Bh≤2βhB_h≤ 2 _h. Neither argument uses interval validity. Consequently, every sampled arm has βε(Nk,δ/K)>ε/2 _ (N_k,δ/K)> /2. At the deterministic count nfix∘n_ fix , its stitched logarithm is exactly the logarithm in the proposition, and 23αεσ2xnfix∘(δ/K)nfix∘≤ε8,2αεσ2xnfix∘(δ/K)nfix∘ε≤ε384.2 3 _ σ^2x_n_ fix (δ/K)n_ fix ≤ 8, 2 _ σ^2x_n_ fix (δ/K)n_ fix ≤ 384. Including the bias ε/4 /4 gives a radius strictly below ε/2 /2. Once an arm reaches this count it cannot be sampled again, since its unchanged estimate and local count retain the same radius. Including the initialization query, each arm receives at most nfix∘n_ fix queries, proving the cap. Exponential growth of 2m2^m versus the logarithm ensures mε<∞m_ <∞. The same inversion as in Appendix B.5, with rounding to a power of two, gives the stated order. ∎ C.3.2 Restart phased clipping Proposition 33 (Pathwise phased cap). With nj∘n_j and Γj _j from Lemma 27, on every realization, τph≤K∑j=0Jnj∘=O(K(1+logσε)σ2ε2ΓJ). _ ph≤ K _j=0^Jn_j =O\! (K (1+ σ ) σ^2 ^2 _J ). Proof. Lemma 27 gives βj(nj∘)≤rj _j(n_j )≤ r_j deterministically. The sampling rule selects only an arm with radius greater than rjr_j: it samples the larger-radius candidate or challenger when possible, and otherwise an active arm of maximum radius. An arm reaching nj∘n_j is therefore never sampled again in that phase. Once all active radii are at most rjr_j, the algorithm returns or advances to the next phase. The active set cannot become empty, since an arm maximizing the LCB has UCB at least that LCB and survives elimination, even for invalid intervals. There are J+1J+1 phases, so their caps sum to at most K∑jnj∘K _jn_j . Finally, ρJ∈(ε/2,ε] _J∈( /2, ], αj _j and Γj _j are nondecreasing, and ∑j=0J4j≤(4/3)4J _j=0^J4^j≤(4/3)4^J. These facts yield the displayed order. ∎ Combining either pathwise cap with its simultaneous confidence event proves almost-sure termination and (ε,δ)( ,δ)-PAC correctness. The caps are gap-independent; the high-probability theorems give sharper instance-dependent guarantees. C.4 Lau–Scarlett estimators with phased successive elimination We record a batched alternative to make the scope of our rate claim explicit. Use ρj=2−jσ _j=2^-jσ, J=⌈log2(σ/ε)⌉J= _2(σ/ ) , and γ=δ/[K(J+1)]γ=δ/[K(J+1)]. In phase j, invoke the finite-variance fixed-target estimator of Lau and Scarlett [20] separately on each active arm with accuracy ρj/8 _j/8 and failure probability γ, using the supplied anchor. Retain arms whose estimates are within ρj/2 _j/2 of the largest completed estimate. Return a singleton immediately, or any survivor at phase J. A union bound gives simultaneous accuracy of all completed arm–phase estimates with probability at least 1−δ1-δ. On this event, the estimated maximum exceeds the best arm’s estimate by at most ρj/4 _j/4, so the best arm survives. A suboptimal arm with Δk>3ρj/4 _k>3 _j/4 has estimated deficit greater than ρj/2 _j/2 and is removed. Conversely every survivor has Δk≤3ρj/4 _k≤ 3 _j/4, so a final-phase survivor is ε -optimal. The deterministic cost per active arm in phase j is mj=O(σ2ρj2(1+logσρj)logK(J+1)δ).m_j=O\! ( σ^2 _j^2 (1+ σ _j ) K(J+1)δ ). An arm is not sampled at resolutions finer than a constant multiple of Δ¯k _k on the simultaneous event; for the best arm, all challengers are removed by the corresponding scale. Summing geometrically increasing phase costs gives O(∑k=1Kσ2Δ¯k2(1+logσΔ¯k)logK(J+1)δ)=O(Hgap[logKδ+loglog(eσε)]).O\! ( _k=1^K σ^2 _k^2 (1+ σ _k ) K(J+1)δ )=O\! (H_ gap [ Kδ+ (e^e σ ) ] ). Thus this wrapper matches the leading phased BAI rate. It gives simultaneous confidence at completed checkpoints, while Theorem 5 also provides valid intervals after every intermediate local sample. Appendix D Proofs for Section 4 (Lower bound) The proof of Theorem 12 establishes an information-theoretic limit by explicitly constructing a “hard pair” of distributions (ν0,ν1)( _0, _1). These distributions are carefully engineered to have a mean gap of exactly Δ , yet they are geometrically structured so that any single 1-bit measurable set query yields at most O(Δ2/(Jσ2))O( ^2/(Jσ^2)) KL information. We then use opposite perturbations to embed this construction into a K-arm base instance and alternatives changing one arm at a time, and apply a change-of-measure argument over the predictable σ-algebra of the algorithm’s interaction sequence. D.1 Construction of the hard pair Let J be the largest integer such that 2J−1≤σ2Δ.2^J-1≤ σ2 . This definition implies σ4Δ<2J−1≤σ2Δ σ4 <2^J-1≤ σ2 , so taking the base-2 logarithm yields J=⌊log2(σΔ)⌋J= _2( σ ) . Consequently, the number of scales is J=Θ(logσΔ)J= ( σ ). For each index i=1,…,Ji=1,…,J, we define the geometric support scales mim_i and their corresponding base probability weights wiw_i: mi:=2i−1,wi:=1Jmi2.m_i:=2^i-1, w_i:= 1Jm_i^2. To create the mean shift, we introduce the probability mass perturbations ξi:=Δ2Jmiσ. _i:= 2Jm_iσ. To ensure that we can subtract these perturbations without producing negative probabilities, we verify that ξi≤wi/4 _i≤ w_i/4. By definition, ξi≤wi4⇔Δ2Jmiσ≤14Jmi2⇔mi≤σ2Δ. _i≤ w_i4 2Jm_iσ≤ 14Jm_i^2 m_i≤ σ2 . Since mi=2i−1≤2J−1≤σ2Δm_i=2^i-1≤ 2^J-1≤ σ2 for all i≤Ji≤ J, the condition holds. We now define the baseline distribution ν0 _0 and the perturbed distribution ν1 _1 over the finite support 0∪±miσi=1J\0\∪\± m_iσ\_i=1^J: ν0 _0 =(1−∑i=1Jwi)δ0+∑i=1Jwi2δmiσ+∑i=1Jwi2δ−miσ, = (1- _i=1^Jw_i ) _0+ _i=1^J w_i2 _m_iσ+ _i=1^J w_i2 _-m_iσ, ν1 _1 =(1−∑i=1Jwi)δ0+∑i=1J(wi2+ξi)δmiσ+∑i=1J(wi2−ξi)δ−miσ, = (1- _i=1^Jw_i ) _0+ _i=1^J ( w_i2+ _i ) _m_iσ+ _i=1^J ( w_i2- _i ) _-m_iσ, where δx _x denotes the Dirac measure at x. Note that the central mass at 00 is strictly positive because ∑i=1Jwi=1J∑i=1J4−(i−1)<1J43≤1 _i=1^Jw_i= 1J _i=1^J4^-(i-1)< 1J 43≤ 1 for J≥2J≥ 2. Lemma 34 (Moments of the hard pair). The distributions ν0 _0 and ν1 _1 satisfy ν0[X]=0,ν1[X]=Δ,E_ _0[X]=0, _ _1[X]= , and have variances bounded by σ2σ^2. Proof. For ν0 _0, symmetry across the origin immediately yields ν0[X]=0E_ _0[X]=0. Its second moment expands to exactly the variance proxy: ν0[X2]=∑i=1Jwi(miσ)2=∑i=1J(1Jmi2)mi2σ2=∑i=1Jσ2J=σ2.E_ _0[X^2]= _i=1^Jw_i(m_iσ)^2= _i=1^J ( 1Jm_i^2 )m_i^2σ^2= _i=1^J σ^2J=σ^2. For ν1 _1, the perturbations ξi _i are explicitly designed to shift the mean. Because the support points are symmetric, the base weights wi/2w_i/2 cancel, leaving only the perturbations: ν1[X]=∑i=1J[(wi2+ξi)(miσ)+(wi2−ξi)(−miσ)]=∑i=1J2ξimiσ.E_ _1[X]= _i=1^J [ ( w_i2+ _i )(m_iσ)+ ( w_i2- _i )(-m_iσ) ]= _i=1^J2 _im_iσ. Substituting ξi=Δ2Jmiσ _i= 2Jm_iσ, we obtain ν1[X]=∑i=1JΔJ=ΔE_ _1[X]= _i=1^J J= . The second moment of ν1 _1 remains unchanged because the ξi _i perturbations are added and subtracted at squared symmetric points: ν1[X2]=∑i=1J[(wi2+ξi)(miσ)2+(wi2−ξi)(−miσ)2]=∑i=1Jwimi2σ2=σ2.E_ _1[X^2]= _i=1^J [ ( w_i2+ _i )(m_iσ)^2+ ( w_i2- _i )(-m_iσ)^2 ]= _i=1^Jw_im_i^2σ^2=σ^2. Thus, Varν1(X)=ν1[X2]−(ν1[X])2=σ2−Δ2≤σ2Var_ _1(X)=E_ _1[X^2]-(E_ _1[X])^2=σ^2- ^2≤σ^2. ∎ For the K-arm embedding, write P0:=ν0P_0:= _0 and P+:=ν1P_+:= _1, and define P−P_- by reversing the signs of the perturbations: P−:=(1−∑i=1Jwi)δ0+∑i=1J(wi2−ξi)δmiσ+∑i=1J(wi2+ξi)δ−miσ.P_-:= (1- _i=1^Jw_i ) _0+ _i=1^J ( w_i2- _i ) _m_iσ+ _i=1^J ( w_i2+ _i ) _-m_iσ. By reflection, P−[X]=−ΔE_P_-[X]=- and VarP−(X)=σ2−Δ2≤σ2Var_P_-(X)=σ^2- ^2≤σ^2. All three distributions admit the same valid anchor c=0c=0, since their means have absolute value at most Δ≤σ ≤σ. D.2 A uniform one-query KL bound Consider an arbitrary measurable query set A⊆ℝA . A 1-bit observation Y=X∈AY=1\X∈ A\ follows a Bernoulli distribution: Ber(p)Ber(p) under ν0 _0 and Ber(q)Ber(q) under ν1 _1, where p:=ν0(A)p:= _0(A) and q:=ν1(A)q:= _1(A). We categorize the scales based on how they intersect with A. Let S(A)S(A) denote the set of index scales i∈1,…,Ji∈\1,…,J\ where exactly one of the two support points ±miσ\± m_iσ\ belongs to A. Lemma 35 (One-query probability difference bound). For every measurable set A⊆ℝA , (q−p)2≤2Δ2Jσ2p.(q-p)^2≤ 2 ^2Jσ^2p. Proof. We analyze the mass difference q−pq-p. For any scale i∉S(A)i∉ S(A), either both ±miσ∈A± m_iσ∈ A or neither are in A. If both are in A, the mass difference contributed by scale i is (wi2+ξi)+(wi2−ξi)−wi=0.( w_i2+ _i)+( w_i2- _i)-w_i=0. If neither are, the contribution is naturally 00. The origin 00 also contributes equal mass to both distributions. Thus, only scales in S(A)S(A) cause a discrepancy. For i∈S(A)i∈ S(A), the difference is either +ξi+ _i (if miσ∈Am_iσ∈ A) or −ξi- _i (if −miσ∈A-m_iσ∈ A). We can write q−p=∑i∈S(A)siξiq-p= _i∈ S(A)s_i _i for some signs si∈−1,1s_i∈\-1,1\. By the triangle inequality: |q−p|≤∑i∈S(A)ξi=Δ2Jσ∑i∈S(A)1mi.|q-p|≤ _i∈ S(A) _i= 2Jσ _i∈ S(A) 1m_i. If S(A)S(A) is empty, then q−p=0q-p=0 and the claimed bound is immediate. Otherwise, let S(A)=i1<i2<⋯<irS(A)=\i_1<i_2<…<i_r\ be ordered such that i1i_1 is the smallest index. Because mim_i grows geometrically as 2i−12^i-1, the sum is dominated by its largest term: ∑k=1r1mik≤∑k=0r−11mi12k<2mi1. _k=1^r 1m_i_k≤ _k=0^r-1 1m_i_12^k< 2m_i_1. Squaring this strict bound gives: (∑i∈S(A)1mi)2<4mi12. ( _i∈ S(A) 1m_i )^2< 4m_i_1^2. Because i1i_1 is an element of S(A)S(A), we have 4mi12≤4∑i∈S(A)1mi2 4m_i_1^2≤ 4 _i∈ S(A) 1m_i^2. Simultaneously, we bound the baseline probability p. For every i∈S(A)i∈ S(A), exactly one support point is in A, contributing wi/2w_i/2 to ν0(A) _0(A). Therefore, p≥∑i∈S(A)wi2=12J∑i∈S(A)1mi2⟹∑i∈S(A)1mi2≤2Jp.p≥ _i∈ S(A) w_i2= 12J _i∈ S(A) 1m_i^2 _i∈ S(A) 1m_i^2≤ 2Jp. Combining these inequalities gives the desired result: (q−p)2≤Δ24J2σ2(4∑i∈S(A)1mi2)≤Δ2J2σ2(2Jp)=2Δ2Jσ2p.(q-p)^2≤ ^24J^2σ^2 (4 _i∈ S(A) 1m_i^2 )≤ ^2J^2σ^2(2Jp)= 2 ^2Jσ^2p. ∎ Lemma 36 (Uniform KL divergence bound). There exists an absolute constant C0>0C_0>0 such that for every measurable set A⊆ℝA , maxkl(q,p),kl(p,q)≤C0Δ2Jσ2, \kl(q,p),kl(p,q)\≤ C_0 ^2Jσ^2, where kl(u,v)=uloguv+(1−u)log1−u1−vkl(u,v)=u uv+(1-u) 1-u1-v denotes the binary KL divergence. Moreover, writing p±:=P±(A)p_±:=P_±(A), the opposite perturbations satisfy maxkl(p−,p+),kl(p+,p−)≤4C0Δ2Jσ2. \kl(p_-,p_+),kl(p_+,p_-)\≤ 4C_0 ^2Jσ^2. Proof. If p=0p=0 or p=1p=1, the perturbed laws assign the same probability to A, so all divergences vanish. Otherwise, we first establish that the likelihood ratio is bounded, specifically that qp∈[12,32]. qp∈ [ 12, 32 ]. Using the structural properties of our construction, we bounded ξi≤wi/4 _i≤ w_i/4. Therefore: |q−p|≤∑i∈S(A)ξi≤14∑i∈S(A)wi=12∑i∈S(A)wi2≤12p.|q-p|≤ _i∈ S(A) _i≤ 14 _i∈ S(A)w_i= 12 _i∈ S(A) w_i2≤ 12p. This implies −12p≤q−p≤12p- 12p≤ q-p≤ 12p, which rearranges exactly to 12p≤q≤32p 12p≤ q≤ 32p. By complement invariance of binary KL divergence, kl(q,p)=kl(1−q,1−p)kl(q,p)=kl(1-q,1-p). We may assume without loss of generality that p≤1/2p≤ 1/2 (if not, we simply replace A with its complement AcA^c, noting that S(A)=S(Ac)S(A)=S(A^c)). Using the standard inequality kl(u,v)≤(u−v)2v(1−v)kl(u,v)≤ (u-v)^2v(1-v) and Lemma 35, we obtain: kl(q,p)≤(q−p)2p(1−p)≤(q−p)2p(1/2)=2(q−p)2p≤4Δ2Jσ2.kl(q,p)≤ (q-p)^2p(1-p)≤ (q-p)^2p(1/2)=2 (q-p)^2p≤ 4 ^2Jσ^2. To bound the reverse direction kl(p,q)kl(p,q), we require q(1−q)q(1-q) in the denominator. Since p≤1/2p≤ 1/2, our likelihood bounds give q≤3/4q≤ 3/4, meaning 1−q≥1/41-q≥ 1/4. Furthermore, q≥p/2q≥ p/2. Therefore, q(1−q)≥(p/2)(1/4)=p/8q(1-q)≥(p/2)(1/4)=p/8. Thus: kl(p,q)≤(p−q)2q(1−q)≤8(q−p)2p≤16Δ2Jσ2.kl(p,q)≤ (p-q)^2q(1-q)≤ 8 (q-p)^2p≤ 16 ^2Jσ^2. The first bound holds with the absolute constant C0=16C_0=16. For the opposite perturbations, p+=qp_+=q and p−=2p−qp_-=2p-q, so |p±−p|≤p/2|p_±-p|≤ p/2. With p≤1/2p≤ 1/2 as above, both denominators satisfy p±(1−p±)≥p/8p_±(1-p_±)≥ p/8. Since p+−p−=2(q−p)p_+-p_-=2(q-p), the same binary KL inequality gives maxkl(p−,p+),kl(p+,p−)≤84(q−p)2p≤64Δ2Jσ2=4C0Δ2Jσ2. \kl(p_-,p_+),kl(p_+,p_-)\≤ 8 4(q-p)^2p≤ 64 ^2Jσ^2=4C_0 ^2Jσ^2. ∎ D.3 Embedding and change of measure Define the K-arm base instance ν(0):=(P0,P−,…,P−)ν^(0):=(P_0,P_-,…,P_-), where arm 11 is optimal and all suboptimal gaps equal Δ . For each i∈2,…,Ki∈\2,…,K\, let ν(i)ν^(i) differ only in arm i, whose distribution is changed from P−P_- to P+P_+. Arm i is then uniquely optimal, with gap Δ to arm 11. Let Pr0 _0 and Pri _i denote the corresponding probability measures induced by the interaction of the algorithm, and let 0E_0 and iE_i denote their expectations. The same anchors ck=0c_k=0 are supplied under every instance. Write Ni(t)N_i(t) for the number of queries to arm i up to time t. Let τ be the algorithm’s stopping time. At each round t≤τt≤τ, the algorithm selects an arm Kt∈1,…,KK_t∈\1,…,K\ and a measurable query set At⊆ℝA_t , then observes the 1-bit feedback Yt=Xt∈AtY_t=1\X_t∈ A_t\ where XtX_t is drawn from the distribution of the pulled arm. To facilitate a clean change-of-measure argument over a deterministic time horizon, we formally extend this to an infinite padded transcript Zt:=(K~t,A~t,Y~t)Z_t:=( K_t, A_t, Y_t) defined for all integers t≥1t≥ 1. Let ∅ represent an empty query set and ⟂ a null observation where ⟂∉0,1 ∉\0,1\, and define the padded variables piecewise: K~t:=Kt,if t≤τ,1,if t>τ,A~t:=At,if t≤τ,∅,if t>τ,Y~t:=Yt,if t≤τ,⟂,if t>τ. K_t:= casesK_t,&if t≤τ,\\ 1,&if t>τ, cases A_t:= casesA_t,&if t≤τ,\\ ,&if t>τ, cases Y_t:= casesY_t,&if t≤τ,\\ ,&if t>τ. cases By construction, once the algorithm stops (t>τt>τ), the transcript deterministically locks to the state (1,∅,⟂)(1, , ), ensuring no further statistical information is gathered under either instance. We denote the history up to time t as Z1:t=(Z1,…,Zt)Z_1:t=(Z_1,…,Z_t), which, together with an independent initial random seed U containing the algorithm’s internal randomness, generates the natural filtration ℱt=σ(U,Z1:t)F_t=σ(U,Z_1:t). The law of U is the same under every instance. Consequently, both the stopping time τ and the final arm recommendation k k are measurable with respect to the infinite-horizon σ-algebra ℱ∞=σ(⋃t=1∞ℱt)F_∞=σ ( _t=1^∞F_t ). Lemma 37 (Data processing for the error event). If the algorithm is δ-correct over the instance class, then for each i≥2i≥ 2 KL(Pr0,Pri)≥c1log(1/δ)KL( _0, _i)≥ c_1 (1/δ) for an absolute constant c1>0c_1>0. The same conclusion holds for (ε,δ)( ,δ)-PAC algorithms when 0<ε<Δ/20< < /2, since only the unique best arm is ε -optimal in either instance. Proof. Let E:=k^=1E:=\ k=1\ be the event that the algorithm recommends arm 1. By the δ-correctness requirement, the algorithm must identify the correct arm with probability at least 1−δ1-δ. Therefore, Pr0(E)≥1−δ _0(E)≥ 1-δ and Pri(E)≤δ _i(E)≤δ. Because the recommendation k k is entirely determined by the full transcript (U,(Zt)t≥1)(U,(Z_t)_t≥ 1), the data-processing inequality implies: KL(Pr0,Pri)≥kl(Pr0(E),Pri(E))≥kl(1−δ,δ).KL( _0, _i) ( _0(E), _i(E)) (1-δ,δ). For any δ∈(0,1/4)δ∈(0,1/4), kl(1−δ,δ)≥(1−2δ)log1−δ≥c1log(1/δ)kl(1-δ,δ)≥(1-2δ) 1-δ≥ c_1 (1/δ) for some c1>0c_1>0. ∎ Lemma 38 (Transcript divergence bound). For each i≥2i≥ 2, KL(Pr0,Pri)≤4C0Δ2Jσ20[Ni(τ)]KL( _0, _i)≤ 4C_0 ^2Jσ^2E_0[N_i(τ)]. Proof. Fix i≥2i≥ 2. Let Pr0(T) _0^(T) and Pri(T) _i^(T) denote the marginal laws of the truncated transcript (U,Z1:T)(U,Z_1:T). By the chain rule for relative entropy: KL(Pr0(T),Pri(T))=∑t=1T0[KL(Pr0(Zt∣U,Z1:t−1)∥Pri(Zt∣U,Z1:t−1))].KL( _0^(T), _i^(T))= _t=1^TE_0 [KL( _0(Z_t U,Z_1:t-1) _i(Z_t U,Z_1:t-1)) ]. Let ℱt−1F_t-1 be the σ-algebra generated by (U,Z1:t−1)(U,Z_1:t-1). Conditioned on ℱt−1F_t-1, the event t≤τ\t≤τ\ is determined. If t>τt>τ, the process has stopped, and Zt=(1,∅,⟂)Z_t=(1, , ) is deterministic under both instances. The conditional KL divergence is exactly 00. If t≤τt≤τ, the arm KtK_t and query set AtA_t are deterministic functions of ℱt−1F_t-1. The only randomness lies in the Bernoulli observation YtY_t. If Kt≠iK_t≠ i, its distribution is unchanged between ν(0)ν^(0) and ν(i)ν^(i), so the conditional divergence is 00. If Kt=iK_t=i, then Yt∼Ber(P−(At))Y_t (P_-(A_t)) under ν(0)ν^(0) and Yt∼Ber(P+(At))Y_t (P_+(A_t)) under ν(i)ν^(i). By Lemma 36, the conditional divergence is bounded by 4C0Δ2/(Jσ2)4C_0 ^2/(Jσ^2). Thus: KL(Pr0(T),Pri(T))≤∑t=1T0[t≤τ,Kt=i4C0Δ2Jσ2]=4C0Δ2Jσ20[Ni(T∧τ)].KL( _0^(T), _i^(T))≤ _t=1^TE_0 [1\t≤τ,\ K_t=i\4C_0 ^2Jσ^2 ]=4C_0 ^2Jσ^2E_0[N_i(T τ)]. Because ℱTF_T forms an increasing filtration generating the full transcript, KL(Pr0,Pri)=limT→∞KL(Pr0(T),Pri(T))KL( _0, _i)= _T→∞KL( _0^(T), _i^(T)). Applying the monotone convergence theorem to Ni(T∧τ)N_i(T τ) yields the final bound. ∎ Proof of Theorem 12. Assuming 0[τ]<∞E_0[τ]<∞ (otherwise the lower bound holds trivially), we link the information complexity from Lemma 38 to the statistical requirement from Lemma 37, for each i=2,…,Ki=2,…,K: 4C0Δ2Jσ20[Ni(τ)]≥c1log(1δ).4C_0 ^2Jσ^2E_0[N_i(τ)]≥ c_1 ( 1δ ). Rearranging this inequality for the expected sample complexity yields: 0[Ni(τ)]≥c14C0σ2JΔ2log(1δ).E_0[N_i(τ)]≥ c_14C_0 σ^2J ^2 ( 1δ ). All these inequalities hold under the same base instance. Summing over its K−1K-1 suboptimal arms gives 0[τ]≥∑i=2K0[Ni(τ)]≥c14C0(K−1)σ2JΔ2log(1δ).E_0[τ]≥ _i=2^KE_0[N_i(τ)]≥ c_14C_0(K-1) σ^2J ^2 ( 1δ ). Recalling our construction choice that J=⌊log2(σΔ)⌋J= _2( σ ) , it holds that J≥c2log(σΔ)J≥ c_2 ( σ ) for some constant c2>0c_2>0 given the restriction Δ≤σ/4 ≤σ/4. Substituting this structural scale count gives: 0[τ]≥c(K−1)σ2Δ2log(σΔ)log(1δ),E_0[τ]≥ c(K-1) σ^2 ^2 ( σ ) ( 1δ ), where c=c1c24C0>0c= c_1c_24C_0>0 is an absolute constant, completing the proof. ∎ Appendix E Detailed algorithms This section gives the full pseudocode for the routines described in Section 3. The PAC theorems in the main text assume that valid anchors ckc_k satisfying |μk−ck|≤σ| _k-c_k|≤σ are supplied. If anchors are not supplied but the means are known to lie in [−λ,λ][-λ,λ], the algorithms call MedianEst (Algorithm 1 in Appendix A) for each arm and then run the BAI routine with the remaining confidence budget. This adds the localization cost stated in Remark 1. Algorithm 2 One randomized tail-integral query, TailIntegralQuery 1: arm k, anchor ckc_k, clipping level L≥σL≥σ, variance proxy σ 2: Set αL←1+log(L/σ) _L← 1+ (L/σ) and gL(t)←[αLmaxσ,t]−1g_L(t)←[ _L \σ,t\]^-1 for t∈[0,L]t∈[0,L] 3: Draw S∈+1,−1S∈\+1,-1\ uniformly and draw T∼gLT g_L 4: if S=+1S=+1 then 5: Query arm k with threshold set [ck+T,∞)[c_k+T,∞) and observe Y=Xk≥ck+TY=1\X_k≥ c_k+T\ 6: else 7: Query arm k with threshold set (−∞,ck−T](-∞,c_k-T] and observe Y=Xk≤ck−TY=1\X_k≤ c_k-T\ 8: end if 9: return Z←2SY/gL(T)Z← 2SY/g_L(T) Algorithm 3 FixedClip-1BitBAI 1: arms =[K]A=[K], variance proxy σ, accuracy ε , confidence δ, anchors (ck)k=1K(c_k)_k=1^K or range λ 2: if anchors are not supplied then 3: for k=1,…,Kk=1,…,K do 4: ck←MedianEst(k,λ,σ,δ/(2K))c_k← MedianEst(k,λ,σ,δ/(2K)) 5: end for 6: Set δ0←δ/2 _0←δ/2 7: else 8: Set δ0←δ _0←δ 9: end if 10: Set Lε←2σ2/εL_ ← 2σ^2/ , γ←δ0/Kγ← _0/K 11: for k=1,…,Kk=1,…,K do 12: Initialize an empty list kZ_k 13: Append TailIntegralQuery(k,ck,Lε,σ) TailIntegralQuery(k,c_k,L_ ,σ) to kZ_k 14: end for 15: loop 16: for k=1,…,Kk=1,…,K do 17: Nk←|k|N_k←|Z_k|, μ^k←ck+Nk−1∑Z∈kZ μ_k← c_k+N_k^-1 _Z _kZ 18: βk←βε(Nk,γ) _k← _ (N_k,γ) 19: LCBk←μ^k−βkLCB_k← μ_k- _k, UCBk←μ^k+βkUCB_k← μ_k+ _k 20: end for 21: for k=1,…,Kk=1,…,K do 22: Bk←maxℓ≠kUCBℓ−LCBkB_k← _ ≠ kUCB_ -LCB_k 23: end for 24: h←argmink∈Bkh← _k B_k, ℓ←argmaxa≠hUCBa ← _a≠ hUCB_a 25: if Bh≤εB_h≤ then 26: return h 27: end if 28: kt←argmaxa∈h,ℓβak_t← _a∈\h, \ _a 29: Append TailIntegralQuery(kt,ckt,Lε,σ) TailIntegralQuery(k_t,c_k_t,L_ ,σ) to ktZ_k_t 30: end loop Algorithm 4 RestartPhasedClip-1BitBAI 1: arms =[K]A=[K], variance proxy σ, accuracy ε , confidence δ, anchors (ck)k=1K(c_k)_k=1^K or range λ 2: if anchors are not supplied then 3: for k=1,…,Kk=1,…,K do 4: ck←MedianEst(k,λ,σ,δ/(2K))c_k← MedianEst(k,λ,σ,δ/(2K)) 5: end for 6: Set δ0←δ/2 _0←δ/2 7: else 8: Set δ0←δ _0←δ 9: end if 10: Set J←⌈log2(σ/ε)⌉J← _2(σ/ ) , active set A←A , and γ←δ0/[K(J+1)]γ← _0/[K(J+1)] 11: for j=0,1,…,Jj=0,1,…,J do 12: Set ρj←2−jσ _j← 2^-jσ, Lj←32σ2/ρjL_j← 32σ^2/ _j, rj←ρj/16r_j← _j/16 13: for k∈Ak∈ A do 14: Restart a fresh phase list k,j←∅Z_k,j← 15: end for 16: loop 17: for k∈Ak∈ A do 18: if |k,j|=0|Z_k,j|=0 then 19: βk,j←+∞ _k,j←+∞, LCBk,j←−∞LCB_k,j←-∞, UCBk,j←+∞UCB_k,j←+∞ 20: else 21: Nk,j←|k,j|N_k,j←|Z_k,j|, μ^k,j←ck+Nk,j−1∑Z∈k,jZ μ_k,j← c_k+N_k,j^-1 _Z _k,jZ 22: βk,j←βj(Nk,j) _k,j← _j(N_k,j) 23: LCBk,j←μ^k,j−βk,jLCB_k,j← μ_k,j- _k,j, UCBk,j←μ^k,j+βk,jUCB_k,j← μ_k,j+ _k,j 24: end if 25: end for 26: m←maxi∈ALCBi,jm← _i∈ ALCB_i,j and remove every k∈Ak∈ A with UCBk,j<m−εUCB_k,j<m- 27: if |A|=1|A|=1 then 28: return the unique arm in A 29: end if 30: h←argmaxk∈ALCBk,jh← _k∈ ALCB_k,j, ℓ←argmaxa∈A∖hUCBa,j ← _a∈ A \h\UCB_a,j 31: if UCBℓ,j−LCBh,j≤εUCB_ ,j-LCB_h,j≤ then 32: return h 33: end if 34: if maxk∈Aβk,j≤rj _k∈ A _k,j≤ r_j then 35: if j=Jj=J then 36: return h 37: else 38: break and move to phase j+1j+1 39: end if 40: end if 41: if maxβh,j,βℓ,j>rj \ _h,j, _ ,j\>r_j then 42: kt←argmaxa∈h,ℓβa,jk_t← _a∈\h, \ _a,j 43: else 44: kt←argmaxa∈Aβa,jk_t← _a∈ A _a,j 45: end if 46: Append TailIntegralQuery(kt,ckt,Lj,σ) TailIntegralQuery(k_t,c_k_t,L_j,σ) to kt,jZ_k_t,j 47: end loop 48: end for Appendix F Numerical experiment details F.1 1-bit mean estimation Experimental setting. We compare our tail-integral estimator with the estimator of [20] on three scalar distributions: Normal(μ,1μ,1), Student-t(55) scaled to variance 1, and a shifted exponential law with variance 1. In all cases we set μ=1,σ=1,c=0,μ=1, σ=1, c=0, so that the centered variable is W=X−cW=X-c. We evaluate both estimators over 100100 logarithmically spaced sample sizes between 1010 and 10710^7, and estimate the MAE [|μ^n−μ|]E [| μ_n-μ| ] by averaging over 10001000 Monte Carlo repetitions. Bias-target calibration. We use a common deterministic bias target b=0.1b=0.1 for both estimators. For our estimator, Theorem 5 contains the clipping-bias term σ2/(2L)σ^2/(2L), so we choose L=σ22b.L= σ^22b. In the implementation of the baseline experiment, the [20] truncation parameter t is calibrated to the same target b. With σ=1σ=1 and b=0.1b=0.1, this gives L=t=5.L=t=5. True bias computation. Beyond the common nominal bias budget b, we also compute the exact deterministic bias induced by the chosen clipping/truncation level for each distribution. For our estimator, the true bias is Bours:=|[[W]L−W]|,B_ours:= |E [[W]_L-W ] |, where [W]L=max−L,minW,L[W]_L= \-L, \W,L\\. For the [20] estimator, the true bias is BLS:=|[W|W|<t]−[W]|=|[W|W|≥t]|.B_LS:= |E [W1\|W|<t\ ]-E[W] |= |E [W1\|W|≥ t\ ] |. These quantities are evaluated from the known distribution in each environment and are plotted as horizontal reference lines in Figure 1 whenever they exceed 10−310^-3. Distribution BoursB_ours BLSB_LS Normal 7.15×10−67.15× 10^-6 1.66×10−41.66× 10^-4 Student-t(5)t(5) 1.56×10−31.56× 10^-3 9.06×10−39.06× 10^-3 Exponential 6.74×10−36.74× 10^-3 4.04×10−24.04× 10^-2 Table 1: True bias under the common theoretic bias target b=0.1b=0.1. Figure 3: Ratio MAELS(n)/MAEours(n)MAE_LS(n)/MAE_ours(n) as a function of n. Values above 11 indicate that the [20] estimator has larger error. Discussion of the ratio plot. Figure 3 highlights the MAE comparison more directly. In the pre-asymptotic regime, where neither estimator has yet reached its bias floor, the ratio is close to 22 across all three distributions. In other words, before bias dominates, the [20] estimator has roughly double the MAE of our estimator. As n grows, the ratio increases further in the heavy-tailed and asymmetric cases because the larger true bias of the baseline causes its MAE to plateau earlier and at a higher level. F.2 Variance comparison with Lau–Scarlett The bands in Figure 1 describe absolute errors and do not directly measure the variance of the signed estimates. To compare dispersion, we use the signed n-sample estimates from the same R=1000R=1000 independent repetitions and the same calibration μ=1μ=1, σ=1σ=1, c=0c=0, L=t=5L=t=5. For either estimator, compute Var^(μ^n)=1R−1∑r=1R(μ^n(r)−μ^¯n)2,μ^¯n=1R∑r=1Rμ^n(r). Var( μ_n)= 1R-1 _r=1^R ( μ_n^(r)- μ_n )^2, μ_n= 1R _r=1^R μ_n^(r). Table 2 reports its square root. These values are the Monte Carlo results reported in the rebuttal. Distribution n Std. (ours) Std. (Lau–Scarlett) Ratio (LS/ours) Normal 10410^4 0.025150.02515 0.049170.04917 1.9551.955 10510^5 0.0078060.007806 0.016240.01624 2.0812.081 10610^6 0.0024720.002472 0.0051660.005166 2.0902.090 10710^7 0.00078600.0007860 0.0015370.001537 1.9561.956 Student-t(5)t(5) 10410^4 0.025320.02532 0.049950.04995 1.9731.973 10510^5 0.0077990.007799 0.015850.01585 2.0332.033 10610^6 0.0024520.002452 0.0050020.005002 2.0402.040 10710^7 0.00078630.0007863 0.0015570.001557 1.9801.980 Exponential 10410^4 0.024690.02469 0.049170.04917 1.9921.992 10510^5 0.0072850.007285 0.015060.01506 2.0672.067 10610^6 0.0024130.002413 0.0049160.004916 2.0372.037 10710^7 0.00077160.0007716 0.0014850.001485 1.9241.924 Table 2: Empirical standard deviations of signed estimates over 10001000 repetitions, under the common calibration. Ratios above one indicate greater dispersion for the Lau–Scarlett baseline. Across these twelve configurations, the baseline’s standard deviation is 1.9241.924–2.0902.090 times ours, corresponding to approximately 3.703.70–4.374.37 times the empirical variance. Under this calibration our estimator therefore has smaller dispersion as well as smaller clipping bias. This comparison concerns the implemented fixed-budget estimators on these distributions; it establishes neither a universal variance ordering nor a sample-complexity rate separation. Variance is computed about each estimator’s empirical mean and is distinct from mean squared error, which also includes bias. F.3 1-bit best-arm identification Experiment Setting The empirical performance of the proposed 1-bit best-arm identification algorithms was evaluated against the full-feedback UGapE baseline across three distinct environments. For all experiments, we evaluate a K=5K=5 armed bandit setting with a target accuracy of ϵ=0.05ε=0.05 and a maximum query cap of N=20000N=20000. To thoroughly analyze the sample complexity and safety of each approach, the confidence parameter δ is varied over 10 logarithmically spaced values from 0.010.01 to 0.50.5. The results are averaged over 50005000 independent Monte Carlo runs for each configuration. BAI Environments and Distributions The experiments utilize three distinct reward environments, all bounded by a global variance proxy of σ=0.5σ=0.5: • Bernoulli: The reward distributions are Bernoulli with means μ=[0.5,0.4,0.4,0.4,0.4]μ=[0.5,0.4,0.4,0.4,0.4]. This represents a uniform gap setting where Δk=0.1 _k=0.1 for all suboptimal arms. The arm-wise anchors are ck=0.5c_k=0.5 for all arms and satisfy the localization condition. • Normal: The rewards follow a Gaussian distribution with linearly decaying means μ=[0.5,0.4,0.3,0.2,0.1]μ=[0.5,0.4,0.3,0.2,0.1]. The arm standard deviations are set to σk=0.5 _k=0.5, and the anchors are uniformly set to ck=0c_k=0. • Student-t: The rewards are drawn from a heavy-tailed Student-t distribution with degrees of freedom df=3df=3. The distributions are scaled by a factor of σ(df−2)/dfσ (df-2)/df so that the true variance is precisely σ2σ^2. The arm means are μ=[0.5,0.4,0.3,0.2,0.1]μ=[0.5,0.4,0.3,0.2,0.1] and the anchors are ck=0c_k=0. Algorithms and Exploration Parameter Tuning We evaluate three variations of our 1-bit algorithm—FixedClip, RestartPhase, and ReusePhase—against the full-feedback UGapE baseline. In practice, theoretically derived confidence intervals can be overly conservative. For the empirical comparison, we introduce a constant exploration multiplier to the leading confidence radius term. For the 1-bit algorithms, this is implemented as an exploration parameter that directly scales the logarithmic xn(γ)x_n(γ) term within the tail-integral confidence bounds. The exploration parameters were tuned as follows: • FixedClip: The exploration parameter was tuned to 0.040.04 for the Bernoulli environment and 0.050.05 for the Normal and Student-t environments. • RestartPhase & ReusePhase: The exploration parameter was consistently set to 0.030.03 across all three environments. • UGapE Baseline: The exploration constant c scaling the empirical Bernstein/Hoeffding radius was tuned per environment to 0.060.06 for Bernoulli, 0.00020.0002 for Normal, and 0.00050.0005 for Student-t. UGapE Modifications for Unbounded Support For bounded-support environments (e.g., Bernoulli), the UGapE baseline uses the raw full-feedback rewards. However, for unbounded-support environments (such as the Normal and Student-t settings), the UGapE baseline is modified to include finite-variance clipping. In these unbounded settings, it still receives full continuous feedback, but it clips every observed reward around the arm’s anchor using the same fixed clipping scale L as the FixedClip algorithm. The corresponding finite-variance clipping bias is then explicitly added to the algorithm’s confidence radius. The reported empirical error frequencies remain at or below the target δ in the tested configurations. Reducing the exploration multipliers below their theorem values and imposing the experimental query cap do not preserve the proved PAC guarantee automatically. These results are empirical assessments of the tuned implementations; Theorems 8 and 10 concern the stated, untuned confidence radii and stopping rules. F.4 Compute resources All numerical simulations were executed on a dedicated Linux workstation equipped with an Intel(R) Core(TM) Ultra 9 285K processor (24 cores, up to 5.1 GHz) and 128 GB of RAM. In terms of computational cost, the standalone 1-bit mean estimation experiments required approximately 40 minutes of total execution time. The best-arm identification (BAI) experiments are more computationally intensive due to the adaptive sampling and large number of Monte Carlo iterations (5000 runs per configuration); each BAI experiment (Bernoulli, Normal, and Student-t) required approximately 10 hours to complete. NeurIPS Paper Checklist 1. Claims Question: Do the main claims made in the abstract and introduction accurately reflect the paper’s contributions and scope? Answer: [Yes] Justification: The abstract and Introduction (Section 1) clearly outline the development of the 1-bit mean estimator (Section 2), the fixed and phased clipping algorithms (Section 3), the lower bound (Section 4), and empirical validation (Section 5), which match the paper’s theoretical and experimental results. Guidelines: • The answer [N/A] means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A [No] or [N/A] answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 2. Limitations Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes] Justification: The paper discusses the required variance proxy and anchor point assumptions in Remark 1 and Appendix A, explicitly notes the sample complexity mixed-term penalty incurred by the fixed-clipping approach in Section 3.3, and further summarizes these limitations in Section 6. Guidelines: • The answer [N/A] means that the paper has no limitation while the answer [No] means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate “Limitations” section in their paper. • The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren’t acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 3. Theory assumptions and proofs Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? Answer: [Yes] Justification: The required assumptions are explicitly stated in Section 1 (Problem Setting), and complete rigorous proofs for all lemmas and theorems are provided in Appendix B, Appendix C, and Appendix D. Guidelines: • The answer [N/A] means that the paper does not include theoretical results. • All the theorems, formulas, and proofs in the paper should be numbered and cross-referenced. • All assumptions should be clearly stated or referenced in the statement of any theorems. • The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 4. Experimental result reproducibility Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)? Answer: [Yes] Justification: Section 5 and Appendix F specify the synthetic environments (Bernoulli, Normal, Student-t), target accuracy, confidence parameters, algorithmic hyperparameters, and the number of Monte Carlo runs. Guidelines: • The answer [N/A] means that the paper does not include experiments. • If the paper includes experiments, a [No] answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example (a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully. (c) If the contribution is a new model (e.g., a large language model), then there should either be a way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 5. Open access to data and code Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [Yes] Justification: An anonymized .zip file containing the code, dependency specifications, and instructions necessary to faithfully reproduce the main experimental results is included in the supplementary material, in accordance with the NeurIPS Code and Data Submission Guidelines. Guidelines: • The answer [N/A] means that paper does not include experiments requiring code. • Please see the NeurIPS code and data submission guidelines (https://neurips.c/public/guides/CodeSubmissionPolicy) for more details. • While we encourage the release of code and data, we understand that this might not be possible, so [No] is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark). • The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https://neurips.c/public/guides/CodeSubmissionPolicy) for more details. • The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc. • The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why. • At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable). • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 6. Experimental setting/details Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer) necessary to understand the results? Answer: [Yes] Justification: Appendix F clearly defines the environment setups, arm means, gaps, variances, and algorithmic exploration hyperparameters for both the estimator and BAI experiments. Guidelines: • The answer [N/A] means that the paper does not include experiments. • The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 7. Experiment statistical significance Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments? Answer: [Yes] Justification: The results are averaged over 1000 to 5000 independent Monte Carlo runs. Figure 1 and Figure 2 reports standard deviations of the plotted quantities, while Appendix F.2 compares dispersion of signed estimates. Empirical error rates of the tuned BAI implementations are distinguished from the theoretical PAC guarantees in Appendix F.3. Guidelines: • The answer [N/A] means that the paper does not include experiments. • The authors should answer [Yes] if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g., negative error rates). • If error bars are reported in tables or plots, the authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 8. Experiments compute resources Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments? Answer: [Yes] Justification: Appendix F explicitly details the compute resources (Intel Core Ultra 9 285K CPU, 128 GB RAM) and the execution times for both the estimator experiment (40 minutes) and the BAI experiments (10 hours each). Guidelines: • The answer [N/A] means that the paper does not include experiments. • The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn’t make it into the paper). 9. Code of ethics Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.c/public/EthicsGuidelines? Answer: [Yes] Justification: The research focuses on foundational theoretical and algorithmic machine learning methodology (Sections 2 to 4), which fully conforms to the NeurIPS Code of Ethics. Guidelines: • The answer [N/A] means that the authors have not reviewed the NeurIPS Code of Ethics. • If the authors answer [No] , they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 10. Broader impacts Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? Answer: [N/A] Justification: This is foundational theoretical research on best-arm identification (Sections 3 and 4) evaluated on synthetic distributions (Section 5), presenting no immediate foreseeable negative societal impacts or direct paths to malicious applications. Guidelines: • The answer [N/A] means that there is no societal impact of the work performed. • If the authors answer [N/A] or [No] , they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate Deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 11. Safeguards Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pre-trained language models, image generators, or scraped datasets)? Answer: [N/A] Justification: The paper does not introduce or release high-risk models, language models, or scraped datasets (all data is simulated as per Appendix F). Guidelines: • The answer [N/A] means that the paper poses no such risks. • Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [N/A] Justification: The research relies on standard mathematical formulations and newly generated synthetic data (Normal, Student-t, Bernoulli) as detailed in Appendix F, rather than existing third-party proprietary assets. Guidelines: • The answer [N/A] means that the paper does not use existing assets. • The authors should cite the original paper that produced the code package or dataset. • The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., C-BY 4.0) should be included for each asset. • For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset’s creators. 13. New assets Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets? Answer: [N/A] Justification: The paper introduces new algorithms (Appendix E) but does not release new datasets or pre-trained models. Guidelines: • The answer [N/A] means that the paper does not release new assets. • Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 14. Crowdsourcing and research with human subjects Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)? Answer: [N/A] Justification: The research evaluates algorithms on synthetic statistical environments (Appendix F) and does not involve human subjects. Guidelines: • The answer [N/A] means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 15. Institutional review board (IRB) approvals or equivalent for research with human subjects Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained? Answer: [N/A] Justification: The research utilizes synthetic distributions (Appendix F) and does not involve human subjects. Guidelines: • The answer [N/A] means that the paper does not involve crowdsourcing nor research with human subjects. • Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 16. Declaration of LLM usage Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigor, or originality of the research, declaration is not required. Answer: [N/A] Justification: LLMs are not used as a component of the core theoretical methodology or algorithm design (Sections 2 to 4). Guidelines: • The answer [N/A] means that the core method development in this research does not involve LLMs as any important, original, or non-standard components. • Please refer to our LLM policy in the NeurIPS handbook for what should or should not be described.