Nearly Optimal Fixed-Confidence Best-Arm Identification with 1-Bit Feedback

1 Introduction

• One-bit threshold queries model both sensing-location selection and screening buyer populations by mean valuation, not revenue.The sensing example uses a thresholded pollutant concentration or diagnostic score; the posted-price example observes only accept or reject.Source: §1 · p. 1

1.1 Problem setting

• The setting assumes finite variance and known arm-wise anchors that localize each mean, enabling efficient use of the 1-bit estimator.An anchor distance of O(σ) is sufficient up to changes in constant factors.Source: §1.1 · p. 2

1.2 Contributions

• The randomized-threshold mean estimator supplies confidence sequences valid under adaptive arm selection and stopping, matching the standalone finite-variance rate up to iterated-logarithmic overhead.Its contribution is adaptive validity for BAI, rather than an improved standalone mean-estimation rate over Lau and Scarlett [21].Source: §1.2 · p. 3
• The fixed-clipping and phased adaptive-clipping algorithms are both (ε, δ)-PAC, while the phased method removes the fixed method’s mixed-term cost.The phased method adjusts clipping to the current resolution; experiments report fewer queries than fixed clipping on tested instances with heterogeneous gaps.Source: §1.2 · p. 3
• A K-arm worst-case lower bound makes the logarithmic penalty unavoidable and matches the phased upper bound’s leading dependence up to a log log factor.The lower bound is for fixed-confidence identification under 1-bit set queries.Source: §1.2 · p. 3

1.3 Related work

• Unlike prior fixed-confidence BAI methods using direct rewards, this work handles adaptive 1-bit set queries with finite-variance rewards.Its mean-estimation primitive matches Lau and Scarlett [21] up to the time-uniform log log overhead, while making confidence valid under adaptive selection and stopping.Source: §1.3 · p. 4

2 A 1-bit mean estimator

• Centering rewards at an anchor c satisfying |µ − c| ≤ σ reduces the task to estimating E[W], where W = X − c, using only 1-bit threshold information.The estimator’s clipping level can be set from the target accuracy to obtain β accuracy with probability at least 1 − γ.Source: §2 · p. 4, §2.3 · p. 6

2.1 A tail-integral identity

• The tail-integral identity writes the clipped mean as an integral of upper-tail minus lower-tail probabilities, which randomized threshold queries can estimate one bit at a time.Clipping separates a bounded estimand from a bias term controlled using the variance bound; increasing L reduces bias but worsens the variance and range bounds.Source: §2.1 · p. 5, §2.2 · p. 5

2.2 A 1-bit randomized estimator

• The randomized sign-and-threshold procedure yields Z with E[Z]=E[[W]L], making it unbiased for the clipped mean; Var(Z) ≤ 3αLσ² and |Z| ≤ 2αLL almost surely.The query is Y = 1{S(X − c) ≥ T}, and Z := 2SgL(T)Y.Source: §2.2 · p. 5

2.3 Confidence sequence for the tail-integral estimator

• With probability at least 1 − γ, the confidence sequence bounds estimation error by β(n, γ, L) simultaneously for all n ≥ 1.Its terms represent clipping bias, stochastic fluctuation, and a Bernstein range correction; the stitched penalty is of order log(1/γ) + log log(e + n).Source: §2.3 · p. 6
• The estimator matches the finite-variance 1-bit mean-estimation rate of [21] up to the lower-order log log factor needed for time-uniform validity.Unlike [21]’s fixed regional budgets, it samples a randomized threshold and yields an anytime confidence sequence.Source: §2.3 · p. 6

3 1-bit BAI algorithm and upper bound

• Candidate-challenger sampling selects a candidate and strongest challenger, then samples the less certain arm until the candidate is certified ε-optimal.Both algorithms use arm-wise confidence intervals and are (ε, δ)-PAC.Source: §3 · p. 6

3.1 Fixed clipping bias

