論文の概要: Fast Convergence of Optimistic Gradient Ascent in Network Zero-Sum Extensive Form Games

• arxiv url: http://arxiv.org/abs/2207.08426v1
• Date: Mon, 18 Jul 2022 08:21:39 GMT
• ステータス: 処理完了
• システム内更新日: 2022-07-19 19:08:02.493050
• Title: Fast Convergence of Optimistic Gradient Ascent in Network Zero-Sum Extensive Form Games
• Title（参考訳）: ネットワークゼロサム拡張型ゲームにおける最適勾配上昇の高速収束
• Authors: Georgios Piliouras, Lillian Ratliff, Ryann Sim, Stratis Skoulakis
• Abstract要約: 我々は多種多様なフォームゲーム(EFG)、特に多くのエージェントによるEFGにおける学習について研究している。 このようなオンライン学習力学の時間平均挙動は、ナッシュ平衡の集合に$O(c-t)$レート収束を示すことを示す。 また、あるゲーム依存定数$c>0$に対して、日々の振る舞いは$O(c-t)$でNashに収束することを示す。
• 参考スコア（独自算出の注目度）: 36.17578441482575
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The study of learning in games has thus far focused primarily on normal form games. In contrast, our understanding of learning in extensive form games (EFGs) and particularly in EFGs with many agents lags far behind, despite them being closer in nature to many real world applications. We consider the natural class of Network Zero-Sum Extensive Form Games, which combines the global zero-sum property of agent payoffs, the efficient representation of graphical games as well the expressive power of EFGs. We examine the convergence properties of Optimistic Gradient Ascent (OGA) in these games. We prove that the time-average behavior of such online learning dynamics exhibits $O(1/T)$ rate convergence to the set of Nash Equilibria. Moreover, we show that the day-to-day behavior also converges to Nash with rate $O(c^{-t})$ for some game-dependent constant $c>0$.
• Abstract（参考訳）: ゲームにおける学習の研究は、これまで主に通常のフォームゲームに焦点を当ててきた。 対照的に、広範囲なフォームゲーム(EFG)、特に多くのエージェントが遅れているEFGでの学習に対する私たちの理解は、多くの現実世界のアプリケーションに近づきつつあります。 我々は,エージェントペイオフのグローバルゼロサム特性,グラフィカルゲームの効率的な表現,EFGの表現力を組み合わせたネットワークゼロサム拡張フォームゲーム(Network Zero-Sum Extensive Form Games)の自然クラスを考える。 これらのゲームにおいて,OGA(Optimistic Gradient Ascent)の収束特性について検討する。 このようなオンライン学習力学の時間平均挙動は、ナッシュ平衡の集合に対してO(1/T)$レート収束を示す。 さらに,ゲーム依存定数 $c>0$ に対して,nash に対する日々の行動も$o(c^{-t})$ で収束することを示した。

関連論文リスト

• Exploiting Approximate Symmetry for Efficient Multi-Agent Reinforcement Learning [19.543995541149897]
  我々は、任意の有限プレイヤー、おそらく非対称なゲームから「誘導MFG」に拡張する方法論を提供する。 まず、$N$-player の動的ゲームは、明示的な Kirszbraun 拡張によって、無限プレーヤ連続体に対称性を持ち、滑らかに拡張できることを示す。 単調性を満たす特定のゲームに対しては、$widetildemathcalO(varepsilon-6)$のサンプル複雑性を証明し、$N$エージェントゲームに対して、$varepsilon$-Nashを対称性バイアスまで学習する。
  論文  参考訳（メタデータ） (2024-08-27T16:11:20Z)
• Neural Population Learning beyond Symmetric Zero-sum Games [52.20454809055356]
  我々はNuPL-JPSROという,スキルの伝達学習の恩恵を受けるニューラル集団学習アルゴリズムを導入し,ゲームの粗相関(CCE)に収束する。 本研究は, 均衡収束型集団学習を大規模かつ汎用的に実施可能であることを示す。
  論文  参考訳（メタデータ） (2024-01-10T12:56:24Z)
