強化学習では、エージェントが環境と相互作用しながら試行錯誤で最適な行動を学びます。動的計画法（DP）のように環境の遷移確率が既知である必要はなく、実際に行動して得られる経験だけから学習できるのがモデルフリー手法の強みです。
その代表的なアルゴリズムが Q学習（Q-Learning） と SARSA です。どちらもTD学習（Temporal Difference Learning）に基づくモデルフリー手法ですが、学習の仕方に決定的な違いがあります。本記事では、両アルゴリズムの理論を数式で導出し、CliffWalking環境でのPython実装を通じてその違いを体感します。
本記事の内容
- TD学習（Temporal Difference）の基本とブートストラップの考え方
- SARSAの更新則の導出
- Q学習の更新則の導出とSARSAとの違い
- オンポリシーとオフポリシーの概念
- $\varepsilon$-greedy方策による探索と活用のバランス
- CliffWalking環境でのPython比較実験
前提知識
この記事を読む前に、以下の記事を読んでおくと理解が深まります。
特に、マルコフ決定過程（MDP）、状態価値関数 $V(s)$、行動価値関数 $Q(s, a)$、ベルマン方程式の概念を前提とします。
TD学習（Temporal Difference）の基本
モンテカルロ法の問題点
モンテカルロ法では、エピソード全体が終了してから各状態の価値を更新します。状態価値関数の更新則は次のとおりです。
$$ V(s_t) \leftarrow V(s_t) + \alpha \left[ G_t – V(s_t) \right] $$
ここで $G_t = r_{t+1} + \gamma r_{t+2} + \gamma^2 r_{t+3} + \cdots$ はステップ $t$ 以降の累積報酬（リターン）、$\alpha$ は学習率です。
しかし、モンテカルロ法にはエピソードが終わるまで更新できないという欠点があります。エピソードが非常に長い場合や、連続的なタスク（終了状態がない場合）では使いにくいのです。
ブートストラップの考え方
TD学習のアイデアは、リターン $G_t$ の代わりに 1ステップ先の推定値 を使うことです。ベルマン方程式を思い出しましょう。
$$ V(s_t) = \mathbb{E}\left[ r_{t+1} + \gamma V(s_{t+1}) \right] $$
これに着想を得て、リターン全体を待つ代わりに $r_{t+1} + \gamma V(s_{t+1})$ をターゲットとして使います。これを TD(0) と呼びます。
$$ 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ターゲット、$\delta_t = r_{t+1} + \gamma V(s_{t+1}) – V(s_t)$ を TD誤差 と呼びます。
このように、まだ正確にはわからない将来の価値を現在の推定値で代用する手法を ブートストラップ と言います。TD学習の大きな利点は、エピソードの完了を待たずに毎ステップ更新できることです。
SARSAの更新則
状態価値関数から行動価値関数へ
TD(0)は状態価値関数 $V(s)$ を更新しますが、方策を改善するためには行動価値関数 $Q(s, a)$ を直接学ぶ方が便利です。SARSAはTD(0)のアイデアを行動価値関数に拡張したアルゴリズムです。
更新則の導出
行動価値関数のベルマン方程式は次のように書けます。
$$ Q^{\pi}(s_t, a_t) = \mathbb{E}_{\pi}\left[ r_{t+1} + \gamma Q^{\pi}(s_{t+1}, a_{t+1}) \right] $$
ここで $a_{t+1}$ は方策 $\pi$ に従って選ばれた行動です。TD(0)と同様に、この期待値を1サンプルで近似すると、SARSAの更新則が得られます。
$$ 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] $$
名前の由来は、更新に必要な5つの要素 $(s_t, a_t, r_{t+1}, s_{t+1}, a_{t+1})$ の頭文字、すなわち State, Action, Reward, State, Action です。
SARSAのアルゴリズム
SARSAのアルゴリズムをまとめると以下のとおりです。
- $Q(s, a)$ を任意に初期化（全状態・全行動について）
- 各エピソードについて繰り返す:
– 初期状態 $s$ を観測
– $\varepsilon$-greedy方策で行動 $a$ を選択
– エピソードが終了するまで繰り返す:
- 行動 $a$ を実行し、報酬 $r$ と次の状態 $s’$ を観測
- $\varepsilon$-greedy方策で次の行動 $a’$ を選択
- $Q(s, a) \leftarrow Q(s, a) + \alpha \left[ r + \gamma Q(s’, a’) – Q(s, a) \right]$
- $s \leftarrow s’$, $a \leftarrow a’$
重要なポイントは、次の行動 $a’$ を 実際に方策に従って選んでから 更新に使うことです。つまり、学習に使う行動と実際に実行する行動が同じ方策から来ています。
Q学習の更新則
更新則の導出
Q学習では、ベルマン 最適性 方程式に基づいて更新します。最適行動価値関数 $Q^{*}$ のベルマン方程式は次のとおりです。
$$ Q^{*}(s_t, a_t) = \mathbb{E}\left[ r_{t+1} + \gamma \max_{a’} Q^{*}(s_{t+1}, a’) \right] $$
SARSAでは次の行動 $a_{t+1}$（実際に方策が選ぶ行動）を使いましたが、Q学習では $\max_{a’} Q(s_{t+1}, a’)$ を使います。これにより、Q学習の更新則は次のようになります。
$$ 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] $$
SARSAとの違い
更新則を並べて比較しましょう。
$$ \begin{align} \text{SARSA:} \quad & 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] \\ \text{Q学習:} \quad & 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] \end{align} $$
違いは1箇所だけです。
| TDターゲットに使う値 | 意味 | |
|---|---|---|
| SARSA | $Q(s_{t+1}, a_{t+1})$ | 実際に方策が選んだ行動の価値 |
| Q学習 | $\max_{a’} Q(s_{t+1}, a’)$ | 最も価値の高い行動の価値 |
SARSAは「自分が実際にとる行動」に基づいて学び、Q学習は「理論上最善の行動」に基づいて学びます。この違いが、オンポリシーとオフポリシーの本質的な違いにつながります。
Q学習のアルゴリズム
- $Q(s, a)$ を任意に初期化
- 各エピソードについて繰り返す:
– 初期状態 $s$ を観測
– エピソードが終了するまで繰り返す:
- $\varepsilon$-greedy方策で行動 $a$ を選択
- 行動 $a$ を実行し、報酬 $r$ と次の状態 $s’$ を観測
- $Q(s, a) \leftarrow Q(s, a) + \alpha \left[ r + \gamma \max_{a’} Q(s’, a’) – Q(s, a) \right]$
- $s \leftarrow s’$
Q学習では次の行動 $a’$ を事前に選ぶ必要がなく、更新後に改めて方策から行動を選びます。
オンポリシー vs オフポリシー
強化学習のアルゴリズムを理解する上で、オンポリシー と オフポリシー の区別は非常に重要です。
オンポリシー（On-Policy）
SARSAはオンポリシー です。更新に使う方策（ターゲット方策）と、実際に行動を選ぶ方策（行動方策）が同一です。
$$ \underbrace{Q(s_t, a_t)}_{\text{行動方策で選んだ}} \leftarrow Q(s_t, a_t) + \alpha \left[ r_{t+1} + \gamma \underbrace{Q(s_{t+1}, a_{t+1})}_{\text{行動方策で選んだ}} – Q(s_t, a_t) \right] $$
行動方策が $\varepsilon$-greedy であれば、時折ランダムに選んでしまう行動も含めて学習します。そのため、探索中のリスクを考慮した「慎重な」方策を学びやすくなります。
オフポリシー（Off-Policy）
Q学習はオフポリシー です。行動方策（$\varepsilon$-greedy）とターゲット方策（greedy = $\max$）が異なります。
$$ Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha \left[ r_{t+1} + \gamma \underbrace{\max_{a’} Q(s_{t+1}, a’)}_{\text{greedy方策}} – Q(s_t, a_t) \right] $$
探索のために $\varepsilon$-greedy で行動しつつも、学習するのは最適方策（greedy方策）です。つまり「探索はするが、学ぶのは常に最善のケース」です。そのため、Q学習は最適方策を直接学びますが、探索中のリスクを無視しがちです。
$\varepsilon$-greedy方策
Q学習もSARSAも、行動を選ぶ際には $\varepsilon$-greedy方策 を使います。これは探索（exploration）と活用（exploitation）のバランスをとるシンプルな方法です。
定義
$\varepsilon$-greedy方策では、確率 $\varepsilon$ でランダムな行動を選び、確率 $1 – \varepsilon$ で現在のQ値が最大の行動を選びます。
$$ \pi(a \mid s) = \begin{cases} 1 – \varepsilon + \dfrac{\varepsilon}{|\mathcal{A}|} & \text{if } a = \arg\max_{a’} Q(s, a’) \\[8pt] \dfrac{\varepsilon}{|\mathcal{A}|} & \text{otherwise} \end{cases} $$
ここで $|\mathcal{A}|$ は行動の総数です。
探索と活用のトレードオフ
- $\varepsilon = 0$: 完全にgreedy（活用のみ、探索なし）。初期のQ値が悪いと局所解に陥る
- $\varepsilon = 1$: 完全にランダム（探索のみ、活用なし）。学習した知識を使わない
- $\varepsilon = 0.1$: 10%の確率でランダムに探索、90%の確率で最善と信じる行動を選択
実用上は、学習の初期には $\varepsilon$ を大きめにして十分探索し、学習が進むにつれて $\varepsilon$ を減衰させる $\varepsilon$-decay がよく使われます。
収束性の直感的説明
Q学習とSARSAの収束性について、直感的に理解しましょう。
Q学習の収束
Q学習は、以下の条件を満たすとき、Q値が最適行動価値関数 $Q^{*}$ に確率1で収束することが証明されています。
- 全ての状態-行動ペア $(s, a)$ が無限回訪問される
- 学習率 $\alpha_t$ が ロビンス-モンロー条件 を満たす:
$$ \sum_{t=0}^{\infty} \alpha_t = \infty, \quad \sum_{t=0}^{\infty} \alpha_t^2 < \infty $$
直感的には、更新式を繰り返すことで、各 $Q(s, a)$ がベルマン最適性方程式の不動点に近づいていくということです。$\max$ 演算子がベルマン最適性方程式に対応しているため、最適方策のQ値に収束します。
SARSAの収束
SARSAはオンポリシーであるため、収束先は 行動方策 $\pi$ に対するQ値 $Q^{\pi}$ です。$\varepsilon$-greedy方策のもとでは、$Q^{*}$ ではなく $\varepsilon$-greedy方策の下での最適値に収束します。
ただし、$\varepsilon$ を適切に減衰させる（GLIE条件: Greedy in the Limit with Infinite Exploration）と、SARSAも $Q^{*}$ に収束します。
CliffWalking環境での比較実験
CliffWalking環境とは
CliffWalking（崖歩き）は、Sutton & Barto の教科書で紹介されている有名な環境です。Q学習とSARSAの違いを顕著に示します。
S: スタート, G: ゴール, C: 崖（落ちると大きなペナルティ）
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
S C C C C C C C C C C G
- グリッドサイズ: 4行 x 12列
- 行動: 上・下・左・右の4方向
- 通常の移動: 報酬 $-1$
- 崖に落ちた場合: 報酬 $-100$、スタートに戻される
- ゴールに到達: エピソード終了
期待される結果
- Q学習: 崖のすぐ上を通る最短経路を学びます。$\max$ で更新するため、探索中のランダム行動で崖に落ちるリスクを無視します
- SARSA: 崖から離れた安全な経路を学びます。$\varepsilon$-greedy の探索行動も考慮に入れるため、崖の近くを通るリスクを回避します
Python実装
CliffWalking環境をスクラッチで実装し、Q学習とSARSAを比較します。
import numpy as np
import matplotlib.pyplot as plt
# =============================================
# CliffWalking環境のスクラッチ実装
# =============================================
class CliffWalking:
"""4x12グリッドの崖歩き環境"""
def __init__(self):
self.rows = 4
self.cols = 12
self.start = (3, 0)
self.goal = (3, 11)
# 崖の位置: 最下行の(3,1)から(3,10)
self.cliff = [(3, c) for c in range(1, 11)]
self.state = self.start
# 行動: 0=上, 1=右, 2=下, 3=左
self.n_actions = 4
self.action_effects = {
0: (-1, 0), # 上
1: (0, 1), # 右
2: (1, 0), # 下
3: (0, -1), # 左
}
def reset(self):
"""環境をリセットしてスタート位置を返す"""
self.state = self.start
return self.state
def step(self, action):
"""行動を実行して(次の状態, 報酬, 終了フラグ)を返す"""
dr, dc = self.action_effects[action]
r, c = self.state
new_r = max(0, min(self.rows - 1, r + dr))
new_c = max(0, min(self.cols - 1, c + dc))
new_state = (new_r, new_c)
if new_state in self.cliff:
# 崖に落ちた: 大きなペナルティ + スタートに戻る
self.state = self.start
return self.start, -100, False
elif new_state == self.goal:
# ゴールに到達
self.state = new_state
return new_state, -1, True
else:
# 通常の移動
self.state = new_state
return new_state, -1, False
# =============================================
# ε-greedy方策
# =============================================
def epsilon_greedy(Q, state, n_actions, epsilon):
"""ε-greedy方策で行動を選択"""
if np.random.random() < epsilon:
return np.random.randint(n_actions)
else:
# Q値が最大の行動を選択（同値の場合はランダム）
q_values = Q[state]
max_q = np.max(q_values)
best_actions = np.where(q_values == max_q)[0]
return np.random.choice(best_actions)
# =============================================
# Q学習（Off-Policy TD制御）
# =============================================
def q_learning(env, n_episodes=500, alpha=0.5, gamma=1.0, epsilon=0.1):
"""Q学習アルゴリズム"""
# Q値テーブルの初期化
Q = {}
for r in range(env.rows):
for c in range(env.cols):
Q[(r, c)] = np.zeros(env.n_actions)
episode_rewards = []
for episode in range(n_episodes):
state = env.reset()
total_reward = 0
while True:
# ε-greedyで行動選択
action = epsilon_greedy(Q, state, env.n_actions, epsilon)
next_state, reward, done = env.step(action)
total_reward += reward
# Q学習の更新: maxを使う（オフポリシー）
best_next_q = np.max(Q[next_state])
td_target = reward + gamma * best_next_q
td_error = td_target - Q[state][action]
Q[state][action] += alpha * td_error
state = next_state
if done:
break
episode_rewards.append(total_reward)
return Q, episode_rewards
# =============================================
# SARSA（On-Policy TD制御）
# =============================================
def sarsa(env, n_episodes=500, alpha=0.5, gamma=1.0, epsilon=0.1):
"""SARSAアルゴリズム"""
# Q値テーブルの初期化
Q = {}
for r in range(env.rows):
for c in range(env.cols):
Q[(r, c)] = np.zeros(env.n_actions)
episode_rewards = []
for episode in range(n_episodes):
state = env.reset()
# SARSAでは最初の行動を先に選ぶ
action = epsilon_greedy(Q, state, env.n_actions, epsilon)
total_reward = 0
while True:
next_state, reward, done = env.step(action)
total_reward += reward
# 次の行動をε-greedyで選択（実際に実行する行動）
next_action = epsilon_greedy(Q, next_state, env.n_actions, epsilon)
# SARSAの更新: 実際の次の行動を使う（オンポリシー）
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
episode_rewards.append(total_reward)
return Q, episode_rewards
# =============================================
# 可視化用ユーティリティ
# =============================================
def extract_policy(Q, env):
"""Q値テーブルからgreedy方策を抽出"""
policy = {}
for r in range(env.rows):
for c in range(env.cols):
state = (r, c)
policy[state] = np.argmax(Q[state])
return policy
def plot_policy(policy, env, title):
"""方策をグリッド上に矢印で可視化"""
arrow_map = {0: '\u2191', 1: '\u2192', 2: '\u2193', 3: '\u2190'} # ↑→↓←
fig, ax = plt.subplots(figsize=(12, 4))
for r in range(env.rows):
for c in range(env.cols):
state = (r, c)
if state == env.goal:
ax.text(c, env.rows - 1 - r, 'G', ha='center', va='center',
fontsize=14, fontweight='bold', color='green')
elif state == env.start:
ax.text(c, env.rows - 1 - r, 'S', ha='center', va='center',
fontsize=14, fontweight='bold', color='blue')
elif state in env.cliff:
ax.add_patch(plt.Rectangle((c - 0.5, env.rows - 1 - r - 0.5),
1, 1, color='gray', alpha=0.5))
ax.text(c, env.rows - 1 - r, 'C', ha='center', va='center',
fontsize=10, color='white')
else:
arrow = arrow_map[policy[state]]
ax.text(c, env.rows - 1 - r, arrow, ha='center', va='center',
fontsize=16)
ax.set_xlim(-0.5, env.cols - 0.5)
ax.set_ylim(-0.5, env.rows - 0.5)
ax.set_xticks(range(env.cols))
ax.set_yticks(range(env.rows))
ax.set_title(title, fontsize=14)
ax.grid(True, linewidth=0.5)
ax.set_aspect('equal')
plt.tight_layout()
plt.show()
def plot_learning_curves(rewards_q, rewards_sarsa, window=20):
"""学習曲線（移動平均）の比較プロット"""
fig, ax = plt.subplots(figsize=(10, 5))
# 移動平均の計算
def moving_avg(data, w):
return np.convolve(data, np.ones(w) / w, mode='valid')
avg_q = moving_avg(rewards_q, window)
avg_sarsa = moving_avg(rewards_sarsa, window)
ax.plot(avg_q, label='Q-Learning', linewidth=1.5)
ax.plot(avg_sarsa, label='SARSA', linewidth=1.5)
ax.set_xlabel('Episode', fontsize=12)
ax.set_ylabel(f'Reward (moving avg, window={window})', fontsize=12)
ax.set_title('Q-Learning vs SARSA on CliffWalking', fontsize=14)
ax.legend(fontsize=12)
ax.grid(True, alpha=0.3)
plt.tight_layout()
plt.show()
# =============================================
# 実験の実行
# =============================================
np.random.seed(42)
env = CliffWalking()
# Q学習の実行
Q_ql, rewards_ql = q_learning(env, n_episodes=500, alpha=0.5, gamma=1.0, epsilon=0.1)
# SARSAの実行
Q_sarsa, rewards_sarsa = sarsa(env, n_episodes=500, alpha=0.5, gamma=1.0, epsilon=0.1)
# 学習曲線の比較
plot_learning_curves(rewards_ql, rewards_sarsa, window=20)
# 学習された方策の可視化
policy_ql = extract_policy(Q_ql, env)
plot_policy(policy_ql, env, 'Q-Learning: Learned Policy (Optimal Path)')
policy_sarsa = extract_policy(Q_sarsa, env)
plot_policy(policy_sarsa, env, 'SARSA: Learned Policy (Safe Path)')
実験結果の読み方
学習曲線を見ると、以下の特徴が観察されます。
- SARSA（オンポリシー）のエピソード報酬は安定しています。崖から離れた安全な経路を学ぶため、$\varepsilon$-greedy の探索でたまたまランダムに動いても崖に落ちにくいです
- Q学習（オフポリシー）の平均報酬は変動が大きくなりがちです。最短経路（崖のすぐ上）を学びますが、$\varepsilon$ の確率でランダム行動をとると崖に落ちて $-100$ のペナルティを受けるためです
方策の可視化を見ると、以下の違いがわかります。
- Q学習は崖のすぐ上を通る最短経路を学びます。これは $\varepsilon = 0$（完全にgreedy）で行動する場合の最適経路です
- SARSAは崖から1段以上離れた安全な経路を学びます。$\varepsilon$-greedy で探索する際のリスクを織り込んだ方策です
つまり、Q学習は「もし常に最善の行動をとれるなら」という理想的な状況での最適方策を学び、SARSAは「探索もしながら行動する」という現実的な状況での最適方策を学ぶのです。
まとめ
本記事では、モデルフリー強化学習の代表的なアルゴリズムであるQ学習とSARSAについて解説しました。
- TD学習 はモンテカルロ法と異なり、ブートストラップにより毎ステップ更新できる
- SARSA（オンポリシー）は実際に方策が選ぶ行動 $a_{t+1}$ を使って更新する
- Q学習（オフポリシー）は $\max_{a’} Q(s_{t+1}, a’)$ を使って最適方策を直接学ぶ
- $\varepsilon$-greedy方策 で探索と活用のバランスをとる
- CliffWalkingでは、Q学習は最短経路を、SARSAは安全経路を学ぶという違いが現れる
次のステップとして、以下の記事も参考にしてください。
- DQN（Deep Q-Network） ではQ学習を深層学習と組み合わせ、大規模な状態空間に対応します
- 方策勾配法 ではQ値を介さず方策を直接最適化するアプローチを学びます