Nearly Optimal Best-of-Both-Worlds Guarantees for Delayed Multi-Armed Bandits.

We study multi-armed bandits with delayed feedback. Our goal is to provide best-of-both-worlds regret guarantees, which is to say, guarantee optimal performance in both stochastic and adversarial environments. To this end, we propose a new version of Follow-the-Regularized-Leader (FTRL) with a time-varying hybrid regularizer combining Tsallis entropy and KL divergence. The novelty of the algorithm is in the learning rate for the KL divergence, which tracks the drift of the iterates of the algorithm. This allows the amount of regularization to respond directly to the drift induced by delayed observations. In the stochastic setting, our algorithm guarantees a regret of $O\left({\sum }_{i\ne i^{\star }}\frac{\log T}{\Delta (i)}+d_{\max }\sqrt{K}\right),$ where $\Delta (i)$ denotes the suboptimality gap of arm $i$, $T$ is the number of rounds, $d_{\max }$ is the maximum delay, and $K$ is the number of actions. On the other hand, in the adversarial setting, the same algorithm guarantees a regret of $O\left(\sqrt{KT}+\sqrt{D\log K}+d_{\max }\sqrt{K}\right)$, where $D$ is the total delay. The algorithm requires neither prior knowledge of the total delay $D$ nor knowledge of whether the environment is stochastic or adversarial. In both the stochastic and adversarial settings, these guarantees are optimal up to the $d_{\max }\sqrt{K}$ term. Additionally, we compare our new algorithm with prior state-of-the-art algorithms through synthetic experiments.