Acquisition Functions: Deciding Where to Look Next

The surrogate describes what you believe about the objective. It does not tell you what to do. At every candidate point the Gaussian process reports a mean and a variance, and you must collapse those into a single scalar score so you can pick the highest-scoring point and evaluate it.

That scoring rule is the acquisition function. It is cheap to compute, so you optimize it thoroughly over the whole input space, using ordinary gradient or grid methods, to find where it peaks. Then you pay for exactly one expensive evaluation there.

Every acquisition function is a different answer to one question: how should a high predicted mean, which argues for exploiting, be weighed against a high variance, which argues for exploring? The three that follow are the canonical answers.

This tension is the same one at the heart of the multi-armed bandit, covered in reinforcement-learning-foundations. Exploit and you sample where the surrogate already predicts a good value, refining a known-promising region. Explore and you sample where the surrogate is most uncertain, testing whether something better is hiding.

Neither extreme works. Pure exploitation converges immediately onto the best point seen so far and never discovers the taller peak two regions over: it gets trapped in a local optimum. Pure exploration samples the most uncertain point every time, spreading effort uniformly and never settling to refine the best region it has found.

An acquisition function is a principled compromise between these, and the differences among the popular ones are mostly differences in how that compromise is struck and whether it comes with a guarantee.

The simplest useful rule is Probability of Improvement. Let the best value observed so far be the incumbent. For each candidate, the GP gives a full Gaussian over its possible value, so you can compute the probability that this value beats the incumbent, and score the candidate by that probability.

It is intuitive and easy, but it has a known flaw: it is greedy. A point predicted to be a whisker above the incumbent with tiny uncertainty gets a probability near one, while a point that might be far better but is less certain scores lower. So PI over-exploits, clustering queries just past the current best and rarely taking the larger gamble.

A standard patch adds a margin, requiring a candidate to beat the incumbent by some amount before it counts, which forces a little more exploration. Even patched, PI is mostly a stepping stone to the next idea.

Expected Improvement fixes the greed by scoring not the probability of beating the incumbent but the expected amount by which it is beaten. A point that will probably improve by a tiny margin and a point that will occasionally improve by a huge margin can now score equally, so large uncertain upside competes fairly with small certain gains.

The expectation has a clean closed form from the GP's Gaussian, so it stays cheap to optimize. The idea traces to Jonas Mockus in the 1970s, and it became the workhorse of the field through the 1998 Efficient Global Optimization algorithm of Donald Jones, Matthias Schonlau, and William Welch, published in the Journal of Global Optimization.

EI has a natural, parameter-free balance: the expectation is large either when the mean is high or when the variance is high, so exploration and exploitation fall out of one formula. It remains the default acquisition function in many libraries.

GP-UCB takes a different route, borrowed directly from the bandit literature: optimism in the face of uncertainty. Instead of reasoning about improvement, it scores each point by an optimistic guess of its value, the posterior mean plus a multiple of the standard deviation.

The score is mean plus beta times standard deviation. Reading it is easy: a point scores well if its predicted value is high, or if its uncertainty is high, or both. The parameter beta is the single exploration dial. Small beta trusts the mean and exploits; large beta inflates the uncertainty bonus and explores.

The principle is to act as if each point is as good as its confidence interval plausibly allows. If that optimism proves right, you found a great point; if it proves wrong, you learned a lot about a high-uncertainty region. Either outcome is progress.

GP-UCB matters beyond its simplicity because it comes with a guarantee, established by Niranjan Srinivas, Andreas Krause, Sham Kakade, and Matthias Seeger in their 2010 ICML paper "Gaussian Process Optimization in the Bandit Setting". Krause leads the Learning and Adaptive Systems group at ETH Zurich and directs the ETH AI Center.

The result concerns regret, the gap between the best value you could have found and what you actually sampled, summed over all queries. They proved that with a suitable schedule for beta, GP-UCB achieves sublinear cumulative regret: the total regret grows more slowly than the number of evaluations, so the average regret tends to zero and the method provably converges to the optimum.

This was the first algorithm to give such rates for this setting, connecting the bound to how fast the kernel lets information accumulate. The paper received the ICML Test of Time Award in 2020.

A third rule sidesteps hand-designed scores. Thompson sampling, named for a 1933 idea of William R. Thompson, draws one random function from the GP posterior and picks the point that maximizes that single sample.

Because the sample is random, well-explored regions, where the posterior is tight, produce nearly the same sample every time, while uncertain regions vary wildly between draws. So the method naturally explores in proportion to uncertainty: an uncertain region occasionally produces a sample with a high peak there, and gets probed, without any explicit exploration parameter.

Its practical strength is parallelism. To choose a batch of points to evaluate at once, you draw several independent posterior samples and take the maximizer of each; they scatter across promising and uncertain regions automatically. That makes Thompson sampling a common choice when you can run many expensive evaluations simultaneously.

For most single-query problems the choice is not decisive, and Expected Improvement is a sound default. The distinctions matter when you need a specific property.

Reach for GP-UCB when you want an explicit exploration dial or the theoretical guarantee. Reach for Thompson sampling when you are running a batch of evaluations in parallel. Reach for Expected Improvement when you want a strong, assumption-light default and are querying one point at a time. All four consume nothing but the GP's mean and variance, so switching between them is a one-line change in practice.

One subtlety completes the picture. You solve an expensive black-box optimization by repeatedly solving a cheap one: maximizing the acquisition function to find the next query.

That inner problem is friendly. The acquisition surface is cheap to evaluate, and for EI and GP-UCB you can even compute its gradient, so you attack it with ordinary optimizers, usually restarted from many points because it too can be multimodal. This is the trade at the core of the method: convert one costly, gradient-free problem into a sequence of cheap, well-behaved ones.

With a surrogate and an acquisition function in hand, you have a complete algorithm. The final lesson turns it into practice: the tools that implement it, tuning machine-learning models as the flagship use, and the situations where it falls short.