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

David Simchi-Levi (), Zeyu Zheng () and Feng Zhu ()
Additional contact information
David Simchi-Levi: Institute for Data, Systems, and Society, Department of Civil and Environmental Engineering, Operations Research Center, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Zeyu Zheng: Department of Industrial Engineering and Operations Research, University of California, Berkeley, California 94720
Feng Zhu: Institute for Data, Systems, and Society, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139

Management Science, 2025, vol. 71, issue 7, 6298-6318

Abstract: 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.

Keywords: stochastic bandits; worst-case optimality; instance-dependent consistency; tail risk; safety (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.2022.03512 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:71:y:2025:i:7:p:6298-6318

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().