ベルマン方程式（Bellman equation）は、強化学習と動的計画法の中核をなす再帰的な方程式です。価値関数が満たすべき条件を数学的に記述したものであり、「現在の状態の価値 = 即時報酬 + 割引された次の状態の価値」という直感的な分解を厳密に定式化します。
ベルマン方程式を正しく理解することは、動的計画法（方策反復・価値反復）、モンテカルロ法、TD学習など、あらゆる強化学習アルゴリズムの基盤となります。本記事では、ベルマン期待方程式とベルマン最適方程式を条件付き期待値の操作から丁寧に導出し、縮小写像定理に基づく解の存在・一意性の証明のスケッチまで踏み込みます。
本記事の内容
- ベルマン期待方程式の導出（$V^{\pi}$ と $Q^{\pi}$）
- ベルマン最適方程式の導出（$V^{*}$ と $Q^{*}$）
- $V^{*}$ と $Q^{*}$ の関係
- 最適方策の存在定理
- ベルマン作用素と縮小写像定理（バナッハの不動点定理）
- 行列形式 $\bm{V} = \bm{R} + \gamma \bm{P} \bm{V}$
- Pythonによるグリッドワールドでの数値解法
前提知識
この記事を読む前に、以下の記事を読んでおくと理解が深まります。
ベルマン期待方程式の導出
状態価値関数のベルマン期待方程式
方策 $\pi$ のもとでの状態価値関数は $V^{\pi}(s) = \mathbb{E}_{\pi}[G_t \mid S_t = s]$ と定義されます。リターンの再帰的な分解 $G_t = R_{t+1} + \gamma G_{t+1}$ を用いて、この式を展開していきます。
$$ \begin{align} V^{\pi}(s) &= \mathbb{E}_{\pi}[G_t \mid S_t = s] \\ &= \mathbb{E}_{\pi}[R_{t+1} + \gamma G_{t+1} \mid S_t = s] \end{align} $$
ここで、$A_t$ と $S_{t+1}$ について条件分けを行います。まず行動 $A_t = a$ について全確率の法則を適用します。
$$ \begin{align} V^{\pi}(s) &= \sum_{a \in \mathcal{A}} \pi(a | s) \, \mathbb{E}_{\pi}[R_{t+1} + \gamma G_{t+1} \mid S_t = s, A_t = a] \end{align} $$
次に、$S_{t+1} = s’$ について条件分けを行います。
$$ \begin{align} V^{\pi}(s) &= \sum_{a \in \mathcal{A}} \pi(a | s) \sum_{s’ \in \mathcal{S}} P(s’ | s, a) \, \mathbb{E}_{\pi}[R_{t+1} + \gamma G_{t+1} \mid S_t = s, A_t = a, S_{t+1} = s’] \end{align} $$
$S_t = s, A_t = a, S_{t+1} = s’$ が与えられたとき、$R_{t+1}$ は確定値 $R(s, a, s’)$ になります。また、マルコフ性より $G_{t+1}$ の期待値は $S_{t+1} = s’$ のみに依存するため
$$ \mathbb{E}_{\pi}[G_{t+1} \mid S_t = s, A_t = a, S_{t+1} = s’] = \mathbb{E}_{\pi}[G_{t+1} \mid S_{t+1} = s’] = V^{\pi}(s’) $$
したがって
$$ \begin{align} 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] \end{align} $$
これが $V^{\pi}$ のベルマン期待方程式 です。
$$ \begin{equation} \boxed{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]} \end{equation} $$
行動価値関数のベルマン期待方程式
同様に、$Q^{\pi}(s,a) = \mathbb{E}_{\pi}[G_t \mid S_t = s, A_t = a]$ についてベルマン期待方程式を導出します。
$$ \begin{align} Q^{\pi}(s, a) &= \mathbb{E}_{\pi}[R_{t+1} + \gamma G_{t+1} \mid S_t = s, A_t = a] \\ &= \sum_{s’ \in \mathcal{S}} P(s’ | s, a) \, \mathbb{E}_{\pi}[R_{t+1} + \gamma G_{t+1} \mid S_t = s, A_t = a, S_{t+1} = s’] \\ &= \sum_{s’ \in \mathcal{S}} P(s’ | s, a) \left[ R(s, a, s’) + \gamma \, \mathbb{E}_{\pi}[G_{t+1} \mid S_{t+1} = s’] \right] \end{align} $$
$G_{t+1}$ の期待値を展開します。$S_{t+1} = s’$ から方策 $\pi$ に従って行動を選ぶため
$$ \mathbb{E}_{\pi}[G_{t+1} \mid S_{t+1} = s’] = V^{\pi}(s’) = \sum_{a’ \in \mathcal{A}} \pi(a’ | s’) Q^{\pi}(s’, a’) $$
したがって
$$ \begin{equation} \boxed{Q^{\pi}(s, a) = \sum_{s’ \in \mathcal{S}} P(s’ | s, a) \left[ R(s, a, s’) + \gamma \sum_{a’ \in \mathcal{A}} \pi(a’ | s’) Q^{\pi}(s’, a’) \right]} \end{equation} $$
ベルマン期待方程式の解釈
ベルマン期待方程式は次のことを述べています。
「ある状態の価値は、そこで取りうる行動と、行動の結果として遷移しうる次の状態に関する期待値で表される。具体的には、即時報酬と割引された次状態の価値の和の期待値である。」
これは動的計画法の原理そのものです。大きな最適化問題を、小さな部分問題の再帰的な関係として表現しています。
ベルマン最適方程式の導出
最適価値関数の定義
最適状態価値関数 $V^{*}(s)$ は、全ての方策の中で価値を最大化するものです。
$$ V^{*}(s) = \max_{\pi} V^{\pi}(s), \quad \forall s \in \mathcal{S} $$
同様に、最適行動価値関数 $Q^{*}(s,a)$ は
$$ Q^{*}(s, a) = \max_{\pi} Q^{\pi}(s, a), \quad \forall s \in \mathcal{S}, \forall a \in \mathcal{A} $$
と定義されます。
$V^{*}$ のベルマン最適方程式
最適方策 $\pi^{*}$ のもとでは、各状態 $s$ で $Q^{*}(s,a)$ を最大化する行動が選択されます。
$$ \begin{align} V^{*}(s) &= \max_{a \in \mathcal{A}} Q^{*}(s, a) \end{align} $$
$Q^{*}$ を展開すると
$$ \begin{align} V^{*}(s) &= \max_{a \in \mathcal{A}} Q^{*}(s, a) \\ &= \max_{a \in \mathcal{A}} \mathbb{E}[R_{t+1} + \gamma G_{t+1} \mid S_t = s, A_t = a, \pi^{*}] \\ &= \max_{a \in \mathcal{A}} \sum_{s’ \in \mathcal{S}} P(s’ | s, a) \left[ R(s, a, s’) + \gamma V^{*}(s’) \right] \end{align} $$
最後の行でマルコフ性を用い、最適方策のもとでは $\mathbb{E}_{\pi^{*}}[G_{t+1} \mid S_{t+1} = s’] = V^{*}(s’)$ であることを使いました。
$$ \begin{equation} \boxed{V^{*}(s) = \max_{a \in \mathcal{A}} \sum_{s’ \in \mathcal{S}} P(s’ | s, a) \left[ R(s, a, s’) + \gamma V^{*}(s’) \right]} \end{equation} $$
$Q^{*}$ のベルマン最適方程式
$Q^{*}(s,a)$ についても同様に導出します。
$$ \begin{align} Q^{*}(s, a) &= \mathbb{E}[R_{t+1} + \gamma G_{t+1} \mid S_t = s, A_t = a, \pi^{*}] \\ &= \sum_{s’ \in \mathcal{S}} P(s’ | s, a) \left[ R(s, a, s’) + \gamma \, \mathbb{E}_{\pi^{*}}[G_{t+1} \mid S_{t+1} = s’] \right] \\ &= \sum_{s’ \in \mathcal{S}} P(s’ | s, a) \left[ R(s, a, s’) + \gamma V^{*}(s’) \right] \\ &= \sum_{s’ \in \mathcal{S}} P(s’ | s, a) \left[ R(s, a, s’) + \gamma \max_{a’ \in \mathcal{A}} Q^{*}(s’, a’) \right] \end{align} $$
3行目から4行目で $V^{*}(s’) = \max_{a’} Q^{*}(s’, a’)$ を代入しました。
$$ \begin{equation} \boxed{Q^{*}(s, a) = \sum_{s’ \in \mathcal{S}} P(s’ | s, a) \left[ R(s, a, s’) + \gamma \max_{a’ \in \mathcal{A}} Q^{*}(s’, a’) \right]} \end{equation} $$
$V^{*}$ と $Q^{*}$ の関係
ベルマン最適方程式から、$V^{*}$ と $Q^{*}$ は次の関係で結ばれます。
$$ V^{*}(s) = \max_{a \in \mathcal{A}} Q^{*}(s, a) $$
$$ Q^{*}(s, a) = \sum_{s’ \in \mathcal{S}} P(s’ | s, a) \left[ R(s, a, s’) + \gamma V^{*}(s’) \right] $$
$V^{*}$ が分かれば $Q^{*}$ は直ちに計算でき、$Q^{*}$ が分かれば $V^{*}$ も直ちに求まります。
最適方策の存在定理
有限MDPにおいて、以下の定理が成り立ちます。
定理（最適方策の存在）: 有限MDP $(\mathcal{S}, \mathcal{A}, P, R, \gamma)$ （$\gamma < 1$）に対して、以下を満たす決定的定常方策 $\pi^{*}$ が少なくとも1つ存在する。
$$ V^{\pi^{*}}(s) = V^{*}(s) = \max_{\pi} V^{\pi}(s), \quad \forall s \in \mathcal{S} $$
証明の概略:
$Q^{*}(s,a)$ が求まったとき、貪欲方策
$$ \pi^{*}(s) = \arg\max_{a \in \mathcal{A}} Q^{*}(s, a) $$
を構成します。この方策のもとでの価値関数がベルマン最適方程式を満たすことを示します。
$$ \begin{align} V^{\pi^{*}}(s) &= Q^{*}(s, \pi^{*}(s)) \\ &= \max_{a} Q^{*}(s, a) \\ &= V^{*}(s) \end{align} $$
$Q^{*}$ の存在自体は、次節で説明するベルマン最適作用素の不動点定理によって保証されます。有限MDPでは $|\mathcal{S}|$ と $|\mathcal{A}|$ が有限なので、$\arg\max$ で最大値を達成する行動が必ず存在し、決定的方策として構成できます。
ベルマン作用素と縮小写像定理
ベルマン方程式の解の存在と一意性を厳密に保証するのが、バナッハの不動点定理（縮小写像定理）です。
ベルマン期待作用素
方策 $\pi$ に対するベルマン期待作用素 $\mathcal{T}^{\pi}$ を次のように定義します。任意の価値関数 $V: \mathcal{S} \to \mathbb{R}$ に対して
$$ (\mathcal{T}^{\pi} V)(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(s’) \right] $$
$V^{\pi}$ はこの作用素の不動点です。つまり
$$ \mathcal{T}^{\pi} V^{\pi} = V^{\pi} $$
ベルマン最適作用素
同様に、ベルマン最適作用素 $\mathcal{T}^{*}$ を定義します。
$$ (\mathcal{T}^{*} V)(s) = \max_{a \in \mathcal{A}} \sum_{s’ \in \mathcal{S}} P(s’|s,a) \left[ R(s,a,s’) + \gamma V(s’) \right] $$
$V^{*}$ は $\mathcal{T}^{*}$ の不動点です。
縮小写像であることの証明
定理: $\gamma < 1$ のとき、$\mathcal{T}^{\pi}$ と $\mathcal{T}^{*}$ はいずれも $\sup$-ノルム $\|V\|_{\infty} = \max_{s} |V(s)|$ のもとで $\gamma$-縮小写像である。
証明（$\mathcal{T}^{\pi}$ の場合）: 任意の $V_1, V_2: \mathcal{S} \to \mathbb{R}$ に対して
$$ \begin{align} |(\mathcal{T}^{\pi} V_1)(s) – (\mathcal{T}^{\pi} V_2)(s)| &= \left| \sum_{a} \pi(a|s) \sum_{s’} P(s’|s,a) \gamma \left[ V_1(s’) – V_2(s’) \right] \right| \\ &\leq \sum_{a} \pi(a|s) \sum_{s’} P(s’|s,a) \gamma |V_1(s’) – V_2(s’)| \\ &\leq \gamma \|V_1 – V_2\|_{\infty} \sum_{a} \pi(a|s) \sum_{s’} P(s’|s,a) \\ &= \gamma \|V_1 – V_2\|_{\infty} \end{align} $$
1行目で $R(s,a,s’)$ の項はキャンセルしました。2行目で三角不等式を適用しました。3行目で $|V_1(s’) – V_2(s’)| \leq \|V_1 – V_2\|_{\infty}$ を用いました。4行目で $\sum_a \pi(a|s) = 1$ かつ $\sum_{s’} P(s’|s,a) = 1$ を用いました。
全ての $s$ について成り立つので
$$ \|\mathcal{T}^{\pi} V_1 – \mathcal{T}^{\pi} V_2\|_{\infty} \leq \gamma \|V_1 – V_2\|_{\infty} $$
$\gamma < 1$ なので、$\mathcal{T}^{\pi}$ は $\gamma$-縮小写像です。
$\mathcal{T}^{*}$ の場合 も同様に示せます。$\max$ 演算子に対しては $|\max_a f(a) – \max_a g(a)| \leq \max_a |f(a) – g(a)|$ を用いれば、上と同じ議論が適用できます。
バナッハの不動点定理の適用
バナッハの不動点定理: 完備距離空間上の縮小写像は、唯一の不動点を持つ。さらに、任意の初期値から縮小写像を繰り返し適用すると、その不動点に収束する。
$\mathbb{R}^{|\mathcal{S}|}$ は $\sup$-ノルムのもとで完備距離空間です。したがって
- $\mathcal{T}^{\pi}$ の不動点 $V^{\pi}$ は存在し、かつ一意である
- $\mathcal{T}^{*}$ の不動点 $V^{*}$ は存在し、かつ一意である
- 任意の初期値 $V_0$ に対して $V_{k+1} = \mathcal{T} V_k$ は $V^{\pi}$ または $V^{*}$ に収束する
さらに、収束の速度について
$$ \|V_k – V^{*}\|_{\infty} \leq \gamma^k \|V_0 – V^{*}\|_{\infty} $$
が成り立ちます。これは指数的な収束速度を保証しています。
行列形式のベルマン方程式
有限MDPで方策 $\pi$ が固定されているとき、ベルマン期待方程式は行列形式で書くことができます。
方策に基づく遷移行列
方策 $\pi$ のもとでの状態遷移確率行列 $\bm{P}^{\pi} \in \mathbb{R}^{|\mathcal{S}| \times |\mathcal{S}|}$ を定義します。
$$ P^{\pi}_{ss’} = \sum_{a \in \mathcal{A}} \pi(a|s) P(s’|s,a) $$
これは、方策 $\pi$ に従って行動を選んだときに、状態 $s$ から $s’$ に遷移する確率です。
方策に基づく報酬ベクトル
同様に、報酬ベクトル $\bm{R}^{\pi} \in \mathbb{R}^{|\mathcal{S}|}$ を定義します。
$$ R^{\pi}_s = \sum_{a \in \mathcal{A}} \pi(a|s) \sum_{s’ \in \mathcal{S}} P(s’|s,a) R(s,a,s’) $$
行列形式
ベルマン期待方程式を全状態についてまとめると
$$ \bm{V}^{\pi} = \bm{R}^{\pi} + \gamma \bm{P}^{\pi} \bm{V}^{\pi} $$
ここで $\bm{V}^{\pi} = (V^{\pi}(s_1), \dots, V^{\pi}(s_n))^{\top}$ は価値関数を並べたベクトルです。
解析解
この連立一次方程式を $\bm{V}^{\pi}$ について解くと
$$ \begin{align} \bm{V}^{\pi} &= \bm{R}^{\pi} + \gamma \bm{P}^{\pi} \bm{V}^{\pi} \\ \bm{V}^{\pi} – \gamma \bm{P}^{\pi} \bm{V}^{\pi} &= \bm{R}^{\pi} \\ (\bm{I} – \gamma \bm{P}^{\pi}) \bm{V}^{\pi} &= \bm{R}^{\pi} \\ \bm{V}^{\pi} &= (\bm{I} – \gamma \bm{P}^{\pi})^{-1} \bm{R}^{\pi} \end{align} $$
$\gamma < 1$ のとき、$\bm{I} - \gamma \bm{P}^{\pi}$ は正則であることが保証されます（$\bm{P}^{\pi}$ の固有値の絶対値は1以下であるため、$\gamma \bm{P}^{\pi}$ の固有値の絶対値は $\gamma < 1$ 以下となり、$\bm{I} - \gamma \bm{P}^{\pi}$ の固有値は全て0でなくなるため）。
この解析解は $O(|\mathcal{S}|^3)$ の計算量を要するため、状態数が大きい場合は反復法が用いられます。
Pythonでの実装
グリッドワールドでのベルマン方程式の数値解法
解析解（行列逆行列）と反復法の両方でベルマン方程式を解き、結果が一致することを確認します。
import numpy as np
import matplotlib.pyplot as plt
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)]
def solve_bellman_matrix(env, policy):
"""
行列形式 V = (I - γP^π)^{-1} R^π でベルマン方程式を解く（解析解）
"""
n = env.n_states
# 遷移行列 P^π と報酬ベクトル R^π の構築
P_pi = np.zeros((n, n))
R_pi = np.zeros(n)
for s in range(n):
row, col = env.idx_to_state(s)
if env.is_terminal(row, col):
continue
for a in env.actions:
pi_a = policy[s, a]
for prob, next_row, next_col, reward in env.get_transition_prob(row, col, a):
s_next = env.state_to_idx(next_row, next_col)
P_pi[s, s_next] += pi_a * prob
R_pi[s] += pi_a * prob * reward
# 解析解: V = (I - γP)^{-1} R
I = np.eye(n)
V = np.linalg.solve(I - env.gamma * P_pi, R_pi)
return V
def solve_bellman_iterative(env, policy, theta=1e-10, max_iter=100000):
"""
反復法でベルマン期待方程式を解く（方策評価）
"""
n = env.n_states
V = np.zeros(n)
history = []
for iteration in range(max_iter):
V_new = np.zeros(n)
for s in range(n):
row, col = env.idx_to_state(s)
if env.is_terminal(row, col):
continue
for a in env.actions:
pi_a = policy[s, a]
for prob, next_row, next_col, reward in env.get_transition_prob(row, col, a):
s_next = env.state_to_idx(next_row, next_col)
V_new[s] += pi_a * prob * (reward + env.gamma * V[s_next])
delta = np.max(np.abs(V_new - V))
history.append(delta)
V = V_new
if delta < theta:
print(f"反復法: {iteration + 1} 回で収束（Δ < {theta}）")
break
return V, history
def solve_bellman_optimal(env, theta=1e-10, max_iter=100000):
"""
価値反復法でベルマン最適方程式を解く
V*(s) = max_a Σ_{s'} P(s'|s,a)[R(s,a,s') + γV*(s')]
"""
n = env.n_states
V = np.zeros(n)
history = []
for iteration in range(max_iter):
V_new = np.zeros(n)
for s in range(n):
row, col = env.idx_to_state(s)
if env.is_terminal(row, col):
continue
q_values = []
for a in env.actions:
q = 0
for prob, next_row, next_col, reward in env.get_transition_prob(row, col, a):
s_next = env.state_to_idx(next_row, next_col)
q += prob * (reward + env.gamma * V[s_next])
q_values.append(q)
V_new[s] = max(q_values)
delta = np.max(np.abs(V_new - V))
history.append(delta)
V = V_new
if delta < theta:
print(f"価値反復法: {iteration + 1} 回で収束（Δ < {theta}）")
break
return V, history
# --- メイン実行 ---
env = GridWorld(rows=4, cols=4, gamma=0.99)
# ランダム方策
policy = np.ones((env.n_states, env.n_actions)) / env.n_actions
# 方法1: 行列の逆行列による解析解
V_matrix = solve_bellman_matrix(env, policy)
print("【解析解（行列形式）】")
print(V_matrix.reshape(env.rows, env.cols).round(4))
# 方法2: 反復法
V_iter, history_iter = solve_bellman_iterative(env, policy)
print("\n【反復法】")
print(V_iter.reshape(env.rows, env.cols).round(4))
# 解析解と反復法の誤差
print(f"\n解析解と反復法の最大誤差: {np.max(np.abs(V_matrix - V_iter)):.2e}")
# 方法3: ベルマン最適方程式（価値反復法）
V_opt, history_opt = solve_bellman_optimal(env)
print("\n【最適価値関数 V*（価値反復法）】")
print(V_opt.reshape(env.rows, env.cols).round(4))
収束過程の可視化
反復法の収束過程をプロットして、縮小写像定理が保証する指数的収束を確認します。
import numpy as np
import matplotlib.pyplot as plt
# 上のコードで history_iter, history_opt が得られているとする
# ここでは再計算の例を示す
# --- 収束過程の可視化 ---
fig, axes = plt.subplots(1, 2, figsize=(14, 5))
# ベルマン期待方程式の反復法の収束
ax = axes[0]
ax.semilogy(history_iter, linewidth=2, color='blue')
ax.set_xlabel('Iteration', fontsize=12)
ax.set_ylabel('Max |V_new - V_old|', fontsize=12)
ax.set_title('Bellman Expectation Equation\n(Iterative Policy Evaluation)', fontsize=13)
ax.grid(True, alpha=0.3)
# ベルマン最適方程式の価値反復法の収束
ax = axes[1]
ax.semilogy(history_opt, linewidth=2, color='red')
ax.set_xlabel('Iteration', fontsize=12)
ax.set_ylabel('Max |V_new - V_old|', fontsize=12)
ax.set_title('Bellman Optimality Equation\n(Value Iteration)', fontsize=13)
ax.grid(True, alpha=0.3)
plt.tight_layout()
plt.show()
解析解と反復法の比較
import numpy as np
import matplotlib.pyplot as plt
# V_matrix: 解析解, V_opt: 最適価値関数 を用いる
# (上のコードで計算済みとする)
fig, axes = plt.subplots(1, 3, figsize=(18, 5))
titles = [
'$V^{\\pi}$ (Analytic Solution)',
'$V^{\\pi}$ (Iterative Solution)',
'$V^{*}$ (Optimal Value Function)'
]
data_list = [V_matrix, V_iter, V_opt]
for ax, V_data, title in zip(axes, data_list, titles):
V_grid = V_data.reshape(4, 4)
im = ax.imshow(V_grid, cmap='RdYlGn', interpolation='nearest')
for i in range(4):
for j in range(4):
ax.text(j, i, f'{V_grid[i, j]:.3f}', ha='center', va='center',
fontsize=11, fontweight='bold')
ax.set_title(title, fontsize=13)
ax.set_xticks(range(4))
ax.set_yticks(range(4))
plt.colorbar(im, ax=ax)
plt.suptitle('Bellman Equation Solutions Comparison', fontsize=15)
plt.tight_layout()
plt.show()
このコードでは以下のことが確認できます。
- 解析解と反復法の一致: 行列の逆行列 $(\bm{I} – \gamma \bm{P}^{\pi})^{-1} \bm{R}^{\pi}$ による解析解と、ベルマン期待方程式の反復適用による数値解が、機械精度の範囲で一致する
- 縮小写像による指数的収束: 反復法の誤差が指数的に減少する様子を対数プロットで確認できる
- 最適価値関数: ベルマン最適方程式を解くことで、ランダム方策より大幅に高い最適価値 $V^{*}$ が得られる
まとめ
本記事では、ベルマン方程式の導出と解釈について解説しました。
- ベルマン期待方程式は条件付き期待値の全確率の法則による分解から導出され、$V^{\pi}(s) = \sum_a \pi(a|s) \sum_{s’} P(s’|s,a)[R(s,a,s’) + \gamma V^{\pi}(s’)]$ と表される
- ベルマン最適方程式は max 演算子が加わり、$V^{*}(s) = \max_a \sum_{s’} P(s’|s,a)[R(s,a,s’) + \gamma V^{*}(s’)]$ と表される
- ベルマン作用素は $\gamma$-縮小写像であり、バナッハの不動点定理により解の存在・一意性が保証される
- 行列形式 $\bm{V} = (\bm{I} – \gamma \bm{P})^{-1} \bm{R}$ として解析的に解くことも、反復法で数値的に解くこともできる
次のステップとして、以下の記事も参考にしてください。