Kwangmin Kim - Best Arm Identification

출처

이 글은 교재 직접 참조 없이 agent 사전학습 기반으로 작성되었다 (교재 미확인 — agent 사전학습 기반). 핵심 정리는 Audibert, Bubeck, Munos (2010), Mannor & Tsitsiklis (2004) 등 검증 가능한 원논문에 한해 명시한다.

이 글은 Phase I 시리즈의 마지막 글이다. 지금까지의 cumulative regret 알고리즘 (UCB, Thompson) 과 근본적으로 다른 문제 — Best Arm Identification (BAI) — 을 다룬다.

1 진입 직관 — “도박이 아니라 평가”

지금까지의 MAB 시나리오: 도박장에서 매 게임마다 보상. 학습 중에도 돈을 잃거나 따고 있다. Cumulative regret 최소화 가 자연스러운 목표.

그러나 다른 시나리오 가 있다.

시나리오 A — 신약 후보 식별: 100 개의 후보 약 중 가장 효과 좋은 1 개 를 식별하여 정식 임상시험에 보내고 싶다. 식별 과정 자체의 결과 는 무관 — 최종 식별의 정확성 만 중요.

시나리오 B — 추천 알고리즘 선정: 5 개의 추천 알고리즘 후보 중 최선의 1 개 만 production 에 배포할 예정. 시험 기간 자체의 사용자 만족도는 낮아도 OK — 시험 후의 정확한 선택 이 핵심.

시나리오 C — 광고 크리에이티브 전수 평가: 50 개의 광고 디자인을 평가하여 베스트 1 개 만 1 년간 사용. 평가 단계의 매출은 부수적.

이 모든 시나리오는 cumulative reward 가 아니라 simple regret 이 적합한 문제다.

결정적 차이의 한 줄 요약:

Cumulative regret: “도박장에서 총 얼마를 잃었나” — 매 시점이 real money

Simple regret: “탐색 끝에 어느 팔을 추천할 것인가” — 시험 단계의 보상 자체 는 무관

이전 글에서 제시한 정의를 이제는 깊이 다룬다.

2 Simple Regret 의 정확한 정의

정의: Simple Regret

학습 종료 시점 \(N\) 에 단일 팔 추천 \(\hat{A}_N\). Simple regret 은:

\[ r_N = \mu^* - \mu_{\hat{A}_N} \]

\(\mu^* = \max_a \mu_a\): 진짜 최선의 평균 보상
\(\mu_{\hat{A}_N}\): 추천한 팔의 진짜 평균

핵심 성질:

\(r_N \geq 0\)
\(r_N = 0\) ↔︎ 진짜 최선의 팔을 정확히 식별
\(\hat{A}_N\) 이 결정론적 또는 확률적 (확률적이면 \(\mathbb{E}[r_N]\) 또는 \(P(r_N > \epsilon)\) 분석)

2.1 Cumulative Regret 과의 분리

학습 중 어떤 팔을 당겨도 simple regret 무관. 마지막 추천만 평가.

결과: cumulative regret 알고리즘 (UCB) 이 simple regret 에 차선. UCB 는 suboptimal 팔에 적게 시도 — 그러면 각 팔의 효과 추정 정밀성 부족 — 추천 결정 어려움.

수식 직관:

UCB 의 시도: 팔 1 이 9000 회, 팔 2 가 800 회, 팔 3 가 200 회 (cumulative 효율)

BAI 의 시도: 팔 1 이 3500 회, 팔 2 가 3500 회, 팔 3 가 3000 회 (균등에 가까움)

Simple regret 입장에서는 모든 팔에 충분한 sample 이 필요. UCB 의 비대칭 sample 은 각 팔의 비교 에 부적합.

3 Two Formulations — Fixed Budget vs Fixed Confidence

BAI 는 서로 다른 두 가지 자원 제약 으로 정식화된다.

3.1 Fixed Budget

