Multi-Armed Bandits for Extreme Value Search

33 concepts20 papers1 proposal

Imagine you are drilling for oil across several different territories. Territory A consistently yields a modest 50 barrels of oil per well. Territory B is highly volatile: most wells come up completely dry, but there is a 1% chance of striking a massive reservoir that yields 10,000 barrels.

If your goal is to maximize your total oil production over a thousand wells, you should choose Territory A. But if you only have the resources to operate a single successful well, and a single massive hit is all that matters, Territory B becomes infinitely more valuable.

This is the core intuition behind extreme value search (often formalized as the max $k$-armed bandit problem). While traditional multi-armed bandit frameworks and search heuristics are designed to maximize the cumulative sum or average of rewards, many real-world problems are winner-takes-all. In hyperparameter tuning, combinatorial optimization, and scientific discovery, we do not care about the average performance of our attempts; we care solely about the single best outcome ever discovered.

The Core Mismatch: Why the Mean Fails

Standard optimization and reinforcement learning algorithms rely heavily on expected utility. They track the mean reward of an action and use metrics like the Upper Confidence Bound (UCB) to balance exploration and exploitation. However, as Vincent A. Cicirello and Stephen F. Smith demonstrated when introducing the max $K$-armed bandit framework in The Max K-Armed Bandit: A New Model of Exploration Applied to Search Heuristic Selection, this creates a fundamental objective mismatch. An option with a high average performance might have a very low ceiling, while a highly volatile option might contain the global optimum in its extreme upper tail.

Mathematically, if we pull an arm $t$ times, traditional bandits care about the expected sum $\mathbb{E}[\sum R_t]$, whereas extreme bandits care about the expected maximum $\mathbb{E}[\max R_t]$. As a result, the mean reward becomes entirely irrelevant. Instead, as shown by Yahel David and Nahum Shimkin in PAC Lower Bounds and Efficient Algorithms for The Max (K)-Armed Bandit Problem, the only factor that determines an arm's value is its right-tail behavior—the probability of it producing an extreme outlier.

The Mathematics of Extreme Exploitation

Shifting the objective from the mean to the maximum fundamentally alters how an algorithm must explore. In a standard bandit problem, exploitation means repeatedly pulling the arm with the highest expected value to rack up steady rewards. In an extreme bandit problem, once an arm reveals a high peak value, the strategy must change dramatically.

Vincent A. Cicirello and Stephen F. Smith proved that to successfully find the absolute best solution, an algorithm must increase its trials for the leading option at a double-exponential rate. This aggressive exploitation is necessary because failing to beat the current maximum costs nothing (the maximum remains unchanged), but finding an even higher outlier requires a massive volume of samples from the tail. Building on this, Matthew J. Streeter and Stephen F. Smith delivered the first provably asymptotically optimal algorithm for this setting in An Asymptotically Optimal Algorithm for the Max k-Armed Bandit Problem.

However, extreme value optimization introduces severe theoretical hurdles. In No Regret Bound for Extreme Bandits, David Lopez-Paz et al. proved a striking impossibility result: without making strict assumptions about the underlying reward distributions, it is impossible to guarantee a "no-regret" performance bound. Because extreme outliers are by definition rare, an algorithm can easily be misled.

To bypass this limitation, modern algorithms use robust statistical estimators to track the upper tail without getting tricked by noise. For example:

The mismatch between average-case optimization and extreme-value discovery is particularly glaring in tree search algorithms like Monte Carlo Tree Search (MCTS). Traditionally designed for competitive games like Go or Chess, MCTS evaluates the quality of a search branch by backpropagating the average win rate of simulated games.

But when MCTS is applied to deterministic optimization problems—like finding the shortest route in a Traveling Salesman Problem (TSP) or discovering a formula in Symbolic Regression—averaging outcomes leads the search astray. A branch that contains a single flawless solution might be surrounded by thousands of terrible failures, giving it a low statistical average. Standard MCTS would abandon this branch in favor of a "safe" branch where all solutions are mediocre.

