Fetching the paper…

Reading the bibliography…

2019

An Optimal Algorithm for Adversarial Bandits with Arbitrary Delays

Zimmert, Julian, Seldin, Yevgeny

Original
PDF
Post on X

Understand

We propose a new algorithm for adversarial multi-armed bandits with unrestricted delays.

The algorithm is based on a novel hybrid regularizer applied in the Follow the Regularized Leader (FTRL) framework.
It achieves $\mathcal{O}(\sqrt{kn}+\sqrt{D\log(k)})$ regret guarantee, where $k$ is the number of arms, $n$ is the number of rounds, and $D$ is the total delay.
The result matches the lower bound within constants and requires no prior knowledge of $n$ or $D$.

An Optimal Algorithm for Adversarial Bandits with Arbitrary Delays · Around

Built on

Prediction with limited advice and multiarmed bandits with paid observations
Yevgeny Seldin, Peter L. Bartlett, Koby Crammer, and Yasin Abbasi-Yadkori · 2014
Earlier work this paper cites.
Delay and cooperation in nonstochastic bandits
Nicolò Cesa-Bianchi, Claudio Gentile, Yishay Mansour, and Alberto Minora · 2016
Earlier work this paper cites.
Delay-tolerant online convex optimization: Unified analysis and adaptive-gradient algorithms
Pooria Joulani, Andras Gyorgy, and Csaba Szepesvári · 2016
Earlier work this paper cites.
Sparsity, variance and curvature in multi-armed bandits
Sébastien Bubeck, Michael B. Cohen, and Yuanzhi Li · 2018
Earlier work this paper cites.

Similar

Nonstochastic bandits with composite anonymous feedback
Nicolo Cesa-Bianchi, Claudio Gentile, and Yishay Mansour · 2018
Cited alongside, same era.
Efficient online portfolio with logarithmic regret
Haipeng Luo, Chen-Yu Wei, and Kai Zheng · 2018
Cited alongside, same era.
Online exp3 learning in adversarial bandits with delayed feedback
Ilai Bistritz, Zhengyuan Zhou, Xi Chen, Nicholas Bambos, and Jose Blanchet · 2019
Cited alongside, same era.
Bandit Algorithms
Tor Lattimore and Csaba Szepesvári · 2019
Cited alongside, same era.

Then

On first-order bounds, variance and gap-dependent bounds for adversarial bandits
Roman Pogodin and Tor Lattimore · 2019
Closest in time.
Nonstochastic multiarmed bandits with unrestricted delays
Tobias Sommer Thune, Nicolò Cesa-Bianchi, and Yevgeny Seldin · 2019
Closest in time.
An optimal algorithm for stochastic and adversarial bandits
Julian Zimmert and Yevgeny Seldin · 2019
Closest in time.
Beating stochastic and adversarial semi-bandits optimally and simultaneously
Julian Zimmert, Haipeng Luo, and Chen-Yu Wei · 2019
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…