首页 > AI前沿 > Holdout Best-of-N: Unbiased Evaluation and Its Cost

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

arXiv自然语言 2026-10-07 01:26 5 阅读 查看原文

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.

Unbiased Estimator

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

Selector Deepening

At $J=K-1$, the selector deepens as $K$ grows.

Unbiased Minimax Risk

For independent Gaussian scores with common variance and fixed $M\ge N\ge2$, the unbiased minimax risk in this regime is of order $σ^2/\sqrt K$, attained by Holdout; allowing bias improves the rate to $σ^2/K$.

Minimum-Variance Unbiased Estimator

For two candidates, we derive the minimum-variance unbiased estimator at known variance and the sharp asymptotic unbiased minimax constant $1/(π\sqrt2)$, which Holdout attains without knowing the variance.

Cyclic Average Computation

The cyclic average over subsets and ties can be computed in $O(MK\log M)$ operations.

Fixed Selector Depth

At fixed selector depth, cyclic evaluation of bounded scores has $O(K^{-1})$ risk uniformly in pool size.

Impossibility Result

The impossibility result concerns the fixed matrix: one additional fresh winner score permits unbiased evaluation of the all-$K$ policy.