Convergence And Connectivity: Dynamics Of Multi-agent Q-learning In Random Networks

Abstract

Beyond specific settings, many multi-agent learning algorithms fail to converge to an equilibrium solution, instead displaying 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 normal-form games where the network structure is drawn from classical random graph models. In particular, we focus on the Erd\H\{o\}s-R\'enyi model, which is used to analyze connectivity in distributed systems, and the Stochastic Block model, which generalizes the above by accounting for community structures that naturally arise in multi-agent systems. 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 probabilities of interactio

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyleonte2025convergence

Related papers

• On The Stability Of Learning In Network Games With Many Players (2024)0.00
• Asymptotic Convergence And Performance Of Multi-agent Q-learning Dynamics (2023)0.00
• Stability Of Multi-agent Learning In Competitive Networks: Delaying The Onset Of Chaos (2023)0.00
• Beyond Strict Competition: Approximate Convergence Of Multi Agent Q-learning Dynamics (2023)0.00
• Exploration-exploitation In Multi-agent Competition: Convergence With Bounded Rationality (2021)0.00
• Convergence Analysis Of Gradient-based Learning With Non-uniform Learning Rates In Non-cooperative Multi-agent Settings (2019)0.00
• The Bounds Of Algorithmic Collusion; \(q\)-learning, Gradient Learning, And The Folk Theorem (2024)0.00
• Chaos Persists In Large-scale Multi-agent Learning Despite Adaptive Learning Rates (2023)0.00