On the Expressivity of Markov Reward

在強化學習（Reinforcement Learning, RL）的領域中，獎勵函數（Reward Function）扮演著關鍵角色，是引導智能體學習並優化行為的核心信號。然而，獎勵函數的建構通常依賴領域知識或手工調校，且其形式對最終學習成果的影響尚未被充分理解。特別是在馬可夫決策過程（Markov Decision Processes, MDPs）中，以狀態-行動對為基礎的即時獎勵函數是否具備足夠的表達力，來涵蓋所有可能目標及其對應的行為策略，一直是理論與應用層面的重要問題。

《On the Expressivity of Markov Reward》由Abel等人於NeurIPS 2021發表，並榮獲Outstanding Paper獎項，針對馬可夫獎勵函數的表達能力（Expressivity）進行深入理論探討與實證分析，開啟了強化學習研究中對獎勵設計本質的嶄新視角。

研究背景與動機

在標準的MDP框架中，我們定義了狀態空間(S)、行動空間(A)、轉移機率(P)、折扣因子(γ)和獎勵函數(R)。獎勵函數通常被設計成依賴當前狀態以及所採取的行動，即所謂的Markov獎勵函數。然而，真實世界任務的獎勵結構往往比單一狀態-行動對更複雜，可能涉及歷史資訊、延遲回饋，甚至是非馬可夫性質。

過去，有研究嘗試使用非馬可夫獎勵或是引入額外的記憶狀態（如部分觀測MDP）來提升獎勵函數的靈活性，但同時增加了學習的困難度與理論分析的複雜度。作者因此聚焦於根本問題：標準的馬可夫獎勵函數究竟有多強大？它到底能不能「表達」出與非馬可夫獎勵等效的目標？如果不能，限制在哪裡？這些問題的答案將有助於指導未來獎勵設計與強化學習演算法的開發。

核心方法與創新

本論文創新的角度在於系統性地分析馬可夫獎勵函數的表達能力，並提出了關鍵理論定義與框架。作者定義了「獎勵表達能力」(Reward Expressivity)這一概念，旨在衡量給定MDP和報酬函數類別，是否存在一個馬可夫獎勵函數，其最優策略能夠對應任何給定的目標策略。

具體而言，作者分析了兩種獎勵函數：

• Markov Reward Functions (MRFs)： 傳統定義，只依賴當前狀態與動作。
• Non-Markov Reward Functions (NMRFs)： 可依賴歷史或環境中更複雜的特徵。

關鍵貢獻包括：

1. 理論證明： 作者嚴格證明MRFs在一般情況下無法表達所有NMRFs對應的行為策略。換句話說，存在某些策略目標，只能透過非馬可夫獎勵函數明確指定，而馬可夫獎勵函數難以準確地「表達」這些目標。
2. 構建反例： 藉由精巧構造的簡單MDP模型，展示了無法被馬可夫獎勵函數捕捉的行為差異，具體說明表達能力的限制區域。
3. 表示增強條件： 探討在何種條件下，可以通過擴充狀態空間（如增加記憶狀態）或改變折扣因子，提升馬可夫獎勵函數的表達力，使其能夠近似或等效於部分非馬可夫獎勵函數。
4. 計算複雜度與可學習性討論： 持平理論結果與實際學習過程，闡述獎勵函數設計與學習難易之間的取捨。

主要實驗結果

作者透過一系列嚴謹的實驗驗證理論結果，主要涵蓋：

• 簡化MDP實驗： 利用理論構造的MDP場景，展示不同獎勵函數對策略的影響，並證實某些策略確實無法由任意馬可夫獎勵函數所誘導。
• 擴展狀態空間試驗： 將原本的MDP擴展為擁有更豐富狀態向量的形式，測試此舉是否能提升馬可夫獎勵的表達範圍。結果顯示，透過擴充記憶狀態，部分非馬可夫獎勵可近似表示。
• 深度強化學習方法結合獎勵調整： 採用現代深度RL演算法，評估不同獎勵函數對學習速度與策略表現的影響，結果支持理論推論，即限制的馬可夫獎勵會影響最終策略的多樣性和最優性。

對 AI 領域的深遠影響

本論文的理論洞見與實驗驗證，為強化學習中獎勵設計的根本問題提供了明確回答和引導，具有以下多面向的深遠影響：

1. 理論基石： 明確了傳統馬可夫獎勵函數在表達行為策略上的局限，促使研究者重新思考RL框架中獎勵與策略間的內在關係，有助於推動更普適的理論模型發展。
2. 實務指引： 在複雜任務建模與智能體設計中，強調單純依賴馬可夫獎勵函數可能不足以準確表達目標，建議引入狀態擴充、歷史資訊整合或非馬可夫獎勵設計，提升策略適切性與效率。
3. 強化學習演算法創新： 研究結果激勵未來設計能夠處理非馬可夫獎勵的演算法，例如增強學習中帶記憶體的架構、序列決策模型與元學習技術，進一步提升智能體的泛化能力與決策品質。
4. 交叉領域啟示： 獎勵設計常涉及人類行為的模擬與價值觀表達，該研究對於從事逆向強化學習（Inverse RL）、因果推理與可解釋性AI的研究者具有重要啟示，能夠幫助他們更準確定義與推斷隱藏的獎勵目標。

綜合而言，Abel等人以嚴謹的數學推導和實驗分析，揭露了馬可夫獎勵函數的本質表達限制，這不僅深化了我們對強化學習理論的認知，也為未來更靈活且可擴展的獎勵設計指明了方向。隨著人工智慧應用場景日益複雜，理解與突破這些限制將成為推動智能體行為更精準、多樣且自主的重要里程碑。

---

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