# Sub-linear Regret Bounds for Bayesian Optimisation in Unknown Search Spaces

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

## Key facts

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

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

- [Regret Bounds for Expected Improvement Algorithms in Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2203.07875/) (2022)
- [Model-Based Transfer Learning for Contextual Reinforcement Learning](https://mlsanity.com/paper/2408.04498/) (2024)
- [High Dimensional Bayesian Optimization using Lasso Variable Selection](https://mlsanity.com/paper/2504.01743/) (2025)
- [Bayesian Optimistic Optimisation with Exponentially Decaying Regret](https://mlsanity.com/paper/2105.04332/) (2021)
- [Predicting the utility of search spaces for black-box optimization: a simple, budget-aware approach](https://mlsanity.com/paper/2112.08250/) (2021)

## Abstract (arXiv)

Bayesian optimisation is a popular method for efficient optimisation of expensive black-box functions. Traditionally, BO assumes that the search space is known. However, in many problems, this assumption does not hold. To this end, we propose a novel BO algorithm which expands (and shifts) the search space over iterations based on controlling the expansion rate thought a hyperharmonic series. Further, we propose another variant of our algorithm that scales to high dimensions. We show theoretically that for both our algorithms, the cumulative regret grows at sub-linear rates. Our experiments with synthetic and real-world optimisation tasks demonstrate the superiority of our algorithms over the current state-of-the-art methods for Bayesian optimisation in unknown search space.