機械学習と情報技術

SARSA（On-policy TD制御）の理論と実装を解説

強化学習

強化学習のTD制御手法には大きく分けてOn-policyとOff-policyの2つのアプローチがあります。前者の代表的なアルゴリズムが SARSA です。SARSAは、エージェントが実際に従う方策（行動方策）そのものを改善していくOn-policy手法であり、学習中の安全性やオンライン性能に優れた特徴を持ちます。

SARSAという名前は、更新に使う5つの要素 $(S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1})$ の頭文字を並べたものです。この命名が示す通り、SARSAでは「次の状態で実際に選んだ行動」の価値を用いて更新を行います。この一見小さな違いが、Q学習とは質的に異なる学習結果をもたらします。

本記事の内容

  • SARSAの名前の由来と更新則の導出
  • Q学習との本質的な違い（On-policy vs Off-policy）
  • Expected SARSAの導出と性質
  • n-step SARSAと適格度トレース（SARSA(λ)）
  • Cliff WalkingおよびWindy GridWorldでのPython実装と比較実験

前提知識

この記事を読む前に、以下の記事を読んでおくと理解が深まります。

SARSAとは

名前の由来

SARSAの名前は、1ステップの更新に必要な5つの要素の頭文字に由来します。

$$ (S_t, \; A_t, \; R_{t+1}, \; S_{t+1}, \; A_{t+1}) $$

すなわち、現在の State（状態）、現在の Action（行動）、得られた Reward（報酬）、次の State（状態）、次の Action（行動）です。Q学習が $(S_t, A_t, R_{t+1}, S_{t+1})$ の4つの要素しか必要としないのに対し、SARSAでは 次の行動 $A_{t+1}$ が明示的に必要 である点が決定的に異なります。

SARSAの更新則

行動価値関数 $Q^\pi(s, a)$ のベルマン方程式は次の通りです。

$$ Q^\pi(s, a) = \mathbb{E}_\pi \left[ R_{t+1} + \gamma Q^\pi(S_{t+1}, A_{t+1}) \mid S_t = s, A_t = a \right] $$

Q学習では右辺を $R_{t+1} + \gamma \max_{a’} Q(S_{t+1}, a’)$ で近似しましたが、SARSAでは方策 $\pi$ に従って選んだ 実際の次行動 $A_{t+1}$ を使います。この期待値を1サンプルで近似し、確率的近似の枠組みで更新則を導出します。

ステップ1: ベルマン方程式のサンプルベース近似

$$ Q^\pi(S_t, A_t) \approx R_{t+1} + \gamma Q^\pi(S_{t+1}, A_{t+1}) $$

ここで $A_{t+1} \sim \pi(\cdot \mid S_{t+1})$ です。

ステップ2: 現在の推定値をターゲットに向けて学習率 $\alpha$ で更新

$$ 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] $$

これが SARSAの更新則 です。TD誤差は

$$ \delta_t = R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) – Q(S_t, A_t) $$

と定義されます。

On-policyである理由

SARSAがOn-policyである理由を明確にしましょう。更新則のターゲット部分を見ると

$$ \text{ターゲット} = R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) $$

であり、$A_{t+1}$ は 現在の方策 $\pi$（たとえばε-greedy方策）に従って実際に選んだ行動 です。つまり、SARSAは「今の方策に従ったらどうなるか」を学習しています。

一方、Q学習のターゲットは $R_{t+1} + \gamma \max_{a’} Q(S_{t+1}, a’)$ であり、$\max$ は 貪欲方策 に対応します。行動方策がε-greedyであっても、ターゲットは貪欲方策で評価するため、Off-policyです。

SARSA（On-policy） Q学習（Off-policy）
ターゲットの次行動 $Q(S_{t+1}, A_{t+1})$（方策 $\pi$ で選択） $\max_{a’} Q(S_{t+1}, a’)$（貪欲方策）
学習対象 現在の方策 $\pi$ の価値 最適方策 $\pi^*$ の価値
方策改善の方法 $Q$ に基づくε-greedyが自然に改善 $Q$ の $\max$ が暗黙的に最適方策

Q学習との本質的な違い

Q学習とSARSAの更新則を並べて比較しましょう。

$$ \begin{align} \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] \\ \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] \end{align} $$