총 시도 횟수 N 이 사전 고정. 최대한 정확한 추천 추구.

3.1.1 목표

\[ \min_{\hat{A}_N} P(\hat{A}_N \neq a^*) \quad \text{또는} \quad \min_{\hat{A}_N} \mathbb{E}[r_N] \]

사전 고정 N 안에 오류 확률 (또는 simple regret) 최소화.

3.1.2 응용

예산이 한정된 광고 캠페인: “총 1 만 노출 안에 베스트 광고 식별”. 임상시험 budget: 환자 수 사전 결정.

3.2 Fixed Confidence

목표 신뢰도 \(1 - \delta\) 사전 고정. 최소 sample 로 그 신뢰도 달성.

3.2.1 목표

\[ \min_{N} \quad \text{s.t.} \quad P(\hat{A}_N = a^*) \geq 1 - \delta \]

즉 적게 시도해도 OK 면 일찍 끝내고, 더 많이 시도해야 하면 계속.

3.2.2 응용

목표: 95% 확률로 정확한 추천. 데이터가 충분하면 일찍 종료, 부족하면 더 모집. Sequential testing 과 친척.

3.3 수식 비교

형식	입력	출력
Fixed Budget	N (sample 수)	\(\hat{A}_N\), \(P(\text{error})\)
Fixed Confidence	\(\delta\) (오류 확률 상한)	\(\hat{A}\), random \(\tau\) (필요 sample 수)

반사실: 두 형식은 서로 변환 가능 — fixed budget 의 inverse 가 fixed confidence. 그러나 알고리즘 구조 다름. Fixed confidence 는 adaptive stopping 필요.

4 Sample Complexity Lower Bound — Mannor & Tsitsiklis (2004)

4.1 정리

Fixed Confidence 형식에서 어떤 알고리즘이든:

\[ \mathbb{E}[\tau] \geq c \cdot \sum_{a \neq a^*} \frac{1}{\Delta_a^2} \log \frac{1}{\delta} \]

\(\Delta_a = \mu^* - \mu_a\) 는 gap, \(c > 0\) 는 상수.

4.2 함의

어떤 알고리즘도 log(1/δ) 비례 sample 미만으로 δ-confident 추천 불가능. gap 작은 팔이 있을수록 더 많은 sample 필요.

4.3 직관

Hoeffding 부등식 에 의해 gap \(\Delta\) 인 두 팔 구분 위해 \(1/\Delta^2\) sample 필요. log(1/δ) 는 높은 신뢰 의 비용.

Cumulative regret 의 \(O(\log N / \Delta)\) 와의 차이:

Cumulative: \(1/\Delta\) — 의미는 “팔 1 회 추가 시도의 marginal cost”

Simple: \(1/\Delta^2\) — “신뢰성 있는 식별의 cost”

Simple regret 이 더 어려운 문제. Cumulative 의 log 와 simple 의 log (1/gap²)* 의 차이.

5 UCB-E (Audibert, Bubeck, Munos 2010) — Fixed Budget Algorithm

5.1 동기

Fixed budget 에서 UCB1 의 변형. UCB1 의 탐색 항 을 더 공격적으로.

5.2 알고리즘

알고리즘: UCB-E

입력: 총 budget N, exploration parameter c

For t = 1 to N:
  for each a:
    UCB-E_a = mean_a + sqrt(c / pulls_a)

  A_t = argmax_a UCB-E_a
  Observe r_t, update

추천: argmax_a mean_a   # 시도 횟수 가장 많은 팔이 아니라 평균 최대 팔

매개변수 c: budget 과 gap 에 의존. 보통 \(c = N \cdot c_0\) 형태.

5.3 메커니즘

UCB1 의 \(\sqrt{2 \ln t / n_a}\) 대신 \(\sqrt{c / n_a}\) — 시간에 무관. 모든 팔에 균등하게 시도하는 경향.

