The Role of Contextual Information in Best Arm Identification

最適腕識別では、複数の選択肢のうち平均報酬が最大のものを、できるだけ少ない試行で見つけます。この研究は、各回に共変量が観測できる場合を扱い、共変量で周辺化した平均報酬が最大の腕を特定する問題について、必要な標本数の下界と、その下界に漸近的に届くアルゴリズムを与えました。

研究が扱う問題

関心があるのは、共変量ごとの条件付き平均報酬ではなく、共変量の分布で周辺化した平均報酬です。因果推論でいえば、個人ごとの効果ではなく平均処置効果を見る立場に当たります。共変量を使わない最適腕識別については、問題例ごとの標本複雑度の下界と、それに漸近的に一致するアルゴリズムが知られていました。一方、共変量が使える場合に下界がどう変わるのかは分かっていませんでした。

提案した方法

共変量が連続の場合と有限個の場合の双方について、問題例ごとの標本複雑度の下界を導きました。下界を達成するには腕をどの割合で引くべきかが決まるので、その最適な配分を追跡するように腕を選ぶ Track-and-Stop の共変量つき版を構成します。停止規則と判定規則も合わせて設計し、指定した誤り確率を満たすことを示しました。

主な結果と成立条件

導いた下界は、共変量を使わない場合の Garivier と Kaufmann（2016年）の下界より小さくなります。つまり共変量を使えば識別を速められる余地があり、提案アルゴリズムの標本複雑度の上界は漸近的にこの下界と一致します。結果を示した設定は二つで、報酬と共変量が多変量正規分布に従う2腕のガウスバンディットと、報酬分布が1母数指数型分布族に属し共変量が有限個の場合です。数値実験でも、共変量を使うほうが速く最適腕にたどり着くことを確認しました。

先行研究との関係

共変量を使わない最適腕識別では、Kaufmann、Cappé、Garivier が問題例ごとの標本複雑度の下界を与え（2016年、On the Complexity of Best-Arm Identification in Multi-Armed Bandit Models）、Garivier と Kaufmann が下界に漸近的に一致する Track-and-Stop を提案しました（2016年、Optimal Best Arm Identification with Fixed Confidence）。Degenne、Koolen、Ménard は、この最適配分を求める問題をゲームとして解く方法を示しています（2019年、Non-Asymptotic Pure Exploration by Solving Games）。共変量を使って周辺化した量を効率よく推定するという発想は、Hahn、Hirano、Karlan の適応的実験計画に近く（2011年、Adaptive Experimental Design Using the Propensity Score）、そこでも共変量に応じて処置を割り当てると推定量の分散が下がることが示されています。この研究は、推定の効率化として論じられてきたこの効果を、最適腕識別の標本複雑度の言葉で定量化したものです。

利用できる状況

複数の案を比べて最良のものを早く決めたい実験を想定しています。利用者の属性や時間帯のような情報が取れるなら、それを割り当てに使うことで、同じ確信度に到達するまでの試行回数を減らせます。適応的実験計画のページで扱う設計とは、効果を精度よく推定したいのか、最良の案を選びたいのかという目的の違いで対をなします。

論文と資料

• 論文（JMLR）
• プレプリント（arXiv）
• 論文一覧の項目

BibTeX

@article{role-of-contextual-information-bai,
  author       = {Masahiro Kato and Kaito Ariu},
  title        = {The Role of Contextual Information in Best Arm Identification},
  journal      = {Journal of Machine Learning Research},
  volume       = {27},
  number       = {51},
  pages        = {1--61},
  year         = {2026},
  url          = {https://jmlr.org/papers/v27/22-0358.html},
}

関連する研究テーマ

• 最適腕識別
• 適応的実験計画