跳轉到

07.1 MDP 與貝爾曼方程#

本章導讀#

前面的章節都是「監督學習」：有標準答案，照著學。 但走迷宮、下棋、開車——沒人告訴你每一步該做什麼，只有事後的獎勵。 強化學習（RL）就是「從獎勵中學決策」的數學。其基石是 1950 年代 Bellman 的一個方程， 以及一個保證收斂的定理——巴拿赫不動點。

淺顯說明#

想像你在迷宮裡，每走一步能撿到金幣（或觸雷）：

  • 你的目標不是「這一步撿最多」，而是「總共撿最多」——要走長遠。
  • 貝爾曼的洞見：一個狀態的「價值」= 立即獎勵 + 下一個狀態的價值（打折扣）。
  • 這是遞迴定義：要算 \(V(s)\) ，得先算 \(V(s')\) ——看起來是循環，但 Bellman 證明： 這個遞迴有唯一解，而且反覆迭代必定收斂到它。

「折扣」 \(\gamma\) 就是「未來的錢不如現在的錢值」—— \(\gamma = 0\) 只看眼前， \(\gamma \to 1\) 走長遠。

正規理論#

馬爾可夫決策過程（MDP）#

MDP 是五元組 \(\langle \mathcal{S}, \mathcal{A}, \mathcal{P}, \mathcal{R}, \gamma \rangle\) ：

  • \(\mathcal{S}\) ：狀態集； \(\mathcal{A}\) ：動作集。
  • \(\mathcal{P}(s' \mid s, a)\) ：轉移機率。
  • \(\mathcal{R}(s, a, s')\) ：獎勵； \(\gamma \in [0, 1)\) ：折扣因子。

馬爾可夫性（無記憶性）是核心假設：

\[ P(S_{t+1} \mid S_t, A_t, S_{t-1}, A_{t-1}, \dots) = P(S_{t+1} \mid S_t, A_t) \]

未來只依賴當前狀態與動作——歷史可以「壓縮」進 \(S_t\) 。

價值函數與貝爾曼方程#

策略 \(\pi(a \mid s)\) 是「在狀態 \(s\) 採取動作 \(a\) 的機率」。狀態價值函數定義為期望累積獎勵：

\[ V^\pi(s) = \mathbb{E}_\pi\left[\sum_{t=0}^{\infty} \gamma^t r_t \;\middle|\; S_0 = s\right] \]

展開期望並用馬爾可夫性，得貝爾曼期望方程：

\[ \boxed{\; V^\pi(s) = \sum_{a \in \mathcal{A}} \pi(a \mid s) \sum_{s', r} P(s', r \mid s, a) \left[ r + \gamma V^\pi(s') \right] \;} \]

動作價值函數 \(Q^\pi(s, a)\) 同理：

\[ Q^\pi(s, a) = \sum_{s', r} P(s', r \mid s, a)\left[r + \gamma \sum_{a'} \pi(a' \mid s') Q^\pi(s', a')\right] \]

貝爾曼算子與壓縮映射#

定義貝爾曼期望算子 \(T^\pi\) ：

\[ (T^\pi V)(s) = \sum_a \pi(a \mid s) \sum_{s', r} P(s', r \mid s, a)\left[r + \gamma V(s')\right] \]

定理（壓縮映射）： \(T^\pi\) 在 \(\|\cdot\|_\infty\) 下是 \(\gamma\) -壓縮的：

\[ \|T^\pi V_1 - T^\pi V_2\|_\infty \le \gamma\, \|V_1 - V_2\|_\infty \]

證明：逐狀態估計，

\[ |(T^\pi V_1)(s) - (T^\pi V_2)(s)| = \gamma\left|\sum_a \pi(a\mid s)\sum_{s'} P(s'\mid s,a)\big(V_1(s') - V_2(s')\big)\right| \le \gamma \max_{s'}|V_1(s') - V_2(s')| \]

（用了 \(\sum_a \pi = 1\) 、 \(\sum_{s'} P = 1\) 與三角不等式。） \(\blacksquare\)

巴拿赫不動點定理：完備度量空間上的壓縮映射有唯一不動點，且從任意點出發的迭代幾何收斂到它。因此：

  1. \(V^\pi\) 是 \(T^\pi\) 的唯一不動點： \(V^\pi = T^\pi V^\pi\) ——貝爾曼方程的解存在且唯一。
  2. 價值迭代 \(V_{k+1} = T^\pi V_k\) 收斂，誤差以 \(\gamma^k\) 衰減：
\[ \|V_k - V^\pi\|_\infty \le \gamma^k \,\|V_0 - V^\pi\|_\infty \]

貝爾曼最佳算子與 Q-Learning#

最佳算子取 max：

\[ (T^* V)(s) = \max_a \sum_{s', r} P(s', r \mid s, a)\left[r + \gamma V(s')\right] \]

同樣是 \(\gamma\) -壓縮，唯一不動點 \(V^*\) （最佳價值）。Q-learning 的更新：

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

在適當條件（所有狀態動作無窮探訪、 \(\alpha\) 滿足 Robbins–Monro 條件 \(\sum \alpha_t = \infty\) , \(\sum \alpha_t^2 < \infty\) ）下**以機率 1 收斂到 \(Q^*\) **——壓縮映射又一次保證了收斂。

簡易範例：兩狀態迷宮#

狀態 \(\{A, B\}\) ，動作「走」確定轉移： \(A \to B\) 得 \(r = 1\) ； \(B \to A\) 得 \(r = 0\) 。 \(\gamma = 0.9\) ， \(\pi\) 恆「走」。

貝爾曼方程：

\[ V(A) = 1 + \gamma V(B), \qquad V(B) = 0 + \gamma V(A) \]

代入解： \(V(A) = 1 + 0.9 \times 0.9 V(A) \Rightarrow V(A)(1 - 0.81) = 1 \Rightarrow V(A) \approx 5.26\) ， \(V(B) \approx 4.74\) 。

用價值迭代驗證（ \(V_0 = 0\) ）： \(V_1(A) = 1, V_1(B) = 0\) ； \(V_2(A) = 1.9, V_2(B) = 0.9\) ； \(V_3(A) = 1.9, V_3(B) = 1.71\) ……震盪衰減，逐步逼近 \(5.26 / 4.74\) ——每步誤差乘 \(0.9\) ，正是壓縮映射的幾何收斂。

歷史典故#

  • 1997 年 Deep Blue：見卷宗 ../1997-DeepBlue搜尋智能.md——搜尋 + 評估函數（手工版的價值函數）擊敗世界棋王。
  • 2016 年 AlphaGo：見 ../2016-AlphaGo.md——價值網路 + 策略網路 + 蒙地卡羅樹搜尋，把 Bellman 的思想推上圍棋之巔。
  • 2022 年 ChatGPT 與 RLHF：見 ../2022-ChatGPT與RLHF.md——RL 從迷宮走進了對話（下一節細講）。

習題#

  1. 對本節兩狀態例子改 \(\gamma = 0.5\) ，重解貝爾曼方程與價值迭代的前三步。
  2. 證明：貝爾曼最佳算子 \(T^*\) 也是 \(\gamma\) -壓縮（提示： \(\max_a f(a) - \max_a g(a) \le \max_a |f(a) - g(a)|\) ）。
  3. 說明為什麼馬爾可夫性是「壓縮」的關鍵：若轉移依賴歷史，貝爾曼方程還成立嗎？

補充#

1. 數學推導證明#

證明（習題 2）：最佳算子 \(T^*\) 也是 \(\gamma\) -壓縮。

對任意 \(V_1, V_2\) 與狀態 \(s\) ，設 \(a_1^*\) 、 \(a_2^*\) 分別是 \((T^*V_1)(s)\) 、 \((T^*V_2)(s)\) 的取 max 動作。不失一般性設 \((T^*V_1)(s) \ge (T^*V_2)(s)\) ，則

\[ (T^*V_1)(s) - (T^*V_2)(s) \le \sum_{s',r} P(s',r\mid s,a_1^*)\big[r + \gamma V_1(s')\big] - \sum_{s',r} P(s',r\mid s,a_1^*)\big[r + \gamma V_2(s')\big] \]

（第二項把 max 換成 \(a_1^*\) 只會變小，故差變大。）獎勵 \(r\) 相消，得

\[ \le \gamma\sum_{s'} P(s'\mid s,a_1^*)|V_1(s') - V_2(s')| \le \gamma\,\|V_1 - V_2\|_\infty \]

反向同理，故 \(|(T^*V_1)(s) - (T^*V_2)(s)| \le \gamma\|V_1 - V_2\|_\infty\) 對一切 \(s\) 成立，即 \(\|T^*V_1 - T^*V_2\|_\infty \le \gamma\|V_1 - V_2\|_\infty\) 。關鍵不等式 \(\max_a f(a) - \max_a g(a) \le \max_a|f(a) - g(a)|\) 用了兩次。 \(\blacksquare\)

計算（習題 1）： \(\gamma = 0.5\) 的兩狀態解。

方程 \(V(A) = 1 + 0.5V(B)\) 、 \(V(B) = 0.5V(A)\) ，解得 \(V(A) = 1/(1-0.25) = 4/3 \approx 1.333\) ， \(V(B) = 2/3 \approx 0.667\) 。價值迭代（ \(V_0 = 0\) ）： \(V_1 = (1, 0)\) ； \(V_2 = (1, 0.5)\) ； \(V_3 = (1.25, 0.5)\) ——與程式 _code/07.1-bellman-value-iteration.py 末段輸出逐項一致，誤差每步乘 \(0.5\) 。 \(\blacksquare\)

說明（習題 3）：馬爾可夫性為何關鍵。 貝爾曼方程把「從 \(s\) 出發的未來」寫成「一步獎勵 \(+\) 從 \(s'\) 出發的未來」——這要求「從 \(s'\) 出發的未來」與「怎麼到達 \(s'\) 」無關，即無記憶性。若轉移依賴歷史， \(V(s)\) 不是充分統計量：同一個 \(s\) 、不同歷史，未來期望不同， \(V^\pi(s) = T^\pi V^\pi(s)\) 不再成立。實務解法是擴充狀態（把歷史塞進 \(s\) ，如加過去 \(k\) 步、或用循環網路隱狀態），讓擴充後的過程重新馬爾可夫化。

2. 簡易範例#

範例一：價值迭代的正確表格。 \(\gamma = 0.9\) 、 \(V_0 = 0\) ： \(V_1 = (1, 0)\) ； \(V_2 = (1, 0.9)\) ； \(V_3 = (1.81, 0.9)\) ； \(V_4 = (1.81, 1.629) \dots\) （程式逐步印出 \(k = 1 \dots 12\) ，本章正文 \(V_3\) 的數字應以此表為準）。解析解 \(V^* = (5.2632, 4.7368) = (1/(1-\gamma^2), \gamma/(1-\gamma^2))\) 。

範例二：壓縮的數值指紋。 程式印出每步 \(\|V_k - V^*\|_\infty\) 與誤差比： \(4.737 \to 4.263 \to 3.837 \dots\) ，比值恆為 \(0.9000 = \gamma\) ——幾何收斂不是比喻，是印出來的 \(0.9\) 。