AI時代系列(3) 機器學習三部曲: 📘 第三部：《強化學習 —— AI 的決策與進化》
22/100 第三週：📌 蒙地卡羅方法（Monte Carlo Methods）
22.第一次-訪問與每次-訪問法 📋 兩種觀察方式，結果各異！
_______________________________________
🎯 單元導讀：
在上一單元中，我們認識了蒙地卡羅方法（Monte Carlo, MC）透過「樣本平均」來估算狀態價值。
但你知道嗎？
在一個 episode 中，同一狀態可能出現多次，究竟該怎麼記錄並估算其報酬呢？
這就帶出蒙地卡羅方法中的兩大實作方式：
First-Visit（第一次訪問法） vs Every-Visit（每次訪問法）
雖然兩者最終都會收斂，但學習效率、穩定性與實作策略，可能大不相同！
________________________________________
🧠 一、兩種估值法的定義
在蒙地卡羅方法中，First-Visit MC 與 Every-Visit MC 是兩種常見的估值方式。
First-Visit MC 只在每個 episode 中，當某狀態第一次出現時才記錄該次的累積報酬 Gₜ，這樣可以去除重複樣本，雖然學習速度較慢，但估計值穩定、偏差較小。
而 Every-Visit MC 則在每次遇到該狀態時都記錄 Gₜ，樣本數快速累積，學習速度較快，但可能會因重複樣本而引入較高的變異性。
無論哪一種方法，核心都是透過多次完整的 episode 累積從時間 t 到回合結束的 累積折扣報酬 Gₜ 來估計狀態價值 V(s)，隨著樣本增加，估計會逐步收斂至真實期望。
________________________________________
📦 二、範例說明
假設一個 episode 中的狀態序列為：
s0 → s1 → s2 → s1 → s3
First-Visit MC 統計
[第一次遇到 s1 時記錄 G (從第一次 s1 到結束的報酬)]
統計 G 值：
s1 (第一次出現) → G₁ = 累積報酬
（第二次出現的 s1 不記錄
Every-Visit MC 統計
[每次遇到 s1 都記錄對應的 G]
統計 G 值：
s1 (第一次出現) → G₁ = 累積報酬
s1 (第二次出現) → G₃ = 累積報酬（從第二次 s1 開始計算）
小總結
First-Visit：只統計第一次 s1 → G₁
Every-Visit：統計 s1 的兩次出現 → G₁ 與 G₃，兩個都計入平均
________________________________________
🔁 三、估值流程對比圖
graph LR
A[Episode 開始] --> B1[First-Visit 檢查是否第一次出現]
A --> B2[Every-Visit 全部記錄 Gt]
B1 --> C1[若第一次則更新 V(s)]
B2 --> C2[每次出現都更新 V(s)]
________________________________________
📊 四、優劣比較分析
在蒙地卡羅方法中，First-Visit MC 與 Every-Visit MC 各有優缺點。First-Visit MC 因只記錄每個狀態在每個 episode 中首次出現時的 G 值，有效避免樣本重複造成的偏差，適合變異性較低的任務，但因樣本累積較慢，收斂速度較慢，實作上需判斷是否為首次出現。
Every-Visit MC 每次狀態出現都記錄 G 值，樣本快速累積，收斂速度較快，但在高變異性環境中可能出現樣本偏誤，需留意穩定性。不過在理論上，兩者最終都能保證一致收斂，實作上 Every-Visit MC 邏輯較單純、易於程式實現。
________________________________________
💻 五、簡易實作範例（Python）
以B lackjack-v1 為例：
First-Visit MC：
python
visited_states = set()
for t in reversed(range(len(episode))):
state, _, reward = episode[t]
G = reward + gamma * G
if state not in visited_states:
returns[state].append(G)
V[state] = np.mean(returns[state])
visited_states.add(state)
Every-Visit MC：
python
for t in reversed(range(len(episode))):
state, _, reward = episode[t]
G = reward + gamma * G
returns[state].append(G)
V[state] = np.mean(returns[state])
以 Blackjack-v1 環境為例，First-Visit MC 和 Every-Visit MC 主要差異在是否避免重複統計同一個狀態。First-Visit MC 透過建立 visited_states 集合，在每次回溯過程中，僅在第一次遇到該狀態時才記錄對應的累積報酬 G，避免同一回合中重複樣本造成偏差。而 Every-Visit MC 則在每次回溯時都直接將當下狀態的 G 累計進 returns 中，無論是否已經記錄過，因此樣本累積較快，更新更頻繁。最後，兩者皆透過對該狀態的所有 G 取平均，更新狀態價值函數 V(s)。兩種方法在實作上邏輯簡單，僅差在是否判斷狀態是否首次出現，適合根據任務特性選用。
_______________________________________
🎮 六、實務應用選擇建議
情境 建議方法
教學示範、 避免樣本偏態 使用 First-Visit
環境簡單、資料收集快 使用 Every-Visit
線上學習（即時） 較不適合 MC，建議用 TD
________________________________________
🧩 七、問題挑戰與反思任務
1️⃣ 如果一個任務中狀態反覆出現頻率很高，你會選用哪一種方法？為什麼？
建議選用：First-Visit MC。
原因是當某些狀態在單一 episode 中高頻出現時，Every-Visit 會將這些重複樣本全部納入平均，可能導致某些 G 值偏重而產生樣本偏誤（尤其是在 early stage，樣本量還不夠平衡時）。First-Visit 透過只取首次出現的 G 值，避免單次 episode 內的樣本偏倚，讓估計過程更穩定，特別適合反覆狀態頻繁出現的環境。
________________________________________
2️⃣ First-Visit MC 為何能減少樣本偏誤？
原因：
• 每個 episode 中，同一狀態可能因為策略結構或環境設計反覆出現，若每次都累積 G 值，會讓高頻狀態的 early samples 對整體平均影響過重，形成「樣本集中偏誤」。
• First-Visit 僅記錄第一次出現時的 G，等於每個 episode 中，對每個狀態僅貢獻一筆樣本，讓各次 episode 貢獻的樣本權重一致。
• 這樣可以使不同 episode 之間的統計貢獻更均衡，降低 early bias，收斂雖稍慢，但估計更穩定。
_______________________________________
3️⃣ 試著設計一個小遊戲（如 4x4 走迷宮），記錄 First-Visit 與 Every-Visit 所產生的 Gₜ 差異。
設計範例：
• 地圖：4x4 迷宮（FrozenLake 類型簡化版）
• 起點：左上角 (0,0)，終點：右下角 (3,3)
• 有 2 個冰洞設置在 (1,1) 和 (2,2)
• 策略設計：智能體採隨機移動，容易在 (1,1) 附近來回滑動
• Episode 範例路徑：
• s0 → s1 → s5 → s1 → s6 → s10 → s14 → s15
• 其中 s1 出現兩次。
記錄差異：
• First-Visit：只記錄第一次 s1 出現的 G 值（假設為 0.7）
• Every-Visit：兩次 s1 出現，分別記錄 G₁=0.7 和 G₂=0.3，兩筆樣本都進入平均
差異說明：若 s1 在多數 episode 中持續高頻出現，Every-Visit 對 s1 的統計樣本成長速度快，但容易受這些重複樣本主導平均值；First-Visit 則保持每回合每狀態一筆樣本，避免樣本權重失衡，收斂穩定但速度稍慢。
___________________________________
✅ 八、小結與啟示：
• 蒙地卡羅方法中有兩種觀察法：First-Visit（穩健）與 Every-Visit（效率高）
• 雖然理論上都會收斂，但實際應用場景與任務性質，會大幅影響表現
• 瞭解兩者差異，有助於未來開發更有效率的策略學習系統！
