迷路で理解する動的計画法と方策反復法

動的計画法とは
方策反復法とは
迷路の問題設定
1. 迷路の構造：
2. Pythonでの実装
解説
実行結果
まとめ

動的計画法とは

動的計画法（Dynamic Programming, DP）は、問題を部分問題に分解して解く手法です。強化学習では、状態ごとに最適な価値を計算し、その情報をもとに最適な方策（Policy）を決定します。特に、エージェントがどの状態でどの行動を取るべきかを学習するためのアルゴリズムとして、方策反復法 (Policy Iteration) があります。

方策反復法とは

方策反復法では、次の2つのステップを繰り返します：

方策評価 (Policy Evaluation)
– 現在の方策に従って、各状態の価値 $V(s)$ を計算。
方策改善 (Policy Improvement)
– 各状態で最適な行動を選び、方策を更新。

この反復を通じて、エージェントがどの行動を取るべきかを学習します。

迷路の問題設定

次のような迷路を使います。エージェントは「上下左右」の行動が取れますが、壁には進めません。

迷路の構造：

S：スタート地点
G：ゴール地点（報酬 +1）
#：壁（通れない）
他のセルは報酬 0

S  0  0  G
0  #  0  0
0  0  0  0

Pythonでの実装

以下は、方策反復法を用いて迷路を解くプログラムです。

import numpy as np
import matplotlib.pyplot as plt

# 迷路の設定 (S: スタート, G: ゴール, #: 壁)
maze = np.array([
    [0, 0, 0, 1],  # 1: ゴール
    [0, -1, 0, 0], # -1: 壁
    [0, 0, 0, 0]
])

# パラメータ設定
gamma = 0.9  # 割引率
theta = 1e-4 # 価値関数の収束判定

# 状態の初期化
rows, cols = maze.shape
V = np.zeros((rows, cols))  # 価値関数
policy = np.full((rows, cols, 4), 0.25)  # 初期方策（等確率）

# 行動の定義: 上、下、左、右
actions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

# 迷路の外または壁かどうかをチェックする関数
def is_valid(state):
    r, c = state
    return 0 <= r < rows and 0 <= c < cols and maze[r, c] != -1

# 方策評価ステップ
def policy_evaluation(policy):
    while True:
        delta = 0  # 価値関数の変化量
        new_V = np.copy(V)
        for r in range(rows):
            for c in range(cols):
                if maze[r, c] == 1:  # ゴール地点
                    continue
                value = 0
                for a, (dr, dc) in enumerate(actions):
                    nr, nc = r + dr, c + dc
                    if is_valid((nr, nc)):
                        reward = maze[nr, nc]
                        value += policy[r, c, a] * (reward + gamma * V[nr, nc])
                    else:  # 無効な遷移は同じ場所に留まる
                        value += policy[r, c, a] * (gamma * V[r, c])
                new_V[r, c] = value
                delta = max(delta, abs(V[r, c] - new_V[r, c]))
        V[:] = new_V  # 更新
        if delta < theta:  # 収束判定
            break

# 方策改善ステップ
def policy_improvement():
    stable = True  # 方策が安定したかどうか
    new_policy = np.zeros_like(policy)
    for r in range(rows):
        for c in range(cols):
            if maze[r, c] == 1:  # ゴール地点
                continue
            values = []
            for (dr, dc) in actions:
                nr, nc = r + dr, c + dc
                if is_valid((nr, nc)):
                    values.append(maze[nr, nc] + gamma * V[nr, nc])
                else:
                    values.append(gamma * V[r, c])
            best_action = np.argmax(values)
            new_policy[r, c] = np.eye(4)[best_action]
            if not np.array_equal(new_policy[r, c], policy[r, c]):
                stable = False
    policy[:] = new_policy  # 更新
    return stable

# 方策反復の実行
while True:
    policy_evaluation(policy)  # 方策評価
    if policy_improvement():  # 方策改善
        break

# 結果の表示
print("最適価値関数:")
print(np.round(V, 2))

print("\n最適方策 (矢印で表示):")
arrows = {0: '↑', 1: '↓', 2: '←', 3: '→'}
for r in range(rows):
    line = ""
    for c in range(cols):
        if maze[r, c] == 1:
            line += " G "
        elif maze[r, c] == -1:
            line += " # "
        else:
            best_action = np.argmax(policy[r, c])
            line += f" {arrows[best_action]} "
    print(line)

# 価値関数の可視化
plt.imshow(V, cmap='coolwarm', interpolation='nearest')
plt.colorbar(label="Value")
plt.title("Optimal Value Function")
plt.show()