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

• arxiv url: http://arxiv.org/abs/2311.00676v1
• Date: Wed, 1 Nov 2023 17:34:58 GMT
• ステータス: 処理完了
• システム内更新日: 2023-11-02 12:55:43.550509
• Title: Last-Iterate Convergence Properties of Regret-Matching Algorithms in Games
• Title（参考訳）: ゲームにおける後悔マッチングアルゴリズムのラストイテレート収束特性
• Authors: Yang Cai, Gabriele Farina, Julien Grand-Cl\'ement, Christian Kroer, Chung-Wei Lee, Haipeng Luo, Weiqiang Zheng
• Abstract要約: RM$+$ の様々な一般的な変種の最後の点収束特性について検討する。 本稿では, RM$+$の同時適用, RM$+$の交互化, RM$+$の予測, 最終項目収束保証の欠如など, 実用的バリエーションのいくつかを数値的に示す。 そして、スムーズな手法に基づく最近のアルゴリズムの変種は、最終点収束を楽しむことを証明した。
• 参考スコア（独自算出の注目度）: 72.43065138581589
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Algorithms based on regret matching, specifically regret matching$^+$ (RM$^+$), and its variants are the most popular approaches for solving large-scale two-player zero-sum games in practice. Unlike algorithms such as optimistic gradient descent ascent, which have strong last-iterate and ergodic convergence properties for zero-sum games, virtually nothing is known about the last-iterate properties of regret-matching algorithms. Given the importance of last-iterate convergence for numerical optimization reasons and relevance as modeling real-word learning in games, in this paper, we study the last-iterate convergence properties of various popular variants of RM$^+$. First, we show numerically that several practical variants such as simultaneous RM$^+$, alternating RM$^+$, and simultaneous predictive RM$^+$, all lack last-iterate convergence guarantees even on a simple $3\times 3$ game. We then prove that recent variants of these algorithms based on a smoothing technique do enjoy last-iterate convergence: we prove that extragradient RM$^{+}$ and smooth Predictive RM$^+$ enjoy asymptotic last-iterate convergence (without a rate) and $1/\sqrt{t}$ best-iterate convergence. Finally, we introduce restarted variants of these algorithms, and show that they enjoy linear-rate last-iterate convergence.
• Abstract（参考訳）: 後悔のマッチングに基づくアルゴリズム、特に後悔のマッチする$^+$(rm$^+$)とその変種は、実際に大規模2人プレイのゼロサムゲームを解くための最も一般的なアプローチである。 ゼロサムゲームで強いラストイテレートとエルゴード収束特性を持つ楽観的勾配降下上昇のようなアルゴリズムとは異なり、後悔マッチングアルゴリズムのラストイテレート特性についてはほとんど知られていない。 本稿では,ゲームにおける実単語学習のモデル化における最終項目収束の重要性を考慮し,RM$^+$の様々な人気変種の最終項目収束特性について検討する。 まず, 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)

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

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