# Provably Efficient Online Hyperparameter Optimization with Population-Based Bandits

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

## Key facts

- Cited by 63 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Feb 2020.

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

- [Hyperparameter Optimization: Foundations, Algorithms, Best Practices and Open Challenges](https://mlsanity.com/paper/2107.05847/) (2021)
- [Automated Reinforcement Learning (AutoRL): A Survey and Open Problems](https://mlsanity.com/paper/2201.03916/) (2022)
- [Hyperparameters in Reinforcement Learning and How To Tune Them](https://mlsanity.com/paper/2306.01324/) (2023)
- [Think Global and Act Local: Bayesian Optimisation over High-Dimensional Categorical and Mixed Search Spaces](https://mlsanity.com/paper/2102.07188/) (2021)
- [Revisiting Design Choices in Offline Model-Based Reinforcement Learning](https://mlsanity.com/paper/2110.04135/) (2021)
- [Contextualize Me -- The Case for Context in Reinforcement Learning](https://mlsanity.com/paper/2202.04500/) (2022)
- [AutoML in the Age of Large Language Models: Current Challenges, Future Opportunities and Risks](https://mlsanity.com/paper/2306.08107/) (2023)
- [Evolution Strategies at the Hyperscale](https://mlsanity.com/paper/2511.16652/) (2025)
- [A survey on multi-objective hyperparameter optimization algorithms for Machine Learning](https://mlsanity.com/paper/2111.13755/) (2021)
- [CARL: A Benchmark for Contextual and Adaptive Reinforcement Learning](https://mlsanity.com/paper/2110.02102/) (2021)
- [Bayesian Generational Population-Based Training](https://mlsanity.com/paper/2207.09405/) (2022)
- [Scalarization for Multi-Task and Multi-Domain Learning at Scale](https://mlsanity.com/paper/2310.08910/) (2023)
- [Distributionally Robust Bayesian Optimization with varphi-divergences](https://mlsanity.com/paper/2203.02128/) (2022)
- [Scaling Laws for Hyperparameter Optimization](https://mlsanity.com/paper/2302.00441/) (2023)
- [Structure in Deep Reinforcement Learning: A Survey and Open Problems](https://mlsanity.com/paper/2306.16021/) (2023)
- [Supervising the Multi-Fidelity Race of Hyperparameter Configurations](https://mlsanity.com/paper/2202.09774/) (2022)
- [AutoLRS: Automatic Learning-Rate Schedule by Bayesian Optimization on the Fly](https://mlsanity.com/paper/2105.10762/) (2021)
- [On Controller Tuning with Time-Varying Bayesian Optimization](https://mlsanity.com/paper/2207.11120/) (2022)
- [Theory-inspired Parameter Control Benchmarks for Dynamic Algorithm Configuration](https://mlsanity.com/paper/2202.03259/) (2022)
- [Time-Varying Gaussian Process Bandits with Unknown Prior](https://mlsanity.com/paper/2402.01632/) (2024)
- [Reinforcement Learning and Bandits for Speech and Language Processing: Tutorial, Review and Outlook](https://mlsanity.com/paper/2210.13623/) (2022)
- [Automated Reinforcement Learning: An Overview](https://mlsanity.com/paper/2201.05000/) (2022)
- [A Lipschitz Bandits Approach for Continuous Hyperparameter Optimization](https://mlsanity.com/paper/2302.01539/) (2023)
- [Tuning Mixed Input Hyperparameters on the Fly for Efficient Population Based AutoRL](https://mlsanity.com/paper/2106.15883/) (2021)
- [AutoRL Hyperparameter Landscapes](https://mlsanity.com/paper/2304.02396/) (2023)
- [Hyperparameter Tuning for Deep Reinforcement Learning Applications](https://mlsanity.com/paper/2201.11182/) (2022)
- [Event-Triggered Time-Varying Bayesian Optimization](https://mlsanity.com/paper/2208.10790/) (2022)
- [No More Pesky Hyperparameters: Offline Hyperparameter Tuning for RL](https://mlsanity.com/paper/2205.08716/) (2022)
- [Episodic Policy Gradient Training](https://mlsanity.com/paper/2112.01853/) (2021)
- [Combining Automated Optimisation of Hyperparameters and Reward Shape](https://mlsanity.com/paper/2406.18293/) (2024)

## Abstract (arXiv)

Many of the recent triumphs in machine learning are dependent on well-tuned hyperparameters. This is particularly prominent in reinforcement learning (RL) where a small change in the configuration can lead to failure. Despite the importance of tuning hyperparameters, it remains expensive and is often done in a naive and laborious way. A recent solution to this problem is Population Based Training (PBT) which updates both weights and hyperparameters in a single training run of a population of agents. PBT has been shown to be particularly effective in RL, leading to widespread use in the field. However, PBT lacks theoretical guarantees since it relies on random heuristics to explore the hyperparameter space. This inefficiency means it typically requires vast computational resources, which is prohibitive for many small and medium sized labs. In this work, we introduce the first provably efficient PBT-style algorithm, Population-Based Bandits (PB2). PB2 uses a probabilistic model to guide the search in an efficient way, making it possible to discover high performing hyperparameter configurations with far fewer agents than typically required by PBT. We show in a series of RL experiments that PB2 is able to achieve high performance with a modest computational budget.