論文の概要: 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}$ のベストイテレート収束を享受する。
最後に,これらアルゴリズムのリスタート変種を導入し,リニアレートラストイテレート収束を楽しんだことを示す。
関連論文リスト
- 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) - Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms [71.73971094342349]
オンライン学習によるセルフプレイは、大規模な2人プレイのゼロサムゲームを解くための重要な方法の1つだ。
我々は,OMWUが支払行列のサイズに対数依存するなど,いくつかの利点があることを示した。
我々は、過去のことをすぐに忘れない幅広い種類のアルゴリズムが、すべて同じ問題に悩まされていることを証明している。
論文 参考訳（メタデータ） (2024-06-15T13:26:17Z) - Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods [25.831462008050387]
グラディエント・Descent(SGD)アルゴリズムは、実際の性能が良く、理論的な理解が欠如していることから、人々の関心を喚起している。
有限収束がより広い合成最適化や非ユークリッドノルムに証明可能な拡張が可能かどうかはまだ不明である。
論文 参考訳（メタデータ） (2023-12-13T21:41:06Z) - Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedback [75.29048190099523]
オンライン勾配降下(OGD)は、強い凸性や単調性仮定の下では二重最適であることが知られている。
本稿では,これらのパラメータの事前知識を必要としない完全適応型OGDアルゴリズム,textsfAdaOGDを設計する。
論文 参考訳（メタデータ） (2023-10-21T18:38:13Z) - 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) - On the Last Iterate Convergence of Momentum Methods [32.60494006038902]
我々は、任意の一定の運動量係数に対して、最後の反復が誤差に苦しむリプシッツおよび凸函数が存在することを初めて証明する。
凸関数と滑らかな関数の設定では、新しいSGDMアルゴリズムが自動的に$O(fraclog TT)$のレートで収束することを示しています。
論文 参考訳（メタデータ） (2021-02-13T21:16:16Z) - 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) - A Simple Convergence Proof of Adam and Adagrad [74.24716715922759]
我々はAdam Adagradと$O(d(N)/st)$アルゴリズムの収束の証明を示す。
Adamはデフォルトパラメータで使用する場合と同じ収束$O(d(N)/st)$で収束する。
論文 参考訳（メタデータ） (2020-03-05T01:56:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。