強化学習において、エージェントが環境と相互作用しながら最適な行動を学ぶ方法はいくつかありますが、その中でも最も有名かつ基本的なアルゴリズムが Q学習（Q-Learning） です。Q学習は1989年にChris Watkinsによって提案され、モデルフリーかつOff-policyなTD制御手法として、強化学習の理論と応用の両面で中心的な役割を果たしてきました。
Q学習の最大の特徴は、実際にエージェントが取る行動方策（行動方策）とは独立に、最適行動価値関数 $Q^*$ を直接学習できる点にあります。これにより、探索のための方策と最適方策の学習を分離でき、非常に柔軟かつ強力なアルゴリズムとなっています。
本記事の内容
- Q学習の更新則の導出（Off-policy TD制御としての位置づけ）
- SARSAとの本質的な違い（On-policy vs Off-policy）
- 収束定理とRobbins-Monro条件
- 探索と利用のジレンマ（ε-greedy, ε-decay, UCB）
- Cliff Walking環境でのPython完全実装と比較実験
前提知識
この記事を読む前に、以下の記事を読んでおくと理解が深まります。
行動価値関数とは
強化学習では、状態 $s$ において行動 $a$ を取ったときに将来得られる累積報酬の期待値を 行動価値関数（Action-Value Function） と呼びます。方策 $\pi$ のもとでの行動価値関数 $Q^\pi(s, a)$ は次のように定義されます。
$$ Q^\pi(s, a) = \mathbb{E}_\pi \left[ \sum_{t=0}^{\infty} \gamma^t R_{t+1} \mid S_0 = s, A_0 = a \right] $$
ここで、$\gamma \in [0, 1)$ は割引率、$R_{t+1}$ は時刻 $t$ から $t+1$ への遷移で得られる報酬です。
全ての状態・行動ペアについて価値を最大化する 最適行動価値関数 $Q^*(s, a)$ は次のように定義されます。
$$ Q^*(s, a) = \max_\pi Q^\pi(s, a) $$
最適行動価値関数が分かれば、各状態で $Q^*(s, a)$ を最大にする行動を選べばよいため、最適方策が直ちに得られます。
$$ \pi^*(s) = \arg\max_a Q^*(s, a) $$
ベルマン最適方程式からQ学習へ
ベルマン最適方程式の復習
最適行動価値関数 $Q^*$ は ベルマン最適方程式 を満たします。
$$ Q^*(s, a) = \mathbb{E} \left[ R_{t+1} + \gamma \max_{a’} Q^*(S_{t+1}, a’) \mid S_t = s, A_t = a \right] $$
この方程式は、最適な行動価値が「即時報酬 + 次状態での最適行動の割引価値」に等しいことを述べています。
TD制御への拡張
TD学習では、状態価値関数 $V(s)$ を次のように更新しました。
$$ 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}) – V(S_t)$ が TD誤差 です。これを行動価値関数に拡張し、さらにベルマン最適方程式の構造を利用すると、Q学習の更新則が得られます。
Q学習の更新則の導出
ベルマン最適方程式をサンプルベースの逐次更新に変換します。時刻 $t$ で状態 $S_t$ にいて行動 $A_t$ を取り、報酬 $R_{t+1}$ を受け取って状態 $S_{t+1}$ に遷移したとします。
ベルマン最適方程式の右辺の期待値を、1サンプルで近似します。
$$ Q^*(s, a) \approx R_{t+1} + \gamma \max_{a’} Q^*(S_{t+1}, a’) $$
現在の推定値 $Q(S_t, A_t)$ をこのターゲットに向けて更新するのが 確率的近似（Stochastic Approximation） の考え方です。学習率 $\alpha$ を導入して、以下の更新則を得ます。
$$ \begin{align} Q(S_t, A_t) &\leftarrow Q(S_t, A_t) + \alpha \left[ \text{ターゲット} – Q(S_t, A_t) \right] \\ &= 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} $$
これが Q学習の更新則 です。角括弧内の量
$$ \delta_t = R_{t+1} + \gamma \max_{a’} Q(S_{t+1}, a’) – Q(S_t, A_t) $$
を TD誤差 と呼びます。
Off-policyである理由
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] $$
ここで重要なのは、ターゲットに含まれる $\max_{a’} Q(S_{t+1}, a’)$ の部分です。この $\max$ 操作は 貪欲方策（greedy policy） に基づく行動選択に対応しています。一方、データを生成する方策（行動方策）は $\varepsilon$-greedy方策など、必ずしも貪欲方策ではありません。
つまり、Q学習は以下の2つの方策を分離しています。
| 方策の種類 | 役割 | Q学習での具体的な方策 |
|---|---|---|
| 行動方策（Behavior policy） $\mu$ | データ収集に使う方策 | $\varepsilon$-greedy方策 |
| 目標方策（Target policy） $\pi$ | 学習・改善の対象となる方策 | 貪欲方策（$\max$） |
行動方策と目標方策が異なるため、Q学習は Off-policy なアルゴリズムです。
SARSAとの比較
SARSAはQ学習と同じくTD制御手法ですが、On-policy です。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] $$
両者の違いは次の一点に集約されます。
| Q学習（Off-policy） | SARSA（On-policy） | |
|---|---|---|
| ターゲットの次行動 | $\max_{a’} Q(S_{t+1}, a’)$ | $Q(S_{t+1}, A_{t+1})$ |
| $A_{t+1}$ の選び方 | 全行動から最大値を取る | 実際の方策 $\pi$ で選んだ行動 |
| 学習する対象 | 最適方策 $\pi^*$ の価値 | 現在の方策 $\pi$ の価値 |
直感的に言うと、Q学習は「次の状態で最善の行動を取ると仮定して」価値を更新しますが、SARSAは「次の状態で実際に取る行動に基づいて」価値を更新します。
この違いは、探索的な行動を取る場面で大きな差を生みます。たとえばCliff Walking問題（後述）では、Q学習は崖際の最短経路を学びますが、SARSAは探索中に崖に落ちるリスクを考慮して、安全な迂回路を学ぶ傾向があります。
Q学習の収束定理
Q学習が最適行動価値関数 $Q^*$ に収束するための条件を述べます。
定理（Q学習の収束）: 全ての状態-行動ペア $(s, a)$ が無限回訪問され、かつ学習率 $\alpha_t(s, a)$ が以下の Robbins-Monro条件 を満たすとき、Q学習は確率1で $Q^* $ に収束する。
$$ \begin{align} \sum_{t=0}^{\infty} \alpha_t(s, a) &= \infty \\ \sum_{t=0}^{\infty} \alpha_t(s, a)^2 &< \infty \end{align} $$
第1条件 $\sum \alpha_t = \infty$ は、学習率の総和が無限大であること、つまり初期推定値がどれだけ離れていても修正できることを保証します。第2条件 $\sum \alpha_t^2 < \infty$ は、学習率が十分速く減少し、確率的なノイズ（1サンプルの分散）が消えていくことを保証します。
たとえば $\alpha_t = 1/t$ はこの条件を満たしますが、定数 $\alpha_t = \alpha$ は第2条件を満たしません。ただし実用上は、定数学習率でも十分に良い性能を示すことが多く、収束先の近傍で揺らぎ続けるものの、環境が変化する場合にはむしろ適応的に働くという利点もあります。
探索と利用のジレンマ
Q学習の性能は、行動方策の探索戦略に大きく依存します。探索と利用のジレンマ（Exploration-Exploitation Dilemma） とは、現在の知識に基づく最善の行動（利用, exploitation）と、未知の行動を試して情報を得ること（探索, exploration）のトレードオフです。
ε-greedy方策
最も基本的な探索戦略が ε-greedy方策 です。
$$ \pi(a \mid s) = \begin{cases} 1 – \varepsilon + \frac{\varepsilon}{|\mathcal{A}|} & \text{if } a = \arg\max_{a’} Q(s, a’) \\ \frac{\varepsilon}{|\mathcal{A}|} & \text{otherwise} \end{cases} $$
ここで $|\mathcal{A}|$ は行動の数です。確率 $1 – \varepsilon$ で現在最良と思われる行動（greedy行動）を選び、確率 $\varepsilon$ でランダムに行動を選びます。
ε-decay（減衰型ε-greedy）
学習の初期は探索を多く行い、学習が進むにつれて利用を増やすのが自然です。ε-decay では、$\varepsilon$ をエピソード数に応じて減少させます。
$$ \varepsilon_k = \max(\varepsilon_{\min}, \varepsilon_0 \cdot d^k) $$
ここで $k$ はエピソード番号、$d \in (0, 1)$ は減衰率、$\varepsilon_{\min}$ は最小探索率です。たとえば $\varepsilon_0 = 1.0$, $d = 0.995$, $\varepsilon_{\min} = 0.01$ とすると、約920エピソード目で $\varepsilon$ がほぼ最小値に達します。
UCB（Upper Confidence Bound）
ε-greedy方策はすべての非最適行動を等確率で試しますが、UCB方策 は各行動の不確実性を考慮して探索します。
$$ A_t = \arg\max_a \left[ Q(s, a) + c \sqrt{\frac{\ln t}{N_t(s, a)}} \right] $$
ここで $N_t(s, a)$ は状態 $s$ で行動 $a$ を選んだ回数、$c > 0$ は探索の度合いを制御するパラメータです。訪問回数が少ない行動ほど第2項が大きくなり、探索が促進されます。
Q学習のアルゴリズム
以上を整理して、Q学習のアルゴリズムをまとめます。
アルゴリズム: Q学習（Off-policy TD制御）
- $Q(s, a)$ を任意に初期化（終端状態では $Q(\text{terminal}, \cdot) = 0$）
- 各エピソードについて繰り返し:
- 初期状態 $S$ を観測
- 各ステップについて繰り返し（$S$ が終端状態でない間）:
- $Q$ に基づくε-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’$
Pythonでの実装
グリッドワールド環境
まず、シンプルなグリッドワールド環境を実装し、Q学習の基本動作を確認します。
import numpy as np
import matplotlib.pyplot as plt
# グリッドワールド環境の定義
class GridWorld:
"""4x4グリッドワールド: 左上(0,0)がスタート、右下(3,3)がゴール"""
def __init__(self, rows=4, cols=4):
self.rows = rows
self.cols = cols
self.start = (0, 0)
self.goal = (rows - 1, cols - 1)
# 行動: 上, 下, 左, 右
self.actions = [0, 1, 2, 3]
self.action_effects = {
0: (-1, 0), # 上
1: (1, 0), # 下
2: (0, -1), # 左
3: (0, 1) # 右
}
def reset(self):
"""環境をリセットしてスタート状態を返す"""
self.state = self.start
return self.state
def step(self, action):
"""行動を実行して次状態、報酬、終了フラグを返す"""
dr, dc = self.action_effects[action]
new_r = np.clip(self.state[0] + dr, 0, self.rows - 1)
new_c = np.clip(self.state[1] + dc, 0, self.cols - 1)
self.state = (new_r, new_c)
if self.state == self.goal:
return self.state, 1.0, True # ゴールで報酬+1
else:
return self.state, -0.01, False # 各ステップで小さなペナルティ
# Q学習の実装
def q_learning(env, episodes=500, alpha=0.1, gamma=0.99, epsilon=0.1):
"""Q学習アルゴリズム"""
n_states_r = env.rows
n_states_c = env.cols
n_actions = len(env.actions)
# Qテーブルの初期化
Q = np.zeros((n_states_r, n_states_c, n_actions))
rewards_per_episode = []
for ep in range(episodes):
state = env.reset()
total_reward = 0
done = False
while not done:
r, c = state
# ε-greedy方策で行動選択
if np.random.random() < epsilon:
action = np.random.choice(env.actions)
else:
action = np.argmax(Q[r, c])
# 行動を実行
next_state, reward, done = env.step(action)
nr, nc = next_state
total_reward += reward
# Q学習の更新則
td_target = reward + gamma * np.max(Q[nr, nc]) * (1 - done)
td_error = td_target - Q[r, c, action]
Q[r, c, action] += alpha * td_error
state = next_state
rewards_per_episode.append(total_reward)
return Q, rewards_per_episode
# 学習の実行
env = GridWorld()
Q, rewards = q_learning(env, episodes=1000, alpha=0.1, gamma=0.99, epsilon=0.1)
# 学習曲線の可視化
fig, axes = plt.subplots(1, 2, figsize=(14, 5))
# 報酬の推移（移動平均）
window = 50
avg_rewards = np.convolve(rewards, np.ones(window)/window, mode='valid')
axes[0].plot(avg_rewards)
axes[0].set_xlabel('Episode')
axes[0].set_ylabel('Average Reward (window=50)')
axes[0].set_title('Q-Learning: Learning Curve')
axes[0].grid(True, alpha=0.3)
# 最適方策の可視化
action_symbols = ['↑', '↓', '←', '→']
policy = np.argmax(Q, axis=2)
for i in range(env.rows):
for j in range(env.cols):
if (i, j) == env.goal:
axes[1].text(j, i, 'G', ha='center', va='center', fontsize=20, fontweight='bold')
else:
axes[1].text(j, i, action_symbols[policy[i, j]],
ha='center', va='center', fontsize=20)
axes[1].set_xlim(-0.5, env.cols - 0.5)
axes[1].set_ylim(env.rows - 0.5, -0.5)
axes[1].set_xticks(range(env.cols))
axes[1].set_yticks(range(env.rows))
axes[1].grid(True)
axes[1].set_title('Learned Policy')
axes[1].set_aspect('equal')
plt.tight_layout()
plt.show()
上のコードでは、4×4のグリッドワールドでQ学習を実行しています。左上がスタート、右下がゴールで、ゴールに到達すると報酬+1を獲得します。学習が進むにつれて、エージェントはゴールへの最短経路を学びます。
Cliff Walking環境でのQ学習 vs SARSA比較
次に、Q学習とSARSAの違いを際立たせる Cliff Walking 環境を実装します。この環境は4行12列のグリッドで、下段の左端がスタート、下段の右端がゴール、その間が「崖」になっています。崖に落ちると報酬-100で、スタートに戻されます。
import numpy as np
import matplotlib.pyplot as plt
class CliffWalking:
"""Cliff Walking環境（Sutton & Barto, Example 6.6）"""
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 = [0, 1, 2, 3] # 上, 下, 左, 右
self.action_effects = {0: (-1, 0), 1: (1, 0), 2: (0, -1), 3: (0, 1)}
def reset(self):
self.state = self.start
return self.state
def step(self, action):
dr, dc = self.action_effects[action]
new_r = np.clip(self.state[0] + dr, 0, self.rows - 1)
new_c = np.clip(self.state[1] + dc, 0, self.cols - 1)
self.state = (new_r, new_c)
if self.state in self.cliff:
# 崖に落ちた: 大きなペナルティ、スタートに戻る
self.state = self.start
return self.state, -100, False
elif self.state == self.goal:
return self.state, -1, True
else:
return self.state, -1, False
def q_learning_cliff(env, episodes=500, alpha=0.5, gamma=1.0, epsilon=0.1):
"""Q学習（Cliff Walking用）"""
Q = np.zeros((env.rows, env.cols, len(env.actions)))
rewards_per_episode = []
for ep in range(episodes):
state = env.reset()
total_reward = 0
done = False
while not done:
r, c = state
# ε-greedy行動選択
if np.random.random() < epsilon:
action = np.random.choice(env.actions)
else:
action = np.argmax(Q[r, c])
next_state, reward, done = env.step(action)
nr, nc = next_state
total_reward += reward
# Q学習更新
Q[r, c, action] += alpha * (
reward + gamma * np.max(Q[nr, nc]) * (1 - done) - Q[r, c, action]
)
state = next_state
rewards_per_episode.append(total_reward)
return Q, rewards_per_episode
def sarsa_cliff(env, episodes=500, alpha=0.5, gamma=1.0, epsilon=0.1):
"""SARSA（Cliff Walking用、比較のため）"""
Q = np.zeros((env.rows, env.cols, len(env.actions)))
rewards_per_episode = []
for ep in range(episodes):
state = env.reset()
r, c = state
# 初期行動をε-greedyで選択
if np.random.random() < epsilon:
action = np.random.choice(env.actions)
else:
action = np.argmax(Q[r, c])
total_reward = 0
done = False
while not done:
r, c = state
next_state, reward, done = env.step(action)
nr, nc = next_state
total_reward += reward
# 次の行動をε-greedyで選択
if np.random.random() < epsilon:
next_action = np.random.choice(env.actions)
else:
next_action = np.argmax(Q[nr, nc])
# SARSA更新
Q[r, c, action] += alpha * (
reward + gamma * Q[nr, nc, next_action] * (1 - done) - Q[r, c, action]
)
state = next_state
action = next_action
rewards_per_episode.append(total_reward)
return Q, rewards_per_episode
# 複数回実行して平均を取る
n_runs = 30
n_episodes = 500
q_rewards_all = np.zeros((n_runs, n_episodes))
sarsa_rewards_all = np.zeros((n_runs, n_episodes))
for run in range(n_runs):
env_q = CliffWalking()
env_s = CliffWalking()
_, q_rewards = q_learning_cliff(env_q, episodes=n_episodes)
_, sarsa_rewards = sarsa_cliff(env_s, episodes=n_episodes)
q_rewards_all[run] = q_rewards
sarsa_rewards_all[run] = sarsa_rewards
# 平均報酬の計算（移動平均）
window = 10
q_mean = np.mean(q_rewards_all, axis=0)
sarsa_mean = np.mean(sarsa_rewards_all, axis=0)
q_smooth = np.convolve(q_mean, np.ones(window)/window, mode='valid')
sarsa_smooth = np.convolve(sarsa_mean, np.ones(window)/window, mode='valid')
# 最終的な方策の取得
env_final = CliffWalking()
Q_final, _ = q_learning_cliff(env_final, episodes=1000)
Q_sarsa_final, _ = sarsa_cliff(env_final, episodes=1000)
# 可視化
fig, axes = plt.subplots(2, 2, figsize=(16, 10))
# 学習曲線の比較
axes[0, 0].plot(q_smooth, label='Q-Learning', alpha=0.8)
axes[0, 0].plot(sarsa_smooth, label='SARSA', alpha=0.8)
axes[0, 0].set_xlabel('Episode')
axes[0, 0].set_ylabel('Sum of Rewards')
axes[0, 0].set_title('Learning Curves: Q-Learning vs SARSA (Cliff Walking)')
axes[0, 0].legend()
axes[0, 0].set_ylim(-200, 0)
axes[0, 0].grid(True, alpha=0.3)
# Q学習の方策
action_symbols = ['↑', '↓', '←', '→']
policy_q = np.argmax(Q_final, axis=2)
for i in range(4):
for j in range(12):
if (i, j) == (3, 0):
axes[0, 1].text(j, i, 'S', ha='center', va='center', fontsize=10, fontweight='bold')
elif (i, j) == (3, 11):
axes[0, 1].text(j, i, 'G', ha='center', va='center', fontsize=10, fontweight='bold')
elif (i, j) in [(3, c) for c in range(1, 11)]:
axes[0, 1].add_patch(plt.Rectangle((j-0.5, i-0.5), 1, 1, color='gray', alpha=0.5))
axes[0, 1].text(j, i, 'C', ha='center', va='center', fontsize=8, color='white')
else:
axes[0, 1].text(j, i, action_symbols[policy_q[i, j]],
ha='center', va='center', fontsize=12)
axes[0, 1].set_xlim(-0.5, 11.5)
axes[0, 1].set_ylim(3.5, -0.5)
axes[0, 1].set_title('Q-Learning Policy (Optimal but risky path)')
axes[0, 1].grid(True)
axes[0, 1].set_aspect('equal')
# SARSAの方策
policy_s = np.argmax(Q_sarsa_final, axis=2)
for i in range(4):
for j in range(12):
if (i, j) == (3, 0):
axes[1, 0].text(j, i, 'S', ha='center', va='center', fontsize=10, fontweight='bold')
elif (i, j) == (3, 11):
axes[1, 0].text(j, i, 'G', ha='center', va='center', fontsize=10, fontweight='bold')
elif (i, j) in [(3, c) for c in range(1, 11)]:
axes[1, 0].add_patch(plt.Rectangle((j-0.5, i-0.5), 1, 1, color='gray', alpha=0.5))
axes[1, 0].text(j, i, 'C', ha='center', va='center', fontsize=8, color='white')
else:
axes[1, 0].text(j, i, action_symbols[policy_s[i, j]],
ha='center', va='center', fontsize=12)
axes[1, 0].set_xlim(-0.5, 11.5)
axes[1, 0].set_ylim(3.5, -0.5)
axes[1, 0].set_title('SARSA Policy (Safe detour path)')
axes[1, 0].grid(True)
axes[1, 0].set_aspect('equal')
# ε-decayの効果
epsilons_decay = []
eps = 1.0
decay_rate = 0.995
eps_min = 0.01
for k in range(1000):
epsilons_decay.append(eps)
eps = max(eps_min, eps * decay_rate)
axes[1, 1].plot(epsilons_decay)
axes[1, 1].set_xlabel('Episode')
axes[1, 1].set_ylabel('Epsilon')
axes[1, 1].set_title('ε-decay Schedule (decay=0.995)')
axes[1, 1].grid(True, alpha=0.3)
axes[1, 1].axhline(y=eps_min, color='r', linestyle='--', alpha=0.5, label=f'ε_min={eps_min}')
axes[1, 1].legend()
plt.tight_layout()
plt.show()
# 数値結果の表示
print(f"Q学習の平均報酬（最後100エピソード）: {np.mean(q_mean[-100:]):.1f}")
print(f"SARSAの平均報酬（最後100エピソード）: {np.mean(sarsa_mean[-100:]):.1f}")
結果の考察
Cliff Walking環境での比較実験から、Q学習とSARSAの違いが明確に表れます。
Q学習 は最適方策（崖のすぐ上を通る最短経路）を学習します。これは、更新則の $\max$ 操作が最適行動を前提としているためです。しかし、ε-greedy方策による探索中に崖に落ちるリスクがあるため、学習中のエピソード報酬は大きく変動します。
SARSA は安全な経路（崖から離れた迂回路）を学習する傾向があります。これは、実際にε-greedy方策で選ばれる行動（たまにランダムに崖に向かう可能性がある行動）を考慮して価値を更新するためです。結果として、学習中のオンライン性能はSARSAの方が安定します。
この違いは、Off-policyとOn-policyの本質的な特徴を反映しています。
- Q学習（Off-policy）: 探索中のリスクを無視して最適方策を学ぶ。学習後に探索をやめれば最適に振る舞える。
- SARSA（On-policy）: 探索中のリスクを考慮した方策を学ぶ。学習中の安全性が高い。
まとめ
本記事では、Q学習について、その理論的背景から実装まで解説しました。
- Q学習は Off-policy TD制御 であり、ベルマン最適方程式に基づく更新則 $Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha [R + \gamma \max_{a’} Q(S’, a’) – Q(S, A)]$ で最適行動価値関数を学習します
- SARSAとの違いは、ターゲットに $\max$ を使う（Q学習）か、実際の次行動の価値を使う（SARSA）かの一点にあります
- Robbins-Monro条件を満たす学習率のもとで、Q学習は $Q^*$ に収束することが保証されています
- 探索戦略としてε-greedy、ε-decay、UCBなどがあり、問題に応じて使い分けます
- Cliff Walking環境での比較実験により、Off-policy（Q学習）とOn-policy（SARSA）の違いを確認しました
次のステップとして、以下の記事も参考にしてください。