長程決策中的成對偏好強化學習：Markov Decision Contest 的機制與邊界

by
目錄

🌏 Read this article in English

強化學習（RL）在長程決策任務中正面臨一個結構性的張力：當時間跨度拉長、狀態空間變得龐大時，傳統的標量獎勵函數往往難以精確捕捉複雜的價值觀；而依賴成對偏好（Pairwise Preferences）的方法雖然更易於定義目標，卻在理論保證與計算效率上存在缺口。研究團隊提出的「Markov Decision Contest」模型試圖填補這個缺口，它不僅證明了在特定偏好標準下，隨機定常馬可夫策略即為全域最優，更將求解複雜度證明為屬於 P 類問題。這項保證僅適用於論文證明的平均偏好邊際與有限單鏈設定：精確求解與 HPI 具有相應的理論保證，而 HPI-Clip 是面向高維任務的近似方法，目前支持它的是實證比較結果，不能直接沿用前述保證。

標量獎勵的邊界與成對偏好的比較

在傳統的強化學習範式中，代理的目標被定義為最大化預期標量獎勵的總和。這種方法在目標可量化的環境中表現良好，但在處理人類價值觀或複雜多目標決策時，往往顯得笨拙。給出一個具體的數字獎勵容易，但精確量化「什麼樣的行為軌跡更符合人類偏好」卻極具挑戰性。相比之下，要求人類比較兩個結果並指出「哪個更好」，在實務操作上通常較容易指定。

然而，現有的成對偏好強化學習方法在面對長程決策時遇到了瓶頸。這些方法通常缺乏對馬可夫策略相對於歷史依賴型策略的性能保證。雖然歷史依賴策略在理論上能提供更完整的決策資訊，但在計算上往往是不可行的。這種理論與實踐的脫節，導致了訓練效率較低且缺少明確的理論邊界。

核心機制：Markov Decision Contest 的因果鏈

為了解決上述缺口，研究團隊提出了「Markov Decision Contest」這一新的問題模型。要理解其為何成立，可以將其類比為一場策略競賽。

在傳統 RL 中，Agent 試圖最大化一個固定的獎勵函數 r。而在 Markov Decision Contest 中，該模型將偏好關係建模為一個零和遊戲的變體。具體而言，研究定義了一個偏好邊際（Preference Margin）M((s,a),(s′,a′))，它衡量了在狀態 s 採取動作 a 後，與另一個策略在狀態 s′ 採取動作 a′ 相比，前者相對於後者的優勢程度。

Markov Decision Contest 將偏好學習轉化為「平均偏好邊際」的極大化問題，這使得原本需要依賴複雜歷史記憶的決策問題，能夠在馬可夫策略空間內找到最優解。這個模型的核心洞察在於：通過最大化平均偏好邊際，可以將問題轉化為一個可以在馬可夫策略空間內求解的優化問題。研究證明，在這種設定下，存在一個隨機定常馬可夫策略 π，它是所有歷史依賴策略中最優的。這為處理複雜偏好設定提供了一個更高效的計算框架，而不必強制要求模型具備複雜的歷史記憶。

從數學機制上看，最優的隨機定常馬可夫策略等價於解決以下極小化極大問題： maxπ ∈ ΠSRminπ′ ∈ ΠSR∑s, a∑s′, a′xπ(s,a)xπ′(s′,a′)M((s,a),(s′,a′)) 其中 ΠSR 代表隨機定常馬可夫策略空間。這個公式表明，研究不是在尋找一個絕對的獎勵函數，而是在尋找一個在與所有可能對手的比較中表現最穩健策略。

計算可行性與 HPI 算法的實踐

這項研究最關鍵的貢獻不僅在於概念創新，更在於嚴格的理論保證與實證效率的提升。

理論突破：計算可行性

首先，在理論層面，研究證明瞭求解一個有限單鏈（Finite Unichain）Markov Decision Contest 的問題屬於 P 類。這意味著該問題具備高效的計算可行性，存在一個線性規劃，能夠使用 |S||A| + |S| + 1 個變數和 2|S||A| + |S| + 1 個約束條件來精確求解。這項研究提供了明確的計算可行性邊界，因為它將成對偏好 RL 的複雜度與傳統 Markov Decision Processes (MDPs) 拉平了。

算法實踐：從理論 HPI 到實務 HPI-Clip

其次，在算法設計上，研究區分了理論保證與實務近似兩個層次。在理論端，研究提出了一種基於 Hedge Algorithm 思想的迭代算法 HPI（Hedge Policy Iteration）。理論分析顯示，HPI 的優化間隙不超過 $4M_{max} \tau \sqrt{\log(|A|)/K}$，並以 $1/\sqrt{K}$ 的次線性速率收斂。

