半パラメトリック・バンディットにおけるほぼ最適な最良アーム同定
arXiv stat.ML / 2026/4/7
📰 ニュースIdeas & Deep AnalysisModels & Research
要点
- 本論文は、報酬がアームの特徴量に対する線形項に加え、未知の加法的なベースラインシフトを持つ半パラメトリック・バンディットにおける、固定信頼度の最良アーム同定（BAI）を研究し、標準的な線形バンディットのBAIと区別している。
- 推移型（transductive）の場合について、シフト後の特徴量に対して計算される線形バンディットの計算量と一致する、達成可能な事例依存の下限を証明する。
- この半パラメトリック設定において直交化された回帰を可能にする新しい$XY$-designを導入し、計算効率の高いフェーズ除去アルゴリズムを提案する。
- 著者らは、サンプル複雑度に関する、高確率のほぼ最適な上界を導出しており、下限と対数因子まで一致しつつ、さらに加法的に$d^2$項が付加される。
- 合成データとJesterデータセットでの実験により、従来のベースラインよりも明確な改善が報告されている。
