DOP: OFF-POLICY MULTI-AGENT DECOMPOSED POLICY GRADIENTS
Year: 2021

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/ .

heading: 1 INTRODUCTION
text: 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 et al., 2020c). Advances in valued-based MARL (Sunehag et al., 2018; Rashid et al., 2018; Son et al., 2019; Wang et al., 2020e) contribute significantly to the progress, achieving state-ofthe-art performance on challenging tasks, such as StarCraft II micromanagement (Samvelyan et al., 2019). However, these value-based methods present a major challenge for stability and convergence in multi-agent settings (Wang et al., 2020a), 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 decentralized actors (CCDA), which not only deals with the issue of nonstationarity (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 (Iqbal & Sha, 2019).
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 policy can propagate through the centralized joint critic and negatively affect policy learning of other agents, causing catastrophic miscoordination, which we call centralized-decentralized mismatch (CDM). (3) For deterministic MAPG methods, realizing efficient credit assignment (Tumer et al., 2002; Agogino & Tumer, 2004) with a single global reward signal largely remains challenging.
∗Equal Contribution. Listing order is random.
In this paper, we find that these problems can be addressed by introducing the idea of value decomposition into the multi-agent actor-critic framework and learning a centralized but factorized critic. This framework decomposes the centralized critic as a 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-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.
A 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 a great bias-variance trade-off.
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., 2017; Mordatch & 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-art valuedbased methods in discrete-action benchmark tasks.
Related works on value decomposition methods. In value-based MARL, value decomposition (Guestrin et al., 2002b; 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 summation. QMIX (Rashid et al., 2018; 2020) proposes a non-linear monotonic factorization structure. QTRAN (Son et al., 2019) and QPLEX (Wang et al., 2020b) further extend the class of value functions that can be represented. NDQ (Wang et al., 2020e) addresses the miscoordination problem by learning nearly decomposable architectures. A concurrent work (de Witt et al., 2020) finds that a 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 multi-agent policy gradient methods.

heading: 2 BACKGROUND
text: We consider fully cooperative multi-agent tasks that can be modelled as a Dec-POMDP (Oliehoek et al., 2016) G=〈I, S,A, P,R,Ω, O, n, γ〉, where I is the finite set of agents, γ ∈ [0, 1) is the discount factor, and s ∈ S is the true state of the environment. At each timestep, each agent i receives an observation oi ∈ Ω drawn according to the observation function O(s, i) and selects an action ai ∈ A, forming a joint action a ∈ An, leading to a next state s′ according to the transition function P (s′|s,a) and a reward r = R(s,a) shared by all agents. Each agent learns a policy πi(ai|τi; θi), which is parameterized by θi and conditioned on the local history τi ∈ T ≡ (Ω × A)∗. The joint policy π, with parameters θ = 〈θ1, · · · , θn〉, induces a joint action-value function: Qπtot(τ ,a)=Es0:∞,a0:∞ [ ∑∞ t=0 γ
tR(st,at)| s0=s,a0=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 µ = 〈µ1, · · · , µn〉. 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 ability to address non-stationarity while maintaining decentralized execution. Learning a centralized critic with decentralized actors (CCDA) is 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 = Eτ ,a∼D [∑ i ∇θiµi(τi)∇aiQ µ tot(τ ,a)|ai=µi(τi) ] , (1)
and D is a replay buffer. COMA (Foerster et al., 2018) updates stochastic policies using the gradients:
g = Eπ [∑ i ∇θi log πi(ai|τi)Aπi (τ ,a) ] , (2)
where Aπi (τ ,a) = Q π tot(τ ,a) − ∑ a′i Qπtot(τ , (a-i, a ′ i)) is a counterfactual advantage (a-i is the joint action other than agent i) that deals with the issue of credit assignment and reduces variance.

heading: 3 ANALYSIS
text: In this section, we investigate challenges that limit the performance of state-of-the-art multi-agent policy gradient methods.

heading: 3.1 OFF-POLICY LEARNING FOR MULTI-AGENT STOCHASTIC POLICY GRADIENTS
text: Efficient stochastic policy learning in single-agent settings relies heavily on using off-policy data (Lillicrap 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 framework, off-policy policy evaluation—estimating Qπtot from data drawn from behavior policies β = 〈β1, . . . , βn〉—encounters major challenges. Importance sampling (Meuleau et al., 2000; Jie & Abbeel, 2010; Levine & Koltun, 2013) is a simple way to correct for the discrepancy between π and β, but, it requires computing ∏ i πi(ai|τi) βi(ai|τi) , whose variance grows exponentially with the number of agents in multi-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:
yTB = Qπtot(τ ,a) + k−1∑ t=0 γt ( t∏ l=1 λπ(al|τl) ) [rt + γEπ[Qπtot(τt+1, ·)]−Qπtot(τt,at)] , (3)
where τ0 = τ , a0 = a. However, the complexity of computing Eπ[Qπtot(τt+1, ·)] is O(|A|n), which becomes intractable when the number of agents is large. Therefore, it is challenging to develop off-policy stochastic MAPG methods.

heading: 3.2 THE CENTRALIZED-DECENTRALIZED MISMATCH ISSUE
text: In the centralized critic with decentralized actors (CCDA) framework, agents learn individual policies, πi(ai|τi; θi), conditioned on the local observation-action history. However, the gradients for updating these policies are dependent on the centralized joint critic, Qπtot(τ ,a) (see Eq. 1 and 2), 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 in the estimates of such directions.
Formally, the variance of policy gradients for agent i at (τi, ai) is dependent on other agents’ actions:
Vara-i∼π-i [Q π tot(τ , (ai,a-i))∇θi log πi(ai|τi)]
=Vara-i∼π-i [Q π tot(τ , (ai,a-i))] (∇θi log πi(ai|τi))(∇θi log πi(ai|τi))T,
(4)
where Vara-i [Q π tot(τ , (ai,a-i))] can be very large due to the exploration or suboptimality of other agents’ policies, which may cause suboptimality in individual policies. For example, suppose that the optimal joint action under τ is a∗= 〈a∗1, . . . , a∗n〉. When Ea-i∼π-i [Qπtot(τ , (a∗i ,a-i))] < 0 , πi(a∗i |τi) will decrease, possibly resulting in a suboptimal πi. 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. We call this issue centralized-decentralized mismatch (CDM).
Does CDM occur in practice for state-of-the-art algorithms? To answer this question, we carry out a case study in Sec. 5.1. We can see that the variance of DOP gradients is significantly smaller than COMA and MADDPG (Fig. 2 left). This smaller variance enables DOP to outperform other algorithms (Fig. 2 middle). We will explain this didactic example in detail in Sec. 5.1. In Sec. 5.2 and 5.3, we further show that CDM is exacerbated in sequential decision-making settings, causing divergence even after a near-optimal strategy has been learned.

heading: 3.3 CREDIT ASSIGNMENT FOR MULTI-AGENT DETERMINISTIC POLICY GRADIENTS
text: MADDPG (Lowe et al., 2017) and MAAC (Iqbal & Sha, 2019) extend deterministic policy gradient algorithms (Silver et al., 2014; Lillicrap et al., 2015) to multi-agent settings, enabling efficient offpolicy learning in continuous action spaces. However, they leave the issue of credit assignment (Tumer et 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 a probability distribution. As a result, it remains challenging to realize efficient credit assignment in deterministic cases.

heading: 4 DECOMPOSED OFF-POLICY POLICY GRADIENTS
text: 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 a Decomposed Off-Policy policy gradient (DOP) method. We factor the centralized critic as a weighted summation of individual critics across agents:
Qφtot(τ ,a) = ∑ iki(τ )Q φi i (τ , ai) + b(τ ), (5)
where φ and φi are parameters of the global and local Q functions, respectively, and ki ≥ 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.
Fig. 1 shows the architecture for learning decomposed critics. We learn individual critics Qφii by backpropagating gradients from global TD updates dependent on the joint global reward, i.e., Qφii is learned implicitly rather than from any reward specific to agent i. We enforce ki ≥ 0 by applying an absolute activation function at the last layer of the network. The network structure is described in detail in Appendix H.
Based on the critic decomposition learning, the following sections will introduce decomposed off-policy policy gradients for learning stochastic policies and deterministic policies, respectively. Similar to other actor-critic methods, DOP alternates between policy evaluation—estimating the value function for a policy—and policy improvement—using the value function to update the policy (Barto et al., 1983).

heading: 4.1 STOCHASTIC DECOMPOSED OFF-POLICY POLICY GRADIENTS
text: 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.

heading: 4.1.1 OFF-POLICY LEARNING
text: Policy Evaluation: Train the Critic As discussed in Sec. 3.1, using tree backup (Eq. 3) to carry out multi-agent off-policy policy evaluation requires calculating Eπ[Qφtot(τt+1, ·)], which needs O(|A|n) 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φtot(τ , ·)] = ∑ iki(τ )Eπi [Q φi i (τ , ·)] + b(τ ), (6)
making the tree backup technique tractable (detailed proof can be found in Appendix A.1). Another challenge of using multi-agent tree backup (Eq. 3) is that the coefficient ct = ∏t l=1 λπ(al|τl) decays
as t gets larger, which may lead to relatively lower training efficiency. To solve this issue, we propose to mix off-policy tree backup updates with on-policy TD(λ) updates to trade off sample efficiency and training efficiency. Formally, DOP minimizes the following loss for training the critic:
L(φ) = κLDOP-TBβ (φ) + (1− κ)LOnπ (φ) (7)
where κ is a scaling factor, β is the joint behavior policy, and φ is the parameters of the critic. The first loss item is LDOP-TBβ (φ) = Eβ[(yDOP-TB −Q φ tot(τ ,a))
2], where yDOP-TB is the update target of the proposed k-step decomposed multi-agent tree backup algorithm:
yDOP-TB = Qφ ′
tot(τ ,a) + k-1∑ t=0 γtct
[ rt + γ
∑ i ki(τt+1)Eπi [Q φ′i i (τt+1, ·)] + b(τt+1)−Q φ′ tot(τt,at)
] .
(8)
Here, φ′ is the parameters of a target critic, and at ∼ β(·|τt). The second loss item is LOnπ (φ) = Eπ[(yOn −Qφtot(τ ,a))2], where yOn is the on-policy update target as in TD(λ):
yOn = Qφ ′
tot(τ ,a) + ∞∑ t=0 (γλ)t [ rt + γQ φ′ tot(τt+1,at+1)−Q φ′ tot(τt,at) ] . (9)
In practice, we use two buffers, an on-policy buffer for computing LOnπ (φ) and an off-policy buffer for estimating LDOP-TBβ (φ).
Policy Improvement: Train Actors Using the linearly decomposed critic architecture, we can derive the following on-policy policy gradients for learning stochastic policies:
g = Eπ [∑ iki(τ )∇θi log πi(ai|τi; θi)Q φi i (τ , ai) ] (10)
In Appendix A.2, we provide the detailed derivation and an 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φii . (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, 2002) (Appendix A.2). Eq. 7 and 10 form the core of our DOP algorithm for learning stochastic policies, which we call stochastic DOP and is described in detail in Appendix E.
The CDM Issue occurs when decentralized policies’ suboptimality exacerbates each other through the joint critic. As an agent’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.

heading: 4.1.2 STOCHASTIC DOP POLICY IMPROVEMENT THEOREM
text: In this section, we theoretically demonstrate that stochastic DOP can converge to local optimal despite the fact that a linearly decomposed critic has limited representational capability. Since an accurate analysis for a complex function approximator (e.g., neural network) is 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φii (τ , ai) preserve the order of Q π i (τ , ai) = ∑ a-i π-i(a-i|τ-i)Qπtot(τ ,a) for a wide range of function class. Fact 1. Under mild assumptions, when value evaluation converges, ∀π, Qφii satisfies that
Qπi (τ , ai) ≥ Qπi (τ , a′i) ⇐⇒ Q φi i (τ , ai) ≥ Q φi i (τ , a ′ i), ∀τ , ai, a′i.
Detailed proof of Fact 1 can be found in Appendix C.1 as well as 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φii is sufficiently large and the loss of critic training is minimized.
Proposition 1. Suppose the function class expressed by Qφii (τ , ai) is sufficiently large (e.g. neural networks) and the following loss L(φ) is minimized
L(φ) = ∑ a,τ p(τ )π(a|τ )(Qπtot(τ ,a)−Q φ tot(τ ,a)) 2,
where Qφtot(τ ,a) ≡ ∑ iki(τ )Q φi i (τ , ai) + b(τ ). Then, we have
g = Eπ [ ∑ i∇θi log πi(ai|τi; θi)Q π(τ ,a)]
= Eπ [∑ iki(τ )∇θi log πi(ai|τi; θi)Q φi i (τ , ai) ] ,
which means stochastic DOP policy gradients are the same as those calculated using centralized critics (Eq. 2). Therefore, policy improvement is guaranteed.
The proof can be found in Appendix C.2, which is inspired by Wang et al. (2020a).

heading: 4.2 DETERMINISTIC DECOMPOSED OFF-POLICY POLICY GRADIENTS

heading: 4.2.1 OFF-POLICY LEARNING
text: To enable efficient learning with continuous actions, we propose deterministic DOP. As in singleagent settings, because deterministic policy gradient methods avoid the integral over actions, it greatly eases the cost of off-policy learning (Silver et al., 2014). For policy evaluation, we train the critic by minimizing the following TD loss:
L(φ) = E(τt,rt,at,τt+1)∼D [( rt + γQ φ′ tot(τt+1,µ(τt+1; θ ′))−Qφtot(τt,at) )2] , (11)
where D is a replay buffer, and φ′, θ′ are the parameters of the target critic and actors, respectively. For policy improvement, we derive the following deterministic DOP policy gradients:
g = Eτ∼D [∑ iki(τ )∇θiµi(τi; θi)∇aiQ φi i (τ , ai)|ai=µi(τi;θi) ] . (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 a linearly decomposed critic is used. Based on Eq. 11 and Eq. 12, we develop the DOP algorithm for learning deterministic policies in continuous action spaces, which is described in Appendix E and called deterministic DOP.

heading: 4.2.2 REPRESENTATION CAPACITY OF DETERMINISTIC DOP CRITICS
text: In continuous and smooth environments, we first show that a DOP critic has sufficient expressive capability to represent Q values in the proximity of µ(τ ),∀τ with a bounded error. For simplicity, we denote Oδ(τ ) = {a| ‖ a− µ(τ ) ‖2≤ δ}. Fact 2. Assume that ∀τ ,a,a′ ∈ Oδ(τ ), ‖ ∇aQµtot(τ ,a)−∇a′Qµtot(τ ,a′) ‖2≤ L ‖ a− a′ ‖2. The estimation error of a DOP critic can be bounded by O(Lδ2) for a ∈ Oδ(τ ),∀τ .
Detailed proof can be found in Appendix D. Here we assume that the gradients of Q-values with respect 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 µ(τ ),∀τ are well estimated with a bounded error, deterministic DOP policy gradients are good approximation to the true gradients (Eq. 1). Approximately, |∇aiQ µ tot(τ ,a)−∇aiki(τ )∇aiQ φi i (τ , ai)| ∼ O(Lδ),∀i when δ 1. For detailed proof, we refer readers to Appendix D.

heading: 5 EXPERIMENTS
text: 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 of off-policy learning? (Sec. 5.2.1) (3) Can deterministic DOP learn reasonable credit assignment? (Sec. 5.3) (4) Can DOP outperform state-of-the-art MARL algorithms? For evaluation, all the results are averaged over 12 different random seeds and are shown with 95% confidence intervals.

heading: 5.1 DIDACTIC EXAMPLE: THE CDM ISSUE AND BIAS-VARIANCE TRADE-OFF
text: We use a didactic example to demonstrate how DOP attenuates CDM and achieves bias-variance trade-off. In a state-less game with 3 agents and 14 actions, if agents take action1, 5, 9, respectively, they get a team reward of 10; otherwise -10. 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-Softmax 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. 2-left). As discussed in Sec. 3.2, large variance of other algorithms is due to the CDM issue that undecomposed joint critics are affected by actions of all agents. Free from the influence of other agents, DOP preserves the order of local Q-values (bottom of Fig. 2-right) and effectively reduces the variance of policy gradients. In this way, DOP sacrifices value estimation accuracy for accurate and low-variance policy gradients, which explains why it can outperform other algorithms (Fig. 2-middle).

heading: 5.2 DISCRETE ACTION SPACES: THE STARCRAFT II MICROMANAGEMENT BENCHMARK
text: We evaluate stochastic DOP on the challenging SMAC benchmark (Samvelyan et al., 2019) for its high control complexity. We compare our method with the state-of-the-art 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., 2020b)), exploration method (MAVEN, Mahajan et al. (2019)), and role-based method (ROMA, Wang et al. (2020c)). 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 state-of-the-art value-based methods.

heading: 5.2.1 ABLATIONS
text: 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-policy policy evaluations tractable. We test the contribution of each component by carrying out the following ablation studies.
Off-Policy Learning In our method, κ controls the "off-policyness" of training. For DOP, we set κ to 0.5. To demonstrate the effect of off-policy learning, we change κ to 0 and 1 and compare the performance. In Fig. 4, we can see that both DOP and off-policy DOP perform much better than the on-policy version (κ=0), highlighting the importance of using off-policy data. Moreover, purely off-policy learning generally needs more samples to 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 as 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 a 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 a near-optimal policy has been learned. For example, on map so_many_baneling, 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 as DOP except that Eπ[Qφtot(τ , ·)] is estimated by sampling 200 joint actions from π. Here, we estimate this expectation by sampling because direct computation is intractable (for example, 2010 summations are needed on the map MMM). Fig. 4 shows that when the number of 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.

heading: 5.3 CONTINUOUS ACTION SPACES: MULTI-AGENT PARTICLE ENVIRONMENTS
text: 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 (Iqbal & 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 as 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 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
shown in Fig. 5-left – methods with undecomposed critics can find rewarding configurations but then quickly diverge, while DOP converges with stability.
Credit Assignment We use task Mill to 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 or counterclockwise with force between 0 and 1. If the millstone’s angular velocity, ω, gets greater than 30, agents are rewarded 3 per step. If ω exceeds 100 in 10 steps, the agents win the episode and get a reward of 10; otherwise, they lose and get a punishment of -10. Fig. 5-right shows that deterministic DOP can gradually learn a 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, as shown in Fig. 5-middle.

heading: 6 CLOSING REMARKS
text: This paper pinpointed drawbacks that hinder the performance of state-of-the-art MAPG algorithms: on-policy learning of stochastic policy gradient methods, the centralized-decentralized mismatch problem, and the credit assignment issue in 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.

heading: ACKNOWLEDGMENTS
text: We would like to thank the anonymous reviewers for their insightful comments and helpful suggestions. This work is supported in part by Science and Technology Innovation 2030 – “New Generation Artificial Intelligence” Major Project (No. 2018AAA0100904), and a grant from the Institute of Guo Qiang, Tsinghua University.

heading: A MATHEMATICAL DETAILS FOR STOCHASTIC DOP
text: A.1 DECOMPOSED CRITICS ENABLE TRACTABLE MULTI-AGENT TREE BACKUP
In Sec. 4.1.1, we propose to use tree backup (Precup et al., 2000; Munos et al., 2016) to carry out multi-agent off-policy policy evaluation. When a joint critic is used, calculating Eπ [ Qφtot(τ , ·) ] requires O(|A|n) steps of summation. To solve this problem, DOP uses a linearly decomposed critic, and it follows that:
Eπ[Qφtot(τ ,a)] = ∑ a π(a|τ )Qφtot(τ ,a) = ∑ a π(a|τ ) [∑ i ki(τ )Q φi i (τ , ai) + b(τ ) ] = ∑ a π(a|τ ) ∑ i ki(τ )Q φi i (τ , ai) + ∑ a π(a|τ )b(τ )
= ∑ i ∑ ai πi(ai|τi)ki(τ )Qφii (τ , ai) ∑ a-i π-i(a-i|τ-i) + b(τ )
= ∑ i ki(τ )Eπi [Q φi i (τ , ·)] + b(τ ),
(13)
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: g = Eπ [∑ iki(τ )∇θi log πi(ai|τi; θi)Q φi i (τ , ai) ] . (14)
We now derive it in detail.
Proof. We use the aristocrat utility (Wolpert & Tumer, 2002) to perform credit assignment:
Ui(τ , ai) = Q φ tot(τ ,a)− ∑ x πi(x|τi)Qφtot(τ , (x,a−i))
= ∑ j kj(τ )Q φj j (τ , aj)− ∑ x πi(x|τi) ∑ j 6=i kj(τ )Q φj j (τ , aj) + ki(τ )Q φi i (τ , x)  = ki(τ )Q φi i (τ , ai)− ki(τ )
∑ x πi(x|τi)Qφii (τ , x)
= ki(τ ) [ Qφii (τ , ai)− ∑ x πi(x|τi)Qφii (τ , x) ] ,
It is worth noting that Ui is independent of other agents’ actions. Then, for the policy gradients, we have:
g = Eπ[ ∑ i ∇θ log πi(ai|τi)Ui(τ , ai)]
= Eπ [∑ i ∇θ log πi(ai|τi)ki(τ ) ( Qφii (τ , ai)− ∑ x πi(x|τi)Qφii (τ , x) )]
= Eπ [∑ i ∇θ log πi(ai|τi)ki(τ )Qφii (τ , ai) ] .
A.2.2 OFF-POLICY VERSION
In Appendix A.2, we 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-policy policy gradients for learning stochastic policies are:
g = Eβ [ π(τ ,a)
β(τ ,a)
∑ iki(τ )∇θ log πi(ai|τi; θi)Q φi i (τ , ai) ] . (15)
Proof. The objective function is:
J(θ) = Eβ [V πtot(τ )] .
Similar to Degris et al. (2012), we have:
∇θJ(θ) = Eβ [ π(a|τ ) β(a|τ ) ∑ i ∇θ log πi(ai|τi)Ui(τ , ai) ]
= Eβ [ π(a|τ ) β(a|τ ) ∑ i ∇θ log πi(ai|τi)ki(τ )Ai(τ , ai) ]
= Eβ [ π(a|τ ) β(a|τ ) ∑ i ∇θ log πi(ai|τi)ki(τ )Qφii (τ , ai) ] .

heading: B MATHEMATICAL DETAILS FOR DETERMINISTIC DOP
text: B.1 DETERMINISTIC DOP POLICY GRADIENT THEOREM
In Sec. 4.2.1, we give the following deterministic DOP policy gradients: ∇J(θ) = Eτ∼D [∑ iki(τ )∇θiµi(τi; θi)∇aiQ φi i (τ , ai)|ai=µi(τi;θi) ] . (16)
Now we present the derivation of this update rule.
Proof. Drawing inspirations from single-agent cases (Silver et al., 2014), we have:
∇J(θ) = Eτ∼D[∇θQφtot(τ ,a)] = Eτ∼D[ ∑ i ∇θki(τ )Qφii (τ , ai)|ai=µi(τi;θi)]
= Eτ∼D[ ∑ i ∇θµi(τi; θi)∇aiki(τ )Q φi i (τ , ai)|ai=µi(τi;θi)].

heading: C THEORETICAL JUSTIFICATION FOR STOCHASTIC DOP POLICY IMPROVEMENT
text: In order to understand how DOP works despite the biased Qπ(τ ,a) estimation, we provide some theoretical justification for the policy update. Unfortunately, a thorough analysis on deep neural network and TD-learning is too complex to be carried out. Thus, we make some assumptions for the mathematical proof. The following two subsections provide two different view points of theoretical understanding.
1. In the first view (Sec. C.1), we assume some mild assumptions on value evaluation which holds on a wide range of function class. In this way, we can prove a policy improvement theorem similar to Degris et al. (2012).
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 critics output Qφii (τ , ai) to be a good estimate of Q π i (τ , ai)), the DOP gradients in Eq. 12 equal to Eq. 2
which is the standard gradient form.
C.1 PROOF OF STOCHASTIC DOP POLICY IMPROVEMENT THEOREM
Inspired by previous work (Degris et al., 2012), we relax the requirement that Qφtot is a good estimate of Qπtot and show that stochastic DOP still guarantees policy improvement.
First, we define Qπi (τ , ai) = ∑ a-i π-i(a-i|τ-i)Qπtot(τ ,a), Aπi (τ , ai) = ∑ a-i π(a-i|τ-i)Aπi (τ ,a).
Directly analyzing the minimization of TD-error is challenging. To make it tractable, some works (Feinberg et al., 2018) simplify this analysis to an MSE problem. For the analysis of stochastic DOP, we adopt the same technique and formalize the critic’s learning as the following problem:
L(φ) = ∑ a,τ p(τ )π(a|τ ) ( Qπtot(τ ,a)−Q φ tot(τ ,a) )2 , (17)
where Qπtot(τ ,a) are the true values, which are fixed during optimization. In the following analysis, we assume distinct parameters for different τ . We first show that Fact 1 holds for a wide range of function class of Qφii . To this end, we first prove the following lemma. Lemma 1. Without loss of generality, we consider the following optimization problem:
Lτ (φ) = ∑ a π(a|τ ) ( Qπ(τ ,a)− f(Qφ(τ ,a)) )2 . (18)
Here, f(Qφ(τ ,a)) : Rn → R, and Qφ(τ ,a) is a vector whose ith entry is Qφii (τ , ai). In DOP, f satisfies that ∂f
∂Q φi i (τ ,ai)
> 0 for any i, ai.
If ∇φiQ φi i (τ , ai) 6= 0,∀φi, ai it holds that:
Qπi (τ , ai) ≥ Qπi (τ , a′i) ⇐⇒ Q φi i (τ , ai) ≥ Q φi i (τ , a ′ i), ∀ai, a′i.
Proof. When the optimization converges, φi reaches a stationary point where∇φiLτ (φ) = 0,∀i. πi(ai|τi) ∑ a-i ∏ j 6=i πj(aj |τj) ( Qπtot(τ ,a)− f(Qφ(τ ,a)) ) (− ∂f ∂Qφii (τ , ai) )∇φiQ φi i (τ , ai) = 0, ∀ai.
Since∇φiQ φi i (τ , ai) 6= 0, this implies that ∀i, ai, we have∑
a-i ∏ j 6=i πj(aj |τj)(Qπtot(τ ,a)− f(Qφ(τ ,a))) = 0
⇒ ∑ a-i π-i(a-i|τ-i)f(Qφ(τ ,a)) = Qπi (τ , ai)
We consider the function q(τ , ai) = ∑ a-i π-i(a-i|τ−i)f(Qφ(τ ,a))), which is a function of Qφ. Its partial derivative w.r.t Qφii (τ , ai) is:
∂q(τ , ai) ∂Qφii (τ , ai) = ∑ a-i π-i(a-i|τ-i) ∂f(Qφ(τ ,a)) ∂Qφii (τ , ai) > 0
Therefore, if Qπi (τ , ai) ≥ Qπi (τ , a′i), then any local minimal of Lτ (φ) satisfies Q φi i (τ , ai) ≥ Qφii (τ , a ′ i).
We argue that ∇φiQ φi i (τ , ai) 6= 0 is a rather mild assumption and holds for a large range of function class of Qφii .
Fact 3. [Formal Statement of Fact 1] For the following choices of Qφii :
1. Tabular expression of Qφii which requires Q(n|A||τ |) space;
2. Linear function class where ai are one-hot coded:
Qφii (τ , ai) = φi · 〈τ , ai〉;
3. 2-layer neural networks (φi 6= 0) with strictly monotonic increasing activation functions (e.g. tanh, leaky-relu).
4. Arbitrary k-layer neural networks whose activation function at the (k−1)th layer is sigmoid.
when value evaluation converges, ∀π, Qφii satisfies that
Qπi (τ , ai) ≥ Qπi (τ , a′i) ⇐⇒ Q φi i (τ , ai) ≥ Q φi i (τ , a ′ i), ∀τ , ai, a′i.
Proof. We need to prove that∇φiQ φi i (τ , ai) 6= 0. For brevity, we use aki to denote the kth element of the one-hot coding, and use φta k i
i to denote the weight connecting the t th element of the upper layer
and the aki element.
(1 & 2) For tabular expression and linear functions, ∀ai = k we have
∂Qφii (τ , ai)
∂φ 1aki i
= 1
(3) The 2-layer neural network can be written as Qφii (τ , ai) = W2σ(W1(τ , ai)). Besides, we denote the hidden layer as h. Since φi 6= 0, we consider some nonzero element φW21t,i. For the kth action, the gradient of the parameter φW1tk,i is
∂Qφii (τ , ai)
∂φW1tk,i = φW21t,iσ ′(ht) 6= 0, ∀k
(4) Without loss of generality, we consider the last layer φWk1t,i:
∂Qφii (τ , ai)
∂φWk1t,i = σ(hk−1t ) > 0
These are the cases where ∇φiQ φi i 6= 0. Even when ∃φi,∇φiQ φi i = 0 , such φi usually occupy only a small parameter space and happen with a small probability. As a result, we conclude that ∇φiQ φi i (τ , ai) 6= 0 is a rather mild assumption.
Based on Fact 1, we are able to prove the policy improvement theorem for stochastic DOP. We will show that even without an accurate estimate of Qπtot, the stochastic DOP policy updates can still improve the objective function J(π) = Eπ[ ∑ t γ trt]. We first prove the following lemma.
Lemma 2. For two sequences {ai}, {bi}, i ∈ [n] listed in an increasing order. If ∑ i bi = 0, then∑
i aibi ≥ 0.
Proof. We denote ā = 1n ∑ i ai, then ∑ i aibi = ā( ∑ i bi) + ∑ i ãibi where ∑ i ãi = 0. Without loss of generality, we assume that āi = 0,∀i. j and k which aj ≤ 0, aj+1 ≥ 0 and bk ≤ 0, bk+1 ≥ 0. Since a, b are symmetric, we assume j ≤ k. Then we have∑
i∈[n] aibi = ∑ i∈[1,j] aibi + ∑ i∈[j+1,k] aibi + ∑ i∈[k+1,n] aibi
≥ ∑
i∈[j+1,k]
aibi + ∑
i∈[k+1,n]
aibi
≥ ak ∑
i∈[i+1,k]
bi + ak+1 ∑
i∈[k+1,n]
bi
As ∑ i∈[j+1,n] bi ≥ 0, we have − ∑ i∈[j+1,k] bi ≤ ∑ i∈[k+1,n] bi.
Thus, ∑ i∈[n] aibi ≥ (ak+1 − ak) ∑ i∈[k+1,n] bi ≥ 0.
Based on Fact 1 and 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 to π, denote πi(ai|τi) = πoi (ai|τi) + βai,τ δ, where δ > 0 is a sufficiently small number. If it holds that ∀τ, a′i, ai, Q φi i (τ , ai) ≥ Q φi i (τ , a ′ i) ⇐⇒ βai,τ ≥ βa′i,τ (MONOTONE condition, and φi is the parameters before update.), then we have
J(π) ≥ J(πo), (19)
i.e., the joint policy is improved by the update.
Proof. Under Fact 1, it follows that
Qπ o i (τ , ai) > Q πo i (τ , a ′ i) ⇐⇒ βai,τ ≥ βa′i,τ . (20)
Since J(π) = ∑ τ0 p(τ0)V π tot(τ0), it suffices to prove that ∀τt, V πtot(τt) ≥ V π o
tot (τt). We have:∑ at π(at|τt)Qπ o tot(τt,at) = ∑ at ( n∏ i=1 πi(a t i|τ ti ) ) Qπ o tot(τt,at)
= ∑ at ( n∏ i=1 (πoi (a t i|τ ti ) + βati,τtδ) ) Qπ o tot(τt,at)
= V π o tot (τt) + δ n∑ i=1 ∑ at βati,τt ∏ j 6=i πoj (a t j |τ tj ) Qπotot(τt,at) + o(δ) = V π o
tot (τt) + δ n∑ i=1 ∑ ati βati,τtQ πo i (τt, a t i) + o(δ). (21)
Since δ is sufficiently small, in the following analysis we omit o(δ). Observing that ∑ ai πi(ai|τi) =
1,∀i, we get ∑ ai βai,τ = 0. Thus, by Lemma 2 and Eq. 21, we have∑
at
π(at|τt)Qπ o tot(τt,at) ≥ V π o tot (τt). (22)
Similar to the policy improvement theorem for tabular MDPs (Sutton & Barto, 2018) , we have
V π o tot (τt) ≤ ∑ at π(at|τt)Qπ o tot(τt,at)
= ∑ at π(at|τt) r(τt,at) + γ∑ τt+1 p(τt+1|τt,at)V π o tot (τt+1) 
≤ ∑ at π(at|τt) r(τt,at) + γ∑ τt+1 p(τt+1|τt,at) ∑ at+1 π(at+1|τt+1)Qπ o tot(τt+1,at+1)  ≤ · · · ≤ V πtot(τt).
This implies J(π) ≥ J(πo) for each update.
Moreover, we verify that ∀τ, a′i, ai, Q φi i (τ , ai) > Q φi i (τ , a ′ i) ⇐⇒ βai,τ ≥ βa′i,τ (the MONOTONE condition) holds for any π with a tabular expression. For these π, let πi(ai|τi) = θai,τ , then it holds that ∑ ai θai,τ = 1. Since the gradient of policy update can be written as:
∇θJ(πθ) = Ed(τ) [∑ i ki(τ )∇θ log πi(ai|τi; θi)Qφii (τ , ai) ] = ∑ τ d(τ) ∑ i ki(τ )∇θiπ(ai|τi)Q φi i (τ , ai)
= ∑ τ d(τ) ∑ i ki(τ )∇θiπ(ai|τi)A φi i (τ , ai)
where dπ(τ) is the occupancy measure w.r.t our algorithm. With a tabular expression, the update of each θai,τ is proportion to βai,τ
βai,τ ∝ dη(πθ)
dθai,τ = d(τ )Aφii (τ , ai)
Clearly, βa′i,τ ≥ βai,τ ⇐⇒ Q φi i (τ , a ′ i) ≥ Q φi i (τ , ai) .
C.2 ANALYSIS WITHOUT MONOTONE CONDITION
For practical implementation of policy πi(ai|τi), the MONOTONE condition is too strong to be satisfied for all πi. Analyzing the policy update when the condition is violated is difficult with only Fact 1 at hand. Therefore, it is beneficial to understand policy improvement without the MONOTONE condition.
To bypass the MONOTONE condition, we require a stronger property of the learnt Qφii (τ , ai) in addition to order preserving (Fact 1). Theorem 1 in Wang et al. (2020a) offers a closed form solution of additive decomposition and we restate it as the following lemma Lemma 3 (Restatement of Theorem 1 in Wang et al. (2020a)). If we consider the solution of
arg min Q ∑ (s,a)∈S×A π(a|τ )
( y(τ ,a)−
n∑ i=1 Qi(τ , ai)
)2 ,
∀i ∈ [n],∀τ ,a the individual action-value function Qi(τ , ai) =
E a−i∼π−i(·|τ−i) [y (τ , ai, a−i)]− n− 1 n E a∼π(·|τ ) [y(τ ,a)] + wi(s), (23)
The residual term w is an arbitrary vector satisfying ∀s, ∑n i=1 wi(s) = 0.
Based on this lemma, we can derive another proposition to theoretically justify the DOP architecture.
Proposition 1. Suppose the function class expressed by Qφii (τ , ai) is sufficiently large (e.g. neural networks) and the following loss L(φ) is minimized
L(φ) = ∑ a,τ p(τ )π(a|τ )(Qπtot(τ ,a)−Q φ tot(τ ,a)) 2,
where Qφtot(τ ,a) ≡ ∑ iki(τ )Q φi i (τ , ai) + b(τ ). Then, we have
g = Eπ [ ∑ i∇θi log πi(ai|τi; θi)Q π(τ ,a)]
= Eπ [∑ iki(τ )∇θi log πi(ai|τi; θi)Q φi i (τ , ai) ] ,
which means stochastic DOP policy gradients are the same as those calculated using centralized critics (Eq. 2). Therefore, policy improvement is guaranteed.
Proof. For brevity, we denote Qkφii (τ , ai) = k(τ )Q φi i (τ , ai). Then L(φ) can be written as L(φ) = ∑ a,τ p(τ )π(a|τ )(Qπtot(τ ,a)− ∑ iQk φi i (τ , ai)− b(τ )) 2
According to Lemma 3, when L(φ) is minimized, we have
Qkφii (τ , ai) = Q π i (τ , ai)− n− 1 n V π(τ ) + wi(s)− 1 n b∗(τ )
= Qπi (τ , ai)− w′i(τ )
Then
g = Eπ [∑ iki(τ )∇θi log πi(ai|τi; θi)Q φi i (τ , ai) ] = Eπ [∑ i∇θi log πi(ai|τi; θi)Qk φi i (τ , ai)
] = Eπ [ ∑ i∇θi log πi(ai|τi; θi)Q π(τ ,a)]
Therefore, in expectation, stochastic DOP gradients are the same as those calculated using centralized critics (Eq. 2). We no longer require the MONOTONE condition to guarantee improvement of the policy update. Proposition 1 is another point of view to explain the performance guarantee of DOP despite its constrained critics.

heading: D REPRESENTATIONAL CAPABILITY OF DETERMINISTIC DOP CRITICS
text: In Sec. 4.2.2, we present the following facts about deterministic DOP: Fact 2. Assume that ∀τ ,a,a′ ∈ Oδ(τ ), ‖ ∇aQµtot(τ ,a)−∇a′Qµtot(τ ,a′) ‖2≤ L ‖ a− a′ ‖2. The estimation error of a DOP critic can be bounded by O(Lδ2) for a ∈ Oδ(τ ),∀τ .
We consider the Taylor expansion with Lagrange remainder of Qµtot(τ ,a). Namely,
Qµtot(τ ,a) = Q µ tot(τ ,µ(τ)) +∇aQ µ tot(τ ,a)|a=µ(τ ) · (a− µ(τ )) +
1 2 ∇2Qµtot(τ ,aζ) ‖ a− π(τ ) ‖2
Since ∀a ∈ Oδ(π(τ )), we have
|Qµtot(τ ,a)−Q µ tot(τ ,µ(τ ))−∇aQ µ tot(τ ,a)|a=µ(τ ) · (a− µ(τ ))| ≤
1 2 Lδ2
Noticing that the first order Taylor expansion of Qµtot has the form ∑ [n] ki(τ )Q φ i (τ , ai) + b(τ ). Therefore, the optimal solution of the MSE problem in Eq. 17 under DOP critics has an error term less than O(Lδ2) for arbitrary sampling distribution p(τ ,a) of a ∈ Oδ(µ(τ )). When Q values in the proximity of µ(τ ),∀τ is well estimated within a bounded error and δ 1, approximately, we have
|∂Q µ tot(τ ,a)
∂ai − ∂Q
φ tot(τ ,a)
∂ai | ≈ |Q
µ tot(τ , a−i, ai + δ)−Q µ tot(τ ,a)
δ − Q
φ tot(τ , a−i, ai + δ)−Q φ tot(τ ,a)
δ |
= |Q µ tot(τ , a−i, ai + δ)−Q φ tot(τ , a−i, ai + δ)
δ − Q
µ tot(τ ,a)−Q φ tot(τ ,a)
δ |
∼ O(Lδ)

heading: E ALGORITHMS
text: In this section, we describe the details of our algorithms, as shown in Algorithm 1 and 2.
Algorithm 1 Stochastic DOP
Initialize a critic networkQφ, actor networks πθi , and a mixer networkM ψ with random parameters φ,θi, ψ. Initialize target networks: φ′ = φ, θ′ = θ, ψ′ = ψ Initialize an off-policy replay buffer Doff and an on-policy replay buffer Don. for t = 1 to T do
Generate a trajectory and store it in Doff and Don Sample a batch consisting of N1 trajectories from Don Update decentralized policies using the gradients described in Eq. 10 Calculate LOn(φ) Sample a batch consisting of N2 trajectories from Doff Calculate LDOP-TB(φ) Update critics using LOn(φ) and LDOP-TB(φ) if t mod d = 0 then
Update target networks: φ′ = φ, θ′ = θ, ψ′ = ψ end if
end for
Algorithm 2 Deterministic DOP
Initialize a critic networkQφ, actor networks µθi and a mixer networkM ψ with random parameters θ, φ, ψ Initialize target networks: φ′ = φ, θ′ = θ, ψ′ = ψ Initialize replay buffer D for t = 1 to T do
Select action with exploration noise a ∼ µ(τ )+ , generate a transition and store the transition tuple in D
Sample N transitions from D Update the critic using the loss function described in Eq. 11 Update decentralized policies using the gradients described in Eq. 12 if t mod d = 0 then
Update target networks: φ′ = αφ+ (1−α)φ′, θ′ = αθ+ (1−α)θ′, ψ′ = αψ+ (1−α)ψ′ end if
end for

heading: F DOP WITH COMMUNICATION
text: Although DOP can solve many coordination problems, as shown by the comparison against IQL in Fig.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(a)), two agents randomly start at states a1 to am and b1 to bn, respectively. Agents can observe their position and choose to move left, move right, or keep still at each timestep. Agents win and are rewarded 10 if they arrive at state g simultaneously. Otherwise, if any agent arrives at g earlier 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 on hallway with m=n=4, the team can win only 25% of the games (Fig. 7(b)). Equipping DOP with communication can largely solve the problem – agents learn to communicate their positions and move left at a1 or b1 simultaneously. For communication, we
use the technique introduced by Wang et al. (2020e). Agents share a communication module, and messages are passed both between actors and individual Q-functions.
Such miscoordination problems are common in complex multi-agent tasks (Wang et al., 2020e). We believe introducing communication into DOP can help it solve a larger range of problems.

