Multi-Agent Trust Region Learning
Authors: Ying Wen
Hui Chen
Yaodong Yang
Zheng Tian
Minne Li
Xu Chen
Jun Wang
Venue:  (2021)
Keywords: multi-agent learning
reinforcement learning
empirical game-theoretic analysis

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 two-player 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 multi-agent 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 multi-player general-sum games; results suggest that MATRL significantly outperforms strong MARL baselines on grid worlds, multi-agent MuJoCo, and Atari games. 

Under review as a conference paper at ICLR 2021
MULTI-AGENT TRUST REGION LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Trust-region methods are widely used in single-agent reinforcement learning. One advantage is that they guarantee lower bound of monotonic payoff improvement for policy optimization at each iteration. Nonetheless, when applied in multi-agent settings, such guarantee is lost because 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. Al- though game-theoretical solution concepts such as Nash equilibrium can be applied, the algorithm (e.g.. Nash-Q Q learning) suffers from poor scalability beyond two- player discrete games. To mitigate the above measurability and tractability issues, in this paper, we propose Multi-Agent Trust Region Learning (MATRI.) method. MATRL augments the meglle-agen trust-region optimization process with the multi- agent solution concept of stable fixed point that is computed at the policy-space meta-game level. When multiple agents learn simultancously, stable fixed points at the meta-game level can effectively measure agents' payoff improvements, and, importantly, metaa-amme representation enjoys better scalability for multi- multi-player games. We derive the lower bound of agents' payoff improvements for MATRL methods, and also prove the convergence of our method the meta-game fixed points. We evaluate the MATRL method on both discrete and continuous multi- player general-sum games; results suggest that MATRL significantly outperforms strong MARL baselines on grid worlds, multi-agent MuloCo, and Atari games.
INTRODUCTION
Multi-agent systems (MAS) (Shoham & Ecyton-BBownr 2008) have received much attention from the reinforcement learning community. In real-world, automated driving (Cao et al., 2012), StarCraft (Vinyals al., 2019) and Dota 2 (Berner et al., 2019) are few examples of the myriad of appli- cations 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 environ- ments 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 stable environment (Buşoniu 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 al., 2015; 2017)) based II. 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 's improvement is affected by other agent's adaptive behaviors (i.e., the multi-agent environment is non-stationary (Hernandez-Lean 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 IIs act less well in MAS as in single-agent tasks. Moreover, the convergence to fixed point, such as a Nash equilibrium (Nash et al., 1950; Bowling & Veloso, 2004; Mazumdar et al., 2020), is 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 Game- Theoretic Analysis (EGTA) (Wellman, 2006), which approximates the best response 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 al., 2019) establish

---

Under review as a conference paper at ICLR 2021
Monotonic Improvement
m (TT, R--)--
Th
(T R πI -i) n- n T i) n n ( T--
Against Fixed Opponent Policy
Simulianously Updated Policies
Improvemen:
uriinone
(T T n
Improvemene
unknow
The relationship of discounted returns NN for an agent given the different joint policy pairs, where и; is the current policy, ni. is the simultaneously updated policy. Given Tú, the monotonic im- provement against fixed opponent be easily measured: ( TT-)) 2 (=(=,,==))) However, due to the simultaneous learning, the improvement of 1% (T x"1)) is unknown compared to 77. (TT, T-1)-
Figure 1:
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; Sunchag 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 IIs with meta-game analysis improve the stability and efficiency of learning. In MATRI, 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 gama, 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, 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 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 hypee-parameetes, centralized VDN (Sunehag et al., 2018), QMIX (Rashid al., 2018) methods in discrete action grid-worlds, centralized MADDPG (Lowe et al., 2017) in a continuous action multi-agent MuJoCo task (de Witt al., 2020) and zero-sum multi-agent Atari (Terry & Black, 2020).
PRELIMINARY
A Stochastic Game (Shapley, 1953; Littman, 1994) can be defined as: G (N,S, [A:}, [R.]. PoPo,"), 7), where N is a set of agents, n = [ is the number of agents and S denotes the state space. A, the action space for agent i. A = Ai x... x A,, = A, A_; is the joint action space, and for the simplicity we use -i denotes the other agents except agent i. R, (s, a,, a-s) is the reward function for agent i N. P S:Sx A x S - [0, 1] is the transition function. Po is the initial state distribution, 7 E [0, 1] is discount factor. Each agent i E W has stochastic policy n, (a;(s)) :S x A [0, 1). and aims to maximize its long term discounted return:
TH mi) Es ag
Σ yd Ri(o", of dit
where 50 ~ Po. st+1 ~ P(s |s", at, a'.), of (aaat:))) We then can have the standard definitions of the state-action value function Qu a',a",)) / (s af ,f
Ex-i aatt .a Egg 1 D (sttt at 4t (a,,)) and the advantage function A, A (st, afta)) Q (8", al, a'.) VV, V.
the value function V,
t *(*t) given the state and joint action.
3 MULTI-AGENT TRUST REGION POLICY OPTIMIZATION
trust region algorithm aims to answer two questions: how to compute a trust region trial step and whether trial step should be accepted. In multi-agent learning, trust region trial step towards agents' payoff improvement can be easily implemented with independent leamers, and we call the independent payoff improvement area Trust Payoff Region The remaining issue is
2

---

Under review as a conference paper at ICLR 2021
Trust Stable Region
π
π
Trust Payoff
Trust Payoff Region
Region
π
Trust Payoff Region π
π
Trust Payoff Region
π
TT
π
i
T
Mossoasic Payeff Ingrovement
Improvemenee Against Lecal Sobie Favod-Poin
(a) Independent trust region learning.
(b) Multi-agent trust region learning.
Figure 2: Comparisons between independent trust region learner and multi-agent trust region learner. Ti, R-; are the current policies for two agents. n. f- predicted policies within TPR, (T) T-.) forms Nash equilibrium, m. and Tr_; are the best responses the weak stable fixed point (#,, - (a): independent trust region learning, an agent only considers itself"s policy improvement against the fixed opponent policy m-+- (b): multi-agent trust region learning, agents' policy improvement should be explored in the joint policy space (Ta π x toward a stable region.
revolved by finding restricted step leading to stable point in the joint policy space, denoted as Trust Stable RSgion(TSR). In other words, multi-agent trust region learning (MATRL) decomposes the trust region learning into two parts: firstly, find trust payoff region between current policy Ti and predicted policy fG; then, with the help of the predicted policy. a precise method can, to some extent, approximate weak stable fixed point. Instead of line searching in single-agent payoff improvement, MATRL searches for the joint policy space to achieve a weak stable fixed point (see Fig. 2). Essentially, MATRL 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 find weak stable points via empirical veta-game analysis, while the execution can still be fully decentralized. We explain every step of MATRL in detail in the following sections.
3.1 INDEPENDENT TRUST PAYOFF IMPROVEMENT
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 when each the other agents plays according to a fixed policy. We set agent i's make a monotonic improvement against the fixed opponent policies. Thus, at each iteration, the policy is updated by maximizing the utility function m over local neighborhood of the current joint policy Te, --j ft arg max,, ElI, 17 T-4) based on the trajectories sampled by Ti Æ-J. We can adopt trust region policy optimization (e.g.. PPO (Schulman et al., 2017)), which constrains step size in the policy update:
प = arg max 17ss TT) s.t. (Ty, +t) S 8;, m;Ella;
(2)
where D a distance measurement and 6, a constraint. Independent trust region learners produce the monotonically improved policy â which guarantees T): (ft T-;) 2 y (m,, T-)) and give a trust payoff bound by ăς. 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 precise lower bound for multi-agent simultaneous trust payoff region in Theorem 1:
Theorem (Independent Trust Payoff Region). Denote the expected advantage gain when Ti, m + Ti, R= as:
Fi mimm (its, #)) E (6) #1 Σ (a.
'(s,a;aa;)
Let a; = D (TT t.)) = max, Dry (+s() A (-ss) for agent i, where Drv is total variation divergence (Schulman et al., 2015). Then, the following lower bound can be derived for multi-agent independent trust region optimization:
9, n.. "Tii +1) - 4yc
(i A - Ths (T( T-1) 2
(ai + a- a,a-))3, (4)
(1 (1-
where 6 maxx.a ;a- 1A,T00 'ss, a=))
3

---

Under review as a conference paper at ICLR 2021
Proof. See Appendix B.
Based on the independent trust payoff improvement, although the predicted policy f will guide us in determining the step size of the TPR, but the stability of #-:) is still unknown. As shown in Theorem an agent's 's lower bound roughly O442), which is four times larger than the single-agent lower bound trust region of O(a²) (Kakade & Langford, 2002). Furthermore, & = mnaxs.a-.aa... | '(8, d; a-:) depends on the other agents's action a- 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.
APPROXIMATING WEAK STABLE FIXED POINT 3.2
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- bro--prblems,, finding the efficient solver for stable trust region sub sub-problems very important. Instead of using the stable fixed points (Balduzzi et al., 2018) as TSR, we choose weak stable fixed point in Definition I which is much easier to be found. To maximize the objective defined Eq. we could ask that reasonable algorithms avoid all strict minimums (a.k.a unstable fixed points), which imposes only that agents are 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.
regarding strict minimum
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 TI [ At] C H,
Denote the simultaneous gradient of the restricted underlying game as E (V x, Iis V a 9-1) and
Hessian H = E. We call (ft. (5. R-)) a fixed point if [Tt, R-i) = O. We then say (T R-;) is a weak stable fixed point if ( T--) & 0', 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-gams game that each agent has only two strategies Tı, क. for each agent i:
M(T,, Rep π -=) =
9
9
g
(5)
94
9
where 9; 2.-3 T (ite, -i) (as defined in Eq. 3) is empirical payoff entry of the meta- game, and note g. g,- 0 it has an expected advantage over itself. Compared with using the (, (-)) = n: (T :) + g - the meta-game payoff, o --- has lower variance and is easier to approximate because (T,, -) is a constant baseline. However, the most of entries in M are unknown, often requires lots of extra simulations to estimate the payoff entries (e.g.. -i in EGTA. Instead, we reuse the trajectories in the TPR step to approximate the 97-2 by ignoring small changes in state visitation density caused by the प. - मं (Schulman et al., 2015).
9:
Take two-agent case as an example, as we can see in Eq. the meta-game M becomes 2 x 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 Pt. P-i = NashSolver for the meta-game M, where P; and p-s E [0, 1). and the mixed Nash equilibrium of the meta-game also an approximated equilibrium of the restricted underlying game (Tuyls et al., 2020). Then, the trust stable region policies n. -- can be aggregated based on current policy म. and predicted policy n. 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 T; to के 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 म; and t; In this case, with μ being agent i's Nash Equilibrium policy in the meta-game, म, can be derived via the linear mixture: म, p.m; + (1 pt) p;) which delimit agent i's trust stable region. Now can prove that (7,, 7 = is weak stable fixed point for the underlying game in Theorem 2.
In this paper, we want maximize the return, not minimizing the loss, so we need avoid strict minimum.
4

---

Under review as a conference paper at ICLR 2021
Cunce Policies
Independent Podcy Improvementt
M n- 2 (T (T m-)) n- R-1) 2 T- TT)))
Next lleiioo
Respoase Fixed
2. Sobre Equitbrium Meta
Policy Aggregation
A argmaxs, 17: 2 Rx)
T-
PA(E, Rups)) PA(T-n------)
Pe NASH
T
-- argmaxx=, (-, R-4)
Figure 3: Overview of the multi- trust region learning phases in two-agent games. It can be easily extended the n-agent case by solving the n-agent two-action matrix form meta-game,
Algorithm Multi-Agent Trust Region Learning
Input: Initializing policies π; for each
1: for & E {0, 1,2, do
2: Using current policies Tr Th to collect trajectories.
3: For each i: compute trust payoff region policy म; using Eq. 2.
D> Trust Payoff Region.
4: Solve meta-game M(T ü, π T-i, π-:) and obtain meta-game Nash Pi, p--.
5: Compute weak stable fixed point ãg. R-s.
Trust Stable Region.
6: For each i: compute best response कदद using Eq. 6.
> Best Response to Fixed Point.
7: Ti Thi カ- <- T'
8: end for
Theorem (Existence of Weak Stable Fixed Point). Consider the restricted underlying game where policy space is bounded in a linear contimuous policy-spend (T, Rs), where ft is monotonically improved based on n, within TPR. (pis (pexp-x) a Nash equilibrium of the meta-gamm M, then, the linear mixture joint policy (ā;, R-1) is a weak stable fixed point for the restricted underlying game.
Proof. see Appendix C.
According Theorem 2, (T;, σ-;) is 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 al., 2018), we have stated, weak stable fixed point is 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 general- sum games, the fixed-point found by the meta-game analysis can be either stable or saddle points. Similarly, a local Nash equilibrium can 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 stronger fixed- txxed-ooint types. Nevertheless, it comes with cost, requiring additional computation assumptions which may break the most general settings. Besides, when the meta-game has multiple Nash equilibria, an equilibrium is randomly selected in 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 two major-cost sources in common meta-game analysis: approximating and solving the meta-game (Muller et al., 2019). In case, the deta-game is restricted to local two-action game, where two actions n, and म, 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 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 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-for ffom 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 small, for example, n < 10, it is affordable to find meta-game Nash equilibrium in sub-exponential complexity (Lipton al., 2003). However, this problem still exists when n is large. In this case, we could try mean mean-field approximation (Yang et al., 2018) 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.
5

---

Under review as a conference paper at ICLR 2021
3.3 IMPROVEMENT AGAINST WEAK STABLE FIXED POINT
Although the weak stable fixed point, (T,, -=),, 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 (Lanntoo 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:
.T= arg max 17 (T,, T-:)-
(6)
m; 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 already have the trajectories in the TPR step and the best response to the weak stable fixed point can be casily estimated through importance sampling. Alternatively, through defining 6
def min (1 + é, max(1 (1 - é, Fr(au)))
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: पं. = arg max,, |, [c-:7) (T,, T=:]]
Connections to Existing Methods. MATRL generalizes many existing methods with the best response. In extreme cases where the meta-game Nash is (pi.p-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 _. and T.- = arg måx,, TB [T; R-4) following the Eq. 6. The policy prediction (Zhang & Lesser, 2010; Foerster et al., 2018; Letcher et al., 2018), extra- garra-ggrdient (Antipin, 2003) and exploitability descent (Tang et al., 2018; Lockhart et al., 2019) methods are also special instances of MATRL when meta- gata- Nash (ps: p-:) +) (0. 0). This means the best response to the most aggressive predicted policy f_; and ग.. arg max=, 7, (T,, =.).
gradient-based algorithm with the best response to policies within TSR, which is essentially a variant of Look methods(e.g. LOLA LOLA (Foerster et al., 201 8),
Global Convergence. MATRL
SOS (Letcher 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 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 reasonable to avoid unstable fixed-points. Unlike LOLA, which uses first-order Taylor expansion to estimate the best response to predicted policy, we elaborately design the boo--hhedd step within the TSR and do the best response gradient steps to TSR. We also show that MATRL empirically outperforms the typical Lhokd 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 simulation. Although MATRL's training is centralized, its execution is fully decentralized. It also does not require any extra centralized parameters or higher- order 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.
4 RELATED WORK
The study of gradient- methods in multi-agent learning is quite extensive (Mazumdar et al., 2020; Buçoniu et al., 2010). Some works on learning in games have mostly focused on adjusting the step size, which attempts to use 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-orde fixed-point information via a small samt- 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 al., 2018; Tang et al., 2018; Lockhart al., 2019),

---

Under review as a conference paper at ICLR 2021
Policy, of Player 7,
50
10
Matching Pannies
Policy of Player?
Table 1: Convergence rate and average convergence step in 1000 random 2 matrix games. MATRL shows slightly better convergence rate and speed compared to IGA-PP.
CONVERGENCE RATE/ / AVERAGE CONVERGENCE STEP
ALGORITHM
COORDINATION
ANTI-COORD.
CYCLIC
Learning dynamics of MATRL in matching pennies game. The blue arrow gradient direction and the pale blue area is TSR.
Figure 4:
IGA
0.99/ / 140.67
0.975 88.95
0.78/ 452.92
IGA-PP MATRL
0.99 138.56
0.975 / 83,11
0.809 / 432.98
0.99 / 86.54
0.9825 / 75.52
0.846 369.40
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 al., 2018: Jordan & Wellman, 2009; Tuyls et al., 2020), which creates policy-space space meta-gama gett-game for modeling the multi-agent interactions. Using various evaluation metrics, 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). A Although these methods are broad with respect to multi-agent tasks, they require extensive computing resourees to estimate the empirical meta-game and solve it with its increasing size (Omidshafici 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- neta-game, which is computationally achievable in most cases. The payoff entry in MATRL's meta-game is the expected advantage, which has lower estimation variance compared to the commonly used empirically-estimee Regardless, we can reuse the trajectories in the TPR step estimate the payoff's without incurring additional sampling costs.
return in EGTAs.
Recently, due 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 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 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.
5 EXPERIMENTS
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/competiivv 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 al., 2018)) for discrete grid world games
7

