A Formal Model for Multiagent Q-Learning Dynamics on Regular Graphs

1 Introduction

Multi-agent learning has recently received much attention, as learning (in particular, reinforcement learning) has found wide applications in many real-world multi-agent systems (MASs), such as multiplayer online games [Brown and Sandholm, 2019], traffic control [Zhou et al., 2019], motion coordination [Liu et al., 2021a] and online auction [Jin et al., 2018]. However, while learning under single-agent settings has gained a strong theoretical foundation, learning under multi-agent settings has still remained an open problem [Bailey and Piliouras, 2019].

One of the main foci of previous theory about multiagent learning is to formalize and examine the learning dynamics [Bloembergen et al., 2015]. As Tuyls and Parsons voiced [2007], this not only provides a better theoretical understanding of existing algorithms, but also facilitates many important tasks, such as parameter tuning and the design of new algorithms.

Early works in this line of research mostly consider that there are only few learning agents in a MAS [Panait et al., 2008; Hennes et al., 2009; Galstyan, 2013]. In the pioneering work, Tuyls et al. [2003] developed a system of replicator equations to model the policy (or strategy) dy-

∗Corresponding Author

University

namics of two Q-learning agents in repeated 2-player matrix games. Subsequent studies generalized this evolutionary game-theoretic approach to other learning algorithms, such as FAQ-learning, infinitesimal gradient ascent and regret minimization; as such, formal models for the dynamics of two agents that apply these learning algorithms have been proposed [Kaisers and Tuyls, 2010; Klos et al., 2010].

In this paper, in contrast to the 2-agent settings considered in most previous works, we consider that there are a large number of Q-learning agents in a MAS and that the underlying topology is a regular graph. Recently, Hu et al. [2019] focused on a similar setting in which there are infinitely many Q-learning agents in a MAS, and they developed a FokkerPlanck equation-based model to characterize the population dynamics. However, we note that the underlying topology of their MASs are essentially well-mixed populations; put differently, for each game-play, every agent interact with another agent that is randomly drawn from the population.

The study of learning dynamics on graphs is important. Compared with all-to-all interactions in well-mixed populations, it is more realistic to assume some constraints in the interactions between agents, due to the high communication costs between remote agents in many practical scenarios, such as sensor networks, power grids, and unmanned vehicular networks [Zhang et al., 2021; Delgado, 2002]. Moreover, multi-agent learning on graphs has recently gained growing interest [Zhang et al., 2018; Wang et al., 2018; Liu et al., 2021b]. Previous findings, which rely on agentbased simulations, suggest that topological structure can significantly influence system evolution [Villatoro et al., 2011; Hu and Leung, 2017; Sen and Sen, 2009].

The model of Hu et al. [2019] was proposed for learning in well-mixed populations; thus, it is by nature inappropriate for learning on regular graphs, which features constrained interactions among agents. To address this knowledge gap, we develop a new formal model for the learning dynamics on regular graphs. More specifically, we consider that given a regular graph with degree k, each vertex represents a Q-learning agent and agents learn from repeated symmetric games with their neighbours on the graph. To provide an accurate description for the learning dynamics, we first focus on the Qvalues dynamics of individual agents. By capturing the effects of different neighbour configurations of a regular graph, we derive a differential equation that describes the change of Q-values for individual agents. Then, following the approach of Hu et al. [2019], we derive a system of equations, one of which is a partial differential equation, to model the time evolution of the Q-values distribution of the system. To the best of our knowledge, our model is the first formal model for the dynamics of multiagent learning on regular graphs.

In the experiments, we consider two specific types of regular graphs: translational symmetric lattice and random regular graphs. We validate our model by showing that the Qlearning dynamics predicted by our model match the actual dynamics in agent-based simulations across different games and different regular graphs. In addition, we show that in prisoner's dilemma games, as the temptation to defect and the degree of the regular graph increases, Q-learning agents are less likely to cooperate. However, if the temptation to defect is low, the effects of the degree of the regular graph becomes insignificant.

2 AMultiagent Q-Learning Framework on Regular Graphs

2.1 Agent Interaction on Graphs

