Overview on Reinforcement Learning of Multi-agent Game

doi:10.3778/j.issn.1002-8331.2104-0432

Abstract

Abstract:

The use of deep reinforcement learning to solve single-agent tasks has made breakthrough progress. Since the complexity of multi-agent systems, common algorithms cannot solve the main difficulties. At the same time, due to the increase in the number of agents, taking the expected value of maximizing the cumulative return of a single agent as the learning goal often fails to converge and some special convergence points do not satisfy the rationality of the strategy. For practical problems that there is no optimal solution, the reinforcement learning algorithm is even more helpless. The introduction of game theory into reinforcement learning can solve the interrelationship of agents very well and explain the rationality of the strategy corresponding to the convergence point. More importantly, it can use the equilibrium solution to replace the optimal solution in order to obtain a relatively effective strategy. Therefore, this article investigates the reinforcement learning algorithms that have emerged in recent years from the perspective of game theory, summarizes the important and difficult points of current game reinforcement learning algorithms and gives several breakthrough directions that may solve the above-mentioned difficulties.

Key words: multi-agent, reinforcement learning, game theory

摘要：

使用深度强化学习解决单智能体任务已经取得了突破性的进展。由于多智能体系统的复杂性，普通算法无法解决其主要难点。同时，由于智能体数量增加，将最大化单个智能体的累积回报的期望值作为学习目标往往无法收敛，某些特殊的收敛点也不满足策略的合理性。对于不存在最优解的实际问题，强化学习算法更是束手无策，将博弈理论引入强化学习可以很好地解决智能体的相互关系，可以解释收敛点对应策略的合理性，更重要的是可以用均衡解来替代最优解以求得相对有效的策略。因此，从博弈论的角度梳理近年来出现的强化学习算法，总结当前博弈强化学习算法的重难点，并给出可能解决上述重难点的几个突破方向。

关键词: 多智能体, 强化学习, 博弈论

WANG Jun, CAO Lei, CHEN Xiliang, LAI Jun, ZHANG Legui. Overview on Reinforcement Learning of Multi-agent Game[J]. Computer Engineering and Applications, 2021, 57(21): 1-13.

王军，曹雷，陈希亮，赖俊，章乐贵. 多智能体博弈强化学习研究综述[J]. 计算机工程与应用, 2021, 57(21): 1-13.

References

