On the Expressivity of Markov Reward

在強化學習（Reinforcement Learning, RL）領域中，獎勵函數（reward function）是指引智能體行為的核心角色，它定義了智能體的目標與學習方向。然而，獎勵函數的設計往往充滿挑戰：如何用一個合適的獎勵函數完整且精確地描述我們希望智能體達成的任務？這不僅牽涉到任務的可表達性（expressivity），更關係到強化學習的效能與應用範圍。NeurIPS 2021 年一篇獲獎論文《On the Expressivity of Markov Reward》由Abel等人發表，深刻探討了獎勵函數作為「任務定義機制」的潛力與局限，提供了理論基礎並帶來實務啟示，對強化學習領域具有深遠意義。

研究背景與動機

在強化學習的架構中，獎勵函數通常被設定為馬可夫獎勵（Markov Reward），意即獎勵依賴於現有狀態與行為而非歷史軌跡。這種假設讓問題被大幅簡化，也方便使用馬可夫決策過程（MDP）理論來設計與分析演算法。然而，真實世界的任務往往不只是簡單依賴當前狀態，也包含長期行為的排序、軌跡的完整性評估等複雜需求。過去的研究中，獎勵函數的設計多屬經驗性且缺乏理論框架，導致智能體無法準確達成預期行為，甚至陷入「獎勵錯誤」（reward hacking）或「負面轉移學習」（negative transfer）。

因此，作者團隊提出一個核心問題：“獎勵函數——尤其是馬可夫獎勵函數——究竟能表達什麼樣的任務？”他們抽象化任務為三種形式：
(1)「可接受行為集合」：定義哪些行為被認為是合格或符合要求的；
(2)「行為上的偏序關係」：對行為之間的優劣進行部分排序；
(3)「軌跡上的偏序關係」：對整條行為軌跡的優劣排序，強調歷史脈絡。
透過這三種抽象層級，探討現有標準的馬可夫獎勵系統能否完整表達這些概念。

核心方法與創新

本論文的最大貢獻在於理論證明與算法設計的結合。作者首先從理論角度嚴謹證明，存在這三類任務中，某些任務是無法被任何馬可夫獎勵函數精確描述的，即使是最理想化的構造也無解。這表明現有獎勵函數設計的本質限制，揭示了強化學習框架中“任務”與“獎勵”之間根本性的鴻溝。

接著，針對每一種任務類型，作者提出多項多項式時間（polynomial-time）的構造算法，用於產生對應的馬可夫獎勵函數，或判定該任務是否存在等價的馬可夫獎勵函數。這些算法不僅具有理論上的有效性，也為實務提供了可操作的工具，可指導研究者和工程師設計更合理的獎勵函數。具體而言：

• 針對「可接受行為集合」，提出判斷並生成獎勵函數的方法，確保智能體能最大化獎勵，進而行為落在合格集合內。
• 對於「行為偏序」，構造獎勵函數來反映行為之間的優劣關係，使得獎勵激勵智能體優先選擇優越策略。
• 在「軌跡偏序」層級，因軌跡涉及歷史影響，作者分析證明這是馬可夫獎勵函數的挑戰區域，且提出相應算法嘗試以馬可夫獎勵近似實現。

這些方法的提出，突破了以往獎勵設計多模糊和經驗性強、不可驗證的瓶頸，引入嚴謹的數學與算法工具，提升任務定義的透明度與精確度。

主要實驗結果

為驗證理論洞察，作者團隊針對三種任務概念執行了豐富的實驗。實驗部分採用典型的强化學習環境，測試新生成的馬可夫獎勵函數在智能體學習上的表現。結果證實以下幾點：

• 所提出的建構算法成功生成了符合任務定義的獎勵函數，使智能體行為大幅接近目標行為集合或行為排序。
• 在部分任務中，智能體若被強制使用馬可夫獎勵，確實無法達到任務目標，與理論預測相符，凸顯馬可夫獎勵的限制。
• 實驗也演示了利用證明框架判別任務不可表達的案例，避免了資源浪費於不可能達成目標的獎勵設計。

這些實驗不只是理論的驗證，更向社群展現如何在實務中利用新方法改進獎勵設計，尤其對複雜半結構化任務的提升效果明顯。

對 AI 領域的深遠影響

本論文在強化學習理論與實務上均具指標性意義。首先，它為「任務的數學定義」提供了更深刻的理解，拓展了強化學習中「獎勵函數=任務描述」的典型觀念。這破除過往研究中獎勵函數能無限表達任務的假設，強調設計者需清楚任務類型與其可表達性限制。

其次，從方法論角度，本論文帶來了算法工具，實現理論與實踐的銜接。工程師與研究者可用這些工具檢驗自己任務設計的合理性，及早識別無法由馬可夫獎勵函數表達的問題，促進定制化獎勵或替代架構的發展。

更廣泛來看，本研究的理念推動了強化學習中的「獎勵工程」（reward engineering）向「任務工程」（task engineering）轉型，鼓勵研究者思考智能體的根本目標與價值判斷，激發人工智能目標設定與規範化的深入探索，這對未來 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