論文の概要: Global Nash Equilibrium in Non-convex Multi-player Game: Theory and Algorithms

• arxiv url: http://arxiv.org/abs/2301.08015v1
• Date: Thu, 19 Jan 2023 11:36:50 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-20 15:18:38.355283
• Title: Global Nash Equilibrium in Non-convex Multi-player Game: Theory and Algorithms
• Title（参考訳）: 非凸多人数ゲームにおけるグローバルナッシュ平衡:理論とアルゴリズム
• Authors: Guanpu Chen, Gehui Xu, Fengxiang He, Yiguang Hong, Leszek Rutkowski, and Dacheng Tao
• Abstract要約: ナッシュ均衡(NE)はマルチプレイヤーゲームにおいて全てのプレイヤーに受け入れられることを示す。 また、一般理論から一歩ずつ一方的に利益を得ることはできないことも示している。
• 参考スコア（独自算出の注目度）: 66.8634598612777
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Wide machine learning tasks can be formulated as non-convex multi-player games, where Nash equilibrium (NE) is an acceptable solution to all players, since no one can benefit from changing its strategy unilaterally. Attributed to the non-convexity, obtaining the existence condition of global NE is challenging, let alone designing theoretically guaranteed realization algorithms. This paper takes conjugate transformation to the formulation of non-convex multi-player games, and casts the complementary problem into a variational inequality (VI) problem with a continuous pseudo-gradient mapping. We then prove the existence condition of global NE: the solution to the VI problem satisfies a duality relation. Based on this VI formulation, we design a conjugate-based ordinary differential equation (ODE) to approach global NE, which is proved to have an exponential convergence rate. To make the dynamics more implementable, we further derive a discretized algorithm. We apply our algorithm to two typical scenarios: multi-player generalized monotone game and multi-player potential game. In the two settings, we prove that the step-size setting is required to be $\mathcal{O}(1/k)$ and $\mathcal{O}(1/\sqrt k)$ to yield the convergence rates of $\mathcal{O}(1/ k)$ and $\mathcal{O}(1/\sqrt k)$, respectively. Extensive experiments in robust neural network training and sensor localization are in full agreement with our theory.
• Abstract（参考訳）: 幅広い機械学習タスクは、nash均衡(ne)が全てのプレイヤーにとって許容可能な解決策である非凸マルチプレイヤーゲームとして定式化することができる。 非凸性への貢献により、理論上保証された実現アルゴリズムを設計するだけでも、グローバルNEの存在条件を得るのは難しい。 本稿では,非凸マルチプレイヤーゲームの定式化に共役変換を取り入れ,相補的な問題を連続擬次写像を持つ変分不等式(vi)問題にキャストする。 次に、大域的 NE の存在条件を証明し、VI 問題に対する解は双対関係を満たす。 この VI の定式化に基づき,大域的 NE に近づく共役型常微分方程式 (ODE) を設計し,指数収束率を持つことを示した。 ダイナミクスをより実装可能にするため、離散化アルゴリズムをさらに導出する。 本アルゴリズムは,マルチプレイヤー一般化モノトーンゲームとマルチプレイヤーポテンシャルゲームという2つの典型的なシナリオに適用する。 2つの設定において、ステップサイズの設定は $\mathcal{o}(1/k)$ と $\mathcal{o}(1/\sqrt k)$ であり、それぞれ $\mathcal{o}(1/k)$ と $\mathcal{o}(1/\sqrt k)$ の収束率が得られることが証明される。 堅牢なニューラルネットワークトレーニングとセンサローカライゼーションの広範な実験は、我々の理論と完全に一致している。

関連論文リスト

• Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms [71.73971094342349]
  オンライン学習によるセルフプレイは、大規模な2人プレイのゼロサムゲームを解くための重要な方法の1つだ。 我々は,OMWUが支払行列のサイズに対数依存するなど,いくつかの利点があることを示した。 我々は、過去のことをすぐに忘れない幅広い種類のアルゴリズムが、すべて同じ問題に悩まされていることを証明している。
  論文  参考訳（メタデータ） (2024-06-15T13:26:17Z)
• MF-OML: Online Mean-Field Reinforcement Learning with Occupation Measures for Large Population Games [5.778024594615575]
  本稿では,シーケンシャルゲームのナッシュ平衡計算のためのオンライン平均場強化学習アルゴリズムを提案する。 MFOMLは、ナッシュ平衡を実証的に解くための、最初の完全近似マルチエージェント強化学習アルゴリズムである。 副生成物として、モノトーン平均場ゲームの近似計算のための最初のトラクタブル大域収束計算も得られる。
  論文  参考訳（メタデータ） (2024-05-01T02:19:31Z)
• Distributed Extra-gradient with Optimal Complexity and Communication Guarantees [60.571030754252824]
  複数のプロセッサ/ワーカー/クライアントがローカルなデュアルベクトルにアクセス可能なマルチGPU設定において、モノトン変分不等式(VI)問題を考察する。 モノトーンVI問題に対するデファクトアルゴリズムであるExtra-gradientは、通信効率が良くないように設計されている。 そこで本稿では,VI の解法に適した非バイアスで適応的な圧縮手法である量子化一般化外部勾配 (Q-GenX) を提案する。
  論文  参考訳（メタデータ） (2023-08-17T21:15:04Z)
• Learning in Multi-Player Stochastic Games [1.0878040851638]
  有限ホライズン設定において、多くのプレイヤーとゲームにおける同時学習の問題を考える。 ゲームの典型的な対象解はナッシュ均衡であるが、これは多くのプレイヤーにとって難解である。 我々は異なるターゲットに目を向ける:全てのプレイヤーが使用するときの平衡を生成するアルゴリズム。
  論文  参考訳（メタデータ） (2022-10-25T19:02:03Z)
• Minimax-Optimal Multi-Agent RL in Zero-Sum Markov Games With a Generative Model [50.38446482252857]
  2人プレイのゼロサムマルコフゲームは多エージェント強化学習においておそらく最も基本的な設定である。 我々は,$$ widetildeObiggを用いて,$varepsilon$-approximate Markov NEポリシーを学習する学習アルゴリズムを開発した。 我々は、分散型量の役割を明確にするFTRLに対する洗練された後悔境界を導出する。
  論文  参考訳（メタデータ） (2022-08-22T17:24:55Z)
• Learning Two-Player Mixture Markov Games: Kernel Function Approximation and Correlated Equilibrium [157.0902680672422]
  非線形関数近似を用いた2プレイヤーゼロサムマルコフゲームにおけるナッシュ平衡の学習について検討する。 双対性ギャップを最小化してナッシュ均衡を求める新しいオンライン学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-08-10T14:21:54Z)
• 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)
• On the Impossibility of Global Convergence in Multi-Loss Optimization [10.081768261298098]
  所望の収束特性が任意のアルゴリズムに対して同時に保持できないことを証明する。 我々の結果は、それぞれのアルゴリズムよりも、満足のいく結果のないゲームの存在と関係がある。 ML実践者にとって、高次元ゲームにそのような振る舞いが生じるかどうかは、未解決の問題である。
  論文  参考訳（メタデータ） (2020-05-26T12:11:18Z)
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium [116.56359444619441]
  両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。 オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。 オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
  論文  参考訳（メタデータ） (2020-02-17T17:04:16Z)

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

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