UCT: 트리의 모든 노드를 밴딧으로 — MCTS의 이론적 탄생

한 줄 요약

롤아웃 기반 계획(현재 상태에서 시뮬레이션을 반복해 행동을 고르는 것)의 병목은 시뮬레이션 예산의 배분이다 — 명백히 나쁜 가지에 균등하게 예산을 쓰는 것은 낭비고, 유망해 보이는 가지만 파면 진짜 최선을 놓친다. 정확히 탐험-활용 딜레마이고, 이 논문의 답은 밴딧 이론의 낙관주의를 그대로 가져오는 것이다: 트리의 모든 내부 노드를 UCB1 밴딧으로 취급하라. 그렇게 태어난 UCT(UCB applied to Trees)가 이후 MCTS라 불리게 될 알고리즘 가족의 원형이자 수렴 증명이다.

핵심 기여

• 알고리즘 — 선택적 깊이 탐색: 루트에서부터, 트리 안에서는 각 노드에서

$a^* = \arg\max_a \left( \bar{Q}(s, a) + C \sqrt{\frac{\ln N(s)}{N(s, a)}} \right)$

를 최대화하는 자식으로 내려간다 — 첫 항은 지금까지의 표본 평균(활용), 둘째 항은 방문이 적은 가지의 불확실성 보너스(탐험). 트리 밖에 나가면 기본 정책으로 종단까지 굴리고, 결과를 경로의 모든 $(s, a)$ 통계($N$, $\bar{Q}$)에 역전파한다. 반복할수록 트리가 유망한 방향으로만 비대칭하게 자라는 것이 균등 심화(예: 반복 심화 미니맥스)와의 차이다.

• 비정상 밴딧이라는 진짜 어려움: 내부 노드에서 한 행동의 “보상”은 그 서브트리의 UCT 추정값인데, 이것은 시뮬레이션이 쌓이며 계속 변한다(수렴 중이므로) — 고전 UCB1의 i.i.d. 가정이 깨진다. 논문의 이론적 기여의 핵심이 여기다: 보상 시퀀스의 평균이 어떤 극한값으로 드리프트하며 수렴한다는 조건 하에서 UCB1의 후회(regret) 분석을 확장하고, 이 조건이 트리의 잎에서부터 귀납적으로 위로 전파됨을 보인다.

• 수렴 정리: 그 귀납의 결론 — 루트 추정값의 편향은 $O(\log n / n)$으로 줄고, 최적이 아닌 행동을 루트에서 고를 확률은 시뮬레이션 수가 늘며 다항 속도로 0에 수렴한다. 즉 UCT는 언제 끊어도 그 시점 최선의 추정을 주는 anytime 알고리즘이면서, 예산이 무한하면 최적 행동을 보장한다.

• 실험: 랜덤 게임 트리(P-game)에서 알파-베타류 및 균등 몬테카를로 대비 같은 예산으로 훨씬 낮은 실패율을, 확률적 최단 경로 문제인 sailing domain에서 ARTDP 등 대비 우수한 표본 효율을 보인다. 규모는 소박하지만, “선택적 표본 배분이 균등 탐색을 이긴다”는 논지가 이후 바둑에서 극적으로 재현된다.

계보에서의 위치

결정 시점 계획(decision-time planning)의 이론적 초석이다 — 계획과 탐색 글에서 다룬 MCTS의 4단계(선택-확장-시뮬레이션-역전파) 중 “선택”의 수학이 이 논문이고, 같은 해 Coulom의 Crazy Stone(MCTS라는 이름의 유래)과 합류하며 컴퓨터 바둑을 지배하게 된다. ε-greedy가 감으로 하던 탐험-활용 균형(탐험 이론 글)을 신뢰 상한의 낙관주의로 대체한 것이 요체인데, 10년 뒤 알파고는 이 선택 규칙에 학습된 사전 확률 $P(s,a)$를 곱한 변형(PUCT)을 쓴다 — UCT의 탐험 보너스가 “학습이 안내하는 탐색”으로 진화한 것이다. 순수 UCT의 한계(무작위 롤아웃의 부정확한 평가, 넓은 분기에서의 폭발)가 정확히 알파고의 두 신경망이 꽂힌 자리다.