COMPASS-Hedge：世界を知らずに安全に学習する
arXiv cs.LG / 2026/3/25
💬 オピニオンIdeas & Deep AnalysisModels & Research
要点
- 本論文では、敵対的レグレット（adversarial regret）、確率的効率（stochastic efficiency）、および固定された比較対象（コンパレータ）に対するベースラインの安全性に関する一般的な「トリレンマ」を解決するための、新しいフルインフォメーション型のオンライン学習アルゴリズムである COMPASS-Hedge を提案する。
- COMPASS-Hedge は、敵対的状況ではミニマックス最適なレグレットを達成し、確率的状況では（インスタンス／ギャップに依存する）instance-optimal なレグレットを達成し、指定されたベースライン方策に対しては o(1)（対数因子で調整された）のみのレグレットで済むと主張している。
- 本手法はパラメータ不要であり、環境が敵対的か確率的かを事前に知る必要がなく、また問題依存のギャップの大きさに関する知識も不要である。
- アルゴリズムの設計は、適応的な疑似レグレットのスケーリングと、位相（フェーズ）に基づく「攻勢（aggression）」を組み合わせ、さらに比較対象（コンパレータ）を意識した混合戦略を用いることで、3つの性能保証を統一する。
