The knowledge gradient: valuing what you will believe

Every criterion so far scores a point by what it might observe. The knowledge gradient scores it by what you will be able to conclude. The difference sounds philosophical and is entirely practical.

Suppose that when the budget runs out you must name a single answer — the input you would actually put into production. The sensible choice is the maximizer of the posterior mean. So the quantity worth buying is not a better observation, it is a better final recommendation:

KG_n(x) = 𝔼_n[ max_x′ μ_n+1(x′) ∣ x_n+1 = x ] − max_x′ μ_n(x′)

μ_n the posterior mean after n observations · μ_n+1 the posterior mean after sampling at x, which is random because the value has not been seen yet · 𝔼_n averages over that unseen value · the max runs over the whole domain, not just sampled points

Why this matters. KG is one-step Bayes-optimal for the decision you actually face: name the best input you can. EI is one-step Bayes-optimal for a different objective — improving the best value you have seen. When those two objectives diverge, EI optimizes the wrong thing.

They diverge in exactly two situations, and both are common.

Noise. EI is anchored to f^*_n, the best observed value. Under noise that anchor is itself a random variable, and it is biased upward — the largest of n noisy draws tends to be a lucky one. EI then chases an incumbent that may not be real. KG never mentions an observed value; it is built entirely from posterior means, so nothing lucky can anchor it.

Points that move the recommendation. EI scores a point by whether it might beat the observed best, so it clusters tightly around the incumbent. KG asks a different question — could an observation here relocate the peak of the posterior mean? — which favours points just outside the explored cluster, where a good draw would genuinely change your answer. The tutorial makes the split visible on a single-peak problem: EI proposes x ≈ 0.13, essentially resampling the peak it already found, while KG proposes x ≈ 0.38.

The mechanism to hold on to is that KG rewards decision-relevant information specifically. A candidate is worth something exactly insofar as some plausible value there would change which point you would name at the end — not because it reduces uncertainty in the abstract.

Faded derivation: when the knowledge gradient IS expected improvement

1Restrict the final recommendation to points you have already sampled. What does max_x′ μ_n(x′) become?

max_x′ μ_n(x′) → max_{i ≤ n} μ_n(x_i)

The domain of the inner maximization collapses from the whole space to the n sampled locations.

2Now assume observations are noiseless. What is μ_n(x_i) at a sampled point?

μ_n(x_i) = y_i ⇒ max_{i ≤ n} μ_n(x_i) = f^*_n

A noiseless GP interpolates: the posterior mean passes exactly through every observation. So the best posterior mean over sampled points is precisely the best observed value.

3Substitute both into the KG definition. What is left?

𝔼_n[ max( f^*_n, y_n+1 ) ] − f^*_n = 𝔼_n[ max( y_n+1 − f^*_n, 0 ) ]

After the new sample the candidate set is the old points plus x, so the new best is whichever of f^*_n and y_n+1 is larger. Pulling the constant inside the expectation gives the familiar hinge.

4Name the result.

𝔼_n[ max( y_n+1 − f^*_n, 0 ) ] = EI_n(x)

Expected improvement is the knowledge gradient under two hidden assumptions: no noise, and a final answer restricted to points you actually sampled. Drop either assumption and the two criteria genuinely differ — which is why KG earns its cost precisely in the noisy and correlated settings where EI is weakest.

This is the cleanest way to remember the relationship: EI is not a different idea from KG, it is KG with the recommendation restricted to a finite set and the noise set to zero.

← Numerics and batches: LogEI and qEI Paying for the knowledge gradient →