강화학습의 근간 (8): 모델과 계획 — Dyna-Q, MCTS, 그리고 알파고

마지막 축 — 모델

이 시리즈가 걸어온 길을 보자. (3) DP는 모델이 주어진 세계의 계획법이었고, (4)·(6)·(7)은 모델을 포기하고 경험만으로 배우는 model-free 노선이었다. 남은 질문은 자연스럽다 — 모델이 주어지지 않는다면, 배우면 되지 않나?

경계를 정확히 긋자. model-free: 경험 → 가치/정책 (환경이 어떻게 굴러가는지는 표현하지 않는다). model-based: 경험 → 모델($\hat{\mathcal{P}}, \hat{\mathcal{R}}$의 추정) → 계획으로 가치/정책. 모델 학습 자체는 강화학습이 아니라 지도학습이다 — $(s, a) \mapsto s'$은 (밀도 추정 또는) 회귀, $(s, a) \mapsto r$은 회귀. 그래서 지도학습의 온갖 도구가 그대로 들어오고, 보상 신호보다 훨씬 진한 학습 신호(모든 전이가 레이블이다)를 쓸 수 있다.

무엇을 얻고 무엇을 잃는가. 얻는 것: 표본 효율(실제 경험 한 번을 모의 경험 수십 번으로 증폭), 그리고 환경 이해의 전이 가능성(보상이 바뀌어도 전이 모델은 재사용된다). 잃는 것: 오류원이 하나 늘어난다 — 모델이 틀리면, 그 모델에 대한 최적 계획은 실제 환경에서 최적이 아니다. model-based RL의 역사는 사실상 이 모델 오차와의 싸움이다.

Dyna-Q — Q-learning에 상상을 얹다

Dyna-Q(Sutton, 1990)는 이 통합의 원형이고, 위치를 정확히 잡는 것이 중요하다: Dyna-Q는 별도 계열의 “월드 모델” 알고리즘이 아니라, Q-learning의 발전형이다. 골격이 문자 그대로 (6)의 Q-learning이고, 모델은 그 갱신을 증폭하는 장치로만 쓰인다. 실제 스텝 하나마다:

