技術的サマリー：遅延フィードバックを伴う線形およびニューラル決闘型バンディット

1. 問題定義

本論文は、確率的遅延フィードバック下における**文脈型決闘型バンディット（CDB）**の問題を取り扱います。標準的な CDB 設定では、エージェントはアーム（候補）のペアを選択し、潜在的な報酬関数を学習するために即座に二値の選好フィードバック（例：$x_1 \succ x_2$）を受けます。しかし、大規模言語モデル（LLM）の整合性、プロンプト最適化、ディスプレイ広告などの実世界応用では、フィードバックは非同期であることがよくあります。

本論文で形式化された特定の設定は、以下を仮定します：

• 確率的遅延: 時刻 $s$ で実行されたアクションに対するフィードバックは、確率的な遅延 $D_s$ の後に到着します。
• ハードスレッショルド: 最大観測ウィンドウ $M$ が存在します。もし $D_s > M$ である場合、フィードバックは欠損（検閲）されたものとして扱われます。
• 観測確率: ウィンドウ内でフィードバックが到着する確率は $\rho = P(D_s \le M)$ です。
• バイアス課題: 線形バンディットでは推定量が閉形式解（例：リッジ回帰）を持つことと異なり、決闘型バンディットは Bradley-Terry-Luce（BTL）モデル下での最尤推定（MLE）に依存します。この閉形式解の欠如により、単純な補完や欠損データの無視といった標準的な遅延フィードバック技術の単純な適用は、容易に境界付けまたは修正できない体系的なバイアスを導入します。

2. 手法

著者らは、ヒューリスティックな補完なしにこれらの遅延に対処するために設計された 2 つの新しいアルゴリズムを提案します。**遅延フィードバックを伴う線形決闘型バンディット（LDB-DF）と遅延フィードバックを伴うニューラル決闘型バンディット（NDB-DF）**です。

中核メカニズム：逆確率重み付け（IPW）

中核的な革新は、損失関数に直接**逆確率重み付け（IPW）**メカニズムを統合することです。

• 重み付け戦略: 時刻 $t$（ただし $s < t$）で観測されたフィードバックインスタンス $y_s$ に対して、アルゴリズムは重み $\omega_{s,t} = \frac{1}{\rho} \cdot \mathbb{I}\{D_s \le \min(M, t-s)\}$ を割り当てます。
• 不偏補正: 観測されたフィードバックの寄与を $1/\rho$ でスケーリングすることで、代理損失の期待勾配は真の勾配の不偏推定量となり、確率的観測メカニズムと欠損データによって導入されたバイアスを効果的に無効化します。

アルゴリズム 1: LDB-DF（線形設定）

• モデル: 線形報酬関数 $f(x) = \theta^\top \phi(x)$ を仮定します。
• 推定: 「到着した」フィードバックのみを使用して、IPW 正則化ロジスティック損失を最小化します。
• 探索: 上界信頼区間（UCB）戦略を利用します。最初のアームは現在の推定 $\theta_t$ に基づいて貪欲に選択されます。2 番目のアームは、最初のアームに対する選好差の UCB を最大化するように選択され、確率的ノイズと遅延に起因する不確実性の両方を考慮した信頼半径 $\beta_t$ を組み込みます。
• 情報行列: 選択されたペアの特性ベクトルを使用して、フィードバックの遅延に依存せずに即座に更新されます。

アルゴリズム 2: NDB-DF（ニューラル設定）

• モデル: ReLU 活性化を備えた全結合ニューラルネットワーク $h(x; \theta)$ を使用して非線形報酬関数を近似します。
• 推定: 同じ IPW 重み付け交差エントロピー損失を使用してネットワークをオンラインで訓練し、有効ウィンドウ内で到着したフィードバックのサブセットからのみ学習します。
• 理論的枠組み: 解析は**ニューラルタンジェントカーネル（NTK）**領域で行われます。アルゴリズムは、ネットワークが十分に広い（$m$）と仮定し、初期化時に勾配特性空間において線形関数として近似して振る舞うとします。
• 探索: 線形の場合と同様に、UCB 戦略を採用します。探索ボーナスは NTK 特性空間から導出され、選好差における認識的不確実性を定量化します。

