On the Expressivity of Markov Reward

在強化學習（Reinforcement Learning, RL）領域中，「獎勵函數」（reward function）扮演關鍵角色。獎勵是驅動智能體學習並執行特定任務的核心動力，透過定義獎勵，研究者能引導智能體學會希望的行為。然而，獎勵函數本身的表達能力到底有多強？它能否完美且全面地描述我們想讓智能體完成的各種任務？這是Abel 等人於 NeurIPS 2021 榮獲 Outstanding Paper 的論文《On the Expressivity of Markov Reward》所探討的核心問題。

研究背景與動機

目前，強化學習系統多半假設任務可由一個馬可夫獎勵函數（Markov reward function）完全表述，這樣的設計基於馬可夫決策過程（MDP）理論框架，即獎勵函數只依賴當前狀態與行動。然而，實際應用中，我們想讓智能體完成的任務往往涉及複雜行為偏好、部分順序關係，甚至跨多個時間步長的整體軌跡特性。此時，單純以標量獎勵函數表達這些任務是否足夠？這是懸而未決但卻實務上至關重要的問題。

論文作者基於此動機，進一步抽象化「任務」的定義，提出三種任務的定義模式：

1. 接受行為集合（a set of acceptable behaviors）：定義哪些行為是可接受的，而無需更細緻的優劣區分。
2. 行為之間的部分排序（a partial ordering over behaviors）：定義行為間優劣的非全序排列，即允許部分行為無法相比較。
3. 軌跡之間的部分排序（a partial ordering over trajectories）：直接在整個狀態-行動序列上建立優劣關係，用以描述軌跡層次的偏好結構。

這些定義涵蓋了從嚴格集合概念到更細緻排序概念的過渡，目的是探討在這些理想化但高度抽象的框架下，馬可夫獎勵函數的表達受限在哪裡。

核心方法與技術創新

論文的理論貢獻在於嚴格證明馬可夫獎勵函數的「表達力（expressivity）」限制。研究指出，對上述三種任務類型，都存在著無法用任何馬可夫獎勵函數精確表達的任務實例。換句話說，某些行為集合或優劣排序無法由單一、狀態-行動依賴的酬賞函數來刻畫。

為了具體化這些結果，作者提出了多項計算複雜度多項式時間的演算法，包括：

• 判斷給定任務是否存在對應的馬可夫獎勵函數。
• 當存在時，建構出對應的獎勵函數。

這些演算法基於對行為空間及軌跡偏好的嚴謹分析，並利用數學工具來描述部分排序與集合條件，提出有效的構造與檢驗策略。這促使我們不僅知道理論上的限制，還能在實務上檢驗並嘗試獲取可用的獎勵設計。

此外，該研究也指出了一些在實務中可行的「近似」手段與鬆綁條件，為後續的獎勵設計提供理論依據與參考框架。

主要實驗結果與驗證

為了佐證理論結果，作者在論文中設計多組實驗，透過模擬環境展示特定任務的不可表達性。例如，對某些複雜的行為偏好或軌跡排序，嘗試訓練不同的獎勵設計模型，都無法令智能體行為符合預期偏好。相反，在能被馬可夫獎勵函數描述的任務上，其演算法能成功揭示並取得對應的獎勵函數，並引導智能體達成任務。

實驗結果同時展示了理論上的「不可得性」並非紙上談兵，而是具體發生在現代強化學習問題中。此結果引導我們重新思考獎勵函數設計的局限與挑戰，強化了最好在具體任務前檢查是否存在合適獎勵函數的需求。

對 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