Revisiting Simple Regret Minimization in Multi-Armed Bandits. (arXiv:2210.16913v1 [cs.LG])

Simple regret is a natural and parameter-free performance criterion for
identifying a good arm in multi-armed bandits yet is less popular than the
probability of missing the best arm or an $\epsilon$-good arm, perhaps due to
lack of easy ways to characterize it. In this paper, we achieve improved simple
regret upper bounds for both data-rich ($T\ge n$) and data-poor regime ($T \le
n$) where $n$ is the number of arms and $T$ is the number of samples. At its …

arxiv multi-armed bandits