違いは $\max_{a’} Q(S_{t+1}, a’)$ と $Q(S_{t+1}, A_{t+1})$ の部分のみです。しかし、この違いが以下の重要な帰結をもたらします。

1. 安全性の考慮

SARSAはε-greedy方策に従って選んだ行動の価値を使うため、「ランダムに危険な行動を取る可能性」を価値関数に反映します。その結果、危険な状態の近くの価値が低く推定され、安全な方策を学習する傾向があります。

2. 学習中のオンライン性能

Q学習は最適方策を直接学びますが、ε-greedy探索中は最適方策通りに行動しないため、学習中に崖に落ちるなどの事故が多発します。SARSAはε-greedy方策自体の価値を学ぶため、探索のリスクを織り込んだ方策を返し、学習中の性能が安定します。

3. 収束先の違い

$\varepsilon > 0$ が固定の場合: – Q学習: 最適方策 $\pi^*$ の行動価値 $Q^*$ に収束 – SARSA: ε-greedy方策の行動価値 $Q^\pi$ に収束（$\varepsilon$ に依存）

$\varepsilon \to 0$（GLIE条件を満たす減衰型ε-greedy）の場合: – 両者とも $Q^*$ に収束

Expected SARSAの導出

SARSAの更新では、次の行動 $A_{t+1}$ のサンプリングに起因する分散があります。この分散を低減するのが Expected SARSA です。

導出

SARSAのターゲットは

$$ R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) $$

ですが、$A_{t+1}$ は方策 $\pi$ からサンプルされるので、この項の期待値は

$$ \mathbb{E}_\pi [R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) \mid S_{t+1}] = R_{t+1} + \gamma \sum_{a’} \pi(a’ \mid S_{t+1}) Q(S_{t+1}, a’) $$

です。Expected SARSAでは、サンプル $Q(S_{t+1}, A_{t+1})$ の代わりにこの期待値を直接計算します。

$$ Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha \left[ R_{t+1} + \gamma \sum_{a’} \pi(a’ \mid S_{t+1}) Q(S_{t+1}, a’) – Q(S_t, A_t) \right] $$

Expected SARSAの性質

Expected SARSAの重要な性質をまとめます。

分散の低減: サンプリングの確率性を解析的に平均化するため、SARSAよりも分散が小さくなります。

$$ \text{Var}[\text{Expected SARSA target}] \leq \text{Var}[\text{SARSA target}] $$

Q学習との関係: ε-greedy方策のもとでExpected SARSAの期待値を展開すると

$$ \sum_{a’} \pi(a’ \mid s’) Q(s’, a’) = (1 – \varepsilon) \max_{a’} Q(s’, a’) + \frac{\varepsilon}{|\mathcal{A}|} \sum_{a’} Q(s’, a’) $$

$\varepsilon = 0$ のとき、Expected SARSAは $\max_{a’} Q(s’, a’)$ に一致し、Q学習と等価 になります。つまり、Expected SARSAはSARSAとQ学習を連続的につなぐアルゴリズムと見なせます。

n-step SARSAの一般化

1ステップのSARSAをn-stepに一般化すると、TDとモンテカルロ法のスペクトラム上を移動できます。

n-step収益

n-stepのSARSAターゲット（n-step収益）は次のように定義されます。

$$ G_t^{(n)} = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots + \gamma^{n-1} R_{t+n} + \gamma^n Q(S_{t+n}, A_{t+n}) $$

これを用いた更新則は

$$ Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha \left[ G_t^{(n)} – Q(S_t, A_t) \right] $$

です。$n = 1$ のとき通常のSARSA、$n \to \infty$ のときモンテカルロ法に一致します。

バイアスと分散のトレードオフ

n-stepの $n$ を大きくすると

  • バイアスが減少: ブートストラップの割合が減り、推定値への依存度が下がる
  • 分散が増加: より多くのランダムな報酬をサンプルするため

これは1-step TD（低分散・高バイアス）とモンテカルロ法（高分散・低バイアス）の中間を $n$ で制御できることを意味します。

SARSA(λ)と適格度トレース

n-step SARSAの自然な拡張として、全ての $n$ に対するn-step収益の加重平均を考えるのが SARSA(λ) です。

λ-収益

パラメータ $\lambda \in [0, 1]$ を導入して、n-step収益の幾何加重平均を定義します。

