Model-based RL에서 MCTS는 전역 value를 꾸준히 개선하는 Dyna식 background planning과 대비되는, 지금 이 state에서 무엇을 할지를 그 자리에서 탐색하는 decision-time planning으로 소개했다. 이 글은 MCTS의 네 단계를 하나씩 뜯어보고, 왜 이 방식이 거대한 탐색 공간에서도 동작하는지를 본다.
참고: UCT는 Kocsis & Szepesvári (2006)가 제안했다.
왜 트리 탐색인가
현재 state에서 시작해 가능한 모든 행동 순서를 끝까지 펼치면 완벽한 계획을 세울 수 있다. 하지만 바둑처럼 분기 수가 크고 깊이가 깊은 문제에서 이 트리는 천문학적으로 커진다. 전체를 다 볼 수 없다면, 유망한 가지에 탐색을 몰아주고 가망 없는 가지는 일찍 접어야 한다.
MCTS는 이를 위해 모델(시뮬레이터)을 이용해 현재 state를 뿌리로 하는 탐색 트리를 점진적으로, 비대칭적으로 키운다. 매 반복마다 아래 네 단계를 거치며, 시간이 허락하는 만큼 반복한 뒤 가장 좋아 보이는 행동을 실제로 둔다.
네 단계
MCTS 한 번의 반복: selection → expansion → simulation → backpropagation. node의 숫자는 (이긴 횟수 / 방문 횟수)다. 출처: Wikimedia Commons (CC BY-SA)
1. Selection (선택). 뿌리에서 출발해, 이미 트리에 있는 node 안에서는 tree policy에 따라 자식을 골라 내려간다. 아직 펼치지 않은 자식이 있는 node에 도달할 때까지 내려간다. tree policy로는 보통 UCT(아래)를 쓴다.
2. Expansion (확장). 도달한 node에서 아직 시도하지 않은 행동 하나를 골라, 그에 해당하는 자식 node를 트리에 새로 추가한다.
3. Simulation (시뮬레이션, rollout). 새로 추가한 node에서부터 default policy(가장 단순하게는 무작위)로 게임이 끝날 때까지 빠르게 진행해, 그 결과(승패 또는 누적 보상)를 하나 얻는다. 이 단계는 트리에 저장하지 않는, 한 번 쓰고 버리는 추정이다.
4. Backpropagation (역전파). 시뮬레이션 결과를 방금 내려온 경로를 따라 뿌리까지 거슬러 올리며, 경로상 각 node의 방문 횟수 과 가치 추정 를 갱신한다.
여기서 는 이번 시뮬레이션에서 얻은 결과다. 즉 각 의 는 그 가지를 지나간 시뮬레이션 결과들의 평균으로 수렴한다.
이 네 단계를 수천~수십만 번 반복한 뒤, 뿌리에서 가장 많이 방문된(또는 가치가 가장 높은) 행동을 실제 수로 선택한다.
UCT: 탐색과 활용의 균형
Selection 단계의 핵심은 tree policy다. 각 node에서 어떤 자식으로 내려갈지는 UCT(Upper Confidence bounds applied to Trees) 기준으로 정한다. 이는 multi-armed bandit의 UCB1을 트리에 적용한 것이다.
두 항의 역할이 다르다.
- — 활용(exploitation): 지금까지 좋았던 행동을 선호한다.
- — 탐색(exploration): 부모는 많이 방문됐는데( 큼) 정작 적게 시도된( 작음) 행동에 보너스를 준다. 는 둘의 비중을 정하는 상수다.
보너스 항은 어디서 왔나: Hoeffding에서 UCB1까지
탐색 항의 정확한 꼴은 임의로 정한 것이 아니라 신뢰구간의 폭에서 유도된다. 어떤 를 번 시뮬레이션해 평균 를 얻었다고 하자. 결과가 범위의 독립 표본이라면, Hoeffding 부등식이 “추정이 참값보다 이상 낮게 나올 확률”을 제한한다.
이제 이 실패 확률을, 탐색이 진행될수록(가 클수록) 더 엄격해지도록 에 맞춰 잡으면 신뢰폭 가 풀려 나온다.
이것이 UCB1이고, UCT의 탐색 항은 정확히 이 다 (위 유도의 상수가 에 해당). 그래서 UCT 점수 는 “가 그럴듯하게 가질 수 있는 최댓값”, 즉 신뢰구간의 상한이라는 뜻을 갖는다. 매번 상한이 가장 높은 행동을 고르는 것 — optimism in the face of uncertainty — 이 UCB 계열의 핵심 원리다. 시도가 적어 불확실한 행동은 상한이 높아 선택되고, 선택되고 나면 가 늘어 상한이 내려오므로, 나쁜 행동은 로그 빈도로만 재방문된다.
분자가 가 아니라 인 것도 여기서 설명된다. 실패 확률을 다항식 꼴로 조이는 데는 로그만큼의 보너스면 충분하고, 그 덕에 모든 행동이 무한히 자주, 그러나 점점 드물게 재검토된다. 탐색 낭비(regret)가 시뮬레이션 수에 로그로만 자라는 이유다.
이 보너스 덕분에, 한두 번 운 나쁘게 나쁜 결과가 나온 행동도 영영 버려지지 않고 충분히 재검토된다. 시뮬레이션이 무한히 많아지면 UCT는 최적 행동으로 수렴함이 알려져 있다. Model-free Control의 -greedy가 모든 비최적 행동을 똑같은 확률로 찔러보는 것과 달리, UCT는 불확실한 행동에 더, 확실히 나쁜 행동에 덜 탐색을 배분한다는 점이 핵심이다.
비대칭 트리와 anytime 성질
UCT가 만드는 트리는 비대칭적이다. 유망한 수 쪽으로는 트리가 깊고 빽빽하게 자라고, 가망 없는 수 쪽은 얕게 남는다. 인간 기사가 좋은 수 위주로 더 깊이 읽는 것과 닮았다. 전체를 균일하게 펼치는 완전 탐색과 달리, 한정된 계산을 가치 있는 곳에 몰아주는 것이다.
또한 MCTS는 anytime 알고리즘이다. 언제 멈추든 그 시점까지의 추정으로 최선의 행동을 답할 수 있고, 시간을 더 줄수록 추정이 좋아진다. 실시간 대국에서 시간 예산에 맞춰 탐색량을 조절할 수 있는 이유다.
한계, 그리고 다음
기본 MCTS의 약점은 simulation 단계의 무작위 rollout이다. 무작위로 끝까지 두는 추정은 분산이 크고, 분기가 큰 문제에서는 한 번의 rollout이 국면을 제대로 대표하지 못한다. 또 좋은 수로 탐색을 좁히는 일도 순전히 통계에만 의존한다.
AlphaGo·AlphaZero는 바로 이 두 약점을 neural network로 메운다. value network가 끝까지 두지 않고도 국면 가치를 추정해 무작위 rollout을 대체하고, policy network가 selection을 유망한 수로 좁힌다. 다음 글에서 이 결합을 살펴본다.