Modelling the Dynamics of Multi-Agent Q-learning: The Stochastic Effects of Local Interaction and Incomplete Information

1 Introduction

A multiagent system (MAS) concerns multiple intelligent agents interacting in a shared environment. MASs can be used to model many complex scenarios, such as urban traffic flow [Wang et al., 2021], multi-robot coordination [Campbell and Wu, 2011], distributed sensing [Lesser et al., 2003] and load balancing [Keshvadi and Faghih, 2016].

Multiagent reinforcement learning (MARL) has recently received much attention [Bloembergen et al., 2015; Lanctot et al., 2017; Leibo et al., 2017]. However, the theory underlying MARL is far from being understood. In seminal work, Tuyls et al. [2003; 2006] formally model the dynamics of Qlearning [Watkins and Dayan, 1992] in 2-player games and develop the selection-mutation model. Based on this model, Kianercy and Galstyan [2012] provide a comprehensive characterization of the rest point structure for different 2-player games. Gomes and Kowalczyk [2009] develop another formal model for Q-learning with ϵ-greedy exploration in 2player games. Wunder et al. [2010] show that when ϵ-greedy exploration is applied, the Q-learning dynamics may exhibit chaotic behaviors. However, all these earlier works focus on 2-agent interaction scenarios.

∗Corresponding Author.

More recently, there have been some works reported on modeling the Q-learning dynamics beyond the 2-agent setting. A pioneer work that we notice is that of Hu et al. [2019], which models the population dynamics of Q-learning agents according to the concurrent learning (CL) protocol under an n-agent setting with n → ∞. Using mean field theory [Weiss, 1907], the authors capture the population dynamics by a system of three equations.

In this work, we aim at formally modelling the Q-learning dynamics in the scenarios that agents abide by the generalized social learning (GSL) protocol, a generalized version of the social learning (SL) protocol [Sen and Airiau, 2007]. Specifically, at every time step, each agent forms pairs with m ≥ 1 randomly chosen opponents; then each pair of agents simultaneously plays a 2-player symmetric game and learns the strategy based on the reward from the game. SL and CL are the extreme cases of GSL, in which m = 1 and m → ∞, respectively.

However, unlike CL in the work of Hu et al. [2019], we consider that in GSL each agent plays with a finite number (m) of opponents, instead of infinitely many, at each time step. That is, our work tackles the more common scenarios in which agents have only local and incomplete information about the system, instead of complete and global information as in the ideal scenario in the work of Hu et al. [2019].

The (generalized) social learning protocol is significant as it is widely used in the literature of research into norm and cooperation emergence [Eccles et al., 2019; McKee et al., 2020; Hu and Leung, 2017; Hao and Leung, 2013; Baker, 2020; Anastassacos et al., 2020]. Lacking proper mathematical underpinnings, all these previous studies have had to rely on experimental studies using agent-based simulations.

By adopting the GSL protocol, we have to deal with the stochasticity in the learning process of each agent, which is not present in CL. This is because (i) an agent's m opponents in games are randomly chosen and they change over time, and (ii) the exploration mechanism of Q-learning generally presupposes that the action choice is stochastic. Such stochasticity has not been captured by the previous model of Hu et al. [2019], which focuses on depicting the change of expectation of Q-values under the CL protocol and thus is effectively deterministic. To properly characterize these stochastic effects on Q-learning dynamics under the GSL protocol, we carefully model the Q-values dynamics of each individual agent as a system of stochastic differential equations (SDE). Specifically, we approximate the Q-values dynamics by Gaussian moment closure method and evaluate the first and second order moments of the change in Q-values for each individual agent. As such, given d available actions for each agent, we model the Q-values dynamics of each agent using a d-dimensional Wiener process such that the drift and diffusion of the Wiener process depend on the Q-values, the exploration mechanism and the probability density function (PDF) of Q-values in the population. As a result of the learning of individual agents, the PDF of Q-values in the population also evolve accordingly. Based on the SDE, we express the time evolution of the PDF of Q-values in the population with a Fokker-Planck equation (FPE). Therefore, our formal model for the Q-learning dynamics under the GSL protocol is given by two coupled equations: the SDE that captures the Q-values dynamics of each agent and the FPE that captures the Q-values dynamics of the entire population.

