強化學習理論到底在問什麼

為什麼「能跑的智能體」還不是故事的終點

一個實驗結果只告訴你：某一次執行的某個演算法，在某一個任務上找到了不錯的策略。理論問的是更難的問題：它對某一類問題裡的每一個實例都有效嗎？它需要多少資料？以及，是否存在一個本質上更好、還沒被發現的演算法？當你讀過什麼是強化學習與 MDP 形式化之後，理論就是把一堆技巧變成一門有保證、也有極限的科學的東西。

三種衡量單位：樣本複雜度、遺憾值、PAC

理論用幾種標準「貨幣」來衡量代價。樣本複雜度（sample complexity）計算你需要多少次與環境的互動，才能保證學到的策略接近最優。遺憾值（regret）則是把整段執行過程中、相對於「從頭就最優」所損失的回報全部加總——它會為你沿途每一個錯誤收費，而不只看最終答案。PAC-RL（可能近似正確，Probably Approximately Correct）要求以至少 1−δ 的機率得到一個與最優差距在 ε 之內的策略，並把所需樣本量寫成 ε 與 δ 的函數。

樣本複雜度問：要多少樣本才能「夠好」？（這是預算問題）
遺憾值問：我在學習過程中總共付出多少代價？（這是線上、累積的問題）
PAC 問：我能以多高的信心、多高的精度去保證這個結果？（這是保證問題）

下界：任何演算法都打不過的線

上界說的是「這個演算法至少有這麼好」。極小極大下界（minimax lower bound）說的卻是相反、而且強得多的事：在這一類問題的最壞情況下，沒有任何演算法能做得更好。當某演算法的上界與下界相符（差在常數與對數因子之內），我們就稱它為極小極大最優（minimax-optimal）——此時這個問題在精確意義下已被解決。下界的構造方式，是造出幾個在統計上難以區分的 MDP，逼得任何學習者都得碰運氣。

\operatorname{Regret}(T)=\Omega\!\left(\sqrt{H\,S\,A\,T}\right)

极小极大遗憾下界：在最坏情况下，任何算法都无法避免约 √(HSAT) 量级的代价。

已知最佳上界與已知最佳下界之間的差距，正是這個領域的前緣。把這個差距補上——靠找到更聰明的演算法，或構造出更難的困難實例——就是理論論文彼此較勁的戰場。

探索的稅

在監督式學習裡，資料是別人遞給你的；在強化學習裡，你必須靠行動去蒐集資料，因此一個從不嘗試陌生動作的學習者，可能永遠不知道有更好的策略。探索與遺憾值的取捨正是探索／利用兩難的形式化版本：每一步結果很糟的探索都會記在你的遺憾值上，但拒絕探索又會限制住你最終所能達到的高度。理論的工作，就是精確量化最優取捨究竟需要多少探索。

目標的選擇會改變整套理論

在談任何界之前，你得先固定目標函數。折扣（discounted）準則對近期回報賦予較高權重，其有效視界大約是 1/(1−γ)，這個量在折扣型的界裡到處出現。平均獎勵準則（average-reward criterion）則衡量長期下每一步的平均回報，是真正持續性任務（不做折扣）最自然的目標。平均獎勵的理論更微妙——它依賴的是 MDP 的混合時間或直徑，而不是 1/(1−γ)。

G_t=\sum_{k=0}^{\infty}\gamma^{k}\,r_{t+k+1},\qquad H_{\text{eff}}\approx\frac{1}{1-\gamma}

折扣回报及其有效视界约为 1/(1−γ)——这一目标的选择会重塑后续所有的界。

在後續內容中請把這張地圖記在心裡。下一篇我們會證明，為什麼經典的動態規劃與表格型 Q-learning 方法能夠收斂——這是所有更難結果賴以建立的基石。