Optimal $δ$-Correct Best-Arm Selection for Heavy-Tailed Distributions
This addresses a classic best-arm selection problem in learning applications like recommendation systems, but is incremental as it extends prior work from exponential families to heavy-tailed distributions.
The paper tackles the problem of identifying the best arm with maximum mean using a δ-correct algorithm for heavy-tailed distributions, showing that without restrictions, infinite samples are needed, and proposes an algorithm that matches the lower bound asymptotically as δ→0 under mild moment conditions, with batch processing to speed it up.
Given a finite set of unknown distributions or arms that can be sampled, we consider the problem of identifying the one with the maximum mean using a $δ$-correct algorithm (an adaptive, sequential algorithm that restricts the probability of error to a specified $δ$) that has minimum sample complexity. Lower bounds for $δ$-correct algorithms are well known. $δ$-correct algorithms that match the lower bound asymptotically as $δ$ reduces to zero have been previously developed when arm distributions are restricted to a single parameter exponential family. In this paper, we first observe a negative result that some restrictions are essential, as otherwise, under a $δ$-correct algorithm, distributions with unbounded support would require an infinite number of samples in expectation. We then propose a $δ$-correct algorithm that matches the lower bound as $δ$ reduces to zero under the mild restriction that a known bound on the expectation of $(1+ε)^{th}$ moment of the underlying random variables exists, for $ε> 0$. We also propose batch processing and identify near-optimal batch sizes to speed up the proposed algorithm substantially. The best-arm problem has many learning applications, including recommendation systems and product selection. It is also a well-studied classic problem in the simulation community.