바닥부터 배우는 강화 학습 | 10. 알파고와 MCTS

'바닥부터 배우는 강화 학습' 10장에는 MCTS(Monte Carlo Tree Search)의 개념과 알파고에 대해서 설명하고 있습니다. 아래 내용은 공부하면서 핵심 내용을 정리한 것입니다.

참고자료

도서: 바닥부터 배우는 강화 학습 / 10장 알파고와 MCTS

10.1 알파고

알파고는 2016년 3월에 이세돌과 바둑을 뒀던 버전
학습(learning) 단계
◦ 이세돌을 만나기 전에 이루어지는 과정
◦ 이후 단계에서 사용될 재료들을 미리 만들어 두는 과정
플래닝(decision-time planning)
◦ 이세돌과의 대국 도중에 실시간으로 이루어지는 과정
◦ 알파고 차례가 되었을 때 어디에 바둑알을 놓을지 고민하는 과정
◦ 알파고는 실시간 플래닝 알고리즘으로 MCTS(Monte Carlo Tree Search) 사용

◈ 학습 단계

학습 단계는 실시간 플래닝, 즉 MCTS에 쓰일 재료를 만드는 과정
MCTS에 필요한 4가지 (3개의 정책 네트워크, 1개의 밸류 네트워크)
◦ 사람의 기보를 이용해 지도 학습한 정책 $\pi_{sl}$
◦ 롤아웃 정책 $\pi_{roll}$
◦ 스스로 대국하며 강화 학습한 정책 $\pi_{rl}$
◦ 밸류 네트워크 $v_{rl}$

1. 지도 학습 정책 $\pi_{sl}$

알파고의 모든 과정은 바둑 기사의 기보 데이터를 활용해 $\pi_{sl}$이라는 뉴럴넷을 학습시키는 것으로부터 시작
바둑판의 상태 정보 $s$가 인풋으로 들어오면 총 19*19 = 361개의 바둑 칸들 중 현재 둘 수 있는 곳에 대해 실제로 돌을 내려놓을 확률을 리턴 (361개의 클래스가 있고 그중에 하나로 분류(classification) 해주는 네트워크)
위와 같은 방법으로 3천만 개의 기보 안에 있는 "평균 전략"을 학습
13개 층의 컨볼루션 레이어(convolutional layer)를 쌓아 올려서 구성
바둑판의 정보를 토대로 사람의 지식을 이용하여 만든 feature를 48겹을 쌓아서 인풋으로 제공 ($19 \times 19 \times 48$)
학습 결과 $\pi_{sl}$은 주어진 데이터에 대해 57%의 정답률을 기록 (아마 5단 정도의 실력)

2. 롤아웃 정책 $\pi_{roll}$

롤아웃 정책 $\pi_{roll}$은 $\pi_{sl}$의 가벼운 버전
사람의 지식을 이용하여 만든 수많은 feature에 대해 선형 결합 레이어가 1개
속도가 매우 빠름 ($\pi_{sl}: 3ms, \pi_{roll}: 2μs$), $\pi_{sl}$이 $\pi_{roll}$ 보다 1500배 시간이 필요
$\pi_{roll}$의 정확도는 24%
$\pi_{roll}$이 필요한 이유는 MCTS 단계에서 같은 시간 동안 더 많은 수를 시뮬레이션해 볼 수 있음.
결국 MCTS의 성능을 올려 줌

3. 강화 학습 정책 $\pi_{rl}$

$\pi_{rl}$은 $\pi_{sl}$과 완벽히 똑 같이 생긴 뉴럴 네트워크이고 $\pi_{rl}$의 파라미터들은 $\pi_{sl}$을 이용해 초기화
$\pi_{rl}$은 self-play를 통해 계속해서 강화됨
$\pi_{sl}$로 초기화된 정책끼리 대결은 훨씬 고품질의 경기를 생산. (위 그림처럼 높은 산을 오르는데 산의 중간부터 오르는 것)
자신의 과거 모델들을 이용해 풀을 만들고, 풀에서 랜덤 하게 하나를 뽑아와서 경기를 펼치는 방식

학습을 받고 있는 네트워크가 500번 업데이트될 때마다 해당 모델을 풀에 넣어줌
알파고의 보상함수는 경기를 이기면 1, 지면 -1, 그 외의 중간 보상은 전혀 없음
policy gradient 방법론을 사용하였고 그중에서도 리턴만 있으면 학습할 수 있는 REINFORCE 알고리즘 사용

$$\nabla_{\theta}J(\theta) = \mathbb{E} \left[ \nabla_{\theta} \log \pi_{\theta} (s, a) * G_t \right]$$

$\gamma$ 값은 1.0
◦ 이긴 경기에서 발생한 모든 액션의 확률은 동등하게 증가
◦ 진 경기에서 발생한 모든 액션의 확률은 동등하게 감소
GPU 50대를 이용해 1일간 학습, 128경기의 데이터를 이용해 1개의 미니 배치를 구성
학습이 끝난 $\pi_{rl}$은 80%의 승률로 $\pi_{sl}$을 이김
MTCS 과정에서 $\pi_{rl}$이 직접적으로 사용되지 않음. $\pi_{rl}$은 다음 재료인 $v_{rl}$을 구하는데 핵심 역할을 할 뿐

4. 밸류 네트워크 $v_{rl}$

$v_{rl}$의 신경만 구조는 $\pi_{sl}$, $\pi_{rl}$과 동일하지만 아웃풋이 $19 \times 19$가 아니라 1개의 값

$$v_{\pi_{rl}}(s) = \mathbb{E} \left [ G_t | s_t = s \right ]$$

