모델 기반 강화학습과 계획: Dyna-Q · 몬테카를로 트리 탐색(UCT · PUCT) · 월드 모델 지도

모델 기반 강화학습과 계획: Dyna-Q · 몬테카를로 트리 탐색(UCT · PUCT) · 월드 모델 지도

사람은 체스를 둘 때 말을 실제로 움직이기 전에 머릿속으로 몇 수를 미리 둬 봅니다. 강화학습에서도 환경이 어떻게 반응할지 예측하는 모델이 있으면, 실제 경험 없이 '상상 속 경험'으로 배우거나(Dyna), 행동하기 직전에 미리 탐색해(MCTS) 더 좋은 수를 고를 수 있습니다. 이 수업은 Dyna-Q를 직접 돌려 계획의 효과를 숫자로 보고, MCTS의 네 단계와 UCT · PUCT 선택 규칙을 손계산한 뒤, AlphaGo부터 MuZero · Dreamer까지의 모델 기반 방법 지도를 그립니다.

들어가기 전에

• 탐험 심화: UCB · 톰슨 샘플링 · 후회 — MCTS의 선택 규칙은 UCB를 나무의 각 마디에 적용한 것입니다.
• 직접 해 보기: 그리드월드 Q-러닝 — 이 수업의 Dyna-Q 실험은 그 실습의 절벽 걷기 환경을 그대로 씁니다.
• 정책 최적화 실전 — 정책 · 가치 신경망이 무엇인지 알면 AlphaZero 계열이 쉽게 읽힙니다.

한눈에 보기

• 모델 없는(model-free) 방법과 모델 기반(model-based) 방법의 장단점을 비교할 수 있습니다.
• Dyna-Q에서 계획 걸음 수 $n$ 을 늘리면 실제 경험이 얼마나 줄어드는지 실행 결과로 봅니다.
• MCTS의 선택 · 확장 · 시뮬레이션 · 역전파 네 단계를 설명할 수 있습니다.
• UCT와 PUCT 점수를 손으로 계산하고, 사전 확률이 탐색을 어떻게 이끄는지 압니다.
• AlphaGo · AlphaZero · MuZero · 월드 모델 · Dreamer가 지도 위 어디에 있는지 압니다.

1. 모델이란 무엇이고 왜 쓰나

직관(해설용 비유). 운전 연습을 실제 도로에서만 하면 시간도 들고 위험합니다. 머릿속에 "이렇게 핸들을 꺾으면 차가 저렇게 간다"는 감각(모델)이 생기면, 운전대를 잡지 않고도 상상으로 연습할 수 있습니다.

책 8.1절은 모델을 두 가지로 나눕니다.

