ログバリアを用いたバンディットフィードバック下の行列ゲームにおける最適な最終反復収束
arXiv cs.LG / 2026/4/17
📰 ニュースDeveloper Stack & InfrastructureModels & Research
要点
- この論文は、ゼロ和の行列ゲームでミニマックス方策を学習する問題を扱い、最終反復（last-iterate）収束の達成に焦点を当てています。
- 先行研究（Fiegelら、2025年）は、プレイヤーが非連成（uncoupled）の場合、最終反復収束が本質的に難しく、搾取可能性ギャップに対してΩ(t^{-1/4})の下限が成り立つことを示しました。
- 著者らは、ログバリア正則化とデュアル中心の解析を組み合わせたオンラインミラー降下を提案し、高確率でO~(t^{-1/4})（対数因子を除く）の収束率を証明しています。
- さらに、この考え方を広範形ゲーム（extensive-form games）へ拡張し、同様のO~(t^{-1/4})の最終反復収束の評価を得ています。
