In many real-world resource allocation problems, the goal isn't to find the highest average return, but rather to find the most extreme, rare events. This paper, "Extreme Bandits" by Alexandra Carpentier and Michal Valko, introduces a novel approach to this "needle in the haystack" problem.
The authors present EXTREMEHUNTER, a bandit-style algorithm designed specifically to find sources that produce extreme values (outliers). By leveraging Extreme Value Theory (EVT), the algorithm effectively identifies heavy-tailed distributions in semi-parametric settings, outperforming traditional mean-optimizing algorithms in tasks like security and anomaly detection.
The "Mean" Trap and the Max-k Problem
Most Multi-Armed Bandit (MAB) research focuses on maximizing the cumulative sum of rewards—essentially finding the "best average" arm. However, in fields like network security (detecting a DDoS attack), hydrology (predicting peak flood levels), or medicine (identifying rare disease outbreaks), the average is irrelevant. We care strictly about the maximum value observed.
The challenge is two-fold:
- Limited Feedback: You only see the output of the "arm" (source) you choose to sample at any given time.
- Heavy Tails: Extreme events often come from distributions where the "tail" is heavy (e.g., Pareto or Fréchet distributions).
Standard bandit algorithms (like UCB) are fundamentally biased toward arms with high averages. If a source produces zeros 99% of the time but a massive spike 1% of the time, a mean-seeking algorithm will abandon it long before the spike occurs. The authors tackle this "max-k" problem: how to sequentially sample sources to find the single highest value possible over $n$ trials, minimizing what they call extreme regret.
Introducing EXTREMEHUNTER
The authors introduce EXTREMEHUNTER, which adapts the "Optimism in the Face of Uncertainty" principle to the world of extremes.
- Semi-Parametric Approach: Unlike previous work that assumed data followed a strict, known distribution, this paper uses a "second-order Pareto" assumption. This is much more flexible and realistic for real-world data that is "almost" Pareto but not perfectly so.
- Tail Estimation: The algorithm maintains estimates of the tail index ($\alpha$)—which determines how "heavy" the tail is—and a scale parameter ($C$).
- The Upper Confidence Bound (UCB) for Extremes: Instead of calculating a UCB for the mean, EXTREMEHUNTER calculates a UCB for the expected maximum. It asks: "Based on what I've seen, what is the highest value this arm could realistically produce if I pull it $n$ times?"
- EVT Integration: The core innovation is applying the Fisher-Tippett-Gnedenko theorem to bandit arm selection, allowing the learner to predict the behavior of the "tail" without needing to see thousands of outliers first.
Key Results and Performance
The algorithm was evaluated on synthetic data (both exact and approximate Pareto distributions) and real-world computer network traffic data (packet flow start times from enterprise laptops).
In synthetic experiments where the "peak" arm had a low mean (a "trap" for standard algorithms), standard UCB failed completely. EXTREMEHUNTER, however, successfully identified the heavy-tailed source.
Furthermore, EXTREMEHUNTER outperformed THRESHOLDASCENT (the previous leading algorithm for this problem). THRESHOLDASCENT relies on reward discretization, which can struggle with very large, continuous values.
On the real-world network traffic dataset, the goal was to identify which laptop produced the largest "bursts" of activity. EXTREMEHUNTER was significantly more efficient at identifying the source of the largest traffic bursts compared to both UCB and THRESHOLDASCENT, rapidly driving extreme regret down to near zero.
Limitations and Future Directions
While highly effective, the EXTREMEHUNTER approach has a few limitations:
- The "b" Parameter: The algorithm requires the user to provide a lower bound ($b$) for a second-order tail parameter ($\beta$). Learning this parameter automatically is theoretically impossible in this setting, making it a rigid requirement.
- Fréchet Focus: The current analysis focuses on Fréchet-type (heavy-tailed) distributions. Extending the framework to gracefully handle Gumbel (light-tailed) or Weibull (bounded) distributions remains an open path.
- Computational Complexity: The confidence intervals involve complex Gamma functions and tail estimators that are more computationally intensive than simple mean-based UCBs.
Despite these constraints, EXTREMEHUNTER represents a significant step forward for anomaly detection and extreme value discovery in environments with limited feedback.
Summary updated