Introduction
In the classic $k$-armed bandit problem, an agent seeks to maximize the cumulative sum of rewards across multiple trials. However, many real-world applications—such as randomized search heuristics, combinatorial optimization, and algorithm selection—prioritize finding the single best outcome rather than the average performance. This variant is known as the max $k$-armed bandit problem.
The fundamental challenge lies in the fact that the "best" arm for cumulative reward (the one with the highest mean) is often not the best arm for the "max" reward (the one most likely to produce high-value outliers). While previous research relied on heuristics, this paper introduces the first provably asymptotically optimal algorithm for this problem.
Theoretical Foundation: Extreme Value Theory
To address the max $k$-armed bandit problem, the authors leverage Extreme Value Theory (EVT). Just as the Central Limit Theorem describes the distribution of sums, the Extremal Types Theorem describes the distribution of maxima.
The core premise is that the maximum of $n$ independent and identically distributed (i.i.d.) samples from most common distributions converges to a Generalized Extreme Value (GEV) distribution. The GEV is characterized by three parameters:
- Location ($\mu$): The center of the distribution.
- Scale ($\sigma$): The spread of the distribution.
- Shape ($\xi$): Determines the tail behavior of the distribution.
The Proposed Strategy: $S^1$
The authors propose an algorithm, denoted as Strategy $S^1$, which operates in two distinct phases:
- Exploration Phase: The algorithm pulls each of the $k$ arms a specific number of times ($t$) to estimate their respective GEV parameters. Specifically, it estimates $m_n$, the expected maximum payoff after $n$ pulls. To ensure robustness, a "median of means" estimator is employed, providing high-probability ($1-\delta$) estimates.
- Exploitation Phase: Based on the estimates from the exploration phase, the algorithm identifies the arm with the highest predicted $m_n$ and pulls it for all remaining trials.
The sample complexity for the exploration phase is established as $O\left(\frac{k \ln(k/\delta) \ln(n)^2}{\epsilon^2}\right)$, ensuring that the exploration does not overwhelm the total trial budget.
The Role of the Shape Parameter ($\xi$)
A critical insight of this work is how the shape parameter $\xi$ dictates the growth of the expected maximum as the number of trials $n$ increases.
As illustrated in the figure above, the behavior of the expected maximum varies significantly:
- $\xi < 0$ (Weibull-type): The distribution is bounded. This is common in optimization tasks where a maximum possible score exists.
- $\xi = 0$ (Gumbel-type): The expected maximum grows logarithmically with $n$.
- $\xi > 0$ (Fréchet-type): The distribution is heavy-tailed, and the maximum grows polynomially, indicating a high frequency of extreme outliers.
To accurately estimate $m_n$ from a limited sample $t$, the authors utilize different interpolation techniques tailored to the estimated value of $\xi$.
Key Results and Asymptotic Optimality
The primary contribution of this paper is the proof of asymptotic optimality. The authors demonstrate that as the total number of pulls $n$ approaches infinity, the gap between the expected maximum payoff achieved by Strategy $S^1$ and the expected maximum of the single best arm converges to zero.
Furthermore, the paper provides Probably Approximately Correct (PAC) bounds. For arms where $\xi \le 0$, the algorithm is shown to identify an $\epsilon$-optimal arm with probability at least $1-\delta$ after a sufficient number of pulls. The "regret"—defined as the difference between the optimal expected maximum and the algorithm's result—is bounded by $O(\Delta)$, where $\Delta$ decreases as $n$ increases.
Limitations and Future Work
While providing a rigorous theoretical framework, the approach has certain limitations:
- GEV Convergence: The performance guarantees assume that the reward distributions either follow a GEV or converge to one rapidly.
- Parameter Knowledge: Setting the exploration duration correctly requires some prior knowledge of the bounds for the GEV parameters.
- Batching Requirements: The theoretical analysis assumes arms are pulled in batches to satisfy the conditions of the Extremal Types Theorem, which may differ from purely online settings.
Future research may focus on refining the constants within the sample complexity bounds or extending these proofs to non-stationary reward distributions.
Summary updated