$$ G_t^\lambda = (1 – \lambda) \sum_{n=1}^{\infty} \lambda^{n-1} G_t^{(n)} $$

重み $(1 – \lambda)\lambda^{n-1}$ の総和が1になることは容易に確認できます。

$$ (1 – \lambda) \sum_{n=1}^{\infty} \lambda^{n-1} = (1 – \lambda) \cdot \frac{1}{1 – \lambda} = 1 $$

$\lambda = 0$ のとき $G_t^\lambda = G_t^{(1)}$（1-step SARSA）、$\lambda = 1$ のとき $G_t^\lambda = G_t$（モンテカルロ収益）に対応します。

適格度トレース

$G_t^\lambda$ を直接計算するにはエピソード全体が必要ですが、適格度トレース（Eligibility Trace） を使うと、各ステップで逐次的に更新できます。

各状態-行動ペア $(s, a)$ に対して適格度トレース $e_t(s, a)$ を保持します。

$$ e_t(s, a) = \begin{cases} \gamma \lambda \, e_{t-1}(s, a) + 1 & \text{if } s = S_t \text{ and } a = A_t \\ \gamma \lambda \, e_{t-1}(s, a) & \text{otherwise} \end{cases} $$

そして、全ての $(s, a)$ について一括更新します。

$$ Q(s, a) \leftarrow Q(s, a) + \alpha \, \delta_t \, e_t(s, a) $$

ここで $\delta_t = R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) – Q(S_t, A_t)$ は通常のSARSA TD誤差です。

直感的には、適格度トレースは「最近訪れた状態-行動ペア」を記憶する仕組みです。$\gamma \lambda$ のべき乗で指数的に減衰するため、最近の経験ほど強く更新されます。

SARSAのアルゴリズム

アルゴリズム: SARSA（On-policy TD制御）

  1. $Q(s, a)$ を任意に初期化（終端状態では $Q(\text{terminal}, \cdot) = 0$）
  2. 各エピソードについて繰り返し:
  3. 初期状態 $S$ を観測
  4. $Q$ に基づくε-greedy方策で行動 $A$ を選択
  5. 各ステップについて繰り返し（$S$ が終端状態でない間）:
    1. 行動 $A$ を実行し、報酬 $R$ と次状態 $S’$ を観測
    2. $Q$ に基づくε-greedy方策で次行動 $A’$ を選択
    3. $Q(S, A) \leftarrow Q(S, A) + \alpha \left[ R + \gamma Q(S’, A’) – Q(S, A) \right]$
    4. $S \leftarrow S’$, $A \leftarrow A’$

Q学習との違いに注意してください。SARSAでは ステップ2でAを選択 し、ループ内でも 先に次行動A’を選択してから 更新を行います。

Pythonでの実装

