UCB 알고리즘군은 왜 단순한 공식으로 near-optimal 탐색을 달성하는가

Multi-Armed Bandit 문제에서 탐색(exploration)과 착취(exploitation)의 균형을 맞추는 방법은 수십 년간 연구되어 왔다. 그런데 UCB1부터 KL-UCB, MOSS에 이르기까지 서로 다른 알고리즘들이 공통적으로 단 하나의 공식 패턴 — empirical mean + bonus — 을 공유한다는 사실은 우연이 아니다. 왜 이 단순한 구조가 정보이론적 하한에 근접하는 regret 보장을 가능하게 하는가?

Optimism in the Face of Uncertainty

모든 UCB 계열 알고리즘의 출발점은 OFU(Optimism in the Face of Uncertainty) 원칙이다.

$$\text{UCB}_k(t) = \hat\mu_k(t) + \text{bonus}_k(t), \quad I_t = \arg\max_k \text{UCB}_k(t)$$

여기서 $\hat\mu_k(t)$는 arm $k$의 경험적 평균, bonus는 불확실성을 반영한 상향 보정이다. 핵심은 두 가지다. 첫째, 탐색 횟수 $N_k(t)$가 작을수록 bonus가 크므로 덜 시도된 arm을 우선 선택한다. 둘째, arm이 실제로 나쁘면 $\hat\mu_k$가 낮아지므로 bonus가 아무리 커도 결국 선택에서 밀려난다. 이 자동 해소(automatic elimination) 메커니즘이 OFU를 단순한 낙관론과 구분짓는다.

Hoeffding inequality를 사용하면 bonus의 형태가 자연스럽게 유도된다. 샘플 $N$개에서 신뢰수준 $\delta$를 보장하는 confidence radius는

$$b = \sqrt{\frac{\ln(1/\delta)}{2N}}$$

이다. 전체 시간과 arm에 union bound를 적용하면 $\delta = 1/t^2$으로 설정하는 것이 자연스럽고, 이로부터 UCB1의 bonus $\sqrt{2\ln t / N_k}$가 나온다.

UCB1 Regret 증명의 구조

UCB1(Auer et al. 2002)의 regret bound는 다음과 같다.

$$R_T \leq \sum_{k:\,\Delta_k > 0} \frac{8\ln T}{\Delta_k} + \left(1 + \frac{\pi^2}{3}\right)\sum_k \Delta_k$$

여기서 $\Delta_k = \mu^* - \mu_k$는 sub-optimality gap이다.

Worst-case 분석에서 모든 gap을 $\Delta_k = \Theta(1/\sqrt{T})$로 설정하면 이 bound는 $O(\sqrt{KT\ln T})$가 된다. 한편 minimax lower bound는 $\Omega(\sqrt{KT})$이므로, UCB1은 $\sqrt{\ln T}$ factor만큼 최적에서 벗어난다.

KL-UCB — 정보이론적 최적성

UCB1의 Hoeffding bound는 distribution-free이므로 상수가 느슨하다. Garivier & Cappé (2011)의 KL-UCB는 이를 KL divergence로 교체한다.

$$\text{UCB}_k(t) = \sup\left\{q : N_k(t) \cdot D(\hat\mu_k(t) \| q) \leq \ln(t/\delta)\right\}$$

Bernoulli KL divergence $D(\mu \| q) = \mu\ln(\mu/q) + (1-\mu)\ln((1-\mu)/(1-q))$는 Hoeffding보다 약 2배 좁은 confidence set을 만든다. 이 차이는 단순한 상수 개선이 아니라, distribution의 내부 구조를 활용하는 것이다.

KL-UCB의 regret bound는 다음과 같다.

$$R_T \leq (1+o(1))\sum_{k\neq k^*} \frac{\ln T}{D(\mu_k \| \mu^*)}$$

이것이 중요한 이유는 Lai-Robbins lower bound와 정확히 일치하기 때문이다.

$$\liminf_{T\to\infty} \frac{R_T}{\ln T} \geq \sum_{k\neq k^*} \frac{\Delta_k}{D(\mu_k \| \mu^*)}$$

이 하한은 정보이론적으로 불가피하다. Arm $k$와 optimal arm $k^*$를 구분하려면 hypothesis test를 통과해야 하고, 그 비용은 정확히 $\ln T / D(\mu_k \| \mu^*)$만큼의 샘플을 요구한다. KL-UCB는 이 비용을 정확히 지불한다 — 더도 덜도 아니게.

MOSS — $\sqrt{\ln T}$ 없이 Minimax 달성

MOSS(Minimax Optimal Strategy in the Stochastic case, Audibert & Bubeck 2010)는 $\sqrt{\ln T}$ factor를 완전히 제거한다.

$$\text{MOSS}_k(t) = \hat\mu_k(t) + \sqrt{\frac{\ln\!\left(T/(K \cdot N_k(t))\right)^+}{N_k(t)}}$$

여기서 $(x)^+ = \max(x, 0)$이다. UCB1의 $\ln t$와 달리 MOSS는 $\ln(T/(KN_k))$를 사용한다. 이 차이는 작아 보이지만 결정적이다. $N_k > T/K$가 되면 log 항이 0이 되어 bonus가 사라진다 — arm이 “할당된 예산”을 다 썼다는 신호다.

이 메커니즘은 각 arm에 $T/K$의 균등 예산을 암묵적으로 배분한다. 균형 gap $\Delta_k = \Theta(1/\sqrt{T})$ 위에서 MOSS의 regret은

$$R_T = O\!\left(\sqrt{KT}\right)$$

가 되어 lower bound $\Omega(\sqrt{KT})$와 정확히 맞아 떨어진다. 단, MOSS는 $T$를 미리 알아야 한다. UCB1의 anytime 성질을 잃는 대가로 $\sqrt{\ln T}$ factor를 제거한 것이다.

정리

• OFU 원칙은 UCB = empirical mean + bonus 형태로 UCB1, KL-UCB, MOSS, UCRL2, LSVI-UCB까지 이어지는 통일 프레임워크다.
• UCB1의 regret 증명은 good event + case analysis + union bound의 세 단계로 구성되며, $N_k(T) \leq 8\ln T / \Delta_k^2$가 핵심 부등식이다.
• KL-UCB는 distribution 고유의 KL divergence를 활용해 Lai-Robbins 하한을 달성한다 — problem-dependent 최적.
• MOSS는 $\ln(T/(KN_k))$ bonus로 각 arm의 탐색 예산을 동적으로 조절해 $O(\sqrt{KT})$ minimax 최적을 달성한다.

단순한 공식 뒤에는 통계적 신뢰와 정보이론적 필연이 함께 있다.