第2章：Q学習とSARSA

本章では、2つの基本的なTD制御アルゴリズムであるQ学習（オフポリシー）とSARSA（オンポリシー）を学びます。Qテーブルに状態-行動価値を格納する方法を理解し、両アルゴリズムをゼロから実装します。また、古典的な崖歩き問題（Cliff Walking）を通じて、それぞれのアルゴリズムをいつ使用すべきかを理解します。

学習目標

本章を修了すると、以下のことができるようになります：

• Qテーブルの概念と、テーブル形式手法が適切な場面を理解する
• Q学習の更新則と、なぜそれがオフポリシーであるかを説明できる
• SARSAの更新則と、なぜそれがオンポリシーであるかを説明できる
• リスクに敏感な環境でのQ学習とSARSAの挙動を比較できる
• 複数の探索戦略（イプシロン貪欲法、ボルツマン法、UCB）を実装できる
• 崖歩き問題に両アルゴリズムを適用できる
• 分散削減技法としてのExpected SARSAを理解する

2.1 テーブル形式手法入門

Qテーブルの概念

離散的な状態空間と行動空間を持つ強化学習では、すべての状態-行動ペアの価値をテーブルに格納できます。このテーブルはQテーブルと呼ばれ、各（状態、行動）ペアを期待累積報酬を表す値にマッピングします。

Qテーブルは2次元配列で、以下のように構成されます：

• 行は状態 $s \in S$ に対応
• 列は行動 $a \in A$ に対応
• 各セル $Q(s, a)$ は状態 $s$ で行動 $a$ を取ることの推定価値を格納

テーブル形式手法が有効な場合（そうでない場合）

経験則：$|S| \times |A| < 10^6$ の場合、テーブル形式手法は実用的です。それ以上の場合は、関数近似（第3章：DQN）を検討してください。

状態-行動価値の格納

# Requirements:
# - Python 3.9+
# - numpy>=1.24.0
# - gymnasium>=0.29.0

import numpy as np
import gymnasium as gym

class QTable:
    """
    離散状態-行動空間のためのQテーブル実装

    Q値の格納と取得のためのクリーンなインターフェースを提供し、
    初期化戦略もサポートしています。
    """

    def __init__(self, n_states: int, n_actions: int, init_value: float = 0.0):
        """
        Qテーブルを初期化

        Args:
            n_states: 離散状態の数
            n_actions: 離散行動の数
            init_value: すべてのペアの初期Q値（0より大きい場合は楽観的初期化）
        """
        self.n_states = n_states
        self.n_actions = n_actions
        self.table = np.full((n_states, n_actions), init_value)

        # 分析用に訪問回数を追跡
        self.visit_counts = np.zeros((n_states, n_actions), dtype=int)

    def get_value(self, state: int, action: int) -> float:
        """Q(s, a) を取得"""
        return self.table[state, action]

    def set_value(self, state: int, action: int, value: float):
        """Q(s, a) を設定"""
        self.table[state, action] = value
        self.visit_counts[state, action] += 1

    def get_best_action(self, state: int) -> int:
        """argmax_a Q(s, a) を取得"""
        return int(np.argmax(self.table[state]))

    def get_max_value(self, state: int) -> float:
        """max_a Q(s, a) を取得"""
        return float(np.max(self.table[state]))

    def get_action_values(self, state: int) -> np.ndarray:
        """すべての行動に対する Q(s, :) を取得"""
        return self.table[state].copy()


# FrozenLake環境でのデモンストレーション
print("=== Qテーブルのデモンストレーション ===\n")

env = gym.make('FrozenLake-v1', is_slippery=False)

n_states = env.observation_space.n  # 16状態（4x4グリッド）
n_actions = env.action_space.n      # 4行動（左、下、右、上）

print(f"状態空間のサイズ: {n_states}")
print(f"行動空間のサイズ: {n_actions}")
print(f"Qテーブルの形状: ({n_states}, {n_actions})")
print(f"エントリ総数: {n_states * n_actions}")

# 楽観的初期化でQテーブルを作成
q_table = QTable(n_states, n_actions, init_value=1.0)

print(f"\n初期Qテーブル（最初の4状態）:")
print(q_table.table[:4])

env.close()

2.2 Q学習アルゴリズム

オフポリシーTD制御

Q学習はオフポリシーの時間差分制御アルゴリズムです。追従しているポリシーに関係なく、最適行動価値関数 $Q^*$ を直接学習します。

Q学習の更新則

Q学習の核となる更新式は以下の通りです：

ここで：

