Settling the Variance of Multi-Agent Policy Gradients
Authors: Jakub Grudzien Kuba
Muning Wen
Linghui Meng
Shangding Gu
Haifeng Zhang
David Henry Mguni
Jun Wang
Yaodong Yang
Venue: NeurIPS 2021 Poster (2021)
Keywords: Multi-Agent Reinforcement Learning
Policy Gradient
Variance Reduction
Statistics

Abstract: Policy gradient (PG) methods are popular reinforcement learning (RL) methods where a baseline is often applied to reduce the variance of gradient estimates. In multi-agent RL (MARL), although the PG theorem can be naturally extended, the effectiveness of multi-agent PG (MAPG)  methods degrades as the variance of gradient estimates increases rapidly with the number of agents.  In this paper, we offer a rigorous analysis of MAPG methods by, firstly, quantifying the contributions of the number of agents and agents' explorations to the variance of MAPG estimators. Based on this analysis, we derive the optimal baseline (OB) that achieves the minimal variance. In comparison to the OB, we measure the excess variance of existing MARL algorithms such as vanilla MAPG and COMA. Considering using deep neural networks,  we also propose a surrogate version of OB, which can be seamlessly plugged into any existing PG methods in MARL.   On benchmarks of Multi-Agent MuJoCo and StarCraft challenges, our OB technique effectively stabilises training and improves the performance of multi-agent PPO  and COMA algorithms by a significant margin.  Code is released at  \url{https://github.com/morning9393/Optimal-Baseline-for-Multi-agent-Policy-Gradients}. 