[1] 胡晓峰.战争科学论：认识和理解战争的科学基础与思维方法[M].北京：科学出版社，2018.
HU X F.The science of war：the scientific basis and thinking methods for recognizing and understanding war[M].Beijing：Science Press，2018.
[2] 周志华.机器学习[M].北京：清华大学出版社，2015：390-392.
ZHOU Z H.Machine learning[M].Beijing：Tsinghua University Press，2015：390-392.
[3] 孙彧，曹雷，陈希亮，等.多智能体深度强化学习研究综述[J].计算机工程与应用，2020，56（5）：13-24.
SUN Y，CAO L，CHEN X L，et al.Overview of multi-agent deep reinforcement learning[J].Computer Engineering and Applications，2020，56（5）：13-24.
[4] 俞建.博弈论与非线性分析[M].北京：科学出版社，2008.
YU J.Game theory and nonlinear analysis[M].Beijing：Science Press，2008.
[5] HUNG C C，LILLICRAP T，ABRAMSON J，et al.Optimizing agent behavior over long time scales by transporting value[J].Nature Communications，2019，10（1）：1-12.
[6] WANG X，SANDHOLM T.Reinforcement learning to play an optimal Nash equilibrium in team Markov games[J].Advances in Neural Information Processing Systems，2002，15：1603-1610.
[7] ARSLAN G，YüKSEL S.Decentralized Q-learning for stochastic teams and games[J].IEEE Transactions on Automatic Control，2016，62（4）：1545-1558.
[8] MAO H，ZHANG Z，XIAO Z，et al.Modelling the dynamic joint policy of teammates with attention multi-agent DDPG[J].arXiv：1811.07029，2018.
[9] LIU Y，WANG W，HU Y，et al.Multi-agent game abstraction via graph attention neural network[C]//Proceedings of the AAAI Conference on Artificial Intelligence，2020：7211-7218.
[10] ZHU C，LEUNG H，HU S，et al.A Q-values sharing framework for multiple independent Q-learners[C]//Proceedings of the 18th International Conference on Autonomous Agents and Multiagent Systems，2019：2324-2326.
[11] YANG Y，LUO R，LI M，et al.Mean field multi-agent reinforcement learning[C]//International Conference on Machine Learning，2018：5571-5580.
[12] ANAHTARCI B，KARIKSIZ C D，SALDI N.Q-learning in regularized mean-field games[J].arXiv：2003.12151，2020.
[13] ELIE R，PéROLAT J，LAURIèRE M，et al.On the convergence of model free learning in mean field games[C]//Proceedings of the AAAI Conference on Artificial Intelligence，2020：7143-7150.
[14] KOK J R，VLASSIS N.Sparse cooperative Q-learning[C]//Proceedings of the Twenty-First International Conference on Machine Learning，2004：61.
[15] SUNEHAG P，LEVER G，GRUSLYS A，et al.Value-decomposition networks for cooperative multi-agent learning[J].arXiv：1706.05296，2017.
[16] RASHID T，SAMVELYAN M，SCHROEDER C，et al.Qmix：monotonic value function factorisation for deep multi-agent reinforcement learning[C]//International Conference on Machine Learning，2018：4295-4304.
[17] SON K，KIM D，KANG W J，et al.Qtran：learning to factorize with transformation for cooperative multi-agent reinforcement learning[C]//International Conference on Machine Learning，2019：5887-5896.
[18] YANG Y，HAO J，LIAO B，et al.Qatten：a general framework for cooperative multiagent reinforcement learning[J].arXiv：2002.03939，2020.
[19] YANG Y，HAO J，CHEN G，et al.Q-value path decomposition for deep multiagent reinforcement learning[C]//International Conference on Machine Learning，2020：10706-10715.
[20] CANDOGAN O，MENACHE I，OZDAGLAR A，et al.Flows and decompositions of games：harmonic and potential games[J].Mathematics of Operations Research，2011，36（3）：474-503.
[21] MACUA S V，ZAZO J，ZAZO S.Learning parametric closed-loop policies for Markov potential games[J].arXiv：1802.00899，2018.
[22] LESLIE D S，COLLINS E J.Generalised weakened fictitious play[J].Games and Economic Behavior，2016，56（2）：285-298.
[23] MAZUMDAR E，RATLIFF L J，SASTRY S.On the convergence of gradient-based learning in continuous games[J].arXiv：1804.05464，2018.
[24] CHEN G.A new framework for multi-agent reinforcement learning—centralized training and exploration with decentralized execution via policy distillation[J].arXiv：1910.09152，2019.
[25] LI G，JIANG B，ZHU H，et al.Generative attention networks for multi-agent behavioral modeling[C]//Proceedings of the AAAI Conference on Artificial Intelligence，2020：7195-7202.
[26] RYU H，SHIN H，PARK J.Multi-agent actor-critic with hierarchical graph attention network[C]//Proceedings of the AAAI Conference on Artificial Intelligence，2020：7236-7243.
[27] NAYYAR A，MAHAJAN A，TENEKETZIS D.Decentralized stochastic control with partial history sharing：a common information approach[J].IEEE Transactions on Automatic Control，2013，58（7）：1644-1658.
[28] WU F，ZILBERSTEIN S，CHEN X.Rollout sampling policy iteration for decentralized POMDPs[J].arXiv：1203. 3528，2012.
[29] ADLER I.The equivalence of linear programs and zero-sum games[J].International Journal of Game Theory，2013，42（1）：165-177.
[30] SHAPLEY L S.Stochastic games[C]//Proceedings of the National Academy of Sciences of the USA，1953：1095-1100.
[31] LITTMAN M L.Markov games as a framework for multi-agent reinforcement learning[M]//Machine learning proceedings.[S.l.]：Morgan Kaufmann，1994：157-163.
[32] SZEPESVáRI C，LITTMAN M L.A unified analysis of value-function-based reinforcement-learning algorithms[J].Neural Computation，1999，11（8）：2017-2060.
[33] FAN J，WANG Z，XIE Y，et al.A theoretical analysis of deep Q-learning[C]//Learning for Dynamics and Control，2020：486-489.
[34] GOODFELLOW I J，POUGET-ABADIE J，MIRZA M，et al.Generative adversarial networks[J].arXiv：1406.2661，2014.
[35] LI S，WU Y，CUI X，et al.Robust multi-agent reinforcement learning via minimax deep deterministic policy gradient[C]//Proceedings of the AAAI Conference on Artificial Intelligence，2019，33（1）：4213-4220.
[36] ZHANG G，YU Y.Convergence of gradient methods on bilinear zero-sum games[J].arXiv：1908.05699，2019.
[37] MERTIKOPOULOS P，LECOUAT B，ZENATI H，et al.Optimistic mirror descent in saddle-point problems：going the extra（gradient） mile[J].arXiv：1807.02629，2018.
[38] JIN C，NETRAPALLI P，JORDAN M.What is local optimality in nonconvex-nonconcave minimax optimization?[C]//International Conference on Machine Learning，2020：4880-4889.
[39] FIEZ T，CHASNOV B，RATLIFF L J.Convergence of learning dynamics in stackelberg games[J].arXiv：1906. 01217，2019.
[40] ZHANG J，XIAO P，SUN R，et al.A single-loop smoothed gradient descent-ascent algorithm for nonconvex-concave min-max problems[J].arXiv：2010.15768，2020.
[41] CHEN X，DENG X.Settling the complexity of two-player Nash equilibrium[C]//2006 47th Annual IEEE Symposium on Foundations of Computer Science（FOCS’06），2006：261-272.
[42] HERINGS P J J，PEETERS R.Homotopy methods to compute equilibria in game theory[J].Economic Theory，2010，42（1）：119-156.
[43] LOWE R，WU Y，TAMAR A，et al.Multi-agent actor-critic for mixed cooperative-competitive environments[J].arXiv：1706.02275，2017.
[44] ZHANG H，CHEN W，HUANG Z，et al.Bi-level actor-critic for multi-agent coordination[C]//Proceedings of the AAAI Conference on Artificial Intelligence，2020：7325-7332.
[45] BLUM A，HAGHTALAB N，HAJIAGHAYI M T，et al.Computing stackelberg equilibria of large general-sum games[C]//International Symposium on Algorithmic Game Theory.Cham：Springer，2019：168-182.
[46] LITTMAN M L.Friend-or-foe Q-learning in general-sum games[C]//Proceedings of the Eighteenth International Conference on Machine Learning，2001：322-328.
[47] BORKAR V S.Stochastic approximation with two time scales[J].Systems & Control Letters，1997，29（5）：291-294.
[48] PRASAD H L，PRASHANTH L A，BHATNAGAR S.Two-timescale algorithms for learning Nash equilibria in general-sum stochastic games[C]//Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems，2015：1371-1379.
[49] HEUSEL M，RAMSAUER H，UNTERTHINER T，et al.GANs trained by a two time-scale update rule converge to a local nash equilibrium[J].arXiv：1706.08500，2017.
[50] TIAN Y，GONG Q，JIANG T.Joint policy search for multi-agent collaboration with imperfect information[J].arXiv：2008.06495，2020.
[51] ZINKEVICH M，JOHANSON M，BOWLING M，et al.Regret minimization in games with incomplete information[J].Advances in Neural Information Processing Systems，2007，20：1729-1736.
[52] ZHOU Y，REN T，LI J，et al.Lazy-CFR：a fast regret minimization algorithm for extensive games with imperfect information[J].arXiv：1810.04433，2018.
[53] BROWN N，SANDHOLM T.Reduced space and faster convergence in imperfect-information games via pruning[C]//International Conference on Machine Learning，2017：596-604.
[54] HEINRICH J，LANCTOT M，SILVER D.Fictitious self-play in extensive-form games[C]//International Conference on Machine Learning，2015：805-813.
[55] SCHMID M，BURCH N，LANCTOT M，et al.Variance reduction in Monte Carlo counterfactual regret minimization（VR-MCCFR） for extensive form games using baselines[C]//Proceedings of the AAAI Conference on Artificial Intelligence，2019：2157-2164.
[56] LI H，HU K，GE Z，et al.Double neural counterfactual regret minimization[J].arXiv：1812.10607，2018.
[57] LANCTOT M，WAUGH K，ZINKEVICH M，et al.Monte carlo sampling for regret minimization in extensive games[C]//Advances in Neural Information Processing Systems，2009：1078-1086.
[58] HEINRICH J，SILVER D.Deep reinforcement learning from self-play in imperfect-information games[J].arXiv：1603.01121，2016.
[59] STEINBERGER E.Single deep counterfactual regret minimization[J].arXiv：1901.07621，2019.
[60] STEINBERGER E，LERER A，BROWN N.DREAM：deep regret minimization with advantage baselines and model-free learning[J].arXiv：2106.10410，2021.
[61] KASH I A，SULLINS M，HOFMANN K.Combining no-regret and Q-learning[J].arXiv：1910.03094，2019.
[62] FUDENBERG D，LEVINE D K.Consistency and cautious fictitious play[J].Journal of Economic Dynamics and Control，1995，19（5/7）：1065-1089.
[63] HEINRICH J，SILVER D.Deep reinforcement learning from self-play in imperfect-information games[J].arXiv：1603.01121，2018.
[64] FOERSTER J N，CHEN R Y，AL-SHEDIVAT M，et al.Learning with opponent-learning awareness[J].arXiv：1709.04326，2017.
[65] ZHANG L，WANG W，LI S，et al.Monte Carlo neural fictitious self-play：approach to approximate Nash equilibrium of imperfect-information games[J].arXiv：1903. 09569，2019.
[66] BROWN N，BAKHTIN A，LERER A，et al.Combining deep rein-forcement learning and search for imperfect-information games[J].arXiv：2007.13544，2020.
[67] SRINIVASAN S，LANCTOT M，ZAMBALDI V，et al.Actor-critic policy optimization in partially observable multiagent environments[J].arXiv：1810.09026，2018.