• $\alpha \in (0, 1]$ は学習率
• $\gamma \in [0, 1]$ は割引率
• $r_{t+1} + \gamma \max_{a'} Q(s_{t+1}, a')$ はTD目標値
• $\delta_t = r_{t+1} + \gamma \max_{a'} Q(s_{t+1}, a') - Q(s_t, a_t)$ はTD誤差

Q学習がオフポリシーである理由

重要な洞察は、更新におけるmax演算子です：

• 行動ポリシー：エージェントは探索的なポリシー（例：イプシロン貪欲法）に従う
• ターゲットポリシー：更新には $\max_{a'} Q(s_{t+1}, a')$ を使用し、これは貪欲な行動

エージェントは最適なポリシーを学習しながら自由に探索できます。この行動ポリシーとターゲットポリシーの分離が、Q学習を「オフポリシー」にしている理由です。

収束特性

Q学習は以下の条件の下で $Q^*$ に収束します：

1. すべての状態-行動ペアが無限回訪問される
2. 学習率 $\alpha_t$ が以下を満たす：$\sum_t \alpha_t = \infty$ かつ $\sum_t \alpha_t^2 < \infty$
3. 報酬が有界である

実際には、固定された小さな学習率（例：$\alpha = 0.1$）がほとんどのテーブル形式問題でうまく機能します。

Q学習の完全な実装

# Requirements:
# - Python 3.9+
# - numpy>=1.24.0
# - gymnasium>=0.29.0
# - matplotlib>=3.7.0

import numpy as np
import gymnasium as gym
import matplotlib.pyplot as plt
from typing import Tuple, List

class QLearningAgent:
    """
    イプシロン貪欲探索を用いたQ学習エージェント

    次の行動の最大値でブートストラップすることにより、
    Q*を直接学習するオフポリシーTD制御アルゴリズムを実装しています。
    """

    def __init__(
        self,
        n_states: int,
        n_actions: int,
        alpha: float = 0.1,
        gamma: float = 0.99,
        epsilon: float = 0.1,
        epsilon_decay: float = 1.0,
        epsilon_min: float = 0.01
    ):
        """
        Q学習エージェントを初期化

        Args:
            n_states: 離散状態の数
            n_actions: 離散行動の数
            alpha: 学習率
            gamma: 割引率
            epsilon: 初期探索率
            epsilon_decay: 各エピソード後のイプシロン減衰係数
            epsilon_min: イプシロンの最小値
        """
        self.n_states = n_states
        self.n_actions = n_actions
        self.alpha = alpha
        self.gamma = gamma
        self.epsilon = epsilon
        self.epsilon_decay = epsilon_decay
        self.epsilon_min = epsilon_min

        # Qテーブルをゼロで初期化
        self.Q = np.zeros((n_states, n_actions))

    def select_action(self, state: int) -> int:
        """
        イプシロン貪欲ポリシーを使用して行動を選択

        Args:
            state: 現在の状態

        Returns:
            選択された行動
        """
        if np.random.random() < self.epsilon:
            # 探索：ランダムな行動
            return np.random.randint(self.n_actions)
        else:
            # 活用：貪欲な行動
            return int(np.argmax(self.Q[state]))

    def update(
        self,
        state: int,
        action: int,
        reward: float,
        next_state: int,
        done: bool
    ):
        """
        Q学習の更新則を使用してQ値を更新

        Q(s,a) <- Q(s,a) + alpha * [r + gamma * max_a' Q(s',a') - Q(s,a)]

        Args:
            state: 現在の状態
            action: 実行した行動
            reward: 受け取った報酬
            next_state: 次の状態
            done: エピソードが終了したかどうか
        """
        if done:
            # 終端状態には将来の価値がない
            td_target = reward
        else:
            # Q学習：次の状態のQ値の最大値を使用
            td_target = reward + self.gamma * np.max(self.Q[next_state])

        # TD誤差
        td_error = td_target - self.Q[state, action]

        # Q値を更新
        self.Q[state, action] += self.alpha * td_error

    def decay_epsilon(self):
        """各エピソード後に探索率を減衰"""
        self.epsilon = max(self.epsilon_min, self.epsilon * self.epsilon_decay)


