How does Bayesian Optimization balance exploration with exploitation?

Question

I'm decently familiar with Gaussian Processes; I understand that GPs form the backbone of BO but I don't want this question to drift in scope towards an explanation of GPs. Rather, I'm curious, how does BO make decisions given a gaussian process as a surrogate function?

The GP models the problem parameters (to be optimized) as inputs, X, and the corresponding rewards as outputs, y, learning a smooth function that estimates rewards between adjacent observations (specific combinations of parameters to be optimized.) This is the surrogate function.

I can think of a few ways which a system might make parameter adjustments:

1. Pick the parameter configuration corresponding to the absolute highest reward observed (Exploitation.)
2. pick the highest variance region (few observations nearby) and observe what happens (Exploration.)
3. Use reward and variance in some ranking scheme to decide where to move next.

Examples

Ex 1: A very small reward with extremely low variance- should be avoided.

Ex 2: A very high reward with very high variance- probably should be explored more to reduce variance around estimate.

Ex 3: A very high reward with very little variance- probably should not be explored further, however, may be the optimal parameter configuration.

Ex 4: Very low reward with very high variance- probably should be explored to reduce variance around estimate (but perhaps less so than in example 2?)

In answering this question, could you elaborate on how variance and reward are used to inform which regions of the surrogate function ought to be explored most vs least- what is this ranking metric/system?

Likewise, the term acquisition function appears to be very closely related to what I'm asking, but what is it and how does it guide exploration/exploitation?

Answer 1

In Bayesian optimization (BO), one chooses the next sampling point by maximizing the acquisition function $a(x)$, i.e. \begin{equation} x^* = \arg\max_{x\in\mathcal{X}} a(x). \end{equation}

This acquisition function is the key to the balance between exploration and exploitation. There are so many acquisition functions out there but I will list the most common three: the probability of improvement (PI), expected improvement (EI), and upper-confidence bound (UCB).

Assuming that you want to solve a maximization problem, let's take UCB acquisition function because it is easy to type: $a(x) = \mu(x) + \kappa \sigma(x)$. Let's also assume $\kappa$ is a constant for now, e.g. $\kappa = 2$.

Comparing two points $x_1$ and $x_2$: if their means are the same, then BO will pick the one that has larger $\sigma^2(x)$. This is called exploration.

Comparing two points $x_1$ and $x_2$: if their variances are the same, then BO will pick the one that has larger $\mu(x)$. This is called exploitation.

Answer 2

Adding some lines to the previous answer. The constant κ trades-off between exploration-exploitation. If the κ is high, it will focus towards high variance/point from high uncertainty. if it is very low, the variance portion will get suppressed and it will keep focusing on already good result. Picking the right κ is the challenge because you don't know the optimal κ. Optimal κ is different for different optimization problems.

A few researchers are studying to develop generalized method to figure out κ.

A reference