동적 계획법 — 정책 반복과 가치 반복(Dynamic Programming — Policy Iteration & Value Iteration)

동적 계획법(dynamic programming)은 "치트키를 쓰는 강화학습(RL)"에 가깝습니다. 전이 함수(transition function)와 보상 함수(reward function)를 이미 알고 있습니다. 그래서 V 또는 π가 더 이상 움직이지 않을 때까지 벨만 방정식(Bellman equation)을 반복하면 됩니다. 샘플링 기반 방법(sampling-based methods)이 접근하려고 하는 기준점(benchmark)이 바로 이것입니다.

유형: Build 언어: Python 선수 지식: Phase 9 · 01 (MDP) 예상 시간: 약 75분

문제

알려진 모델(known model)이 있는 MDP를 갖고 있습니다. 어떤 상태-행동 쌍(state-action pair)에 대해서도 P(s' | s, a)와 R(s, a, s')를 조회(query)할 수 있습니다. 재고 관리자(inventory manager)는 수요 분포(demand distribution)를 알고 있습니다. 보드게임(board game)은 결정론적 전이(deterministic transitions)를 갖습니다. GridWorld는 네 줄짜리 Python 코드로 표현됩니다. 즉, *모델(model)*이 있습니다.

모델 없는 강화학습(Model-free RL), 예를 들어 Q-learning, PPO, REINFORCE는 모델이 없는 경우를 위해 만들어졌습니다. 환경(environment)에서 샘플링만 할 수 있는 상황입니다. 하지만 모델이 있다면 더 빠르고 더 좋은 방법이 있습니다. 동적 계획법(dynamic programming, DP)입니다. Bellman은 1957년에 이를 설계했습니다. DP는 지금도 정답성(correctness)을 정의합니다. 사람들이 "이 MDP의 최적 정책(optimal policy)"이라고 말할 때, 그것은 DP가 반환할 정책을 뜻합니다.

2026년에도 DP가 필요한 이유는 세 가지입니다. 첫째, 강화학습 연구의 모든 표 형식 환경(tabular environment), 예를 들어 GridWorld, FrozenLake, CliffWalking은 DP로 풀어 황금 기준 정책(gold-standard policy)을 만듭니다. 둘째, 정확한 값(exact values)은 샘플링 방법을 *디버그(debug)*하게 해줍니다. Q-learning의 V*(s_0) 추정값이 DP 정답과 30% 다르면 Q-learning 구현에 버그가 있는 것입니다. 셋째, 현대 오프라인 강화학습(offline RL)과 계획(planning) 방법, 예를 들어 MCTS, AlphaZero의 탐색(search), Phase 9 · 10의 모델 기반 강화학습(model-based RL)은 모두 학습된 모델 또는 주어진 모델 위에서 벨만 백업(Bellman backup)을 반복합니다.

개념

두 알고리즘 모두 벨만(Bellman)에 대한 고정점 반복(fixed-point iteration)입니다.

정책 반복(Policy iteration). 정책이 더 이상 바뀌지 않을 때까지 두 단계를 번갈아 수행합니다.

