Fundamental Limitations of Fixed-Budget Best-Arm Identification

기술 요약: 고정 예산 최적 팔 식별(Fixed-Budget Best-Arm Identification)의 근본적 한계

문제 정식화
본 논문은 고정 예산 최적 팔 식별(Best-Arm Identification, BAI), 즉 순위 및 선택(Ranking and Selection) 문제를 다룬다. 이 설정에서 의사 결정자는 미지의 평균 $\mu_k$를 갖는 분포로부터 독립적인 보상을 생성하는 $K$개의 팔(arm)로부터 순차적으로 샘플을 추출한다. 목표는 총 샘플링 예산 $T$를 사용하여 가장 큰 평균 $\mu_i(\mu)$를 갖는 팔 $i^*$를 식별하는 것이다. 성능 지표는 오답 식별 확률 $p_{\mu, T}$, 구체적으로 $T \to \infty$일 때의 지수적 감소율이다:
$$\liminf_{T \to \infty} \frac{1}{T} \log \frac{1}{p_{\mu, T}}$$

핵심적인 이론적 질문은 이 문제에 "복잡도(complexity)"가 존재하는가 하는 점이다. 복잡도는 다음 두 가지 조건을 만족하는 함수 $\Gamma^*(\mu)$로 정의된다:

1. 보편적 상한(Universal Upper Bound): 모든 알고리즘과 모든 인스턴스 $\mu$에 대해, 오차 감소율은 $\Gamma^*(\mu)$에 의해 상한이 결정된다.
2. 균등 달성 가능성(Uniform Achievability): 모든 문제 인스턴스 $\mu$에 대해 균등하게 이 감소율 $\Gamma^*(\mu)$를 달성하는 단일 알고리즘이 존재한다.

본 논문은 정적 오라클(static oracle) 비율 $\Gamma^*_{so}(\mu)$가 이러한 복잡도 역할을 할 수 있는지 조사한다. 정적 오라클은 미래의 실제 평균 $\mu$를 미리 알고, 최대 감소율을 얻기 위해 고정된 비율로 샘플을 할당하는 비적응적(non-adaptive) 전략에 의해 달성 가능한 최적의 오차 감소율을 나타낸다. 적응형 알고리즘들이 이러한 최적의 정적 비율로 샘플링 비율이 수렴하도록 설계되어 왔으나, 어떤 적응형 알고리즘이 모든 인스턴스에 대해 균등하게 정적 오라클의 오차 감소율을 일치시킬 수 있는지는 미해결 과제로 남아 있었다.

방법론
저자들은 $K \geq 3$일 때 단일 알고리즘이 모든 인스턴스에 대해 정적 오라클 비율을 균등하게 달성할 수 없음을 증명하기 위해 귀류법을 사용한다. 방법론은 다음 구성 요소들에 의존한다:

1. 난이도 비율(Difficulty Ratios): Degenne (2023)를 따라, 본 논문은 벤치마크 난이도 함수 $H(\mu)$에 대한 알고리즘 $A$의 성능을 측정하는 난이도 비율 $R_{H, \infty}(A, \mu)$를 활용한다. 만약 복잡도가 존재한다면, 이 비율의 모든 인스턴스에 대한 상한(supremum)이 $\leq 1$인 알고리즘이 존재해야 한다.
2. 정리 1 (Degenne 2023): 증명은 모든 일관된(consistent) 적응형 알고리즘 패밀리의 성능을 제한하는 Degenne (2023)의 핵심 부등식을 활용한다. 임의의 벤치마크 $H$와 대안 인스턴스 집합 $D(\mu)$에 대하여, 역 난이도 비율은 샘플링 비율 $\omega$에 대한 정적 최적화 문제에 의해 상한이 결정된다:
   $$\left( \sup_{\lambda \in D(\mu)} R_{H, \infty}(A, \lambda) \right)^{-1} \leq \sup_{\omega \in \Delta_K} \inf_{\lambda \in D(\mu)} \left( H(\lambda) \sum_{k=1}^K \omega_k \text{KL}(\mu_k, \lambda_k) \right)$$
