レッスン 3: モンテカルロと時間差学習

強化学習: 基礎から高度まで

パート 1: RL の基礎 — マルコフの意思決定プロセスと表形式の手法

xdev.asia

はじめに

モンテカルロ と 時間差 (TD) は 2 つの主要なモデルフリー手法であり、遷移確率を知る必要はありません。これは、DP から実際の RL への重要な移行です。

---

1. モンテカルロ予測

複数のエピソードからの収益を平均して V を推定します。

from collections import defaultdict

def mc_prediction(policy, env, num_episodes, gamma=1.0):
    returns_sum = defaultdict(float)
    returns_count = defaultdict(int)
    V = defaultdict(float)
    
    for _ in range(num_episodes):
        episode = generate_episode(policy, env)
        G = 0
        visited_states = set()
        
        for t in reversed(range(len(episode))):
            state, action, reward = episode[t]
            G = gamma * G + reward
            
            if state not in visited_states:  # First-visit MC
                visited_states.add(state)
                returns_sum[state] += G
                returns_count[state] += 1
                V[state] = returns_sum[state] / returns_count[state]
    return V

---

2. モンテカルロ制御

MC + ε-greedy ポリシーの改善:

def mc_control(env, num_episodes, gamma=1.0, epsilon=0.1):
    Q = defaultdict(lambda: np.zeros(env.action_space.n))
    returns_sum = defaultdict(float)
    returns_count = defaultdict(int)
    
    for _ in range(num_episodes):
        episode = generate_episode_epsilon_greedy(Q, env, epsilon)
        G = 0
        
        for t in reversed(range(len(episode))):
            state, action, reward = episode[t]
            G = gamma * G + reward
            sa_pair = (state, action)
            returns_sum[sa_pair] += G
            returns_count[sa_pair] += 1
            Q[state][action] = returns_sum[sa_pair] / returns_count[sa_pair]
    return Q

---

3. TD(0) 学習

各ステップの後に V を更新します (エピソードが終了するまで待つ必要はありません)。

$$V(s) \leftarrow V(s) + \alpha [r + \gamma V(s') - V(s)]$$

def td_prediction(policy, env, num_episodes, alpha=0.1, gamma=0.99):
    V = defaultdict(float)
    
    for _ in range(num_episodes):
        state, _ = env.reset()
        done = False
        while not done:
            action = policy(state)
            next_state, reward, terminated, truncated, _ = env.step(action)
            done = terminated or truncated
            
            # TD update
            td_target = reward + gamma * V[next_state] * (1 - done)
            td_error = td_target - V[state]
            V[state] += alpha * td_error
            
            state = next_state
    return V

---

4. SARSA — ポリシーに基づく TD コントロール

def sarsa(env, num_episodes, alpha=0.1, gamma=0.99, epsilon=0.1):
    Q = np.zeros((env.observation_space.n, env.action_space.n))
    
    for _ in range(num_episodes):
        state, _ = env.reset()
        action = epsilon_greedy(Q, state, epsilon)
        done = False
        
        while not done:
            next_state, reward, terminated, truncated, _ = env.step(action)
            done = terminated or truncated
            next_action = epsilon_greedy(Q, next_state, epsilon)
            
            # SARSA update: Q(s,a) += α[r + γQ(s',a') - Q(s,a)]
            Q[state, action] += alpha * (
                reward + gamma * Q[next_state, next_action] * (1-done) - Q[state, action]
            )
            state, action = next_state, next_action
    return Q

---

5. MC と TD の比較

側面	モンテカルロ	TD(0)
モデルフリー	✅	✅
オンライン	❌ (エピソード全体が必要)	✅ (各ステップ)
バイアス	公平な	バイアス (ブートストラッピング)
分散	高	低い
継続的なタスクで動作します	❌	✅

---

概要

方法	主要なアイデア	更新
MC	平均完全収益率	アフターエピソード
TD(0)	次の状態からのブートストラップ	あらゆるステップ
サルサ	オンポリシー TD コントロール	Q(s,a) と実際の次のアクション