技術的概要：共変量を伴うバッチ化単一インデックス型グローバル多腕バンディット

1. 問題定式化

本論文は、バッチ化された設定における**共変量を伴うグローバル多腕バンディット（GMABC）**問題を取り扱います。この枠組みは、臨床試験やパーソナライズされた推薦などの実世界応用において頻繁に見られる 2 つの重要な制約を組み込むことで、標準的なコンテキストバンディットを拡張しています：

1. 共有情報（グローバル構造）：腕は独立しておらず、報酬関数を結びつけるグローバルなパラメータを共有しています。ある腕をプレイすることは、特に共変量が類似している場合、他の腕に関する情報も提供します。
2. バッチ化フィードバック：意思決定は逐次的ではなく、バッチ単位で行われます。方策の更新は、各バッチ内のすべての報酬を観測した後、事前に定められたバッチ境界でのみ可能です。
3. 未知の報酬関数：報酬関数が既知であると仮定する標準的なグローバル MAB モデルとは異なり、この研究では共変量と報酬の間のリンクが未知であり、かつ非線形である可能性を仮定しています。

時間 $t$ における共変量 $X_t$ を伴う腕 $k$ の報酬は、以下のようにモデル化されます：
$$Y_t^{(k)} = g^{(k)}(X_t) + \epsilon_t = f^{(k)}(X_t^\top \beta_0) + \epsilon_t$$
ここで、$f^{(k)}$ は各腕に固有の未知の 1 次元リンク関数であり、$\beta_0 \in \mathbb{R}^d$ はすべての腕にわたる**共有された未知のインデックスパラメータ（方向）**です。目的は、最適期待報酬と方策によって得られた報酬の差として定義される累積後悔 $R_T(\pi)$ を最小化することです。

2. 手法：BIDS アルゴリズム

著者は、共有された単一インデックス構造を活用しつつバッチ制約に対処するために設計された半パラメトリックアルゴリズムであるBIDS（Batched single-Index Dynamic binning and Successive arm elimination：バッチ化単一インデックス型動的ビン分割と逐次腕除去）を提案します。

中核メカニズム

BIDS は、完全な非パラメトリックバンディット向けに開発された**適応的ビン分割と逐次除去（ABSE）**戦略を適応させますが、$d$ 次元の共変量空間全体ではなく、射影空間で動作するように修正しています。

1. 次元削減：BIDS は、完全な共変量空間 $\mathbb{R}^d$ を分割するのではなく、推定されたインデックスベクトル $\hat{\beta}$ によって定義される 1 次元軸 onto 共変量を射影します。これにより次元の呪いが緩和されます。
2. 階層的分割：アルゴリズムは、射影された値 $X_t^\top \hat{\beta}$ に基づいて分割のツリーを構築します。
   • 動的ビン分割：ビンは適応的に分割されます。あるビンに複数のアクティブな腕が含まれており、最良の腕を区別するのに十分なデータがない場合、そのビンは次のバッチで子ビンに分割されます。
   • 逐次除去：各ビン内において、そのビンの現在の最良の腕と比較して、統計的に有意に低い経験平均報酬を持つ腕は、ビンの幅とバッチサイズに依存する信頼閾値に基づいて除去されます。
3. 2 つのシナリオ：
   • パイロット方向がある場合：ある程度正確なパイロット推定値 $\beta$ が利用可能な場合（例：先行研究から）、BIDS はビン分割を導くためにそれを直接使用します。
   • パイロット方向がない場合：パイロットが利用できない場合、最初のバッチは初期化フェーズとして使用されます。すべての腕から周期的にサンプルを収集し、単一インデックス回帰（SIR）手法（例：スライス平均微分推定 - SADE）を用いて $\beta_0$ を推定します。推定された方向は、残りの $M-1$ バッチで使用されます。

3. 主要な貢献

本論文は、以下の 4 つの主要な貢献を行います：

