Where Does the Union Bound Go? Best-Arm Identification and Strong FWER Control

기술 요약: "유니온 바운드는 어디로 가는가? 최적 팔 식별(Best-Arm Identification)과 강한 FWER 제어"

문제 정의
고정 신뢰도 최적 팔 식별(fixed-confidence Best-Arm Identification, BAI) 문제에서 알고리즘은 $K$개의 팔 중 평균 $\mu_{i^\star}$가 가장 높은 유일한 팔 $i^\star$를 식별하는 것을 목표로 하며, 이때 오류 확률이 최대 $\delta$ 이하가 되도록 보장해야 한다. 문헌에 나타나는 반복적인 의문은 유니온 바운드(union bound)를 통해 도출된 오차 한계(error bounds)에 $K-1$과 관련된 인자(종종 정지 임계값에서 $\log(K-1)$로 등장함)가 존재하는 현상이다.

다중 검정(multiple-testing)의 관점에서 볼 때, 이는 모순적으로 보인다. 만약 파라미터 공간이 정확히 하나의 팔이 최적이라는 조건으로 제한되어 있다면, "팔 $i$가 최적이다"라는 가설들 중 오직 하나만이 참이다. 표준 다중 검정 이론(예: 본페로니 교정)에 따르면, 단 하나의 귀무가설만이 참이라면 오차율을 위해 $K-1$개의 대립 가설에 대한 합산 인자를 요구하지 않아야 한다. 그러나 표준적인 BAI 증명들은 일관되게 $K-1$개의 경쟁하는 사건들에 대해 오차 예산을 할당한다. 본 논문은 이 명백한 모순의 근원을 조사한다.

방법론 및 이론적 프레임워크
본 논문은 유일 최적 팔 파라미터 공간 $\Theta_{\text{uniq}}$ 내에서 귀무가설의 방향성(orientation)을 선택하는 두 가지 구별된 방식에 의해 이 의문이 해결됨을 입증함으로써 문제를 해결한다. 저자는 다음과 같이 두 가지 서로 다른 가설 방향성을 분석한다:

1. 방향성 1: "팔 $i$는 최적이 아니다"

   • 가설: $H_i^- := \{ \mu \in \Theta_{\text{uniq}} : i \neq i^\star(\mu) \}$로 정의한다. 귀무가설 $H_i^-$는 팔 $i$가 최적이 아님을 주장한다.
   • 논리: 실제 최적의 팔이 $i^\star$라면, $H_{i^\star}^-$는 거짓이지만, $i \neq i^\star$인 모든 $i$에 대해 $H_i^-$는 참이다.
   • 다중성: 이 공식화에서는 정확히 $K-1$개의 참인 귀무가설이 동시에 존재한다. 따라서 FWER(Familywise Error Rate)을 제어하기 위해서는 이 $K-1$개의 참인 귀무가설들에 대한 표준적인 유니온 바운드가 논리적으로 필요하다. BAI 오류 사건 $\{ \hat{b}_\tau \neq i^\star \}$는 이 가설 집합에서 적어도 하나의 참인 귀무가설을 기각하는 사건과 정확히 일치한다.

2. 방향성 2: "팔 $i$가 최적이다"

   • 가설: $G_i := \{ \mu \in \Theta_{\text{uniq}} : i = i^\star(\mu) \}$로 정의한다. 이들은 파라미터 공간을 분할하며, 정확히 하나의 $G_i$만이 참이다.
   • 논리: 여기서는 단 하나의 참인 귀무가설만이 존재한다. 제거 알고리즘은 팔 $i$가 최적이 아니라는 충분한 증거가 제시될 때 $G_i$를 기각한다.
   • 다중성: 비록 하나의 참인 복합 귀무가설(composite null hypothesis)만 존재하지만, $G_i$에 대한 검정의 구성 자체가 다중성을 도입한다. "팔 $i$가 최적이다"라는 진술은 $K-1$개의 쌍별(pairwise) 진술들의 교집합이다: $G_i = \bigcap_{j \neq i} \{ \mu_i > \mu_j \}$.
   • 메커니즘: 쌍별 제거 규칙은 만약 어떤 경쟁자 $j$가 $i$에 대해 충분한 반증을 제공하면 $G_i$를 기각한다. 즉, 단일 참 복합 귀무가설 $G_{i^\star}$에 대한 기각 사건은 $K-1$개 쌍별 기각 사건들의 합집합이다: $\{ G_{i^\star} \text{가 기각됨} \} = \bigcup_{j \neq i^\star} R_{j, i^\star}$.
   • 결과: 유니온 바운드(그리고 그에 따른 $K-1$ 인자)는 사라지지 않는다. 대신 그것은 단일 참 복합 가설의 검정 "내부"로 이동한다. 오차 확률은 $K-1$개 쌍별 비교의 확률 합에 의해 상한이 정해진다.

