--- title: "Modelling the Dynamics of Regret Minimization in Large Agent Populations: a Master Equation Approach" authors: - "Zhen Wang" - "Chunjiang Mu" - "Shuyue Hu" - "Chen Chu" - "Xuelong Li" doi: "10.24963/ijcai.2022/76" url: "https://ijcai.org/proceedings/2022/76" pdf: "https://ijcai.org/proceedings/2022/0076.pdf" venue: "Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence" year: 2022 pages: "534-540" track: "Main Track" keywords: - "Agent-based and Multi-agent Systems: Multi-agent Learning" - "Agent-based and Multi-agent Systems: Agent-Based Simulation and Emergence" --- # Modelling the Dynamics of Regret Minimization in Large Agent Populations: a Master Equation Approach Zhen Wang, Chunjiang Mu, Shuyue Hu, Chen Chu, Xuelong Li *Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence*, pages 534-540. DOI: [10.24963/ijcai.2022/76](https://doi.org/10.24963/ijcai.2022/76) ## Abstract Understanding the learning dynamics in multiagent systems is an important and challenging task. Past research on multi-agent learning mostly focuses on two-agent settings. In this paper, we consider the scenario in which a population of infinitely many agents apply regret minimization in repeated symmetric games. We propose a new formal model based on the master equation approach in statistical physics to describe the evolutionary dynamics in the agent population. Our model takes the form of a partial differential equation, which describes how the probability distribution of regret evolves over time. Through experiments, we show that our theoretical results are consistent with the agent-based simulation results. ## Full text ## 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: Figure 1: An illustration of an agent moving away from R in 3dimensional space. ![Image](https://ijcai.org/proceedings/2022/fulltext/76/image_000000_41f126694bfb05cd96f603957297475db62e00c1596e4e3556c0a869a1068466.png) 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 ̄ Figure 2: The fraction of agents that cooperate, when agents' policies become stable. We use E[x] and ¯x to denote our theoretical predictions and the simulation results, respectively. In the simulations, there are 1, 000 agents. The number of opponents per time step is o = 50. The temperature λ in Equation (3) is 1. ![Image](https://ijcai.org/proceedings/2022/fulltext/76/image_000001_d5c34c1c4a205dc9892ff1e56056dc9e620bacc552ee5b8d154c5b526ddba1bf.png) 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) ̄ ̄ ̄ Figure 3: Evolution of the expected policy E[x] predicted by our theoretical model and the mean policy ¯x observed in agent-based simulations. In the simulations, there are 1, 000 agents. The number of opponents per time step is o = 50. The temperature λ in Equation (3) is 1 for SH, PD, SD games and is 5 for RPS games. ![Image](https://ijcai.org/proceedings/2022/fulltext/76/image_000002_cf03e3dc7a9c9a3ba63226dd176602a81df0dd8efcfdedf9c783894abb09515c.png) ̄ ̄ ̄ Figure 4: Evolution of the expected cumulative regret value E[R] predicted by our theoretical model and the mean ¯R cumulative regret value observed in agent-based simulations. The experimental settings are the same as in Figure 3. ![Image](https://ijcai.org/proceedings/2022/fulltext/76/image_000003_a5f36b5c784d6b0eb2af92e63efa672e05c0a38e8eecf737966b0de754576db9.png) 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. ## References 1. [Barbosa and Belo, 2010] Rui Pedro Barbosa and Orlando Belo. Multi-agent forex trading system. In Agent and multi-agent technology for internet and enterprise sys- tems, pages 91-118. Springer, 2010. 2. [Bloembergen et al., 2015] Daan Bloembergen, Karl Tuyls, Daniel Hennes, and Michael Kaisers. Evolutionary dy- namics of multi-agent learning: A survey. Journal of Arti- ficial Intelligence Research, 53:659-697, 2015. 3. [Blum and Monsour, 2007] Avrim Blum and Yishay Mon- sour. Learning, regret minimization, and equilibria. Al- gorithmic Game Theory, pages 79-100, 2007. 4. [Börgers and Sarin, 1997] Tilman Börgers and Rajiv Sarin. Learning through reinforcement and replicator dynamics. Journal of economic theory, 77(1):1-14, 1997. 5. [Brown and Sandholm, 2019] Noam Brown and Tuomas Sandholm. Solving imperfect-information games via dis- counted regret minimization. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 1829-1836, 2019. 6. [Brown et al., 2019] Noam Brown, Adam Lerer, Sam Gross, and Tuomas Sandholm. Deep counterfactual regret mini- mization. In International conference on machine learn- ing, pages 793-802. PMLR, 2019. 7. [Hart and Mas-Colell, 2000] Sergiu Hart and Andreu Mas- Colell. A simple adaptive procedure leading to correlated equilibrium. Econometrica, 68(5):1127-1150, 2000. 8. [Hu et al., 2019] Shuyue Hu, Chin-wing Leung, and Ho- fung Leung. Modelling the dynamics of multiagent q- learning in repeated symmetric games: a mean field the- oretic approach. Advances in Neural Information Process- ing Systems, 32:12125-12135, 2019. 9. [Hu et al., 2020] Shuyue Hu, Chin-Wing Leung, Ho-fung Leung, and Harold Soh. The evolutionary dynamics of independent learning agents in population games. arXiv preprint arXiv:2006.16068, 2020. 10. [Jaderberg et al., 2019] Max Jaderberg, Wojciech M Czar- necki, Iain Dunning, Luke Marris, Guy Lever, Anto- nio Garcia Castaneda, Charles Beattie, Neil C Rabinowitz, Ari S Morcos, Avraham Ruderman, et al. Human-level performance in 3d multiplayer games with population- based reinforcement learning. Science, 364(6443):859- 865, 2019. 11. [Kaisers and Tuyls, 2010] Michael Kaisers and Karl Tuyls. Frequency adjusted multi-agent q-learning. In Proceed- ings of the 9th International Conference on Autonomous Agents and Multiagent Systems: volume 1-Volume 1, pages 309-316, 2010. 12. [Kaisers et al., 2012] Michael Kaisers, Daan Bloembergen, and Karl Tuyls. A common gradient in multi-agent rein- forcement learning. In AAMAS, pages 1393-1394, 2012. 13. [Klos et al., 2010] Tomas Klos, Gerrit Jan Van Ahee, and Karl Tuyls. Evolutionary dynamics of regret minimiza- tion. In Joint European Conference on Machine Learn- ing and Knowledge Discovery in Databases, pages 82-96. Springer, 2010. 14. [Lahkar and Seymour, 2013] Ratul Lahkar and Robert M Seymour. Reinforcement learning in population games. Games and Economic Behavior, 80:10-38, 2013. 15. [Mandel and Wolf, 1995] Leonard Mandel and Emil Wolf. Optical coherence and quantum optics. Cambridge uni- versity press, 1995. 16. [Ota, 2006] Jun Ota. Multi-agent robot systems as dis- tributed autonomous systems. Advanced engineering in- formatics, 20(1):59-70, 2006. 17. [Sutton and Barto, 2018] Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018. 18. [Tuyls et al., 2003] Karl Tuyls, Katja Verbeeck, and Tom Lenaerts. A selection-mutation model for q-learning in multi-agent systems. In Proceedings of the second inter- national joint conference on Autonomous agents and mul- tiagent systems, pages 693-700, 2003. 19. [Vinyals et al., 2019] Oriol Vinyals, Igor Babuschkin, Woj- ciech M Czarnecki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster level in star- craft ii using multi-agent reinforcement learning. Nature, 575(7782):350-354, 2019. 20. [Yang et al., 2020] Jiachen Yang, Jipeng Zhang, and Huihui Wang. Urban traffic control in software defined internet of things via a multi-agent deep reinforcement learning ap- proach. IEEE Transactions on Intelligent Transportation Systems, 22(6):3742-3754, 2020.