要旨: 本稿では、制約なしバンディット線形最適化（uBLO）の文脈において、Abernethy ら（2008）の標準的な摂動（摂動に基づく）アプローチを改めて見直す。制約なしの設定では、このアプローチはバンディット線形最適化（BLO）を標準的なオンライン線形最適化（OLO）問題へ実効的に還元することを示す、驚くべき結果が得られる。我々の枠組みは、いくつかの点で先行研究を改善する。まず、摂動方式を比較対象（コンパレーター）に適応した OLO アルゴリズムと組み合わせたときに成り立つ期待劣後（expected-regret）の保証を導出し、異なる敵対的モデルが生じる比較対象適応率に与える影響について新たな洞察を得る。さらに分析を動的劣後（dynamic regret）へ拡張し、事前に P_T を知ることなく、最適な sqrt{P_T} の経路長（path-length）依存性を得る。次に、uBLO において静的劣後と動的劣後の両方について、初めての高確率保証を構築する。最後に、静的劣後に関する下界を議論し、独立した関心がある結果として、単位ユークリッド球上の敵対的線形バンディットに対する、いわゆる素朴な（folklore） Omega(sqrt{dT}) のレートを証明する。
制約なし線形バンディットに対する摂動（perturbation）アプローチ
arXiv stat.ML / 2026/3/31
💬 オピニオンSignals & Early TrendsIdeas & Deep AnalysisModels & Research
要点
- 論文は、Abernethyらの摂動（perturbation）手法を「制約なし」線形バンディット最適化（uBLO）に再適用し、驚くべきことにuBLOを標準的なオンライン線形最適化（OLO）へ実質的に還元できることを示します。
- 摂動を比較器（comparator）に適応するOLOアルゴリズムと組み合わせた際、期待レグレットに対する保証を導き、敵対的モデルの違いがコンパレータ適応率へ与える影響を新たに分析します。
- 動的レグレットについても、区間内の移動量（path-length）P_Tの依存が最適な√P_Tとなり、かつP_Tの事前知識なしでこれを達成できる形で解析を拡張します。
- さらに、静的・動的レグレットの双方に関する初の高確率保証、ならびに下界（静的レグレットの下界や、単位ユークリッド球上の敵対的線形バンディットでのΩ(√(dT))）を提示し、理論的に重要な独立結果も含めています。
