UCB1 — 신뢰구간 기반 탐색

Optimism in the Face of Uncertainty 와 log N regret

Upper Confidence Bound (UCB1) 알고리즘 — 불확실성 앞에서의 낙관 원리. (1) UCB1 공식의 두 항 — 평균 (exploitation) + 신뢰구간 폭 (exploration), (2) Hoeffding 부등식의 직관 — 왜 √(log t / n) 형태인가, (3) Auer-Cesa-Bianchi-Fischer (2002) 의 log N regret 정리, (4) 결정론적 알고리즘의 매력 — hyperparameter 거의 없음, (5) Thompson Sampling 과의 비교. 시뮬레이션과 의사코드.

Experimentation
MAB
저자

Kwangmin Kim

공개

2026년 05월 09일

출처

이 글은 교재 직접 참조 없이 agent 사전학습 기반으로 작성되었다 (교재 미확인 — agent 사전학습 기반). 핵심 정리는 Auer, Cesa-Bianchi, Fischer (2002) 원논문에 한해 명시한다.

이 글은 Phase I 시리즈의 세 번째 글이다. ε-greedy 의 hyperparameter 민감도 문제를 해결하는 결정론적 대안 — UCB1 을 다룬다.

1 진입 직관 — 불확실성 앞에서의 낙관

이전 글에서 ε-greedy 의 hyperparameter 의존 함정을 보았다. UCB (Upper Confidence Bound) 는 다른 관점:

UCB 의 한 줄 원리: Optimism in the Face of Uncertainty — 불확실성 앞에서 낙관하라.

1.1 메커니즘

각 팔에 대해 진짜 평균이 있을 수 있는 상한 (upper confidence bound) 을 계산. 상한이 가장 높은 팔 을 선택. 핵심:

  • 덜 시도된 팔 은 불확실성 큼 → 상한 큼 → 시도되기 쉬움 (자동 탐색)
  • 충분히 시도된 팔 은 불확실성 작음 → 상한이 평균에 가까움 → 평균 큰 팔 선호 (자동 활용)

비유 — 식당 평가: 새로 생긴 식당 별점 1 회만 평가받음, 5점. 단골 식당 100 회 평가받음, 평균 4점. 새 식당의 진짜 평균 은 3점일 수도, 5점일 수도 — 매우 불확실. UCB 는 진짜 평균이 5점일 가능성도 있음 을 인정하고 시도해봄 (낙관).

결정적 차이: ε-greedy 의 무작위 탐색 과 달리, UCB 는 결정론적 (deterministic) — 매 시점 유일한 최선의 팔 을 계산.

2 UCB1 공식

정의: UCB1 Algorithm (Auer et al. 2002)

각 시점 \(t\) 에서:

\[ A_t = \arg\max_a \left[ \hat{\mu}_a(t) + \sqrt{\frac{2 \ln t}{n_a(t)}} \right] \]

여기서: - \(\hat{\mu}_a(t)\): 시점 \(t\) 까지 팔 \(a\) 의 표본 평균 - \(n_a(t)\): 시점 \(t\) 까지 팔 \(a\) 의 시도 횟수 - \(\ln t\): 자연 로그

두 항의 의미:

  • Exploitation 항 \(\hat{\mu}_a(t)\): 현재까지의 평균 — 실제 좋아 보이는 팔
  • Exploration 항 \(\sqrt{2 \ln t / n_a(t)}\): 신뢰구간의 반폭 — 불확실성

알고리즘:

초기화: 각 팔 1 회씩 시도 (n_a = 1, sums_a = X_a)
For t = K+1 to N:
  Compute UCB_a = sums_a / n_a + sqrt(2 ln t / n_a)  for each a
  A_t ← argmax_a UCB_a
  Observe X_t ~ ν_{A_t}, update n_{A_t}, sums_{A_t}

Hyperparameter 자유: ε-greedy 와 달리 UCB1 은 수정 가능 매개변수가 거의 없음. 상수 2 는 Hoeffding 부등식 에서 자연 도출 (다음 섹션). 기본 알고리즘 그대로 사용 가능.

3 Hoeffding 부등식 — 왜 √(log t / n) 인가

UCB1 의 exploration 항 형태 는 임의가 아니다. Hoeffding 의 부등식 에서 자연 도출.

3.1 Hoeffding 부등식

정리: \(X_1, ..., X_n\) 이 독립 동일 분포, \(X_i \in [0, 1]\), \(\mu = \mathbb{E}[X_i]\), \(\hat{\mu}_n = \frac{1}{n} \sum X_i\). 그러면:

\[ P(|\hat{\mu}_n - \mu| \geq \delta) \leq 2 e^{-2 n \delta^2} \]

3.2 UCB 도출

목표: 시점 \(t\) 까지 어떤 팔의 진짜 평균이 신뢰 상한을 초과할 확률 이 매우 작도록 보장.

\(\delta_a = \sqrt{2 \ln t / n_a}\) 로 설정하면:

\[ P(\mu_a > \hat{\mu}_a + \delta_a) \leq 2 e^{-2 n_a \delta_a^2} = 2 e^{-4 \ln t} = 2 t^{-4} \]