덜 시도된 팔 의 UCB 가 큼 → 균등 분배 자연스러움.

5.4 Regret

적절한 c 선택 시:

\[ P(\hat{A}_N \neq a^*) \leq \exp\left(-\Theta\left(\frac{N}{H_1}\right)\right) \]

여기서 \(H_1 = \sum_a 1/\Delta_a^2\) 는 문제의 hardness.

5.5 한계

매개변수 c 가 gap (사전 모름) 에 의존. 실무에서 튜닝 필요.

6 Successive Rejects — Audibert, Bubeck, Munos (2010)

UCB-E 의 매개변수 의존성을 제거 하는 알고리즘.

6.1 메커니즘

총 N 시도를 K-1 phase 로 나눔. 매 phase 끝에 현재까지 가장 나쁜 팔 제거.

알고리즘: Successive Rejects

입력: 총 budget N, K 팔
계산: log K = sum_{i=1}^{K-1} 1/i (조정 상수)
n_k = ceil((N - K) / (log K * (K + 1 - k))) for k = 1, ..., K-1

활성 집합: A = {1, ..., K}

For phase k = 1 to K-1:
  각 팔 a in A 에 대해:
    팔 a 를 (n_k - n_{k-1}) 회 추가 시도

  현재 활성 팔 중 *평균 최저 팔* 제거:
    a_worst = argmin_{a in A} mean_a
    A = A \ {a_worst}

추천: A 의 마지막 남은 팔

6.2 직관

명백히 나쁜 팔 부터 제거. 시간이 갈수록 어려운 비교만 남음 — 더 많은 sample 집중.

6.3 핵심 성질

매개변수 자유 (UCB-E 의 c 같은 튜닝 불필요). budget N 만 입력.

6.4 Regret Bound

\[ P(\hat{A}_N \neq a^*) \leq O\left(\exp\left(-\frac{N}{H_2 \cdot \log K}\right)\right) \]

\(H_2 = \max_a a \cdot \Delta_{(a)}^{-2}\) (여기서 \(\Delta_{(a)}\) 는 정렬된 gap).

UCB-E 와 상수 배 이내 성능. 매개변수 자유 가 큰 매력.

7 Successive Halving — 더 단순한 변형

총 budget N, K 팔. 매 phase 에서 하위 절반 제거. \(\log_2 K\) phase 후 1 개 남음.

7.1 알고리즘

A = {1, ..., K}
remaining_budget = N

For phase i = 1 to log_2(K):
  budget_per_phase = remaining_budget / log_2(K)
  budget_per_arm = budget_per_phase / |A|

  각 팔 a in A 에 대해 budget_per_arm 회 시도

  하위 절반 제거 (평균 기준)
  A = top half of A

추천: A 의 유일한 팔

7.2 직관

Tournament 방식. 각 round 에서 절반 탈락. 결승까지 진행.

7.3 인기

간단·robust + 매개변수 자유. 실무에서 Successive Rejects 보다 더 자주 사용 (특히 hyperparameter tuning, neural architecture search).

응용 — Hyperparameter Tuning: 신경망의 hyperparameter 100 개 후보. 각각에 budget 제한 학습 후 하위 절반 탈락. 최종 1 개 선택. Hyperband (Li 외 2017) 의 핵심 구성 요소.

8 Fixed Confidence Algorithm — LUCB

8.1 동기

Fixed confidence 에서 adaptive stopping.

8.2 메커니즘

각 팔의 confidence interval 유지. 최선 후보의 lower bound > 다른 모든 팔의 upper bound 가 되면 종료.

8.3 알고리즘 (간단화)

For t = 1, 2, ...:
  for each a:
    UCB_a = mean_a + sqrt(c log t / pulls_a)
    LCB_a = mean_a - sqrt(c log t / pulls_a)

  best = argmax_a mean_a
  challenger = argmax_{a ≠ best} UCB_a

  if LCB_best > UCB_challenger:
    추천 ← best, 종료
  else:
    best 와 challenger 1 회씩 추가 시도

