cs.LGOct 2, 2026

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

Authors: Khang Luong, Dinh Thai Son, Hoang Ta, Hung The Tran, Tuan Quang Dam

Organizations: Hanoi University of Science and Technology · Quantum AI & Cyber Security Institute, FPT Corporation

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

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 KK-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⁡\log\log factors.

Figures & tables

Figure 1: Mean absolute error E∣μ^n−μ∣\mathbb{E}|\hat{\mu}_{n}-\mu| over the number of 1-bit queries nn for our estimator and the estimator of [ 20 ] (mean ±σ\pm\sigma over runs). For readability, bias lines below 10−310^{-3} are not shown.
Figure 2: Stopping rounds of best-arm identification algorithms as a function of the confidence parameter δ\delta (mean ±σ\pm\sigma over runs).
Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

 jt=min⁡{j∈{1,…,n−1}:∑i=1jwt(i)≥12}.j_{t}=\min\left\{j\in\{1,\dots,n-1\}:\sum_{i=1}^{j}w_{t}(i)\geq\frac{1}{2}\right\}. 
Appendix
Algorithm 1 MedianEst : 1-Bit Anchor Estimation
DistributionBoursB_{\mathrm{ours}}BLSB_{\mathrm{LS}}
Normal7.15×10−67.15\times 10^{-6}1.66×10−41.66\times 10^{-4}
Student- t(5)t(5)1.56×10−31.56\times 10^{-3}9.06×10−39.06\times 10^{-3}
Exponential6.74×10−36.74\times 10^{-3}4.04×10−24.04\times 10^{-2}
Appendix
Table 1: True bias under the common theoretic bias target b=0.1b=0.1 .
Figure 3: Ratio MAELS(n)/MAEours(n)\mathrm{MAE}_{\mathrm{LS}}(n)/\mathrm{MAE}_{\mathrm{ours}}(n) as a function of nn . Values above 11 indicate that the [ 20 ] estimator has larger error.
DistributionnnStd. (ours)Std. (Lau–Scarlett)Ratio (LS/ours)
Normal10410^{4}0.025150.025150.049170.049171.9551.955
 10510^{5}0.0078060.0078060.016240.016242.0812.081
 10610^{6}0.0024720.0024720.0051660.0051662.0902.090
 10710^{7}0.00078600.00078600.0015370.0015371.9561.956
Student- t(5)t(5)10410^{4}0.025320.025320.049950.049951.9731.973
 10510^{5}0.0077990.0077990.015850.015852.0332.033
Appendix
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.

Explore similar work

CardsList

  1. Fundamental Limitations of Fixed-Budget Best-Arm Identification

    Jul 13, 2026Motti GoldbergerMulti-Armed BanditsBest-Arm Identification

    Yale University

  2. On The Complexity of Best-Arm Identification in Non-Stationary Linear Bandits

    Mar 11, 2026Leo Maynard-Zhang, Zhihan Xiong, Kevin Jamieson +1Multi-Armed BanditsBest-Arm Identification

    University of Washington

  3. Fixed-Budget Constrained Best Arm Identification in Grouped Bandits

    Mar 4, 2026Raunak Mukherjee, Sharayu MoharirBest-Arm IdentificationMulti-Armed Bandits

    Indian Institute of Technology, Bombay · Dept. of Electrical Engineering, IIT Bombay