Year: 2020

Abstract:
Trust-region methods are widely used in single-agent reinforcement learning. One advantage is that they guarantee a lower bound of monotonic payoff improvement for policy optimization at each iteration. Nonetheless, when applied in multi-agent settings, such guarantee is lost because an agent’s payoff is also determined by other agents’ adaptive behaviors. In fact, measuring agents’ payoff improvements in multi-agent reinforcement learning (MARL) scenarios is still challenging. Although game-theoretical solution concepts such as Nash equilibrium can be applied, the algorithm (e.g., Nash-Q learning) suffers from poor scalability beyond twoplayer discrete games. To mitigate the above measurability and tractability issues, in this paper, we propose Multi-Agent Trust Region Learning (MATRL) method. MATRL augments the single-agent trust-region optimization process with the multiagent solution concept of stable fixed point that is computed at the policy-space meta-game level. When multiple agents learn simultaneously, stable fixed points at the meta-game level can effectively measure agents’ payoff improvements, and, importantly, a meta-game representation enjoys better scalability for multi-player games. We derive the lower bound of agents’ payoff improvements for MATRL methods, and also prove the convergence of our method on the meta-game fixed points. We evaluate the MATRL method on both discrete and continuous multiplayer general-sum games; results suggest that MATRL significantly outperforms strong MARL baselines on grid worlds, multi-agent MuJoCo, and Atari games.

heading: 1 INTRODUCTION
text: Multi-agent systems (MAS) (Shoham & Leyton-Brown, 2008) have received much attention from the reinforcement learning community. In real-world, automated driving (Cao et al., 2012), StarCraft II (Vinyals et al., 2019) and Dota 2 (Berner et al., 2019) are a few examples of the myriad of applications that can be modeled by MAS. Due to the complexity of multi-agent problems (Chatterjee et al., 2004), investigating if agents can learn to behave effectively during interactions with environments and other agents is essential (Fudenberg et al., 1998). This can be achieved naively through the independent learner (IL) (Tan, 1993), which ignores the other agents and optimizes the policy assuming a stable environment (Buşoniu et al., 2010; Hernandez-Leal et al., 2017). Due to their theoretical guarantee and good empirical performance in real-world applications, trust region methods (e.g., PPO (Schulman et al., 2015; 2017)) based ILs are popular (Vinyals et al., 2019; Berner et al., 2019). In single-agent learning, trust region methods can produce a monotonic payoff improvement guarantee (Kakade & Langford, 2002) via line search (Schulman et al., 2015).
In multi-agent scenarios, however, an agent’s improvement is affected by other agent’s adaptive behaviors (i.e., the multi-agent environment is non-stationary (Hernandez-Leal et al., 2017)). As a result, trust region learners can measure the policy improvements of the agents’ current policies, but the improvements of the updated opponents’ policies are unknown (shown in Fig. 1). Therefore, trust region based ILs act less well in MAS as in single-agent tasks. Moreover, the convergence to a fixed point, such as a Nash equilibrium (Nash et al., 1950; Bowling & Veloso, 2004; Mazumdar et al., 2020), is a common and widely accepted solution concept for multi-agent learning. Thus, although independent learners can best respond to other agents’ current policies, they lose their convergence guarantee (Laurent et al., 2011).
One solution to address the convergence problem for independent learners is Empirical GameTheoretic Analysis (EGTA) (Wellman, 2006), which approximates the best response to the policies generated by the independent learners (Lanctot et al., 2017; Muller et al., 2019). Although EGTA based methods (Lanctot et al., 2017; Omidshafiei et al., 2019; Balduzzi et al., 2019) establish
Under review as a conference paper at ICLR 2021
<latexit sha1_base64="1NN7F0aZfrdhNGV5c+4oOHrBfTM=">AAACEXicdVDLSgMxFM3UV62vqks3wSK4KjNS0YWLghuXFewD2qFk0jttaJIZk4xQhv6CGxf6K+7ErV/gn7g0087CtnggcDjn3uTkBDFn2rjut1NYW9/Y3Cpul3Z29/YPyodHLR0likKTRjxSnYBo4ExC0zDDoRMrICLg0A7Gt5nffgKlWSQfzCQGX5ChZCGjxGRSj8Njv1xxq+4MeJV4OamgHI1++ac3iGgiQBrKidZdz42NnxJlGOUwLfUSDTGhYzKErqWSCNB+Oss6xWdWGeAwUvZIg2fq342UCK0nIrCTgpiRXvYy8T8vu1EvvJ8GYimPCa/9lMk4MSDpPE6YcGwinNWDB0wBNXxiCaGK2R9hOiKKUGNLLNmqvOViVknrourVqpf3tUr9Ji+tiE7QKTpHHrpCdXSHGqiJKBqhZ/SK3pwX5935cD7nowUn3zlGC3C+fgHH+Z5O</latexit>
<latexit sha1_base64="9HEuAo3NH+KpHjvH/J6u6lMbsxQ=">AAACDnicdVDLSgMxFL1TX7W+qi7dBIvgqsyIogvBghuXLdgHtEPJpJk2NMkMSUYoQ7/AjQv9FXfi1l/wT1yaaWdhWzwQOJxzb3JygpgzbVz32ymsrW9sbhW3Szu7e/sH5cOjlo4SRWiTRDxSnQBrypmkTcMMp51YUSwCTtvB+D7z209UaRbJRzOJqS/wULKQEWys1Ljrlytu1Z0BrRIvJxXIUe+Xf3qDiCSCSkM41rrrubHxU6wMI5xOS71E0xiTMR7SrqUSC6r9dBZ0is6sMkBhpOyRBs3UvxspFlpPRGAnBTYjvexl4n9edqNeeD8NxFIeE974KZNxYqgk8zhhwpGJUNYNGjBFieETSzBRzP4IkRFWmBjbYMlW5S0Xs0paF1XvsnrVuKzUbvPSinACp3AOHlxDDR6gDk0gQOEZXuHNeXHenQ/ncz5acPKdY1iA8/ULDlCc0Q==</latexit>
<latexit sha1_base64="0MwWVFV0mTJ6Pj2jW71gFQUXJfk=">AAACEXicdVDLSgMxFM3UV62vqks3wSK4KjNS0YWLghuXFewD2qFk0jttaJIZk4xQhv6CGxf6K+7ErV/gn7g0087CtnggcDjn3uTkBDFn2rjut1NYW9/Y3Cpul3Z29/YPyodHLR0likKTRjxSnYBo4ExC0zDDoRMrICLg0A7Gt5nffgKlWSQfzCQGX5ChZCGjxGRSbwiP/XLFrboz4FXi5aSCcjT65Z/eIKKJAGkoJ1p3PTc2fkqUYZTDtNRLNMSEjskQupZKIkD76SzrFJ9ZZYDDSNkjDZ6pfzdSIrSeiMBOCmJGetnLxP+87Ea98H4aiKU8Jrz2UybjxICk8zhhwrGJcFYPHjAF1PCJJYQqZn+E6YgoQo0tsWSr8paLWSWti6pXq17e1yr1m7y0IjpBp+gceegK1dEdaqAmomiEntErenNenHfnw/mcjxacfOcYLcD5+gW/nZ5J</latexit>
<latexit sha1_base64="9HEuAo3NH+KpHjvH/J6u6lMbsxQ=">AAACDnicdVDLSgMxFL1TX7W+qi7dBIvgqsyIogvBghuXLdgHtEPJpJk2NMkMSUYoQ7/AjQv9FXfi1l/wT1yaaWdhWzwQOJxzb3JygpgzbVz32ymsrW9sbhW3Szu7e/sH5cOjlo4SRWiTRDxSnQBrypmkTcMMp51YUSwCTtvB+D7z209UaRbJRzOJqS/wULKQEWys1Ljrlytu1Z0BrRIvJxXIUe+Xf3qDiCSCSkM41rrrubHxU6wMI5xOS71E0xiTMR7SrqUSC6r9dBZ0is6sMkBhpOyRBs3UvxspFlpPRGAnBTYjvexl4n9edqNeeD8NxFIeE974KZNxYqgk8zhhwpGJUNYNGjBFieETSzBRzP4IkRFWmBjbYMlW5S0Xs0paF1XvsnrVuKzUbvPSinACp3AOHlxDDR6gDk0gQOEZXuHNeXHenQ/ncz5acPKdY1iA8/ULDlCc0Q==</latexit>
<latexit sha1_base64="mlfS6P1wr0psE/0O2O9hkrlFv2g=">AAACbHicdVHBTtwwEPWmUOiWlm3LDSFZXYGotKySahEgcUDlAEdadQGJpJHjTBYLO4nsCWJl5ev6FXwClx7aS494wx66izqSpaf3ZsbPz0kphUHfv295LxYWXy4tv2q/XnnzdrXz7v25KSrNYcgLWejLhBmQIochCpRwWWpgKpFwkdwcT/SLW9BGFPl3HJcQKTbKRSY4Q0fFnShMIXOzzSarxhrS2n47+VLbYH/Qowe7PToI6nYIyGK7I+rtsBSxFXUvRLjDmalGcS0/HNJCQV1/ijtdv+83RZ+DYAq6ZFpncedvmBa8UpAjl8yYq8AvMbJMo+ASnI/KQMn4DRvBlYM5U2Ai29io6aZjUpoV2p0cacP+O2GZMmasEtepGF6beW1C/k+bbDQz99tEzfnBbD+yIi8rhJw/2ckqSbGgk+RpKjRwlGMHGNfCvYjya6YZR/c/bRdVMB/Mc3D+uR8M+gdfB92jw2loy2SdfCTbJCB75IickjMyJJz8JA/kN/nT+uWteevexlOr15rOfCAz5W09Arjwv3Y=</latexit>
<latexit sha1_base64="DcIAKyRK95otGmn1ylfKJLkPQG4=">AAACiHicdVHBTttAEF2b0oa0hUCPXFaNKlEpRDZKRSJxQHCAI6AGkHBqrddjWLFrW7tjhLXyh3LiN3pkE3IgQYy00tObNzNvZ5JSCoNB8OT5K59WP39prbW/fvu+vtHZ3Lo0RaU5jHkhC32dMANS5DBGgRKuSw1MJRKukvvjaf7qAbQRRf4X6xImit3mIhOcoaPiTh2lkLnaWSerag1pYy9OjhobDgc9OvrTo4OwaUeALLa7otmJEB5xQR2VIrai+eeAFgqapveBZvet6Hfc6Qb9YBb0PQjnoEvmcRZ3/kdpwSsFOXLJjLkJgxInlmkUXILzWBkoGb9nt3DjYM4UmImd2WjoL8ekNCu0eznSGfu2wjJlTK0Sp1QM78xybkp+lJt2NAvzbaKW/GA2nFiRlxVCzl/tZJWkWNDpVWgqNHCUtQOMa+F+RPkd04yju13brSpcXsx7cLnXDwf90fmge3gwX1qLbJOfZIeEZJ8cklNyRsaEk2dv1Vv3Nvy2H/j7/uhV6nvzmh9kIfyjF/pHyLI=</latexit>
<latexit sha1_base64="EGsGKugD16zqH57YPB5KPfiuvxo=">AAACh3icdVFNTxsxEPUuUCDlI9AjF4sIiUppuosCJBIHaA/lSCsCSGwaeb2zYGHvruxZlMjaH9pLf0eP9YYcSBAjWXp67834eRwXUhgMgj+ev7S88mF1bb3xcWNza7u5s3tj8lJzGPBc5vouZgakyGCAAiXcFRqYiiXcxk/fa/32GbQReXaNkwKGij1kIhWcoaNGzXGUQOp6p5OsmmhIKvvrx7fKhr1um/aP27QbVo0IkI2sqA4jhDHOmaNC1MpvB7RQUFXtdzxfXps+j5qtoBNMi74F4Qy0yKyuRs1/UZLzUkGGXDJj7sOgwKFlGgWX4CKWBgrGn9gD3DuYMQVmaKcxKnrgmISmuXYnQzplX3dYpoyZqNg5FcNHs6jV5HtaPdHM3W9jtZAH097QiqwoETL+EictJcWc1p9CE6GBo5w4wLgW7kWUPzLNOLqva7hVhYuLeQtujjpht9P/2W2dn82Wtkb2yD45JCE5JefkklyRAeHkr7fsbXpb/rr/1T/xey9W35v1fCJz5V/8B2ymyHs=</latexit>
<latexit sha1_base64="QmmZ03/Sf6mnjXKt2E0v8KaahaA=">AAACa3icdVHBTtwwEPUGaGFpYYEb9GCxQqLSskqqRYDEAdEDPQJiAYksK8eZgIWdRPYEsbLyc/2L/gEXDvTUY52wh+6ijmTp6b2Z8fNzlEth0Pd/NbyZ2bkPH+cXmoufPi8tt1ZWL01WaA59nslMX0fMgBQp9FGghOtcA1ORhKvo4XulXz2CNiJLL3CUw0Cxu1QkgjN01LAVhjEkbrbeZNVIQ1za85Pj0gb7vQ492O3QXlA2Q0A2tKLcDhGecKI5zEWl3DqghYKy7NTMjii/Dlttv+vXRd+DYAzaZFynw9afMM54oSBFLpkxN4Gf48AyjYJLcDYKAznjD+wObhxMmQIzsLWdkm45JqZJpt1JkdbsvxOWKWNGKnKdiuG9mdYq8n9atdFM3G8jNeUHk/2BFWleIKT8zU5SSIoZrYKnsdDAUY4cYFwL9yLK75lmHN33NF1UwXQw78Hlt27Q6x6c9dpHh+PQ5skG2STbJCB75Ij8IKekTzj5SZ7JK/ndePHWvHXvy1ur1xjPrJGJ8rb+Ajxhvz8=</latexit>
<latexit sha1_base64="oa4StdeIIx+XA1qsMVANMuqxEMQ=">AAACT3icdVHLSgMxFM3UV1tfVZdugkVQqGVGKiq4KLrQpYpVwZaSydzRYDIzJBmhhPkdv8aNCwW/RFdiZpyFVrxwuYdznznxE86Udt03pzIxOTU9U63VZ+fmFxYbS8uXKk4lhR6NeSyvfaKAswh6mmkO14kEInwOV/79UZ6/egCpWBxd6FECA0FuIxYySrSlho1uP4DQ9haTjBhJCDJzfnyYGW+v08L7Oy3c8bJ6HzQZGpZt9BOWx1YRt1i2OWw03bZbGP4LvBI0UWmnw8ZHP4hpKiDSlBOlbjw30QNDpGaUg12VKkgIvSe3cGNhRASogSnuy/C6ZQIcxtJ6pHHB/uwwRCg1Er6tFETfqfFcTv6XyyeqX/uNL8bu0eHewLAoSTVE9PucMOVYxzgXFwdMAtV8ZAGhktkXYXpHJKHafkHdSuWNC/MXXG63vU57/6zT7B6UolXRKlpDG8hDu6iLTtAp6iGKHtETekGvzrPz7nxWytKKU4IV9MsqtS/6MLQF</latexit>
<latexit sha1_base64="H8UEmSja/X4EcOJ731PXDegUMN8=">AAACUHicdVHPSxtBFH4btWq0bbTHXgZDIUIadiVFBQ/WHuwxlkYDJiyzs291cGZ3mZkVwrB/j3+NFw+K/4k3nWxS0EgfPN7H937ON1EuuDa+/+jVFhaXPiyvrNbX1j9++tzY2DzVWaEY9lkmMjWIqEbBU+wbbgQOcoVURgLPoqtfk/zZNSrNs/SvGec4kvQi5Qln1DgqbPwcxpi43mqSlWOFcWn/HB+VNtjrtsn+jzbpBmV9iIaG9jsvW8Och5aX7So6YjtsNP2OXxl5D4IZaMLMemHjaRhnrJCYGiao1ueBn5uRpcpwJtDtKjTmlF3RCzx3MKUS9chWB5bkm2NikmTKeWpIxb7usFRqPZaRq5TUXOr53IT8X24yUb/ZbyM5d49J9kaWp3lhMGXTc5JCEJORibok5gqZEWMHKFPcvYiwS6ooM+4P6k6qYF6Y9+B0pxN0O/sn3ebhwUy0FfgKW9CCAHbhEH5DD/rA4AZu4R4evDvvyXuuedPSfxG+wBur1V8AfZi0PA==</latexit>
convergence guarantees in several games classes, the computational cost is also large when empirically approximating and solving the increasing meta-game (Yang et al., 2019). Other multi-agent learning approaches collect or approximate additional information such as communication (Foerster et al., 2016) and centralized joint critics (Lowe et al., 2017; Foerster et al., 2017; Sunehag et al., 2018; Rashid et al., 2018). Nevertheless, these methods usually require centralized parameters or centralized communication assumptions. Thus, there is considerable interest in multi-agent learning to find an algorithm that, while having minimal requirements and computational cost as independent learners, also improves convergence performance at the same time.
This paper presents the Multi-Agent Trust Region Learning (MATRL) algorithm that augments the trust-region ILs with a meta-game analysis to improve the stability and efficiency of learning. In MATRL, a trust region trial step for an agents’ payoff improvement is implemented by independent learners, which gives a predicted policy based on the current policy. Then, an empirical policy-space meta-game is constructed to compare the expected advantage of predicted policies with the current policies. By solving the meta-game, MATRL finds a restricted step by aggregating the current and predicted policies using meta-game Nash Equilibrium. Finally, MATRL takes the best responses based on the aggregated policies from last step for each agent to explore because the found TSR is not always strict stable. MATRL is, therefore, able to provide a weak stable solution compared with the naive independent learners. Based on trust region independent learners, MATRL does not need extra parameters, simulations, or modifications to the independent learner itself. We provide insights into the empirical meta-game in Section 3.2, showing that an approximated Nash equilibrium of the meta-game is a weak stable fixed point of the underlying game. Our experiments demonstrate that MATRL significantly outperforms deep independent learners (Schulman et al., 2017) with the same hyper-parameters, centralized VDN (Sunehag et al., 2018), QMIX (Rashid et al., 2018) methods in discrete action grid-worlds, centralized MADDPG (Lowe et al., 2017) in a continuous action multi-agent MuJoCo task (de Witt et al., 2020) and zero-sum multi-agent Atari (Terry & Black, 2020).

