Asymptotically Optimal Quantile Pure Exploration for Infinite-Armed Bandits

We study pure exploration with infinitely many bandit arms generated i.i.d. from an unknown distribution. Our goal is to efficiently select a single high quality arm whose average reward is, with probability 1 - δ, within ε of being with the top η-fraction of arms. For fixed confidence, we give an algorithm with expected sample complexity (Equation presented)O (log(1/δηε)/ log(12/η)) which matches a known lower bound up to the log(1/η) factor. In particular the δ-dependence is optimal and closes a quadratic gap. For fixed budget, we show the asymptotically optimal sample complexity as δ → 0 is log(1/δ)(log log(1/δ))2/c. The value of c depends explicitly on the problem parameters (including the unknown arm distribution) through a certain Fisher information distance. Even the strictly super-linear dependence on log(1/δ) was not known and resolves a question of [GM20].