The interaction topology of agents is generalized by an undirected connected graph G(N, E, B), where N = {1, . . . , n} is the vertex set (each agent occupies a vertex), E ⊆ N ×N is the edge set, and B = [bij ]n×n is the adjacency matrix. An edge denoted by eij = (i, j), i, j ∈ N means that vertex i is connected to vertex j. Define the neighbor set of vertex i as Ni = {j : eij ∈ E, j ̸= i}. In the adjacency matrix B, all diagonal elements bii are zero, off-diagonal elements bij = 1 if and only if eij ∈ E, otherwise, bij = 0. In this paper, we consider k-regular graphs such that each agent has exactly k neighbors.

Given a two-player symmetric game G with a set A of actions. The multiagent Q-learning on regular graphs proceeds as follows. For every time step t, an agent i chooses an action aj ∈ A and plays the game G with each of its k neighbors. The immediate reward ri t (aj) of agent i is averaged over all the k games it played. Based on the immediate rewards, agents adapt their strategies using Q-learning. We summarize the learning framework in Algorithm 1.

2.2 Two-player Symmetric Game

A symmetric normal form game is defined as G = ⟨A,R⟩ where A = {a1, . . . , am} is the available action set for each agent and R is the payoff matrix of the row player

where raiaj denotes the reward if the row player plays action ai and the column player plays action aj .

2.3 Q-Learning with Boltzmann Exploration

For a Q-learning agent i, it maintains a vector of Q-values Qi = [Qi (a1), . . . ,Qi (am)]⊤ which estimates the reward of Algorithm 1 A Multiagent Q-Learning Framework on Regular Graphs Require: a structured population G(N, E, B), a symmetric normal form game G, the maximum time step T

• 1: while t < T do
• 2: for each agent i ∈ N do
• 3: Agent i selects an action a ∈ A according to its policy
• 4: end for
• 5: for each agent i ∈ N do
• 6: for each neighbor j ∈ Ni do
• 7: Agents i and j play the game G using their selected actions respectively
• 8: end for
• 9: Agent i receives a payoff ri t (a) that is averaged over the k games it plays
• 10: end for
• 11: for each agent i ∈ N do
• 12: Agent i updates its Q-value:
• 13: end for

• 14: t ← t + 1
• 15: end while

using each action. The agent policy is defined by

where xit (aj), ∀aj ∈ A, denote the probability of agent i choosing action aj at time t. Agents choose their actions based on Boltzmann probability

where β is the Boltzmann exploration temperature. When β is small, the agent tends to be more exploratory. If β = 0, agents will choose their actions randomly. If β →∞, agents will become greedy (that is, they choose the action with the highest Q-value).

For agent i, if it plays action aj at time t, it will update the Q-value of action aj as follows

where α is the learning rate and ri t (aj) is the immediate reward.

3 Modelling Q-Learning Dynamics on Regular Graphs

In this section, we derive the theoretical model of multiagent Q-learning on regular graphs and use a set of equations to describe the system evolution.

3.1 Dynamics of Q-values for Individual Agents

First, let us focus on an arbitrary agent i. The reward of agent i depends on its own action and the actions of its neighbors.

With a slight abuse of notation, we denote the use of action ai ∈ A by ai = [0, . . . , 1, . . . , 0], a one-hot vector with the i-th component equaling to 1 and others 0. Then the payoff of using action ai against the opponent's using action aj is

Define the action of agent i as ai , and the joint action of its neighbors as a-i . Then in every round the agent i gets reward

where Ni is the neighbor set of agent i. Let the number of neighbors using the action ai be kai . Then Equation (4) can be expressed as

where [ka1 , . . . , kam ]⊤ = ∑∀j∈Ni aj describes the number of actions adopted by neighbors. We define γ ≜ [ka1 , . . . , kam ]⊤ as the neighbor configuration.

Suppose that at time t, an agent i uses the j-th action and its neighbor configuration is γ = [ka1 , . . . , kam ]⊤. The change of its Q-values Qt in the j-th dimension can be expressed as

