Modelling the Dynamics of Regret Minimization in Large Agent Populations: a Master Equation Approach

1 Introduction

A multi-agent system (MAS) is a distributed system where independent actors called agents interact in a common environment. During the past decades, MASs have been proved to be useful frameworks to resolve real-world problems with inherently distributed nature, such as traffic control [Yang et al., 2020], online trading [Barbosa and Belo, 2010], multi-robots coordination [Ota, 2006], and video games [Vinyals et al., 2019; Jaderberg et al., 2019]. Due to the non-stationarity of MASs, designing proper agent strategies beforehand is generally hard and thus the capability of learning is crucial for individual agents.

The most commonly studied learning technique is reinforcement learning (RL). A RL agent aims to maximize its cumulative payoffs and learns its strategy through repeated interactions with the environment [Sutton and Barto, 2018]. Although RL under single-agent settings has been well understood, there lacks a solid theoretical grounding for RL under multi-agent settings due to the non-stationary nature of MASs [Bloembergen et al., 2015]. Hence, studying the dynamics of multi-agent learning is important because it can bring benefits to algorithm selection under a certain scenario, parameter tuning and inspiring the design of new learning algorithms [Tuyls et al., 2003].

* Corresponding Author

In this paper, we consider the regret minimization (RM) algorithm and study the learning dynamics under n-agent settings with n → ∞. RM is an important class of learning algorithms in the multi-agent learning literature. The central idea of RM is that during repeated interactions, an agent may look back at the history of payoffs and actions taken so far, and regret not having played another action (i.e. the best action in hindsight). RM has been proved to be effective for solving Nash equilibrium in normal-form games [Blum and Monsour, 2007]. Recently, combined with deep learning, it is shown that RM can also solve complex games with imperfect information settings [Brown et al., 2019; Brown and Sandholm, 2019]. In view of the importance, Blum and Monsour [2007] called for studies on the dynamics of RM algorithms to better understand its strengths and weaknesses.

Klos et al. [2010] derived a formal model for the dynamics of Polynomial Weights RM algorithm under the 2agent settings; based on the model, they revealed an interesting connection between RM in 2-player normal form games and evolutionary game theory (EGT). However, just like other previous works that leverage EGT to study multiagent learning [B¨orgers and Sarin, 1997; Tuyls et al., 2003; Kaisers and Tuyls, 2010; Kaisers et al., 2012; Bloembergen et al., 2015], the approach of Klos et al. [2010] could not scale with a large number of agents.

More recently, utilizing the methods of statistical physics, formal models for the learning dynamics under n-agent settings with n →∞ have been developed. Lahkar et al. [2013] considered the Cross learning in population games and derived the continuity equation model. Hu et al. [2019; 2020] derived a Fokker-Planck equation to model the Q-learning dynamics and a general master-equation-based framework for the dynamics of independent learning in population games.

Despite these advances, the dynamics of RM in MASs with infinitely many agents is still up in the air. In this paper, we focus on the Regret-Matching algorithm proposed by [Hart and Mas-Colell, 2000], and consider that each agent has its own unique regret values and updates its regret values during repeated plays of 2-player symmetric games with random opponents. We propose a theoretical model based on the master equation approach to describe the learning dynamics of RM in such systems. To be more specific, we consider the evolution of regret value distribution on the regret value space. Starting from the master equation of such stochastic process, we derive a partial differential equation, which captures the time evolution of the learning system, depending on the initial regret value's distribution and game settings. Through comparing various learning dynamics obtained by our theoretical model and simulations, we show that our theoretical model not only accurately predicts the steady-state results, but also precisely captures the evolution of the expectation of policy and regret values in the MAS.

To summarize, our key contributions are as follows:

• we formalize the regret dynamics of individual agents that apply RM in 2-player symmetric games;
• we develop the first theoretical model (a partial differential equation) that can accurately describe the regret dynamics of an entire population based on the master equation approach;
• we provide experimental validation of the accuracy of our model through extensive comparisons with agentbased simulation results.

2 Preliminaries

In this paper, we consider a multi-agent system, where all agents play the symmetric bimatrix games repeatedly with randomly selected opponents and adapt their strategies by the Regret-Matching algorithm [Hart and Mas-Colell, 2000].

2.1 Symmetric Bimatrix Games

A 2-agent normal form game is a triple ⟨{1, 2} , {A1,A2} , u⟩, where {1, 2} is the set of two agents, Ai is the set of actions (or pure strategies) available for agent i ∈ {1, 2} and ui : A1 ×A2 → R means the payoff function of agent i. xi ∈ ∆(Ai) is the policy (or a mixed strategy) vector of agent i, which is the probability distribution over Ai. Correspondingly, xti (j) is the probability of agent i choosing action j at time t. In this paper, we consider a typical 2-agent normal form game, called the symmetric bimatrix game, where each agent has the same action set A = {1, 2, · · · , k} and the payoff matrix M of a row agent is given by

