On the Expressivity of Markov Reward

在強化學習（Reinforcement Learning, RL）領域中，「獎勵函數」是驅動代理（Agent）學習的核心力量。它定義了代理在環境中學習和決策的目標，是設計智能體行為的關鍵工具。然而，設計一個能夠精確反映複雜任務目標的獎勵函數，長期以來一直是挑戰性很高的問題。這篇由Abel等人發表於NeurIPS 2021，並榮獲Outstanding Paper獎的論文《On the Expressivity of Markov Reward》，正是針對「馬可夫獎勵函數（Markov reward functions）」在捕捉不同形式任務表達力（expressivity）上的極限與可能性，提出了創新的理論框架與實證分析，為理解與設計有效獎勵機制開啟了一扇新的大門。

研究背景與動機

強化學習代理透過最大化累積獎勵來學習行動策略，獎勵函數通常被設計為馬可夫性的，即獎勵只依賴於當前觀察狀態與行為。然而，日常生活中的任務本質上具備複雜的結構，有時我們想要定義的「任務」並非簡單的獎勵數值，而可能是對行為模式的一組偏好，甚至是對整條軌跡（trajectories）的排序。過去許多研究集中在如何輔助或改進獎勵設計，但缺乏系統地探索馬可夫獎勵函數本身的表達限制與能力。

本論文的動機即在於從根本上理解：以馬可夫獎勵函數為表達工具，我們能精確描述哪些形式的任務？又在哪些情況下馬可夫獎勵函數無法涵蓋我們想要的行為目標？透過理論嚴謹的分析，幫助強化學習研究者和應用工程師在獎勵函數設計時有更明確的預期與指引，避免「獎勵誤導」等問題。

核心方法與創新

論文用三種抽象且具有代表性的「任務（task）」定義框架，依序涵蓋了不同的行為偏好層級：

1. 可接受行為集合（Set of acceptable behaviors）：定義一組代理行為是「允許」的或「不允許」的，重點在於區分好行為與壞行為。
2. 行為的部分排序（Partial ordering over behaviors）：給行為間建立偏好等級，但不必對所有行為完全排序，允許某些行為間比較不明確。
3. 軌跡的部分排序（Partial ordering over trajectories）：將任務描述提升到整個狀態-行為序列的層級，訂定軌跡之間的偏好關係。

這種多層次的任務抽象，是論文的一大創新，因為它拓展了獎勵函數表達力的視角，不僅限於傳統意義上的「數值函數」，而更貼近任務目標的實質需求。

基於這三種任務定義，論文進一步嚴謹證明了：雖然馬可夫獎勵函數能覆蓋許多任務類型，但針對每一種任務抽象，都存在無法被任何馬可夫獎勵函數表達的反例—也就是說，獎勵函數的表達能力並非無限強大，存在本質的限制。

為了克服這種限制，作者設計了一套多項式時間複雜度的算法，這些算法能夠在給定任務的前提下，構造出相應的馬可夫獎勵函數以促使代理優化該任務，或者判定任務是否根本無法以馬可夫獎勵函數表示。這對於獎勵設計者而言是一項強大工具，因為它能自動化評估與生成行為偏好背後的獎勵結構，並明確指出設計困難所在。

主要實驗結果

除了理論貢獻外，論文還進行了一系列實驗，驗證理論分析的正確性與適用性。這些實驗涵蓋模擬環境中的任務建模，展示了所提出的算法能夠有效產生對應的馬可夫獎勵函數，並在這些獎勵函數指導下，強化學習代理成功實現預期的行為目標。

同時，實驗也呈現出部分任務無法被馬可夫獎勵函數覆蓋時，算法能準確識別該狀況，避免無謂的獎勵設計嘗試。此結果驗證了理論上對於表達力限制的推論，也使得研究結論更具實務價值。

對 AI 領域的深遠影響

本論文從根本上揭示了馬可夫獎勵函數在描述任務目標上的本質侷限，對於強化學習的理論基礎具有重要補充意義。許多現實世界應用所面臨的目標常常超越簡單的數值獎勵定義，這促使研究者重新思考獎勵設計及目標指定的策略。

此外，提供可執行的多項式時間算法，不僅讓理論結果得以實踐，也促進了獎勵函數自動合成領域的發展，有助降低人工設計獎勵函數的難度與錯誤率。這亦可能催生出更靈活且穩健的強化學習系統，使其能在複雜、多樣的任務中展現更優異表現。

透過這項研究，我們更清楚地認識到，目前強化學習中依賴的馬可夫獎勵函數，並非萬能的行為規範標準，未來或許需結合其他任務規格手段（如非馬可夫獎勵、輔助目標表示，甚至領域知識整合），來擴充代理理解與自適應的深度與廣度。

整體而言，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