論文の概要: Last-Iterate Convergence Properties of Regret-Matching Algorithms in Games

• arxiv url: http://arxiv.org/abs/2311.00676v2
• Date: Tue, 04 Mar 2025 18:13:47 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-05 19:09:25.132995
• Title: Last-Iterate Convergence Properties of Regret-Matching Algorithms in Games
• Title（参考訳）: ゲームにおけるregret-MatchingアルゴリズムのLast-Iterate Convergence特性
• Authors: Yang Cai, Gabriele Farina, Julien Grand-Clément, Christian Kroer, Chung-Wei Lee, Haipeng Luo, Weiqiang Zheng,
• Abstract要約: 本稿では,Regret$+$ (RM$+$) に基づく2プレーヤゼロサムゲーム解決アルゴリズムの終点収束特性について検討する。 我々の分析は、アルゴリズムの極限点の幾何学的構造を新たに解析し、最終点収束に関する文献の大半から大きく離れていることを示す。
• 参考スコア（独自算出の注目度）: 71.73971094342349
• License:
• Abstract: We study last-iterate convergence properties of algorithms for solving two-player zero-sum games based on Regret Matching$^+$ (RM$^+$). Despite their widespread use for solving real games, virtually nothing is known about their last-iterate convergence. A major obstacle to analyzing RM-type dynamics is that their regret operators lack Lipschitzness and (pseudo)monotonicity. We start by showing numerically that several variants used in practice, such as RM$^+$, predictive RM$^+$ and alternating RM$^+$, all lack last-iterate convergence guarantees even on a simple $3\times 3$ matrix game. We then prove that recent variants of these algorithms based on a smoothing technique, extragradient RM$^{+}$ and smooth Predictive RM$^+$, enjoy asymptotic last-iterate convergence (without a rate), $1/\sqrt{t}$ best-iterate convergence, and when combined with restarting, linear-rate last-iterate convergence. Our analysis builds on a new characterization of the geometric structure of the limit points of our algorithms, marking a significant departure from most of the literature on last-iterate convergence. We believe that our analysis may be of independent interest and offers a fresh perspective for studying last-iterate convergence in algorithms based on non-monotone operators.
• Abstract（参考訳）: 本稿では,Regret Matching$^+$ (RM$^+$) に基づく2プレイヤゼロサムゲームを解くアルゴリズムの終点収束特性について検討する。 現実のゲームを解くのに広く使われているが、最終段階の収束についてはほとんど知られていない。 RM型力学を解析するための大きな障害は、その後悔作用素がリプシッツ性や(擬)単調性を欠いていることである。 まず, RM$^+$, 予測的RM$^+$, 交互RM$^+$などの実戦で使用される変種が, 単純な$3\times 3$行列ゲームにおいても, 最終点収束保証を欠いていることを示す。 次に、これらのアルゴリズムの最近の変種は、滑らかな手法、過度なRM$^{+}$および滑らかな予測的RM$^+$に基づいて、漸近的最終点収束(レートなしで)、1/\sqrt{t}$ベスト点収束(英語版)、そして再帰的線形レート最終点収束(英語版)と組み合わせて証明する。 我々の分析は、アルゴリズムの極限点の幾何学的構造を新たに解析し、最終点収束に関する文献の大半から大きく離れていることを示す。 我々は、我々の分析が独立した関心を持つ可能性があり、非単調作用素に基づくアルゴリズムにおける最終点収束の研究に新たな視点を提供すると考えている。

関連論文リスト

• Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms [71.73971094342349]
  オンライン学習によるセルフプレイは、大規模な2人プレイのゼロサムゲームを解くための重要な方法の1つだ。 我々は,OMWUが支払行列のサイズに対数依存するなど,いくつかの利点があることを示した。 我々は、過去のことをすぐに忘れない幅広い種類のアルゴリズムが、すべて同じ問題に悩まされていることを証明している。
  論文  参考訳（メタデータ） (2024-06-15T13:26:17Z)
• Regret Matching+: (In)Stability and Fast Convergence in Games [68.13214224119024]
  RM+とその予測バージョンは不安定であり,他のプレイヤーが大きな後悔を味わう可能性がある。 これらの修正は、RM+による通常のゲームにおいて、個々の後悔に対して$O(T1/4)$$と$O(1)$の社会的後悔を得るのに十分であることを示す。
  論文  参考訳（メタデータ） (2023-05-24T04:26:21Z)
• Doubly Optimal No-Regret Learning in Monotone Games [10.760195409078591]
  本研究では,スムーズなモノトーンゲームのための2倍最適非線形学習アルゴリズムを提案する。 このアルゴリズムは, 滑らかかつ凸な損失関数の下での対角的条件下での最適$O(sqrtT)$後悔と, (ii) 最適$O(frac1T)$最後の収束率をナッシュ平衡に達成する。
  論文  参考訳（メタデータ） (2023-01-30T17:55:53Z)
• Policy Optimization for Markov Games: Unified Framework and Faster Convergence [81.3266426402464]
  このアルゴリズムのステートワイド平均ポリシはゲームの近似ナッシュ平衡(NE)に収束することを示す。 このアルゴリズムをマルチプレイヤー一般のMarkov Gamesに拡張し、CCE(Correlated Equilibria)への$mathcalwidetildeO(T-1/2)$収束率を示す。
  論文  参考訳（メタデータ） (2022-06-06T14:23:13Z)
• Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Games [104.74734408204749]
  マルチプレイヤーの汎用正規形式ゲームにおいて,OMWU(Optimistic Multiplicative Weights Update)を用いているエージェントが全員,O(textrmpolylog(T))$(T$)$(T$)$(OMWU)$(OMWU)$(OMWU)$(OMWU)$(OMWU)$)であることを示す。 外部の後悔から内部の後悔へと結果を拡張し、後悔を交換することで、近似した平衡に収束する非結合学習ダイナミクスを確立する。
  論文  参考訳（メタデータ） (2021-11-11T01:19:53Z)
• Last-iterate Convergence in Extensive-Form Games [49.31256241275577]
  逐次ゲームにおける楽観的アルゴリズムの最後の点収束について検討する。 これらのアルゴリズムはいずれも最終点収束を楽しみ、そのいくつかは指数関数的に高速に収束する。
  論文  参考訳（メタデータ） (2021-06-27T22:02:26Z)
• Tight last-iterate convergence rates for no-regret learning in multi-player games [31.604950465209335]
  定常的なステップサイズを持つ楽観的勾配(OG)アルゴリズムは,スムーズな単調ゲームにおいて最終定位レートが$O(1/sqrtT)であることを示す。 また、$O (1/sqrtT)$レートは、特別なケースとしてOGを含む全ての$p$-SCLIアルゴリズムに対して厳密であることを示す。
  論文  参考訳（メタデータ） (2020-10-26T17:06:19Z)

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

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