heading: 2 PRELIMINARY
text: A Stochastic Game (Shapley, 1953; Littman, 1994) can be defined as: G = 〈N ,S, {Ai}, {Ri},P, p0, γ〉, where N is a set of agents, n = |N | is the number of agents and S denotes the state space. Ai is the action space for agent i. A = A1 × · · · × An = Ai ×A−i is the joint action space, and for the simplicity we use −i denotes the other agents except agent i. Ri = Ri(s, ai, a−i) is the reward function for agent i ∈ N . P : S ×A×S → [0, 1] is the transition function. p0 is the initial state distribution, γ ∈ [0, 1] is a discount factor. Each agent i ∈ N has a stochastic policy πi(ai|s) : S ×Ai → [0, 1], and aims to maximize its long term discounted return:
ηi(πi, π−i) = Es0,a0i ,a0−i··· [ ∞∑ t=0 γtRi(s t, ati, a t −i) ] , (1)
where s0 ∼ p0, st+1 ∼ P(st+1|st, ati, at−i), ati ∼ πi(ati|τ ti ). We then can have the standard definitions of the state-action value function Qπi,π−ii (s t, ati, a t −i) =
Est+1,at+1i ,at+1−i ···[ ∑∞ l=0 γ lRi(s t+l, at+li , a t+l −i )], the value function V πi,π−i i (s t) =
Eati,at−i,st+1···[ ∑∞ l=0 γ lRi(s t+l, at+li , a t+l −i )], and the advantage function A πi,π−i i (s t, ati, a t −i) = Q πi,π−i i (s t, ati, a t −i)− V πi,π−i i (s t) given the state and joint action.

