[강화학습-4]정적 계획법 (Dynamic Programming)

4. 정적 계획법 (Dynamic Programming)

“모든 것이 알려진(모형이 완전한) MDP라면, 최적 정책은 순환 방정식을 반복적으로 푸는 것만으로 얻을 수 있다.”
이 반복적 과정이 바로 정적 계획법(DP)이며, 두 핵심 루틴—정책 평가와 정책 개선—이 맞물려 돌아갑니다.

---

4-1. 사전 지식 요약

필수 요소	간단 메모	앞서 다룬 섹션
MDP 구조	$\langle\mathcal{S},\mathcal{A},P,R,\gamma\rangle$	2-1
벨만 기대 방정식	$V_\pi, Q_\pi$ 재귀식	3-3
수축 사상 & 고정점	$\gamma<1$ ⇒ 반복 수렴	수학 배경

---

4-2. 정책 평가 (Policy Evaluation)

주어진 정책 $\pi$에 대해 정확한 가치 $V_\pi$를 찾는 단계.

벨만 기대식의 반복 (Iterative Policy Evaluation)

• 초깃값: $V_0(s)=0$ 또는 임의
• 반복: $$V_{k+1}(s)=\sum_a\pi(a\mid s)\sum_{s',r}P(s',r\mid s,a)\,[\,r+\gamma V_k(s')\,]$$
• 종료: $\max_s|V_{k+1}(s)-V_k(s)|<\theta$

def policy_evaluation(pi, states, actions, P, R, gamma=0.9, theta=1e-6):
    V = {s: 0.0 for s in states}
    while True:
        delta = 0.0
        for s in states:
            v_old = V[s]
            V[s] = sum(
                pi[s][a] * sum(
                    P[s][a][s_next] * (R[s][a][s_next] + gamma * V[s_next])
                    for s_next in states
                )
                for a in actions
            )
            delta = max(delta, abs(v_old - V[s]))
        if delta < theta:
            break
    return V

왜 근사 반복? – 상태 공간이 작으면 선형 방정식 $V = \mathcal{T}_\pi V$ 를 직접 풀 수도 있지만, DP에서는 반복이 더 직관적·확장성이 좋습니다.

---

4-3. 정책 개선 (Policy Improvement)

평가 단계로 얻은 $V_\pi$를 사용해 더 나은 정책 $\pi'$을 구성.

$$\pi'(s)=\underset{a}{\arg\max}\;\sum_{s',r}P(s',r\mid s,a)\,[\,r+\gamma V_\pi(s')\,]$$

• 즉, 행동 가치를 한 번 계산하여 가장 큰 $a$를 택함.
• 정책 개선 정리 : $\pi'$이 $\pi$보다 나쁠 일은 없으며, 최소 한 상태에서 더 좋으면 $\pi' \succ \pi$.

def greedy_policy_from_v(states, actions, P, R, V, gamma=0.9):
    pi_new = {s: {a: 0.0 for a in actions} for s in states}
    for s in states:
        # Q값 계산
        q_values = [
            sum(P[s][a][s_next] * (R[s][a][s_next] + gamma * V[s_next])
                for s_next in states)
            for a in actions
        ]
        best = np.argmax(q_values)
        pi_new[s][actions[best]] = 1.0
    return pi_new

---

4-4. 정책 반복 (Policy Iteration, PI)

1. 정책 평가 – $V_\pi$ 계산 (완전 수렴 or 몇 회만).
2. 정책 개선 – $\pi \leftarrow \text{greedy}(V_\pi)$.
3. 정책이 바뀌지 않을 때까지 반복 → $\pi^\*$.

어김없이 $\pi_{k+1} \succeq \pi_k$ 이므로 유한 MDP에선 유한 단계 수렴.

---

4-5. 가치 반복 (Value Iteration, VI)

PI의 두 단계를 한 식으로 합친 방법:

$$V_{k+1}(s)=\max_{a}\sum_{s',r}P(s',r\mid s,a)\,[\,r+\gamma V_k(s')\,]$$

• 한 번의 업데이트에 최적 행동을 바로 사용 → 평가·개선 합본.
• 수렴 후, $$\pi^\*(s)=\arg\max_{a}\sum_{s',r}P(s',r\mid s,a)\,[\,r+\gamma V_\*(s')\,]$$

---

4-6. PI vs VI – 비교

측면	정책 반복 (PI)	가치 반복 (VI)
1회 비용	평가(선형 해 or 반복) + 개선	$|\mathcal{A}|$ 기대값 계산
수렴 속도	평가를 완전 수렴시키면 빠름	작은 스텝이지만 빈번한 개선
메모리	$V(s)$ + $\pi(s)$	$V(s)$ 만
하이브리드	“Modified PI” – 평가를 $k$회만 수행하고 개선 반복

---

4-7. Gridworld 예제 구현

환경 정의

S  B  -  +1
-  B  -  -1
-  -  -   -

• S: 시작, B: 벽(진입 불가), +1/-1: 터미널
• 보상: 이동 −0.04, 터미널에서 종료
• 행동: {상, 하, 좌, 우} – 80% 제시 방향, 10%·10% 좌/우 편차 (stochastic)

파이썬 코드 (Value Iteration 30× 반복)

import numpy as np

grid = np.array([
    ['S','B','-','+'],
    ['-','B','-','-'],
    ['-','-','-','-']
])
rows, cols = grid.shape
states = [(r,c) for r in range(rows) for c in range(cols) if grid[r,c] != 'B']

actions = ['U','D','L','R']
move = {'U':(-1,0),'D':(1,0),'L':(0,-1),'R':(0,1)}

gamma, reward_step = 0.99, -0.04
V = {s:0 for s in states}

def in_grid(r,c): return 0<=r

실행 결과 예시 (U=↑, R=→, D=↓, L=←):

R  ██ R  +1
U  ██ R  D
U   R  D  D

---

4-8. 요약 & 다음 편 예고

• 정책 평가로 $V_\pi$를 계산하고, 정책 개선으로 더 나은 $\pi$를 만든다.
• 이를 번갈아 수행하면 정책 반복(PI), 한 식으로 합치면 가치 반복(VI).
• 모형이 완전한 MDP라면 DP로 최적 정책을 빠르고 확실히 구할 수 있다.

다음 글 : 모델이 없을 때는 어떻게 할까요? 실제 환경에서 샘플을 모아 가치·정책을 학습하는 몬테카를로 방법과 시간차(TD) 학습을 차례로 다뤄봅니다.

---

참고 자료

• Sutton & Barto, Reinforcement Learning: An Introduction, Ch. 4
• Richard Bellman, Dynamic Programming, 1957
• Russell & Norvig, Artificial Intelligence: A Modern Approach, §17.2