論文の概要: Optimal last-iterate convergence in matrix games with bandit feedback using the log-barrier

• arxiv url: http://arxiv.org/abs/2604.15242v1
• Date: Thu, 16 Apr 2026 17:17:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-17 21:29:32.022901
• Title: Optimal last-iterate convergence in matrix games with bandit feedback using the log-barrier
• Title（参考訳）: 対数バリアを用いた帯域フィードバックをもつ行列ゲームにおける最適最終点収束
• Authors: Come Fiegel, Pierre Menard, Tadashi Kozuno, Michal Valko, Vianney Perchet,
• Abstract要約: ゼロサム行列ゲームにおけるミニマックスポリシーの学習問題について検討する。 対数バリア正則化(log-barrier regularization)を用いることで,この O-tilde(t-1/4) 収束を高い確率で実現可能であることを示す。
• 参考スコア（独自算出の注目度）: 39.87105929061084
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of learning minimax policies in zero-sum matrix games. Fiegel et al. (2025) recently showed that achieving last-iterate convergence in this setting is harder when the players are uncoupled, by proving a lower bound on the exploitability gap of Omega(t^{-1/4}). Some online mirror descent algorithms were proposed in the literature for this problem, but none have truly attained this rate yet. We show that the use of a log-barrier regularization, along with a dual-focused analysis, allows this O-tilde(t^{-1/4}) convergence with high-probability. We additionally extend our idea to the setting of extensive-form games, proving a bound with the same rate.
• Abstract（参考訳）: ゼロサム行列ゲームにおけるミニマックスポリシーの学習問題について検討する。 Fiegel et al (2025) は、最近、Omega (t^{-1/4}) のエクスプロイラビリティギャップの低い境界を証明し、プレイヤーがアンカップリングされた場合、この設定で最終点収束を達成することが困難であることを示した。 この問題に関して、いくつかのオンラインミラー降下アルゴリズムが文献で提案されたが、実際にこの速度に達したものはまだない。 対数バリア正規化(log-barrier regularization)の使用は、双対的な解析とともに、高い確率でこの O-tilde(t^{-1/4}) 収束を可能にすることを示す。 さらに、我々のアイデアを広義のゲームの設定に拡張し、同じレートで境界を証明します。

関連論文リスト

• From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applications [54.49053278073321]
  大規模なゲームでは、非結合学習ダイナミクスの平均的な繰り返しを新しい非結合学習ダイナミクスの最後の繰り返しに変換する単純なブラックボックス還元が存在することを示す。 我々の削減は、各プレイヤーの効用が自身の戦略と全ての対戦者の共同戦略の両方において線形であるゲームに適用される。
  論文  参考訳（メタデータ） (2025-06-04T00:24:14Z)
• On Separation Between Best-Iterate, Random-Iterate, and Last-Iterate Convergence of Learning in Games [71.73971094342349]
  ゲームにおける学習力学の非エルゴード収束は、理論と実践の両方において重要であるため、広く研究されている。 近年の研究では、最適乗算重み更新を含む学習力学の幅広いクラスが、任意に遅い最終項目収束を示すことが示されている。 OMWUは、同じクラスのゲームにおいて、その遅い最終点収束とは対照的に、$O(T-1/6)$est-iterate convergence rateを達成することを示す。
  論文  参考訳（メタデータ） (2025-03-04T17:49:24Z)
• Is Thompson Sampling Susceptible to Algorithmic Collusion? [7.398059199829556]
  プレイヤーがトンプソンサンプリングを使用すると、ゲームダイナミクスはナッシュ平衡に収束することを示す。 プレイヤーが意図的に競争戦略を展開していないにもかかわらず、このケースではアルゴリズムによる共謀は発生しないことを示す。
  論文  参考訳（メタデータ） (2024-05-23T08:21:48Z)
• Last-Iterate Convergence Properties of Regret-Matching Algorithms in Games [71.73971094342349]
  本稿では,Regret$+$ (RM$+$) に基づく2プレーヤゼロサムゲーム解決アルゴリズムの終点収束特性について検討する。 我々の分析は、アルゴリズムの極限点の幾何学的構造を新たに解析し、最終点収束に関する文献の大半から大きく離れていることを示す。
  論文  参考訳（メタデータ） (2023-11-01T17:34:58Z)
• Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedback [49.1061436241109]
  非漸近収束率の非結合、収束、合理的なアルゴリズムの開発に注力する。 我々のアルゴリズムは[Chen et al., 2021, Cen et al., 2021]と関係があり、エントロピー正規化技術に基づいている。
  論文  参考訳（メタデータ） (2023-03-05T18:08:54Z)
• No-regret learning for repeated non-cooperative games with lossy bandits [5.437709019435926]
  本研究では,長期的後悔の損失を最小限に抑えるために,プレイヤーの非同期オンライン学習戦略について検討する。 この論文は、損失帯域付きオンライングラディエントDescent(OGD-lb)と呼ばれる、新しい非回帰学習アルゴリズムを提供する。
  論文  参考訳（メタデータ） (2022-05-14T05:02:56Z)
• Last-iterate Convergence in Extensive-Form Games [49.31256241275577]
  逐次ゲームにおける楽観的アルゴリズムの最後の点収束について検討する。 これらのアルゴリズムはいずれも最終点収束を楽しみ、そのいくつかは指数関数的に高速に収束する。
  論文  参考訳（メタデータ） (2021-06-27T22:02:26Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。