A formal model for multiagent Q-learning on graphs

Understanding the dynamics of multi-agent learning has long been an important research topic. Existing research has focused mostly on 2-agent games or well-mixed populations. However, in real-world multi-agent systems, agents often interact in spatially or socially structured networks (or graphs). In this paper, we examine the dynamics of multi-agent Q-learning on graphs. Combining mean-field theory and combinatorics analysis, we present a new analytical approach to formally describe the time evolution of Q-values in the system with a topological structure. Through extensive numerical simulations, we show that our theory consistently provides an accurate depiction of the Q-learning dynamics across different typical games, initial conditions, and various graph structures, encompassing regular graphs, scale-free graphs, and random graphs. Moreover, we show that when comparing regular graphs to other types of graphs with the same average degree, the differences in the system evolution are largely attributed to the behaviors and Q-values of agents with lower degrees.