More Centralized Training, Still Decentralized Execution: Multi-Agent Conditional Policy Factorization
Authors: Jiangxing Wang
Deheng Ye
Zongqing Lu
Venue: ICLR 2023 poster (2023)
Keywords: Multi-Agent Reinforcement Learning

Abstract: In cooperative multi-agent reinforcement learning (MARL), combining value decomposition with actor-critic enables agents to learn stochastic policies, which are more suitable for the partially observable environment. Given the goal of learning local policies that enable decentralized execution, agents are commonly assumed to be independent of each other, even in centralized training. However, such an assumption may prohibit agents from learning the optimal joint policy. To address this problem, we explicitly take the dependency among agents into centralized training. Although this leads to the optimal joint policy, it may not be factorized for decentralized execution. Nevertheless, we theoretically show that from such a joint policy, we can always derive another joint policy that achieves the same optimality but can be factorized for decentralized execution. To this end, we propose multi-agent conditional policy factorization (MACPF), which takes more centralized training but still enables decentralized execution. We empirically verify MACPF in various cooperative MARL tasks and demonstrate that MACPF achieves better performance or faster convergence than baselines. Our code is available at https://github.com/PKU-RL/FOP-DMAC-MACPF.

Published as a conference paper at ICLR 2023
MORE CENTRALIZED TRAINING, STILL DECENTRAL- IZED EXECUTION: MULTI-AGENT CONDITIONAL POL- ICY FACTORIZATION
Jiangxing Wang
Deheng Ye
Zongqing Lu
School of Computer Science
Tencent Inc.
School of Computer Science Peking University zongqing Lu@pku, edu,
Peking University
dericye@tencenttco com
jiangxiwestu. pku. edu.
ABSTRACT
In cooperative multi-agent reinforcement learning (MARL), combining value decomposition with actor-critic enables agents to learn stochastic policies, which are more suitable for the partially observable enviromment. Given the goal of learning local policies that enable decentralized execution, agents are commonly assumed be independent of each other, even in centralized training. However, such assumption may prohibit agents from learning the optimal joint policy. To address this problem, we explicitly take the dependency among agents into centralized training. Although this leads to the optimal joint policy, it may not be factorized for decentralized execution. Nevertheless, we theoretically show that from such joint policy, the same optimality but can be factorized for decentralized execution. To this end, we propose multi-agent conditional policy factorization (MACPF), which takes more centralized training but still enables decentralized execution. We empirically verify MACPF in various cooperative MARL tasks and demonstrate that MACPF achieves better performance or faster convergence than baselines. Our code is available http://gittbb.oom//KK..///O/--D
always derive another joint policy that achieves
INTRODUCTION
The cooperative multi-agemt reinforcement learning (MARL) problem has attracted the attention of many researchers as it is a well-abstracted model for many real-world problems, such as traffic signal control (Wang al., 2021a) and autonomous warehouse (Zhou et al., 2021). In a cooperative MARL problem, we aim to train a group of agents that can cooperate to achieve common goal. Such common goal is often defined by a global reward function that is shared among all agents. If centralized control is allowed, such problem can be viewed as a single-agent reinforcement learning problem with an enormous action space. Based on this intuition, Kraemer & Banerjee (2016) proposed the centralized training with decentralized execution (CTDE) framework to overcome the non-stationarity of MARL. In the CTDE framework, a centralized value function is learned to guide the update of each agent's 's local policy, which enables decentralized execution.
With a centralized value function, there are different ways to guide the learning of the local policy of each agent. One line of research, called value decomposition (Sunehag et al., 2018), obtains local policy by factorizing this centralized value function into the utility function each agent. In order to ensure that the update of local policies can indeed bring the improvement of joint policy, Individual-Gloaal Malobal-Max (IGM) is introduced to guarantee the consistency between joint and local policies. Based on the different interpretations of IGM, various MARL algorithms have been proposed, such as VDN (Sunehag et al., 2018), 8), QMIX (Rashid et al., 2018), QTRAN (Son et al., 2019), and QPLEX (Wang al., 2020a). IGM only specifies the relationship between optimal local actions and optimal joint action, which is often used to learn deterministic policies. In order to learn stochastic policies, which are more suitable for the partially observable environment, recent studies (Su et al., 2021; Wang et al., 2020b; Zhang et al., 2021; Su & Lu, 2022) combine the idea of
1 Corresponning Author

---

Published as a conference paper at ICLR 2023
value decomposition with actor-critic. While most of these decomposed actor-critic methods do not guarantee optimality, FOP (Zhang et al., 2021) introduces -oaettaa--Gobb--Opppie (IGO) for the optimal joint policy learning in terms of maximum-entropy objective and derives the corresponding way of value decomposition. It is proved that factorized local policies of FOP converge to the global optimum, given that IGO is satisfied.
The essence of IGO is for all agents to be independent of each other during both training and execution. However, we find this requirement dramatically reduces the expressiveness of the joint policy, making the learning algorithm fail to converge to the global optimal joint policy, even in some simple scenarios. As centralized training is allowed, a natural way to address this issue is to factorize the joint policy based on the chain rule (Schum, 2001), such that the dependency among agents' policies explicitly considered, and the full expressiveness of the joint policy can be achieved. By incorporating such joint policy factorization into the soft policy iteration (Haarnoja et al., 2018), we can obtain an optimal joint policy without the IGO condition. Though optimal, a joint policy induced by such learning method may not be decomposed into independent local policies, thus decentralized execution not fulfilled, which is the limitation of many previous works that consider dependency among agents (Bertsekas, 2019; Fu et al., 2022).
To fulfill decentralized execution, we first theoretically show that for such a dependent joint policy, there always exists another independent joint policy that achieves the same expected return but can be decomposed into independent local policies. To learn the optimal joint policy while preserving decentralized execution, we propose multi-agent conditional policy factorization (MACPF), where we represent the dependent local policy by combining an independent local policy and a dependency policy correction. The dependent local policies factorize the optimal joint policy, while the indepen- dent local policies constitute their independent counterpart that enables decentralized execution. We evaluate MACPF in several tasks, including matrix game (Rashid al., 2020), SMAC (Samvelyan et al., 2019), and MPE (Lowe et al., 2017). Empirically, MACPF consistently outperforms its base method, i.e., FOP, and achieves better performance or faster convergence than other baselines. By ablation, we verify that the independent local policies can indeed obtain the same level of performance as the dependent local policies.
PRELIMINARIES
2.1 MUL.I--GENT MARKOV DECISION PROCESS
In cooperative MARL, we often formulate the problem as a multi-agent Markov decision process (MDP) (Boutilier, 1996). A multi-agent MDP can be defined by tuple S1, A, P, r, y, N). N is the number of agents, / = 2,, .N} is the set of agents, S is the set of states, and A = A₁ x x Aw the joint action space, where A, is the individual action space for each agent i. For the rigorousness of proof, we assume full observability such that at each state 8 E S, each agent i receives state s, chooses an action a; E A,, and all actions form a joint action a E A. The state transitions to the next state s' upon according to the transition function P(s'|s, a) S x A x S + [0, 1]. and all agents receive a shared reward r(s, a): : S x A + R. The objective is to learn a local policy TT (a s) for each agent such that they can cooperate to maximize the expected cumulative discounted return, EI )'rz). where 7 E [0, 1) is the discount factor. In CTDE, from a centralized perspective, a be viewed as a joint policy Titt (al s). For this joint policy, can define the joint state-action value function (Sr. a²) = Ees a 000 T're4al St, a.). Note that although we assume full observability for the rigorousness of proof, we use the trajectory of each
group of local policies
agent E T (Y x A.)* to replace state s as its policy input to settle the partial observability in practice, where Y is the observation space.
2.2 FOP
FOP (Zhang et al., 2021) is one of the state-of-the-art CTDE methods for cooperative MARL, which extends value decomposition learning stochastic policy. In FOP, the joint policy is decomposed into independent local policies based on Individual-
(IGO), which can be stated as:
N
Ty (a)ss
II
n. (agls))
(1)
1=1
2