• Fixed clipping uses a target-accuracy-based level, is simple and fully anytime, but incurs a mixed term from the clipped statistic’s range.The chosen level ensures clipping bias at most ε/4; the range correction adds a lower-order n^-1 ε^-1 term.Source: §3 · p. 6, §3.1 · p. 7
• The fixed-clipping upper bound guarantees (ε, δ)-PAC identification with probability at least 1 − δ.A finite deterministic query bound also guarantees termination for ε > 0, including outside the confidence event.Source: §3.1 · p. 7

3.2 Phased adaptive clipping

• Phased clipping proceeds from coarse to fine resolutions, eliminating arms distinguishable at each scale so only competitive arms reach finer phases.At phase j, the clipping bias is at most ρ_j/64 and the target statistical radius is ρ_j/16.Source: §3.2 · pp. 7–8
• The phased algorithm is (ε, δ)-PAC; reusing samples across clipping levels preserves the same order as its restart version.The restart design is chosen for proof clarity.Source: §3.2 · p. 8

3.3 Discussion of the sample complexity

• Phased clipping removes the fixed method’s mixed ε- and gap-dependent term, while its additional logarithmic 1-bit penalty is unavoidable under finite variance.The phased cost balances the range term at the scale where each arm is distinguished.Source: §3.3 · p. 8
• A successive-elimination alternative using Lau–Scarlett [21] estimators at each resolution also matches the leading gap-dependent rate.Its total cost is O(H_gap log(K(J + 1)/δ)).Source: §3.3 · p. 8
• When means are not initially localized but lie in [−λ, λ], MEDIANEST adds a query-cost term independent of ε and the gaps.The supplied passages do not state the term’s full expression.Source: §3.3 · p. 8

4 Lower bound

• Opposite perturbations of a multiscale distribution create K-arm alternatives, and adaptive change of measure forces queries to distinguish them.Changing one suboptimal arm at a time creates a different best arm; summing the required queries gives a factor of K − 1.Source: §4 · p. 9
• The worst-case lower bound matches the phased algorithm’s leading K, gap, and confidence dependence, up to lower-order iterated logarithms.The comparison is for equal-gap instances and does not characterize optimal expected complexity on every instance.Source: §4 · p. 9
• The lower bound persists when valid anchors are supplied, and the paper does not claim it characterizes every instance’s optimal expected complexity.On the equal-gap base instance, Hgap = K(1 + log(σ/∆))σ2/∆2.Source: §4 · p. 9

5.1 1-bit mean estimation

• Both estimators show O(n^-1/2) MAE decay in the Gaussian case, while ours has lower MAE and a lower asymptotic error floor for Student-t and exponential distributions.The lower floor is attributed to smaller true deterministic clipping bias at the same clipping/truncation level; the empirical differences do not imply a rate separation.Source: Figure 1 · p. 9, §5.1 · pp. 9–10

5.2 1-bit best-arm identification

• With heterogeneous gaps, phased adaptive-clipping algorithms use fewer stopping rounds than fixed clipping by eliminating larger-gap arms earlier; the algorithms perform similarly with uniform gaps.The performance gap from the unquantized baseline is most significant in the Bernoulli environment and relatively smaller in the Normal and Student-t settings.Source: §5.2 · p. 10, Figure 2 · p. 10

6 Conclusion

• The framework combines a fixed-clipping baseline with a gap-adaptive phased alternative, whose worst-case guarantee is optimal up to log log factors.The conclusion also identifies weakening the localization assumption, determining exact instance-dependent complexity, and extending the primitive to broader pure-exploration tasks as future work.Source: §6 · p. 10

A.1 Bounding the mean via the median

• A median close to the mean supplies a valid arm anchor under the finite-variance assumption.The appendix bounds the median’s distance from the mean by σ, so a point close to the median can provide an anchor within O(σ).Source: §A.1 · p. 13

A.2 Noisy binary search

