[RL] Lecture 6: Value Function Approximation by David Silver

| 강의 목표

• 상태 공간이 너무 크거나 연속적일 때 전통적인 테이블 방식은 불가능
• 이 한계를 극복하기 위해, 함수 근사(Function Approximation) 를 사용해
  가치 함수나 Q함수를 일반화하는 방법을 학습한다

---

| 함수 근사가 필요한 이유

문제: 거대한 상태 공간

• 백개먼(Backgammon): $10^{20}$ 상태
• 바둑: $10^{170}$ 상태
• 헬리콥터 제어: 연속적인 상태 공간

→ 테이블 방식으로는 학습 불가

---

| 가치 함수 근사의 기본 구조

목표:

• $w$: 학습 가능한 파라미터 벡터
• 관찰된 상태에서 일반화하여 보지 못한 상태까지 예측 가능

---

사용 가능한 함수 근사 모델들:

• 선형 조합 (Linear)
• 신경망 (Neural Networks)
• 의사결정트리 (Decision Trees)
• 최근접 이웃 (kNN)
• Fourier/Wavelet basis 등

이 강의에서는 선형 근사(linear approximation) 중심

---

| 점진적 학습 (Incremental Methods)

3-1. 선형 근사 구조

• 상태를 특징 벡터로 표현: $x(s)$
• 근사 함수:

3-2. 오차 최소화: Gradient Descent

오차 함수:

Stochastic Gradient Descent:

MC, TD(0), TD(λ)의 학습법

방법	Target	Update
MC	$G_t$	$\Delta w = \alpha(G_t - \hat{v}(s;w))x(s)$
TD(0)	$R + \gamma \hat{v}(s';w)$	$\Delta w = \alpha \delta x(s)$
TD(λ)	$G^\lambda_t$	$\Delta w = \alpha \delta_t E_t$

• Eligibility trace: $E_t = \gamma \lambda E_{t-1} + x(s_t)$

---

| 제어(Control)에서의 근사

• $\hat{q}(s,a; w) \approx q^\pi(s,a)$

Q-learning/Sarsa with Function Approximation:

• 선형 구조:

• TD(0) 예:

---

Mountain Car 예제

• Linear Sarsa with:

  • Coarse coding
  • Radial basis functions

• $\lambda$에 따른 학습 효과 비교 가능

---

수렴 실패: Baird’s Counterexample

• Off-policy TD(0), TD(λ)는 수렴하지 않음
• 원인: TD는 어떤 목적 함수의 gradient가 아님

---

해결: Gradient TD

• TD의 수렴 문제 해결
• Projected Bellman Error의 진짜 경사(gradient)를 따름
• 수렴 조건 비교:

알고리즘	Table	Linear	Non-linear
MC	✅	✅	✅
TD	✅	✅	❌
Gradient TD	✅	✅	✅

---

| 배치 학습 (Batch Methods)

경험 반복 (Experience Replay)

• 예: DQN

  • 경험 $(s,a,r,s')$ 저장
  • 미니배치 샘플링
  • Q-learning 타깃 계산
  • SGD 업데이트

DQN의 핵심 요소: Replay Buffer + Fixed Q-target

Least-Squares Prediction

• 주어진 경험 집합 $D = \{(s_1, v_1), ..., (s_T, v_T)\}$

LSMC (Least Squares Monte Carlo)

LSTD (TD 타깃 사용):

경험 수에 비해 feature 수가 작을 때 유리

---

| Least Squares Control: LSPI

LSPI: Least Squares Policy Iteration

1. 경험 $D = \{(s,a,r,s')\}$ 수집
2. 정책 평가: LSTDQ
3. 정책 개선: greedy w.r.t. Q
4. 반복

핵심 업데이트:

---

Chain Walk 예시

• 50개의 상태, 2개의 행동(L/R)
• 보상은 상태 10과 41에서만 +1
• LSPI는 약 4~5 반복 후 수렴
• 각 행동마다 개별 basis function 사용

---

| 정리

영역	기법	수렴성
예측	TD, MC, TD(λ), Gradient TD	MC는 모두 수렴, TD는 제한적
제어	Sarsa, Q-Learning, LSPI	LSPI는 안정적, 일반 Q는 수렴 보장 없음
근사 방식	선형, 신경망	선형은 이론적으로 안전, NN은 불안정