1. GMABC 枠組み：共有された単一インデックスパラメータを介してリンクされた、未知の共変量依存報酬関数を許可することで、グローバル MAB を一般化する新しい半パラメトリック枠組みの導入。
2. BIDS アルゴリズム：単一インデックス構造を用いた十分次元削減パラダイム下での、コンテキスト付きバッチバンディットに対する最初の体系的なアルゴリズムの提案。
3. 後悔保証：
   • 下限：バッチ数 $M$、腕数 $K$、およびマージンパラメータ $\alpha$ を含む根本的な難易度を定量化する、バッチ化半パラメトリック GMABC 問題のミニマックス下限の導出。
   • 上限：
     • パイロットあり：パイロット方向が十分な精度（$\rho_{pilot} \approx O((T/K)^{-1/3})$）で利用可能な場合、アルゴリズムは $O((K \log T)^{1-\beta_M} T^{\beta_M})$ の後悔限界を達成します（$K$ が固定の場合、これは $d=1$ の非パラメトリックバンディットに対するミニマックス率と一致します）。
     • パイロットなし：インデックスを推定する必要がある場合、後悔には初期化フェーズからの追加項 $O(K^{1/3} T^{2/3})$ が含まれますが、依然として部分線形後悔を達成します。
4. 実用的な洞察：インデックス方向の推定誤差と学習率の間のトレードオフ、およびバッチ制約と共変量の次元性の役割に関する分析。

4. 結果

理論的結果

• ミニマックス最適性：腕数 $K$ が固定され、パイロット方向が十分に正確である場合、BIDS は実効次元 $d=1$ を持つ非パラメトリックバッチバンディットに対するミニマックス最適率を達成し、高次元共変量に関連する次元の呪いを効果的に回避します。
• $K$ への依存性：上限は多項式的な $K$ 依存性（$K^{1-\beta_M}$）を示し、これは多パラメータバンディットモデルに典型的ですが、下限は対数的な依存性を示します。このギャップは、ビン内ですべての腕を比較するために十分なサンプルを収集する必要性に起因します。
• マージン条件：性能はマージンパラメータ $\alpha$ に依存します。$\alpha$ が小さい場合（腕の区別が困難）、後悔率は遅くなります。

実証的結果

実験は、シミュレーションデータと 3 つの実世界データセット（米の分類、占有検出、EEG 眼の状態）で行われました。

• 比較：BIDS は、すべての設定において非パラメトリックバッチバンディットのベースライン（BaSEDB）を一貫して上回りました。
• パイロットの精度：BIDS はパイロット方向の中程度の摂動に対して頑健でしたが、パイロットと真の方向の間の角度が増加するにつれて性能は低下しました。
• ノイズ感度：パイロットがない場合、BIDS は変動するノイズレベル下でも BaSEDB よりも良好に動作しましたが、ノイズが増加すると（初期 SIR 推定の精度が低下するため）その差は縮まりました。
• 解釈可能性：推定されたインデックスベクトル $\hat{\beta}$ はドメイン知識と一致しており（例、占有検出における温度と湿度を主要な特徴として特定）、ブラックボックスの非パラメトリック手法に対する半パラメトリックアプローチの解釈可能性の優位性を示しています。

5. 意義と主張

本論文は、単一インデックスモデル構造を用いた十分次元削減パラダイム下でのコンテキストバンディットに関する最初の体系的な研究であると主張しています。

• 柔軟性と解釈可能性の架け橋：この研究は、解釈可能だが硬直的な完全パラメトリックモデルと、柔軟だが次元の呪いと解釈可能性の欠如に悩まされる完全非パラメトリックモデルの間のギャップを埋めます。単一インデックス構造を仮定することで、著者らは複雑な非線形報酬関数をモデル化する柔軟性を維持しつつ、実効次元を 1 に削減しています。
• 計算効率：この手法は、ビンの数が共変量次元 $d$ に対して指数関数的に増加しないため、非パラメトリックな対応物に比べて計算上の大きな利点を提供します。
• 実世界への適用性：この枠組みは、データがバッチ単位で収集され、治療が化学組成を共有し（グローバル構造）、患者のプロファイル（共変量）が非線形に影響を与える臨床試験などのシナリオによって特に動機付けられています。

著者は、現在のアルゴリズムがチューニングのためにマージンパラメータ $\alpha$ の事前知識を必要とし、上限における $K$ の多項式的依存性が潜在的に改善可能であることを認め、限界を認めています。将来の研究としては、バッチ間でのインデックス方向の適応的推定や、パイロット方向を推定するための転移学習の活用が提案されています。