• MEDIANEST uses monotonicity of threshold-response probabilities to find an interval whose probability range intersects a window around one half.This is framed as the MONOTONICNBS(τ, ε′) problem with τ = 1/2 and cited guarantee [9].Source: §A.2 · p. 13

A.3 The MEDIANEST algorithm

• MEDIANEST adapts BAYESIANSCREENINGSEARCH to a threshold grid, with the appendix omitting exact loop counts to emphasize asymptotic scaling.The method is cited to [9].Source: §A.3 · p. 14

A.4 Parameter selection and estimate validity

• Fixing ε′ = 0.05 avoids the sample-cost increase from shrinking the localization tolerance, while κ = 0.2 yields |bc − µ| ≤ 1.205σ.The grid step is κσ and its size is Θ(λ/σ); grid density contributes only an additive logarithmic sample-budget term.Source: §A.4 · pp. 14–15
• The MEDIANEST initialization cost is additive, scales with K, and is independent of the arm gaps.The per-arm complexity simplifies to O(log n + log(1/γ)).Source: §A.4 · p. 16

B.1 Proof of Lemma 2 (Tail-integral identity)

• The tail-integral proof establishes a pointwise clipped-value identity and then takes expectations over the bounded integration interval.The proof states that the integrand is bounded in absolute value by 1 on a finite interval.Source: §B.1 · p. 17

B.2 Proof of Lemma 3

• The estimator proof identifies its conditional mean with the clipped input and bounds its second moment using the finite variance proxy.The displayed bound is E[Z2 | W = w] ≤ αL(σ2 + u2).Source: §B.2 · pp. 17–18

B.3 Proof of Lemma 4 (Clipping bias)

• The clipping-bias proof reduces the bound to the case where the input exceeds the clipping level.The proof says the inequality is trivial when x ≤ L and treats x > L separately.Source: §B.3 · p. 18

B.4 Proof of Theorem 5 (Confidence sequence for the 1-bit estimator)

• The proof centers the clipped estimator and uses its variance and range bounds to establish the Bernstein moment-generating-function bound.The centered variables have variance at most v_L and absolute value at most b_L.Source: §B.4 · p. 19
• The centered 1-bit variables yield an exponential supermartingale, which supports the epoch-wise Bernstein bound via Ville’s inequality.The proof optimizes over the exponential parameter and stitches the resulting bounds into a time-uniform sequence.Source: §B.4 · pp. 19–20
• Theorem 5 gives a confidence sequence that holds simultaneously for every n with probability at least 1 − γ.Its proof stitches epoch-wise bounds over dyadic epochs and then accounts for clipping bias.Source: §B.4 · pp. 19, 22

B.5 Sample-complexity inversion

• Sample-complexity inversion bounds the concentration and Bernstein range terms separately to meet the target accuracy.The proof identifies the concentration condition as strictly dominant and accounts for a stitched log-log term.Source: §B.5 · pp. 22–23

Uniform confidence event

• The intervals remain valid under adaptive arm selection because each arm’s estimator samples are i.i.d. when indexed by its local count.The time-uniform confidence sequence makes this event valid regardless of when the arm is selected.Source: §C.1 · p. 24

Structural comparison and pull bound

• A sampled arm’s stochastic radius must remain larger than a constant fraction of its effective gap, yielding an arm-wise pull bound.The structural comparison gives ε < −Δ_k + 4β_k for a sampled arm in a non-stopping round.Source: §C.1 · pp. 25–27

Sample-complexity counting bound

• The final query bound follows by summing arm-wise pull bounds; the stitched term contributes O(log log T) alongside log(K/δ).The proof chooses T proportional to H_fix(ε) times logarithmic factors.Source: §C.1 · pp. 27–28

Theorem 8

• On an event of probability at least 1 − δ, FIXEDCLIP-1BITBAI is (ε, δ)-PAC and its stopping time satisfies the claimed high-probability query bound.The proof combines interval validity, stopping correctness, the counting bound, and termination on every realization.Source: §C.1 · p. 28