Standard MCTS (Backpropagates Average)
[Branch A] Mean: 75%  ---> PRIORITIZED (Safe, consistent)
[Branch B] Mean: 20%  ---> ABANDONED (High risk, but contains the 100% Global Optimum)

Extreme MCTS (Backpropagates Maximum)
[Branch A] Max:  75%  
[Branch B] Max: 100%  ---> PRIORITIZED (Targets peak potential)

To fix this, researchers have systematically rewritten the value estimation formulas inside tree search:

Real-World Applications: From AutoML to Code Tuning

The practical implications of extreme value optimization span across several high-stakes engineering domains where only the peak performance matters.

Automated Machine Learning (AutoML)

In the Combined Algorithm Selection and Hyperparameter optimization (CASH) problem, the goal is to find the single best-performing model configuration within a strict time budget. In Put CASH on Bandits: A Max K-Armed Problem for Automated Machine Learning, Amir Rezaei Balef et al. showed that optimizing for the maximum potential performance of a model class is far more effective than optimizing for its average performance. They introduced MaxUCB to explicitly model the peak value distribution.

The authors extended this in In-Context Decision Making for Optimizing Complex AutoML Pipelines, using transformers to perform in-context predictions of which optimization paths will yield the highest peak values. To stabilize this process against noise, Yi-Qi Hu proposed the Extreme-Region Upper Confidence Bound (ER-UCB) algorithm in Cascaded Algorithm-Selection and Hyper-Parameter Optimization with Extreme-Region Upper Confidence Bound Bandit, which targets the extreme upper tail of a performance distribution to provide a stable, noise-robust selection mechanism.

High-Performance Code Generation

When compiling or tuning software libraries for specific hardware architectures, developers search through massive spaces of code transformations to find the fastest implementation. Arpad Rimmel et al. tackled this in Bandit-based optimization on graphs with application to library performance tuning by treating library tuning as a max-reward bandit problem over directed acyclic graphs, successfully isolating high-performance outliers up to 10x faster than traditional dynamic programming.

Risk-Seeking Bayesian Optimization

In physical experiments or engineering design under uncertainty, environmental factors introduce uncontrollable noise. In Risk Seeking Bayesian Optimization under Uncertainty for Obtaining Extremum, Shogo Iwazaki et al. formulated a "risk-seeking" Bayesian optimization framework designed specifically to target the upper tail of a distribution, allowing engineers to find "home run" designs that achieve extreme outcomes despite input-dependent noise.

Summary

Whether navigating a massive database to retrieve a single black-box optimal image—as explored by Ryoma Sato in Retrieving Black-box Optimal Images from External Databases—or tuning stochastic parameters by averaging only the top-$k$ best scores (Arpad Rimmel et al. in Optimization of the Nested Monte-Carlo Algorithm on the Traveling Salesman Problem with Time Windows), the core lesson of this research direction remains clear: when you only need to win once, stop optimizing for the average. By shifting the mathematical focus from the mean to the maximum, extreme value optimization provides the theoretical and practical tools needed to hunt down the rarest, highest-value outliers in the computing universe.

Key Foundational Work

The Max K-Armed Bandit: A New Model of Exploration Applied to Search Heuristic Selection (2005) — contributed 3 concept elements to this direction.
An Asymptotically Optimal Algorithm for the Max k-Armed Bandit Problem (2006) — contributed 3 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 18 papers
  2. Version 1 · 2026-10-04 · 18 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_extreme_value_optimization_d739213f,
  title = {extreme value optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/extreme-value-optimization/rdr_d739213fdcd94396bb9db2c01d5d30a9},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 2, frozen text):

@misc{lacuna_extreme_value_optimization_d739213f_v2,
  title = {extreme value optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/extreme-value-optimization/rdr_d739213fdcd94396bb9db2c01d5d30a9/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake