The acquisition zoo

Probability of improvement (Kushner, 1964) keeps only the probability and discards the magnitude: PI_n(x) = Φ(z). Its pathology is instructive: a point offering a near-certain microscopic gain outscores one offering a coin-flip at a large gain, so PI hugs the incumbent unless you hand-tune a margin ξ. EI fixed exactly this by weighting improvements by their size.

Upper confidence bound (GP-UCB; Srinivas et al., 2010) is optimism made explicit:

UCB_n(x) = μ_n(x) + β_n^½σ_n(x)

β_n the exploration weight, grown like log n to keep the confidence bound valid as evidence accumulates · a larger β buys more exploration

— act as if every point is as good as its confidence interval allows. Its gift is theory: with β_n growing logarithmically in n, cumulative regret is sublinear — BO provably converges. Its price is that β is a dial someone must set.

Information-theoretic acquisitions (Entropy Search, PES, and the practical favorite MES — Wang & Jegelka, 2017) change the question from “where might I improve?” to “which measurement most reduces my uncertainty about the optimum?” — MES scores the expected drop in entropy of the maximum value f^*. Less myopic in spirit, costlier to compute, and the natural choice when the goal is to learn where the optimum is rather than to rack up good evaluations.

Here are all three reading the same posterior — note how they disagree about where to go next:

Same six observations, same GP posterior (top); switch the acquisition (bottom) and watch the recommended next evaluation (red marker) move. EI and PI both spike in the gap around x ≈ 0.5 but weight it differently; UCB with β = 2 is happy to chase wide bands even where the mean is mediocre.

And here is the arithmetic itself — the quiz will ask you to do this by hand, so try a few settings (in particular Δ = 0):

← Improvement, and its expectation Numerics and batches: LogEI and qEI →