從經驗中學習價值：蒙地卡羅預測

為什麼需要免模型學習

動態規劃可以精確算出每個狀態的價值——但前提是你已經知道環境的轉移機率與獎勵函數。在多數真實問題中你並不知道。你無法寫下一個你從未完整分析過的遊戲的動態、機器人的接觸物理，或顧客的行為。但你能做的是行動並觀察：採取動作，看看接著出現什麼狀態與獎勵，然後從這串互動本身學習。

蒙地卡羅（Monte Carlo, MC）預測是做這件事最直接的方法。它的想法簡單到近乎尷尬：一個狀態的價值就是從它出發的期望回報，所以就用你觀察到的實際回報的平均來估計這個期望。這正是經典蒙地卡羅方法的精神——用樣本的平均取代難算的期望。

核心要求：完整的回合

要平均回報，你得先量到一個回報，而某狀態的回報是從該狀態到結束之間所有獎勵的折扣總和。因此蒙地卡羅需要互動真的會結束：它適用於回合制任務（episodic task）——會到達終止狀態的遊戲、會結束的機器人試驗、會完成的對話。你從頭到尾玩完一個回合（episode），再回頭計算你拜訪過的每個狀態最終跟著出現的回報。

G_t = R_{t+1} + \gamma R_{t+2} + \cdots = \sum_{k=0}^{\infty} \gamma^{k} R_{t+k+1}, \qquad V(s) = \mathbb{E}\,[\,G_t \mid S_t = s\,]

回报是直到回合结束的所有奖励的折扣总和；状态的价值就是从该状态出发的期望回报。

首次拜訪 vs 每次拜訪

在一個回合中，同一個狀態可能出現不只一次。這帶出一個問題：當我們為狀態 s 平均回報時，要用 s 每次出現後的回報，還是只用第一次的？這就是兩種標準變體。首次拜訪 MC（first-visit MC）對每個回合只平均 s 第一次被拜訪之後的回報。每次拜訪 MC（every-visit MC）則平均 s 每次出現之後的回報。

兩者在回合數增加時都會收斂到真實價值，但統計性質不同。首次拜訪在同一回合內的回報彼此獨立，使估計量成為獨立樣本的無偏平均——容易分析。每次拜訪在同一回合的回報彼此相關，所以在小樣本時有偏差，但仍是一致估計，而且通常實作上略簡單、用到更多資料。實務上兩者表現非常接近。

演算法，一步一步來

為每個狀態初始化一個估計值 V(s)（用零即可），並準備一種追蹤平均的方式——記錄次數與總和，或用增量更新。
依照目前的策略產生一個完整回合：s0, a0, r1, s1, a1, r2, …，直到終止。
從回合的尾端往回走，在每一步累積折扣回報 G = r + γ·G。
對每個拜訪過的狀態（首次拜訪：只取第一次出現），把 G 記錄為該狀態回報的又一個樣本。
把 V(s) 朝其觀察到的回報平均更新。在許多回合上重複。

# First-visit MC prediction for V (one episode)
G = 0
visited = set()
for t in reversed(range(len(episode))):       # walk backwards
    s, a, r = episode[t]
    G = r + gamma * G                          # discounted return from t
    if s not in [step.s for step in episode[:t]]:   # first visit?
        returns[s].append(G)
        V[s] = sum(returns[s]) / len(returns[s])    # average of samples

首次拜訪 MC，在回合上做一次反向掃描即可算完。

一個等價、省記憶體的形式是用增量平均 V(s) ← V(s) + (1/N(s))·(G − V(s))，其中 N(s) 計算拜訪次數。把 1/N(s) 換成一個小的固定步長 α，就成了一個能追蹤緩慢變動目標的方法——這個更新形狀你在時間差分學習中會再次遇到。

V(s) \leftarrow V(s) + \frac{1}{N(s)}\bigl(G - V(s)\bigr)

增量平均把每个状态的价值朝最新观测到的回报更新，步长为访问次数的倒数。

優點、缺點，以及接下來

蒙地卡羅的優點很實在：它不需要模型，對每個狀態的估計是無偏的（首次拜訪），而且不受馬可夫性質被破壞的影響，因為它從不依賴單步結構——它只看結果。它甚至能只估計少數感興趣狀態的價值，而不必掃過整個狀態空間。

缺點正好引出本主線其餘的內容。第一，你必須等到一個回合結束才能從它學到任何東西——對連續型任務毫無用處，回合很長時也很慢。第二，回報取決於一長串隨機選擇，所以 MC 估計的變異數很高，可能需要很多回合才穩定。下一篇保留免模型、由樣本驅動的精神，但藉由自助在回合進行中就學習——那就是時間差分學習。