第 3 課：蒙地卡羅和時間差分學習

強化學習：從基礎到高級

第 1 部分：強化學習基礎 — 馬可夫決策過程與表格方法

亞洲開發網

簡介

蒙特卡羅和時間差分 (TD) 是兩種核心的無模型方法 - 無需知道轉移機率。這是從 DP 到實際 RL 的重要轉變。

---

1. 蒙地卡羅預測

透過平均多個情節的回報來估計 V(s)：

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+ε-貪婪策略改進：

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 比較

方面	蒙地卡羅	達陣 (0)
無模型	✅	✅
線上	❌（需要完整劇集）	✅（每一步）
偏見	公正	有偏見（引導）
方差	高	低
適用於連續任務	❌	✅

---

總結

方法	關鍵想法	更新
主持人	平均完全回報	劇集結束後
達陣 (0)	從下一個狀態引導	每一步
非典	同策略 TD 控制	Q(s,a) 與實際的下一步行動