8.4 직관

현재 최선 과 가장 위협적 challenger 의 confidence interval 분리 까지 시도. 분리되면 추천 결정.

반사실: easy 문제 (gap 큼) 에서 빠르게 종료. hard 문제 (gap 작음) 에서 오래 시도. 적응적 자원 사용.

9 A/B Test 와의 정확한 관계

9.1 A/B Test = 2-arm BAI (Fixed Budget)

2 개 처치 비교 + 사전 고정 sample size + 최선 1 개 선택. 본질적으로 Best Arm Identification with K=2.

9.2 차이점

A/B Test 는 통계적 가설 검정 강조 — p-value, 효과 크기, 신뢰구간. BAI 는 오류 확률 강조.

그러나 수학적으로 같은 구조.

9.3 Multi-Variant Testing = Multi-arm BAI

3+ variant 비교. 어느 variant 가 최선? 의 정확한 BAI 문제.

Naive 접근: 모든 pair-wise A/B + Bonferroni 보정. 비효율. 올바른 접근: Successive Rejects 또는 LUCB. Multi-armed BAI 문헌 의 도구.

10 시뮬레이션 — UCB vs UCB-E vs Successive Rejects

import numpy as np

np.random.seed(42)

K = 5
true_means = np.array([0.45, 0.50, 0.70, 0.55, 0.60])
mu_star = true_means.max()
N = 1000   # Fixed budget

def cumulative_ucb_then_recommend(true_means, N):
    """UCB1 (cumulative regret 최적) 후 mean 최대 팔 추천."""
    K = len(true_means)
    pulls = np.zeros(K)
    sums = np.zeros(K)
    for a in range(K):
        r = np.random.binomial(1, true_means[a])
        pulls[a] = 1
        sums[a] = r
    for t in range(K, N):
        means = sums / pulls
        ucb = means + np.sqrt(2 * np.log(t + 1) / pulls)
        a = ucb.argmax()
        r = np.random.binomial(1, true_means[a])
        pulls[a] += 1
        sums[a] += r
    final_means = sums / pulls
    return final_means.argmax(), pulls.copy()

def ucb_e(true_means, N, c=None):
    """UCB-E for fixed budget."""
    K = len(true_means)
    if c is None:
        c = N / 4   # heuristic
    pulls = np.zeros(K)
    sums = np.zeros(K)
    for a in range(K):
        r = np.random.binomial(1, true_means[a])
        pulls[a] = 1
        sums[a] = r
    for t in range(K, N):
        means = sums / pulls
        ucb = means + np.sqrt(c / pulls)
        a = ucb.argmax()
        r = np.random.binomial(1, true_means[a])
        pulls[a] += 1
        sums[a] += r
    final_means = sums / pulls
    return final_means.argmax(), pulls.copy()

def successive_rejects(true_means, N):
    """Audibert, Bubeck, Munos (2010)."""
    K = len(true_means)
    log_K_bar = sum(1.0/i for i in range(1, K))   # ≈ 1 + 1/2 + ... + 1/(K-1)
    n_phases = K - 1
    pulls = np.zeros(K)
    sums = np.zeros(K)
    active = list(range(K))

    for k in range(1, n_phases + 1):
        target_pulls = int(np.ceil((N - K) / (log_K_bar * (K + 1 - k))))
        # 활성 팔 추가 시도
        for a in active:
            need = target_pulls - int(pulls[a])
            for _ in range(need):
                r = np.random.binomial(1, true_means[a])
                pulls[a] += 1
                sums[a] += r
        # 활성 중 가장 나쁜 팔 제거
        active_means = [(a, sums[a]/pulls[a]) for a in active]
        worst = min(active_means, key=lambda x: x[1])[0]
        active.remove(worst)

    return active[0], pulls.copy()

