On the Expressivity of Markov Reward 論文深度簡介

強化學習（Reinforcement Learning，RL）是現今人工智慧領域中的重要研究方向，其中「報酬函數」(reward function) 可說是推動智能體行為決策的動力核心。報酬定義了任務的目標，是智能體學習最優策略的唯一依據。然而，在實務與理論研究中，我們常遇到一個深刻且關鍵的問題：所給定的報酬函數是否能夠充分描述我們想要智能體完成的各種任務？換言之，報酬的表達能力（expressivity）到底有多強？

由Abel等人於NeurIPS 2021發表的論文《On the Expressivity of Markov Reward》針對此議題提出了系統性且具理論深度的探討，並榮獲Outstanding Paper獎項。以下將從研究背景與動機、核心方法與創新、主要實驗結果，以及此研究對AI領域的深遠影響四個面向，深入解析這篇代表作。

一、研究背景與動機

強化學習中，智能體透過與環境互動以最大化累積報酬，但「報酬」究竟能描繪哪些形式的「任務」呢？傳統上報酬函數通常是定義於環境狀態或狀態-動作對上，即所謂的Markov報酬函數（Markov Reward Function），意味著報酬的決定僅取決於目前狀態及行動，並無直接考慮歷史資訊。

然而，現實世界中的任務往往比單一路徑的狀態回饋要複雜，例如：

• 任務可接受多種不同行為策略，行為間存在優劣排序（行為不僅是單點決策）
• 我們可能只關心整個軌跡（trajectory）或時間序列的質量排序，而非單獨狀態的回饋
• 部分任務目標本質上難以用Markov報酬函數完整描述，造成智能體無法透過最大化報酬學到理想行為

基於此，論文動機在於嚴謹定義「任務」的抽象形式，並探討Markov報酬函數在這些抽象任務定義上的表達能力，嘗試回答「究竟有那些任務是Markov報酬無法捕捉的？」及「如何構造報酬函數來最佳化不同類型任務？」

二、核心方法與創新

論文提出三種抽象層次的任務定義，對應不同層面上如何刻畫智能體期望行為：

1. 可接受行為集合（Set of Acceptable Behaviors）：定義一組行為被視為可接受，學習目標是選擇行為落在此集合中。
2. 行為上的偏序關係（Partial Ordering over Behaviors）：不僅區分好壞，更定義行為間的偏好次序，但不要求完整排序。
3. 軌跡上的偏序關係（Partial Ordering over Trajectories）：對整條行為軌跡建立偏序，比較整體執行結果的優劣，能捕捉歷史資訊對評價的重要性。

這三種概念層層深入，試圖覆蓋現實中各種可能的任務形式。核心創新與貢獻包括：

• 嚴謹證明雖然Markov報酬函數能夠表達多數任務，但對上述三種任務類型均存在無法表達的例子。此結果打破傳統認為報酬函數可萬能描述任務的既有印象，揭示固有限制。
• 設計多組多項式時間（polynomial-time）的演算法，能在給定任務形式下，嘗試構造對應的Markov報酬函數，並且判定是否存在可行的報酬函數。
• 提出能基於偏序定義，轉化為報酬函數建構的數學架構，使得任務的可行性和報酬函數的存在性成為判定問題，並非僅是啟發式嘗試。

整體而言，論文從理論出發，將「任務定義」與「報酬表達」嚴格鏈結，提供實用且具判定性的工具，使得報酬函數設計不再是黑盒，而是有理論保證的建構過程。

三、主要實驗結果

論文除了提供嚴謹數學證明，亦進行大量實證實驗，目的是：

• 驗證理論上無法構造報酬函數的任務確實在實務中導致學習失敗
• 演算法在合理規模環境中能高效建構出對應Markov報酬函數，成功引導智能體完成目標任務

實驗涵蓋經典強化學習benchmarks，並刻意設計具備不同偏序結構的任務設定。結果展示：

• 標準報酬函數設計往往無法捕捉任務的精細要求，導致智能體無法學到期望行為
• 論文演算法設計的報酬函數明顯提升了學習效率與任務達成度
• 在部分無法以Markov報酬完美表達的情況下，演算法依然能判定該任務非報酬可行，避免浪費學習資源

這些實驗不僅佐證了理論推論，也展現了該研究方法在實際強化學習系統中的應用潛力。

四、對 AI 領域的深遠影響

這份工作深化了我們對強化學習中「任務」與「報酬」兩大核心概念的認識。其影響主要體現在以下幾點：

1. 理論層面：論文明確界定了報酬函數的表達力限制，指出並非所有定義良好的優先關係或可接受行為集合，都能用Markov報酬函数來完整反映。此一結果對RL理論有重大啟示，提醒研究者在設計報酬函數時需警惕其本質限制。
2. 算法層面：提供多項式時間算法，實現了「自動化地依據任務偏序結構產生報酬函數」，這降低了人工設計報酬函數的難度，有助於推動報酬工程（reward shaping）和報酬自動化設計（reward learning）的發展。
3. 應用層面：該研究為複雜任務的設計與驗證提供了理論工具，使得基於報酬的學習系統能更精準地對齊人類期待的目標，避免「代理人偏差」（specification gaming）等問題，提升強化學習在工業和日常生活場景的可靠度。
4. 未來研究：論文提出的三種任務抽象概念成為後續報酬設計和多任務強化學習的理論基礎，促進研究者探索非Markov或歷史依賴的報酬結構，推進更靈活和強大智能體的發展。

總結來說，Abel等人的這篇《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