Towards convergence to Nash equilibria in two-team zero-sum games
- URL: http://arxiv.org/abs/2111.04178v4
- Date: Mon, 17 Apr 2023 01:57:55 GMT
- Title: Towards convergence to Nash equilibria in two-team zero-sum games
- Authors: Fivos Kalogiannis, Ioannis Panageas, Emmanouil-Vasileios
Vlatakis-Gkaragkounis
- Abstract summary: Two-team zero-sum games are defined as multi-player games where players are split into two competing sets of agents.
We focus on the solution concept of Nash equilibria (NE)
We show that computing NE for this class of games is $textithard$ for the complexity class $mathrm$.
- Score: 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.
Related papers
- MF-OML: Online Mean-Field Reinforcement Learning with Occupation Measures for Large Population Games [5.778024594615575]
This paper proposes an online mean-field reinforcement learning algorithm for computing Nash equilibria of sequential games.
MFOML is the first fully approximate multi-agent reinforcement learning algorithm for provably solving Nash equilibria.
As a byproduct, we also obtain the first tractable globally convergent computational for approximate computing of monotone mean-field games.
arXiv Detail & Related papers (2024-05-01T02:19:31Z) - 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) - Differentiable Arbitrating in Zero-sum Markov Games [59.62061049680365]
We study how to perturb the reward in a zero-sum Markov game with two players to induce a desirable Nash equilibrium, namely arbitrating.
The lower level requires solving the Nash equilibrium under a given reward function, which makes the overall problem challenging to optimize in an end-to-end way.
We propose a backpropagation scheme that differentiates through the Nash equilibrium, which provides the gradient feedback for the upper level.
arXiv Detail & Related papers (2023-02-20T16:05:04Z) - Global Nash Equilibrium in Non-convex Multi-player Game: Theory and
Algorithms [66.8634598612777]
We show that Nash equilibrium (NE) is acceptable to all players in a multi-player game.
We also show that no one can benefit unilaterally from the general theory step by step.
arXiv Detail & Related papers (2023-01-19T11:36:50Z) - Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
We develop the concepts of Mean-Field correlated and coarse-correlated equilibria.
We show that they can be efficiently learnt in emphall games, without requiring any additional assumption on the structure of the game.
arXiv Detail & Related papers (2022-08-22T08:31:46Z) - Efficiently Computing Nash Equilibria in Adversarial Team Markov Games [19.717850955051837]
We introduce a class of games in which a team identically players is competing against an adversarial player.
This setting allows for a unifying treatment of zero-sum Markov games potential games.
Our main contribution is the first algorithm for computing stationary $epsilon$-approximate Nash equilibria in adversarial team Markov games.
arXiv Detail & Related papers (2022-08-03T16:41:01Z) - Provably Efficient Fictitious Play Policy Optimization for Zero-Sum
Markov Games with Structured Transitions [145.54544979467872]
We propose and analyze new fictitious play policy optimization algorithms for zero-sum Markov games with structured but unknown transitions.
We prove tight $widetildemathcalO(sqrtK)$ regret bounds after $K$ episodes in a two-agent competitive game scenario.
Our algorithms feature a combination of Upper Confidence Bound (UCB)-type optimism and fictitious play under the scope of simultaneous policy optimization.
arXiv Detail & Related papers (2022-07-25T18:29:16Z) - Learning to Compute Approximate Nash Equilibrium for Normal-form Games [15.321036952379488]
We propose a general meta learning approach to computing approximate Nash equilibrium for finite $n$-player normal-form games.
Unlike existing solutions that approximate or learn a Nash equilibrium from scratch for each of the games, our meta solver directly constructs a mapping from a game utility matrix to a joint strategy profile.
arXiv Detail & Related papers (2021-08-17T07:06:46Z) - 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.