---

Under review as a conference paper at ICLR 2021
GINAM
1ATTIL
1000
Eploode Reward
15
Rwward
Ejiocia Raward
500
6
200
100K
200K
100K
400K
100K
200K
200K
400K
100:
00
200K
400K
60CK
500K
Stops
Staps
(a) Two-agent checker.
(b) Four-agent switch.
(c) Three-agent MuJoCo hopper.
Figure 5: Learning curves in discrete and continuous tasks. The solid lines are average episode returns with 10 random seeds for each model, and the light color areas are the error bar.
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 MATRL can mitigate unstable cyclic behaviors (Balduzzi et al., 2019) in zero-sum games. In these tasks, MATRL uses the same PPO configurations 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 II. which has similar procedures (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 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. www./otoommme/.//eeeeeee htt//maatrrppooo ject / mm.
LOLA Foerster et al.
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 x random matrix games. Using IGA (Singh et al., 2000) as ILs of MATRL, the learning 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 x 2 games for three types: coordination, anti noti-coordinatinn, 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 I show that MATRL has a higher convergence rate and needs fewer steps for convergence in all types of games.
dynamics of MATRL
Grid World Checker and Switch. We evaluated MATRL in two grid world games from MA- Gym (Koul, 2019), two-agent checker, and four-agent switch, which are similar to games 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 and - 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 connected with 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 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 II. 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 -PO-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-playe 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
8

---

Under review as a conference paper at ICLR 2021
IL VS
MATRL VS MATRL
MATRL VS
15
6
-10
-00
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 multi-agent continuous control task with three-agent hopper from (de Witt et al., 2020). Here, three agents cooperatively control each part of hopper 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 time.
Multi-Agent Pong Atari Game. In the 2-agent pong game experiments, we used raw pixel as observation and train the MATRL and 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. II. setting in most of the policy pairs. Besides, from the MATRL vs. MATRL and IL IL settings' results, we can see MATRL. has a more transitive learning process than II., which means MATRL can mitigate the common cyclic behaviors zero-sum games.
Effect and Cost of Trust Stable Region and Best Re- sponse 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 tings are obtained by removing the trust stable region (II.-P) 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 con- vergence 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 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 and IL-PP, as shown in Fig. 7, 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.
MATRL
MATRL IL
Aggntts
3 Agents
4 Agents
Figure 7: Running time of 20,000 environ- ment steps (including 50 gradient steps) for the algorithms in 2-4 agents games.
CONCLUSION
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 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 basclines both continuous and discrete games with various agent numbers.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Anatoly Antipin. Extragradient approach to the solution of two person non-zero sum games. In Optimization and Optimal Control, pp. 1-28. World Scientific, 2003.
David Balduzzi, Sehastien Racaniere, James Martens, Jakob Foerster, Karl Tuyls, and Thore Graepel. The mechanics of n-player differentiable games. arXiv preprint arXhv:1802.05642. 2018.
David Balduzzi, Marta Garnelo, Yoram Bachrach, Wojeiech M Czarnecki, Julien Perolat, Max Jaderberg, and Thore Graepel. Open-ended learning in symmetric zero-sum games. arXiv preprini arXiv:1901.08106. 2019.
Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemyslaw Debiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Chris Hesse, et al. Dota 2 with large scale deep reinforcement learning. arXiv preprint arXiv:1912.06690, 2019.
Michael Bowling and Manuela Veloso. Multiagent learning using variable learning rate. Artificial Intelligence, 136(2):215-250, 2002.
Michael Bowling and Manuela Veloso. Existence of multiagent equilibria with limited agents. Journal of Artificial Intelligence Research, 22:353-384, 2004.
Bryan Randolph Bruns. Names for games: Locating 2x 2 games. Games, 6(4):495-520, 2015.
Lucian Buşoniu, Robert Babuška, and Bart De Schutter. Multi-agent reinforcement learning: An
overview. In Innovations in multi-agent systems and applications- pp. 183-221. Springer, 2010.
Yongcan Cao, Wenwu Yu, Wei Ren, and Guanrong Chen. An overview of recent progress in the study of distributed multi-agent coordination. IEEE Trunsactions on Industrial informatics, 9(1): 427-438, 2012.
Krishnendu Chatterjee, Rupak Majumdar, and Marcin Jurdziński. On nash equilibria in stochastic games. In International Workshop on Computer Science Logic, pp. 26-40. Springer, 2004.
Xi Chen, Xiaotie Deng, and Shang-Hup Teng. Computing nash equilibria: Approximation and smoothed complexity. In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (66) pp. 603-612. IEEE, 2006.
Constantinos Daskalakis, Paul W Goldberg, and Christos H Papadimitriou. The complexity of computing a nash equilibrium. SIAM Journal on Computing, 39(1):195-259, 2009.
Christian Schroeder de Witt, Bei Peng, Pierre-Alexandre Kamienny, Philip Torr, Wendelin Böhmer, and Shimon Whiteson. Deep multi-agent reinforcement learning for decentralized continuous cooperative control, 2020.
Jakob Foerster, Ioannis Alexandros Assael, Nando de Freitas, and Shimon Whiteson. Learning to communicate with deep multi-agent reinforcement learning. In Advances in Neural Information Processing Systems, pp. 2137-2145, 2016.
Jakob Foerster, Richard Chen, Maruan Al-Shedivat, Shimon Whiteson, Pieter Abbeel, and Igor Mordatch. Learning with opponent-leaming awareness. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, pp. 122-130. International Foundation for Autonomous Agents and Multiagent Systems, 2018.
Jakob N. Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson. Counterfactual multi-agent policy gradients. CoRR, 0os/17055.0926, 2017. URL http://
arxiv. org. abs 1100/11011000 08926.
Drew Fudenberg, Fudenberg Drew, David K Levine, and David Levine. The theory of learning in games, volume 2. MIT press, 1998.
Nikolaus Hansen, Sibylle D Müller, and Petros Koumoutsakos. Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (cma-es). Evolutionary computation, 111)):1-8, 2003.
10

