文脈バンディットにおけるベストインクラスの高速な後悔（regret）

arXiv stat.ML / 2026/4/6

💬 オピニオンIdeas & Deep AnalysisModels & Research

共有:

要点

本論文は、確率的文脈バンディットの「エイゴスティック（非実現可能）」設定において、損失・報酬に制約を課さずに、クラス内の最良方策（best-in-class）に対する後悔（regret）を達成する問題を扱っています。
すべてのラウンドで悲観的（pessimistic）目的関数を最小化して方策を更新し、その目的は、クリップ付き逆確率重み付け（clipped inverse-propensity estimate）による方策価値に分散ペナルティを加えた形になっています。
方策クラスに対するエントロピー仮定と、マージン条件の一般化であるHölder型の誤差境界条件を用いることで、best-in-classに対する「最初の高速率（first fast rate）」の後悔保証を示しています。
分析では、適応的なデータ収集下でも悲観性を保証するために、bounded martingale empirical processesに対する逐次自己正規化の最大不等式を用いて、一様に分散適応的な信頼区間を構築しています。

Abstract

本研究では、非実現可能性を仮定せず、損失や報酬に対するモデル制約も課さない、いわゆるアグノスティック設定における確率的文脈付きバンディットの問題を扱います。この仕事では、クラス内で最良の方策に対する後悔（regret）について、最初の高速率を確立します。提案手法は、方策価値のクリップされた逆確率推定値に分散ペナルティを加えたものとして定義される、悲観的（pessimistic）目的関数を最小化することで、各ラウンドごとに方策を更新します。方策クラスに関するエントロピー仮定と、ヘルダー的な誤差上界条件（マージン条件の一般化）を活用することで、最良クラス内後悔の高速な率を達成し、パラメトリックの場合には多項対数的（polylogarithmic）な率も含みます。解析は、有界マルチンゲール経験過程に対する逐次の自己正規化された最大不等式により推進されます。これにより、分散に適応した一様な信頼区間（confidence bounds）が得られ、適応的なデータ収集のもとで悲観性（pessimism）が保証されます。