[RL] Lecture 8: Integrating Learning and Planning by David Silver

| 강의 목표

• 모델 기반 강화학습에서 모델을 학습하고 활용하는 방법 이해
• 학습(Learning)과 계획(Planning)을 통합하는 아키텍처 학습
• 샘플 기반 탐색(Simulation-Based Search)을 통한 효율적인 계획 수립

---

| Introduction – RL 세 접근 방식

구분	설명
Model-Free	모델 없이 경험으로 가치/정책 학습
Model-Based	모델을 학습하고 그 모델을 기반으로 계획 수립
Integrated	모델도 학습하고, 그로부터 샘플링해서 가치/정책도 학습 (Dyna 구조)

---

| Model-Based Reinforcement Learning

개념 요약

• 환경의 모델 $M = (P_\eta, R_\eta)$ 를 학습하여
  Value Function 또는 Policy를 Planning 기법으로 계산

---

모델 학습

• 입력: $(S_t, A_t)$

• 출력: $R_{t+1}, S_{t+1}$

• 방법:

  • $(s,a) \rightarrow r$: 회귀 문제
  • $(s,a) \rightarrow s'$: 밀도 추정 (Density Estimation)

모델 예시

모델 종류	설명
Table Lookup	경험을 기반으로 표 생성
Linear/Gaussian	상태-행동을 선형/정규 분포로 근사
Deep Models	딥러닝 기반의 모델 (ex. Deep Belief Network)

예시: AB 문제

• 실제 경험: A → 0 → B → 0, B → 1, B → 1, ...
• 모델을 테이블 형태로 구축한 후, 이를 기반으로 샘플링하여 계획 수행

샘플 기반 계획

• 모델을 이용해 가짜 샘플 생성 (Sample-based Planning)
• 예: Sarsa, MC Control, Q-learning을 샘플에 적용
  → 기존 모델 기반 DP보다 훨씬 효율적

---

| 통합 구조: Dyna

Dyna 구조 요약

종류	설명
Model-Free	실제 경험만 학습
Model-Based	실제 경험으로 모델을 학습 → 모델을 사용해 계획
Dyna	실제 경험으로 모델 + 가치 함수 동시 학습 + 시뮬레이션도 사용

Dyna Architecture

• 실제 경험으로 모델 학습
• 모델로부터 시뮬레이션된 경험 생성
• 시뮬레이션된 경험으로 가치 함수/정책 업데이트

Dyna-Q 알고리즘

For each real step:
  - Update Q with real experience
  - Update model with real experience
  - Repeat K times:
      - Sample (s, a) from past
      - Simulate r, s' using model
      - Update Q with (s, a, r, s')

실험: Simple Maze

• Dyna-Q는 모델을 통해 빠르게 가치 함수 학습
• 모델이 부정확할 경우 성능 저하
  → 환경 변화에 민감

---

| Simulation-Based Search (샘플 기반 탐색)

Forward Search

• 현재 상태 $s_t$에서 출발해 탐색 트리 구성
• 전체 MDP가 아닌 현 상태에서 시작되는 부분 MDP만 고려

Monte Carlo Search

• 현재 상태에서 각 행동 $a$에 대해 K개의 시뮬레이션

For each a ∈ A:
  - Run K simulations: (s_t, a, r, s', ...)
  - Evaluate Q(s_t, a) = mean(G)
Choose a with highest Q

Monte Carlo Tree Search (MCTS)

• 시뮬레이션을 통해 트리 구성

• In-tree vs. Out-of-tree 구분:

  • In-tree: 트리 정책으로 행동 선택 (greedy)
  • Out-of-tree: 기본 정책 (ex: 랜덤)

MCTS 핵심 구성 요소

구성	설명
Search Tree	시뮬레이션으로 생성된 트리
Evaluation	Q(s,a)는 방문한 에피소드 평균 Return
Tree Policy	탐색에 사용되는 정책 (ε-greedy 등)
Default Policy	시뮬레이션에 사용되는 정책 (랜덤 등)

Case Study: 바둑 (Go)

• 전통적인 DP/Minimax 탐색이 실패한 환경
• MCTS 기반 AI들이 강력한 성능을 보임

MCTS 장점

• 고차원, 복잡 환경에서도 작동
• 샘플링 기반 → 차원의 저주 회피
• black-box 모델에도 적용 가능
• Anytime, 병렬화 가능

---

| TD Search

MC 대신 TD 학습을 시뮬레이션에 적용

• 매 시뮬레이션 step에서 Sarsa 방식으로 업데이트:

Q(s, a) ← Q(s, a) + α [r + γ Q(s', a') - Q(s, a)]

• 부트스트래핑 덕분에 MC보다 효율적

Dyna-2 구조

기억 종류	설명
Long-Term Memory	실제 경험 기반 TD 학습
Short-Term Memory	시뮬레이션 경험 기반 TD Search
전체 가치 함수	LTM + STM의 합으로 구성

---

| 정리

주제	설명
모델 기반 학습	MDP 모델 $P, R$ 을 학습 후 계획 수행
샘플 기반 계획	모델로부터 샘플 생성 후 RL 알고리즘 적용
Dyna	모델 학습 + 샘플 생성 + 가치 함수 업데이트 통합
MCTS	시뮬레이션 기반 탐색, 고차원 환경에 적합
TD Search	부트스트래핑 기반 효율적인 탐색 및 학습
Dyna-2	LTM + STM 통합으로 지역/전역 정보 활용