• On the Convergence of No-Regret Learning Dynamics in Time-Varying Games [89.96815099996132]
  時間変化ゲームにおける楽観的勾配降下(OGD)の収束を特徴付ける。 我々のフレームワークは、ゼロサムゲームにおけるOGDの平衡ギャップに対して鋭い収束境界をもたらす。 また,静的ゲームにおける動的後悔の保証に関する新たな洞察も提供する。
  論文  参考訳（メタデータ） (2023-01-26T17:25:45Z)
• Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
  我々は平均場相関と粗相関平衡の概念を発展させる。 ゲームの構造に関する仮定を必要とせず,効率よくゲーム内で学習できることが示される。
  論文  参考訳（メタデータ） (2022-08-22T08:31:46Z)
• Efficient $\Phi$-Regret Minimization in Extensive-Form Games via Online Mirror Descent [49.93548413166884]
  $Phi$-Hedgeは、正規形式ゲーム(NFG)のための大規模な平衡を学習できる汎用アルゴリズムである。 EFGにおけるNash Equilibria(ゼロサム設定)、Normal-Form Coarse Correlated Equilibria(NFCCE)、Extensive-Form Correlated Equilibria(EFCE)の学習に$Phi$-Hedgeが直接利用できることを示す。 それらの設定において、emph$Phi$-Hedgeアルゴリズムは標準ミラーDescent(OMD)アルゴリズムと等価であることを示す。
  論文  参考訳（メタデータ） (2022-05-30T17:58:06Z)
• Kernelized Multiplicative Weights for 0/1-Polyhedral Games: Bridging the Gap Between Learning in Extensive-Form and Normal-Form Games [76.21916750766277]
  カーネルトリックを用いて,最適乗算重み更新(OMWU)アルゴリズムをゲームツリーサイズ毎のリニア時間でEFGの正規形等価値にシミュレート可能であることを示す。 特に、KoMWUは、最終点収束を同時に保証する最初のアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2022-02-01T06:28:51Z)
• Towards convergence to Nash equilibria in two-team zero-sum games [17.4461045395989]
  2チームゼロサムゲームは、プレイヤーが2つの競合するエージェントに分割されるマルチプレイヤーゲームとして定義される。 我々はNash equilibria(NE)の解の概念に焦点をあてる。 このクラスのゲームに対する計算 NE は、複雑性クラス $mathrm$ に対して $textithard$ であることを示す。
  論文  参考訳（メタデータ） (2021-11-07T21:15:35Z)
• Complex Momentum for Learning in Games [42.081050296353574]
  我々は、微分可能なゲームにおいて学習する運動量を伴う勾配降下を複素数値運動量を持つように一般化する。 我々は、複雑な値の運動量によってゲーム内の収束性が改善できることを実証する。 我々はまた、CIFAR-10のより良いスコアにBigGANを訓練するために使用する複素値アダム変種への実用的な一般化を示す。
  論文  参考訳（メタデータ） (2021-02-16T19:55:27Z)
• Evolutionary Game Theory Squared: Evolving Agents in Endogenously Evolving Zero-Sum Games [27.510231246176033]
  本稿では、エージェントとプレイするゲームの両方が戦略的に進化する競争環境のクラスを紹介し、分析する。 エージェントの人口は、現在の人口混合物に反対して進化するゼロサム競争で互いに競います。 驚くべきことに、エージェントとゲームのカオスな共進化にもかかわらず、システムは多くの規則性を示すことを証明しています。
  論文  参考訳（メタデータ） (2020-12-15T15:54:46Z)
• Exponential Convergence of Gradient Methods in Concave Network Zero-sum Games [6.129776019898013]
  コンケーブネットワークゼロサムゲーム(NZSG)におけるナッシュ平衡の計算について検討する。 この一般化において,凸凹型2プレーヤゼロサムゲームの様々なゲーム理論的性質が保存されていることを示す。
  論文  参考訳（メタデータ） (2020-07-10T16:56:56Z)

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

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