def train_q_learning(
    env: gym.Env,
    agent: QLearningAgent,
    n_episodes: int = 1000,
    max_steps: int = 200
) -> Tuple[List[float], List[int]]:
    """
    環境でQ学習エージェントを訓練

    Args:
        env: Gymnasium環境
        agent: Q学習エージェント
        n_episodes: 訓練エピソード数
        max_steps: エピソードあたりの最大ステップ数

    Returns:
        (エピソード報酬, エピソード長) のタプル
    """
    episode_rewards = []
    episode_lengths = []

    for episode in range(n_episodes):
        state, _ = env.reset()
        total_reward = 0
        steps = 0

        for step in range(max_steps):
            # 行動を選択
            action = agent.select_action(state)

            # 行動を実行
            next_state, reward, terminated, truncated, _ = env.step(action)
            done = terminated or truncated

            # Q値を更新
            agent.update(state, action, reward, next_state, done)

            total_reward += reward
            steps += 1

            if done:
                break

            state = next_state

        # イプシロンを減衰
        agent.decay_epsilon()

        episode_rewards.append(total_reward)
        episode_lengths.append(steps)

        # 進捗ログ
        if (episode + 1) % 100 == 0:
            avg_reward = np.mean(episode_rewards[-100:])
            print(f"エピソード {episode + 1}: 平均報酬 = {avg_reward:.2f}, "
                  f"イプシロン = {agent.epsilon:.3f}")

    return episode_rewards, episode_lengths


# FrozenLakeでの訓練デモンストレーション
print("=== FrozenLakeでのQ学習訓練 ===\n")

env = gym.make('FrozenLake-v1', is_slippery=False)

agent = QLearningAgent(
    n_states=env.observation_space.n,
    n_actions=env.action_space.n,
    alpha=0.1,
    gamma=0.99,
    epsilon=1.0,
    epsilon_decay=0.995,
    epsilon_min=0.01
)

rewards, lengths = train_q_learning(env, agent, n_episodes=500)

# 学習したQテーブルを表示
print("\n=== 学習したQテーブル（4x4グリッドに整形） ===")
print("各状態での最良行動:")
action_names = ['左', '下', '右', '上']
policy = [action_names[np.argmax(agent.Q[s])] for s in range(16)]
for i in range(4):
    print(policy[i*4:(i+1)*4])

env.close()

2.3 SARSAアルゴリズム

オンポリシーTD制御

SARSA（State-Action-Reward-State-Action）はオンポリシーの時間差分制御アルゴリズムです。Q学習とは異なり、SARSAは実際に追従しているポリシーの価値を学習します。

SARSAの更新則

SARSAの核となる更新式は以下の通りです：

Q学習との違いに注目してください：

• Q学習：$\max_{a'} Q(s_{t+1}, a')$（最良の行動）を使用
• SARSA：$Q(s_{t+1}, a_{t+1})$（実際の次の行動）を使用

SARSAがオンポリシーである理由

SARSAという名前は、各更新で使用される5つ組 $(S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1})$ に由来しています。

SARSAは（同じポリシーで選択された）実際の次の行動 $a_{t+1}$ を使用するため、追従しているポリシーの価値を学習します。エージェントが最適でない探索をすると、SARSAはその価値推定にそれを反映させます。

重要な洞察：SARSAは将来の探索的な（潜在的に悪い）行動の可能性を考慮するため、「より安全な」ポリシーを学習します。

SARSAの完全な実装

# Requirements:
# - Python 3.9+
# - numpy>=1.24.0
# - gymnasium>=0.29.0

import numpy as np
import gymnasium as gym
from typing import Tuple, List, Optional

class SARSAAgent:
    """
    イプシロン貪欲探索を用いたSARSAエージェント

    追従しているポリシーの価値を学習する
    オンポリシーTD制御アルゴリズムを実装しています。
    """

    def __init__(
        self,
        n_states: int,
        n_actions: int,
        alpha: float = 0.1,
        gamma: float = 0.99,
        epsilon: float = 0.1,
        epsilon_decay: float = 1.0,
        epsilon_min: float = 0.01
    ):
        """
        SARSAエージェントを初期化

        Args:
            n_states: 離散状態の数
            n_actions: 離散行動の数
            alpha: 学習率
            gamma: 割引率
            epsilon: 初期探索率
            epsilon_decay: イプシロンの減衰係数
            epsilon_min: イプシロンの最小値
        """
        self.n_states = n_states
        self.n_actions = n_actions
        self.alpha = alpha
        self.gamma = gamma
        self.epsilon = epsilon
        self.epsilon_decay = epsilon_decay
        self.epsilon_min = epsilon_min

        self.Q = np.zeros((n_states, n_actions))

    def select_action(self, state: int) -> int:
        """イプシロン貪欲ポリシーを使用して行動を選択"""
        if np.random.random() < self.epsilon:
            return np.random.randint(self.n_actions)
        else:
            return int(np.argmax(self.Q[state]))

    def update(
        self,
        state: int,
        action: int,
        reward: float,
        next_state: int,
        next_action: Optional[int],
        done: bool
    ):
        """
        SARSAの更新則を使用してQ値を更新

        Q(s,a) <- Q(s,a) + alpha * [r + gamma * Q(s',a') - Q(s,a)]

        Args:
            state: 現在の状態
            action: 実行した行動
            reward: 受け取った報酬
            next_state: 次の状態
            next_action: 次の行動（同じポリシーから）、終端ならNone
            done: エピソードが終了したかどうか
        """
        if done:
            td_target = reward
        else:
            # SARSA：実際の次の行動のQ値を使用
            td_target = reward + self.gamma * self.Q[next_state, next_action]

        td_error = td_target - self.Q[state, action]
        self.Q[state, action] += self.alpha * td_error

    def decay_epsilon(self):
        """探索率を減衰"""
        self.epsilon = max(self.epsilon_min, self.epsilon * self.epsilon_decay)