Cliff Walking環境でのSARSA実装

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 = [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 epsilon_greedy(Q, state, epsilon, n_actions):
    """ε-greedy方策による行動選択"""
    r, c = state
    if np.random.random() < epsilon:
        return np.random.randint(n_actions)
    else:
        return np.argmax(Q[r, c])

def sarsa(env, episodes=500, alpha=0.5, gamma=1.0, epsilon=0.1):
    """SARSAアルゴリズム"""
    Q = np.zeros((env.rows, env.cols, len(env.actions)))
    rewards_per_episode = []

    for ep in range(episodes):
        state = env.reset()
        # SARSAでは最初に行動を選択（S, A が必要）
        action = epsilon_greedy(Q, state, epsilon, len(env.actions))
        total_reward = 0
        done = False

        while not done:
            # 行動を実行してR, S'を取得
            next_state, reward, done = env.step(action)
            total_reward += reward

            # 次の行動A'をε-greedyで選択
            next_action = epsilon_greedy(Q, next_state, epsilon, len(env.actions))

            # SARSA更新: Q(S,A) ← Q(S,A) + α[R + γQ(S',A') - Q(S,A)]
            r, c = state
            nr, nc = next_state
            td_target = reward + gamma * Q[nr, nc, next_action] * (1 - done)
            td_error = td_target - Q[r, c, action]
            Q[r, c, action] += alpha * td_error

            # S ← S', A ← A'
            state = next_state
            action = next_action

        rewards_per_episode.append(total_reward)

    return Q, rewards_per_episode

def expected_sarsa(env, episodes=500, alpha=0.5, gamma=1.0, epsilon=0.1):
    """Expected SARSAアルゴリズム"""
    Q = np.zeros((env.rows, env.cols, len(env.actions)))
    n_actions = 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
            action = epsilon_greedy(Q, state, epsilon, n_actions)
            next_state, reward, done = env.step(action)
            nr, nc = next_state
            total_reward += reward

            # Expected SARSAターゲット: Σπ(a'|s')Q(s',a')
            expected_q = 0
            greedy_action = np.argmax(Q[nr, nc])
            for a in range(n_actions):
                if a == greedy_action:
                    prob = 1 - epsilon + epsilon / n_actions
                else:
                    prob = epsilon / n_actions
                expected_q += prob * Q[nr, nc, a]

            td_target = reward + gamma * expected_q * (1 - done)
            Q[r, c, action] += alpha * (td_target - Q[r, c, action])

            state = next_state

        rewards_per_episode.append(total_reward)

    return Q, rewards_per_episode

def q_learning(env, episodes=500, alpha=0.5, gamma=1.0, epsilon=0.1):
    """Q学習（比較用）"""
    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
            action = epsilon_greedy(Q, state, epsilon, len(env.actions))
            next_state, reward, done = env.step(action)
            nr, nc = next_state
            total_reward += reward

            td_target = reward + gamma * np.max(Q[nr, nc]) * (1 - done)
            Q[r, c, action] += alpha * (td_target - Q[r, c, action])
            state = next_state

        rewards_per_episode.append(total_reward)

    return Q, rewards_per_episode

# 3手法の比較実験
n_runs = 50
n_episodes = 500
sarsa_all = np.zeros((n_runs, n_episodes))
expected_sarsa_all = np.zeros((n_runs, n_episodes))
q_learning_all = np.zeros((n_runs, n_episodes))

for run in range(n_runs):
    _, rewards_s = sarsa(CliffWalking(), episodes=n_episodes)
    _, rewards_e = expected_sarsa(CliffWalking(), episodes=n_episodes)
    _, rewards_q = q_learning(CliffWalking(), episodes=n_episodes)
    sarsa_all[run] = rewards_s
    expected_sarsa_all[run] = rewards_e
    q_learning_all[run] = rewards_q

# 移動平均
window = 10
def smooth(data, w):
    return np.convolve(np.mean(data, axis=0), np.ones(w)/w, mode='valid')

fig, ax = plt.subplots(figsize=(12, 6))
ax.plot(smooth(sarsa_all, window), label='SARSA', linewidth=2)
ax.plot(smooth(expected_sarsa_all, window), label='Expected SARSA', linewidth=2)
ax.plot(smooth(q_learning_all, window), label='Q-Learning', linewidth=2)
ax.set_xlabel('Episode', fontsize=12)
ax.set_ylabel('Sum of Rewards (averaged over runs)', fontsize=12)
ax.set_title('Cliff Walking: SARSA vs Expected SARSA vs Q-Learning', fontsize=14)
ax.legend(fontsize=12)
ax.set_ylim(-150, -10)
ax.grid(True, alpha=0.3)
plt.tight_layout()
plt.show()

Windy GridWorld環境での実装

Windy GridWorldは、特定の列に「横風」が吹いており、エージェントが上方向に押される環境です。SARSAの動作を確認するのに適した標準的な問題です。

import numpy as np
import matplotlib.pyplot as plt

class WindyGridWorld:
    """Windy GridWorld環境（Sutton & Barto, Example 6.5）"""
    def __init__(self):
        self.rows = 7
        self.cols = 10
        self.start = (3, 0)
        self.goal = (3, 7)
        # 各列の風の強さ（上方向への押し上げ量）
        self.wind = [0, 0, 0, 1, 1, 1, 2, 2, 1, 0]
        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 = self.state[0] + dr - self.wind[self.state[1]]
        new_c = self.state[1] + dc
        new_r = np.clip(new_r, 0, self.rows - 1)
        new_c = np.clip(new_c, 0, self.cols - 1)
        self.state = (new_r, new_c)

        if self.state == self.goal:
            return self.state, 0, True
        else:
            return self.state, -1, False

def sarsa_windy(env, episodes=500, alpha=0.5, gamma=1.0, epsilon=0.1):
    """SARSAによるWindy GridWorldの学習"""
    Q = np.zeros((env.rows, env.cols, len(env.actions)))
    steps_per_episode = []

    for ep in range(episodes):
        state = env.reset()
        action = epsilon_greedy(Q, state, epsilon, len(env.actions))
        steps = 0
        done = False

        while not done:
            next_state, reward, done = env.step(action)
            next_action = epsilon_greedy(Q, next_state, epsilon, len(env.actions))

            r, c = state
            nr, nc = next_state
            Q[r, c, action] += alpha * (
                reward + gamma * Q[nr, nc, next_action] * (1 - done) - Q[r, c, action]
            )

            state = next_state
            action = next_action
            steps += 1

        steps_per_episode.append(steps)

    return Q, steps_per_episode

# Windy GridWorldでの学習
env_windy = WindyGridWorld()
Q_windy, steps = sarsa_windy(env_windy, episodes=500, alpha=0.5, gamma=1.0, epsilon=0.1)

# 学習した方策の経路を取得
def get_trajectory(env, Q):
    """学習した方策で1エピソード実行し、経路を取得"""
    state = env.reset()
    trajectory = [state]
    done = False
    max_steps = 100

    for _ in range(max_steps):
        r, c = state
        action = np.argmax(Q[r, c])
        state, _, done = env.step(action)
        trajectory.append(state)
        if done:
            break

    return trajectory

trajectory = get_trajectory(WindyGridWorld(), Q_windy)

fig, axes = plt.subplots(1, 2, figsize=(16, 5))

# ステップ数の推移（累積タイムステップ vs エピソード数）
cumulative_steps = np.cumsum(steps)
# エピソード番号 vs 累積ステップ数（Sutton & Bartoの図6.3に相当）
axes[0].plot(cumulative_steps, range(len(steps)))
axes[0].set_xlabel('Time Steps', fontsize=12)
axes[0].set_ylabel('Episodes', fontsize=12)
axes[0].set_title('Windy GridWorld: SARSA Learning Progress', fontsize=14)
axes[0].grid(True, alpha=0.3)

# 学習した経路の可視化
traj_rows = [s[0] for s in trajectory]
traj_cols = [s[1] for s in trajectory]

# 風の強さを背景色で表示
wind_grid = np.zeros((env_windy.rows, env_windy.cols))
for c in range(env_windy.cols):
    wind_grid[:, c] = env_windy.wind[c]

axes[1].imshow(wind_grid, cmap='Blues', alpha=0.3, origin='upper')
axes[1].plot(traj_cols, traj_rows, 'ro-', markersize=6, linewidth=2, label='Trajectory')
axes[1].plot(env_windy.start[1], env_windy.start[0], 'gs', markersize=15, label='Start')
axes[1].plot(env_windy.goal[1], env_windy.goal[0], 'r*', markersize=20, label='Goal')

# 風の強さを列の下に表示
for c in range(env_windy.cols):
    if env_windy.wind[c] > 0:
        axes[1].annotate(f'↑{env_windy.wind[c]}', (c, env_windy.rows - 0.3),
                        ha='center', fontsize=10, color='blue')

axes[1].set_xlim(-0.5, env_windy.cols - 0.5)
axes[1].set_ylim(env_windy.rows - 0.5, -0.5)
axes[1].set_xticks(range(env_windy.cols))
axes[1].set_yticks(range(env_windy.rows))
axes[1].grid(True, alpha=0.3)
axes[1].set_title('Windy GridWorld: Learned Path', fontsize=14)
axes[1].legend(fontsize=10)
axes[1].set_aspect('equal')

plt.tight_layout()
plt.show()

# ステップ数の収束状況
print(f"最初の10エピソードの平均ステップ数: {np.mean(steps[:10]):.1f}")
print(f"最後の10エピソードの平均ステップ数: {np.mean(steps[-10:]):.1f}")
print(f"学習した経路のステップ数: {len(trajectory) - 1}")

SARSA(λ)の実装

適格度トレースを用いたSARSA(λ)の実装例です。

import numpy as np
import matplotlib.pyplot as plt

class CliffWalking:
    """Cliff Walking環境（再掲）"""
    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 sarsa_lambda(env, episodes=500, alpha=0.5, gamma=1.0,
                 epsilon=0.1, lam=0.9):
    """SARSA(λ)アルゴリズム（適格度トレース使用）"""
    n_actions = len(env.actions)
    Q = np.zeros((env.rows, env.cols, n_actions))
    rewards_per_episode = []

    for ep in range(episodes):
        # 適格度トレースの初期化（各エピソード開始時にゼロ）
        e = np.zeros_like(Q)

        state = env.reset()
        r, c = state
        if np.random.random() < epsilon:
            action = np.random.randint(n_actions)
        else:
            action = np.argmax(Q[r, c])

        total_reward = 0
        done = False

        while not done:
            next_state, reward, done = env.step(action)
            nr, nc = next_state
            total_reward += reward

            # 次の行動をε-greedyで選択
            if np.random.random() < epsilon:
                next_action = np.random.randint(n_actions)
            else:
                next_action = np.argmax(Q[nr, nc])

            # TD誤差の計算
            r_s, c_s = state
            delta = reward + gamma * Q[nr, nc, next_action] * (1 - done) - Q[r_s, c_s, action]

            # 適格度トレースの更新（累積トレース）
            e[r_s, c_s, action] += 1

            # 全状態-行動ペアを一括更新
            Q += alpha * delta * e

            # トレースの減衰
            e *= gamma * lam

            state = next_state
            action = next_action

        rewards_per_episode.append(total_reward)

    return Q, rewards_per_episode

# λの異なるSARSA(λ)の比較
lambdas = [0.0, 0.3, 0.6, 0.9]
n_runs = 30
n_episodes = 300

fig, ax = plt.subplots(figsize=(12, 6))

for lam in lambdas:
    all_rewards = np.zeros((n_runs, n_episodes))
    for run in range(n_runs):
        _, rewards = sarsa_lambda(CliffWalking(), episodes=n_episodes, lam=lam, alpha=0.3)
        all_rewards[run] = rewards

    mean_rewards = np.mean(all_rewards, axis=0)
    window = 10
    smoothed = np.convolve(mean_rewards, np.ones(window)/window, mode='valid')
    ax.plot(smoothed, label=f'SARSA(λ={lam})', linewidth=2)

ax.set_xlabel('Episode', fontsize=12)
ax.set_ylabel('Sum of Rewards', fontsize=12)
ax.set_title('Cliff Walking: SARSA(λ) for Different λ Values', fontsize=14)
ax.legend(fontsize=12)
ax.set_ylim(-200, -10)
ax.grid(True, alpha=0.3)
plt.tight_layout()
plt.show()

結果の考察

Cliff Walking環境 では、SARSAはQ学習に比べて学習中の報酬が安定しています。SARSAは崖から離れた安全な経路を学習する傾向があり、ε-greedy探索中に崖に落ちるリスクを反映した方策を返します。

Expected SARSA はSARSAよりも分散が小さく、安定した学習を実現します。特にα（学習率）が大きい場合にその差が顕著になります。

Windy GridWorld では、SARSAは風の効果を考慮した最適経路を効率的に学習します。累積タイムステップとエピソード数の関係から、学習の進行が確認できます。

SARSA(λ) では、λの値が大きいほどモンテカルロ法に近づき、信用割当が長い時間スパンで行われます。しかし、λが大きすぎると分散が増加し、学習が不安定になることがあります。

まとめ

本記事では、SARSAについて理論と実装の両面から解説しました。

  • SARSAは On-policy TD制御 であり、更新則 $Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha [R + \gamma Q(S’, A’) – Q(S, A)]$ で現在の方策の価値を学習します
  • Q学習との違いは「次行動を実際の方策から選ぶ（SARSA）か、$\max$ で選ぶ（Q学習）か」の一点です
  • On-policyの利点として、探索中のリスクを考慮した安全な方策を学習できます
  • Expected SARSA は次行動の期待値を解析的に計算することで分散を低減し、$\varepsilon = 0$ でQ学習と一致します
  • n-step SARSA はTDとモンテカルロ法の中間を制御し、SARSA(λ) は適格度トレースで効率的に実装できます

次のステップとして、以下の記事も参考にしてください。

関連記事

前の記事

TD学習（Temporal Difference Learning）の理論と実装

次の記事

Q学習の理論と実装をわかりやすく解説

関連タグ: Expected SARSA On-policy SARSA TD制御 強化学習 方策改善