動的計画法による方法（価値反復法、方策反復法）は環境モデル（遷移確率 $P$ と報酬関数 $R$）が完全に既知であることを前提とします。しかし現実の多くの問題ではモデルが未知です。TD学習（Temporal Difference Learning）はモデルフリーな手法であり、環境との直接的なインタラクションから価値関数を学習します。本記事では、代表的なTD学習手法であるQ学習とSARSAを解説します。
本記事の内容
- TD学習の基本概念
- Q学習（off-policy）
- SARSA（on-policy）
- ε-greedy方策
- Q学習とSARSAの違い
- グリッドワールドでのPython実装
前提知識
この記事を読む前に、以下の記事を読んでおくと理解が深まります。
TD学習の基本概念
モンテカルロ法 vs TD学習
モンテカルロ法はエピソード終了まで待ち、実際の収益 $G_t$ で価値関数を更新します。
$$ V(S_t) \leftarrow V(S_t) + \alpha \left[G_t – V(S_t)\right] $$
TD学習はエピソード終了を待たず、次の時刻の推定値を使って更新します。
$$ V(S_t) \leftarrow V(S_t) + \alpha \left[R_{t+1} + \gamma V(S_{t+1}) – V(S_t)\right] $$
ここで $R_{t+1} + \gamma V(S_{t+1})$ をTD目標（TD target）、$\delta_t = R_{t+1} + \gamma V(S_{t+1}) – V(S_t)$ をTD誤差（TD error）と呼びます。
TD学習の利点:
- エピソードの途中でも更新できる（オンライン学習）
- エピソードが終了しない（連続的な）タスクにも適用できる
- モンテカルロ法より分散が小さい（ただしバイアスを持つ）
ε-greedy方策
Q値を学習する際、探索（exploration）と活用（exploitation）のバランスが重要です。ε-greedy方策は最も単純な探索戦略です。
$$ \pi(a|s) = \begin{cases} 1 – \varepsilon + \frac{\varepsilon}{|A|} & \text{if } a = \arg\max_{a’} Q(s, a’) \\ \frac{\varepsilon}{|A|} & \text{otherwise} \end{cases} $$
- 確率 $1 – \varepsilon$ で最良の行動（活用）
- 確率 $\varepsilon$ でランダムな行動（探索）
$\varepsilon$ を時間とともに減衰させることで、初期は探索を重視し、学習が進むにつれて活用に移行します。
Q学習（off-policy TD制御）
Q学習（Q-learning）はWatkinsが1989年に提案したアルゴリズムで、行動価値関数 $Q(s, a)$ を直接学習します。
更新則
$$ \boxed{Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha \left[R_{t+1} + \gamma \max_{a’} Q(S_{t+1}, a’) – Q(S_t, A_t)\right]} $$
TD目標に $\max_{a’} Q(S_{t+1}, a’)$ を使う点が特徴です。これは最適方策に対するQ値の推定を用いることに相当します。
off-policyとは
Q学習はoff-policyな手法です。つまり:
- 行動方策（behavior policy）: 実際に環境で行動を選ぶ方策（例: ε-greedy）
- 目標方策（target policy）: 学習の対象となる方策（greedy方策: $\max_a Q(s,a)$）
行動方策と目標方策が異なるため「off-policy」と呼ばれます。
収束性
適切な条件（全ての $(s, a)$ ペアが無限回訪問される、学習率が $\sum \alpha = \infty$, $\sum \alpha^2 < \infty$ を満たす）のもとで、Q学習は最適行動価値関数 $Q^*$ に確率1で収束します。
SARSA（on-policy TD制御）
SARSAは、名前の通り $(S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1})$ の5つ組を用いる手法です。
更新則
$$ \boxed{Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha \left[R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) – Q(S_t, A_t)\right]} $$
Q学習との違いは、TD目標に $Q(S_{t+1}, A_{t+1})$（次の状態で実際に選んだ行動のQ値）を使う点です。
on-policyとは
SARSAはon-policyな手法です。行動方策と目標方策が同一です。ε-greedy方策で行動し、そのε-greedy方策自体のQ値を学習します。
Q学習とSARSAの比較
| Q学習 | SARSA | |
|---|---|---|
| 種別 | off-policy | on-policy |
| TD目標 | $R + \gamma \max_{a’} Q(s’, a’)$ | $R + \gamma Q(s’, a’)$ |
| 学習対象 | 最適方策のQ値 | 現在の方策のQ値 |
| 探索の影響 | TD目標に影響しない | TD目標に影響する |
| 振る舞い | 大胆（危険な状態の近くも通る） | 慎重（危険を避ける傾向） |
Pythonでの実装
Cliff Walkingでの比較
import numpy as np
import matplotlib.pyplot as plt
class CliffWalking:
"""Cliff Walking 環境
4x12 グリッド。左下がスタート、右下がゴール。
下辺の崖に落ちると大きなペナルティ。
"""
def __init__(self):
self.rows = 4
self.cols = 12
self.start = (3, 0)
self.goal = (3, 11)
# 崖: 下辺のスタートとゴール以外
self.cliff = [(3, c) for c in range(1, 11)]
self.actions = [(-1, 0), (1, 0), (0, -1), (0, 1)] # 上下左右
self.n_actions = 4
def reset(self):
self.state = self.start
return self.state
def step(self, action):
dr, dc = self.actions[action]
r, c = self.state
nr = max(0, min(self.rows - 1, r + dr))
nc = max(0, min(self.cols - 1, c + dc))
next_state = (nr, nc)
if next_state in self.cliff:
# 崖に落ちた
return self.start, -100, False
elif next_state == self.goal:
self.state = next_state
return next_state, -1, True
else:
self.state = next_state
return next_state, -1, False
def epsilon_greedy(Q, state, epsilon, n_actions):
"""ε-greedy方策"""
if np.random.random() < epsilon:
return np.random.randint(n_actions)
else:
return np.argmax(Q[state])
def q_learning(env, n_episodes=500, alpha=0.5, gamma=1.0, epsilon=0.1):
"""Q学習"""
Q = {}
for r in range(env.rows):
for c in range(env.cols):
Q[(r, c)] = np.zeros(env.n_actions)
rewards_per_episode = []
for episode in range(n_episodes):
state = env.reset()
total_reward = 0
while True:
action = epsilon_greedy(Q, state, epsilon, env.n_actions)
next_state, reward, done = env.step(action)
total_reward += reward
# Q学習の更新（max を使う）
td_target = reward + gamma * np.max(Q[next_state])
td_error = td_target - Q[state][action]
Q[state][action] += alpha * td_error
state = next_state
if done:
break
rewards_per_episode.append(total_reward)
return Q, rewards_per_episode
def sarsa(env, n_episodes=500, alpha=0.5, gamma=1.0, epsilon=0.1):
"""SARSA"""
Q = {}
for r in range(env.rows):
for c in range(env.cols):
Q[(r, c)] = np.zeros(env.n_actions)
rewards_per_episode = []
for episode in range(n_episodes):
state = env.reset()
action = epsilon_greedy(Q, state, epsilon, env.n_actions)
total_reward = 0
while True:
next_state, reward, done = env.step(action)
total_reward += reward
next_action = epsilon_greedy(Q, next_state, epsilon, env.n_actions)
# SARSAの更新（次の行動の Q 値を使う）
td_target = reward + gamma * Q[next_state][next_action]
td_error = td_target - Q[state][action]
Q[state][action] += alpha * td_error
state = next_state
action = next_action
if done:
break
rewards_per_episode.append(total_reward)
return Q, rewards_per_episode
# --- 実行と比較 ---
np.random.seed(42)
env = CliffWalking()
Q_ql, rewards_ql = q_learning(env, n_episodes=500, alpha=0.5, gamma=1.0, epsilon=0.1)
Q_sarsa, rewards_sarsa = sarsa(env, n_episodes=500, alpha=0.5, gamma=1.0, epsilon=0.1)
# --- 可視化 ---
fig, axes = plt.subplots(2, 2, figsize=(16, 10))
# 学習曲線（移動平均）
window = 20
rewards_ql_smooth = np.convolve(rewards_ql, np.ones(window)/window, mode='valid')
rewards_sarsa_smooth = np.convolve(rewards_sarsa, np.ones(window)/window, mode='valid')
axes[0, 0].plot(rewards_ql_smooth, 'b-', linewidth=1.5, label='Q-Learning', alpha=0.8)
axes[0, 0].plot(rewards_sarsa_smooth, 'r-', linewidth=1.5, label='SARSA', alpha=0.8)
axes[0, 0].set_xlabel('Episode', fontsize=12)
axes[0, 0].set_ylabel('Total Reward (moving avg)', fontsize=12)
axes[0, 0].set_title('Learning Curves: Q-Learning vs SARSA', fontsize=13)
axes[0, 0].legend(fontsize=11)
axes[0, 0].grid(True, alpha=0.3)
# 方策の可視化
action_symbols = ['↑', '↓', '←', '→']
for ax_idx, (Q, title) in enumerate([(Q_ql, 'Q-Learning Policy'), (Q_sarsa, 'SARSA Policy')]):
ax = axes[0, 1] if ax_idx == 0 else axes[1, 0]
grid = np.zeros((env.rows, env.cols))
for r in range(env.rows):
for c in range(env.cols):
grid[r, c] = np.max(Q[(r, c)])
ax.imshow(grid, cmap='RdYlGn', interpolation='nearest')
for r in range(env.rows):
for c in range(env.cols):
if (r, c) == env.start:
ax.text(c, r, 'S', ha='center', va='center', fontsize=12, fontweight='bold')
elif (r, c) == env.goal:
ax.text(c, r, 'G', ha='center', va='center', fontsize=12, fontweight='bold')
elif (r, c) in env.cliff:
ax.text(c, r, 'X', ha='center', va='center', fontsize=12, color='red')
else:
best_action = np.argmax(Q[(r, c)])
ax.text(c, r, action_symbols[best_action],
ha='center', va='center', fontsize=14)
ax.set_title(title, fontsize=13)
# 最適経路の描画
def extract_path(Q, env, max_steps=100):
"""学習済みQ値から最適経路を抽出"""
state = env.reset()
path = [state]
for _ in range(max_steps):
action = np.argmax(Q[state])
next_state, _, done = env.step(action)
path.append(next_state)
state = next_state
if done:
break
return path
env_ql = CliffWalking()
env_sarsa = CliffWalking()
path_ql = extract_path(Q_ql, env_ql)
path_sarsa = extract_path(Q_sarsa, env_sarsa)
ax = axes[1, 1]
grid_display = np.zeros((env.rows, env.cols))
for pos in env.cliff:
grid_display[pos] = -1
ax.imshow(grid_display, cmap='RdYlGn', interpolation='nearest', alpha=0.3)
# Q学習の経路
path_ql_arr = np.array(path_ql)
ax.plot(path_ql_arr[:, 1], path_ql_arr[:, 0], 'b-o', linewidth=2,
markersize=4, label='Q-Learning path')
# SARSAの経路
path_sarsa_arr = np.array(path_sarsa)
ax.plot(path_sarsa_arr[:, 1] + 0.1, path_sarsa_arr[:, 0] + 0.1, 'r-s',
linewidth=2, markersize=4, label='SARSA path')
ax.set_title('Learned Paths', fontsize=13)
ax.legend(fontsize=11)
ax.set_xlim(-0.5, env.cols - 0.5)
ax.set_ylim(env.rows - 0.5, -0.5)
plt.tight_layout()
plt.show()
Q学習は最適な経路（崖のすぐ上を通る最短経路）を学習しますが、ε-greedy探索中に崖に落ちるリスクがあります。一方、SARSAはε-greedy方策自体を評価するため、崖から離れた安全な経路を学習する傾向があります。
まとめ
本記事では、Q学習とSARSAの理論と実装について解説しました。
- TD学習: エピソード終了を待たず、次の推定値で更新する
- Q学習（off-policy）: $Q(s,a) \leftarrow Q(s,a) + \alpha[R + \gamma \max_{a’} Q(s’,a’) – Q(s,a)]$
- SARSA（on-policy）: $Q(s,a) \leftarrow Q(s,a) + \alpha[R + \gamma Q(s’,a’) – Q(s,a)]$
- ε-greedy: 確率 $\varepsilon$ でランダム行動（探索）、$1-\varepsilon$ で最良行動（活用）
- Q学習は大胆な方策、SARSAは慎重な方策を学習する傾向がある
次のステップとして、以下の記事も参考にしてください。