On the Expressivity of Markov Reward — NeurIPS 2021 優秀論文深度解析

在強化學習（Reinforcement Learning, RL）領域中，「獎勵函數（Reward Function）」是核心組件，驅動智能體學習與優化行為。過去大多數研究關注於如何設計能有效促使智能體完成特定任務的獎勵，但對於「獎勵函數本身能表達多少任務類型」的本質性問題，探討較少。來自Abel等人的 NeurIPS 2021 優秀論文《On the Expressivity of Markov Reward》便聚焦此議題，深入剖析「Markov獎勵函數對於任務表示能力（expressivity）的極限」，並推導能否利用此類函數完全描述真實世界中我們希望智能體達成的多元目標。

研究背景與動機

強化學習的重要前提是設計獎勵函數，透過即時給予回饋，鼓勵智能體產生期望行為。這種過程隱含一個假設：用「一個獎勵函數」能夠代表我們所需的「任務」。然而，現實中任務的定義往往非常複雜，可能不僅是簡單「最大化累積獎勵」那般直觀。例如，我們在設計無人駕駛車時，不僅希望車子通過特定路線，更盼望它遵守優先權規則、行為安全、以及不同路段的行為策略；更複雜的任務還涉及到對行為排序的偏好，而非單純「正負獎勵」的累積。傳統Markov決策過程（MDP）中的獎勵函數是否能涵蓋這些多元的「任務意義」？這是本論文想要解答的根本問題。

因此，作者提出三種對任務的抽象定義，以幫助分析獎勵函數的表達能力：

1. 「可接受的行為集合」（a set of acceptable behaviors）：如一個二分判斷，這些行為被視為符合任務要求。
2. 「行為的偏序關係」（a partial ordering over behaviors）：定義部分行為間優劣，但不要求完全排序。
3. 「軌跡的偏序關係」（a partial ordering over trajectories）：對完整軌跡進行排序，考慮動態決策連續性的優劣。

上述三種類型涵蓋了從最基本的行為合格標準到細膩且結構化的任務偏好，是對強化學習中任務定義的全新視角。

核心方法與創新

論文的核心在於嚴謹的理論證明和構造性算法，闡明：

• 即使獎勵函數能表達大量任務，但仍存在無法用任何Markov獎勵函數完全表示的任務類別。這種有限性來自於獎勵函數依賴狀態-行動而非整個歷史軌跡，故缺乏充分的表達力。
• 作者提出多項多項式時間內可運行的演算法，用以嘗試為各類任務建構對應的Markov獎勵函數，或在不可行時給出判定，這是實踐上非常重要的貢獻，讓理論結果具有落地的可能性。

具體來說，論文中著重對以下議題建構算法與理論：

• 對於「可接受行為集合」的任務，定義並檢驗對應的reward函數建構問題。
• 對「行為的偏序關係」與「軌跡偏序關係」，提出如何用分段線性或錨點方法近似表示，協助最佳化。

這些方法彼此互補，涵蓋從簡單到複雜的任務結構，提出了完整的理論體系，澄清了獎勵函數設計的極限與可行途徑。

主要實驗結果

論文附帶的實證研究主要是透過模擬環境來驗證理論發現，提供直觀例證說明：

• 在部分任務設定中，所合成的Markov獎勵函數能成功保證最優行為集合與任務定義的一致性。
• 某些任務本質上無法用Markov獎勵函數完全表達，智能體即便找出最優解，也無法達成任務需求，驗證理論中不可表達性的存在。
• 演算法在各種任務結構下皆可在理論時間複雜度內完成獎勵函數建構，證明方法的實用性。

這些實驗不僅複現理論假設，也展示了研究成果可指導實際獎勵設計與任務理解。

對 AI 領域的深遠影響

本論文對強化學習獎勵設計提出了全新且深刻的理解框架。過去，許多研究熱衷於如何建立複雜任務的獎勵函數，卻未必清楚相信一個Markov獎勵函數就足以完全描述想要的任務目標。Abel等人的研究明確指出了這種「表達極限」，為未來獎勵函數設計提出了以下重要啟示：

1. 明確任務定義的本質限制：設計者需認識某些任務結構本質上無法依靠狀態即可決的Markov獎勵函數來妥善表述，鼓勵探索非馬可夫獎勵、歷史依賴獎勵或多層次任務表示。
2. 提供驗證與建構工具：所提出的算法不只理論價值，也為實務工程師提供評估任務是否能被獎勵函數表示的途徑，並可根據結果調整任務規範或獎勵設計。
3. 啟發後續研究方向：未來可探索如何利用更豐富的任務表示形式，如行為偏序的多維表示，或結合模糊獎勵、邏輯規則強化學習，以克服Markov獎勵函數的瓶頸。

綜觀而言，這篇論文深化了我們對「任務本質」和「獎勵設計」間關係的認知，對推動強化學習從理論到實踐的可靠性和通用性具有里程碑意義。

總結來說，《On the Expressivity of Markov Reward》不僅挑戰了慣常的獎勵設計思維，也為開發更具泛用性與解釋力的強化學習系統鋪路。對具備基礎 AI 知識的工程師與研究生而言，透過熟悉這篇論文，可以建立對任務與獎勵設計的根本性理解，並在面臨實際應用挑戰時更有洞察力與工具支撐。

---

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