Goodhart’s law famously says: “When a measure becomes a target, it ceases to be a good measure.” Although originally from economics, it’s something we have to grapple with at OpenAI when figuring out how to optimize objectives that are difficult or costly to measure. It’s often necessary to introduce some **proxy objective** that’s easier or cheaper to measure, but when we do this, we need to be careful not to optimize it too much.

For example, as part of our work to align models like GPT-3 with human intent and values, we would like to optimize things like “How helpful is this response?”, or “How factually accurate is this claim?”. These are complex objectives that require humans to carefully check things over. For this reason, we train a model to predict these human preferences, known as a **reward model**, and use the reward model’s predictions as a proxy objective. But it’s important to keep track of how well the true objective is being optimized.

In this post we’ll look at some of the mathematics behind how we do this. We’ll focus on a setting that is particularly clean to analyze, in which we have access to the true objective. In practice, even human preferences can fail to measure what we really care about, but we’re setting that issue aside in this post.

## Best-of-n sampling

There are many ways in which one could optimize the proxy objective, but perhaps the simplest is **best-of-$n$ sampling**, also known as **rejection sampling** or **reranking**. We simply sample n times and take the one that scores the highest according to the proxy objective.

Although this method is very simple, it can actually be competitive with more advanced techniques such as reinforcement learning, albeit at the cost of more inference-time compute. For example, in WebGPT, our best-of-64 model outperformed our reinforcement learning model, perhaps in part because the best-of-64 model got to browse many more websites. Even applying best-of-4 provided a significant boost to human preferences.

In addition, best-of-$n$ sampling has reliable performance and is straightforward to analyze mathematically, making it well-suited to empirical studies of Goodhart’s law and related phenomena.

## The mathematics of best-of-n sampling

Let’s study best-of-$n$ sampling more formally. Suppose we have some sample space $S$ (such as the set of possible question-answer pairs), some probability distribution $P$ over $S$, a true objective (or “reward”) $R_{\text{true}}:S\to\mathbb R$, and a proxy objective $R_{\text{proxy}}:S\to\mathbb R$. Let’s say that we somehow optimize $R_{\text{proxy}}$ and thereby obtain some new distribution $P^\prime$. Then:

- The expectation $\mathbb E_{x^\prime\sim P^\prime}\left[R_{\text{true}}\left(x^\prime\right)\right]$ measures how well we have optimized the true objective.
- The KL divergence $D_{\text{KL}}\left(P^\prime\parallel P\right)$ measures how much optimization we have done. For example, if $P^\prime$ is obtained by taking the first sample from $P$ that lies in some subset $S^\prime\subseteq S$, then this KL divergence is just the negative log probability that a sample from $P$ lies in $S^\prime$.

It turns out that in the case of best-of- $n$ sampling, both of these quantities can be estimated efficiently using samples from $P$.

Let’s look at the expectation first. The naive approach is to use a Monte Carlo estimator: run best-of- $n$ sampling many times, measure the true objective on those samples, and average the results. However, there is a better estimator. If we have $N\geq n$ samples from $P$ overall, then we can simultaneously consider *every possible subset* of these samples of size $n$$\binom{k-1}{n-1}$, where $k$ is the rank of the sample under the proxy objective, from $1$ (worst) up to $N$ (best).^{A}

The sum of these weights is $\binom{N}{n}$, giving a proof of the Hockey-stick identity. For a formal derivation of the estimator described here, see Appendix I of the WebGPT paper.

The sum of these weights is $\binom{N}{n}$, giving a proof of the Hockey-stick identity. For a formal derivation of the estimator described here, see Appendix I of the WebGPT paper.

As well as using samples more efficiently, this also allows us to reuse samples for different values of $n$$P$ (i.e., as long as $P$ has no point masses). One might naively guess that the answer is $\log n$, since best-of-$n$ is doing something like taking the top $\frac 1n$ of the distribution, and this is roughly correct: the exact answer is $\log n-\frac{n-1}n$. ^{B}

Hint: express the PDF of the best-of-$n$ distribution as a function of both the PDF and the CDF of the original distribution.

Together, these estimators allow us to easily analyze how the true objective varies with the amount of optimization applied to the proxy objective.

Here’s a real-life example from WebGPT:

# Best-of-$n$ performance for WebGPT 175B

## Going beyond best-of-n sampling

The main limitation of best-of-$n$ sampling is that the KL divergence grows logarithmically with $n$, so it is only suitable for applying a small amount of optimization.

To apply more optimization, we typically use reinforcement learning. In the settings we’ve studied so far, such as summarization, we’ve typically been able to reach a KL of around 10 nats using reinforcement learning before the true objective starts to decrease due to Goodhart’s law. We’d have to take n to be around 60,000 to reach this KL using best-of-$n$, and we hope to be able to reach much larger KLs than this with improvements to our reward modeling and reinforcement learning practices.

However, not all nats are equal. Empirically, for small KL budgets, best-of-$n$$n$ is the “brute force” approach, making it more information-theoretically efficient than reinforcement learning, but less computationally efficient at large KLs.^{C}

Best-of-$n$ is not necessarily optimal in the information-theoretic sense, however. For example, if $P$ has a heavy right tail, then for any $x>0$ and any $\varepsilon>0$, there is a distribution $Q$ such that $\mathbb E_{y\sim Q}\left[y\right]>x$ and $D_{\text{KL}}\left(Q\parallel P\right)<\varepsilon$ (exercise).