heading: 3 MULTI-AGENT TRUST REGION POLICY OPTIMIZATION
text: A trust region algorithm aims to answer two questions: how to compute a trust region trial step and whether a trial step should be accepted. In multi-agent learning, a trust region trial step towards agents’ payoff improvement can be easily implemented with independent learners, and we call the independent payoff improvement area as Trust Payoff Region(TPR). The remaining issue is
Under review as a conference paper at ICLR 2021
<latexit sha1_base64="2oAtTy/Ncb1ME0cbS1OEdDjtsJk=">AAACFHicdVDLSgMxFL1TX7W+qi7dBIvgqsxIoQouCm5cVrAPaIeSSTNtaJIZkoxQhn6EGxf6K+7ErXv/xKWZdha2xQOBwzn3JicniDnTxnW/ncLG5tb2TnG3tLd/cHhUPj5p6yhRhLZIxCPVDbCmnEnaMsxw2o0VxSLgtBNM7jK/80SVZpF8NNOY+gKPJAsZwcZKnX7MBimbDcoVt+rOgdaJl5MK5GgOyj/9YUQSQaUhHGvd89zY+ClWhhFOZ6V+ommMyQSPaM9SiQXVfjqPO0MXVhmiMFL2SIPm6t+NFAutpyKwkwKbsV71MvE/L7tRL72fBmIljwmv/ZTJODFUkkWcMOHIRChrCA2ZosTwqSWYKGZ/hMgYK0yM7bFkq/JWi1kn7auqV6vePNQqjdu8tCKcwTlcggd1aMA9NKEFBCbwDK/w5rw4786H87kYLTj5zikswfn6BXmRn8c=</latexit>
<latexit sha1_base64="Klbc1KwZmtVbQeokYl+k7FxbmTM=">AAACFXicdVDLSgMxFL1TX7W+qi7dBIvgxjIjBRVcFNy4rGAf0A4lk2ba0CQzJBmhDP0JNy70V9yJW9f+iUsz7SxsiwcCh3PuTU5OEHOmjet+O4W19Y3NreJ2aWd3b/+gfHjU0lGiCG2SiEeqE2BNOZO0aZjhtBMrikXAaTsY32V++4kqzSL5aCYx9QUeShYygo2VOr2Y9dMLNu2XK27VnQGtEi8nFcjR6Jd/eoOIJIJKQzjWuuu5sfFTrAwjnE5LvUTTGJMxHtKupRILqv10lneKzqwyQGGk7JEGzdS/GykWWk9EYCcFNiO97GXif152o154Pw3EUh4TXvspk3FiqCTzOGHCkYlQVhEaMEWJ4RNLMFHM/giREVaYGFtkyVblLRezSlqXVa9WvXmoVeq3eWlFOIFTOAcPrqAO99CAJhDg8Ayv8Oa8OO/Oh/M5Hy04+c4xLMD5+gXr8p/+</latexit>
<latexit sha1_base64="nVAjToaXS6TUfJk8m1M/i0MhQuI=">AAACGnicdVDLSgMxFM3UV62vqks3wSK4KjNSUMFFwY3LCvYB7VAyaaYNTTJjckcoQ7/DjQv9FXfi1o1/4tJMOwvb4oELh3MfOTlBLLgB1/12CmvrG5tbxe3Szu7e/kH58KhlokRT1qSRiHQnIIYJrlgTOAjWiTUjMhCsHYxvs377iWnDI/UAk5j5kgwVDzklYCW/NyKQ9mI+7ae2yhW36s6AV4mXkwrK0eiXf3qDiCaSKaCCGNP13Bj8lGjgVLBpqZcYFhM6JkPWtVQRyYyfzkxP8ZlVBjiMtC0FeKb+3UiJNGYiAzspCYzMci8T/+tlF83C+2kgl/xAeOWnXMUJMEXndsJEYIhwlhMecM0oiIklhGpuf4TpiGhCwaZZslF5y8GsktZF1atVr+9rlfpNHloRnaBTdI48dInq6A41UBNR9Iie0St6c16cd+fD+ZyPFpx85xgtwPn6BbVvopQ=</latexit>
<latexit sha1_base64="y8DmZzR1FkK1TScjZBKVMREfb1A=">AAACG3icdVDLSgMxFL3js9ZX1aWbYBHcWGakoIKLghuXFewDOrVk0kwbmmSGJCOUof/hxoX+ijtx68I/cWmmnYVt8UDC4Zx7b25OEHOmjet+Oyura+sbm4Wt4vbO7t5+6eCwqaNEEdogEY9UO8CaciZpwzDDaTtWFIuA01Ywus381hNVmkXywYxj2hV4IFnICDZWevSH2KR+zCa99NxepbJbcadAy8TLSRly1HulH78fkURQaQjHWnc8NzbdFCvDCKeTop9oGmMywgPasVRiQXU3nW49QadW6aMwUvZIg6bq344UC63HIrCVApuhXvQy8T8vm6jn3k8DsbCPCa+6KZNxYqgks3XChCMToSwo1GeKEsPHlmCimP0RIkOsMDE2zqKNylsMZpk0LypetXJ9Xy3XbvLQCnAMJ3AGHlxCDe6gDg0goOAZXuHNeXHenQ/nc1a64uQ9RzAH5+sXKnyiyw==</latexit>
<latexit sha1_base64="9WUTxmFWU67i+UjWWsa7nYUvrow=">AAACFnicdVDLSgMxFL1TX7W+qi7dBIsgLsqMFFRwUXDjsoJ9SDuWTJppQ5PMkGSEMvQr3LjQX3Enbt36Jy7NtF3YFg8EDufcm5ycIOZMG9f9dnIrq2vrG/nNwtb2zu5ecf+goaNEEVonEY9UK8CaciZp3TDDaStWFIuA02YwvMn85hNVmkXy3oxi6gvclyxkBBsrPXRi1k3Z+PGsWyy5ZXcCtEy8GSnBDLVu8afTi0giqDSEY63bnhsbP8XKMMLpuNBJNI0xGeI+bVsqsaDaTyeBx+jEKj0URsoeadBE/buRYqH1SAR2UmAz0IteJv7nZTfquffTQCzkMeGlnzIZJ4ZKMo0TJhyZCGUdoR5TlBg+sgQTxeyPEBlghYmxTRZsVd5iMcukcV72KuWru0qpej0rLQ9HcAyn4MEFVOEWalAHAgKe4RXenBfn3flwPqejOWe2cwhzcL5+AaxmoGM=</latexit>
<latexit sha1_base64="ymbUExUlNEE2ahN3gNpcw6isMQ8=">AAACF3icdVDLSgMxFL3js9ZX1aWbYBFEsMxIQQUXBTcuK9gHtmPJpGkbmmSGJCOUoX/hxoX+ijtx69I/cWmmnYVt8UDgcM69yckJIs60cd1vZ2l5ZXVtPbeR39za3tkt7O3XdRgrQmsk5KFqBlhTziStGWY4bUaKYhFw2giGN6nfeKJKs1Dem1FEfYH7kvUYwcZKD+2IdZIzNn487RSKbsmdAC0SLyNFyFDtFH7a3ZDEgkpDONa65bmR8ROsDCOcjvPtWNMIkyHu05alEguq/WSSeIyOrdJFvVDZIw2aqH83Eiy0HonATgpsBnreS8X/vPRGPfN+Eoi5PKZ36SdMRrGhkkzj9GKOTIjSklCXKUoMH1mCiWL2R4gMsMLE2CrztipvvphFUj8veeXS1V25WLnOSsvBIRzBCXhwARW4hSrUgICEZ3iFN+fFeXc+nM/p6JKT7RzADJyvXx80oJo=</latexit>
<latexit sha1_base64="2oAtTy/Ncb1ME0cbS1OEdDjtsJk=">AAACFHicdVDLSgMxFL1TX7W+qi7dBIvgqsxIoQouCm5cVrAPaIeSSTNtaJIZkoxQhn6EGxf6K+7ErXv/xKWZdha2xQOBwzn3JicniDnTxnW/ncLG5tb2TnG3tLd/cHhUPj5p6yhRhLZIxCPVDbCmnEnaMsxw2o0VxSLgtBNM7jK/80SVZpF8NNOY+gKPJAsZwcZKnX7MBimbDcoVt+rOgdaJl5MK5GgOyj/9YUQSQaUhHGvd89zY+ClWhhFOZ6V+ommMyQSPaM9SiQXVfjqPO0MXVhmiMFL2SIPm6t+NFAutpyKwkwKbsV71MvE/L7tRL72fBmIljwmv/ZTJODFUkkWcMOHIRChrCA2ZosTwqSWYKGZ/hMgYK0yM7bFkq/JWi1kn7auqV6vePNQqjdu8tCKcwTlcggd1aMA9NKEFBCbwDK/w5rw4786H87kYLTj5zikswfn6BXmRn8c=</latexit>
<latexit sha1_base64="Klbc1KwZmtVbQeokYl+k7FxbmTM=">AAACFXicdVDLSgMxFL1TX7W+qi7dBIvgxjIjBRVcFNy4rGAf0A4lk2ba0CQzJBmhDP0JNy70V9yJW9f+iUsz7SxsiwcCh3PuTU5OEHOmjet+O4W19Y3NreJ2aWd3b/+gfHjU0lGiCG2SiEeqE2BNOZO0aZjhtBMrikXAaTsY32V++4kqzSL5aCYx9QUeShYygo2VOr2Y9dMLNu2XK27VnQGtEi8nFcjR6Jd/eoOIJIJKQzjWuuu5sfFTrAwjnE5LvUTTGJMxHtKupRILqv10lneKzqwyQGGk7JEGzdS/GykWWk9EYCcFNiO97GXif152o154Pw3EUh4TXvspk3FiqCTzOGHCkYlQVhEaMEWJ4RNLMFHM/giREVaYGFtkyVblLRezSlqXVa9WvXmoVeq3eWlFOIFTOAcPrqAO99CAJhDg8Ayv8Oa8OO/Oh/M5Hy04+c4xLMD5+gXr8p/+</latexit>
<latexit sha1_base64="nVAjToaXS6TUfJk8m1M/i0MhQuI=">AAACGnicdVDLSgMxFM3UV62vqks3wSK4KjNSUMFFwY3LCvYB7VAyaaYNTTJjckcoQ7/DjQv9FXfi1o1/4tJMOwvb4oELh3MfOTlBLLgB1/12CmvrG5tbxe3Szu7e/kH58KhlokRT1qSRiHQnIIYJrlgTOAjWiTUjMhCsHYxvs377iWnDI/UAk5j5kgwVDzklYCW/NyKQ9mI+7ae2yhW36s6AV4mXkwrK0eiXf3qDiCaSKaCCGNP13Bj8lGjgVLBpqZcYFhM6JkPWtVQRyYyfzkxP8ZlVBjiMtC0FeKb+3UiJNGYiAzspCYzMci8T/+tlF83C+2kgl/xAeOWnXMUJMEXndsJEYIhwlhMecM0oiIklhGpuf4TpiGhCwaZZslF5y8GsktZF1atVr+9rlfpNHloRnaBTdI48dInq6A41UBNR9Iie0St6c16cd+fD+ZyPFpx85xgtwPn6BbVvopQ=</latexit>
<latexit sha1_base64="y8DmZzR1FkK1TScjZBKVMREfb1A=">AAACG3icdVDLSgMxFL3js9ZX1aWbYBHcWGakoIKLghuXFewDOrVk0kwbmmSGJCOUof/hxoX+ijtx68I/cWmmnYVt8UDC4Zx7b25OEHOmjet+Oyura+sbm4Wt4vbO7t5+6eCwqaNEEdogEY9UO8CaciZpwzDDaTtWFIuA01Ywus381hNVmkXywYxj2hV4IFnICDZWevSH2KR+zCa99NxepbJbcadAy8TLSRly1HulH78fkURQaQjHWnc8NzbdFCvDCKeTop9oGmMywgPasVRiQXU3nW49QadW6aMwUvZIg6bq344UC63HIrCVApuhXvQy8T8vm6jn3k8DsbCPCa+6KZNxYqgks3XChCMToSwo1GeKEsPHlmCimP0RIkOsMDE2zqKNylsMZpk0LypetXJ9Xy3XbvLQCnAMJ3AGHlxCDe6gDg0goOAZXuHNeXHenQ/nc1a64uQ9RzAH5+sXKnyiyw==</latexit>
<latexit sha1_base64="9WUTxmFWU67i+UjWWsa7nYUvrow=">AAACFnicdVDLSgMxFL1TX7W+qi7dBIsgLsqMFFRwUXDjsoJ9SDuWTJppQ5PMkGSEMvQr3LjQX3Enbt36Jy7NtF3YFg8EDufcm5ycIOZMG9f9dnIrq2vrG/nNwtb2zu5ecf+goaNEEVonEY9UK8CaciZp3TDDaStWFIuA02YwvMn85hNVmkXy3oxi6gvclyxkBBsrPXRi1k3Z+PGsWyy5ZXcCtEy8GSnBDLVu8afTi0giqDSEY63bnhsbP8XKMMLpuNBJNI0xGeI+bVsqsaDaTyeBx+jEKj0URsoeadBE/buRYqH1SAR2UmAz0IteJv7nZTfquffTQCzkMeGlnzIZJ4ZKMo0TJhyZCGUdoR5TlBg+sgQTxeyPEBlghYmxTRZsVd5iMcukcV72KuWru0qpej0rLQ9HcAyn4MEFVOEWalAHAgKe4RXenBfn3flwPqejOWe2cwhzcL5+AaxmoGM=</latexit>
<latexit sha1_base64="ymbUExUlNEE2ahN3gNpcw6isMQ8=">AAACF3icdVDLSgMxFL3js9ZX1aWbYBFEsMxIQQUXBTcuK9gHtmPJpGkbmmSGJCOUoX/hxoX+ijtx69I/cWmmnYVt8UDgcM69yckJIs60cd1vZ2l5ZXVtPbeR39za3tkt7O3XdRgrQmsk5KFqBlhTziStGWY4bUaKYhFw2giGN6nfeKJKs1Dem1FEfYH7kvUYwcZKD+2IdZIzNn487RSKbsmdAC0SLyNFyFDtFH7a3ZDEgkpDONa65bmR8ROsDCOcjvPtWNMIkyHu05alEguq/WSSeIyOrdJFvVDZIw2aqH83Eiy0HonATgpsBnreS8X/vPRGPfN+Eoi5PKZ36SdMRrGhkkzj9GKOTIjSklCXKUoMH1mCiWL2R4gMsMLE2CrztipvvphFUj8veeXS1V25WLnOSsvBIRzBCXhwARW4hSrUgICEZ3iFN+fFeXc+nM/p6JKT7RzADJyvXx80oJo=</latexit>
<latexit sha1_base64="dGmSt7Qks3BA2LjCv++bzX6uitc=">AAACH3icdVDNS8MwHE3n15xfVY9egkPwNFoRVPAw8OJxgvuAtZY0S7ewpA1JOhil/4kXD/qveBOv+088mm49uA0fBB7v/X7JywsFo0o7zsyqbGxube9Ud2t7+weHR/bxSUclqcSkjROWyF6IFGE0Jm1NNSM9IQniISPdcPxQ+N0JkYom8bOeCuJzNIxpRDHSRgps2xM0yGj+knlCUk7ywK47DWcOuE7cktRBiVZg/3iDBKecxBozpFTfdYT2MyQ1xYzkNS9VRCA8RkPSNzRGnCg/myfP4YVRBjBKpDmxhnP170aGuFJTHppJjvRIrXqF+J9X3KiW3s9CvpJHR7d+RmORahLjRZwoZVAnsCgLDqgkWLOpIQhLan4E8QhJhLWptGaqcleLWSedq4Z73bh7uq4378vSquAMnINL4IIb0ASPoAXaAIMJeAXv4MN6sz6tL+t7MVqxyp1TsARr9gvEf6Qh</latexit>
<latexit sha1_base64="pyoziTv79JsJ9qsAPoGpMJD40Kc=">AAACIHicdVDNS8MwHE39nPOr06OX4BC8OFoZqOBh4MXjBPcBay1plm5hSVqSVBmlf4oXD/qveBOP+pd4NN12cBs+CDze+/2SlxcmjCrtOF/Wyura+sZmaau8vbO7t29XDtoqTiUmLRyzWHZDpAijgrQ01Yx0E0kQDxnphKObwu88EqloLO71OCE+RwNBI4qRNlJgV7yEBtkZzR8yL5GUkzywq07NmQAuE3dGqmCGZmD/eP0Yp5wIjRlSquc6ifYzJDXFjORlL1UkQXiEBqRnqECcKD+bRM/hiVH6MIqlOULDifp3I0NcqTEPzSRHeqgWvUL8zytuVHPvZyFfyKOjSz+jIkk1EXgaJ0oZ1DEs2oJ9KgnWbGwIwpKaH0E8RBJhbTotm6rcxWKWSfu85tZrV3f1auN6VloJHIFjcApccAEa4BY0QQtg8ASewSt4s16sd+vD+pyOrliznUMwB+v7Fzi1pFg=</latexit>
<latexit sha1_base64="GgMP7Zgs4dXCmTjvBxmEYdeShb4=">AAACG3icdVDLSgMxFL3js9ZX1aWbYBHcWGakoIKLghuXFewDOmPJpGkbmmSGJCOUof/hxoX+ijtx68I/cWmmnYVt8UDC4Zx7b25OGHOmjet+Oyura+sbm4Wt4vbO7t5+6eCwqaNEEdogEY9UO8SaciZpwzDDaTtWFIuQ01Y4us381hNVmkXywYxjGgg8kKzPCDZWevRDrFI/ZpNuem6vUtmtuFOgZeLlpAw56t3Sj9+LSCKoNIRjrTueG5sgxcowwumk6CeaxpiM8IB2LJVYUB2k060n6NQqPdSPlD3SoKn6tyPFQuuxCG2lwGaoF71M/M/LJuq599NQLOxj+ldBymScGCrJbJ1+wpGJUBYU6jFFieFjSzBRzP4IkSFWmBgbZ9FG5S0Gs0yaFxWvWrm+r5ZrN3loBTiGEzgDDy6hBndQhwYQUPAMr/DmvDjvzofzOStdcfKeI5iD8/ULHNCiww==</latexit>
<latexit sha1_base64="ID+Z/3jlew3kk/MK1ozKW97Oqfo=">AAACGnicdVDLSgMxFL1TX7W+qi7dBIvgqsxIQQUXBTcuK9gHdIaSSTNtaJIZk4xQhn6HGxf6K+7ErRv/xKVpOwvb4oELh3MfOTlhwpk2rvvtFNbWNza3itulnd29/YPy4VFLx6kitEliHqtOiDXlTNKmYYbTTqIoFiGn7XB0O+23n6jSLJYPZpzQQOCBZBEj2Fgp8EOsMj9hk15mq1xxq+4MaJV4OalAjkav/OP3Y5IKKg3hWOuu5yYmyLAyjHA6KfmppgkmIzygXUslFlQH2cz0BJ1ZpY+iWNmSBs3UvxsZFlqPRWgnBTZDvdybiv/1phf1wvtZKJb8mOgqyJhMUkMlmduJUo5MjKY5oT5TlBg+tgQTxeyPEBlihYmxaZZsVN5yMKukdVH1atXr+1qlfpOHVoQTOIVz8OAS6nAHDWgCgUd4hld4c16cd+fD+ZyPFpx85xgW4Hz9AqfLoow=</latexit>
revolved by finding a restricted step leading to a stable point in the joint policy space, denoted as Trust Stable Region(TSR). In other words, multi-agent trust region learning (MATRL) decomposes the trust region learning into two parts: firstly, find a trust payoff region between current policy πi and predicted policy π̂i; then, with the help of the predicted policy, a precise method can, to some extent, approximate a weak stable fixed point. Instead of line searching in a single-agent payoff improvement, MATRL searches for the joint policy space to achieve a weak stable fixed point (see Fig. 2). Essentially, MATRL is a simple extension of the single-agent TRPO to MAS where independent learners learn to find a stable point between current policy and predicted policy. To solve the TSR, we assume the knowledge about other agents’ policies during the training to find weak stable points via empirical meta-game analysis, while the execution can still be fully decentralized. We explain every step of MATRL in detail in the following sections.