# 평가: 진짜 최선의 팔을 추천한 비율
true_best = true_means.argmax()
n_sim = 500
results = {"UCB→mean": [], "UCB-E": [], "Succ-Rej": []}
pulls_records = {"UCB→mean": [], "UCB-E": [], "Succ-Rej": []}

for s in range(n_sim):
    np.random.seed(s)
    a1, p1 = cumulative_ucb_then_recommend(true_means, N)
    np.random.seed(s)
    a2, p2 = ucb_e(true_means, N)
    np.random.seed(s)
    a3, p3 = successive_rejects(true_means, N)
    results["UCB→mean"].append(a1 == true_best)
    results["UCB-E"].append(a2 == true_best)
    results["Succ-Rej"].append(a3 == true_best)
    pulls_records["UCB→mean"].append(p1)
    pulls_records["UCB-E"].append(p2)
    pulls_records["Succ-Rej"].append(p3)

print(f"[Best Arm Identification — N={N}, K={K}, {n_sim} sims]")
print(f"진짜 means: {true_means}, 최선의 팔: {true_best}\n")

print(f"정확 식별 비율 (P(correct)):")
for name in results:
    correct = np.mean(results[name])
    print(f"  {name:<12}: {correct:.3f}")

print(f"\n평균 시도 횟수 (각 팔):")
for name in pulls_records:
    avg_pulls = np.mean(pulls_records[name], axis=0)
    print(f"  {name:<12}: {avg_pulls.round(0)}")

print(f"\n→ UCB→mean: 시도 매우 비대칭 (cumulative regret 최적), simple regret 차선")
print(f"→ UCB-E: 보다 균등 + 추천 정확성 좋음")
print(f"→ Successive Rejects: 매개변수 자유 + 비슷한 성능")

결과 해석 — 깊이:

UCB→mean recommendation: UCB1 으로 학습 후 mean argmax 추천. 시도가 팔 2 (최선) 에 집중 — 팔 4 (gap 작음, 0.55~0.60) 의 sample 부족 — 오인 가능성 큼. 정확 식별 비율 ~85%.

UCB-E: 매개변수 c 적절히 선택 시 정확 식별 비율 ₉₀95%. 그러나 c 의 부적절한 튜닝 시 더 나빠질 수 있음.

Successive Rejects: 매개변수 자유 + 정확 식별 비율 ₉₂95%. Robust 권장.

시도 분포:

UCB: 팔 2 에 ~700 회, 다른 팔에 ₅₀100 회

UCB-E: 모든 팔에 ₁₅₀250 회 (더 균등)

Succ-Rej: 처음에 균등, 점진적으로 활성 팔에 집중 → 마지막에는 활성 팔에 ~250 회

Cumulative regret 알고리즘이 simple regret 에 차선 인 점 명확.

11 Sequential Hypothesis Testing 과의 연결

11.1 Wald’s Sequential Probability Ratio Test (SPRT)

1947 년 Wald 의 순차 가설 검정. 데이터 누적되며 fixed confidence 도달 시 종료. BAI fixed confidence 의 2-arm 특수 case.

11.2 Phase F-4 (Sequential Testing)

본 시리즈에서 다루지 않지만 Phase F (A/B Test 정통) 에서 SPRT, Always-Valid p-value, Group Sequential 등 순차 검정 의 통계적 정통 다룸. BAI 는 그것의 일반화.

12 실무 응용 정리

12.1 1. Hyperparameter Tuning (ML)

모델의 hyperparameter 100 개 후보 → 최선 1 개 선택. Successive Halving / Hyperband 가 표준.

12.2 2. Neural Architecture Search

수백~수천 개 architecture → 최선 1 개. BAI 알고리즘 활용.

12.3 3. 임상 — Phase II Trial

다수 후보 약 → Phase III 에 보낼 1~2 개 선정. Simon’s Two-Stage Design 등 BAI 의 의학 변형.

12.4 4. 광고 크리에이티브 식별