heading: G BASELINE BY SAMPLING
text: One problem of existing MAPG methods is the CDM issue, which describes the large variance in policy gradients caused by the influence of 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). In this section, we investigate whether using baselines can effectively reduce variance in multi-agent 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. 5, we omit it here and study the baseline where actions of all agents are marginalized. In multi-agent settings, the calculation of this baseline requires computing an 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 we call Regular Critics with Baseline. Results are shown in Fig. 8. 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 hyper-parameter settings, which are described in the following sections.
H.1 STOCHASTIC DOP
In stochastic DOP, each agent has a 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 s. The output of the local utility networks is Qφii (τ , ·) 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, ki and b, are generated by linear networks conditioned on the global state s. ki is enforced to be non-negative by applying absolute activation at the last layer. We then divide ki by ∑ i ki to scale ki 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 fully-connected layer.
For all experiments, we set κ = 0.5 and use an off-policy replay buffer storing the latest 5000 episodes and an on-policy buffer with a size of 32. We run 4 parallel environments to collect data. The optimization of both the critic and actors is conducted using RMSprop with a learning rate of 5 × 10−4, α 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 500k 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 1× 10−4 and 5× 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 deterministic DOP. For actors, we use a fully-connected forward network with two 64-dimensional hidden layers with ReLU activation, and the output of actors is a local action. We use an off-policy 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× 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 a single environment to collect data, because we empirically find it more sample efficient than parallel environments in the MPE benchmark. RMSprop with a learning rate of 5 × 10−4, α 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.

