Multi-Agent Q-Learning Dynamics in Random Networks: Convergence due to Exploration and Sparsity

• URL: http://arxiv.org/abs/2503.10186v1
• Date: Thu, 13 Mar 2025 09:16:51 GMT
• Title: Multi-Agent Q-Learning Dynamics in Random Networks: Convergence due to Exploration and Sparsity
• Authors: Aamal Hussain, Dan Leonte, Francesco Belardinelli, Raphael Huser, Dario Paccagnan,
• Abstract summary: We study Q-learning dynamics in network polymatrix games where the network structure is drawn from random graph models.<n>In each setting, we establish sufficient conditions under which the agents' joint strategies converge to a unique equilibrium.<n>We validate our theoretical findings through numerical simulations and demonstrate that convergence can be reliably achieved in many-agent systems.
• Score: 5.925608009772727
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Beyond specific settings, many multi-agent learning algorithms fail to converge to an equilibrium solution, and instead display complex, non-stationary behaviours such as recurrent or chaotic orbits. In fact, recent literature suggests that such complex behaviours are likely to occur when the number of agents increases. In this paper, we study Q-learning dynamics in network polymatrix games where the network structure is drawn from classical random graph models. In particular, we focus on the Erdos-Renyi model, a well-studied model for social networks, and the Stochastic Block model, which generalizes the above by accounting for community structures within the network. In each setting, we establish sufficient conditions under which the agents' joint strategies converge to a unique equilibrium. We investigate how this condition depends on the exploration rates, payoff matrices and, crucially, the sparsity of the network. Finally, we validate our theoretical findings through numerical simulations and demonstrate that convergence can be reliably achieved in many-agent systems, provided network sparsity is controlled.

Related papers

• Sample Complexity of Linear Regression Models for Opinion Formation in Networks [36.75032460874647]
  We study the study of sample complexity of opinion convergence in networks.<n>Our framework is built on the recognized opinion formation game.<n> Empirical results on both synthetic and real-world networks strongly support our theoretical findings.
  arXiv  Detail & Related papers  (2023-11-04T08:28:33Z)
• Leveraging Low-Rank and Sparse Recurrent Connectivity for Robust Closed-Loop Control [63.310780486820796]
  We show how a parameterization of recurrent connectivity influences robustness in closed-loop settings. We find that closed-form continuous-time neural networks (CfCs) with fewer parameters can outperform their full-rank, fully-connected counterparts.
  arXiv  Detail & Related papers  (2023-10-05T21:44:18Z)
• Stability of Multi-Agent Learning: Convergence in Network Games with Many Players [34.33866138792406]
  We study Q-Learning dynamics and determine a sufficient condition for the dynamics to converge to a unique equilibrium in any network game. We evaluate this result on a number of representative network games and show that, under suitable network conditions, stable learning dynamics can be achieved with an arbitrary number of agents.
  arXiv  Detail & Related papers  (2023-07-26T02:45:02Z)
• How neural networks learn to classify chaotic time series [77.34726150561087]
  We study the inner workings of neural networks trained to classify regular-versus-chaotic time series. We find that the relation between input periodicity and activation periodicity is key for the performance of LKCNN models.
  arXiv  Detail & Related papers  (2023-06-04T08:53:27Z)
• Generalization and Estimation Error Bounds for Model-based Neural Networks [78.88759757988761]
  We show that the generalization abilities of model-based networks for sparse recovery outperform those of regular ReLU networks. We derive practical design rules that allow to construct model-based networks with guaranteed high generalization.
  arXiv  Detail & Related papers  (2023-04-19T16:39:44Z)
• Generative Adversarial Network for Probabilistic Forecast of Random Dynamical System [19.742888499307178]
  We present a deep learning model for data-driven simulations of random dynamical systems without a distributional assumption. We propose a regularization strategy for a generative adversarial network based on consistency conditions for the sequential inference problems. The behavior of the proposed model is studied by using three processes with complex noise structures.
  arXiv  Detail & Related papers  (2021-11-04T19:50:56Z)
• Anomaly Detection on Attributed Networks via Contrastive Self-Supervised Learning [50.24174211654775]
  We present a novel contrastive self-supervised learning framework for anomaly detection on attributed networks. Our framework fully exploits the local information from network data by sampling a novel type of contrastive instance pair. A graph neural network-based contrastive learning model is proposed to learn informative embedding from high-dimensional attributes and local structure.
  arXiv  Detail & Related papers  (2021-02-27T03:17:20Z)
• Continuous-in-Depth Neural Networks [107.47887213490134]
  We first show that ResNets fail to be meaningful dynamical in this richer sense. We then demonstrate that neural network models can learn to represent continuous dynamical systems. We introduce ContinuousNet as a continuous-in-depth generalization of ResNet architectures.
  arXiv  Detail & Related papers  (2020-08-05T22:54:09Z)
• Tractably Modelling Dependence in Networks Beyond Exchangeability [0.0]
  We study the estimation, clustering and degree behavior of the network in our setting. This explores why and under which general conditions non-exchangeable network data can be described by a block model.
  arXiv  Detail & Related papers  (2020-07-28T17:13:59Z)
• Kernel and Rich Regimes in Overparametrized Models [69.40899443842443]
  We show that gradient descent on overparametrized multilayer networks can induce rich implicit biases that are not RKHS norms. We also demonstrate this transition empirically for more complex matrix factorization models and multilayer non-linear networks.
  arXiv  Detail & Related papers  (2020-02-20T15:43:02Z)
• Time-invariant degree growth in preferential attachment network models [8.929656934088989]
  We study the degree dynamics in a class of network models where preferential attachment is combined with node fitness and aging. We show that it is self-consistent only for two special network growth forms: the uniform and exponential network growth.
  arXiv  Detail & Related papers  (2020-01-22T16:31:11Z)

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.