Reinforcement Learning for SBM Graphon Games with Re-Sampling

• URL: http://arxiv.org/abs/2310.16326v1
• Date: Wed, 25 Oct 2023 03:14:48 GMT
• Title: Reinforcement Learning for SBM Graphon Games with Re-Sampling
• Authors: Peihan Huo, Oscar Peralta, Junyu Guo, Qiaomin Xie, Andreea Minca
• Abstract summary: We develop a novel learning framework based on a Graphon Game with Re-Sampling (GGR-S) model. We analyze GGR-S dynamics and establish the convergence to dynamics of MP-MFG.
• Score: 4.6648272529750985
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Mean-Field approximation is a tractable approach for studying large population dynamics. However, its assumption on homogeneity and universal connections among all agents limits its applicability in many real-world scenarios. Multi-Population Mean-Field Game (MP-MFG) models have been introduced in the literature to address these limitations. When the underlying Stochastic Block Model is known, we show that a Policy Mirror Ascent algorithm finds the MP-MFG Nash Equilibrium. In more realistic scenarios where the block model is unknown, we propose a re-sampling scheme from a graphon integrated with the finite N-player MP-MFG model. We develop a novel learning framework based on a Graphon Game with Re-Sampling (GGR-S) model, which captures the complex network structures of agents' connections. We analyze GGR-S dynamics and establish the convergence to dynamics of MP-MFG. Leveraging this result, we propose an efficient sample-based N-player Reinforcement Learning algorithm for GGR-S without population manipulation, and provide a rigorous convergence analysis with finite sample guarantee.

Related papers

• Provably Efficient Information-Directed Sampling Algorithms for Multi-Agent Reinforcement Learning [50.92957910121088]
  This work designs and analyzes a novel set of algorithms for multi-agent reinforcement learning (MARL) based on the principle of information-directed sampling (IDS) For episodic two-player zero-sum MGs, we present three sample-efficient algorithms for learning Nash equilibrium. We extend Reg-MAIDS to multi-player general-sum MGs and prove that it can learn either the Nash equilibrium or coarse correlated equilibrium in a sample efficient manner.
  arXiv  Detail & Related papers  (2024-04-30T06:48:56Z)
• Model-Based RL for Mean-Field Games is not Statistically Harder than Single-Agent RL [57.745700271150454]
  We study the sample complexity of reinforcement learning in Mean-Field Games (MFGs) with model-based function approximation. We introduce the Partial Model-Based Eluder Dimension (P-MBED), a more effective notion to characterize the model class complexity.
  arXiv  Detail & Related papers  (2024-02-08T14:54:47Z)
• On the Statistical Efficiency of Mean-Field Reinforcement Learning with General Function Approximation [20.66437196305357]
  We study the fundamental statistical efficiency of Reinforcement Learning in Mean-Field Control (MFC) and Mean-Field Game (MFG) with general model-based function approximation. We introduce a new concept called Mean-Field Model-Based Eluder Dimension (MF-MBED), which characterizes the inherent complexity of mean-field model classes.
  arXiv  Detail & Related papers  (2023-05-18T20:00:04Z)
• Joint Graph Learning and Model Fitting in Laplacian Regularized Stratified Models [5.933030735757292]
  Laplacian regularized stratified models (LRSM) are models that utilize the explicit or implicit network structure of the sub-problems. This paper shows the importance and sensitivity of graph weights in LRSM, and provably show that the sensitivity can be arbitrarily large. We propose a generic approach to jointly learn the graph while fitting the model parameters by solving a single optimization problem.
  arXiv  Detail & Related papers  (2023-05-04T06:06:29Z)
• A General Framework for Sample-Efficient Function Approximation in Reinforcement Learning [132.45959478064736]
  We propose a general framework that unifies model-based and model-free reinforcement learning. We propose a novel estimation function with decomposable structural properties for optimization-based exploration. Under our framework, a new sample-efficient algorithm namely OPtimization-based ExploRation with Approximation (OPERA) is proposed.
  arXiv  Detail & Related papers  (2022-09-30T17:59:16Z)
• Soft Hierarchical Graph Recurrent Networks for Many-Agent Partially Observable Environments [9.067091068256747]
  We propose a novel network structure called hierarchical graph recurrent network(HGRN) for multi-agent cooperation under partial observability. Based on the above technologies, we proposed a value-based MADRL algorithm called Soft-HGRN and its actor-critic variant named SAC-HRGN.
  arXiv  Detail & Related papers  (2021-09-05T09:51:25Z)
• Efficient Model-Based Multi-Agent Mean-Field Reinforcement Learning [89.31889875864599]
  We propose an efficient model-based reinforcement learning algorithm for learning in multi-agent systems. Our main theoretical contributions are the first general regret bounds for model-based reinforcement learning for MFC. We provide a practical parametrization of the core optimization problem.
  arXiv  Detail & Related papers  (2021-07-08T18:01:02Z)
• Continual Learning with Fully Probabilistic Models [70.3497683558609]
  We present an approach for continual learning based on fully probabilistic (or generative) models of machine learning. We propose a pseudo-rehearsal approach using a Gaussian Mixture Model (GMM) instance for both generator and classifier functionalities. We show that GMR achieves state-of-the-art performance on common class-incremental learning problems at very competitive time and memory complexity.
  arXiv  Detail & Related papers  (2021-04-19T12:26:26Z)
• Robust Finite Mixture Regression for Heterogeneous Targets [70.19798470463378]
  We propose an FMR model that finds sample clusters and jointly models multiple incomplete mixed-type targets simultaneously. We provide non-asymptotic oracle performance bounds for our model under a high-dimensional learning framework. The results show that our model can achieve state-of-the-art performance.
  arXiv  Detail & Related papers  (2020-10-12T03:27:07Z)

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.