def train_sarsa(
    env: gym.Env,
    agent: SARSAAgent,
    n_episodes: int = 1000,
    max_steps: int = 200
) -> Tuple[List[float], List[int]]:
    """
    環境でSARSAエージェントを訓練

    Q学習との違いに注意：SARSAは更新に a_{t+1} が必要なため、
    更新前に次の行動を選択します。

    Args:
        env: Gymnasium環境
        agent: SARSAエージェント
        n_episodes: 訓練エピソード数
        max_steps: エピソードあたりの最大ステップ数

    Returns:
        (エピソード報酬, エピソード長) のタプル
    """
    episode_rewards = []
    episode_lengths = []

    for episode in range(n_episodes):
        state, _ = env.reset()
        action = agent.select_action(state)  # 最初の行動を選択

        total_reward = 0
        steps = 0

        for step in range(max_steps):
            # 行動を実行
            next_state, reward, terminated, truncated, _ = env.step(action)
            done = terminated or truncated

            # 次の行動を選択（SARSA更新用）
            if not done:
                next_action = agent.select_action(next_state)
            else:
                next_action = None

            # (s, a, r, s', a') を使用してQ値を更新
            agent.update(state, action, reward, next_state, next_action, done)

            total_reward += reward
            steps += 1

            if done:
                break

            # 次の状態と行動に移動
            state = next_state
            action = next_action

        agent.decay_epsilon()

        episode_rewards.append(total_reward)
        episode_lengths.append(steps)

        if (episode + 1) % 100 == 0:
            avg_reward = np.mean(episode_rewards[-100:])
            print(f"エピソード {episode + 1}: 平均報酬 = {avg_reward:.2f}, "
                  f"イプシロン = {agent.epsilon:.3f}")

    return episode_rewards, episode_lengths


# 訓練デモンストレーション
print("=== FrozenLakeでのSARSA訓練 ===\n")

env = gym.make('FrozenLake-v1', is_slippery=False)

sarsa_agent = SARSAAgent(
    n_states=env.observation_space.n,
    n_actions=env.action_space.n,
    alpha=0.1,
    gamma=0.99,
    epsilon=1.0,
    epsilon_decay=0.995,
    epsilon_min=0.01
)

sarsa_rewards, sarsa_lengths = train_sarsa(env, sarsa_agent, n_episodes=500)

print("\n=== SARSAが学習したポリシー ===")
action_names = ['左', '下', '右', '上']
policy = [action_names[np.argmax(sarsa_agent.Q[s])] for s in range(16)]
for i in range(4):
    print(policy[i*4:(i+1)*4])

env.close()

2.4 Q学習とSARSAの比較

主な違い

オンポリシー vs オフポリシー：実践的な意味

Q学習（オフポリシー）：

• 任意のポリシー（ランダムや古いポリシーを含む）で収集したデータから学習可能
• 経験を再利用する際のサンプル効率が高い
• 完璧な実行を前提とした危険なポリシーを学習する可能性がある

SARSA（オンポリシー）：

• 実行しているポリシーから学習する必要がある
• エージェント自身の探索ミスを考慮する
• 危険な環境でより安全なポリシーを学習する

どちらを選ぶべきか

• Q学習を使う場合：
  • 失敗のコストが低いシミュレーションで訓練する場合
  • 理論的に最適なポリシーが欲しい場合
  • 経験再生を使用する予定の場合（オフポリシーが必要）
• SARSAを使う場合：
  • 実ハードウェア（ロボティクス）で訓練する場合
  • 探索中の失敗コストが高い場合
  • 探索を考慮した安全なポリシーが欲しい場合

2.5 探索戦略の詳細

