임상시험 후보, A/B 테스트, 시뮬레이션 설계처럼 여러 선택지 중 평균 보상이 가장 큰 하나를 골라야 할 때 표본 수가 미리 정해져 있다면 어떻게 배분해야 할까. 예일대 모티 골드버거의 프리프린트는 고정 예산 최적 팔 식별 문제에서 모든 문제 사례에 통하는 단일 최적 알고리즘이 존재하는지를 다뤘다. 결론은 선택지가 세 개 이상이면 불가능하다는 것이다.
비교 기준은 각 선택지의 평균을 미리 아는 정적 오라클이다. 오라클은 고정 표본 비율을 골라 오답 확률의 지수적 감소율을 최대화한다. 실제 적응형 알고리즘은 평균을 모르지만 관측 결과에 따라 다음 표본을 정한다. 연구는 어떤 단일 알고리즘이 모든 평균 벡터에서 오라클 감소율을 달성할 수 있을 때 이 문제가 하나의 보편적 ‘복잡도’를 갖는다고 정의했다.
핵심 정리는 팔 수 K가 3 이상이고 보상이 정규 1모수 자연지수족에서 나오면, 어떤 일관된 알고리즘에도 오라클보다 어려운 사례가 적어도 하나 존재한다고 밝힌다. 그 사례에서 알고리즘의 오류 감소율은 정적 오라클의 최대 (1+log(K)/8)의 역수 배에 그친다. K가 커질수록 보장 가능한 비율이 더 낮아져, 오라클 표본 비율로 수렴한다는 사실만으로 같은 오류 지수를 얻을 수 없음을 정량화한다.
증명은 먼저 분산 1인 가우시안 보상에서 기준 사례와 여러 대안 사례를 구성한다. 한 대안은 상위 두 팔의 관계를 바꾸고, 다른 대안들은 나머지 각 팔이 최적이 되도록 만든다. 정보변경 하한과 정적 오라클의 난이도를 결합해 어떤 표본 배분도 모든 대안을 동시에 잘 구분할 수 없음을 보인 뒤, 하한을 1+log(K)/8보다 큰 형태로 정리한다.
다음 단계에서는 평균 주변에서 쿨백·라이블러 발산이 이차식으로 근사된다는 성질을 사용한다. 가우시안 증명의 문제 사례를 충분히 작은 이웃으로 축소하면 같은 정보 기하를 유지할 수 있어, 결과가 베르누이·포아송 등을 포함하는 정규 1모수 자연지수족으로 확장된다. 이는 K=2 가우시안에서는 복잡도가 존재하지만 K=2 베르누이와 K≥3 자연지수족에서는 존재하지 않는다는 기존·신규 경계를 한 표로 정리한다.
| 범위 | 복잡도 존재 여부 | 원문 근거 |
|---|---|---|
| K=2, Gaussian | 예 | Table 1, PDF p.4 |
| K=2, Bernoulli | 아니오 | Table 1, PDF p.4 |
| K≥e^(80/3), Gaussian variance 1 | 아니오 | Table 1, PDF p.4 |
| K≥3, regular one-parameter NEF | 아니오; 이 논문의 결과 | Theorem 3 and Table 1, PDF pp.4, 9 |
| 오류 감소율 상한 사례 | 정적 오라클의 최대 (1+log(K)/8)^−1배 | Abstract; Sec. 1.4, PDF pp.1, 3 |
자료: STORIUM 정리
이 논문은 새 알고리즘이나 실험 벤치마크를 제시하지 않는 순수 이론 연구다. 보상은 알려진 정규 1모수 자연지수족이고 평균 모수 공간은 열린 구간이며 최적 팔이 유일하다는 조건을 둔다. 유한 예산의 실제 오차, 비정상·상관 보상, 다모수 분포나 복수 최적 팔에는 정리가 그대로 적용되지 않는다. 또한 동료검토 전 arXiv v1이므로 증명의 독립 검토가 필요하다.
1차 출처: https://arxiv.org/abs/2607.11635
저작권자 © STORIUM 무단전재 및 재배포 금지