주요 기여

• 명시적 동등성: 본 논문은 BAI와 다중 검정 커뮤니티의 용어를 사용하여 BAI의 표준 오차 분석과 강한 FWER 제어 사이의 동등성을 명시적으로 밝힌다. 이는 "의문"이 되는 $K-1$ 인자가 가설 방향성을 전환하는 과정에서 발생하는 결과임을 명확히 한다.
• 다중성의 명확화: BAI에서의 다중성이 부실한 증명 기법의 산물이 아니라 문제 구조의 근본적인 속성임을 입증한다. 이를 $K-1$개의 참인 귀무가설으로 보든(방향성 1), 혹은 단 하나의 참인 복합 귀무가설을 반박하는 $K-1$개의 잠재적 방식(방향성 2)으로 보든, 조합론적 인자는 그대로 유지된다.
• 순위(Rank)와 증인(Witness)의 구분: 본 논문은 문제의 "순위"(BAI의 경우 두 개의 팔만 있으면 후보를 부정할 수 있으므로 2임)와 "증인"의 수(이는 $K-1$임) 사이의 구분을 명확히 한다. 순위는 왜 쌍별 통계량이 충분한지를 설명하고, 증인에 대한 유니온은 비점근적 오차 보정에서 $K-1$ 항이 나타나는 이유를 설명한다.

기존 문헌의 결과 및 분석
본 논문은 이러한 이중성이 특정 알고리즘과 경계값에 어떻게 나타나는지 분석한다:

• Garivier와 Kaufmann (2016): 임계값 $\beta(t, \delta) = \log(2t(K-1)/\delta)$는 실제 최적의 팔을 고정한 후 $K-1$개의 잘못된 승자들을 명시적으로 합산한다.
• Kaufmann와 Koolen (2021): 이들의 개선된 시간 균일 혼합 마틴게일(time-uniform mixture-martingale) 경계는 쌍(pair) 내부의 집중도를 정교하게 만들지만, 여전히 $\{1, j\}$ 부분 집합들에 대해 가중 유니온 바운드를 적용한다. 다중성은 보정 함수 내의 $\log((K-1)/\delta)$ 항을 통해 등장하며, 이 경우 시간 의존성은 이전 경계들보다 더 정교하다.
• 표본 복잡도(Sample Complexity): 본 논문은 $K-1$ 인자가 비점근적 경계에 나타나더라도, 이것이 고정된 $K$에 대해 $\delta \to 0$일 때 표본 복잡도에 곱연산적인 $K-1$ 손실을 반드시 의미하는 것은 아니라고 언급한다. 주된 차수(leading order term)는 여전히 $\log(1/\delta)$에 의해 지배된다.

의의 및 주장
본 논문은 새로운 알고리즘이나 실험 결과를 제안하기보다는 논리적 동등성을 명확히 하는 "노트(note)"로서 겸손하게 자신을 규정한다. 본 논문의 주요 의의는 다음과 같다:

1. 관점의 통합: BAI 문헌(종종 문제를 유일한 승자를 식별하는 것으로 취급함)과 다중 검정 문헌(FWER 제어 및 논리적 제약에 집중함) 사이의 간극을 메운다.
2. 유니온 바운드의 해명: BAI 증명에서 유니온 바운드가 "낭비"되는 것이 아니라, 문제의 특정 논리적 구조에 적합한 올바른 도구임을 주장한다. 이는 문제를 많은 참인 귀무가설으로 보든, 혹은 하나의 참인 귀무가설과 이를 반박하는 많은 잠재적 반증자로 보든 마찬가지이다.
3. 향후 방향: 본 논문은 (Katz-Samuels 등, 2020의 연구와 같이) 전체 복합 귀무가설의 기하학적 구조를 활용하는 결합 검정(joint tests)을 사용하면 명시적인 팔 단위 유니온 바운드를 피할 수 있을 수도 있지만, 증인(witnesses)의 근본적인 조합론적 성격은 문제 기하학의 핵심 특징으로 남을 것임을 시사한다.

결론적으로, 두 커뮤니티 모두 논리적으로 연관된 후보 답안들에 대해 오차를 정리하고 있으나, 다중성을 배치하는 수준(level)이 서로 다를 뿐이다.