← All papers
First page of Best of both worlds: Stochastic & adversarial best-arm identification

Best of both worlds: Stochastic & adversarial best-arm identification

Yasin Abbasi-Yadkori, Peter L. Bartlett, Victor Gabillon, Alan Malek, Michal Valko

stat.ML Apr 16, 2026 · v2 cs.LG
The paper's principal theoretical results on best-arm identification error rates and lower bounds were formalized in Lean 4.
We study bandit best-arm identification with arbitrary and potentially adversarial rewards. A simple random uniform learner obtains the optimal rate of error in the adversarial scenario. However, this type of strategy is suboptimal when the rewards are sampled stochastically. Therefore, we ask: Can we design a learner that performs optimally in both the stochastic and adversarial problems while not being aware of the nature of the rewards? First, we show that designing such a learner is impossible in general. In particular, to be robust to adversarial rewards, we can only guarantee optimal rates of error on a subset of the stochastic problems. We give a lower bound that characterizes the optimal rate in stochastic problems if the strategy is constrained to be robust to adversarial rewards. Finally, we design a simple parameter-free algorithm and show that its probability of error matches (up to log factors) the lower bound in stochastic problems, and it is also robust to adversarial ones.

Bandit best-arm identification is studied when rewards may be stochastic or adversarial and the learner does not know which. Uniform random sampling is optimal against adversarial rewards but suboptimal for stochastic ones.

The authors first prove that no single learner can be optimal in both settings in general. They derive a lower bound on the optimal stochastic error rate for strategies constrained to be robust to adversarial rewards. They then design a simple parameter-free algorithm and analyze its probability of error. The principal theoretical results were formalized in Lean 4.

The algorithm's error probability matches the lower bound up to log factors in stochastic problems while remaining robust to adversarial rewards.