heading: 3.1 INDEPENDENT TRUST PAYOFF IMPROVEMENT
text: Single-agent reinforcement learning algorithms can be straightforwardly applied to multi-agent learning, where we assume that all agents behave independently (Tan, 1993). In this section, we have chosen the policy-based reinforcement learning method as independent learners. In multi-agent games, the environment becomes a Markov decision process for agent i when each of the other agents plays according to a fixed policy. We set agent i’s to make a monotonic improvement against the fixed opponent policies. Thus, at each iteration, the policy is updated by maximizing the utility function ηi over a local neighborhood of the current joint policy πi, π−i: π̂i = arg maxπi∈Πi ηi(πi, π−i) based on the trajectories sampled by πi, π−i. We can adopt trust region policy optimization (e.g., PPO (Schulman et al., 2017)), which constrains step size in the policy update:
π̂i = arg max πi∈Πθi
ηi(πi, π−i) s.t. D (πi, π̂i) ≤ δi, (2)
where D is a distance measurement and δi is a constraint. Independent trust region learners produce the monotonically improved policy π̂i which guarantees ηi (π̂i, π−i) ≥ ηi (πi, π−i) and give a trust payoff bound by π̂i. Due to the simultaneous policy improvement without awareness of other agents , however, the lower bound of payoff improvement from single-agent Schulman et al. (2015) no longer holds for multi-agent payoff improvement. Following the similar proof procedures, we can obtain a precise lower bound for a multi-agent simultaneous trust payoff region in Theorem 1: Theorem 1 (Independent Trust Payoff Region). Denote the expected advantage gain when πi, π−i → π̂i, π̂−i as:
g πi,π−i i (π̂i, π̂−i) := ∑ s pπi,π−i(s) ∑ ai π̂i(ai|s) ∑ a−i π̂−i(a−i|s)Aπi,π−ii (s, ai, a−i). (3)
Let αi = DmaxTV (πi, π̂i) = maxsDTV(πi(·|s)‖π̂i(·|s)) for agent i, where DTV is total variation divergence (Schulman et al., 2015). Then, the following lower bound can be derived for multi-agent independent trust region optimization:
ηi(π̂i, π̂−i)− ηi(πi, π−i) ≥ gπi,π−ii (π̂i, π̂−i)− 4γ i
(1− γ)2 (αi + α−i − αiα−i) 2, (4) where i = maxs,a−i,a−i ∣∣Aπi,π−ii (s, ai, a−i)∣∣.
Under review as a conference paper at ICLR 2021
Proof. See Appendix B.
Based on the independent trust payoff improvement, although the predicted policy π̂i will guide us in determining the step size of the TPR, but the stability of (π̂i, π̂−i) is still unknown. As shown in Theorem 1, an agent’s lower bound is roughly O(4α2), which is four times larger than the single-agent lower bound trust region of O(α2) (Kakade & Langford, 2002). Furthermore, i = maxs,a−i,a−i
∣∣Aπi,π−ii (s, ai, a−i)∣∣ depends on the other agents’s action a−i that would be very large when agents have conflicting interests. Therefore, the most critical issue underlying the multi-agent trust region learning is to find a TSR after the TPR. In next section, we will illustrate how to search for a weak stable fixed point within the TPR, based on the policy-space meta-game analysis.

