技術的概要：深層表現と浅い探索を備えた分散考慮型ニューラルデュエリングバンディット

1. 問題定義

本論文は、**文脈型デュエリングバンディット（CDBs）**を取り扱います。これは、学習者が文脈を観測し、2 つの腕（行動）を選択して比較し、数値報酬ではなく二値の選好フィードバック（例：腕 $i$ は腕 $j$ より好まれる）を受け取るフレームワークです。既存の CDB 研究はしばしば線形効用関数を仮定しますが、現実世界のユーザー選好は複雑な非線形相互作用を示すことが多く、線形モデルでは捉えきれません。

最近の研究（Verma ら、2024）はニューラルネットワークを用いて非線形性に対処しようとしましたが、2 つの重要な限界に直面しました：

1. 計算的非効率性： 彼らのアプローチは、すべての学習可能パラメータからの勾配を用いてグラム行列を構築する必要があり、大きな計算オーバーヘッド（パラメータ総数 $p$ に対して $O(p^3)$）をもたらしました。
2. 理論的制約： デュエリング設定におけるパラメータベクトル $\hat{\theta}_{t-1}$ の閉形式推定量の欠如により、先行研究は部分線形後悔を保証するために極めて大きなニューラルネットワークの幅（$m = \tilde{\Omega}(T^{14})$）を仮定せざるを得ませんでした。この要件は、標準的なニューラルバンディット文献の結果と矛盾します。

さらに、既存の手法は大半が**分散考慮（variance-awareness）**を無視しています。デュエリングバンディットにおいて、フィードバックノイズ（ベルヌーイ分散）は、腕間の効用差がゼロに近いとき（最も困難な比較）に最大化されます。この分散を無視すると、観測値の重み付けが最適でなくなります。

2. 手法：NVLDB

著者は、深層表現学習と浅い探索、および分散考慮型重み付けを統合したフレームワークである**分散考慮型ニューラル線形デュエリングバンディット（NVLDB）**を提案します。

2.1 浅い探索を伴う深層表現

ニューラルネットワークの完全な勾配を使用する代わりに、NVLDB は浅い探索戦略を採用します。これは、深層ニューラルネットワーク $f(x; \theta, W)$ を用いて非線形効用関数 $u(x)$ を近似しますが、グラム行列 $V_t$ を**最終層のパラメータ（$\theta$）**の勾配のみを用いて構築します。

• 効率性： これにより、グラム行列の逆行列計算の複雑さが $\tilde{O}(p^3)$ から $\tilde{O}(d^3)$ に削減され（ここで $d$ は文脈の次元）、大幅な高速化が実現されます。
• バイアスの処理： 隠れ層を固定された特徴抽出器として扱うことは、表現バイアスを導入します。著者は、理論的分析において補助的なバイアス項を通じてこれを考慮しています。

2.2 分散考慮型重み付け

アルゴリズムは、基礎となるベルヌーイ選好分布の分散 $\hat{\sigma}^2_t = g(\Delta f_t)(1 - g(\Delta f_t))$ を推定します。ここで $g$ はリンク関数（例：Bradley-Terry-Luce）です。

• 損失関数は、観測値を $1/\zeta_i^2$ で重み付けした重み付き負対数尤度です。
• 分散考慮型バリアントでは $\zeta_i = \max\{\hat{\sigma}_i, \epsilon\}$ となり、分散非考慮型バリアントでは $\zeta_i = 1$ です。
• この重み付けは情報フィルタとして機能し、効用マージンが小さい（分散が高い）ペアからの不確実な観測値の重みを下げることで、より tight な後悔 bound を達成します。

2.3 腕選択戦略

NVLDB は、3 つの異なる選択戦略を備えた**Upper Confidence Bound（UCB）およびThompson Sampling（TS）**の両方のフレームワークをサポートします：

1. 非対称（ASYM）： 最初の腕を貪欲に選択し、2 番目の腕を楽観的に選択します。
2. 楽観的対称（OSYM）： 推定効用の合計に探索ボーナスを加えたものを最大化する腕のペアを選択します。
3. 候補ベースの対称（CSYM）： 強力な候補の信頼集合を構築し、最大の探索ボーナスを持つペアを選択します。