where prc is the row agent's payoff when the row agent chooses action r and faces an action c taken by the column agent. The payoff matrix of the column agent is MT. The payoff of a row agent with action j against its opponent with action j ′ is

where ej is the action vector with size k (the jth element equals to 1 and the other k - 1 elements equal to 0).

2.2 Regret-Matching

The Regret-Matching algorithm is a classic regret minimization algorithm proposed by Hart and Mas-Colell [2000]. Suppose that at time t, agent i uses action ati and its opponent uses action at-i , we define rti (a) = u(a, at-i ) - u(ati , at-i ) as the regret of agent i using action ati at time t but not using action a. At time t + 1, for agent i, the cumulative regret value of action a is

Agents tend to choose the action with a high cumulative regret value. For agent i, the probability of choosing action a at time t is given by

where λ is a temperature and represents the level of rationality or the degree of exploitation of agents. If λ = 0, agents will choose each action with an equal probability. If λ →∞, agents will choose the action with the highest cumulative regret value.

2.3 Multi-agent Learning Framework

Consider a system N = {1, 2, · · · , n} containing n agents, where each agent plays the symmetric bimatrix game repeatedly. The interactions in this MAS proceeds as follows. First, each agent i obtains an initial R-value vector R1i over its action set A. At each time step t, the agent chooses an action with the probability of exponential form of its cumulative regret value, according to Equation (3). Then, the agent plays the symmetric bimatrix game with o randomly chosen agents and receives an immediate payoff which will be averaged over o games. We define O as the set of o chosen agents. At the end of each time step t, each agent updates the cumulative regret values for all actions, according to Equation (2). To generalize the Regret-Matching algorithm to our learning framework, we consider the regret of action j as rti (a) = u(a, ati′∈O ) - u(ati , ati′∈O ) where

We summarize our learning framework in Algorithm 1. We will analyze the dynamics of this system in the following section.

3 The Analysis of Regret Minimization Dynamics

In this section, we derive the continuous-time differential equations for describing the dynamics of policy and cumulative regret values in our MASs. Specifically, we introduce an analysis method based on the master equation. We first derive the dynamics of cumulative regret for individual agents, and then analyze the dynamics of the system on the regret value space, where the number of agents is infinite.

Algorithm 1: Multi-Agent Learning Model

Input: a symmetric bimatrix game ⟨{1, 2} , {A} , u⟩, a multi-agent systemM, an initial regret vector R1i over Ai for each i ∈M, the maximum number of iteration time T for each i ∈ M do initialize agent i's policy x1i according to R1i ; t ← 1; while t < T do for each i ∈ M do choose an action from A according to xti ; for each i ∈ M do agent i chooses o opponents fromM and plays the matrix game with them; for each i ∈ M do for each a ∈ A do agent i reviews games, and obtains rti (a); obtains Rt+1 i (a) by rti (a) and Rti (a); for each i ∈ M do update xt+1 i according to Rt+1 i ; t ← t + 1;

3.1 Dynamics of an Agent's Regrets

We start from the case of individual agent i, whose policy is xti at time t. First, agent i chooses an action j with the probability xti (j), and obtains the payoff u(j, at-i ). Then it reviews the games, and calculates the regrets for all actions:

According to Equation (2), if we consider the difference equation of the cumulative regret, we have

Next, following the method of [Tuyls et al., 2003], we derive a continuous-time differential equation for the update of the cumulative regret. Given the time interval between two adjacent updates of the cumulative regret being ∆t, and let t = n∆t (which means until time t + ∆t, there will be n updating processes of cumulative regrets),

Naturally, we can define the velocity of cumulative regret's change as ∆R t . Due to the randomness of ∆R, we consider its expectation. The velocity of cumulative regret's change for any action a at time t, when agent i chooses action j, can be described as a conditional expectation

Let us consider the expected payoff in above equation. The expected payoff of agent i obtained from one agent i′ is equal to the payoff when agent i's action facing with agent i′ 's policy

Note that one agent interacts with o other randomly chosen agents. The o agents' average policy is a unbiased estimator of the system's expected (or mean) policy; as o increases to infinity, the variance of that estimator will decrease to zero [Hu et al., 2019]. Hence, we let the payoff expectation of agent i facing with policy expectation of all agents in N approximate her payoff expectation