効果的な探索は強化学習において非常に重要です。ここでは3つの人気のある戦略を検討します。

1. 減衰付きイプシロン貪欲法

最もシンプルな探索戦略です：

イプシロンは通常、時間とともに減衰します：$\epsilon_t = \epsilon_0 \cdot \text{decay}^t$

2. ボルツマン（ソフトマックス）探索

Q値に基づいて確率的に行動を選択します：

ここで $\tau$ は温度パラメータです：

• $\tau \to 0$：貪欲（決定論的）
• $\tau \to \infty$：一様ランダム
• $\tau = 1$：標準的なソフトマックス

3. 信頼上限（UCB）

不確実性を使用して探索と活用のバランスを取ります：

ここで：

• $N(s, a)$ は状態 $s$ で行動 $a$ が選択された回数
• $c$ は探索係数
• ボーナス項 $\sqrt{\frac{\ln t}{N(s, a)}}$ は訪問回数の少ない行動を試すことを促進

探索戦略の比較

# Requirements:
# - Python 3.9+
# - numpy>=1.24.0
# - matplotlib>=3.7.0

import numpy as np
import matplotlib.pyplot as plt

class ExplorationStrategy:
    """探索戦略の基底クラス"""

    def select_action(self, q_values: np.ndarray, **kwargs) -> int:
        raise NotImplementedError


class EpsilonGreedy(ExplorationStrategy):
    """イプシロン貪欲探索"""

    def __init__(self, epsilon: float = 0.1):
        self.epsilon = epsilon

    def select_action(self, q_values: np.ndarray, **kwargs) -> int:
        if np.random.random() < self.epsilon:
            return np.random.randint(len(q_values))
        return int(np.argmax(q_values))


class BoltzmannExploration(ExplorationStrategy):
    """ボルツマン（ソフトマックス）探索"""

    def __init__(self, temperature: float = 1.0):
        self.temperature = temperature

    def select_action(self, q_values: np.ndarray, **kwargs) -> int:
        # 数値安定性：最大値を引く
        exp_values = np.exp((q_values - np.max(q_values)) / self.temperature)
        probabilities = exp_values / np.sum(exp_values)
        return np.random.choice(len(q_values), p=probabilities)


class UCBExploration(ExplorationStrategy):
    """信頼上限探索"""

    def __init__(self, c: float = 2.0):
        self.c = c

    def select_action(
        self,
        q_values: np.ndarray,
        visit_counts: np.ndarray = None,
        total_steps: int = 1,
        **kwargs
    ) -> int:
        if visit_counts is None:
            return np.random.randint(len(q_values))

        # 未訪問の行動を処理
        if np.min(visit_counts) == 0:
            return int(np.argmin(visit_counts))

        # UCB公式
        ucb_values = q_values + self.c * np.sqrt(
            np.log(total_steps) / visit_counts
        )
        return int(np.argmax(ucb_values))


# 探索戦略を比較
print("=== 探索戦略の比較 ===\n")

# 4行動問題のシミュレートされたQ値
q_values = np.array([1.0, 2.0, 1.5, 0.5])  # 行動1が最良
visit_counts = np.array([100, 50, 75, 25])

strategies = {
    'イプシロン貪欲 (eps=0.1)': EpsilonGreedy(epsilon=0.1),
    'イプシロン貪欲 (eps=0.3)': EpsilonGreedy(epsilon=0.3),
    'ボルツマン (tau=0.5)': BoltzmannExploration(temperature=0.5),
    'ボルツマン (tau=1.0)': BoltzmannExploration(temperature=1.0),
    'UCB (c=2)': UCBExploration(c=2.0),
}

n_samples = 10000

print(f"Q値: {q_values}")
print(f"訪問回数: {visit_counts}\n")

fig, axes = plt.subplots(1, len(strategies), figsize=(15, 4))

for idx, (name, strategy) in enumerate(strategies.items()):
    action_counts = np.zeros(4)

    for step in range(n_samples):
        if isinstance(strategy, UCBExploration):
            action = strategy.select_action(
                q_values,
                visit_counts=visit_counts,
                total_steps=step + 1
            )
        else:
            action = strategy.select_action(q_values)
        action_counts[action] += 1

    action_probs = action_counts / n_samples

    axes[idx].bar(range(4), action_probs, color=['#e74c3c', '#27ae60', '#3498db', '#9b59b6'])
    axes[idx].set_xlabel('行動')
    axes[idx].set_ylabel('選択確率')
    axes[idx].set_title(name)
    axes[idx].set_xticks(range(4))
    axes[idx].set_ylim(0, 1)

    print(f"{name}:")
    print(f"  行動確率: {action_probs}")

