Part 4 · The Maths II: Acquisition Functions
Paying for the knowledge gradient
The definition contains an optimization inside an expectation inside an optimization. Written naively you would, for each candidate x, average over possible observed values, and for each of those refit the GP and maximize its posterior mean over the domain. That is far more expensive than EI's closed form, and it is the only reason KG is not the default.
Three ideas make it affordable.
Discretize the inner maximum. Replace max over the domain with a max over a finite candidate set. The inner problem becomes the maximum of a collection of lines in the unobserved value, which has an exact and cheap solution — the discrete-prior algorithm of Frazier, Powell and Dayanik, extended to correlated Gaussian process beliefs by Scott, Frazier and Powell as the KGCP.
Differentiate through the sample average. Draw a fixed set of “fantasy” observations, and note that by the envelope theorem you do not need to differentiate through the inner argmax — only through the objective at that argmax. KG then becomes a stochastic optimization problem solvable with ordinary gradient methods.
Optimize jointly, in one shot. The one-shot reformulation of BoTorch (arXiv:1910.06403) treats the fantasy maximizers as decision variables alongside x, turning the nested problem into a single deterministic optimization over a higher-dimensional space. This is what makes KG practical in modern libraries.
The same machinery extends where EI's closed form cannot follow. q-KG (arXiv:1606.04414) gives the Bayes-optimal batch, and unlike heuristic batch-EI it accounts for noise directly. d-KG (arXiv:1703.04389) incorporates gradient observations when they are available, which is common when the objective is itself a training run. Multi-fidelity variants value a cheap approximate evaluation by how much it will improve the recommendation you would make about the expensive one — a question EI cannot even phrase, because a low-fidelity observation never improves the true incumbent.
When to reach for it. With cheap, noiseless evaluations and a low-dimensional space, EI is close to KG and vastly cheaper — use EI. Reach for KG when observations are noisy, when you must commit to a final recommendation rather than return the best point seen, when you are combining fidelities or sources, or when gradients are available. The honest summary is that KG buys a better decision rule with compute, and whether that trade is worth it depends on how expensive your evaluations are relative to your optimizer.