Explore, Refine, then Commit: Nearly Optimal Multi-Group Mean Estimation with Active Learning

摘要

We present nearly optimal algorithms for simultaneously estimating the means of multiple distributions given a fixed total sample budget while ensuring uniform confidence intervals for the distributions. Our algorithms are based on the well-known _explore-then-commit_ policy from the bandit literature along with an additional refinement phase between the exploration phase and the commit phase. Our algorithms achieve regret Õ( (logσ_min^-1)^0.5 T^-1.5) when the rewards are subgaussian and Õ(σ_min^-1T^-1.5) regret when the rewards have bounded fourth moment, where T is the horizon and σ_min^2 is the minimum among the variances of the distributions of the G arms. We also provide lower bounds on the regret that nearly match the upper bounds for a constant G in both these cases. IImportantly, we show that the dependence on σ_min in both cases is necessary, resolving a long-standing open problem of [Carpentier et al]. We also study the setting where the distributions are hypercontractive. This distribution class includes the family of Gaussian distributions but also includes several families of heavy-tailed distributions. We propose an algorithm for hypercontractive reward distributions that achieves a Õ(T^-1.5) regret, independent of σ_min, and show a nearly matching lower bound for Gaussians.