In the experiments, we consider four canonical 2-player symmetric games: prisoner's dilemma, stag hunt, hawkdove and rock-paper-scissors. We show that across different games and initial Q-value settings, our new model always provides a significantly more accurate description of the learning dynamics under the GSL protocol than the model of Hu et al. [2019], particularly when the number (m) of opponents is small (Figure 1). Even when the number (m) of opponents tends to infinity, which is equivalent to the CL protocol, our new model still has a better accuracy (Figure 2). Moreover, our model reveals that different values of m, which determines the completeness of information each agent has, can lead to qualitatively different Q-learning dynamics (Figure 4 in the appendix) and even outcomes (Figure 3).

Our results clearly indicate that the effects of local interactions and incomplete information on multiagent Q-learning are non-trivial. This provides theoretical evidence for the previous findings that rely on agent-based simulations [Hao and Leung, 2013; Yu et al., 2013]. To aid investigations on such effects, our model lays the mathematical underpinnings and can provide insights that are unable to obtain using the previous model [Hu et al., 2019]. Therefore, our model is an important theoretical contribution towards a better understanding of multiagent Q-learning.

2 Preliminaries

Throughout this paper, we denote a column vector x ∈ ℜd as (x1, ..., xd).

2.1 Symmetric Games

Conventionally, a 2-player-d-action normal-form game involves a row player and a column player, each of which has a set of d available actions to choose from. During game plays, the two players simultaneously choose an action and receive an immediate payoff (or reward) based on their joint action choices. Formally, a 2-player-d-action game can be represented by two payoff matrices (Urow and Ucolumn) as follows:

where each element represents the immediate payoff of the row or column player given joint action choices. The game is symmetric if (i) both the players have the same set of available actions, and (ii) the resulting payoffs depend not on the roles of the players, but only on their joint action choices, i.e. Urow = U ⊤ column . Let us define U := Urow = U ⊤ column . For any player, suppose that it chooses action ai and its opponent chooses action aj , its immediate payoff denoted by r is given by

where ei and ej represent basis vectors such that ei = (0...1...0) with only the ith element equaling 1.

2.2 Q-Learning and Boltzmann Exploration

Q-learning is a reinforcement learning algorithm. It is defined in a Markov decision process (MDP) ⟨S,A, T,R⟩, where S is a set of states, A is a set of the available action, T : S × A → P(S) is a state transition probability function, and R : S × A → ℜ is a reward (or payoff) function. A Qlearning agent maintains a Q-value for each state-action pair (s, a) to estimate the expected reward of using each action a ∈ A under each state s ∈ S. Suppose that at a given time step t, the agent is in state s and selects an action ai, we denote the corresponding Q-value as Qti (s) := Qt (s, ai). Let rt be the immediate reward it receives as the new state becomes s′ . The agent updates its Q-value for the state-action pair (s, ai) as follows:

where Qt+1 i (s) is the updatedQ-value, α ∈ (0, 1) is the learning rate, γ is the discount factor, and maxaj∈AQtj (s′ ) estimates the maximum reward after state transition. For symmetric games, since there is no state transition in every play of the games, Equation (2) is simplified to

A Q-learning agent selects its action based on its Q-values and the exploration mechanism that it applies. Let xt = (xt1 , ..., xtd ) (conventionally referred to as the policy) be a point in a d-1 probability simplex where xtk is the probability of selecting action ak given the current Q-values at time t. For Boltzmann exploration, the probability that an agent uses an action ai at time t is given by

where τ is a parameter known as the inverse of the temperature. The agent is in pure exploration (randomly taking each action) when τ is 0, and in pure exploitation (taking the action with the highest Q-value) when τ → ∞.

Algorithm 1 Generalized Social Learning Protocol

Input: N, m, T, α, τ 1: create and initialise Agents[0] to Agents[N -1] 2: for time = 1 to T do 3: for all agent in Agents parallel do 4: agent.genAction() 5: end for 6: assignments = gameAssignment(N,m) 7: for all am in assignments parallel do 8: playGame(Agents[am[0]], Agents[am[1]]) 9: end for 10: for all agent in Agents parallel do 11: agent.train(α, τ) according to equation (6) 12: end for 13: end for

3 A Formal Model of Population Dynamics for Large-Scale Multiagent Q-learning

