On the Expressivity of Markov Reward

在強化學習（Reinforcement Learning, RL）領域中，獎勵函數（Reward Function）被視為驅動智能體學習行為的核心元素。它不僅決定了智能體獲得回報的方式，也是設計和定義任務目標的關鍵。然而，過去關於獎勵函數的「表達能力」——也就是一個獎勵函數能否充分且恰當刻畫我們希望智能體完成的任務——的系統性理解相對缺乏。Abel等人在2021年NeurIPS發表的這篇榮獲Outstanding Paper的論文《On the Expressivity of Markov Reward》，深入探討了獎勵函數在建模不同任務類型上的能力限制與潛力，為強化學習社群提供了理論指引與實用算法，對獎勵設計與智能體行為理解均有深遠影響。

研究背景與動機

在強化學習中，任務通常透過定義獎勵函數來指定：智能體透過最大化累積獎勵來學習期望行為。不過，實際情況中，我們希望描述的任務往往複雜多樣，不只是單一數值的最大化那麼簡單。例如，有些任務要求行為達到某種「可接受的集合」，或者在多種行為之間存在偏好（partial ordering），甚至希望根據整條軌跡（trajectory）做偏好排序。這引發了兩個核心問題：第一，現有的「馬爾可夫獎勵函數」（Markov Reward Function，獎勵只依賴當前狀態與動作）是否足以表達這些多樣且抽象的任務需求？第二，若不足，又該如何判斷某個任務是否可被標準獎勵函數恰當表示，並如何構造這樣的函數？

基於此，作者將研究聚焦在獎勵函數的「表達能力（expressivity）」，即獎勵函數能否覆蓋我們理想中的「任務空間」。為此，他們提出三種抽象且劃時代的任務定義方式：

1. 可接受行為集合（Set of Acceptable Behaviors）：定義哪些行為是合格的，而對其他行為不感興趣。
2. 行為偏好偏序（Partial Ordering over Behaviors）：不只有好與壞，有些行為具有更細緻的偏好關係。
3. 軌跡偏好偏序（Partial Ordering over Trajectories）：對於整條軌跡（由狀態與動作序列組成）定義偏好結構，而非單純看單一狀態或行為。

這三種設想二是抽象又貼近實際，涵蓋了從嚴格要求到「軟性偏好」的多種任務描述，引領我們重新審視馬爾可夫獎勵的極限與可能。

核心方法與創新

論文的理論重點在於嚴格定義上述任務形式，並系統性探討對應的獎勵函數表達能力。作者從數學與計算複雜度視角切入，證明了以下重要事實：

• 雖然馬爾可夫獎勵能夠表達大量常見任務，但對於三類任務中的某些特殊例子而言，不存在任何馬爾可夫獎勵函數能完全再現其行為或軌跡的偏好順序。
• 換言之，馬爾可夫獎勵函數存在「表達盲區」，無法捕捉所有合理又實用的任務形式。

此後，作者進一步提出了三組多項式時間複雜度的算法——一組針對可接受行為集合，一組針對行為偏序，一組針對軌跡偏序。這些算法具有兩大功能：

1. 當給定一個任務定義後，判斷是否存在馬爾可夫獎勵函數可表達該任務。
2. 若存在，則自動構造出該獎勵函數，協助設計智能體的學習目標。

這不僅推動了理論分析，也提供了實務上可操作的方法，降低任務設計的試誤成本。

主要實驗結果

為了驗證理論主張與算法效用，作者針對人工合成的多種任務實驗，實證三種不同任務定義的獎勵表達能力與算法表現，成果包括：

• 清楚展示了存在無法被馬爾可夫獎勵函數捕捉的任務案例，強調理論界限真實存在。
• 算法成功識別並構造出所能表達的任務獎勵，且在強化學習環境中驗證這些獎勵確實引導智能體達成預期目標。
• 實際強化學習訓練曲線與智能體行為均符合由算法生成的獎勵設定，支持理論與實務一致。

此外，論文也針對不同軌跡偏好情境，分析獎勵結構設計對表達能力的影響，展現其高度的泛用性與理論嚴謹態度。

對 AI 領域的深遠影響

這篇論文對強化學習甚至整個人工智能領域有多重層次的貢獻：首先，它從根本上挑戰了「獎勵函數即任務規格」這一基本假設，揭示了馬爾可夫獎勵函數不能萬能的真相，有助於警醒研究者慎選或拓展任務描述方式。

其次，提出三種抽象且實用的「任務」定義，為後續理論分析和應用研究奠定了堅實基礎。這些定義不僅豐富了強化學習中「任務」的內涵，也推動了對多樣行為偏好及決策結構的深入理解。

第三，所設計的多項式演算法可實際應用於任務設計與獎勵構造，為智能體設計者提供了判斷及自動化工具，促進獎勵工程（Reward Engineering）從經驗法則走向理論指導甚至程式化驗證。

更廣義地，該研究促使我們重新思考強化學習中獎勵與目標的關係，推進獎勵缺陷理論（Reward Hacking）、安全強化學習，以及更複雜、多目標任務的表達設計，對工業應用、機器人控制、以及倫理AI等領域的影響深遠。

總結來說，《On the Expressivity of Markov Reward》不僅深入揭示了強化學習獎勵函數的本質侷限，亦開創了任務建模與獎勵設計的新視野，是強化學習理論與實務結合的典範之作。對於追求設計更可靠、可解釋且可擴展智能體的工程師與研究生而言，此篇論文是不可或缺的理論寶庫與方法指南。

---

論文資訊
📄 On the Expressivity of Markov Reward
👥 Abel, Dabney, Harutyunyan, Ho, Littman, Precup, Singh
🏆 NeurIPS 2021 · Outstanding Paper
🔗 arxiv.org/abs/2111.00876