目錄／強化學習

時間差分學習與 Q-learning

動態規劃要先知道轉移機率 $P(s' \mid s, a)$。實際上常常不知道模型，只能和環境互動、記錄「在 s 做了 a，得到報酬 r、到了 s′」。時間差分學習（temporal-difference learning，TD）直接從這些經驗學習價值函數，不需要模型。

時間差分學習 TD Learning

Bellman 方程式說 $V(s)$ 應該等於 $r + \gamma V(s')$ 的期望值。每走一步，就把 $V(s)$ 往這一步看到的估計值拉近一點：

$$V(s) \leftarrow V(s) + \alpha\left[\underbrace{r + \gamma V(s')}_{\text{TD 目標}} - V(s)\right]$$

括號裡的差稱為 TD 誤差，α 是學習率。它不用等到整個回合結束才知道總報酬，每走一步就能更新，用的是「自己對下一個狀態的估計」（bootstrapping）。

Q-learning

只學 V 還不夠決定動作（要知道每個動作會到哪裡，又需要模型）。Q-learning（Watkins，1989）直接學動作價值 $Q(s, a)$，目標用的是下一個狀態中最好的動作：

$$Q(s, a) \leftarrow Q(s, a) + \alpha\left[r + \gamma \max_{a'} Q(s', a') - Q(s, a)\right]$$

學好之後，策略就是在每個狀態選 Q 最大的動作。只要每個狀態–動作都被試過無限多次，且學習率適當遞減，Q-learning 保證收斂到最佳的 $Q^*$。

探索與利用：若總是選目前 Q 最大的動作，可能永遠發現不了更好的路。最簡單的做法是 ε-貪婪：以機率 ε 隨機選一個動作（探索），否則選 Q 最大的（利用）。

SARSA：同策略與離策略 On-Policy vs Off-Policy

SARSA 的目標改用下一步實際要做的動作 a′（也是由 ε-貪婪選出）：

$$Q(s, a) \leftarrow Q(s, a) + \alpha\left[r + \gamma Q(s', a') - Q(s, a)\right]$$

名稱來自更新時用到的五個量 $(s, a, r, s', a')$。差別很微妙：Q-learning 學的是「之後都走最好的動作」的價值（離策略，off-policy），SARSA 學的是「照目前含探索的策略走下去」的價值（同策略，on-policy）。

範例：懸崖行走 Cliff Walking

Sutton 與 Barto 教科書的例子：4×12 的格子，從左下角走到右下角，中間的底排是懸崖，掉下去報酬 −100 並回到起點，其餘每走一步 −1。兩種方法都用 ε = 0.1、α = 0.2，訓練 500 回合：

# 懸崖行走（Sutton & Barto 例 6.6）：比較 Q-learning 與 SARSA
# 4×12 格，從左下角走到右下角，中間的底排是懸崖（掉下去 −100 並回到起點），每走一步 −1
import numpy as np

H, W = 4, 12
START, GOAL = (0, 0), (0, 11)                                          # (列, 行)，第 0 列是最下面
MOVES = [(1, 0), (0, 1), (-1, 0), (0, -1)]                              # 上、右、下、左

def step(s, a):
    r, c = min(max(s[0] + MOVES[a][0], 0), H - 1), min(max(s[1] + MOVES[a][1], 0), W - 1)
    if r == 0 and 0 < c < W - 1:
        return START, -100.0                                            # 掉下懸崖
    return (r, c), -1.0

def run(method, rng, episodes=500, alpha=0.2, eps=0.1):
    Q = np.zeros((H, W, 4))
    pick = lambda s: rng.integers(4) if rng.random() < eps else int(Q[s].argmax())   # ε-貪婪
    returns = []
    for _ in range(episodes):
        s, G = START, 0.0
        a = pick(s)
        while s != GOAL:
            s2, r = step(s, a)
            a2 = pick(s2)
            if s2 == GOAL:
                target = r
            elif method == "Q-learning":
                target = r + Q[s2].max()                                # 用「最好的下一步」更新（離策略）
            else:
                target = r + Q[s2][a2]                                  # 用「實際要走的下一步」更新（同策略）
            Q[s][a] += alpha * (target - Q[s][a])
            s, a, G = s2, a2, G + r
        returns.append(G)
    return Q, returns

def greedy_path(Q):
    s, cells = START, {START}
    for _ in range(60):
        s, _ = step(s, int(Q[s].argmax()))
        cells.add(s)
        if s == GOAL:
            break
    return cells

for method in ("Q-learning", "SARSA"):
    avg = np.mean([np.mean(run(method, np.random.default_rng(k))[1][-100:]) for k in range(50)])
    Q, _ = run(method, np.random.default_rng(0))
    cells = greedy_path(Q)
    print(f"{method}：最後 100 回合的平均報酬（50 次平均）{avg:.1f}；學到的貪婪路徑：")
    for r in range(H - 1, -1, -1):
        print("   " + "".join("S" if (r, c) == START else "G" if (r, c) == GOAL else "*" if (r, c) in cells
                              else "x" if r == 0 else "." for c in range(W)))

⬇ 下載 cliff_walking.py（Python 3＋numpy）

實際執行的輸出：

Q-learning：最後 100 回合的平均報酬（50 次平均）-48.0；學到的貪婪路徑：
   ............
   ............
   ************
   SxxxxxxxxxxG
SARSA：最後 100 回合的平均報酬（50 次平均）-23.2；學到的貪婪路徑：
   ...***......
   .***.*******
   **.........*
   SxxxxxxxxxxG

Q-learning 學到貼著懸崖邊走的最短路線，這是不探索時真正最好的路。但訓練時有 10% 的機率隨機走一步，貼著懸崖走常常掉下去，所以訓練中的平均報酬約 −48。
SARSA 把「自己會隨機亂走」也算進價值裡，學到遠離懸崖的路線，路比較長，但很少掉下去，平均報酬約 −23。

對控制系統來說這個差別很重要：在實體設備上學習時，探索造成的失誤（例如撞到極限開關）是真實的代價，同策略的方法較保守。

理論上，若 ε 逐漸降到 0、同時每個狀態–動作仍被試過無限多次，兩種方法都會收斂到最短路線。但這兩個條件互相矛盾：探索一減少，貼著懸崖的格子就很少被試到。本站實驗中，讓 ε 從 0.1 逐漸降到 0、訓練到 5000 回合，SARSA 的路線只靠近到 15～17 步（和懸崖之間仍隔著至少一排），沒有走到貼著懸崖、最短的 13 步（verify_rl.py 核對）。理論保證的條件，在有限的訓練裡不一定做得到。

自製動畫（依控制理論數值模擬）

表格法的限制 Beyond Tables

這頁的方法都把每個狀態–動作的 Q 值存在一張表裡，只適用於狀態不多、而且是離散的問題。倒單擺的狀態是四個連續量（擺角、角速度、位置、速度）；即使每個量只切 20 格，也有 $20^4 = 160{,}000$ 個狀態，而且相鄰的狀態之間學到的經驗不能共用。解法是用函數（例如類神經網路）來近似 Q 或直接表示策略，這就是深度強化學習：DQN 與策略梯度方法，將在後續頁面以倒單擺為例介紹。