C.2 Phased adaptive clipping: proof of Theorem 10

• On a simultaneous valid-interval event of probability at least 1 −δ, the phased algorithm returns an ε-optimal arm and satisfies Theorem 10’s query bound.The proof controls phase costs and shows arms are sampled only down to resolutions comparable to their capped effective gaps.Source: §C.2 · pp. 28, 29, 32
• The reusable phased algorithm preserves the order of Theorem 10’s query bound by retaining slab samples while certifying the same phase radii.Its stopping and elimination arguments apply because the confidence intervals remain valid and each completed phase reaches its target radius.Source: §C.2 · pp. 33, 35

C.3 Deterministic finite query bounds

• Both algorithms have finite gap-independent query caps on every realization for positive accuracy, establishing termination without conditioning on confidence validity.The stated scope assumes supplied anchors and 0 < ε ≤σ; for larger accuracy, the algorithms may use target σ.Source: §C.3 · p. 35

C.3.1 Fixed clipping

• The fixed-clipping algorithm has a finite pathwise query cap, with Proposition 32 specifying the cap through Aε and mε.The supplied passage gives Aε = αεσ2/ε2 and defines mε as the smallest nonnegative integer satisfying a condition not fully present in the excerpt.Source: §C.3.1 · pp. 35–36

C.3.2 Restart phased clipping

• Sampling stops for an arm once its radius reaches the phase threshold; after all active radii fall below it, the algorithm returns or advances phases.The rule samples only arms above the threshold, prioritizing the candidate or challenger with larger radius when possible, otherwise an active arm of maximum radius.Source: §C.3.2 · p. 36

j. Finally, ρJ ∈(ε/2, ε], αj and Γj are nondecreasing, and PJ

• Pathwise caps combined with the simultaneous confidence event imply almost-sure termination and (ε, δ)-PAC correctness, while high-probability theorems provide sharper instance-dependent guarantees.Source: j. Finally, ρJ ∈(ε/2, ε], αj and Γj… · p. 36

C.4 Lau–Scarlett estimators with phased successive elimination

• The batched wrapper runs Lau and Scarlett’s [21] finite-variance fixed-target estimator per active arm and phase, retains estimates within ρj/2 of the largest, and stops at a singleton or final phase.It uses accuracy ρj/8 and failure probability γ = δ/[K(J + 1)], with the supplied anchor.Source: §C.4 · p. 36
• On simultaneous accuracy, the best arm survives, arms with ∆k > 3ρj/4 are removed, and every final-phase survivor is ε-optimal.The wrapper matches the leading phased BAI rate, but gives simultaneous confidence only at completed checkpoints; Theorem 5 provides valid intervals after every intermediate local sample.Source: §C.4 · pp. 36–37
• On the simultaneous event, arms are not sampled at resolutions finer than a constant multiple of their gaps, and challengers of the best arm are removed by the corresponding scale.Source: §C.4 · p. 36

D Proofs for Section 4 (Lower bound)

• A hard pair with mean gap Δ limits the information from any single 1-bit query to O(Δ^2/(Jσ^2)).The pair is embedded into a K-arm instance by changing one arm at a time, followed by a change-of-measure argument.Source: D Proofs for Section 4 (Lower bound) · p. 38

D.1 Construction of the hard pair

• The construction uses geometrically spaced support scales and perturbed masses to create distributions with bounded variance and a controlled mean shift.The baseline and perturbed distributions have variance proxy σ^2, and the hard-pair lemma records their moments.Source: §D.1 · p. 38

D.2 A uniform one-query KL bound

• Uniformly over measurable query sets, the hard pair’s induced Bernoulli observations satisfy the one-query KL divergence bound.Only scales where exactly one of the two support points lies in the query set contribute to the probability discrepancy.Source: §D.2 · pp. 39–40

D.3 Embedding and change of measure

