On the Expressivity of Markov Reward

強化學習（Reinforcement Learning，RL）中的「獎勵函數」一直是驅動智能體學習與行動策略的核心元素。傳統上，我們利用馬可夫獎勵函數（Markov Reward Function, MRF）來定義環境中的即時回饋，期望藉此引導智能體達成目標任務。然而，隨著強化學習應用範圍的擴展，對於「什麼樣的行為或任務能夠透過獎勵函數來精確描述與實現」的基礎理論探究卻相對匱乏。來自Abel等人於NeurIPS 2021發表並榮獲Outstanding Paper獎項的論文《On the Expressivity of Markov Reward》，正是一篇對於獎勵函數表達能力（expressivity）進行系統性分析的劃時代之作。

研究背景與動機

在強化學習裡，獎勵函數被視為「任務」的數學表徵，智能體依此學習最大化累積獎勵。然而，任務本身的定義可以比單純最大化某種獎勵更為複雜。許多實際情境中我們關注的，往往是複雜的行為偏好結構，諸如允許多種「可接受的行為」集合、行為之間的偏好等階關係，或甚至對整個軌跡（trajectory）—而非單一狀態或行為序列的即時獎勵—的偏好。論文指出，以馬可夫獎勵函數來描述這類任務是否充足，存在理論上的空白與挑戰。該研究由此出發，嘗試回答：馬可夫獎勵函數表達任務的範圍究竟有多大？對哪些類型的任務類型是表達不足的？同時，是否存在有效演算法幫助我們從抽象任務規格中構造對應的獎勵函數或判別不可行性？

核心方法與創新

本論文首先從理論層面定義了三種抽象的「任務」概念：

1. 一組可接受的行為（acceptable behaviors）：任務可被定義為一集合，所有集合內的行為均被認為合格，且若行為不在集合中即視為不合格。
2. 行為的偏好部分序（partial ordering over behaviors）：不僅指定哪個行為是可接受的，還對行為之間建立偏好關係，例如A行為優於B行為，但C行為與A不可比。
3. 軌跡的偏好部分序（partial ordering over trajectories）：將任務視為對整個狀態-行為序列（軌跡）的偏好排序，考量的對象不只是單一行為而是整體行為序列的質量。

這三個定義試圖以不同層次的抽象刻畫「任務」的多元面向，與用獎勵函數描述任務的傳統思路相互對照。

論文的重要理論貢獻在於證明：

• 雖然馬可夫獎勵函數能表示許多任務類型，但對於上述三類任務，各自仍存在一組任務無法被任何馬可夫獎勵函數精確刻畫。
• 換言之，馬可夫獎勵函數的表達能力不是全能，也存在根本限制。

針對此，作者提出多個多項式時間複雜度的演算法，這些演算法可根據任務規格：

• 嘗試構造出一個對應的馬可夫獎勵函數，使得最大化該獎勵的策略能夠實現任務定義的偏好目標。
• 當不存在此類獎勵函數時，演算法能夠證明沒有馬可夫獎勵函數可捕捉該任務。

這套演算法不僅理論上填補了獎勵函數表達能力的空白，也為任務規格和獎勵函數的轉換流程提供了具體操作步驟。

主要實驗結果

為了驗證理論分析及演算法的實用性，作者在多種環境中進行實驗，並搭配理論所預測的表達限制相互對照。實驗設計包括：

• 嘗試構造可行的馬可夫獎勵函數來符合特定的任務偏好設定。
• 測試當給定的行為偏好或軌跡偏好無法被馬可夫獎勵函數描述時，演算法是否能正確識別不可行狀況。

結果顯示演算法成功在多數可被表達的任務中找到合適的獎勵函數，而在理論上不可表達的任務中則能準確判斷出無解，顯示其在實務應用中具備高可靠度。

此外，通過具體案例說明，使得結果不僅是抽象理論，而能用直觀的強化學習場域具體呈現，幫助研究者發現現實環境中設計獎勵函數的潛在問題與陷阱。

對 AI 領域的深遠影響

本論文的貢獻不僅在於對獎勵函數的表達極限劃下明確界線，更對強化學習及更廣泛的人工智慧領域提出幾項深遠啟示：

1. 重新審視獎勵設計的本質：傳統依賴手動設計獎勵函數（reward shaping）實際上可能無法捕捉所期待的偏好或複雜任務目標，提醒研究者設計時需謹慎評估獎勵函數的可行性和表達限制。
2. 促使結合其他任務規格架構：既然馬可夫獎勵函數在表達上有限，未來可朝結合邏輯語義、偏好學習（preference learning）、階層式任務規範或利用更高階策略演算法發展。
3. 引導獎勵工程與任務轉換自動化：提出了系統化算法給予理論指引，將任務偏好轉化為獎勵函數，對產業落地的強化學習系統設計具有直接技術價值，降低手動調試代價。
4. 理清目標達成與表達方式的根本差異：論文讓社群警覺到獎勵函數並非所有任務目標的萬能鑰匙，任務規格設計應成為研究的主軸之一，推動AI系統行為的可控性與可解釋性提升。

綜言之，《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