plt.tight_layout()
plt.savefig('exploration_strategies.png', dpi=150, bbox_inches='tight')
print("\n保存しました: exploration_strategies.png")
plt.close()

2.6 崖歩き問題

環境の説明

崖歩き（Cliff Walking）環境は、Q学習とSARSAの違いを完璧に示す古典的な問題です。これは4x12のグリッドワールドです：

• スタート：左下隅（状態36）
• ゴール：右下隅（状態47）
• 崖：スタートとゴールの間の最下行（状態37-46）
• 報酬：ステップごとに-1、崖から落ちると-100（そしてスタートにリセット）

なぜ崖歩きは比較に最適なのか

この環境では：

• Q学習は最適経路を学習：崖の縁に沿って右に歩く（最短だが危険）
• SARSAはより安全な経路を学習：上に行き、横断し、下に降りる（長いが安全）

この違いは、SARSAがイプシロン貪欲探索によってエージェントが誤って崖から落ちる可能性を考慮するために生じます。

崖歩きの完全な実装

# Requirements:
# - Python 3.9+
# - numpy>=1.24.0
# - gymnasium>=0.29.0
# - matplotlib>=3.7.0

import numpy as np
import gymnasium as gym
import matplotlib.pyplot as plt
from typing import Tuple, List

def train_and_compare_cliff_walking(
    n_episodes: int = 500,
    alpha: float = 0.5,
    gamma: float = 1.0,
    epsilon: float = 0.1
) -> Tuple[np.ndarray, np.ndarray, List[float], List[float]]:
    """
    崖歩きでQ学習とSARSAの両方を訓練して比較

    Args:
        n_episodes: 訓練エピソード数
        alpha: 学習率
        gamma: 割引率（エピソディック・非割引の場合は1.0）
        epsilon: 探索率（固定、減衰なし）

    Returns:
        (Q_qlearning, Q_sarsa, qlearning_rewards, sarsa_rewards) のタプル
    """
    # 環境を作成
    env_q = gym.make('CliffWalking-v0')
    env_s = gym.make('CliffWalking-v0')

    n_states = env_q.observation_space.n   # 48状態（4x12）
    n_actions = env_q.action_space.n       # 4行動（上、右、下、左）

    # Qテーブルを初期化
    Q_qlearning = np.zeros((n_states, n_actions))
    Q_sarsa = np.zeros((n_states, n_actions))

    qlearning_rewards = []
    sarsa_rewards = []

    for episode in range(n_episodes):
        # === Q学習エピソード ===
        state_q, _ = env_q.reset()
        total_reward_q = 0

        while True:
            # イプシロン貪欲行動選択
            if np.random.random() < epsilon:
                action = np.random.randint(n_actions)
            else:
                action = int(np.argmax(Q_qlearning[state_q]))

            next_state, reward, terminated, truncated, _ = env_q.step(action)
            done = terminated or truncated

            # Q学習更新：次の状態の最大値を使用
            if done:
                td_target = reward
            else:
                td_target = reward + gamma * np.max(Q_qlearning[next_state])

            Q_qlearning[state_q, action] += alpha * (
                td_target - Q_qlearning[state_q, action]
            )

            total_reward_q += reward
            state_q = next_state

            if done:
                break

        qlearning_rewards.append(total_reward_q)

        # === SARSAエピソード ===
        state_s, _ = env_s.reset()

        # 最初の行動を選択
        if np.random.random() < epsilon:
            action_s = np.random.randint(n_actions)
        else:
            action_s = int(np.argmax(Q_sarsa[state_s]))

        total_reward_s = 0

        while True:
            next_state, reward, terminated, truncated, _ = env_s.step(action_s)
            done = terminated or truncated

            # 次の行動を選択（SARSA用）
            if not done:
                if np.random.random() < epsilon:
                    next_action = np.random.randint(n_actions)
                else:
                    next_action = int(np.argmax(Q_sarsa[next_state]))

            # SARSA更新：実際の次の行動を使用
            if done:
                td_target = reward
            else:
                td_target = reward + gamma * Q_sarsa[next_state, next_action]

            Q_sarsa[state_s, action_s] += alpha * (
                td_target - Q_sarsa[state_s, action_s]
            )

            total_reward_s += reward
            state_s = next_state

            if done:
                break

            action_s = next_action

        sarsa_rewards.append(total_reward_s)

    env_q.close()
    env_s.close()

    return Q_qlearning, Q_sarsa, qlearning_rewards, sarsa_rewards