$\gamma=1.0$이고 중간 보상이 없기 때문에 결국 $s$에서 시작하여 1을 받을지, -1을 받을지 예측하는 함수, 즉 승자를 예측하는 함수 임
$v_{rl}$의 손실함수는 MSE(mean squared error)로 정의
총 3천만 개의 각기 다른 게임에서 나온 상태를 가지고 데이터 셋을 만드고 50개의 GPU로 1주일간 학습
$v_{rl}$은 임의의 상태를 인풋으로 넣었을 때 해당 경기의 승가가 누가 될지 그 결과를 가늠할 수 있음

◈ Monte Carlo Tree Search(MCTS)

MCTS는 주어진 상황에서 시작하여 "그냥 많이 둬 보는" 방법론
MCTS는 주어진 상황에 특화된 해를 찾는데 쓰이는 플래닝(planning) 알고리즘

주어진 상황을 $s$라 하면 $s$부터 시작하여 주어진 시간 안에 초대한 많은 게임을 시뮬레이션해 보는 것
$s$에서 할 수 있는 액션 $a_1, a_2, ..., a_{180}$까지 할 수 있는 액션을 최대한 다양하게 해 봄
다양한 액션을 해 보고 결과가 가장 좋았던 액션을 실제로 선택하는 방법이 MCTS
$\pi_{rl}$이 바로 결정을 내리는 것보다 좋음
MCTS를 사용하기 위한 몇 가지 까다로운 조건
◦ MDP의 모델을 알아야 함 $(P_{ss'}^a, R_s^a)$
◦ 게임 중간마다 MCTS를 실행할 시간적 틈이 있어야 함
MCTS는 선택, 확장, 시뮬레이션, 백 프로파게이션 4 단계로 구성
4단계가 한 바퀴 돌면 새로운 노드가 생성됨, 노드(node)는 바둑판의 상태에 해당, 엣지(edge)는 액션에 해당
노드를 평가하고 그 노드에 오기까지 거쳐온 모든 경로의 모든 엣지(액션)의 가치를 업데이트
이 평가를 바탕으로 좋았던 액션을 선택

1. 선택

루트 노두에서 출발하여 리프 노드(leaf node, 자식이 없는 노드)까지 과는 과정
리프 노드에 도착하면 다음 단계인 확장 단계로 넘어감
기존에 평가해 놓은 각 액션의 벨류를 높은 액션을 선택

$$a_t = \underset{a}{\mathrm{argmax}} \left ( Q(s_t, a) + u(s_t, a) \right ) $$

$Q(s_t, a)$: 시뮬레이션 실행 후 얼마나 좋은 지
$u(s_t, a)$: 시뮬레이션 실행 전 얼마나 좋을 것이라 추측하는지(prior)
시뮬레이션을 진행하면 경험이 쌓일수록 $Q(s_t, a)$의 영향력이 커지고 $u(s_t, a)$의 영향력은 줄어듦
시뮬레이션 도중 어떤 상태 $s_{78}$에서 액션 $a_{33}$을 선택하는 경험을 총 100번 했다고 가정한 경우

$$Q(s_{78}, a_{33}) = {1 \over 100} \sum_{i=1}^{100} V(s_L^i)$$

다시 말해 $(s_{78}, a_{33})$을 지나서 도달한 리프 노드의 평균 밸류

$$u(s_t, a) \propto {P(s, a) \over 1 + N(s, a)}$$

$P(s, a)$는 사전 확률(prior probability)로 시뮬레이션해 보기 전에 각 액션에 확률을 부여함
$P(s, a) = \pi_{sl}(s, a)$
$N(s, a)$는 시뮬레이션 도중 엣지 (s, a)를 지나간 횟수
$N(s, a)=0$에서 시작하여 한 번 지나갈 때마다 1씩 더해 짐
시뮬레이션이 진행되면 분모가 커지면서 사전 확률의 영향이 줄어듦
$\pi_{rl}$ 보다 $\pi_{sl}$이 더 다양한 액션을 시도하는 정책이었기 때문에 $\pi_{sl}$로 사전확률을 초기화

2. 확장(Expansion)

방금 도달한 리프 노드를 실제로 트리에 매달아 주는 과정
또한 이 노드에서 뻗어나가는 엣지들의 다양한 정보를 초기화

$$\begin{equation}
\begin{split}
P(s, a) &\gets \pi_{sl}(s, a) \\
N(s, a) &\gets 0 \\
Q(s, a) &\gets 0 \\
\end{split}
\end{equation}$$

3. 시뮬레이션(Simulation)

리프 노두가 트리의 정식 노드가 되었기 때문에 노드의 가치를 평가, $V(s_L)$를 계산
MCTS에서 노드의 벨류를 계산하는 두 가지 방법
◦ 리프 노드 $s_L$부터 시작하여 게임이 끝날 때까지 빠르게 시뮬레이션해 봄 ($\pi_{roll}$을 이용해 $z_L$ 계산)
◦ 벨류 네트워크 $v_{rl}(s)$를 활용
알파고는 위 두 가지 방법을 섞어서 계산

$$V(s_L) = {1 \over 2} v_{rl}(s_L) + {1 \over 2} z_L$$

4. 백 프로파게이션(Back propagation)

백 프로파게이션은 에지를 지나서 도달한 리프 노드 밸류의 평균값인 $Q(s, a)$를 계산해 주는 과정
이미 계산된 평균값에 새롭게 도달한 리프 노드의 밸류를 평균에 반영하기 위해 평균값 Q(s, a)를 업데이트해 주는 과정

$$\begin{equation}
\begin{split}
N(s, a) &\gets N(s, a) + 1 \\
Q(s, a) &\gets Q(s, a) + {1 \over N(s, a)} \left ( V(s_L) - Q(s, a) \right ) \\
\end{split}
\end{equation}$$