heading: 3.2 APPROXIMATING WEAK STABLE FIXED POINT
text: In multi-agent trust region learning, TSR is one of the essential parts. Since each iteration of MATRL requires solving the TPR and TSR sub-problems, finding the efficient solver for stable trust region sub-problems is very important. Instead of using the stable fixed points (Balduzzi et al., 2018) as TSR, we choose weak stable fixed point in Definition 1 which is much easier to be found. To maximize the objective defined in Eq. 1 we could ask that reasonable algorithms avoid all strict minimums (a.k.a unstable fixed points), which imposes only that agents are well-behaved regarding strict minimum even if their individual behaviors is not self-interested (Letcher, 2020), and we say a point is in TSR if it is weak stable fixed point.
Definition 1 (Weak Stable Fixed Point in Restricted Underlaying Game). Consider a restricted underlying game, where each agent’s policy space is restricted to open sets Π̄i = [πi, π̂i] ⊆ Πi. Denote the simultaneous gradient of the restricted underlying game as ξ = (∇πigi,∇π−ig−i) and Hessian H = ∇ξ. We call (π̄i, π̄−i) a fixed point if ξ(π̄i, π̄−i) = 0. We then say (π̄i, π̄−i) is a weak stable fixed point if H(π̄i, π̄−i) 01, which avoids unstable fixed points (strict minimum). A trust stable region within weak stable fixed points is reasonable if it converges only to fixed points and avoids unstable fixed points almost surely.
Given that we already have the TPR, which produces a predicted policy, with the knowledge about all the agents policies, it is natural to conduct an empirical game-theoretic analysis (Tuyls et al., 2018) to search for a weak stable fixed point in the area bounded by current policy pair predicted policy pair. We then define a meta-game that each agent i has only two strategies πi, π̂i for each agent i:
M(πi, π̂i, π−i, π̂−i) = ( gi,−ii , g i,−i −i g i,−î i , g i,−î −i
gî,−ii , g î,−i −i g î,−î i , g î,−î −i
) , (5)
where gî,−îi = g πi,π−i i (π̂i, π̂−i) (as defined in Eq. 3) is an empirical payoff entry of the metagame, and note gi,−ii = 0 as it has an expected advantage over itself. Compared with using the ηi(π̂i, π̂−i) = ηi(πi, π−i) + g î,−î i as the meta-game payoff, g î,−î i has lower variance and is easier to approximate because ηi(πi, π−i) is a constant baseline. However, the most of entries inM are unknown, it often requires lots of extra simulations to estimate the payoff entries (e.g., gî,−îi ) in EGTA. Instead, we reuse the trajectories in the TPR step to approximate the gî,−îi by ignoring small changes in state visitation density caused by the πi → π̂i (Schulman et al., 2015). Take two-agent case as an example, as we can see in Eq. 5, the meta-gameM becomes a 2 × 2 matrix-form game, which is much smaller in size than the whole underlaying game. To this end, we can use the existing Nash solvers (e.g. CMA-ES (Hansen et al., 2003)) for matrix-form games to compute a mixed Nash equilibrium ρi, ρ−i = NashSolver(M) for the meta-gameM, where ρi and ρ−i ∈ [0, 1], and the mixed Nash equilibrium of the meta-game is also an approximated equilibrium of the restricted underlying game (Tuyls et al., 2020). Then, the trust stable region policies π̄i, π̄−i can be aggregated based on current policy πi and predicted policy π̂i in TPR for each agent i. In the TPR step, we require ILs enjoy the monotonic improvement against the fixed opponent policies, in which the change from πi to π̂i is usually constrained by a small step size. Therefore, it is reasonable to assume there is a continuous and monotonic change in the restricted policy space between πi and π̂i. In this case, with ρi being agent i’s Nash Equilibrium policy in the meta-game, π̄i can be derived via the linear mixture: π̄i = ρiπi + (1− ρi)π̂i, which delimit agent i’s trust stable region. Now we can prove that (π̄i, π̄−i) is a weak stable fixed point for the underlying game in Theorem 2.
1In this paper, we want to maximize the return, not minimizing the loss, so we need to avoid strict minimum.
Under review as a conference paper at ICLR 2021
<latexit sha1_base64="JTwaVRPOBRz6uvQKqWETkzQvZ74=">AAACFHicdVDLSgMxFL1TX7W+qi7dBIvgqsyUQnVXcOOygn1AO5RMmmlDk8yQZIQy9CPcuNBfcSdu3fsnLs20s7AtHggczrk3OTlBzJk2rvvtFLa2d3b3ivulg8Oj45Py6VlHR4kitE0iHqlegDXlTNK2YYbTXqwoFgGn3WB6l/ndJ6o0i+SjmcXUF3gsWcgINlbqDmI2TNl8WK64VXcBtEm8nFQgR2tY/hmMIpIIKg3hWOu+58bGT7EyjHA6Lw0STWNMpnhM+5ZKLKj200XcObqyygiFkbJHGrRQ/26kWGg9E4GdFNhM9LqXif952Y165f00EGt5THjjp0zGiaGSLOOECUcmQllDaMQUJYbPLMFEMfsjRCZYYWJsjyVblbdezCbp1KpevXr7UK80a3lpRbiAS7gGDxrQhHtoQRsITOEZXuHNeXHenQ/nczlacPKdc1iB8/ULdo+fvQ==</latexit>
<latexit sha1_base64="2oAtTy/Ncb1ME0cbS1OEdDjtsJk=">AAACFHicdVDLSgMxFL1TX7W+qi7dBIvgqsxIoQouCm5cVrAPaIeSSTNtaJIZkoxQhn6EGxf6K+7ErXv/xKWZdha2xQOBwzn3JicniDnTxnW/ncLG5tb2TnG3tLd/cHhUPj5p6yhRhLZIxCPVDbCmnEnaMsxw2o0VxSLgtBNM7jK/80SVZpF8NNOY+gKPJAsZwcZKnX7MBimbDcoVt+rOgdaJl5MK5GgOyj/9YUQSQaUhHGvd89zY+ClWhhFOZ6V+ommMyQSPaM9SiQXVfjqPO0MXVhmiMFL2SIPm6t+NFAutpyKwkwKbsV71MvE/L7tRL72fBmIljwmv/ZTJODFUkkWcMOHIRChrCA2ZosTwqSWYKGZ/hMgYK0yM7bFkq/JWi1kn7auqV6vePNQqjdu8tCKcwTlcggd1aMA9NKEFBCbwDK/w5rw4786H87kYLTj5zikswfn6BXmRn8c=</latexit>
<latexit sha1_base64="Klbc1KwZmtVbQeokYl+k7FxbmTM=">AAACFXicdVDLSgMxFL1TX7W+qi7dBIvgxjIjBRVcFNy4rGAf0A4lk2ba0CQzJBmhDP0JNy70V9yJW9f+iUsz7SxsiwcCh3PuTU5OEHOmjet+O4W19Y3NreJ2aWd3b/+gfHjU0lGiCG2SiEeqE2BNOZO0aZjhtBMrikXAaTsY32V++4kqzSL5aCYx9QUeShYygo2VOr2Y9dMLNu2XK27VnQGtEi8nFcjR6Jd/eoOIJIJKQzjWuuu5sfFTrAwjnE5LvUTTGJMxHtKupRILqv10lneKzqwyQGGk7JEGzdS/GykWWk9EYCcFNiO97GXif152o154Pw3EUh4TXvspk3FiqCTzOGHCkYlQVhEaMEWJ4RNLMFHM/giREVaYGFtkyVblLRezSlqXVa9WvXmoVeq3eWlFOIFTOAcPrqAO99CAJhDg8Ayv8Oa8OO/Oh/M5Hy04+c4xLMD5+gXr8p/+</latexit>
<latexit sha1_base64="oWJphugGwXmCCKLYMNvie5TQmLg=">AAACFXicdVDLSgMxFL1TX7W+qi7dBIvgxjJTCuqu4MZlBfuAdiiZNNOGJpkhyQhl6E+4caG/4k7cuvZPXJppZ2FbPBA4nHNvcnKCmDNtXPfbKWxsbm3vFHdLe/sHh0fl45O2jhJFaItEPFLdAGvKmaQtwwyn3VhRLAJOO8HkLvM7T1RpFslHM42pL/BIspARbKzU7cdskF6x2aBccavuHGideDmpQI7moPzTH0YkEVQawrHWPc+NjZ9iZRjhdFbqJ5rGmEzwiPYslVhQ7afzvDN0YZUhCiNljzRorv7dSLHQeioCOymwGetVLxP/87Ib9dL7aSBW8pjwxk+ZjBNDJVnECROOTISyitCQKUoMn1qCiWL2R4iMscLE2CJLtipvtZh10q5VvXr19qFeadTy0opwBudwCR5cQwPuoQktIMDhGV7hzXlx3p0P53MxWnDynVNYgvP1C+jwn/Q=</latexit>
<latexit sha1_base64="7hWffr0w1h5HfU1UFRO49K6irPw=">AAACL3icdVBNS8MwGE79nPOr6tFLcAgedLRjoB6EiZedZKL7gHWMNEu3sKQtSSqM0qu/xosH/SviRbz6Dzyadj24DV8IeXie902e93FDRqWyrA9jaXlldW29sFHc3Nre2TX39lsyiAQmTRywQHRcJAmjPmkqqhjphIIg7jLSdsc3qd5+JELSwH9Qk5D0OBr61KMYKU31TeiIUdCnp9kVn9EEXkGHIzUSPL69vq8nfbNkla2s4CKwc1ACeTX65o8zCHDEia8wQ1J2bStUvRgJRTEjSdGJJAkRHqMh6WroI05kL842SeCxZgbQC4Q+voIZ+3ciRlzKCXd1Z2pSzmsp+Z+Wvihn/o9dPudHeRe9mPphpIiPp3a8iEEVwDQ8OKCCYMUmGiAsqN4I4hESCCsdcVFHZc8HswhalbJdLV/eVUu1Sh5aARyCI3ACbHAOaqAOGqAJMHgCz+AVvBkvxrvxaXxNW5eMfOYAzJTx/QvLU6mi</latexit>
<latexit sha1_base64="AI25SQjkSZdEb90uW+vNEgRkl0g=">AAACGHicdVDLSsNAFL3xWeur6tJNsAiuSlIK6q7gxmUF+4AmlMl00g6dR5iZCCX0M9y40F9xJ27d+ScunbRZ2BYPDBzOuXfmzIkSRrXxvG9nY3Nre2e3tFfePzg8Oq6cnHa0TBUmbSyZVL0IacKoIG1DDSO9RBHEI0a60eQu97tPRGkqxaOZJiTkaCRoTDEyVuoHY2SyIKGzAR1Uql7Nm8NdJ35BqlCgNaj8BEOJU06EwQxp3fe9xIQZUoZiRmblINUkQXiCRqRvqUCc6DCbR565l1YZurFU9gjjztW/GxniWk95ZCc5MmO96uXif15+o156P4v4Sh4T34QZFUlqiMCLOHHKXCPdvCV3SBXBhk0tQVhR+yMXj5FC2Nguy7Yqf7WYddKp1/xG7fahUW3Wi9JKcA4XcAU+XEMT7qEFbcAg4Rle4c15cd6dD+dzMbrhFDtnsATn6xfBuKF+</latexit>
<latexit sha1_base64="14FWVV+c0vmlbBut4VMcU61X8Fw=">AAACG3icdVDLSgMxFL1TX7W+qi7dBIvgxjJTCuqu4MZlBdsK7VgyaaYNTTJDkhHK0P9w40J/xZ24deGfuDTTzsK2eCDhcM69NzcniDnTxnW/ncLa+sbmVnG7tLO7t39QPjxq6yhRhLZIxCP1EGBNOZO0ZZjh9CFWFIuA004wvsn8zhNVmkXy3kxi6gs8lCxkBBsrPfZG2KS9mE376YW9yhW36s6AVomXkwrkaPbLP71BRBJBpSEca9313Nj4KVaGEU6npV6iaYzJGA9p11KJBdV+Ott6is6sMkBhpOyRBs3Uvx0pFlpPRGArBTYjvexl4n9eNlEvvJ8GYmkfE175KZNxYqgk83XChCMToSwoNGCKEsMnlmCimP0RIiOsMDE2zpKNylsOZpW0a1WvXr2+q1catTy0IpzAKZyDB5fQgFtoQgsIKHiGV3hzXpx358P5nJcWnLznGBbgfP0CJ3qiwQ==</latexit>
<latexit sha1_base64="IjUiooJmwIdWtqMXG/+LJLO/1Hw=">AAACKXicdVDLSsNAFJ3UV62vqDvdBIvgoi2JFNRdwY3LCvYBbQyT6aQdOjMJMxOhhIBf48aF/oo7detPuHTSBrEtHhg499zH3Hv8iBKpbPvDKKysrq1vFDdLW9s7u3vm/kFbhrFAuIVCGoquDyWmhOOWIoribiQwZD7FHX98neU7D1hIEvI7NYmwy+CQk4AgqLTkmUdDLyHpfUIqVZJWdFD9jTyzbNfsKaxl4uSkDHI0PfO7PwhRzDBXiEIpe44dKTeBQhFEcVrqxxJHEI3hEPc05ZBh6SbTG1LrVCsDKwiFflxZU/VvRwKZlBPm60oG1Ugu5jLxv1w2Uc79n/hsYR8VXLoJ4VGsMEezdYKYWiq0MtusAREYKTrRBCJB9EUWGkEBkdLmlrRVzqIxy6R9XnPqtavberlh56YVwTE4AWfAARegAW5AE7QAAo/gCbyAV+PZeDPejc9ZacHIew7BHIyvH1Eip14=</latexit>
<latexit sha1_base64="mub6YIed4oUikSXx8GXpH4LMe7A=">AAACNXicdVC7TsMwFHV4lvIKMLJYVCCGtkpQJWCrxMJYJPqQ2hA5rtNatZPIdpCqKH/A17AwwI8wsCFWVkacNgNNxZEsHZ1z7/W9x4sYlcqy3o2V1bX1jc3SVnl7Z3dv3zw47MgwFpi0cchC0fOQJIwGpK2oYqQXCYK4x0jXm9xkfveRCEnD4F5NI+JwNAqoTzFSWnLNs5Gb0PQhodXaYIyU5mlVS7WC5poVq27NAJeJnZMKyNFyzZ/BMMQxJ4HCDEnZt61IOQkSimJG0vIgliRCeIJGpK9pgDiRTjK7J4WnWhlCPxT6BQrO1L8dCeJSTrmnKzlSY1n0MvE/L5soF/5PPF7YR/lXTkKDKFYkwPN1/JhBFcIsQjikgmDFppogLKi+COIxEggrHXRZR2UXg1kmnYu63ahf3zUqTSsPrQSOwQk4Bza4BE1wC1qgDTB4As/gFbwZL8aH8Wl8zUtXjLznCCzA+P4FMZWs+A==</latexit>
<latexit sha1_base64="PEyTuz6NDUY4C6gRL4r+IMOl5+o=">AAACQXicdZBNS8MwGMfT+TbnW9Wjl+AQPGyjHQP1NvDicYJ7ga2WNEu3sKQtSSqM0u/hp/HiQb+CH8GbeBK8mG49uE0fCPz4/58kz/P3Ikalsqw3o7C2vrG5Vdwu7ezu7R+Yh0cdGcYCkzYOWSh6HpKE0YC0FVWM9CJBEPcY6XqT68zvPhAhaRjcqWlEHI5GAfUpRkpLrlkfuQlN75PBGCkNlWoOaUUb1T8d1yxbNWtWcBXsHMogr5Zrfg2GIY45CRRmSMq+bUXKSZBQFDOSlgaxJBHCEzQifY0B4kQ6yWy3FJ5pZQj9UOgTKDhTf99IEJdyyj3dyZEay2UvE//zshflwv+Jx5fmUf6lk9AgihUJ8HwcP2ZQhTCLEw6pIFixqQaEBdUbQTxGAmGlQy/pqOzlYFahU6/ZjdrVbaPctPLQiuAEnIJzYIML0AQ3oAXaAINH8ARewKvxbLwbH8bnvLVg5HeOwUIZ3z9XDrKS</latexit>
<latexit sha1_base64="Fw1dfCbZJkKFI2hnPQ98LMPUPAY=">AAACNXicdZA9T8MwEIYdPkv5CjCyWFQghrZKUCVgq8TCWCT6IbUhcly3tWo7ke0gVVH+Ab+GhQH+CAMbYmVlxGkz0FacdNKr5+7suzeIGFXacd6tldW19Y3NwlZxe2d3b98+OGypMJaYNHHIQtkJkCKMCtLUVDPSiSRBPGCkHYxvsnr7kUhFQ3GvJxHxOBoKOqAYaYN8+2zoJzR9SHojpI0oV0waVMkYLVdynPp2yak604DLws1FCeTR8O2fXj/EMSdCY4aU6rpOpL0ESU0xI2mxFysSITxGQ9I1UiBOlJdM70nhqSF9OAilSaHhlP6dSBBXasID08mRHqnFWgb/q2Uvqrn/k4Av7KMHV15CRRRrIvBsnUHMoA5hZiHsU0mwZhMjEJbUXATxCEmEtTG6aKxyF41ZFq2LqlurXt/VSnUnN60AjsEJOAcuuAR1cAsaoAkweALP4BW8WS/Wh/Vpfc1aV6x85gjMhfX9CzS8rPg=</latexit>
<latexit sha1_base64="FJvkU7DV4jSSBKrnDinbQeKHKfc=">AAACSnicdVBdS8MwFE3n1Dm/qj76EhzCBBntGKiIMPHFxwnuA9ZS0izbgklbklQYpT/GX+OLD/ro3/BJ8cV0K+I2vBA4Oefc5N7jR4xKZVnvRmGluLq2Xtoob25t7+yae/sdGcYCkzYOWSh6PpKE0YC0FVWM9CJBEPcZ6foPN5nefSRC0jC4V5OIuByNAjqkGClNeeal4yOROBFNvYSm8Ao6HKmx4EnrOq1qOmNPoTNG6tekr2IcevTEMytWzZoWXAZ2Diogr5ZnfjqDEMecBAozJGXftiLlJkgoihlJy04sSYTwAxqRvoYB4kS6yXTJFB5rZgCHodAnUHDK/u1IEJdywn3tzFaQi1pG/qdlL8q5/xOfL8yjhuduQoMoViTAs3GGMYMqhFmucEAFwYpNNEBYUL0RxGMkEFY6/bKOyl4MZhl06jW7Ubu4a1Sa9Ty0EjgER6AKbHAGmuAWtEAbYPAEnsEreDNejA/jy/ieWQtG3nMA5qpQ/AEiarQ8</latexit>
<latexit sha1_base64="Qm796agVEwoLg34NMapQFt+yPJg=">AAACUHicdVFdS8MwFL2dX7N+TX30JTiECTraMVAfBMUXHye4TVjLSLNsC0vakqTCKP09/hpffFD8J75pWifqxAshJ+eem9x7EsScKe04r1ZpYXFpeaW8aq+tb2xuVbZ3OipKJKFtEvFI3gVYUc5C2tZMc3oXS4pFwGk3mFzl+e49lYpF4a2extQXeBSyISNYG6pfufQCLFMvZlk/PWYZOkeewHosRdq6zGqGL+gj5I2x/paZsxxHBTzsV6pO3SkC/QXuDFRhFq1+5c0bRCQRNNSEY6V6rhNrP8VSM8JpZnuJojEmEzyiPQNDLKjy02LUDB0YZoCGkTQr1Khgf1akWCg1FYFR5nOo+VxO/pfLb1S/3k8DMdePHp76KQvjRNOQfLYzTDjSEcrdRQMmKdF8agAmkpmJEBljiYk2f2Abq9x5Y/6CTqPuNutnN83qRWNmWhn2YB9q4MIJXMA1tKANBB7gEZ7hxXqy3qz3kvUp/dphF35Fyf4AJNS1JQ==</latexit>
<latexit sha1_base64="KjxX7vY8UaMI852OzA+r3Zb0HkE=">AAACfnicdVFNS8NAEN3G7/pV9ehlsSgKWhMRrAdB8OJRwapgaplsp3VxNwm7E7GE/EwP/hPBi5taUSsOLDzevJmdeROlSlry/deKNzE5NT0zO1edX1hcWq6trF7bJDMCWyJRibmNwKKSMbZIksLb1CDoSOFN9HhW5m+e0FiZxFc0SLGtoR/LnhRAjurUkjACk4epLDr5nizuHTRSY8FPeKiBHozOwfSLL6zh2QlDkqqL31VFiARDtP2jnSx2+bhyp1Or+w1/GPwvCEagzkZx0am9hd1EZBpjEgqsvQv8lNpuKJJCYVENM4spiEfo452DMWi07XxoTME3HdPlvcS4FxMfsj8rctDWDnTklOWCdjxXkv/lyo721/95pMfmoV6zncs4zQhj8TlOL1OcEl7egnelQUFq4AAII91GXDyAAUHuYlVnVTBuzF9wfdAIDhvHl4f10+bItFm2zjbYNgvYETtl5+yCtZhgL+y9MlmZ8pi35e15+59SrzKqWWO/wmt+AI1Qxkw=</latexit>
<latexit sha1_base64="RmEhXuKMESeXTLqItVf6386vzfs=">AAACe3icdVHfaxNBEN47tbZR21Qf+7IYhCgx3ElK44MQ8MXHCCYt5GKY20zSJbt3x+5cMRz3T/at/0lfBPeSKPmBAwsf33wzO/NNnClpKQgePP/J02dHz49Pai9evjo9q5+/Hto0NwIHIlWpuYnBopIJDkiSwpvMIOhY4XW8+Frlr+/QWJkmP2iZ4VjDPJEzKYAcNamrKAZTRJksJ4UsfzpkpMaSf+GRBro1ugAzL/9iDb+cLiKppvivqIyQoALNrV4fZdnie8L3k3ojaAer4Icg3IAG20R/Un+MpqnINSYkFFg7CoOMxm4kkkJhWYtyixmIBcxx5GACGu24WLlS8neOmfJZatxLiK/Y7YoCtLVLHTtltZ7dz1Xk/3JVR7vzfxHrvXlo1h0XMslywkSsx5nlilPKq0PwqTQoSC0dAGGk24iLWzAgyJ2r5qwK9405BMNP7bDT/vy90+h1N6Ydswv2ljVZyK5Yj31jfTZggt2zR8/zfO+33/A/+K211Pc2NW/YTviXfwABPsam</latexit>
<latexit sha1_base64="ULWi/ZIc5l2mK36yR99hr0XKr7M=">AAACUXicdVFNSwMxEJ2u3/Wr6tFLsAgKWnaloN5ELx4VrApuWbLptA1mP0xmhbLs//HXePGg/hO9ma0FbcWBwMubN5OZlzBV0pDrvlecqemZ2bn5heri0vLKam1t/dokmRbYEolK9G3IDSoZY4skKbxNNfIoVHgT3p+V+ZtH1EYm8RUNUmxHvBfLrhScLBXUTn0kHuSy2PH7nHI/lUV522MWBfm+LHaZ38MH9iMr+TFBUKu7DXcY7C/wRqAOo7gIah9+JxFZhDEJxY2589yU2jnXJIXCoupnBlMu7nkP7yyMeYSmnQ93Ldi2ZTqsm2h7YmJD9ndFziNjBlFolRGnvpnMleR/ubKjGXs/D6OJeah71M5lnGaEsfgep5spRgkr7WUdqVGQGljAhZZ2Iyb6XHNB9hOq1ipv0pi/4Pqg4TUbx5fN+snRyLR52IQt2AEPDuEEzuECWiDgCZ7hFd4qL5VPBxznW+pURjUbMBbO4hdNe7TO</latexit>
<latexit sha1_base64="c8WZPQ42qH3CmIbJ3KseYDuF5+Q=">AAACU3icdVFNSwMxEE3Xr1q/qh69BItQQcuuFNSboAePFWwV3LJk02kbzH6YzApl2T/kr/Hiof4SwYvZdg+21YHAy5s3k5kXP5ZCo22PS9bS8srqWnm9srG5tb1T3d3r6ChRHNo8kpF69JkGKUJoo0AJj7ECFvgSHvzn6zz/8ApKiyi8x1EM3YANQtEXnKGhvOqNC8i89FRkdTcWXiqyE+oOGabmlk34Y+oO4IX+pctBrvCqNbthT4IuAqcANVJEy6t+ub2IJwGEyCXT+smxY+ymTKHgErKKm2iIGX9mA3gyMGQB6G462TajR4bp0X6kzAmRTtjfFSkLtB4FvlEGDId6PpeT/+Xyjnrm/dQP5ubB/kU3FWGcIIR8Ok4/kRQjmhtMe0IBRzkygHElzEaUD5liHM03VIxVzrwxi6Bz1nCajcu7Zu3qojCtTA7IIakTh5yTK3JLWqRNOHkj72RMPksfpW/LspanUqtU1OyTmbC2fgBM0bU8</latexit>
Algorithm 1 Multi-Agent Trust Region Learning Input: Initializing policies πi for each i.
1: for k ∈ {0, 1, 2, · · · } do 2: Using current policies πi, π−i to collect trajectories. 3: For each i: compute a trust payoff region policy π̂i using Eq. 2. Trust Payoff Region. 4: Solve meta-gameM(πi, π̂i, π−i, π̂−i) and obtain a meta-game Nash ρi, ρ−i. 5: Compute weak stable fixed point π̄i, π̄−i. Trust Stable Region. 6: For each i: compute best response π′i using Eq. 6. Best Response to Fixed Point. 7: πi ← π′i, π−i ← π′−i. 8: end for
Theorem 2 (Existence of Weak Stable Fixed Point). Consider the restricted underlying game where policy space is bounded in a linear continuous policy-space [πi, π̂i], where π̂i is monotonically improved based on πi within TPR. If (ρi, ρ−i) is a Nash equilibrium of the meta-gameM, then, the linear mixture joint policy (π̄i, π̄−i) is a weak stable fixed point for the restricted underlying game.
Proof. see Appendix C.
According to Theorem 2, (π̄i, π̄−i) is a weak stable fixed point of the restricted underlying game. Although the weak stable fixed point is relatively weak compared to the stable fixed points (Balduzzi et al., 2018), as we have stated, a weak stable fixed point is a reasonable (not strong as rational) requirement for an algorithm to avoid the minimum. Furthermore, the weak stable fixed points can suit for general game settings. As shown in Appendix C, in cooperative, competitive, and generalsum games, the fixed-point found by the meta-game analysis can be either stable or saddle points. Similarly, a local Nash equilibrium can be a stable or saddle in different differential games (Mazumdar et al., 2020). Therefore, the goodness of stable concepts would depend on specific settings. If we make some additional game class assumptions, we can easily obtain a stronger fixed-point types. Nevertheless, it comes with a cost, requiring additional computation or assumptions which may break the most general settings. Besides, when the meta-game has multiple Nash equilibria, an equilibrium is randomly selected in our work. Some equilibria can produce a more stable fixed point, however, we leave the equilibrium selection problem for future work.
Extra Cost for Approximating and Solving meta-game. There are two major-cost sources in common meta-game analysis: approximating and solving the meta-game (Muller et al., 2019). In our case, the meta-game is restricted to a local two-action game, where two actions πi and π̂i are close to each other. This proximity property reduces the meta-game approximation cost (without extra sampling) by reusing the collected trajectories in the TPR step (Tuyls et al., 2020). The next crucial problem is how to solve the n-agent two-action meta-game, which consists of the 2n entries of each of the n payoff matrices. This is much simpler than solving the whole underlying game, which increases exponentially with state size, action size, agent number, and time horizons. As the general-sum matrix-form game has no fully polynomial-time approximation for computing Nash equilibria (Chen et al., 2006), it usually costs a lot to solve the game (Daskalakis et al., 2009). If we only require an approximated Nash equilibrium, when n is small, for example, n ≤ 10, it is affordable to find a meta-game Nash equilibrium in a sub-exponential complexity (Lipton et al., 2003). However, this problem still exists when n is large. In this case, we could try mean-field approximation (Yang et al., 2018) or utilizing special payoff structure assumptions (e.g., graphical game (Littman et al., 2002; Daskalakis et al., 2009), which is polynomial-time computable.) in the meta-game to reduce the computation complexity.
Under review as a conference paper at ICLR 2021

