の上界を証明します。ここで d_z$ は、最適に近い領域のジーミング次元です。さらに、本アルゴリズムは、総時間ホライズンに関して対数的な空間しか必要とせず、連続アクション空間上でのいかなるバンディット・アルゴリズムによっても達成可能な最良の性質です。
連続アクション空間におけるリプシッツ・デュエリング・バンディット
arXiv cs.LG / 2026/4/2
📰 ニュースSignals & Early TrendsIdeas & Deep AnalysisModels & Research
要点
- 本論文は、リプシッツ構造の下での連続アクション空間における確率的デュエリング・バンディットを扱い、純粋に比較によるフィードバックという前提と組み合わせた研究を取り上げる。これは従来、検討されてこなかった組み合わせである。
- リプシッツ・デュエリング・バンディットに対する初のラウンドベースのアルゴリズムを提案し、探索と、適応的な参照アームによって導かれる領域の再帰的な除外を用いる。
- 著者らは相対（デュエリング）フィードバックに特化した新たな解析手法を開発し、近最適領域のズーミング次元に依存して、
- \(\tilde O\left(T^{\frac{d_z+1}{d_z+2}}\right)\)
- の損失（レグレット）上界を証明する。
- 本手法はさらに、時間の地平線に関して対数的な空間計算量も達成しており、著者らはこれが連続アクション空間におけるバンディットアルゴリズムの中で最適であると主張している。
