Online learning is a fast-growing research area in sequential decision-making. While previous work mostly focuses on achieving efficiency by minimizing regret expectation, controlling the regret tail risk to ensure safety is essential in applications such as revenue management, clinical trials, and financial investment, but has not been well studied. This work tries to provide a detailed characterization of regret distribution in online learning under the safety concern of managing tail risk.

In Part I, we aim to design policies that enjoy both optimal regret expectation and light-tailed regret distribution. We first find that any policy that obtains the optimal instance-dependent regret expectation could incur a heavy-tailed regret tail risk. We then design a novel policy that enjoys the optimal worst-case regret expectation and has the optimal worst-case regret tail risk with an optimal exponential decaying rate for any regret threshold. Numerical experiments show that our new policy design leads to similar efficiency and much better safety compared to celebrated policies. Our policy design also bears an interesting connection with Monte Carlo Tree Search (MCTS) used in AlphaGo. In Part II, we study the optimal trade-off between expectation and tail risk for regret distribution. We fully characterize the interplay among three desired properties for policy design: worst-case optimality, instance-dependent consistency, and light-tailed risk. Our results reveal several insights on how to design policies that balance efficiency and safety. All our results are extended to the stochastic linear bandit setting.