動的計画法（Dynamic Programming, DP）は、マルコフ決定過程（MDP）の環境モデルが完全に既知である場合に、最適方策を求めるための古典的かつ強力な手法です。ベルマン方程式を反復的に解くことで、価値関数を計算し、最適な行動規則を導きます。
動的計画法には大きく分けて方策反復（Policy Iteration）と価値反復（Value Iteration）の2つのアルゴリズムがあります。方策反復は「方策の評価」と「方策の改善」を交互に繰り返し、価値反復はベルマン最適方程式を直接反復的に解きます。本記事では、これらのアルゴリズムの理論的基盤（収束証明を含む）を丁寧に解説し、Pythonでの完全な実装と収束過程の可視化を行います。
本記事の内容
- 方策評価アルゴリズムと縮小写像による収束証明
- 方策改善定理の証明
- 方策反復アルゴリズムと有限ステップ収束
- 価値反復アルゴリズム
- 方策反復と価値反復の比較
- 非同期DPの概要
- Pythonでグリッドワールドに対する完全実装と可視化
前提知識
この記事を読む前に、以下の記事を読んでおくと理解が深まります。
動的計画法の位置づけ
動的計画法はモデルベースの手法です。つまり、環境の完全なモデル（状態遷移確率 $P(s’|s,a)$ と報酬関数 $R(s,a,s’)$）が既知であることを前提とします。
| 手法 | モデル | 更新方式 |
|---|---|---|
| 動的計画法（DP） | 必要（$P, R$ が既知） | 全状態の一括更新 |
| モンテカルロ法 | 不要 | エピソード完了後に更新 |
| TD学習 | 不要 | 1ステップごとに更新 |
DPは実用上の制約があるものの、強化学習の理論的基盤を理解するうえで不可欠です。
方策評価（Policy Evaluation）
アルゴリズム
方策評価は、与えられた方策 $\pi$ のもとでの状態価値関数 $V^{\pi}$ を計算する手順です。ベルマン期待方程式
$$ V^{\pi}(s) = \sum_{a \in \mathcal{A}} \pi(a|s) \sum_{s’ \in \mathcal{S}} P(s’|s,a) \left[ R(s,a,s’) + \gamma V^{\pi}(s’) \right] $$
を反復的に解きます。
反復方策評価アルゴリズム:
- 初期化: $V_0(s) = 0$ （全状態）
- 繰り返し $k = 0, 1, 2, \dots$: – 全ての $s \in \mathcal{S}$ に対して $$ V_{k+1}(s) = \sum_{a \in \mathcal{A}} \pi(a|s) \sum_{s’ \in \mathcal{S}} P(s’|s,a) \left[ R(s,a,s’) + \gamma V_k(s’) \right] $$
- $\max_s |V_{k+1}(s) – V_k(s)| < \theta$ で終了
これはベルマン期待作用素 $\mathcal{T}^{\pi}$ の反復適用 $V_{k+1} = \mathcal{T}^{\pi} V_k$ に他なりません。
収束証明（縮小写像）
定理: 反復方策評価は $V^{\pi}$ に収束する。
証明: ベルマン期待作用素 $\mathcal{T}^{\pi}$ が $\gamma$-縮小写像であることは前記事で示しました。
$$ \|\mathcal{T}^{\pi} V_1 – \mathcal{T}^{\pi} V_2\|_{\infty} \leq \gamma \|V_1 – V_2\|_{\infty} $$
$V_{k+1} = \mathcal{T}^{\pi} V_k$ であるから
$$ \begin{align} \|V_{k+1} – V^{\pi}\|_{\infty} &= \|\mathcal{T}^{\pi} V_k – \mathcal{T}^{\pi} V^{\pi}\|_{\infty} \\ &\leq \gamma \|V_k – V^{\pi}\|_{\infty} \\ &\leq \gamma^2 \|V_{k-1} – V^{\pi}\|_{\infty} \\ &\quad \vdots \\ &\leq \gamma^{k+1} \|V_0 – V^{\pi}\|_{\infty} \end{align} $$
$\gamma < 1$ なので $\gamma^{k+1} \to 0$ ($k \to \infty$) となり、$V_k \to V^{\pi}$ が示されました。
収束速度は $O(\gamma^k)$ です。$\gamma = 0.99$ の場合、誤差を $10^{-6}$ にするには約 $k \approx \log(10^{-6}) / \log(0.99) \approx 1376$ 回の反復が必要です。
方策改善定理
方策評価で $V^{\pi}$ が得られたら、次にそれを用いてより良い方策を構成します。その際の理論的保証を与えるのが方策改善定理です。
定理の記述
方策改善定理: 方策 $\pi$ に対して、貪欲方策 $\pi’$ を
$$ \pi'(s) = \arg\max_{a \in \mathcal{A}} Q^{\pi}(s, a) = \arg\max_{a \in \mathcal{A}} \sum_{s’ \in \mathcal{S}} P(s’|s,a) \left[ R(s,a,s’) + \gamma V^{\pi}(s’) \right] $$
と定義する。このとき、全ての状態 $s$ に対して
$$ V^{\pi’}(s) \geq V^{\pi}(s) $$
が成り立つ。等号が全ての $s$ で成り立つのは $\pi$ が既に最適方策である場合に限る。
証明
任意の状態 $s$ から出発して、$\pi’$ に従った場合を考えます。
ステップ1: 貪欲方策の定義より
$$ Q^{\pi}(s, \pi'(s)) = \max_{a} Q^{\pi}(s, a) \geq Q^{\pi}(s, \pi(s)) = V^{\pi}(s) $$
最後の等号は、$\pi$ が決定的方策の場合 $Q^{\pi}(s, \pi(s)) = V^{\pi}(s)$ であることを用いました（確率的方策の場合は $V^{\pi}(s) = \sum_a \pi(a|s) Q^{\pi}(s,a) \leq \max_a Q^{\pi}(s,a)$ から同様に成立）。
ステップ2: $Q^{\pi}(s, \pi'(s))$ を展開します。
$$ \begin{align} V^{\pi}(s) &\leq Q^{\pi}(s, \pi'(s)) \\ &= \sum_{s’} P(s’|s, \pi'(s)) \left[ R(s, \pi'(s), s’) + \gamma V^{\pi}(s’) \right] \end{align} $$
ステップ3: 右辺の $V^{\pi}(s’)$ にも同じ不等式 $V^{\pi}(s’) \leq Q^{\pi}(s’, \pi'(s’))$ を再帰的に適用します。
$$ \begin{align} V^{\pi}(s) &\leq \sum_{s’} P(s’|s, \pi'(s)) \left[ R(s, \pi'(s), s’) + \gamma V^{\pi}(s’) \right] \\ &\leq \sum_{s’} P(s’|s, \pi'(s)) \left[ R(s, \pi'(s), s’) + \gamma \sum_{s”} P(s”|s’, \pi'(s’)) \left[ R(s’, \pi'(s’), s”) + \gamma V^{\pi}(s”) \right] \right] \end{align} $$
ステップ4: これを無限に繰り返すと
$$ \begin{align} V^{\pi}(s) &\leq \mathbb{E}_{\pi’}\left[R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots \mid S_t = s\right] \\ &= \mathbb{E}_{\pi’}[G_t \mid S_t = s] \\ &= V^{\pi’}(s) \end{align} $$
よって $V^{\pi’}(s) \geq V^{\pi}(s)$ が全ての $s$ について成り立ちます。
等号条件: $V^{\pi’}(s) = V^{\pi}(s)$ が全ての $s$ で成り立つためには、ステップ1の不等式が全状態で等号でなければなりません。これは $\pi$ が既にベルマン最適方程式を満たしている場合、すなわち $\pi$ が最適方策である場合に限ります。 $\square$
方策反復アルゴリズム
方策改善定理を活用して、方策を反復的に改善していくのが方策反復です。
アルゴリズム
- 初期化: 任意の方策 $\pi_0$（例: ランダム方策）
- 繰り返し $k = 0, 1, 2, \dots$: – 方策評価: ベルマン期待方程式を反復的に解いて $V^{\pi_k}$ を計算 – 方策改善: 貪欲方策を構成 $$ \pi_{k+1}(s) = \arg\max_{a} \sum_{s’} P(s’|s,a) \left[ R(s,a,s’) + \gamma V^{\pi_k}(s’) \right] $$
- 終了条件: $\pi_{k+1} = \pi_k$（方策が変化しなくなったら終了）
有限ステップ収束
定理: 有限MDPにおいて、方策反復は有限ステップで最適方策に収束する。
証明の概略: 有限MDPの決定的定常方策の総数は $|\mathcal{A}|^{|\mathcal{S}|}$ で有限です。方策改善定理により、各反復で方策が改善されるか（$V^{\pi_{k+1}}(s) > V^{\pi_k}(s)$ がある $s$ で成立）、あるいは既に最適です。改善される場合、同じ方策が二度出現することはありません。方策の総数が有限なので、有限回の反復で最適方策に到達します。
実際には、方策反復の収束は非常に速く、多くの場合数回の反復で最適方策が得られます。
価値反復アルゴリズム
アルゴリズム
価値反復は、ベルマン最適方程式を直接反復的に解く手法です。方策評価と方策改善を分離せず、一度の更新で最適価値に向かいます。
- 初期化: $V_0(s) = 0$ （全状態）
- 繰り返し $k = 0, 1, 2, \dots$: – 全ての $s \in \mathcal{S}$ に対して $$ V_{k+1}(s) = \max_{a \in \mathcal{A}} \sum_{s’ \in \mathcal{S}} P(s’|s,a) \left[ R(s,a,s’) + \gamma V_k(s’) \right] $$
- 終了: $\max_s |V_{k+1}(s) – V_k(s)| < \theta$ で終了
- 方策の抽出: 収束後の $V^{*}$ から最適方策を計算 $$ \pi^{*}(s) = \arg\max_{a} \sum_{s’} P(s’|s,a) \left[ R(s,a,s’) + \gamma V^{*}(s’) \right] $$
価値反復の解釈
価値反復は、ベルマン最適作用素 $\mathcal{T}^{*}$ の反復適用です。
$$ V_{k+1} = \mathcal{T}^{*} V_k $$
$\mathcal{T}^{*}$ は $\gamma$-縮小写像なので、バナッハの不動点定理により $V_k \to V^{*}$ が保証されます。
価値反復は、方策反復において方策評価を1回だけ行う（厳密に収束させずに切り上げる）特殊ケースとも解釈できます。
方策反復と価値反復の比較
| 特性 | 方策反復 | 価値反復 |
|---|---|---|
| 各反復の計算量 | 方策評価で多数の反復 | 1回の更新 |
| 収束までの反復数 | 少ない（通常5〜20回程度） | 多い（数百〜数千回） |
| 各反復のコスト | 高い（方策評価が重い） | 低い（1回のスイープ） |
| 総計算量 | 少ない状態数では効率的 | 方策評価の精度が不要な分、有利な場合も |
| 収束先 | 最適方策 + $V^{*}$ | $V^{*}$（方策は後から抽出） |
実用的には、方策反復は各反復で方策を確実に改善するため反復数が少なく済みますが、各反復で方策評価を収束させるコストがかかります。価値反復は各反復が軽量で実装もシンプルですが、収束には多くの反復を必要とします。
非同期DPの概要
上記のアルゴリズムは同期的DP（synchronous DP）であり、各反復で全ての状態を一括更新します。非同期DP（asynchronous DP）は、任意の順序で一部の状態のみを更新します。
主な非同期DPの手法:
-
In-place DP: $V_{k+1}(s)$ を計算したら即座に $V(s)$ を上書きする。2つの配列を保持する必要がなく、最新の情報を即時利用できる
-
優先スイープ（Prioritized Sweeping）: ベルマン誤差 $|V_{k+1}(s) – V_k(s)|$ が大きい状態を優先的に更新する。重要な更新を先に行うことで収束が速まる
-
リアルタイムDP: エージェントが実際に訪問した状態のみを更新する。巨大な状態空間を持つ問題で有効
非同期DPは、全ての状態が無限回更新される限り、最適値関数に収束することが保証されています。
Pythonでの実装
グリッドワールドと共通ユーティリティ
import numpy as np
import matplotlib.pyplot as plt
import time
class GridWorld:
"""4x4 グリッドワールド MDP 環境"""
def __init__(self, rows=4, cols=4, gamma=0.99):
self.rows = rows
self.cols = cols
self.gamma = gamma
self.actions = [0, 1, 2, 3] # 上, 下, 左, 右
self.action_names = ['↑', '↓', '←', '→']
self.action_deltas = [(-1, 0), (1, 0), (0, -1), (0, 1)]
self.n_states = rows * cols
self.n_actions = len(self.actions)
self.goal_state = (rows - 1, cols - 1)
self.goal_reward = 1.0
self.step_reward = -0.04
def state_to_idx(self, row, col):
return row * self.cols + col
def idx_to_state(self, idx):
return idx // self.cols, idx % self.cols
def is_terminal(self, row, col):
return (row, col) == self.goal_state
def get_next_state(self, row, col, action):
if self.is_terminal(row, col):
return row, col
dr, dc = self.action_deltas[action]
new_row, new_col = row + dr, col + dc
if new_row < 0 or new_row >= self.rows or new_col < 0 or new_col >= self.cols:
new_row, new_col = row, col
return new_row, new_col
def get_transition_prob(self, row, col, action):
if self.is_terminal(row, col):
return [(1.0, row, col, 0.0)]
next_row, next_col = self.get_next_state(row, col, action)
reward = self.goal_reward if (next_row, next_col) == self.goal_state else self.step_reward
return [(1.0, next_row, next_col, reward)]
方策反復の完全実装
import numpy as np
import matplotlib.pyplot as plt
import time
# GridWorldクラスは上で定義済みとする
def policy_evaluation(env, policy, theta=1e-10, max_iter=100000):
"""方策評価: V^π を反復法で計算"""
V = np.zeros(env.n_states)
iteration_count = 0
for k in range(max_iter):
delta = 0
for s in range(env.n_states):
row, col = env.idx_to_state(s)
if env.is_terminal(row, col):
continue
v_old = V[s]
v_new = 0
for a in env.actions:
pi_a = policy[s, a]
for prob, nr, nc, reward in env.get_transition_prob(row, col, a):
s_next = env.state_to_idx(nr, nc)
v_new += pi_a * prob * (reward + env.gamma * V[s_next])
V[s] = v_new
delta = max(delta, abs(v_new - v_old))
iteration_count += 1
if delta < theta:
break
return V, iteration_count
def policy_improvement(env, V):
"""方策改善: V から貪欲方策を構成"""
policy = np.zeros((env.n_states, env.n_actions))
for s in range(env.n_states):
row, col = env.idx_to_state(s)
if env.is_terminal(row, col):
policy[s, 0] = 1.0
continue
q_values = np.zeros(env.n_actions)
for a in env.actions:
for prob, nr, nc, reward in env.get_transition_prob(row, col, a):
s_next = env.state_to_idx(nr, nc)
q_values[a] += prob * (reward + env.gamma * V[s_next])
# 貪欲方策: 最大Q値を持つ行動に確率1
best_a = np.argmax(q_values)
policy[s, best_a] = 1.0
return policy
def policy_iteration(env, max_iter=100):
"""方策反復アルゴリズムの完全実装"""
# 初期方策: ランダム方策
policy = np.ones((env.n_states, env.n_actions)) / env.n_actions
history = {
'V': [],
'policy': [],
'eval_iters': [],
'policy_changed': []
}
for k in range(max_iter):
# 方策評価
V, eval_iters = policy_evaluation(env, policy)
history['V'].append(V.copy())
history['eval_iters'].append(eval_iters)
# 方策改善
new_policy = policy_improvement(env, V)
history['policy'].append(new_policy.copy())
# 方策が変化したか確認
policy_stable = np.allclose(policy, new_policy)
history['policy_changed'].append(not policy_stable)
policy = new_policy
if policy_stable:
print(f"方策反復: {k + 1} 回のイテレーションで収束")
print(f"各イテレーションの方策評価回数: {history['eval_iters']}")
break
return V, policy, history
# 方策反復の実行
env = GridWorld(rows=4, cols=4, gamma=0.99)
start_time = time.time()
V_pi, policy_pi, history_pi = policy_iteration(env)
time_pi = time.time() - start_time
print(f"\n方策反復の計算時間: {time_pi:.4f} 秒")
print("\n最適価値関数 V*:")
print(V_pi.reshape(env.rows, env.cols).round(4))
print("\n最適方策:")
for s in range(env.n_states):
row, col = env.idx_to_state(s)
if not env.is_terminal(row, col):
best_a = np.argmax(policy_pi[s])
print(f" 状態({row},{col}): {env.action_names[best_a]}")
価値反復の完全実装
import numpy as np
import matplotlib.pyplot as plt
import time
# GridWorldクラスは上で定義済みとする
def value_iteration(env, theta=1e-10, max_iter=100000):
"""価値反復アルゴリズムの完全実装"""
V = np.zeros(env.n_states)
history = {
'V': [V.copy()],
'delta': []
}
for k in range(max_iter):
delta = 0
for s in range(env.n_states):
row, col = env.idx_to_state(s)
if env.is_terminal(row, col):
continue
v_old = V[s]
q_values = []
for a in env.actions:
q = 0
for prob, nr, nc, reward in env.get_transition_prob(row, col, a):
s_next = env.state_to_idx(nr, nc)
q += prob * (reward + env.gamma * V[s_next])
q_values.append(q)
V[s] = max(q_values)
delta = max(delta, abs(V[s] - v_old))
history['V'].append(V.copy())
history['delta'].append(delta)
if delta < theta:
print(f"価値反復: {k + 1} 回のイテレーションで収束")
break
# 最適方策の抽出
policy = np.zeros((env.n_states, env.n_actions))
for s in range(env.n_states):
row, col = env.idx_to_state(s)
if env.is_terminal(row, col):
policy[s, 0] = 1.0
continue
q_values = np.zeros(env.n_actions)
for a in env.actions:
for prob, nr, nc, reward in env.get_transition_prob(row, col, a):
s_next = env.state_to_idx(nr, nc)
q_values[a] += prob * (reward + env.gamma * V[s_next])
best_a = np.argmax(q_values)
policy[s, best_a] = 1.0
return V, policy, history
# 価値反復の実行
env = GridWorld(rows=4, cols=4, gamma=0.99)
start_time = time.time()
V_vi, policy_vi, history_vi = value_iteration(env)
time_vi = time.time() - start_time
print(f"\n価値反復の計算時間: {time_vi:.4f} 秒")
print("\n最適価値関数 V*:")
print(V_vi.reshape(env.rows, env.cols).round(4))
収束過程の可視化
import numpy as np
import matplotlib.pyplot as plt
# 上のコードで history_pi, history_vi が得られているとする
fig, axes = plt.subplots(2, 2, figsize=(14, 10))
# --- (1) 方策反復: 各ステップの方策評価回数 ---
ax = axes[0, 0]
ax.bar(range(1, len(history_pi['eval_iters']) + 1), history_pi['eval_iters'], color='steelblue')
ax.set_xlabel('Policy Iteration Step', fontsize=12)
ax.set_ylabel('Policy Evaluation Iterations', fontsize=12)
ax.set_title('Policy Iteration:\nEvaluation Iterations per Step', fontsize=13)
ax.grid(True, alpha=0.3)
# --- (2) 価値反復: 収束過程 ---
ax = axes[0, 1]
ax.semilogy(history_vi['delta'], color='red', linewidth=2)
ax.set_xlabel('Iteration', fontsize=12)
ax.set_ylabel('Max |V_new - V_old|', fontsize=12)
ax.set_title('Value Iteration:\nConvergence', fontsize=13)
ax.grid(True, alpha=0.3)
# --- (3) 方策反復: V の推移 ---
ax = axes[1, 0]
V_history_pi = np.array(history_pi['V'])
# 状態(0,0) と 状態(2,2) の価値関数の推移
ax.plot(V_history_pi[:, 0], 'o-', label='State (0,0)', linewidth=2, markersize=8)
ax.plot(V_history_pi[:, 10], 's-', label='State (2,2)', linewidth=2, markersize=8)
ax.plot(V_history_pi[:, 14], '^-', label='State (3,2)', linewidth=2, markersize=8)
ax.set_xlabel('Policy Iteration Step', fontsize=12)
ax.set_ylabel('$V^{\\pi}(s)$', fontsize=12)
ax.set_title('Policy Iteration:\nValue Function Evolution', fontsize=13)
ax.legend(fontsize=10)
ax.grid(True, alpha=0.3)
# --- (4) 価値反復: V の推移 ---
ax = axes[1, 1]
V_history_vi = np.array(history_vi['V'])
# 適当な間隔でサンプリング
sample_iters = np.arange(0, len(V_history_vi), max(1, len(V_history_vi) // 50))
ax.plot(sample_iters, V_history_vi[sample_iters, 0], 'o-', label='State (0,0)',
linewidth=1.5, markersize=4)
ax.plot(sample_iters, V_history_vi[sample_iters, 10], 's-', label='State (2,2)',
linewidth=1.5, markersize=4)
ax.plot(sample_iters, V_history_vi[sample_iters, 14], '^-', label='State (3,2)',
linewidth=1.5, markersize=4)
ax.set_xlabel('Value Iteration Step', fontsize=12)
ax.set_ylabel('$V(s)$', fontsize=12)
ax.set_title('Value Iteration:\nValue Function Evolution', fontsize=13)
ax.legend(fontsize=10)
ax.grid(True, alpha=0.3)
plt.suptitle('Dynamic Programming: Policy Iteration vs Value Iteration', fontsize=15)
plt.tight_layout()
plt.show()
最適方策の可視化
import numpy as np
import matplotlib.pyplot as plt
# 上のコードで env, V_pi, policy_pi, V_vi, policy_vi が定義済みとする
def visualize_optimal_policy(env, V, policy, title):
"""最適方策と価値関数の可視化"""
fig, axes = plt.subplots(1, 2, figsize=(14, 6))
# 矢印の方向
arrow_dx = [0, 0, -0.3, 0.3] # 上, 下, 左, 右
arrow_dy = [-0.3, 0.3, 0, 0]
# --- 左: 最適方策 ---
ax = axes[0]
ax.set_title('Optimal Policy $\\pi^{*}$', fontsize=14)
ax.set_xlim(-0.5, env.cols - 0.5)
ax.set_ylim(-0.5, env.rows - 0.5)
ax.set_aspect('equal')
ax.invert_yaxis()
for i in range(env.rows + 1):
ax.axhline(i - 0.5, color='black', linewidth=1)
for j in range(env.cols + 1):
ax.axvline(j - 0.5, color='black', linewidth=1)
for s in range(env.n_states):
row, col = env.idx_to_state(s)
if env.is_terminal(row, col):
ax.text(col, row, 'G', ha='center', va='center',
fontsize=18, fontweight='bold', color='red')
continue
best_a = np.argmax(policy[s])
ax.annotate('', xy=(col + arrow_dx[best_a], row + arrow_dy[best_a]),
xytext=(col, row),
arrowprops=dict(arrowstyle='->', color='blue', lw=2.5))
ax.set_xticks(range(env.cols))
ax.set_yticks(range(env.rows))
# --- 右: 最適価値関数 ---
ax = axes[1]
ax.set_title('Optimal Value Function $V^{*}$', fontsize=14)
V_grid = V.reshape(env.rows, env.cols)
im = ax.imshow(V_grid, cmap='RdYlGn', interpolation='nearest')
for i in range(env.rows):
for j in range(env.cols):
ax.text(j, i, f'{V_grid[i, j]:.3f}', ha='center', va='center',
fontsize=11, fontweight='bold')
ax.set_xticks(range(env.cols))
ax.set_yticks(range(env.rows))
plt.colorbar(im, ax=ax)
plt.suptitle(title, fontsize=16)
plt.tight_layout()
plt.show()
visualize_optimal_policy(env, V_pi, policy_pi, "Policy Iteration Result")
visualize_optimal_policy(env, V_vi, policy_vi, "Value Iteration Result")
# 方策反復と価値反復の結果が一致することを確認
print(f"V* の最大差: {np.max(np.abs(V_pi - V_vi)):.2e}")
print(f"方策の一致: {np.allclose(policy_pi, policy_vi)}")
このコードにより、以下のことが確認できます。
- 方策反復はわずか数回の反復で最適方策に到達し、各反復で方策評価に多くの計算が費やされる
- 価値反復は多くの反復を必要とするが、各反復は軽量であり、指数的に収束する
- 両手法は同一の最適価値関数 $V^{*}$ と最適方策 $\pi^{*}$ に収束する
- 最適方策ではゴールに向かって最短経路を取る行動が選択される
まとめ
本記事では、強化学習における動的計画法について解説しました。
- 方策評価はベルマン期待方程式の反復適用であり、縮小写像定理により $V^{\pi}$ に収束する
- 方策改善定理は、貪欲方策が元の方策以上の性能を持つことを保証する
- 方策反復は評価と改善の交互適用であり、有限ステップで最適方策に収束する
- 価値反復はベルマン最適方程式の直接反復であり、$V^{*}$ に指数的に収束する
- 非同期DPは状態の更新順序を柔軟にし、大規模問題への適用を可能にする
次のステップとして、以下の記事も参考にしてください。