1. 직접 RL: 실제 전이 $(S, A, R, S')$로 보통의 Q-learning 갱신 $Q(S, A) \leftarrow Q(S, A) + \alpha \big( R + \gamma \max_{a'} Q(S', a') - Q(S, A) \big)$
2. 모델 학습: $\text{Model}(S, A) \leftarrow (R, S')$ (결정적 표 환경이면 그냥 마지막 결과를 기억)
3. 계획: $n$번 반복 — 과거에 겪은 $(s, a)$를 무작위로 뽑고, 모델이 돌려준 $(r, s')$로 1과 정확히 같은 Q-learning 갱신

계획 단계의 갱신식이 직접 RL과 동일하다는 것이 설계의 핵심이다 — 경험이 실제냐 모의냐만 다를 뿐, 학습기는 하나다. 효과는 극적이다: 미로 실험에서 $n = 0$(순수 Q-learning)이 수십 에피소드 걸리는 것을 $n = 50$이 몇 에피소드에 끝낸다. 실제 경험 한 스텝이 가치 표 전체에 $n$배로 전파되기 때문이다. 모델이 틀렸을 때(환경이 도중에 바뀌는 blocking/shortcut 미로)의 취약성과, 탐험 보너스로 그것을 완화한 Dyna-Q+까지가 원 논문의 이야기다 — 상세는 리뷰 참고.

한 가지 계보 정리. 잠재 공간에서 상상 궤적을 굴리는 현대의 월드 모델 계열(World Models, PlaNet, Dreamer)은 “배운 모델 안에서 학습한다”는 정신을 Dyna와 공유하지만, 표 형태 모델로 Q 갱신을 증폭하는 Dyna-Q와는 문제 설정(픽셀 관측, 잠재 상태 학습)도 계보도 다른, 한참 뒤의 발전이다. Dyna-Q를 “월드 모델의 시조”로만 읽으면 정작 본체 — Q-learning의 표본 효율 증강 — 를 놓친다.

배경 계획과 결정 시점 계획

Dyna의 계획은 배경(background) 계획이다 — 모의 경험으로 전역 가치 함수를 조금씩 개선하고, 행동은 그 가치에서 나온다. 전혀 다른 사용법이 있다: 행동해야 하는 바로 그 순간, 현재 상태 하나를 위해 모델을 굴려 계산을 쏟아붓고, 수를 고른 뒤 그 계산을 버리는 — 결정 시점(decision-time) 계획이다. 체스 기사가 지금 이 국면만 깊이 읽는 것과 같다. 상태 공간 전체의 가치를 유지할 수 없는 거대한 문제(바둑: $\sim 10^{170}$ 상태)에서는 이쪽이 유일한 길이다.

MCTS — 유망한 곳만 깊게 파는 트리

결정 시점 계획의 소박한 형태는 롤아웃: 현재 상태에서 각 행동을 한 번씩 해보고, 이후를 아무 정책으로 끝까지 시뮬레이션해 평균 수익이 최고인 행동을 고른다. MCTS(Monte-Carlo Tree Search) 는 여기에 두 가지를 얹는다 — 시뮬레이션 결과를 트리로 축적하고, 다음 시뮬레이션을 유망한 가지에 집중 배분한다. 한 번의 시뮬레이션은 네 단계다:

1. 선택(selection): 루트에서부터, 트리 안에서는 다음 기준을 최대화하는 자식으로 내려간다 — UCT(UCB for Trees): $a^* = \arg\max_a \left( Q(s, a) + c \sqrt{\frac{\ln N(s)}{N(s, a)}} \right)$ 첫 항은 활용(지금까지의 평균 성적), 둘째 항은 탐험(적게 방문한 가지의 보너스) — 트리의 각 내부 노드를 “자식 중 어디에 다음 시뮬레이션을 쓸까”라는 밴딧으로 취급한 것으로, (5)에서 다진 UCB1의 낙관주의가 문자 그대로 트리에 이식되는 순간이다.
2. 확장(expansion): 트리의 잎에 도달하면 노드를 하나 추가한다.
3. 시뮬레이션(rollout): 거기서부터 빠른 기본 정책으로 종단까지 굴려 결과를 얻는다.
4. 역전파(backup): 결과를 경로의 모든 $(s, a)$에 반영 — $N$을 올리고 $Q$를 평균으로 갱신.

이것을 시간이 허락하는 만큼 반복하면, 트리는 비대칭으로 자란다 — 유망한 변화는 수십 수 깊이, 나쁜 수는 한 층에서 방치. 시뮬레이션이 무한하면 UCT의 루트 가치는 미니맥스 최적값으로 수렴함이 증명되어 있고, 유한 예산에서는 “계산을 가장 중요한 곳에 배분하는” 언제든-멈출-수-있는(anytime) 알고리즘이 된다. 강화학습의 언어로 읽으면 MCTS는 현재 상태를 루트로 하는 부분 MDP에 대해, 표본 backup으로 국소 가치표를 만드는 즉석 GPI다.

알파고 — 배운 신경망으로 탐색을 자르다

순수 MCTS는 2000년대 바둑 프로그램을 아마추어 고수까지 올렸지만 거기서 멈췄다. 병목은 두 개 — 폭(바둑은 수당 선택지가 ~250개라 트리가 옆으로 폭발한다)과 깊이(무작위 롤아웃은 바둑처럼 긴 게임에서 평가가 부정확하다). 알파고(2016)의 설계는 이 두 병목에 학습된 신경망을 하나씩 꽂은 것이다:

• 정책망 $p_\sigma(a \mid s)$ — 폭을 자른다. 인간 기보로 지도학습(SL)한 착수 예측망을 사전(prior) 으로 써서, UCT의 탐험 항을 변형한 $a^* = \arg\max_a \left( Q(s, a) + c \, p_\sigma(a \mid s) \frac{\sqrt{N(s)}}{1 + N(s, a)} \right)$ 로 “사람이라면 고려할 수”부터 탐색한다. 이 SL 정책망을 self-play policy gradient로 더 강화한 RL 정책망이 다음 부품의 학습 데이터를 만든다.
• 가치망 $v_\theta(s)$ — 깊이를 자른다. RL 정책망의 self-play 국면 3천만 개로 “이 국면의 승률”을 회귀 학습해, 잎 노드를 끝까지 굴리지 않고 평가한다. 실제로는 빠른 롤아웃 결과 $z$와 혼합한 $V(s_L) = (1 - \lambda) v_\theta(s_L) + \lambda z$가 어느 한쪽보다 강했다.

즉 알파고 = MCTS(계획) + 정책망(폭 축소 사전) + 가치망(깊이 절단 평가) — 이 시리즈에서 쌓은 부품들이 처음으로 한 시스템에 전부 등장한다: 지도학습, policy gradient, 가치 함수 회귀, 그리고 결정 시점 계획.

알파고 제로(2017)는 이 설계를 증류한다. 인간 기보 제거, 롤아웃 제거, 정책·가치를 하나의 네트워크 $(p, v) = f_\theta(s)$로 통합 — 그리고 학습 루프가 아름답다: 현재 네트워크로 MCTS를 돌리면 탐색이 만든 착수 분포 $\pi_{\text{MCTS}}$는 네트워크의 원래 정책 $p$보다 강하다(탐색이 정책을 개선했으므로). 그러니 $p$를 $\pi_{\text{MCTS}}$에, $v$를 self-play 승패 $z$에 맞추도록 지도학습하면 네트워크가 강해지고, 강해진 네트워크는 더 강한 MCTS를 만든다. MCTS가 정책 개선 연산자, 네트워크 학습이 정책 평가 — (3)의 GPI가 그대로, 사상 최대 규모로 구현된 것이다. 36시간의 self-play만으로 이세돌을 이긴 버전을 넘어섰다.

시리즈를 닫으며

(1)의 두 뿌리에서 출발해 — (2) MDP라는 언어, (3) 모델이 있을 때의 계획(DP), (4) 모델 없이 예측(MC/TD/TD(λ)), (5) 탐험의 이론(밴딧/regret/UCB), (6) 모델 없이 제어(SARSA/Q-learning/DQN), (7) 정책 직접 최적화(REINFORCE→PPO), (8) 모델을 배워서 계획(Dyna-Q/MCTS/알파고) — 강화학습의 뼈대 전부를 걸었다. 이 지형 전체를 가치/정책 두 갈래의 지도 한 장으로 접는 다음 글로 시리즈를 닫는다.