強化学習の理論的基盤となるのがマルコフ決定過程（MDP）です。MDPはエージェントが環境と相互作用しながら最適な行動を学習する問題を数学的に定式化するフレームワークであり、ロボット制御、ゲームAI、推薦システムなど幅広い応用を持ちます。
本記事の内容
- MDPの構成要素
- マルコフ性
- 方策（policy）
- 累積報酬と割引率
- 状態価値関数と行動価値関数
- Pythonでの実装
前提知識
この記事を読む前に、以下の知識があると理解が深まります。
- 確率の基礎（条件付き確率、期待値）
- 行列演算の基礎
MDPとは
マルコフ決定過程（Markov Decision Process, MDP）は、逐次的な意思決定問題を定式化するための数学的枠組みです。MDPは次の5つの要素の組で定義されます。
$$ \boxed{\text{MDP} = (S, A, P, R, \gamma)} $$
各要素の意味は以下の通りです。
| 要素 | 記号 | 説明 |
|---|---|---|
| 状態空間 | $S$ | エージェントが取りうる全ての状態の集合 |
| 行動空間 | $A$ | エージェントが取りうる全ての行動の集合 |
| 遷移確率 | $P$ | $P(s’|s, a)$: 状態 $s$ で行動 $a$ を取ったとき状態 $s’$ に遷移する確率 |
| 報酬関数 | $R$ | $R(s, a, s’)$: 状態遷移に伴う即時報酬 |
| 割引率 | $\gamma$ | $0 \leq \gamma \leq 1$: 将来の報酬の割引係数 |
マルコフ性
MDPの「マルコフ」とは、マルコフ性（Markov property）を満たすことを意味します。
$$ P(S_{t+1} | S_t, A_t, S_{t-1}, A_{t-1}, \dots, S_0, A_0) = P(S_{t+1} | S_t, A_t) $$
つまり、次の状態は現在の状態と行動のみに依存し、過去の履歴には依存しません。「未来は現在のみで決まる」という性質です。
方策
方策（policy）$\pi$ は、エージェントの行動選択規則です。
確率的方策
$$ \pi(a|s) = P(A_t = a | S_t = s) $$
各状態 $s$ で行動 $a$ を選ぶ確率を定めます。
決定的方策
$$ a = \pi(s) $$
各状態に対して一意に行動を定めます。
累積報酬と割引率
エージェントの目標は、将来にわたる報酬の総和（累積報酬）を最大化することです。時刻 $t$ からの累積報酬（収益: return）は:
$$ G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1} $$
割引率 $\gamma$ の役割は:
- $\gamma = 0$: 目先の報酬のみを重視（近視的）
- $\gamma = 1$: 将来の報酬を現在と同等に評価（遠視的）
- $0 < \gamma < 1$: 将来の報酬を割り引いて評価
$\gamma < 1$ とすることで、無限の時間ステップがあっても $G_t$ が有界になります。報酬が $|R_t| \leq R_{\max}$ で有界なら:
$$ |G_t| \leq \sum_{k=0}^{\infty} \gamma^k R_{\max} = \frac{R_{\max}}{1 – \gamma} $$
収益の再帰的表現
$$ G_t = R_{t+1} + \gamma G_{t+1} $$
この再帰的構造がベルマン方程式の基礎となります。
状態価値関数
方策 $\pi$ のもとでの状態価値関数（state-value function）$V^\pi$ は、状態 $s$ から方策 $\pi$ に従ったときの期待収益です。
$$ \boxed{V^\pi(s) = E_\pi[G_t | S_t = s] = E_\pi\left[\sum_{k=0}^{\infty} \gamma^k R_{t+k+1} \bigg| S_t = s\right]} $$
これを展開すると:
$$ \begin{align} V^\pi(s) &= E_\pi[R_{t+1} + \gamma G_{t+1} | S_t = s] \\ &= \sum_{a} \pi(a|s) \sum_{s’} P(s’|s, a) \left[R(s, a, s’) + \gamma V^\pi(s’)\right] \end{align} $$
これがベルマン期待方程式（状態価値関数版）です。
行動価値関数
方策 $\pi$ のもとでの行動価値関数（action-value function）$Q^\pi$ は、状態 $s$ で行動 $a$ を取り、その後は方策 $\pi$ に従ったときの期待収益です。
$$ \boxed{Q^\pi(s, a) = E_\pi[G_t | S_t = s, A_t = a]} $$
展開すると:
$$ Q^\pi(s, a) = \sum_{s’} P(s’|s, a) \left[R(s, a, s’) + \gamma \sum_{a’} \pi(a’|s’) Q^\pi(s’, a’)\right] $$
$V^\pi$ と $Q^\pi$ の関係
$$ V^\pi(s) = \sum_{a} \pi(a|s) Q^\pi(s, a) $$
$$ Q^\pi(s, a) = \sum_{s’} P(s’|s, a) \left[R(s, a, s’) + \gamma V^\pi(s’)\right] $$
Pythonでの実装
グリッドワールドMDPの実装
import numpy as np
import matplotlib.pyplot as plt
class GridWorldMDP:
"""4x4 グリッドワールド MDP"""
def __init__(self, size=4, gamma=0.9):
self.size = size
self.n_states = size * size
self.n_actions = 4 # 上, 下, 左, 右
self.gamma = gamma
# 行動の定義: 上, 下, 左, 右
self.actions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
self.action_names = ['Up', 'Down', 'Left', 'Right']
# 終端状態（左上と右下）
self.terminal_states = [0, self.n_states - 1]
# 遷移確率と報酬を構築
self.P = np.zeros((self.n_states, self.n_actions, self.n_states))
self.R = np.zeros((self.n_states, self.n_actions, self.n_states))
self._build_transitions()
def _state_to_pos(self, s):
return s // self.size, s % self.size
def _pos_to_state(self, r, c):
return r * self.size + c
def _build_transitions(self):
for s in range(self.n_states):
if s in self.terminal_states:
# 終端状態: 自分自身に遷移、報酬0
for a in range(self.n_actions):
self.P[s, a, s] = 1.0
self.R[s, a, s] = 0.0
continue
r, c = self._state_to_pos(s)
for a, (dr, dc) in enumerate(self.actions):
nr, nc = r + dr, c + dc
# 壁にぶつかる場合は元の位置に留まる
if 0 <= nr < self.size and 0 <= nc < self.size:
s_next = self._pos_to_state(nr, nc)
else:
s_next = s
self.P[s, a, s_next] = 1.0
self.R[s, a, s_next] = -1.0 # 各ステップに-1の報酬
def evaluate_policy(self, pi, tol=1e-8, max_iter=1000):
"""方策評価: 方策πのもとで状態価値関数V^πを計算"""
V = np.zeros(self.n_states)
for iteration in range(max_iter):
V_new = np.zeros(self.n_states)
for s in range(self.n_states):
for a in range(self.n_actions):
for s_next in range(self.n_states):
V_new[s] += pi[s, a] * self.P[s, a, s_next] * (
self.R[s, a, s_next] + self.gamma * V[s_next]
)
if np.max(np.abs(V_new - V)) < tol:
print(f"方策評価: {iteration + 1} 回で収束")
return V_new
V = V_new
return V
def compute_q_from_v(self, V):
"""V^πからQ^πを計算"""
Q = np.zeros((self.n_states, self.n_actions))
for s in range(self.n_states):
for a in range(self.n_actions):
for s_next in range(self.n_states):
Q[s, a] += self.P[s, a, s_next] * (
self.R[s, a, s_next] + self.gamma * V[s_next]
)
return Q
# --- MDPの構築と方策評価 ---
mdp = GridWorldMDP(size=4, gamma=0.9)
# ランダム方策（一様）
pi_random = np.ones((mdp.n_states, mdp.n_actions)) / mdp.n_actions
# 方策評価
V = mdp.evaluate_policy(pi_random)
Q = mdp.compute_q_from_v(V)
# 結果の可視化
fig, axes = plt.subplots(1, 2, figsize=(14, 5))
# 状態価値関数
V_grid = V.reshape(mdp.size, mdp.size)
im1 = axes[0].imshow(V_grid, cmap='RdYlGn', interpolation='nearest')
for i in range(mdp.size):
for j in range(mdp.size):
axes[0].text(j, i, f'{V_grid[i, j]:.2f}',
ha='center', va='center', fontsize=12, fontweight='bold')
axes[0].set_title(r'State-Value Function $V^\pi$ (Random Policy)', fontsize=13)
plt.colorbar(im1, ax=axes[0])
# 行動価値関数（状態(1,1)の例）
state_example = 5 # 状態(1,1)
axes[1].bar(mdp.action_names, Q[state_example], color='steelblue')
axes[1].set_title(f'Action-Value Q(s={state_example}, a) at state (1,1)', fontsize=13)
axes[1].set_ylabel('Q value', fontsize=12)
axes[1].grid(True, alpha=0.3, axis='y')
plt.tight_layout()
plt.show()
MDP要素の可視化
import numpy as np
import matplotlib.pyplot as plt
# --- MDPの遷移確率の可視化 ---
mdp = GridWorldMDP(size=4, gamma=0.9)
fig, axes = plt.subplots(1, 4, figsize=(16, 4))
for a_idx, (ax, name) in enumerate(zip(axes, mdp.action_names)):
# 遷移確率行列
P_a = mdp.P[:, a_idx, :]
im = ax.imshow(P_a, cmap='Blues', vmin=0, vmax=1)
ax.set_title(f'P(s\'|s, {name})', fontsize=12)
ax.set_xlabel('Next state s\'', fontsize=10)
ax.set_ylabel('Current state s', fontsize=10)
plt.suptitle('Transition Probability Matrices', fontsize=14)
plt.tight_layout()
plt.show()
# --- 割引率と累積報酬の関係 ---
gammas = [0.0, 0.5, 0.9, 0.99]
T = 50
rewards = np.ones(T) # 毎ステップ報酬1
fig, ax = plt.subplots(figsize=(10, 5))
for gamma in gammas:
discounted = [gamma**k * rewards[k] for k in range(T)]
cumulative = np.cumsum(discounted)
ax.plot(range(T), cumulative, linewidth=2,
label=f'γ={gamma} (sum={sum(discounted):.2f})')
ax.set_xlabel('Time step', fontsize=12)
ax.set_ylabel('Cumulative discounted reward', fontsize=12)
ax.set_title('Effect of Discount Factor γ', fontsize=13)
ax.legend(fontsize=11)
ax.grid(True, alpha=0.3)
plt.tight_layout()
plt.show()
まとめ
本記事では、マルコフ決定過程（MDP）の定式化について解説しました。
- MDP = $(S, A, P, R, \gamma)$: 状態空間、行動空間、遷移確率、報酬関数、割引率
- マルコフ性: 次の状態は現在の状態と行動のみに依存する
- 方策 $\pi(a|s)$: エージェントの行動選択規則
- 状態価値関数 $V^\pi(s)$: 状態 $s$ からの期待収益
- 行動価値関数 $Q^\pi(s, a)$: 状態 $s$ で行動 $a$ を取ったときの期待収益
次のステップとして、以下の記事も参考にしてください。