論文の概要: Towards convergence to Nash equilibria in two-team zero-sum games
- arxiv url: http://arxiv.org/abs/2111.04178v4
- Date: Mon, 17 Apr 2023 01:57:55 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-19 01:01:56.126559
- Title: Towards convergence to Nash equilibria in two-team zero-sum games
- Title（参考訳）: 2チームゼロサムゲームにおけるnash平衡への収束に向けて
- Authors: Fivos Kalogiannis, Ioannis Panageas, Emmanouil-Vasileios
Vlatakis-Gkaragkounis
- Abstract要約: 2チームゼロサムゲームは、プレイヤーが2つの競合するエージェントに分割されるマルチプレイヤーゲームとして定義される。
我々はNash equilibria(NE)の解の概念に焦点をあてる。
このクラスのゲームに対する計算 NE は、複雑性クラス $mathrm$ に対して $textithard$ であることを示す。
- 参考スコア（独自算出の注目度）: 17.4461045395989
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Contemporary applications of machine learning in two-team e-sports and the
superior expressivity of multi-agent generative adversarial networks raise
important and overlooked theoretical questions regarding optimization in
two-team games. Formally, two-team zero-sum games are defined as multi-player
games where players are split into two competing sets of agents, each
experiencing a utility identical to that of their teammates and opposite to
that of the opposing team. We focus on the solution concept of Nash equilibria
(NE). We first show that computing NE for this class of games is
$\textit{hard}$ for the complexity class ${\mathrm{CLS}}$. To further examine
the capabilities of online learning algorithms in games with full-information
feedback, we propose a benchmark of a simple -- yet nontrivial -- family of
such games. These games do not enjoy the properties used to prove convergence
for relevant algorithms. In particular, we use a dynamical systems perspective
to demonstrate that gradient descent-ascent, its optimistic variant, optimistic
multiplicative weights update, and extra gradient fail to converge (even
locally) to a Nash equilibrium. On a brighter note, we propose a first-order
method that leverages control theory techniques and under some conditions
enjoys last-iterate local convergence to a Nash equilibrium. We also believe
our proposed method is of independent interest for general min-max
optimization.
- Abstract（参考訳）: 2チームeスポーツにおける機械学習の現代的応用と、複数エージェント生成対向ネットワークの優れた表現性は、2チームゲームにおける最適化に関する重要かつ見過ごされた理論的疑問を提起する。
正式には、2チームのゼロサムゲームはマルチプレイヤーゲームとして定義され、プレイヤーは2つの競合するエージェントに分割され、それぞれがチームメイトと同一のユーティリティを経験し、相手チームのそれと反対である。
我々はNash equilibria(NE)の解の概念に焦点を当てる。
このクラスのゲームに対する NE の計算は、複雑性クラス ${\mathrm{CLS}}$ に対して $\textit{hard}$ であることを示す。
完全情報フィードバックを持つゲームにおけるオンライン学習アルゴリズムの能力をさらに検証するために,そのようなゲームファミリーの単純だが非自明なベンチマークを提案する。
これらのゲームは、関連するアルゴリズムの収束を証明するために使われる性質を享受しない。
特に, 動的系の観点を用いて, 勾配降下上昇, 楽観的変種, 楽観的乗法重みの更新, 余剰勾配が(局所的にも)nash平衡に収束しないことを示す。
より明るい注意として,制御理論の手法を活用し,ある条件下ではナッシュ平衡へのラストイテレート局所収束を享受する一階法を提案する。
また,提案手法は一般のmin-max最適化に独立した関心を持っている。
関連論文リスト
- MF-OML: Online Mean-Field Reinforcement Learning with Occupation Measures for Large Population Games [5.778024594615575]
本稿では,シーケンシャルゲームのナッシュ平衡計算のためのオンライン平均場強化学習アルゴリズムを提案する。
MFOMLは、ナッシュ平衡を実証的に解くための、最初の完全近似マルチエージェント強化学習アルゴリズムである。
副生成物として、モノトーン平均場ゲームの近似計算のための最初のトラクタブル大域収束計算も得られる。
論文 参考訳（メタデータ） (2024-05-01T02:19:31Z) - Optimistic Policy Gradient in Multi-Player Markov Games with a Single
Controller: Convergence Beyond the Minty Property [89.96815099996132]
単一コントローラを用いたマルチプレイヤーゲームにおいて,楽観的なポリシー勾配手法を特徴付ける新しいフレームワークを開発した。
我々のアプローチは、我々が導入する古典的なミニティの自然一般化に依存しており、マルコフゲームを超えてさらなる応用が期待できる。
論文 参考訳（メタデータ） (2023-12-19T11:34:10Z) - Differentiable Arbitrating in Zero-sum Markov Games [59.62061049680365]
ゼロサムマルコフゲームにおいて、2人のプレイヤーが望ましいナッシュ均衡、すなわち仲裁を誘導する報酬を摂動する方法を研究する。
低いレベルでは、与えられた報酬関数の下でのナッシュ均衡の解決が必要であり、それによって全体的な問題をエンドツーエンドで最適化することが難しくなる。
上層階の勾配フィードバックを提供するナッシュ平衡を微分するバックプロパゲーション方式を提案する。
論文 参考訳（メタデータ） (2023-02-20T16:05:04Z) - 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) - Efficiently Computing Nash Equilibria in Adversarial Team Markov Games [19.717850955051837]
我々は,同じプレイヤーが対戦相手と競合するゲームのクラスを紹介する。
この設定により、ゼロサムマルコフゲームの可能性ゲームの統一処理が可能になる。
我々の主な貢献は、対戦チームマルコフゲームにおける固定的な$epsilon$-approximate Nash平衡を計算するための最初のアルゴリズムである。
論文 参考訳（メタデータ） (2022-08-03T16:41:01Z) - Provably Efficient Fictitious Play Policy Optimization for Zero-Sum
Markov Games with Structured Transitions [145.54544979467872]
本研究では,ゼロサムマルコフゲームに対して,構造的だが未知の遷移を伴う架空のプレイポリシー最適化アルゴリズムを提案し,解析する。
我々は、2年制の競争ゲームシナリオで、$K$のエピソードに続き、$widetildemathcalO(sqrtK)$ regret boundsを証明した。
提案アルゴリズムは,アッパー信頼境界(UCB)型最適化と,同時政策最適化の範囲内での架空のプレイの組み合わせを特徴とする。
論文 参考訳（メタデータ） (2022-07-25T18:29:16Z) - Learning to Compute Approximate Nash Equilibrium for Normal-form Games [15.321036952379488]
有限$n$-playerの正規形式ゲームに対して,Nash平衡を近似的に計算するための一般的なメタ学習手法を提案する。
ゲーム毎のナッシュ均衡をスクラッチから近似あるいは学習する既存の解とは異なり、メタソルバはゲームユーティリティ行列からジョイント戦略プロファイルへの写像を直接構築する。
論文 参考訳（メタデータ） (2021-08-17T07:06:46Z) - Learning Zero-Sum Simultaneous-Move Markov Games Using Function
Approximation and Correlated Equilibrium [116.56359444619441]
両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。
オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。
オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
論文 参考訳（メタデータ） (2020-02-17T17:04:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。