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

David Simchi-Levi, Zeyu Zheng, Feng Zhu

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…