Optimal Algorithms for Stochastic Multi-Armed Bandits with Heavy Tailed Rewards

Kyungjae Lee, Hongjun Yang, Sungbin Lim, Songhwai Oh

Introduction

Researchers have developed a new "$p$-robust estimator" and exploration strategy (APE²) for Multi-Armed Bandit (MAB) problems that involve heavy-tailed rewards—environments where extreme outliers are common. Unlike previous methods, this approach doesn't require prior knowledge of reward bounds and is the first to achieve the theoretically optimal "minimax" regret rate, effectively removing a long-standing efficiency gap in the field.

The Challenge of Heavy-Tailed Rewards

In the classic Multi-Armed Bandit problem, an agent must choose between several "arms" (actions) to maximize cumulative rewards. Most standard algorithms assume rewards follow a "sub-Gaussian" distribution, meaning extreme values are vanishingly rare. However, real-world data—from financial markets to web traffic—often features "heavy tails," where massive outliers occur frequently.

Existing "robust" algorithms designed for heavy-tailed rewards suffer from two major flaws:

  1. The "Prior Knowledge" Trap: They usually require the agent to know the exact bound of the reward's $p$-th moment ($\nu_p$) beforehand. In practice, you rarely know how "heavy" the tails are until you start collecting data.
  2. Sub-optimal Efficiency: Even the best existing methods (like Robust UCB) exhibit a "regret" (the gap between the agent's performance and the theoretical best) that is slightly higher than necessary, specifically by a factor of $\ln(T)^{1-1/p}$.

Proposed Solution: $p$-Robustness and APE²

The authors introduce a two-part solution to tackle these flaws:

1. The $p$-Robust Estimator

Instead of a simple average, the authors propose a novel estimator that employs an "influence function" ($\psi_p$) to dampen the impact of extreme outliers. Crucially, this estimator is designed to work without needing the moment bound ($\nu_p$) as an input, making it highly practical for real-world applications. Despite lacking this prior information, the estimator's error probability still decays exponentially fast.

2. Adaptively Perturbed Exploration (APE²)

Rather than using Upper Confidence Bounds (UCB)—which adds a deterministic "bonus" to uncertain arms—the authors utilize a perturbation-based approach. At each step, the algorithm adds a random "noise" value to the robust reward estimates, stochastically encouraging the agent to explore different arms.

Theoretical bounds and optimal parameters for various perturbation distributions used in APE².

The team developed a generalized regret analysis scheme proving that if the "tail" of the random perturbation is slightly heavier than the error probability of the estimator, the algorithm achieves optimal performance. The table above illustrates the theoretical bounds and optimal parameters derived for various perturbation distributions (such as Weibull, Gamma, and Pareto).

Key Insights and Results

The authors evaluated their work using synthetic simulations with Pareto distributions to generate heavy-tailed noise, varying the $p$ value (the "heaviness" of the tail) between 1.1 and 1.9.

  • Closing the Regret Gap: By switching from UCB to a perturbation-based strategy, the authors proved they could hit the minimax optimal regret bound of $O(T^{1/p})$. This removes the sub-optimal logarithmic factor that has plagued heavy-tailed bandit research for years.
  • Estimator Performance: In simulations, the $p$-robust estimator converged faster and with less error than baselines like the truncated mean, median of means, and sample mean. This was especially true when the moment bound $\nu_p$ was unknown.
Performance of the $p$-robust estimator compared to baselines across different tail heaviness ($p$) values.
  • Regret Reduction in MABs: In full bandit simulations, APE² (using Gumbel or Exponential perturbations) significantly outperformed Robust UCB and DSEE. The performance gap was most noticeable when the "reward gap" between the best arm and the second-best arm was small, proving APE² is better at distinguishing between similar options in noisy environments.

Limitations and Future Work

  • Constraint on $p$: The current analysis focuses on rewards where the $p$-th moment exists for $1 < p \le 2$. While this covers many heavy-tailed scenarios (including those with infinite variance), it does not cover the most extreme cases where $p \le 1$.
  • Hyperparameter Tuning: While the estimator doesn't need $\nu_p$, the perturbation strategy still involves hyperparameters (like the scale of the noise). The authors suggest optimal values, but these might still require tuning in complex real-world settings.
  • Extension to Complex Bandits: The paper focuses on the "multi-armed" case. Extending this robust, perturbation-based approach to Linear Bandits or Reinforcement Learning remains an open and promising direction.

Summary updated

Abstract

In this paper, we consider stochastic multi-armed bandits (MABs) with heavy-tailed rewards, whose p-th moment is bounded by a constant nu_p for 1 <p novel="" where="" information="" about="" is="" not="" required="" while="" other="" demand="" constant="" nu_p="" as="" prior="" information.="" show="" an="" error="" probability="" decays="" exponentially="" fast.="" using="" this="" propose="" perturbation-based="" develop="" scheme="" that="" provides="" a="" general="" by="" revealing="" relationship="" between="" cumulative="" density="" function="" perturbation.="" from="" analysis="" obtain="" gap-dependent="" gap-independent="" upper="" and="" lower="" bounds="" of="" perturbations.="" we="" also="" find="" hyperparameters="" each="" which="" can="" achieve="" minimax="" optimal="" regret="" bound="" with="" respect="" total="" rounds.="" in="" estimator="" shows="" favorable="" performance="" compared="" to="" robust="" estimators="" various="" values="" for="" mab="" the="" proposed="" perturbation="" strategy="" outperforms="" existing="" exploration="" methods.=""></p>
BibTeX
@inproceedings{lee2020optimal,
  author = {Kyungjae Lee and Hongjun Yang and Sungbin Lim and Songhwai Oh},
  title = {{Optimal Algorithms for Stochastic Multi-Armed Bandits with Heavy Tailed Rewards}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=pI_xx0o8PMV},
}
Figure