where E[xt ] is the system's policy expectation vector of all agents such that its element E[xt (j)] is the expected probability of taking action j in the system. Therefore, the Equation (7) can be rewritten as

By Equation (8), we can obtain the velocity of agent i's cumulative regret's change for all actions if agent i chooses action j at time t, which is composed of the velocity vector Vj(Rti , t) = [Vj(Rti (1), t),Vj(Rti (2), t), ...,Vj(Rti (k), t)]. For simplicity, we call cumulative regret value as regret value in the rest of this paper. Theoretically, if we can write out the velocity vector for each agent, the dynamics of the regret values is straightforward. However, this becomes impossible when the number of agents in that system tends to infinity. In the next subsection, we introduce a method based on the master equation, which allows us to obtain the dynamics of the system based on the regret value distribution in the regret value space.

3.2 Dynamics on the Regret Space

Now we consider the regret value space, a k-dimensional euclidean space, where k is the size of action set. A specific R value vector R = [R(1), R(2), ..., R(k)] is a coordinate or a position in this space. We denote by pt (R) the probability distribution of the regret values in the system at time t such that pt (R) can be regarded as how many agents in the system with their regret value equaling to R. Next, we focus on the evolution of this distribution in this regret value space.

Note that all agents in the system have the same payoff function and apply the same learning parameters. As we have used the policy expectation to ignore the randomness of the agent's opponent, this fact enables us to remove the agent index directly and rewrite Equation (8) as the function of any coordinate R in the regret value space and time t as follows:

In the regret value space, Vj (R(a), t) is the change of regret's velocity component in direction a, due to agent in position R selecting action j. And Vj(R, t) is the vector sum of the velocities in all directions, as shown in Figure 1, which is a 3dimensional situation. Since we have defined the probability distribution pt (R), any element Ext (a) of the vector Ext in Equation (9) can be calculated by formula of expectation of random variable R's function:

According to Equation (9) and (10), the key challenge is to capture the evolution dynamics of probability distribution pt (R). To address this challenge, we introduce our method based on the master equation, which is one of the main contributions of our paper.

From a spatial perspective, the evolution of pt (R) can be described as the transport of agents among different positions in regret value space. If we focus on a given R, we can find that the change of its probability density from t to t+∆t is the process of existing agents leaving the position R, to other positions and incoming agents entering R from other positions. We denote the set of positions, including the target positions towards which the agents in R moving and the source positions from which other agents entering R by {R′}. In other words, {R′} is all the positions where agents may exchange with position R. Here we set R /∈ {R′}. Consider that the time interval ∆t is small enough so that the agents can not move once more, we can represent the change of pt (R) by the master equation

where W(R,R′ , t) is the transition rate from position R′ to R at time t, and likewise for W (R′ ,R, t). The condition of using this equation is that the change of probability pt (R) is a Markov process, that is, pt+∆t (R) only depends on pt (R). In our setting, this condition is satisfied. The physical meaning of the master equation is that all the change velocity of probability at R is the increase velocity of probability minus decrease velocity of probability. Next, we further expand and deduce the master equation.

We consider the first term of Equation (11), ∫ W(R,R′ , t)pt (R′ )dR′ , which is the increase velocity of probability from all possible position {R′}. Therefore, we rewrite R′ in the first term as Rfrom, which makes the term become ∫ W(R,Rfrom, t)pt (Rfrom)dRfrom. According to the definition, W(R, Rfrom, t) is defined as follows [Mandel and Wolf, 1995]:

where Pr(R, t + ∆t | Rfrom, t) is the conditional probability of the agents in Rfrom at time t moving to R in ∆t. Here Pr(R, t | Rfrom, t) = 0 always holds according to our definition of Rfrom.

Note that the agent in one position can move to different positions because agents can choose different actions randomly. Therefore, to further distinguish the different positions {Rfrom}, where agents may choose different actions to arrive to R, we define the set {Rfrom} = {Rfrom 1 } ∪ {Rf rom 2 } ∪...∪ {Rfrom k }. Rfrom j means if an agent chooses action j to reach R in ∆t, her position at time t must be in set {Rf rom j }. Now we can further rewrite the first term of the master equation:

Let us consider the size of set {Rfrom a }. According to the definition of element Rfrom j and the velocity Vj(R, t), we have Rfrom j (a) + Vj(Rfrom j (a), t)∆t = Rfrom j (a) + 1t (u(a, E[xt ]) - u(j, E[xt ]) - Rf rom j (a)) ∆t = R(a). For each a ∈ A, there is only one Rfrom j (a) to satisfy the requirements of the above equation, which means ∣∣∣{Rfrom j }∣∣∣ = 1. Therefore, we can remove the integral sign

