That work focuses on reward earned during the experiment. [1]} formulates a nonstochastic best-arm identification problem where the focus is on post-experiment performance. In this model, reward sequences can be arbitrary, as long as they have a cesaro limit. The goal is to identify the arm with the best limiting value. [2]} and [3]} provide best-arm identification algorithms with guarantees in the nonstochastic case that still offer competitive performance in the stochastic case relative to algorithms designed for that setting. Especially related to us is the work of [2]}. They show there is an inherent price to being robust against advesarial reward sequences. They provide a robust algorithm whose instance-dependent guarantees in problems with i.i.d rewards are nearly optimal among robust algorithms, but algorithms designed only for the i.i.d setting offer provably better performance in such problems.
