# Scale Free Adversarial Multi Armed Bandits

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 33 references that are in the map.
- First posted on arXiv 8 Jun 2021.

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

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits](https://mlsanity.com/paper/1807.07623/) (2018)
- [More Adaptive Algorithms for Adversarial Bandits](https://mlsanity.com/paper/1801.03265/) (2018)
- [Scale-Free Online Learning](https://mlsanity.com/paper/1601.01974/) (2016)
- [Follow the Leader If You Can, Hedge If You Must](https://mlsanity.com/paper/1301.0534/) (2013)
- [Sparsity, variance and curvature in multi-armed bandits](https://mlsanity.com/paper/1711.01037/) (2017)
- [A Modular Analysis of Adaptive (Non-)Convex Optimization: Optimism, Composite Objectives, and Variational Bounds](https://mlsanity.com/paper/1709.02726/) (2017)
- [Improved Path-length Regret Bounds for Bandits](https://mlsanity.com/paper/1901.10604/) (2019)
- [Exploration by Optimisation in Partial Monitoring](https://mlsanity.com/paper/1907.05772/) (2019)
- [Refined Lower Bounds for Adversarial Bandits](https://mlsanity.com/paper/1605.07416/) (2016)
- [Adaptation to the Range in K-Armed Bandits](https://mlsanity.com/paper/2006.03378/) (2020)
- [Bandit Regret Scaling with the Effective Loss Range](https://mlsanity.com/paper/1705.05091/) (2017)

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

- [Refined Regret for Adversarial MDPs with Linear Function Approximation](https://mlsanity.com/paper/2301.12942/) (2023)
- [uniINF: Best-of-Both-Worlds Algorithm for Parameter-Free Heavy-Tailed MABs](https://mlsanity.com/paper/2410.03284/) (2024)
- [Banker Online Mirror Descent: A Universal Approach for Delayed Online Bandit Learning](https://mlsanity.com/paper/2301.10500/) (2023)
- [BanditQ: Fair Bandits with Guaranteed Rewards](https://mlsanity.com/paper/2304.05219/) (2023)
- [Capacity-Constrained Online Learning with Delays: Scheduling Frameworks and Regret Trade-offs](https://mlsanity.com/paper/2503.19856/) (2025)
- [Improved Algorithms for Adversarial Bandits with Unbounded Losses](https://mlsanity.com/paper/2310.01756/) (2023)
- [Scale-free Adversarial Reinforcement Learning](https://mlsanity.com/paper/2403.00930/) (2024)
- [Scale-Free Adversarial Multi-Armed Bandit with Arbitrary Feedback Delays](https://mlsanity.com/paper/2110.13400/) (2021)
- [Online Learning for Approximately-Convex Functions with Long-term Adversarial Constraints](https://mlsanity.com/paper/2508.16992/) (2025)
- [One-shot acceleration of transient PDE solvers via online-learned preconditioners](https://mlsanity.com/paper/2509.08765/) (2025)
- [α-Fair Contextual Bandits](https://mlsanity.com/paper/2310.14164/) (2023)
- [A Complete Characterization of Learnability for Adversarial Noisy Bandits](https://mlsanity.com/paper/2605.09200/) (2026)

## Abstract (arXiv)

We consider the Scale-Free Adversarial Multi Armed Bandits(MAB) problem. At the beginning of the game, the player only knows the number of arms n. It does not know the scale and magnitude of the losses chosen by the adversary or the number of rounds T. In each round, it sees bandit feedback about the loss vectors l1,dots, lT ∈ ℝn. The goal is to bound its regret as a function of n and norms of l1,dots, lT. We design a bandit Follow The Regularized Leader (FTRL) algorithm, that uses an adaptive learning rate and give two different regret bounds, based on the exploration parameter used. With non-adaptive exploration, our algorithm has a regret of tildeO(√nL2 + L_∞√nT) and with adaptive exploration, it has a regret of tildeO(√nL2 + L_∞√nL1). Here L_∞ = supt | lt|_∞, L2 = sumt=1T |lt|22, L1 = sumt=1T |lt|1 and the tildeO notation suppress logarithmic factors. These are the first MAB bounds that adapt to the |·|2, |·|1 norms of the losses. The second bound is the first data-dependent scale-free MAB bound as T does not directly appear in the regret. We also develop a new technique for obtaining a rich class of local-norm lower-bounds for Bregman Divergences. This technique plays a crucial role in our analysis for controlling the regret when using importance weighted estimators of unbounded losses. This technique could be of independent interest.