1. 평가(Evaluation): 정책 π가 주어졌을 때 V(s) ← Σ_a π(a|s) Σ_{s',r} P(s',r|s,a) [r + γ V(s')]를 반복 적용해 수렴할 때까지 V^π를 계산합니다.
2. 개선(Improvement): V^π가 주어졌을 때, V^π에 대해 탐욕적(greedy)인 정책을 만듭니다. π(s) ← argmax_a Σ_{s',r} P(s',r|s,a) [r + γ V(s')].

수렴은 보장됩니다. 이유는 (a) 각 개선 단계가 π를 그대로 유지하거나 어떤 상태의 V^π를 엄격히 증가시키고, (b) 결정론적 정책(deterministic policies)의 공간이 유한하기 때문입니다. 큰 상태 공간에서도 보통 바깥 반복(outer iterations) 5-20회 정도에 수렴합니다.

가치 반복(Value iteration). 평가와 개선을 하나의 훑기(sweep)로 합칩니다. 벨만 최적성 방정식(Bellman optimality equation)을 적용합니다.

V(s) ← max_a Σ_{s',r} P(s',r|s,a) [r + γ V(s')]

max_s |V_{new}(s) - V(s)| < ε가 될 때까지 반복합니다. 마지막에 탐욕적 행동(greedy action)을 선택해 정책을 추출합니다. 반복당 비용은 더 작습니다. 내부 평가 루프(inner evaluation loop)가 없기 때문입니다. 하지만 보통 수렴까지 더 많은 반복이 필요합니다.

일반화 정책 반복(Generalized policy iteration; GPI). 통합된 관점입니다. 가치 함수(value function)와 정책(policy)은 양방향 개선 루프(two-way improvement loop)에 묶여 있습니다. 둘을 상호 일관성(mutual consistency)으로 몰고 가는 모든 방법, 예를 들어 비동기 가치 반복(async value iteration), 수정 정책 반복(modified policy iteration), Q-learning, 액터-크리틱(actor-critic), PPO는 모두 GPI의 한 사례입니다.

왜 γ < 1이 중요한가. 벨만 연산자(Bellman operator)는 상한 노름(sup-norm)에서 γ-수축(γ-contraction)입니다. ||T V - T V'||_∞ ≤ γ ||V - V'||_∞입니다. 수축은 고유한 고정점(unique fixed point)과 기하 수렴(geometric convergence)을 의미합니다. γ < 1 조건을 잃으면 보장을 잃습니다. 이때는 유한한 시간 지평(finite horizon) 또는 흡수 종단 상태(absorbing terminal state)가 필요합니다.

직접 만들기

Step 1: GridWorld MDP 모델 만들기

Lesson 01과 같은 4×4 GridWorld를 사용합니다. 여기에 확률적 변형(stochastic variant)을 추가합니다. 확률 0.1로 에이전트가 진행 방향에 수직인 임의의 방향(random perpendicular direction)으로 미끄러집니다.

SLIP = 0.1

def transitions(state, action):
    if state == TERMINAL:
        return [(state, 0.0, 1.0)]
    outcomes = []
    for direction, prob in action_probs(action):
        outcomes.append((apply_move(state, direction), -1.0, prob))
    return outcomes

transitions(s, a)는 (s', r, p)의 리스트를 반환합니다. 이것이 전체 모델입니다.

Step 2: 정책 평가(policy evaluation)

정책 π(s) = {action: prob}가 주어졌을 때, V가 더 이상 움직이지 않을 때까지 벨만 방정식을 반복합니다.

def policy_evaluation(policy, gamma=0.99, tol=1e-6):
    V = {s: 0.0 for s in states()}
    while True:
        delta = 0.0
        for s in states():
            v = sum(pi_a * sum(p * (r + gamma * V[s_prime])
                              for s_prime, r, p in transitions(s, a))
                   for a, pi_a in policy(s).items())
            delta = max(delta, abs(v - V[s]))
            V[s] = v
        if delta < tol:
            return V

Step 3: 정책 개선(policy improvement)

V에 대해 탐욕적(greedy)인 정책으로 π를 교체합니다. π가 바뀌지 않았다면 반환합니다. 최적점에 도달한 것입니다.

def policy_improvement(V, gamma=0.99):
    new_policy = {}
    for s in states():
        best_a = max(
            ACTIONS,
            key=lambda a: sum(p * (r + gamma * V[s_prime])
                              for s_prime, r, p in transitions(s, a)),
        )
        new_policy[s] = best_a
    return new_policy

Step 4: 둘을 연결하기

def policy_iteration(gamma=0.99):
    policy = {s: "up" for s in states()}   # arbitrary start
    for _ in range(100):
        V = policy_evaluation(lambda s: {policy[s]: 1.0}, gamma)
        new_policy = policy_improvement(V, gamma)
        if new_policy == policy:
            return V, policy
        policy = new_policy

4×4에서는 보통 바깥 반복 4-6회에 수렴합니다. V*(0,0) ≈ -6과 스텝(step) 수를 엄격하게 줄이는 정책을 출력합니다.

Step 5: 가치 반복(value iteration), 하나의 루프로 끝내는 버전

def value_iteration(gamma=0.99, tol=1e-6):
    V = {s: 0.0 for s in states()}
    while True:
        delta = 0.0
        for s in states():
            v = max(sum(p * (r + gamma * V[s_prime])
                       for s_prime, r, p in transitions(s, a))
                   for a in ACTIONS)
            delta = max(delta, abs(v - V[s]))
            V[s] = v
        if delta < tol:
            break
    policy = policy_improvement(V, gamma)
    return V, policy

같은 고정점(fixed point)에 도달하지만 코드가 더 적습니다.

주의할 점

• 종단 상태 처리를 잊는 것(Forgetting to handle terminals). 흡수 상태(absorbing state)에 벨만을 적용하면 여전히 아무것도 바꾸지 않는 "최선의 행동(best action)"을 줍니다. if s == terminal: V[s] = 0으로 방어합니다.
• 상한 노름(sup-norm) 대 L2 수렴. 평균이 아니라 max |V_new - V|를 사용합니다. 이론적 보장은 상한 노름 위에 있습니다.
• 제자리 갱신 대 동기 갱신(In-place vs synchronous updates). V[s]를 제자리에서 갱신하는 방식(Gauss-Seidel)은 별도 V_new 딕셔너리를 쓰는 방식(Jacobi)보다 빠르게 수렴합니다. 운영 코드(production code)는 제자리 갱신을 사용합니다.
• 정책 동률(Policy ties). 두 행동의 Q-값이 같으면 argmax가 반복마다 동률을 다르게 깰 수 있어 "정책 안정(policy stable)" 확인이 진동할 수 있습니다. 고정된 순서의 첫 번째 행동을 택하는 안정적인 동률 처리(tie-break)를 사용합니다.
• 상태 공간 폭발(State-space explosion). DP는 한 번의 훑기(sweep)마다 O(|S| · |A|)입니다. 대략 10⁷개 상태까지 작동합니다. 그 이상에서는 함수 근사(function approximation)가 필요합니다(Phase 9 · 05 이후).

사용해보기

2026년에 DP는 정답성 기준(correctness baseline)이자 계획기(planner)의 내부 루프입니다.

누군가 "최적 가치 함수(optimal value function)"라고 말할 때마다 "DP 고정점"을 뜻한다고 보면 됩니다. 논문에서 V* 또는 Q*를 보면 이 루프를 떠올립니다.

산출물 만들기

outputs/skill-dp-solver.md로 저장합니다.

---
name: dp-solver
description: Solve a small tabular MDP exactly via policy iteration or value iteration. Report convergence behavior.
version: 1.0.0
phase: 9
lesson: 2
tags: [rl, dynamic-programming, bellman]
---

Given an MDP with a known model, output:

1. Choice. Policy iteration vs value iteration. Reason tied to |S|, |A|, γ.
2. Initialization. V_0, starting policy. Convergence sensitivity.
3. Stopping. Sup-norm tolerance ε. Expected number of sweeps.
4. Verification. V*(s_0) computed exactly. Greedy policy extracted.
5. Use. How this baseline will be used to debug/evaluate sampling-based methods.

Refuse to run DP on state spaces > 10⁷. Refuse to claim convergence without a sup-norm check. Flag any γ ≥ 1 on an infinite-horizon task as a guarantee violation.

연습문제

1. 쉬움. γ ∈ {0.9, 0.99}로 4×4 GridWorld에서 가치 반복(value iteration)을 실행합니다. max |ΔV| < 1e-6이 될 때까지 몇 번의 훑기(sweep)가 걸리나요? V*를 4×4 격자로 출력합니다.
2. 중간. 확률적 GridWorld(미끄러질 확률 0.1)에서 정책 반복과 가치 반복을 비교합니다. 훑기 수, 실제 경과 시간(wall-clock time), 최종 V*(0,0)을 세어봅니다. 반복 수 기준으로 어느 쪽이 더 빨리 수렴하나요? 실제 경과 시간 기준으로는 어떤가요?
3. 어려움. 수정 정책 반복(modified policy iteration)을 구현합니다. 평가 단계에서 수렴할 때까지가 아니라 k번의 훑기만 실행합니다. k ∈ {1, 2, 5, 10, 50}에 대해 V*(0,0) 오차를 그래프로 그립니다(plot). 이 곡선은 평가와 개선 사이의 균형(evaluation/improvement tradeoff)에 대해 무엇을 말해주나요?

핵심 용어

더 읽을거리

• Sutton & Barto (2018). Ch. 4 — Dynamic Programming — 정책 반복과 가치 반복의 표준 설명입니다.
• Bertsekas (2019). Reinforcement Learning and Optimal Control — 수축 사상(contraction-mapping) 논증을 엄밀하게 다룹니다.
• Puterman (2005). Markov Decision Processes — 수정 정책 반복(modified policy iteration)과 수렴 분석입니다.
• Howard (1960). Dynamic Programming and Markov Processes — 원래의 정책 반복 논문입니다.
• Bertsekas & Tsitsiklis (1996). Neuro-Dynamic Programming — DP에서 근사 DP(approximate-DP)와 심층 강화학습(deep RL)으로 이어지는 다리입니다. 이후 모든 lesson에서 사용됩니다.