🖖

もう一度、強化学習を理解する

2025/01/18に公開

はじめに

強化学習はLLMのRLHFや、ロボット制御、自動運転技術などで活用されています。
以前、私が書いたDPOの記事で触れたPPOの実装を試そうと思いましたが、強化学習は機械学習や深層学習と比べて抽象的で分かりづらい部分も多いです。今回の記事でPPOの実装の前に強化学習の基本的なアルゴリズムについてシンプルな迷路問題を題材にスクラッチでコードを書いて理解を深めていきます。

対象者

  • 私のように強化学習や深層強化学習を実装してみたいが、基礎的な理解や実装のイメージがわかない方
  • 強化学習を試してみたいけれど、抽象的な説明が多くて挫折しそうになった方

強化学習とは

強化学習は、「環境」(state: s)、「行動」(action: a)、「報酬」(reward: r)、「方策」(policy: π)を定義し、最適な行動を探索する手法です。
モデルが環境内で試行錯誤を繰り返すことで、目的を達成する最適な方策を探索します。

  1. 現在の状態 s を観測する
  2. 方策 \pi に基づいて行動 a を選択する
  3. 行動の結果として得られる報酬 r を観測する
  4. 新たな状態 s' に移行する
  5. 過去の経験を元に方策を更新する

手法

今回は、以下の強化学習のアルゴリズムを取り上げます。

  1. モンテカルロ法
  2. SARSA
  3. Q学習
  4. DQN(Deep Q-Network)

1. モンテカルロ法

1エピソードが終了する毎に最適行動価値を更新します。モンテカルロ法では、全ての探索(経路)を含める逐一訪問と最初の訪問だけを用いる初回訪問があります。今回実装しているコードは、初回訪問を用いていますま。

Q(s,a) \leftarrow Q(s,a) + \alpha [G_t - Q(s,a)]
  • Q(s,a): 状態 s で行動 a を取ったときの価値(期待累積報酬)。
  • \alpha: 学習率(0~1)。
  • G_t = \sum_{k=0}^\infty \gamma^k \cdot r_{t+k+1}: エピソード終了までの累積報酬。

2. SARSA

現在と次の最適行動価値(TD誤差)を使って最適行動価値を更新します。次の最適行動価値は方策に基づき選択肢し、(オンポリシー)更新します。

Q(s,a) \leftarrow Q(s,a) + \alpha [r + \gamma \cdot Q(s',a') - Q(s,a)]
  • Q(s,a): 状態 s で行動 a を取ったときの価値(期待累積報酬)。
  • \alpha: 学習率(0~1)。
  • r: 即時報酬。
  • \gamma: 割引率(未来の報酬の重要度を調整)。
  • Q(s',a'): 次の状態 s' で実際に選択した行動 a' に対するQ値。

3. Q学習

現在と次の最適行動価値(TD誤差)を使って最適行動価値を更新します。SARSAと似ていますが、次の最適行動価値は方策を用いず最大の最適価値を用いて(オフポリシー)更新します。

