方策反復法と価値反復法の違い
動的計画法には、強化学習の文脈でよく使われる方策反復法と価値反復法という2つのアプローチがあります。どちらも最適な方策を見つけることを目指しますが、そのアプローチや計算の進め方に違いがあります。
基本概念
状態価値関数 V(s)
- 状態 からスタートして将来得られる累積報酬の期待値を表します。
- 特定の方策 に従ったときの価値は次のように定義されます：
行動価値関数 Q(s, a)
- 状態 で行動 を選択した場合の期待累積報酬です：
方策反復法
手順
- 方策評価：
– 現在の方策 に基づき、状態価値関数 を以下のように求めます（ベルマン方程式に基づく反復）：
- 方策改善：
– 各状態 で、最適な行動を選択することで方策を改善します：
- 方策が収束するまで評価と改善を繰り返します。
特徴
- 価値関数の評価にコストがかかります。すべての状態で価値が収束するまで繰り返しが必要です。
- 一度の評価で正確な方策改善が可能。
価値反復法
手順
- 価値反復法では、方策を逐次改善するのではなく、状態価値関数を直接更新していきます。
1. 価値関数の更新（ベルマン方程式を用いた反復）：
-
価値関数が収束するまでこの更新を繰り返します。
-
最後に、収束した価値関数 に基づき、最適方策 を一度だけ決定します：
特徴
- 方策の改善ステップを逐次行わず、価値関数の更新だけを行います。
- 各反復で価値関数を最大化するため、計算が単純で収束が速いです。
数式から見る違い
-
方策反復法では、「方策評価」と「方策改善」を交互に行います。価値関数 は完全に評価される必要があり、その後に方策を改善します。
-
一方、価値反復法では、方策を改善することなく、価値関数を反復的に更新することで最適解に近づきます。最適な価値関数が得られた後で、一度だけ最適方策を決定します。
どちらを使うべきか
- 方策反復法は、価値関数の計算が難しくない場合や、評価の精度が重要な場合に向いています。
- 価値反復法は、計算が単純で速く、収束が速いため、実践的な用途に向いています。
方策反復法と価値反復法の実装
迷路の問題設定
次のような迷路を使います。エージェントは「上下左右」の行動が取れますが、壁には進めません。
迷路の構造：
- S：スタート地点
- G：ゴール地点（報酬 +1）
- #：壁（通れない）
- 他のセルは報酬 0
S 0 0 G
0 # 0 0
0 0 0 0
方策反復法の実装
以下は、方策反復法を用いて迷路を解くプログラムです。
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()
価値反復法の実装
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)) # 価値関数
# 行動の定義: 上、下、左、右
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 value_iteration():
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
values = []
for (dr, dc) in actions:
nr, nc = r + dr, c + dc
if is_valid((nr, nc)):
reward = maze[nr, nc]
values.append(reward + gamma * V[nr, nc])
else: # 無効な遷移は同じ場所に留まる
values.append(gamma * V[r, c])
new_V[r, c] = max(values) # 最適な価値を選ぶ
delta = max(delta, abs(V[r, c] - new_V[r, c]))
V[:] = new_V # 更新
if delta < theta: # 収束判定
break
# 最適方策の決定
def extract_policy():
policy = np.full((rows, cols), ' ')
arrows = {0: '↑', 1: '↓', 2: '←', 3: '→'}
for r in range(rows):
for c in range(cols):
if maze[r, c] == 1:
policy[r, c] = 'G'
continue
if maze[r, c] == -1:
policy[r, c] = '#'
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)
policy[r, c] = arrows[best_action]
return policy
# 価値反復法の実行
value_iteration()
# 最適方策の取得
optimal_policy = extract_policy()
# 結果の表示
print("最適価値関数:")
print(np.round(V, 2))
print("\n最適方策:")
for row in optimal_policy:
print(" ".join(row))
# 価値関数の可視化
plt.imshow(V, cmap='coolwarm', interpolation='nearest')
plt.colorbar(label="Value")
plt.title("Optimal Value Function (Value Iteration)")
plt.show()
どちらの場合でも同様の結果を得られます。
最適価値関数（各状態の期待報酬を表示）と
最適方策（矢印で表示）