In this section, we propose a formal model of population dynamics for large-scale multiagent systems in which the interaction protocol is a generalized version of social learning [Sen and Airiau, 2007]. We first revisit the model proposed by Hu et al. [2019], and point out an inadequacy of their model in this scenario. We then develop a formal model that rectifies this inadequacy.

3.1 The Generalized Social Learning (GSL) Protocol

Social learning (SL) [Sen and Airiau, 2007] is a widely adopted protocol in the multiagent reinforcement learning literature [Eccles et al., 2019; McKee et al., 2020; Baker, 2020; Anastassacos et al., 2020]. Consider a large population of N Q-learning agents, where N tends to infinity. The social learning (SL) protocol prescribes that agents learn their strategies during repeated local interactions with different agents. Specifically, at each time step t, each agent is paired up with a randomly chosen opponent to play a 2-player symmetric game. All these games are played simultaneously and independently. Before a game play, each agent selects an action based on its Q-values and the exploration mechanism. During the game play, each pair of agents take actions simultaneously and receive immediate payoffs. After the game play, each agent updates the Q-value of the action it takes independently.

In this paper we consider generalized social learning (GSL), in which each agent will instead choose an action, play with m ≥ 1 randomly chosen opponents and update the Q-value of the chosen action based on the averaged rewards. We present the pseudocode of this interaction protocol in Algorithm 1. The canonical social learning is a special case when we consider m = 1, while the concurrent learning (CL) protocol considered by Hu et al. [2019] is another special case with m → ∞.

3.2 Formalizing the Q-Learning Dynamics under the Social Learning Protocol

In the concurrent learning (CL) scenario studied in Hu et al. [2019], each agent has global interactions, that is, with all the other (infinitely many) agents, at every time step. Hence each agent's learning dynamics can be abstracted by that of its interaction with a virtual mean field agent, and the population dynamics can be described by a system of deterministic equations. A consequent shortcoming in their model is that the stochasticity arising from each agent's local interactions with only m randomly chosen opponents is not captured. As we shall show in Section 4, the population behaviour in the 'ideal' situation as predicted by their model can significantly deviate from the actual one when agents are learning through local interactions rather than global interactions, particularly when the value of m is small.

Change of Q-values with respect to time. Adopting the notations used by Hu et al. [2019], we denote the vector of Q-values of an arbitrary agent by Qt = (Qt1 , . . . ,Qtd ) such that each agent is represented by its Q-value vector in a ddimensional space. Let p(Qt ) : ℜd → ℜ be the probability density function (PDF) that represents the density of agents having certain Q-values at time step t. We denote the action distribution in the population by yt = (yt1 , ..., ytd ), where yt i is the proportion of agents that take action ai at time t. Given the PDF of agents at time t, we have

where xti is given by Equation (4) for Boltzmann exploration. The change ∆Qt in Q-values depends on the immediate reward jointly determined by the agent's action and its opponent's action. Let ai be the action used by the agent and aj1 , aj2 , . . . , ajm be the actions used by its m opponents, by Equation (1) and (3), we have

Note that ∆Qtk = 0 for any other action ak not used. Consider the change in Q-values in continuous time, where ∂tQti := ∂Qti ∂t =∆Qti , we have

where t ∈ ℜ.

Moment closure approximation of rate of changes of Qvalues. From this point we shall apply the moment closure method [Goodman, 1953; Whittle, 1957] to approximate ∂tQt = (∂tQt1 , ..., ∂tQtd ). In a nutshell, the moment closure method takes the cumulant-generating function of ∂tQt

where i = √-1, κi, κi,j, κi,j,k, . . . are cumulants, and sets the 3rd and higher order cumulants to zero. In other words, ∂tQt is approximated by a multivariate Gaussian distribution. Hence, it is expressed by the following stochastic process

where µt = E[∂tQt ] is the mean vector, and Σt = [σtkl ] ∈ ℜd×d is the covariance matrix with σtkk = Var(∂tQtk ) being the variance of ∂tQtk and σtkl = Cov(∂tQtk , ∂tQtl ) the covariance between ∂tQtk and ∂tQtl . W t = (W t 1 , ...,W t d ) is the standard d-dimensional Wiener process. Note that Σt is positive definite.

