A new algorithm can still crown the best option in a multi-armed bandit test even when every round of feedback is reduced to a single bit.
The setup: a learner repeatedly picks an arm and a query set, then gets back only a yes-or-no signal on whether the sampled reward landed inside that set - never the reward itself. Researchers built a 1-bit mean-estimation method using randomized threshold queries, since ordinary averaging is impossible without seeing actual values. They then used it in two algorithms: a simple fixed-clipping version with an anytime accuracy guarantee, and a phased adaptive-clipping version that tightens its queries as it narrows down the answer, achieving better sample efficiency. The team also proved a matching lower bound for any number of arms, showing that a logarithmic efficiency penalty from this extreme feedback limit is unavoidable, not just a gap in their method.
This matters because most bandit algorithms - the ones behind A/B tests, ad auctions, and clinical trial designs - assume you can measure the actual outcome. Here, the result quantifies exactly what you give up when you can't: systems limited by privacy rules, coarse sensors, or bandwidth can still find the best option, just slower, and now there's a precise number for how much slower.
It is an elegant proof, not a product: the gains are measured in asymptotic log terms, and there is no mention of the algorithm surviving contact with a real dataset.