---

Under review as a conference paper at ICLR 2021
Pablo Hernandez-Laal. Michael Kaisers, Tim Baarslag, and Enrique Munoz de Cote. A survey of learn- ing in multiagent environments: Dealing with non-stationarity. arXiv preprint arXiv:1707.09.0 2017.
Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. Gans trained by a two time-scale update rule converge to local nash equilibrium. In Advances in neural information processing systems, pp.
2017.
Patrick R Jordan and Michael P Wellman. Generalization risk minimization in empirical game models. In Proceedings The Sth International Conference on Autonomous Agents and Multiagent
Kestems-Volumee 1, pp. 553 560, 2009.
Sham M. Kakade and John Langford. Approximately optimal approximate reinforcement learning. In ICML,, 2002.
Anurag Koul.
collection of multi agent environments based on OpenAl gym, 2019. URL https: / / wiggttthhhu..e. cwm/ anuran -ammag/mmagymm..mmmmmmm
gym git.
Mare Lanctot, Vinieius Zambaldi, Audrunas Gruslys, Angeliki Lazaridou, Karl Tuyls, Julien Pérolat, David Silver, and Thore Graepel. A unified game-theoretic approach to multiagent reinforcement learning. In Advances in Neural Information Processing Systems, pp. 4190-4203, 2017.
Guillaume J Laurent, Læëtitia Matignon, Le Fort-Piat, et al. The world of independent learners is not markovian. International Journal of Knowledge-base and Intelligent Engineering Systems, 15(1): 55-64, 2011.
David S Leslie and Edmund Collins. Individual q-leanning in normal form games. SIAM Journal on Control and Optimization, 44(2):495-514, 2005.
David S Leslie, EJ Collins, et al. Convergent multiple multiple-timescales timescaless reinforcement learning algorithms in normal form games. The Annals of Applied Probability, 13(4): 2003.
Alistair Letcher. On the impossibility of global convergence in multi-loss optimization. arXiv preprint 1rXiv 2020.
Alistair Letcher, Jakob Foerster, David Balduzzi, Tim Rocktäschel, and Shimon Whiteson. Stable opponent shaping in differentiable games. arXiv preprint arXiv: /8/
/. 1.08469, 2018
Timothy P Lillicrap, Jonathan J Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. arXiv preprint arXiv: /5099 0tt./5599999299 2015.
Tianyi Lin, Zhengyuan Zhou, Panayotis Mertikopoulos, and Michael Jordan. Finite-time last-iterate convergence for multi multi-agent learning in games. arXiv preprint arXiv:2002.09806 2020.
Richard Lipton, Evangelos Markakis, and Aranyak Mehta. Playing large games using simple strategies. In Proceedings of the 4th ACM conference Electronic commerce, pp. 36 41, 2003.
Michael L Littman. Markov games framework for multi-agent reinforcement learning. In Machine learning proceedings 1994, pp. 157-163. Elsevier, 1994.
Michael Littman, Michael Kearns, and Satinder P Singh. An efficient, exact algorithm for solving tree-structured graphical games. In Advances in Neural Information Processing Systems, pp. 817-823, 2002.
Edward Lockhart, Mare Lanctot, Pérolat Julien, Jean-Baptiste Lespiau, Dustin Morrill, Finbarr TImbers, and Karl Tuyls. Computing approximate equilibria in sequential adversarial games by exploitability descent. IJCAI 2019, pp. 464 470, 08 2019. doi: 10.24963/ijca. 201 2/69/66.
Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, OpenAl Picter Abbeel, and Igor Mordatch. Multi-agent actor-critic for mixed cooperative-compettine environments. In Advances in neural information processing systems, pp. 2379-63990 2017.
Eric Mazumdar, Lillian Ratliff, and S Shankar Sastry. On gradient- learning in continuous games. SIAM Journal Mathematics Data Science, 103--103-13, 2020.
11