Calculation of the mean vector and the covariance matrix. For the particular setting we consider, the value of µt and Σt are derived in the following. From Equation (7), it is clear that ∂tQt depends on the agent's action and its opponents' action. Let ai be the agent's action chosen by the policy xt and aj1 , ..., ajm be the m opponents' actions determined by the action distribution yt in the population, and zt = (0...1...0) and ξth = (0...1...0), h = 1, ...,m the corresponding one-hot vectors. Let ζ t = ∑h ξth , we have zt |xt ∼ multinomial(1, xt ) ∈ [0, 1]d . Likewise, we also have ζ t |yt ∼ multinomial(m, yt ) ∈ [0, ..., m]d .

Recall that at each time step, an agent interacts with m randomly chosen opponents, and since the agent chooses to play action ai, the Q-value of non-chosen actions are not updated (∂tQtk | ztk = 0) ≡ 0. Hence by Equation (7),

The unconditional first and second moments of ∂tQt are evaluated as

where U ◦ U represents the element-wise multiplication of matrix U and U, µt = (µt1 , ..., µtd ) and Σt = [σtkl ].

We can see from Equation (11) that the variance of ∂tQti is decomposed into two terms: the first term is induced by the randomness of the action choice of the focal agent, whereas the second term is induced by the randomness of the action choices of the opponents that are randomly selected from the population. The covariance (Equation 12) between ∂tQti and ∂tQtj is purely induced by the action choice of the focal agent such that choosing an action ai forces ∂tQtk = 0 for all the other actions ak ̸= ai.

Time evolution of the PDF of agent density. We are now ready to formalize the time evolution of the PDF p(Qt ) representing density of agents having certain Q-values at time step t by applying the Fokker-Planck equation (FPE) [Fokker, 1914; Planck, 1917]. In general, the FPE for a d-dimensional stochastic process xt depicted by the stochastic process

is

where µt = {µt1 , . . . , µtd } is known as the drift vector and Dt = [Dt ij ] = 1 2 ϱtϱt⊤ the diffusion tensor. Hence the FPE that describes how p(Qt ) changes over time according to Equation (8) is given by

Given the initial Q-values distribution of agents p(Q0 ), the PDF p(Qt ) ∀t ∈ ℜ can be obtained by solving Equations (8) and (13) simultaneously. Note that the population policy yt can then be obtained by Equation (5).

3.3 Discussion

In their pioneer work, Hu et al. [2019] assume that an agent always plays with a virtual mean field agent, whose policy is the expectation of all of the (infinitely many) other agents in the population. Hence the counterpart of Equations 8 and 9

where yt is the policy of the virtual mean field agent at time t. It is worth noting that the stochasticity of focal agent's interactions with m opponents, which is captured by Equation (7) and approximated via the moment closure method in Equation (8), is omitted in the previous model. Specifically, the covariance matrix Σ in the second term of Equation (8) depicting the stochastic process of ∂tQt , together with the variances (Equation 11) and covariances (Equation 12) in it, are effectively summarily assumed to be zero in the previous model.

We note that such differences would be less and less significant when m → ∞, as m appears as a denominator in a factor in Equation (11). However, they are noticeable when m is small. Particularly, the model of Hu et al. [2019], which assumes m→∞, is generally unable to correctly depict the population dynamics in the canonical social learning settings, in which m = 1. The inaccuracy keeps noticeable as long as the value of m is small. The new model provides a more accurate depiction of the population dynamics, and rectifying these inaccuracies. As we will show in Section 4 (Figure 1), the new model represents the population dynamics much more correctly when m is small.

On the other hand, it should be noted that the new model provides a more accurate depiction of the population dynamics than the previous model in many cases even when the

(c) Hawk-Dove

(d) Rock, Paper, Scissors

Table 2: Nash equilibria of the games considered in our experiments. The mixed-strategy Nash equilibrium (β, β) means that both players take each action with probability β.

value of m is large, as we shall show in Section 4 (Figure 2). This is largely due to the fact that the newmodel does not consider the covariances (Equation 12) to be zero, which is nonetheless an implicit working assumption in the previous model. Consequently, the influence of the changes of the Qvalue of an action on the changes of the Q-value of another action of the same agent is duly recognised, and it manifests in the generally nonzero covariances σkl in the covariance matrix Σ.

4 Experiments

In this section, we apply the model derived in Section 3 to four canonical types of 2-player symmetric games. In Section 4.1, we describe the game configurations and our settings of multiagent Q-learning. In Section 4.2, we validate that our model provides a more accurate description than the previous model [Hu et al., 2019] through comparisons with agentbased simulation results across different settings. In Section 4.3, we illustrate that our model can shed light on the effects of local interactions and incomplete information on multiagent Q-learning.

