No Regret Bound for Extreme Bandits

Robert Nishihara, David Lopez-Paz, Léon Bottou

Introduction

In the field of machine learning, hyperparameter optimization (HPO) is a ubiquitous challenge. Researchers must navigate a vast space of configurations to find the one that yields the highest performance. This process is frequently modeled using the Multi-Armed Bandit (MAB) framework. However, a fundamental discrepancy exists between standard MAB theory and the practical goals of HPO. While traditional bandits aim to maximize the average reward over a series of trials, HPO is concerned exclusively with the extreme value—the single best configuration discovered during the search.

This paper explores the "Extreme Bandit" problem, providing a rigorous theoretical analysis of whether algorithms can achieve "no-regret" performance in this setting. The authors present a sobering "no-go" theorem, proving that without restrictive assumptions on the underlying probability distributions, it is impossible to guarantee performance that matches an oracle.

The Extreme Bandit Framework

In a standard bandit problem, the "best" arm is typically defined as the one with the highest mean. In the extreme bandit setting, the objective shifts: we want to find the maximum value $M_n = \max_{t=1 \dots n} X_t$ after $n$ trials.

The authors identify a critical issue: traditional metrics for regret (the difference between the learner's performance and the oracle's) behave poorly when applied to extreme values. They are often hypersensitive to the infinitesimal details of a distribution's tail. To address this, the paper introduces Extreme Regret. This metric measures the ratio of the time horizon a policy $\pi$ requires to reach a certain threshold compared to the time an oracle would require.

Defining the Oracle

To establish a baseline for "perfect" performance, the authors define different classes of oracles:

  • Single-Armed Oracle: Knows which single distribution is best to sample from for a given horizon.
  • Optimal Oracle: An omniscient baseline used to measure the absolute limits of the search.

The Impossibility of No-Regret

The core of the research is Theorem 11, which establishes a fundamental lower bound on the hardness of the extreme bandit problem.

The authors use a probabilistic construction to demonstrate that for any possible search policy $\pi$, there exists a configuration of $K$ distributions that will inevitably "trick" the policy. By creating scenarios where the optimal arm periodically switches based on the time horizon, they show that a learner cannot identify the best arm quickly enough to close the gap with the oracle.

Key Result: The $K$-Factor Gap

Theorem 11 states that for any policy, the extreme regret is at least $K$, where $K$ is the number of available arms (or search strategies). This has significant practical implications: in the worst-case scenario, a general-purpose HPO algorithm could be $K$ times slower than simply knowing which strategy was the best from the outset. If a researcher is choosing between 10 different search ranges, a general algorithm might take 10 times longer to find a top-tier model than an oracle.

Why Extreme Bandits are Harder

The difficulty arises from two primary factors:

  1. The Moving Target: In standard bandits, the best arm is static. In extreme bandits, the "best" arm is a function of the time horizon $n$. An arm that frequently produces "good" results is preferable for short-term searches, but an arm with a "heavy tail"—producing rare but exceptional results—becomes superior as the number of trials increases.
  2. Tail Sensitivity: The performance of an extreme search is entirely dependent on the extreme tails of the distributions. Unlike means, which are relatively stable, the tails are difficult to estimate without a massive amount of data, making it nearly impossible for a learner to "catch up" to an oracle asymptotically.

Conclusion and Future Directions

This work provides a theoretical limit on what is achievable in hyperparameter optimization. It proves that the "no-regret" property, a staple of standard bandit algorithms, does not naturally extend to the extreme value setting.

However, this is not a counsel of despair. Instead, it highlights the necessity of structural assumptions. To perform better than the $K$-factor limit, HPO algorithms must exploit specific properties of the problem, such as:

  • Structural Assumptions: Utilizing knowledge like quasiconvexity or smoothness in the objective function.
  • Tail Behavior: Incorporating assumptions from Extreme Value Theory (e.g., Fréchet or Gumbel distributions), which previous "no-regret" results relied upon.
  • Oracle Selection: Refining how we compare HPO strategies to ensure we are using fair and achievable baselines.

By defining the boundaries of what is impossible, this paper clarifies the path forward for developing more efficient and robust hyperparameter search strategies.

Summary updated

BibTeX
@inproceedings{nishihara2016no,
  author = {Robert Nishihara and David Lopez-Paz and Léon Bottou},
  title = {{No Regret Bound for Extreme Bandits}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2016},
  url = {https://openreview.net/forum?id=zRPigG35GS},
}
Figure