Holdout Best-of-N: Unbiased Evaluation and Its Cost

Reusing the scores that select a Best-of-N winner can overstate its expected reward. We study evaluation from a fixed matrix of K independent scores per candidate for a policy that selects using J fresh scores. A single estimator based only on this matrix is exactly unbiased for expected judge reward under every independent, stable collection of candidate-specific score laws if and only if J<K, for every pool size M≥ N≥2. At J=K-1, the selector deepens as K grows. For independent Gaussian scores with common variance and fixed M≥ N≥2, the unbiased minimax risk in this regime is of order σ2/√ K, attained by Holdout; allowing bias improves the rate to σ2/K. For two candidates, we derive the minimum-variance unbiased estimator at known variance and the sharp asymptotic unbiased minimax constant 1/(π√2), which Holdout attains without knowing the variance. The cyclic average over subsets and ties can be computed in O(MKlog M) operations. At fixed selector depth, cyclic evaluation of bounded scores has O(K-1) risk uniformly in pool size. The impossibility result concerns the fixed matrix: one additional fresh winner score permits unbiased evaluation of the all-K policy.