On the Expressivity of Markov Reward

在強化學習（Reinforcement Learning, RL）中，獎勵信號（reward）是驅動智能體學習與決策的核心動力。設計一個合適的獎勵函數，不僅直接影響智能體的學習效率，更決定了智能體能否成功掌握與執行預期的任務。然而，在現實應用中，如何利用獎勵函數來全面而精確地表達我們希望智能體完成的「任務」（task）依然是一大挑戰。NeurIPS 2021 年 Abel 等人發表的論文《On the Expressivity of Markov Reward》獲得Outstanding Paper獎，針對強化學習中獎勵函數的表達能力提出了深刻而系統的理論分析，並開拓性地提出了多種任務抽象，為獎勵設計的理論基礎與實務應用提供重要啟示。

研究背景與動機

在傳統強化學習框架下，我們習慣以馬可夫獎勵函數（Markov Reward Function, 即獎勵僅取決於當前狀態及行動）來定義任務。這種定義方式結構簡單且易於計算，但也極具限制性。複雜的任務常常不能僅靠單一的馬可夫獎勵函數來完美描述，例如需要考慮行為序列某些長期特性、或者要求多種行為之間的偏好排序，這就挑戰了獎勵的表示能力。儘管有不少實務上嘗試透過豐富的特徵工程或額外的環境設計來彌補，此論文則從理論角度系統地探討了獎勵函數的「表達能力」（expressivity），試圖揭示哪些理想的任務類型是馬可夫獎勵函數能夠完美覆蓋，哪些則無法。

他們定義了三種不同抽象層次的「任務」概念：

1. 行為集合（Set of Acceptable Behaviors）：智能體展現的行為屬於某個「可接受」集合即可，不必精確排序。
2. 行為的偏序（Partial Ordering over Behaviors）：對不同行為存在偏好等級，即某些行為比其他行為優越，但未必形成嚴格的全序。
3. 軌跡的偏序（Partial Ordering over Trajectories）：對狀態-行動序列本身建立偏序，強調軌跡端對端的偏好。

這三個抽象層次的任務逐層遞進，表述的任務結構也更趨複雜。

核心方法與理論創新

本論文的核心在於形式化「任務表達」（task expressivity）問題，並深入探討馬可夫獎勵函數能否在上述三種任務抽象下精確或近似地表示智能體的行為偏好。

首先，作者嚴格定義了「表示任務」的需求，即存在一個馬可夫獎勵函數，使得根據該獎勵函數優化的策略能夠達成特定的任務標準。接著，論文提出了幾個重要的理論結果：

• 在行為集合層次，大多數簡單的任務可以透過馬可夫獎勵函數表達，但存在無法完全用單一馬可夫獎勵函數捕捉的特殊行為集合。
• 在行為偏序層次，部分任務偏好結構能用獎勵函數表示，然而對於多數複雜的偏序結構，尤其中間存在不連續或矛盾的偏好，無法被馬可夫獎勵函數完全覆蓋。
• 在軌跡偏序層次，將偏好直接施加在整個狀態-行動序列上，這種抽象更加強大且靈活，但同時也超越了馬可夫獎勵函數的表達範圍，存在明顯的不可表達情況。

此外，作者開發了一組多項式時間複雜度的演算法，用於：

1. 建構對應於特定任務描述的馬可夫獎勵函數（若存在）。
2. 判斷某個任務描述是否能由馬可夫獎勵函數表示。

這些演算法結合了優化與形式邏輯推理，為實務中獎勵設計提供了系統化、理論保證的方法，而非靠經驗法則或手動實驗。此外，論文中多項定理證明了馬可夫獎勵函數的理論邊界，尤其強調了避免誤用獎勵函數的重要性。

主要實驗結果

論文在多個合成環境與實驗場景中驗證理論發現，主要包含：

• 使用已知的行為集合範例，展示如何有效地回推具有任務識別能力的馬可夫獎勵函數。
• 針對帶有偏序的行為，實現了計算偏序能夠被馬可夫獎勵函數表示的判定，並在部分實驗案例成功刻畫了獎勵函數。
• 對於軌跡偏序的情境，證明在特定情況下，無法找到合適獎勵函數，而智能體若強行優化錯誤的獎勵，將導致與預期目標嚴重偏離的結果。
• 通過智能體在標準強化學習任務中執行的試驗，展示在知道任務不可被馬可夫獎勵函數完全表達時，使用論文提出的方法能夠及早警示設計者。

這些實驗不僅驗證了理論結果的準確性，也強調實際應用中對獎勵設計的策略性思考。

對 AI 領域的深遠影響

此篇論文在理論與實務層面均具有深遠意義：

• 理論基礎的補足：強化學習社群長久以來依賴馬可夫獎勵函數，卻缺乏對其表達能力的系統理解。此論文填補了這一空白，將獎勵函數的使用界限以嚴謹證明形式呈現，為後續推廣或改良獎勵設計奠定堅實基石。
• 細化任務規範的框架：提出三種抽象層次的任務定義，提供AI設計者更清晰的思考框架，幫助明確界定並拆解任務需求，促進更加合理與有效的獎勵表示策略。
• 啟示獎勵設計與安全：理論結果表明，盲目優化錯誤的獎勵函數可能導致行為偏離任務目標，這與強化學習在現實應用中的安全性、可靠性密切相關，提升了獎勵設計的警示作用。
• 跨領域推廣效果：該研究方法與理論可推廣至相關領域，包括模仿學習、逆向強化學習（IRL）、多目標優化等，促進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