heading: 3.3 IMPROVEMENT AGAINST WEAK STABLE FIXED POINT
text: Although the weak stable fixed point, (π̄i, π̄−i), binds the policy update to another fixed point, there are still undesired saddle points according to Theorem 1. It is difficult to generalize for the other parts of the policy-space not reached by these saddle points, especially in the anti-coordination games (Lanctot et al., 2017). Similar to the extra-gradient method (Mertikopoulos et al., 2018), to escape the saddle points we apply the best response against the weak stable fixed point:
π′i = arg max πi ηi (πi, π̄−i) . (6)
To perform the best response, we need another round to collect the experiences and do a gradient step in Eq. 6. However, in practice, since we already have the trajectories in the TPR step and so the best response to the weak stable fixed point can be easily estimated through importance sampling. Alternatively, through defining ci def = min ( 1 + c̄,max(1 − c̄, πi(ai|s)π̄i(ai|s) ) ) as truncated importance sampling weights, we can re-write the best response update to Eq. 6 into an equivalent form to the following one in terms of expectations: π′i = arg maxπi Ea−i∼π̄−i [c−iηi (πi, π−i)].
Connections to Existing Methods. MATRL generalizes many existing methods with the best response. In extreme cases where the meta-game Nash is (ρi, ρ−i) = (1, 1), which means the Nash aggregated policies always keep the current policies, MATRL degenerates to independent learners. Here, we always best response to the other agents’ current policy πi and π′i = arg maxπi ηi(πi, π−i) following the Eq. 6. The policy prediction (Zhang & Lesser, 2010; Foerster et al., 2018; Letcher et al., 2018), extra-gradient (Antipin, 2003) and exploitability descent (Tang et al., 2018; Lockhart et al., 2019) methods are also special instances of MATRL when meta-game Nash is (ρi, ρ−i) = (0, 0). This means the best response to the most aggressive predicted policy π̂−i and π′i = arg maxπi ηi(πi, π̂−i).
Global Convergence. MATRL is a gradient-based algorithm with the best response to policies within TSR, which is essentially a variant of LookAhead methods(e.g., LOLA (Foerster et al., 2018), SOS (Letcher et al., 2018) and IGA-PP (Zhang & Lesser, 2010). More specifically, MATRL enhances the classic LookAhead method with variable step size scaling (Bowling & Veloso, 2002) or two time-scale update rule (Heusel et al., 2017) at each TSR step, which is controlled by the restricted meta-game analysis. It has been proven that LookAhead method can locally converge and avoid strict saddles in all differentiable games (Letcher et al., 2018), and enjoys the better convergence with variable step size scaling (Song et al., 2019). The convergence analysis of gradient-based algorithms is usually based on fixed-point iterations and dynamical systems. And please note, here, to investigate the convergence, the fixed-point iterations are conducted on the whole learning process. While the meta-game analysis step in MATRL borrows the concepts of different fixed-points to show the meta-game analysis is reasonable to avoid unstable fixed-points. Unlike LOLA, which uses first-order Taylor expansion to estimate the best response to a predicted policy, we elaborately design the look-ahead step within the TSR and do the best response gradient steps to TSR. We also show that MATRL empirically outperforms the typical LookAhead method independent learner the policy prediction (IL-PP) in the experiments.
In summary, independent trust region learners’ learning in MTARL will be constrained by a weak stable fixed point. By analyzing the relatively simpler meta-game, we can easily approximate this weak stable fixed point without extra rollouts or simulation. Although MATRL’s training is centralized, its execution is fully decentralized. It also does not require any extra centralized parameters or higherorder gradient computation. Fig. 3 shows the overview of MATRL. We also give the pseudocode of MATRL in Algo. 1, which is compatible with any policy-based independent learner.

heading: 4 RELATED WORK
text: The study of gradient-based methods in multi-agent learning is quite extensive (Mazumdar et al., 2020; Buşoniu et al., 2010). Some works on learning in games have mostly focused on adjusting the step size, which attempts to use a multiple-timescales learning scheme (Leslie & Collins, 2005; Leslie et al., 2003; Bowling & Veloso, 2002) to achieve convergence. Balduzzi et al. (2018); Mazumdar et al. (2019); Letcher et al. (2018) tried to utilize the second-order methods to shape the step size. However, the computational cost for second-order methods is very limiting in many cases. Alternatively, MATRL approximates the second-order fixed-point information via a small meta-game with less cost comparing to real Hessian computation. An alternative augments the gradient-based algorithms with the best response to predicted polices (Antipin, 2003; Zhang & Lesser, 2010; Lin et al., 2020; Foerster et al., 2018; Tang et al., 2018; Lockhart et al., 2019),
Under review as a conference paper at ICLR 2021
which target the challenge of instability caused by agents’ change policies. Instead of taking the best response to the approximated opponent’s policy, MATRL exploits the ideas from both streams and and introduces the improvement over the weak stable fixed point.
The research also focuses on the EGTA (Tuyls et al., 2018; Jordan & Wellman, 2009; Tuyls et al., 2020), which creates a policy-space meta-game for modeling the multi-agent interactions. Using various evaluation metrics, it then updates and extends the policies based on the analysis of the meta policies (Lanctot et al., 2017; Muller et al., 2019; Omidshafiei et al., 2019; Balduzzi et al., 2019; Yang et al., 2019). Although these methods are broad with respect to multi-agent tasks, they require extensive computing resources to estimate the empirical meta-game and solve it with its increasing size (Omidshafiei et al., 2019; Yang et al., 2019). In our method, we adopt the idea of a policy-space meta-game to approximate the fixed point. Unlike previous works, we only maintain the current policies and predicted policies to construct the meta-game, which is computationally achievable in most cases. The payoff entry in MATRL’s meta-game is the expected advantage, which has a lower estimation variance compared to the commonly used empirically-estimated return in EGTAs. Regardless, we can reuse the trajectories in the TPR step to estimate the payoffs without incurring additional sampling costs.
Recently, due to the use of neural networks as a function approximation for policies and values, there have emerged many works on deep reinforcement learning (DRL) (Mnih et al., 2013; Lillicrap et al., 2015). Trust region policy optimization (Kakade & Langford, 2002; Schulman et al., 2015; 2017) is one of the most successful DRL methods in the single-agent setting, which puts constraints on the step size of policy updates, preserving any improvements monotonically. Based the monotonic improvement in single-agent trust region policy optimization (TRPO) (Schulman et al., 2015), MATRL extends the improvement guarantee to the multi-agent level, towards a weak stable fixed point. Some works directly apply fully decentralized single-agent DRL methods (Tan, 1993), which can be unstable during when learning due to the non-stationary issue. Whereas (Foerster et al., 2016; Sukhbaatar et al., 2016; Peng et al., 2017) added an extra communication channel during the training and execution in a centralized way to avoid this non-stationarity issue. Sunehag et al. (2018); Rashid et al. (2018); Foerster et al. (2017); Lowe et al. (2017) further exploit the setting of centralized learning decentralized execution (CTDE). These methods provide solutions for training agents in complex multi-agent environments, and the experimental results show the effectiveness compared with independent learners. Similar to the CTDE setting, the MATRL also enjoy fully decentralized execution. Although MATRL still needs knowledge about the other agents’ policies during the training, it only requires a centralized mechanism to adjust the step size rather than the additional centralized critic or communication.

heading: 5 EXPERIMENTS
text: We design the experiments to answer the following questions: 1). Can the MATRL method empirically contribute to the convergence in the general game settings, including cooperative/competitive and continuous/discrete games? 2). How is the performance of MATRL compared to the ILs with the same hyper-parameters and other strong MARL baselines in discrete and continuous games with various agent number? 3). Do the meta-game and best response to the weak stable fixed point bring benefits? We first evaluate the convergence performance of MATRL in matrix form games to answer the first question and validate the effectiveness of convergence. For Question 2, we show that MATRL largely outperforms ILs (PPO (Schulman et al., 2017)) and other centralized baselines (QMIX (Rashid et al., 2018), QTRAN (Son et al., 2019) and VDN (Sunehag et al., 2018)) for discrete grid world games
Under review as a conference paper at ICLR 2021
that have coordination problems. It also outperforms MADDPG (Lowe et al., 2017) for continuous multi-agent MuJoCo games. Besides, we test the algorithms with 2-agent pong Atari game to investigate if MATRL can mitigate unstable cyclic behaviors (Balduzzi et al., 2019) in zero-sum games. In these tasks, MATRL uses the same PPO configurations as ILs to examine the effectiveness of the trust region gradient-update mechanism, and we use official implementations for the other baselines. The step-by-step PPO based MATRL algorithm is given in Algo. 2. Finally, ablation studies are conducted by: 1. removing the best response, called the MATRL w/o BR; 2. skipping the trust-stable region estimation, named IL-PP, which has similar procedures as LOLA Foerster et al. (2018); Zhang & Lesser (2010), which approximated the best response to the predicted policies via Taylor expansion, but IL-PP takes the best response gradient steps to the predicted policies. These configurations provide insights about how much does the trust stable region and the best response contribute to the MATRL’s performance if any. We also provide more environment details and extra experiment results, including 4-agent Ant (multi-agent MuJoCo), in the Appendix D and E with detailed experiment settings and hyper-parameters used for the algorithms. The code and experiment scripts are also anonymously available at https://github.com/matrl-project/matrl.
Matrix Game and Random 2× 2 Matrix Games. To illustrate the effectiveness of MATRL, we conducted an experiment on well known zero-sum matching pennies (MP) (Bruns, 2015) game and devise the 2×2 random matrix games. Using IGA (Singh et al., 2000) as ILs of MATRL, the learning dynamics of MATRL on MP are shown in Fig. 4, where the blue arrow is trust payoff direction and the pale blue area is TSR.. The MATRL reaches the Nash Equilibrium (central red star point) by updating the policies with the constraints from the trust stable region (the pale blue area). It would be trapped to a cyclic loop if following the original trust pay off direction (the dark blue arrow). To adequately examine the MATRL on border matrix games, we randomly generate three thousand 2× 2 games for three types: coordination, anti-coordination, and cyclic (Pangallo et al., 2017). More details about the game generation are provided in Section D. We choose the IGA and IGA-PP (Zhang & Lesser, 2010) as baselines, and the results in Table 1 show that MATRL has a higher convergence rate and needs fewer steps for convergence in all types of games.
Grid World Checker and Switch. We evaluated MATRL in two grid world games from MAGym (Koul, 2019), two-agent checker, and four-agent switch, which are similar to games in Sunehag et al. (2018), but with more agents to examine if the MATRL can handle the games that have more than two agents. In the checker game, two agents cooperate in collecting fruits on the map; the sensitive agent gets 5 for apple and −5 for lemon, while the other one gets 1 and −1 respectively. So the optimal solution is to let the sensitive agent get the apple and the less sensitive one get the lemon. In the four-agent switch game, two rooms are connected with a corridor, each room has two agents, and the four agents try to go through one corridor to the target in the opposite room. Only one agent can pass the corridor at one time, and agents get −0.1 for each step and 5 for reaching targets, so they need to cooperate to get optimal scores. In both games, The agents can move in four directions and only partially observe their position. Although our formulation uses a fully observable setting, in this game, the methods adopt to the partially observable by pretending the observation is a state. We compare the MATRL with the PPO based IL and two off-policy centralized training and decentralized execution baselines: VDN (Sunehag et al., 2018), QTRAN (Son et al., 2019) and QMIX (Rashid et al., 2018). Results are given in Fig. 5a and 5b, where MATRL has a stable improvement and outperforms other baselines. In two-player checker, using the best response, our method can achieve a total reward of 18, while the independent learners’ rewards stay at −2. Besides, although PPO-based MATRL uses on-policy learning, it achieved better final results in fewer time steps compared to the off-policy baselines. As for the four-player switch, as shown in Fig. 5b, MATRL can continuously improve the total rewards to 6.5, which is the closest to the optimal score for this game when compared with
Under review as a conference paper at ICLR 2021
Under review as a conference paper at ICLR 2021
(a) Two-agent checker. (b) Four-agent switch. (c) Three-agent MuJoCo hopper.
Figure 5: Learning curves in discrete and continuous tasks, each with 5 random seeds.
(a) (b) (c)
Figure 6: MATRL/IL versus Random/MATRL/IL in the 2-agent pong game.
lemon. In the four-agent switch game, each side of the corridor has a room, each room has two agents, and the four agents try to go through one corridor to the target in the opposite room. Only one agent can pass the corridor at one time, and agents get 0.1 for each step and 5 for reaching targets, so they need to cooperate to get optimal scores. In both games, The agents can move in four directions and only partially observe their position. We compare the MATRL with the PPO based IL and two off-policy centralized training and decentralized execution baselines: VDN (Sunehag et al., 2018) and QMIX (Rashid et al., 2018). Results are given in Fig. 5a and 5b, where MATRL has a stable improvement and outperforms other baselines. In two-player checker, using the best response, our method can achieve a total reward of 18, while the independent learners’ rewards stay at 2. Besides, although PPO-based MATRL uses on-policy learning, it achieved better final results in fewer time steps compared to the off-policy baselines. As for the four-player switch, as shown in Fig. 5b, MATRL can continuously improve the total rewards to 6.5, which is the closest to the optimal score for this game when compared with other baselines. The result in the four-agent switch also demonstrates the effectiveness of MATRL in guaranteeing the stable policy improvement for the games that have more than two agents.
Multi-Agent MuJoCo Hopper. We also examined MATRL in a multi-agent continuous control task with a three-agent hopper from (de Witt et al., 2020). Here, three agents cooperatively control each part of a hopper to move forward. The agents are rewarded with distance and the number of steps they make before falling. Fig. 5c shows that MATRL significantly outperforms IL, MADDPG, and also the benchmarks in de Witt et al. (2020) within the same amount of time.
Effect and Cost of Trust Stable Region and Best Response to Fixed Point. This section analyzes the effect of the TSR from meta-game Nash and the best response against the weak stable fixed point. The ablation settings are obtained by removing the trust stable region (IL-PP) and the best response
(MATRL w/o BR). In Fig. 5, we can observe that in all the tasks, without the best response to the
fixed point, the learning curves of MATRL o/w BR have higher variance and the lowest final scores.
This establishes the importance of the best response to stabilize and improve agents’ performance.
Also, without the TSR to select a fixed point, the MATRL recovers to independent learners with the policy prediction (IL-PP) (Zhang & Lesser, 2010; Foerster et al., 2018). Similarly, the curves of IL-PP have lower final scores, and the convergence speed is not as good as the MATRL, which suggests that the TSR provides benefits. The MATRL w/o BR has lower variance compared to the IL-PP, which reveals the trust stable region can stabilize the learning via weak stable fixed point constraints. Finally, when comparing to IL and IL-PP, the time for each training step in MATRL is
8
Figure 6: MATRL/IL versus MATRL/IL in the two-agent pong game. For each setting, the grids are pair-wise performance (average scores) by pitting their ten checkpoints against one another, yellow means higher score.
other baselines. The result in the four-agent switch also demonstrates the effectiveness of MATRL in guaranteeing the stable policy improvement for the games that have more than two agents.
Multi-Agent MuJoCo Hopper. We also examined MATRL in a multi-agent continuous control task with a three-agent hopper from (de Witt et al., 2020). Here, three agents cooperatively control each part of a hopper to move forward. The agents are rewarded with distance and the number of steps they make before falling. Fig. 5c shows that MATRL significantly outperforms IL, MADDPG, and also the benchmarks in de Witt et al. (2020) within the same amount of time.
Multi-Agent Pong Atari Game. In the 2-agent pong game experiments, we used raw pixel as observation and train the MATRL and IL agents independently. Following training, we compare these models’ pair-wise performance by pitting their ten checkpoints against one another and recording the average scores. We report the results in Fig. 6, which shows MATRL outperforms IL in MATRL vs. IL setting in most of the policy pairs. Besides, from the MATRL vs. MATRL and IL vs. IL settings’ results, we can see MATRL has a more transitive learning process than IL, which means MATRL can mitigate the common cyclic behaviors in zero-sum games.
0
200
400
600
800
1000
1200
Ti m
e in
s ec
on d
MATRL MATRL w/o BR IL-PP IL
2 Agents 3 Agents 4 Agents
Figure 7: Running time of 20,000 environment steps (including 50 gradient steps) for the algorithms in 2-4 agents games.
Effect and Cost of Trust Stable Region and Best Response to Fixed Point. This section analyzes the effect of the TSR from meta-game Nash and the best response against the weak stable fixed point. The ablation settings are obtained by removing the trust stable region (IL-PP) and the best response (MATRL w/o BR). In Fig. 5, we can observe that in all the tasks, without the best response to the fixed point, the learning curves of MATRL o/w BR have higher variance and the lowest final scores. This establishes the importance of the best response to stabilize and improve agents’ performance, and empirically shows that the MATRL has better convergence ability than other baselines. Also, without the
TSR to select a fixed point, the MATRL recovers to independent learners with the policy prediction (IL-PP) (Zhang & Lesser, 2010; Foerster et al., 2018). Similarly, the curves of IL-PP have lower final scores, and the convergence speed is not as good as the MATRL, which suggests that the TSR provides benefits. The MATRL w/o BR has lower variance compared to the IL-PP, which reveals the trust stable region can stabilize the learning via weak stable fixed point constraints. Finally, when comparing to IL and IL-PP, as shown in Fig. 7, in 2-4 agents games with 20,000 environment steps and 50 gradient steps, the training time of MATRL is empirically about 1.1-1.2 times slower. We think this extra computational cost from the TSR and the best response is acceptable given the performance improvement brought by these operations.

