# Bayesian Optimistic Optimisation with Exponentially Decaying Regret

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 35 references that are in the map.
- First posted on arXiv 10 May 2021.

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

- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [On Kernelized Multi-armed Bandits](https://mlsanity.com/paper/1704.00445/) (2017)
- [Predictive Entropy Search for Efficient Global Optimization of Black-box Functions](https://mlsanity.com/paper/1406.2541/) (2014)
- [Gaussian Processes and Kernel Methods: A Review on Connections and Equivalences](https://mlsanity.com/paper/1807.02582/) (2018)
- [High Dimensional Bayesian Optimisation and Bandits via Additive Models](https://mlsanity.com/paper/1503.01673/) (2015)
- [Batched Large-scale Bayesian Optimization in High-dimensional Spaces](https://mlsanity.com/paper/1706.01445/) (2017)
- [Learning Search Space Partition for Black-box Optimization using Monte Carlo Tree Search](https://mlsanity.com/paper/2007.00708/) (2020)
- [Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization](https://mlsanity.com/paper/1706.00090/) (2017)
- [Bandit optimisation of functions in the Mat'ern kernel RKHS](https://mlsanity.com/paper/2001.10396/) (2020)
- [Bayesian Optimization with Exponential Convergence](https://mlsanity.com/paper/1604.01348/) (2016)
- [Bayesian Multi-Scale Optimistic Optimization](https://mlsanity.com/paper/1402.7005/) (2014)
- [Trading Convergence Rate with Computational Budget in High Dimensional Bayesian Optimization](https://mlsanity.com/paper/1911.11950/) (2019)
- [Sub-linear Regret Bounds for Bayesian Optimisation in Unknown Search Spaces](https://mlsanity.com/paper/2009.02539/) (2020)
- [Embedded Bandits for Large-Scale Black-Box Optimization](https://mlsanity.com/paper/1611.08773/) (2016)
- [Multi-Objective Simultaneous Optimistic Optimization](https://mlsanity.com/paper/1612.08412/) (2016)

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

- [Regret Bounds for Expected Improvement Algorithms in Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2203.07875/) (2022)
- [BioBO: Biology-informed Bayesian Optimization for Perturbation Design](https://mlsanity.com/paper/2509.19988/) (2025)
- [Optimistic Optimization of Gaussian Process Samples](https://mlsanity.com/paper/2209.00895/) (2022)

## Abstract (arXiv)

Bayesian optimisation (BO) is a well-known efficient algorithm for finding the global optimum of expensive, black-box functions. The current practical BO algorithms have regret bounds ranging from O(fraclogN√N) to mathcal O(e^-√N), where N is the number of evaluations. This paper explores the possibility of improving the regret bound in the noiseless setting by intertwining concepts from BO and tree-based optimistic optimisation which are based on partitioning the search space. We propose the BOO algorithm, a first practical approach which can achieve an exponential regret bound with order mathcal O(N^-√N) under the assumption that the objective function is sampled from a Gaussian process with a Mat'ern kernel with smoothness parameter nu > 4 +fracD2, where D is the number of dimensions. We perform experiments on optimisation of various synthetic functions and machine learning hyperparameter tuning tasks and show that our algorithm outperforms baselines.