帶函數近似的理論

為什麼表格型的界無法直接搬過去

到目前為止的每一個界都隨狀態數 S 成長。對西洋棋、圍棋或畫面像素而言，S 實際上是無限大，因此那些界毫無意義。我們必須用函數近似在不同狀態間做泛化——代價是第二篇那個令人安心的壓縮性可能會崩壞。當自助（bootstrapping）、離策略（off-policy）資料與函數近似三者結合——也就是致命三元組（deadly triad）——價值估計可能會發散，所以天真的表格型直覺不只是不精確，甚至可能完全錯誤。

近似誤差如何傳播

在假設有漂亮結構之前，你必須知道：每一步的小近似誤差，會在最終策略裡造成多大代價。價值函數近似誤差界回答了這點：如果每次備份的誤差至多為 ε，那麼由此得到的貪婪策略的次優程度至多約為 2εγ/(1−γ)²。這個 1/(1−γ)² 的放大倍率，正是一個實務痛點的理論面貌——長視界問題很不寬容，因為微小的價值誤差會在有效視界上層層累積。

先界定你函數類別每次迭代的近似誤差 ε。
乘上視界放大倍率約 1/(1−γ)²（在分節設定下相當於 H²）。
據此讀出所回傳策略在最壞情況下的次優程度。

\limsup_{k\to\infty}\;\lVert V^{*}-V^{\pi_k}\rVert_\infty\;\le\;\frac{2\gamma}{(1-\gamma)^2}\,\varepsilon

近似值迭代：每步近似誤差 ε 在最終策略的次優性中被視界因子 1/(1−γ)² 放大。

模擬引理：這個領域的主力工具

大多數樣本複雜度的證明都倚賴模擬引理（simulation lemma）：如果一個學到的模型在其轉移與獎勵上接近真實 MDP，那麼任何固定策略在學到模型下的價值，都會接近它在真實 MDP 下的價值——而誤差同樣帶有一個 1/(1−γ)（或視界）因子。它是一座橋，讓你只量測自己的模型，卻能對真實環境進行推理；它同時撐起了基於模型的分析，以及許多無模型方法的化約論證。

線性 MDP：真正可解的結構

最乾淨、最可解的結構是線性 MDP（linear MDP）：假設轉移動態與獎勵，對每個狀態–動作對的某個已知 d 維特徵映射是線性的。如此一來，每個動作價值函數對那些特徵也是線性的，於是你可以執行樂觀的最小平方價值迭代，得到隨特徵維度 d 與視界成長的遺憾值與樣本複雜度——而不是隨狀態數成長。這是 UCRL 在函數近似下的對應物，也是「在正確結構下，PAC 保證能在無限狀態空間中存活」的範本結果。

P(s'\mid s,a)=\langle \phi(s,a),\,\mu(s')\rangle,\qquad r(s,a)=\langle \phi(s,a),\,\theta\rangle

線性 MDP：轉移動態與獎勵都是已知 d 維特徵映射 φ(s,a) 的線性函數。

貝爾曼秩：統御眾多結構的單一旋鈕

線性 MDP 只是一種結構；表格型 MDP、低秩 MDP、區塊 MDP 都是其他結構。貝爾曼秩（Bellman rank）是一個統一的複雜度度量：它大致捕捉「跨策略的平均貝爾曼誤差所組成矩陣」的秩，而低貝爾曼秩足以保證 PAC-RL 的樣本複雜度對該秩、視界與 log(|函數類別|) 是多項式的——且與狀態數無關。它是 VC 維度在強化學習裡的對應物：用單一純量回答「在這裡探索的統計難度有多高？」