# Efficient Algorithms for Extreme Bandits

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 22 references that are in the map.
- First posted on arXiv 21 Mar 2022.

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

- [No Regret Bound for Extreme Bandits](https://mlsanity.com/paper/1508.02933/) (2015)
- [Max K-armed bandit: On the ExtremeHunter algorithm and beyond](https://mlsanity.com/paper/1707.08820/) (2017)
- [Sub-sampling for Efficient Non-Parametric Bandit Exploration](https://mlsanity.com/paper/2010.14323/) (2020)
- [On Limited-Memory Subsampling Strategies for Bandits](https://mlsanity.com/paper/2106.10935/) (2021)
- [Extreme Bandits using Robust Statistics](https://mlsanity.com/paper/2109.04433/) (2021)

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

- [Put CASH on Bandits: A Max K-Armed Problem for Automated Machine Learning](https://mlsanity.com/paper/2505.05226/) (2025)
- [Theoretical Foundations of max@k Reinforcement Learning](https://mlsanity.com/paper/2607.17823/) (2026)

## Abstract (arXiv)

In this paper, we contribute to the Extreme Bandit problem, a variant of Multi-Armed Bandits in which the learner seeks to collect the largest possible reward. We first study the concentration of the maximum of i.i.d random variables under mild assumptions on the tail of the rewards distributions. This analysis motivates the introduction of Quantile of Maxima (QoMax). The properties of QoMax are sufficient to build an Explore-Then-Commit (ETC) strategy, QoMax-ETC, achieving strong asymptotic guarantees despite its simplicity. We then propose and analyze a more adaptive, anytime algorithm, QoMax-SDA, which combines QoMax with a subsampling method recently introduced by Baudry et al. (2021). Both algorithms are more efficient than existing approaches in two aspects (1) they lead to better empirical performance (2) they enjoy a significant reduction of the memory and time complexities.