論文の概要: Asynchronous Gradient Play in Zero-Sum Multi-agent Games

• arxiv url: http://arxiv.org/abs/2211.08980v1
• Date: Wed, 16 Nov 2022 15:37:23 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-17 17:04:42.206870
• Title: Asynchronous Gradient Play in Zero-Sum Multi-agent Games
• Title（参考訳）: ゼロサムマルチエージェントゲームにおける非同期勾配プレイ
• Authors: Ruicheng Ao, Shicong Cen, Yuejie Chi
• Abstract要約: ゼロサムポリマトリクスゲームにおける遅延フィードバック下での非同期勾配プレイについて検討した。 我々の知る限りでは、この研究はゼロサムポリマトリクスゲームにおける非同期勾配プレイを理解することを目的とした最初のものである。
• 参考スコア（独自算出の注目度）: 25.690033495071923
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Finding equilibria via gradient play in competitive multi-agent games has been attracting a growing amount of attention in recent years, with emphasis on designing efficient strategies where the agents operate in a decentralized and symmetric manner with guaranteed convergence. While significant efforts have been made in understanding zero-sum two-player matrix games, the performance in zero-sum multi-agent games remains inadequately explored, especially in the presence of delayed feedbacks, leaving the scalability and resiliency of gradient play open to questions. In this paper, we make progress by studying asynchronous gradient plays in zero-sum polymatrix games under delayed feedbacks. We first establish that the last iterate of entropy-regularized optimistic multiplicative weight updates (OMWU) method converges linearly to the quantal response equilibrium (QRE), the solution concept under bounded rationality, in the absence of delays. While the linear convergence continues to hold even when the feedbacks are randomly delayed under mild statistical assumptions, it converges at a noticeably slower rate due to a smaller tolerable range of learning rates. Moving beyond, we demonstrate entropy-regularized OMWU -- by adopting two-timescale learning rates in a delay-aware manner -- enjoys faster last-iterate convergence under fixed delays, and continues to converge provably even when the delays are arbitrarily bounded in an average-iterate manner. Our methods also lead to finite-time guarantees to approximate the Nash equilibrium (NE) by moderating the amount of regularization. To the best of our knowledge, this work is the first that aims to understand asynchronous gradient play in zero-sum polymatrix games under a wide range of delay assumptions, highlighting the role of learning rates separation.
• Abstract（参考訳）: 近年、競合型マルチエージェントゲームにおける勾配遊びによる均衡の発見が注目を集めており、エージェントが収束を保証しながら分散的かつ対称的に行動する効率的な戦略の設計に重点が置かれている。 ゼロサム2プレイヤーマトリクスゲームを理解するために多大な努力がなされてきたが、ゼロサムマルチエージェントゲームの性能は、特に遅延フィードバックの存在下では不十分であり、勾配のスケーラビリティとレジリエンスは疑問に残る。 本稿では,ゼロサムポリマトリクスゲームにおける遅延フィードバック下での非同期勾配プレイについて検討する。 まず, エントロピー正規化楽観的乗法重み更新 (omwu) 法の最終反復が, 有界合理性の下での解概念である量子応答平衡 (qre) に線形収束することを確認した。 軽度な統計的仮定の下でランダムにフィードバックが遅れても線形収束は継続するが、許容範囲の学習率が低いため、明らかに遅い速度で収束する。 さらに,2段階の学習速度を遅延認識方式で導入することにより,遅延が平均値に任意に拘束された場合でも,一定の遅延の下で最終値の収束速度が向上することを示す。 また,本手法は正規化量の調整によりナッシュ平衡(NE)を近似する有限時間保証ももたらした。 我々の知る限り、この研究はゼロサムポリマトリクスゲームにおいて、幅広い遅延仮定の下で非同期勾配プレイを理解することを目的としており、学習率分離の役割を強調している。

関連論文リスト

• Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Sampling [73.5602474095954]
  マルコフサンプリングの遅延更新による近似スキームの非漸近的性能について検討した。 我々の理論的な発見は、幅広いアルゴリズムの遅延の有限時間効果に光を当てた。
  論文  参考訳（メタデータ） (2024-02-19T03:08:02Z)
• Game-Theoretic Robust Reinforcement Learning Handles Temporally-Coupled Perturbations [98.5802673062712]
  我々は時間的に結合した摂動を導入し、既存の頑健な強化学習手法に挑戦する。 本稿では、時間的に結合したロバストなRL問題を部分的に観測可能な2プレイヤーゼロサムゲームとして扱う新しいゲーム理論であるGRADを提案する。
  論文  参考訳（メタデータ） (2023-07-22T12:10:04Z)
• On the Convergence of No-Regret Learning Dynamics in Time-Varying Games [89.96815099996132]
  時間変化ゲームにおける楽観的勾配降下(OGD)の収束を特徴付ける。 我々のフレームワークは、ゼロサムゲームにおけるOGDの平衡ギャップに対して鋭い収束境界をもたらす。 また,静的ゲームにおける動的後悔の保証に関する新たな洞察も提供する。
  論文  参考訳（メタデータ） (2023-01-26T17:25:45Z)
• Faster Last-iterate Convergence of Policy Optimization in Zero-Sum Markov Games [63.60117916422867]
  本稿では,対戦型マルチエージェントRLの最も基本的な設定,すなわち2プレーヤゼロサムマルコフゲームに焦点を当てる。 両エージェントから対称更新を施した単一ループポリシー最適化手法を提案し,この手法はエントロピー規則化楽観的乗算重み更新法(OMWU)によって更新される。 我々の収束結果は、最もよく知られた複雑性を改善し、競合するマルコフゲームにおけるポリシー最適化をよりよく理解する。
  論文  参考訳（メタデータ） (2022-10-03T16:05:43Z)
• Fast Policy Extragradient Methods for Competitive Games with Entropy Regularization [40.21627891283402]
  本稿では,競争ゲームの均衡の計算問題について考察する。 エントロピー正則化のアルゴリズム的役割に動機付けられ、我々は証明可能な効率の良い指数関数法を開発した。
  論文  参考訳（メタデータ） (2021-05-31T17:51:15Z)
• Linear Last-iterate Convergence in Constrained Saddle-point Optimization [48.44657553192801]
  我々は、OGDA(Optimistic Gradient Descent Ascent)とOMWU(Optimistic Multiplicative Weights Update)に対する最終段階の独特さの理解を著しく拡大する。 平衡が一意である場合、線形終端収束は、値が普遍定数に設定された学習速度で達成されることを示す。 任意のポリトープ上の双線型ゲームがこの条件を満たすことを示し、OGDAは一意の平衡仮定なしで指数関数的に高速に収束することを示した。
  論文  参考訳（メタデータ） (2020-06-16T20:53:04Z)
• Finite-Time Last-Iterate Convergence for Multi-Agent Learning in Games [116.0771177871705]
  我々は,$lambda$-cocoerciveゲーム上での連立OGD学習における有限時間最終点収束率を特徴付ける。 新たなダブルストッピング時間法により, この適応アルゴリズムは, 非適応的手法と同じ有限時間終点収束率が得られることを示す。
  論文  参考訳（メタデータ） (2020-02-23T01:46:34Z)

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

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