2.1 Markov 決策過程：狀態、獎勵與策略（1957）#

前言：把「決策」變成數學#

第 1 章我們確認了強化學習的核心處境：沒有標籤、只有回饋、必須探索。但要在數學上談「最優行為」，我們需要一個形式化的世界模型。這就是 Markov 決策過程（Markov Decision Process, MDP）——1957 年由 Richard Bellman 在RAND 公司研究序列決策時正式提出。MDP 是整本書的語法：之後所有方法（TD、Q-Learning、DQN、PPO、AlphaZero、RLHF）都只是「當你不知道 MDP 的某些部分時，該如何應對」的不同策略。本節我們把 MDP 的六個要素、Markov 性質、折扣因子、策略與價值函數的定義一次講透，並用 Gym 的實例讓你摸得到它。

歷史背景：從最優控制到 Bellman#

1950 年代的背景問題來自最優控制（optimal control）：飛彈軌道、庫存管理、資源分配——都是「序列決策」問題。當時的主流工具是變分法（calculus of variations）與 Pontryagin 的極大值原理，它們擅長連續時間問題，但（1）要求系統動力學已知且可微，(2) 對高維、離散、隨機的問題束手無策。

Bellman 在 RAND 研究多階段決策時發現：與其一次解整條軌跡，不如逐段求解——「最優策略的剩餘部分，相對於當前狀態也是最優的」。這個看似顯然的觀察（後稱最優性原理）把全域優化拆解成一組局部遞迴，配合電腦的迭代計算能力，誕生了動態規劃（dynamic programming）。「dynamic」指問題隨時間演化，「programming」在當時指規劃而非程式設計。

Bellman 提到當時他在 RAND 遭遇的困擾：國防部長不喜歡「規劃」這個詞，於是他把方法命名為「動態規劃」——「它聽起來像科幻小說，又像原子能，完美得無法反駁。」這段軼事提醒我們：MDP 框架從誕生起就是為了實際計算服務，而非純理論。

幾乎同時，俄國的 Kolmogorov 學派（Markov 過程）、經濟學的 Shapley（隨機博弈 1953）也在同樣的數學上工作。MDP 是這些線索的匯流。它之後六十多年的命運也值得注意：1957-1988 年間 MDP 是控制理論的專利，AI 界幾乎不碰；1988-2013 年間它成為 RL 的理論骨架；2013 年之後，它成為深度學習時代的訓練範式——包括 LLM 的 RLHF（把「狀態」定義為對話歷史）。一個 1957 年的框架，成為 2024 年推理模型的訓練語言，這是本書要反覆強調的「理論的前因後果」。

MDP 的形式定義：五元組#

一個 MDP 由 \(\langle \mathcal{S}, \mathcal{A}, P, R, \gamma \rangle\) 定義：

