A Simple and Optimal Policy Design with Safety against Heavy-tailed Risk for Multi-armed Bandits. (arXiv:2206.02969v3 [stat.ML] UPDATED)

We design new policies that ensure both worst-case optimality for expected
regret and light-tailed risk for regret distribution in the stochastic
multi-armed bandit problem. Recently, arXiv:2109.13595 showed that
information-theoretically optimized bandit algorithms suffer from some serious
heavy-tailed risk; that is, the worst-case probability of incurring a linear
regret slowly decays at a polynomial rate of $1/T$, as $T$ (the time horizon)
increases. Inspired by their results, we further show that widely used policies
(e.g., Upper Confidence Bound, Thompson Sampling) also …

arxiv design ml multi-armed bandits policy risk safety