Max k-Armed Bandits for Extreme Value Discovery

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 218 papers26 conceptsfrozen 2026-10-04

In the classic multi-armed bandit problem, an agent pulls levers to maximize the total sum of rewards over time. This is the logic of a steady paycheck: you want the arm with the highest average payout. However, in many high-stakes domains—like searching for a breakthrough mathematical formula, tuning a high-performance compiler, or finding the best hyperparameter configuration for a neural network—the average doesn't matter. You are looking for the jackpot.

This shift in objective defines the Max $k$-Armed Bandit (or Extreme Bandit) problem. Instead of maximizing the expected sum, the goal is to maximize the maximum reward observed across all trials.

The Failure of the Mean

Standard bandit algorithms like UCB (Upper Confidence Bound) are designed to identify the arm with the highest mean. But as Vincent A. Cicirello and Stephen F. Smith argue in The Max K-Armed Bandit: A New Model of Exploration Applied to Search Heuristic Selection, the "best" arm in a max-bandit setting might actually have a lower average than its peers, provided it has a "heavy tail" capable of producing rare, extreme outliers.

Consider two search heuristics: one that consistently delivers "good" results and another that mostly fails but occasionally finds a "perfect" solution. A standard bandit would quickly abandon the second heuristic because its average is abysmal. A max-bandit algorithm, however, recognizes that the second heuristic is the only one capable of winning the game.

Hunting for the Tail

To find these "superstar" samples, researchers have turned to Extreme Value Theory (EVT). The core intuition is that the maximum value of a distribution is governed by its "tail index"—a parameter that describes how likely the distribution is to produce extreme outliers.

In Max K-Armed Bandit: On the ExtremeHunter Algorithm and Beyond, Mastane Achab, Claire Vernade, and colleagues demonstrate that the problem of finding the highest single reward can be reduced to finding the arm with the heaviest tail. Their ExtremeHunter algorithm estimates these tail indices to prioritize arms that are "risky" in the right way.

Other approaches, such as the QoMax estimator introduced by Dorian Baudry and Emilie Kaufmann in Efficient Algorithms for Extreme Bandits, use the "Quantile of Maxima" to track potential peaks with much lower computational overhead than traditional methods.

Aggressive Exploitation

One of the most counterintuitive findings in this field is the required rate of exploitation. In standard bandits, we explore for a long time to ensure we haven't missed a slightly better mean. But in the max-bandit setting, Matthew J. Streeter and Stephen F. Smith proved in An Asymptotically Optimal Algorithm for the Max k-Armed Bandit Problem that the optimal strategy involves increasing trials for the leading arm at a double-exponential rate.

This aggressive exploitation is necessary because every trial spent on a sub-optimal arm is not just a loss of "average" reward, but a lost opportunity to push the "record" further on the best arm. As Eren Ozbay and Vijay Kamble show in Training a Single Bandit Arm, this makes the "max" objective fundamentally harder than the "sum" objective, as resources must be concentrated heavily on the most promising candidate to reach its true potential.

The max-bandit framework has proven particularly powerful for "Combined Algorithm Selection and Hyperparameter optimization" (CASH). In Put CASH on Bandits: A Max K-Armed Problem for Automated Machine Learning, Amir Rezaei Balef and Claire Vernade introduce MaxUCB, which outperforms standard AutoML by focusing on the "ceiling" of a model's performance rather than its average.

Similarly, in the realm of Symbolic Regression, Zhengyao Huang and colleagues apply these principles to Monte Carlo Tree Search in Improving Monte Carlo Tree Search for Symbolic Regression. By prioritizing search branches based on their potential to yield a global maximum, they can navigate the near-infinite space of mathematical formulas more effectively than methods seeking high-performing "average" branches.

Whether it is tuning high-performance code libraries using the TAG algorithm (Arpad Rimmel et al., Bandit-based optimization on graphs) or retrieving the single best image from a database (Ryoma Sato, Tiara), the core lesson remains: when you only need one winner, stop looking for the best average and start hunting for the extreme.

Papers in this version

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 1, frozen text):

@misc{lacuna_max_k_armed_bandits_for_extreme_value_di_d739213f_v1,
  title = {Max k-Armed Bandits for Extreme Value Discovery},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/max-k-armed-bandits-for-extreme-value-discovery/rdr_d739213fdcd94396bb9db2c01d5d30a9/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}