Learning Regularized Graphon Mean-Field Games with Unknown Graphons

• URL: http://arxiv.org/abs/2310.17531v1
• Date: Thu, 26 Oct 2023 16:19:24 GMT
• Title: Learning Regularized Graphon Mean-Field Games with Unknown Graphons
• Authors: Fengzhuo Zhang, Vincent Y. F. Tan, Zhaoran Wang, Zhuoran Yang
• Abstract summary: 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.
• Score: 155.38727464526923
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We design and analyze reinforcement learning algorithms for Graphon Mean-Field Games (GMFGs). In contrast to previous works that require the precise values of the graphons, we aim to learn the Nash Equilibrium (NE) of the regularized GMFGs when the graphons are unknown. Our contributions are threefold. First, we propose the Proximal Policy Optimization for GMFG (GMFG-PPO) algorithm and show that it converges at a rate of $O(T^{-1/3})$ after $T$ iterations with an estimation oracle, improving on a previous work by Xie et al. (ICML, 2021). Second, using kernel embedding of distributions, we design efficient algorithms to estimate the transition kernels, reward functions, and graphons from sampled agents. Convergence rates are then derived when the positions of the agents are either known or unknown. Results for the combination of the optimization algorithm GMFG-PPO and the estimation algorithm are then provided. These algorithms are the first specifically designed for learning graphons from sampled agents. Finally, the efficacy of the proposed algorithms are corroborated through simulations. These simulations demonstrate that learning the unknown graphons reduces the exploitability effectively.

Related papers

• Amplify Graph Learning for Recommendation via Sparsity Completion [16.32861024767423]
  Graph learning models have been widely deployed in collaborative filtering (CF) based recommendation systems. Due to the issue of data sparsity, the graph structure of the original input lacks potential positive preference edges. We propose an Amplify Graph Learning framework based on Sparsity Completion (called AGL-SC)
  arXiv  Detail & Related papers  (2024-06-27T08:26:20Z)
• A Differentially Private Clustering Algorithm for Well-Clustered Graphs [6.523602840064548]
  We provide an efficient ($epsilon,$delta$)-DP algorithm tailored specifically for such graphs. Our algorithm works for well-clustered graphs with $k$ nearly-balanced clusters.
  arXiv  Detail & Related papers  (2024-03-21T11:57:16Z)
• Learning Regularized Monotone Graphon Mean-Field Games [155.38727464526923]
  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.
  arXiv  Detail & Related papers  (2023-10-12T07:34:13Z)
• Graph Signal Sampling for Inductive One-Bit Matrix Completion: a Closed-form Solution [112.3443939502313]
  We propose a unified graph signal sampling framework which enjoys the benefits of graph signal analysis and processing. The key idea is to transform each user's ratings on the items to a function (signal) on the vertices of an item-item graph. For the online setting, we develop a Bayesian extension, i.e., BGS-IMC which considers continuous random Gaussian noise in the graph Fourier domain.
  arXiv  Detail & Related papers  (2023-02-08T08:17:43Z)
• Learning Graphon Autoencoders for Generative Graph Modeling [91.32624399902755]
  Graphon is a nonparametric model that generates graphs with arbitrary sizes and can be induced from graphs easily. We propose a novel framework called textitgraphon autoencoder to build an interpretable and scalable graph generative model. A linear graphon factorization model works as a decoder, leveraging the latent representations to reconstruct the induced graphons.
  arXiv  Detail & Related papers  (2021-05-29T08:11:40Z)
• Correcting Momentum with Second-order Information [50.992629498861724]
  We develop a new algorithm for non-critical optimization that finds an $O(epsilon)$epsilon point in the optimal product. We validate our results on a variety of large-scale deep learning benchmarks and architectures.
  arXiv  Detail & Related papers  (2021-03-04T19:01:20Z)
• Adaptive Graph Encoder for Attributed Graph Embedding [36.06427854846497]
  Attributed graph embedding learns vector representations from graph topology and node features. We propose Adaptive Graph (AGE), a novel attributed graph embedding framework. We conduct experiments using four public benchmark datasets to validate AGE on node clustering and link prediction tasks.
  arXiv  Detail & Related papers  (2020-07-03T10:20:34Z)
• Learning Sparse Graphons and the Generalized Kesten-Stigum Threshold [21.044900734651627]
  This paper provides an efficient algorithm to learn graphons in the constant expected degree regime. The algorithm is shown to succeed in estimating the rank-$k$ projection of a graphon in the $L$ metric if the top $k$ eigenvalues of the graphon satisfy a generalized Kesten-Stigum condition.
  arXiv  Detail & Related papers  (2020-06-13T18:38:05Z)
• Heuristic Semi-Supervised Learning for Graph Generation Inspired by Electoral College [80.67842220664231]
  We propose a novel pre-processing technique, namely ELectoral COllege (ELCO), which automatically expands new nodes and edges to refine the label similarity within a dense subgraph. In all setups tested, our method boosts the average score of base models by a large margin of 4.7 points, as well as consistently outperforms the state-of-the-art.
  arXiv  Detail & Related papers  (2020-06-10T14:48:48Z)

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.