즉 시점 \(t\) 의 모든 팔에 대해 진짜 평균이 상한 위에 있을 확률 이 \(O(t^{-3})\) 이하 — 매우 작음.

수식 직관: \(\sqrt{\ln t}\) 의 log 증가 가 모든 시점에 신뢰 보장 을 위한 최소 비용. Union bound 로 시간에 따른 누적 위반 확률 통제.

상수 2 의 의미: Hoeffding 의 2 nδ² 에서 도출. 다른 상수 (예: \(\sqrt{2}\), \(2\sqrt{2}\)) 도 상수 배 차이 만 — 이론 결과 동일.

3.3 직관

덜 시도된 팔 (\(n_a\) 작음) 의 신뢰구간 폭이 큼 — 진짜 평균이 매우 높을 가능성 인정. 충분히 시도된 팔 (\(n_a\) 큼) 은 진짜 평균 ≈ 표본 평균 — 신뢰구간 좁음.

4 Regret Bound — Auer et al. (2002)

4.1 정리

Theorem (Auer-Cesa-Bianchi-Fischer 2002): UCB1 의 cumulative regret 은:

\[ R_N \leq \sum_{a: \mu_a < \mu^*} \frac{8 \ln N}{\Delta_a} + \left(1 + \frac{\pi^2}{3}\right) \sum_a \Delta_a \]

여기서 \(\Delta_a = \mu^* - \mu_a\) 는 gap.

4.2 함의

상한: \(R_N = O(\log N)\) — Lai-Robbins 하한 달성.

상수 8: 분석 기법 (Hoeffding) 에 의존. 더 정밀한 KL-UCB (Garivier & Cappé 2011) 는 Lai-Robbins 의 KL 형태와 정확히 일치.

4.3 핵심 통찰

Gap-dependent vs Gap-independent: UCB1 의 regret 은 gap \(\Delta_a\) 에 반비례. gap 이 크면 (팔들이 명확히 다름) regret 작음. gap 이 작으면 학습 어려움 — 자연스러움.

4.4 Regret 의 점근 형태

시간이 갈수록:

  • \(N = 100\): \(R_N \approx 8 \cdot \ln 100 / \Delta = 36.8 / \Delta\)
  • \(N = 10000\): \(R_N \approx 8 \cdot 9.2 / \Delta = 73.6 / \Delta\)

N 이 100 배 늘어도 regret 은 2 배만 증가. ε-greedy fixed 의 N 배 증가 와 대조.

5 ε-Greedy 와의 비교

측면 ε-Greedy UCB1
탐색 방식 무작위 결정론적 (신뢰구간 기반)
Hyperparameter ε (튜닝 필요) 거의 없음
Regret (이론) \(O(\log N)\) (decaying) \(O(\log N)\)
짧은 horizon 좋음 초기 K 회 의무 시도
긴 horizon Decaying 잘 튜닝 시 좋음 안정적으로 좋음
Robustness 낮음 높음

반사실: 같은 환경에서 UCB1 과 ε-greedy decaying 비교 — 보통 UCB1 이 상수 배 작은 regret. ε-greedy 는 hyperparameter 잘 튜닝하면 비슷, 잘못 튜닝하면 훨씬 나쁨. UCB1 의 robustness 가 실무 매력.

6 UCB 변형들

6.1 UCB-Tuned (Auer et al. 2002)

분산 정보 를 활용하여 exploration 항을 더 정교하게. Bounded 분산을 이용.

수식 (간략):

\[ \text{UCB-Tuned}_a = \hat{\mu}_a + \sqrt{\frac{\ln t}{n_a} \cdot \min\left(\frac{1}{4}, \hat{V}_a + \sqrt{\frac{2 \ln t}{n_a}}\right)} \]

\(\hat{V}_a\) 는 팔 \(a\) 의 표본 분산.

이론적으로는 비슷하지만 실무에서 약간 더 좋은 성능.

6.2 KL-UCB (Garivier & Cappé 2011)

Hoeffding 부등식 대신 KL divergence 사용. Lai-Robbins 하한과 정확히 일치.

6.3 Bayesian UCB

베이지안 사후분포의 quantile 을 신뢰 상한으로. Thompson Sampling 과 친척.

7 Hyperparameter 의 부재 — 매력과 한계

7.1 매력

기본 UCB1 그대로 사용 가능. 다른 알고리즘처럼 ε, decay rate, prior 같은 결정 부담 없음. baseline 으로 우수.

7.2 한계

일부 환경에서 너무 보수적 또는 너무 공격적. 변형 (UCB-Tuned, KL-UCB) 으로 조정 가능하나, 기본 UCB1 의 단순함을 잃음.

반사실: 매우 작은 gap (\(\Delta < 0.01\)) 환경에서 UCB1 의 상수 8 이 불필요한 보수성. KL-UCB 가 더 적합.

8 시뮬레이션 — UCB1 vs ε-Greedy

import numpy as np

np.random.seed(42)

K = 5
true_means = np.array([0.30, 0.50, 0.70, 0.40, 0.60])
mu_star = true_means.max()
N = 5000