• Changing one arm from P− to P+ makes it uniquely optimal, and the per-query KL bound feeds a change-of-measure argument over the interaction transcript.Data processing links δ-correct identification to a lower bound on the expected sample complexity.Source: §D.3 · pp. 41–42

E Detailed algorithms

• The detailed routines use randomized tail-integral threshold queries; the phased routine restarts phase lists and adjusts clipping to the phase resolution.The fixed-clipping routine sets L_ε = 2σ^2/ε, while the phased routine sets L_j = 32σ^2/ρ_j.Source: E Detailed algorithms · pp. 43–44

• The comparison evaluates the estimators on Normal, variance-1 Student-t(5), and shifted-exponential distributions over sample sizes from 10 to 10^7.MAE is averaged over 1,000 Monte Carlo repetitions.Source: §F.1 · pp. 44–45
• The true deterministic bias is evaluated for both estimators under a common nominal bias target of b = 0.1.The passage identifies Table 1 as reporting true bias under this target, but supplies no cell values.Source: Table 1 · p. 45, §F.1 · p. 45
• Before either estimator reaches its bias floor, the [21] estimator’s MAE ratio is close to 2 across all three distributions and grows further for heavy-tailed and asymmetric cases.The baseline’s larger true bias makes its MAE plateau earlier and at a higher level.Source: §F.1 · p. 45, Figure 3 · p. 45

• The comparison uses signed n-sample estimates from 1,000 independent repetitions under the common calibration µ = 1, σ = 1, c = 0, and L = t = 5.Table 2 reports the square root of the empirical variance.Source: §F.2 · p. 46, Table 2 · p. 46
• The [21] baseline’s standard deviation is 1.924–2.090 times the proposed estimator’s, or approximately 3.70–4.37 times its empirical variance.This fixed-budget comparison establishes neither a universal variance ordering nor a sample-complexity rate separation.Source: §F.2 · p. 46, Table 2 · p. 46
• Empirical variance is computed about each estimator’s empirical mean and is distinct from mean squared error, which also includes bias.Source: §F.2 · p. 46

• The evaluation compares FIXEDCLIP, RESTARTPHASE, and REUSEPHASE with full-feedback UGAPE at K = 5, ε = 0.05, and a query cap of N = 20,000.The results average 5,000 Monte Carlo runs per configuration over 10 values of δ from 0.01 to 0.5.Source: §F.3 · pp. 46–47
• The three environments are Bernoulli with uniform suboptimal gaps, Normal with linearly decreasing means, and heavy-tailed Student-t with linearly decreasing means.The settings use a global variance proxy of σ = 0.5; Student-t rewards have three degrees of freedom and are scaled to variance σ^2.Source: §F.3 · p. 46
• For unbounded Normal and Student-t rewards, UGAPE retains full continuous feedback but clips observations around each arm’s anchor using FIXEDCLIP’s scale and adds the clipping bias to its confidence radius.Source: §F.3 · p. 47
• Empirical error frequencies remain at or below the target δ in the tested configurations, but tuning exploration multipliers below theorem values and imposing a query cap do not automatically preserve the proved PAC guarantee.The theorems concern the stated, untuned confidence radii and stopping rules.Source: §F.3 · p. 47

F.4 Compute resources

• The standalone mean-estimation experiments take about 40 minutes, while each Bernoulli, Normal, and Student-t BAI experiment takes about 10 hours.The simulations ran on an Intel Core Ultra 9 285K workstation with 24 cores and 128 GB of RAM.Source: §F.4 · p. 47, NeurIPS Paper Checklist · p. 51

NeurIPS Paper Checklist

• The paper reports specifying synthetic environments, target accuracy, confidence parameters, algorithmic hyperparameters, and Monte Carlo run counts for reproducing the main experiments.Source: NeurIPS Paper Checklist · p. 49
• The checklist states that results average 1,000 to 5,000 independent Monte Carlo runs and distinguishes empirical error rates of tuned BAI implementations from theoretical PAC guarantees.Source: NeurIPS Paper Checklist · p. 51