Next, we consider the conditional probability Pr(R, t + ∆t | Rfrom j , t). An agent in position Rfrom j at time t is able to reach R at t +∆t if and only if it chooses action j. Therefore, we have Pr(R, t+∆t | Rfrom j , t) = Prj(Rfrom j ), where Prj(Rfrom j ) = exp(λRfrom j )) ∑j′∈A exp (λRfrom j′ ) is the probability of the agent at position Rfrom j choosing action j at time t. Note that Vj(Rfrom j (a), t) ≈ Vj(R(a), t) for each a ∈ A as ∆ → 0, so we have

Finally, after our derivation, the first term of the right hand side of the master equation can be rewritten as

Using almost the same derivation, we can rewrite the second term of the right hand side of the master equation ∫ W(R′ ,R, t)pt (R′ )dR′ as

The above equation is simpler than Equation (16) because we do not need to know the exact target position of the agent at R. What we only need to know is the probability of leaving from each direction, due to choosing different actions.

Based on Equations (16), (17) and Taylor expansion at R, we obtain a Partial Differential equation, which describes the velocity of change of probability density pt (R) at time t

By Equations (9), (10) and (18), we obtain a system of differential equations, which can completely describe the dynamics of the system

̄

In fact, the above Equation (18) can be further expanded according to the law of vector derivation and multiplication:

where the term dja = d(Prj(R) pt (R)) dR(a) Vj(R(a), t) is the change of pt (R) in direction a caused by choosing action j. Note the size of action set is k. We introduce a change square matrix D consisting of k × k terms:

Here the sum of ath column of this matrix ∑kj ′=1 dj ′ a is the change of action a's regret.

4 Experiments

In this section, we will verify the effectiveness of our dynamics model by different experiments. First, we introduce our method of calculating Equation (19). Then, we show our experimental settings including the game models and parameter settings. Under these settings, we compare the expected policies predicted by our theoretical model and the mean policies obtained from agent-based simulations.

All the results shown below are divided into two types: theoretical analysis results and simulation results. The theoretical analysis results are obtained by Equation (19); we solve the equation by the finite difference method. The simulations are carried out according to Algorithm 1. Simulation results are averaged over up to 100 independent runs in order to ensure accuracy.

We consider the following payoff matrix with one parameter b:

Different ranges of b correspond to different game types: b ∈ [0, 2] for Prisoner's Dilemma (PD) games; b ∈ [2, 6] for Snowdrift (SD) games; b ∈ (-∞, 0) for Stag Hunt (SH)

̄

̄

̄

̄

̄

̄

games; and b ∈ (6,∞) for the mixed stable (MS) games. Without loss of generality, we let the initial regret values of the first action and the second action follow Beta distributions Beta (20, 80, rmin - rmax, rmax - rmin) and Beta (10, 90, rmin - rmax, rmax - rmin), where rmin and rmax are the minimum and maximum payoff of games, respectively. Figure 2 shows the fraction of agents that play cooperation, when agents' policies become stable. We can see that agents are more likely to cooperate as b increases, and our theoretical predictions are consistent with simulation results.

Next, we show that our model is able to precisely capture the evolution of policy and cumulative regret values in the MAS. In Figure 3, we show how the expected policy of the system evolves in SH (b = -1), PD (b = 2), SD (b = 3) game and Rock-Paper-Scissors (RPS) games whose payoff bimatrix is as follows:

In SH,PD,and SD games, due to the temperature constant λ, the mean policy of this system does not exactly converge to the Nash equilibria. In RPS game, interestingly, our model successfully captures the oscillation phenomenon of evolution. Figure 4 shows the evolution of the cumulative regret values of the theoretic prediction and simulation results. It is clear that our model well captures the evolution of policy and cumulative regret values across different kinds of games.

5 Conclusion

In this paper, we model the dynamics of regret minimization in MASs with infinitely many agents, where the regret values of each agent are heterogeneous. In detail, we consider the evolution of the cumulative regret values in the regret value space. Started from the master equation, we derive a partial differential equation that describes the evolution of the distribution of cumulative regret values in the population. By carrying out experiments on typical types of symmetric bimatrix games with different parameter settings, we verify that the evolutionary dynamics of multi-agent learning system can be well predicted by our theoretical model. However, our method works for the MAS where agents are allowed to apply the same learning algorithm to play symmetric bimatrix games. In future works, we can extend our model to asymmetric games and stochastic games.

Acknowledgments

This research was supported by the National Science Fund for Distinguished Young Scholarship of China (No. 62025602), the National Key R&D Program of China (No. 2018AAA0100900), the National Natural Science Foundation of China ( Nos. U1803263, 11931015 and 62066045), 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.