홀드아웃 베스트-오브-N: 편향되지 않은 평가와 그 비용

Best-of-$N$ 승자를 선택하는 데 사용된 점수를 재사용하는 것은 예상 보상을 과대평가할 수 있습니다. 우리는 $J$개의 새로운 점수를 사용하여 선택하는 정책에 대해, $K$개의 독립적인 후보별 고정 행렬로부터의 평가를 연구합니다. 이 행렬에만 기반한 단일 추정량은 모든 독립적이고 안정적인 후보별 점수 법칙 하에서 예상 심사위원 보상에 정확히 편향되지 않습니다 (unbiased) (expected judge reward) $ ext{if and only if } J<K$, 모든 풀 크기 $M ext{에 대해 } M ext{을 만족하는 } N ext{에 대해서도 성립합니다. } J=K-1 ext{일 때, 선택기는 } K ext{가 증가함에 따라 깊어집니다. 공통 분산과 고정된 } M ext{의 } M ext{을 만족하는 독립적인 가우시안 점수(Gaussian scores)의 경우, 이 체제에서의 편향되지 않은 minimax 위험은 $O(rac{ ext{σ}^2}{ ext{√}K})$의 순서를 가지며, Holdout이 이를 달성합니다. 편향을 허용하면 그 비율이 $rac{ ext{σ}^2}{K}$로 개선됩니다. 두 후보자의 경우, 알려진 분산에서의 최소분산 편향되지 않은 추정량과 날카로운 점근적 편향되지 않은 minimax 상수인 $rac{1}{( ext{π} ext{√}2)}$를 도출했으며, Holdout은 분산을 알지 못해도 이를 달성합니다. 부분집합 및 동점(ties)에 대한 순환 평균은 $O(MK ext{log }M)$ 연산으로 계산될 수 있습니다. 고정된 선택기 깊이에서, 유한 점수(bounded scores)의 순환 평가는 풀 크기에 관계없이 $O(rac{1}{K})$ 위험을 가집니다. 불가능성 결과는 고정 행렬에 관한 것으로, 추가적인 새로운 승자 점수는 모든-$K$ 정책의 편향되지 않은 평가를 허용합니다.