Dealing with Non-Stationarity in MARL via Trust-Region Decomposition
Authors: Wenhao Li
Xiangfeng Wang
Bo Jin
Junjie Sheng
Hongyuan Zha
Venue: ICLR 2022 Poster (2022)
Keywords: Nonstationarity
Trust-Region Methods
Multi-Agent Reinforcement Learning

Abstract: Non-stationarity is one thorny issue in cooperative multi-agent reinforcement learning (MARL). One of the reasons is the policy changes of agents during the learning process. Some existing works have discussed various consequences caused by non-stationarity with several kinds of measurement indicators. This makes the objectives or goals of existing algorithms are inevitably inconsistent and disparate. In this paper, we introduce a novel notion, the $\delta$-$stationarity$ measurement, to explicitly measure the non-stationarity of a policy sequence, which can be further proved to be bounded by the KL-divergence of consecutive joint policies. A straightforward but highly non-trivial way is to control the joint policies' divergence, which is difficult to estimate accurately by imposing the trust-region constraint on the joint policy. Although it has lower computational complexity to decompose the joint policy and impose trust-region constraints on the factorized policies, simple policy factorization like mean-field approximation will lead to more considerable policy divergence, which can be considered as the trust-region decomposition dilemma. We model the joint policy as a pairwise Markov random field and propose a trust-region decomposition network (TRD-Net) based on message passing to estimate the joint policy divergence more accurately. The Multi-Agent Mirror descent policy algorithm with Trust region decomposition, called MAMT, is established by adjusting the trust-region of the local policies adaptively in an end-to-end manner. MAMT can approximately constrain the consecutive joint policies' divergence to satisfy $\delta$-stationarity and alleviate the non-stationarity problem. Our method can bring noticeable and stable performance improvement compared with baselines in cooperative tasks of different complexity.

Published as a conference paper at ICLR 2022
DEALING WITH NON-STATIONARITY IN MARL VIA TRUST-REGION DECOMPOSITION
Wenhao Li, Xiangfeng Wang", Bo Jin", Junjie Sheng School of Computer Science and Technology East China Normal University Shanghai, China
(521945010260stt) xfwangêes, bjinêcs, 521945010C30stu).eee www.:eessssseeeeeeeee. en
Hongyuan Zha
School of Data Science, The Chinese University of Hong Kong (Shenzhen)
Shenzhen Institute of Artificial Intelligence and Roboties for Society
Shenzhen, China
baahy@cuk.edd...
ABSTRACT
Non-stationarity is one thorny issue in cooperative multi-agent reinforcement learning (MARL.). One of the reasons is the policy changes of agents during the learning process. Some existing works have discussed various consequences caused by non-stationarity with several kinds of measurement indicators. This makes the objectives or goals of existing algorithms are inevitably inconsistent and disparate. In this paper, we introduce a novel notion, the 6-stationarity measurement, to explicitly measure the non-stationarity of a policy sequence, which can further proved to be bounded by the KL--divergence joint policies. A straightforward but highly non-trivial way is to control the joint policies' divergence, which is difficult to estimate accurately by imposing the trust-region constraint the joint policy. Although it has lower computational complexity to decompose the joint policy and impose trust-region constraints on the factorized policies, simple policy factorization like mean-field approximation will lead to more considerable policy divergence, which can be considered as the trust-region decomposition dilemma. We model the joint policy pairwise Markov random field and propose a trust-region decomposition network (TRD-Net) based on message passing estimate the joint policy divergence more accurately. The Multi-Agent Mirror descent policy algorithm with Trust region decomposition, called MAMT, established by adjusting the trust-region of the local policies adaptively in an end-to-end manner. MAMT can approximately constrain the consecutive joint policies' divergence
consecutive
satisfy 5-stationarity and alleviate the non-stationarity problem. Our method can bring noticeable and stable performance improvement compared with baselines in cooperative tasks of different complexity.
INTRODUCTION
Learning how to achieve effective collaboration in multi-agent decision- makinn tasks, such as multi- player games (Berner et al., 2019; Vinyals et al., 2019; Ye et al., 2020), resource allocation (Zimmer al., 2021; Sheng et al., 2022), and network routing (Mao al., 2020a;b), is significant problem in cooperative multi-agent reinforcement learning (MARL.. Although deep reinforcement learning (RL) has achieved great success in single-agent environments, its adaptation to the multi-agent system (MAS) still faces many challenges due to the complicated interactions among agents. This paper focuses on one of these thorny issues, i.e., statiionatirit caused by changing agents' policies during the learning process. Specifically, the state transition function and the reward function of each agent depend on the joint action of all agents. The policy change other agents leads to the change
"Corresponding authors: Xiangfeng Wang and Bo Jin

---

Published as a conference paper at ICLR 2022
of above two functions for each agent. Recently, many works have been proposed to deal with this non-stationarity problem. These works can be divided into two categories (Papoudakis et al., 2019): targeted modifications on standard RL learning schemes (Lowe et al., 2017; Foerster et al., 201 18;; Iqbal & Sha, 2019; Baker et al., 2019), and opponent information estimation and sharing (Raileanu et al., 2018; Foerster et al., 201 8a; Rabinowitz et al., 2018; Al-Shedivat et al., 2018).
Both categories aim to mitigate the negative impact of policy changes to solve the non-stationarity problem. These algorithms have studied the various consequences caused by non-stationarity and put forward several indicators to measure these consequences. The objectives or goals of these algorithms are inevitably inconsistent and disparate, which makes them ineffective general. Additionally, those methods also require either an unexpansive training scheme or excessive information exchange, which significantly increase the training costs. Recently, some work has shown that naive parameter sharing, particular case of opponent information sharing, can effectively alleviate the non-stationarity problem (Gupta et al., 2017; Terry et al., 2020). However, we can prove that naive parameter sharing can lead to an exponentially worse suboptimal outcome with the increasing number of agents.
From the perspective of each agent, solving the non-stationarity problem in cooperative MARL can be transformed into solving multiple non-stationary Markov decision processes (MDPs) (Jaksch et al., 2010; Ortner et al., 2020; Cheung et al., 2019; Mao et al., 2021). In these MDPs, the interactive environment is composed of multiple agents, and the reason for the non-stationary environment is the changing of agent policies. If the policies of all agents change slowly, the environment can remain stable. In this case, each agent could converge optimality, i.e., pursue the best response to other agents, which will alleviate the non-stationarity problem. Moreover, the changing opponents will significantly hinder the agent's learning in MAS (Radanovic al., 2019; Lee et al., 2020; Mao et al., 2021). To address this issue, a popular class of RL algorithms focus on limiting the divergence between consecutive policies of the learned policy sequence by imposing direct constraints or regularization terms. These methods are referred to as trust-region-bere based or proximity -assed algorithms (Schulman et al., 2015; 2017; Tomar et al., 2020). However, the precise connection between joint policy divergence and the non-stationarity is still unclear, which motivates to analyze the relationship theoretically. Furthermore, directly adding the trust-region constraint to the joins policy will make the problem intractable. Therefore, effective factorization of the joint policy and trust-region constraint is the key to improve the algorithm's 's efficiency (Oliehoek et al., 2008).
In this paper, we propose novel notion called o-stationarity to measure the stationarity of a given policy sequence. The core of d-stationarity is the opponent switching cost, which is inspired by the local switching cost (Bai al., 2019; Gao al., 2021) that measure the changing behavior of an single-agent RI., and is used to measures the changing of the agent's joint behavior. Furthermore, the relationship where 8-stationarity is bounded by the KI.-divergence of consecutive joint policies is theoretically established. Similar to existing works (Ortner et al., 2020; Cheung et al., 2019; Mao et al., 2021), which use dynamic regret (Jaksch et al., 2010) to measure the optimality of solving non-stationary MDPs algorithms, we can also prove a O(Di/ |0) for each agent. This provides theoretical support impose the trust-region constraint on the joint policy to alleviate the non-stationarity problem. However, directly dealing with the trust-region constraint on the joint policy computationally expensive. The natural idea is decompose the joint policy while imposing trust-region constraints on the factorized policies. However, simple policy factorization like mean-fiell field approximation will lead to sinificant policy divergence, which is considered as the trust-region decomposition dilemma.
dynamic regret bound
To this end, we model the joint policy as a Markov random field and propose trust-region decomposi- tion network (TRD-Nett to adaptively factorize the trust-region of the joint policy and approximately satisfy the ô-stationarity. Local trust-region constraints are imposed on factorized policies, which can be efficiently solved through mirror descent. The TRD-Net constructs the relationship among factorized policies, factorized trust-regions, and the estimated joint policy divergence. To accurately estimate the joint policy divergence, auxiliary task, which borrowes the idea in offline RL to measure the degree of diitrii-tdttiiiiinnn is constructed to train the TRD-Net. The proposed algo- rithm is denoted as Multi-Agent Mirror descent policy optimization with Trust region decomposition, i..., MAMT. MAMT can alleviate the non-stationarity problem and factorize joint trust-region con- straint into trust-region constraints on local policies. which could significantly improve the learning effectiveness and robustness. Our contributions mainly consist of the following: 1) We propose a formal non-stationarity definition of cooperative MARL, 8-stationarity, which derived from the
2

---

Published as a conference paper at ICLR 2022
local switching cost. 6-stationarity is bounded by the joint policy divergence and bounds the dynamic regret of each agent. 2) The novel trust-region decomposition scheme based on message passing and mirror descent could upproximately satisfy the 6-stationarity through computationally efficient way; 3) Our proposed algorithm could bring noticeable and stable performance improvement in multiple cooperative tasks of different complexity than baselines.
THE STATIONARITY OF THE LEARNING PROCEDURE
In our work, consider cooperative multi-agent task that can be modelled by cooperative POSG (Hansen et al., 2004) (I. S, {Ar)== {O,) P,E, {R.]=1) where I represents the n- agent space. S represents the true state of the environment. We consider partially observable settings, where agent i only accessible to a local observation o, E O, according to the emission function {(oi(s). At each timestep, each agent i selects an action a, E क, (a oz). forming a joint action a = (a),-.-. an) E x,i, results in the next state s' according to the transition function P (s' s, a) and reward r; [s, a) and ØR. 0 where i and i' are pair of agents. Intuitively, this means that there is no conflict of interest for any pair of agents.
@R2
To explore and mitigate the non-stationarity cooperative MARI,, we first need to model the non- stationarity explicitly. To emphasize, the non-stationarity is not an intrinsic attribute of cooperative POSG but is additionally introduced when using a specific learning algorithm.
As mentioned above, solving the non-stationarity problem in cooperative MARL can be transformed into solving multiple dynamic non-stationary MDPs, where the non-stationary transition probability Ti and reward function R; is caused by the changing of environment (other agents policies). Switching cost is a standard notion in the literature to measure the changing behavior of an single-agent RL algorithm Diesa-Bianchi al., 2013; Bai et al., 2019; Gao et al., 2021). We consider the following definition of the (local) switching cost from Bai et al. (2019):
Definition 1 (Local switching cost). Let H be the horizon of the MDP and K be the number of episodes that the agent can play. The local switching cost (henceforth also "switching cost") ") between any pair of policies (x, x²) is defined as the number of (h, o) pairs on which at and x' are different:
Dewitch (TT, π²) = ={((h,)) E [H] x :0:0== >0) + [77' (o))
where [H] : I,... H and O are the local observation and observation space. For single- agent RL algorithm that employs policies (x² ( , ,)), its local switching cost is defined as
Nywitch := =EK- K-1
Teawitch (Tx, Tk+1))
In MARL, it needs more attention that the magnitude of the change of other agents' joint policy at each learning step. Thus, we propose the following opponent switching cost to measure the changing behavior of opponents by naturally extending the local switching cost:
Definition 2 (Opponent switching cost). Let H be the horizon of the MDP and K be the number of episodes that the agent can play, that total number of steps T := -K. The opponent switching cost agent i is defined as the maximum Kullback- -Lebber divergence of all (1., o) pairs between any pair of opponents' joint policies (m-i, n'1)) on which m- and n'=; are different:
d'wittch (T ii _., = max((1, o) [T] O: -rs.(Tt
where [7] 1,... T and o, O are the joint observation and observation space.
The larger the changing magnitude of other agents' joint policy is, the larger the opponent switching cost is, and the more serious atasstiionarity problem will be suffered (Radanovic et al., 2019; Lee et al., 2020; Mao et al., 2021). Therefore, opponent switching cost could play effective role to measure the non- staaiontton.... Based on the definition of opponent switching cost, the (non-) noot-nstaionnarity of the learning procedure can be further defined as follows:
Definition 3 (6-stationarity of the learning procedure). For a MAS containing n agents, we have di Pewiieh (m T';)) 8;, then the learning procedure of agent is ōe-stationary. Further, if all agents are b-stationary with corresponding {8.). then the learning procedure of entire multi- agent system is 5 5-stationary with 5 1/ Σ, 6z.
There is a strong relationship between the Definition 3 and the changing of the T,, R, for each agent which is stated by Lemma and Lemma 2:
3

---

Published as a conference paper at ICLR 2022
Lemma 1. If any agent satisfies 5,-stationarity, then the total variation distance of its two consecutive transition probability distribution p ('( a,) and p-+1 as) is bounded by ö, i.e.
Drv (-'(-lo, as)llp*+ a:)) < 2.
Lemma 2. Assume the absolute value of joint reward is less than 1. If any agent i satisfies de- stationarity, then the total variation distance of its two consecutive reward function r' ai) and y (o, a.) is bounded by 5, i.e., DTV (r"(o,
(o,,)) < 2 2. 6.12.
Lemma and Lemma 2 indicate that the 5-stationarity is a reasonable mathematical description of the non-stationarity problem (Hernandez-Leeal et al., 2017; Papoudakis et al., 2019; Padakandla, 2021), which can measure the non-stationarity of the learning procedure. Besides, we find that controlling the 6-stationarity of the learning procedure can obtain tighter (dynamic) regret bound for each agent i, which indicates smaller distance to the set of coarse correlated equilibria (CCE) in finite games (Hannan, 2016; Hart& & Mas-Colell. 2000; Hsieh et al., 2021). Based on the Lemma I and Lemma 2. Theorem states that the (dynamic) regret of each agent i can be bounded by corresponding 5, (the definitions Dmax, B, and B, are shown appendix):
Theorem 1. Consider the learning procedure of MAS satisfies the 6-stationarity and each agent satisfies the o--stationarity. Let H be the horizon and K be the number of episodes, so that to- tal number of steps T HK. In addition, suppose that T 2 B, + 2D Bp >> 0, then O 011/266 dynamic regret bound is attained for each agent i.
However, computing the KL-divergence of the consecutive opponents' joint policies (T',, x still intractable. For a n-agents system, n constraints on the joint policy divergence should be modeled simultancously. Before proposing the algorithm, we still need relax the constraints increase efficiency. Based on the following theorem, the constraints on the opponents' joint policy divergence can be limited by the joint policy divergence of all agents, independent of the agent number.
Theorem 2. For multi-agent system, the maximum KL-divergence of all agents' consecu- tive joint policies (I, TT) is the upper bound of the average opponent switching cost (1/n) Ex=rd (m-S. T's) S max, DKL (T(-)O))[T(((-o)
With the above Theorem 2, it only needs to impose only one trust-region constraint on all agents' joint policy to control the non-stationarity of the entire learning procedure. This allows us to design a MARL algorithm with better effectiveness to approximate the defined 8-stationarity.
THE PROPOSED MAMT METHOD
According Theorem 2, we need properly constrain the maximum divergence of consecutive joint policies to make the learning procedure more stable and efficient. In other words, the algorithm needs to balance between eliminating the non-stationarity (i.e.. 8 - 0) and fast learning (i.c., - oo). To emphasize, based on Definition 3. Theorem I and Theorem 2, we can modify the cooperative MARL formulation by adding stationarity constraint. This problem imposes a constraint that the KL divergence is bounded at every point in the state space. While it is motivated by the theory, this problem is impractical to solve due to the large number constraints. Instead, we can use a heuristic approximation, similar as Schulman et al. (2015), which considers the average KL divergence:
T k+1 E arg max E. (.)(()), Vo, s.t. EODD Basn
[DKL. (T(a o), <a I o])]] s 6, (1)
where π represents the joint policy; o (o), 0j On.) represents the joint observation with n be the agent number. D is the replay buffer. Considering the low sample efficiency of MARL, we did not adapt the fully on-policy learning, but use off off-policy training with a small replay buffer. In this way. it can be ensured that samples are less different from the current policy thereby alleviating the instability caused by off-policy training. Directly imposing a constraint on the joint policy as in (1) will make the problem intractable. A straightforward way is to evenly distribute the trust-region to all agents based on mean-field policy approximation (as shown in Figure in the appendix). However, this will bring up the problem which we call trust-region decomposition dilemma.
3.1 TRUST-REGION DECOMPOSITION DILEMMA
Formally, inspired by Lowe et al. (2017), Foerster et al. (2018b) and Iqbal & Sha (2019), we first introduce the mean-field approximation assumption.
4

