技術要約：未知の遅延と敵対的汚染下における、事後提供コンテキストを伴う堅牢な線形デュエリング・バンディット

1. 問題定式化

本論文は、以下の3つの課題が同時に発生する揮発性の高い環境を対象とした、線形コンテキスト・デュエリング・バンディット (Linear Contextual Dueling Bandits: CDB) フレームワークにおける複雑な意思決定問題を扱っている。

1. 事後提供コンテキスト (Post-serving Contexts): 標準的なコンテキスト・バンディットでは、効用は事前アクション特徴量（例：ユーザー属性）のみによって決定されるが、ここでの真の効用は、アクション実行後に明らかになる潜在的な特徴量（例：配送時間、食品の温度）に依存する。学習者は、事前提供コンテキスト $x_t$ から事後提供コンテキスト $y_t$ へのマッピング $\phi^*$ を推定しなければならない。
2. 未知のフィードバック遅延 (Unknown Feedback Delays): フィードバックは遅延 $\tau_t$ を伴って到着するが、この遅延は確率的（劣ガウス的）または敵対的である。学習者は、どちらのレジームがアクティブであるか、また具体的な遅延シーケンスがどのようなものであるかを知ることはできない。
3. 敵対的汚染 (Adversarial Corruption): 敵対者は、累積的な予算 $C$ の範囲内で、観測された選好結果を汚染（0を1に、あるいはその逆に反転させる）することができる。

核心となる困難さは、これら要因の相乗的な相互作用にある。遅延は有効なサンプルサイズを減少させ、汚染された信号の統計的なレバレッジを増幅させる。さらに、学習者は、すでに遅延と汚染によって損なわれたフィードバックを用いて事後提供のマッピング $\phi^*$ を推定しなければならず、これが推定誤差の悪循環を生み出す。

目的は、最適な腕のペアと選択されたペアの間の効用ギャップである累積リグレット $R_T$ を最小化することであり、特定の遅延レジームや汚染の有無に対して不可知（agnostic）な状態でこれを達成することである。

2. 手法: RCDP-UCB

著者らは、これらの絡み合った課題に対処するために設計されたアルゴリズム・フレームワークである RCDP-UCB (Robust to Corruption, Delay, and Post-serving UCB) を提案する。

主要構成要素:

• コンテキスト予測: アルゴリズムは、アクション選択前に、事前提供コンテキスト $x_t$ から事後提供コンテキスト $y_t$ を予測するための学習済み近似器 $\hat{\phi}_t$（例：ニューラルネットワーク）を採用する。特徴ベクトルは $\hat{z}_t = (x_t, \hat{\phi}_t(x_t))$ として構築される。
• 二重デザイン行列 (Dual Design Matrices): アルゴリズムは、選択と推定を分離するために2つの異なる行列を保持する。
  • $\tilde{V}_t$: 全履歴行列 (Full History Matrix)。すべての時系列コンテキスト（到着したものと保留中のものの両方）を用いて構築される。この行列は、楽観性と安定性を確保するために、腕の選択と重みの計算に使用される。
  • $\hat{W}_t$: 観測履歴行列 (Observed History Matrix)。時刻 $t$ までに実際に到着したフィードバックのみから構築される。これは、統計的な妥当性を確保するために、パラメータ推定 ($\Theta_t$) にのみ使用される。
• 適応型重み付け戦略: 汚染と遅延によるバイアスの両方を軽減するために、統一された重み付けメカニメントが導入されている。サンプル $s$ に対する重み $\omega_s$ は次のように定義される：
  $$\omega_s = \min\left(1, \frac{\alpha}{\|\Delta z_s\|_{\tilde{V}_{s-1}^{-1}}}\right)$$
  ここで $\alpha$ は堅牢性パラメータである。この「クリッピング」戦略は、統計的レバレッジが高い（ノルムが大きい）サンプルをダウンウェイトし、敵対的に汚染された観測、および情報の幾何学的構造を歪ませる遅延フィードバックの両方の影響を効果的に制限する。
• リグレット最小化: アルゴリズムは、$\tilde{V}_t$ と予測された特徴量に基づき、探索と活用のバランスを取りながら、上限信頼境界 (Upper Confidence Bound: UCB) 戦略を用いて腕のペア $(a_t, b_t)$ を選択する。この際、選好パラメータ $\Theta^*$ と事後提供マッピング $\phi^*$ の両方の不確実性を考慮する。