Settling the Variance of Multi-Agent Policy Gradients
Jakub Grudzien Kuba":1,2 Muning Wen" Linghui Meng', Shangding Gu', Haifeng Zhang', David Henry Mguni", Jun Wang', Yaodong Yang .6 Imperial College London, Huawei R&D UK, Shanghai Jiao Tong University, IInttiuute of Automation, Chinese Academy of Science, $ University College London, 6 Institute for AI, Peking University.
Abstract
Policy gradient (PG) methods are popular reinforcement learning (RL. methods where baseline often applied to reduce the variance of gradient estimates. In multi-agent RL (MARL), although the PG theorem can be naturally extended, the effectiveness of multi-agent PG (MAPG) methods degrades as the variance of gra- dient estimates increases rapidly with the number of agents. In this paper we offer a rigorous analysis of MAPG methods by, firstly, quantifying the contributions of the number of agents and agents' explorations to the variance of MAPG estimators. Based on this analysis, we derive the optimal baseline (OB) that achieves the mini- mal variance. In comparison to the OB, we measure the excess variance of existing MARL algorithms such as vanilla MAPG and COMA. Considering using deep neu- ral networks, we also propose surrogate version of OB, which can be seamlessly plugged into any existing PG methods in MARL. On benchmarks of Multi- Aalti- MuJoCo and StarCraft challenges, our OB technique effectively stabilises training and improves the performance of multi-agent PPO and COMA algorithms by a significant margin. Code is released at https: /tte::///tttut con/morning9393/ Optimal- Beslll-Bseeinne
Multi- agent- Gradients.
Introduction
Policy gradient (PG) methods refer to the category of reinforcement learning (RL) algorithms where the parameters stochastic policy are optimised with respect to the expected reward through gradient ascent. Since the earliest embodiment of REINFORCE [40], PG methods, empowered by deep neural networks [33], are among the most effective model-free RL algorithms on various kinds of tasks [2, 6, 10]. However, the performance of PG methods is greatly affected by the variance of the PG estimator [35, 37]. Since the RL agent behaves an unknown stochastic environment, which is often considered as black box, the randomness of expected reward easily become very large with increasing sizes of the state and action spaces; this renders PG estimators with high variance, which concequently leads low sample efficiency and unsuccessful trainings [9, 35].
To address the large variance issue and improve the PG estimation, different variance reduction methods were developed [9, 23, 35, 48). One of the most successfully applied and extensively studied methods is the control variate subtraction [8, 9, 37]. also known as the baseline trick. A baseline is scalar random variable, which can be subtracted from the state-action value samples in the PG estimates so as to decrease the variance, meanwhile introducing no bias to its expectation. Baselines can be implemented through constant value [8, 12] or value that is dependent the state [8, 9, 11, 33] such as the state value function, which results in the zero-centered advantage function and the advantage actor-critic algorithm [18]. State-action dependent baselines also be applied [9, 41], although they are reported to have no advantages over state- nete-deeendent baselines [35].
"Equal contribution. CCorresponding author syaodong. yang @ @kpu.edu.en>
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

When it comes to multi-agen reinforcement learning (MARL) [43], PG methods can naturally be applied. One naive approach make each agent disregard its opponents and model them as part of the environment. In such a setting, single-agent PG methods can be applied in a fully decentralised way (hereafter referred as decentralised training (DT)). Although DT has numerous drawbacks, for example the non-stationarity issue and poor convergence guarantees [3, 16], it demonstrates excellent empirical performance in certain tasks [19, 263. A more rigorous treatment is to extend the PG theorem to the multi-agent policy gradient (MAPG) theorem, which induces a learning paradigm known as centralised training with decentralised execution (CTDE) [7, 42, 45, 46]. In CTDE, each agent during training maintains centralised critic which takes joint information input, for example COMA [7] takes joint state- atate-action pair; meanwhile, it learns a decentralised policy that only depends on the local state, for execution. Learning the centralised critic helps address the non- non-stationarity issue encountered in DT [7, 16]; this makes CTDE an effective framework for implementing MAPG and successful applications have been achieved in many real-world tasks [13, 17, 22, 38, 39, 50].
Unfortunately, compared to single-agent PG methods, MAPG methods suffer more from the large variance issue. This is because in multi-agent settings, the randomness comes not only from each agent's own interactions with the environment but also other agents' explorations. In other words, an agent would not be able to tell if an improved outcome is due to its own behaviour change or other agents' actions. Such a credit assignment problem [7, 36] is believed to be one of the main reasons behind the large variance of CTDE methods [16]; yet, despite the intuition being built, there is still a lack of mathematical treatment for understanding the contributing factors to the variance of MAPG estimators. As result, addressing the large variance issuc in MARL is still challenging. One relevant baseline trick in MARL is the application of a counterfactual baseline, introduced in COMA [7]: however, COMA still suffers from the large variance issue empirically [19].
In this work, we analyse the variance of MAPG estimates mathematically. Specifically, we try to quantify the contributions of the number of agents and the effect of multi-agent explorations to the variance of MAPG estimators. One natural outcome of our analysis is the optimal baseline (OB), which achieves the minimal variance for MAPG estimators. Our OB technique can be seamlessly plugged into any existing MAPG methods. We incorporate in COMA [7] and a multi-agent version of PPO [29], and demonstrate its effectiveness by evaluating the resulting algorithms against the state-of thetthe-art algorithms. Our main contributions are summarised as follows:
1. We rigorously quantify the excess variance of the CTDE MAPG estimator to that of the DT and prove that the order of such excess depends linearly the number of agents, and quadratically on agents' exploration terms (i.e., the local advantages).
2. We demonstrate that the counterfactual baseline of COMA reduces the noise induced by other agents, but COMA still faces the large variance due to agent's own exploration.
3. We derive that there exists an optimal baseline (OB), which minimises the variance of an MAPG estimator, and introduce a surrogate version of OB that can be easily implemented in any MAPG algorithms with deep neural networks.
4. We show by experiments that OB can effectively decrease the variance of MAPG estimates in COMA and multi-agent PPO, stabilise and accelerate training in StarCraftII and Multi-Agent MuJoCo environments.
2 Preliminaries & Background
In this section, we provide the prelimiaries for the MAPG methods in MARL. We introduce notations and problem formulations in Section 2.1, present the MAPG theorem in Section 2.2, and finally, review two existing MAPG methods that our OB can be applied to in Section 2.3.
2.1 Multi-Agent Reinforcement Learning Problem
We formulate a MARL problem as a Markov game [14], represented as a tuple SW.SAA,P,r 7). Here, .' = fl..... n) is the set of agents, S is the state space, A = II=
action spaces of the n agents, known as the joint action space, P: A - A' is the product of
+ R is the transition probability kernel, r: S x A- - R is the reward function (with Ir(s, a)l < 3, Vs E E E A), and y E [0, 1) is the discount factor. Each agent possesses a parameter vector 0², which concatenated with parameters of other agents, gives the joint parameter vector 0. At time step N, the
2

---

agents are at state E S. An agent i takes an action af AA' drawn from its stochastic policy To (-1,)) parametrised by 8 ()) simultaneously with other agents, which together gives a joint action a, (a) (a.....,,a)) ,,)) E A. drawn from the joint policy Te rg(ar/s)) = II. (a (st). The system moves to state St+1 E S with probability mass/density P(sc+ Se, az A trajectory is a sequence r= (St, a, Eu of states visited, actions taken, and rewards received by the agents in an interaction with the environment. The joint policy πe, the transition kernel P. and the initial state distribution d", induce the marginal state distributions at time t, i.e. dg (s), which is probability mass when S is discrete, and density function when S is continuous. The total reward at time t E N is defined as R.
A 7 Tetk- The state value function Vo and the state-action value function Qo are given by
Vo (s)) - Emaise Noo uP Ro = $) : Qo(s, a) - Essio P.atoe [Ro So s, ap
The advantage function is defined Ao a) - Qa(s,a) Vo(s). The goal of the agents is to maximise the expected total reward [() & Eggar [Vo(s)]
In this paper, we write- - (f1,....ia, to denote the set of all agents excluding é1, ....... de (we drop the bracket when &o = 1). We define the multi aggett state- action value function for agents i...... as D0 " (s, (f.......4))) - -E_ (a-(4------)- (f1..... [Qo (s, (f......4)), a ) which the expected total reward once agents .i....> .......,. ig have taken their actions. Note that for k this becomes the state value function, and for l = n, this is the usual state-action value function. As such, we can define the multi-agent advantage function as
Ag fun.dk
(s, (in a ((fe)...f)))
Quminddm (s, alhrmmda))
(I)
which is the advantage of agents i1, ................................ dg playing a" ...., a't, given a² ,...,,m amm When n-1 and h: = 1, this is often referred to as the local advantage of agent [7].
2.2 The Multi-Agent Policy Gradient Theorem
The Multi-Agent Policy Gradient Theorem 17, 47] is an extension of the Policy Gradient Theorem [33] from RL to MARL, and provides the gradient of (0) with respect to agent i's parameter, 0', as
8o
Vg T(O] = Sanse wot 10:00 Puu.o
roQoss a, at) Var log (a//
From this theorem we can derive two MAPG estimators, one for CTDE (i.e. ge), where learners can query for the joint state-action value function, and one for DT (i.e., gi), where every agent can only query for its own state-action value function. These estimators, respectively, are given by
gi:
Σ 2'2 (St, aT Ve: log T (a]]s:) and Bi = Σ 1=0
2' (St, at) Vos log TO (a/(s:),
1=
where ~ dg. at ~ =g((1s))) a. (-(s)) Here, Q is (joint) critic which agents query for values Qs a). Similarly, Q² is a critic providing values of (h,s, The roles of the critics are, in practice. played by neural networks that can be trained with TD-learning [7, 34]. For the purpose of this paper. we assume they give exact values. In CTDE, a baseline [7] is any function b(s, a '). For any such function, we can easily prove that
E E aoadlya--o -immn Latway [b(s, a Vo log () [s]] = 0,
(for proof see Appendix A or [7]) which allows augmenting the CTDE estimator as follows
20
(b) Σn (Q(s), a, at) b(Se, a, a V a. log (a](ss)))
OI could have been more clear to write ThJ. to highlight that n' depends only on and no other parts of 0. Our notation, however, allows for more convenience in the later algebraic manipulations. TTe notation "a" and "(a -t ",at)., as well as "a ~ лe" and "a- क a² m are equivalent. write a' and when refer the action and joint action as values, and a' and random variables.
3

---

and it has exactly the same expectation as gC BC (0), but can lead to different variance properties. In this paper, we study total variance, which is the sum of variances of all components s of a vector estimator (b). We note that one could consider the variance of every component of parameters, and for each of them choose a tuned baseline [23]. This, however, in light of neural networks with overwhelming parameter sizes used in deep MARL seems not to have practical applications.
2.3 Existing CTDE Methods
The first stream CTDE methods uses the collected experience in order to approximate MAPG and apply stochastic gradient ascent [34] optimise the policy parameters.
COMA [7] is one of the most successful examples of these. It employs centralised critic, which it adopts to compute a counterfactual baseline b(s, a=) is, "(ssa=" a²). Together with Equations & 2, COMA gives the following MAPG estimator
SCUMA
Σ 1=
As,, a V log (a(a((s)
(3)
Another stream is the one of trust-region methods, started in RL by TRPO [27] in which at every iteration, the algorithm aims to maximise the total reward with policy in proximity of the current policy. It achieves by maximising the objective
(a(a))) Te.u (a|s)
Egrepesy Bao3
A(s, a)
subject to Egripss (Te.a (-1s) no (-Is)) = 6.
(4)
PPO [29] has been developed as a trust-region method that is friendly for implementation: approxi- mates TRPO by implementing the constrained optimisation by means of the PPO-clip objective.
Multi-Agent PPO. PPO methods can be naturally extended to the MARL setting by leveraging the CTDE framework to train shared policy for each agent via maximising the sum of their PPO-clip objectives, written
Taaalss) Tee (a'ss) Als, a), clip
To(a'ls) Te (a*ls) 1 - e, c,1+e) A(s.aa)
E pa ad
min
(5)
(a'ls The clip operator replaces the ratio new (s] with, when its value is lower, + when its value is higher, to prevent large policy updates. Existing implementations of Equation have been mentioned by [4, 45].
In addition to these, there are other streams of CTDE methods in MARL,, such as MADDPG [15], which follow the idea of deterministic policy gradient method [30], and QMIX [24), Q-DPP [44] and FQL [49], which focus on the value function decomposition. These methods learn either deterministic policy or a value function, thus are not in the scope of stochastic MAPG methods.
3 Analysis and Improvement of Multi-agent Policy Gradient Estimates
In this section, we provide a detailed analysis of the variance of the MAPG estimator, and propose a method for its reduction. Throughout the whole section rely the following two assumptions. Assumption 1.
The state space S, and every agent i's action space A is either discrete and finite, or continuous and compact.
Assumption 2. For all i E N. s E S, a' E A', the map 0* + (a(aa (s) is continuously differentiable.
3.1 Analysis MAPG Variance
The goal of this subsection is to demonstrate how an agent's MAPG estimator's 's variance is influenced by other agents. In particular, we show how the presence other agents makes the MARL problem different from single-agent RI. problems (e.g., the DT framework). We start our analysis by studying the variance the component in CTDE estimator that depends on other agents, which the joint f-fnuction. Since Vara~ [Qe(s, a)] Vara-aa (Vo(s) + Ao a)] Var [Ae a)), we

---

can focus our analysis on the advantage function, which has more interesting algebraic properties. We start by presenting simple lemma which, in addition being premise for the main result, offers some insights about the relationship between RI and MARL problems.
Lemma (Multi-agent advantage decomposition). For any state & E S, the sollowing equation holds for any subset of m agents and any permutation of their labels.
Ag Al....m
(s.a
Σ Ab 8, a al at)
For proof see Appendix B.I. The statement of this lemma that the joint advantage of agents' joint action is the sum of sequentially unfolding multi-agent advantages of individual agents' actions. suggests that a MARL problem can be considered as a sum of n RL problems. The intuition from Lemma I leads to idea of decomposing the variance of the total advantage into variances of multi-agent advantages of individual agents. Leveraging the proof of Lemma I, we further prove that
Lemma 2. For any state & E S, we have
Vara-m [Ao(s, a)] Σ
11
E Band
1 Vargaaa [Ab (s.altmmt- )1]
For proof see Appendix B.I. The above result reveals that the variance of the total advantage takes a sequential and additive structure of the advantage that is presented in Lemma This hints that similar additive relation can hold once we loose the sequential structure of the multi-agent advantages. Indeed, the next lemma, which follows naturally from Lemma 2, provides an upper bound for the joint advantage's 's variance in terms of local advantages, and establishes notion of additivity of variance in MARL..
Lemma 3. For any state & E S, we have
Vara-m [)) S
Var iu anaa [A ,a)]
For proof Appendix B. Upon these lemmas derive the main theoretical result of this subsection. The following theorem describes the order of excess variance that the centralised policy gradient estimator has over the decentralised one.
Theorem 1. The CTDE and DT estimators of MAPG satisfy
B²
(n 1) (eB.)²
Var So. oogo a0: [8c]
Var Sa. ~00 00.50
BD
1 72
E
2
S
72
jfi
where B, = sups.a a log Th (a' ds)s sup Ab(ss a ",)a)))) and c maxi
Proof sketch. (For the full proof see Appendix B.2.) We start the proof by fixing a state and consider- ing the difference of Var.>n, [Q(x, "","a""aa)) a log (a()))))) Var
((x,a'VV, log T (aa))))) The goal of our proof strategy was to collate the terms Q(s, a ai, and Q'(s, a') because such an expres- sion could be related to the above lemmas about multi-agent advantage, given that the latter quantity is the expected value of the former when a To Based on the fact that these two estimators are unbi-
ased, we transform the considered difference into Ea-To || log (a'))' |s)]| (Q(s.a) - (=(,.a')
a'), and the result of Lemma 3, we bound this expectation by B Σjæs Bat Var Vara-i-a;' a ,a)) which we then rewrite bound it by B² Eg 23. As such, the first inequality in the theorem follows from summing, with discounting, over all time steps t, and the second one is its trivial upper bound. O
Using the upper bound B,, the fact that À Â aaaa,aa'' a- ((s, -²)
The result Theorem exposes the level of difference between MAPG and PG estimation which, measured by variance, is not only non-negative, as shown in [16], but can grow linearly with the number of agents. More precisely, a CTDE learner's gradient estimator comes with an extra price of variance coming from other agents' local advantages (i.c., explorations). This further suggests
5

---

that we shall search for variance reduction techniques which augment the state-action value signal. In RL, such well-studied technique maseline-subtractinn where many successful baselines are state-dependent. In CTDE, we can employ baselines taking state and other agents' actions into account. We demonstrate their strength on the example of counterfactual baseline of COMA [7]-
Theorem 2. The COMA and DT estimators of MAPG satisfy
(e,B:)² 1 72
Var to go
[BCOMA]
Var 50.00 dd 20
BD
S
For proof see Appendix B.2. The above theorem discloses the effectiveness of the counterfactual baseline. COMA baseline essentially allows to drop the number of agents from the order of excess variance of CTDE, thus potentially binding it closely to the single-agent one. Yet, such binding is not exact, since it still contains the dependence on the local advantage, which can be very large in scenarios when, for example, a single agent has a chance to revert its collaborators' errors with its own single action. Based on such insights, in the following subsections, we study the method of optimal basclines, and derive solution to these issues above.
3.2 The Optimal Baseline for MAPG
In order to search for the optimal baseline, we first demonstrate how it can impact the variance of an MAPG estimator. To achieve that, we decompose the variance an arbitrary time step / 2 and separate the terms which are subject to possible reduction from those unchangable ones. Let us denote (b) = 1K(s,, ar) bj a log T (aflse), sampled with St ~ dg. a T-(ss))), which is essentially the hhh summand of the gradient estimator given by Equation 2. Specifically, we have
Var Novagaann (b) = Var.,wd
[Bainmo
[BC.
+ Bng (Vara BC.,(6)]
(6)
Var Em wwo [6] Berwag Var
Eas Ca
[BC.c((i]] + E aaai'on "mr" (Varaaes (0).
Var
Eme~
[0] +B Var
E Eat (b)
+ E Bund af 'mm
Var Var wo [Bc.
Variance from state
Variance from other agents' actions
Variance from agent i's action
Thus, in a CTDE estimator, there are three main sources of variance, which are: state St, other agents' joint action a, and the agent i's action a/. The first two terms of the right-hand side of the above equation, which are those involving variance coming from and a," remain constant for all b. However, the baseline subtraction influences the local variance of the agent, Var.;=rū [BC,,(0 (b)]. and therefore minimising it for every (s, a) pair minimises the third term, which is equivalent to minimising the entire variance. In this subsection, we describe how to perform this minimisation.
Theorem (Optimal baseline for MAPG). The optimal baseline (OB) the MAPG estimator is
Raiwag ( || log (sa)s)))) 22
poptimal (s, a 1)
E Eg'waj
V log TO (a' (s) [|]
For proof see Appendix C.I. Albeit elegant, OB in Equation 7 is computationally challenging to estimate due to the fact that it requires repeated computation of the norm of the gradient V log TO (a (s), which can have dimension of order ~ 10 when the policy is parametrised by neural network (e.g., [31, Appendix C.2]). Furthermore, in continuous action spaces, in principle the Q-function does not have simple analytical form, this baseline cannot be computed exactly, and instead must be approximated. This is problematic, too, because the huge dimension of the gradients may induce large variance in the approximation of OB in addition to the variance of the policy gradient estimation. To make OB computable and applicable, we formulate in the next section a surrogate auriance-miimissae objective, whose solution is much more tractable.
3.3 Optimal Baselines for Deep Neural Networks
Recall that in deep MARL, the policy Th is assumed to be member of specific family of distributions, and the network 0t only computes its parameters, which can refer to as vog In

---

the discrete MARL. it can be the last layer before softmax, and in the continuous MARL, vi can be the mean and the standard deviation of a Gaussian distribution [7, 45]. We can then write Th (a"(s) n' (a 1// (s)), and factorise the gradient Vo log vo with the chain rule. This allows us to rewrite the local variance as
Ve log (a))v(())) (É(s.a (a')- b(s, [1)
=Var,ingg
V (5)
(g log (s)) (Ā(s, ,a') b(s, b(s, 1)
vg log (d))v((s) (Q(s,a - (a)a-",a)bb(ss-
V Vo()))
(8)
This allows to formulate surrogate minimisation objective, which is the variance term from Equation 8, which we refer to as surrogate local variance. The optimal baseline for this objective comes corollary to the proof of Theorem 3.
Corollary 1. The optimal baseline for the surrogate local variance in Equation 8 is
E Barwng
[e(s,a aaa) V og(o)
log (d))66())
6" (s,
(9)
Balwar [[| [ og log (al=6()))
Note that the vector V (g)ss) log n' (a" (s)) can be computed without backpropagation when the family of distributions to which Th belongs is known, which is fairly common in deep MARL. Additionally, the dimension of this vector is of the same size the size of the action space, which in the order ~ 10 in many cases (e.g.. [7, 32J) which makes computations tractable. Equation essentially allows us to incorporate the OB in any existing (deep) MAPG methods, accouting for both continuous and discrete-actinn taks. Hereafater, we refer to the surrogate OB in Equation as the OB and apply it in the later experiment section.
3.4 Excess Variance of MAPG/COMA OB
(a = V ugenn log (10))))))
We notice that for probability measure xy vi
the OB takes
- [I| v "ygco (n) log ( (a'lv()))
(va(e)) [T]
the form of 6* (s, a)
Egewet [Q(s, aa)] It is then instructive to look at practical deep MARL
v1 example, which is that of a discrete actor with policy Tt (a'1s) (s) softmax(vi (s)) In this case, we can derive that
2/ (a'ls) o T (a'ls) (1 (d)) 2 (a'ls)
(10)
(Full derivation is shown in Appendix C.2). This measure, in contrast to COMA, scales up the weight of actions with small weight in Th. and scales down the weight of actions with large z while COMA's baseline simply takes each action with weight determined by zg.- which has an opposite effect OB. Let the excess surrogate local variance of CTDE MAPG estimator (b) of agent i be defined as Equation 11. We analyse the excess variance in Theorem
Var(b) Var,
ge (b)
Var, [c((0"]
(11)
Theorem 4. The excess surrogate local variance for baseline satisfies
AVar(b) (b- bb-b"(s, Bytnni
[| log ' (a') (d]]u6(s))ll
In particular, the excess variance of the vanilla MAPG and COMA estimators satisfy
2
VarMArG D2 (Var,t-wgg [Ab(s, ,aa)] + Q (s,
2
1-
VarcoMa S DJ Var [Ab(s, ".,' & (e.D.)²
where D, sup.. V log (a (o)))]())) and e = sup
7

---

Table I: A numerial toy exmaple that shows the effectiveness of OB. all actions column a', agent i is provided with the last layer before softmax of its actor network and the actions' values (columns (a') and Qía (, It computes the remaining quantities in the table, which are used to derive the three gradient estimators, whose variance is summarised the right part of the table. The full calculations of the below values are stored in Appendix E.
a²
vo (a))
(a')
(a')
Q(a ,,²)
Á' (,a) X' ",a')
Method
Variance
log 8
0.8
0.14
2
-9.7
411.7
MAPG COMA
1321
0.1
0.43
1
10.7
42.71
1015
0.1
0.43
100
88.3
56.29
673
#CMA
#COMA
100
mrrm
6.3
035
Km
2x3t
(R] 3 manines
(b) 8 marines
[c) stalkers & zealets
(d) gradient norm comparison
Figure 1: Performance comparisons between COMA with and without OB three SMAC challenges.
For proof see Appendix C.3. This theorem implies that OB is particularly helpful in situations when the value of Q function is large, when agent i's local advantage has large variance. In these scenarios, a baseline like COMA might fail because when certain actions have large local advantage, would want the agent learn them, although its gradient estimate may be inaccurate, disabling the agent to learn to take the action efficiently.
3.5 Implementation of the Optimal Baseline
Our OB technique is general method to any MAPG methods with joint critic. It can be seamlessly integrated into any existing MARL algorithms that require MAPG estimators. One only needs to replace the algorithm's state-action value signal (either state-action value advantage function) with
(s, a ,a)) = Q(s. a aaaaaaaaa a,a' - as,
(12)
This gives us an estimator of COMA with OB
(se, at) o log me (a/)se),
8x
and variant of Multi-agent PPO with OB, which maximises the objective of
Ta(a'ls) 8' a), clip Tome (2)|s)
nh (a'ls) To.. (a'
1 1 8((s.a)
Ea-pesta a Rosid
min
In order to compute OB, agent i follows these two steps: firstly, it evaluates the probability measure T/g. and then computes the expectation of ((,, a') over with dot product. Such a protocol allows for exact computation of OB when the action space is discrete. When it comes continuous action space, the first step of evaluating <'g relies on sampling actions from agent's 's policy, which gives the approximation of OB. To make it clear, provide PyTorch implmentations of OB in both discrecte and continuous settings in Appendix D.
Experiments
On top of theoretical proofs, this section, we demonstrate empircial evidence that OB can decrease the variance of MAPG estimators, stabilise training, and most importantly. lead to better performance. To verify the adaptability of OB, we apply OB on both COMA and multi-agent PPO methods as described in Section 3.5. We benchmark the OB-modified algorithms against existing state-of-the-art

---

111
22000
110
2.40
2343
1554
221 05
(a) 3-Agent Hopper
(b) 2-Agent Swimmer
(c) 6-Agent HalfChetuah
(d) 2-Agent Walker
Sea tax 2tr
St st. ScSre Heat
27t She thamn hestt
g.4
8.44
NATPO d8
122
690
(e) stalkers vs. zealots
(f) marines vs. marinos
(g) 6 hydralisks vs. 8 zealots
(h) 27 marines vs. 30 marines
Figure 2: Performance comparisons between multi-agent PPO method with and without OB on four multi-agent MuJoCo tasks and four (super-)hard SMAC challenges.
Table 2: Comparisons on the standard deviation of the gradient norm of multi-agent PPO method with and without OB. All quantities are provided scale 0.01. Standard errors are provided in brackets. Results suggest OB consistently reduces gradient norms across all eight tasks.
M Task
34
5m
6b
27m 30m
6-Agent HalfCheetah
3-Agent Happer
2-Agemt Swimmer
2-Agent Walker
MAPPO w/ OB
2.20 (0.17)
1.50 (0,02)
2.33 (0.03)
11.55 (4.80)
30.64 (0.50)
79.67 (3.79)
66,72 (3.67)
372,03 (10.83)
MAPPO w/o OB
6.67 (0.35)
2.17 (0,0T)
2.54 (0.09)
19.62 (6.90)
33.65 (2.04)
K2.45
73.54 (11.98)
66 (18.34)
(SOTA) methods, which include COMA [7] and MAPPO [45], and value-based methods such as QMIX [24] and COMIX [21], and a deterministic PG method, ie., MADDPG [15]. Notably, since OB relies the Q-function eritics, we did not apply the GAE [28] estimator that builds only on the state value function when implementing multi-agent PPO for fair comparisons. For each of the baseline on each task, we report the results of five random seeds. We refer to Appendix F for the detailed hyper-parameter settings for baselines.
Numerical Toy Example. We first offer numerical toy example demonstrate how the subtraction of OB alters the state-action value signal in the estimator, as well as how this technique performs, against vanilla MAPG and COMA. We assume stateless setting, and given joint action of other agents. The results in Table show that the measure 2t puts more weight on actions neglected by
Ty. lifting the value of OB beyond the COMA baseline, as suggested by Equation 10. The resulting X function penalises the sub-optimal actions more heavily. Most importantly, OB provides a MAPG estimator with far lower variance as expected.
StarCraft Multi-Agent Challenge (SMAC) [25]. In SMAC, each individual unit is controlled by a learning agent, which has finitely many possible actions to take. The units cooperate to defeat enemy bots across scenarios of different levels of difficulty. Based on Figure 1(a-d), we can tell that OB provides more accurate MAPG estimates and stabilises training of COMA across all three maps. Importantly, COMA with OB learns policies that achieve higher rewards than the classical COMA. Since COMA perform badly on hard and super- hard maps in SMAC [19], we only report their results on easy maps. On the hard and super-hard maps in Figures 2e, 2f, and 2g. OB improves the performance of multi-agent PPO. Surprisingly on Figure 2e, OB improves the winning rate of multi-agent PPO from zero to 90%. Moreover, with an increasing number of agents, the effectiveness of OB increases in terms of offering a low-variance MAPG estimator. According to Table 2, when the tasks involves 27 learning agents, OB offers a 40% reduction in the variance of the gradient norm.
Multi-Agent MuJoCo [5]. SMAC are discrete control tasks; here we study the performance of OB when the action space continuous. In each environment of Multi-Agent MuJoCo, each individual agent controls part of shared robot (e.g., a leg of Hopper), and all agents maximise a shared reward function. Results are consistent with the findings on SMAC in Table 2: on all tasks, OB helps decrease the variance of gradient norm. Moreover, OB can improve the performance of multi-agent PPO on most MuJoCo tasks Figure 2 (top row), and decreases its variance in all of them. In particular, multi-agent PPO with OB performs the best on Walker (i.e., Figure 2d) and HalfCheetah (i.e., Figure 2c) robots, and with the increasing number of agents, the effectiveness OB becomes apparent; 6-agent HalfCheetah achieves the largest performance gap.

---

Conclusion
In this paper, we try to settle the variance of multi-agent policy gradient (MAPG) estimators. We start contribution by quantifying. for the first time, the variance of the MAPG estimator and revealing the key influencial factors. Specifically, we prove that the excess variance that a centralised estimator has over its decentralised counterpart grows linearly with the number of agents, and quadratically with agents' local advantages. A natural outcome of our analysis is the optimal baseline (OB) technique. We adapt OB exsiting deep MAPG methods and demonstrate its empirical effectiveness on challenging benchmarks against strong baselines. In the future, we plan to study other variance reduction techniques that can apply without requiring Q-function critics.
Author Contributions
We summarise the main contributions from each of the authors follows:
Jakub Grudzien Kuba:
Theoretical results, algorithm design, code implementation (discrete OB, continuous OB) and paper writing.
Muning Wen: Algorithm design, code implementation (discrete OB, continuous OB) and experi- ments running.
Linghui Meng: Code implementation (discrete OB) and experiments running.
Shangding Gu: Code implementation (continuous OB) and experiments running.
Haifeng Zhang: Computational resources and project discussion.
David Mguni: Project discussion.
Jun Wang: Project discussion and overall technical supervision.
Yaodong Yang: Project lead, idea proposing, theory development and experiment design supervision, and whole manuscript writing. Work were done at King's 's College London.
Acknowledgements
The authors from CASIA thank the Strategic Priority Research Program of Chinese Academy of Sciences, Grant No. XDA27030401.
References
[1] Joshua Achiam. Spinning Up in Deep Reinforcement Learning. 2018.
[2] Jonathan Baxter and Peter L Bartlett. aafinite-horizon Artificial Intelligence Research, 15:319-350, 2001.
estimation. Journal of
[3] Caroline Claus and Craig Boutilier. The dynamics reinforcement learning in cooperative multiagent systems. AAAI/IAAI, 1998(746-752)22 1998.
[4] Christian Schroeder de Witt. Tarun Gupta, Denys Makoviichuk, Viktor Makoviychuk, Philip HS Torr, Mingfei Sun, and Shimon Whiteson, Is independent learning all you need in the starcraft multi-agent challenge? arXiv preprint arXiv:2011.09533, 2020.
[5] Christian Schröder de Witt, Bei Peng, Pienre-Alexanrre Kamienny, Philip H. S. Torr, Wendelin Böhmer, and Shimon Whiteson. Deep multi-agent reinforcement learning for decentralized continuous cooperative control. CoRR, abs/2003.06709, 2020.
[6] Yan Duan, Xi Chen, Rein Houthooft, John Schulman, and Pieter Abbeel. Benchmarking deep reinforcement learning for continuous control. In International conference on machine learning, pages 1329-1338. PMLR, 2016.
[7] Jakoh Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson. Counterfactual multi-agent policy gradients. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
[8] Evan Greensmith, Peter I. Bartlett, and Jonathan Baxter. Variance reduction techniques for gra- dient estimates in reinforcement learning. Journal of Muchine Learning Research, 5(Nov)::471- 1530, 2004.
10

---

[9] S Gu, T Lillicrap. Z Ghahramani. RE Turner, and S Levine. Q-prop: Sample-efficien policy gradient with an off policy critic. In 5th International Conference on Learning Representations. ICLR 2017-Conference Track Proceedings, 2017.
[10] Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off- policy maximum entropy deep reinforcement learning with a stochastic actor. In International Conference on Machine Learning, pages 1861-1870. PMLR, 2018.
[11] Shimon Whiteson Kamil Ciosek. Expected policy gradients for reinforcement learning. Journal of Machine Learning Research, 2 21:1-51, 2020.
[12] Hajime Kimura, Kazuteru Miyazaki, and Shigenobu Kobayashi. Reinforcement learning in pomdps with function approximation. In Proceedings the Fourleenth International Conference on Machine Learning, pages 152-160, 1997.
[13] Minne Li, Zhiwei Qin, Yan Jiao, Yaodong Yang, Jun Wang, Chenxi Wang, Guobin Wu, and Jieping Ye. Efficient ridesharing order dispatching with mean field multi-agent reinforcement learning. In The World Wide Web Conference, pages 983-994, 2019.
[14] Michael L Littman. Markov games as a framework for multi-agent reinforcement learning. In Machine learning proceedings 1994, pages 157-163. Elsevier, 1994.
[15] Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, Pieter Abbeel, and Igor Mordatch. Multi-agent actor- critic for mixed cooperativ-ccompettive environments. In Proceedings of the 3/st International Conference on Neural Information Processing Systems, pages 6382-6393, 2017.
[16] Xueguang Lyu, Yuchen Xiao, Brett Daley, and Christopher Amato. Contrasting centralized and decentralized critics in multi-agent reinforcement learning. In Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems, pages 844-852, 2021.
[17] David H Mguni, Yutong Wu, Yali Du, Yaodong Yang. Ziyi Wang, Minne Li, Ying Wen, Joel Jennings, and Jun Wang. Learning nonzero-sum stochastic games with potentials. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 7688-7699. PMLR, 18 24 Jul 2021.
[18] Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforce- ment learning. In International conference on machine learning, pages 1937. PMLR, 2016.
[19] Georgios Papoudakis, Filippos Christianos, Lukas Schäfer, and Stefano V Albrecht. Compara- tive evaluation of cooperative multi-agent deep reinforcement learning algorithms. 2020.
[20] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in Neural Information Processing Systems, 32:8026-8037, 2019.
[21] Bei Peng, Tabish Rashid, Christian A Schroeder de Witt, Pierre-Alexandee Kamienny, Philip HS Torr, Wendelin Böhmer, and Shimon Whiteson. Facmac: Factored multi- agent centralised policy gradients. arXiv e-prints, pages arXiv-2003, 2020.
[22] Peng, Q Yuan, Y Wen, Y Yang, Z Tang. H Long, and J Wang. Multiagent bidirectionally- coordinated nets for learning to play starcraft combat games. arxiv 2017. arXiv preprint arXiv: 10069, 2017.
[23] Jan Peters and Stefan Schaal. Policy gradient methods for robotics. In 2006 IEEE/RS/ International Conference on Intelligent Robots and Systems, pages 2219-2225. IEEE, 2006.
[24] Tabish Rashid, Mikayel Samvelyan, Christian Schroeder, Gregory Farquhar, Jakob Foerster, and Shimon Whiteson. Qmix: Monotonic value function factorisation for deep multi-agent reinforcement learning. In International Conference on Machine Learning, pages 4205-4304. PMLR, 2018
11

---

[25] Mikayel Samvelyan, Tabish Rashid, Christian Schroeder de Witt, Gregory Farquhar, Nan- tas Nardelli, Tim GJ Rudner, Chia-Man Hung, Philip HS Torr, Jakob Foerster, and Shimon Whiteson. The starcraft multi-agent challenge. 2019.
[26] Christian Schroeder de Witt, Tarun Gupta, Denys Makoviichuk, Viktor Makoviychuk, Philip HS Torr, Mingfei Sun, and Shimon Whiteson. Is independent learning all you need in the starcraft multi-agent challenge? arXiv e-prints, pages arXiv-2011, 2020.
[27] John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference on machine learning, pages 1889-1897. PMLR, 2015.
[28] John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Pieter Abbeel. High- dimensional continuous control using generalized advantage estimation. arXiv preprint /50.v:/506.0044 02438, 2015.
[29] John Schulman, F. Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. ArXiv, abs/1 7777006347, 2017.
[30] David Silver, Guy Lever, Nicolas Heess, Thomas Degris, Daan Wierstra, and Martin Riedmiller. Deterministic policy gradient algorithms. In International conference on machine learning. pages 387-395. PMLR, 2014.
[31] Kyunghwan Son, Daewoo Kim, Wan Ju Kang, David Earl Hostallero, and Yung Yi. Qtran: Learning to factorize with transformation for cooperative multi-agent reinforcement learning. In International Conference on Machine Learning, pages 5887-5896. PMLR, 2019.
[32] Peter Sunehag, Guy Lever, Audrunas Gruslys, Wojeiech Marian Czarnecki, Vinicius Zambaldi, Max Jaderberg, Mare Lanetot, Nicolas Sonnerat, Joel Leibo, Karl Tuyls, et al. Value- decomposition networks for cooperative multi-agent learning based on team reward. In Pro- ceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, pages 2085-2087, 2018.
[33] R. S. Sutton, D. Mcallester, S. Singh, and Y. Mansour. Policy gradient methods for reinforcement learning with function approximation. In Advances in Neural Information Processing Systems 12, volume 12, pages 1057-1063. MIT Press, 2000.
[34] Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. 2018.
[35] George Tucker, Surya Bhupatiraju, Shixiang Gu, Richard Turner, Zoubin Ghahramani, and Sergey Levine. The mirage of action-dependent baselines in reinforcement learning, In International conference on machine learning, pages 5015-5024, PMLR, 2018
[36] Yihan Wang, Beining Han, Tonghan Wang. Heng Dong, and Chongjie Zhang. Off-policy multi-agent decomposed policy gradients. arXiv preprint arXiv:2007. /2322, 2020.
[37] Lex Weaver and Nigel Tao. The optimal reward baseline for gradient-basse based reinforcement learning. In Proceedings of the Seventeenth conference on Uncertainty artificial intelligence, pages 538-545, 2001.
[38] Ying Wen, Yaodong Yang, Rui Luo, Jun Wang, and Wei Pan. Probabilistic recursive reasoning for multi-agent reinforcement learning. In International Conference on Learning Representa- tions, 2018
[39] Ying Wen, Yaodong Yang, and Jun Wang. Modelling bounded rationality in multi-agen agent interactions by generalized recursive reasoning. In Christian Bessiere, editor, Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20, pages 414-421. International Joint Conferences on Artificial Intelligence Organization, 7 2020. Main track.
[40] Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforce- ment learning. Machine learning, 8(3-4):229-256 1992.
12

---

[41] Cathy Wu, Aravind Rajeswaran, Yan Duan, Vikash Kumar, Alexandre M Bayen, Sham Kakade, Igor Mordatch, and Pieter Abbeel. Variance reduction for policy gradient with action cetion-dependent factorized baselines. arXiv preprint arXiv: arXiv: 07246, 2018
[42] Yaodong Yang, Rui Luo, Minne Li, Ming Zhou, Weinan Zhang, and Jun Wang. Mean field multi-agent reinforcement learning. In International Conference on Machine Learning, pages 5571-5580. PMLR, 2018.
[43] Yaodong Yang and Jun Wang. An overview of aulti-agent reinforcement learning from game theoretical perspective. arXiv preprint arXiv:201 1.00583, 2020.
[44] Yaodong Yang, Ying Wen, Jun Wang, Liheng Chen, Kun Shao, David Mguni, and Weinan Zhang. Multi-agent determinantal q-learning. International Conference Machine Learning. pages 10757-10766. PMLR, 2020.
[45] Chao Yu, A. Velu, Eugene Vinitsky, Yu Wang. A. Bayen, and Yi Wu. The surprising effectiveness of mappo in cooperative, multi-agent games. ArXiv, abss2103.011 03.01955, 2021.
[46] Haifeng Zhang, Weizhe Chen, Zeren Huang, Minne Li, Yaodong Yang, Weinan Zhang, and Jun Wang. Bi-level actor-critic for multi-agent coordination. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 7332, 2020.
[47] Kaiqing Zhang, Zhuoran Yang, Han Liu, Tong Zhang, and Tamer Basar. Fully decentralized multi-agent reinforcement learning with networked agents. In International Conference on Machine Learning, pages 5872-5881. PMLR, 2018.
[48] Tingting Zhao, Hirotaka Hachiya, Gang Niu, and Masashi Sugiyama, Analysis and improvement of policy gradient estimation. In NIPS, pages 262-26 270. Citeseer, 2011.
[49] Ming Zhou, Yong Chen, Ying Wen, Yaodong Yang, Yufeng Su, Weinan Zhang, Dell Zhang, and Jun Wang. Factorized q-learning for large-scale multi-agent systems. In Proceedings of the First International Conference on Distributed Artificial Intelligence, pages 1-7, 2019.
[50] Ming Zhou, Jun Luo, Julian Villella, Yaodong Yang, David Rusu, Jiayu Miao, Weinan Zhang, Montgomery Alban, Iman Fadakar, Zheng Chen, al. Smarts: Scalable multi-agent rein- forcement learning training school for autonomous driving. arXiv preprint 2rX.v:2010.09776. 2020.
13


Reviews:
[{"review_id": "gMSrj3h1cGQ", "reviewer": "Reviewer_n8hf", "summary": "The paper formally analyzes the variance of multi-agent policy gradients and propose a baseline (and a practical implementation) to reduce the variance. The problem considered is interesting, but the reviewer is concerned about some assumptions used by the authors and is confused about the experimental results. ", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Quality\n(1) Assumption: the authors assume that (1) critics (both centralized and decentralized versions) are accurate and can give exact value estimations, and (2) agents can observe the global state $s$. Based on the second assumption, the joint policy is decomposed as a multiplication of local policies. These two assumptions make the theoretical results provided in this paper less surprising. \n\nFor example, lemma 1-3 can be obtained by using preliminary math given the second assumption. When Q is accurate, the proof of Theorem 1 does not give much insight, which can be finished by introducing a notation for the upper bound for the gradients and advantages. \n\n(2) In Fig. 2, the variance of the proposed method is very large, especially for complex tasks like SMAC and 2-Agent Walker. It is quite strange because the authors claim that they use an *optimal* baseline for MAPG methods. In contrast, state-of-the-art MAPG methods, like stochastic DOP [Wang et al., ICLR 2021], have much smaller variance. \n\nMoreover, the reviewer is confused about the experimental results. MAPPO performs well on 3s_vs_5z, but the authors report a win rate of 0. And, the confidence interval (or variance or std, the authors do not explain what's this in the main text) in Fig. 2 is quite strange. Why does QMIX not have shaded areas? And, for MAPPO w/o OB, why the intervals are very small when the mean value oscillates significantly. This does not make sense unless only two or three seeds are used when drawing the plots. \n\n### Clarity\n(1) Line 43. Not all CTDE PG methods take actions as input to the critic, like COMA. And, the output is the expected return, not the reward.\n(2) Line 142, although MADDPG learns deterministic policies, it is a multi-agent policy gradient method. The statement of \"These methods are not of our interest, as they learn either a deterministic policy or a value function, thus not in the scope of MAPG methods.\" is not accurate.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors didn't discuss the limitations and potential impact of the proposed method.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "dWnPEDhbJKV", "reviewer": "Reviewer_uNWS", "summary": "This paper theoretically studies the variance of multi-agent policy gradients. \n\nIt shows that the extra variance that CTDE MAPG methods have compared to DT methods scales linearly on the number of agents, and quadratically on the local advantage of each agent. \n\nThe paper further proposes the optimal baseline technique to reduce the variance of the MAPG estimator. While the analytic form of the optimal baseline is computational challenging to compute, the assumption that the policies are parameterized by neural networks with softmax layer is used to find a surrogate minimisation objective that is more tractable to compute/approximate. \n\nExperiments are conducted to confirm the effectiveness of the optimal baseline technique. ", "questions": "", "limitations": "", "rating": 7, "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": "Originality: The results presented in this paper are novel as far as I know.\n\nQuality: The theorems and proofs look correct.\n\nClarity: The submission was very clearly written and well orgnaized. \n\nSignificance: I think this work takes an important step towards understanding policy gradient methods for MARL. The theorem 1 and 2 are very insightful. \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "My main concern is that the experimental results are a bit weak in terms of supporting the effectiveness of the optimal baseline technique. It seems to be clear that using the OB can further reduce variance of policy gradients. However, that doesn't seem to be directly translated into an increase of performance, as shown by experiments in SMAC except 2(e). ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "XKdfGSCC7Ep", "reviewer": "Reviewer_uERi", "summary": "This paper carefully analyzes the variance of multi-agent policy gradients and derives the multi-agent baseline estimation with the smallest possible variance, which also indeed leads to a lower variance of policy gradients of the state-of-the-art multi-agent PPO algorithm. ", "questions": "", "limitations": "", "rating": 7, "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": "This paper is clearly written with very intuitive explanations and thorough step-by-step derivations on the multi-agent variance. This is, to the best of my knowledge, the first paper that rigorously studies the variance of multi-agent policy gradient methods (although some empirical studies have been indeed investigated). The theoretical analysis starts from the simplest formulation and carefully goes through all the details, which makes the paper particularly easy to follow.\n\nI enjoy reading this paper a lot and this paper indeed tackles an important problem in MARL. I'm happy to see it get accepted. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Here are a few minor comments.\n\n(1) I couldn't see the confidence interval in Fig2 (e)-(h). I would suggest the authors complete the results in the final version.\n\n(2) I do like the variance analysis. However, these insights only hold under the ideal unbiased case while in practice, the biggest benefit of PPO is due to GAE. The paper could be even stronger if the authors could investigate how to incorporate GAE into the framework. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "4bt7p7-Gga0", "reviewer": "Reviewer_23LJ", "summary": "This paper analyzes the variance of gradient estimates in policy-gradient-based multi-agent RL, specifically for standard multi-agent policy gradient (including both centralized and decentralized training) and for the COMA gradient. The paper then derives an optimal baseline (OB) as well as a tractable surrogate for variance reduction. The non-optimality of the variance of standard MAPG and COMA is shown. Numerically, lower variance of the OB is shown in an analytical example, and performance (in terms of reward and win rate) improvement is shown when the OB is implemented on top of MAPPO and COMA in the discrete-action StarCraft micromanagement scenarios and continuous-action multi-agent MuJoCo.", "questions": "", "limitations": "", "rating": 7, "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": "This is a timely paper, given the increasing attention on multi-agent learning and the existence of a number of empirical methods-centric work that builds on policy-gradient methods for MARL. The style of this work should remind a reader of the single-agent counterpart---Variance Reduction for Policy Gradient with Action-Dependent Factorized Baselines, Wu et al, ICLR 2018 (not cited)---but the analysis and multi-agent context are different enough from the single-agent case that this paper has sufficient originality.\n\nQuality meets the bar (but see the detailed questions below). Overall, this work is a good and rare example of a paper in multi-agent RL that derives an algorithmic improvement from theoretical analysis and also provides empirical validation.\n\nOne point that the authors should clarify: could the left-hand side of the inequaltiy in Theorem 1 be negative, so that the variance of the decentralized estimator is higher than the centralized one? If not, the paper can be improved if the authors include a conceptual explanation for the reason. The centralized one uses the joint $Q(s,\\mathbf{a})$ that receives the joint action as input, while the decentralized one uses $Q^i(s,a^i)$ that itself requires an expectation over the other agents' actions $a^{-i}$. Is there any intuition for one to have higher variance than the other?\n\nThe clarity of the paper's notation is appreciated. Providing reductions to known cases also helps a reader to check correctness.\n\nIt's not clear what the paper means by line 162: \"a MARL problem can be considered as a sum of $n$ RL problems\". At best, it's an unnecessary description of Lemma 1. At worst, it could confuse someone into thinking that decentralized training is sufficient for cooperation in MARL, which is obviously false.\n\nIt appears that the surrogate optimal baseline in equation (9) is not the one the paper actually uses in practice. Instead, the paper uses the form given in lines 249-250, which is consistent with the description in lines 274-275 that says \"firstly, it evaluates the probability measure $x^i_{\\psi^i_{\\theta}}$, and then computes the expectation ...\". It's not very clear how the expression in lines 249-250 is equivalent to equation (9). \n\nIn lines 252-253, it's not clear where the \"importance weight\" arises; perhaps the authors do not mean it in the sense of importance sampling.\n\nThe claim in line 314 that OB improves MAPPO on all four tasks is incorrect: there is no significant difference between MAPPO with OB and without OB in 3-agent Hopper, Figure 2a.\n\n\nMinor points:\n1. There are numerous typos that the authors should fix: line 37 \"single-agnet\", line 236 \"this this\", line 245 \"Hereafater\", Table 1 caption \"a numerical toy exmaple tha shows\", line 272 \"This gives as an estimator\", line 279 \"continuosu\"\n\n---------------------------------\nPost rebuttal: The authors have responded in detail and addressed my questions, and I am keeping the score for this good paper.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper does mention that deterministic methods and value-function based methods are not in scope.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies how to reduce the variance of stochastic gradient estimates in policy gradient approaches to Multi-agent Reinforcement Learning (MARL). Focusing on the popular Centralized Training Decentralized Execution setting, the authors provide a theoretical analysis that quantifies excess variance and connects it to the number of agents and agents' local advantages. They build on these insights by empirically showing how these insights affect COMA, and by deriving a new optimal baseline (OB) which is empirically validated in StarCraft and multi-agent MUJOCO environments.

Reviewers were positive about the importance of the problem addressed in this work. They largely agreed that the question of policy gradient variance has not been widely studied in the MARL community, but has important implications and potential for impact. The paper was considered clear and well written.

At the same time, several concerns were raised. In particular, the assumptions of the analysis are idealised, and findings do not always translate into corresponding empirical gains. 

During the rebuttal and discussion phase, reviewers were generally satisfied with the clarifications provided by the authors and recommend acceptance. Unfortunately, the most negative reviewer did not engage beyond the initial review. Therefore, the AC examined the concerns raised in the initial review and judged these as sufficiently addressed by the authors.

The paper is assessed as meeting the bar for acceptance, based on the important theoretical insights and high potential for impact on the MARL community. The authors are strongly encouraged to take on board all reviewer comments to further improve clarity and potential for impact in the camera ready version.
Decision: Accept (Poster)