Convergence and Connectivity: Dynamics of Multi-Agent Q-Learning in Random Networks
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911438822440960 |
|---|---|
| author | Leonte, Dan Hussain, Aamal Huser, Raphael Belardinelli, Francesco Paccagnan, Dario |
| author_facet | Leonte, Dan Hussain, Aamal Huser, Raphael Belardinelli, Francesco Paccagnan, Dario |
| contents | 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ős-Rényi 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 interaction between network agents. We validate our theoretical findings through numerical simulations and demonstrate that convergence can be reliably achieved in many-agent systems, provided interactions in the network are controlled. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_10186 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Convergence and Connectivity: Dynamics of Multi-Agent Q-Learning in Random Networks Leonte, Dan Hussain, Aamal Huser, Raphael Belardinelli, Francesco Paccagnan, Dario Multiagent Systems Artificial Intelligence Computer Science and Game Theory Dynamical Systems 93A16, 91A26, 91A68, 58K35 G.3; J.4; F.2.2 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ős-Rényi 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 interaction between network agents. We validate our theoretical findings through numerical simulations and demonstrate that convergence can be reliably achieved in many-agent systems, provided interactions in the network are controlled. |
| title | Convergence and Connectivity: Dynamics of Multi-Agent Q-Learning in Random Networks |
| topic | Multiagent Systems Artificial Intelligence Computer Science and Game Theory Dynamical Systems 93A16, 91A26, 91A68, 58K35 G.3; J.4; F.2.2 |
| url | https://arxiv.org/abs/2503.10186 |