The Price of Tail Safety in Heavy-tailed Bandits

Traditional bandit algorithms focus on minimizing expected regret to achieve good average performance. However, low expected regret can mask tail risk—the possibility of exceptionally large regret on individual runs, which can be unacceptable in risk-sensitive applications. Under heavy-tailed rewards, extreme observations can distort reward estimates and lead to large regret. Additional exploration can make these estimates more reliable and reduce this risk, but at the cost of higher expected regret. We study this trade off under a known bound on the centered $(1+ϵ)$-th moment. Our target is pseudo-regret, which measures decision error: realized payoff shortfall also contains reward noise that can cause large losses even for an oracle. We establish matching upper and lower bounds relating a worst-case expected-regret budget to the pseudo-regret tail probability. For fixed $ϵ$ and a fixed number of arms, a budget of order $\rho$ times the minimax regret scale yields a $\rho$-fold improvement in the negative-log tail rate, up to constants. We therefore propose Budget-Calibrated Robust Racing (BCRR), a novel algorithm that jointly calibrates exploration and robust arm elimination to the expected-regret budget, attaining the optimal trade off between average performance and tail protection. Numerical experiments demonstrate the algorithm's effectiveness in controlling the risk of large decision errors.