where the learning rate α and Boltzmann exploration temperature β are fixed for all agents. Moreover, for symmetric normal form games, the payoff is independent of the roles of individual agents. Therefore, at time step t, how fast agent i changes its Q-values should be attributed to its current Qvalues Qt and its neighbor configuration γ.

Next we consider the probability that the agent has a certain neighbor configuration γ. Using the mean-field theory, for an arbitrary agent in the population, its probability of using action aj can be approximated as

where

is the average probability of using action aj in the population.

For a given neighbour configuration γ = [ka1 , . . . , kam ]⊤, we calculate its probability as

where C denotes a combination. We observe that the vector γ is subject to multinomial distribution.

3.2 Evolution of the Distribution of Q-values

To capture the evolution of the Q-values in a population on regular graphs, we first derive a dynamic equation for a certain configuration of neighbours by adopting the approach proposed by Hu et al. [2019], and then obtain the dynamic equation considering all possible configurations of neighbours.

1 Consider a m-dimension Q-value space Rm, in which m is the number of available actions. Following the approach of Hu et al. [2019], we denote each agent in the system with a particle in this space such that the change of Q-values can be viewed as the transport of particle (or agent) mass in the space. Denote the distribution of agent mass in this space by the joint density function p(Qt, t), i.e., p(Qt, t) intuitively means the fraction of agents having the Q-values Qt in the system. Then, for an arbitrary infinitesimal box in the space, whose volume equals to dV , the number of agents in this box at time t is np(Qt, t)dV , where n is the total number of agents.

The change of the number of agents in this box from time t to time t + dt can be expressed by the difference between the number of agents entering the box and the number of agents leaving the box

Since agents adopting the action aj are only allowed to update Qt(aj), the change of the number of agents in this box equals to the sum of changes along k different directions. For a particular configuration of neighbours, Equation (10) can be rewritten as

A full derivation of the Equation (11) can be found in the Supplementary Material.

The right-hand side of Equation (11) is a function determined by the neighbor configuration γ, and we show the graphical demonstration for k = 2 and m = 2 in Figure 2. As the neighbor configuration is subject to multinomial distribution, the term ∂p(Qt,t) ∂t for total population can be written as the expectation of a function of γ as follows

where Γ is the set of all possible neighbour configurations γ given the average degree k and the number m of available actions. By this equation, the change of density function p(Qt, t) is determined by the current density function p(Qt, t), the velocity vj(Qt, γ) and the policy xt(aj,Qt(aj)). It is worth noting that the the policy of an agent depends only on its Q-values. Therefore, the mean policy ¯xt follows

Then, the evolutionary dynamics of an infinite population in which agents interact with local neighbours can be modelled by the following system of equations

3.3 Connection to the Previous Model

For a large number of neighbours (i.e. a large average degree k), the limit of multinomial distribution with k random variables can be approximated by (k - 1)-dimension normal distribution,

Thus, as the number of neighbours is sufficiently large, our model coincides with the model reported by Hu et al. [2019].

4 Experiments

4.1 Experimental Settings

Game Configurations. We consider three widely used symmetric normal form games including prisoner's dilemma (PD), hawk dove (HD) and common interest (CI) games to verify the effectiveness of our model with different settings.

The action set and payoff matrices for these three games are summarized as follows.

In PD game, although mutual cooperation is Pareto dominant, mutual defection is the unique Nash equilibrium. In HD game, the Nash equilibrium is that one agent adopts the "hawk" policy and the other adopts the "dove" policy. In CI game, there are two Nash equilibria, i.e.,(X,X) and (Y,Y). Choosing the optimal joint action (Y, Y ) will lead to the highest payoff, while choosing the joint action (X,X) will lead to the suboptimal payoff.

Regular Graphs. We consider two typical types of regular graphs with degree k:

• Translational Symmetry Lattice. A regular graph is translational symmetric if the graph is constructed by translational splicing of the smallest repeating unit (a node and its edges). We provide examples of this type of regular graphs in Figure 5 (a). The graph is a ring if
• k = 2, a honeycomb if k = 3, a square lattice if k = 4, and a triangular if k = 6.
• Random Regular Graph. A random regular graph is a random graph where all nodes have the same degree. Here, we consider random regular graphs that have no self-loops and allow at most one edge between any two nodes. As shown in Figure 5 (b), a random regular graph is in general not translational symmetric.

