# Bandit algorithms: Letting go of logarithmic regret for statistical robustness

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Jun 2020.

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

- [Optimal Rates of (Locally) Differentially Private Heavy-tailed Multi-Armed Bandits](https://mlsanity.com/paper/2106.02575/) (2021)
- [The Fragility of Optimized Bandit Algorithms](https://mlsanity.com/paper/2109.13595/) (2021)
- [Regret Distribution in Stochastic Bandits: Optimal Trade-off between Expectation and Tail Risk](https://mlsanity.com/paper/2304.04341/) (2023)
- [From Optimality to Robustness: Dirichlet Sampling Strategies in Stochastic Bandits](https://mlsanity.com/paper/2111.09724/) (2021)
- [A Simple and Optimal Policy Design with Safety against Heavy-Tailed Risk for Stochastic Bandits](https://mlsanity.com/paper/2206.02969/) (2022)
- [When Lower-Order Terms Dominate: Adaptive Expert Algorithms for Heavy-Tailed Losses](https://mlsanity.com/paper/2506.01722/) (2025)
- [Parameter-Free Heavy-Tailed Bandits](https://mlsanity.com/paper/2607.29460/) (2026)
- [Bilateral Trade Under Heavy-Tailed Valuations: Minimax Regret without a Variance Bound](https://mlsanity.com/paper/2603.06851/) (2026)
- [Regret Tail Characterization of Optimal Bandit Algorithms with Generic Rewards](https://mlsanity.com/paper/2604.14876/) (2026)
- [(ε, u)-Adaptive Regret Minimization in Heavy-Tailed Bandits](https://mlsanity.com/paper/2310.02975/) (2023)
- [Conformal bandits: bringing statistical validity and reward efficiency under weak arm separability](https://mlsanity.com/paper/2512.09850/) (2025)
- [Bandits with Multiple Optimal Arms: Minimax Regret and Non-Adaptivity](https://mlsanity.com/paper/2609.38659/) (2026)
- [Reliable Scale-Free Bandits via Empirical Likelihood](https://mlsanity.com/paper/2610.18055/) (2026)

## Abstract (arXiv)

We study regret minimization in a stochastic multi-armed bandit setting and establish a fundamental trade-off between the regret suffered under an algorithm, and its statistical robustness. Considering broad classes of underlying arms' distributions, we show that bandit learning algorithms with logarithmic regret are always inconsistent and that consistent learning algorithms always suffer a super-logarithmic regret. This result highlights the inevitable statistical fragility of all `logarithmic regret' bandit algorithms available in the literature---for instance, if a UCB algorithm designed for σ-subGaussian distributions is used in a subGaussian setting with a mismatched variance parameter, the learning performance could be inconsistent. Next, we show a positive result: statistically robust and consistent learning performance is attainable if we allow the regret to be slightly worse than logarithmic. Specifically, we propose three classes of distribution oblivious algorithms that achieve an asymptotic regret that is arbitrarily close to logarithmic.