heading: I RELATED WORKS
text: Cooperative multi-agent reinforcement learning provides a scalable approach to learning collaborative strategies for many challenging tasks (Vinyals et al., 2019; Berner et al., 2019; Samvelyan et al., 2019; Jaderberg et al., 2019) and a computational framework to study many problems, including the emergence of tool usage (Baker et al., 2020), communication (Foerster et al., 2016; Sukhbaatar et al., 2016; Lazaridou et al., 2017; 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-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 a promising approach to achieve scalable centralized learning, which exploits coordination independencies between agents and decomposes a global reward function into a 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 is 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; Son et al., 2019; Wang et al., 2020e). The stability of multi-agent off-policy learning is a long-standing problem. Foerster et al. (2017); Wang et al. (2020a) study this problem in value-based methods. In this paper, we focus on how to achieve efficient off-policy policy-based learning. Our work is complementary to previous work based on multi-agent policy gradients, such as those regarding multi-agent multi-task learning (Teh et al., 2017; Omidshafiei et al., 2017) and multi-agent exploration (Wang et al., 2020d).
Multi-agent policy gradient algorithms enjoy stable convergence properties compared to value-based methods (Gupta et al., 2017; 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; Zhang et al., 2018; Yang et al., 2018; Cassano et al., 2018; Suttle et al., 2019; Zhang & Zavlanos, 2019). Different from the setting of this paper, agents have local reward functions and full observation of the true state in these works.

Review summaries:
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.

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.