# A Simple and Optimal Policy Design with Safety against Heavy-Tailed Risk for Stochastic Bandits

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 25 references that are in the map.
- First posted on arXiv 7 Jun 2022.

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

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [Mean estimation and regression under heavy-tailed distributions--a survey](https://mlsanity.com/paper/1906.04280/) (2019)
- [Optimal Thompson Sampling strategies for support-aware CVaR bandits](https://mlsanity.com/paper/2012.05754/) (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)
- [Diffusion Approximations for a Class of Sequential Testing Problems](https://mlsanity.com/paper/2102.07030/) (2021)

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

- [Contextual Online Uncertainty-Aware Preference Learning for Human Feedback](https://mlsanity.com/paper/2504.19342/) (2025)
- [Reliability and Effectiveness of Autonomous AI Agents in Supply Chain Management](https://mlsanity.com/paper/2605.17036/) (2026)
- [Minimax Optimal Reinforcement Learning with Quasi-Optimism](https://mlsanity.com/paper/2503.00810/) (2025)
- [Reliable Scale-Free Bandits via Empirical Likelihood](https://mlsanity.com/paper/2610.18055/) (2026)

## Abstract (arXiv)

We study the stochastic multi-armed bandit problem and design new policies that enjoy both worst-case optimality for expected regret and light-tailed risk for regret distribution. Specifically, our policy design (i) enjoys the worst-case optimality for the expected regret at order O(√KTln T) and (ii) has the worst-case tail probability of incurring a regret larger than any x>0 being upper bounded by exp(-Omega(x/√KT)), a rate that we prove to be best achievable with respect to T for all worst-case optimal policies. Our proposed policy achieves a delicate balance between doing more exploration at the beginning of the time horizon and doing more exploitation when approaching the end, compared to standard confidence-bound-based policies. We also enhance the policy design to accommodate the "any-time" setting where T is unknown a priori, and prove equivalently desired policy performances as compared to the "fixed-time" setting with known T. Numerical experiments are conducted to illustrate the theoretical findings. We find that from a managerial perspective, our new policy design yields better tail distributions and is preferable than celebrated policies especially when (i) there is a risk of under-estimating the volatility profile, or (ii) there is a challenge of tuning policy hyper-parameters. We conclude by extending our proposed policy design to the stochastic linear bandit setting that leads to both worst-case optimality in terms of expected regret and light-tailed risk on the regret distribution.