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

• 成果类型: Article
• 署名作者: Simchi-Levi, David; Zheng, Zeyu; Zhu, Feng
• 署名单位: Massachusetts Institute of Technology (MIT); University of California System; University of California Berkeley; Massachusetts Institute of Technology (MIT)
• 刊物名称: MANAGEMENT SCIENCE
• ISSN/ISSBN: 0025-1909
• DOI: 10.1287/mnsc.2022.03512
• 发表日期: 2025
• 页码: 6298-6318
• 关键词: stochastic bandits; worst-case optimality; instance-dependent consistency; Tail risk; safety

摘要

We study the stochastic multi-armed bandit problem and design new policies that enjoy both optimal regret expectation and light-tailed risk for regret distribution. We first find that any policy that obtains the optimal instance-dependent expected regret could incur a heavy-tailed regret tail risk that decays slowly with T. We then focus on policies that achieve optimal worst-case expected regret. We design a novel policy that (i) enjoys the worst-case optimality for regret expectation and (ii) has the worst-case tail probability of incurring a regret larger than any regret threshold that decays exponentially with respect to T. The decaying rate is proved to be optimal 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 with standard confidence-bound-based policies. We also enhance the policy design to accommodate the any-time setting where T is unknown a priori, highlighting lifelong exploration, and prove equivalently desired policy performances as compared with the fixed-time setting with known T. From a managerial perspective, we show through numerical experiments that our new policy design yields similar efficiency and better safety compared to celebrated policies. Our policy design is preferable especially when (i) there is a risk of underestimating 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 regret expectation and light-tailed risk on regret distribution.