def ucb1(true_means, N):
    K = len(true_means)
    pulls = np.zeros(K)
    sums = np.zeros(K)
    rewards = np.zeros(N)

    # 각 팔 1 회 사전 시도
    for a in range(K):
        r = np.random.binomial(1, true_means[a])
        pulls[a] = 1
        sums[a] = r
        rewards[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
        rewards[t] = r
    return rewards

def epsilon_greedy_decaying(true_means, N, c=10):
    K = len(true_means)
    pulls = np.zeros(K)
    sums = np.zeros(K)
    rewards = np.zeros(N)

    for a in range(K):
        r = np.random.binomial(1, true_means[a])
        pulls[a] = 1
        sums[a] = r
        rewards[a] = r

    for t in range(K, N):
        eps_t = min(1.0, c / (t + 1))
        if np.random.random() < eps_t:
            a = np.random.randint(K)
        else:
            means = sums / pulls
            a = means.argmax()
        r = np.random.binomial(1, true_means[a])
        pulls[a] += 1
        sums[a] += r
        rewards[t] = r
    return rewards

def cumulative_regret(rewards, mu_star):
    return np.arange(1, len(rewards) + 1) * mu_star - np.cumsum(rewards)

n_sim = 200
ucb_regrets = np.zeros((n_sim, N))
eg_regrets = np.zeros((n_sim, N))

for s in range(n_sim):
    ucb_regrets[s] = cumulative_regret(ucb1(true_means, N), mu_star)
    eg_regrets[s] = cumulative_regret(epsilon_greedy_decaying(true_means, N), mu_star)

print(f"[UCB1 vs ε-Greedy Decaying — N={N}, 200 회 시뮬레이션]")
print(f"진짜 means: {true_means}, mu* = {mu_star}\n")

for t_check in [100, 500, 1000, 2000, 5000]:
    if t_check <= N:
        print(f"  t={t_check:>4}: UCB1 = {ucb_regrets[:, t_check-1].mean():>6.1f}, "
              f"ε-Greedy = {eg_regrets[:, t_check-1].mean():>6.1f}")

print()
print("→ UCB1 은 N 증가 시 log 증가 (e.g., t=100 → 5000 에서 ~5 배)")
print("→ ε-Greedy decaying 도 비슷, 그러나 hyperparameter c 의 튜닝 필요")
print("→ 이론적 하한 (Lai-Robbins): O(log N)")

결과 해석:

  1. UCB1 의 regret 곡선이 log N 형태 (시간 갈수록 평탄).
  2. ε-greedy decaying 도 비슷하지만 상수 c 의 영향. c=10 은 보통 잘 작동, c=1 은 탐색 부족, c=100 은 탐색 과다.
  3. UCB1 의 robustness — hyperparameter 무관 안정.

9 A/B Test 와의 연결

9.1 A/B 의 신뢰구간

A/B 테스트의 결과는 처치 효과의 신뢰구간. 예: lift = 5%, 95% CI = (2%, 8%). 의사결정자는 전체 CI 가 0 보다 큼 또는 MDE 보다 큼 인지 확인.

9.2 UCB 의 신뢰구간

UCB 의 exploration 항 도 본질적으로 신뢰구간. 그러나 결정 단위가 다름:

  • A/B: 전체 모집단의 평균 효과 — 단일 추정
  • UCB: 각 팔의 평균을 매 시점 추정 — 적응적

9.3 결론

통계적 도구는 같음 (신뢰구간). 결정 구조가 다름. UCB 는 A/B 의 연속적·실시간 버전.

10 결론

UCB1 은 불확실성 앞에서의 낙관 원리로 log N regret 을 hyperparameter 자유 로 달성. ε-greedy 의 robustness 함정을 해결.

핵심 메시지:

  1. UCB 공식: 평균 + 신뢰구간 폭. 결정론적 탐색
  2. Hoeffding 부등식: \(\sqrt{2 \ln t / n}\) 형태의 수학적 정당화
  3. Regret O(log N): Lai-Robbins 하한 달성
  4. Hyperparameter 거의 없음: baseline 으로 매력
  5. 변형들: UCB-Tuned, KL-UCB, Bayesian UCB

다음 글: Thompson Sampling — 베이지안 사후 분포 샘플링 의 또 다른 접근.

11 관련 주제

선행 지식

Phase I 후속 글

12 참고문헌

  • Auer, P., Cesa-Bianchi, N., Fischer, P. (2002). Finite-time analysis of the multiarmed bandit problem. Machine Learning 47, 235-256.
  • Garivier, A. & Cappé, O. (2011). The KL-UCB algorithm for bounded stochastic bandits and beyond. Proceedings of COLT.
  • Lai, T. L. & Robbins, H. (1985). Asymptotically efficient adaptive allocation rules. Adv. Appl. Math. 6, 4-22.
  • Hoeffding, W. (1963). Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. 58, 13-30.
  • Lattimore, T. & Szepesvári, C. (2020). Bandit Algorithms. Cambridge University Press. (교재 미확인 — agent 사전학습 기반)

Subscribe

Enjoy this blog? Get notified of new posts by email: