Multi-Player Zero-Sum Markov Games with Networked Separable Interactions

• URL: http://arxiv.org/abs/2307.09470v3
• Date: Sat, 12 Jul 2025 20:06:53 GMT
• Title: Multi-Player Zero-Sum Markov Games with Networked Separable Interactions
• Authors: Chanwoo Park, Kaiqing Zhang, Asuman Ozdaglar,
• Abstract summary: We study a new class of Markov games, emph(multi-player) zero-sum Markov Games with emphNetworked separable interactions (zero-sum NMGs)<n>We show that finding approximate Markov emphstationary CCE in infinite-horizon discounted zero-sum NMGs is textttPPAD-hard, unless the underlying network has a star topology''
• Score: 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.

Related papers

• Convex Markov Games and Beyond: New Proof of Existence, Characterization and Learning Algorithms for Nash Equilibria [20.875347023588652]
  General Utility Markov Games (GUMGs) capture new applications requiring coupling between agents' occupancy measures.<n>We prove that Nash equilibria coincide with the fixed points of projected pseudo-gradient dynamics (i.e., first-order stationary points) enabled by a novel agent-wise gradient domination property.<n>Building on this characterization, we establish a policy gradient theorem for GUMGs and design a model-free policy gradient algorithm.
  arXiv  Detail & Related papers  (2026-02-12T17:11:20Z)
• Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Games [40.05960121330012]
  Multi-agent reinforcement learning (MARL) lies at the heart of a plethora of applications involving the interaction of a group of agents in a shared unknown environment.<n>We propose a novel model-based algorithm, called VMG, that incentivizes exploration via biasing the empirical estimate of the model parameters.
  arXiv  Detail & Related papers  (2025-02-13T21:28:51Z)
• Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence Beyond the Minty Property [89.96815099996132]
  We develop a new framework to characterize optimistic policy gradient methods in multi-player games with a single controller. Our approach relies on a natural generalization of the classical Minty property that we introduce, which we anticipate to have further applications beyond Markov games.
  arXiv  Detail & Related papers  (2023-12-19T11:34:10Z)
• Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedback [49.1061436241109]
  We focus on developing an algorithm that is uncoupled, convergent, and rational, with non-asymptotic convergence rates. Our algorithm is related to [Chen et al., 2021, Cen et al., 2021] and also builds on the entropy regularization technique.
  arXiv  Detail & Related papers  (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]
  We propose a new model, independent linear Markov game, for reinforcement learning with a large state space and a large number of agents. We design new algorithms for learning correlated equilibria (CCE) and Markov correlated equilibria (CE) with sample bounds complexity that only scalely with each agent's own function class complexity. Our algorithms rely on two key technical innovations: (1) utilizing policy replay to tackle non-stationarity incurred by multiple agents and the use of function approximation; and (2) separating learning Markov equilibria and exploration in the Markov games.
  arXiv  Detail & Related papers  (2023-02-07T18:47:48Z)
• When is Offline Two-Player Zero-Sum Markov Game Solvable? [48.34563955829649]
  We show that the single strategy concentration assumption is insufficient for learning the Nash equilibrium (NE) strategy in offline two-player zero-sum Markov games. We propose a new assumption named unilateral concentration and design a pessimism-type algorithm that is provably efficient under this assumption.
  arXiv  Detail & Related papers  (2022-01-10T18:34:32Z)
• On the Complexity of Computing Markov Perfect Equilibrium in General-Sum Stochastic Games [18.48133964089095]
  Games (SGs) lay the foundation for the study of multi-agent reinforcement learning (MARL) and sequential agent interactions. We derive an approximate Perfect Equilibrium (MPE) in a finite-state SGs Game within the exponential precision of textbfPPAD-complete. Our results indicate that finding an MPE in SGs is highly unlikely to be textbfNP-hard unless textbfNP=textbfco-NP.
  arXiv  Detail & Related papers  (2021-09-04T05:47:59Z)
• Towards General Function Approximation in Zero-Sum Markov Games [126.58493169301012]
  This paper considers two-player zero-sum finite-horizon Markov games with simultaneous moves. Provably efficient algorithms for both decoupled and coordinated settings are developed.
  arXiv  Detail & Related papers  (2021-07-30T15:25:13Z)
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium [116.56359444619441]
  We develop provably efficient reinforcement learning algorithms for two-player zero-sum finite-horizon Markov games. In the offline setting, we control both players and aim to find the Nash Equilibrium by minimizing the duality gap. In the online setting, we control a single player playing against an arbitrary opponent and aim to minimize the regret.
  arXiv  Detail & Related papers  (2020-02-17T17:04:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.