기권(Abstention)을 포함한 베이지안 최적 팔 식별: 다항식에서 지수 함수로의 상전이

우리는 학습자가 최종 권고를 하는 것을 기권(abstain)할 수 있는 베이지안 고정 예산 최적 팔 식별(Bayesian fixed-budget best-arm identification) 문제를 연구합니다. 기권 예산 $α$가 주어졌을 때, 우리는 기권하지 않고 차선책(suboptimal arm)을 권고할 위험인 미감지 오류(undetected error)의 확률을 분석합니다. 우리의 핵심 발견은 기권이 상전이(phase transition)를 유도한다는 것입니다. 즉, 기권이 없으면 오류 확률은 샘플링 예산 $T$에 대해 다항식(polynomially)적으로 감소하지만, 아주 작은 양의 기권 예산이라도 도입하면 이것이 지수적 감소(exponential decay)로 전환됩니다. 가우시안 사전 확률(Gaussian priors) 및 보상(rewards)에 대해, $T o ext{∞}$ 이후 $α ext{↓}0$인 영역에서, 우리는 최적 오류 지수(optimal error exponent)에 대한 정확히 일치하는 정보 이론적 하한(information-theoretic lower bounds)과 알고리즘적 상한(algorithmic upper bounds)을 확립하였으며, 이는 $ ext{exp}(-rac{α^{2}T}{8κ_ν^{2}})$의 형태를 가집니다. 난이도 파라미터(hardness parameter) $κ_ν$는 0에서의 상위 2개 간격(top-two gap)에 대한 사전 밀도(prior density)를 나타내며, 이는 거의 동점인 사례들이 근본적인 오류를 유발함을 강조합니다. 우리는 통계적으로 모호한 사례에 기권 예산을 소비함으로써 이 최적 지수를 성공적으로 달성하는 적응형 알고리즘인 PGWS를 소개합니다. 나아가 우리는 이러한 다항식에서 지수 함수로의 개선이 오직 베이지안(Bayesian) 현상임을 입증합니다. 빈도주의(frequentist) 설정에서 기권은 오직 저차수 지수 항(lower-order exponent terms)에만 영향을 미칩니다. 또한 우리는 가우시안 모델을 넘어 연구 결과를 확장합니다.