# Regret Distribution in Stochastic Bandits: Optimal Trade-off between Expectation and Tail Risk

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 36 references that are in the map.
- First posted on arXiv 10 Apr 2023.

## Builds on (most cited first, 14 of 14)

- [Mean estimation and regression under heavy-tailed distributions--a survey](https://mlsanity.com/paper/1906.04280/) (2019)
- [A Closer Look at the Worst-case Behavior of Multi-armed Bandit Algorithms](https://mlsanity.com/paper/2106.02126/) (2021)
- [Thompson Sampling Algorithms for Mean-Variance Bandits](https://mlsanity.com/paper/2002.00232/) (2020)
- [Regret Minimization in Heavy-Tailed Bandits](https://mlsanity.com/paper/2102.03734/) (2021)
- [Optimal Rates of (Locally) Differentially Private Heavy-tailed Multi-Armed Bandits](https://mlsanity.com/paper/2106.02575/) (2021)
- [Action Centered Contextual Bandits](https://mlsanity.com/paper/1711.03596/) (2017)
- [Semiparametric Contextual Bandits](https://mlsanity.com/paper/1803.04204/) (2018)
- [Optimal Algorithms for Stochastic Multi-Armed Bandits with Heavy Tailed Rewards](https://mlsanity.com/paper/2010.12866/) (2020)
- [The Fragility of Optimized Bandit Algorithms](https://mlsanity.com/paper/2109.13595/) (2021)
- [Bandit algorithms: Letting go of logarithmic regret for statistical robustness](https://mlsanity.com/paper/2006.12038/) (2020)
- [Generalized Risk-Aversion in Stochastic Multi-Armed Bandits](https://mlsanity.com/paper/1405.0833/) (2014)
- [A Scale Free Algorithm for Stochastic Bandits with Bounded Kurtosis](https://mlsanity.com/paper/1703.08937/) (2017)
- [Contextual Multi-armed Bandit Algorithm for Semiparametric Reward Model](https://mlsanity.com/paper/1901.11221/) (2019)
- [Diffusion Approximations for a Class of Sequential Testing Problems](https://mlsanity.com/paper/2102.07030/) (2021)

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

- [Allocation Stability and Wald Inference under Variance-Aware UCB](https://mlsanity.com/paper/2412.08843/) (2024)
- [Testing the Feasibility of Linear Programs with Bandit Feedback](https://mlsanity.com/paper/2406.15648/) (2024)
- [Bandit Allocational Instability](https://mlsanity.com/paper/2602.07472/) (2026)
- [Reliability and Effectiveness of Autonomous AI Agents in Supply Chain Management](https://mlsanity.com/paper/2605.17036/) (2026)
- [A characterization of sample adaptivity in UCB data](https://mlsanity.com/paper/2503.04855/) (2025)
- [Design Experiments to Compare Multi-armed Bandit Algorithms](https://mlsanity.com/paper/2603.05919/) (2026)
- [Unified Framework of Distributional Regret in Multi-Armed Bandits and Reinforcement Learning](https://mlsanity.com/paper/2605.05102/) (2026)
- [Experimentation and Commitment under Reward Shifts](https://mlsanity.com/paper/2607.23432/) (2026)
- [Reliable Scale-Free Bandits via Empirical Likelihood](https://mlsanity.com/paper/2610.18055/) (2026)

## Abstract (arXiv)

We study the optimal trade-off between expectation and tail risk for regret distribution in the stochastic multi-armed bandit model. We fully characterize the interplay among three desired properties for policy design: worst-case optimality, instance-dependent consistency, and light-tailed risk. New policies are proposed to characterize the optimal regret tail probability for any regret threshold. In particular, we discover an intrinsic gap of the optimal tail rate depending on whether the time horizon T is known a priori or not. Interestingly, when it comes to the purely worst-case scenario, this gap disappears. Our results reveal insights on how to design policies that balance between efficiency and safety, and highlight extra insights on policy robustness with regard to policy hyper-parameters and model mis-specification. We also conduct a simulation study to validate our theoretical insights and provide practical amendment to our policies. Finally, we discuss extensions of our results to (i) general sub-exponential environments and (ii) general stochastic linear bandits. Furthermore, we find that a special case of our policy design surprisingly coincides with what was adopted in AlphaGo Monte Carlo Tree Search. Our theory provides high-level insights to why their engineered solution is successful and should be advocated in complex decision-making environments.