3. 인스턴스 구축: 복잡도의 비존재를 증명하기 위해, 저자들은 특정 "베이스라인" 인스턴스 $x$와 대안 인스턴스 패밀리 $D(x) = \{\lambda_A, \lambda_{B,3}, \dots, \lambda_{B,K}\}$를 구축한다.
   • $\lambda_A$: $x$와 팔 1과 2에서만 차이가 난다. $x$와 $\lambda_A$를 구별하기 위해서는 팔 1과 2에 대한 상당한 샘플링이 필요하다.
   • $\lambda_{B,j}$ (for $j \in \{3, \dots, K\}$): $x$와 팔 $j$에서만 차이가 나며, 이로 인해 팔 $j$가 새로운 최적의 팔이 된다. $x$와 $\lambda_{B,j}$를 구별하기 위해서는 팔 $j$에 대한 상당한 샘플링이 필요하다.
     이 구축 방식은 "구별하기 가장 어려운" 팔들이 패밀리 전반에 걸쳐 다양하게 나타나도록 보장한다. 단일 샘플링 할당 $\omega$는 서로 분리된 팔 세트에 정보가 집중되어 있기 때문에, $x$를 $D(x)$의 모든 멤버와 구별하는 데 동시에 최적일 수 없다.

주요 결과
본 논문은 고정 예산 BAI에 대한 근본적인 부정적 결과를 확립한다:

• 가우시안 보상(Gaussian Rewards): 가우시안 보상(분산 1)을 갖는 $K \geq 3$개의 팔에 대해, 저자들은 모든 일관된 알고리즘 패밀리 $A$에 대하여 정적 오라클에 대한 난이도 비율이 1을 초과하는 인스턴스 $\mu$가 존재함을 증명한다. 구체적으로:
  $$\inf_{A \in \mathcal{C}_{cons}} \sup_{\mu} R_{H_{so}, \infty}(A, \mu) \geq 1 + \sum_{j=3}^K \frac{1}{(1 + \sqrt{j-1})^2} > 1 + \frac{1}{8} \log(K)$$
  이 하한은 모든 $K \geq 3$에 대해 1보다 엄격히 크며, 따라서 어떤 알고리즘도 정적 오라클을 균등하게 일치시킬 수 없음을 증명한다.

• 자연 지수 가족(Natural Exponential Families, NEF)으로의 일반화: 이 결과는 임의의 일변량 자연 지수 가족(NEF)으로 확장된다. 쿨백-라이블러(KL) 발산의 국소 이차 근사(local quadratic approximation)를 사용하여, 저자들은 가우시안 결과가 모든 정규 일변량 NEF에 대해서도 동일한 제한을 가짐을 보여준다.

• 열린 질문에 대한 답변: 이 연구는 Qin (2022)이 제기하고 Degenne (2023)이 정식화한 열린 질문에 확정적인 답을 제시한다: 고정 예산 BAI는 $K \geq 3$일 때 복잡도를 갖지 않는다. 즉, 정적 오라클이 오차 감소율에 대한 하한을 제공하지만, 단일 적응형 알고리즘이 모든 문제 인스턴스에 대해 이 상한을 균등하게 달성할 수는 없다.

의의 및 주장
본 논문은 고정 예산 BAI의 이해에 있어 근본적인 이론적 간극을 해결한다고 주장한다.

• 적응성의 한계: 샘플링 비율이 정적 오라클로 수렴하는 것(적응형 알고리즘의 일반적인 설계 목표)이 정적 오라클의 오차 감소율을 일치시키는 것을 보장하기에는 불충분함을 보여준다. 고정 예산 설정에서 "적응성의 대가(price of adaptivity)"는 알고리즘이 모든 인스턴스에 대해 동시에 최적일 수 없다는 점이다.
• 범위: 이 결과는 가우시안 보상의 경우 $3 \leq K < e^{80/3}$ 범위의 문헌적 공백을 채우며, 복잡성의 비존재성을 모든 일변량 NEF로 확장한다.
• 이론적 경계: 이 연구는 정적 오라클이 $K \geq 3$인 고정 예산 BAI의 보편적 복잡도가 아님을 확립한다. 저자들은 정적 오라클을 균등하게 달성할 수 없으므로, 대안적인 이론적 목표나 벤치마크가 필요함을 시사한다.

본 논문은 이러한 한계를 극복하기 위한 새로운 알고리즘을 제안하거나, 순위 및 선택(Ranking-and-Selection) 또는 멀티 암드 밴딧(Multi-Armed Bandits) 이외의 구체적인 응용 분야를 제안하지 않는다. 기여는 순수하게 이 설정에서 무엇이 달성 가능한지에 대한 근본적인 한계를 규정하는 부정적 결과(negative result)에 집중되어 있다.