# No Regret Bound for Extreme Bandits

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Aug 2015.

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

- [Extreme Bandits using Robust Statistics](https://mlsanity.com/paper/2109.04433/) (2021)
- [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)
- [Unified theory of upper confidence bound policies for bandit problems targeting total reward, maximal reward, and more](https://mlsanity.com/paper/2411.00339/) (2024)
- [In-Context Decision Making for Optimizing Complex AutoML Pipelines](https://mlsanity.com/paper/2508.13657/) (2025)
- [Theoretical Foundations of max@k Reinforcement Learning](https://mlsanity.com/paper/2607.17823/) (2026)
- [Equal-Budget Monte Carlo Tree Search versus Randomized-Restart List Scheduling for DAG Workflows: A Controlled Equal-Budget Computational Study](https://mlsanity.com/paper/2610.12542/) (2026)

## Abstract (arXiv)

Algorithms for hyperparameter optimization abound, all of which work well under different and often unverifiable assumptions. Motivated by the general challenge of sequentially choosing which algorithm to use, we study the more specific task of choosing among distributions to use for random hyperparameter optimization. This work is naturally framed in the extreme bandit setting, which deals with sequentially choosing which distribution from a collection to sample in order to minimize (maximize) the single best cost (reward). Whereas the distributions in the standard bandit setting are primarily characterized by their means, a number of subtleties arise when we care about the minimal cost as opposed to the average cost. For example, there may not be a well-defined "best" distribution as there is in the standard bandit setting. The best distribution depends on the rewards that have been obtained and on the remaining time horizon. Whereas in the standard bandit setting, it is sensible to compare policies with an oracle which plays the single best arm, in the extreme bandit setting, there are multiple sensible oracle models. We define a sensible notion of "extreme regret" in the extreme bandit setting, which parallels the concept of regret in the standard bandit setting. We then prove that no policy can asymptotically achieve no extreme regret.