---

Published as a conference paper at ICLR 2022
Assumption 1 (Mean-Fiel) Approximation). We use the mean-field variation family π estimate the joint policy of all agents, i.e., π (aao)) = =I[== (t(a))))).
Based on mean-field approximation assumption, the joint policy trust-region constraint can be factorized into trust-region constraints of local policies with the following theorem.
Theorem 3. For any consecutive policies which are belong to mean-field variational family т and n in the policy sequence obtained by any learning algorithm, the KL divergence constraint on joint policy in (1) is equivalent with the following summation constraints of local policies, i.e.,
BogDD [BageR, [Tx((m:(aslos) n. (a=lo:))]] S 8.
(2)
Further the joint summation trust-region constraint (2) can be equivalently decomposed into the following local trust-region constraints, i.e.,
Bo [Bar, [DKI, (Ta((la((s))))) [a:]o:])]]]== S, Vi,
(3)
with Ei_ 6, S 8; ny and o. represent the consecutive local policies of agent i; o, and Us represent the local observation and initial local observation distribution of agent respectively.
Due to the summation constraint term (2), it is still need to jointly train the policies of all agents with limited effectiveness and solvability. Therefore, we further equivalently transform (2) into (3) Based on Theorem 3, problem (I) can be reformulated as
(4) The trust-region decomposition scheme adopted in the above, we called MAMD, is based on the mean-field approximation assumption (i.e., formulation (4)). The similar optimization problem also obtained by Li & He (2020) that try to implement TRPO for MARL through distributed consensus optimization. However, decomposing the trust-region inappropriately will make the algorithm converge to sub-optimal solutions, which can be numerically proved through the following example. By considering a simple MAS with three agents i, k. assume that the agent k is independent with two agents i and j. Then for the multi-agent system, we have pt (o o, a, aj, ax) = lo,a,, ps Pa(o'lo lo, ai, az); Py(e) lo, aj, 0g ag) = Pj(o' o, ajj a:), Ph (o' o0 ak, as a3) = p(o' (o, ax)-
Earg max V,"' (o). Yo, s.t. E.,-D [Eay [KL (It (a: ,,, (a: o.))]] & 6/n,
The change of k's policy cannot affect the state transition probability of j. and vice versa. As a result, the constraints the i,j are "insufficient" but the constraint for i is "excessive", when 8 in (2) is decomposed into three parts equally, which is called trust-region decomposition dilemma? in this paper. Theoretically, the reason for the trust-region decomposition dilemma might be the inaccurate estimation of the joint policy divergence based on the mean-field approximation assumption. The simple summation of local policies' divergence is not equal to the joint policy divergence, while the gap might be enormous. Once the latter cannot be accurately estimated, the non-stationarity cannot be judged accordingly, and imposing constraints on may run counter to our goals.
3.2 THE MAMT ALGORITHM FRAMEWORK
Solving the trust-region decomposition dilemma need to accurately model the relationship between the local policy divergences and the joint policy divergence. However, calculating the joint policy divergence is intractable. MAMT solves this dilemma from another perspective, i.c., directly learning the relationship through the following three steps. First, approximating the joint policy divergence; Then, using differentiable function, i.e., the trust-region decomposition network (TRD-Net), to fit the relationship between the approximated joint policy divergence and local trust-regions; Finally, adaptively adjust local trust regions by optimizing the approximated joint policy divergence. The rest of this section will be organized in three aspects: joint policy divergence approximation, the trust-region decomposition network, and local trust-region optimization.
Joint Policy Divergence Approximation. From the analysis of the trust-region decomposition dilemma, it can be seen that the dependence between agents an essential factor affecting the joint policy divergence. Formally, we use non-negative real number, coordination coefficient, to represent the dependency between two agents². In the learning procedure, the coordination relationship between
"In this case, the number of constraints will increase to n, however the number of constraints will become if the decomposition technique is imposed the n joint policy of the other agents.
We verify the existence of trust-region decomposition dilemma through a typical example in the appendix. IIn this paper, we only model the pairwise relationship.
5

---

Published as a conference paper at ICLR 2022
agents is changing with the learning of policies and completing tasks. Therefore, model the coop- erative relationship between two agents based on counterfactual (Foerster et al., 2018b; Jaques et al., 2019). In Jaques et al. (2019), the causal influence reward of agent w.n.t opponent is calculated by c = Dxt. [p (a) d of) lI (a} o) where p (a' | (4)) Ea; p (al āt o²) p (af of). It can be seen that the greater the causal influence reward, the tighter the coordination between the two agents. However, when calculating the causal influence reward, the agent's policy needs to be modified. That is, the agent needs to explicitly rely on the actions of other agents when making decisions. To solve this problem, we modified the process of calculating the counterfactual baseline in Foerster et al. (2018b) based the idea of Jaques et al. (2019), and obtained a new way of calculating the coordination coefficient
Cr softmax (IQ) (a)))) - 2 o -C--C..
(5)
where Q:(-) is the centralized critic of agent i. a is the joint action of all agents, and ag is the joint action of all agents expect for j; is the threshold to keep sparsity.
According to Theorem 2, Definition 2 and Assumption 1, after modeling the coordination coefficient between agents, does it mean that the weighted summation of the local policy divergence, i.e., 1/n. E, C,,
Ejer [T, (oz) (m (of) can accurately estimate the joint policy divergence? It can be seen from Definition that the agents' policies do not directly cause the non-stationarity. The agent cannot directly observe the opponent's 's policy but only the action sequences. This explicit information directly affects the learning process of the agent and leads to non-stationarity. Therefore, we borrowed the idea in offline RL to measure the degree of -uttt--distribution through the model-based RI. (Kidambi et al., 2020; Yu et al., 2020). Specifically, each agent has a prediction model hag for each other agent j. predicting the other agent's s actions based on its local history observation. The prediction model can naturally replace the old policy x' since it is trained using historical information. Thus the summation of the divergence between the predicted action distribution and the actual action distribution of all other agents could represent the non-stationarity of the agent i, i.e.,
D Inn(nnn Ci,,Ci, (KLTh of (T)) (o))))
where "ns" denotes the "non-stationarity": TTy is the policy of agent which is parameterized by thy: Ims represents the projection function, which constrains Dr to specific range. Kim et al. (2020) also introduces inter-agent action prediction, but Kim et al. (2020) is to promote collaboration, and this paper is to estimate the non-stationarity of the joint policy better. The joint policy divergence can then be approximated by the summation of all local con-saationariiies Dí = =E. Di... i.ms
Trust-Region Decomposition Network. To achieve more reasonable joint policy decomposition, recent works (Böhmer et al., 2020; Qu et al., 2020; Li et al., 2021) modeled the joint policy as a Markov random field with pairwise interactions (shown in the Figure 6 in the appendix) based on graph neural networks (GNN). The joint policy divergence is related to the local policies and local trust-regions. Inspired by these methods, a similar mechanism is utilized in this paper to decompose the joint policy divergence into local policies and local trust regions (which can be input to the GNN) with pairwise interactions. The employed GNN is denoted as Irust-region decomposition nelwork and the network structure is shown in Figure 1. The approximated joint policy divergence Dna can then be used as an surrogate supervision signal to train the trust-region decomposition network. Formally, the loss function to learn the trust-region decomposition network can be formulated as ming Lus = KL, E,Pi,
where 9 and KL, are the parameters and the output of the trust-region decomposition network.
Local Trust-Region Optimization. Based on the approximated joint policy divergence and the trust-region decomposition network, the learning of local trust-region ö, can be formulated by the trade-off between two parts, i.e., the von-stationarity of the learning procedure and the performance of all agents. Formally, the learning objective of 6, is to maximize
( (o) (o)-Ki,, (8)) (o)6:)))
F(6) = EoO EE/
where 8 (6 and π (6) represent the joint policy is related to the 6, of all agents; KI,," m()) denotes the output of the TRD-Net which is parameterized by 6. Finally, the learning of { and e can be modeled as a bilevel optimization problem (Dempe & Zemkoho. 2020)
8* arg max F(5,0
s.t. 0* (*()) = arg min (5,
6

---

Published as a conference paper at ICLR 2022
Input Layer
Lx GNN Layers
Prodiction Layer
The trust-region decomposition network. "MP" denotes message passing. Each agent first encodes of and of and concatenates them with the local trust-region embedding and gets the agent's s embedding (Input Layer). Next, we construct agents as a weighted undirected graph, C. are calculated in advance, and the updated agent's 's embedding is obtained through the GNN Layers. Each agent then obtains another agent's embedding. Finally, we concatenate the two embeddings together and input them into KL-Encoder to estimate the current joint policy divergence (Prediction Layer).
Figure 1:
We can employ the efficient two-timescale gradient descent method to simultaneously perform gradient update for both 5 and 0. Specifically, we have
ok+1 6%- ag F( 0k), 0k+1 + - - Vokns 0x), s.t. 0t.3x 0, (8)
where au - indicates that {0u updates faster than {ōx [8s) In practical, we make ag and 8x 2 equal but perform more gradient descent steps on 0, similar as Fujimoto et al. (2018). At the same time, in order ensure that the updated 0k+1 can meet the constraint, that is, ELA++ < 6, added an additional regular term ReLU(E, 0c,4+1 5) to F(6) during algorithm training.
Algorithm Summary. By directly combing the MAAC (Iqbal & Sha, 2019) and the mirror descent technique in MDPO (Tomar et al., 2020), we can get the algorithm framework for solving problem formulated in Equation (1) after decomposing the trust-region constraint. Each agent has its local policy network Ty., and local critic network Qç, which is similar to MADDPG (Lowe et al., 2017). All critics are centralized updated iteratively by minimizing a joint regression loss function, i.c..
Ceritic(S1, ... Sn) = .
(Q2,))))@[((00))00000 (o. a) - yy)
with y: = - + " (o)) [Qg, (o', a') log( Tw. (a' of)]], and the parameters of the attention module are shared among agents; म represents the joint target policy (similar as target Q-network in DQN) of all agents; Qg. represents the target local critic of agent i. a denotes the temperature
balancing parameter between maximal entropy and rewards.
As for the individual policy updating step, the mirror descent (Tomar et al., 2020) is introduced to deal with the decomposed local trust-region constraints:
V Ve (TTp) = EE-DDarn V log(T (. (a; o:)) (KLW>alWe 1/6, Q5. b(o, ax))
where b(o, (x))) denotes the counterfactual baseline (Foerster al., 2018b); Tygoa represents the policy of agent at last step; 5, is the assigned trust-region range: KL[Wasl = log( (a, log)-lo(TTToo (a; o.)). However, if we only perform a single-step SGD, the resulting gradient would be equivalent to vanilla policy gradient and misses the purpose of enforcing the trust-region constraint. As a result, the policy update at each iteration l involves m SGD steps as
5,6 di 0 -
(++)) + olf + V (TT) -6, Wi = wiT Ui
(m)
For off-policy mirror descent policy optimization, performing multiple SGD steps at each iteration becomes increasingly cone-consuming as the value of m grows, Therefore, similar with Tomar et al. (2020), we resort to staying close to an m step old copy of the current policy while performing a single gradient update at each iteration of the algorithm. This copy is updated every m iterations with the parameters of the current policy. The pseudo-code of MAMT is shown in the Algorithm
EXPERIMENTS
This section aims verify the effectiveness of the trust-region constraints, the existence of the trust-region decomposition dilemma, and the capacity of the TRD-Net with 4 cooperative tasks Spread, Walker, Rover-Tower, Pursuit (more details are in the appendix).
Our algorithm also follows the centralized crities and decentralized actors framework.

---

Published as a conference paper at ICLR 2022
Baselines. The fisrt CCDA algorithm MAD-
Algorithm 1 MAMT
DPG (Lowe et al., 2017) is chosen. Our pro- posed trust-region technique motivates us set the combination of PPO and MADDPG as an- other baseline, MA-PPO (Yu al., 2021). The MAAC (Iqbal & Sha, 2019) which is based on the attention mechanism also considered. MA-PPO's ' policy network also uses an attention mechanism similar to MAAC. LOLA (Foerster
Require: Randomly initialize Jui., Qu and 1: Initialize empty replay buffer D
2: Assign Q₁ + Qu (T Tagia) m..
3:
for 2.... do
4: Collect interaction 7, with Tel
5: Update replay buffer D < (T)
forj=1, 1, do
7:
Sample transitions from
et al., 201 8a) algorithm that models opponent
8:
Compute [C Dinss] with Eq.
agents to solve the non-stationarity problem is compared as the baseline. LOLA is only com- pared the Spread environment due to the poor scalability. MAMD, i.c., MAMT without the TRD-Net, is also considered.
y:
Update 6), with Eq. 8
10:
Update Qc Tv. by Eq. 9. 10
II:
Update target networks Qz, and T..
Update old policy Ryyla
Comparisons. compare MAMT with all baselines and get three conclusions:
Ni-thg
MDND shar))
MAMO Oumi
MAND
MAAD (3mm))
Trai Coleces 2030
(a) Spread.
(b) Multi-Walke
(c) Rover- Tower.
(d) Pursuit.
Figure 2: The performance comparisons under coordination tasks with different complexity.
1). Combine the single-agent trust-region technique with MARL directly cannot bring stable per- formance improvement. The averaged episode rewards of all methods four environments are shown in Figure 2. Directly combining the single-agent trust-region technique with MARL cannot bring stable performance improvement by comparing MAAC and MA-PPO. the Rover- Tower and Pursuit, MA-PPO did not bring noticeable performance improvement; MA-PPO only has a subtle improvement in the simple Spread and even causes performance degradation in Walke.. In contrast, MAMT can bring noticeable and stable performance improvements in all environments. It worth noting that MAMD also shows promising results. This shows that even a simple trust-region decomposition can bring noticeable improvement in simple scenarios. This further verifies the rationality and effectiveness of non-stationarity modeling.
6-16
0,12
0.12
6.15
012
6.0
0.04
200
2001
206
308
42x
2006
0.5
3.5
0.4
1.2
224
1004
203c
324
1204
200c
(a) Spread.
(b) Multi-Walken
(c) Rover-Tower.
(d) Pursuit.
Figure 3: Upper:
The averaged KL divergence of each agent with the orange and green line representing MAAC and MAMT respectively; Bottom: The Dns of all agents.
2). MAMT achieves the trust-region constraint on the local policies and minimizes the non stationarity of the learning procedure. Below we conduct an in-depth analysis of why MAMT can noticeably and stably improve the final performance. MAMT uses an end-to-end approach to adaptively adjust the sizes of the local trust-regions according to the current dependencies between agents to constrain
We combine LOLA with DQN to solve more complex stochastic game.
8

