The optimizer's curse

The model

We have a population of options indexed by \(i\). Option \(i\) has an unknown true value \(G_i\) (the goal) and we observe only a noisy proxy

The proxy is unbiased as a measurement: averaged over the noise, it equals the truth. We optimise by selecting the option with the largest proxy, \(i^* = \operatorname{argmax}_i P_i\).

Derivation by precision-weighting (completing the square)

Because \(\varepsilon = P - G\), the conditional density of \(G\) given \(P = p\) is proportional to the product of the prior on \(G\) and the likelihood of the observation:

The exponent is quadratic in \(g\), so the posterior is Gaussian. Completing the square (equivalently: combining two Gaussian "beliefs" by adding their precisions \(1/\sigma^2\) and taking the precision-weighted mean) gives

where the shrinkage factor is the proxy's reliability, the fraction of its variance that is signal:

Bias of the proxy at a given score

Define the over-statement \(b(p)\) as proxy minus expected truth at proxy value \(p\):

Equivalently, the expected noise of an option conditioned on its score is positive for above-average scores: \(\mathbb{E}[\varepsilon \mid P = p] = b(p) > 0\) for \(p > \mu_G\). Selecting a high proxy preferentially selects options that "got lucky".

Extreme-value scaling

Let \(P_1,\ldots,P_N\) be i.i.d. \(\mathcal{N}(\mu_P, \sigma_P^2)\) with \(\sigma_P^2 = \sigma_G^2 + \sigma_\varepsilon^2\), and \(M_N = \max_i P_i\). The normal distribution lies in the Gumbel domain of attraction, with centering constant (Embrechts, Klüppelberg & Mikosch, 1997)

Then \((M_N - b_N)/a_N\) converges in distribution to a standard Gumbel, whose mean is the Euler–Mascheroni constant \(\gamma \approx 0.5772\). Hence the expected maximum is

(leading order). (The leading term is \(\sqrt{2 \ln N}\); \(b_N\) is the precise centering constant and the \(\gamma \cdot a_N\) term is the same order as the correction, so we keep both rather than mixing them.)

The winner's shortfall

The selected option's expected over-statement is, to leading order, \(b\) evaluated at the winning score:

So the gap between what the winner scored and what it is actually worth grows like \(\sqrt{\ln N}\) in the number of options searched: slowly, but without bound. More search, more capability, more compute → a winner further into the tail → a larger illusory inflation.

The optimizer's curse, in general

Suppose options \(1,\ldots,N\) have fixed true values \(V_i\) and we hold unbiased estimates \(\hat{V}_i\) (so \(\mathbb{E}[\hat{V}_i] = V_i\)). Select \(i^* = \operatorname{argmax}_i \hat{V}_i\). Because the maximum is a convex function, Jensen's inequality gives

Taking expectations, \(\mathbb{E}[\hat{V}_{i^*} - V_{i^*}] \ge 0\): the estimate of the selected option is biased high, regardless of the distribution of the estimation errors. Normality only fixes the size of the gap (§②–④); its sign is forced by selection alone.

The dictionary

• Options ↔ the policies / behaviours a model can reach.
• Proxy \(P\) ↔ the reward or training metric we actually optimise.
• True value \(G\) ↔ the intended objective we cannot write down.
• argmax over N ↔ training: searching the policy space for high-reward behaviour. A more capable optimiser explores a larger effective \(N\).

Read in these terms, the result gives a quantitative basis for Session 3.1's empirical claims. The winner's-shortfall formula says the gap between measured reward and true quality grows with optimisation power, the mechanism behind Pan, Bhatia & Steinhardt's (2022) finding that more capable agents game misspecified rewards more. And it sharpens Skalse et al.'s (2022) impossibility result: a non-trivial proxy can be optimised in a value-lowering direction, and the expected over-statement of the best-by-proxy option is strictly positive and increasing in search. "Just write a better reward" reduces \((1-\beta)\); it cannot reach the \(\beta = 1\) that would be needed to make the curse vanish.