UCB1 알고리즘이란?
UCB1(Upper Confidence Bound 1)은 Multi-Armed Bandit 문제의 대표적인 해법입니다. 각 선택지(arm)에 대해 "지금까지의 평균 보상"과 "아직 잘 모르니까 주는 보너스"를 합산하여 가장 높은 점수를 가진 arm을 선택합니다.
수식
$\text{Score}_a = \bar{x}_a + \sqrt{\frac{2 \ln t}{n_a}}$
- $\bar{x}_a$ : arm $a$의 평균 보상 (관측된 평균 CTR)
- $t$ : 전체 라운드 수
- $n_a$ : arm $a$가 선택된 횟수
- $\sqrt{\frac{2 \ln t}{n_a}}$ : 탐색 보너스 (많이 선택될수록 줄어듦)
탐색 보너스가 줄어드는 원리
분자의 $\ln t$는 전체 라운드가 늘어날수록 천천히 증가합니다 (로그 함수). 분모의 $n_a$는 해당 arm이 선택될 때마다 1씩 증가합니다. 따라서 특정 arm을 많이 선택할수록 보너스가 빠르게 감소합니다. 반대로, 오래 선택되지 않은 arm은 $t$만 증가하므로 보너스가 서서히 커집니다. 이것이 "덜 탐색된 arm에 기회를 준다"는 UCB의 핵심 메커니즘입니다.
로그 Regret 보장
UCB1은 수학적으로 $O(\ln t)$의 regret bound를 보장합니다. 이는 "최적의 arm만 선택했을 때와 비교한 손실"이 라운드 수에 대해 로그 함수적으로만 증가한다는 뜻입니다. 사실상 최적에 가까운 성능을 보장합니다.
UCB1 vs Thompson Sampling
- UCB1은 Deterministic: 같은 상태에서 항상 같은 arm을 선택. 디버깅과 재현이 쉬움.
- TS는 Stochastic: 확률 분포에서 샘플링하므로 매번 다른 결과. 실전 성능은 보통 TS가 약간 우위.
- UCB1은 이론적 보장이 강함. TS는 실험적 성능이 강함.
- 실무에서는 둘 다 Context-Free이므로, 개인화가 필요하면 LinUCB나 Linear TS로 확장해야 합니다.
이 데모에서 관찰할 것
- 초반 5라운드: 각 arm을 한 번씩 선택 (보너스가 INF이므로 미탐색 arm 우선)
- 10~30라운드: 보너스가 줄어들면서 높은 CTR의 arm이 더 자주 선택되기 시작
- 50라운드 이후: Ad A (High CTR)와 Ad D (Hidden Gem)에 선택이 집중되는 것을 확인
- 200라운드: Mean Reward가 실제 CTR에 매우 가깝게 수렴