# Improved Algorithms for Adversarial Bandits with Unbounded Losses

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 30 references that are in the map.
- First posted on arXiv 3 Oct 2023.

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

- [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)
- [Multi-armed Bandit Models for the Optimal Design of Clinical Trials: Benefits and Challenges](https://mlsanity.com/paper/1507.08025/) (2015)
- [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)
- [Scale-Free Algorithms for Online Linear Optimization](https://mlsanity.com/paper/1502.05744/) (2015)
- [Unconstrained Online Learning with Unbounded Losses](https://mlsanity.com/paper/2306.04923/) (2023)
- [Sparsity, variance and curvature in multi-armed bandits](https://mlsanity.com/paper/1711.01037/) (2017)
- [Improved Path-length Regret Bounds for Bandits](https://mlsanity.com/paper/1901.10604/) (2019)
- [Adaptation to the Range in K-Armed Bandits](https://mlsanity.com/paper/2006.03378/) (2020)
- [Scale-free Unconstrained Online Learning for Curved Losses](https://mlsanity.com/paper/2202.05630/) (2022)
- [Scale Free Adversarial Multi Armed Bandits](https://mlsanity.com/paper/2106.04700/) (2021)
- [Banker Online Mirror Descent: A Universal Approach for Delayed Online Bandit Learning](https://mlsanity.com/paper/2301.10500/) (2023)

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

- [uniINF: Best-of-Both-Worlds Algorithm for Parameter-Free Heavy-Tailed MABs](https://mlsanity.com/paper/2410.03284/) (2024)
- [Scale-free Adversarial Reinforcement Learning](https://mlsanity.com/paper/2403.00930/) (2024)
- [State-free Reinforcement Learning](https://mlsanity.com/paper/2409.18439/) (2024)

## Abstract (arXiv)

We consider the Adversarial Multi-Armed Bandits (MAB) problem with unbounded losses, where the algorithms have no prior knowledge on the sizes of the losses. We present UMAB-NN and UMAB-G, two algorithms for non-negative and general unbounded loss respectively. For non-negative unbounded loss, UMAB-NN achieves the first adaptive and scale free regret bound without uniform exploration. Built up on that, we further develop UMAB-G that can learn from arbitrary unbounded loss. Our analysis reveals the asymmetry between positive and negative losses in the MAB problem and provide additional insights. We also accompany our theoretical findings with extensive empirical evaluations, showing that our algorithms consistently out-performs all existing algorithms that handles unbounded losses.