---

Published as a conference paper at ICLR 2023
As all policies learned by maximum -etttmmpeeetrpyy RL (Haarnoja et al., 2018), i.e., (T(ass)) exp(2, (Q,(s, a.) - Vi(s))), IGO immediately implies a specific way of value decomposition:
N
(s a)
(Q((s. Vi(s)] Vj((s).
(2)
Unlike IGM, which used to learn deterministic local policies and naturally avoids the dependency of agents, IGO assumes agents independent of each other in both training and execution. Although
IGO advances FOP to learn stochastic policies, such an assumption can problematic even in some simple scenarios and prevent learning the optimal joint policy.
2.3 PROBLEMATIC IGO
(a) contralized control
(b) FOP
(c) dependency
Figure I: Sampled trajectories from the learned policy: (a) centralized control; (b) FOP, where IGO is assumed;
(c) considering dependency during training.
As stated in soft Q-learning (Haarnoja et al., 2018), goal of maximum-entropy RL is to learn optimal maximum-entropy policy that captures multiple modes of near-optimal behavior. Since FOP be seen the extension of maximum-entropp RL in multi-agent settings, is natural to assume that FOP can also learn a multi-modal joint policy in multi-agent settings. However, as shown the following example, such desired property of maximum-entropy RI. is not inherited in FOP due the IGO condition.
We extend the single-agent multi-goal environment used in soft Q-leaming (Haarnoja et al., 2018) to its multi-agent variant to illustrate the problem of IGO. In this environment, we want to control a 2D point mass reach one of four symmetrically placed goals, as illustrated in Figure The reward is defined as mixture of Gaussians, with means placed at the goal positions. Unlike the original environment, this 2D point mass is now jointly controlled by two agents, and can only move when these two agents select the same moving direction; otherwise, it will stay where it is. As shown Figure la, when centralized control is allowed, multi-agent training degenerates to single-agent training, and the desired multi-modal policy can be learned. However, shown in Figure 1b, FOP struggles to learn any meaningful joint policy for the multi-agent setting. One possible explanation is that, since IGO is assumed in FOP, the local policy of each agent is always independent of each other during training, and the expressiveness of joint policy dramatically reduced. Therefore, when two agents have to coordinate make decisions, they may fail reach agreement and eventually behave in a less meaningful way due to the limited expressiveness solve this problem, propose to consider dependency among agents in MARL algorithms enrich the expressiveness of joint policy. As shown in Figure 1c, the learned joint policy can once again capture multiple modes of near-optimal behavior when the dependency is considered. Details of this algorithm will be discussed in the next section.
joint policy. To
3 METHOD
To overcome the aforementioned problem of IGO, we propose multi-agent conditional policy factorization (MACPF). In MACPF, we introduce dependency among agents during centralized training to ensure the optimality of the joint policy without the need for IGO. This joint policy consists of dependent local policies, which take the actions other agents as input, and we use this joint policy as the behavior policy to interact with the environment during training. In order fulfill
3

---

Published as a conference paper at ICLR 2023
decentralized execution, independent local policies obtained from these dependent local policies such that the joint policy resulting from these independent local policies is equivalent to the behavior policy in terms of expected return.
3.1 CONDITIONAL FACTORIZED SOFT POLICY ITERATION
Like FOP, we also use maximum -ettiiuuueettryyyyyyoo RL (Ziebart, 2010) to bridge policy and state-action value function for each agent. Additionally, will also be used introduce dependency among agents. For each local policy, we take the actions of other agents as its input and define it as follows:
T. (as/ aci) = expl 1 (Qi(s, aci a;) - Vi(8, a<i)))
(3)
04
((ss = ai Σ exp(
1 Qu(,
(4)
where a'i represents the joint action of all agents whose indices are smaller than agent i. We then can get the relationship between the joint policy and local policies based on the chain rule factorization of joint probability:
Tje (al 8)
II (ajlss,,a
(5)
The full expressiveness of the joint policy be guaranteed by (5) as it is no longer restricted by the IGO condition. From (5), together with (aa(a]s) s) = exp() (Q, a) (s))), we have the Qj. factorization as:
N
Qnts a) = Σ
a (((s, - Vs ac:)l Vj.(s).
(6)
Note that maximum- centimmm-entrpyy RL, we can easily compute V by Q. From (6), we introduce conditional factorized soft policy iteration and prove its convergence to the optimal joint policy in the following theorem.
Theorem 1 (Conditional Factorized Soft Policy Iteration). For any joint policy Tyt we repeatedly apply joint soft policy evaluation and individual conditional soft policy improvement from n, II.
Then the joint policy Tjy(a} s) = II mr(ay s, acs) converges to Tiy. such that Q (s. a) 2
2ftt (s, a) for all Tjt, assuming [A| < cc.
Proof. See Appendix A.
3.2
Independent JOINT POLICY
Using the conditional factorized soft policy iteration, we are able to get the optimal joint policy. However, such joint policy requires dependent local policies, which are incapable of decentralized execution. To fulfill decentralized execution, we have to obtain independent local policies.
Q2
a2
4
01
01
A
0.5
0
A
0.5
0
0.5
0.5
dependent joint policy Tjj
(b) independent joint policy mf. (c) dependency correction aft
Figure 2: A dependent joint policy and its independent counterpart
dep Consider the joint policy shown in Figure 2a. This joint policy, called dependent joint policy mj. involves dependency among agents and thus cannot be factorized into two independent local policies. However, one may notice that this policy can be decomposed as the combination of an independent joint policy n/j that involves dependency among agents, shown in Figure 2b, and dependency
4

---

Published as a conference paper at ICLR 2023
gdep_ policy correction Djt shown in Figure 2c. More importantly, since the Boltzmann distribution of joint Q-values as the joint policy, the equivalence of probabilities of two joint actions also indicates that their joint Q-values are the same,
dep (A, A) = "it dep [B, B) = Q,, = (B,
"it
Therefore, in Table the expected return of the independent joint policy m/je will be the same the dep dependent joint policy "jt
dep E dop [qr1] = Jjt (A, A) (A, A) + "jt (B, B) * (B
dep
(8)
Jtt
Tj ind (A, Qj E Begndd Qjul-
(9)
Formally, we have the following theorem.
dep that involves dependency among agents, there Theorem 2. For any dependent joint policy "t exists an independent joint policy Tip that does not involve dependency among agents, such that V (s) = (s) any state E S. Rjt
Proof. See Appendix B.
Note that the independent counterpart of the optimal dependent joint policy may not be directly learned by FOP, as shown in Figure 1. Therefore, we need to explicitly learn the optimal dependent joint policy to obtain its independent counterpart.
3.3 MACPF FRAMEWORK
With Theorem I and 2, we are ready to present the learning framework of MACPI, as illustrated in Figure 3, for simultaneously learning the dependent joint policy and its independent counterpart.
In MACPF, each agent i has an independent local policy m(!"((s) s; 0;) parameterized by 0; and dependency policy correction (ale((a.) 8, acii Φi) parameterized by di which together constitute
dependent local policy `
dep dep (agl s, a So, we have:
dep T
(a:1 ac)) .::d (a:l s;0,) "/. acii
(10)
dep (s a) II m (apl s,i))
(11)
jt
N
Kit (s, a) = II क. (a]ss;0)))
(12)
Similarly, each agent also has an independent local critic Qidd (a.]s; (h)) parameterized by 1i and a dependency critic correction ddep (a:) aes wi) parameterized by wi, which together constitute de- pendent local critic Qdee((a)) (ayl s, aci). Given all Qind and edlep, we use mixer network, Mixer ())
parameterized by O to get Q and Qjad as follows.
(atP((a s, a.)) = Q!!d (agl s; th) + dep (ap(aa (a Qee a) Mixer((Q, s a<:)) 9) Qj (s. = Mixer (nqind (a.l s; th ) s; θ).
(13)
(14)
(15)
QoeP Qidd and Mixer are learned by minimizing the TD error,
(o (odee a) (r + (s) a') a log qjt dep dep((a) (a'l ss))
edep (l: θ) Ep
(16)
clnd( θ) ED
(Q)ed (s, a) (r+ 7 7Qjnd (s', a') a log oe (a' {))
(17)
'The logit न.. (a.) s; 0.) first added with 65 (as (as/sx uzsi sbe) to get the logit of क. dep (a. ues). then
softmax used this combined logit get zdee (a, azx)-
5

---

Published as a conference paper at ICLR 2023
Rdinal
Mixer Network
(1.0))
H
Soltmax
Bolonas
4) (u
Critic 1
Crita
(nuor)
MLP
MLP
MLP
MLP
Agent
Agentin
MLP
(m)
(1)%%)
(R)
(mx)
(a.a)
Q:
Qn
Environment
Independent CitcPPalley
Dependent CrticPPllcy
Figure 3: Learning framework of MACPF, where each agent i has four modulcs: an independent local policy r!nd (;; dependency policy correction 1eep (:; (s.) independent local critic Qi (:s dss). and dependency critic correction eeop(( (r,wa).
dep Q is the target network, and a' is sampled from where D is the replay buffer collected by Tit
dep the current "jt and "jt ind respectively. To ensure the independent joint policy Tit has the same performance as "jt the same batch sampled from D is used to compute both _dep and Lind, is worth noting that the gradient of _dep only updates |c; J==1, [e while the gradient of gind only updates dep and ni!m are updated by minimizing KL--ivergence as follows, [Q]ndiN k= Then, TT
dep
gdep(db)) = E. oP a aas log =, dep (as 8, aci)) Q
dee (ad 8, aci)l
(18)
find (0:) = Epa (ag log (a.l s; 0.) Qi (a:l s; vh:)].
(19)
Similarly, the gradient of Jdep only updates t and the gradient of Find only updates r.!dd. For computing Jdop, aci is sampled from their current policies ddep.
The purpose of learning arjed is to enable decentralized execution while achieving the same perfor- mance Tjt dep Therefore, certain level of coupling has to be assured between Tje and Kjt dep First, motivated by Figure 2, we constitute the dependent policy as a combination of an independent policy and a dependency policy correction, similarly for the local critic. Second, as aforementioned, the dep is the behavior policy and the learning of ind is offline. Third, we use the same Mixer to compute Oft and Qjad. The performance "jt comparison between Tjt
dep which implies "jt replay buffer 'D is collected by Tit
dep and njj will be studied by experiments.
RELATED WORK
Multi-agent policy gradient. In multi-agent policy gradient, a centralized value function is usually learned to evaluate current joint policy and guide the update of each local policy. Most multi-agent policy gradient methods can be considered as an extension of policy gradient from RL. to MARL. For example, MAPPDG (Lowe al., 2017) extends DDPG (Lillicrap al., 2015), PS-TRPO(Guptt et al., 2017) and MATRPO (Kuba et al., 2021) extend TRPO (Schulman et al., 2015), and MAPPO (Yu al., 2021) extends PPO (Schulman al., 2017). Some methods additionally address multi-agent credit assignment by policy gradient, e.g., counterfactual policy gradient (Foerster et al., 2018) or difference rewards policy gradient (Castellini al., 2021; Li al., 2022).
Value decomposition. Instead of providing gradients for local policies, in value decomposition, the centralized value function, usually a joint Q-function, directly decomposed into local utility functions. Many methods have been proposed different interpretations of Individual-Gioo -Goball- Maximum (IGM), which indicates the consistency between optimal local actions and optimal joint action. VDN (Sunehag et al., 2018) 8) and QMIX (Rashid et al., 2018 8) give sufficient conditions for IGM by additivity and monotonicity, respectively. QTRAN (Son et al., 2019) transforms IGM into optimization constraints, while QPLEX (Wang et al., 2020a) takes advantage of duplex dueling architecture to guarantee IGM. Recent studies (Su et al., 2021; Wang et al., 2020b; Zhang et al., 2021: Su & Lu, 2022) combine value decomposition with policy gradient to learn stochastic policies, which

---

Published as a conference paper at ICLR 2023
Matrix
Q2
A
B
C
D
A
B
C
D
20
20
A
0.5
B
12
20
B
C
12
-0
10P
C
D
12
12
12
0.5
6013
(a) payoff matrix
(b) learning curves
(c) Tji
dep of MACPF
Figure 4: A matrix game that has two optimal joint actions: (a) payoff matrix; (b) learning curves different
methods; (c) the learned dependent joint policy of MACPF.
more desirable in partially observable environments. However, most research in this category does not guarantee optimality, while our method enables agents to learn the optimal joint policy.
Coordination graph. In coordination graph (Guestrin et al., 2002) methods (Böhmer al., 2020; Wang et al., 2021b; Yang et al., 2022), the interactions between agents are considered as part of value decomposition. Specifically, the joint Q-function is decomposed into the combination of utility functions and payoff functions. The introduction of payoff functions increases the expressiveness of the joint Q-function and considers at least pair-wise dependency among agents, which is similar to our algorithm, where the complete dependency is considered. However, to get the joint action with the maximum Q- v-lleee, communication between agents is required in execution in coordination graph methods, while our method still fulfills fully decentralized execution.
Coordinated exploration. One of the benefits of considering dependency is coordinated exploration. From this perspective, our method might be seen as relative of coordinated exploration methods (Mahajan et al., 2019; Iqbal & Sha, 2019; Zheng al., 2021). In MAVEN (Mahajan al., 2019), shared latent variable is used to promote committed, temporally extended exploration. In EMC (Zheng et al., 2021), the intrinsic reward based on the prediction error of individual Q-values is used to induce coordinated exploration. It is worth noting that our method does not conftict with coordinated exploration methods and can be used simultaneously as our method is a base cooperative MARL algorithm. However, such combination is beyond the scope of this paper.
5 EXPERIMENTS
In this section, evaluate MACPF in three different scenarios. One is simple yet challenging matrix game, which we use to verify whether MACPF can indeed converge to the optimal joint policy. Then, evaluate MACPF two popular cooperative MARL scenarios: StarCraft Multi-Agent Challenge (SMAC) (Samvelyan et al., 2019) and MPE (Lowe et al., 2017), comparing it against QMIX (Rashid et al., 2018), QPLEX (Wang al., 2020a), FOP (Zhang al., 2021), and MAPPO (Yu et al., 2021). More details about experiments and hyperparameters are included in Appendix C. All results are presented using the mean and standard deviation of five runs with different random seeds. In SMAC experiments, for visual clarity, we plot the curves with the moving average of window size of five and half standard deviation.
5.1 MATRIX GAME
In this matrix game, we have two agents. Each can pick one of the four actions and get reward based on the payoff matrix depicted in Figure 4a. Unlike the non-monotonic matrix game QTRAN (Son et al., 2019), where there is only one optimal joint action, we have two optimal joint actions in this game, making this scenario much more challenging for many cooperative MARI. algorithms.
As shown in Figure 4b, general value decomposition methods, QMIX, QPLEX, and FOP, fail to learn the optimal coordinated strategy in most cases. The same negative result can also be observed for MAPPO. For general MARL algorithms, since agents are fully independent of each other when making decisions, they may fail to converge to the optimal joint action, which eventually leads to a suboptimal joint policy. As shown in Figure 4b, QMIX and MAPPO fail to converge to the optimal policy but find a suboptimal policy in all the seeds, while QPLEX, QTRAN, and FOP find the optima by chance (i.e., 60% for QPLEX, 20% for QTRAN, and 40% for FOP). This is because, in QMIX, the
7

---

Published as a conference paper at ICLR 2023
1.0
vs
1.0
9m myopic
1.0
10m vs 11m
MACFF
0.8
QPLEX
FOP
MAGR
MAGPE
QMIX
0.4
QMIX
QPLEX
QPLEX
0.2
FOP
0.2
0.2
FOP
MAPPO
MAPPO
0.0
0.4
1.2
2.0
0.0
0.4
0.8
1.6
2.0
0.00
0.4
166
2.0
1.0
10m vs. 11m myople
1.0
MMM2
1.0
corridor
MACPF
MACFF
MACPF
0.8
QMIX
0.8
0.8
QMIX
QPLEX
QPLEX
QPLEX
0.6
FOP
0.6
0.6
FOP
MAPPO
MAPPO
MAPPO
0.0
0.4
1.2
0.0
0.8
0.00
Figure 5: Learning curves of all the methods in six maps of SMAC, where the unit of x-axis 1M timesteps and y-axis represents the win rate each map.
mixer network is purely a function of state and the input utility functions that are fully independent of each other. Thus it considers no dependency at all and cannot solve this game where dependency has be considered. For QPLEX and FOP, since the joint action considered as the input of their mixer network, the dependency among agents may be implicitly considered, which leads to the case where they can find the optima by chance. However, since the dependency is not considered explicitly, there is also a possibility that the mixer network misinterppets the dependency, which makes QPLEX and FOP sometimes find even worse policies than QMIX (20% for QPLEX and 40% for FOP). For QTRAN, it always finds at least the suboptimal policy in all the seeds. However, its optimality largely relies on the learning of its Vj,, which is very unstable, so it also only finds the optima by chance.
For the dependent joint policy "jt
dop of MACPF, the local policy of the second agent depends on the
action of the first agent. As a result, we can see from Figure 4b that dep (denoted as MACPF DEP) *jt
always converges the highest return. We also notice that in Figure 4c, Tjj indeed captures two optimal joint actions. Unlike QMIX, QPLEX, and FOP, the mixer network in MACPF is function of state and the input utility functions Q,a0P (a,l s, a<s)) that are properly dependent on each other, so the dependency among agents is explicitly considered. More importantly, the learned independent joint policy "it of MACPF, denoted as MACPF in Figure 4b, always converges to the optimal joint policy. Note that in the rest of this section, the performance of MACPF is achieved by the learned ind unless stated otherwise. jt
5.2 SMAC
Further, we evaluate MACPF on SMAC. Maps used in our experiment include two hard maps 11), 10m),__11m),
(8m_vs fom_vs_9m, 10m_vs_ challenging customized maps (8m_vs__ 2s_9m_mm 9mmmyopic, 10m_ vs_ 11mmm_mm (mmmyopic),, where the sight range of each agent is reduced from 9 to 6, and the information of allies is removed from the observation of agents. These changes are adopted to increase the difficulty of coordination in the original maps. Results are shown in Figure 5. In general. MACPF outperforms the baselines in all six maps. In hard maps. MACPF outperforms the baselines mostly in convergence speed, while in super-hard maps, MACPF outperforms other algorithms in either convergence speed or performance. Especially in corridor, when other value decomposition algorithms fail learn any meaningful joint policies, MACPF obtains winning rate of almost 70%. In the two more challenging maps, the margin between MACPF and the baselines becomes much larger than that in the original maps. These results show that MACPF better handle complex cooperative tasks and learn coordinated strategies by introducing dependency among agents even when the task requires stronger coordination.
and two super-hard maps (MMM2, corridor). We also consider two
We compare MACFP with the baselines in 18 maps totally. Their final performance is summarized in Appendix D. The win rate of MACFP is higher than or equivalent to the best baseline in 16 out of 18 maps, while QMIX, QPLEX, MAPPO, and FOP are respectively 7/18, 8/18, 9/18, and 5/18.
8

---

Published as a conference paper at ICLR 2023
1.2
8m, 9m
1.0
MMN2
1.0
corridor
0.5
0.8
98
120
0.6
0.4
3.-
02
2..0
2.2
0.0
0.8
000
0.4
1.6
0.0
Figure 6: Performance of dop and ind during training in four maps of SMAC, where the unit of x- x-axis is IM timesteps and y-axis represents the win rate of each map.
MACFF
MACHF
0.8
MACFF CONTROL
CONTRRL
066
5.6-
0.6
0.6
0.4-
5.4
0.4
0.4
0.2
VACFF
0,2
NACF!
0.2
MACIF CONTROL
MACF CONTROL
0.0
0.4
0.6
1.
200
0.0
0.4
0.8
1.2
2.0
8,2
0.4
0.8
12
26
2.2
0.0
0.8
1.2
2.0
Figure 7: Ablation study in four maps of SMAC, where the unit of x-axis is 1M timesteps and y-axis represents the win rate of each map.
Dependent and Independent Joint Policy. As discussed in Section 3.2, the learned independent joint policy of MACPF should not only enable decentralized execution but also match the performance of dependent joint policy, as verified in the matrix game. What about complex environments like SMAC? dep As shown in Figure 6, we track the evaluation result of both Ttt and Tjt during training. As can see, their performance stays at the same level throughout training.
Ablation Study. Without learning a dependent joint policy to interact with the environment, our algorithm degenerates to FOP. However, since our factorization of Q₁ is induced from the chain rule factorization of joint probability (5), we use a mixer network different from FOP (the reason is discussed and verified in Appendix E). Here we present an ablation study to further show that the improvement of MACPF indeed induced by introducing the dependency among agents. In Figure 7, MACPF CONTROL represents algorithm where all other perspectives are the same as MACPF, except no dependent joint policy is learned. As shown in Figure 7, MACPF outperforms MACPF CONTROL in all four maps, demonstrating that the performance improvement is indeed achieved by introducing the dependency among agents.
5.3
MPE
We further evaluate MACPF on three MPE tasks, including simple spread, formation control, and line control (Agarwal et al., 2020). As shown in Table 1, MACPF outperforms the baselines in all three tasks. A large margin can be observed in simple spread, while only a minor difference can be observed in the other two. This result may indicate that these MPE tasks are not challenging enough for strong MARL algorithms.
Table I: Average rewards per episode on three MPE tasks.
A Algorithms
MАCPF
QMIX
QPLEX
FOP
MАPPO
Tasks
Simple Spread
118.2441..44
-145.93=21.09
122.50=2.58
125.11955.42
166675523.44
Formation Control
-15.79
-16.1140.00
-16110+0.28
-15.84 0.19
.2..71+1.69
Line Control
-13.60
-20.12:40.1
-20.17:1..26
-19.78-0277
-24.47:2.54
6 CONCLUSION
We have proposed MACPF, where dependency among agents is introduced to enable more centralized training. By conditional factorized soft policy iteration, we show that dependent local policies provably converge to the optimum. To fulfill decentralized execution, represent dependent local policies as a combination of independent local policies and dependency policy corrections, such that independent local policies achieve the same level of expected return dependent ones. Empirically, we show that MACPF can obtain the optimal joint policy in a simple yet challenging matrix game while baselines fail and MACPF also outperforms the baselines in SMAC and MPE.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
This work was supported in part by NSFC (under grant 62250068) and Tencent.
REFERENCES
Akshat Agarwal, Sumit Kumar, Katia Sycara, and Michael Lewis. Learning transferable cooperative behavior in multi-agent teams. In International Conference Autonomous Agents and MultiAgent Systems, 2020.
Dimitri Bertsekas. Multiagent rollout algorithms and reinforcement learning, arXiv preprint arXiv:1910.001200 2019.
Wendelin Böhmer, Vitaly Kurin, and Shimon Whiteson. Deep coordination graphs. In International Conference Machine Learning, 2020.
Craig Boutilier. Planning, learning and coordination in multiagent decision processes. In TARK, volume 96, pp. 195-210, 1996.
Jacopo Castellini, Sam Devlin, Frans A Olichock, and Rahul Savani. Difference rewards policy gradients. In International Conference on Autonomous Agents and MultiAgent Systems, 2021.
Jakob Foerster, Gregory Farqubar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson. Counterfactual multi-agent policy gradients. In AAAI conference on artificial intelligence, 2018.
Wei Fu, Chao Yu, Zelai Xu, Jiaqi Yang. and Yi Wu. Revisiting some common practices in cooperative multi-agent reinforcement learning. In International Conference Machine Learning, pp. 6863- 6877. PMLR, 2022.
Carlos Guestrin, Michail Lagoudakis, and Ronald Parr. Coordinated reinforcement learning. In International Conference on Machine Learning, 2002.
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, 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 International conference machine learning, 2018
Shariq Iqbal and Fei Sha. Coordinated exploration via intrinsic rewards for multi multi-agent reinforcement learning. arXiv preprint 100. 2019.
Landon Kraemer and Bikramjit Banerjee. Multi-agent reinforcement learning rehearsal for decentralized planning. Neurocomputingg 190:82-94, 2016.
Jakub Grudzien Kuba, Ruiqing Chen, Munning Wen, Ying Wen, Fanglei Sun, Jun Wang, and Yaodong Yang. Trust region policy optimisation in multi-agent reinforcement learning. arXiv preprint 11X1:12009.11251, 2021.
Yueheng Li, Guangming Xie, and Zongqing Lu. Difference advantage estimation for multi-agent policy gradients. In International Conference on Machine Learning, 2022.
Timothy P Lillicrap, Jonathan J Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. arXiv 2015.
preprint X009:15000000
Ryan Lowe, Yi I Wu, Aviv Tamar, Jean Harb, OpenAl Pieter Abbeel, and Igor Mordatch. Multi-agent actor-critic for mixed pooerative-competee environments. Advances in neural information processing systems, 2017.
Anuj Mahajan, Tabish Rashid, Mikayel Samvelyan, and Shimon Whiteson. Maven: Multi-agent variational exploration. Advances in Neural Information Processing Systems, 2019.
10

---

Published as a conference paper at ICLR 2023
James R Munkres. Topology, volume 2. Prentice Hall Upper Saddle River, 2000.
Tabish Rashid, Mikayel Samvelyan, Christian Schroeder, Gregory Farquhar, Jakob Foerster, and Shi- mon Whiteson. Qmix: Monotonic value function factorisation for deep multi-agent reinforcement learning. International Conference on Machine Learning. 2018.
Tabish Rashid, Gregory Farquhar, Bei Peng, and Shimon Whiteson. Weighted qmix: Expanding monotonic value function factorisation for deep multi-agent reinforcement learning. Advances in neural information processing systems, 2020.
Mikayel Samvelyan, Tabish Rashid, Christian Schroeder de Witt, Gregory Farquhar, Nantas Nardelli, Tim G. J. Rudner, Chia-Man Hung, Philiph H. S. Torr, Jakob Foerster, and Shimon Whiteson. The StarCraft Multi-Agent Challenge. arXiv preprint arXiv:2007. 12322, 2019.
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference on machine learning, 2015.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347 2017.
David A Schum. The Evidential Foundations of Probabilistic Reasoning. Northwestern University Press, 2001.
Kyunghwan Son, Daewoo Kim, Wan Ju Kang, David Earl Hostallero, and Yung Yi. Qtran: Learning factorize with transformation for cooperative multi-agent reinforcement learning. In International Conference on Machine Learning, 2019.
Jianyu Su, Stephen Adams, and Peter A Beling. Value-decomposition multi-agent actor-critics. In AAAI Conference on Artificial Intelligence, 2021.
Kefan Su and Zongqing Lu. Divergence-regullaizee multi-agent actor-critic. International Conference Machine Learning, 2022.
Peter Sunehag, Guy Lever, Audrunas Gruslys, Wojeiech Marian Czarnecki, Vinicius Zambaldi, Max Jaderberg, Mare Lanctot, Nicolas Sonnerat, Joel Z Leibo, Karl Tuyls, et al. Value-decooposittoon networks for cooperative multi-agent learning based on team reward. In International Conference Autonomous Agents and MultiAgent Systems, 2018.
Richard S Sutton and Andrew G Barto. Reinforcement Learning: Introduction. MIT press, 2018.
Jianhao Wang, Zhizhou Ren, Terry Liu, Yang Yu, and Chongjic Zhang. Qplex: Duplex dueling multi-agent geearnnng. In International Conference on Learning Representations, 2020a.
Tong Wang. Jiahua Cao, and Azhar Hussain. Adaptive traffic signal control for large-scale scenario with cooperative group-based multi-agent reinforcement learning. Transportation research part C: 2021a.
emerging technologies,
Tonghan Wang, Liang Zeng, Weijun Dong, Qianlan Yang, Yang Yu, and Chongjic Zhang. Context- aware sparse deep coordination graphs. arXiv preprint wrXiv:2106.02886, 2021b.
Yihan Wang, Beining Han, Tonghan Wang, Heng Dong, and Chongjie Zhang. Off-policy multi-agent decomposed policy gradients. arXiv preprint arXiv:2007. 12322, 2020b.
Qianlan Yang, Weijun Dong, Zhizhou Ren, Jianhao Wang. Tonghan Wang, and Chongjie Zhang Self-organized polynomial coordination graphs. In International Conference on Machine Learning, 2022.
Chao Yu, Akash Velu, Eugene Vinitsky, Yu Wang, Alexandre Bayen, and Yi Wu. The surprising effectiveness of ppo in cooperative, multi-agent games. arXiv preprint arXiv:2103.0199 2021.
Tianhao Zhang, Yueheng Li, Chen Wang, Guangming Xie, and Zongqing Lu. Fop: Factorizing optimal joint policy of maximum-entron multi-agent reinforcement learning. In International Conference Machine Learning, 2021.
11

---

Published as a conference paper at ICLR 2023
Lulu Zheng, Jiarui Chen, Jianhao Wang, Jiamin He, Yujing Hu, Yingfeng Chen, Changjie Fan, Yang Gao, and Chongjie Zhang. Episodic multi-agent reinforcement learning with curiosity-driven exploration. Advances in Neural Information Processing Systems, 2021.
Tong Zhou, Dunbing Tang, Haihua Zhu, and Zequn Zhang. Multi-agent reinforcement learning for online scheduling in smart factories. Robolics and Computer-Inlegrated Manufacturing, 72: 102202, 2021.
Brian D Ziebart. Modeling Purposeful Adaptive Behavior with the Principle of Maximum Causal Entropy. Carnegie Mellon University, 2010.
12

---

Published as a conference paper at ICLR 2023
A PROOF OF THEOREM
In this subsection, we incorporate dependency among agents into the standard soft policy iteration and prove that this modified soft policy iteration converges to the optimal joint policy.
For soft policy evaluation, we will repeatedly apply soft Bellman operator my to Qj Th until conver- gence, where:
Tia Qje(St as) = r + Baces (sc(s++1) Vi1 (st) = E. Qqu a,) - a log je (ay) st)].
(20)
(21)
In this way, as shown in Lemma A.I, we can get Q7²²" for any joint policy Tjt- Lemma A.1 (Joint Soft Policy Evaluation). Consider the modified soft Bellman backup operator
Tay and a mapping Oft X + R with |A| < oo, and define Qjt sequence Of will converge to the joint soft Q-function of Tn as k + co.
Ta Of. Then, the
Proof. First, define the entropy augmented reward as:
Ty (St, at): == r(se, at) + Best [H( 8t41))]-
Then, rewrite the update rule as:
(s, an) + Tay (St, az) + Ba. 1Q (8241, 1r+1)]-
Last, apply the standard convergence results for policy evaluation (Sutton & Barto, 2018).
After we get Oj we will make one-step improvement for the joint policy. First, restrict the local policy of each agent i to some set of policies II, and update the local policy according the following optimization problem:
new arg min EIT;
E
DKL. (T(((s1 (,ci)) exp (- (0, olld
(s, (s, - V.Ti (s, ace))))
new
as
Japia (nt
(22)
Based on individual conditional soft policy improvement, we will show that the newly projected joint soft policy has a higher state-action value than the old joint soft policy with respect to the maximum-entrope RI. objective.
Lemma A.2 (Individual Conditional Soft Policy Improvement). Let m. E II, and m be
the optimizer of the minimization problem in (22). Then, we have Qj new for all (St, ar) E x A with |A| < co, where Jj
(st, a:) 2 Oj (st, az) old (as 8, acs) and Tjt new old (al s) = II m,
(al 8)
I1 m.e (as a.))).
Proof. Let Q and V.*i" be the corresponding soft state-action value and soft state value of indi- vidual policy mold First, considering that Jaala aas mcs (ITpo (a: (a:)s,acs)) S Japta ees Then, we have:
(T (a, az))).
Q²" olld (8, + V. (s,
E Eagwapew www.meew...ceeeeee meow (as log n. new (ail a,s)))
(23)
E agld aec (as log old (ail 8,02))
Q,1 nith (s,aci;)))) + V.r (s,
Since V. old
depends only on and azi, where:
E Eacrarir [V=" (s, aess) = E Bagaora anoopli [Q old (s, azi ai) - a; log +. (ald(as (ag1s, (24)
By deducing (24) from both sides of (23), we have:
Eapoaye aeceongg 12, sold
(s, acis a.) a; log क.. new (a.(s, Eaceoryny [V="' (s,azi))
(25)
13

---

Published as a conference paper at ICLR 2023
And since
old 1t jt
(8, - -Vje" "t (6)
Jt
new
exp
Q
new exp
1
Q7
(s, 15, az) Vi (s, (s,a))))
R1
N
jt
new
(als)
=
new 7i
(a:1s,
we can have:
N
old
- a:) -V," old (s,) + +V Rl
(s, a)
Q (s,
(s).
03
Then we have
old
E Eawretow new
10
(s, a) - a log jjt
new
(al s)]
Q
mi (s, ai) V." (s, Vij (s) log new (al
oold
N
E Bawa new acrra
new
a
10,
(s, V,: (s, - a; log म. (a. s, azil] + Vi"" (s)
a2
i=1
(s),
(26)
where the inequality from plugging in (25).
Last, considering the soft bellman equation, the following holds:
0j4² a1) = rt + Ee [V,
(s)
S rt + Bessp Baan 10 old
(st+1, a141) log new (art1l 8441)]]
SO The new
(st,
oold "
where we have repeatedly expanded Qjt" bound (26).
on the RHS by applying the soft Bellman equation and the
Conditional factorized soft policy iteration alternates between joint soft policy evaluation and individ- ual conditional soft policy improvement, and provably converges to the global optimum, as shown in Theorem 1.
Theorem 1 (Conditional Factorized Soft Policy Iteration). For any joint policy Tjt we repeatedly apply joint soft policy evaluation and individual conditional soft policy improvement from n, II, Then the joint policy TT((a)s s) = II (a s, azs) will eventually converge to The such that
of (s. a) > 27th (s, a) for all Tjt. assuming |A|
Proof. First, by Lemma A.2, the sequence (mf) monotonically improves with O
Q tf Since
both the reward and entropy are bounded, then O is bounded. Thus, this sequence must converge to some Tht. Then, at convergence, we have the following inequality:
Jaj. (mf (()))) S Jmj (TTe(+)s)), V Tjt + nsC-
Using the same iterative argument as in the proof of Lemma A.2, we get Q (s, a) 2 2 (s, a) for all (s, a) E A. That is, the soft value of any other policy Tj. lower than that of the converged policy Tj. Therefore, nद.. is optimal in II, ... x NI
14

---

Published as a conference paper at ICLR 2023
B PROOF OF THEOREM 2
Theorem 2. For any dependent joint policy "jt
dep that involves dependency among agents, there exists independent joint policy Th that does not involve dependency among agents, such that V Vagen Vijna (8) for any state E S.
dep that involves dependency among agents, let max Q Proof. For a dependent joint policy "jt A and mina Qashe = B, we have A S independent joint policy Tjt" ajpd
V dep (s) < B. Then, we can construct the following
Rjs
N II 1a,
ind jj
II 1=1
arg max Q [i]]
1=1
For such independent joint policy mijed have Ea T/e Q dep construct another independent joint policy, such that Σa Tit Quder "gz
A. Similarly, can also
B. Based on the generalized
intermediate value theorem (Munkres, 2000), We can have that for any dependent joint policy jj there exist an independent joint policy Tft such that:
dep
dep ge
Σ
jtt
dep
Q
dep "jt
Σ
Ind jt
Q dep
Ea, Barnjj
[Q dep].
Thus, we can have:
V dep (St)
E aardd 12 Qaaar as))
JJt
E an 1 (r a:) (V VV (sc-1)]
Ba (ot)) 1l an P (st. a.) + 2Q (8t, (8t, ar)
E E Ba si P/r(ss az) + + ar+1) +...] jad (st),
which concludes the proof.
C EXPERIMENT SETTINGS AND IMPLEMENTATION DETAILS
C.I MATRIX GAME
In the matrix game, we use a learning rate of 3 x 10 4 for all algorithms. For FOP and MACPF, a decays from 1 to 0.5, with decay rate of 0.999 per episode. For QMIX and QPLEX, decays from to 0.01, with a decay rate 0.999 per episode. The batch size used in the experiment is 64 for FOP, MACPF, QMIX, and QPLEX, and 32 for MAPPO it is on-policy learning algorithm. All crities and actors used the experiments consist of one hidden layer of 64 units with ReLU non-linearity. For the Mixer network, QMIX and MACPF both use hypernetwork, except ELU non-linearity is used for QMIX and no non-linearity is used for MACPE FOP and QPLEX both use attention network for their mixer network. The environment and model are implemented in Python. All models are built on PyTorch and are trained on machine with Nvidia GPU (RTX 1060) and 8 AMD CPU Cores.
C.2 SMAC
In StarCraft II, for MACPF, we use a learning rate of 5 10 The critic network and policy network of MACPF consist of three layers, fully-connected layer with 64 units activated by ReLU, followed by a 64 bit GRU, and followed by another fully-connected layer. The policy correction network and critic correction network consist of two layers, one fully-connected layer with 64 units activated by
15

---

Published as a conference paper at ICLR 2023
ELU, followed by another fully-connected layer. The target networks updated after every 200 training episodes. The temperature parameters a and a; are annealed from 0.5 to 0,05 over 200k time steps for all easy and hard maps and fixed as 0.001 for all super-hard maps. For QMIX, QPLEX, FOP, and MAPPO, we use their default setting of each map. The environment and model are implemented in Python. All models are built on Py TyToch and are trained and 224 Intel CPU Cores. For 3s5z_M Vs 3s6z, all models are built on PyTorch and are trained on machine with 1 Nvidia GPU (RTX 2080 TI) and 16 Intel CPU Cores. Our implementation of MACPF is based on PyMARL (Samvelyan et al., 2019) with MIT license. It worth noting that, although we assume full observability for the rigorousness proof, the trajectory of each agent used to replace state for each agent as input to settle the partial observability in all SMAC experiments.
machine with 4 Nvidia GPUs (A (A100)
C.3 MPE
In MPE (MIT license), use the default settings of MAPPO. For QMIX, QPLEX, FOP, and MACPF, we use a learning rate of 5 x 10-4 For FOP and MACPF, a decays from 0.5 to 0.05 over 50k time steps. For QMIX and QPLEX, decays from 1 to 0.05 over 50k time steps. The batch size used in the experiment is 64. All critics and actors used in the experiments consist of hidden layers of 64 units with ReLU non-linearity and 64 bit GRU. For the Mixer network, QMIX and MACPF both hypernetwork, except ELU non- non-linearity is used for QMIX and no non coneaiiyyy is used for MACPE. FOP and QPLEX both use attention network for their mixer network. The environment and model are implemented in Python. All models are built on PyTorch and are trained on machine with Nvidia GPU (RTX 2080 TT) and 16 Intel CPU Cores. We also use the trajectory of each agent as input to settle the partial observability in all MPE experiments.
D MORE EXPERIMENTS ON SMAC
D.1 MORE MAPS
We additionally evaluate MACPF on more SMAC maps. The maps used here include six easy maps (8m, MMM, 3$_vv_33,, 3$_vs___ 47, so_ many many_baneling, 1c3s5z), three hard maps (3s5z, 2c_vs__f_____________________2 sa______g____ 3s_v8_57 and three super-hard maps (3s52_vs_3sd) 27m_m2mm_______ 77m0mm 6h_vs_8z). Results are shown in Figure 8. In general, MACPF matches or slightly outperforms the best performance of the baselines on all twelve maps.
D.2 SUMMARY OF SMAC FINAL PERFORMANCE
In this section, we provide the summary of SMAC experiments in terms of final performance. All results are achieved by 2M training timesteps. As shown in Table 2, MACPF outperforms or least matches the best performance of the baselines on all twelve maps.
E MIXER SELECTION
As mentioned in Section 5.2, we use a hypernetwork without non-linearity as our mixer network, which differs from QMIX, QPLEX, and FOP. In QPLEX and FOP, weighted summation is used to reflect the relationship between Qj: and Q. where the weight is function of both state and agent actions, such that the dependency among agents implicitly considered. However, this implicit dependency may contradict our explicit dependency model deee and decrease the performance of both dep and Qind.
Another choice is to use a hypernetwork with non-linearity to reflect the relationship between Qjs and Qi which is used in QMIX. However, due the existence of the non-linearity unit, two joint actions with the same 2j value may not be properly decomposed into two sets of Qi with the same sum. Thus, their joint probability may not be the same, and the dependency among agents is distorted.
Therefore, the only option left for MACPF to use hypernetwork without non- non-lincarity, which is equivalent to weighted summation where the weight is just function of state.
16

---

Published as a conference paper at ICLR 2023
1.0
1.0
1.0
0.8
0.0
0.8
MACPF
MACPF
MACK
QMIX
QMIX
QMX
QPLEX
QPLEX
QPLEX
MAPPO
MAPPO
MAPPO
0.0
0.4
0.8
1.6
2.0
0.0
0.4
0.8
1.2
1.6
2.0
0.00
0.4
0.8
1.2
2.0
1.0
MACPT
MACPY
QMIX
MACPT QPLEX
QPLEX
OPLEX
FOP
FOP
FOP
MAPPO
0.0
0.8
1.6
2.0
0.0
0.0
1.2
2.0
0.0
0.8
1.2
2.0
0.8
QMIX
OPLEX
0.6
FOP
MACPT
MACPT
0.4
QPLEX
OPLEX
FOP
FOP
MAPPO
MAPPO
0.0
0.0
0.0
many baneling
1c3s52
1.0
6h, 8z
0.8
QMIX
0.6
FOP
MACPF
MACPT
MAPPO
QMIX
0.4
QMIX
0.4
QPLEX
OPLEX
FOP
0.2
FOP
0.2
0.0
0.0
0.8
2.0
0.0
1.2
2.0
Figure Learning curves of all the methods in twelve maps of SMAC, where the unit of x-axis is 1M timesteps and y-axis represents the win rate of cach map.
As shown in Figure 9, MACPF NONLINEAR and MACPF ATT represent algorithms where all other aspects are the same as MACPF, except using a hypemeework with non-linearity and a weighted summation with actions input their mixer networks, respectively. MACPF NONNNONNN achieves similar performance as MACPF in the easy and hard maps, indicating that even distorted dependency can still benefit the learning. However, in the super-hard maps, MACPF outperforms MACPF_NONLAN NONNINNNNRRRR demonstrating the importance of accurate modeling of dependency among agents. MACPF ATT is outperformed by both MACPF and MACPF NONLINEAR by a large margin in all the maps, which verifies that the implicit dependency model in the mixer network of ATT confficts with the explicit dependency model in Q.TeP.
MACPF ATT
2.0
NB0N
10
8m vS 9m
2.0
NNNM2
2.0
corrider
2.6
WAOPE
HACFE
WACPT NONLINTAR
MACST NONUNEAR
0.2
5.2
MACPT ATT
MACIT ATT
2.0
2.4
2.2
0.0
04
0.5
0.4
0.
1.0
2.2
1.2
Figure 9: Ablation study of the mixer selection of MACPF four maps of SMAC, including easy map (MMM), one hard map (Sm_vs__ vs_ 9m) and two super-hard maps (MMM2, corridor), where x-axis M timesteps and y-axis represents the win rate each map.
17

---

Published as a conference paper at ICLR 2023
Table 2: Final performance all SMAC maps. We bold all values within standard deviation of the best mean performance each map.
Algorithms
MACPF
QMIX
QPLEX
FOP
MAPPO
Tasks
8m (easy)
0.994 0.006
0.986
0.99:10.01
0.992-10.005 0.997-10.003
MMM (easy)
0.984-0.015
0.984+0.01
0.905
1 0.975=0.017 0.962++0.035
2c_ys vs_ 2s_64z (hard)
0.972 0.031
0.946
0.904
0.976+0.011
0.945+H0.037
3s5z (hard)
0.976 0.008
0.955.10.017
0.969-10.018
0.26.10.212
0.715110215
8m_vs_ 10_ys___mmmm (hard)
0.916
0.798+00.021
0.571
0.85+
10m_vs vmm (hard)
11m
0.965 09035
0.939=10.032
0.95-10.016
0.545+10.25
0.774
MMM2 (super-hard)
0.788 0.083
0.709-10.16
0.224.10.231
0.506.10.14
0.679110.054
3s5x_ve vs_3s67 (super-hard)
0.209-0.202
0.024-0.031
0.0099
0.0++..0
0.144++0.175
corridor (super-hard)
0.691 0.344
0.0.10.0
0.002:10.005
0.0.10.0
0.58.10.184
27m vs 30m (super-hard)
0.726 0.094
0.532:10.23
0.294
0.45
0.7810.095
8m_vs is_9m (myopic)
0.855 0.069
0.675=:0.127
0.716:10.075
0.338
0.81
10m I 11m (myopic)
0.888 0. 188
0.702.10.129
0.664.10.089
0.384.1..722
0.514-10.253
3s vs 3z (easy)
0.974
0.988=0.014
0.994:1.0004
0.99911.002
0.997-100003
3s vs 4z (easy)
0.995 0.005
0.99-100008
0.997-10.003
0.789-10.22
0.957
3s vs. 5z (hard)
0.759-10.15
0.992.10.006
0.862.10.076
0.576110.063
so_ many baneling (easy)
0.969 0.001
0.974=0.00P
0.941
0.97=:0.225
0.979=:0.012
cc355z (casy)
0.984 0.006
0.98+
0.985 0.0
0.984
0.989=+0.007
6h vs. 8z (super-hard)
1059-0.033
0.001 0.0002
0.059110009
0.028:10.055
0.13:10.074
F FUTURE WORK
One limitation of our work is the sequential decision- process training. Since the dependent local policy яι (a:l a.cs) takes as input the joint action of all agents whose indices are smaller than agent agents have to make decisions one by one. This makes the whole decision process be O(N). There is not much difference when N is small. However, when is large, it slows down the training process. One approximate solution is to divide agents into groups, such that agents can make decisions group by group instead of one by one. However, such a mechanism may raise new question about how group agents, which will be considered in future work.
18


Reviews:
[{"review_id": "WbD237KF0wP", "reviewer": "Reviewer_krAZ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper addresses the problem of centralized training and decentralized execution (CTDE) in multiagent reinforcement learning. The paper contributes the MACPF algorithm (multi-agent conditional policy factorization), which relies on the idea that the joint policy given the history can be factorized conditioned on the actions of previous agents. In other words, in a $N$-agent Dec-POMDP, \n\n$$\\pi_{joint}(\\boldsymbol a\\mid\\boldsymbol \\tau)=\\prod_{n=1}^N\\pi_n(a_n\\mid\\tau_n,a_{<n}),$$\n\nwhere $\\tau_n$ is the history of agent $n$. Additionally, the paper observes that a dependent policy $\\pi_n(a_n\\mid\\tau_n,a_{<n})$ can be written as the sum of an independent policy plus a correction term, i.e., \n\n$$\\pi_n(a_n\\mid\\tau_n,a_{<n})=\\pi_n(a_n\\mid \\tau_n)+b_n(a_n\\mid \\tau_n,a_{<n}),$$\n\nwhere $b_n$ is the correction term. During the centralized training, the agents thus learn the dependent policy by learning the two components (the independent policy and the correction term). The former can then be used for decision-making during decentralized execution. The results portrayed in the paper indicate that the proposed approach indeed leads to improved performance over other competing approaches.", "summary_of_the_review": "The paper proposes a novel approach for centralized training and decentralized execution in multiagent reinforcement learning. The proposed approach is novel and provides improvements over the state of the art. There are, however, a couple of technical issues that I did not fully understand and which could be better explained.", "strength_and_weaknesses": "**Strengths**\n\nThe paper is very clearly written, and the ideas proposed are interesting and - to the extent of my knowledge - novel. The results also suggest that the proposed approach indeed pushes the performance of existing CTDE approaches.\n\n**Weaknesses**\n\nThere are some steps in the proofs which I didn't fully grasp and which could be better discussed. Specifically,\n1. I may have missed/misunderstood something, but it is not clear to me that the optimal policy factories as shown in (5), particularly in terms of the dependency on history. In light of this, I have some difficulty in making sense of Theorem 1, which seems to state that there is an optimal policy that verifies such factorization. Or is it stating that the algorithm converges to an optimal policy _over all policies that factorize as in (5)_?\n2. Still on the point above (and, again, I may have missed/misunderstood something) in the proof of Theorem 1 it is not clear to me how the conclusion that the sequence of policies $\\{\\pi^k\\}$ generated by the algorithm is improving (or, better said, not worsening) leads to the conclusion that the resulting policy is optimal overall joint policies. It seems to me that - in order for such a conclusion to hold - the limit must be unique from any initial policy, but it's not clear to me how such a conclusion follows from the proof...", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "BTDJU-CE22", "reviewer": "Reviewer_FBdE", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "This paper deals with the problem of decentralized policy in MARL when using the factorizing value method, especially FOP. To solve this problem, they propose **multi-agent conditined policy factorization** (MACPF) that incorporate dependency between the agents. \nDue to the fact that the proposed method learns the joint policy, it can guarantee to the optimal joint policy. They \nThey give the suitable network structure for the condition policy, also show the proper experiment results both in toy-example and complex task, SMAC. \n", "summary_of_the_review": "Learning the coordinated strategies in multi-agent is challenging because of partial-observability.\nThe author gives the intuition about what the problem is in the previous value-factorized method. To learn the opitmal policy, the depedency between agents should be considered, but it can break the decentralied execution in the test time. To keep the decentralized execution, having the factorized policies, they build the two seperate networks, dependent and individual networks. The proposed network structure is not simple, but they show the good performance by using the valued-based method when comparing strong baselines.  ", "strength_and_weaknesses": "- Streagth   \nActually, learn the joint-policy, it can gaurantee the optimal policy in joint-aciton space.   \nOuput the decentrazlied individual policies distilled from the dependent policies   \n\n- Weakness   \n  Complex network structure, do exist dependent and individual networks ( $Q^{dep}_i, Q^{int}_i$ )    \n  To learn the individual policies from joint dependency policies, they propose the naive method\n   ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "8DLXPvmq-7", "reviewer": "Reviewer_9QY5", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In order to better utilize the training paradigm of CTDE, the authors introduce dependency policy correction and dependency critic correction based on AC architecture to consider the action dependencies among the agents, and also design the corresponding network structure so that more accurate joint policy can be learned and thus more effective and better training results can be obtained.", "summary_of_the_review": "The work is interesting, but I currently have some doubts and I will adjust my scores further after the rebuttal", "strength_and_weaknesses": "Strength.\n* The paper is clearly written and well understood\n* Looks interesting by introducing corrections in the central training\n* The experimental section shows that the method proposed by the author works very well\n\nWeaknesses.\n* Equation (10) looks wrong because I don't see other additional constraints that make it mathematically reasonable since there is no way to ensure that the sum of \\pi_i^{dep} is 1. Also Equation (10) is not consistent with the implementation in Fig 3.\n* Equation (13) looks like it has many combinations possible, such as (Q - 10) + (c + 10), which means that its optimization space will become larger\n* Equations (16) and (17) are not clear on what policy the choice of next action is based on\n* Currently I am confused about the learning process of both ind and dep polices. In fig4, we can find that ind is slower than dep, but in fig7, the two polices are similar. Does this mean that there is no need to actually consider other agent's actions in smac? So why MACPF can outperform other strategies? Also is there a need for other experiments that consider agent?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "3p0T6wFwc0", "reviewer": "Reviewer_Eh9U", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "This paper studies the optimality issue of cooperative multi-agent reinforcement learning and claims that the independent policy factorization may lead to learning suboptimal policies. The authors propose a conditional policy factorization method, where an agent’s policy conditions on other agents (e.g., with lower indices). This paper claims that learning with such factorization theoretically leads to the optimal joint policy. It also shows that there exists an independent policy factorization that has the same value as conditional policy factorization, which enables decentralized execution. This paper empirically demonstrates the outperformance of the proposed method over baselines in a set of cooperative MARL tasks.", "summary_of_the_review": "The proposed method is interesting and shows outperformance over baselines. However, it is still not quite intuitive to understand why the proposed method outperforms baselines (see weaknesses above). In addition, the motivation of this paper shall be strengthened. ", "strength_and_weaknesses": "**Strengths**\n1. This paper studies the optimality of cooperative multi-agent reinforcement learning (MARL), which is an important problem. \n2. Although the idea of conditional policy factorization is not novel, it is interesting to see this idea to be implemented with the deep neural network.\n3. Empirical results on both a simple matrix game and more complex SMAC tasks show the effectiveness of the proposed method, compared to the baseline methods.\n\n**Weaknesses**\n1. The motivating example in Section 2.3 is confusing. From Section 2.2, FOP seems to have very limited expressiveness, the same capacity as a linear value factorization, e.g., VDN. This is because IGO factorization with the Boltzmann policy is equivalent to the linear value factorization. Therefore, FOP may not be a good candidate to show the limitations of independent policy factorization.\n2. The idea of conditional policy factorization has been proposed in [1], which shall be cited and discussed.\n3. Given the motivating example and the didactic matrix game, this paper seems to study multi-modality problems in cooperative MARL. This problem has been studied in [2], which should also be discussed or compared. \n4. The reviewer tried QTRAN on the matrix game in Figure 4 and found it could quickly learn the optimal policy, which has different results from the paper and may invalidate the claim of this paper. \n5.  Does the proposed method have a larger number of parameters than other methods, like FOP? If so, does this contribute to its outperformance?\n6. How does the proposed method perform against baselines on all benchmark tasks in SMAC?\n7. The paper is well-organized, but the presentation can be improved. The reviewer strongly suggests the authors use multi-agent MDPs to rewrite theorems and their proofs because Dec-POMDP with the infinite horizon is an undecidable problem. In addition, the approximation in Theorem 1 is quite informal.\n\n[1] Dimitri Bertsekas. Multiagent rollout algorithms and reinforcement learning, 2019. https: //arxiv.org/abs/1910.00120\n[2] Wei Fu, Chao Yu, Zelai Xu, Jiaqi Yang, Yi Wu. Revisiting Some Common Practices in Cooperative Multi-Agent Reinforcement Learning. ICML 2022.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster