Research map / Bandits and online learning / Multi-armed bandits

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

NeurIPS 2026 · Bandits and online learning › Multi-armed bandits · approach: Fixed-confidence versus fixed-budget identification · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Studies fixed-confidence best-arm identification where each pull returns only one bit (a threshold/set query), using a randomized-threshold clipped 1-bit mean estimator inside candidate-challenger BAI with fixed and phased adaptive clipping, plus a K-arm lower bound.

Problem

Fixed-confidence best-arm identification when the learner receives only a single bit per pull indicating whether the reward lies in a queried set, under only finite-variance reward distributions with known anchors.

Approach

A randomized-threshold 1-bit estimator built on a clipped tail-integral identity yields a time-uniform confidence sequence for arm means, which is embedded in UGapE-style candidate-challenger BAI; phased adaptive clipping matches the clipping level to the current resolution to obtain gap-adaptive complexity with a matching-up-to-loglog lower bound.

Key results

• Phased adaptive clipping uses fewer queries than fixed clipping on instances with heterogeneous gaps (Normal and Student-t settings).
• Theory: K-arm equal-gap lower bound of order (K-1) sigma^2/Delta^2 log(sigma/Delta) log(1/delta) matches the phased upper bound's leading dependence up to log log factors.
• Standalone 1-bit estimator achieves lower MAE and smaller bias floor than the Lau-Scarlett baseline in simulations.

Limitations

• Requires known anchor points c_k with |mu_k - c_k| <= sigma (or obtained via MedianEst with known bounded range).
• Lower bound is worst-case over K-arm equal-gap instances, not instance-optimal for expected complexity on every instance.
• Known variance proxy sigma is assumed.

Experimental setup

Benchmarks: simulated bandit instances (Bernoulli, Normal, Student-t)

Metrics: mean absolute error stopping round / sample complexity

Baselines: UGapE Lau-Scarlett 1-bit mean estimator FixedClip-1BitBAI

Builds on: UGapE Lau-Scarlett 1-bit mean estimation Bernstein inequality

Closest papers by meaning

• Optimal Multi-Fidelity Best-Arm Identification (NeurIPS 2024 · similarity 0.90)
• Fixing the Loose Brake: Exponential-Tailed Stopping Time in Best Arm Identification (ICML 2025 · similarity 0.89)
• Best Arm Identification in Generalized Linear Bandits via Hybrid Feedback (NeurIPS 2026 · similarity 0.88)
• Optimal Batched Best Arm Identification (NeurIPS 2024 · similarity 0.88)
• Fixed Confidence Best Arm Identification in the Bayesian Setting (NeurIPS 2024 · similarity 0.88)
• Balancing Performance and Costs in Best Arm Identification (NeurIPS 2025 · similarity 0.87)