\(\mathcal{S}\) ：狀態集——環境在每個時刻的全部相關資訊。
\(\mathcal{A}\) ：動作集——決策者可做的選擇（可依狀態不同而不同： \(\mathcal{A}(s)\) ）。
\(P(s'|s,a)\) ：轉移核——在狀態 \(s\) 執行 \(a\) 後，轉移到 \(s'\) 的機率。
\(R(s,a)\) 或 \(r = R(s,a,s')\) ：獎勵函數——轉移伴隨的即時報酬（常含隨機性）。
\(\gamma \in [0,1)\) ：折扣因子——未來獎勵的現值折損率。

互動過程：在 \(t\) 時刻，環境處於 \(S_t = s\) ，agent 選動作 \(A_t = a\) ，環境回饋獎勵 \(R_{t+1}\) 並轉移到 \(S_{t+1}\) 。軌跡（trajectory/episode）為：

\[ S_0, A_0, R_1, S_1, A_1, R_2, S_2, \ldots \]

回報（return）定義為折扣總和：

\[ G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1} \]

\(\gamma\) 的三重角色：

數學收斂性：若獎勵有界且 \(\gamma < 1\) ， \(G_t\) 幾乎必然收斂（ \(|G_t| \le \max|r|/(1-\gamma)\) ），使期望值與不動點方程有意義。
經濟直覺：今天的 1 元勝過明天的 1 元； \(\gamma\) 是利率的倒數概念。
決策視野的旋鈕： \(\gamma \to 0\) 是近視（只看眼前一步）， \(\gamma \to 1\) 是遠視（AlphaGo 用接近 1 的 \(\gamma\) ，因為圍棋的勝負要到數十步後才揭曉）。

Markov 性質：為什麼「狀態」必須定義得好#

Markov 性質：未來只依賴當前狀態，不依賴歷史：

\[ \Pr(S_{t+1} \mid S_t = s, A_t = a, S_{t-1}, A_{t-1}, \ldots, S_0) = P(s'|s,a) \]

這不是一個假設，而是對「狀態」的設計要求：只要你的狀態包含足夠資訊（例如西洋棋盤面本身已含全部規則所需資訊），性質就成立。設計狀態的成敗直接決定後果：

丟掉關鍵資訊：西洋棋只記「剩哪些子」而不記位置 → 非 Markov，價值函數學不準。
部分可觀測（POMDP）：真實世界常只給觀測 \(O_t\) 而非狀態（撲克看不到對手手牌）。工程對策是把歷史折疊進表示：用 LSTM/Transformer 編碼 \(O_0, O_1, \ldots, O_t\) 當作「狀態」。第 7 章的 World Models 用 RNN 做的正是這件事；RLHF 中把整段對話歷史當狀態，同理。
觀測 ≠ 狀態的實例：Atari 的單一畫面無法判斷球速與方向 → DQN 疊 4 幀畫面當狀態（第 4 章會看到程式碼）。

策略與兩種價值函數#

策略（policy） \(\pi\) 是從狀態到動作（或動作分布）的映射：

\[ \pi(a|s) = \Pr(A_t = a \mid S_t = s) \]

狀態價值函數：從 \(s\) 出發、一直照 \(\pi\) 行動的期望回報：

\[ v^\pi(s) = \mathbb{E}_\pi[G_t \mid S_t = s] \]

動作價值函數（Q 函數）：從 \(s\) 出發先執行 \(a\) 、之後照 \(\pi\) 行動的期望回報：

\[ q^\pi(s,a) = \mathbb{E}_\pi[G_t \mid S_t = s, A_t = a] \]

兩者關係（對隨機策略）：

\[ v^\pi(s) = \sum_a \pi(a|s)\, q^\pi(s,a) \]

為什麼需要兩種價值？因為它們服務不同決策情境：知道 \(q^\pi\) ，不需要知道轉移機率就能選動作（ \(\arg\max_a q(s,a)\) ）；只知 \(v^\pi\) 則還需 \(P(s'|s,a)\) 才能比較動作。這個「是否需要模型」的分野，正是第 2 章動態規劃（有模型）與第 3 章無模型學習的斷層線，也是第 7 章 model-based 方法要解決的問題：能不能學出 \(P\) 與 \(R\) ，讓規劃重新變得可能？

flowchart TD
    S["s_t = s"] -->|"agent 選 a ∼ π(·|s)"| A["a_t = a"]
    A --> E[環境]
    E --> R["r_t+1 = R(s, a, s')"]
    E --> S2["s_t+1 = s' ∼ P(·|s, a)"]
    S2 --> S
    S -.->|v^π·s· = E[G_t | S_t=s]| V[狀態價值]
    A -.->|q^π·s,a· = E[G_t | S_t=s, A_t=a]| Q[動作價值]

程式碼：在 Gymnasium 中觸摸 MDP#

我們用最經典的環境之一——FrozenLake（4×4 網格，從起點走到終點，冰面會滑）——展示 MDP 的五元組如何具體存在於環境物件中。

# pip install gymnasium numpy
import gymnasium as gym
import numpy as np

env = gym.make("FrozenLake-v1", is_slippery=True, render_mode="ansi")
print("狀態數 S:", env.observation_space.n)          # 16 個格子
print("動作數 A:", env.action_space.n)               # 左/下/右/上

# Gymnasium 的 FrozenLake 直接暴露了 P(s'|s,a) 與 R —— 這是一個「有模型」的環境
P = env.unwrapped.P                    # P[s][a] = [(prob, s_next, r, done), ...]
print("\n狀態 6 執行動作 2(右) 的轉移分布:")
for prob, s_next, r, done in P[6][2]:
    print(f"  以機率 {prob:.2f} 轉移到 {s_next}, 獎勵 {r}, 終止={done}")
# 注意: is_slippery=True 時, 動作會以機率「滑」到別的方向 —— 這就是隨機轉移核

# 互動一回合: 觀察軌跡四元組 (s, a, r, s')
obs, info = env.reset(seed=42)
done, steps, total_r = False, 0, 0.0
rng = np.random.default_rng(0)
print("\n隨機策略走一回合:")
while not done and steps < 30:
    a = env.action_space.sample()                 # 均勻隨機策略 π(a|s) = 1/4
    obs2, r, term, trunc, info = env.step(a)
    print(f"  s={obs:2d} --a={a}--> s'={obs2:2d}  r={r}  term={term}")
    total_r += r
    obs, done, steps = obs2, term or trunc, steps + 1
print(f"回合結束, 總獎勵 {total_r} (隨機策略幾乎到不了終點)")

這段程式值得盯著看三件事：（1）P[6][2] 列出的機率總和為 1 且動作可能「滑」向意外方向——MDP 的隨機性不只在獎勵，更在轉移本身；（2）我們可以讀出 \(P\) 與 \(R\) 是因為 FrozenLake 特意暴露了模型；Gym 的多數環境（Atari、MuJoCo）不暴露——這正是無模型方法（第 3-5 章）存在的現實理由；（3）隨機策略走一回合的總獎勵接近 0——這直觀展示了「不學習就到不了目標」。

為什麼 MDP 是整本書的地基#

後續每章其實都在問同一個問題的變體：「當 MDP 的某個組成部分未知或難以利用時，怎麼辦？」

未知/受限部分	對應方法	章
知道 \(P, R\)	動態規劃: 價值/策略迭代	第 2.2
不知道 \(P, R\) , 只能採樣	TD, Q-Learning	第 3
狀態是高維圖像	深度近似: DQN	第 4
想直接學策略 π	策略梯度, PPO	第 5
兩人對抗博弈	MCTS + 自我對弈	第 6
採樣昂貴, 想學 \(P\)	World Models, Dreamer	第 7
沒有環境, 獎勵=人類偏好	RLHF	第 8
獎勵=可驗證的正確性	RLVR, o1/R1	第 9

本節重點#

MDP 五元組 \(\langle \mathcal{S}, \mathcal{A}, P, R, \gamma \rangle\) 是序列決策的標準形式化；Bellman 1957 為了讓最優控制「可計算」而提出動態規劃與最優性原理。
Markov 性質是狀態設計的要求：狀態必須涵蓋影響未來的一切資訊；部分可觀測時用歷史編碼（RNN/Transformer、疊幀）折疊出 Markov 表示。
回報 \(G_t = \sum_k \gamma^k R_{t+k+1}\) ； \(\gamma\) 同時擔任數學收斂保證、時間偏好與決策視野旋鈕。
\(v^\pi(s)\) 與 \(q^\pi(s,a)\) 的區別決定了「是否需要環境模型」：知 \(q\) 者不需 \(P\) 即可貪婪行動——這是無模型方法（第 3 章）的立足點。
本書其餘各章都是對「MDP 哪個部分未知」的回應：模型未知 → 無模型；採樣昂貴 → 學模型；獎勵不可寫 → 學偏好模型；獎勵可驗證 → 大規模 RL 鍛鍊推理。

思考問題#

若把西洋棋的「狀態」定義為「當前棋盤 + 雙方剩餘時間」，為何仍是 Markov 的？若定義為「只剩黑王白王的盤面」呢？請指出後者遺漏了什麼造成非 Markov。
FrozenLake 中把 is_slippery 設為 False 後，狀態 6 執行動作 2 的轉移分布會變成什麼？這說明「確定性 MDP」與「隨機 MDP」在 \(P\) 的形式上有何差別？
\(\gamma = 0.99\) 時，100 步之後的獎勵折損為 \(0.99^{100} \approx 0.366\) 。請以此討論：在「每步都有小獎勵」與「300 步後才有大獎勵」兩種環境中， \(\gamma\) 的選擇會如何系統性偏袒某一種行為？
RLHF 把「狀態」定義為「到目前為止的對話」、把 \(|\mathcal{A}|\) 定義為詞表大小（數萬）。請估計這對「 \(q\) 的表格表示」與「探索」意味著什麼，並說明為何第 8 章必須仰賴神經網路近似。
為什麼知道 \(v^\pi\) 卻不知道 \(P\) 時無法直接選最優動作？請寫出需要的計算式 \(a^* = \arg\max_a \sum_{s'} P(s'|s,a)[R(s,a,s') + \gamma v^\pi(s')]\) ，並說明哪些項缺失了。