• 분포 모델(distribution model): 가능한 모든 다음 상태 · 보상과 그 확률 $p(s', r\mid s,a)$ 를 알려 줌. 동적 계획법(가치 반복)이 쓰는 것.
• 표본 모델(sample model): 확률에 따라 다음 상태 · 보상 하나를 뽑아 줌. 시뮬레이터 · 게임 규칙 엔진 · 학습된 신경망 모델이 여기에 해당.

계획(planning) 은 모델로 만든 가상 경험으로 가치나 정책을 개선하는 것, 학습(learning) 은 실제 경험으로 개선하는 것입니다. 책은 두 가지가 같은 갱신 규칙(예: Q-러닝)을 경험의 출처만 바꿔 쓸 수 있다고 강조합니다.

장단점(Spinning Up 정리). 모델이 있으면 미리 생각해 볼 수 있어 표본 효율이 크게 좋아질 수 있습니다(AlphaZero가 대표적). 하지만 진짜 모델은 대개 주어지지 않아 경험에서 배워야 하고, 배운 모델의 오차를 에이전트가 악용하면 모델 속에서는 좋지만 실제로는 나쁜 정책이 나올 수 있습니다. 모델 없는 방법은 그 이득을 포기하는 대신 구현과 조정이 쉽습니다.

2. Dyna-Q: 실제 한 걸음, 상상 n 걸음

단계(책 8.2절 표 형식 Dyna-Q).

1. 현재 상태 $S$ 에서 ε-탐욕으로 $A$ 를 고르고 실제로 실행해 $R, S'$ 를 얻습니다.
2. 직접 학습: Q-러닝 갱신 $Q(S,A) \leftarrow Q(S,A)+\alpha[R+\gamma\max_a Q(S',a)-Q(S,A)]$.
3. 모델 학습: $\text{Model}(S,A) \leftarrow (R, S')$ (결정적 환경 가정 — 마지막으로 본 결과를 기억).
4. 계획: $n$ 번 반복 — 전에 겪은 $(S,A)$ 하나를 무작위로 골라 모델이 주는 $(R,S')$ 로 같은 Q-러닝 갱신을 합니다.

4단계를 빼면 그냥 한 걸음 Q-러닝입니다. 계획 단계는 이미 겪은 경험을 반복 재생하며 가치를 멀리까지 퍼뜨립니다.

책의 실험(예제 8.1 Dyna 미로). 상태 47개 미로, $\gamma=0.95$, $\alpha=0.1$, $\varepsilon=0.1$. 계획 없는 에이전트($n=0$)는 (ε-)최적 성능에 약 25판이 걸렸고, $n=5$ 는 약 5판, $n=50$ 은 3판 만에 도달했습니다.

직접 해 보기(이 페이지를 위해 실제로 돌린 결과). 앞 실습의 절벽 걷기 환경(step · eps_greedy)에 계획 단계만 붙였습니다($\alpha=0.5$, $\varepsilon=0.1$, $\gamma=1$, 씨앗 0~9).

123456789model = {}                                   # (s, a) -> (r, s2, done)
# ... 실제 한 걸음: a 선택 → s2, r, done = step(s, a) → Q-러닝 갱신 ...
model[(s, a)] = (r, s2, done)                # 3) 모델 학습
keys = list(model.keys())
for _ in range(n):                           # 4) 계획: 상상 경험 n 번
    ps, pa = keys[rng.integers(len(keys))]
    pr, ps2, pd = model[(ps, pa)]
    t = pr if pd else pr + gamma * Q[ps2].max()
    Q[ps][pa] += alpha * (t - Q[ps][pa])

실제 환경과의 상호작용이 약 8분의 1로 줄었습니다. 대신 계산(상상 갱신)은 늘었습니다. 실제 경험이 비싸고(로봇 · 실서비스) 계산이 싼 경우에 모델 기반이 빛나는 이유입니다.

모델이 틀리면(8.3절). 환경이 바뀌면 모델은 옛 세상을 기억합니다. 책의 Dyna-Q+ 는 마지막으로 실제로 시도한 지 $\tau$ 걸음이 지난 전이에 보너스를 얹어, 상상 경험의 보상을 $r+\kappa\sqrt{\tau}$ ($\kappa$ 는 작은 상수)로 계산합니다. 오래 확인 안 한 길을 다시 가 보게 만드는 '호기심'입니다.

3. 결정 시점 계획과 MCTS

Dyna는 배경에서 계속 가치를 다듬는 계획입니다. 반대로 결정 시점 계획(decision-time planning) 은 지금 상태에서 행동을 고르기 직전에 모델로 앞을 내다보고, 그 결과로 이번 행동만 고릅니다. 가장 단순한 형태가 롤아웃(각 행동 뒤를 간단한 정책으로 끝까지 여러 번 시뮬레이션해 평균 내기)이고, 그 발전형이 몬테카를로 트리 탐색(MCTS) 입니다.

책 8.11절은 MCTS가 2005년 약한 아마추어 수준이던 컴퓨터 바둑을 2015년 6단 이상으로 끌어올린 주역이라고 소개하며, 핵심 아이디어의 출처로 Coulom(2006)과 Kocsis · Szepesvári(2006)를 듭니다.

한 번의 반복 = 네 단계.

1. 선택(Selection): 뿌리(현재 상태)에서 출발해, 나무 안에서는 나무 정책(UCB 같은 규칙)으로 잎까지 내려갑니다.
2. 확장(Expansion): 잎에서 아직 안 해 본 행동으로 자식 마디를 하나 이상 붙입니다(반복에 따라 생략 가능).
3. 시뮬레이션(Simulation): 거기서부터 롤아웃 정책으로 한 판 끝까지 둬 봅니다.
4. 역전파(Backup): 얻은 반환으로 지나온 나무 안 마디들의 방문 수 · 평균 가치를 고칩니다(나무 밖 롤아웃 구간은 저장 안 함).

시간이 다 되면 뿌리에서 행동 하나를 고릅니다. 가치가 가장 큰 행동, 또는 튀는 값에 덜 흔들리도록 방문 수가 가장 많은 행동을 고릅니다.

1234567flowchart LR
  R[뿌리 = 현재 상태] --> S1[1 선택<br/>UCT/PUCT로 잎까지]
  S1 --> S2[2 확장<br/>새 자식 마디]
  S2 --> S3[3 시뮬레이션<br/>롤아웃 또는 가치망]
  S3 --> S4[4 역전파<br/>N · Q 갱신]
  S4 -->|시간 남음| S1
  S4 -->|시간 끝| A[방문 수 최대 행동 실행]

4. UCT와 PUCT 손계산

UCT(Upper Confidence bounds applied to Trees). Kocsis · Szepesvári(2006)는 각 마디의 행동 선택을 슬롯머신 문제로 보고 UCB1을 적용했습니다. 마디 $s$ 에서

$N(s)$ 는 마디의 총 방문 수, $N(s,a)$ 는 그 행동으로 내려간 횟수, $Q(s,a)$ 는 그 아래 시뮬레이션들의 평균 결과입니다.

숫자로 해 보기(해설용, $c=\sqrt2$). 뿌리에서 10번 시뮬레이션했고, 수 A는 6번(4승, $Q=0.667$), 수 B는 4번(2승, $Q=0.5$) 갔습니다. $\ln10\approx2.303$.

• A: $0.667+1.414\sqrt{2.303/6}=0.667+0.876=1.543$
• B: $0.5+1.414\sqrt{2.303/4}=0.5+1.073=1.573$ ← 선택

B로 내려가 시뮬레이션한 결과가 승리(+1)였다면, 역전파로 B는 $N=5$, 승 3, $Q=0.6$ 이 됩니다.

PUCT(AlphaGo Zero 계열). 신경망이 주는 사전 확률 $P(s,a)$ 로 탐험 보너스를 조절합니다(AlphaGo Zero 해설의 식).

숫자로 해 보기(해설용, $c_{\text{puct}}=1$). 같은 방문 기록에 정책망이 $P(A)=0.7$, $P(B)=0.3$ 을 줬다면 $\sqrt{10}\approx3.162$.

• A: $U=0.7\times3.162/7=0.316$ → $0.667+0.316=0.983$ ← 선택
• B: $U=0.3\times3.162/5=0.190$ → $0.5+0.190=0.690$

UCT에서는 B를 골랐지만, 정책망이 A를 유망하다고 보자 A를 더 깊이 봅니다. 학습된 직관(사전 확률)이 탐색을 이끄는 것이 AlphaGo 계열의 핵심입니다. 또 AlphaGo Zero 이후로는 끝까지 두는 롤아웃 대신 가치망의 평가로 3단계를 대신합니다.

5. 모델 기반 방법의 지도

Spinning Up은 모델 기반 방법을 모델을 어떻게 쓰느냐에 따라 나눕니다. 이 사이트의 논문 해설과 묶으면 다음과 같습니다.

여기에 두 갈래가 더 이어집니다.

• 규칙 없이 배운 모델로 트리 탐색: MuZero 는 진짜 화면을 재현하는 대신 보상 · 가치 · 정책 예측에 필요한 것만 담은 잠재 모델을 배워, 그 안에서 MCTS를 합니다.
• 잠재 공간 상상으로 정책 학습: Dreamer · DreamerV3 는 월드 모델의 잠재 공간에서 궤적을 상상하고, 그 위에서 액터-크리틱을 학습합니다.

왜 이렇게 갈라지나. 바둑 · 체스처럼 규칙(완벽한 모델)이 있으면 탐색에 집중하고, 로봇 · 비디오 게임처럼 모델을 배워야 하면 "모델 오차를 얼마나 믿을지"를 다루는 장치(짧은 구간만 계획, 잠재 공간, 재계획)가 핵심이 됩니다.

연습 문제

1. Dyna-Q에서 $n=0$ 이면 어떤 알고리즘이 되나요?
   • 풀이: 계획 단계가 없으므로 한 걸음 표 형식 Q-러닝 그대로입니다.
2. UCT 예에서 B가 패배(0)였다면 역전파 뒤 B의 $Q$ 는?
   • 풀이: $N=5$, 승 2 → $Q=2/5=0.4$ 입니다.
3. PUCT 예에서 $c_{\text{puct}}=3$ 이면 어느 수를 고르나요?
   • 풀이: $U_A=3\times0.316=0.949$ → $1.616$, $U_B=3\times0.190=0.569$ → $1.069$. 여전히 A입니다.
4. 표 Dyna-Q 실험에서 $n=50$ 이 실제 걸음을 크게 줄였는데, 대신 무엇이 늘었나요?
   • 풀이: 실제 걸음마다 상상 갱신을 50번씩 하므로 계산량이 늘었습니다.
5. 학습된 모델의 오차를 정책이 '악용'한다는 말은 무슨 뜻인가요?
   • 풀이: 모델이 실제보다 좋게 예측하는 엉뚱한 행동 경로를 정책이 찾아내, 모델 속에서는 점수가 높지만 실제 환경에서는 실패하는 현상입니다.

스스로 점검

1. Dyna의 계획과 MCTS의 계획은 무엇이 다른가요?
   • 답: Dyna는 배경에서 모델의 경험을 재생해 가치 함수 전체를 꾸준히 개선하고, MCTS는 행동하기 직전에 현재 상태에서만 앞을 탐색해 이번 행동을 고릅니다.
2. MCTS 마지막에 방문 수가 가장 많은 행동을 고르는 이유는?
   • 답: 평균 가치가 높아도 방문이 적으면 우연일 수 있는데, 방문 수가 많다는 것은 탐색 내내 꾸준히 좋아 보였다는 뜻이라 더 믿을 만하기 때문입니다.
3. PUCT에서 $P(s,a)$ 가 하는 역할은?
   • 답: 신경망이 유망하다고 보는 수에 탐험 보너스를 더 주어, 넓은 탐색 공간에서 제한된 시뮬레이션을 좋은 후보에 집중시킵니다.

용어 정리

더 깊이 보려면

• S&B 8.4절(우선순위 쓸기: 가치가 크게 바뀐 곳부터 계획), 8.10절(롤아웃), 16.6절(AlphaGo).
• Spinning Up 「Kinds of RL Algorithms」 — 모델 기반 갈래와 대표 논문 목록.
• 딥 강화학습으로 사람 수준의 제어 (DQN, Nature 판) — 경험 재생은 '모델 없는 Dyna'처럼 볼 수도 있습니다(옛 실제 경험을 재생).

다음에 볼 것

• 중간 점검: 강화학습 기초 15문제 — 지금까지의 강화학습 수업을 계산 문제로 점검합니다.
• 신경망과 트리 탐색으로 바둑 정복하기 (AlphaGo) — 오늘의 MCTS에 정책망 · 가치망을 결합한 원 논문.

라이선스

본문은 KAITABASE 자체 해설입니다. 참고한 Sutton · Barto 2판 PDF는 판권면에 CC BY-NC-ND 2.0, Spinning Up 저장소는 MIT 라이선스입니다. 책 실험 수치(예제 8.1)는 본문 서술을 요약했고, Dyna-Q 절벽 실험 · UCT · PUCT 숫자는 이 수업을 위해 만들어 python으로 돌리거나 검산한 해설용입니다.

출처

• Sutton · Barto, Reinforcement Learning: An Introduction 2판(2020 PDF) 8장: http://incompleteideas.net/book/RLbook2020.pdf
• OpenAI Spinning Up, Part 2: Kinds of RL Algorithms: https://spinningup.openai.com/en/latest/spinningup/rl_intro2.html
• Kocsis, Szepesvári (2006), Bandit based Monte-Carlo Planning, ECML (S&B 참고 문헌 기준)
• Silver 외 (2017), Mastering the game of Go without human knowledge — PUCT 식은 이 사이트의 AlphaGo Zero 해설 기준