3. 理論的貢献

本論文は、遅延パラメータ（$M$ および $\rho$）の影響を明示的に特徴づけた、両設定に対する厳密な後悔の上限を提供します。

• 線形後悔の上限: LDB-DF の累積後悔は $\tilde{O}\left(\frac{M}{\rho \kappa_\mu} d \sqrt{T}\right)$ として確立されます。

  • 項 $\frac{M}{\rho}$ は乗法的なペナルティとして機能します。観測確率 $\rho$ が小さい（サンプル数が少ない）こと、および閾値 $M$ が大きいこと（より長い潜在的遅延）は、後悔を線形的に増加させます。
  • $\rho=1$ かつ $M=1$（遅延なし）の場合、この上限は標準的な線形決闘型バンディットにおける最先端の $\tilde{O}(d\sqrt{T})$ を回復します。

• ニューラル後悔の上限: NDB-DF の累積後悔は $\tilde{O}\left(\frac{M}{\rho \kappa_\mu} \tilde{d} \sqrt{T}\right)$ として確立されます。ここで $\tilde{d}$ は NTK 行列の有効次元です。

  • 証明は、遅延に起因する体系的なバイアスからマルチンゲールノイズを分離するための新しい「加算と減算」分解技術に依存しています。
  • 解析は、複雑な非線形関数近似子を用いても、問題の根本的な難しさ（観測確率と遅延の大きさの間のトレードオフ）が維持されることを確認しています。

4. 実験結果

著者らは、遅延を無視するかヒューリスティックな補完を使用するベースラインに対して、LDB-DF と NDB-DF を評価しました。

• ベースライン:
  • 無視: 同じモデルアーキテクチャを使用しますが、重み付けなしで到着するまで保留中のフィードバックを破棄します。
  • ヒューリスティック: 現在のモデルが予測する選好（バイアスのかかった代理）を使用して欠損フィードバックを補完します。
• データセット:
  • 合成: 確率的幾何学的遅延を伴う線形、二次、および三次の報酬関数。
  • 実世界: InstructZero ベンチマーク（29 の指示誘導タスク）を使用した自動化プロンプト最適化。
• 知見:
  • 提案された 2 つのアルゴリズムは、累積後悔の点でベースラインを大幅に上回ります。
  • 非線形設定では、ヒューリスティックベースラインは自己増幅的な予測誤差（ハルシネーション）により、しばしば最適ではない領域に収束し、無視ベースラインはデータの希少性に苦しみます。
  • LDB-DF と NDB-DF はフィードバックの遅延に対して頑健であり、プロンプト最適化タスクにおいて効果的に探索空間をナビゲートします。

5. 意義と主張

本論文は、以下の 3 つを同時に処理する最初の統合フレームワークを提供することにより、選好ベースの学習における重要なギャップを埋めると主張しています：

1. 選好フィードバック（決闘）: 絶対報酬ではなく、二値の相対結果。
2. 非線形近似（ニューラル）: ニューラルネットワークによる複雑な報酬ランドスケープ。
3. 確率的遅延/欠損データ: 現実的なフィードバック遅延と検閲。

著者らは、そのアプローチがヒューリスティックな補完から離れ、IPW を通じた原理的かつ不偏の解を提供することを強調しています。理論的解析は、この特定の設定に対する最初の後悔の上限を確立し、パフォーマンスの低下が予測可能であり、遅延特性（$M/\rho$）に線形依存することを示しています。この研究は、特に LLM の整合性とプロンプト最適化における、人間ループシステムにおける非同期な選好学習の改善のための基礎的なステップとして位置づけられています。