# Fighting Bandits with a New Kind of Smoothness

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

## Key facts

- Cited by 47 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Dec 2015.

## Built on by (most cited first, 30 of 47)

- [Adapting to Misspecification in Contextual Bandits](https://mlsanity.com/paper/2107.05745/) (2021)
- [Smoothed Online Learning is as Easy as Statistical Learning](https://mlsanity.com/paper/2202.04690/) (2022)
- [A Best-of-Both-Worlds Algorithm for Bandits with Delayed Feedback](https://mlsanity.com/paper/2206.14906/) (2022)
- [Adaptive Best-of-Both-Worlds Algorithm for Heavy-Tailed Multi-Armed Bandits](https://mlsanity.com/paper/2201.11921/) (2022)
- [Nonstochastic Bandits with Composite Anonymous Feedback](https://mlsanity.com/paper/2112.02866/) (2021)
- [Improved Analysis of the Tsallis-INF Algorithm in Stochastically Constrained Adversarial Bandits and Stochastic Bandits with Adversarial Corruptions](https://mlsanity.com/paper/2103.12487/) (2021)
- [Stability-penalty-adaptive follow-the-regularized-leader: Sparsity, game-dependency, and best-of-both-worlds](https://mlsanity.com/paper/2305.17301/) (2023)
- [Better Best of Both Worlds Bounds for Bandits with Switching Costs](https://mlsanity.com/paper/2206.03098/) (2022)
- [Adapting to game trees in zero-sum imperfect information games](https://mlsanity.com/paper/2212.12567/) (2022)
- [A Best-of-both-worlds Algorithm for Bandits with Delayed Feedback with Robustness to Excessive Delays](https://mlsanity.com/paper/2308.10675/) (2023)
- [Adaptive Learning Rate for Follow-the-Regularized-Leader: Competitive Analysis and Best-of-Both-Worlds](https://mlsanity.com/paper/2403.00715/) (2024)
- [Towards a Sharp Analysis of Offline Policy Learning for f-Divergence-Regularized Contextual Bandits](https://mlsanity.com/paper/2502.06051/) (2025)
- [Efficient Competitions and Online Learning with Strategic Forecasters](https://mlsanity.com/paper/2102.08358/) (2021)
- [On the Minimax Regret for Online Learning with Feedback Graphs](https://mlsanity.com/paper/2305.15383/) (2023)
- [Meta-Learning Adversarial Bandit Algorithms](https://mlsanity.com/paper/2307.02295/) (2023)
- [No-Regret Learning for Fair Multi-Agent Social Welfare Optimization](https://mlsanity.com/paper/2405.20678/) (2024)
- [Banker Online Mirror Descent: A Universal Approach for Delayed Online Bandit Learning](https://mlsanity.com/paper/2301.10500/) (2023)
- [A Unified Perspective on Value Backup and Exploration in Monte-Carlo Tree Search](https://mlsanity.com/paper/2202.07071/) (2022)
- [Meta-Learning Adversarial Bandits](https://mlsanity.com/paper/2205.14128/) (2022)
- [On Efficient Online Imitation Learning via Classification](https://mlsanity.com/paper/2209.12868/) (2022)
- [Oracle-Efficient Smoothed Online Learning for Piecewise Continuous Decision Making](https://mlsanity.com/paper/2302.05430/) (2023)
- [Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity](https://mlsanity.com/paper/2410.00690/) (2024)
- [Provably Efficient Regularized Online RLHF with Generalized Bilinear Preferences](https://mlsanity.com/paper/2602.23116/) (2026)
- [The equivalence of dynamic and strategic stability under regularized learning in games](https://mlsanity.com/paper/2311.02407/) (2023)
- [Near-optimal Per-Action Regret Bounds for Sleeping Bandits](https://mlsanity.com/paper/2403.01315/) (2024)
- [A Simple and Adaptive Learning Rate for FTRL in Online Learning with Minimax Regret of Theta(T2/3) and its Application to Best-of-Both-Worlds](https://mlsanity.com/paper/2405.20028/) (2024)
- [Improved Regret Bounds for Bandits with Expert Advice](https://mlsanity.com/paper/2406.16802/) (2024)
- [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)
- [Online Meta-Learning in Adversarial Multi-Armed Bandits](https://mlsanity.com/paper/2205.15921/) (2022)

## Abstract (arXiv)

We define a novel family of algorithms for the adversarial multi-armed bandit problem, and provide a simple analysis technique based on convex smoothing. We prove two main results. First, we show that regularization via the Tsallis entropy, which includes EXP3 as a special case, achieves the Theta(√TN) minimax regret. Second, we show that a wide class of perturbation methods achieve a near-optimal regret as low as O(√TN log N) if the perturbation distribution has a bounded hazard rate. For example, the Gumbel, Weibull, Frechet, Pareto, and Gamma distributions all satisfy this key property.