• 新規性： 対称 TS 戦略（TS-OSYM、TS-CSYM）は、先行研究とは異なり、両方の腕を逐次的ではなく、同時に関係事後分布からサンプリングする点で異なります。

3. 主要な理論的貢献

本論文の主要な理論的ブレイクスルーは、デュエリングバンディットにおける閉形式推定量の欠如を克服し、必要なネットワーク幅を削減したことです。

3.1 新規分析アプローチ

著者は、スペクトル分析（Courant-Fischer Minimax 定理を使用）を組み合わせたブートストラップ論法を導入します。

• 反復的自己改善： まず、パラメータノルム $\|\theta_{t-1}\|_2$ に対する緩い時間依存 bound を確立します。これを分析に代入することで、より鋭く時間非依存の bound を導出します。
• スペクトル摂動： 現在の特性のグラム行列を摂動されたグラム行列に関連付け、特徴のドリフトを乗法的因子として吸収します。
• 結果： このアプローチにより、閉形式解がなくても推定量ノルムが時間非依存の定数によって有界であることを証明します。

3.2 後悔 Bound

標準的な仮定（有界な文脈、リプシッツ連続なリンク関数、ニューラルタンジェントカーネルの正の最小スペクトル）の下で、著者は部分線形累積平均後悔を証明します：

• 分散考慮型： $\tilde{O}\left(\sqrt{dT} + d\sqrt{\sum_{t=1}^T \sigma_t^2}\right)$。
• 分散非考慮型： $\tilde{O}(d\sqrt{T})$。
• ネットワーク幅の要件： この分析により、必要なネットワーク幅が $m = \tilde{\Omega}(T^6)$ に削減されました。これは Verma ら（2024）が要求した $m = \tilde{\Omega}(T^{14})$ からの大幅な改善です。この要件は標準的なニューラルバンディットの結果（$\tilde{\Omega}(T^3)$）に近づきましたが、デュエリング設定固有の課題により、依然としてギャップが存在します。

4. 実験結果

著者は、合成データセットおよび実世界データセット上で NVLDB を検証しました。

• 合成タスク： 非線形効用関数（コサイン、平方、行列）を使用し、NVLDB のバリアントは、累積平均後悔においてベースライン（線形デュエリングバンディット VACDB/ColSTIM およびニューラルデュエリングバンディット NDB）を一貫して上回りました。
• 実世界データセット： UCI データセット（Statlog、Magic、Covertype）での実験は、部分線形後悔と優れた性能を確認しました。特に、決定論的選好モデル（低分散）を用いた Statlog データセットでは、分散考慮型バリアントがほぼゼロの後悔を達成し、分散非考慮型の対照群を大幅に上回りました。
• スケーラビリティ： 本手法は、より高い次元（$d=100$）およびより広いネットワーク（$m=1000$）でも部分線形後悔を維持しました。
• 効率性： NVLDB は完全勾配法（NDB）に対して大幅な高速化を示し、同一ハードウェア上で 2,000 ラウンドを約 1.7 分で完了しました（NDB は約 48.8 分）。

5. 意義と主張

本論文は、浅い探索戦略を利用する分散考慮型ニューラルデュエリングバンディットを初めて導入したと主張しています。その意義は以下の点にあります：

1. 理論的進展： ブートストラップ論法とスペクトル分析の新奇な組み合わせを通じて、ネットワーク幅の条件（$T^6$ 対 $T^{14}$）を大幅に緩和した条件下で部分線形後悔を証明することで、ニューラルデュエリングバンディットの理論的分析における重要なボトルネックを解消しました。
2. 実用的効率性： 浅い探索を活用することで、ニューラルデュエリングバンディットを大規模アプリケーションに対して計算的に実行可能にし、グラム行列の逆行列計算コストを桁違いに削減しました。
3. 分散考慮： 分散推定（逆分散重み付け）を統合することが、tight な後悔 bound と、特に低分散領域における優れた実証的パフォーマンスにつながることを実証しました。

著者は、$m = \tilde{\Omega}(T^6)$ が重要な改善である一方で、標準的なニューラル CMAB における $\tilde{\Omega}(T^3)$ の要件とのギャップを埋めることは、主にデュエリング設定における閉形式推定量の固有の難しさにより、今後の研究の方向性であると認めています。