論文の概要: On the Convergence of Fictitious Play: A Decomposition Approach

• arxiv url: http://arxiv.org/abs/2205.01469v1
• Date: Tue, 3 May 2022 13:04:09 GMT
• ステータス: 処理完了
• システム内更新日: 2022-05-04 18:27:04.944206
• Title: On the Convergence of Fictitious Play: A Decomposition Approach
• Title（参考訳）: 架空の遊びの収束について:分解的アプローチ
• Authors: Yurong Chen, Xiaotie Deng, Chenchen Li, David Mguni, Jun Wang, Xiang Yan, Yaodong Yang
• Abstract要約: 我々は、FP(Fictitious Play)の収束結果を、そのようなゲームとそれ以上の組み合わせに拡張する。 我々は,この2種類のゲームが相互に移動可能であるという意味で,協調と競争を統一する線形関係を構築している。 我々は、FPの非収束例であるShapleyゲームを分析し、FPが収束するのに十分な条件を開発する。
• 参考スコア（独自算出の注目度）: 17.607284715519587
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Fictitious play (FP) is one of the most fundamental game-theoretical learning frameworks for computing Nash equilibrium in $n$-player games, which builds the foundation for modern multi-agent learning algorithms. Although FP has provable convergence guarantees on zero-sum games and potential games, many real-world problems are often a mixture of both and the convergence property of FP has not been fully studied yet. In this paper, we extend the convergence results of FP to the combinations of such games and beyond. Specifically, we derive new conditions for FP to converge by leveraging game decomposition techniques. We further develop a linear relationship unifying cooperation and competition in the sense that these two classes of games are mutually transferable. Finally, we analyze a non-convergent example of FP, the Shapley game, and develop sufficient conditions for FP to converge.
• Abstract（参考訳）: Fictitious Play (FP)は、現代のマルチエージェント学習アルゴリズムの基礎を築いた、$n$-playerゲームにおけるナッシュ均衡を計算するための最も基本的なゲーム理論学習フレームワークの1つである。 FP はゼロサムゲームやポテンシャルゲームにおいて証明可能な収束を保証するが、実世界の問題の多くは両者の混合であり、FP の収束性はまだ十分に研究されていない。 本稿では,FPの収束結果を,そのようなゲームとそれ以上の組み合わせに拡張する。 具体的には、ゲーム分解技術を利用してFPが収束する新しい条件を導出する。 さらに,これら2種類のゲームが相互に転送可能であるという意味で,協調と競争を統一する線形関係を発達させる。 最後に、FPの非収束例であるShapleyゲームを分析し、FPが収束するのに十分な条件を開発する。

関連論文リスト

• Neural Population Learning beyond Symmetric Zero-sum Games [52.20454809055356]
  我々はNuPL-JPSROという,スキルの伝達学習の恩恵を受けるニューラル集団学習アルゴリズムを導入し,ゲームの粗相関(CCE)に収束する。 本研究は, 均衡収束型集団学習を大規模かつ汎用的に実施可能であることを示す。
  論文  参考訳（メタデータ） (2024-01-10T12:56:24Z)
• Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence Beyond the Minty Property [89.96815099996132]
  単一コントローラを用いたマルチプレイヤーゲームにおいて,楽観的なポリシー勾配手法を特徴付ける新しいフレームワークを開発した。 我々のアプローチは、我々が導入する古典的なミニティの自然一般化に依存しており、マルコフゲームを超えてさらなる応用が期待できる。
  論文  参考訳（メタデータ） (2023-12-19T11:34:10Z)
• Global Nash Equilibrium in Non-convex Multi-player Game: Theory and Algorithms [66.8634598612777]
  ナッシュ均衡(NE)はマルチプレイヤーゲームにおいて全てのプレイヤーに受け入れられることを示す。 また、一般理論から一歩ずつ一方的に利益を得ることはできないことも示している。
  論文  参考訳（メタデータ） (2023-01-19T11:36:50Z)
• Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
  我々は平均場相関と粗相関平衡の概念を発展させる。 ゲームの構造に関する仮定を必要とせず,効率よくゲーム内で学習できることが示される。
  論文  参考訳（メタデータ） (2022-08-22T08:31:46Z)
• 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)
• Exploration-Exploitation in Multi-Agent Competition: Convergence with Bounded Rationality [21.94743452608215]
  本研究では,ゲーム報酬と探索費用のバランスを捉えたプロトタイプ学習モデルであるスムーズQ-ラーニングについて検討する。 Q-ラーニングは常に、有界な有理性の下でのゲームに対する標準的な解概念である一意の量子-応答平衡(QRE)に収束することを示す。
  論文  参考訳（メタデータ） (2021-06-24T11:43:38Z)
• Operator Splitting for Learning to Predict Equilibria in Convex Games [26.92001486095397]
  平衡を自然に出力するニューラルネットワークのクラスであるNash Fixed Point Networks (N-FPNs)を紹介する。 N-FPNは暗黙のネットワークをトレーニングするための最近開発されたヤコビアンフリーバックプロパゲーション技術と互換性がある。 実験の結果,N-FPNは既存の学習ゲーム解法よりも桁違いに大きい問題にスケール可能であることがわかった。
  論文  参考訳（メタデータ） (2021-06-02T02:55:46Z)
• Scaling up Mean Field Games with Online Mirror Descent [55.36153467919289]
  オンラインミラー Descent (OMD) を用いた平均場ゲーム (MFG) のスケールアップ均衡計算に対処する。 連続時間 OMD は自然かつモチベーションの良い単調性仮定の集合の下でナッシュ平衡に確実に収束することを示す。 様々な単一および多集団MFGに関する徹底的な実験的研究は、OMDがFictitious Play (FP)のような従来のアルゴリズムより優れていることを示している。
  論文  参考訳（メタデータ） (2021-02-28T21:28:36Z)
• Convergence of Deep Fictitious Play for Stochastic Differential Games [6.875312133832078]
  最近提案された機械学習アルゴリズム、Deep fictitious Playは、大きな$N$非対称微分ゲームにおけるマルコフ的ナッシュ均衡を見つけるための、新しい効率的なツールを提供する。 架空のプレイの概念を取り入れることで、アルゴリズムはゲームを$N$のサブ最適化問題に分解する。 DFPに基づく戦略が$eps$-Nash均衡を形成することを示す。
  論文  参考訳（メタデータ） (2020-08-12T18:27:13Z)
• Finite-Time Last-Iterate Convergence for Multi-Agent Learning in Games [116.0771177871705]
  我々は,$lambda$-cocoerciveゲーム上での連立OGD学習における有限時間最終点収束率を特徴付ける。 新たなダブルストッピング時間法により, この適応アルゴリズムは, 非適応的手法と同じ有限時間終点収束率が得られることを示す。
  論文  参考訳（メタデータ） (2020-02-23T01:46:34Z)

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

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