Picking the best of $K$ options from noisy trials, known as best-arm identification, is the standard model for A/B testing, portfolio screening and hyperparameter search. When the noise is well behaved, recent algorithms come within a doubly-logarithmic factor of the provable minimum number of trials. When the noise has heavy tails, the situation is much worse. Heavy tails here mean that rare, huge observations occur often enough that the variance may be infinite, as with financial returns. The best available algorithms then either pay an extra $\ln K$ factor or are optimal only in the limit of vanishing error probability. We propose an algorithm and matching analysis that close this gap for a realistic setting: arms whose noise is heavy-tailed, and whose noise scales differ from arm to arm and are unknown in advance.
The core idea fits in two sentences. First, estimate each arm's noise scale from quantiles. A quantile-based estimate has confidence intervals that hold for any distribution, so a few hundred cheap samples give a valid upper bound on how heavy that arm's tail is, without knowing the scale ahead of time. Second, sort arms into buckets of similar scale and run a grouped median-elimination procedure inside each bucket with a robust mean estimator. Each arm then pays only for its own tail, and no union bound over all $K$ arms is needed.
Core Claim
Assume each arm $i$ has mean $\mu_i$ and gap $\Delta_i$ to the best arm. Its centered $p$-th moment, for a known $p \in (1,2]$, is bounded relative to a quantile-defined scale $s_i$, such as an interquantile range: $\mathbb{E}|X_i-\mu_i|^p \le C^p s_i^p$ for a known shape constant $C$. The scales $s_i$ themselves are unknown. Under this assumption, we claim a $\delta$-correct algorithm that, with high probability, stops after
$$ O\left(\sum_{i=1}^{K}\left[\left(\frac{C^p s_i^p}{\Delta_i^{p}}\right)^{\frac{1}{p-1}} + \frac{C s_i}{\Delta_i}\right]\left(\ln \delta^{-1} + \ln\ln \Delta_i^{-1}\right)\right) $$
samples. Here the bracketed per-arm cost comes from inverting the deviation rate $s\,(\ln(1/\delta)/n)^{(p-1)/p}$ of robust mean estimators under $p$ moments. We also claim a matching per-arm lower bound of order $(C^p s_i^p/\Delta_i^p)^{1/(p-1)}\ln\delta^{-1}$ within this class. When $p=2$, the result reduces to the variance-dependent bound of Variance-dependent best arm identification, but it no longer requires bounded rewards.
This assumption is chosen to respect a known impossibility result. Optimal δ-Correct Best-Arm Selection for Heavy-Tailed Distributions proves that $\delta$-correct identification with finite expected cost is impossible for unrestricted heavy tails, because an arm can imitate a good arm until a single rare value moves its mean. That paper therefore assumes a known bound $\mathbb{E}f(|X|)\le B$. Our class is also a known restriction, but it is scale-free: the user specifies the shape of the tail, and the algorithm learns its size. For the scale estimate to be valid, the quantile bracket must bound the $p$-th moment. We prove this using DKW-type confidence intervals on the empirical distribution function, which hold for every distribution.
Relation to Prior Work
Two papers motivate the work by exposing the gap. Pure Exploration of Multi-Armed Bandits with Heavy-Tailed Payoffs runs successive elimination with a truncated empirical average under bounded $p$-th moments. Its bound keeps polylogarithmic factors in $K$ and $1/\Delta_i$, and it requires the moment bound $v$ to be known in advance and shared across arms. AL1, from the impossibility paper above, is asymptotically optimal as $\delta\to 0$. At practical confidence levels, however, it uses 28 times the lower bound at $\delta=10^{-3}$ and 16 times at $\delta=10^{-8}$ on its 4-armed Pareto instance. The authors attribute part of this to batching with batch size $\Theta(\log 1/\delta)$.
Two lines of work supply our methods. From Variance-dependent best arm identification we reuse the structure of scale bucketing followed by grouped median elimination (its VAREST/GROUPELIM subroutines), which is what removes $\ln K$ there. That analysis relies on empirical Bernstein bounds and so on bounded rewards. We replace both of its estimators. Its variance estimator becomes a distribution-free quantile bracket, and its mean estimator becomes median-of-means or truncation with an arm-specific threshold. The analysis of Uniform Mean Estimation for Heavy-Tailed Distributions via Median-of-Means shows that careful median-of-means arguments can keep confidence and complexity additive rather than multiplicative. It also warns that such proofs can introduce constants in the hundreds, and we treat that as a practical risk to measure. Finally, Nearly Instance Optimal Sample Complexity Bounds for Top-k Arm Selection provides the instance-embedding technique we adapt for the lower bound. Its upper bound holds only under sub-Gaussian noise.
One paper constrains the design. Fixing the Loose Brake shows that successive elimination can fail to stop with constant probability. Under heavy tails this risk plausibly worsens. Median-elimination designs have deterministic per-round budgets, so we expect exponentially decaying stopping-time tails without the extra polylogarithmic cost of BrakeBooster's repeated runs. We will both prove and measure this.
Research Program
The theory has three parts. The first is the scale-estimation lemma. From $O(\ln(1/\delta'))$ samples per arm it gives an upper confidence bound $\hat s_i^+$ that is within a constant factor of $s_i$, valid simultaneously for every arm in a bucket, with no union bound over $K$. Achieving this requires amortizing failures in the way GROUPELIM does. The second is the elimination analysis. Inside a bucket where scales differ by at most a factor of two, a robust estimator thresholded at $\hat s^+$ has deviation of order $\hat s^+(\ln(1/\delta)/n)^{(p-1)/p}$, and median elimination removes a constant fraction of arms per round at geometrically shrinking accuracy. The third is the lower bound within the moment-ratio class, built from two-point changes of measure using Pareto-type perturbations that preserve the ratio constraint.
The algorithm will be implemented with constants tuned against the proofs. It will be released together with all instances and the baseline implementations.
Baselines
The naive reference point is successive elimination with plain empirical averages. Prior evidence shows it degrades sharply as $\delta$ shrinks under Student-t noise with three degrees of freedom (Pure Exploration…Heavy-Tailed Payoffs). It establishes how much robustness matters at all.
The direct predecessor is SE-δ(TEA), run with the true $v$ given as an oracle so that it is not handicapped. No reported sample-complexity number for it was found on Lacuna. We will rerun it on its own synthetic Student-t instances S1 and S2 and on the 10-cryptocurrency hourly returns.
The strongest existing method at practical $\delta$ is AL1, given the true bounding function $f$ and bound $B$. Its reported ratios of sample complexity to the lower bound, 28 at $\delta=10^{-3}$ and 16 at $\delta=10^{-8}$ on 4-armed Pareto bandits, are the numbers to beat. We will report the same ratio on the same instance type and count a ratio below 10 at $\delta=10^{-3}$ as a clear win. AL1 solves a convex program every batch, so we report both wall-clock time and samples.
We also include VD-BESTARMID run on rewards clipped to a range chosen with oracle knowledge, which tests whether clipping alone suffices.
The key ablation replaces per-arm quantile scale estimation with a single known worst-case scale $s_{\max}$ while keeping the grouped elimination. This isolates whether per-arm adaptivity, rather than the grouping, produces the gains.
All methods receive the same instances, the same $\delta$, 1,000 independent runs per configuration, and the same timeout. Hyperparameters, such as AL1's batch size and the TEA threshold constants, get equal grid-search budgets on held-out instances.
Why not just…?
Why not just plug median-of-means into an existing grouped-elimination algorithm with a known global moment bound? This is the real threat, and it is exactly our ablation. With one known scale, a robust estimator with sub-Gaussian-type deviations drops into median elimination and likely already removes $\ln K$. Its cost, however, scales with $s_{\max}$ for every arm. On instances where scales are similar, we expect the ablation to tie our method, and we will report that honestly. The claimed contribution lives on heterogeneous instances, where a few very noisy arms would otherwise inflate the cost of every arm. If the ablation matches us even when scales span two or more orders of magnitude, the per-arm claim fails.
Why not just use AL1, which is already optimal? It is optimal only as $\delta\to0$, and its own experiments show a 16–28× gap at practical confidence levels. Our experiments sweep $\delta$ from $10^{-1}$ to $10^{-8}$ to locate any crossover. AL1 may win at extremely small $\delta$, and we would report it.
Why not just clip rewards and run a light-tailed algorithm? A fixed clip either introduces bias, especially under asymmetric noise, which is why Robust Matrix Completion with Heavy-Tailed Noise needs an adaptive threshold, or requires the very scale knowledge we are trying to learn. The clipped VD-BESTARMID baseline with oracle clipping measures this directly. An asymmetric Pareto instance with arms whose means are close is designed so that clipping flips the identity of the best arm.
Proposed Experiments
The decisive synthetic test fixes $p\in\{1.5, 2\}$ and $K\in\{10, 100, 1000\}$. Arm scales are drawn log-uniformly over a range of $10^{0}$ to $10^{3}$, using Pareto and Student-t noise (1.5 and 3 degrees of freedom). We plot samples-to-stop divided by the per-arm lower-bound sum, as a function of $K$. Our method should give a flat curve. The SE-δ(TEA) baseline should grow roughly like $\ln K$. The global-scale ablation should grow with the spread of scales.
A second test reproduces the 4-armed Pareto setting of AL1 and reports the ratio to the lower bound at $\delta\in\{10^{-3},10^{-8}\}$. A third reruns the Student-t S1/S2 instances and the cryptocurrency returns from the TEA paper, checking whether we recover the same best arm, EOS, with fewer hourly samples.
We will also measure the empirical misidentification rate, which must stay below $\delta$, and the survival curve of the stopping time $P(\tau>t)$ over $10^6$ runs. These follow the Loose Brake protocol, so we can test the predicted exponential tail of the stopping time against SE-δ(TEA).
Finally, a stress test deliberately violates the moment-ratio assumption by mixing in a tiny-probability, huge-magnitude component. This shows how gracefully correctness fails outside the assumed class, which the impossibility result says must happen somewhere.
References
- Variance-dependent best arm identification
- Optimal $δ$-Correct Best-Arm Selection for Heavy-Tailed Distributions
- Pure Exploration of Multi-Armed Bandits with Heavy-Tailed Payoffs
- Uniform Mean Estimation for Heavy-Tailed Distributions via Median-of-Means
- Nearly Instance Optimal Sample Complexity Bounds for Top-k Arm Selection
- Fixing the Loose Brake: Exponential-Tailed Stopping Time in Best Arm Identification
- Robust Matrix Completion with Heavy-tailed Noise