# Banker Online Mirror Descent

arXiv: https://arxiv.org/abs/2106.08943 · HTML: https://mlsanity.com/paper/2106.08943/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Jun 2021.

## Built on by (most cited first, 1 of 1)

- [Scale-Free Adversarial Multi-Armed Bandit with Arbitrary Feedback Delays](https://mlsanity.com/paper/2110.13400/) (2021)

## Abstract (arXiv)

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 tildeO(√T + √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 tildeO(poly(n)(√T + √D)) regret.