3. 主な貢献

1. 統一的な解析フレームワーク: 事後提供コンテキスト、未知の遅延（確率的または敵対的）、および敵対的汚染を同時に組み込んだ、最初の線形デュエリング・バンディットの設定を定式化した。
2. アルゴリズム設計 (RCDP-UCB): コンテキスト・マッピングの推定と適応型クリッピング機構を統合した新しいアルゴリズムを導入した。決定的なのは、この重み付けスキームが遅延レジームに依存しない (delay-regime-agnostic) ことであり、遅延が確率的であるか敵対的であるかを事前に知ることなく効果的に機能する。
3. 理論的保証:
   • 上界 (Upper Bound): 標準的な正則性条件の下で、アルゴニズムは $\tilde{O}(d(\sqrt{T} + C + D))$ のリグレット上界を達成する。ここで $d$ は特徴量次元、$T$ はタイムホライゾン、$C$ は汚染予算、$D$ は遅延の複雑さ ($D = \max(\sqrt{\Lambda}, \mu_\tau)$) を表す。
   • 下界 (Lower Bound): 著者らは、事後提供コンテキストが存在しない場合において、$\Omega(\sqrt{dT} + dC + D')$ (ここで $D' = \max(\sqrt{d\Lambda}, d\mu_\tau)$) のミニマックス下界を導出した。これにより、遅延と汚染によるオーバーヘッドが情報理論的に避けられないものであることが確認された。
   • 最適性: 上界は、敵対的遅延に対して $\sqrt{d}$ の因子を除いて下界と一致しており、ほぼ最適な効率性を示している。

4. 実験結果

著者らは、合成環境および実世界のデータセット (UCI および OpenML) において、様々な条件下で RCDP-UCB を評価している。

• 合成設定: 線形および非線形（多項式、正弦波、絶対値）の事後提供マッピング、および変化する汚染予算 ($C$) と遅延レジーム（戦略的/敵対的、および確率的）をカバーする実験を行った。
• ベースライン: RCDB (汚染に堅牢)、ColSTIM、MaxInP、および MaxPairUCB を含む最先端の手法と比較した。
• 知見:
  • RCDP-UCB は、すべての遅延レジームおよび汚染レベルにおいて、ベースラインを一貫して上回る累積リグレットを達成した。
  • 本アルゴリズムは、事後提供コンテキストが極めて重要な「潜在的」環境において優れた堅牢性を示した。これらのコンテキストをモデル化できない、あるいは堅牢な重み付けを欠くベースラインは、著しく高いリグレットを被った。
  • 適応型重み付けメカニズムは、汚染と遅延の複合的なノイズを効果的に中和し、コンテキストの次元数 ($d$) や腕の数 ($K$) が増加しても安定したパフォーマンスを維持する。
  • 実世界のデータセットを用いた実験により、線形選好の仮定が近似に過ぎない場合でも、アルゴリズムの拡張性と堅牢性が確認された。

5. 意義と主張

本論文は、コンテキスト・デュエリング・バンディットの枠組みにおいて、敵対的汚染、未知のフィードバック遅延、および事後提供コンテキストという課題を同時に扱う最初の研究であると主張している。

• 理論的影響: これらの要因の組み合わせた効果は根本的に相乗的であるが、全情報の幾何学的構造 ($\tilde{V}_t$) に基づく統一的な重み付け戦略によって管理可能であることを確立した。得られた結果は、明示的な検出を必要とせずに、確率的設定と敵対的設定の両方に適応する「ベスト・オブ・ボース・ワールズ (best-of-both-worlds)」の保証を提供している。
• 実用的関連性: 本研究は、大規模言語モデル (LLM) に対する人間からのフィードバックによる強化学習 (RLHF) を含む、現代のインタラクティブなシステムから動機付けられている。これらのシステムでは、ユーザーの選好は相対的（デュエリング）であり、フィードバックは遅延し、データはノイズが多い、あるいは操作される可能性がある。提案されたフレームワークは、事後アクション要因やデータの不規則性を考慮することで、AIシステムを人間の意図に、より信頼性が高く、堅牢かつ正確に適合させるための道筋を提供する。

著者らは、敵対的遅延の下界における $\sqrt{d}$ のギャップが依然として未解決の問題であること、および、遅延を伴う事後提供コンテキストを扱うようにフレームワークを拡張することが今後の研究方向であることを認め、限界事項として挙げている。