DOP: Off-Policy Multi-Agent Decomposed Policy Gradients
Authors: Yihan Wang
Beining Han
Tonghan Wang
Heng Dong
Chongjie Zhang
Venue: ICLR 2021 Poster (2021)
Keywords: Multi-Agent Reinforcement Learning
Multi-Agent Policy Gradients

Abstract: Multi-agent policy gradient (MAPG) methods recently witness vigorous progress. However, there is a significant performance discrepancy between MAPG methods and state-of-the-art multi-agent value-based approaches. In this paper, we investigate causes that hinder the performance of MAPG algorithms and present a multi-agent decomposed policy gradient method (DOP). This method introduces the idea of value function decomposition into the multi-agent actor-critic framework. Based on this idea, DOP supports efficient off-policy learning and addresses the issue of centralized-decentralized mismatch and credit assignment in both discrete and continuous action spaces. We formally show that DOP critics have sufficient representational capability to guarantee convergence. In addition, empirical evaluations on the StarCraft II micromanagement benchmark and multi-agent particle environments demonstrate that DOP outperforms both state-of-the-art value-based and policy-based multi-agent reinforcement learning algorithms. Demonstrative videos are available at https://sites.google.com/view/dop-mapg/.

Published as a conference paper at ICLR 2021
DOP: OFF-POLICY MULTI-AGENT DECOMPOSED POLICY GRADIENTS
Yihan Wang', Beining Han", Tonghan Wang", Heng Dong, Chongjie Zhang Institute for Interdisciplinary Information Sciences Tsinghua University, Beijing, China (memorys wwwliyilille 1 ces, bould dinghan, httphhaannnnngaangggggggg 996, drdhii @@gmai coom chongj i eê wwwnguuu..............o www.gh..eduu........
ABSTRACT
Multi-agent policy gradient (MAPG) methods recently witness vigorous progress. However, there is a significant performance discrepancy between MAPG meth- ods and state-of-the-an art multi-agent value-based approaches. this paper, we investigate causes that hinder the performance of MAPG algorithms and present a multi-agent decomposed policy gradient method (DOP). This method introduces the idea of value function decomposition into the multi-agent actor-critic framework. Based on this idea, DOP supports efficient off-policy learning and addresses the issue of and continuous action spaces. We formally show that DOP critics have sufficient representational capability to guarantee convergence. In addition, empirical evalu- ations on the StarCraft II micromanagement benchmark and multi-agent particle environments demonstrate that DOP outperforms both state-of-the-ar value-based and policy-basee multi-agent reinforcement learning algorithms. Demonstrative videos are available at http::/siiissggggleeoeeeo com/ view/ whtp///iiw///o///e//e// dop-mapg/
mismatch and credit assignment in both discrete
INTRODUCTION
Cooperative multi-agent reinforcement learning (MARL) has achieved great progress in recent
years (Hughes et al. 2018 Jaques et al., 2019 Vinyals et al. 2019 Zhang et al. 2019 Baker et al.
2020
Wang al. 2020c). Advances in valued-based MARL (Sunehag al. 2018 Rashid et al.
2018 Son et al. 2019 Wang et al. 2020e) contribute significantly to the progress, achieving state-of- challenging tasks, such as StarCraft II micromanagement (Samvelyan et al., 2019). However, these based methods present major challenge for stability and convergence multi-agent settings (Wang et al. 2020aa,, which is further exacerbated in continuous action spaces. Policy gradient methods hold great promise to resolve these challenges. MADDPG (Lowe et al. 2017) and COMA (Foerster et al. 2018) are two representative methods that adopt the paradigm of centralized critic with decentra ized actors (CCDA), which not only deals with the issue of non- stationarity (Foerster et al. 2017 Hernandez-Leal et al. 2017) by conditioning the centralized critic on global history and actions but also maintains scalable decentralized execution via conditioning policies on local history. Several subsequent works make improvements to the CCDA framework by introducing the mechanism of recursive reasoning (Wen et al. 2019) or attention (Igbal & Sha 2019).
the-art performance
Despite the progress, most of the multi-agent policy gradient (MAPG) methods do not provide satisfying performance, e.g., significantly underperforming value-based methods on benchmark tasks (Samvelyan et al. 2019). In this paper, we analyze this discrepancy and pinpoint three major issues that hinder the performance of MAPG methods. (1) Current stochastic MAPG methods do not support off-policy learning, partly because using common off-policy learning techniques is computationally expensive in multi-agent settings. (2) In the CCDA paradigm, the suboptimality of one agent's 's policy can propagate through the centralized joint critic and negatively affect policy learn- ing of other agents, causing catastrophic miscoordination, which we call centralized- decentralizee mismatch (CDM). (3) For deterministic MAPG methods, realizing efficient credit assignment (Tumer al. 2002 Agogino & Tumer 2004) with single global reward signal largely remains challenging.
"Equal Contribution. Listing order is random.

---

Published as a conference paper at ICLR 2021
In this paper, find that these problems can be addressed by introducing the idea of value decompo- sition into the multi-agent actor-critic framework and learning a centralized but factorized critic. This framework decomposes the centralized critic as weighted linear summation of individual critics that condition on local actions. This decomposition structure not only enables scalable learning on the critic, but also brings several benefits. It enables tractable off off-policy evaluations of stochastic policies, attenuates the CDM issues, and also implicitly learns an efficient multi-agent credit assignment. Based on this decomposition, we develop efficient off-policy multi-agent decomposed policy gradient methods for both discrete and continuous action spaces.
drawback of an linearly decomposed critic is its limited representational capacity (Wang et al. 2020b), which may induce bias in value estimations. However, we show that this bias does not violate the policy improvement guarantee of policy gradient methods and that using decomposed critics can largely reduce the variance in policy updates. In this way, a decomposed critic achieves great bias-variance tra
We evaluate our methods on both the StarCraft II micromanagement benchmark (Samvelyan et al. 2019) (discrete action spaces) and multi-agent particle environments (Lowe et al. Mordatchh & Abbeel 2018) (continuous action spaces). Empirical results show that DOP is very stable across different runs and outperforms other MAPG algorithms by a wide margin. Moreover, to our best knowledge, stochastic DOP provides the first MAPG method that outperforms state-of-the-an aht valued- based methods in discrete-action benchmark tasks.
Related works on value decomposition methods. In value-based MARL, value decomposi- tion (Guestrin et al., [002b] Castellini et al.) 2019) is widely used. These methods learn local Q-value functions for each agent, which are combined with a learnable mixing function to produce global action values. In VDN (Sunehag et al.] 2018), the mixing function is an arithmetic summa- tion. QMIX (Rashid et al. 2018: 2020) proposes a non -on-linear monotonic factorization structure. QTRAN (Son et al. 2019) and QPLEX (Wang et al. (2220) further extend the class of value func- tions that can be represented. NDQ (Wang al. 2020e) addresses the miscoordination problem by learning nearly decomposable architectures. A concurrent work (de Witt et al., 2020) finds that decomposed centralized critic in QMIX style can improve the performance of MADDPG for learning in continuous action spaces. In this paper, we study how and why linear value decomposition can enable efficient policy-based learning in both discrete and continuous action spaces. In Appendix F, we discuss how DOP is related to recent progress in multi-agent reinforcement learning and provide detailed comparisons with existing aalti- policy gradient methods.
2 BACKGROUND
We consider fully cooperative multi-agent tasks that can be modelled as Dec-POMDP (Oliehoek) al. 2016) (= S, A, P, R, f2, O, n, where I is the finite set of agents, y E [0. 1) is the discount factor, and E S is the true state of the environment. At each timestep, each agent i receives an observation 0g E Ω drawn according to the observation function O(s, and selects an action a; A, forming joint action
A", leading to next state s' according to the transition function P(s"|s, |s, a) and a reward r = R(s, a) shared by all agents. Each agent learns a policy n. <a(a//Ts m;; 0,), which is parameterized by 0, and conditioned
the local history T; E T (A x A)". The joint policy π, with parameters = (01,... Bn), induces a joint action-value function: Q (T.aa)=Eso....oc))
D2 7 R(s,, ar)l so s, ag a, πτ.. We consider both discrete and continuous action spaces, for which stochastic and deterministic policies are learned, respectively. To distinguish deterministic policies, we denote them by μ (UI,...,,,u))
Multi-Agent Policy Gradients The centralized training with decentralized execution (CTDE) paradigm (Foerster et al.) 2016 Wang et al., 2020d) has recently attracted attention for its abil- ity to address non-stationarity while maintaining decentralized execution. Learning a centralized critic with decentralized actors (CCDA) an efficient approach that exploits the CTDE paradigm. MADDPG and COMA are two representative examples. MADDPG (Lowe et al.] 2017) learns deterministic policies in continuous action spaces and uses the following gradients to update policies:
g = Ey BnDD
Σ Vo. Quae (aa
(1)
2

---

Published as a conference paper at ICLR 2021
and D is replay buffer. COMA (Foerster et al. 2018 updates stochastic policies using the gradients:
g Ex Σ V. log (a
where AT a) Qio (T, a) Ea; QToe (T, (a-;, counterfactual advantage (a.;; is the joint action other than agent that deals with the issue of credit assignment and reduces variance.
ANALYSIS
In this section, investigate challenges that limit the performance of state-of-the-ar multi-agent policy gradient methods.
3.1 OFF-POLICY LEARNING FOR MULTI-AGENT STOCHASTIC POLICY GRADIENTS
Efficient stochastic policy learning in single-agent settings relies heavily using off-policy data (Ei licrap et al. 2015: Wang et al. 2016 Fujimoto et al. 2018 Haarnoja et al. 2018). which is not supported by existing stochastic MAPG methods (Foerster et al.) 2018). In the CCDA frame- work, off-policy policy evaluation-estimeee
Qiot from data drawn from behavior policies 0(3, .B....... .. (n,) encounters major challenges. Importance sampling (Meuleau al. 2000
Jie & Abbeel 2010 Levine & Koltun 2013) is simple way to correct for the discrepancy between π
and B. but, it requires computing II,
[.la; 7T) whose variance grows exponentially with the number (.(a;17)
of agents in multi aulti-agent settings. An alternative is to extend the tree backup technique (Precup et al.)
2000; Munos et al. 2016) to multi-agent settings and use the k-step tree backup update target for
training the critic:
7 (MAm(aa))) Ina + En Qio Qial 10oo((T.))))) (T,, at)l:
y = Qio (T.
(3)
t=
where To = ag a. However, the complexity of computing E,, 'Q (T++1, )) is 0(14["), which becomes intractable when the number of agents is large. Therefore, it is challenging to develop off- off-policy stochastic MAPG methods.
3.2 THE CENTRALIZED CENTRALIZED-DECENTRRLLZEE MISMATCH ISSUE
In the centralized critic with decentralized actors (CCDA) framework, agents learn individual policies, Ty (a, O,), conditioned on the local observation-action history. However, the gradients for updating these policies are dependent on the centralized joint critic, Qh (T, a) (see Eq. D and 2p. which introduces the influence of actions of other agents. Intuitively, gradient updates will move an agent in the direction that can increase the global Q value, but the presence of other agents' actions incurs large variance the estimates of such directions.
Formally, the variance of policy gradients for agent i at (T;, aa) is dependent other agents' actions:
Vara..>m.: ( (a;, Vo, log h; (a:(m))
(4)
-Vara 1 (T, (a;, a-))) oVo, log Ti (a:laa))) log (a,l:)
where Vara.; [QT (a,, ])) can be very large due the exploration or suboptimality of other agents' policies, which may cause suboptimality in individual policies. For example, suppose that the optimal joint action under a== (af.... .......aa a. When Ea.,< Q (T, (aī a.))) ] < 0, nz = will decrease, possibly resulting in suboptimal क; This becomes problematic because a negative feedback loop created, in which the joint critic affected by the suboptimality of agent which
disturbs policy updates of other agents. We call this issue centralized-deccenratiiaee mismatch (CDM).
Does CDM occur in practice for state-of- thete-- algorithms? To answer this question, we carry out a case study in Sec. 5. We can see that the variance of DOP gradients is significantly smaller than COMA and MADDPG (Fig. left). This smaller variance enables DOP to outperform other algorithms (Fig. 2 middle). We will explain this didactic example in detail in Sec. [.1 In Sec. [.2
[533 we further show that CDM exacerbated in sequential decision decision-making settings, causing divergence even after netr-optimal strategy has been learned.
3

---

Published as a conference paper at ICLR 2021
3.3 CREDIT ASSIGNMENT FOR MULTI-AGENT DETERMINISTIC POLICY GRADIENTS
MADDPG (owe et al.
2017 and MAAC (Igbal & Sha 2019) extend deterministic policy gradient Lillierap al. 2015) to multi-agent settings, enabling efficient off-
algorithms (Silver et al. policy learning in continuous action spaces. However, they leave the issue of credit assignment (Tumer al. 2002 Agogino & Tumer 2004) largely untouched in fully cooperative settings, where agents learn policies from a single global reward signal. In stochastic cases, COMA assigns credits by designing a counterfactual baseline (Eq. 2 However, it is not straightforward to extend COMA to deterministic policies, since the output of polices is no longer probability distribution. As result, it remains challenging to realize efficient credit assignment in deterministic cases.
2014
DECOMPOSED OFF-POLICY POLICY GRADIENTS
To address the limitations of existing MAPG methods discussed in Sec. 3 we introduce the idea of value decomposition into the multi-agent actor-critic framework and propose Decomposed Off- Policy policy gradient (DOP) method. We factor the centralized critic as a weighted summation of individual critics across agents:
(5) where o and d; are parameters of the global and local Q functions, respectively, and k; 2 0 and b are generated by learnable networks whose inputs are global observation-action histories. In the following sections, we show that this linear decomposition helps address existing limitations of previous methods. A concern is the limited expressivity of linear decomposition (Wang et al.) 2020b), which may introduce bias in value estimations. We will show that this limitation does not violate the policy improvement guarantee of DOP.
(T, (T, b(T).
Fig. D shows the architecture for learning decomposed critics. We learn individual critics 0.at by backpropagating gradients from global TD updates dependent on the joint global reward, i.e. Q is learned implicitly rather than from any reward specific to agent i. We enforce & 2 O by applying an abso- lute activation function at the last layer of the network. The network structure is described in detail in Appendix
2
TT, a)
TD loss
b
(k,, kn)
0 (I,
Q (T, an)
Based on the critic decomposition learning, the following sec- tions will introduce decomposed off-policy policy gradients for learning stochastic policies and deterministic policies, respec- tively. Similar to other actor-critic methods, DOP alternates between policy
Critic 1
Critic
eetiiiitinntttmtintng the value function for a policy-and and policy improvement -uinn the value function update the policy (Barto et al. 1983).
Figure 1: DECOMPOSED critic.
4.1 STOCHASTIC DECOMPOSED OFF-POLICY POLICY GRADIENTSS
For learning stochastic policies, the linearly decomposed critic plays an essential role in enabling tractable multi-agent tree backup for off-policy policy evaluation and attenuating the CDM issue while maintaining provable policy improvement.
4.1.1 OFF-POLICY LEARNING
Policy Evaluation: Train the Critic As discussed in Sec. 3.1 using tree backup (Eq. 3 to carry out
multi-agent off off-policy policy evaluation requires calculating Ex [Q (T++1: -). which needs O(IA(")
steps of summation when a joint critic is used. Fortunately, using the linearly decomposed critic, DOP reduces the complexity of computing this expectation to O(n]A)):
E Q (T, = (T) 1Q, (T, B(T).
making the tree backup technique tractable (detailed proof can be found in Appendix A.1). Another challenge of using multi-agent tree backup (Fqq. 3) is that the coefficient e II Am (ail7) decays
4

---

Published as a conference paper at ICLR 2021
as gets larger, which may lead to relatively lower training efficiency. To solve this issue, propose to mix off- off-policy tree backup updates with on-policy (A) updates to trade off sample efficiency and training efficiency. Formally, DOP minimizes the following loss for training the critic:
(()) kLg DOP TB
(Ø) + (1 Co (Ø)
where x is scaling factor, 3 is the joint behavior policy, and Φ is the parameters of the critic. The first loss item is 2g CDOP-TB (Ø) Ey PO - Qiae a)) where y pOP-TB is the update target of the proposed k-step decomposed multi-agent tree backup algorithm:
4-1
y DOP-TB = -hhoe ( (T, a)
+
Σ t-0
r'ce
Tt +
E (T (TaI1 b(To.1) 1)- Qio (T,, a1)
(8)
Here, o' is the parameters of a target critic, and B(117)). The second loss item is Co (Ø) Ex Ex Qloe (T, a)) where you is the on-policy update target as in TD()):
you = Qi a) + (()) re + 72 (Te11, a4+1) - Qiae ( Te, ai)
(9)
In practice, we use two buffers, an on-policy buffer for computing (x) and an off off-policy buffer for estimating 23 CDOP-TB (o).
Policy Improvement: Train Actors Using the linearly decomposed critic architecture, we can derive the following on-policy policy gradients for learning stochastic policies:
= E EE log (u: (,))) (T, a.)]
(10)
In Appendix A.2
we provide the detailed derivation and off-policy version of stochastic policy
gradients. This update rule reveals two important insights. (1) With a linearly decomposed critic,
each agent's policy update only depends on the individual critic Q (2) Learning the decomposed critic implicitly realizes multi-agent credit assignment, because the individual critic provides credit information for each agent to improve its policy in the direction of increasing the global expected return. Moreover, Eq. 10 is also the policy gradients when assigning credits via the aristocrat
utility (Wolpert& & Tumer (2022) (Appendix A.2). Eq, and I0 form the of our DOP algorithm for learning stochastic policies, which we call stochastic DOP and is described detail in Appendix
The CDM Issue occurs when decentralized policies' suboptimality exacerbates each other through the joint critic. As an agent's 's stochastic DOP gradients do not rely on the actions of other agents, they attenuate the effect of CDM. We empirically show that DOP can reduce variance in policy gradients in Sec. 5.1 and can attenuate the CDM issue in complex tasks in Sec. 5.2.1
4.1.2 STOCHASTIC DOP POLICY IMPROVEMENT THEOREM
In this section, we theoretically demonstrate that stochastic DOP can converge to local optimal despite the fact that linearly decomposed critic has limited representational capability. Since accurate analysis for a complex function approximator (c.g.. neural network) difficult, we adopt several mild assumptions used in previous work (Feinberg et al. 2018 Degris et al.) 2012).
We first show that the linearly decomposed structure ensures that the learned local value functions Q (T, ax) preserve the order of QT (T, as) = Ea., π (a= (T,a) a) for a wide range of function class.
Fact 1. Under mild assumptions, when value evaluation converges, VT,, Q satisfies that = QT 2 (T. VT, az a.,
QT 2 QF (T.
well more detailed discussion of its implications. Furthermore, we prove the following proposition to show that policy improvement can be guaranteed as long as the function class expressed by Q is sufficiently large and the loss of critic training is minimized.
Detailed proof of Fact [ can be found in Appendix C.I
5

---

Published as a conference paper at ICLR 2021
Proposition 1. Suppose the function class expressed by Qº (T, 0z) is sufficiently large (e.g. neural networks) and the following loss L(ő) is minimized
L(Ø) Σ ( -ooe (T
where aT) = ki (T, a.) + b(T). Then, we have
g g= ET E, Ve, log ma
EE E, log (.laalt;::)) (T, (T,
which means stochastic DOP policy gradients are the same as those calculated using centralized critics (Eq. -. Therefore, policy improvement is guaranteed.
The proof can be found in Appendix which is inspired by Wang et al. (2020a).
4.2
DETERMINISTIC DECOMPOSED OFF-POLICY POLICY GRADIENTS
4.2.1
OFT-POLICY LEARNING
To enable efficient learning with continuous actions, we propose deterministic DOP. As in single- agent settings, because deterministic policy gradient methods avoid the integral over actions, it greatly cases the cost of off-policy learning (Silver al. 2014). For policy evaluation, we train the critic by minimizing the following TD loss:
( = (m (r++ ( (T ( - Qio a.)) )
(II)
where D is replay buffer, and ø', H' are the parameters of the target critic and actors, respectively. For policy improvement, we derive the following deterministic DOP policy gradients:
g= ETwD E,k(T)Vo, V.) Of (T, (=)aa==((((()))
(12)
Detailed proof can be found in Appendix B.1 Similar to the stochastic case, This result reveals that updates of individual deterministic policies depend on local critics when linearly decomposed critic is used. Based on Eq. 11 and Eq. [2 we develop the DOP algorithm for learning deterministic
policies in continuous action spaces, which is described in Appendix D and called deterministic DOP.
4.2.2 REPRESENTATION CAPACITY OF DETERMINISTIC DOP CRITICS
In continuous and smooth environments, capability to represent Q values in the proximity of μ(T), VT with a bounded error. For simplicity, denote Os(T) = {al a μu(T) ||25 8). Fact Assume that VT, a, a' E (&()). V a) - V a') 1| L a a-aa a' 1|2. The estimation error of DOP critic can be bounded by O(L8)) Os(T),
first show that DOP critic has sufficient expressive
Detailed proof can be found in Appendix D Here we assume that the gradients of Q-values with re- spect to actions are Lipschitz smooth under the deterministic policy μ.. This assumption is reasonable given that Q-values of most continuous environments with continuous policies are rather smooth.
We further show that when Q-values in the proximity of (u(T), ) VT are well estimated with a bounded error, deterministic DOP policy gradients are good approximation the true gradients (Eq. [ Approximately, Qu aT. V k, (T) Q (T,a,) ( Vi when 8 1. For detailed proof, we refer readers to Appendix D
5 EXPERIMENTS
We design experiments to answer the following questions: (1) Does the CDM issue commonly
exist and can decomposed critics attenuate it? (Sec. 5.1 5.2.1 and 5.3) (2) Can our decomposed multi-agent tree backup algorithm improve the efficiency off policy learning? (Sec. 5.2.1) (3)
Can deterministic DOP learn reasonable credit assignment? (Sec. 5.3) (4) Can DOP outperform state-of-fe of-th-rrtt MARL algorithms? For evaluation, all the results are averaged over 12 different random seeds and are shown with 95% confidence intervals.

---

Published as a conference paper at ICLR 2021
Machns LOOR BRA
COMS
Mackadi (owk)
COPA
Secthetic DOP (uni
COPA
1000
3000
110-136661111 11.114
-30
42-15 4. 48
4 004-48
32 6/66
Figure 2: Bias-variance trade-off of DOP on the didactic example. Left: gradient variance; Middle: Performance; Right: Average bias in Q estimationn; Right-bottom: bottom: the element in ith row and jth column is the local Q value learned by DOP for agent taking action j.
(Ours!
OPLEX
OTBAN
VIN
QMIX
COMA
100
100
100
Te0 Witn
50
50
Text
(mill
100
Tmml Win %%
Tox Win
(m/)
0mi0
(mill
Figure 3: Comparisons with baselines on the SMAC benchmark.
5.1 DIDACTIC EXAMPLE: THE CDM ISSUE AND BIAS- VARIANCE TRADE-OFF
We use didactic example to demonstrate how DOP attenuates CDM and achieves bias-variance trade-off. In state-less game with 3 agents and 14 actions, if agents take actioni, 5, 9, respectively, they get a team reward of 10; otherwise 100. We train stochastic DOP, COMA, and MADDPG for 10K timesteps and show the gradient variance, value estimation bias, and learning curves in Fig. 2 Gumbel-Softmal trick (Jang et al. 2017 Maddison et al. 2017 is used to enable MADDPG to learn in discrete action spaces.
Fig. 2 right shows the average bias in the estimations of all Q values. We see that linear decomposition introduces extra estimation errors. However, the variance of DOP policy gradients is much smaller than other algorithms (Fig. leeft). As discussed Sec. S.2. large variance of other algorithms is due to the CDM issue that undecomposed joint crities affected by actions of all agents. Free from the influence of other agents, DOP preserves the order of local Q-values (bottom of Fig. riight and effectively reduces the variance of policy gradients. In this way, DOP sacrifices value estimation accuracy for accurate and low- variacceee policy gradients, which explains why it can outperform other algorithms (Fig. 2 middle).
5.2 DISCRETE ACTION SPACES: THE STARCRAFT II MICROMANAGEMENT BENCHMARK
We evaluate stochastic DOP on the challenging SMAC benchmark (Samvelyan al. 2019) for its high control complexity. We compare our method with the state-of-the-ar multi-agent stochastic policy gradient method (COMA), value-based methods (VDN, QMIX, QTRAN (Son et al. 2019)) NDQ Wang et al. 2020e), and QPLEX (Wang et al. 2220b)), exploration method (MAVEN, Mahajan ctt al. 2019)), and role-based method (ROMA, Wang et al. (2020ch). For stochastic DOP, we fix the hyperparameter setting and network structure in all experiments which are described in Appendix H For baselines, we use their default hyperparameter settings that have been fine-tuned on the SMAC benchmark. Results are shown in Fig. 3 Stochastic DOP significantly outperforms all the baselines by a wide margin. To our best knowledge, this is the first time that a MAPG method has significantly better performance than oate-of-theear value-hased methods.
7

---

Published as a conference paper at ICLR 2021
Stochastic DOP (Ours)
On-Policy DDP
Off-elicy DDP (em1) 2x3r
DOP Tree Backup
NKN
100
300
1000
Tan: win
50
-0
Tex:
16
[m]]
(mill
10m vs 12m
Mt many banwing
100
100
100
Ten:: Wit
50
30
Test
10
[m/)
Tmmi
(m/l))
Figure 4: Comparisons with ablations on the SMAC benchmark.
5.2.1 ABLATIONS
Stochastic DOP has three main components: (a) off-policy policy evaluations, (b) the decomposed critic, and (c) decomposed multi-agent tree backup. By design, component (a) improves sample efficiency, component (b) can attenuate the CDM issue, and component (c) makes off off-policy policy evaluations tractable. We test the contribution of each component by carrying out the following ablation studies.
Off-Policy Learning In method, controls the "off- ooff-policyness of training. For DOP, set to 0.5. To demonstrate the effect of off-policy learning, we change x to 0 and 1 and compare the performance. In Fig. 4 we can that both DOP and off-policy DOP perform much better than the on-policy version (x=0), highlighting the importance of using off-policy data. Moreover, purely off-policy learning generally needs more samples achieve similar performance to DOP. Mixing with on-policy data can largely improve training efficiency.
The CDM Issue On-Policy DOP uses the same decomposed critic structure DOP, but is trained only with on-policy data and does not use tree backup. The only difference between On-Policy DOP and COMA is that the former one uses decomposed joint critic. Therefore, given that a COMA critic has a more powerful expression capacity than a DOP critic, the outperformance of On-Policy DOP against COMA shows the effect of CDM. COMA is not stable and may diverge after near-optimal policy has been learned. For example, on map so moo_aan_bbaae banel COMA policies degenerate after 2M steps. In contrast, On-Policy DOP can converge with efficiency and stability.
Decomposed Multi-Agent Tree Backup DOP with Common Tree Backup (DOP without component (c)) is the same DOP except that E, [ (T. is estimated by sampling 200 joint actions from т. Here, we estimate this expectation by sampling because direct computation is intractable (for example, 20 summations agents increases, sampling becomes less efficient, and common tree backup performs even worse than On-Policy DOP. In contrast, DOP with decomposed tree backup can quickly and stably converge using a similar number of summations.
needed the map MMM). Fig. 4 shows that when the number of
5.3 CONTINUOUS ACTION SPACES: MULTI-AGENT PARTICLE ENVIRONMENTS
We evaluate deterministic DOP on multi-agent particle environments (MPE, (Mordatch & Abbeel 2018)), where agents take continuous actions in continuous spaces. We compare our method with MADDPG (Lowe et al. 2017) and MAAC (Igbal & Sha 2019). Hyperparameters, and the network structure are fixed for deterministic DOP across experiments, which are described in Appendix H
The CDM Issue We use task Aggregation an example to show that deterministic DOP attenuates the CDM issue, In this task, 5 agents navigate to one landmark. Only when all agents reach the landmark will they get a team reward of 10 and successfully end the episode; otherwise, an episode ends after 25 timesteps and agents get a reward of -10. Aggregation is a typical example where other agents' actions can influence an agent's 's local policy through an undecomposed joint critic. Intuitively, as long as one agent does not reach the landmark, the centralized Q value is negative, confusing other agents who get to the landmark. This intuition is supported by the empirical results
8

---

Published as a conference paper at ICLR 2021
Determmistic DOP 1Duist
MA03PG
MAAC
Push Clocwiis
Push Counturcackeise
10
0.00
0.16
0.15
0.20
025
mm
Figure 5: Left and middle: performance comparisons with COMA and MAAC on MPE. Right: The learned credit assignment mechanism task Mill& by deterministic DOP.
shown in Fig. 5e methods with undecomposed critics can find rewarding configurations but then quickly diverge, while DOP converges with stability.
Credit Assignment We task Mill show that DOP can learn effective credit assignment mechanisms. In this task, 10 agents need to rotate a millstone clockwise. They can push the millstone clockwise counterclockwise with force between 0 and If the millstone's angular velocity, w, gets greater than 30, agents are rewarded 3 per step. If w exceeds 100 in 10 steps, the agents win the episode and get reward of 10; otherwise, they lose and get punishment -10 Fig. riight shows that deterministic DOP can gradually learn reasonable credit assignment during training, where rotating the millstone clockwise has much larger Q-values. This explains why deterministic DOP outperforms previous state-of-the-art deterministic MAPG methods, shown in Fig. middle.
CLOSING REMARKS
This paper pinpointed drawbacks that hinder the performance of state-of-the-ar MAPG algorithms: on-policy learning of stochastic policy gradient methods, the centralizee-ddeeenrrliieee mismatch problem, and the credit assignment issue deterministic policy learning. We proposed decomposed actor-critic methods (DOP) to address these problems. Theoretical analyses and empirical evaluations demonstrate that DOP can achieve stable and efficient multi-agent off-policy learning.
ACKNOWLEDGMENTS
We would like to thank the anonymous reviewers for their insightful comments and helpful sugges- tions. This work is supported in part by Science and Technology Innovation 2030 "New Generation Artificial Intelligence" Major Project (No. 2018AAA0100904), and grant from the Institute of Guo Qiang, Tsinghua University.
REFERENCES
Adrian K. Agogino and Kagan Tumer. Unifying temporal and structural credit assignment problems. In Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems Volume 2, AAMAS '04, pp. 980-987, USA, 2004. IEEE Computer Society. ISBN 1581138644.
Bowen Baker, Ingmar Kanitscheider, Todor Markov, Yi Wu, Glenn Powell, Bob McGrew, and Igor Mordatch. Emergent tool use from multi-agent autocurricula. In Proceedings of the International Conference on Learning Representations (ICLR), 2020.
A. G. Barto, R. S. Sutton, and C. W. Anderson. Neuronlike adaptive elements that solve difficult learning control problems. IEEE Transactions on Systems, Man, and Cybernetics, SMC-13(5): 834-846, 1983.
Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemyslaw Debiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Chris Hesse, et Dota 2 with large scale deep reinforcement learning, arXiv preprint arXiv: 1912::9912006800 2019.
Lucas Cassano, Kun Yuan, and Ali H Sayed. Multi-agent fully decentralized value function learning with linear convergence rates. arXiv preprint arXiv: 18100077,, 2018.

---

Published as a conference paper at ICLR 2021
Jacopo Castellini, Frans A Olichock, Rahul Savani, and Shimon Whiteson. The representational capacity of action-value networks for multi-agent reinforcement learning. In Proceedings of the 18th International Conference Autonomous Agents and MultiAgent Systems, pp. 1862-1864. International Foundation for Autonomous Agents and Multiagent Systems, 2019.
Abhishek Das, Théophile Gervet, Joshua Romoff, Dhruv Batra, Devi Parikh, Mike Rabbat, and Joelle Pineau. Tarmac: Targeted multi-agent communication. International Conference on Machine Learning, pp. 1538-1546, 2019.
Christian Schroeder de Witt, Bei Peng, Alexandee Kamienny, Philipp Torr, Wendelin Böhmer, and Shimon Whiteson. Deep multi-agent reinforcement learning for decentralized continuous cooperative control. arXiv preprini wrXiv:2003.06709 2020.
Thomas Degris, Martha White, and Richard Sutton. Off-policy actor-critic In Proceedings of the 29th International Coference International Conference Machine Learning, pp. 179-186, 2012.
Vladimir Feinberg, Alvin Wan, Ion Stoica, Michael Jordan, Joseph E Gonzalez, and Sergey Levine. Model-based value estimation for efficient model-free reinforcement learning. arXiv preprini arXiv:1803.00101, 2018.
Jakob Foerster, Ioannis Alexandros Assael, Nando de Freitas, and Shimon Whiteson. Learning to communicate with deep multi-agent reinforcement learning. In Advances in Neural Information Processing Systems, pp. 2137-2145, 2016.
Jakob Foerster, Nantas Nardelli, Gregory Farquhar. Triantafyllos Afouras, Philip HS Torr, Pushmeet Kohli, and Shimon Whiteson. Stabilising experience replay for deep multi-agent reinforcement learning. In Proceedings of the 34th International Conference on Machine Learning-Volle 70, pp. 1116-111111 1155. JMLR. org, 2017.
Jakob N Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson. Counterfactual multi-agent policy gradients. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
Scott Fujimoto, Herke Hoof, and David Meger. Addressing function approximation error in actor- critic methods. In International Conference on Machine Learning, pp. 1587-1596, 2018.
Carlos Guestrin, Daphne Koller, and Ronald Parr. Multiagent planning with factored mdps. In Advances in neural information processing systems, pp. 1523-1530, 2002a.
Carlos Guestrin, Michail Lagoudakis, and Ronald Parr. Coordinated reinforcement learning. In ICML, volume pp. 227-234. Citeseer, 2002b.
Jayesh K Gupta, Maxim Egorov, and Mykel Kochenderfer. Cooperative multi-agent control using deep reinforcement learning. In International Conference on Autonomous Agents and Multiagent Systems, pp. 66-83. Springer, 2017.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 18861-8700 Stockholmsmässan, Stockholm Sweden, 10-15 Jul 2018. PMLR. URL http://pweeeeiin..mmmeer/s/////s
hbm
Pablo Hernandez- Leal, Michael Kaisers, Tim Baarslag, and Enrique Munoz de Cote. A survey of learning in multiagent environments: Dealing with non-stationarity. ArXiv, abs/1 abs/1707.ne 001110770999999 ,09183, 2017.
Edward Hughes, Joel Z Leibo, Matthew Phillips, Karl Tuyls, Edgar Dueñez-Guuzzn Guzman, Antonio García Castañeda, lain Dunning, Tina Zhu, Kevin McKee, Raphael Koster, al. Inequity aversion improves cooperation in intertemporal social dilemmas. In Advances in Neural Information Processing Systems, pp. 3330-3340, 2018.
Shariq Iqbal and Fei Sha. Actor-attention-criti for multi-agent reinforcement learning. In Interna- fional Conference on Machine Learning, pp. 2961-2970, 2019.
10

---

Published as a conference paper at ICLR 2021
Max Jaderberg, Wojciech M Czarnecki, lain Dunning, Luke Marris, Guy Lever, Antonio Garcia Castaneda, Charles Beattie, Neil C Rabinowitz, Ari S Morcos, Avraham Ruderman, et al. Human- level performance in 3d multiplayer games with population- basedd reinforcement learning. Science, 364(6443):859-866 865, 2019.
Eric Jang, Shixiang Gu, and Ben Poole. Proceedings of the International Conference on Learning Representations (ICI.), 2017.
Categorical reparameterizatioon with gumbel-softmax. In
Natasha Jaques, Angeliki I 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 International Conference Machine Learning, pp- 3040-30499 2019.
Tang Jie and Pieter Abbeel. On connection between importance sampling and the likelihood ratio policy gradient. In Advances in Neural Information Processing Systems, pp. 1000-1008, 2010.
Jelle R Kok and Nikos Vlassis. Collaborative multiagent reinforcement learnin by payoff propagation. Journal of Machine Learning Research, (SSep))1789-115 2006.
Angeliki Lazaridou, Alexander Peysakhovich, and Marco Baroni. Multi-agent cooperation and the emergence of (natural) language. In Proceedings of the International Conference on Learning Representations (ICLR), 2017.
Sergey Levine and Vladlen Koltun. Guided policy search. International Conference on Machine Learning, pp. 1-9, 2013.
Timothy Lillicrap. Jonathan J Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa. David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. In Proceedings of the International Conference on Learning Representations (ICLR), 2015.
Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, OpenAl Pieter Abbeel, and Igor Mordatch. Multi-agent actor-critic for mixed cooperative-compettivy environments. Advances in Neural Information Processing Systems, pp. 6379-6390) 2017.
Sergio Valcarcel Macua, Aleksi Tukiainen, Daniel Garefa-Ocaña Oсańa Hernández, David Baldazo, En- rique Munoz de Cote, and Santiago Zazo. Diff-dac: Distributed actor-critic for multitask deep reinforcement learning. arXiv preprint arXiv:1710.10366 2017.
Chris J Maddison, Andriy Mnih, and Yee Whye Teh. The concrete distribution: A continuous relaxation of discrete random variables. In Proceedings of the International Conference on Learning Representationss (ICLR), 2017.
Anuj Mahajan, Tabish Rashid, Mikayel Samvelyan, and Shimon Whiteson. Maven: Multi-agent variational exploration. In Advances in Neural Information Processing Systems, pp. 761 1-7622, 2019.
Nicolas Meuleau, Leonid Peshkin, Leslie P Kaelbling, and Kee-Eung Kim. Off-policy policy search. MIT Articical Intelligence Laboratory, 2000.
Igor Mordatch and Pieter Abbeel. Emergence of grounded compositional language in multi-agent populations. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
Rémi Munos, Tom Stepleton, Anna Harutyunyan, and Marc Bellemare. Safe and efficient off-policy reinforcement learning. Advances Neural Information Processing Systems, pp. 1054-1062, 2016.
Frans A Olichock, Christopher Amato, et al. A concise introduction to decentralized POMDPs, volume 1. Springer, 2016.
Shayegan Omidshafiei, Jason Pazis, Christopher Amato, Jonathan P How, and John Vian. Deep decentralized multi-task multi-agent reinforeement learning under partial observability. In Pro- ceedings of the 34th International Conference on Machine Learning Volume 70, pp. 2681-2690. JMLR. org, 2017.
11

---

Published as a conference paper at ICLR 2021
Doina Precup, Richard S Sutton, and Satinder Singh. Eligibility traces for off-po policy evaluation. In 1CMLML '0 Proceedings of the Seventeenth International Conference on Machine Learning. 2000.
Tabish Rashid, Mikayel Samvelyan, Christian Schroeder Witt, Gregory Farquhar, Jakob Foerster, and Shimon Whiteson. Qmix: Monotonic value function factorisation for deep multi-agent reinforcement learning. In International Conference on Machine Learning, pp. 4292-4301, 2018.
Tabish Rashid, Mikayel Samvelyan, Christian Schroeder De Witt, Gregory Farquhar, Jakob Foerster, and Shimon Whiteson. Monotonic value function factorisation for deep multi-agent reinforcement learning. arXiv preprint arXiv:2003, 088899 2020.
Mikayel Samvelyan, Tabish Rashid, Christian Schroeder de Witt, Gregory Farquhar, Nantas Nardelli, Tim GJ Rudner, Chia-Man Hung, Philip HS Torr, Jakob Foerster, and Shimon Whiteson. The starcraft multi-agent challenge. arXiv preprint arXiv: /902004022, 2019.
David Silver, Guy Lever, Nicolas Heess, Thomas Degris, Daan Wierstra, and Martin Riedmiller. Deterministic policy gradient algorithms. In Proceedings of the 31 International Conference on International Conference Machine Learning- Volume 32, pp. I-387, 2014.
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 Machine Learning, pp. 5887-5896, 2019.
Sainbayar Sukhbaatar, Rob Fergus, et al. Learning multiagent communication with backpropagation. In Advances in Neural Information Processing Systems, pp. 2244-2252, 2016.
Peter Sunehag, Guy Lever, Audrunas Gruslys, Wojciech Marian Czarnecki, Vinicius Zambaldi, Max Jaderberg, Mare Lanctot, Nicolas Sonnerat, Joel Z Leibo, Karl Tuyls, et al. Value-deecomposition networks for cooperative multi-agent learning based on team reward. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, pp. 2085-2087. International Foundation for Autonomous Agents and Multiagent Systems, 2018.
Wesley Suttle, Zhuoran Yang, Kaiqing Zhang, Zhaoran Wang, Tamer Basar, and Ji Liu. A multi- agent off off-policy actor critic algorithm for distributed reinforcement learning. arXiv preprint arXiv:1903.06332, 2019.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018
Yee Teh, Victor Bapst, Wojciech M Czarnecki, John Quan, James Kirkpatrick, Raia Hadsell, Nicolas Heess, and Razvan Pascanu. Distral: Robust multitask reinforcement learning. In Advances in Neural Information Processing Systems, pp. 4496-4506. 2017.
Kagan Tumer, Adrian K. Agogino, and David H. Wolpert. Learning sequences of actions in collectives of autonomous agents. In Proceedings of the First International Joint Conference on Autonomous Agents and Multiagent Systems: Part 1, AAMAS '02, pp. 378-385, New York, NY, USA, 2002. Association for Computing Machinery. ISBN 1581134809 134800.
doi: 10. 06.11445544741154444
URL
https://oooor//110114/44777474.
Oriol Vinyals, Igor Babuschkin, Wojeiech M Czarnecki. Michaël Mathieu, Andrew Dudzik, Junyoung Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature, 575(7782):350-334 2019.
Jianhao Wang. Zhizhou Ren, Beining Han, and Chongjie Zhang. Towards understanding linear value decomposition in cooperative multi-agent q-learnig. 2020a.
Jianhao Wang, Zhizhou Ren, Terry Liu, Yang Yu, and Chongjic Zhang. Qplex: Duplex dueling multi-agent leaarnngg. arXiv preprint arXiv:2008.00 01062, 2020b.
Tonghan Wang, Heng Dong, Victor Lesser, and Chongjic Zhang. Roma: Multi-agent reinforcement learning with emergent roles. In Proceedings of the 37th International Conference Machine Learning, 2020c.
Tonghan Wang, Jianhao Wang. Wu Yi, and Chongjie Zhang. Influence- based multi-agent exploration. In Proceedings of the International Conference on Learning Representations (ICLR), 2020d.
12

---

Published as a conference paper at ICLR 2021
Tonghan Wang. Jianhao Wang, Chongyi Zheng, and Chongjie Zhang. Learning nearly decomposable value functions with communication minimization. In Proceedings of the International Conference on Learning Representations (ICLR), 2020c.
Tonghan Wang. Tarun Gupta, Anuj Mahajan, Bei Peng, Shimon Whiteson, and Chongjie Zhang. Rode: Learning roles to decompose multi-agent tasks. In Proceedings of the International Conference on Learning Representations (ICLR), 2021.
Ziyu Wang, Victor Bapst, Nicolas Heess, Volodymyr Mnih, Remi Munos, Koray Kavukcuoglu, and Nando de Freitas. Sample efficient actor-critic with experience replay. In Proceedings of the International Conference on Learning Representations (ICLR), 2016.
Ying Wen, Yaodong Yang, Rui Luo, Jun Wang, and Wei Pan. Probabilistic recursive reasoning for multi-agent reinforcement learning. In Proceedings of the International Conference Learning Representations (ICLR), 2019.
David H Wolpert and Kagan Tumer. Optimal payoff functions for members of collectives. In Modeling complexity economic and social systems, pp- 339-369. World Scientific, 2002.
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, pp. 5571-5580, 2018.
Chongjie Zhang and Victor Lesser. Coordinated multi-agent reinforcement learning in networked distributed pomdps. In Twenty-Fifth AAAI Conference Artificial Intelligence, 2011.
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, pp. 5872-5881, 2018.
Kaiqing Zhang, Zhuoran Yang, and Tamer Başar. Multi-agent reinforcement learning: A selective overview of theories and algorithms. arXiv preprint
2019.
Yan Zhang and Michael M Zavlanos. Distributed off- pollco actor-critic reinforcement learning with policy consensus. arXiv preprint 19X3v:1903.0920 2019.
13

---

Published as a conference paper at ICLR 2021
A
MATHEMATICAL DETAILS FOR STOCHASTIC DOP
A.1 DECOMPOSED CRITICS ENABLE TRACTABLE MULTI-AGENT TREE BACKUP
In Sec. 4.1.1 propose tree backup (Precup al. 2000 Munos et al. 2016) carry
multi-agent off-policy policy evaluation. When a joint critic is used, calculating Er Q (T,
requires A{ ") steps of summation. To solve this problem, DOP uses a linearly decomposed critic, and it follows that:
Ex Ex (T, a)] = Σ (tu,,)) = -E T((a)))
Σ (T(T) + b(T))
Σ T(|TT) Σ (TT) (T) +
Σ T(aaT)b(T)
(13)
ΣΣ (((a)) (T) az) Σ Tai(a-,|T b(T)
a.:
Σ (T) (T. (T.-) b(T))
which means the complexity of calculating this expectation is reduced to O(n]A)).
A.2
STOCHASTIC DOP POLICY GRADIENTS
A.2.1
ON-POLICY VERSION
In Sec. 4.1.1 we give the on-policy stochastic DOP policy gradients:
E Vo, log 00) (T,
(14)
We now derive it in detail.
Proof. We use the aristocrat utility (Wolpert & Tumer 2002 to perform credit assignment:
U,( (io((T Σ (. a.:)
() - Σ (
(1))
=T(T)(f (T, (1. - ((((T) Σ (5) (T,2)
= k;(T) (T, ( (T,
It is worth noting that U, is independent of other agents' actions. Then, for the policy gradients, we have:
9 = E
Vo (olgm((//)))
(T) Σ Tm (f (r.00)
Er
Vologm(((m))((()
E
Vologm Volema(ammMk1100
14

---

Published as a conference paper at ICLR 2021
A.2.2 OFF-POLICY VERSION
In Appendix A.2 derive the on-policy policy gradients for updating stochastic multi-agent policies. Similar to policy evaluation, using off-policy data can improve the sample efficiency with regard to policy improvement.
Using the linearly decomposed critic architecture, the off ooficy policy gradients for learning stochas- tic policies are:
パ a) g g= Eg (3( a)
ki (a 7; (T, ai)
(15)
Proof. The objective function is:
((0) RB [V (T)).
Similar to Degris et al. 2012
we have:
<aaTT)
(0) Es
V Volggm(a/))Ui(t...)
B(alT)
T(aTT)
Es
B(alT)
<(aTT) B(aTT) Σ Vologm(aam))
Es
B MATHEMATICAL DETAILS FOR DETERMINISTIC DOP
B.1 DETERMINISTIC DOP POLICY GRADIENT THEOREM
In Sec. 4.2. give the following deterministic DOP policy gradients:
( Er~D ee Of alla
(16)
Now we present the derivation of this update rule.
Proof. Drawing inspirations from single-agent cases (Silver et al. 2014), we have:
VJ(()) ETTD VoQu (T.
= ETnD!
Vek (7,
ETND Σ Vouu(T::)NVa (r, an) (r.a)))))m)))))))
C THEORETICAL JUSTIFICATION CRRREEETICAAIUSSTIFFCATTOOO IMPROVEMENT
FOR STOCHASTIC DOP POLICY
In order to understand how DOP works despite the biased (T a) estimation, we provide some theoretical justification for the policy update. Unfortunately, a thorough analysis on deep neural network and TD TD-learning is too complex to be carried out. Thus, make assumptions for the mathematical proof. The following two subsections provide two different view points of theoretical understanding.
15

---

Published as a conference paper at ICLR 2021
1. In the first view (Sec. holds on a wide range of function class. In this way, we can prove policy improvement theorem similar to Degris et al. (2012).
assume mild assumptions value evaluation which
2. In the second view, we remove the MONOTONE condition from a practical point of view.
We then prove that when the loss of value evaluation is minimized (individual crities output
Q (T, a;) to be a good estimate of QT (T, a4)), the DOP gradients Eq. eqqul to Eq. which is the standard gradient form.
C.1 PROOF OF STOCHASTIC DOP POLICY IMPROVEMENT THEOREM
Inspired by previous work (Dgrris et al. 2012). we relax the requirement that Q is a good estimate of Pio and show that stochastic DOP still guarantees policy improvement.
First, we define
(T Σ I=. (T, [T(aa) a.
Directly analyzing the minimization of TD-error is challenging. To make it tractable, some works (Feinberg et al., 2018)) simplify this analysis an MSE problem. For the analysis of stochastic DOP, we adopt the same technique and formalize the critic's learning as the following problem:
((Ø) = [((T)((((T)) (T - (T. a,7
(17)
where (T, a) are the true values, which are fixed during optimization. the following analysis, we assume distinct parameters for different т. We first show that [T holds for wide range of function class of Q.ah To this end, first prove the following lemma. Lemma 1, Without loss of generality, we consider the following optimization problem:
(+(0) = Σ t(alT) (Q* - -
(18)
Here, ((Q R + R, and Q a) is a vector whose tth entry is Q1 (T,):). In DOP, f satisfies that 8Q.0 (T,as)
B5
> 0 for any a.
If V (T, a:) 0, Vol. it holds that:
(T ..) 2 Q7 (T, at) + Q (T, 2 (T, (T, df),
Va,, df-
Proof. When the optimization converges, o; reaches a stationary point where V.LL(()) = 0, Vi.
as
(T) EI (5(())T;) (Q (T, f(Q (T, ())) (- 8Q.h (T.
0f = 0, Va:-
J#
Since Vo, Q (T,a,) a.) * 0, this implics that Vi, a, we have
EI (1 (T, S(Q a))) a- J
Σ n (a I7- (T((Ta:)
We consider the function g(T, a;) Ea,
which is function of Q
Its partial derivative w.r.t Q (T, ai) is:
0g(T. a:) Σ
Of(Q((r.a) > 0 aQ;¹ (T,
8 (T,as) a.;
16

---

Published as a conference paper at ICLR 2021
Therefore, if QT 2 QT (T) then any local minimal of (ő()) satisfies (T. (T,
We argue that Vo, Q. (T, ai) o is rather mild assumption and holds for a large range of function class of Q
Fact 3. (Formal Statement of Fact 1] For the following choices of Q
1. Tabular expression of O which requires Q(n[A[[T]) space;
2. Linear function class where 04 are one-hot coded:
2 az) = 0b+ (T,a:);
3. 2-layer neural networks (6, # 0) with strictly monotonic increasing activation functions (e.g. tanh, lelu)-
4. Arbitrary k-layer neural networks whose activation function at the (k: - 1)th layer is sigmoid.
when value evaluation converges, VTT, º satisfies that
@T 2 (T,,)))
(T, VT, 0r,00,00 dc-
(T, a,) + O. For brevity, we use a to denote the h element of the one-hot coding, and use o; to denote the weight connecting the 7hh element of the upper layer and the a element.
Proof. We need to prove that V (T tta
& For tabular expression and linear functions, Va, le have
aQ!1 (T, a.))
0Φ, !
(3) The 2-layer neural network can be written as O (T. 0s) = (Wi(W((T. Besides, we denote the hidden layer h. Since di * O, we consider some nonzero element @ W2 gradient of the parameter sk. is
11.. For the 1thh action, the
aQa (T, aT)
Wa
Whbe)) + 0, Vk
W1
(4) Without loss of generality, we consider the last layer @1.
aQ. (T, o(hi-1)
We
These are the cases where Q. * 0. Even when 3ø,, V Q.. 0 such d; usually occupy only a small parameter space and happen with small probability. As result, we conclude that Vo, O aT) # 0 is rather mild assumption.
Based on Fact [ we are able to prove the policy improvement theorem stochastic DOP. will show that even without accurate estimate of Q the stochastic DOP policy updates can still improve the objective function J(TT) = Ex IE, 7 We first prove the following lemma.
Lemma 2. For two sequences (a:). {b,}. E [n]] listed in an increasing order. If E b, = then
Σ, axb; 2 0.
17

---

Published as a conference paper at ICLR 2021
Proof. We denote à = E; ag then E, a.b; a{
6,) + Σ drb where Σ, a 0. Without
loss generality, we assume that 0; = 0, vi. j and & which - aj+1 2 0 and by I 0, bx+1 2 Since a, b are symmetric, assume j S k. Then we have
Σ ag4 = xE(n]
Σ
aeb +
E
a +
Σ
asb
1E|R+I,n]
Σ
agb; Σ
arb;
i,
1E|e+I,n
Σ
bi + ax+1
b
1E(++1,
As Eie(itiin) b, 2 O, we have E EiE(i+i b, S EiE((+1m)) bi.
Thus, Eie(n) a;b; 2 (ax+1 .x)) EiE(++in) b; 120. O.
Based on Fact Fad Lemma 2 we prove the following proposition.
Proposition 2. [Stochastic DOP policy improvement theorem) Under mild assumptions, for any pre-update policy πO which is updated by Eq. 10 n, denote T((a:TT)) = = (0,1T;) + Bar where > 0 is a sufficiently small number. If it holds that Vt, de, as Q. (T, a:) 2 ( = Bagt Bot,r (MONOTONE condition, and Φ, is the parameters before update.), then we have
2
2 J(TT))
(19)
i.e., joint policy is improved by the update.
Proof. Under Fact I it follows that
QT (T, > QT (T,(T, = BBsT 2 Bag.r.
(20)
Since J(T) E.o (io it suffices to prove that VT,, (io( 2 V (T:). We have:
Σ (( a:) Σ
II vi=l
n: (a(l):)))
OT (Ti((T as)
Σ
(a(())))))) + Pott
Qioi aT)
n
Via (Tx) +
Bate
Il jt
(3 ai)
ae
Vo (Tt) +
Bat (T + o())
(Te,
(21)
i=1
Since ó is sufficiently small, in the following analysis we omit o()). Observing that Ea, TT(a:TT)) =
1, Vi, we get Ea, BUgT = 0. Thus, by Lemma 2 and Eq. 21 we have
Σ T T2) QT) (T,, a.) Viri (Tt).
(22)
Similar to the policy improvement theorem for tabular MDPs (Sutton & Barto 2018) we have
Vir (Tt) & Σ (Ta
ac
Σ T(a(TT))
a()
ai) + Ep(THIlT, an (T(11) (oo(()
a.
T:11
18

---

Published as a conference paper at ICLR 2021
ग az+ + T ) (T++) (T ant1)) ))
s Σ {(a|T:) ar
ai) + E((TetITr,a)))
Σ dr+1
T(-1
< Vitl (T:).
This implies J 2 "T)") for each update.
Moreover, we verify that VT, af, oi O (T, a;) > QT" d() - Barr 2 Baj,r (the MONOTONE condition) holds for any æ with a tabular expression. For these n, let h. (a: Ooc,s then it holds that 2n, la.t 1. Since the gradient of policy update can be written as:
(TT( Bd((T)
Σ
b
Ed(1) Σ o (T,
= Σ d(r) Σ ( (T,
where (T) is the occupancy measure w.r.t our algorithm. With a tabular expression, the update of each larr proportion to Sa,,
dn((T) d(T) (T.a)
B
ddant
Clearly, Bai,r 2 Pasi = 0f (T, a 2 Of (r,
L
C.2 ANALYSIS WITHOUT MONOTONE CONDITION
For practical implementation of policy TH ((,.(TT). the MONOTONE condition is too strong to be satisfied for all π₁ Analyzing the policy update when the condition is violated is difficult with only Fact I at hand. Therefore, it is beneficial to understand policy improvement without the MONOTONE condition.
To bypass the MONOTONE condition, we require stronger property of the learnt Q." (T, a;) in addition to order preserving [F.ct[]. Theorem in Wang al. (2020a) offers closed form solution of additive decomposition and we restate it as the following lemma
Lemma (Restatement of Theorem in Wang et al. 2020aa), If we consider the solution of
arg min
Σ
<(alT)
(((T,)) Ed((T.a))
(s.a)ESxA
1=1
Vi E [n),Vr VT, a the individual action-value funnctonnn Qi(T, as)
E (./T-))
[y/ (T, as a-)) n
E [y(T + w((ss,
(23)
a~>((-17)
The residual term w an arbitrary vector satisfying Vs. Σn ws(s) = 0.
Based this lemma,
derive another proposition theoretically justify the DOP architecture.
Proposition 1. Suppose the function class expressed by Q (T, a;) is sufficiently large (e.g. neural networks) and the following loss L(Ø) is minimized
L(Φ) = (
( a))²
0,7
19

---

Published as a conference paper at ICLR 2021
where (Toc(T,a) (T), (T, a.) + b(T). Then, have
g = ET I Vo, log (a, 0, (.) (T,
=En [ log (a. 0.) (T, (T.
which means stochastic DOP policy gradients the those calculated using centralized critics (Eq. 2 Therefore, policy improvement is guaranteed.
Proof. For brevity, we denote (T) (T, Then L(ø) can be written as
L(Ø) Σ ((T) E,00, b(T)))
7.7
According to Lemma
when L(Ø) is minimized, we have
Qk (T, a.) = (T, ((Taaa)) n
VT + wi(s) (o(ss)-ao 1 (T)
= -w((T)
Then
g Ex E,ki(T) log lag (T, (r)
Er log. (T, (T,ai)
E, E.Vo, (a (r, a)]
Therefore, in expectation, stochastic DOP gradients are the same as those calculated using centralized critics (Fq.2)) We no longer require the MONOTONE condition to guarantee improvement of the policy update. Proposition another point of view explain the performance guarantee of DOP despite its constrained critics.
D REPRESENTATIONAL CAPABILITY OF DETERMINISTIC DOP CRITICS
In Sec. 4.2.2 we present the following facts about deterministic DOP:
Fact 2. Assume that VT, a, a' E O₂(T). || VaQu a) - V o a') 2|55 L || a - 1|.. The estimation error DOP critic can be bounded by O(L8²) for (x(T),
We consider the Taylor expansion with Lagrange remainder Qt (T, a). Namely,
Qui (T. a) = Qlu (T, ((T)) + VaQ a)la=p(T) (a- (a-M(T)) + Q ac) || l a- T(T) 1|? 2
Since Va E Os(TT(T), we have
1
(T. ( - V VaQui u (a- (a- < LD²
Noticing that the first order Taylor expansion of Qti has the form Σ [n) (x(T) (T, a.) + b(T).
Therefore, the optimal solution of the MSE problem Eq. [7 under DOP crities an error term less than O for arbitrary sampling distribution p(T, a) of a E Os(H(T)).
When Q values in the proximity of p(T), VT is well estimated within a bounded error and < approximately, we have
aQua(T (T,a)
aQt (Q (T,a)
Que amis a; 5) - Qt (T,
Qia (T, a,,aa,, a; +0)
Q a)
Da;
Da;
8
8
Que (T, aa a4 + 8)
Q (T, a. +4:4000 +5)
Qu (T, a) aT)
8
((T8)
20

---

Published as a conference paper at ICLR 2021
E ALGORITHMS
In this section, we describe the details of our algorithms, as shown in Algorithm
| and
Algorithm Stochastic DOP
Initialize critic network Q", actor networks na, and mixer network M with random parameters 0.0, v..
Initialize target networks: o' Φ. 0' = 0, v/d
Initialize an off-ppoiccy replay buffer Doff and an on-policy replay buffer Dmn-
for ( 1 T do
Generate a trajectory and store it in Df and Dm
Sample batch consisting of N, trajectories from Don Update decentralized policies using the gradients described in Eq. 10
Calculate _ (Ø)
Sample batch consisting of N2 trajectories from Don
Calculate CDOP-TB (Φ)
Update critics using [o2(o) and CDOPTBB (Φ)
(Ø)
l mod then
Update target networks: ø' Φ. l' 0, v/ end for
end
Algorithm 2 Deterministic DOP
Initialize critic network Q", actor networks poo and mixer network M with random parameters
0,0, 1b
Initialize target networks: ø' d. 6, vt/ sb
Initialize replay buffer D Select action with exploration noise a (e(T) + generate transition and store the transition
for 1. 1 to do
tuple in
Sample N transitions from D
Update the critic using the loss function described in Eq.
Update decentralized policies using the gradients described in Eq. 12 if mod then
Update target networks: o' ar (1 a' , 0' al + a))0' w/ on +1 aNy end
end for
F DOP WITH COMMUNICATION
Although DOP can solve many coordination problems, shown by the comparison against IQL in 6 its complete decomposition critic raises the concern that DOP can not deal with the miscoordination problem induced by highly uncertain and partial observable environments.
We use an example to illustrate the causes of miscoordination problems and argue that introducing communication into DOP can help address these problems. In hallway (Fig. (7))), two agents randomly start at states a to a.m and b to bn. respectively. Agents can observe their position and choose move left, tt, move right, or keep still at each timestep. Agents win and are rewarded 10 if they arrive at state g simultancously. Otherwise. if any agent arrives at carlier than the other, the team gets no reward, and the next episode begins. The horizon is set to max(m, n) + 10 to avoid an infinite loop.
Without communication, one agent cannot know the position of its teammates, so it is difficult to coordinate actions. This explains why hallway with m=n=4, the team win only 25% of the games (Fig. (b)).. Equipping DOP with communication can largely solve the problem agents leam communicate their positions and move left at a1 by simultaneously. For communication,
21

---

Published as a conference paper at ICLR 2021
Stochastic DOP (Ours)
101
MMMIZ
Tand
(m)))
(miil)
Figure 6: decomposed critic can solve many coordination problems which can not solved by IQL.
Halleay
a1
a2
4m
80
1eat
40
D
(a) Task hallway
Timlo
(b) Performance comparison
Figure 7: A highly partial observable task. (a) Task hallway; (b) Performance of DOP with and without communication hallway with m=n=4.
use the technique introduced by Wang al. (2020e). Agents share communication module, and messages are passed both between actors and individual Q-functions.
Such miscoordination problems common in complex multi-agent tasks (Wang et al. 2020e). We believe introducing communication into DOP can help solve larger range of problems.
G BASELINE SAMPLING
One problem of existing MAPG methods is the CDM issue, which describes the large variance in policy gradients caused by the influence other agents' actions introduced through the joint critic. Another technique that is frequently used to reduce the variance in policy gradients in the single-agent RL literature is by using baselines (Sutton Barto 2018). this section, we investigate whether using baselines can effectively reduce variance in multi-agen settings.
We start from centralized critics. COMA uses a baseline where local actions are marginalized.. Since the variance and performance of COMA have been discussed in Sec. [ omit it here and study the baseline where actions of all agents are marginalized. multi-agent settings, the calculation of this baseline requires computing expectation over the joint action space, which is generally intractable. To solve this problem, we estimate the expectation by sampling.
We compare stochastic DOP, COMA, and On-Policy DOP against this method, which call Regular Critics with Baseline. Results are shown in Fig. We can see that Regular Critics with Baseline performs better than COMA. However, Regular Critics with Baseline performs worse than On-Policy DOP. These results indicate that a linearly decomposed critic can reduce variance in policy gradients more efficiently.
H INFRASTRUCTURE, ARCHITECTURE, AND HYPERPARAMETERS
Experiments are carried out on NVIDIA P100 GPUs and with fixed settings, which described in the following sections.
22

---

Published as a conference paper at ICLR 2021
Stochastic DOP (Durs)
On-Policy DOP
COMA
Regular Critics with Reseline
2x3r
NKN
100
200
100
Tanc Wil Kg
50
30
Tex:
0
10
[m]]
Tomio
(miil vs
10m vs
My many banwing
100
100
100
Tenl: with
50
30
Teo.
Test
(m/))
Figure 8: Using baselines where actions of all other agents are marginalized within centralized critic is more efficient than COMA, but less efficient than a decomposed critic.
H.1 STOCHASTIC DOP
In stochastic DOP, each agent has neural network to approximate its local utility. The local utility network consists of two 256-dimensional fully-connected layers with ReLU activation. Since the critic is not used when execution, we condition local Q networks on the global state 8. The output of the local utility networks is Q.' (T. for each possible local action, which are then linearly combined to get an estimate of the global Q value. The weights and bias of the linear combination, h; and b, are generated by linear networks conditioned on the global state s. K; is enforced to be non-negative by applying absolute activation the last layer. We then divide k2 by >; Kū to scale k; to [0, 1].
The local policy network consists of three layers, a fully-connected layer, followed by a 64 bit GRU, and followed by another fully-connected layer that outputs a probability distribution over local actions. We use ReLU activation after the first fonnecco layer.
For all experiments, we set K 0.5 and use an off-policy replay buffer storing the latest 5000 episodes and an on-policy buffer with size of 32. We run 4 parallel environments to collect data. The optimization of both the critic and actors conducted using RMSprop with a learning rate of 5 x 10-4, a of 0.99, and with no momentum or weight decay. For exploration, we use é-greedy with annealed linearly from 1.0 to 0.05 over 500% time steps and kept constant for the rest of the training. Mixed batches consisting of 32 episodes sampled from the off-policy replay buffer and 16 episodes sampled from the on-policy buffer are used to train the critic. For training actors, we sample 16 episodes from the on-policy buffer each time. The framework is trained on fully unrolled episodes. The learning rates for the critic and actors are set to x 10-4 and 5 x 10-4, respectively. And we use 5-step decomposed multi-agent tree backup. All experiments on StarCraft II use the default reward and observation settings of the SMAC benchmark.
H.2 DETERMINISTIC DOP
The critic network structure of deterministic DOP is similar to that of stochastic DOP, except that local actions are part of the input in deterninistic DOP. For actors, we use a fully-connected forward network with two di-dimensional hidden layers with ReLU activation, and the output of actors is a local action. We use an off-polico replay buffer storing the latest 10000 transitions, from which 1250 transitions are sampled each time to train the critic and actors. The learning rates of both the critic and actors are set to 5 x 10-3, To reduce variance in the updates of actors, we update the actors and target networks only after 2 updates to the critic, as proposed by Fujimoto et al. (2018). We also use this technique of delaying policy update in all the baselines. For all the algorithms, we run single environment to collect data, because we empirically find more sample efficient than parallel environments in the MPE benchmark. R.Mpprpp with a learning rate of 5 x 1 of 0.99, and with no momentum or weight decay is used to optimize the critic and actors, which is the same as in stochastic DOP.
23

---

Published as a conference paper at ICLR 2021
1 RELATED WORKS
Cooperative multi-agent reinforcement learning provides a scalable approach to learning collaborative
strategies for many challenging tasks (Vinyals et al., 2019 Berner al. 2019; Samvelyan al. 2019; Jaderberg et al. 2019) and a computational framework to study many problems, including
the emergence of tool usage (Baker al. 2020), communication (Foerster et al., 2016: Sukhbaatar et al., 2016] Lazaridou et al., [017]] Das et al. 2019), social influence (Jaques et al. 2019), and
inequity aversion (Hughes et al. 2018). Recent work on role-based learning (Wang et al.) | 2020c)
2021 introduces the concept of division of labor into multi-agent learning and grounds MARL into
more realistic applications.
Centralized learning of joint actions can handle coordination problems and avoid non non-stationarity. However, the major concern of centralized training is scalability, as the joint action space grows exponentially with the number of agents. The coordination graph (Guestrin et al. 2002b a) is promising approach to achieve scalable centralized learning, which exploits coordination indepen- dencies between agents and decomposes global reward function into sum of local terms. Zhang Lesser 2011) employ the distributed constraint optimization technique to coordinate distributed learning of joint action-value functions. Sparse cooperative Q-learning (Kok & Vlassis 2006) learns to coordinate the actions of a group of cooperative agents only in the states where such coordination necessary. These methods require the dependencies between agents to be pre-supplied. To avoid this assumption, value function decomposition methods directly learn centralized but factorized global Q-functions. They implicitly represent the coordination dependencies among agents by the decomposable structure (Sunehag et al.) 2018; Rashid et al., 2018 |oon et al., 2019 Wang et al.) 2020e). The stability multi-agent off oof-policy learning is a long-standing problem. Foerster et al. (2017): Wang al. (2020a) study this problem in value-based methods. In this paper, we focus on how to achieve efficient off- off-policy policy-based learning. Our work is complementary to previous work based multi-agent policy gradients, such those regarding multi-agent multi-task learning (Tch) ct al. 2017 Omidshafici et al. 2017) and multi-agent exploration (Wang et al.) 2020d).
Multi-agent policy gradient algorithms enjoy stable convergence properties compared to allue-based methods (Gupta et al.] [017]] |Wang et al.] (2020a) and can extend MARL to continuous control problems. COMA (Foerster et al. 2018)) and MADDPG (Lowe et al. 2017) propose the paradigm of centralized critic with decentralized actors to deal with the non-stationarity issue while maintaining decentralized execution. PR2 (Wen et al. 2019) and MAAC (Iqbal & Sha 2019) extend the CCDA paradigm by introducing the mechanism of recursive reasoning and attention, respectively. Another line of research focuses on fully decentralized actor-critic learning (Macua et al., (2017; Zhhng et al.)
2018 Yang et al. 2018 Cassano et al. 2018 Suttle et al. 2019) Zhang & Zay Zavlanos| (019)). Different from the setting this paper, agents have local reward functions and full observation of the true state in these works.
24


Reviews:
[{"review_id": "isTA35yheEL", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 9, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This works motivates the use of a factorized critic for multi-agent policy gradient.   The technique is well-motivated, and the exposition anticipates and answers readers' likely concerns.   The experiment section is well-organized, supports the paper's major claims, and is empirically compelling.\n\nThe policy improvement claims in section 4.1.2 are initially unintuitive, but ultimately are intelligible as an agent-block-coordinate local optimality statement.  However this reviewer is not clear on the quality of these local optima (i.e., when do we get \"trapped\"?).  For example, is it possible to design a task where the local optima are all very poor?   Of course, the experiment section indicates many benchmark tasks are amenable to this decomposition; but perhaps reasoning about this would help in (re)defining multi-agent problems to encourage success, e.g., it would be interesting if adding actions that communicate information directly between agents mitigates the local optima problem.\n\n\n\n ", "extra_scores": {}, "extra_text": {}}, {"review_id": "d3m1wYkeqa", "reviewer": "AnonReviewer4", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nThe paper proposed a simple but powerful idea of assuming a linear decomposition structure of the centralized critic into individual critics. It demonstrated 2 existing problems in the baseline MAPG agents (COMA, MADDPG), namely \"centralized-decentralized mismatch\" problem and credit assignment issues, and offers a theoretically motivated solution with carefully conducted experiment results including ablation studies as well as comparison with sota gradient-based and value-based algorithms.\n\n##########################################################################\n\nReasons for score: \n \nThe paper is very well written. Its proposal is simple but theoretically motivated to solve existing problems in MAPG algorithms. The experiment results support its claims and provides additional insightful analysis. Therefore I recommend \"accept\". However, its theoretical justification is weakened by assuming a tabular case of pi and Q functions which is rarely the case in practice. Furthermore, in Proposition 1, the conditioning just above Eq. 11 looks quite particular and I'm not sure how general it is satisfied in practice. Last but not least, it would be nice to see comparisons with more recent value decomposition algorithms such as NDQ and QTRAN/QPLEX. Overall I gave it a score 7.\n \n##########################################################################\n\nPros: \n\n1. The paper is organized in very clear fashion. It is well motivated by existing problems and provides a simple and effective solution. \n2. It conducted clever experimental analysis that made the advantages of DOP very obvious and understandable.\n3. Its method of linear decomposition of the central critic into individual critics is simple yet powerful. The paper gave adequate theoretical support to this method. \n \n##########################################################################\n\nCons: \n\n1. Both the tabular assumption on functions pi and Q, and especially the conditioning of Proposition 1 weaken the theoretical guarantee that the algorithm will converge to local optima.\n2. The paper did not compare with more recent value decomposition algorithms such as NDQ and QTRAN/QPLEX. It's unclear that the baselines are the SOTA results on the chosen domains.\n \n##########################################################################\n\nQuestions during rebuttal period: \n\n Please address the two points in \"Cons\" above.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "R2dzz0goQ-G", "reviewer": "AnonReviewer1", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In the context centralized training distributed execution in cooperative multi-agent reinforcement learning (MARL), the paper proposes an architecture to learn a decomposed action value function expressed as a weighted sum of the agent's individual functions (plus an additional weight). Those weights are themselves learned and depend on the observed history. Thanks to this decomposition, gradients can be decomposed over each agent. The authors propose to use a combination of off-policy (using tree backup) and on-policy (using TD(\\lambda) methods for estimating the decomposed critic. They formulate both a deterministic and stochastic decomposed policy gradients, which are analyzed theoretically to some extent and evaluated experimentally.\n\nPROS\n\nThe paper contributes to the active effort of designing more efficient MARL algorithms. The authors introduce the idea of value decomposition, which was investigated first in the value-based methods, to the actor-critic scheme. The experimental results suggest that the proposed combination of value decomposition and off-policy critic training has a good performance.\n\nThe writing of the paper is clear. The identification of the issue of centralized-decentralized mismatch and how it is tackled by the proposed methods are useful and interesting.\n\n\nCONS\n\nThe formulation of Prop. 1 is hard to understand. What is Q_i^{\\phi_i}? Is it the value function wrt \\pi or \\pi^0? Besides, how do we ensure that the strict inequality about Q_i^{\\phi_i} holds?\n\nSome theoretical analyses (e.g., A3 or C) are only loosely related to the actual proposed method, although I agree that a direct analysis would be difficult to conduct.", "extra_scores": {}, "extra_text": {}}, {"review_id": "9O4g7FXyvx2", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper focuses on the problem of multi-agent reinforcement learning (MARL) for CTDE scenario which is well studied in recent literature.  The work discusses shortcomings of actor-critic methods for MARL and proposes a solution using linearly factored critic. The paper is somewhat difficult to read and can be made better by deferring the details about previous methods to appendix. However my main concern is with the problem of centralized-decentralized mismatch (CDM) motivated in the paper and its proposed solution itself. \n\n1. How exactly is a regular critic bad? As such a critic is supposed to be \"true\" to the policy, the requirement of decentralization has little bearing on the variance of policy gradients. Gradient noise increases with number of agents irrespective of whether there is centralized or decentralized execution. \n\n2. The so called problem of CDM seems rather redundant (see 1 above), for example the authors say in page 3, 3rd para from bottom in line 3 that if the critic expectation under policy is negative, then individual policy performance is hurt. Such problem can easily be fixed using baselines, see Sutton and Barto, 2018 for example.\n\n3. How is a linear factored critic compatible with an arbitrary joint policy? In general this not true and requires many strong assumptions, see for ex. Bhatnagar, 2009. While the authors acknowledge this, bypassing the actual complexity for modelling a joint critic with a linear one will in general render it insufficient to model inter-agent interactions. This puts into serious question, whether coordination is required in the experiment domains in the first place and if the performance improvement is just coming due to a biased but albeit easier to learn critic. \n\n4. There are some unsupported claims which need better explanation like \"This becomes problematic because a negative feedback loop is created, in which the joint critic is affected by the suboptimality of agent i, which disturbs policy updates of other agents\" How is that so? The updates in principle can affect the policies of already suboptimal agents, which might fix them?\n\n5. \"Learning the decomposed critic implicitly realizes multi-agent credit assignment, because the individual critic provides credit\ninformation for each agent to improve its policy in the direction of increasing the global expected return\" again how so? claims like this need to be well supported.\n\n6. Expectations are usually sampled so in principle even the $O(|A|^n)$ can be estimated with fewer samples incurring some variance, it might not be necessary to bias the critic drastically for this.\n\n7. The authors need to shed more light on when the precondition $Q_i(\\tau, a_i) > Q_i(\\tau, a_i') \\iff \\beta_{a_i, \\tau}\\geq \\beta_{a_i', \\tau}$ in Prop. 1 holds beyond tabular settings. It seems a rather strong assumption to hold for all trajectory and \n$O(|A|^n)$ inputs. Right now it seems rather grab bag to show policy improvement.\n\n8. Why isn't comparison on SC2 done against more recent baselines like QTRAN, MAVEN, ROMA etc.?", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents a decomposition of the value function in the context of CCDA.

Most reviewers find this paper clear and well written, although one reviewer suggests to change the paper structure.

The method presented in this paper is simple and well justified by a theoretical section. Experiments on several domains, including Starcraft 2 micro-management tasks, are supporting the claims of that section. After some reviewers pointed out that the tabular setup is not useful in practice, the authors have extended the empirical and theoretical results to a more general setup.

Some reviewers point out that some theoretical results may not be directly related to the experimental findings. In particular, reviewer 3 does not support a central claim of the paper, and find that CDM is misleading and not provably representing the core problem.
In general, reviewer 3 does not support acceptance of this paper, but I still believe this paper should be accepted based on the other reviews (clearly in favour of acceptance). I hope that the authors and reviewer 3 will be able to further discuss and reach understanding, which hopefully should lead to fruitful results.
Decision: Accept (Poster)