Learning Kernel-Based MDPs from Episodic Preferential Feedback

技術的サマリー：エピソード型選好フィードバックからのカーネルベース MDP の学習

問題定式化
本研究は、エピソード型マルコフ決定過程（MDP）の枠組みにおける人間フィードバックからの強化学習（RLHF）の問題に取り組みます。標準的な RL ではエージェントがスカラー報酬を受け取るのに対し、ここでは学習者は二値の選好フィードバックのみを受けます。各エピソード $k$ において、学習者は共通の開始状態から 2 つの方策 $\pi$ と $\pi'$ を展開し、2 つの軌道 $\tau_k$ と $\tau'_k$ を生成します。フィードバックは、どちらの軌道が選好されるかを示す単一の二値ラベル $y_k \in \{0, 1\}$ で構成されます。この選好は、累積（観測されない）報酬の差に適用された Bradley–Terry–Luce（BTL）リンク関数を介してモデル化されます：
$$y_k \sim \text{Ber}\left(\sigma\left(\sum_{h=1}^H r_h(z^k_h) - \sum_{h=1}^H r_h(z'^k_h)\right)\right)$$
ここで $\sigma$ はシグモイド関数です。目的は、価値関数 $V^\pi_1$ を最大化し、展開された方策の平均価値と最適価値との差として定義される累積後悔を最小化する方策を学習することです。

この設定は、報酬関数 $r_h$ と遷移演算子 $P_h$ が既知のカーネル $k$ によって誘導される再生核ヒルベルト空間（RKHS）$\mathcal{H}_k$ の要素である「カーネル MDP」構造を仮定します。具体的には、著者は非線形構造を捉え、ソボレフ空間とノルム同値であり、線形 MDP を超えた一般化を提供する「Matérn カーネル族」に焦点を当てています。

手法：PROSTO アルゴリズム
著者は、PROSTO（Sampled Trajectory induced Optimism による選好ベースの正則化最適化）を提案します。このアルゴリズムはエピソード単位で動作し、選好フィードバックとカーネル関数近似に適応された値反復アプローチを利用します。

1. 正則化カーネルロジスティック回帰（KLRR）による報酬推定：
   フィードバックが軌道レベルで二値であるため、報酬ベクトル $\theta$ は、ノルム重み付きペナルティを備えた最尤推定を用いて推定されます。推定量 $\hat{\theta}_k$ は、観測された選好の負の対数尤度を、正則化項 $\tau \|\theta\|^2_{\mathcal{H}_k}$ とともに最小化します。この回帰の共変量は、軌道差特徴量 $\phi_i = \sum_{h=1}^H \phi(z^i_h) - \phi(z'^i_h)$ です。

2. ランダム化 GP 摂動による探索：
   遷移ダイナミクスを事前に知らない（これにより決定論的楕円ボーナスが不可能になる）状態で軌道レベルでの十分な探索を確保するため、PROSTO はランダム化探索を採用します。探索ノイズベクトル $\epsilon_k$ は、軌道差の経験的共分散に依存する共分散構造を持つガウス過程（GP）からサンプリングされます。このノイズは報酬推定値に追加され、楽観性を誘発します。

3. カーネルリッジ回帰（KRR）による価値関数推定：
   価値関数は再帰的に推定されます。次の状態の期待値は、遷移サンプルに対する標準的なカーネルリッジ回帰を用いて近似されます。最終的な Q 関数推定値 $\hat{Q}^k_h$ は、報酬推定値（KLRR + GP ノイズ）と遷移推定値（KRR）を組み合わせ、有界性を確保するためにクリッピングを施して構成されます。

4. 方策の実行：
   学習者は、それぞれの楽観的 Q 関数推定値に対して貪欲な 2 つの方策 $\pi$ と $\pi'$ を選択します。これらの方策を実行して、次のエピソードの軌道と選好フィードバックを生成します。

主要な技術的貢献と課題
本論文は、カーネル MDP と軌道レベルの選好フィードバックを組み合わせる際に特有の 3 つの主要な技術的課題を特定し、新たな解決策を提供します。

• 対数被覆数の制御： カーネル MDP において、価値関数クラスの対数被覆数は、被覆メッシュ $\epsilon$ の逆数に対して多項式スケールで増加し、推定量の RKHS ノルムに依存します。線形 MDP では被覆数がエピソード数に対して対数的であるのに対し、カーネル設定では推定量ノルムが過度に増大すると、後悔の上限が空虚なものになる可能性があります。

  • 解決策： 著者は、KLRR における正則化パラメータ $\tau$ を慎重に調整し、報酬推定量の RKHS ノルムを明示的に制御します。これにより、誘導された関数クラスの被覆数を小さく保ち、意味のある信頼区間を可能にします。

• 非平滑ノイズを伴う軌道レベルの探索： 標準的な探索ボーナス（楕円ボーナス）は、意思決定時点では利用できない完全な軌道の知識を必要とします。GP サンプリングによるランダム化探索が使用されますが、Matérn カーネルからの GP サンプルパスは一般に対応する RKHS に属しません（より滑らかでないため）。これにより、標準的な被覆境界が適用不可能になります。

  • 解決策： 著者は、事後 GP サンプルパスに対する新しい高確率ガウス被覆境界を導出します。van der Vaart と van Zanten [2008] の結果を活用し、GP パスが RKHS 球の外に位置する一方で、高確率で適切に拡大された RKHS 球の $\epsilon$ 近傍（$\ell_\infty$ ノルムにおいて）内に位置することを示します。これにより、後悔分析に必要な被覆境界の導出が可能になります。

• 正則化パラメータと被覆パラメータのバランス： 正則化パラメータ（報酬用 $\tau$、遷移用 $\lambda$）と被覆メッシュ $\epsilon$ の調整は容易ではありません。小さな $\epsilon$ は誤指定エラーを減らしますが被覆数を増大させ、大きな $\epsilon$ は逆の効果をもたらします。

  • 解決策： 著者は、エピソード数 $K$ とカーネルの滑らかさパラメータ $\beta_p$ の関数として、$\tau$、$\lambda$、および $\epsilon$ を共同最適化します。このバランス調整により、信頼区間の幅が部分線形後悔のために十分に狭く保たれつつ、関数クラスの複雑さが制御されます。

結果と後悔の上限
本論文は、PROSTO が Matérn カーネル族のすべてのカーネルに対して部分線形累積後悔の上限を達成することを証明します。具体的には、後悔 $R(K)$ は以下のようにスケールします：
$$R(K) \leq \tilde{O}\left( \kappa_Z \max\left( H^{2.5} K^{1 - \frac{(\beta_p-1)^2}{2\beta_p(\beta_p+1)}}, H^3 K^{1 - \frac{\beta_p-1}{2(\beta_p+1)}} \right) \right)$$
ここで $\beta_p > 1$ はカーネルの固有値減衰パラメータ、$H$ はホライズン、$\kappa_Z$ は最大逆リンク勾配です。$K$ の指数は厳密に 1 より小さいため、$K \to \infty$ として最適方策への収束を意味します。

さらに、このアルゴリズムは計算的に効率的であり、エピソード数 $K$ に対して多項式時間のランタイムを持ちます。これは、標準的な報酬を伴うカーネル MDP に関する先行研究（例：Maran ら [2024b]）と区別されます。先行研究は部分線形後悔を達成するものの、一般のカーネル設定において多項式時間で計算的に実行可能であることが知られていないドメイン分割や最適化オラクルに依存しています。

意義と主張
著者は、本研究が Matérn カーネル族全体に対して証明可能な部分線形後悔を達成し、かつ計算的に効率的である、選好ベースの RL におけるカーネル MDP 向けの最初のアルゴリズムを提供すると主張します。

• 理論的新規性： 本研究は、通常は表形式または線形設定を扱う選好ベースの RL と、非線形設定を扱うカーネルベースの関数近似の間のギャップを埋めます。値反復の文脈における GP 探索ノイズの非平滑性を処理するための新しい手法を導入します。
• 計算効率： 非可解な最適化を必要とする可能性のある滑らかな MDP 向けの以前のノーリグレットアルゴリズムとは異なり、PROSTO は多項式時間実装を提供します。
• 限界： 著者は、後悔の上限が順序最適ではない可能性を認めています。現在、一部のカーネル設定で順序最適の境界を提供するドメイン分割アプローチは、遷移の確率性により局所的なベルマン演算子の推定が不可能になるため、軌道レベルのフィードバックとは互換性がないと指摘しています。

本論文は、導出された後悔の上限が部分線形である一方で、順序最適の境界を達成することは未解決の問題であり、現在のドメイン分割や一様被覆手法を超えた根本的に異なる手法が必要である可能性があると結論付けています。