# On the Optimality of Perturbations in Stochastic and Adversarial Multi-armed Bandit Problems

arXiv: https://arxiv.org/abs/1902.00610 · HTML: https://mlsanity.com/paper/1902.00610/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Feb 2019.

## Built on by (most cited first, 11 of 11)

- [Stochastic Contextual Dueling Bandits under Linear Stochastic Transitivity Models](https://mlsanity.com/paper/2202.04593/) (2022)
- [Optimism in the Face of Ambiguity Principle for Multi-Armed Bandits](https://mlsanity.com/paper/2409.20440/) (2024)
- [Revisiting Follow-the-Perturbed-Leader with Unbounded Perturbations in Bandit Problems](https://mlsanity.com/paper/2508.18604/) (2025)
- [Follow-the-Perturbed-Leader Approaches Best-of-Both-Worlds for the m-Set Semi-Bandit Problems](https://mlsanity.com/paper/2504.07307/) (2025)
- [CORe: Capitalizing On Rewards in Bandit Exploration](https://mlsanity.com/paper/2103.04387/) (2021)
- [Some performance considerations when using multi-armed bandit algorithms in the presence of missing data](https://mlsanity.com/paper/2205.03820/) (2022)
- [Graph Neural Thompson Sampling](https://mlsanity.com/paper/2406.10686/) (2024)
- [Follow-the-Perturbed-Leader for Decoupled Bandits: Best-of-Both-Worlds and Practicality](https://mlsanity.com/paper/2510.12152/) (2025)
- [Self-Concordant Perturbations for Linear Bandits](https://mlsanity.com/paper/2510.24187/) (2025)
- [Adaptive Learning Rates with Surrogate Probability for Follow-the-Perturbed-Leader](https://mlsanity.com/paper/2606.06043/) (2026)
- [Follow the Perturbed Leader for Linear Bandits: √T Regret over General Convex Sets](https://mlsanity.com/paper/2610.17818/) (2026)

## Abstract (arXiv)

We investigate the optimality of perturbation based algorithms in the stochastic and adversarial multi-armed bandit problems. For the stochastic case, we provide a unified regret analysis for both sub-Weibull and bounded perturbations when rewards are sub-Gaussian. Our bounds are instance optimal for sub-Weibull perturbations with parameter 2 that also have a matching lower tail bound, and all bounded support perturbations where there is sufficient probability mass at the extremes of the support. For the adversarial setting, we prove rigorous barriers against two natural solution approaches using tools from discrete choice theory and extreme value theory. Our results suggest that the optimal perturbation, if it exists, will be of Frechet-type.