# Asymptotically Optimal Pure Exploration for Infinite-Armed Bandits

arXiv: https://arxiv.org/abs/2306.01995 · HTML: https://mlsanity.com/paper/2306.01995/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 45 references that are in the map.
- First posted on arXiv 3 Jun 2023.

## Builds on (most cited first, 18 of 18)

- [Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization](https://mlsanity.com/paper/1603.06560/) (2016)
- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits](https://mlsanity.com/paper/1312.7308/) (2013)
- [Batched Multi-armed Bandits Problem](https://mlsanity.com/paper/1904.01763/) (2019)
- [Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem](https://mlsanity.com/paper/1605.09004/) (2016)
- [An elementary introduction to information geometry](https://mlsanity.com/paper/1808.08271/) (2018)
- [The True Sample Complexity of Identifying Good Arms](https://mlsanity.com/paper/1906.06594/) (2019)
- [Nearly Optimal Sampling Algorithms for Combinatorial Pure Exploration](https://mlsanity.com/paper/1706.01081/) (2017)
- [On the Optimal Sample Complexity for Best Arm Identification](https://mlsanity.com/paper/1511.03774/) (2015)
- [Bandits with many optimal arms](https://mlsanity.com/paper/2103.12452/) (2021)
- [Pure Exploration in Infinitely-Armed Bandit Models with Fixed-Confidence](https://mlsanity.com/paper/1803.04665/) (2018)
- [PAC Identification of Many Good Arms in Stochastic Multi-Armed Bandits](https://mlsanity.com/paper/1901.08386/) (2019)
- [Tight Lower Bound on the Probability of a Binomial Exceeding its Expectation](https://mlsanity.com/paper/1306.1433/) (2013)
- [On the exact Berk-Jones statistics and their p-value calculation](https://mlsanity.com/paper/1311.3190/) (2013)
- [Near Instance Optimal Model Selection for Pure Exploration Linear Bandits](https://mlsanity.com/paper/2109.05131/) (2021)
- [Exploring k out of Top ρ Fraction of Arms in Stochastic Bandits](https://mlsanity.com/paper/1810.11857/) (2018)
- [Amplification and Derandomization Without Slowdown](https://mlsanity.com/paper/1509.08123/) (2015)

## Abstract (arXiv)

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 varepsilon of being among the top η-fraction of arms; this is a natural adaptation of the classical PAC guarantee for infinite action sets. We consider both the fixed confidence and fixed budget settings, aiming respectively for minimal expected and fixed sample complexity. For fixed confidence, we give an algorithm with expected sample complexity Oleft(fraclog (1/η)log (1/δ)ηvarepsilon2right). This is optimal except for the log (1/η) factor, and the δ-dependence closes a quadratic gap in the literature. For fixed budget, we show the asymptotically optimal sample complexity as δ→ 0 is c-1log(1/δ)big(loglog(1/δ)big)2 to leading order. Equivalently, the optimal failure probability given exactly N samples decays as expbig(-cN/log2 Nbig), up to a factor 1± oN(1) inside the exponent. The constant 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 Grossman and Moshkovitz (FOCS 2016, SIAM Journal on Computing 2020).