Banker Online Mirror Descent
  We propose Banker-OMD, a novel framework generalizing the classical Online
Mirror Descent (OMD) technique in online learning algorithm design. Banker-OMD
allows algorithms to robustly handle delayed feedback, and offers a general
methodology for achieving $\tilde{O}(\sqrt{T} + \sqrt{D})$-style regret bounds
in various delayed-feedback online learning tasks, where $T$ is the time
horizon length and $D$ is the total feedback delay. We demonstrate the power of
Banker-OMD with applications to three important bandit scenarios with delayed
feedback, including delayed adversarial Multi-armed bandits (MAB), delayed
adversarial linear bandits, and a novel delayed best-of-both-worlds MAB
setting. Banker-OMD achieves nearly-optimal performance in all the three
settings. In particular, it leads to the first delayed adversarial linear
bandit algorithm achieving $\tilde{O}(\text{poly}(n)(\sqrt{T} + \sqrt{D}))$
regret.
