Banker Online Mirror Descent: A Universal Approach for Delayed Online Bandit Learning

We propose Banker Online Mirror Descent (Banker-OMD), a novel framework generalizing the classical Online Mirror Descent (OMD) technique in the online learning literature. The Banker-OMD framework almost completely decouples feedback delay handling and the task-specific OMD algorithm design, thus facilitating the design of new algorithms capable of efficiently and robustly handling feedback delays. Specifically, it offers a general methodology for achieving $\tilde{\mathcal{O}}(\sqrt{T}+\sqrt{D})$-style regret bounds in online bandit learning tasks with delayed feedback, where $T$ is the number of rounds and $D$ is the total feedback delay. We demonstrate the power of $\mathtt{\text{Banker-OMD}}$ by applications to two important bandit learning scenarios with delayed feedback, including delayed scale-free adversarial Multi-Armed Bandits (MAB) and delayed adversarial linear bandits. $\mathtt{\text{Banker-OMD}}$ leads to the first delayed scale-free adversarial MAB algorithm achieving $\tilde{\mathcal{O}}(\sqrt{K}L(\sqrt{T}+\sqrt{D}))$ regret and the first delayed adversarial linear bandit algorithm achieving $\tilde{\mathcal{O}}(\text{poly}(n)(\sqrt{T}+\sqrt{D}))$ regret. As a corollary, the first application also implies $\tilde{\mathcal{O}}(\sqrt{KT}L)$ regret for non-delayed scale-free adversarial MABs, which is the first to match the $\mathrm{\Omega }(\sqrt{KT}L)$ lower bound up to logarithmic factors and can be of independent interest.