難しい道：バンディットフィードバックを伴うゼロサムゲームにおける、結合しない学習のラスト・イテレート収束
arXiv cs.LG / 2026/4/20
📰 ニュースIdeas & Deep AnalysisModels & Research
要点
- 本論文は、ゼロサム行列ゲームを反復しつつバンディット（部分）フィードバックの下で学習する問題を扱い、プレイヤー間で通信を行わない「結合しない（uncoupled）」アルゴリズムによるラスト・イテレート収束を目指しています。
- 著者らは否定的結果を示します。すなわち、各プレイヤーの方策プロファイルをナッシュ均衡へ収束させるよう保証することは、平均イテレートの収束に比べて性能面で不利である、という点です。
- 結合しない手法におけるラスト・イテレートのエクスプロイタビリティギャップの最良到達率は Ω(T^-1/4) であり、通常の平均イテレート収束の Ω(T^-1/2) より遅くなることを明らかにしています。
- さらに、探索と活用の単純なトレードオフに基づく手法と、二段のミラー降下に基づく正則化を用いる手法の2つのアルゴリズムを提案し、定数および対数因子を除けば最適な Ω(T^-1/4) の率を達成するとしています。
