# Simple regret for infinitely many armed bandits

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

## Key facts

- Cited by 39 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 May 2015.

## Built on by (most cited first, 30 of 39)

- [Optimal Order Simple Regret for Gaussian Process Bandits](https://mlsanity.com/paper/2108.09262/) (2021)
- [Huxley-G"odel Machine: Human-Level Coding Agent Development by an Approximation of the Optimal Self-Improving Machine](https://mlsanity.com/paper/2510.21614/) (2025)
- [Revisiting Simple Regret: Fast Rates for Returning a Good Arm](https://mlsanity.com/paper/2210.16913/) (2022)
- [Practice Makes Perfect: Planning to Learn Skill Parameter Policies](https://mlsanity.com/paper/2402.15025/) (2024)
- [Bandits with many optimal arms](https://mlsanity.com/paper/2103.12452/) (2021)
- [Fast and Robust: Task Sampling with Posterior and Diversity Synergies for Adaptive Decision-Makers in Randomized Environments](https://mlsanity.com/paper/2504.19139/) (2025)
- [Sample Complexity and Representation Ability of Test-time Scaling Paradigms](https://mlsanity.com/paper/2506.05295/) (2025)
- [A Lipschitz Bandits Approach for Continuous Hyperparameter Optimization](https://mlsanity.com/paper/2302.01539/) (2023)
- [From Finite to Countable-Armed Bandits](https://mlsanity.com/paper/2105.10721/) (2021)
- [Non-stationary Bandits and Meta-Learning with a Small Set of Optimal Arms](https://mlsanity.com/paper/2202.13001/) (2022)
- [Be Greedy in Multi-Armed Bandits](https://mlsanity.com/paper/2101.01086/) (2021)
- [On the Safety of Interpretable Machine Learning: A Maximum Deviation Approach](https://mlsanity.com/paper/2211.01498/) (2022)
- [Online Bandit Learning with Offline Preference Data for Improved RLHF](https://mlsanity.com/paper/2406.09574/) (2024)
- [Improving LLM-based Global Optimization with Search Space Partitioning](https://mlsanity.com/paper/2505.21372/) (2025)
- [Multi-armed Bandit Algorithm against Strategic Replication](https://mlsanity.com/paper/2110.12160/) (2021)
- [Rotting Infinitely Many-armed Bandits](https://mlsanity.com/paper/2201.12975/) (2022)
- [Speed Up the Cold-Start Learning in Two-Sided Bandits with Many Arms](https://mlsanity.com/paper/2210.00340/) (2022)
- [Beyond the Best: Estimating Distribution Functionals in Infinite-Armed Bandits](https://mlsanity.com/paper/2211.01743/) (2022)
- [Non-Stationary Lipschitz Bandits](https://mlsanity.com/paper/2505.18871/) (2025)
- [A Bandit Approach with Evolutionary Operators for Model Selection](https://mlsanity.com/paper/2402.05144/) (2024)
- [An Adaptive Approach for Infinitely Many-armed Bandits under Generalized Rotting Constraints](https://mlsanity.com/paper/2404.14202/) (2024)
- [Periodic-GP: Learning Periodic World with Gaussian Process Bandits](https://mlsanity.com/paper/2105.14422/) (2021)
- [Bandits with Dynamic Arm-acquisition Costs](https://mlsanity.com/paper/2110.12118/) (2021)
- [Discover Life Skills for Planning with Bandits via Observing and Learning How the World Works](https://mlsanity.com/paper/2207.08130/) (2022)
- [Max-Quantile Grouped Infinite-Arm Bandits](https://mlsanity.com/paper/2210.01295/) (2022)
- [HPC Application Parameter Autotuning on Edge Devices: A Bandit Learning Approach](https://mlsanity.com/paper/2501.01057/) (2025)
- [Tracking Most Significant Shifts in Infinite-Armed Bandits](https://mlsanity.com/paper/2502.00108/) (2025)
- [Control-Data Separation and Logical Condition Propagation for Efficient Inference on Probabilistic Programs](https://mlsanity.com/paper/2101.01502/) (2021)
- [Nonstochastic Bandits with Infinitely Many Experts](https://mlsanity.com/paper/2102.05164/) (2021)
- [Improving Sequential Query Recommendation with Immediate User Feedback](https://mlsanity.com/paper/2205.06297/) (2022)

## Abstract (arXiv)

We consider a stochastic bandit problem with infinitely many arms. In this setting, the learner has no chance of trying all the arms even once and has to dedicate its limited number of samples only to a certain number of arms. All previous algorithms for this setting were designed for minimizing the cumulative regret of the learner. In this paper, we propose an algorithm aiming at minimizing the simple regret. As in the cumulative regret setting of infinitely many armed bandits, the rate of the simple regret will depend on a parameter β characterizing the distribution of the near-optimal arms. We prove that depending on β, our algorithm is minimax optimal either up to a multiplicative constant or up to a log(n) factor. We also provide extensions to several important cases: when β is unknown, in a natural setting where the near-optimal arms have a small variance, and in the case of unknown time horizon.