How to determine the optimal exploitation-exploration trade off for a fixed number of objective function evaluations

Question

In Bayesian optimization, we guess the next sampling point by finding $x = \textrm{argmax}_x \alpha(x)$, where $\alpha(x)$ is the acquisition function. For simplicity, let us consider the upper confidence bound (UCB) acquisition function: $\alpha(x)=\mu(x) + \sqrt\beta \sigma(x)$, where $\mu(x)$ is the usual mean and $\sigma(x)$ denotes the usual square root of the variance. Here, $\beta$ is of course the dimensionless parameter ($\beta\geq0$) that tunes the trade off between exploration (high $\beta$) and exploitation (low $\beta$).

Suppose I have a computational or experimental budget of $N$ evaluations of the objective function. Is there an algorithm or heuristic for setting $\beta$ as a function of $N$?

Answer 1

Srinivas et al's 2010 paper Gaussian Process Optimization in the Bandit Setting is one foundational paper introducing the GP-UCB framework which is often referenced when discussing $\beta$ scheduling in Bayesian optimization. They provided theoretical analysis for the choice of $\beta$ and suggest scaling $\beta$ with a kind of logarithm schedule heuristic which is optimal in terms of regret bounds.

We formalize this task as a multiarmed bandit problem, where the payoff function is either sampled from a Gaussian process (GP) or has low RKHS norm... In our experiments on real sensor data, GP-UCB compares favorably with other heuristical GP optimization approaches... Theorem 2... $β_t=2\log(t^22π^2/(3δ)) + 2d\log(t^2dbrp\sqrt(\log(4da/δ)))$.

Considering evaluations budget bounded up by your fixed $N$, you can simply scale the above suggested schedule with $t/N$ or $\log(t+1)/\log(N+1)$ heuristically.