# An Asymptotically Optimal Multi-Armed Bandit Algorithm and Hyperparameter Optimization

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Jul 2020.

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

- [NAS-Bench-x11 and the Power of Learning Curves](https://mlsanity.com/paper/2111.03602/) (2021)
- [SODA: Self-organizing data augmentation in deep neural networks -- Application to biomedical image segmentation tasks](https://mlsanity.com/paper/2202.03223/) (2022)
- [FlexHB: a More Efficient and Flexible Framework for Hyperparameter Optimization](https://mlsanity.com/paper/2402.13641/) (2024)
- [A Review on Single-Problem Multi-Attempt Heuristic Optimization](https://mlsanity.com/paper/2509.26321/) (2025)

## Abstract (arXiv)

The evaluation of hyperparameters, neural architectures, or data augmentation policies becomes a critical model selection problem in advanced deep learning with a large hyperparameter search space. In this paper, we propose an efficient and robust bandit-based algorithm called Sub-Sampling (SS) in the scenario of hyperparameter search evaluation. It evaluates the potential of hyperparameters by the sub-samples of observations and is theoretically proved to be optimal under the criterion of cumulative regret. We further combine SS with Bayesian Optimization and develop a novel hyperparameter optimization algorithm called BOSS. Empirical studies validate our theoretical arguments of SS and demonstrate the superior performance of BOSS on a number of applications, including Neural Architecture Search (NAS), Data Augmentation (DA), Object Detection (OD), and Reinforcement Learning (RL).