  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 $\mathcal{O}(\frac{logN}{\sqrt{N}})$
to $\mathcal O(e^{-\sqrt{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^{-\sqrt{N}})$ under the assumption that the objective
function is sampled from a Gaussian process with a Mat\'ern kernel with
smoothness parameter $\nu > 4 +\frac{D}{2}$, 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.
