AI時代系列(3) 機器學習三部曲: 📘 第三部：《強化學習 —— AI 的決策與進化》
27/100 第三週：📌 蒙地卡羅方法（Monte Carlo Methods）
27.蒙地卡羅控制策略 🔄 試著做、學著選，策略逐步改善！
_______________________________________
🎯 單元導讀：
前面幾個單元，我們學會了如何透過「試著玩、記錄回報」估算一個策略的好壞（策略評估）。
但這還不夠，我們想要讓 AI 不只評估，而是 不斷地改善策略、變得越來越聰明！
這正是「蒙地卡羅控制（Monte Carlo Control）」的重點所在：
📌 從試錯經驗中，學出更好的策略，直到收斂到最優解！
________________________________________
🧠 一、什麼是蒙地卡羅控制？
MC 控制是一種不依賴環境模型的策略優化技術。它的核心流程是：
1️⃣ 利用現有策略與環境互動（產生 episode）
2️⃣ 對每個狀態-動作對 (s, a) 統計其回報
3️⃣ 利用平均回報更新 Q 值
4️⃣ 根據 Q 值改善策略，通常用 ε-Greedy
5️⃣ 重複以上過程直到策略收斂
________________________________________
🔁 二、策略改進方式：ε-Greedy 策略
為了讓 AI 保持探索（而非過早陷入局部最優），我們通常不直接選 Q 最大值，而是：
如果 a 是目前 Q(s,a) 最大的行動：
π(a|s) = (1 - ε) + ε / |A(s)|
否則（a 不是最佳行動）：
π(a|s) = ε / |A(s)|
ε 是探索率（例如 0.1 代表 10% 會探索）
|A(s)| 是在狀態 s 下可選擇的行動總數
✅ 多數時間選最好的行動
✅ 少數時間仍然嘗試其他行動，保持學習機會
________________________________________
📦 三、蒙地卡羅控制（On-policy）的完整流程圖
graph LR
A[初始化策略 π] --> B[執行策略產生多次 episode]
B --> C[對每個 (s,a) 統計 Gt]
C --> D[更新 Q(s,a) 為平均回報]
D --> E[使用 ε-Greedy 更新策略 π]
E --> B
整個流程開始於初始化一個初始策略 π。接著，AI 依照當前的策略反覆執行多次完整的 episode（從起點到結束），在這些過程中記錄每次 (s,a) 配對所得到的回報 Gt。當所有資料收集完成後，將每個 (s,a) 出現時的回報進行平均，更新 Q(s,a) 的估計值。接著，利用新的 Q 值，透過 ε-Greedy 方式更新策略 π —— 也就是在大多數情況下選擇目前 Q 值最高的行動，但仍保留一定比例 ε 的隨機探索，避免過早陷入次佳解。更新後的策略再回到執行環節，持續進行迭代，直到收斂到穩定的最優策略。
________________________________________
💻 四、實作範例（簡化版 On-policy MC 控制）
python
from collections import defaultdict
import numpy as np
def epsilon_greedy(Q, state, n_actions, epsilon):
if np.random.rand() < epsilon:
return np.random.randint(n_actions)
else:
return np.argmax(Q[state])
def mc_control(env, num_episodes=10000, gamma=0.99, epsilon=0.1):
Q = defaultdict(lambda: np.zeros(env.action_space.n))
returns = defaultdict(list)
for _ in range(num_episodes):
episode = []
state = env.reset()
done = False
while not done:
action = epsilon_greedy(Q, state, env.action_space.n, epsilon)
next_state, reward, done, _ = env.step(action)
episode.append((state, action, reward))
state = next_state
G = 0
visited = set()
for t in reversed(range(len(episode))):
s, a, r = episode[t]
G = gamma * G + r
if (s, a) not in visited:
returns[(s, a)].append(G)
Q[s][a] = np.mean(returns[(s, a)])
visited.add((s, a))
return Q
整個流程開始於初始化一個初始策略 π。接著，AI 依照當前的策略反覆執行多次完整的 episode（從起點到結束），在這些過程中記錄每次 (s,a) 配對所得到的回報 Gt。當所有資料收集完成後，將每個 (s,a) 出現時的回報進行平均，更新 Q(s,a) 的估計值。接著，利用新的 Q 值，透過 ε-Greedy 方式更新策略 π —— 也就是在大多數情況下選擇目前 Q 值最高的行動，但仍保留一定比例 ε 的隨機探索，避免過早陷入次佳解。更新後的策略再回到執行環節，持續進行迭代，直到收斂到穩定的最優策略。
________________________________________
🎮 五、應用場景
應用 說明
走迷宮 找出安全而最短的路徑
黑傑克（Blackjack） 訓練 AI 學會何時該要牌、停牌
模擬對弈遊戲 模仿 AlphaGo 初期自我訓練
智能教學系統 根據學生反應調整出題策略，逐步改善教學效果
________________________________________
📊 六、與其他方法比較
在強化學習中，蒙地卡羅控制、Q-Learning 與 SARSA 都屬於「不需要模型（model-free）」的方法，也就是不必事先知道環境的轉移機率與報酬分布，但三者在學習方式上有明顯差異：
• 蒙地卡羅控制屬於「完整回合型學習（episode-based learning）」，必須等整個回合結束後，才能根據實際觀察到的完整回報（G 值）來更新所有曾出現過的 (狀態, 行動) 組合。更新時通常搭配 ε-Greedy 策略改進，保持探索與利用的平衡。
• Q-Learning 是典型的「離線 Off-policy 學習」，每走一步就即時更新 Q 值，利用當前下一狀態的最大 Q 值（max Q）來做更新。因為它用的是假設的「最佳行動」作為更新依據，因此屬於 Off-policy 學習。
• SARSA 則是「在線 On-policy 學習」，每一步更新時根據實際執行的行動 a' 來計算回報（而非取最大值），因此更新方向更忠實於當下的策略，適合學習期間仍在持續探索的情境。
總體來說：
• 蒙地卡羅控制強調完整回合觀察，適合線上模擬與探索初期；
• Q-Learning 學習收斂速度快，適合追求最優策略；
• SARSA 則更保守穩定，特別適合環境存在風險或探索安全性要求高的場景。
________________________________________
🧩 七、挑戰任務與反思：
1️⃣ 試著使用蒙地卡羅控制實作一個「走迷宮」任務，觀察策略如何改進?
可以設計一個 5x5 網格迷宮，起點在左上角，終點在右下角，中間放置一些障礙物。每次移動的獎勵為 -1，成功到達終點的獎勵為 +10。
使用蒙地卡羅控制時，agent 每次隨機探索完整個 episode，記錄整條路徑的 (state, action, reward) 資料，再根據整體回報更新 Q 值。隨著學習次數增加，策略會從隨機亂走，逐漸偏向成功通關的最佳路徑。這可以清楚觀察到 MC 控制透過完整經驗累積，不斷改進策略。
________________________________________
2️⃣ 在長 episode、稀疏獎勵的情況下，MC 控制有什麼挑戰？
當 episode 很長或只有最終成功才有高獎勵時，MC 控制面臨兩大挑戰：
• 學習收斂慢：需要完整 episode 才能更新，每次學習步驟間隔較長，導致學習效率低。
• 回報變異性高：若 agent 偶爾幸運通關，但大部分時間失敗，Q 值更新容易出現震盪，收斂不穩定。
因此在這類環境下，MC 控制效果有限，常需要非常多的樣本才能學到穩定的好策略。這也是為什麼在稀疏獎勵環境，TD 方法（如 Q-learning、SARSA）常優於純 MC 控制。
________________________________________
3️⃣ ε 該固定還是逐步降低？你會怎麼設計一個有效的探索機制？
探索參數 ε 建議採用逐步降低的設計。初期需要高 ε（如 1.0）來大量探索未知空間，隨著學習進展，慢慢衰減至較小值（如 0.1 或 0.05），以穩定學習結果。例如：
ε_t = ε_0 * exp(-k * t)
此外，也可以設計「分階段衰減」或「自適應衰減」：當 Q 值的變動幅度穩定時，自動降低探索；當發現某些區域仍有高度不確定性，則暫時提高探索，讓學習更有效率且穩定。
________________________________________
✅ 八、小結與啟示：
• 蒙地卡羅控制是強化學習中最直觀的策略優化方法之一
• 不需模型，完全靠「做 → 學 → 選 → 再做」的實戰訓練
• 策略逐步改善，最終可收斂至近似最優策略
• 適合可模擬環境的應用，也為 Actor-Critic 等方法奠定概念基礎！