heading: 6 CONCLUSION
text: We proposed and analyzed the trust region method for multi-agent learning problems, which considers the trust payoff region and the trust stable region to meet the multi-agent learning objectives. In practice, based on independent trust payoff learners, we provide a convenient way to approximate a further restricted step size within TSR via the meta-game. This ensures that the MATRL is generalized, flexible, and easily implemented to deal with multi-agent learning problems in general. Our experimental results justify the fact that MATRL method significantly outperforms independent learners using the same configurations, and other strong MARL baselines on both continuous and discrete games with various agent numbers.
Under review as a conference paper at ICLR 2021

heading: A MATRL ALGORITHM BASED ON PPO
text: Algorithm 2 Multi-Agent Trust Region Learning Algorithm (PPO Based, Two-Agent Example). Input: The initial policy parameters θ1, θ2, initial value function parameters φ1, φ2 and .
1: for k ∈ {0, 1, 2, · · · } do 2: Using π1(θ1), π2(θ2) to collect trajectories τ1, τ2. 3: Compute GAE reward R̂i for each i. 4: Compute estimated advantages Â1, Â2 based on the current value functions Vφ1 , Vφ2 . 5: for i ∈ {1, 2} do 6: Compute a trust payoff region policy π̂i using Eq. 2. 7: Update the policy by maximizing the PPO-Clip objective:
θ̂i = arg maxθi 1 |τi|T ∑ τ∈τi ∑T t=0 min ( πi(at|st;θ) πi(a1,t|st;θi)A π1,π2 i (st, a1,t, a2,t) , g ( , A π1,π2 i (st, a1,t, a2,t)) ) ,
where g is a clipping function. 8: Fit value function by regression on mean-squared error:
φ′i = arg min φi
1 |τi|T ∑ τ∈τi T∑ t=0 ( Vφ (st)− R̂i,t )2 9: end for
10: Construct the meta-gameM(π1(θ1), π̂1(θ̂1), π2(θ2), π̂2(θ̂2)). 11: SolveM and obtain meta Nash ρ1, ρ2. 12: Compute aggregated weak stable fixed point (π̄1, π̄2). 13: for i ∈ {1, 2} do 14: Compute π(′)i which best responses to π̄−i using Eq. 6. 15: Estimate the best response by importance sampling:
θ′i = θ̂i |τi|T ∑ τ∈τi T∑ t=0 g ( , πi/π̄−i)
16: end for 17: θ1 ← θ′1, θ2 ← θ′2 . 18: end for Output: π1(θ1), π2(θ2).
B INDEPENDENT TRUST PAYOFF REGION We use the total variation divergence, which is defined by DTV(p‖q) = 12 ∑ j |pj − qj | for discrete probability distributions p, q (Schulman et al., 2015). DmaxTV (π, π̃) is defined as:
DmaxTV (π, π̃) = max s DTV(π(·|s)‖π̃(·|s)). (7)
Based on this, we can define α-coupled policy as:
Definition 2 (α-Coupled Policy (Schulman et al., 2015)). (π, π′) is an α-coupled policy pair if it defines a joint distribution (a, a′)|s, such that P (a 6= a′|s) ≤ α for all s. π and π′ will denote the marginal distributions of a and a′, respectively.
When the joint policy pair πi, π−i changes to π′i, π ′ −i and coupled with αi and α−i correspondingly:
ηi(π ′ i, π ′ −i)− ηi(πi, π−i) ≥ Aπi,π−ii (π′i, π′−i)−
4γ
(1− γ)2 (αi + α−i − αiα−i) 2, (8)
where = max
s,ai,a−i ∣∣Aπi,π−ii (s, ai, a−i)∣∣. The proofs are as following:
Under review as a conference paper at ICLR 2021
Lemma 1. Given that (πi, π′i) and (π−i, π′−i) are both α-coupled policies bounded by αi and α−i respectively, for all s,∣∣Aπi,π−ii (s)∣∣ ≤ 2(αi + α−i − αiα−i) maxs,a−i,a−i ∣∣Aπi,π−ii (s, ai, a−i)∣∣ (9) Proof. A πi,π−i i (s) = Ea′i,a′−i∼π′i,π′−i [ A πi,π−i i (s, a ′ i, a ′ −i) ] (10)
= E(ai,a′i)∼(πi,π′i),(a−i,a′−i)∼(π−i,π′−i) [ A πi,π−i i (s, a ′ i, a ′ −i)−Aπi,π−ii (s, ai, a−i) ] (11)
= P (ai 6= a′i ∨ a−i 6= a′−i|s)E(ai,a′i)∼(πi,π′i),(a−i,a′−i)∼(π−i,π′−i)[A πi,π−i i (s, a ′ i, a ′ −i) (12)
−Aπi,π−ii (s, ai, a−i)] (13)
≤ (αi + α−i − αiα−i) · 2 max s,a−i,a−i ∣∣Aπi,π−ii (s, ai, a−i)∣∣, (14) where P (ai 6= a′i ∨ a−i 6= a′−i|s) = 1− (1− αi)(1− α−i) = αi + α−i − αiα−i.
Lemma 2. Let (πi, π′i) and (π−i, π′−i) are α-coupled policy pairs. Then,∣∣∣Est∼π′i,π′−i[Aπi,π−ii (s) ]− Est∼πi,π−i[Aπi,π−ii (s) ]∣∣∣ ≤ 4(αi + α−i − αiα−i)(1− (1− αi)t(1− α−i)t) max
s,a−i,a−i ∣∣Aπi,π−ii (s, ai, a−i)∣∣ (15) Proof. The preceding Lemma bounds the difference in expected advantage at each time step t. When t′ = 0 indicates that πi, π−i and π′i, π ′ −i both agreed on all time steps less than t. By the definition of αi, α−i, P (πi, π−i := π′i, π ′ −i|t = i) ≥ (1− αi)(1− α−i), so P (t′ = 0) ≥ (1− αi)t(1− α−i)t and P (t′ > 0) ≤ 1 − (1 − αi)t(1 − α−i)t. We can sum over time to bind the difference between ηi(π
′ i, π ′ −i) and ηi(πi, π−i).∣∣∣ηi(π′i, π′−i)− Lπi,π−ii (π′i, π′−i)∣∣∣ = ∞∑
t=0
γt ∣∣∣Est∼π′i,π′−i[Aπi,π−ii (s) ]− Est∼πi,π−i[Aπi,π−ii (s) ]∣∣∣
(16)
≤ ∞∑ t=0 γt · 4 (αi + α−i − αiα−i)(1− (1− αi)t(1− α−i)t)
(17) = 4 (αi + α−i − αiα−i) ( 1
1− γ − 1 1− γ(1− αi)(1− α−i) )
(18)
= 4 (αi + α−i − αiα−i)2
(1− γ)(1− γ(1− αi)(1− α−i)) (19)
≤ 4 (αi + α−i − αiα−i) 2
(1− γ)2 , (20) where = maxs,ai,a−i ∣∣Aπi,π−ii (s, ai, a−i)∣∣.
Note that L πi,π−i i (π ′ i, π ′ −i) = ηi(πi, π−i) + ∑ s ρπi,π−i(s) ∑ ai π′i(ai|s) ∑ a−i π′−i(a−i|s)Aπi,π−ii (s, ai, a−i). (21) Then, we can have
ηi(π ′ i, π ′ −i)− ηi(πi, π−i) ≥ Aπi,π−ii (π′i, π′−i)−
4γ
(1− γ)2 (αi + α−i − αiα−i) 2. (22)
Under review as a conference paper at ICLR 2021