def visualize_cliff_walking_results(
    Q_qlearning: np.ndarray,
    Q_sarsa: np.ndarray,
    qlearning_rewards: List[float],
    sarsa_rewards: List[float]
):
    """Q学習とSARSAの比較を可視化"""

    fig, axes = plt.subplots(2, 2, figsize=(14, 10))

    # --- プロット1：学習曲線 ---
    ax1 = axes[0, 0]

    # 移動平均で報酬を平滑化
    window = 10
    q_smooth = np.convolve(qlearning_rewards, np.ones(window)/window, mode='valid')
    s_smooth = np.convolve(sarsa_rewards, np.ones(window)/window, mode='valid')

    ax1.plot(q_smooth, label='Q学習', color='#e74c3c', linewidth=2)
    ax1.plot(s_smooth, label='SARSA', color='#3498db', linewidth=2)
    ax1.set_xlabel('エピソード')
    ax1.set_ylabel('報酬の合計（平滑化）')
    ax1.set_title('学習曲線：Q学習 vs SARSA')
    ax1.legend()
    ax1.grid(True, alpha=0.3)

    # --- プロット2：Q学習ポリシーの可視化 ---
    ax2 = axes[0, 1]
    visualize_policy(Q_qlearning, ax2, "Q学習ポリシー（最適だが危険）")

    # --- プロット3：SARSAポリシーの可視化 ---
    ax3 = axes[1, 0]
    visualize_policy(Q_sarsa, ax3, "SARSAポリシー（安全な経路）")

    # --- プロット4：最終性能比較 ---
    ax4 = axes[1, 1]

    # 最後の100エピソードの平均
    q_final = np.mean(qlearning_rewards[-100:])
    s_final = np.mean(sarsa_rewards[-100:])

    bars = ax4.bar(['Q学習', 'SARSA'], [q_final, s_final],
                   color=['#e74c3c', '#3498db'])
    ax4.set_ylabel('平均報酬（最後の100エピソード）')
    ax4.set_title('最終性能比較')
    ax4.axhline(y=-13, color='green', linestyle='--',
                label='最適値（探索なし）', linewidth=2)
    ax4.legend()

    # バーに値ラベルを追加
    for bar, val in zip(bars, [q_final, s_final]):
        ax4.text(bar.get_x() + bar.get_width()/2, bar.get_height() + 1,
                f'{val:.1f}', ha='center', fontsize=12, fontweight='bold')

    plt.tight_layout()
    plt.savefig('cliff_walking_comparison.png', dpi=150, bbox_inches='tight')
    print("保存しました: cliff_walking_comparison.png")
    plt.close()


def visualize_policy(Q: np.ndarray, ax, title: str):
    """崖歩きグリッド上にポリシーを矢印で可視化"""

    # 行動矢印：上=0、右=1、下=2、左=3
    arrows = {0: (0, 0.3), 1: (0.3, 0), 2: (0, -0.3), 3: (-0.3, 0)}

    # グリッドを作成
    grid = np.zeros((4, 12))

    # 崖をマーク
    for j in range(1, 11):
        grid[3, j] = -1  # 崖

    ax.imshow(grid, cmap='RdYlBu', alpha=0.3)

    # ポリシー矢印を描画
    for state in range(48):
        row = state // 12
        col = state % 12

        # 崖セルとゴールをスキップ
        if row == 3 and 1 <= col <= 10:
            ax.text(col, row, 'X', ha='center', va='center',
                   fontsize=12, color='red', fontweight='bold')
            continue

        if row == 3 and col == 11:
            ax.text(col, row, 'G', ha='center', va='center',
                   fontsize=14, color='green', fontweight='bold')
            continue

        if row == 3 and col == 0:
            ax.text(col, row, 'S', ha='center', va='center',
                   fontsize=14, color='blue', fontweight='bold')

        best_action = np.argmax(Q[state])
        dx, dy = arrows[best_action]
        ax.arrow(col, row, dx, dy, head_width=0.15, head_length=0.1,
                fc='black', ec='black')

    ax.set_xlim(-0.5, 11.5)
    ax.set_ylim(3.5, -0.5)
    ax.set_xticks(range(12))
    ax.set_yticks(range(4))
    ax.set_title(title)
    ax.grid(True, alpha=0.3)


# 比較を実行
print("=== 崖歩き：Q学習 vs SARSA ===\n")

Q_q, Q_s, rewards_q, rewards_s = train_and_compare_cliff_walking(
    n_episodes=500,
    alpha=0.5,
    gamma=1.0,
    epsilon=0.1
)