---

Published as a conference paper at ICLR 2022
the KL divergence more accurately. Therefore, analyze MAMT from the two perspectives: the trust-region constraint satisfaction and the non-stationarity satisfaction via surrogate measure. Figure 3 shows the average value of the local KL divergences in different environments. It can be seen from the figure that MAMT controls the policy divergence. The non-stationarity of the learning the surrogate measure Dns to represents the non-stationarity. It can be seen from Figure 3 that as the learning progresses, the non-stationarity gradually decreasing.
procedure is challenging to calculate according the definition,
Agene-3
Agere
Agen03
Ageni3
Aghopi
Agepp
Agenia
4glet2
ceos
(a) Spread.
(b) Multi- Walker.
(c) Rover-Tower.
(d) Pursuit.
Figure 4: Mean and variance of local trust-region of each agent. The y-axis range from 0.01 to 100.0.
Agert
Ageet
06
03-
18
mean
Apellyy
Ager
mann
mean
(a) Spread.
(b) multi-Walker.
(c) Rover-Tower
(d) Pursuit.
Figure 5: Mean and variance of pairwise coordination coefficients. Different colors represent different agents in (a) and (b). In addition, since there are fewer agents in Spread and Multi- Walker, the display effect of the radar chart is poor, so we use the histogram for more precise display in (a) and (b).
3). Trust-region decomposition works better when there are more agents and more complex coordina- tion relationships. Figure 2 shows that MAMT and MAMD have similar performance in the Spread and Walki, but MAMT is noticeably better than MAMD in the Rover-Towel and Pursuit. To analyze separately record the coordination coefficients and the sizes of the trust-regions of the local policies, see Figure 5 and Figure 4. can be seen that the Spread and Multi- Walker are relatively simple, and the number of agents is small. This makes the interdependence between agents is very tight (larger mean) and will not change over time (variance is microscopic). Moreover, the corresponding trust-region sizes are similar coordination coefficients. These figures show that in simple coordination tasks trust-region decomposition is not a severe problem, which leads to the fact that the MAMT cannot bring a noticeable performance improvement. In the other two environments, the dependence between agents is not static (the variance in Figure 5 is more considerable) due to the more significant number of agents and more complex tasks. This also makes the sizes of the trust-regions of the agent's 's local policies fluctuate significantly in different stages (the variance in Figure is more considerable). MAMT alleviates the trust-region decomposition dilemma through the TRD-Net, which brings noticeable and stable performance improvement.
5 CONCLUSION
In this paper, we define the 5-stationarity to explicitly model the stationarity in the learning procedure of the multi-agent system and provide a theoretical basis for proposing an achievable learning algorithm based on joint policy trust-region constraints. To solve the trust-region decomposition dilemma caused by the mean-field approximation and to estimate the joint policy divergence more accurately, we propose an efficient and robust algorithm MAMT combining message passing and mirror descent with the purpose to satisfy 5 5-stationarity. Experiments show that MAMT can bring noticeable and stable performance improvement and more suitable for large-scale scenarios with complex coordination relationships between agents.

---

Published as a conference paper at ICLR 2022
Acknowledgment. This work was supported in part by the National Key Research and Development Program of China (No. 2020AAA0107400), NSFC (No. 12071145), STCSM (No. 192R 191414, No. 20DZ1 100304 and 20DZI 100300), Shanghai Trusted Industry Internet Software Collaborative Innovation Center, and the Fundamental Research Funds for the Central Universities.
Ethics Statement. Our method is not generative model, nor does it involve the training of super- large-scale models. The training data is sampled in the simulated environments, so it does not involve fairness issues. Our method also does not involve model or data stcaling and adversarial attacks.
Reproducibility Statement. The source code of this paper available at https:// anonymous. 4open. wwwenceeeeeeecccccee //MMTT We specify all the training details (e.g., hyperparam- eters, how they were chosen), the error bars (e.g., with respect to the random seed after running experiments multiple times), and the total amount of compute and the type of resource used (e.g., type of GPUs and CPUs) in the Section 4 or the Appendix G. We also cite the creators partial code of our method and mention the license of the assets in the Appendix G.
REFERENCES
Maruan Al-Shedivat, Trapit Bansal, Yura Burda, Ilya Sutskever, Igor Mordatch, and Pieter Abbeel. Continuous adaptation via meta-learning in nonstationary and competitive environments. In ICLR, 2018.
Yu Bai, Tengyang Xie, Nan Jiang, and Yuxiang Wang. Provably efficient q-learning with low switching cost. NeurlPS, 2019.
Bowen Baker, Ingmar Kanitscheider, Todor Markov, Yi Wu, Glenn Powell, Bob McGrew, and Igor Mordatch. Emergent tool use from multi-agent autocurricula. In ICLR, 2019.
Christopher Berner, G. Brockman, Brooke Chan, Vicki Cheung, Przemyslaw Debiak, Christy Denni- son, D. Farhi, Quirin Fischer, Shariq Hashme, Chris Hesse, R. Józefowicz, Scott Gray, C. Olsson, Jakub W. Pachocki, M. Petrov, Henrique Pondé de Oliveira Pinto, Jonathan Raiman, Tim Salimans, Jeremy Schlatter, Schneider, Sidor, Ilya Sutskever, Jie Tang, F. Wolski, and Susan Zhang. Dota with large scale deep reinforcement learning. ArXiv, abs/1912.06680, 2019.
Wendelin Böhmer, Vitaly Kurin, and Shimon Whiteson. Deep coordination graphs. In ICML, 2020.
Nicolo Cesa-Bianchi Bianchian Ofer Dekel, and Ohad Shamir. Online learning with switching costs and other adaptive adversaries. In NeurlPS, 2013.
Wang Chi Cheung, David Simchi-Levi, and Ruihao Zhu. Non-stationary reinforcement learning: The blessing of (more) optimism. Machine Learning eJournal, 2019.
Stephan Dempe and Alain Zemkoho. Bilevel optimization. Springer, 2020.
Jakob Foerster, Richard Y Chen, Maruan Al-Shedivat, Shimon Whiteson, Pieter Abbeel, and Igor Mordatch. Learning with opponent-leaming awareness. In AAMAS, 2018a.
Jakob N Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson. Counterfactual multi-agent policy gradients. In AAAI, 2018b.
Scott Fujimoto. Herke Hoof, and David Meger. Addressing function approximation error in actor- critic methods. In ICML,, 2018
Minbo Gao, Tianle Xie, Simon S Du, and Lin F Yang. A provably efficient algorithm for linear markov decision process with low switching cost. ArXiv preprint 2Xiv:2107.00494 2021.
Jayesh K Gupta, Maxim Egorov, and Mykel Kochenderfer. Cooperative multi-agent control using deep reinforcement learning. In AAMAS, 2017.
James Hannan. Chapter 4. Approximation to rayes risk in repeated play. Contributions to the
Theory of Games (AM-39), Volume III, pp. 97-140. Princeton University Press, 2016.
10

---

Published as a conference paper at ICLR 2022
Sergiu Hart and Andreu Mas-Coleld A simple adaptive procedure leading correlated equilibrium. Econometrica, 68(5):1127-11555) 2000.
Pablo Hemandez-Leall Michael Kaisers, Tim Baarslag, and Enrique Munoz de Cote. A survey of learn- ing in multiagent environments: Dealing with non-stationarity. arXiv preprint (e0.::1777.9910 2017.
Yu-Guan Hsieh, Kimon Antonakopoulos, and Panayotis Mertikopoulos. Adaptive learning in continuous games: Optimal regret bounds and convergence to nash equilibrium. arXiv preprint arXiv:2104. 12761, 2021.
Shariq Iqbal and Fei Sha. 2019.
for multi-agent reinforcement learning. In ICML,
Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11651):1533-160, 2010.
Natasha Jaques, Angeliki Lazaridou, Edward Hughes, Caglar Gulcehre, Pedro Ortega, DJ Strouse, Joel Z Leibo, and Nando De Freitas. Social influence as intrinsic motivation for multi-agent deep reinforcement learning. In ICML, 2019.
Rahul Kidambi, Aravind Rajeswaran, Praneeth Netrapalli, and Thorsten Joachims. MOReL: Model- based offline reinforcement learning. In NeurIPS, 2020.
Woojun Kim, Whiyoung Jung, Myungsik Cho, and Youngchul Sung. A maximum mutual information framework for multi-agent reinforcement learning. arXiv preprint arXiv:2006.02732, 2020.
Chung-wei Lee, Haipeng Luo, Chen- Yu Wei, and Mengxiao Zhang. Linear last-iterate convergence for matrix games and stochastic games. ArXiv, 0as/2006.09511 2020.
Hepeng Li and Haibo He. Multi-agent trust region policy optimization. arXiv preprint arXiv:2010.07916, 2020.
Sheng Li, Jayesh K Gupta, Peter Morales, Ross Allen, and Mykel J Kochenderfer. Deep implicit coordination graphs for multi-agent reinforcement learning. In AAMAS, 2021.
Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, OpenAl Pieter Abbeel, and Igor Mordatch. Multi-agent actor-critic for mixed cooperative-compettiie environments. In NeurIPS, 2017.
Hangyu Mao, Wulong Liu, Jianye Hao, Jun Luo, Dong Li, Zhengchao Zhang, Jun Wang, and Zhen Xiao. Neighborhood cognition consistent multi-agent reinforcement learning. In AAAI, 2020a.
Hangyu Mao, Zhengchao Zhang, Zhen Xiao, Zhibo Gong, and Yan Ni. Learning multi-agent communication with double attentional deep reinforcement learning. Autonomous Agents and Multi-Agent Systems, 34(1):1-33 2020b.
Weichao Mao, Kaiging Zhang, Ruihao Zhu, David Simchi-Levi, and Tamer Başar. Near-optimal model-free reinforcement learning in non-stationary episodic mdps. In ICML, 2021.
Frans A Oliehoek, Matthijs TJ Spaan, and Nikos Vlassis. Optimal and approximate Q-value functions for decentralized POMDPs. Journal of Artificial Intelligence Research, 32:289-353, 2008
Ronald Ortner, Pratik Gajane, and Peter Auer. Variational regret bounds for reinforcement learning. In UAI, 2020.
Sindhu Padakandla. A survey of reinforcement learning algorithms for dynamically varying environ- ments. ACM Computing Surveys (CSUR), 54(6):1-25, 2021.
Georgios Papoudakis, Filippos Christianos, A. Rahman, and Stefano V. Albrecht. Dealing with non-stationarity in multi-agent deep reinforcement learning. ArXiv, abs/1906.04737, 2019.
Chao Qu, Hui Li, Chang Liu, Junwu Xiong, James Zhang, Wei Chu, Yuan Qi, and Le Song. Intention propagation for multi-agent reinforcement learning. arXiv preprint arXiv:2004.088 08883, 2020.
11

---

