Active Context Selection Improves Simple Regret in Contextual Bandits

技術的サマリー：文脈選択の能動化による文脈付きバンドット問題における単純後悔の改善

問題定式化
本論文は、有限な文脈空間における文脈付き多腕バンディット問題を調査する。ここで、文脈は異なるサブ集団（例：人口統計学的グループ）を表す。学習の目的は、文脈重み付き単純後悔によって定義される。固定された実験予算 $T$ の後、学習者は各サブ集団に対して単一の最良の治療法を推奨しなければならない。性能指標は、$k$ 個のサブ集団にわたる人口分布ベクトル $p$ によって重み付けられた、最適治療法と推奨治療法の間の期待ギャップである。

本研究は、2 つのサンプリング様式を区別する。

1. 受動的サンプリング：文脈は固定分布 $p$ に従ってランダムに現れ、学習者は治療法のみを選択する。
2. 能動的サンプリング：学習者は各ラウンドで、サブ集団（文脈）と治療法の両方を能動的に選択できる。

分析は、報酬分布に関しては最悪ケースを仮定するが、文脈分布 $p$ に関してはインスタンス依存のままとする。本論文は、地平線 $T$ が治療法の数 $n$、文脈の数 $k$、および最小文脈確率の逆数よりも著しく大きい「データ豊富」な領域に焦点を当てる。

手法と理論的枠組み

• 既知の $p$ に対する最適配分：
  サブ集団分布 $p$ が既知の場合、著者は実験予算の最適配分を特徴づける。最悪ケースの単純後悔基準について、履歴非依存方策（文脈選択が $p$ のみに基づき、観測履歴に依存しない方策）がミニマックス率を達成するのに十分であることを証明する。

  • 受動的率：受動的サンプリング下では、後悔は $\Theta(\sqrt{\frac{n}{T}} \|p\|_{1/2})$ としてスケーリングする。
  • 能動的率：能動的サンプリング下では、最適戦略は、サブ集団 $j$ に対して確率 $p_j^{2/3}$ に比例してサンプルを割り当てる。これにより、後悔率は $\Theta(\sqrt{\frac{n}{T}} \|p\|_{2/3})$ となる。
  • ギャップ：能動サンプリングが受動サンプリングに対して達成する改善因子は、比率 $R(p) = \|p\|_{1/2} / \|p\|_{2/3}$ によって特徴づけられる。著者は、高度に非一様な分布において、このギャップは最大で $\Theta(k^{1/4})$ となり得ることを示す。最適な能動配分は、$p$ と比較してより一様な分布へとサンプリング確率をシフトさせ、それにより小さなサブ集団における探索を増加させる。

• 予算制約付き介入：
  本論文は、能動的サンプリングにコストがかかる設定への分析を拡張し、学習者が $1-\alpha$ 分のラウンドでのみサブ集団を選択できる場合を扱う。著者は、配分 $q$ が $q_j \geq (1-\alpha)p_j$ を満たすという制約の下で後悔を最小化する制約付き最適化問題を定式化する。最適配分に対する閾値構造を導出する。予算が不十分な場合、$p_j$ が大きいサブ集団は受動的配分のままとなる可能性があるが、他のサブ集団は $p_j^{2/3}$ の割合へと引き上げられる。また、完全な能動的最適率を回復するために必要な最小予算 $\alpha_{\min}(p)$ を特定する。

• 未知の $p$（EETC アルゴリズム）：
  $p$ が未知の場合、完全な能動方策は単純に $p^{2/3}$ ルールを採用することはできない。著者は、3 つのフェーズをバランスさせる**探索 - 探索 - 後コミット（EETC）**アルゴリズムを提案する。

  1. 初期の受動的探索：学習者は $p$ を推定するために受動的に行動する。
  2. 継続的な受動サンプリング：学習者は、残りの予算が現在の推定値に基づいた最適能動配分を実行するのに十分になるまで、受動的サンプリングを継続する。
  3. コミットメント：学習者は、推定された分布を使用して残りのラウンドを割り当てるために、能動的サンプリングに切り替わる。
     理論的分析により、大きな地平線において、EETC は定数因子まで、既知の $p$ を持つ最適完全能動方策と同じ単純後悔率を達成することが示される。

主要な結果と実験

• 理論的保証：本論文は、既知および未知の $p$ に対して、tight な後悔率を確立する。能動的な文脈選択は受動的サンプリングを厳密に改善することを証明し、その改善の大きさは文脈分布の不均一性に依存する。
• 合成データ実験：合成データを用いた実験は、サブ集団の数 $k$ が増加するにつれて、受動方策と能動方策の間の後悔ギャップが拡大することを確認しており、理論的な $\Theta(k^{1/4})$ 境界と一致する。EETC アルゴリズムは、オラクル（既知の $p$）能動方策のパフォーマンスとほぼ一致することが示された。
• 実世界データ（MovieLens）：著者は MovieLens 1M データセット上で手法を評価した。ここでは、映画の推薦を治療法、人口統計学的グループをサブ集団として扱った。結果は、受動的方策が最も高い後悔をもたらすことを示している。既知の $p$ を持つ能動方策と EETC の両方は、受動的ベースラインを大幅に上回り、地平線が増加するにつれて EETC はオラクル能動方策のパフォーマンスに近づく。

意義と主張
本論文は、実験デザインと方策学習において、サブ集団を能動的に選択することの具体的な価値を定量化することを主張する。その主な貢献は、能動的なサブ集団選択は受動的サンプリングよりも常にパフォーマンスを改善することを実証することであり、人口分布が歪んでいる場合、その利益は甚大である。

著者は、標準的な文脈付きバンディット（文脈が環境的なもの）と実験デザイン（実験者がサンプルを制御するもの）の間のギャップを埋めていることを強調する。最適配分則（$q_j \propto p_j^{2/3}$）を特徴づけ、漸近的最適性を犠牲にすることなく未知の分布に適応するアルゴリズム（EETC）を提供することで、本論文は不均質な集団における効率的な資源配分のための厳密な枠組みを提供する。この研究は、ターゲットとした募集や制御されたサンプリングが可能なシナリオにおいて、文脈を選択する能力を無視することは、最適でない治療法の推奨につながることを示唆している。