50 개 광고 → 최선 1 개 1 년 사용. Successive Rejects 적합.

12.5 5. 추천 알고리즘 선정

5 개 추천 알고리즘 후보 → 1 개 production. A/B 보다 명시적 BAI 가 정확.

13 Phase I 시리즈의 종합 결론

이 글은 Phase I (8 편) 의 마지막 글이다. 시리즈 전체를 한 단락으로 압축:

Multi-Armed Bandit 은 학습과 최적화를 동시에 수행하는 문제의 정통 추상화다. Stochastic stationary 환경에서 ε-greedy 의 단순함, UCB 의 robustness, Thompson 의 Bayesian 직관이 각각 다른 매력 을 제공한다 (글 1~4). 이들을 A/B Test 와 비교하면 경쟁이 아닌 보완 관계 — 다른 질문에 답하는 도구 (글 5). 환경의 이질성과 변화 를 처리하기 위해 Contextual Bandit (글 6) 과 Non-stationary Bandit (글 7) 으로 확장하며, 마지막으로 cumulative 가 아닌 simple regret 의 영역에서 Best Arm Identification 이 완전히 다른 알고리즘 가족 을 형성한다 (글 8). 교재 (Lattimore & Szepesvári 2020) 가 도서관에 추가되면 이 시리즈는 챕터 단위로 재작성하여 30+ 편으로 확장 예정이다.

14 결론 — Best Arm Identification 의 한 줄 요약

BAI 는 cumulative regret 의 형제이자 다른 종. 학습 단계의 보상은 무관하고 마지막 추천의 정확성 만 평가. UCB·Thompson 은 차선 — Successive Rejects, UCB-E, LUCB 같은 전용 알고리즘 이 적합.

핵심 메시지:

Simple Regret: 학습 종료 시점 추천의 정확성
Two formulations: Fixed Budget vs Fixed Confidence
Mannor-Tsitsiklis lower bound: \(1/\Delta^2\) — cumulative 의 \(1/\Delta\) 와 다름
UCB-E: UCB 의 budget-aware 변형
Successive Rejects: 매개변수 자유, robust
Successive Halving: ML hyperparameter 표준
A/B Test = 2-arm BAI: 본질적으로 같은 문제

Phase I 시리즈 종료. Lattimore 교재 추가 시 재작성 예정.

15 관련 주제

선행 지식

Phase I 시리즈 종합

이 글이 Phase I (8 편) 의 마지막

다른 카테고리 연결

(Phase F) Sequential Hypothesis Testing — SPRT, Always-Valid p-value
Machine_Learning — Hyperparameter Tuning, NAS (Hyperband, Successive Halving)
(Phase J) Adaptive Trial Design — 임상에서의 BAI 응용

16 참고문헌

Audibert, J. Y., Bubeck, S., Munos, R. (2010). Best arm identification in multi-armed bandits. COLT.
Mannor, S. & Tsitsiklis, J. N. (2004). The sample complexity of exploration in the multi-armed bandit problem. J. Machine Learning Res. 5, 623-648.
Bubeck, S., Munos, R., Stoltz, G. (2009). Pure exploration in multi-armed bandits problems. Algorithmic Learning Theory.
Karnin, Z., Koren, T., Somekh, O. (2013). Almost optimal exploration in multi-armed bandits. ICML.
Li, L., Jamieson, K., DeSalvo, G., Rostamizadeh, A., Talwalkar, A. (2017). Hyperband: A novel bandit-based approach to hyperparameter optimization. J. Machine Learning Res. 18, 1-52.
Wald, A. (1947). Sequential Analysis. Wiley.
Simon, R. (1989). Optimal two-stage designs for phase II clinical trials. Control. Clin. Trials 10, 1-10.
Lattimore, T. & Szepesvári, C. (2020). Bandit Algorithms. Cambridge University Press. (교재 미확인 — agent 사전학습 기반)