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

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 24 references that are in the map.
- First posted on arXiv 26 Oct 2021.

## Builds on (most cited first, 16 of 16)

- [More Adaptive Algorithms for Adversarial Bandits](https://mlsanity.com/paper/1801.03265/) (2018)
- [Corralling a Band of Bandit Algorithms](https://mlsanity.com/paper/1612.06246/) (2016)
- [Scale-Free Online Learning](https://mlsanity.com/paper/1601.01974/) (2016)
- [Delay and Cooperation in Nonstochastic Bandits](https://mlsanity.com/paper/1602.04741/) (2016)
- [Follow the Leader If You Can, Hedge If You Must](https://mlsanity.com/paper/1301.0534/) (2013)
- [Fighting Bandits with a New Kind of Smoothness](https://mlsanity.com/paper/1512.04152/) (2015)
- [Nonstochastic Multiarmed Bandits with Unrestricted Delays](https://mlsanity.com/paper/1906.00670/) (2019)
- [An Optimal Algorithm for Adversarial Bandits with Arbitrary Delays](https://mlsanity.com/paper/1910.06054/) (2019)
- [Learning Adversarial Markov Decision Processes with Delayed Feedback](https://mlsanity.com/paper/2012.14843/) (2020)
- [Adapting to Delays and Data in Adversarial Multi-Armed Bandits](https://mlsanity.com/paper/2010.06022/) (2020)
- [First-order regret bounds for combinatorial semi-bandits](https://mlsanity.com/paper/1502.06354/) (2015)
- [Connections Between Mirror Descent, Thompson Sampling and the Information Ratio](https://mlsanity.com/paper/1905.11817/) (2019)
- [Exploration by Optimisation in Partial Monitoring](https://mlsanity.com/paper/1907.05772/) (2019)
- [Adaptation to the Range in K-Armed Bandits](https://mlsanity.com/paper/2006.03378/) (2020)
- [Scale Free Adversarial Multi Armed Bandits](https://mlsanity.com/paper/2106.04700/) (2021)
- [Banker Online Mirror Descent](https://mlsanity.com/paper/2106.08943/) (2021)

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

- [Isotuning With Applications To Scale-Free Online Learning](https://mlsanity.com/paper/2112.14586/) (2021)

## Abstract (arXiv)

We consider the Scale-Free Adversarial Multi-Armed Bandit (MAB) problem with unrestricted feedback delays. In contrast to the standard assumption that all losses are [0,1]-bounded, in our setting, losses can fall in a general bounded interval [-L, L], unknown to the agent beforehand. Furthermore, the feedback of each arm pull can experience arbitrary delays. We propose a novel approach named Scale-Free Delayed INF (SFD-INF) for this novel setting, which combines a recent "convex combination trick" together with a novel doubling and skipping technique. We then present two instances of SFD-INF, each with carefully designed delay-adapted learning scales. The first one SFD-TINF uses frac 12-Tsallis entropy regularizer and can achieve widetildemathcal O(√K(D+T)L) regret when the losses are non-negative, where K is the number of actions, T is the number of steps, and D is the total feedback delay. This bound nearly matches the Omega((√KT+√Dlog K)L) lower-bound when regarding K as a constant independent of T. The second one, SFD-LBINF, works for general scale-free losses and achieves a small-loss style adaptive regret bound widetildemathcal O(√KmathbbE[tildemathfrak LT2]+√KDL), which falls to the widetildemathcal O(√K(D+T)L) regret in the worst case and is thus more general than SFD-TINF despite a more complicated analysis and several extra logarithmic dependencies. Moreover, both instances also outperform the existing algorithms for non-delayed (i.e., D=0) scale-free adversarial MAB problems, which can be of independent interest.