Published as a conference paper at ICLR 2022
Neil Rabinowitz, Frank Perbet, Francis Song, Chiyuan Zhang, SM Ali Eslami, and Matthew Botvinick. Machine theory of mind. In ICML, 2018.
Goran Radanovic, Rati Devidze, David Parkes, and Adish Singla. Learning to collaborate in markov decision processes. In ICML, 2019.
Roberta Raileanu, Emily Denton, Arthur Szlam, and Rob Fergus. Modeling others using oneself in multi-agent reinforcement learning. In ICML, 2018.
John Schulman, Sergey Levine, Picter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In JCML, 2015.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: 1707.06347, 2017.
Junjie Sheng, Yiqiu Hu, Wenli Zhou, Lei Zhu, Bo Jin, Jun Wang, and Xiangfeng Wang. Learning to schedule multi-numa virtual machines via reinforcement learning. Pattern Recognition, 121: 108254, 2022.
Justin K Terry, Nathaniel Grammel, Ananth Hari, Luis Santos, and Benjamin Black. Revisiting parameter sharing in multi-agent deep reinforcement learning. arXiv preprint arXiv:2005.13625, 2020.
Manan Tomar, Lior Shani, Yonathan Efroni, and Mohammad Ghavamzadeh. Mirror descent policy optimization. arXiv preprint arXiv:2005.090 09814, 2020.
Oriol Vinyals, Babuschkin, W. Czarnecki, Michaël Mathieu, Andrew Dudzik, Chung, D. Choi, R. Powell, Timo Ewalds, P. Georgiev, Junhyuk Oh, Dan Horgan, Manuel Kroiss, Ivo Danihelka, Aja Huang. L. Sifre, Trevor Cai, John Agapiou, Max Jaderberg, A. S. Vezhnevets, Rémi Leblond, Tobias Pohlen, Valentin Dalibard, D. Budden, Yury Sulsky, James Molloy, T. L. Paine, Caglar Gulcehre, Ziyu Wang, T. Pfaff, Yuhuai Wu, Roman Ring, Dani Yogatama, Dario Wünsch, Katrina McKinney, O. Smith, T. Schaul, T. Lillicrap. K. Kavukcuoglu, Demis Hassabis, Chris Apps, and D. Silver. Grandmaster level starcraft ii using multi-agent reinforcement learning. Nature, 575 (7782):350-354, 2019.
Deheng Ye, Guibin Chen, W. Zhang, Sheng Chen, Bo Yuan, B. Liu, J. Chen, Z. Liu, Fuhao Qiu, Hongsheng Yu, Yinyuting Yin, Bei Shi, L. Wang, Tengfei Shi, Qiang Fu, Wei Yang, L. Huang, and Wei Liu. Towards playing full MOBA games with deep reinforcement learning. In NeurIPS, 2020.
Chao Yu, Akash Velu, Eugene Vinitsky, Yu Wang, Alexandre M. Bayen, and Yi Wu. The surprising effectiveness of MAPPO in cooperative, multi-agent games. ArXiv, abs/2103.0195, 2021.
Tianhe Yu, Garrett Thomas, Lantao Yu,, Stefano Ermon, James Zou, Sergey Levine, Chelsea Finn, and Tengyu Ma. MOPO: Model-based offline policy optimization. In NeurlPS, 2020.
Matthieu Zimmer, Claire Glanois, Umer Siddique, and Paul Weng. Learning fair policies in decen- tralized cooperative multi-agent reinforcement learning. In ICML, 2021.
12

---

Published as a conference paper at ICLR 2022
Supplementary Material
Table of Contents
A Preliminaries
14
B Related Works
15
B.1 Tackle Sta-Stationarity in MARL
15
B.2 trust-region Methods
16
C Pseudo-code of MAMT and MAMD
18
D trust-region Decomposition Dilemma
19
E
Proofs
21
E.1 Proof of Lemma
21
E.2 Proof Lemma
................................
21
Proof Theorem
................................
21
E.4 Proof of Thcorem
................................
22
E.5
Proof of Theorem
................................
23
F
More Discussion on the Linear Regret
25
E.
MAMT Is A Near-Sublinear Regret Implementation
25
F2
Future Work to Achieve Sublinear Regret
26
Experimental Details
27
G.1 Environments
27
G.2 Other Details..
27
More Results and Ablation Studies
32
13

---

Published as a conference paper at ICLR 2022
A PRELIMINARIES
Cooperative POSG. POSG (Hansen et al., 2004) denoted as a seven-tuple via the stochastic game (or Markov game)
where n denotes the number of agents; represents the agent space; S represents the finite set of states; A,, Og denote finite action set and a finite observation set of agent I respectively; A Ai x A x ... x An is the finite set of joint actions; P [s, a) denotes the Markovian state transition probability function, where 8, 8 represents the action of agent i; O = Oj x O2 x ... x On is the finite set of joint observations; {(oss is the Markovian observation emission probability function, where represents the local observation of agent i; R2 S x A X S - R denotes the reward function of agent and r; E R. is the reward of agent The game in POSG unfolds over a finite or infinite sequence of stages (or timesteps), where the number of stages is called horizon. In this paper, we consider the finite horizon case. The objective for each agent is to maximize the expected cumulative reward received during the game. For a cooperative POSG, we quote the definition in Song et al. (2020),
represent states of environment and
{ai) 4, A;
[o.)0000 O O
OR 0,
Vi E I, Vi E IVf.), VT E II, VTy E Hg, aR,
where and are a pair of agents in agent space I; n, and Ny are the corresponding policies in the policy space II, and II, respectively. Intuitively, this definition means that there conflict of interest for any pair of agents.
Mirror descent method in RL. The mirror descent method (Beck & Teboulle, 2003) is typical first-order optimization method, which can be considered an extension of the classical proximal gradient method. In order minimize the objective function (xx under a constraint x E C R the basic iterative scheme at iteration k+1 can be written as
k++
arg min (v/ (x*),x x x²) + B (x, x*)
(10)
XEC
where B& (x) x x-) denotes the Bregman divergence associated with a strongly convex function & and 7ht is the step size (or learning rate). Each reinforcement learning problem be formulated optimization problems from two distinct perspectives, i.e.,
()) arg max V*(8), V' E
(11a)
π E arg max Earg [V* [V*(s).
(11b)
Geist al. (2019) and Shani et al. (2020) have utilized the mirror descent scheme (10) and update the policy iteratively as follows
(-19)+ arg max Earr [A=* (s, -g*h KL. (IT, x*); π arg max Hanp, Eawn [A=* (s, a1] -g KL (TT, x²))
where KL(.,) denotes the Bregman divergence corresponding to negative entropy.
14

---

Published as a conference paper at ICLR 2022
B RELATED WORKS
B.1 TACKLE STTATIINNARRTY IN MARL
Many works have been proposed to tackle non-stationarity in MARL. These methods range from using& modification of standard RL training schemes to computing and sharing additional other agents' information.
B.1.1 MODIFICATION OF STANDARD RL TRAINING SCHEMES
One modification of the standard RL training schemes is the centralized critic and decentralized actor (CCDA) architecture. Since the centralized critics can access the information of all other agents during training, the dynamics of the environment remain stable for the agent. Lowe al. (2017) combined DDPG (Lillicrap et al., 2016) with CCDA architecture and proposed MADDPG algorithm. Foerster et al. (2018b) proposed counterfactual baseline in the advantage estimation and used the REINFORCE (Williams, I 1992) algorithm as the backbone in the CCDA architecture. Similar with Lowe al. (2017), Iqbal & Sha (2019) combined SAC (Haarnoja et al., 2018) with CCDA architecture and introduced attention mechanism into the centralized critic design. In addition, Iqbal & Sha (2019) also introduced the counterfactual baseline proposed by Foerster et al. (2018b), CCDA alleviated non-stationarity problems indirectly makes it unstable and ineffective, and our experiments have also verified this. Specifically, on the one hand, the centralized critic does not directly affect the agent's s policy but only influences the update direction of the policy through the gradient. The policy modeling does not take into account the actions of other agents like centralized critics (considering the decisions of other agents in centralized crities is the crucial improvement of this type of algorithm) but only based on local observations. On the other hand, and more importantly, even if centralized crities explicitly consider the actions of other agents, they cannot mitigate the adverse effects of non-stationarity. Centralized critics only consider the sample of other agent's 's policy distribution. Once the other agent's policy change drastically and frequently (corresponding to more severe non-stationarity) they need more samples to "implicit" modeling the outside environment, which leads higher sample complexity.
Another modification to handle non-staie non-stationarrty in MARL is self-play for competitive tasks or population- based training for cooperative tasks (Papoudakis et al., 2019). Tesauro (1995) used self- play to train the ID-Gammon, which managed to win against the human champion in Backgammon. Baker al. (2019) extended self-play to more complex environments with continuous state and action space. Liu et al. (2019) and Jaderberg et al. (2019) combined aopulation-based training with self-play to solve complex team competition tasks, a popular 3D multiplayer first-person video game, Quake III Arena Capture the Flag, and MuJoCo Soccer, respectively. However, such methods require a lot of hardware resources and a well-designed parallelization platform.
B.1.2 COMPUTING AND SHARING ADDITIONAL INFORMATION
In addition to modifying the standard RL training scheme, there are also methods to solve non- stationarity problems by computing and sharing additional information. One naive approach is parameter sharing and use agents' aggregated trajectories to conduct policy optimization every iteration (Gupta et al., 2017: 7: Terry et al., 2020). Unfortunately, this simple approach has significant drawbacks. An obvious demerit that parameter sharing requires that all agents have identical action spaces, i.e., A'' = A', Vi,j j E N, which limits the class of MARL problems to solve. Importantly, enforcing parameter sharing is equivalent to putting a constraint f 0³ Vi,j E N on the joint policy space. In principle, this can lead to a suboptimal solution. To elaborate, we have following proposition proposed by Kuba al. (2021):
Proposition 1 (suhoptimal), Let's 's consider a cooly-cooperativv game with an even number of agents n, one state, and the joint action space {0, 1)",, where the reward is given by r(0"/2 1=/2) r11"/2 0m/2)= 1. and r-) 0 for all other joint actions. Let J be the optimal joint reward, and Jäne be the optimal joint reward under the shared policy constraint. Then
Taune J
2
2
15

---

Published as a conference paper at ICLR 2022
This proposition shows that parameter sharing can lead to suboptimal outcome that is exponentially- worse with the increasing number of agents.
In addition, there are many other ways to share or compute additional information among agents. Foerster et al. (2017) proposed importance sampling corrections to adjust the weight of previous cxpe- rience to the current environment dynamic to stabilize multi-agent experience replay. Raileanu et al. (2018) and Rabinowitz et al. (2018) used additional networks to predict the actions or goals of other agents and input them as additional information into the policy network assist decision-making. Foerster et al. (2018a) 8a) accessed the optimized trajectory of other agents by explicitly predicting the parameter update of other agents when calculating the policy gradient, thereby alleviating the non-stationarity problem. These explicitly considering other agents' information are also called modeling of others. To solve the convergence problem shown by Foerster et al. (2018a) under certain n-player and non-convex games, Letcher et al. (2019) presents Stable Opponent Shaping(SOS). This new method interpolates between Foerster et al. (201 and stable variant named AhokA which is proved that converges locally to equilibria and avoids strict saddles in all differentiable games. Different from Foerster et al. (2018a); Letcher et al. (2019) directly predicting the opponent's s policy parameters, Xie et al. (2020) solves the non-stationary problem by predicting and influencing the latent representation of the opponent's 's policy. Recently, Al-Shedivat et al. (2018) transformed non-stationarity problems into meta-learning problems, and extended MAML (Finn et al., 2017) to MAS to find an initialization policy that can quickly adapt to non-stationarity. However, Al-Shedivat al. (2018) treats other agents as if they are external factors whose learning it cannot affect, and this does not hold in practice for the general multi-agent learning settings, Kim et al. (2021) combines Foerster et al. (2) to consider both an agent's own non-stationary policy dynamics and the non-stationary policy dynamics of other agents in the environment. Due to the unique training mechanism of the above methods, they are difficult to extend to the tasks of more than 2 agents.
B.2 TRUST-REGION METHODS
B.2.1 TRUST-REGION METHODS IN SINGLE-AGENT RL.
trust-region or proximity- -based methods, resonating the fact they make the new policy lie within a trust-region around the old one. Such methods include traditional dynamic programming- based conservative policy iteration (CPI) algorithm (Kakade & Langford, 2002), well deep RL methods, such as trust-region policy optimization (TRPO) (Schulman et al., 2015) and proximal policy optimization (PPO) (Schulman al., 2017). TRPO used line-search to ensure that the KL divergence between the new policy and the old policy is below a certain threshold. PPO is to solve a more relaxed unconstrained optimization problem, in which the ratio of the old and new policy is clipped to specific bound. Wu et al. (2017) (ACKTR) extended the framework of natural policy gradient and proposed optimize both the actor and the critic using cronecker-factrres approximate curvature (K-FAC) with trust-region. Nachum et al. (2018) proposed an off- off-policy trust- region method, Trust-PCI. which introduced relative entropy regularization to maintain optimization stability while exploiting off- off-policy data. Recently, Tomar et al. (2020) used mirror decent to solve relaxed unconstrained optimization problem and achieved strong performance.
B.2.2 TRUST-REGION METHODS IN MARL
Extending trust-region methods to MARL is highly non-trivial. Despite empirical successes, none of them managed to propose a theoretically-jjssifiee trust-region protocol in multi-agent learning. Instead, they tend to impose certain assumptions to enable direct implementations of TRPO/PPO in MARL problems. For example, IPPO (de Witt et al., 2020) assume homogeneity of action spaces for all agents and enforce parameter sharing which is discussed above. Yu al. (2021) proposed MAPPO which enhances IPPO by considering a joint critic function and finer implementation techniques for on-policy methods. Yet, it still suffers similar drawbacks of IPPO. Wen et al. (2021) ) adjusted PPO for MARL by considering a tame-theoretical approach at the meta-game level among agents. Unfortunately, it can only deal with two-agent cases due to the intractability of Nash equilibrium. Hu & Hu (2021) developed NoiSy-MAPPO that targets to address the sub-optimality issue; however, it still lacks theoretical insights for the modification made on MAPPO. Recently, Li & He (2020) tried to implement TRPO for MARL through distributed consensus optimization; however, they enforced the same trust-region for all agents (see their Equation (7)) which, similar to parameter sharing, largely limits the policy space for optimization, and this also will make the algorithm face the
16

---

Published as a conference paper at ICLR 2022
trust-region decomposition dilemma. The method HATRPO (Kuba al., 2021) based on sequential update scheme is proposed from the perspective of monotonic improvement guarantee. But at the same time, sequential update scheme also limit the scalability of the algorithm.
In addition, Jiang Lu (2021) proposes a MARL algorithm to adjust the learning rates of agents adaptively. Limiting the size of the trust-region of each agent's local policy is related to limiting the learning rate of its local policy. They focus on speeding up the learning speed, instead solving non-stationarity problems, However, Jiang & Lu (2021) has no theoretical support, and matching the direction of adjusting the learning rates with the directions of maximizing the Q values may cause overestimation problems.
17

---

Published as a conference paper at ICLR 2022
C PSEUDO-CODE OF MAMT AND MAMD
This section gives the pseudo-code the MAMT algorithm (see Algorithm 2') and the MAMT algorithm without trust-region decomposition network (see Algorithm 3). For convenience, named the latter MAMD. In the MAMD algorithm, the trust-region constraint is equally distributed to the local policies of all agents.
Algorithm 2 MAMT
Require:
Initialize behavior policy Té. and main centralized critic Qs, for each agent i, empty replay buffer D, trust-region decomposition network So and Iw+, local trust-region 89
1: Set target critic Qž equal to main critic
2: Set Te. and Tygla equal behavior policy
3: while not convergence do
4: Observe local observation o and select action a, ~ TT(. o,) for each agent
5: Execute joint action in the environment
6: Observe next local observation o4, local reward r; and local done signal d, of each agent
7:
Store (for), {a,), {o)), {d:}) in replay buffer D
8:
if it's time to update then
9:
for j in range(however many updates) do Sample batch of transitions from D
10:
11:
Compute {C with Eq.
12:
Compute {Di, with Eq.
13:
for slow update do
14:
Update oj with Eq.
15:
for fast update do
Update 9w+ with Eq.
17:
Update centralized critic of all agents by Eq. 9 Update individual policy all agents by Eq. Update target networks Q2, and W.; if it's time to update then
19:
20:
21:
Update old policy woold
Algorithm 3 MAMD
Require:
Initialize behavior policy ny. and main centralized critic QG, for each agent i, empty
replay buffer D
1: Set target critic Qū. equal to main critic
2: Set target policy næ, equal behavior policy
3: Set old policy Ryold equal to behavior policy
4: while not convergence do
5: Observe local observation o; and select action a, TTa o:) for each agent
6: Execute joint action a in the environment
7: Observe next local observation o', local reward r; and local done signal d, each agent
8:
Store (fo:), (a:), {r:), ). {d+}) in replay buffer D
9:
if All d, are terminal then
10:
Reset the environment
it's time to update then
12:
for j in range(however many updates) do Sample batch of transitions from D Update centralized critic of all agents by Eq. 9 Update individual policy of all agents by Eq. 10 Update target networks Q2, and nw. it's time to update then Update old policy goold
13:
14:
15:
16:
17:
18:
'The code is available https: //t/////oonn /awoymooooooosaam//m// wwwp:ymoouuuuu.o..ooooooo sci scwence//eeeeccccooo
18

