← News

ResearchSources: arXiv · 16 Nov 2026

Researchers design best-arm identification algorithms for strict 1-bit feedback

An arXiv paper proposes a mean-estimation primitive and two algorithms for identifying the best arm when each round returns only one bit, with matching lower bounds.

In plain words

The paper studies a problem where a learner must find the best option among several, but each test returns only a single bit saying whether the observed reward fell inside a chosen range. Because averages cannot be computed directly in this setting, the authors build an estimation method from randomized threshold queries and use it in two algorithms for finding the best arm.

What was announced

The work addresses fixed-confidence best-arm identification under strict 1-bit feedback: at each round the learner picks an arm and a query set, and receives one bit indicating whether the sampled reward belongs to that set. The authors consider a distribution-free finite-variance setting with arm-wise localization, where direct empirical mean estimation is unavailable and clipping becomes unavoidable. They first formulate a time-uniform 1-bit mean-estimation primitive based on randomized threshold queries and a clipped tail-integral identity, then embed it into candidate-challenger identification algorithms.

Two variants emerge. A fixed-clipping algorithm gives a simple anytime (ε,δ)-PAC guarantee, while a phased adaptive-clipping algorithm matches its clipping level to the current resolution and yields a gap-adaptive sample complexity. The authors also prove a K-arm worst-case information-theoretic lower bound, arguing 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 logarithmic factors.

What it does not show

  • The source is an abstract only; the paper's full proofs, experiments and practical performance are not covered by the supplied passages.
  • No independent evaluation or implementation results are reported in the provided material.

Sources

Source-support review completed 17 Nov 2026. This story was drafted with AI assistance and checked against retained source passages. Automated checking is not independent verification.

Coverage: arXiv: abstract.

Updates and corrections

No corrections so far.

First published 17 Nov 2026

New to the subject? AI from the Ground Up starts from the beginning.