Reinforcement Learning with Pairwise Preferences in Long-Term Decision Problems

技術要約：長期的な意思決定問題におけるペアワイズ選好を用いた強化学習

問題定義
従来の強化学習（RL）は、目標をマルコフ決定過程（MDP）内でのスカラー報酬関数の期待値の最大化として定式化します。しかし、大規模言語モデル（LLM）の微調整など、多くのアプリケーションにおいては、スカラー報酬を定義するよりも、ペアワイズ選好（例：「軌跡Aは軌跡Bよりも優れている」）を指定する方が自然であり、かつ実現可能です。ペアワイズ選好を用いた既存の強化学習手法は、報酬関数を推論するか、あるいは選好に対して直接最適化を行いますが、これらには以下の2つの決定的な限界があります。

1. 有限かつ固定された時間ホライゾンに依存しており、エージェントが固定ステップで終了しない長期的な意思決定問題においては実用的ではありません。
2. 定常的なマルコフ方策が履歴依存方策に対して最適であるという、標準的なMDP理論の根幹となる理論的保証を欠いています。

さらに、標準的なアプローチは、非推移的な選好（例：コンドルセのパラドックス）を捉えることができないことがよくあります。ここで、グループの集団的な選好やマルチフィーチャーによる評価は、推移的な順序を形成しません。

手法：マルコフ決定コンテスト（MDC）
著者らは、これらのギャップを埋めるために、**マルコフ決定コンテスト（MDC）**と呼ばれる新しい問題モデルを提案しています。MDCは、有限な環境 $(S, A, P, \mu)$ とマルコフ選好マージン $M: (S \times A) \times (S \times A) \to \mathbb{R}$ によって定義されます。目的は、他のあらゆる方策 $\pi'$ に対して平均選好マージンを最大化する方策 $\pi$ を見つけることであり、これはゼロサムゲームとして定式化されます：
$$\max_{\pi} \min_{\pi'} \sum_{s,a} \sum_{s',a'} x_\pi(s,a) x_{\pi'}(s',a') M((s,a), (s',a'))$$
ここで、$x_\pi$ は限定的な平均状態行動頻度（占有測度）を表します。

無限ホライゾン設定における理論的な扱いやすさを確保するため、著者らは遷移確率関数が**ユニチェイン（unichain）かつ非周期的（aperiodic）**であることを仮定しています。これらの条件下では、履歴依存方策の占有測度の集合は、定常的な決定論的方策の占有測度の凸包に等しいことが確立されています。

主な貢献

1. 定常方策の最適性: 本論文は、有限のユニチェインMDC内において、定常的な確率的方策がすべての履歴依存方策の中で最適であることを証明しています。これにより、探索空間をマルコフ方策に限定することの正当性が示され、選好ベースの強化学習における理論と実践の間の溝が埋められました。
2. 計算複雑性: 著者らは、MDCを正確に解くことが P（多項式時間）に含まれることを示しています。具体的には、$|S||A| + |S| + 1$ 個の変数と $2|S||A| + |S| + 1$ 個の制約を持つ線形計画問題を構築します。この複雑さは、MDCが非推移的な選好をサポートする厳密な一般化であるにもかかわらず、標準的な平均報酬MDPと同等です。
3. ヘッジ方策反復（Hedged Policy Iteration: HPI）: 近似的な反復アルゴリズムである**ヘッジ方策反復（HPI）**が導入されています。これは、「限界値（marginal values）」（累積選好マージン）に基づいて意思決定ルールを更新するためにHedgeアルゴリズムを利用します。
   • 収束性: HPIは、反復回数を $K$ とすると、$O(1/\sqrt{K})$ の劣線形レートで最適方策に収束します。
   • スケーラビリティ: 著者らは、HPIのポリシーグラディエント形式と、バッファおよび価値関数近似を利用するディープラーニング実装（アルゴリズム3）を導出しており、これにより高次元の環境への適用が可能になっています。

実験結果
著者らは、長期間のホライゾン（2048ステップ）を持つ13の高次元タスク（Mujoco-v5スイート）を用いて、HPIおよびそのクリップ版であるHPI-Clipを、自己プレイ選好最適化（SPPO）（Swamy et al., 2024）と比較評価しました。

• セットアップ: タスクには、標準的な連続制御問題（報酬の差から選好を導出したもの）と、明示的に非推移的な選好マージン（例：3つのうちベスト2つを選ぶルール）を特徴とする「Mujoco-NT」タスクが含まれます。
• パフォーマンス: 13タスク中12タスクにおいて、HPIおよびHPI-Clipは、SPPOと比較して著しく高い学習効率（エピソードリターンまたは反転最適性ギャップの曲線下面積によって測定）を示しました。
• アブレーション: 選好モデルがオフラインデータから学習された場合でも、これらの結果は維持されました。

意義と主張
本論文は、長期的な意思決定問題におけるペアワイズ選好を用いた強化学習が、これまで考えられていたよりも扱いやすいものであると主張しています。MDCモデルを導入することで、著者らは以下のフレームワークを提供しています。

• 定常的な方策が理論的に十分であり、複雑な履歴依存戦略の必要性を排除していること。
• 非推移的な選好が存在する場合でも、問題が計算効率的（P内）であること。
• 実用的なアルゴリズム（HPI）が高次元・長期間の問題にスケールし、既存の最先端手法を凌駕すること。

著者らは、これらの結果は長期間のタスクにおけるLLMなどのアプリケーションに対して有望であるものの、いつ報酬ベースの学習よりも選好マージンの学習が優位になるのか、また、これらの手法が実際に言語モデルをどの程度効果的に整列（align）させるのかについては、さらなる調査が必要であると述べています。本研究は、ペアワイズ選好RLの理論と実践を近づけることを目的としています。