跳轉到

3.2 Q-Learning（1989）與 ε-greedy、表格方法的極限#

前言：從「評估策略」躍升到「學最優策略」#

TD(λ) 解決了評估（給定策略學 \(v^\pi\) ），但學完 \(v^\pi\) 還是不能直接行動——要選動作得靠 \(P(s'|s,a)\) （第 2.1 節的難題），或得知道「如果換成貪婪策略，價值會變成什麼」。1989 年，Chris Watkins 在劍橋的博士論文中提出 Q-Learning：直接學 Q 函數 \(q^*(s,a)\) ——「這一步先做 \(a\) ，之後永遠貪婪」的價值。它有一個驚人性質：完全 off-policy——不論你當下的行為策略多爛（探索用什麼都行），只要每個 \((s,a)\) 被嘗試無窮多次， \(Q\) 會收斂到 \(q^*\) ，與探索方式無關。這一性質把「探索」與「學習」徹底解耦，配合 ε-greedy 成為之後三十年 RL 的主力工具：TD-Gammon（6.1）、DQN（4.1）的核心更新就是它。本節講清 Q-Learning 的數學、ε-greedy 的探索原理、表格方法的樣本與維度極限——後者正是把本書推向第 4 章深度方法的直接壓力。

歷史背景：Watkins、Sutton 與一場關鍵的博士生答辯#

1989 年，Sutton 在劍橋一場研討會上講 TD 學習；台下博士生 Chris Watkins 當場意識到：如果把 TD 的預測目標從 \(v\) 換成 \(q\) ，並在更新中對下一狀態取 max，就能繞過「需要知道模型才能改進策略」的瓶頸。他的 1989 年博士論文《Learning from Delayed Rewards》系統地提出了 Q-Learning 並證明其收斂性（Watkins & Dayan 1992 在《Machine Learning》正式發表）。這是 RL 史上最戲劇性的「理論即刻催生演算法」案例之一。同一時期，控制理論界（Bertsekas, Tsitsiklis）用非同步隨機逼近證明了同一演算法；Sutton 與 Barto 1998 的教科書《Reinforcement Learning: An Introduction》把整條線整合成標準框架。之後 1992 年 Tesauro 的 TD-Gammon 證明「TD+神經網路」能贏世界級棋手，但這條線在 1992-2013 年間陷入二十年的沉寂——不是理論不對，而是（1）表格與淺層網路的表達力不夠，（2）沒有標準化的環境基準讓方法可以比較與累積，（3）計算力不足。這三個缺口的填補分別是 DQN（第 4 章）、Gym（第 4 章）與 GPU——理解本節末尾的「極限」，就理解了 2013 年爆發的全部前因。

數學：Q-Learning 的更新與收斂#

更新規則#

每步觀察 \((s_t, a_t, r_{t+1}, s_{t+1})\) ，執行：

\[ Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha \left[ r_{t+1} + \gamma \max_{a'} Q(s_{t+1}, a') - Q(s_t, a_t) \right] \]

與 TD(0) 的差別一目了然：左邊更新的是 \(Q\) 而非 \(V\) ；右邊把「下一步的策略價值 \(V(s_{t+1})\) 」換成「下一步取 max 的 Q 值」。max 就是「假設下一步起永遠最優」——這正是 Bellman 最優方程（第 2.2 節）的右端！所以 Q-Learning 的更新是「把 Bellman 最優方程當作學習目標」：目標的期望不動點就是 \(q^*\) 。

為何 off-policy 可行（關鍵證明骨架）#

令行為策略（探索用）為 \(b(a|s)\) （任何保證 \(\pi_{\text{greedy}}(a|s) > 0\) 的策略皆可）。更新在給定 \(s_{t+1}\) 條件下的期望為：

\[ \mathbb{E}\left[ Q_{new}(s,a) \mid s_{t+1} \right] = (1-\alpha)Q(s,a) + \alpha\left[ r + \gamma \sum_{s'} P(s'|s,a) \max_{a'} Q(s',a') \right] \]

注意：行為策略 \(b\) 沒有出現在期望式中（它只決定「你去了哪裡」，不決定「目標是什麼」）。因此 \(Q\) 的期望動力學與行為策略無關，收縮映射 \(T^*Q = r + \gamma P \max Q\) 的不動點唯一且是 \(q^*\) 。加上 Robbins-Monro 步長條件與「所有 \((s,a)\) 無窮次拜訪」，得機率 1 收斂到 \(q^*\) （Watkins & Dayan 1992）。對比第 3.1 節：TD(λ) 評估的是「你實際走的那個策略」，而 Q-Learning 評估的是「貪婪化之後的最優策略」——max 讓更新目標脫離了行為策略的綁架。

貪婪化與 ε-greedy#

有了 \(Q\) ，行動策略自然是貪婪： \(a = \arg\max_a Q(s,a)\) 。但純貪婪沒有探索（第 1.2 節差異三），標準解法 ε-greedy：

\[ \pi(a|s) = \begin{cases} \text{均匀隨機} & \varepsilon \\ \arg\max_a Q(s,a) & 1-\varepsilon \end{cases} \]

ε-greedy 的理論缺陷：它在所有狀態、對所有非最優動作花同樣的探索力度——已確認很差的動作還一直試。多臂老虎機理論給出更聰明的答案 UCB（Upper Confidence Bound, Auer et al. 2002）：

\[ a = \arg\max_a \left[ Q(s,a) + c \sqrt{\frac{\ln N(s)}{N(s,a)}} \right] \]

其中 \(N(s,a)\) 是該動作被嘗試次數：越少試過的動作，樂觀加分越大。這把「不確定性」變成「吸引力」，遺憾界為對數而非線性。記住這個式子——2016 年 AlphaGo 的 PUCT 公式 \(U(s,a) = Q(s,a) + c_{puct} P(s,a)\frac{\sqrt{\sum_b N}}{1+N(s,a)}\) 就是 UCB 加上先驗（網路的策略輸出 \(P\) ）的版本（第 6.2 節）。

程式碼：表格 Q-Learning 解 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

Q = np.zeros((S, A))                    # 表格: 16×4
EPISODES = 20000

for ep in range(EPISODES):
    obs, _ = env.reset(seed=ep)
    done = False
    while not done:
        # ε-greedy: 探索率線性衰減 1.0 → 0.05
        eps = max(0.05, 1.0 - ep / 10000)
        if np.random.random() < eps:
            a = env.action_space.sample()
        else:
            a = int(np.argmax(Q[obs]))  # 打破平手可加微小雜訊
        ns, r, term, trunc, _ = env.step(a)
        # 核心: Bellman 最優方程當學習目標 (off-policy)
        target = r + GAMMA * np.max(Q[ns]) * (not term)
        Q[obs, a] += 0.1 * (target - Q[obs, a])
        obs, done = ns, term or trunc

pi = np.argmax(Q, axis=1)
# 檢驗: 貪婪策略的實際勝率
env2 = gym.make("FrozenLake-v1", is_slippery=True)
wins = 0
for ep in range(1000):
    obs, _ = env2.reset(seed=10_000 + ep); done = False
    while not done:
        obs, r, term, trunc, _ = env2.step(int(pi[obs]))
        done = term or trunc
        if term: wins += (r == 1.0)
print(f"學得策略 1000 回合勝率: {wins/1000:.1%}   (動態規劃最優約 65-70%)")
print("學到的 Q 表 (前 4 狀態):")
print(np.round(Q[:4], 3))

觀察要點：（1）學得的勝率應接近（但可能略低於）第 2.2 節動態規劃的結果——我們全程沒看過 \(P\) 與 \(R\) ，只靠採樣就逼近了規劃的答案；（2）探索率必須從高衰減：初期高 ε 才能找到路徑，後期低 ε 才能精修；（3）(not term) 處理終止狀態——終點的「未來價值」必須為 0，否則 \(q^*\) 的定義會被破壞（常見 bug）。

表格方法的極限：三重天花板#

  1. 維度災難：表格大小 \(= |\mathcal{S}| \times |\mathcal{A}|\) 。FrozenLake 是 \(16 \times 4\) ，輕鬆；Atari 畫面是 \(2^{210 \times 160 \times 3}\) 量級的狀態空間，表格直接不可行。即便離散化，維度一高，「見過的狀態」占比趨近 0——泛化成為生死問題。
  2. 樣本效率：收斂條件要求「所有 \((s,a)\) 無窮次拜訪」。實際中多数 \((s,a)\) 永遠見不到幾次；表格無法把經驗從「相鄰狀態」借過來（狀態 14 的教訓救不了狀態 15）。函數近似的意義正是共享表示。
  3. 沒有標準環境：1990 年代每篇論文用自製環境，結果無法比較、無法累積。1998 年 Sutton & Barto 教科書催生了共同語言，但要等到 2016 年 OpenAI Gym（第 4 章）提供標準化 API（reset/step/space），深度 RL 才能以可比較、可複現的方式快速疊代。本書程式碼全程使用 Gymnasium API，正是踩在這個標準化遺產上。

這三個天花板在 1989-2013 年間都存在，逐一被破解的順序是：Gym（標準化）→ DQN（神經網路近似 Q）→ GPU 算力。第 4 章我們將看到：DQN 幾乎原封不動地保留了 Q-Learning 的更新式，只是把「查表 \(Q(s,a)\) 」換成「神經網路前向傳播」——但僅僅這一步替換，就引爆了致命三要素（自舉 + 函數近似 + off-policy），迫使經驗回放與目標網路誕生。

本節重點#

  1. Q-Learning（Watkins 1989）直接學 \(q^*\) ：更新式 \(Q \leftarrow Q + \alpha[r + \gamma \max_{a'} Q(s') - Q]\) 就是把 Bellman 最優方程當學習目標。
  2. off-policy 是它的超能力：max 使更新目標不受行為策略影響，探索（怎麼走）與學習（目標是什麼）解耦；配合「所有 (s,a) 無窮次拜訪」條件，機率 1 收斂到 \(q^*\) 。
  3. ε-greedy 簡單但對所有非最優動作一視同仁（線性 regret）；UCB 把不確定性轉為樂觀加分（對數 regret），其思路經 PUCT 進化成 AlphaGo 的樹搜尋核心。
  4. 表格方法的三重天花板：維度災難、無泛化的樣本效率、缺乏標準環境基準——1989-2013 的沉寂正是等這三題被破解。
  5. Q-Learning 的數學骨架（Bellman 最優方程 + 收縮映射 + 隨機逼近）自 1957-1989 一路未變；2013 年 DQN 的革命不在理論，而在「用神經網路承載這條方程」以及随之而來的穩定性工程。

思考問題#

  1. Q-Learning 收斂條件要求每個 \((s,a)\) 被拜訪無窮多次。在「探索必須穿過狹窄通道才能到達大片區域」的環境中，ε-greedy 為何可能永遠到不了？你會怎麼改進探索？
  2. 把程式中 eps 的衰減改成「保持 0.2 不變」與「0.9 快速衰減」，比較最終勝率。請解釋兩種失敗模式（探索不足 vs. 永遠被隨機動作干擾）。
  3. 第 2.2 節說最優策略存在且確定性；本節 Q-Learning 學的正是 \(q^*\) 。那為什麼實務中學到的 \(\arg\max Q\) 常常在「兩個相近動作」間不穩定？這對後續（第 5 章）「直接學隨機策略」的動機有何啟示？
  4. UCB 公式中 \(\sqrt{\ln N(s)/N(s,a)}\) 在 \(N(s,a)=0\) 時無窮大。請說明這「無窮樂觀」的意義，以及它與嬰兒「什麼都往嘴裡塞」行為的類比。
  5. 若把 FrozenLake 狀態空間放大到 100×100，表格 Q-Learning 需要多少次有效拜訪才可能收斂？請估算並說明為何「函數近似共享表示」是唯一出路。