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

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.

Bayesian Fixed-Confidence Best-Arm Identification with Abstention
Yuqi Huang, Yunlong Hou, Vincent Y. F. Tan
arXiv21 Oct 2026PreprintCC BY 4.0Full textGeneral mathematicsarXiv
Optimal no-feedback card guessing after a fixed number of riffle shuffles
Tipaluck Krityakierne, Thotsaporn Aek Thanatipanonda
arXiv3 Nov 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematics ProbabilityarXiv
Asymptotically Optimal Best Arm Identification with Fixed-Budget under Differential Privacy
Keqin Chen, Jie Bian, Yulian Wu +1
arXiv3 Oct 2026PreprintCC BY 4.0Full textGeneral mathematicsarXiv
FOCUS: Fixed-Confidence Online Causal Learning Using Sequential Adaptive Interventions
Haijie Xu, Chen Zhang
arXiv26 Sep 2026PreprintarXiv licenceFull textStatisticsarXiv
Nearly optimal Kolmogorov widths under holomorphic mappings
Yuwen Li, Guozhi Zhang
arXiv1 Oct 2026PreprintarXiv licenceFull textAnalysis & PDEsarXiv

Cite

BibTeX RIS

BibTeX

@misc{luong2026nearly,
  title = {{Nearly Optimal Fixed-Confidence Best-Arm Identification with 1-Bit Feedback}},
  author = {Khang Luong and Dinh Thai Son and Hoang Ta and Hung The Tran and Tuan Quang Dam},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.02771},
  eprint = {2610.02771},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.02771},
}

RIS

TY  - UNPB
TI  - Nearly Optimal Fixed-Confidence Best-Arm Identification with 1-Bit Feedback
AU  - Khang Luong
AU  - Dinh Thai Son
AU  - Hoang Ta
AU  - Hung The Tran
AU  - Tuan Quang Dam
PY  - 2026
DA  - 2026/10/02
PB  - arXiv
DO  - 10.48550/arxiv.2610.02771
UR  - https://arxiv.org/abs/2610.02771
AB  - 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.
ER  -

Abstract

Related

Cite