論文の概要: Teamwork makes von Neumann work: Min-Max Optimization in Two-Team Zero-Sum Games

• arxiv url: http://arxiv.org/abs/2111.04178v1
• Date: Sun, 7 Nov 2021 21:15:35 GMT
• ステータス: 処理完了
• システム内更新日: 2021-11-10 04:27:07.022313
• Title: Teamwork makes von Neumann work: Min-Max Optimization in Two-Team Zero-Sum Games
• Title（参考訳）: チームワークがフォン・ノイマンを働かせる: 2チームゼロサムゲームにおける最小最適化
• Authors: Fivos Kalogiannis, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Ioannis Panageas
• Abstract要約: チームゼロサムゲームにおけるmin-max最適化に焦点を当てる。 我々のクラスにおけるナッシュ均衡を見つけることは、CRSハードであることが示される。 我々は, エンフェノ・マルチリニアと, エンフェノ・エンフェノ・セミックス・ナッシュ・エクイリビアを併用したチームゲーム群を提示する。
• 参考スコア（独自算出の注目度）: 19.702066333512548
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Motivated by recent advances in both theoretical and applied aspects of multiplayer games, spanning from e-sports to multi-agent generative adversarial networks, we focus on min-max optimization in team zero-sum games. In this class of games, players are split in two teams with payoffs equal within the same team and of opposite sign across the opponent team. Unlike the textbook two-player zero-sum games, finding a Nash equilibrium in our class can be shown to be CLS-hard, i.e., it is unlikely to have a polynomial time algorithm for computing Nash equilibria. Moreover in this generalized framework, we establish that even asymptotic last iterate or time average convergence to a Nash Equilibrium is not possible using Gradient Descent Ascent (GDA), its optimistic variant and extra gradient. Specifically, we present a family of team games whose induced utility is \emph{non} multi-linear with \emph{non} attractive \emph{per-se} mixed Nash Equilibria, as strict saddle points of the underlying optimization landscape. Leveraging techniques from control theory, we complement these negative results by designing a modified GDA that converges locally to Nash equilibria. Finally, we discuss connections of our framework with AI architectures with team competition structure like multi-agent generative adversarial networks.
• Abstract（参考訳）: チームゼロサムゲームにおける,eスポーツからマルチエージェント生成逆数ネットワークにまたがる,マルチプレイヤーゲームの理論的・応用的側面の最近の進歩に着目し,min-max最適化に着目する。 このクラスでは、プレイヤーは2つのチームに分かれ、同じチーム内と反対のチーム間で対等に報酬が支払われる。 教科書の2プレイヤーゼロサムゲームとは異なり、クラス内のナッシュ均衡を見つけることは CLS-hard、すなわち、ナッシュ平衡を計算する多項式時間アルゴリズムを持つことは不可能である。 さらに, この一般化された枠組みでは, 漸近的な最終反復あるいはナッシュ平衡への時間平均収束は, 勾配降下上昇 (gda) やその楽観的変種, 余分な勾配を用いては不可能であることを示す。 具体的には、誘導効用が \emph{non} multi-linear with \emph{non} attractive \emph{per-se} mixed Nash Equilibria を基礎となる最適化景観の厳密なサドルポイントとして提示する。 制御理論の手法を活用し,nash平衡に局所収束する修正gdaを設計することにより,これらの負の結果を補完する。 最後に,マルチエージェント生成型adversarial networkのようなチームコンペティション構造とaiアーキテクチャとの接続について論じる。

関連論文リスト

• 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)

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

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