# Pure Exploration in Infinitely-Armed Bandit Models with Fixed-Confidence

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Mar 2018.

## Built on by (most cited first, 15 of 15)

- [Revisiting Simple Regret: Fast Rates for Returning a Good Arm](https://mlsanity.com/paper/2210.16913/) (2022)
- [Bandits with many optimal arms](https://mlsanity.com/paper/2103.12452/) (2021)
- [AC-Band: A Combinatorial Bandit-Based Approach to Algorithm Configuration](https://mlsanity.com/paper/2212.00333/) (2022)
- [Active Ranking of Experts Based on their Performances in Many Tasks](https://mlsanity.com/paper/2306.02628/) (2023)
- [On the Optimal Sample Complexity of Offline Multi-Armed Bandits with KL Regularization](https://mlsanity.com/paper/2605.02141/) (2026)
- [Beyond the Best: Estimating Distribution Functionals in Infinite-Armed Bandits](https://mlsanity.com/paper/2211.01743/) (2022)
- [A Bandit Approach with Evolutionary Operators for Model Selection](https://mlsanity.com/paper/2402.05144/) (2024)
- [Max-Quantile Grouped Infinite-Arm Bandits](https://mlsanity.com/paper/2210.01295/) (2022)
- [Stochastic Sample Approximations of (Local) Moduli of Continuity](https://mlsanity.com/paper/2509.15368/) (2025)
- [Active Bipartite Ranking with Smooth Posterior Distributions](https://mlsanity.com/paper/2602.24263/) (2026)
- [Asymptotically Optimal Pure Exploration for Infinite-Armed Bandits](https://mlsanity.com/paper/2306.01995/) (2023)
- [Exploration Unbound](https://mlsanity.com/paper/2407.12178/) (2024)
- [Probably Approximately Correct Maximum A Posteriori Inference](https://mlsanity.com/paper/2601.16083/) (2026)
- [When May a Model Replace the Experiment? Audits, Licenses, and the Price of Trust in Surrogate-Driven Design](https://mlsanity.com/paper/2608.01378/) (2026)
- [Bandits with Multiple Optimal Arms: Minimax Regret and Non-Adaptivity](https://mlsanity.com/paper/2609.38659/) (2026)

## Abstract (arXiv)

We consider the problem of near-optimal arm identification in the fixed confidence setting of the infinitely armed bandit problem when nothing is known about the arm reservoir distribution. We (1) introduce a PAC-like framework within which to derive and cast results; (2) derive a sample complexity lower bound for near-optimal arm identification; (3) propose an algorithm that identifies a nearly-optimal arm with high probability and derive an upper bound on its sample complexity which is within a log factor of our lower bound; and (4) discuss whether our log^2(1/delta) dependence is inescapable for "two-phase" (select arms first, identify the best later) algorithms in the infinite setting. This work permits the application of bandit models to a broader class of problems where fewer assumptions hold.