Learning Parameters. The exploration temperature β is set to 2 and the learning rate α is set to 0.4. Unless otherwise specified, we set the initial Q-values to zero for all agents which means that agents take their actions randomly.

Agent-based Simulations. In the simulations, there are 100 agents, and agents interact and adapt their strategies according to Algorithm 1. To avoid the finite-size effects and randomness, the presented simulation results are averaged over 100 independent runs.

4.2 The Evolution of Agent Behaviors

We first focus the case that degree k = 4. Unless stated otherwise, we consider the translational symmetric lattice in the simulations for comparison. Figure 3 shows the time evolution of the mean Q-value and the mean policy of the population, as predicted by our model and observed in the simulations. It is clear that our model precisely predicts the time evolution across three different games.

Our model also reflects the differences in Q-learning in different games. In PD games, defection becomes the dominant policy which is consist with the prediction of classic game theory. However, some cooperation still exists. For HD games and CI games, it is shown that the population eventually converges to the evolutionary stable strategy.

In Figure 4, we present the Q-value density distribution for PD games. The first row is the theoretical result, and the second row is the simulation result. For ease of presentation, we focus on three time steps: t = 0, 5 and 100. It is shown that given the same initialization (t = 0), the theoretical predictions on the Q-value distributions are consistent with the counterparts observed in the simulations, no matter whether the system has stabilized (t = 100) or not (t = 5).

a. Translational Symmetry Lattice

...

Figure 5: Examples of Translational Symmetry Lattice and Random Regular Graph.

To further verify the accuracy of our model, in the following, we contrast the theoretical predictions made by our model and the simulation results obtained from translational symmetry lattice and random regular graph. In Figure 6, we focus on PD games. However, different than the PD game shown in Section 4.1, we consider that there is a parameter b in the payoff matrix such that

where the payoff obtained by unilateral defection is controlled by b representing the temptation to defect. We vary the value of b from 1.0 to 2.0. Obviously, if b is equal to 1, players will get the same payoff by choosing to cooperate or defect. As the value of b increases, players will get higher payoffs by choosing to defect. As shown in Figure 6, with the increase of b, Q-learning agents are significantly less likely to cooperate.

Moreover, we observe from Figure 6 that how likely Qlearning agents choose cooperate are also under the effect of the degree k. Given the same temptation to defect (denoted by b), agents are more likely to cooperate in regular graphs where agents have few neighbours (i.e. a small value of k). However, in general, this effect is marginal when the temptation to defect is low (i.e. a small value of b).

Note that when k = 99, our theoretical model approximates the model of Hu et al. [2019], as analyzed in Section 3.3. Therefore, Figure 6 also shows that the previous model fails to capture how regular graphs with different degrees affect Q-learning dynamics.

5 Conclusions

1 In the paper, we propose the first formal model for Q-learning dynamics on regular graphs. By capturing the influence of different neighbour configurations on the learning of agents, we derive a system of differential equations to describe the evolution of the Q-value distribution of the system. To verify the accuracy of our model, we contrast the theoretical predictions of our model with agent-based simulation results. Under three typical types of symmetric normal form games, we show that our model accurately describes the dynamics of the mean Q-values and the mean policy. Moreover, our model reveals that in PD games, as the temptation to defect and the degree of the regular graph increases, Q-learning agents are less likely to cooperate. However, in general, when the temptation to defect is low, the effect of the degree of the regular graph becomes insignificant.

Acknowledgments

This research was supported by the National Science Fund for Distinguished Young Scholarship of China (No. 62025602), the National Key RD Program of China (No. 2018AAA0100900), the National Natural Science Foundation of China ( Nos. U1803263, 11931015, 62066045 and 62866039), Key Technology Research and Development Program of Science and Technology-Scientific and Technological Innovation Team of Shaanxi Province (Grant No. 2020TD-013), the Natural Science Foundation of Yunnan Province (No. 20190FB083) and the XPLORER PRIZE.