論文の概要: Multi-Player Zero-Sum Markov Games with Networked Separable Interactions

• arxiv url: http://arxiv.org/abs/2307.09470v2
• Date: Thu, 21 Mar 2024 19:12:08 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-25 23:38:50.920330
• Title: Multi-Player Zero-Sum Markov Games with Networked Separable Interactions
• Title（参考訳）: ネットワーク分離可能な相互作用を持つマルチプレイヤーゼロサムマルコフゲーム
• Authors: Chanwoo Park, Kaiqing Zhang, Asuman Ozdaglar,
• Abstract要約: 我々は,emphNetworked separable interaction (zero-sum NMGs)を用いた新しいマルコフゲーム,emph(multi-player) 0-sum Markov Gamesの研究を行った。 無限水平割引ゼロサムNMGにおける近似マルコフ非定常CCEの発見は、基礎となるネットワークが星のトポロジーを持っていなければ、textttPPAD-hardであることを示す。」
• 参考スコア（独自算出の注目度）: 23.270589136657254
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study a new class of Markov games, \emph(multi-player) zero-sum Markov Games} with \emph{Networked separable interactions} (zero-sum NMGs), to model the local interaction structure in non-cooperative multi-agent sequential decision-making. We define a zero-sum NMG as a model where {the payoffs of the auxiliary games associated with each state are zero-sum and} have some separable (i.e., polymatrix) structure across the neighbors over some interaction network. We first identify the necessary and sufficient conditions under which an MG can be presented as a zero-sum NMG, and show that the set of Markov coarse correlated equilibrium (CCE) collapses to the set of Markov Nash equilibrium (NE) in these games, in that the product of per-state marginalization of the former for all players yields the latter. Furthermore, we show that finding approximate Markov \emph{stationary} CCE in infinite-horizon discounted zero-sum NMGs is \texttt{PPAD}-hard, unless the underlying network has a ``star topology''. Then, we propose fictitious-play-type dynamics, the classical learning dynamics in normal-form games, for zero-sum NMGs, and establish convergence guarantees to Markov stationary NE under a star-shaped network structure. Finally, in light of the hardness result, we focus on computing a Markov \emph{non-stationary} NE and provide finite-iteration guarantees for a series of value-iteration-based algorithms. We also provide numerical experiments to corroborate our theoretical results.
• Abstract（参考訳）: マルコフゲームの新しいクラスである「emph(multi-player) zero-sum Markov Games} with \emph{Networked separable interaction} (zero-sum NMGs)を研究し、非協調的マルチエージェントシーケンシャル意思決定における局所的相互作用構造をモデル化する。 ゼロサム NMG を、各状態に関連する補助ゲームのペイオフがゼロサムであり、ある相互作用ネットワーク上で隣り合う分離可能な(つまりポリマトリクス)構造を持つモデルとして定義する。 まず、MG をゼロサム NMG として提示できる必要十分条件を特定し、これらのゲームにおいてマルコフ粗相関平衡(CCE)の集合がマルコフ・ナッシュ平衡(NE)の集合に崩壊することを示し、前者のすべてのプレイヤーに対する状態ごとの辺化積が後者を得る。 さらに、無限水平割引零サム NMG における近似Markov \emph{stationary} CCE の発見は、基礎となるネットワークが '‘star topology''' を持たない限り、 \texttt{PPAD}-hard であることが示される。 そこで我々は,通常のゲームにおける古典的な学習力学である架空のプレイ型ダイナミクスをゼロサムNMGに対して提案し,星型ネットワーク構造の下でマルコフ定常NEへの収束保証を確立する。 最後に、その硬さを考慮し、Markov \emph{non-stationary} NE の計算に集中し、一連の値イテレーションに基づくアルゴリズムに対する有限イテレーション保証を提供する。 また、理論的結果を裏付ける数値実験も行います。

関連論文リスト

• Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence Beyond the Minty Property [89.96815099996132]
  単一コントローラを用いたマルチプレイヤーゲームにおいて,楽観的なポリシー勾配手法を特徴付ける新しいフレームワークを開発した。 我々のアプローチは、我々が導入する古典的なミニティの自然一般化に依存しており、マルコフゲームを超えてさらなる応用が期待できる。
  論文  参考訳（メタデータ） (2023-12-19T11:34:10Z)
• Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedback [49.1061436241109]
  非漸近収束率の非結合、収束、合理的なアルゴリズムの開発に注力する。 我々のアルゴリズムは[Chen et al., 2021, Cen et al., 2021]と関係があり、エントロピー正規化技術に基づいている。
  論文  参考訳（メタデータ） (2023-03-05T18:08:54Z)
• Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximation [56.715186432566576]
  そこで本稿では,大規模状態空間と多数のエージェントを用いた強化学習のための新しいモデルである独立線形マルコフゲームを提案する。 我々は,各エージェントの関数クラスの複雑性にのみ対応して,サンプル境界複雑性を持つ相関平衡 (CCE) とマルコフ相関平衡 (CE) を学習するための新しいアルゴリズムを設計する。 提案アルゴリズムは,1)複数のエージェントによる非定常性に対処するためのポリシーリプレイと,機能近似の利用,2)マルコフ均衡の学習とマルコフゲームにおける探索の分離という,2つの重要な技術革新に依存している。
  論文  参考訳（メタデータ） (2023-02-07T18:47:48Z)
• When is Offline Two-Player Zero-Sum Markov Game Solvable? [48.34563955829649]
  オフライン2プレイヤーゼロサムマルコフゲームにおいて,ナッシュ均衡(NE)戦略を学習するには単一戦略集中仮定が不十分であることを示す。 本稿では,一方向集中という新しい仮定を提案し,この仮定の下で有効である悲観型アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2022-01-10T18:34:32Z)
• On the Complexity of Computing Markov Perfect Equilibrium in General-Sum Stochastic Games [18.48133964089095]
  ゲーム(SG)は、マルチエージェント強化学習(MARL)とシーケンシャルエージェント相互作用の研究の基礎となった。 我々は,textbfPPAD-completeの指数的精度において,有限状態SGsゲームにおける近似完全平衡(MPE)を導出する。 その結果,textbfNP=textbfco-NP がなければ,SGs における MPE の発見は textbfNP-hard である可能性が極めて低いことが示唆された。
  論文  参考訳（メタデータ） (2021-09-04T05:47:59Z)
• Towards General Function Approximation in Zero-Sum Markov Games [126.58493169301012]
  本稿では,同時移動を伴う2プレーヤゼロサム有限ホライゾンマルコフゲームについて考察する。 分離された設定とコーディネートされた設定の両方の効率的なアルゴリズムが開発されている。
  論文  参考訳（メタデータ） (2021-07-30T15:25:13Z)
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium [116.56359444619441]
  両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。 オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。 オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
  論文  参考訳（メタデータ） (2020-02-17T17:04:16Z)

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

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