然而，在面對高維度連續狀態空間時，嚴格執行 HPI 並不現實。為此，研究團隊進一步提出了 HPI-Clip 作為實務上的近似算法。在實證層面，研究團隊在多個高維度、長時間跨度的決策任務上進行了測試，並與現有方法 SPPO（Swamy et al., 2024）進行了對比。結果顯示，HPI-Clip 在學習效率上顯著優於 SPPO：

  • 性能提升：在 Ant-v5, Half Cheetah-v5, Hopper-v5, Humanoid Standup-v5, Pusher-v5, Reacher-v5, Swimmer-v5 這七個任務中，HPI-Clip 的 AUC 置信區間嚴格高於 SPPO。
  • 核心差異：SPPO 對整個軌跡中的每個時間步偏好累積進行平均；而 HPI-Clip 則保留了區域性訊號（不進行此種平均），這使其在捕捉局部偏好時更具敏銳度。

此外，在 Walker2d-NT 任務中，研究還展示了一種基於非傳遞性偏好的邊界實現，其中三個競爭目標遵循「高度 > 速度 > 穩定性 > 高度」的迴圈關係，這進一步驗證了模型處理複雜偏好結構的能力。

取捨與實務意涵：從 PPO 到 HPI-Clip 的演進

將 HPI-Clip 視為 PPO 的一般化形式是一個極具洞察力的視角。PPO 學習自獎勵函數 r，而 HPI-Clip 學習自偏好邊際 M。當偏好邊際 M 等於基於 Bradley–Terry 模型的勝率機率 PBT 時，兩者的最優策略並不一致。這揭示了成對偏好學習與傳統獎勵最大化之間的內在差異：前者關注的是相對優勢，後者關注的是絕對價值。

在實務應用中，這種轉變帶來了明確的取捨：

  1. 標記成本 vs. 訓練效率：收集成對偏好數據通常比設計精確的獎勵函數更容易，尤其是當目標涉及主觀價值時。HPI-Clip 的引入使得利用這些更易獲取的數據進行高效長程優化成為可能。
  2. 理論保證 vs. 實務擴展性：理論上的 HPI 算法提供了次線性收斂率與明確的優化間隙界限，但在極端高維狀態空間中，精確求解的計算成本過高。實務上使用的 HPI-Clip 雖然放寬了這些嚴格的理論保證，卻透過近似機制換取了在高維任務中的執行效率。這要求研究者在「具備理論保證的精確求解」與「具備擴展性的近似算法」之間做出權衡。

對於正在使用 RLHF 的團隊而言，這項研究提供了一個值得考慮的方向：當傳統 PPO 在長程任務中出現不穩定或難以定義獎勵時，轉向基於偏好邊際的優化框架可能是一個更穩健的選擇。不過，目前的證據主要來自高維控制任務，尚未涵蓋大型語言模型微調或實際 RLHF 工作流，這仍是一個待驗證的假說。

結論與未來驗證點

在平均偏好邊際判準與有限單鏈設定下，Markov Decision Contest 證明隨機定常馬可夫策略可在所有歷史依賴策略中達到最優，且精確求解屬於 P 類。HPI 具備明確的次線性收斂保證；HPI-Clip 則是面向高維問題的近似算法，其證據來自與 SPPO 在一組長程控制任務上的比較，不能直接沿用 HPI 的理論保證。這些結果界定了該框架目前可支持的範圍，但控制任務之外的轉移效果尚未獲得驗證。

然而，該框架也有其明確的邊界。目前的理論保證主要針對有限單鏈 Markov Decision Contest，對於更複雜的狀態轉移結構或部分可觀察環境（POMDPs），其推廣性仍需進一步研究。此外，算法的性能高度依賴於偏好數據的質量；若人類偏好存在內在矛盾或噪聲過大，收斂性可能會受到影響。

未來值得觀察的方向包括：在更大規模的大型語言模型微調中，評估 HPI-Clip 相對於 SPPO 的長期穩定性；探索在非傳遞性偏好更複雜的場景下，算法的魯棒性與收斂行為；以及研究如何將線性規劃求解器與深度神經網絡更好地結合，以處理連續狀態空間中的精確求解問題。

這項工作並非要取代傳統的獎勵最大化方法，而是為強化學習工具箱增添了一個在特定情境下具備嚴格理論基礎的替代路徑。當獎勵函數的邊界變得模糊時，偏好邊際提供了一條可計算的路徑。

Sources