On the Expressivity of Markov Reward

在強化學習（Reinforcement Learning, RL）中，「獎勵」（reward）扮演關鍵角色，是引導智能體學習並完成任務的主要驅動力。然而，獎勵的設計既是科學也是藝術，牽涉到如何用合適的獎勵函數來定義智能體的目標，使其行為符合期望。經典的假設是：透過設定適當的馬可夫獎勵函數（Markov Reward Function），智能體能以最大化期望累積獎勵的方式，達成我們想要的任務。然而，這種觀念中「獎勵的表達能力」（expressivity）究竟有多強？是否所有我們想要的任務，都可以被某個馬可夫獎勵函數完美捕捉？這篇由 Abel 等人於 NeurIPS 2021 發表，並榮獲 Outstanding Paper 的論文《On the Expressivity of Markov Reward》正是針對此核心問題，提出了系統性且嚴謹的研究。

研究背景與動機

在 RL 領域，任務通常是透過獎勵函數來定義。獎勵函數的設計不當，可能導致智能體「走歪樓」──例如產生不符合人類期望的行為，或是陷入局部最優解。過去研究多半假設除了環境的馬可夫性質，很容易透過獎勵函數來刻劃目標行為。事實上，任務的定義具有多樣性，不僅是具體的行為，也包括「行為之間的偏好順序」甚至對完整軌跡的偏好排序。這些更抽象的任務定義是否都能用一個馬可夫獎勵函數表示，尚未被充分探究。

本論文首要動機即是深入解析「任務」的抽象概念，並用數學嚴謹的方式探討獎勵函數的能耐與限制。藉此，希望能為獎勵設計與任務建模提供更理論化的指導，避免盲目設定獎勵而導致智能體不當行為。

核心方法與創新

論文提出三種不同的抽象任務概念：

• 接受行為集合（Set of Acceptable Behaviors）：定義哪些行為是合格的，智能體需要選擇在這集合內的行為即可。
• 行為的部分偏序（Partial Ordering over Behaviors）：不只接受與否，而是在多個行為間存在「偏好順序」，但這排序並非全序，即某些行為無法直接比較。
• 軌跡的部分偏序（Partial Ordering over Trajectories）：直接對整個狀態-行為序列（軌跡）進行排序，描述更精細的任務偏好。

接著，論文的核心貢獻包括：

1. 嚴格證明：雖然馬可夫獎勵函數可表達多數情況，卻存在上述三種任務類型中無法被任何馬可夫獎勵函數完全表示的例子。這說明獎勵函數的表達能力有其本質限制，破除了過往獎勵設計無限能量的迷思。
2. 針對這三種任務類型，作者設計了一套多項式時間複雜度的演算法，能有效判斷任務是否存在相應的馬可夫獎勵函數，並在存在時構造該函數。
3. 該架構為獎勵函數設計提供了形式化理論工具，不僅告訴我們哪些任務無法以馬可夫獎勵函數表達，更給出如何找到正確獎勵函數的具體方法。

主要實驗結果

為了驗證理論，論文作者進行了一系列模擬實驗，具體設計不同複雜度與任務類型的環境，並嘗試依據提出的演算法設定獎勵函數：

• 實驗顯示許多在實務中常見的任務，都能透過找到適合的馬可夫獎勵函數來優化，但也確實碰到無法被任何馬可夫獎勵函數捕捉的情形。
• 迴圈、非單調偏序等複雜任務場景表明，需額外擴展非馬可夫獎勵、歷史感知獎勵或結合其他偏好表示方法。
• 演算法能有效識別何時存在對應獎勵，並成功構造出獎勵函數，示範了方法的實用性與計算可行性。

對 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