レッスン 2: 動的プログラミング — ポリシーの反復と値の反復

強化学習: 基礎から高度まで

パート 1: RL の基礎 — マルコフの意思決定プロセスと表形式の手法

xdev.asia

はじめに

動的計画法 (DP) は、モデル全体、つまり遷移確率 P(s'|s,a) と報酬 R を認識して MDP を解きます。これは、すべての RL アルゴリズムの理論的基礎です。

---

1. ベルマン方程式

ベルマンの期待方程式

$$V^\pi(s) = \sum_a \pi(a|s) \sum_{s'} P(s'|s,a)[R(s,a,s') + \gamma V^\pi(s')]$$

ベルマン最適性方程式

$$V^(s) = \max_a \sum_{s'} P(s'|s,a)[R(s,a,s') + \gamma V^(s')]$$

---

2. 政策の評価

固定ポリシーの V(s) を計算します。

import numpy as np

def policy_evaluation(policy, env, gamma=0.99, theta=1e-8):
    V = np.zeros(env.nS)
    while True:
        delta = 0
        for s in range(env.nS):
            v = 0
            for a, action_prob in enumerate(policy[s]):
                for prob, next_state, reward, done in env.P[s][a]:
                    v += action_prob * prob * (reward + gamma * V[next_state])
            delta = max(delta, abs(V[s] - v))
            V[s] = v
        if delta < theta:
            break
    return V

---

3. ポリシーの改善

V に基づいた貪欲な改善:

def policy_improvement(V, env, gamma=0.99):
    policy = np.zeros([env.nS, env.nA])
    for s in range(env.nS):
        q_values = np.zeros(env.nA)
        for a in range(env.nA):
            for prob, next_state, reward, done in env.P[s][a]:
                q_values[a] += prob * (reward + gamma * V[next_state])
        best_action = np.argmax(q_values)
        policy[s][best_action] = 1.0
    return policy

---

4. ポリシーの反復

def policy_iteration(env, gamma=0.99):
    policy = np.ones([env.nS, env.nA]) / env.nA  # Uniform random
    while True:
        V = policy_evaluation(policy, env, gamma)
        new_policy = policy_improvement(V, env, gamma)
        if np.array_equal(policy, new_policy):
            break
        policy = new_policy
    return policy, V

---

5. 値の反復

def value_iteration(env, gamma=0.99, theta=1e-8):
    V = np.zeros(env.nS)
    while True:
        delta = 0
        for s in range(env.nS):
            v = V[s]
            V[s] = max(
                sum(p * (r + gamma * V[s_])
                    for p, s_, r, _ in env.P[s][a])
                for a in range(env.nA)
            )
            delta = max(delta, abs(v - V[s]))
        if delta < theta:
            break
    return V

---

6. GridWorld デモ

import gymnasium as gym

env = gym.make("FrozenLake-v1", is_slippery=False)
policy, V = policy_iteration(env.unwrapped, gamma=0.99)

print("Optimal Value Function:")
print(V.reshape(4, 4))
print("Optimal Policy (0=L, 1=D, 2=R, 3=U):")
print(np.argmax(policy, axis=1).reshape(4, 4))

---

概要

方法	アプローチ	収束	複雑さ
ポリシーの反復	評価→改善	反復回数が少ない	評価ごとの O(S²A)
値の反復	ワンステップ先読み	多くの反復	反復ごとの O(SA)