heading: C PROOF OF THEOREM 2
text: At each iteration, denote ∇igi = ∇πig πi,π−i i and ∇i,−igi = ∇πi∇π−ig πi,π−i i for each i. Consider the simultaneous gradient ξ of the expected advantage gains and the corresponding Hessian H:
ξ(πi, π−i) = (∇igi,∇−ig−i) , (23) H = ∇ξ = ( ∇i,igi ∇i,−igi ∇−i,ig−i ∇−i,−ig−i ) . (24)
For a restricted underlying game, where policy space is bounded: πi ∈ [πi, π̂i]. Assume πi is the linear mixture of πi, π̂i, and π̄i = ρiπi + (1− ρi)π̂i, where ρi ∈ [0, 1]. Therefore, we can re-write the gπi,π−ii (πi, π−i) in the form of:
g πi,π−i i (πi, π−i) = g πi,π−i i (ρi, ρ−i) = ρi(1−ρ−i)gi,−îi +(1−ρi)ρ−igî,−ii +(1−ρi)(1−ρ−i)gî,−îi . (25) Then we have: ∇igi(ρ−i) = (1− ρ−i)gi,−îi − ρ−igî,−ii − (1− ρ−i)gî,−̂ii , (26) and ξ(πi, π−i) = ξ(ρi, ρ−i). Given a meta Nash policy pair (π̄i, π̄−i), where π̄i = ρ̄iπi+(1− ρ̄i)π̂i, according to the Nash definition, we have:(
ρ̄i 1− ρ̄i
)T ( gi,−ii g i,−î i
gî,−ii g î,−î i
)( ρ̄−i
1− ρ̄−i
) ≥ (
ρi 1− ρi
)T ( gi,−ii g i,−î i
gî,−ii g î,−î i
)( ρ̄−i
1− ρ̄−i
) , (27)
which implies:
(ρ̄i − ρi)∇igi(ρ̄−i) ≥ 0, ρ̄i,∀ρ−i ∈ [0, 1], (ρ̄−i − ρ−i)∇−ig−i(ρ̄i) ≥ 0, ρ̄i,∀ρ−i ∈ [0, 1].
(28)
When ρ̄i, ρ̄−i ∈ (0, 1) in accordance with the Nash condition in Eq. 28,∇igi(ρ̄−i) = ∇−ig−i(ρ̄i) = 0. It shows that (π̄i, π̄−i) is a fixed point due to ξ(π̄i, π̄−i) = ξ(ρ̄i, ρ̄−i) = 0. For the boundary case, where ρ̄i or ρ̄−i ∈ {0, 1}, because they are constrained to the unit square [0, 1]× [0, 1], the gradients on the boundaries of the unit square are projected onto the unit square, which means additional points of zero gradient exist. In other words,∇igi and∇−ig−i are still equal to zero in boundary case, and the (π̄i, π̄−i) is a fixed point in both cases.
Next, we determine what types of the fixed point that (π̄i, π̄−i) belongs to. According to the Eq. 24, we have the exact Hessian Matrix for the restricted game:
H = ∇ξ = (
0 gî,−îi − gi,−îi − gî,−ii gî,−î−i − gi,−î−i − gî,−i−i 0
) (29)
The eigenvalue λ of H can be computed:
λ2 − Tr(H)λ+ det(H) = λ2 − (gî,−îi − gi,−îi − gî,−ii )(gî,−î−i − gi,−î−i − gî,−i−i ) = 0 (30)
Denotes ḡi := g î,−î i − gi,−îi − gî,−ii , we have λ = ± √ ḡiḡ−i. Therefore, we can have following cases for the fixed point (ρ̄i, ρ̄−i):
1. Fully cooperative games: ḡi ≤ 0, ḡ−i ≤ 0, then H(ρ̄i, ρ̄−i) 0, which means (ρ̄i, ρ̄−i) is a stable fixed point as we are maximizing the objective.
2. Fully competitive games: ḡi > 0, ḡ−i < 0 or ḡi < 0, ḡ−i > 0, all λ have two pure imaginary eigenvalues with zero real part, where (ρ̄i, ρ̄−i) is a saddle point.
3. General sum games: they are in-between the cooperative and competitive games, which means (ρ̄i, ρ̄−i) can be either stable fixed point or saddle point.
Because we assume π̂i monotonically improved compared to πi, then even in zero-sum case, there is at least one negative value in ḡi and ḡ−i. Therefore, in all the situations, (ρ̄i, ρ̄−i) is not unstable, and could be a stable point or saddle point. We define them as a weak stable fixed point. It also has a tighter lower bound than the independent trust region improvement seen in Remark 1:
Under review as a conference paper at ICLR 2021
Remark 1. Let (ρi, ρ−i) be a Nash equilibrium of the policy-space meta-gameM(πi, π̂i, π−i, π̂−i), which is used for computing the linear mixture policies π̄i, π̄−i. For simplicity, define ρ̄i = 1− ρi, then we have the payoff improvement lower bound for π̄i, π̄−i:
ηi(π̄i, π̄−i)− ηi(πi, π−i) ≥ gπi,π−ii (π̄i, π̄−i)− 4γ i
(1− γ)2 (αiρ̄i + α−iρ̄−i − αiα−iρ̄iρ̄−i) 2, (31)
that is a tighter lower bound compared with Theorem 1. Finally, we obtain MATRL as follows: First, an agent i collects a set of trajectories using its current policy πi by independent play with other agents. Then a predicted policy π̂i can be estimated using the single-agent trust region methods, which has a trust payoff improvement against the other agents’ current policy π−i. However, this trust payoff improvements would not benefit convergence requirements for the multi-agent system due to other agents adaptive learning. To solve this problem, we approximate a n-agent two-action meta-game in policy-space by reusing the trajectories from the last TPR step. In this game, each agent i has two pure strategies: choosing the current policy πi or predicted policy π̂i and the corresponding payoffs are the expected advantages (defined in Eq. 3) of the joint policy pairs. By constructing such a meta-game, we transform a complex multiagent interactions problem into game-theoretic analysis concerning the underlying game restricted in [πi, π̂i]. Then we can obtain a weak stable fixed point as TSR within the TPR by solving the meta-game,. When the fixed point is a saddle point we then take the best response to the weak stable fixed point to get the next iteration’s policies. This encourages exploration and avoid stagnation at an unexpected saddle point.

heading: D ENVIRONMENT DETAILS
text: Random 2× 2 Matrix Games. We created a generator of 2× 2 matrix games based on the category provided by (Pangallo et al., 2017). Coordination games have characteristics enabling one agent to improve the payoff without decreasing the payoff of the other agent. Anti-coordination games are ones where one agent improves the payoff while the other agent’s payoff decreases. Both coordination and anti-coordination games can have two pure NEs and one mixed strategy NE. In cyclic games, the action selections of agents that is based on their actions will form a cycle, ensuring that there is no pure NE in the game. Instead only mixed strategy NE will be found.
Under review as a conference paper at ICLR 2021
Grid World Games. In two-player checker, as shown in Fig. 8a, there is one sensitive player who gets reward 5 when they collect an apple and 5 when they collect a lemon; a less sensitive player gets 1 for apple and 1 for lemon. The learning goal is to let the sensitive player get apples and the other one get lemons to have a higher total reward. In four-player switch, as shown in Fig. 8b, to reach the targets, agents need to figure out a way to go through a narrow corridor. The agent gets −1 for taking each step and 5 when arriving at a target. Four-player switch uses the same map as two-player switch, where two agents start from the left side and the others from the right side to go through the corridor to reach the targets. With more agents in four-player switch, learning becomes more challenging. MATRL agents achieved higher total rewards compared to baseline algorithms within the same number of steps.
Multi-Agent MuJoCo Tasks. We used the three-agent Hopper environment described in (de Witt et al., 2020), and Fig. 8c, where three agents control three joints of the robot and learn to cooperate to move forward as far as possible. The agent is rewarded by the number of time steps that they move without falling. Each agent has 3 continuous output values as the action, and all the agents have a full observation of the states of size 17. We use the same hyper-parameters for MATRL, MATRL w/o BR, and IL-PP. For MADDPG agent, we use the hyper-parameters described in the paper (de Witt et al., 2020).
Multi-Agent Atari Game. The pong game is a multi-agent Atari version2 of table tennis, as shown in Fig. 10. Two players must prevent a ball from whizzing past their paddles and allowing their opponent to score. The game ends when one side earns 21 points.

heading: E EXPERIMENTAL PARAMETER SETTINGS
text: For all the tasks, the most important hyper-parameters are learning rate/step size, the number of update steps, batch size and value, policy loss coefficient. Appropriate learning rate and update steps plus larger batch size give a more stable learning curve. And for different environments, policy and value network loss coefficients that keep two losses at the same scale are essential in improving the learning result and speed. Also, for meta-game construction and best response update where we use the importance ratio to do estimation, a clipping factor of the ration is vital to achieving a stable and monotonic improving result. The followings are the detailed parameter settings for each task.
Matrix Game and Random 2 × 2 Matrix Games. The hyper-parameters settings for MATRL, IGA-PP, and WoLF are listed in Table 2. As shown in Fig. 9, we also listed the additional convergence analysis in classical Chicken and Prisoners’ Dilemma Games, which demonstrate good convergence performance of MATRL on both games. For MATRL, we have the KL-divergence coefficient as an extra hyper-parameter to add the KL-divergence as part of the loss in policy updating. And for the baseline algorithm WoLF, we give the real NE of the game as part of the parameters. In all the games, all the algorithms shared the same initial policy values [0.9, 0.1] for player 1 and [0.2, 0.8] for player 2.
Grid World Games and Multi-agent Continuous Control Task. The hyper-parameters settings for MATRL are given in Table 3. We used the same hyper-parameters for MATRL, MATRL w/o BR, IL-PP, and IL. The only difference is whether to use Best Response and the meta-game or not. We
2https://github.com/PettingZoo-Team/Multi-Agent-ALE
Under review as a conference paper at ICLR 2021
used Leaky ReLU as the activation function for both policies and value networks. For the training, we used paralleled workers to collect experience data and update the network weights separated then synchronize all the works to have the final updated weights. We used different value loss and policy loss coefficients to balance the weights of two losses. For the Switch games, we used small value loss coefficients because the value loss is between [0− 10] while the absolute value policy loss is smaller than 1e − 2. For the Checker game, the value loss and policy loss are at the same scale between [1e − 4, 1e − 2]. Also, we added entropy loss and KL loss to encourage exploration and limit the policy update for each step. We used (Šebek, 2013) as the Nash equilibrium solver for finding the meta-game Nash. The Nash solver is CMAES for all the experiments. If not particularly indicated, all the baselines use common settings as listed in Table 3. VDN, QMIX use common individual action-value networks as those used by MATRL; each consists of two 128-width hidden layers. We includes more experiment result on 4-agent ant task multi-agent MuJoCo task in Fig. 9c, which also demonstrate the superior performance of MATRL compared to other settings. The specialized parameter settings for each algorithm are provided in Table 4 and 5:
Multi-agent Atari Pong. The hyper-parameters setting for MATRL are listed in Table 6. We used the same hyper-parameters for MATRL and IL. We take the raw pixel input from the Atari environment, and we processed it with a convolution network, which has filter sizes [8,4,3], kernel sizes (3,3,3), and stride sizes [4,2,1] and ”VALID” as padding. Then we pass the processed embedding to a 2 layer fully connected network to get the policy.
Under review as a conference paper at ICLR 2021

Review summaries:
This paper proposes a modification of the Independent Learners trust region policy optimization method in general sum games. The modification consists of first forming a “meta game”—ie. the matrix game in which each agent’s options are his previous policy and his independent trust region optimized policy—-and then interpolating between the two for each agent according to a Nash equilibrium of the meta game. The paper shows that this algorithm results in each step generating a “weak stable fixed point”. The paper concludes by showing a number of experimental results indicating the convergence and overall performance of the method as compared with relevant baselines in a number of different games.

This paper presents a new trust-region method for multi-agent reinforcement learning (MARL). This approach extends ideas from single-agent trust-region methods to construct a smaller meta-game representing possible policy changes for each agent. The meta-game can then be solve to provide policy updates for the agents. Theory is provided for the meta-game (and corresponding restricted underlying game) and experimental results are shown with a number of baselines.