[2025 강화학습 Recap] Chapter 4. Model-Free Prediction

AI/Reinforcement Learning 2025. 8. 10. 10:50

728x90

[2025 강화학습 Recap] Chapter 4. Model-Free Prediction

Chapter 3에서 Dynamic Programming의 우아한 이론을 배웠지만, 현실 세계로 나오면 벽에 부딪힘. 자율주행차가 "비 올 때 브레이크 밟으면 미끄러질 확률이 정확히 0.23"이라고 미리 알 수 있을까? 게임 AI가 상대방의 모든 전략과 확률을 사전에 계산할 수 있을까?
대부분의 실제 문제에서는 환경의 완벽한 모델을 알 수 없음. 전이확률 P(s'|s,a)도, 보상함수 R(s,a)도 모르는 상황에서 어떻게 학습할 수 있을까?
답은 간단함. "모르면 직접 해보자." 모델을 추측하는 대신 환경과 실제로 상호작용하면서 경험을 쌓고, 그 경험으로부터 가치함수를 추정하는 것. 이것이 바로 Model-free 강화학습의 핵심 아이디어임.
이 장에서는 주어진 정책을 평가하는 문제(Prediction)를 Model-free 방식으로 해결하는 두 가지 근본적 접근법을 다룸. Monte Carlo 방법은 완전한 에피소드 경험을 활용하고, Temporal Difference 방법은 한 스텝씩 점진적으로 학습함. 각각의 장단점과 언제 어떤 방법을 써야 하는지도 알아볼 예정임.
이론에서 실제로, 계획에서 학습으로 넘어가는 중요한 전환점임. 불완전한 정보로도 똑똑하게 학습하는 방법을 찾아보자.

1. Chapter 3에서 Chapter 4로: 이상에서 현실로

1.1 Dynamic Programming의 성과와 한계

Chapter 3에서 달성한 것: ✅ 완벽한 모델(P, R)이 있을 때 최적 해법 ✅ 벨만 방정식을 실제 알고리즘으로 구현 ✅ Prediction과 Control 문제의 체계적 해결

하지만 현실적 한계들: ❌ 완벽한 모델 필요: 실제로는 전이확률 P(s'|s,a)와 보상함수 R(s,a)를 모름 ❌ 상호작용 없음: 환경과 직접 경험하지 않고 모델로만 계산 ❌ 사전 지식 의존: 환경에 대한 완벽한 사전 지식 필요

1.2 현실 세계의 문제들

실제 상황들:

자율주행: "비 올 때 브레이크 밟으면 미끄러질 확률"을 정확히 아는가?
게임 AI: 상대방의 모든 전략과 확률을 미리 알 수 있는가?
로봇 제어: 모터의 정확한 응답 특성을 완벽히 모델링할 수 있는가?

→ 대부분의 실제 문제에서는 모델을 모르거나 불완전함!

1.3 Model-Free RL의 등장 배경

핵심 아이디어: "모델을 모르니까 직접 경험해서 배우자!"

Model-Free 접근법:

환경과 상호작용: 실제로 행동하고 결과를 관찰
경험으로 학습: 관찰된 데이터로 가치함수/정책 개선
점진적 개선: 더 많은 경험으로 점점 더 나은 성능

2. Model-Free vs Model-Based 비교

2.1 근본적 차이점

특성Model-Based (DP)Model-Free환경 지식완벽한 모델 필요모델 불필요학습 방식계산 (Planning)경험 (Learning)상호작용없음필수데이터사전 지식샘플링된 경험업데이트정확한 기댓값샘플 기반 추정

2.2 벨만 방정식의 변화

Model-Based (DP):

v(s) = Σ π(a|s) Σ P(s'|s,a) [R(s,a) + γv(s')]
       전체 합계 (정확한 기댓값)

Model-Free:

v(s) ← 샘플된 경험으로 추정
      (불완전하지만 실제 경험 기반)

2.3 두 가지 접근법

Model-Free에서 벨만 방정식을 근사하는 두 가지 방법:

Monte Carlo: 전체 에피소드 경험으로 실제 Return 계산
Temporal Difference: 부분 경험 + 추정값으로 즉시 업데이트

3. Prediction 문제: 정책 평가하기

3.1 문제 정의

목표: 주어진 정책 π에 대해 vπ(s)를 모든 상태에서 구하기 제약: 환경 모델(P, R)을 모르는 상황

DP와의 차이:

DP: 정확한 벨만 방정식으로 계산
Model-Free: 샘플링된 경험으로 추정

3.2 핵심 아이디어

경험적 평균으로 기댓값 근사:

E[X] ≈ (x1 + x2 + ... + xn) / n

강화학습에 적용:

vπ(s) = E[Gt | St = s] ≈ 상태 s에서 관찰된 Return들의 평균

4. Monte Carlo 방법

4.1 Monte Carlo란?

정의: 무작위 샘플링을 통해 수치적 결과를 얻는 방법

강화학습에서 Monte Carlo: "정책을 따라 실제로 여러 에피소드를 실행해보고, 각 상태에서 받은 Return들의 평균을 구하자"

4.2 Monte Carlo Prediction 알고리즘

기본 아이디어:

정책 π를 따라 완전한 에피소드 실행
각 상태에서 받은 실제 Return 계산: Gt = Rt+1 + γRt+2 + γ²Rt+3 + ...
해당 상태의 가치 추정값을 Return으로 업데이트

수식:

V(St) ← V(St) + α[Gt - V(St)]

4.3 First-Visit vs Every-Visit MC

First-Visit Monte Carlo

규칙: 한 에피소드에서 상태를 처음 방문했을 때만 Return 기록
장점: 이론적으로 깔끔함, 수렴 보장
사용: 대부분의 이론적 분석

Every-Visit Monte Carlo

규칙: 상태를 방문할 때마다 Return 기록
장점: 더 많은 데이터 활용, 실제로 더 빠른 수렴
사용: 실제 구현에서 선호

예시:

에피소드: S1 → S2 → S1 → S3 (terminal)
First-Visit: S1의 첫 방문(step 1)만 기록
Every-Visit: S1의 두 방문(step 1, 3) 모두 기록

4.4 Incremental Mean 업데이트

문제: 모든 Return을 저장하고 평균 계산하면 메모리/계산 비효율

해결: 점진적 평균 업데이트

평균 ← 이전평균 + 학습률 × (새값 - 이전평균)
V(s) ← V(s) + α[Gt - V(s)]

학습률 α의 역할:

α = 1/N(s): 완전한 평균 (stationary)
α = 상수: 최근 경험에 더 가중치 (non-stationary)

4.5 Monte Carlo의 특징

장점: ✅ Unbiased: 편향 없음 (실제 Return 사용) ✅ Model-free: 환경 모델 불필요 ✅ Simple: 개념과 구현이 단순 ✅ Convergence: 수렴 보장 (큰 수의 법칙)

단점: ❌ High Variance: 에피소드마다 큰 변동 ❌ Episodic only: 종료되는 태스크에만 적용 ❌ Slow: 에피소드 끝까지 기다려야 학습 ❌ Memory: 긴 에피소드는 메모리 소모

4.6 Monte Carlo 예시: GridWorld

정책: 목표까지 랜덤 이동
에피소드 1: S1 → S2 → S3 → Goal, Return = 10
에피소드 2: S1 → S4 → S2 → Goal, Return = 8  
에피소드 3: S1 → S1 → S3 → Goal, Return = 7

V(S1) = (10 + 8 + 7) / 3 = 8.33
V(S2) = (8 + 6) / 2 = 7 (두 번째, 세 번째 에피소드)
V(S3) = (6 + 5) / 2 = 5.5 (첫 번째, 세 번째 에피소드)

5. Temporal Difference (TD) 방법

5.1 TD의 핵심 아이디어

Monte Carlo의 한계: 에피소드가 끝날 때까지 기다려야 함

TD의 해법: "한 스텝만 가보고 나머지는 현재 추정값 사용"

핵심 통찰:

실제 Return: Gt = Rt+1 + γRt+2 + γRt+3 + ...
TD 추정: Rt+1 + γV(St+1)

5.2 TD(0) 알고리즘

가장 간단한 TD 방법: 한 스텝만 실제 경험, 나머지는 추정

업데이트 규칙:

V(St) ← V(St) + α[Rt+1 + γV(St+1) - V(St)]

구성요소:

TD Target: Rt+1 + γV(St+1)
TD Error: Rt+1 + γV(St+1) - V(St)
학습률: α

5.3 TD Target과 TD Error

TD Target (r + γV(St+1))

즉시 보상: Rt+1 (실제 관찰)
미래 가치: γV(St+1) (현재 추정값)
의미: "한 스텝 후 상태의 추정 가치"

TD Error (δt)

δt = Rt+1 + γV(St+1) - V(St)

양수: 현재 추정이 너무 낮음 → 가치 증가
음수: 현재 추정이 너무 높음 → 가치 감소
영역: 추정이 정확함

5.4 TD의 특징

장점: ✅ Online: 매 스텝마다 즉시 학습 ✅ Low Variance: Monte Carlo보다 안정적 ✅ Continuing: 무한히 계속되는 태스크에도 적용 ✅ Efficient: 빠른 학습 속도

단점: ❌ Biased: 추정값 사용으로 편향 발생 ❌ Initial Value Sensitive: 초기값에 민감 ❌ Convergence: 수렴 보장이 약함 (조건부)

5.5 Bootstrapping의 개념

정의: 추정값으로 추정값을 업데이트하는 것

TD에서 Bootstrapping:

V(St) ← ... + γV(St+1)
     현재 추정   미래 추정값 사용

DP vs TD Bootstrapping:

DP: 정확한 벨만 방정식으로 부트스트래핑
TD: 샘플 기반 부트스트래핑

5.6 TD 예시: GridWorld

현재 상태: S1, V(S1) = 5
행동 후: S2로 이동, 보상 = -1, V(S2) = 3, γ = 0.9

TD Target = -1 + 0.9 × 3 = 1.7
TD Error = 1.7 - 5 = -3.3
V(S1) ← 5 + 0.1 × (-3.3) = 4.67

6. Monte Carlo vs Temporal Difference

6.1 비교 요약표

특성Monte CarloTemporal Difference데이터 요구완전한 에피소드한 스텝 전이학습 속도느림빠름Bias없음 (Unbiased)있음 (Biased)Variance높음낮음수렴성보장됨조건부초기값 민감도낮음높음적용 범위Episodic만모든 태스크

6.2 Bias vs Variance Trade-off

Monte Carlo:

Unbiased: 실제 Return을 사용하므로 편향 없음
High Variance: 에피소드마다 큰 변동성

Temporal Difference:

Biased: 추정값(V(St+1))을 사용하므로 편향 있음
Low Variance: 한 스텝만 실제 경험하므로 변동성 적음

6.3 시각적 이해: Bias vs Variance

Target (참값): ●

Monte Carlo: 편향 없지만 퍼져있음
  ○ ○     ○
    ○ ● ○
  ○     ○ ○

TD: 편향 있지만 모여있음  
      ◇◇◇
      ◇◇◇  ● 
      ◇◇◇

6.4 언제 무엇을 사용할까?

Monte Carlo 선호 상황:

에피소드가 짧을 때
정확한 추정이 중요할 때
Non-Markov 환경
충분한 데이터가 있을 때

TD 선호 상황:

실시간 학습이 필요할 때
에피소드가 길거나 무한할 때
빠른 초기 개선이 중요할 때
제한된 데이터 상황

6.5 Markov Property와의 관계

TD: Markov 환경에 최적화

현재 상태만으로 미래 예측 가능
부트스트래핑이 효과적

Monte Carlo: Non-Markov 환경에도 robust

전체 궤적 정보 활용
Markov 가정에 덜 의존

7. 세 방법의 통합적 이해

7.1 Sampling vs Bootstrapping

두 가지 핵심 아이디어:

Sampling

정의: 모든 가능성을 계산하지 않고 실제 경험만 사용
장점: 모델 불필요, 실제 환경 적용 가능
단점: 노이즈, 변동성

Bootstrapping

정의: 추정값으로 추정값을 업데이트
장점: 빠른 학습, 적은 데이터 필요
단점: 편향, 초기값 의존성

7.2 세 방법의 특성 매트릭스

방법SamplingBootstrapping특징DP❌✅정확하지만 모델 필요MC✅❌정확하지만 느림TD✅✅빠르지만 편향

7.3 실제 성능 비교

학습 곡선 특성:

성능
 ↑
 │    TD: 빠른 초기 개선, 조기 수렴
 │   ╱╱╱╱╱╱╱━━━━━━
 │  ╱
 │ ╱     MC: 느린 개선, 높은 최종 성능  
 │╱      ╱╱╱╱╱╱╱╱╱╱╱╱╱
 └────────────────────────→ 시간

7.4 하이브리드 접근법들

λ-Return: MC와 TD의 조합

Gλt = (1-λ)∑λⁿ⁻¹G(n)t

Experience Replay: 과거 경험을 반복 학습 Eligibility Traces: 여러 스텝의 정보 조합

8. 실제 구현 고려사항

8.1 학습률 (Learning Rate) 선택

이론적 조건 (수렴 보장):

∑α = ∞, ∑α² < ∞
예: α = 1/N(s) 또는 α = 1/t

실제 사용:

상수 학습률: α = 0.01~0.1 (non-stationary 환경)
감소 학습률: α = 1/N(s) (stationary 환경)

8.2 초기값 설정

Monte Carlo: 초기값 영향 적음 TD: 초기값이 학습에 큰 영향

초기값 전략:

Optimistic: 높은 초기값으로 탐험 유도
Realistic: 도메인 지식 기반 설정
Zero: 간단하지만 편향 가능

8.3 탐험 vs 활용 (Exploration vs Exploitation)

문제: 정책 평가 중에도 탐험 필요

해결법:

ε-greedy: 확률적 탐험
Soft policies: 모든 행동에 양수 확률
Importance sampling: 다른 정책으로 수집한 데이터 활용

9. Chapter 4 정리 및 다음 단계

9.1 Model-Free RL이 해결한 것

✅ 모델 독립성: 환경 모델 없이도 학습 가능 ✅ 실제 적용성: 현실 환경에서 사용 가능 ✅ 온라인 학습: 상호작용하면서 실시간 개선 ✅ 경험 기반: 실제 데이터로 점진적 개선

9.2 남은 문제들

❌ Prediction만 해결: Control 문제 (최적 정책 찾기) 미해결 ❌ 정책이 주어진 경우만: 어떻게 정책을 개선할 것인가? ❌ 탐험 문제: 어떻게 효과적으로 탐험할 것인가?

9.3 다음 단계: Model-Free Control (Chapter 5)

해결하고 싶은 문제들:

"정책을 어떻게 개선할까?" → Q-Learning, SARSA
"탐험을 어떻게 할까?" → ε-greedy, UCB
"On-policy vs Off-policy?" → 데이터 효율성

활용할 핵심 아이디어들:

GPI (Generalized Policy Iteration): Chapter 3에서 배운 평가↔개선 반복
MC/TD Prediction: Chapter 4에서 배운 가치 추정 방법
Action-Value Function: 정책 개선을 위한 Q(s,a) 활용

9.4 핵심 메시지

Model-Free Prediction은 실제 강화학습의 첫 걸음:

환경 모델 없이도 가치를 추정할 수 있음을 보여줌
MC와 TD라는 두 가지 근본적 접근법 제시
Bias-Variance trade-off라는 중요한 개념 도입

"이제 가치를 추정할 수 있으니, 이를 바탕으로 정책을 어떻게 개선할까?"

이 장에서 우리는 강화학습의 실용성을 크게 한 걸음 전진시켰음. 환경의 완벽한 모델 없이도 실제 경험만으로 가치함수를 추정할 수 있다는 것을 보여줬음. Monte Carlo는 편향 없는 정확한 추정을, Temporal Difference는 빠르고 효율적인 학습을 제공함.

하지만 여전히 한 가지 큰 문제가 남아있음. 지금까지는 정책이 주어진 상황에서 그 정책을 평가하는 방법만 배웠음. "이 정책을 따르면 얼마나 좋을까?"라는 질문에는 답할 수 있지만, "어떤 정책이 가장 좋을까?"라는 더 중요한 질문은 아직 해결하지 못했음.

다음 장에서는 이 마지막 퍼즐 조각을 맞춰볼 예정임. Model-free 환경에서 어떻게 정책을 개선하고 최적 정책을 찾을 수 있는지 알아보자. MC와 TD에서 배운 가치 추정 방법들이 이제 정책 개선의 도구로 변신하게 됨.

Generalized Policy Iteration의 구조(평가 ↔ 개선)는 그대로 유지되지만, 이제 모든 것이 실제 경험 기반으로 바뀜. Q-Learning과 SARSA 같은 강력한 알고리즘들이 등장하면서, 강화학습은 비로소 실용적인 문제 해결 도구로 완성될 것임.

가치를 추정하는 방법을 배웠으니, 이제 그 가치를 바탕으로 더 나은 행동을 선택하는 방법을 찾아보자