3.1 蒙地卡羅與時序差分 TD(λ)（1988）#
前言：不知道 P 與 R，如何評價一個狀態？#
第 2 章的動態規劃是「理想國」： \(P\) 與 \(R\) 已知，用收縮映射迭代即可。但現實中你面對的世界（Atari 遊戲、真實機器人、人類用戶）不給你轉移機率，只讓你互動、只回饋一個標量。於是核心問題變成：只憑採樣經驗，如何估計 \(v^\pi\) ？ 兩個答案構成了本節的對比軸：蒙地卡羅（MC）——等回合結束，用真實回報當目標；時序差分（TD）——每走一步，用自己下一步的估計當目標。Sutton 1988 年的論文《Learning to Predict by the Methods of Temporal Differences》把兩者用 TD(λ) 統一成一條光譜，並證明 TD 的收斂性。這一節的張力——自舉的偏差 vs. 等待的變異——將是貫穿全書的第一條主線，直接孕育了 Q-Learning（3.2）、DQN 的目標網路（4.1）與 TD-Gammon（6.1）。
歷史背景：Samuel 的遺產被重新發現#
1980 年代初，Sutton 在讀 Samuel 的跳棋論文時意識到：Samuel 1959 年「用後來的評估教先前的評估」的做法，正是心理學中次級強化物（secondary reinforcer）的計算版本——不是食物本身強化了行為，而是「接近食物的線索」成了強化物。Klopf 1972 年的理論也強調強化訊號應隨預測改變而改變。Sutton 把這些直覺整理成一個乾淨的數學問題：「多步預測的線上學習」，並在 1988 年於《Machine Learning》發表完整理論。這篇論文的三個貢獻至今仍是標準：（1）TD 更新規則與 TD 誤差；（2）TD(λ) 與資格跡的統一框架；（3）收斂性證明（表格、固定策略、機率 1 收斂到 \(v^\pi\) ）。Barto、Sutton 與 Anderson 1983 的 cart-pole Actor-Critic 是它的實踐先聲，而 Sutton 的博士生 Watkins（1989）將在一個關鍵的研討會上聽到這套理論後發展出 Q-Learning——歷史的因果鏈就藏這種師承與會議裡。
兩個演算法：定義與直覺#
蒙地卡羅（MC）：等答案#
策略 \(\pi\) 下採樣完整回合 \(\tau = (s_0, a_0, r_1, \ldots, r_T)\) ，對回合中每個首次拜訪的狀態 \(s_t\) ，用實際回報更新：
- 優點：目標 \(G_t\) 是 \(v^\pi(s_t)\) 的無偏估計（期望恰好等於真值）；不需要環境模型；不受其他狀態估計誤差的牽連。
- 缺點：必須等回合結束（長回合的遊戲、無終止的連續控制都難以適用）； \(G_t\) 的變異數極大（隨機策略下不同回合的 \(G_t\) 可差數倍），需要大量回合平均；不利用回報的遞迴結構（浪費資訊）。
TD(0)：用估計當答案#
- 優點：線上（每步更新）、增量（記憶體 \(O(|\mathcal{S}|)\) ）、自然處理無終止問題、變異數小（只依賴一步隨機性）。
- 缺點：目標 \(r + \gamma V(s_{t+1})\) 中的 \(V(s_{t+1})\) 是估計而非真值 → 有偏。若 \(V\) 初期很爛，目標也爛，學習早期是在「以錯教錯」。此外自舉會傳播誤差：一步估錯，會沿著鏈條往回污染。
一個數值例子感受差異#
假設 \(V\) 初值全為 0，你在真實世界走了一條路： \(s_1 \xrightarrow{r=0} s_2 \xrightarrow{r=0} s_3 \xrightarrow{r=1}\) （終點）。更新時刻對比：
| 時點 | MC 更新 | TD(0) 更新 |
|---|---|---|
| 到達 \(s_3\) 時 | 尚無更新（未結束） | \(V(s_3)\) 由 \(r=1\) 更新為 1 |
| 回合結束時 | \(V(s_1) \mathrel{+}= \alpha \cdot 1\) ， \(V(s_2) \mathrel{+}= \alpha \cdot 1\) ， \(V(s_3) \mathrel{+}= \alpha \cdot 1\) | 已在每步逐步把 1 往回傳一層 |
TD 用了 \(\gamma\) 把資訊逐步回傳，MC 則在終點一次到位。這就是「廣播 vs. 等待」的取捨。
數學：TD(λ) 與資格跡——把光譜連起來#
n 步回傳與 λ-回傳#
在「一步自舉（TD(0)）」與「無限步（MC）」之間是 n 步回傳：
TD(λ) 不選單一 \(n\) ，而是指數加權平均所有 n 步回傳（ \(\lambda \in [0,1]\) ，權重 \(\propto \lambda^{n-1}\) ），稱 λ-回傳 \(G_t^\lambda\) 。可以證明（Sutton 1988）前向視角下：
\(\lambda = 0\) ：只剩 \(G_t^{(1)}\) ，即 TD(0)； \(\lambda \to 1\) ：全為 MC。λ 是「信任自己估計的程度」旋鈕。
資格跡：後向視角的等價實作#
前向公式需要未來資訊（無法線上），Sutton 的工程天才在於發現一個線上等價的後向實作：
- 每拜訪狀態 \(s\) ： \(e(s) \leftarrow e(s) + 1\) （給它一條「跡」）。
- 每步衰減所有跡： \(e(s) \leftarrow \gamma \lambda\, e(s)\) 。
- 每步用共享的 TD 誤差 \(\delta_t = r_{t+1} + \gamma V(s_{t+1}) - V(s_t)\) 更新所有有跡的狀態： \(V(s) \leftarrow V(s) + \alpha\, \delta_t\, e(s)\) 。
含義：每個狀態保有「我最近多久沒被拜訪」的指數衰減記錄；任何時刻的預測誤差，沿著跡向過去分配功勞。 跡越長（λ 越大），功勞傳得越遠。數學上可證明（線性函數近似、on-policy）後向視角的更新與前向 λ-回傳的期望等效。
收斂性：為何 TD(0) 會學到真值#
定理（Sutton 1988; Watkins & Dayan 1992）：表格表示、固定策略、每個狀態-動作無限次拜訪、學習率滿足 \(\sum_t \alpha_t = \infty\) 、 \(\sum_t \alpha_t^2 < \infty\) （Robbins-Monro 條件），則 TD(0) 以機率 1 收斂到 \(v^\pi\) 。
證明骨架：把更新寫成隨機逼近形式 \(V_{t+1} = V_t + \alpha_t (b_t - A_t V_t)\) ，其中期望上 \(A_t = I - \gamma P^\pi\) （正定，因 \(\gamma < 1\) 與行隨機矩陣的性質）、 \(b_t\) 期望上收斂於 \(R^\pi\) 。Robbins-Monro + 噪音條件下隨機逼近收斂到線性系統 \((I - \gamma P^\pi)v = R^\pi\) 的解，而那正是 \(v^\pi\) （第 2.2 節的 Bellman 期望方程）。注意：MC 不需要這些條件也收斂（它就是普通的隨機梯度最小平方），而 TD 需要策略固定、表格、步長條件——當我們在第 4 章把表格換成神經網路、加上 off-policy 資料時，這些保證會全部失效，這正是「致命三要素（deadly triad）」的伏筆：自舉 + 函數近似 + off-policy = 理論上可發散。DQN 的目標網路、批次正規化等工程手段都是為了馴服它。
偏差-變異數的定量刻畫#
以 \(n\) 步目標為例： \(\mathrm{Var}[G_t^{(n)}]\) 隨 \(n\) 增大（更多隨機獎勵與轉移被計入），而偏差由 \(V\) 與真值的距離決定、隨 \(n\) 減小（自舉比例下降）。λ-回傳正是沿這條 trade-off 曲線的最優化點。實務經驗：自舉太強（λ≈0）→ 誤差自強化；完全不自舉（λ=1）→ 訊號太吵。中間值（TD-Gammon 用 λ≈0.7-0.9）往往最好。
程式碼：在 Gym 上直接對比 MC 與 TD#
用 Gym 的 FrozenLake 以隨機策略做策略評估，對比兩法的收斂速度與最終誤差：
# pip install gymnasium numpy
import gymnasium as gym
import numpy as np
env = gym.make("FrozenLake-v1", is_slippery=True)
S, A, GAMMA = env.observation_space.n, env.action_space.n, 0.99
P = env.unwrapped.P
# 解析真值: v^π 滿足線性方程組
V_true = np.zeros(S)
V = np.zeros(S)
for _ in range(10000): # 動態規劃算真值(僅為了對照)
V_new = np.zeros(S)
for s in range(S):
for a in range(A):
q = sum(p * (r + GAMMA * V[ns]) for p, ns, r, _ in P[s][a]) / A
V_new[s] += q
V = V_new
V_true = V
def run(method, alpha=0.05, episodes=2000, lam=None, seed=0):
rng = np.random.default_rng(seed)
V = np.zeros(S); errors = []
for ep in range(episodes):
obs, _ = env.reset(seed=ep)
done = False
if method == "MC": # 蒙地卡羅: 先存整條軌跡
traj = []
while not done:
a = rng.integers(A)
ns, r, term, trunc, _ = env.step(a)
traj.append((obs, r)); obs = ns
done = term or trunc
G, first = 0.0, set()
for s, r in reversed(traj):
G = r + GAMMA * G
if s not in first: # first-visit
first.add(s)
V[s] += alpha * (G - V[s])
elif method == "TD0": # TD(0): 每步更新
while not done:
a = rng.integers(A)
ns, r, term, trunc, _ = env.step(a)
V[obs] += alpha * (r + GAMMA * V[ns] - V[obs])
obs, done = ns, term or trunc
elif method == "TDL": # TD(λ) 資格跡
e = np.zeros(S)
while not done:
a = rng.integers(A)
ns, r, term, trunc, _ = env.step(a)
delta = r + GAMMA * V[ns] - V[obs]
e[obs] += 1
V += alpha * delta * e # 所有有跡狀態一起更新
e *= GAMMA * lam
obs, done = ns, term or trunc
if (ep + 1) % 100 == 0:
errors.append(np.abs(V - V_true).mean())
return errors
for name, kw in [("MC", {}), ("TD0", {}), ("TDL(lam=0.8)", dict(lam=0.8))]:
err = run(name, **kw)
print(f"{name:14s} 前100回合均誤差={err[0]:.3f} 500回合={err[4]:.3f} 2000回合={err[-1]:.3f}")
典型結果：TD0 與 TDL 早期誤差下降最快（資訊即時回傳），MC 前期較慢但最終也收斂；TDL(lam=0.8) 常在整體上最平衡。你可以把 alpha 加大觀察：MC 爆震盪、TD 可能發散——這是「自舉對步長更敏感」的實體感受，也是第 4 章 DQN 需要目標網路的直覺基礎。
本節重點#
- 無模型策略評估的兩極：MC（等局終、無偏但高變異、需終止）vs. TD(0)（每步更新、低變異、有偏且誤差會傳播）。
- TD(λ) 用 λ-回傳把所有 n 步目標做指數加權平均；資格跡給出其線上後向等價實作——「預測誤差沿時間軸向過去分配功勞」，正面回答第 1 章的信用分配問題。
- TD 收斂定理依賴表格、固定策略、Robbins-Monro 步長；一旦換成函數近似 + off-policy + 自舉（致命三要素），理論保證消失——這是理解 DQN 一切工程補丁的鑰匙。
- 偏差-變異數取捨由 λ 控制：自舉強→快但有偏，自舉弱→慢但準。實務常取中間值。
- Samuel 1959 的自舉直覺 → Sutton 1988 的理論與演算法 → 1989 Watkins 的 Q-Learning：一條清晰的學術因果鏈。
思考問題#
- MC 的目標無偏、TD 的目標有偏，但實務上 TD 幾乎總是學得更快。請用「變異數影響需要的樣本數」定量解釋這個悖論。
- 在什麼樣的環境中（回合極長？永不終止？獎勵極噪？）你會選 MC 而不是 TD？請給出至少兩個具體條件。
- 資格跡更新 \(V \leftarrow V + \alpha \delta e\) 一次更新所有狀態。請說明這與第 2 章 Bellman 算子「一次掃描全部狀態」的異同——兩者都是「全域更新」，但資訊來源有何根本不同？
- 若環境轉移機率在學習中途改變（非平穩），MC 與 TD 哪個適應較快？為什麼「忘掉舊資料」的速度在此至關重要？（這也預告了第 4 章經驗回放的兩難。）
- 致命三要素中，若你只能消除其中一個來保證穩定，你會選哪個？分別說明消除「自舉」（如第 6 章 AlphaGo 的做法）與消除「off-policy」（如 on-policy PPO）各自的代價。