Best-arm identification asks a learner to find the arm with the highest reward while interacting with a bandit environment. The new arXiv paper by Abbasi-Yadkori and colleagues studies this problem under two very different reward models: stochastic rewards, drawn from fixed distributions, and adversarial rewards, chosen arbitrarily. A uniform random learner is known to achieve the optimal error rate in the adversarial setting, but the same strategy performs poorly when rewards are stochastic.

The paper's main contribution is an impossibility result. The authors prove that no algorithm can be simultaneously optimal for both settings without knowing which one it faces. More precisely, any strategy that is robust to adversarial rewards can only guarantee optimal error rates on a subset of stochastic problems. They provide a lower bound that characterizes the best possible stochastic error rate under this adversarial-robustness constraint.

To complement the lower bound, the authors design a simple parameter-free algorithm. Its probability of error matches the lower bound up to logarithmic factors in stochastic problems, and it remains robust to adversarial rewards. The paper is a corrected version of a COLT 2018 paper and includes Lean formalizations of the main theoretical results.