[RL] Lecture 4: Model-Free Prediction by David Silver

| 강의 목표

• MDP의 전이 확률과 보상을 모르는 상황에서
  정책 π에 따른 가치 함수 vπ(s) 를 추정하는 방법을 배운다.

• 대표적인 두 가지 학습 방식 비교:

  1. Monte-Carlo (MC)
  2. Temporal-Difference (TD)

• 그리고 이를 일반화한 TD(λ) 학습

---

| 1. Model-Free Reinforcement Learning

구분	설명
Last Lecture	MDP가 알려진 상태에서 planning (DP)
This Lecture	MDP를 모르는 상태에서 prediction
Next Lecture	MDP를 모르는 상태에서 control

---

| 2. Monte-Carlo Learning

개념 요약

• 환경에 대한 모델이 필요 없음 (model-free)
• 한 에피소드가 완전히 종료된 뒤 누적 보상을 통해 가치 추정
• 부트스트래핑 없음: 추정된 가치가 다른 가치에 의존하지 않음
• 단점: 에피소드가 반드시 종료되어야 학습 가능

---

Monte-Carlo Policy Evaluation

• 목표: 정책 π에 따라 상태 s의 가치 함수 $v^{\pi}(s)$ 추정
• 방법: 여러 에피소드에서 $s$를 방문했을 때의 평균 return 계산

---

두 가지 평가 방법

First-Visit MC

• 한 에피소드 내에서 처음 방문한 시점의 Gt만 고려

Every-Visit MC

• 한 에피소드 내에서 방문한 모든 시점의 Gt를 평균

V(s) ← S(s)/N(s)

---

블랙잭 예시

• 상태: (현재 합계, 딜러의 카드, usable ace 여부)
• 행동: stick(멈춤), twist(카드 더 받기)
• 리워드: 승(1), 무(0), 패(-1)

→ MC로 학습한 가치 함수 시각화 가능

---

Incremental MC

• 점진적 평균 계산:

• 또는 고정 학습률 α 사용:

---

| 3. Temporal-Difference (TD) Learning

개념 요약

• MC와 달리 에피소드 종료 전에도 학습 가능
• 부트스트래핑 사용 → 추정된 가치에 의존

---

TD(0) 업데이트 식

• TD Target: $R_{t+1} + \gamma V(S_{t+1})$
• TD Error: $\delta_t = \text{Target} - \text{Prediction}$

---

Driving Home 예시

• 각 시점마다 남은 예상 시간이 갱신됨
• TD는 한 단계 이후의 값을 바로 반영하며 지속적으로 업데이트 가능
• MC는 도착 후만 업데이트 가능 → 느림

---

MC vs. TD 비교

항목	MC	TD
부트스트랩	❌	✅
학습 시점	에피소드 종료 후	매 단계마다
요구 조건	완전한 에피소드	중간 학습 가능
환경	종결 환경	지속 환경 가능
편향	없음	있음
분산	큼	작음

---

| 4. Batch MC vs. Batch TD

실험: AB 예시

• 에피소드: A → 0 → B → 0 / B → 1 / B → 0 ...
• MC: 평균 보상 그대로 → $V(A) = 0$
• TD: 추정 모델 기반 → $V(A) ≈ 0.75$

TD는 MDP를 근사해 학습
MC는 데이터에 직접 맞춤

---

| 5. Unified View of RL Backup

MC Backup

TD(0) Backup

DP Backup

방법	샘플링	부트스트랩
MC	✅	❌
TD	✅	✅
DP	❌	✅

---

| 6. TD(λ): MC와 TD의 연결

n-Step Return

• 다양한 n에 대해 TD target 정의:

• MC: $n \to \infty$
• TD: $n = 1$

---

λ-Return (Forward View)

• 여러 n-step return을 평균화:

• λ ∈ [0, 1] 조절 가능

---

Backward View: Eligibility Traces

• 모든 상태에 대해 자격 추적 (eligibility trace) 유지:

• 업데이트:

---

Forward vs. Backward TD(λ) 비교

λ 값	의미	Forward	Backward
0	TD(0)	=	=
1	MC	=	=
(0,1)	일반 TD(λ)	≠ (온라인)	≠ (온라인)

오프라인에서는 이론적으로 동일
온라인에서는 Sutton(2014)의 Exact TD(λ)로 완전 일치 가능

---

| 정리

개념	특징
Monte Carlo	샘플 기반, 부트스트랩 없음, 에피소드 필수
TD(0)	1단계 부트스트랩, 즉시 업데이트 가능
TD(λ)	다양한 n-step 정보를 융합
Eligibility Trace	최근 방문한 상태에 더 큰 책임 부여