Introduction
The Stochastic Multi-Armed Bandit (MAB) problem is a cornerstone of sequential decision-making. While standard algorithms like Upper Confidence Bound (UCB) excel under sub-Gaussian reward assumptions, they often falter in real-world scenarios characterized by heavy-tailed distributions—where extreme outliers, or "black swan" events, are frequent. This paper introduces APE² (Adaptively Perturbed Exploration), the first MAB algorithm to achieve minimax optimal regret for heavy-tailed rewards without requiring prior knowledge of the reward distribution's moments.
The Challenge of Heavy Tails
Existing robust MAB algorithms typically face two significant hurdles. First, they often require the user to know the bound on the reward's $p$-th moment ($\nu_p$) in advance, a parameter rarely available in practice. Second, there remains a theoretical gap between the regret lower bounds and the upper bounds achieved by state-of-the-art methods like Robust UCB. Specifically, Robust UCB carries an extra $\ln(T)^{1-1/p}$ factor in its regret, preventing it from reaching the theoretical "speed limit" of learning.
Methodology: APE² and the $p$-Robust Estimator
The authors propose a synergistic two-part solution to bridge these gaps:
- A Novel $p$-Robust Estimator: This estimator is designed to be parameter-free, requiring neither the moment bound ($\nu_p$) nor the error probability ($\delta$) beforehand. It employs a specialized influence function $\psi_p(x)$ that sub-linearly regularizes large noise, effectively taming outliers without discarding valuable data.
- Adaptively Perturbed Exploration (APE²): Moving away from deterministic confidence intervals, APE² adopts a perturbation-based strategy. It injects random noise—sampled from distributions such as Weibull, Gamma, or Pareto—into the robust estimates. The algorithm then selects the arm with the highest perturbed value.
The researchers developed a generalized regret analysis scheme to prove that as long as the perturbation's tail decays slower than the estimator's error probability, effective exploration is guaranteed.
Experimental Evaluation
The proposed methods were evaluated using synthetic simulations with heavy-tailed noise generated from Pareto distributions (varying the shape parameter $\alpha$ for $1 < p \le 2$). APE² was benchmarked against Robust UCB, Deterministic Sequencing of Exploration and Exploitation (DSEE), and traditional mean estimators like the truncated mean and median-of-means.
Key Results and Insights
The study yields several critical findings:
- Minimax Optimality: APE² is the first algorithm to achieve the minimax optimal regret bound of $O(T^{1/p})$ for heavy-tailed rewards, successfully eliminating the sub-optimal logarithmic penalty found in previous methods.
- Superior Estimation Performance: The $p$-robust estimator demonstrates faster convergence to the true mean than traditional robust estimators, even in the absence of known moment bounds.
- Tail Matching: A vital insight is the necessity of "tail matching"—the random perturbation must have a sufficiently "thick" tail to prevent the algorithm from being misled by heavy-tailed outliers.
Conclusion and Future Directions
APE² represents a significant advancement in robust MABs, offering a "plug-and-play" solution for practitioners operating in volatile environments. While the current analysis is restricted to $1 < p \le 2$ (finite mean), future work could explore "ultra-heavy" tails ($p \le 1$) or extend this perturbation-based approach to contextual and linear bandits.
Summary updated