# Bayesian Optimisation with Unknown Hyperparameters: Regret Bounds Logarithmically Closer to Optimal

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 41 references that are in the map.
- First posted on arXiv 14 Oct 2024.

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

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Pyro: Deep Universal Probabilistic Programming](https://mlsanity.com/paper/1810.09538/) (2018)
- [On Kernelized Multi-armed Bandits](https://mlsanity.com/paper/1704.00445/) (2017)
- [On Information Gain and Regret Bounds in Gaussian Process Bandits](https://mlsanity.com/paper/2009.06966/) (2020)
- [High-Dimensional Bayesian Optimization with Sparse Axis-Aligned Subspaces](https://mlsanity.com/paper/2103.00349/) (2021)
- [Corralling a Band of Bandit Algorithms](https://mlsanity.com/paper/1612.06246/) (2016)
- [HEBO Pushing The Limits of Sample-Efficient Hyperparameter Optimisation](https://mlsanity.com/paper/2012.03826/) (2020)
- [Misspecified Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2111.05008/) (2021)
- [No-Regret Bayesian Optimization with Unknown Hyperparameters](https://mlsanity.com/paper/1901.03357/) (2019)
- [Regret Bound Balancing and Elimination for Model Selection in Bandits and RL](https://mlsanity.com/paper/2012.13045/) (2020)
- [Are Random Decompositions all we need in High Dimensional Bayesian Optimisation?](https://mlsanity.com/paper/2301.12844/) (2023)
- [Inducing Point Allocation for Sparse Gaussian Processes in High-Throughput Bayesian Optimisation](https://mlsanity.com/paper/2301.10123/) (2023)
- [Theoretical Analysis of Bayesian Optimisation with Unknown Gaussian Process Hyper-Parameters](https://mlsanity.com/paper/1406.7758/) (2014)
- [Regret bounds for meta Bayesian optimization with an unknown Gaussian process prior](https://mlsanity.com/paper/1811.09558/) (2018)
- [Self-Correcting Bayesian Optimization through Bayesian Active Learning](https://mlsanity.com/paper/2304.11005/) (2023)
- [Regret Balancing for Bandit and RL Model Selection](https://mlsanity.com/paper/2006.05491/) (2020)
- [BOiLS: Bayesian Optimisation for Logic Synthesis](https://mlsanity.com/paper/2111.06178/) (2021)
- [Gaussian Process Uniform Error Bounds with Unknown Hyperparameters for Safety-Critical Applications](https://mlsanity.com/paper/2109.02606/) (2021)
- [An Optimization-based Algorithm for Non-stationary Kernel Bandits without Prior Knowledge](https://mlsanity.com/paper/2205.14775/) (2022)
- [Fast Bayesian Optimization of Needle-in-a-Haystack Problems using Zooming Memory-Based Initialization (ZoMBI)](https://mlsanity.com/paper/2208.13771/) (2022)
- [Time-Varying Gaussian Process Bandits with Unknown Prior](https://mlsanity.com/paper/2402.01632/) (2024)
- [How Bayesian Should Bayesian Optimisation Be?](https://mlsanity.com/paper/2105.00894/) (2021)
- [Adaptation to Misspecified Kernel Regularity in Kernelised Bandits](https://mlsanity.com/paper/2304.13830/) (2023)
- [A Quadrature Approach for General-Purpose Batch Bayesian Optimization via Probabilistic Lifting](https://mlsanity.com/paper/2404.12219/) (2024)

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

- [Adaptive Prior Selection in Gaussian Process Bandits with Thompson Sampling](https://mlsanity.com/paper/2502.01226/) (2025)
- [Just One Layer Norm Guarantees Stable Extrapolation](https://mlsanity.com/paper/2505.14512/) (2025)
- [Informed Initialization for Bayesian Optimization and Active Learning](https://mlsanity.com/paper/2510.23681/) (2025)
- [Regret Analysis of Guided Diffusion for Black-Box Optimization over Structured Inputs](https://mlsanity.com/paper/2605.10385/) (2026)
- [Vector Optimization with Gaussian Process Bandits](https://mlsanity.com/paper/2412.02484/) (2024)
- [Online Sharp-Calibrated Bayesian Optimization](https://mlsanity.com/paper/2605.10572/) (2026)
- [Bayesian Optimization of CVaR with Unknown Hyperparameters](https://mlsanity.com/paper/2610.18306/) (2026)

## Abstract (arXiv)

Bayesian Optimization (BO) is widely used for optimising black-box functions but requires us to specify the length scale hyperparameter, which defines the smoothness of the functions the optimizer will consider. Most current BO algorithms choose this hyperparameter by maximizing the marginal likelihood of the observed data, albeit risking misspecification if the objective function is less smooth in regions we have not yet explored. The only prior solution addressing this problem with theoretical guarantees was A-GP-UCB, proposed by Berkenkamp et al. (2019). This algorithm progressively decreases the length scale, expanding the class of functions considered by the optimizer. However, A-GP-UCB lacks a stopping mechanism, leading to over-exploration and slow convergence. To overcome this, we introduce Length scale Balancing (LB) - a novel approach, aggregating multiple base surrogate models with varying length scales. LB intermittently adds smaller length scale candidate values while retaining longer scales, balancing exploration and exploitation. We formally derive a cumulative regret bound of LB and compare it with the regret of an oracle BO algorithm using the optimal length scale. Denoting the factor by which the regret bound of A-GP-UCB was away from oracle as g(T), we show that LB is only log g(T) away from oracle regret. We also empirically evaluate our algorithm on synthetic and real-world benchmarks and show it outperforms A-GP-UCB, maximum likelihood estimation and MCMC.