---

Published as a conference paper at ICLR 2022
D TRUST-REGION DECOMPOSITION DILEMMA
In order verify the existence of the trust-region decomposition dilemma, defined a simple coordination environment. We extend the Spread environment of Section to 3 agents and 3 landmarks, labeled Spread-3. We define different Markov random fields (see Figure 7) of the joint policy by changing the reward function to influence the transition function of each agent indirectly.
al
ag
a
aj
a
a
af
a
a
Figure 6: The probabilistic graphical models of two different modelings of the joint policy. Left: Modeling the joint policy with the mean-field variation family; Right: Modeling the joint policy as pairwise Markov random field. Each node represents the action of agent at timestep t.
4
Figure 7: In the Spread-3 environment, different Markov random fields are generated due the different definitions of the reward function of each agent. Note that these are not all possible Markov random fields, but three typical cases.
Specifically, the reward function of each agent is composed of two parts: the minimum distance between all agents and the landmarks, and the other is the collision. For the leftmost MRF Figure all agents are independent. The reward function of each agent is only related to itself, only related to the minimum distance between itself and specific landmark, and will not collide with other agents. We labeled this situation as Spread-3-Sep. For the middle MRF in Figure 7, the reward function of agent is the same as that of Spread-3-Sep, which only related to itself; but agent and are interdependent. For agent its reward function consists of the minimum distance between i and and the landmark and whether the two collide. The reward function of agent & similar. We labeled this situation Spread-3-Mix. Finally, the rightmost MRF is consistent with the standard environment settings, labeled Spread-3-Ful.
To verify the existence of the trust-region decomposition dilemma, we compare the performance of three different algorithms. First, we select MAAC without any trust-region constraints as the baseline, labeled MAAC. Secondly, we choose MAMD based on mean-field approximation and naive trust-region decomposition as one of the algorithms to be compared, labeled MAMD. Finally, we optimally assign trust-region based on prior knowledge. For Spread-3-S5 --SSpp we do not impose any trust-region constraints, same as MAAC; for Spread-3- 3-Mxx, we only impose equal size constraints on agent and k; and for Spreud-3-Ful we impose equal size constraints on agents, same as MAMD. We labeled these optimally decomposition as MAMD-OP. The performance is shown in Figure 8.
can be seen from the figure that inappropriate decomposition of the trust-region will negatively affect the convergence speed and performance of the algorithm. The optimal decomposition method can make the algorithm performance and convergence speed steadily exceed baselines.
Note that the three algorithms compared here are all based on the MAAC with centralized critics. After we change the reward function of the agent, the information received by these centralized critics has more redundancy in some scenarios (for example, in Spread-3-Sep and Mpre To exclude the algorithm's 's performance from being affected by this redundant information, we output the attention weights in MAAC, shown in Figure 9. can be from the figure that
19

---

Published as a conference paper at ICLR 2022
-10
NACC
15
-25
202
400
600
200
1000
200
100
E00
305
1000
22
30
73
100
123
150
375
200
(a) Spread-3-Sep.
(b) Spread-3-Mix.
(c) Spread-3-Ful
Figure 8: The performance of different trust-region decompositions in different scenarios. These results indicate the existence of trust-region decomposition dilemma.
different algorithms can filter redundant information well, thus eliminating the influence of redundant information on the convergence speed and performance of the algorithm.
1.5
1.0
0.6
0.6
0.6
0.5
0.6
0.8
08
08
08
0.6
0.4
0.4
0.4
0.4
04
0.0
0.0
MAAC in Spread-3-Sep.
(b) MAMD in Spread-3-Sep.
(c) MAMD-OP in Spread-3-Sep.
1.0
0.0
0.5
0.0
0.5
0.5
0.8
68
04
0.
0.5
0.0
0.0
0.5
0.6
0.2
0.2
0.2
0.2
0.2
0.
0.2
022
0.
0.0
0.0
0.0
0.0
0.0
5.0
(d) MAAC in Spread-3-Mix.
(c) MAMD Spread-3-Mix.
(f) MAMD-OP in Spread-3-Mix.
Figure 9: The attention weights of the different agents of different trust-region decomposition in different scenarios. These results indicate the existence a trust-region decomposition dilemma.
20

---

Published as a conference paper at ICLR 2022
E PROOFS
E.
PROOF OF LEMMA
Proof.
Piv(e'(1o,aa) (
max Ip (.1, - a1))
o.a:
f p(-10,a) (T - (a_:)0) ===((_-)))) da
max
0,8;
max (a=t (a= da max - (0) =
I 2ln2 max D DLL (T' (o) (0)) - 2ln 6//2
E.2
PROOF OF LEMMA 2
Proof.
Drv(r' (o, max lr+ (0,a;) - -r(oa
0,8;
r(o,a) (F (a_:lo) - x² (a)(o_)))) da
max
max o
x=م(a_م0)) da=;
(o) =
max
< 2 In max K2 (o) (o))
< 2 2- 2 1/2
E.3 PROOF OF THEOREM
Proof. In this paper, model the learning procedure of each agent in multi-agent system dy- namic non-stationary MDP. From each agent's perspective, the quantities ra rx a;)'s and p-(-lo, a;)'s of each agent vary across different I's in general. Following Besbes al. (2014), Cheung al. (2019) and Mao et al. (2021), we quantify the variations on (o ((),,:))' and pr(-lo, a;''s 'ss in terms of their respective variation budgets B,, Bp (> 0):
B,
Brd where Brg = max [rt+( - r, oEO,a,E:
T-1 Bp = Σ By... where Bp.t max ||pt+((- o, o, pr( 0, (=1
oEO.aEA
To measure the convergence to the best-response from each agent's perspective, we consider an objective of minimizing the dynamic regrel (Jaksch et al., 2010; Besbes et al., 2014; Cheung et al., 2019; Mao et al., 2021)
Dyn- Regr (II) = Σ (pi E [r (o,, a.)]
In the oracle ΣT= P. the summand & is the optimal long term average reward of the stationary MDP, i.e., other agents follow the fixed optimal policies, with state transition distribution Pi, and mean reward ri,t- Below we give definition and assumption.
21

---

Published as a conference paper at ICLR 2022
Definition 4 (Communicating MDPs and Diameter). Consider set of states S, collection A {Aa) Jes of action sets, and a state transition distribution p = {p(- s, s.a)).ES.aE.. For any s' E S and stationary policy TT, the hitting time from to s' under is the random variable (s' π., == min (t: 8141 = 8', 81 = 8, 8741 ~ p( 8 (s+)) VT), which can be infinite. We say that is communicating MDP iff D quantity D is the diameter (Jaksch et al., 2010) associated with A,A.)).
se statioay EE [A (s' [T, ) is finite. The
Assumption 2 (Bounded Diameters). For each t [T', the tuple (S,A, A, pt) constitutes a communicat- ing MDP with diameter at most Dr. We denote the maximum diameter as Dmaa (1.....)) Dr-
Then have following proposition (Cheung et al., 2019) from each agent's perspective:
Proposition 2. Consider an instance (S,A,T.p. p.r) from each agent's 's perspective that satisfies Assumption 2 with maximum diameter Daax and has variation budgets Br, Bp for rewards and transition distributions respectively. In addition, suppose that T 2 B, + 2D Bp > 0, then it holds that
T E 1=1
T Σ
-
ra (st at) (Dmax + 1) V (B, + 2D max By) T.
max TI
The maximum is taken over all anticiiicipatory policies II's. We denote {(T) a ) as the trajectory under policy II, where af E A, is determined based on II and H4-1 1 (8 and 8441 Pt (: st, aa") for each I.
The proof of Proposition 2 is shown in (Cheung et al., 2019). Based on Lemma and Lemaa 2, we easily obtain B, < 21n 6//22 T and Bp S 21n 0//2 T |O|. Then have following corollary:
Corollary 1. Consider instance (S,A, from each agent's perspective that satisfies As- sumption with maximum diameter Dmax and has variation budgets Br. Bp for rewards and transition distributions respectively. In addition, suppose that T 2 B, 222 Dmmax By > 0, then holds that
Σ pi
max E
Σ
(of (+,, atf
-4(mmax +1) TV (1 + D (0)) In 2- 2////2
According to the Definition 4, Theorem is proved.
E.4 PROOF THEOREM
Proof.
1 -1= / al0)) x(a;, (0))
KL T
da,da
T'(a, |
/ n () r'(aaa_i, () da
o)
/ T(alaa x'(asla=;,0)
=(a.la.,,0) da;da_;
(a)
7 <(a o) T'(a-10)
da
/ 70  ['aaaa=,,
a(a(a_i,0)
da;da=; KT, [ m'_]]
/ [(0 KL M== [
2 KL. [ mL.]-
22

---

Published as a conference paper at ICLR 2022
So we have KL x²] 2 Σ KL [T-6 m-1]-- Take the maximum value both sides of the inequality, Theorem 2 proved.
Since similar conclusion is reached in Li & He (2020), will make brief comparison with it here. Theorem establishes the relationship between the maximum Kl.-divergence of the consecutive joint policies of all agents and the maximum KL-divergence of the consecutive joint policies of other agents. It establishes the theoretical connection between the KL-divergence of the consecutive joint policies of all agents and environmental statiiotton.. The Equation (8) of Li & He (2020) extends the KL divergence constraint of the TRPO algorithm to the multi-agent scenario and establishes the connection between the divergence of the joint policy of all agents and the divergence of local policy of each agent.
E.5 PROOF OF THEOREM 3
Proof.
Eas (T,(T(-1)), T (+10)] <8
TT(10) log T--10) da <
Boww
(+)))
n (:10) log
Bown
(-|00)
da <8
(+1a))
(1;()):) da
Eorn
π T-110)
<
(-(o))
n
(-1o0) da
Bonn
(T-11) log
π. ((:):))
/
(-10) dado
ulo)
TT-10) log
<.
क. (-lo:))
We first simplify the integral term of the inner layer
T(-l0) log T+(+)0;) da (-(()1o:)
(-(0)) day
Trr(-oo (10s) log
T (-lo))
xa:
/
(1o())
Ti(-lox) log
Tir(la))day das
(-(0)) aa
(-(0): das = KL (T(() (-1o:))
T. (T(-lo:) log
+ (-1o:))
Jaz
We replace the original formula with the simplified one
Σ u(o) / T T-110) log (-100) dado <8 x.. (-1o:)
(m:(
~ (-10z)) do <8
((o)o(o))do <8.
23

---

Published as a conference paper at ICLR 2022
where we denote KL ( o. (-lo.) as 6(0,). For the outer integral term, we have
m(0)6(o,)do
/ m(a))(o))))
/ mlawdady do;
p(o,)0(o))do
Rora: [8(0:)].
Overall, we have
Bonn (T) <
u(o) /. (T-10) log :T(-1o;) dado < (-1o,)
u(o))(o,)do <8
Eacoy [6(a;)] <
E Barw (+lo))] <8.
24

---

