Learning Regularized Monotone Graphon Mean-Field Games

• URL: http://arxiv.org/abs/2310.08089v1
• Date: Thu, 12 Oct 2023 07:34:13 GMT
• Title: Learning Regularized Monotone Graphon Mean-Field Games
• Authors: Fengzhuo Zhang, Vincent Y. F. Tan, Zhaoran Wang, Zhuoran Yang
• Abstract summary: We study fundamental problems in regularized Graphon Mean-Field Games (GMFGs) We establish the existence of a Nash Equilibrium (NE) of any $lambda$-regularized GMFG. We propose provably efficient algorithms to learn the NE in weakly monotone GMFGs.
• Score: 155.38727464526923
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper studies two fundamental problems in regularized Graphon Mean-Field Games (GMFGs). First, we establish the existence of a Nash Equilibrium (NE) of any $\lambda$-regularized GMFG (for $\lambda\geq 0$). This result relies on weaker conditions than those in previous works for analyzing both unregularized GMFGs ($\lambda=0$) and $\lambda$-regularized MFGs, which are special cases of GMFGs. Second, we propose provably efficient algorithms to learn the NE in weakly monotone GMFGs, motivated by Lasry and Lions [2007]. Previous literature either only analyzed continuous-time algorithms or required extra conditions to analyze discrete-time algorithms. In contrast, we design a discrete-time algorithm and derive its convergence rate solely under weakly monotone conditions. Furthermore, we develop and analyze the action-value function estimation procedure during the online learning process, which is absent from algorithms for monotone GMFGs. This serves as a sub-module in our optimization algorithm. The efficiency of the designed algorithm is corroborated by empirical evaluations.

Related papers

• Last Iterate Convergence in Monotone Mean Field Games [5.407319151576265]
  Mean Field Game (MFG) is a framework utilized to model and approximate the behavior of a large number of agents. We propose the use of a simple, proximal-point-type algorithm to compute equilibria for MFGs. We provide the first last-iterate convergence guarantee under the Lasry--Lions-type monotonicity condition.
  arXiv  Detail & Related papers  (2024-10-07T15:28:18Z)
• Learning Arithmetic Formulas in the Presence of Noise: A General Framework and Applications to Unsupervised Learning [4.10375234787249]
  We present a framework for designing efficient algorithms for unsupervised learning problems. Our framework is based on a meta algorithm that learns arithmetic circuits in the presence of noise.
  arXiv  Detail & Related papers  (2023-11-13T12:26:25Z)
• Learning Regularized Graphon Mean-Field Games with Unknown Graphons [155.38727464526923]
  We design reinforcement learning algorithms for Graphon Mean-Field Games (GMFGs) We aim to learn the Nash Equilibrium (NE) of the regularized GMFGs when the graphons are unknown. These algorithms are the first specifically designed for learning graphons from sampled agents.
  arXiv  Detail & Related papers  (2023-10-26T16:19:24Z)
• Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
  We study differentially private approximation algorithms for hierarchical clustering. We show strong lower bounds for the problem: that any $epsilon$-DP algorithm must exhibit $O(|V|2/ epsilon)$-additive error for an input dataset. We propose a private $1+o(1)$ approximation algorithm which also recovers the blocks exactly.
  arXiv  Detail & Related papers  (2023-01-31T19:14:30Z)
• Linear-Time Algorithms for Front-Door Adjustment in Causal Graphs [3.707290781951909]
  Causal effect estimation from observational data is a fundamental task in empirical sciences. This paper focuses on front-door adjustment -- a classic technique which, using observed mediators, allows to identify causal effects even in the presence of unobserved confounders.
  arXiv  Detail & Related papers  (2022-11-29T18:44:03Z)
• Efficient $\Phi$-Regret Minimization in Extensive-Form Games via Online Mirror Descent [49.93548413166884]
  $Phi$-Hedge is a generic algorithm capable of learning a large class of equilibria for Normal-Form Games (NFGs) We show that $Phi$-Hedge can be directly used to learn Nash Equilibria (zero-sum settings), Normal-Form Coarse Correlated Equilibria (NFCCE), and Extensive-Form Correlated Equilibria (EFCE) in EFGs. We prove that, in those settings, the emph$Phi$-Hedge algorithms are equivalent to standard Mirror Descent (OMD) algorithms for
  arXiv  Detail & Related papers  (2022-05-30T17:58:06Z)
• Kernelized Multiplicative Weights for 0/1-Polyhedral Games: Bridging the Gap Between Learning in Extensive-Form and Normal-Form Games [76.21916750766277]
  We show that the Optimistic Multiplicative Weights Update (OMWU) algorithm can be simulated on the normal-form equivalent of an EFG in linear time per iteration in the game tree size using a kernel trick. Specifically, KOMWU gives the first algorithm that guarantees at the same time last-iterate convergence.
  arXiv  Detail & Related papers  (2022-02-01T06:28:51Z)
• Higher-order Derivatives of Weighted Finite-state Machines [68.43084108204741]
  This work examines the computation of higher-order derivatives with respect to the normalization constant for weighted finite-state machines. We provide a general algorithm for evaluating derivatives of all orders, which has not been previously described in the literature. Our algorithm is significantly faster than prior algorithms.
  arXiv  Detail & Related papers  (2021-06-01T19:51:55Z)

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.