print(f"Q学習 最終平均報酬（最後の100）: {np.mean(rewards_q[-100:]):.2f}")
print(f"SARSA 最終平均報酬（最後の100）: {np.mean(rewards_s[-100:]):.2f}")

visualize_cliff_walking_results(Q_q, Q_s, rewards_q, rewards_s)

print("\n=== 経路分析 ===")
print("Q学習は崖の縁に沿って右に歩くことを学習（最適だが危険）")
print("SARSAはまず上に行き、次に横断して崖を避けることを学習")
print("epsilon=0.1では、Q学習は訓練中に時々崖から落ちるが、")
print("SARSAは探索ミスを考慮したより安全な経路を学習する。")

経路の違いを理解する

なぜQ学習は危険な経路を取るのか？
Q学習は更新に $\max_{a'} Q(s', a')$ を使用します。これはエージェントが将来最適に行動すると仮定し、探索的な行動の可能性を無視します。イプシロンが0であるかのように最適なポリシーを学習するのです。

なぜSARSAは安全な経路を取るのか？
SARSAは $Q(s', a')$ を使用し、ここで $a'$ は実際の次の行動（探索的かもしれない）です。崖の近くでは、SARSAはイプシロン貪欲探索によって時々崖に向かって一歩踏み出すことを「知っている」ため、崖から離れることを学習します。

2.7 Expected SARSA

次の行動の期待値を取る

Expected SARSAは、単一のサンプル行動ではなく、ポリシーの下での期待値を使用するバリアントです：

イプシロン貪欲ポリシーの場合：

Expected SARSAの特性

• SARSAより低い分散（サンプルではなく期待値を使用）
• オンポリシーにもオフポリシーにもなれる（期待値で使用するポリシーに依存）
• $\epsilon = 0$（貪欲ポリシー）のときQ学習に帰着
• 一般的に多くの環境でQ学習とSARSAの両方より優れた性能を発揮

# Requirements:
# - Python 3.9+
# - numpy>=1.24.0

import numpy as np

def expected_sarsa_update(
    Q: np.ndarray,
    state: int,
    action: int,
    reward: float,
    next_state: int,
    done: bool,
    alpha: float,
    gamma: float,
    epsilon: float
) -> None:
    """
    Expected SARSAの更新則

    単一の次の行動をサンプリングするのではなく、
    イプシロン貪欲ポリシーの下で次の行動の期待値を使用します。
    """
    n_actions = Q.shape[1]

    if done:
        td_target = reward
    else:
        # イプシロン貪欲ポリシーの下での期待値
        # E[Q(s', a')] = eps/n * sum(Q(s', :)) + (1-eps) * max(Q(s', :))
        greedy_action = np.argmax(Q[next_state])
        expected_q = (
            (epsilon / n_actions) * np.sum(Q[next_state]) +
            (1 - epsilon) * Q[next_state, greedy_action]
        )
        td_target = reward + gamma * expected_q

    td_error = td_target - Q[state, action]
    Q[state, action] += alpha * td_error


# 使用例
print("=== Expected SARSAの例 ===\n")

# シンプルなQテーブルの例
Q = np.array([
    [1.0, 2.0, 1.5, 0.5],  # 状態 0
    [0.8, 1.2, 0.9, 1.5],  # 状態 1
])

epsilon = 0.1
n_actions = 4

# 状態1について：
# max Q = 1.5（行動3）
# sum Q = 0.8 + 1.2 + 0.9 + 1.5 = 4.4
# Expected Q = (0.1/4) * 4.4 + 0.9 * 1.5 = 0.11 + 1.35 = 1.46

expected_q = (epsilon / n_actions) * np.sum(Q[1]) + (1 - epsilon) * np.max(Q[1])
print(f"状態1のQ値: {Q[1]}")
print(f"イプシロン貪欲（epsilon={epsilon}）の下での期待Q: {expected_q:.3f}")
print(f"最大Q（Q学習で使用）: {np.max(Q[1]):.3f}")
print(f"サンプルQ（SARSAで使用）: サンプリングされた行動に依存")

まとめ

本章では、テーブル形式強化学習の2つの基本的なTD制御アルゴリズムを学びました：

重要なポイント

アルゴリズム選択ガイド

次のステップ

第3章：Deep Q-Network（DQN）では、ニューラルネットワーク関数近似を使用して大規模かつ連続状態空間を扱う方法を学びます。主要なトピック：

• なぜテーブル形式手法は大規模状態空間で失敗するか
• ニューラルネットワーク関数近似
• 安定した学習のための経験再生
• 振動を防ぐためのターゲットネットワーク
• DQNのバリアント：Double DQN、Dueling DQN、Rainbow

演習問題