Published as a conference paper at ICLR 2022
F MORE DISCUSSION ON THE LINEAR REGRET
The bound on Theorem has linear dependence the number of time intervals T HK. Therefore, the average regret doesn't 't vanish to zero as T becomes large, even when small non- stationarity. But from the experimental results, algorithm has faster convergence speed and better performance than baselines. Therefore, the rest of this section will expand from the following two aspects. First, although theoretically only linear regret be achieved, it can be close to sub- linear in actual implementation; second, we can achieve theoretical and implementation sub-linearity through some improvements that will bring higher computational load.
F.1
MAMT IS A NEAR- SARR-SULLNNEAR REGRET IMPLEMENTATION
Setting
Algorithm
Regret
Jaksch et al. (2010)
Ö(S A Ti)
Undis- counted
Gajane al. (2018)
Ab D3r3)
Ortner et al. (2020)
Ö(S A T
Cheung et al. (2019)
As T
Domingues et al. (2021)
Ö(s H
Episodic
(Mao al., 2021)
Ab T
(Mao et al., 2021)
#
Table 1: Dynamic regret comparisons for single-agent RL in non-stationary MDPs. S and A the numbers states and actions, is the number of abrupt changes, B, + Bp. D is the maximum diameter, H is the number of steps per episode, and T is the total number of steps. O(-) suppresses logarithmic terms.
First, we explain why controlling the d-stationarity can only achieve linear regret. Table lists the sublinear regret bounds that current SOTA algorithms solve the single-agent non-stationarity problem can reach. is worth noting that these single-agent algorithms cannot modify A because this is the intrinsic property of the external environment. But our method, the environment is made up of other agents' policies, so A can be adjusted. As can be seen from the table, the power of A (B, + Bp) and T add up to And from the proof of Theorem 1, B, and B, are both the summation over T, i.e., B, = ΣT= BY and B, = ='= By However, opponent switching cost considers the maximum value of the continuous policy divergence in the entire learning procedure, so we have
T
T
A ATTI-o = (Br + Bp)
BT)aT1-o
BC
B
1=1
8, + Σ 6, 11- IT
where 0 < < 1/3. In general, constraining 5-stationarity produces linear regret because the opponent switching cost is relatively loose constraint. The key to achieving sub-linear regret is to constrain the consecutive joint policy divergence at each timestep, not the maximum expected value of the entire learning procedure. Therefore, we propose tighter constraint based on opponent switching cost, and prove that by imposing this constraint on the consecutive joint policy divergence, the algorithm can achieve sub-linear regret Ō(Di/2 //////////////////////////////// First, we define the temporal opponent switching cost.
Definition 5 (Temporal opponent switching cost). Let H be the horizon of the MDP and K be the number of episodes that the agent can play, so that total number of steps T HK. The temporal opponent switching cost of agent i is defined the Kullback-Leible divergence (over the joint
25

---

Published as a conference paper at ICLR 2022
Table 2:
The proportion of the timesteps that the MAMT meets the condition of a<b the total timesteps in the training procedure of different cooperative tasks.
Spread
Multi-Walker Rover- Tower
Pursuit
95.
90.16%
83.76%
85.88%
observation space O at specific timestep t) between any pair of opponents' joint policies (T- T'i)) on which - and n²=; are different:
d swizch (T- :.a.)
= max for DRL (NLn(O) [=.11) (
where o, O are the joint observation and observation space and T.
Correspondingly, we can also define temporal o'-stationarity.
Definition (Temporal -'-stationarity). For a MAS containing n. agents, if we have drwitch ( S 6%, then the learning procedure of agent i is 81-stationary at timestep t. Fur- ther, if all agents are d-stationary with corresponding { then the learning procedure of entire multi-agent system 8' -taattiiny with
Σ, 5%
Similarly, we can also get Lemma I and Lemma 2 about temporal o'-stationarity. Since the content similar, we won't 't repeat them here. Then have B, 2 2n Ei=10 and B₁ S In Ea 0/1/22 10). In addition, denote, B3 1T=1" 8: With these definitions and lemmas, can get the following theorem.
Theorem 4. Let H be the horizon and K be the number of episodes, so that total number of steps T HK. Consider the learning procedure of a MAS satisfies the 8' -Sstttiionarity and each agent addition, suppose that T 2 B,+2D max B, > O, 1/2 /2/p//2)) sublinear dynamic regret bound is attained for each agent
satisfies the 8% -/-ttition at each timestep
then ÖD max /1 B3
The proof is similar to Theorem Theorem shows that if want to achieve sub-linear regret, need to constrain the consecutive joint policy divergence at each timestep instead of only constraining the maximum value of the policy divergence. Looking back at the implementation of the MAMT, although the algorithm has a global hyperparameter to constrain the adaptively adjusted {6: L 1=11 the constraint only works when Σ. 6 > ö. We have observed in the experiment that most of the time Σ, 5g I 5 (see Table 2). In this way, a different 8 = Σ; 5f at each timestep / constrain the consecutive joint policy divergence, thereby approximately achieving a sub-linear regret.
F.2 FUTURE WORK TO ACHIEVE SUBLINEAR REGRET
Again, Theorem 4 shows that if we want to achieve sub-linear regret, we need to constrain the consecutive joint policy divergence at each timestep. This means that we need to set a hyperparameter 8' at every timestep to constrain the consecutive joint policy divergence, and manual adjustment will bring an extremely complicated workload.
A more realistic way is to treat the 5' of each timestep formulate it as a dual variable about delta, and the policy parameter vff. Then the dual gradient descent can be used optimize 8¹, similar to the adaptive reward scale learning in the soft-actor-critic (SAC, Haarnoja et al. (2018)) algorithm. In addition, non-parameter optimization methods, such as evolutionary methods, it will bring a higher computational load. How to balance the computational load and algorithm performance, we leave it to the future explore.
additional optimization variable and
also be used adjust the 8'. But matter which technique is adopted,
26

---

Published as a conference paper at ICLR 2022
G EXPERIMENTAL DETAILS
G.1 ENVIRONMENTS
(8)
(b)
(d)
Figure 10: Coordination environments with increasing complexity.(a) Spread; (b) Multi-Walker; (c)
Rover-tower; (d) Pursuit.
Spread. This environment (Lowe et al., 2017) has 2 agents. landmarks. Each agent is globally rewarded based on how far the closest agent is to each landmark (sum of the minimum distances). Locally, the agents are penalized if they collide with other agents (-1 for each collision).
Multi- Walker. In this environment (Terry et al., 2020a), bipedal robots attempt to carry a package as far right as possible. A package placed on top of bipedal robots. A positive reward awarded to each walker, which is the change in the package distance.
Rover-Tower. This environment (Iqbal & Sha, 2019) involves agents, 4 of which are "rovers" and another 4 which are "towers". In each episode, rovers and towers randomly paired. The pair is negatively rewarded by the distance of the rover to its goal. The rovers are unable to see in their surroundings and must rely communication from the towers, sending one of 5 discrete messages. Pursuit. 30 blue evaders and red pursuer agents are placed in a grid with an obstacle. The evaders move randomly, and the pursuers are controlled (Terry al., 2020a). Every time the pursuers surround an evader, each of the surrounding agents receives reward of 5, and the evader is removed from the environment. Pursuers also receive a reward of 0.01 every time they touch an evader.
G.2 OTHER DETAILS
Random seeds. All experiments line) and std dev (shaded) performance over random seed throughout training.
for 8 random seeds each. Graphs show the average (solid
Performance metric. Performance for the on-policy (MA-PPO) algorithms is measured as the average reward across the batch collected at each epoch. Performance for the off-policy algorithms (MAMT, MAMD, LOLA, MADDPG, and MAAC) is measured by running the deterministie policy (or, in the case of SAC, the mean policy) without action noise for 10 trajectories and reporting the average reward over those test trajectories.
Network Architecture. Figure 11 shows the detailed parameters of the three main networks in the MAMT algorithm.
Hyperparaaetees. Table shows the default configuration used for all the experiments of our methods (MAMD and MAMT) and baselines in this paper. We do fine-tune the hyperparameters of baselines and use the default setting as same as original papers, see Table 4,5,6 and 7. The hyperparameter fine-tune range of our methods are shown in Table 8 and Considering the long training time of the MARL algorithm, we did not train all hyperparameter combinations to the pre- defined maximum number of episodes for MAMT. We first train all hyperparameter combinations to one-sixth of the maximum number of episodes and select the top-sixth hyperparameter combinations with the best performance (defined in Performance metric.). Then we train the selected one-sixth combination to one-third of the maximum number of episodes and select the best- rest-performing one- sixth combination. Finally, we train the remaining combinations to the maximum number episodes and select the best hyperparameter combination.
27

---

Published as a conference paper at ICLR 2022
Table 3: Default settings of our methods used in experiments.
Name
Default value
num parallel envs
12
step size num epochs per step steps per update
from 10, 000 to 50, 000
4
100
buffer size
1,000,000
batch size
1024
batch handling
Shuffle transitions
num critic attention heads
4
value loss
MSR
modeling policy loss
CrossEntropyLoss
discount
0.99
optimizer
Adam
adam lr adam mom adam eps
le-3
0.9
le-7
Ir decay
0.0
policy zegularization type
L2
policy zegularization coefficient
0.001
modeling policy regularization type
1,2
modeling policy regularization coefficient
0.001
critic regularization type
L,
critic regularization coefficient critic clip grad policy clip grad
1.0
10 * num of agents
0.5
soft reward scale
100
modeling policy clip grad
0.5
trust-region decomposits trust-region clip
network clip grad
10 * num of agents
from 0.01 to 100
num of iteration delay in mirror descent
100
tsallis q in mirror descent 8 in coordination coefficient
0.2
0.2
Leaks
Softmos
FC-128
FC- PC-J22
ON
Fc
120
FC.39
LoakyReU
BN
LcakyRell
RC-220
Lcakygeel
FC-128
LeakySeeU
BN
FC-128
FC-30
Inoure
BN
PC-128
Leaky/Bal
FC -2-228
LoakyRauu
GKN
Fc :28
3-128
FC-S2
FC-128
FC 22:39
FC-128
LeskyPall
FC-128
LaskyPall
BN
Figure 11: The actor-network (and modeling policy) architecture, critic- network architecture, and trust-region decomposition network architecture from left to right and from top to bottom.
Hardware. The hardware used in the experiment is server with 128G memory and 4 NVIDIA 1080Ti graphics cards with 11G video memory.
The Code of Baselines. The code and license of baselines shown in following list:
28

---

Published as a conference paper at ICLR 2022
Table 4: Default settings of MAAC used in experiments.
Name
Default value
num parallel envs
12
step size num epochs per step steps per update
from 10, 000 to 50, 000
100
buffer size
1,000,000
batch size
1024
batch handling
Shuffle transitions
num critic attention heads
value loss
MSE
discount optimizer adam ir adam mom
0.99
Adam
le-3
0.9
adam eps
1e-7
Ir decay
0.0
policy regularization type
L.
policy zeqularization coefficient
0.001
critic zeqularization type
L2
critic regularization coefficient. critic clip grad policy clip grad soft reward scale
1.0
10 num of agents
0.5
100
Table 5: Default settings of MADDPG used in experiments.
Name
Default value
num parallel envs
12
step size num epochs per step steps per update
from 10, to 50, 000
100
buffer size
1,000,000
batch size
1024
batch handling
Shuffle transitions
value loss discount optimizer adam ir adam mom adam eps
MSE
0.99
Adam
lc-3
0.9
1e-7
Ir decay
0.0
policy regularization type
policy regularization coefficient critic regularization type
0.001
critic reqularization coefficient critic clip grad policy clip grad
1.0
10 * num of agents
0.5
MADDPG (Lowe et al., 2017): http:://ggtaab..ccomm/ssrrrggggg maddpg-pytorch, MIT License;
MAAC (Iqbal & Sha, 2019): httpe://gtthbbbooo////aaaagg////
MIT License:
MA-PPO: https: httppp///ggttto...ccmmooyyccchpp MIT License;
29

---

Published as a conference paper at ICLR 2022
Table 6: Default settings of MAPPO used in experiments.
Name
Default value
num parallel envs
12
step size
from 10, 000 to 50, 000
batch size
4096
critic attention heads
value loss
Huber Loss
Huber delta
10.0
GAE lambda
0.95
discount
0.99
optimizer
Adam
adam Ir adam mom
le-3
0.9
adam eps
lc-7
ir decay
0.0
policy regularization type
policy regularization coefficient
0.0
critic regularization type
L.
critic reqularization coefficient critic clip grad
0.0
10
policy clip grad
10
use reward normalization
TRUE
feature normalization
TRUE
Table 7: Default settings of LOLA(+DON) used in experiments.
Name
Default value
num parallel envs
12
step size
from 000 to 50, 000
num epochs per step steps per update
100
buffer size
1,000,000
batch size
1024
batch handling
Shuffle transitions
value loss discount optimizer adam ir adam mom adam eps Ir decay reqularization type
MSE
0.99
Adam
le-3
0.9
le-7
0.0
L2
regularization coefficient clip grad
1.0
10 * of agents
LOLA (Foerster et al., 20) and https: //t:://gitttt com/ com/geek-all /MAgent, MIT License.
Learning curves are smoothed by averaging over a window of 11 epochs. Source code is available at https: / anonymous. 4open. science/ \/MMMT.
30

---

Published as a conference paper at ICLR 2022
Table 8: Tuning ranges of key hyperparameters of MAMD in experiments.
Name
Range
num epochs per step
{1, 4, {0.0003, 0.001
adam ir
soft reward scale
{10, 100)
num of iteration delay in mirror descent
{100, 1000)
Table 9: Tuning ranges of key hyperparameters MAMT in experiments.
Name
Range
num epochs per step
{1, 4, 8)
adam 1r
(0.0003, 0.001
soft reward scale
{10, 100)
trust-region clip
(0.01, 1, 100)
num of iteration delay in mirror descent
{100. 1000)
8 in coordination coefficient
{0.002, 0.02, 0.2)
31

---

Published as a conference paper at ICLR 2022
H MORE RESULTS AND ABLATION STUDIES
Figure 13 to Figure 23 show the performance indicators of all agents in 4 environments under different random seeds. In addition, we have also conducted additional ablation studies to analyze the importance of different modules MAMT. These modules mainly include mirror descent, coordination coefficients, and modeling of others.
Regarding the mirror descent. Considering the low sample efficiency of MARL, we did not adopt the fully on-policy learning but used off-policy training with small replay buffer. In this way, it can be ensured that samples are less different from the current policy, thereby alleviating the instability caused by off-policy training. The methods such as TRPO and PPO are all on-policy algorithms. Although there are some off- off-policy trust-region methods, such as Trust-PCL, etc., they are all more complicated. To this end, adopted method of MAMT. MAMT can also use the on-policy method as the backbone, such as PPO. To this end, we have added a comparative experiment, replacing Mirror Descent with the PPO algorithm (MAMT-PPO).
concise technique, Mirror Descent, the optimization
Regarding the coordination coefficients. In the MAMT algorithm, the counterfactual baseline is used in policy learning and used in the calculation of coordination coefficients. To verify the relationship between the correctness of the modeling of the dependencies between agents and the algorithm's performance, we have added two comparative experiments to the revised version. Specifically, we used two pre-defined ways to set the coordination coefficients, set to fixed value (MAMT-Fixed) of 1/(n 1) (where n is the number of agents), and random sampling (MAMT- Random, random sampling from the range of (0, 1) and then input into the softmax function).
Regarding the modeling of others. We borrowed the idea in offline RL to measure the degree of outtof-distribution (see Equation (5)) through the model-based RL to reasonably characterize the non- stationarity or the consecutive joint policy divergence. However, more intuitive and simple method is to directly perform a weighted summation of the consecutive local policy divergence (the weights are the coordination coefficients). The reason why we did not adopt this scheme is based on the following considerations. can be seen from Definition that the agents' policies do not directly cause the non- stationarity. The agent cannot directly observe the opponent's policy but only the action sequences. This explicit information directly affects the learning process of the agent and leads to non-stationarity. To verify the correctness of the idea, we also did additional comparative experiments. Specifically, changed the calculation method of coordination coefficient to the weighted summation consecutive local policy divergence (MAMT-WS), i.e. 1/n. >. Ejjs KL[T's, (o)))[=T,((0)
Table 10: The average return of baselines and ablation algorithms in the last 1, 000 episodes of the training stage. The red part represents the newly added experiment results. The numbers in parentheses indicate the standard deviations under 5 (the red part is 3) different random seeds. MAMT-Random stands for randomly setting the coordination coefficients in MAMT, MAMMT-Fixed stands for setting the coordination coefficients in MAMT to a fixed value of 1/(n 1). MAMT-WS stands for using the weighted sum of the local policy divergence approximate the joint policy divergence, and MAMT-PPO represents the replacement of the off-policy mirror descent algorithm in MAMT with the on-policy PPO algorithm.
Baselines
Environments
MAAC
MA-PPO
MADDPG
LOLA
MAMT -38.06( 09)
Spread
-3..23(10.70)
42.29(10.61)
43.33(13.68)
12.08(11.20)
Multi- Walker
-30.16( +.338)
08..2((+4.22
49.76( 87.46(46.50)
-4.70 145.95(+5..7)
Rover-Tower
121.79(=6.84)
120.36(=6.02)
Pursuit
19.86(11.19)
20.05(11.20)
5.05(11.33)
25.62(+11.30)
Ablation Studies
Environments
MAMD
MAMT-Random
MAMT-Fixed
MAMT-WS
MAMT-PPO
Spread
42.17((11.05)
43.04(10.88)
-1.72
-39.83(10.72)
(00.4)
Multi-Walker
-4.92(+3.91)
-30.52 +3.17)
-4.82(43..14
-4.90(44.86) 6..
-4.98(+4.05)
Rover-Tower
127.80(=5.04)
115.11(26..3)
123.21(-5.87)
(55.3)
Pursuit
22.30(+1.81)
16.48 +1.33)
21.54(+1.62)
17.17(+2.89)
25.04
We compared the above ablation algorithms under 4 cooperative tasks, and the experimental results shown in Table 10. The following points can be seen from the Table 10. First of all, from the
32

---

Published as a conference paper at ICLR 2022
4
3.5
2.5
2
1.5
0.5
0
Spread
Multi-Walker
Rover-Tower
Pursuit
MAMT PPO
3.78
2.05
2.43
1.56
MAMT
MAMT-PPO
Figure 12: The proportional relationship between the number of episodes experienced by the MAMT and MAMT-PPO algorithms when they achieve the results in Table 10.
comparison results of MAMT-PPO and MAMT, it can be seen that our method is not significantly affected by the optimization method of the policy learning, and both achieve the best results on the four cooperative tasks. However, MAMT-PPO is on-policy method, which makes its sample effectiveness lower than MAMT. In Figure 12, we have made statistics on the number of episodes required by the two to achieve the performance in Table 10. It can be seen from the table that MAMT only needs about half of the data to achieve the same performance as MAMT-PPO.
Secondly, from the results of MAMT-Rame Random and MAMT-Fixed the coordination coefficient is significant to the algorithm's 's performance, which also consistent with the theoretical analysis of the trust-region decomposition dilemma in the main body. Here have observed interesting phenomena. First, we found that randomizing the coordination coefficient will seriously affect the performance of MAMT. The possible reason is that the wrong trust-region constraint the local policy will hinder the agent's s learning. Second, we found that setting the coordination coefficient to the same fixed value will make the performance of the MAMT algorithm approach that of MAMD. This shows that the TRD-Net fits the relationship between the local trust regions and the approximated consecutive joint policy divergence well.
Third, it can be seen from the results of MAMT-WS that the effect of approximating the KL divergence of consecutive joint policies by using the weighted summation of the KL divergence of consecutive local policy policies is very unstable. In all cooperative tasks, MAMT-WS WS has greater variance. In simple tasks, such as Spread (2-agents) and Multi- Walker (3-agents), MAMT-WS can have an effect close to MAMT. But once the difficulty of the task increases, the effect of MAMT-WS will even be the same level as MAMT-Random. We believe that the main reason for this instability is that the agent will cause rapid changes in local policies due exploration in the early stages of learning.
33

---

Published as a conference paper at ICLR 2022
Age
Tean
(a) Agent 1.
(b) Agent
(c) Agent 5.
(d) Agent
Team
Agend
Agent'
(e) Agent 2.
(1) Agent 4.
Agent 6. gg)
(h) Agent
Figure 13: The mean and variance of coordination coefficient of each agent in Gover-Tower environ- ment.
Apedd
Agendo
maah
TA0
7887
(a) Agent 1.
(b) Agent
(c) Agent 5.
(d) Agent
(e) Agent 2.
(1 Agent 4.
gg) Agent 6.
(h) Agent 8.
Figure 14: The mean and variance of coordination coefficient of each agent in Pursuit environment.
0.5
0.8
0.0
0.0
0.6
0.6
0.5
0.5
0.4
0.4
0.0
0.0
1,0
mean
variance
1.0
mean
variance
0.2
0.2
0.5
0.5
0.0
0.0
mean
variance
mean
variance
mean
variance
mean
variance
(a) Spread environment.
(b) Multi-Walker environment.
Figure 15: The mean and variance of coordination coefficient of each agent in Spread environment and Multi- Walker environment. Different color represents different agent.
34

---

Published as a conference paper at ICLR 2022
600
604
6.4
004
200
200
40c
624
536
200
200
424
400
536
(a) Seed 1.
(b) Sced 2.
(c) Seed 3.
(d) Seed 4.
0.17
624
(e) Seed 5.
(1) Seed 6.
(g) Seed 7.
(h) Seed 8,
Figure 16: The averaged KL-divergence of each agent in Rover-Tower environments. Red line represents MAAC and green line represents MAMT.
8:16
8:12
6:15
6-15
015
Emm
D17
2006
2004
1008
2004
220
1008
2004
424
2204
5000
2002
(a) Seed 1.
(b) Sced 2.
(c) Seed 3.
(d) Seed 4.
0.10
1:15
1115
0:15
0.0
6:05
0.05
1ick
J004
-200
190h
2004
2004
200L
(e) Seed 5.
(1) Seed 6.
(g) Seed 7.
(h) Seed 8.
Figure 17: The averaged KL-divergence of each agent in Pursuit environments. Red line represents MAAC and green line represents MAMT.
0.12
090
066
2206
2006
2006
430
32224
2006
123k
1500
2008
(a) Seed 1.
(b) Seed 2.
(c) Seed 3.
Figure 18: The averaged KL-divergence of each agent in Walker environments. Red line represents MAAC and green line represents MAMT.
615
015
200
42c
53c
320
200
42c
53c
33c
200
48c
53c
(a) Seed 1.
(b) Seed 2.
(c) Seed 3.
Figure 19: The averaged Kl-divergence each agent Spread environments, Red line represents MAAC and green line represents MAMT.
35

---

Published as a conference paper at ICLR 2022
015
0.5
07
Scod
(b) Seed
Seed
(d) Seed
0.5
02
0.2
(e) Seed
(1) Seed
(g)
Seed
(h) Seed
Figure 20: The averaged KL of each agent in Rover- Tower environments.
Seed
(b) Seed
Seed 3.
(d) Seed
0.5
0.2
(e) Seed
(1) Seed
(g) Seed
(h) Seed
Figure 21: The averaged KL of each agent Pursuit environments.
(a) Seed 1.
(b) Seed
(c) Seed 3.
Figure 22: The averaged KL of each agent in Multi Walker environments.
0.73
0.55
0.99
0.3
0.22
0350
0.6
(a) Sced 1.
(b) Seed
(c) Sced 3.
Figure 23: The averaged KT. of each agent in Spread environments.
36

---

Published as a conference paper at ICLR 2022
REFERENCES FOR SUPPLEMENTARY MATERIAL
Maruan Al-Shedivat, Trapit Bansal, Yura Burda, llya Sutskever, Igor Mordatch, and Pieter Abbeel. Continuous adaptation via meta-learning in nonstationary and competitive environments. In ICLR, 2018.
Bowen Baker, Ingmar Kanitscheider, Todor Markov, Yi Wu, Glenn Powell, Bob McGrew, and Igor Mordatch. Emergent tool use from mullii-gent autocurricula. In ICLR, 2019.
Amir Beck and Mare Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 31(3):677-77,, 2003.
Omar Besbes, Yonatan Gur, and Assaf Zeevi. Stochastic stationary rewards. In NeurlPS, 2014.
problem with non-
Wang Chi Cheung, David Simchi-Levi, and Ruihao Zhu. Non-stationary reinforcement learning: The blessing of (more) optimism. Machine Learning eJournal, 2019.
Christian Schroeder de Witt, Tarun Gupta, Denys Makoviichuk, Viktor Makoviychuk, Philip HS Torr, Mingfei Sun, and Shimon Whiteson. Is independent learning all you need the starcraft multi-agent challenge? arXiv preprint arXiv:201 2020.
Omar Darwiche Domingues, Pierre Ménard, Matteo Pirotta, Emilie Kaufmann, and Michal Valko. A kernel-based approach non-stationary reinforcement learning in metric spaces. International Conference Artificial Intelligence and Statistics, pp. 3538-35466 2021.
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adaptation of deep networks. JCML, 2017.
Jakob Foerster, Richard Chen, Maruan Al-Shedivat, Shimon Whiteson, Pieter Abbeel, and Igor Mordatch. Learning with opponent-learing awareness. In AAMAS, 2018a.
Jakob N. Foerster, Nantas Nardelli, Gregory Farquhar, Triantafyllos Afouras, Philip H. S. Torr, Pushmeet Kohli, and Shimon Whiteson. Stabilising experience replay for deep multi-agent reinforcement learning. In ICMI,, 2017.
Jakob N Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson. Counterfactual multi-agent policy gradients. In AAAI, 2018b.
Pratik Gajane, Ronald Ortner, and Peter Auer. A sliding-window algorithm for Markov decision processes with arbitrarily changing rewards and transitions. arXiv preprint arXiv: 1005.00066 2018.
Matthieu Geist, Bruno Scherrer, and Olivier Pietquin. A theory of regularized markov decision processes. In ICML, 2019.
Jayesh K Gupta, Maxim Egorov, and Mykel Kochenderfer. Cooperative multi-agent control using deep reinforcement learning. In AAMAS, 2017.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with stochastic actor. In ICML, 2018.
Eric A Hansen, Daniel S Bernstein, and Shlomo Zilberstein. Dynamic programming for partially observable stochastic games. AAAI, 2004.
Siyue Hu and Jian Hu. Noisy-MAPPO: Noisy advantage values for cooperative multi-agent actor- critic methods. arXiv preprint arXiv:2106. 14334, 2021.
Shariq Iqbal and Fei Sha. Actor-attentiioncriiicc for multi-agent reinforcement learning. In ICML, 2019.
Max Jaderberg, Wojciech M. Czarnecki, lain Dunning, Luke Marris, Guy Lever, Antonio Gareía Castañeda, Charlie Beattie, Neil C. Rabinowitz, Ari Morcos, Avraham Ruderman, Nicolas Somnerat, Tim Green, Louise Deason, Joel Z. Leibo, David Silver, Demis Hassabis, Koray Kavukcuoglu, and Thore Graepel. Human-level performance in 3D multiplayer games with population-based reinforcement learning. Science, 364:859 865, 2019.
37

---

Published as a conference paper at ICLR 2022
Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11(51):1163-166) 1600, 2010.
Jiechuan Jiang and Zongqing Lu. Adaptive learning rates for multi-agent reinforcement learning, 2021. URL https: hwwp/reeeeeeiieeeeooeeoeeee net/ forum? wrtumiid-yll-1 8 9010..
Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning, In ICML, 2002.
Dong Ki Kim, Miao Liu, Matthew D Riemer, Chuangchuang Sun, Marwa Abdulhai, Golnaz Habibi, Sebastian Lopez-Cor Cot, Gerald Tesauro, and Jonathan How. A policy gradient algorithm for learning to learn in multiagent reinforcement learning. In ICML, 2021.
Jakub Grudzien Kuba, Ruiqing Chen, Munning Wen, Ying Wen, Fanglei Sun, Jun Wang, and Yaodong Yang. Trust region policy optimisation in multi-agent reinforcement learning, arXiv preprint 1xXiv:2109.11250 2021.
Alistair Letcher, Jakob Foerster, David Balduzzi, Tim Rocktäschel, and Shimon Whiteson. Stable opponent shaping in differentiable games. In ICLR, 2019.
Hepeng Li and Haibo He. arXiv:2010.07916 2020.
Multi-agent trust region policy optimization. arXiv preprint
Timothy Lillicrap, Jonathan Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. In ICLR, 2016.
Siqi Liu, Guy Lever, Josh Merel, Saran Tunyasuvunakool, Nicolas Heess, and Thore Graepel. Emergent coordination through competition. ICLR, 2019.
Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, OpenAl Pieter Abbeel, and Igor Mordatch. Multi-agent actor-critic for mixed cooperative-compettivee environments. NeurlPS, 2017.
Weichao Mao, Kaiqing Zhang, Ruihao Zhu, David Simchi-Levi, and Tamer Başar. Near-optimal model-free reinforcement learning in non-stationary episodic mdps. In ICML, 2021.
Ofir Nachum, Mohammad Norouzi, Kelvin Xu, and Dale Schuurmans. Trust-pel: An off-policy trust region method for continuous control. In ICLR, 2018
Ronald Ortner, Pratik Gajane, and Peter Auer. Variational regret bounds for reinforcement learning. In UAI, 2020.
Georgios Papoudakis, Filippos Christianos, A. Rahman, and Stefano Albrecht. Dealing with non-stationarity in multi-agent deep reinforcement learning. ArXiv, abs/1906.04737, 2019.
Neil Rabinowitz, Frank Perbet, Francis Song, Chiyuan Zhang, SM Ali Eslami, and Matthew Botvinick. Machine theory of mind. In ICML, 2018.
Roberta Raileanu, Emily Denton, Arthur Szlam, and Rob Fergus. Modeling others using oneself in multi-agent reinforcement learning. In ICMI, 2018.
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In /CML,, 2015.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXivv1707.063477 2017.
Lior Shani, Yonathan Efroni, and Shie Mannor. Adaptive trust region policy optimization: Global convergence and faster rates for regularized mdps. In AAAI, 2020.
Yuhang Song. Jianyi Wang, Thomas Lukasiewicz, Zhenghua Xu, Mai Xu, Zihan Ding, and Lianlong Wu. Arena: general evaluation platform and building toolkit for multi-agent intelligence. In AAAI 2020.
38

---

Published as a conference paper at ICLR 2022
Justin K Terry, Benjamin Black, Mario Jayakumar, Ananth Hari, Luis Santos, Clemens Dieffendahl, Niall L Williams, Yashas Lokesh, Ryan Sullivan, Caroline Horsch, and Praveen Ravi. PettingZoo: Gym for multi-agent reinforcement learning. arXiv preprint TrXh::2009.14477 2020a.
Justin K Terry, Nathaniel Grammel, Ananth Hari, Luis Santos, and Benjamin Black. Revisiting parameter sharing in multi-agent deep reinforcement learning. arXiv preprint arXiv:200..33625 2020b.
Gerald Tesauro. Temporal difference learning and TD-Gammon. Communications of the ACM, 38 (3):58-68, 1995.
Manan Tomar, Lior Shani, Yonathan Efroni, and Mohammad Ghavamzadeh. Mirror descent policy optimization. arXiv preprint arXiv:2005.09814 2020.
Ying Wen, Hui Chen, Yaodong Yang, Zheng Tian, Minne Li, Xu Chen, and Jun Wang. A game- theoretic approach multi-agent trust region optimization. arXiv preprint (tt::20060008223 2021.
Ronald J Williams. Simple statistical gralient-following algorithms for connectionist reinforcement learning. Machine Learning, 8(3-4):229-255 256, 1992.
Yuhuai Wu, Elman Mansimov, Roger B Grosse, Shun Liao, and Jimmy Ba. Scalable trust-region method for deep reinforcement learning using conneckr-ffcttred approximation. In NeurlPS, 2017.
Annie Xie, Dylan Losey, Ryan Tolsma, Chelsea Finn, and Dorsa Sadigh. Learning latent representa- tions to influence multi-agent interaction. In CoRL, 2020.
Chao Yu, Akash Velu, Eugene Vinitsky, Yu Wang, Alexandre M. Bayen, and Yi Wu. The surprising effectiveness of MAPPO in cooperative, multi-agent games. ArXiv,
2021.
39


Reviews:
[{"review_id": "jNjW0-kfqy-", "reviewer": "Reviewer_16B5", "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": "Strengths: Dealing with non-stationary in MARL is an important research topic in the community. The proposed method in this paper seems to achieve significant performance improvement than baselines.\n\nWeakness: \nThe novelty of $\\delta$-stationarity is relatively less significant to me, especially when provided the mean-field approximation assumption.  It is suggested that the authors provide more discussion about this.  \nThe writing/structure of this paper needs to be improved. For example, the authors didn't summarise the proposed algorithm. The readers need to spend a hard time trying to combine all proposed ideas to imagine the final algorithm and hence it's difficult to follow. It is suggested that the authors clearly present their algorithm in a compact way. ", "summary_of_the_paper": "This paper studies non-stationarity in MARL. They introduce the notion of $\\delta$-stationarity as a measurement of the non-stationarity of a policy sequence. They propose a trust region decomposition framework to impose trust region constraints. They estimate the joint policy divergence with a trust-region decomposition network (TRD-Net), which combined with the mirror descent policy algorithm gives the proposed MAMT algorithm. They show performance improvement in experiments than baselines. ", "summary_of_the_review": "Although the research topic of this paper is important, some parts of the paper should be further discussed and re-organized before it's ready to get accepted. \n\nUpdate after reading the authors' response: I appreciate the authors' response and revision (especially the algorithm section) that have addressed my concerns. I'm happy to increase my score accordingly. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "XH93qusUO4t", "reviewer": "Reviewer_XYrN", "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": "\nStrengths:\n- I like the idea of controlling the non-stationarity of the policies to guide learning in the MARL setting.\n- The proposed switching cost seems to be a useful metric to bound the non-stationarity of the agents' policies.\n- Although it is quite natural that the mean-field approximation directly decomposes the overall switching cost into individual switching costs, I found the connection to be quite interesting.\n- Finally, the experimental section demonstrates the effectiveness of the proposed approach compared to the other algorithms, and also it is an interesting results that the non-stationarity gradually reduces as the number of training rounds is increases.\n\nWeaknesses:\n- I found the paper hard to follow at times. Particularly, the introduction and the related work assumes significant background knowledge.\n- The particular measure of non-stationarity $\\mathcal{D}^t_{i,ns}$, as defined in equation (5), is not well-motivated. The authors should have provided some reasons behind choosing this function.\n\nSome questions for the authors.\n1. The bound on theorem 1 has a linear dependence on the number of time intervals $T = HK$. Therefore, the average regret doesn't vanish to zero as T becomes large, even when non-stationarity is small. What is the reason for this linear dependence? \n2. What is the justification behind replacing the $\\delta_i$ in equation (3) by $\\delta/n$ in equation (4)? Probably an alternative design choice is to keep the constraint $\\sum_i \\delta_i \\le \\delta$ and do a projection after each step of the gradient descent.\n\nSome comments about the presentation.\n1. I found the related work section hard to follow. However, this could be because I am not familiar with the latest work on MARL. But the authors should formally introduce MDP, POMDP, POSG through notations before discussing them in the related section. This could make the related section easy to follow.\n2. Some notations should have been formally defined in the paper e.g. $\\Pi_{ns}, POSG$ etc.\n\n=============Update after reading the authors' response================\nMany thanks for your response. I am happy with the way you addressed my two main concerns and I would vote for accepting the paper.", "summary_of_the_paper": "This paper proposes a new learning algorithm for multi-agent reinforcement learning (MARL) when the stationarity of the policies are bounded. Non-stationarity measures how the agents' policies change with time and high non-stationarity implies slow learning in an MARL setting. The authors introduced a measure based on the KL-divergence between any pair of opponent's joint policies. The first result states that if the switching cost is bounded from above, then it is possible to derive a regret on the learning algorithm used by each agent.\n\nThe main problem is to maximize the sum of values of the agents subject to a bounded switching cost. The authors consider a mean-field approximation which assumes that the joint policy factorizes into individual policies conditioned on the observation. Based on this observations, they are able to show that it is enough to bound the switching cost of each agent rather than the overall switching cost. The authors propose a bilevel optimization problem where the outer optimization is over $\\delta$ the measure of switching cost and the inner variable $\\theta^\\star(\\delta)$ is the optimal parameter for a given choice of $\\delta$. The proposed optimization procedure alternates between gradient descent at different scales. \n\n", "summary_of_the_review": "Overall, I think the paper makes a useful contribution to the vast literature on MARL. In particular, I like the idea of using switching cost to derive better learning algorithms. The experimental evaluation also demonstrates the benefits of the proposes approach. That being said, I thought that the paper should do a better job in presenting the main ideas. Additionally, I believe bounds of some theorems (e.g. theorem 1) can be improved.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "UxIQtUxbUO", "reviewer": "Reviewer_DdBz", "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": "**Strength:**\nThis paper makes a logical and theoretical connection to the proposed method based on the $\\delta$-stationarity, its bound, and trust-region decomposition dilemma.\n\n**Weaknesses and Concerns:**\n1. I am unsure whether the statement \"the insufficient theoretical understanding of non-stationarity\" is true. In the game-theoretical MARL literature, the non-stationarity is represented by a distance of joint policy to an equilibrium. For instance, NashConv is a commonly used metric to measure the distance from a Nash equilibrium (Lanctot et al., 2017). \n\n*Marc Lanctot, Vinicius Zambaldi, Audrunas Gruslys, Angeliki Lazaridou, Karl Tuyls, Julien Perolat, David Silver, Thore Graepel. A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning. NeurIPS, 2017.*\n\n2. I am unsure how novel the new metric $\\delta$-stationarity is because it essentially measures the maximum KLD between two policies. \n\n3. Regarding the considered baseline methods in Section 4, is a fair comparison to MAMT conducted? For example, MAMT employs GNN layers, which could have a larger representation capacity than fully-connected layers. I wonder whether the baselines have a similar network architecture to MAMT for a fair comparison. As another related concern, MAMT's implementation uses other recent techniques, such as attention, mirror descent, and the counterfactual baseline, so it is difficult to identify whether the improvement over baselines is mainly due to which factor.\n\n4. Regarding writing, the paper motivates and explains the idea for a general multiagent environment (e.g., \"opponent\" switching cost). However, the proposed method cannot be applied to competitive and/or general-sum settings because an agent cannot directly control the learning of other agents in these settings. In particular, limiting the divergence between an agent's consecutive policies in competitive settings would not be desirable because the opponent can learn faster, exploit the agent's (relatively) slow learning, and thus gain a bigger return than the agent. I also note that experiments are conducted on the four coordination environments. As a result, rewriting the paper assuming cooperative MARL settings can improve the paper's clarity. \n\n5. Regarding related works in A.1.2, other recent works exploit the opponent's learning process to achieve better performance. Adding the following works will make the related work section more complete:\n*Alistair Letcher, Jakob Foerster, David Balduzzi, Tim Rocktäschel, Shimon Whiteson. Stable Opponent Shaping in Differentiable Games. ICLR, 2019.*\n\n*Annie Xie, Dylan P. Losey, Ryan Tolsma, Chelsea Finn, Dorsa Sadigh. Learning Latent Representations to Influence Multi-Agent Interaction. CoRL, 2020.*\n\n*Dong-Ki Kim, Miao Liu, Matthew Riemer, Chuangchuang Sun, Marwa Abdulhai, Golnaz Habibi, Sebastian Lopez-Cot, Gerald Tesauro, Jonathan P. How. A Policy Gradient Algorithm for Learning to Learn in Multiagent Reinforcement Learning. ICML, 2021.*", "summary_of_the_paper": "This paper proposes MAMT to address the important non-stationarity challenge in MARL, which is inherently resulted from the learning of other agents. Specifically, this paper makes two contributions: 1) introduces the $\\delta$-stationarity metric to measure the non-stationarity, which bounds the dynamic regret of each agent; and 2) addresses the trust-region decomposition dilemma by combining message passing and mirror descent in MAMT. Experiments in four coordinated domains show that MAMT outperforms prior related works. ", "summary_of_the_review": "I initially vote for a score of 5. While the topic studied in this paper is an important problem in MARL and this paper makes a logical motivation to MAMT, I have main concerns regarding the experimental results (i.e., fair comparisons against baselines and identifying the main source of the improvements) and writing of the paper (i.e., needs to be rewritten for a cooperative multiagent setting). After reading the authors' responses to my questions, I am open to raising my score.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "0Dfm4xwodHQ", "reviewer": "Reviewer_LytU", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "The paper is well-written in general and the contributions and the model are well-motivated. Trust region constraints is first mentioned in the abstract, but there has not been enough context provided on how trust region constraints are related to the problem of interest in this paper. That would be great if the authors could briefly elaborate on this in the abstract. \n\nThe main algorithm, MAMT, is not presented in the main body of the paper and I think it would be more instructive if the authors could move it from the appendix to the main body.\n\nIs the algorithm a cooperative one? i.e., do agents communicate messages with each other? If so, how does the communication scheme work and what is the communication cost of the proposed algorithm, i.e., how many number of message bits are being communicated through the agents. Communication cost is an important aspect of every  cooperative multi-agent algorithm and a discussion on it and the ways to improve the tradeoff between the dynamic regret and communication cost is appreciated and would benefit the reader.\n\nCould the authors provide a convincing argument about the non-incremental nature of the novelty?", "summary_of_the_paper": "This paper studies non-stationarity in multi-agent RL. It introduces \\delta-stationarity a notion that measures the non-stationarity of a policy sequence. It proposes an algorithm that satisfy \\delta-stationarity by approximately constraining the consecutive joint policies’ divergence. A dynamic regret bound is proved for each agent. Experiments that verify the provided theoretical guarantees are provided.", "summary_of_the_review": "The problem studied in this paper is interesting and I think it would interest the ICLR community. While the theoretical derivations rely on previous works, e.g., Bai et al., 2019; Gao et al., 2021, they are interesting and elegant. I have not checked all the proofs, but they seem correct.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Although the initial scores of the paper were not positive, the authors managed to properly address the questions/concerns of the reviewers and the changes they made to the paper convinced the reviewers' to update their scores. This clearly shows that there were flaws in the original presentation of the paper. So, I would recommend the authors to take the reviewers' comments into account when they prepare the camera-ready version of their work.
Decision: Accept (Poster)