Q(s,a) \leftarrow Q(s,a) + \alpha [r + \gamma \cdot \max_a Q(s',a) - Q(s,a)]
  • Q(s,a): 状態 s で行動 a を取ったときの価値(期待累積報酬)。
  • \alpha: 学習率(0~1)。
  • r: 即時報酬。
  • \gamma: 割引率(未来の報酬の重要度を調整)。
  • \max_a Q(s',a): 次の状態 s' での最大のQ値。

4. DQN(Deep Q-Network)

深層学習を用いてQ値を近似

\theta \leftarrow \theta + \alpha \nabla_\theta \left[ \left( r + \gamma \cdot \max_a Q(s',a';\theta^-) - Q(s,a;\theta) \right)^2 \right]
  • \theta: ニューラルネットワークのパラメータ。
  • Q(s,a;\theta): 現在のニューラルネットワークによるQ値の近似。
  • \alpha: 学習率(0~1)。
  • r: 即時報酬。
  • \gamma: 割引率(未来の報酬の重要度を調整)。
  • \max_a Q(s',a';\theta^-): 一定期間固定されたターゲットネットワーク \theta^- に基づいて計算された次の状態 s' の最大Q値。
  • \theta^-: 一定期間固定されたターゲットネットワークのパラメータ。

今回の題材

  • 8*8の迷路 ※黄色が最短ルートです。
  • 壁(進めない):1
  • トラップ:-1
  • ゴール:2

8*8の迷路

目的

  • ゴールに到着するルートを見つける。
  • 最短(最大報酬)でゴールする。

報酬の設定

今回の迷路では、最終的なスコアがちょうど 0点 になるようにゴールの報酬を13点と設定し、それ以外を設定しています。

  • ゴール:+13点
  • トラップ:-3点
  • 1ターンごと:-1点
  • 前と同じ場所に戻る:-2点

最大報酬の例

  • ゴール時の報酬:+13点
  • 最大ターン数(14ターン)によるペナルティ:-1点 × 13ターン = -13点
  • 最終スコア:13点(ゴール) - 13点(ペナルティ) = 0点

コードの概要

探索が収束しないケースに対応するため、最大ステップ数を制限してます。
Qテーブルは、迷路内の各位置での行動(上下左右)に対応する報酬値を保持します。以下のように初期化します。

  • 初期値:0(もしくはランダム値、今回は0を使用)
  • 形式:タプル形式で「行位置」「列位置」「4つの行動(上下左右)の報酬値」を持つ
  • 最大行動数:無限に行動されたら困るので、max_stepsを指定して打ち切ります。

迷路の 3行4列目で、「右に移動する」が最適行動の場合:

( (2), (3), (0.01, 0.2, 0.15, 0.8) )

コード

コードはトグルに格納しています。

迷路設定と初期設定
# 迷路設定
# (0: 道, 1: 壁, 2: ゴール, -1: トラップ)
maze = [
    [0, 0, 0, 0, 1, 0, 0, 0],
    [0, 1, 1, 0, -1, 0, -1, 0],
    [0, -1, 0, 0, 1, 0, -1, 0],
    [0, 1, 0, 0, 0, 0, 1, 0],
    [0, 0, -1, 1, 1, 0, 1, 0],
    [0, 0, 0, 0, 1, 0, -1, 0],
    [0, 0, 1, 0, -1, 1, 1, 0],
    [1, 0, 0, 0, 0, 0, 0, 2],
]

# 初期状態
start_position = (0, 0)  # スタート地点
goal_position = (7, 7)   # ゴール地点
# 報酬関数
def get_reward(old_state, new_state):
    # もし移動先が今と同じなら -2
    if new_state == old_state:
        return -2
    x, y = new_state
    # ゴール
    if (x, y) == goal_position:
        return 13
    # トラップ
    elif maze[x][y] == -1:
        return -3
    # 通常
    else:
        return -1

# 方向のマッピング
actions = [(0, -1), (0, 1), (-1, 0), (1, 0)]  # 上, 下, 左, 右

# エージェントの移動
def move_agent(state, action):
    new_state = (state[0] + actions[action][0], state[1] + actions[action][1])
    if new_state[0] < 0 or new_state[0] >= len(maze) or \
       new_state[1] < 0 or new_state[1] >= len(maze[0]) or \
       maze[new_state[0]][new_state[1]] == 1:
        return state
    return new_state

# 結果の格納
results = {
    "monte_carlo": [],
    "sarsa": [],
    "q_learning": [],
    "dqn": []
}
# パラメタ
alpha = 0.1   # 学習率
gamma = 0.9   # 割引率
epsilon = 0.1 # ε-グリーディポリシーのε
num_episodes = 500
max_steps = 200
アルゴリズムのコード
# モンテカルロ法
def monte_carlo():
    q_table = np.zeros((len(maze), len(maze[0]), len(actions)))
    returns = {} 
    rewards = []
    best_path = []
    best_reward = float('-inf')

    for episode in range(num_episodes):
        state = start_position
        path = [state]
        episode_data = []
        total_reward = 0
        done = False
        step_count = 0

        # エピソード生成
        while not done:
            step_count += 1
            # ε-グリーディポリシーで行動を選択
            if random.uniform(0, 1) < epsilon:
                action = np.random.choice(len(actions))
            else:
                action = np.argmax(q_table[state[0], state[1]])

            next_state = move_agent(state, action)
            reward = get_reward(state, next_state)
            total_reward += reward
            path.append(next_state)

            # 状態, 行動, 報酬を記録
            episode_data.append((state, action, reward))
            state = next_state

            # 終了条件
            if state == goal_position or step_count >= max_steps:
                done = True

        rewards.append(total_reward)
        if total_reward > best_reward:
            best_reward = total_reward
            best_path = path

        # モンテカルロ更新
        g = 0
        visited = set()
        for step in reversed(episode_data):
            state, action, reward = step
            g = reward + gamma * g

            # 初めて訪れた状態-行動ペアのみ更新
            if (state, action) not in visited:
                visited.add((state, action))
                if (state, action) not in returns:
                    returns[(state, action)] = []
                returns[(state, action)].append(g)
                q_table[state[0], state[1], action] = np.mean(returns[(state, action)])

    results["monte_carlo"] = {"rewards": rewards, "path": best_path}
# SARSA
def sarsa():
    q_table = np.zeros((len(maze), len(maze[0]), len(actions)))
    rewards = []
    best_path = []
    best_reward = float('-inf')
    for episode in range(num_episodes):
        state = start_position
        path = [state]
        action = np.random.choice(len(actions)) if random.uniform(0, 1) < epsilon else np.argmax(q_table[state[0], state[1]])
        total_reward = 0
        done = False
        step_count = 0  # --- ステップ数を追加 ---
        while not done:
            step_count += 1
            next_state = move_agent(state, action)
            path.append(next_state)

            # --- 修正: 引数を (state, next_state) に ---
            reward = get_reward(state, next_state)
            total_reward += reward

            next_action = np.random.choice(len(actions)) if random.uniform(0, 1) < epsilon else np.argmax(q_table[next_state[0], next_state[1]])

            q_table[state[0], state[1], action] += alpha * (
                reward + gamma * q_table[next_state[0], next_state[1], next_action]
                - q_table[state[0], state[1], action]
            )
            state, action = next_state, next_action
            if state == goal_position or step_count >= max_steps:
                done = True
        rewards.append(total_reward)
        if total_reward > best_reward:
            best_reward = total_reward
            best_path = path
    results["sarsa"] = {"rewards": rewards, "path": best_path}
# Q学習
def q_learning():
    q_table = np.zeros((len(maze), len(maze[0]), len(actions)))
    rewards = []
    best_path = []
    best_reward = float('-inf')
    for episode in range(num_episodes):
        state = start_position
        path = [state]
        total_reward = 0
        done = False
        step_count = 0
        while not done:
            step_count += 1
            action = np.random.choice(len(actions)) if random.uniform(0, 1) < epsilon else np.argmax(q_table[state[0], state[1]])
            next_state = move_agent(state, action)
            path.append(next_state)
            reward = get_reward(state, next_state)
            total_reward += reward

            q_table[state[0], state[1], action] += alpha * (
                reward + gamma * np.max(q_table[next_state[0], next_state[1]])
                - q_table[state[0], state[1], action]
            )
            state = next_state
            if state == goal_position or step_count >= max_steps:
                done = True
        rewards.append(total_reward)
        if total_reward > best_reward:
            best_reward = total_reward
            best_path = path
    results["q_learning"] = {"rewards": rewards, "path": best_path}
# DQN
# ネットワークの定義
class DQNNetwork(nn.Module):
    def __init__(self, state_size, action_size):
        super(DQNNetwork, self).__init__()
        self.fc = nn.Sequential(
            nn.Linear(state_size, 128),
            nn.ReLU(),
            nn.Linear(128, action_size)
        )

    def forward(self, x):
        return self.fc(x)

def dqn():
    device = torch.device("cuda" if torch.cuda.is_available() else "cpu")

    state_size = 2  # (x, y)
    action_size = len(actions)
    policy_net = DQNNetwork(state_size, action_size).to(device)
    target_net = DQNNetwork(state_size, action_size).to(device)
    target_net.load_state_dict(policy_net.state_dict())
    target_net.eval()

    optimizer = optim.Adam(policy_net.parameters(), lr=0.001)
    criterion = nn.MSELoss()

    memory = deque(maxlen=2000)
    batch_size = 64
    update_target_every = 10

    rewards = []
    best_path = []
    best_reward = float('-inf')

    for episode in range(num_episodes):
        state = np.array(start_position, dtype=np.float32)
        path = [tuple(state.astype(int))]
        total_reward = 0
        done = False
        step_count = 0

        while not done:
            step_count += 1

            # 行動選択 (ε-greedy)
            if random.uniform(0, 1) < epsilon:
                action = random.randint(0, action_size - 1)
            else:
                with torch.no_grad():
                    q_values = policy_net(torch.FloatTensor(state).to(device))
                    action = torch.argmax(q_values).item()

            # 移動
            old_state_int = (int(state[0]), int(state[1]))  # 報酬計算に使う
            next_state = np.array(move_agent(old_state_int, action), dtype=np.float32)
            path.append(tuple(next_state.astype(int)))
            reward = get_reward(
                old_state_int,
                (int(next_state[0]), int(next_state[1]))
            )
            total_reward += reward

            # 経験をメモリに保存
            memory.append((
                state,
                action,
                reward,
                next_state,
                (int(next_state[0]), int(next_state[1])) == goal_position
            ))

            # 状態を更新
            state = next_state

            # 終了判定
            if (int(state[0]), int(state[1])) == goal_position:
                done = True
            if step_count >= max_steps:
                done = True

            # ミニバッチ学習
            if len(memory) >= batch_size:
                batch = random.sample(memory, batch_size)
                states, actions_batch, rewards_batch, next_states, dones = zip(*batch)

                states = torch.FloatTensor(states).to(device)
                actions_batch = torch.LongTensor(actions_batch).unsqueeze(1).to(device)
                rewards_batch = torch.FloatTensor(rewards_batch).to(device)
                next_states = torch.FloatTensor(next_states).to(device)
                dones = torch.FloatTensor(dones).to(device)

                current_q = policy_net(states).gather(1, actions_batch).squeeze()
                with torch.no_grad():
                    max_next_q = target_net(next_states).max(1)[0]
                    target_q = rewards_batch + (gamma * max_next_q * (1 - dones))

                loss = criterion(current_q, target_q)
                optimizer.zero_grad()
                loss.backward()
                optimizer.step()

        # ターゲットネットの更新
        if episode % update_target_every == 0:
            target_net.load_state_dict(policy_net.state_dict())

        rewards.append(total_reward)
        if total_reward > best_reward:
            best_reward = total_reward
            best_path = path

    results["dqn"] = {"rewards": rewards, "path": best_path}

実行結果

8*8の報酬グラフ
8*8の報酬グラフ

学習した最適経路

Method: monte_carlo
Best Reward: -203
Optimal Path:
STEP数:  201
[(0, 0), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 1), (0, 2), (0, 1), (0, 2), (0, 3), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 3), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 3), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 3), (0, 2), (0, 1), (0, 2), (0, 1), (0, 0), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1), (0, 2), (0, 1)]
------------------------------
Method: sarsa
Best Reward: 0
Optimal Path:
STEP数:  15
[(0, 0), (1, 0), (2, 0), (3, 0), (4, 0), (4, 1), (5, 1), (6, 1), (7, 1), (7, 2), (7, 3), (7, 4), (7, 5), (7, 6), (7, 7)]
------------------------------
Method: q_learning
Best Reward: 0
Optimal Path:
STEP数:  15
[(0, 0), (1, 0), (2, 0), (3, 0), (4, 0), (5, 0), (5, 1), (5, 2), (5, 3), (6, 3), (7, 3), (7, 4), (7, 5), (7, 6), (7, 7)]
------------------------------
Method: dqn
Best Reward: 0
Optimal Path:
STEP数:  15
[(0, 0), (1, 0), (2, 0), (3, 0), (4, 0), (5, 0), (6, 0), (6, 1), (7, 1), (7, 2), (7, 3), (7, 4), (7, 5), (7, 6), (7, 7)]

結果の所見

  • モンテカルロ法は探索パターンが多いのか最適な報酬に収束しませんでした。
  • Q学習とSARSAは早い段階で収束しています。DQNは収束に時間がかかっているようですが、最大エポック数を直前に収束しています。
  • エポック数をいくつか変えて試してみましたがQ学習が最も安定して早く収束している印象です。

ちなみに

8*8の迷路ではモンテカルロ法が最適な報酬に収束しなかったので、4*4の迷路でも実行してみました。
モンテカルロ法は探索パターンが増えると手に負えなくなることがわかります。
4*4の報酬グラフ

まとめ

  • 報酬の設計:目的を達成するための適切な報酬設計が、学習の成功に大きな影響を与える。
  • アルゴリズム:モンテカルロ法、SARSA、Q学習、DQNのロジックが確認できた。
  • シミュレーション環境:学習や評価には適切なシミュレーション環境の構築が必要。

今回は、迷路探索を題材にして基本的な強化学習アルゴリズムをスクラッチで実装しました。
気合が入ったらDPOの記事で触れたPPOを試してみたいと思います。

Discussion