4.1 Experimental Settings

Game Configurations. We consider 4 different types of 2player symmetric games: Prisoner's Dilemma (PD) game, Stag Hunt (SH) game, Hawk-Dove (HD) game, and Rock, Paper, Scissors (RPS) game. We present the payoff bi-matrices of these games in Table 1 and summarize the properties of these games in Table 2. Note that these games differ greatly in the number and types of Nash equilibria.

Settings of Multiagent Q-Learning. We consider that agents interact according to the GSL protocol (presented in Algorithm 1). For the initial Q-values of each agent at time t = 0, we consider two settings: (i) the Q-values of every action are 0, which is a common setting in MARL research, and (ii) the Q-value of the first action is 1 and the Q-values of the other actions are 0. The default learning rate and Boltzmann temperature are α = 0.1 and τ = 2, respectively.

4.2 Our Model versus Previous Model

In this section, we compare the Q-learning behaviors predicted by our model with the prediction made by the previous model [Hu et al., 2019] across different settings of games and initial Q-values (as described in the previous section). For validation, we take the agent-based simulation results as the benchmark. For each specific setting, we obtain the prediction of our model by solving Equation (8) and (13) with the finite volume method [Wyns and Du Toit, 2017] and obtain the simulation results by repeating 100 independent simulation runs. For each simulation run, we consider 2, 000 agents.

Figure 1 presents the comparisons under the situations with a small value of m. It is clear that across different settings, our model always provides more accurate descriptions on the dynamics of the expected Q-values E[Qk], ∀k in a population. In particular, for Stag-Hunt and Hawk-Dove games, our model precisely predicts the average Q-values at which the population stabilizes; on the contrary, the predictions of the previous model significantly deviate from the benchmark.

Figure 2 presents the comparisons under the situations where m → ∞. In the simulations, since the number of agents is finite, we consider an agent will play with all the other agents. From Figure 2, we again observe that our model more accurately describes the learning dynamics than the previous model.

Note that the significantly better accuracy of our model against the previous model can be observed in many settings. Due to space restrictions, more comparisons under other settings are provided in the appendix. Based on all these comparisons, we validate our main theoretical claim - our model provides more accurate descriptions of the Q-learning dynamics under the GSL protocol.

4.3 Effects of Local Interactions and Incomplete Information

As a direct benefit of more accurate descriptions on learning dynamics, our model can provide new theoretical insights that cannot be obtained using the previous model [Hu et al., 2019]. Remember that a larger value of m indicates that agents have interactions with a broader range of opponents and thus have more complete information about the entire population. Figure 3 shows that the value of m plays an important role on the outcome of multiagent Q-learning with the GSL protocol.

For Stag-Hunt games (Figure 3(a)), as the value of m increases, Q-learner populations tend to stabilize with a smaller proportion of agents playing action S, even though these populations start with the same initial Q-values settings. More interestingly, Q-learner populations converge to the unique completely mixed-strategy Nash equilibrium as m → ∞, while they do not converge to any particular Nash equilibria when m is finite and small. This clearly shows that different values of m can lead to qualitatively different learning outcomes.

We observe similar effects of the value of m on multiagent Q-learning in Hawk-Dove games. The above results suggest

(b) m = 2, the initial Q-value of each action is 0 for all the agents

Figure 2: As m → ∞, comparison among the dynamics of average Q-values predicted by our model (solid line), the previous model (dashed line), and the agent-based simulations (shaded line).

that it is non-trivial to investigate the effects of local interactions and incomplete information on multiagent Q-learning. To aid such investigation, our model can provide accurate theoretical insights, which is not available using the previous model.

5 Conclusion

In this work, we model the population dynamics in the scenarios of the generalized social learning protocol. We approximate the Q-values dynamics of each individual agent as a system of stochastic differential equations. The time evolution of the probability density function of Q-values is evaluated by the Fokker-Planck equation. Experimental results corroborate the correctness of our model and provide theoretical insights on the Q-learning dynamics under the GSL protocol, which are unable to obtain using the previous model.

Acknowledgements

The work presented in this paper is partially supported by a research grant from the Research Grants Council, Hong Kong, China (RGC Ref. No. CUHK 14206820).