Learning in Discounted-cost and Average-cost Mean-field Games

• URL: http://arxiv.org/abs/1912.13309v3
• Date: Thu, 10 Nov 2022 18:44:59 GMT
• Title: Learning in Discounted-cost and Average-cost Mean-field Games
• Authors: Berkay Anahtarc{\i}, Can Deha Kar{\i}ks{\i}z, and Naci Saldi
• Abstract summary: We consider learning approximate Nash equilibria for discrete-time mean-field games with nonlinear state dynamics. We first prove that this operator is a contraction, and propose a learning algorithm to compute an approximate mean-field equilibrium. We then show that the learned mean-field equilibrium constitutes an approximate Nash equilibrium for finite-agent games.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider learning approximate Nash equilibria for discrete-time mean-field games with nonlinear stochastic state dynamics subject to both average and discounted costs. To this end, we introduce a mean-field equilibrium (MFE) operator, whose fixed point is a mean-field equilibrium (i.e. equilibrium in the infinite population limit). We first prove that this operator is a contraction, and propose a learning algorithm to compute an approximate mean-field equilibrium by approximating the MFE operator with a random one. Moreover, using the contraction property of the MFE operator, we establish the error analysis of the proposed learning algorithm. We then show that the learned mean-field equilibrium constitutes an approximate Nash equilibrium for finite-agent games.

Related papers

• Games played by Exponential Weights Algorithms [0.0]
  We consider a repeated interaction in discrete time, where each player uses an exponential weights algorithm characterized by an initial mixed action and a fixed learning rate. We show that whenever a strict Nash equilibrium exists, the probability to play a strict Nash equilibrium at the next stage converges almost surely to 0 or 1.
  arXiv  Detail & Related papers  (2024-07-09T08:49:51Z)
• 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)
• Learning Nash Equilibria in Zero-Sum Markov Games: A Single Time-scale Algorithm Under Weak Reachability [11.793922711718645]
  We consider decentralized learning for zero-sum games, where players only see their information and are to actions and payoffs of the opponent. Previous works demonstrated convergence to a Nash equilibrium in this setting using double time-scale algorithms under strong reachability assumptions. Our contribution is a rational and convergent algorithm, utilizing Tsallis-entropy regularization in a value-iteration-based algorithm.
  arXiv  Detail & Related papers  (2023-12-13T09:31:30Z)
• PAPAL: A Provable PArticle-based Primal-Dual ALgorithm for Mixed Nash Equilibrium [62.51015395213579]
  We consider the non-AL equilibrium nonconptotic objective function in two-player zero-sum continuous games. The proposed algorithm employs the movements of particles to represent the updates of random strategies for the $ilon$-mixed Nash equilibrium.
  arXiv  Detail & Related papers  (2023-03-02T05:08:15Z)
• 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)
• 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)
• Global Convergence of Over-parameterized Deep Equilibrium Models [52.65330015267245]
  A deep equilibrium model (DEQ) is implicitly defined through an equilibrium point of an infinite-depth weight-tied model with an input-injection. Instead of infinite computations, it solves an equilibrium point directly with root-finding and computes gradients with implicit differentiation. We propose a novel probabilistic framework to overcome the technical difficulty in the non-asymptotic analysis of infinite-depth weight-tied models.
  arXiv  Detail & Related papers  (2022-05-27T08:00:13Z)
• On the Nash equilibrium of moment-matching GANs for stationary Gaussian processes [2.25477613430341]
  We show that the existence of consistent Nash equilibrium depends crucially on the choice of the discriminator family. We further study the local stability and global convergence of gradient descent-ascent methods towards consistent equilibrium.
  arXiv  Detail & Related papers  (2022-03-14T14:30:23Z)
• Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games [78.65798135008419]
  It remains vastly open how to learn the Stackelberg equilibrium in general-sum games efficiently from samples. This paper initiates the theoretical study of sample-efficient learning of the Stackelberg equilibrium in two-player turn-based general-sum games.
  arXiv  Detail & Related papers  (2021-02-23T05:11:07Z)
• A mean-field analysis of two-player zero-sum games [46.8148496944294]
  Mixed Nash equilibria exist in greater generality and may be found using mirror descent. We study this dynamics as an interacting gradient flow over measure spaces endowed with the Wasserstein-Fisher-Rao metric. Our method identifies mixed equilibria in high dimensions and is demonstrably effective for training mixtures of GANs.
  arXiv  Detail & Related papers  (2020-02-14T22:46:35Z)

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.