---

Under review as a conference paper at ICLR 2021
Eric V Mazumdar, Michael I Jordan, and S Shankar Sastry. On finding local nash equilibria (and only local nash equilibria) in zero-sum games. arXiv preprint arXiv: 1901.00838, 2019.
Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Chuan-Sheng Foo, Vijay Chandrasekhar, and Georgios Piliouras. Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile. arXiv preprini arXiv: (a0.:08800022.. 2018.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, loannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint arXiv:1312.5602, 2013.
Paul Muller, Shayegan Omidshafiei, Mark Rowland, Karl Tuyls, Julien Perolat, Siqi Liu, Daniel Hennes, Luke Marris, Marc Lanctot, Edward Hughes, et al. A generalized training approach for multiagent learning. arXiv preprint arXiv: (2t.::999..223,, 2019.
John Nash et al. Equilibrium points in n-person games. Proceedings of the national academy of sciences, 36(1):48 49, 1950.
Shayegan Omidshafiei, Christos Papadimitriou, Georgios Piliouras, Karl Tuyls, Mark Rowland, Jean-Baptiste Lespiau, Wojeiech M Czameeki, Marc Lanctot, Julien Perolat, and Remi Munos. a-rank: Multi-agent evaluation by evolution. Scientific reports, 9(1):1-29, 2019.
Marco Pangallo, James Sanders, Tobias Galla, and Doyne Farmer. A taxonomy of learning dynamics in 2 x games, 2017.
Peng Peng, Ying Wen, Yaodong Yang, Quan Yuan, Zhenkun Tang, Haitao Long, and Jun Wang. Multiagent bidircttoonall--corrdnnae nets: Emergence of human-level coordination in learning to play starcraft combat games. arXiv preprint arXiv: 1703. 10069, 2017.
Tabish Rashid, Mikayel Samvelyan, Christian Schroder de Witt, Gregory Farquhar, Jakob N. Foerster, and Shimon Whiteson. QMIX: monotonic value function factorisation for deep multi-agent reinforcement learning. CoRR, abs/1803. 1485, 2018. URL http::/arxiv/ org abs/ 1803. 11485.
John Schulman, Sergey Levine, Philipp Moritz, Michael I. Jordan, and Pieter Abbeel. Trust region policy optimization. CoRR, abs/1502.05577,, 2015. URL httt:://axxiii...o. 05477.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. CoRR, fass/707.00644/ 2017. URL http://arxiv www.aawwwwww..raeaoaoaaaaeooeree org/abs/
Lloyd S Shapley. Stochastic games. Proceedings of the national academy of sciences, 39(10): 1095-1100, 1953.
Yoav Shoham and Kevin Leyton-Browe Multiagent systems: Algorithmic, game-theoretic, and logical foundations. Cambridge University Press, 2008
Satinder Singh, Michael Kearns, and Yishay Mansour. Nash convergence of gradient dynamics in general-sum games. Proceedings of the Sixteenth conference on Uncertainty in artificial intelligence, pp. 541-548. Morgan Kaufmann Publishers Inc., 2000.
Kyunghwan Son, Daewoo Kim, Wan Ju Kang, David Earl Hostallero, and Yung Yi. Qtran: Learning to factorize with transformation for cooperative multi-agent reinforcement learning. arXiv preprint arXiv:1905.05408, 2019.
Xinliang Song, Tonghan Wang, and Chongjie Zhang. Convergence of multi-agent learning with a finite step size in general-sum games. In Proceedings of the 18th International Conference on Au- tonomous Agents and MultiAgent Systems, pp. 935-943, International Foundation for Autonomous Agents and Multiagent Systems, 2019.
Sainbayar Sukhbaatar, Rob Fergus, et al. Learning multiagent communication with backpropagation. In Advances in Neural Information Processing Systems, pp. 2244-222 22522, 2016.
12

---

Under review as a conference paper at ICLR 2021
Peter Sunehag, Guy Lever, Audrunas Gruslys, Wojciech Marian Czarnecki, Vinicius Zambaldi, Max Jaderberg, Mare Lanctot, Nicolas Sonnerat, Joel Z Leibo, Karl Tuyls, et al. Value-deconnosition networks for cooperative multi-agent learning based team reward. In Proceedings of the 17th international conference on autonomous agents and multiagent systems, pp. 2085-2087. International Foundation for Autonomous Agents and Multiagent Systems, 2018.
Ming Tan. Multi-agent reinforcement learning: Independent vs. cooperative agents. In Proceedings of the tenth international conference on machine learning, pp. 330-337, 1993.
Jie Tang, Keiran Paster, and Pieter Abbeel. Equilibrium finding via asymmetric self-play reinforce- ment learning. Deep Reinforcement Learning Workshop NeurIPS 2018, 2018.
Justin K Terry and Benjamin Black. Multiplayer support for the arcade learning environment. arXiv preprint arXiv:2009.09::5 2020.
Karl Tuyls, Julien Perolat, Mare Lanctot, Joel Z Leibo, and Thore Graepel. A generalised method for empirical game theoretic analysis. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, pp. 77-85. International Foundation for Autonomous Agents and Multiagent Systems, 2018.
Karl Tuyls, Julien Perolat, Mare Lanctot, Edward Hughes, Richard Everett, Joel Z Leibo, Csaba Szepesvári, and Thore Graepel. Bounds and dynamics for empirical game theoretic analysis. Autonomous Agents and Multi-Agent Systems, 34(1):7, 2020.
Oriol Vinyals, Igor Babuschkin, Wojciech M Czamecki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature, 575(7782):350-354 2019.
Michael Wellman. Methods for empirical game-theoretic analysis. AAAI, pp. 1552-1556, 2006.
Yaodong Yang, Rui Luo, Minne Li, Ming Zhou, Weinan Zhang, and Jun Wang. Mean field multi-agent reinforcement learning. arXiv preprint 102.:::802..053388. 2018.
Yaodong Yang, Rasul Tutunov, Phu Sakulwongtana, and Haitham Bou Ammar. a-rank: Practically scaling o-rank through stochastic optimisation. arXiv preprint arXiv:1909.11228 2019.
Chongjie Zhang and Victor R. Lesser. Multi-agent learning with policy prediction. In AAAI, 2010.
Petr Šebek. Nash equilibria noncooperative games., sept 2013. URL https:tttttttttieee com/
Art imimmmi/// mmm//eng
13

---

Under review as a conference paper at ICLR 2021
A MATRL ALGORITHM BASED ON PPO
Algorithm 2 Multi-Agent Trust Region Learning Algorithm (PPO Based, Two-Agent Example).
Input: The initial policy parameters 0,, 02, initial value function parameters Φ1, $2 and
1: for {0, 1, 1.2....) do
2: Using π (01), (02) to collect trajectories T1, 72-
3: Compute GAE reward R2 for each i.
4: Compute estimated advantages Å Ag based on the current value functions V Vol
5: for i E { do
6: Compute trust payoff region policy ft using Eq.
7:
Update the policy
by maximizing the PPO-Clip objective:
0. arg maxa; [.. ΣEer, Σ min (ellea)
A A (som.. gle, AT 2 (s (211)))))))
where & a clipping function. Fit value function by regression on mean-squared error:
8:
&f arg min
Vo (8t) Ruit)
T;
T
TET; 1=0
9:
end for
10:
Construct the meta-gama game (11 (01), #1 (02), T2 (22)) t2 (02)).
Solve M and obtain meta Nash Pl, P2-
12:
Compute aggregated weak stable fixed point (TI, 72).
for E {1,2] do
14:
Compute ; which best responses to ã- using Eq. 6.
Estimate the best response by importance sampling:
0 T3
8
9 (c, ns/R-s)
T
FET:
16: end for
17: 01 04 02 +- 8/2-
18: end for
Output: (81), πτ (02).
B INDEPENDENT TRUST PAYOFF REGION
We use the total variation divergence, which is defined by (rl = probability distributions p, q (Schulman al., 2015). Dipas (m. f)) is defined as:
Σ, lpj }
Øj for discrete
D (TT, π) max Drv (1()))))))())
Based on this, can define a-coupled policy as:
Definition 2 (a-Coupled Policy (Schulman et al., 2015)). n') is an a-coupled policy pair if defines a joint distribution (a, d')]s, such that P(a + a' a'ls) I a for all s. and nt' will denote the marginal distributions of a and a'. respectively.
When the joint policy pair Ti, m- changes to n/. T', and coupled with og and a-; correspondingly:
4yc
TT( ='';)
(e(F,,T-1) A. T- ( + (1- (as + +a. a,
(8)
where
max 5,0,0_
The proofs are following:
14

---

Under review as a conference paper at ICLR 2021
Lemma 1. Given that (Ta, u²) and (T- x(-;) are both a-coupled policies bounded by as and a- respectively. for all s,
| A (s) S 2(a; a-; a;a-i) max
A 0s. a-1)
(9)
Proof.
((8) = Ratiol [ATi ((s,d()
(10)
(8,
(11)
= P((a # df V v # a'_ (24 Jola DAA (8,
(12)
A Ti. (8,0;,
(13)
S (ai a-i 0;00-).2 .2 max 5, i.
|A, ((s,a;aa-)))
(14)
where P(a; & df Va_ + d'(l)) =1 a1)(1 a_1)= a4 a:1 0,0-+
Lemma 2. Let (Tt; TT) and (T_ R'ss) are a-coupled policy pairs. Then,
Bewaat [A,..--1 [5)] - E -1 [A, n= [s)]
(15)
< 4(aa; + a-t a,a-;) (1 a1) (1-a)))) max
(s, aq as,
Proof. The preceding Lemma bounds the difference in expected advantage at each time step L. When t' = 0 indicates that Ti, -h= and T/. T'; both agreed on all time steps less than t. By the defimition of ag a-i, P(T,, T- == nH, T' ltt i) 2 (1 - az)(1 a-1), so P(t' = 0) 2 (1- (1-a,)((1 - a_.)'
and P(t' > 0) < - (1 a;)² a_ We can sum over time to bind the difference between mi (T x²,)) and me(TT. -I).
8
(T vL,) L, - - क
Σ 7* E BEINTi [A,
BB [A, [Am (8)
1=0
(16)
4e(a; - -4 a
1=0
(17)
+ aaa 1
1-7
1 x(1 - ai) a
(18)
4e(a; +a ,²
(19)
(1- (1 - 7(1 a1)(1 a-i))
4e(as + a-i ,;a=,)2
(20)
(1 7)-
where e = max |A, (s, (s,am,ai)))
Note that
I. T
(((, =
TT- + Σ 50 (s)) Σ x((asls) Σ (1))))))) a(,,a;,a.).
(21)
Then, we can have
47c
The (T x'1)-= - (T A. T
(as aa- aa,a)))) (22)
(1 7)2
15

---

Under review as a conference paper at ICLR 2021
C PROOF OF THEOREM 2
At each iteration, denote Vigi = V Vr.. TM and vi-i9 = V V = -.. for each i. Consider the simultaneous gradient & of the expected advantage gains and the corresponding Hessian H:
((T = (Vig,, V -
(23)
1 = (
Viig
Vi,-ih
(24)
-1,9--
V -i--
For restricted underlying game, where policy space is bounded: n; E [TT, #t). Assume т; is the linear mixture of Ti, R; and fh; = p; + (1 - pi) where Pi E [0, 1]. Therefore, we can re-write the 9: Th. (Ti TT-)) in the form of:
T (T) 96 - 9i
(ps.P-i) = 1sppp111ppppp p-1) 6. p:) - (11 +
(25)
Then we have:
(e::(p=)) = (1-p-i)g p-19s 7, (1
p=i) 5.=
(26)
and E(T;;; n-1) E(p,, ((p)) Given meta Nash policy pair (M -)), where म.. = p p A according to the Nash definition, we have:
(1
1
Pr Ps
9i
9
9i
g
1
11 -
pp.))
P-i
2
(1
Pi
Pi)
9,
9
9
9
-
(1 p-i
p (27)
which implies:
( P.) P.V 0, P. [0,
(28)
(-----VV-0--000 20, P., Pr E [0, 1].
When Pi p_1 (0, 1) in accordance with the Nash condition in Eq. 28, -
O. It shows that (ā; न -.) .) is a fixed point due to ( = E(p.. p-i) = 0. For the boundary case, where P; or p-; {0. 1). because they are constrained to the unit square [o. 1] x 10, 1). the gradients on the boundaries of the unit square are projected onto the unit square, which means additional points of zero gradient exist. other words, Vagi and - are still equal to zero in boundary case, and the (T;;, =-;) is fixed point in both cases.
Next, we determine what types of the fixed point that (T, --1) belongs to. According to the Eq. 24, we have the exact Hessian Matrix for the restricted game:
3,-1
1, 3.-8
91
9i
11 == =
-
- 9-1
(29)
9-1
0
The eigenvalue À of H can be computed:
2 Tr(H)A + det = X2 - - g: 1 - gi
- 21-2 ( - 9
-
- =
(30)
Denotes 9: = o 3.- for the fixed point (p:, P):):
gi i- 3. - we have A = = VV Therefore, we can have following cases
1. Fully cooperative games: D. S 0, S O, then H(P,, 3 0, which means (Ø,, p_;) is a stable fixed point we are maximizing the objective.
2. Fully competitive games: Ti 0, or 9: 0, 0, all X have pure imaginary eigenvalues with zero real part, where (p., P-+) is saddle point.
3. General sum games: they are in in-between the cooperative and competitive games, which means (p:, p-)) can be either stable fixed point or saddle point.
Because we assume मं monotonically improved compared to T. then even in zero-sum case, there is at least one negative value in 9, and -- Therefore, in all the situations, (pr, p-x) 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:
16

---

Under review as a conference paper at ICLR 2021
(a)
(c)
Figure 8: Multi-agent discrete and continuous action tasks: (a) 2-agent checker (discrete), (b) 4-agent switch (discrete), (c) 3-agent MuloCo hopper (continious).
NMr of Maner 1
-1000
Egisade
2000
-3000
100K
200K
S00K
Pappr2
Palky 1
Steps
(a) Chicken.
(b) Prisoners' Dilemma.
4-Agent Ant.
Figure 9: (a)-(b): Learning dynamics of two games using MATRL. Extra learning curves in 4-Agent Ant multi-agent MuJoCo task.
Remark 1. Let (pi,p-) be a Nash equilibrium of the policy-space meta-game M(T;, āi, m-i, ñ which is used for computing the linear mixture policies T., R-5. For simplicity, define p; = 1 Pi. then we have the payoff improvement lower bound R.. T-
47
Th (T R-1) - ( T_1) 2 9, T.. (f;,,
(a:p: + aa-p-- a,a-; (31)
(1 (1-7)
that is a tighter lower bound compared with Theorem I.
trajectories using its current policy n; by independent play with other agents. Then a predicted policy f can be estimated using the single-agent trust region methods, which agents' current policy --;. 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, approximate n-agent two-action meta-game in policy-space by reusing the trajectories from the last TPR step. this game, each agent has two pure strategies: choosing the current policy T, predicted policy à; and the corresponding payoffss are the expected advantages (defined in Eq. 3) of the joint policy pairs. By constructing such a meta- game, we transform a complex multi- agent interactions problem into game-theorete analysis concerning the underlying game restricted in [TT #t.. Then we can obtain a weak stable fixed point as TSR within the TPR by solving the gemaagamee. When the fixed point is saddle point we then take the best response the weak stable fixed point to get the next iteration's 's policies. This encourages exploration and avoid stagnation at an unexpected saddle point.
Finally, we obtain MATRL as follows: First, an agent collects
a trust payoff improvement against the other
D ENVIRONMENT DETAILS
Random 2 x 2 Matrix Games. We created generator of 2 x 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- cotrrioddinno games have 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.
17

---

Under review as a conference paper at ICLR 2021
Figure 10: Pong game in Atari 2600.
Grid World Games. In two-player checker, shown in Fig. Sa, there is sensitive player who gets reward 5 when they collect an apple and 5 when they collect a lemon; less sensitive player gets for apple and I for lemon. The learning goal is 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 figure out a way to go through a narrow corridor. The agent gets -1 for taking each step and 5 when arriving at 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-playe 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 (de Witt 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 the action, and all the agents have full observation of the states of size 17. We use the same prper-pprameters for MATRL, MATRL w/o BR, and IL-PP. For MADDPG agent, we use the hyper-parameter described in the paper (de Witt et al., 2020).
Multi-Agent Atari Game. The pong game is multi-agent Atari version of table tennis, as shown in Fig. 10. Two players must prevent a ball from whizzing past their paddles and allowing their opponent score. The game ends when one side earns 21 points.
E EXPERIMENTAL PARAMETER SETTINGS
For all the tasks, the most important hyper-parameters 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 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 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.
stable learning curve. And for different environments, policy and
Matrix Game and Random 2 x 2 Matrix Games. The papee--rrameters 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 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
Grid World Games and Multi-agent Continuous Control Task. The hyper-parameee 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
Pttpps: //gi thub. www.bcco....o...ccoooooooo. http:/etttiigggee TeammMiieaaaaaii
Agent-Aln ALIE
18

---

Under review as a conference paper at ICLR 2021
Table 2: Hyper-parameter settings in 2 x matrix games.
SETTINGS
VALUE
DESCRIPTION
COMMON SETTINGS
INITIAL POLICIES I
0.9.0.1
THE INITIAL POLICY VALUES FOR PLAYER
INITIAL POLICIES
0.2.0.88
THE INITIAL POLICY VALUES FOR PLAYER
MATRL SETTINGS
BEST RESPONSE LEARNING RATE
0.03
THE LEARNING RATE FOR THE BEST RESPONSE STEP
KL COEFICIENT
100
THE KL-DIVERGENCE COLTECIENT POLICY
WOLF SETTINGS
LEARNING RATE MAXIMUM
0.06
THE MAXIMUM LEARNING RATE FOR WOLF LEARN FAST AGENT
LEARNING RATE MINIMUM
0.02
THE MINIMUM LEARNING
WoL.F WIN AGENT
Table 3: MATRL parameerr settings in grid worlds.
COMMON SETTINGS
VALUE
DESCRIPTION
POLICY LEARNING
0.002
OPTIMIZER LEARNING RATE.
BATCH SIZE
2000
NUMBER OF DATA POINT FOR EACH UPDATE.
GAMMA
0.99
LONG TERM DISCOUNT FACTOR.
HIDDEN DIMENSION
128
SIZE OF HIDDEN STATES.
NUMBER OF HIDDEN LAYERS
2
NUMBER OF HIDDEN LAYERS.
NASH EQUILIBRUUM SOLVER METHOD
CMAES
THE METHOD FINDING THE NASH EQUILIBRIUM META-GAME
NEURAL NETWORK
MLP
THE NEURAL NETWORK ARCHITECTURE POR POLICY AND CRITIC
POLICY UPDATE INTRRATIONS
10
NUMBER
FOR EACH
UPDATE.
BEST RESPONSE LEARNING RATE
0.002
THE LEARNING RATE FOR BEST RESPONSE STEP
BEST RESPONSE INTERACTIONS
NUMBER GRADIENT STEPS FOR BEST RESPUNSE STEP
KL CORFFICIENT
0.001
THE KL DIVERGENCE COEFRICIENT IN CALCULATING LOSS
ENTROPY COFFFICIENT
0.05
THE ENTROPY COFFFICIENT IN CALCULATING LOSS
POLICY RATIO CLIP
0.1
THE CLIP VALUE FOR POLICY RATIO
BEST RESPONSE IMPORTANCE RATIO CLIP
0.1
THE CLIP VALUE FOR BEST RESPONSE IMPORTANCE WEIGHT
2 PLAYER SWITCH
VALUE LOSS COLFFICIENT
0.01
THE VALUE LOSS IS LARGER THAN POLICY LOSS
PLAYER CHECKER
VALUELOSS COLFFICIENT
1.0
THE VALUE LOSS IS AT SAME SCALE AS POLICY LOSS
PLAYER SWITCH
VALUE CORFRICIENT
VALUE LOSS LARGER THAN POLICY LOSS
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, le 2]. Also, we added entropy loss and KL loss encourage exploration and limit the policy update for each step. We used (Š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 Table 4 and
The syper--parmeters setting for MATRL are listed in Table 6. We used the same hyper-parameters for MATRL and II. We take the raw pixel input from the Atari environment, and we processed it with 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 layer fully connected network to get the policy.
Multi-agent Atari Pong.
19

---

Under review as a conference paper at ICLR 2021
Table 4:
settings for baseline algorithms in grid worlds.
SETTINGS
VALUE
DESCRIPTION
MONOTONE NETWORK LAYER
2
LAYER NUMBER OF MONOTONE, NETWORK.
TARGET NETWORK UPDATR INTERVAL. LEARNER
200 DOUBLE-Q LEARNER
NUMBER OF ITERATIONS BETWEEN RACH TARGET NETWORK UPDATE
THE ALGORITHMS
AGENT
JOINE ACTION- VALUE NETWORK LAVER
2
LAYER NUMBER OF JOINT ACTION- VALUE NETWORK.
ACTION-VALUE
128 DOUBLE-Q LEARNER
ACTION-VALL VALUE
LEARNER
THE ALGORITHMS FOR FACH AGENT
Table 5: Hyper-parameter settings in multi-agent MuloCo hopper.
SETTINGS
VALUE
DESCRIPTION
AGENT ALGORITHM
PPO
THE LEARNING ALGORTH FOR AGENT NETWORK ARCHITECTURE LEARNING RATE FOR AGENTS
[128, 128]
LEARNING RATE
0.002
UPDATE
VALUE LOSS COFFECCIENT
0.001
THE VALUE LOSS COEFFICIENT IN TOTAL LOSS
COEFFICIENT
TOTAL
POLICY UPDATE ITERATIONS
10
NUMBER OF GRADIENT STEPS FOR EACH BATCH OF UPDATE.
RESPONSE LEARNING
BEST RESPONSE INTERACTIONS
NUMBER OF GRADIENT STEPS FOR BEST RESPONSE STEP THE KL-DIVERGENCE COEFFICIENT IN TOTAL LOSS
ENTROPY
0.05
KL-DIVERGENCE CORFFICIENT
0.01
MADDPG
[300, 300]
NETWORK ARCHITECTURE LEARNING RATE FOR AGENTS
LEARNING RATE
0.001
UPDATE INTERVAL
100
UPDATE THE NETWORK EVERY 100 TIME STEPS
GAMMA
0.99
DISCOUNT FACTOR
Table 6: Hyper-parametee settings in multi-agent pong Atari.
SETTINGS
VALUE
DESCRIPTION
MATRL AND HTS VARIANTS
AGENT ALGORITHM
PPO
THE LEARNING ALGORITHM
NETWORK
3 LAYER CNN, 2 LAYER
THE NETWORK ARCHITECTURE, AND SIZE FOR THE PPO AGENT LEARNING RATE POR AGENTS
LEARNING RATE
0.002
IZE:
BATCH SIZE: ONE UPDATE
VALUE LOSS CORFRICIENT
0.1
THE VALUE LOSS COEPRICIENT IN TOTAL LOSS
COEFECIENT
COEFFICIENT
POLICY UPDATE LTERATIONS
10
NUMBER OF GRADIENT STEPS FOR EACH BATCH OP UPDATE.
BEST RESPONSE LEARNING RATE
0.002
THE
BEST RESPONSE INTERACTIONS
NUMBER OF GRADIENT STEPS FOR REST RESPONSE STEP ENTROPY
ENTROPY COEFFCIENT
0.05
LOSS
KL-DIVERGENCE COEFICIENT
THE KL-DIVERGENCE COFFECIENT IN TOTAL LOSS
GAMMA
0.99
DISCOUNT FACTOR
20


Reviews:
[{"review_id": "xPFXEeKDrzz", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "MULTI-AGENT TRUST REGION LEARNING\n\nSummary\n\nThe authors establish a trust-region method for multi-agent RL. The idea is to apply TRPO to each agent separately, but with a trust region whose properties for agent i, depend on those of agent not-i. The authors propose, at iteration k, to find a weak stable fixed point for a game M_k, defined by a matrix of payoffs given by the (expectation value of) advantages. They show that solving for the equilibrium of M_k yields policies that monotonically improve performance, i.e., each agent's payoff at least does not decrease. \n\nThe authors addresss the extra cost introduced by having to solve a game at each iteration, which does not scale well as the number of agents N grows. \n\nThey compare with independent learners (IL), and evaluate 3 synthetic experiments, multi-agent variations of Mujoco sims, and Atari pong. For games have fully cooperative rewards, but feature adversarial dynamics/rewards, the authors compare convergence rates (faster convergence in synthetic games), pair-wise win-rate (MATRL beats IL agents on pong), and overall reward-growth (MATRL improves reward faster in cooperative games). \n\nStrengths\n\n- The paper is written clearly, and the technique is relatively straightforward. \n- The empirical evaluation seems sufficient in terms of showing MATRL improves over IL. \n\nWeaknesses\n\n- I would have liked to also see some comparison with techniques like LOLA, symplectic gradient adjustments, etc, as it's unclear what equilibrium MATRL converges to. Alternative (higher-order) methods don't necessarily converge to the equilibria of the original game -- does MATRL do so? Are MATRL solutions still a 'true' Nash equilibrium of the underlying game? \n- I would have liked to see more reporting on the runtime of solving the meta-game. As the authors mention, this is a crucial issue in scaling this up, and it would be good to see some quantitative benchmark of run-time vs number of agents. \n\nQuestions\n\n- Eq 2 has a typo? D(pi_i, pi_i)", "extra_scores": {}, "extra_text": {}}, {"review_id": "coFUd2X0s9", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nThis 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.\n\nStrengths:\n* good motivation of why independent learner algorithms may not converge due to missed coupling\n* clever construction of meta game\n* good choice of variety of experiments\n\nWeaknesses:\n* the notion of “weak stable fixed point” is extremely weak. For example , Mazumdar 2020 (who is cited) and many others consider much stronger criteria like local Nash or differential Nash, or even quasi-Nash. As I understand it, “weak stability” is just requiring that iterates don’t ever find a local minimum in the coupled strategy space of all agents. Not only is this artificially introducing a coupling requirement between the agents, but it is basically just saying that the agents shouldn’t ever find themselves all wishing to change collectively.\n* the preliminaries are sometimes stated in a way that indicates only two players and other times N players\n* figures 1 and 2 are confusing\n* I find theorem 1 to be hard to parse (much notation is not defined clearly), based on very strong assumptions (alpha coupling, discrete spaces), essentially pointing out a fact about prior work on independent methods (not the current proposed one), and overall unnecessary in the present paper. I would advocate removing it.\n* it should be clarified that the rho are really distributions corresponding to mixed Nash strategies in the meta game, rather than deterministic strategies (which may not even exist)\n* in the experiments, it is not statistically useful to show results for only 5 seeds. I understand that these things are expensive and I have this comment for the vast majority of work in RL I have ever read, but showing plots like figure 5 is misleading, esp. without an immediate caution in the caption and remain text\n* I found figure 6 and the related text very confusing and not really useful in understanding what is going on\n* only validating convergence in matrix games is very limited. I was missing a more complete discussion of convergence, if only experimental\n\nNitpicks:\n* there were numerous typos and syntax/semantic errors throughout the paper. I would recommend employing the services of a copy editor in future\n\nOverall:\nI like the main concept of this paper, but I really can not recommend it for publication at this time, I have listed a number of directions in which I feel this paper could be improved in rebuttal or even in a later submission if it goes that route. My main concerns are: (1) the weakness of the theoretical property of “weak stability”, (2) lack of a more complete evaluation of convergence, (3) general confusion throughout reading the paper.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "L0ZRF9Ubise", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "---- Summary ----\nThis paper proposes a multi-agent learning algorithm where after each policy improvement step, a small meta-game is analysed to propose a corrected step. The paper performs experiments in various MARL environments to test the approach.\n\n---- Reasons for score ----\nI recommend accepting this paper. The paper addresses the important problem of the non-convergence of independent learning in MARL. The algorithm proposed is novel and well justified, and the experiments show that it yields an improvement over independent learners.\n\n---- Pros ----\n1. The fundamental idea of the paper - taking independent policy improvement steps, and then analysing a local metagame to decide how to update policies - is interesting and novel.\n2. The practical algorithm this leads to helps with the problems of independent learning in MARL, without a large increase in algorithm complexity.\n3. The experiments demonstrate the advantages of the algorithm, in a variety of domains and with a fair comparison to the IL methods MATRL is being based on and other relevant baselines.\n4. The paper is situated well with respect to the existing literature.\n\n---- Cons ----\nIt seems to me that the effectiveness of the proposed method is likely to be heavily influenced by the underlying IL algorithm employed. In particular, an IL algorithm making very large policy updates is likely to need more correcting. For this reason, it would be interesting to investigate how the performance of MATRL and IL varies with a range of policy update sizes, and it would also be useful to clarify how the hyperparameters for the various experiments were selected.\n\n---- Typos and other minor comments ----\n1. Please clarify the meaning of the error bars in Figure 5.\n2. In the sentence before section 3.1, steps->step and details->detail.\n3. I didn't understand this in section 3.1: \"We set agent i’s to make a monotonic improvement of its policy.\"\n4. Near the bottom of page 3, \"conflict interests\" -> \"conflicting interests\"", "extra_scores": {}, "extra_text": {}}, {"review_id": "2_u4bPkjy5", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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. \n\nThe idea of extending trust region methods to the multi-agent case is an interesting idea. As the paper points out, the multi-agent case is more complicated since the other agents are also learning, making the environment appear non-stationary from a single agent's perspective. The idea of using a meta-game with limited (i.e., 2) policy update choices at each step greatly simplifies learning, while at least somewhat taking other agent changes into account. Also, the method is based on theory for converging to a (weak stable) fixed point. \n\nThere are a lot of interesting ideas in the paper and the experiments are promising, but many of the details in the paper are not clear.\n\nFor example, the general assumptions and algorithm become clear in Figure 3 and Algorithm 1, but these should be explicitly stated much earlier (e.g., at the beginning of 3). Even so, it still isn't clear exactly what is assumed to be known about other agent policies. It appears that the process is fully centralized, where all agents know all other agents policies at all times. If this is indeed the case, why is it reasonable to use a centralized approach in a self-interested setting? In MARL, even assuming other agent actions are observed is a strong assumption, so assuming other agents policies are known is very strong. Furthermore, the paper says \"MATRL also provides fully decentralized execution and only requires a centralized mechanism to adjust the step size rather than a centralized critic or communication.\" but it appears that the training phase would need much more than that (to solve the meta-game) while the execution could be decentralized. A more detailed description of the algorithm should be given along with the assumptions needed. \n\nIt also isn't clear how useful the theory is since it only applies to the restricted underlying game rather than the full game. Since it appears to assume the other agents are fixed, it would be useful to at least speculate what could be said about the full case (e.g., when other agents are not fixed and when it can't be assumed the other other agent policy updates are known). Also, the game values in 5 would just be estimates in the MARL case (due to sampling and other agent changes) so it doesn't seem like the theory would apply in that case. These issues should be clarified in the paper. \n\nThe experimental results are impressive and show the proposed method works well. The method (MATRL) converges faster or to better values in all the domains. Nevertheless, it is not clear how the domains were chosen and many of the baselines are weak. In terms of the domains, the paper should discuss why a subset of domains is chosen (i.e., why these particular domains). In terms of baselines, there are stronger methods in each case. For example, many other MARL methods would apply in the Checker, Switch and MuJoCo domains (e.g., COMA and MAAC). Why use only VND and QMIX (which are very different than the proposed method)?  Why not use any other method (besides independent learners) in multi-agent pong? Lastly, several of the domains are partially observable, but the method is only defined in terms of full observability and nothing is said about how it was adapted to run in the partially observable case. It is assumed that they pretend the observation is state, but this should be made clear. ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: There was some slight disagreement on the paper, but the majority of reviewers agree that although some answers of the authors on questions brought good clarification, other issues still remain problematic. Some of the assumptions remain unclear (w.r.t CDTE), and reviewers still have doubts about the global convergence and weak stable fixed point concept, that lack clear math details.
The experiments are also still a bit too immature, more comparison is needed, as well as an evaluation on other domains.
Decision: Reject