Robustness comes at a cost, and so [1]} design an algorithm that attains the “best-of-both worlds”. Their procedure behaves like an algorithm designed to work with i.i.d observations, and switches to behave like nonstochastic bandit algorithm if it detects that nature is not i.i.d. They prove both robustness in the nonstochastic world and a result about efficient adaptivity in the i.i.d world.
