[RL] Lecture 3: Planning by Dynamic Programming by David Silver

| Dynamic Programming이란?

• 복잡한 문제를 작은 서브문제(Subproblem)로 분해하여 해결

• DP는 다음 두 가지 속성이 있는 문제에 적용 가능:

  1. Optimal Substructure: 전체 최적해가 부분 최적해로 구성됨
  2. Overlapping Subproblems: 반복되는 부분 문제 존재

MDP는 위 두 조건을 만족 → DP 적용 가능!

---

| Policy Evaluation(정책 평가)

목표

주어진 정책 $\pi$에 대해 상태 가치 함수 $v^{\pi}(s)$를 계산

Bellman Expectation Equation

---

Iterative Policy Evaluation (순차 반복)

1. 초기 값 $v_0(s) = 0$
2. 다음 업데이트 반복:

3. $v_k \to v^{\pi}$ 로 수렴

예시: Gridworld의 무작위 정책 평가
$\pi(n) = \pi(e) = \pi(s) = \pi(w) = 0.25$

---

| Policy Iteration(정책 반복)

전체 구조

1. Policy Evaluation:
   $v^{\pi}$ 계산 (위에서 설명한 반복 방식)

2. Policy Improvement:
   다음 정책을 greedy하게 갱신:

반복 수행 시:
$\pi \to \pi' \to \pi'' \to \dots \to \pi^*$

→ 항상 수렴 보장

---

예시: Jack’s Car Rental

• 두 개의 렌터카 지점 (최대 20대 차량)
• 하루 최대 5대 이동 가능
• 렌트/반납 확률은 포아송 분포 사용
• 정책 반복 알고리즘으로 최적 정책 도출

---

| Value Iteration(가치 반복)

Bellman Optimality Equation

• 가치 함수만 업데이트 → 정책은 implicit하게 정의됨

정책 없이 최적 가치 함수 $v^*$만으로 반복
수렴 후 greedy 정책 추출

---

원리: Optimal Substructure

최적 정책은 항상 최적 첫 행동과 이후 최적 정책으로 분해 가능

---

| DP 알고리즘 요약

문제	벨만 방정식	알고리즘
예측 (prediction)	Bellman Expectation	Iterative Policy Evaluation
제어 (control)	Bellman Expectation	Policy Iteration
제어 (control)	Bellman Optimality	Value Iteration

• 복잡도:

  • 상태 수 $n$, 행동 수 $m$일 때
  • 상태 기반: $\mathcal{O}(mn^2)$
  • 행동 기반: $\mathcal{O}(m^2n^2)$

---

| Asynchronous DP(비동기 DP)

왜 필요한가?

• 동기 방식(synchronous)은 모든 상태를 매번 업데이트 → 비효율

비동기 방식 종류

기법	설명
In-place DP	하나의 value function만 사용
Prioritized Sweeping	Bellman error 기준으로 우선순위 업데이트
Real-Time DP	실제 경험을 기반으로 필요한 상태만 업데이트

---

| Approximate DP

함수 근사(Function Approximation)

상태 공간이 너무 커서 전체를 저장할 수 없을 때

• $\hat{v}(s; w)$: 파라미터 $w$를 가지는 근사 함수
• 반복적으로 Bellman Equation을 통해 target 계산 후
• 회귀 방식으로 업데이트

Target: ṽ_k(s) = max_a [R^a_s + γ ∑ P^a_ss′ v̂(s′, w_k)]
Update: train v̂(·, w_{k+1}) ← regression on (s, ṽ_k(s))

---

| 수렴 이론: Contraction Mapping

∞-Norm 사용

---

Bellman Operator는 γ-수축(Contraction)

• Expectation Operator $T^{\pi}$:

• Optimality Operator $T^*$:

→ 따라서:

항목	수렴 대상
Iterative Policy Evaluation	$v^{\pi}$
Policy Iteration	$v^*$
Value Iteration	$v^*$

---

| 정리

알고리즘	설명
Iterative Policy Evaluation	주어진 정책 평가
Policy Iteration	평가 + 개선 반복
Value Iteration	최적 가치만 업데이트
Async DP	상태 선택을 최적화
Approx. DP	함수 근사 기반