文脈付き組合せセミバンディットに対する、ベスト・オブ・ボスワールズ型の効率的アルゴリズム

arXiv stat.ML / 2026/3/27

💬 オピニオンSignals & Early TrendsIdeas & Deep AnalysisModels & Research

共有:

要点

本論文は、文脈付き組合せセミバンディットに対する初の「ベスト・オブ・ボスワールズ（両方の長所）」アルゴリズムを提案し、敵対的設定ではほぼ最適なo(√T) の後悔（regret）を達成しつつ、破損（corrupted）された確率的設定では同時にほぼ対数的な o(log T) の後悔を実現する。
Shannon エントロピー正則化子を用いる Follow-the-Regularized-Leader（FTRL）フレームワークに基づき、効率的なアルゴリズム構造を備えた柔軟なアプローチを構築する。
主要な貢献は、FTRL/オンライン確率的ミラー降下における計算上のボトルネック、すなわち各ラウンドの高次元射影ステップを、Karush-Kuhn-Tucker（KKT）条件によって言い換える点にある。
射影を単一変数のルート探索問題へと還元し、各ラウンドの計算を大幅に高速化する。
実験により、本手法が所望の後悔保証を維持しながら、実時間・大規模環境での顕著な速度向上を実現することが示され、実運用への適用可能性が裏付けられる。

Abstract

我々は、文脈付き組合せ型セミバンディットに対する、初めての「両世界のベスト（best-of-both-worlds）」アルゴリズムを提案します。このアルゴリズムは、敵対的な状況では

ilde{ mathcal{O}}( sqrt{T})

の劣化（regret）を同時に保証し、さらに破損（corrupted）された確率的状況では

ilde{ mathcal{O}}( ln T)

の劣化を保証します。提案手法は、シャノンエントロピー正則化子を備えた Follow-the-Regularized-Leader（FTRL）フレームワークに基づいており、効率的な実装を可能にする柔軟な方法を提供します。劣化境界にとどまらず、FTRL（同値に、Online Stochastic Mirror Descent）における実際上のボトルネック、すなわち各インタラクション（相互作用）ラウンドで遭遇する高次元の射影ステップに取り組みます。Karush-Kuhn-Tucker 条件を活用することで、

K

次元の凸射影問題を単一変数のルート探索問題へと変換し、各ラウンドを劇的に高速化します。実験的評価により、この組み合わせ戦略が両世界のベストのアルゴリズムに見られる魅力的な劣化境界を達成するだけでなく、1ラウンドあたりの大幅な速度向上も実現し、大規模でリアルタイムなアプリケーションに適していることが示されます。