# Extreme Bandits using Robust Statistics

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 44 references that are in the map.
- First posted on arXiv 9 Sep 2021.

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

- [Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization](https://mlsanity.com/paper/1603.06560/) (2016)
- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits](https://mlsanity.com/paper/1312.7308/) (2013)
- [Algorithms for multi-armed bandit problems](https://mlsanity.com/paper/1402.6028/) (2014)
- [Multi-Armed Bandit Based Client Scheduling for Federated Learning](https://mlsanity.com/paper/2007.02315/) (2020)
- [Thompson Sampling for 1-Dimensional Exponential Family Bandits](https://mlsanity.com/paper/1307.3400/) (2013)
- [No Regret Bound for Extreme Bandits](https://mlsanity.com/paper/1508.02933/) (2015)
- [Regret Analysis of the Finite-Horizon Gittins Index Strategy for Multi-Armed Bandits](https://mlsanity.com/paper/1511.06014/) (2015)
- [Max K-armed bandit: On the ExtremeHunter algorithm and beyond](https://mlsanity.com/paper/1707.08820/) (2017)

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

- [Put CASH on Bandits: A Max K-Armed Problem for Automated Machine Learning](https://mlsanity.com/paper/2505.05226/) (2025)
- [Materials Discovery using Max K-Armed Bandit](https://mlsanity.com/paper/2212.08225/) (2022)
- [Efficient Algorithms for Extreme Bandits](https://mlsanity.com/paper/2203.10883/) (2022)
- [On Penalization in Stochastic Multi-armed Bandits](https://mlsanity.com/paper/2211.08311/) (2022)

## Abstract (arXiv)

We consider a multi-armed bandit problem motivated by situations where only the extreme values, as opposed to expected values in the classical bandit setting, are of interest. We propose distribution free algorithms using robust statistics and characterize the statistical properties. We show that the provided algorithms achieve vanishing extremal regret under weaker conditions than existing algorithms. Performance of the algorithms is demonstrated for the finite-sample setting using numerical experiments. The results show superior performance of the proposed algorithms compared to the well known algorithms.