Banker Online Mirror Descent

Abstract

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.

arXiv commentPreliminary work, merged to arXiv:2301.10500

References in corpus (10)

• A Contextual-Bandit Approach to Personalized News Article Recommendation
• The best of both worlds: stochastic and adversarial bandits
• More Adaptive Algorithms for Adversarial Bandits
• Delay and Cooperation in Nonstochastic Bandits
• Bandits with Delayed, Aggregated Anonymous Feedback
• An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial bandits
• Nonstochastic Bandits with Composite Anonymous Feedback
• Fighting Bandits with a New Kind of Smoothness
• An Optimal Algorithm for Adversarial Bandits with Arbitrary Delays
• Linear Bandits with Stochastic Delayed Feedback

Cited by in corpus (1)

• Scale-Free Adversarial Multi-Armed Bandit with Arbitrary Feedback Delays