Towards Global Optimality in Cooperative MARL with Sequential Transformation
Authors: Jianing Ye
Chenghao Li
Jianhao Wang
Qianchuan Zhao
Chongjie Zhang
Venue: Submitted to ICLR 2023 (2023)

Abstract: Policy learning in multi-agent reinforcement learning (MARL) is challenging due to the exponential growth of joint state-action space with respect to the number of agents. To achieve higher scalability, the paradigm of centralized training with decentralized execution (CTDE) is broadly adopted with factorized structure in MARL. However, we observe that existing CTDE algorithms in cooperative MARL cannot achieve optimality even in simple matrix games. To understand this phenomenon, we analyze two mainstream classes of CTDE algorithms -- actor-critic algorithms and value-decomposition algorithms. Our theoretical and experimental results characterize the weakness of these two classes of algorithms when the optimization method is taken into consideration, which indicates that the currently used centralized training manner is deficient in compatibility with decentralized policy. To address this issue, we present a transformation framework that reformulates a multi-agent MDP as a special "single-agent" MDP with a sequential structure and can allow employing off-the-shelf single-agent reinforcement learning (SARL) algorithms to efficiently learn corresponding multi-agent tasks. After that, a decentralized policy can still be learned by distilling the "single-agent" policy. This framework retains the optimality guarantee of SARL algorithms into cooperative MARL. To instantiate this transformation framework, we propose a Transformed PPO, called T-PPO, which can theoretically perform optimal policy learning in the finite multi-agent MDPs and shows significant outperformance on a large set of cooperative multi-agent tasks.

Under review as a conference paper at ICLR 2023
TOWARDS GLOBAL OPTIMALITY IN COOPERATIVE MARL WITH SEQUENTIAL TRANSFORMATION
Anonymous authors Paper under double-blind review
ABSTRACT
Policy learning in multi-agent reinforcement learning (MARL) is challenging due to the exponential growth of joint state-action space with respect to the number of agents. To achieve higher scalability, the paradigm of centralized training with decentralized execution (CTDE) is broadly adopted with factorized struc- ture in MARL. However, we observe that existing CTDE algorithms in cooper- ative MARL cannot achieve optimality even in simple matrix games. To under- stand this phenomenon, analyze two mainstream classes of CTDE algorithms - -ccto--rittic algorithms and seleeddccomoooition algorithms. Our theoretical and experimental results characterize the weakness of these two classes of algorithms when the optimization method is taken into consideration, which indicates that the currently used centralized training manner is deficient in compatibility with decentralized policy. To address this issue, we present a transformation frame- work that reformulates a multi-agent MDP a special 'single-agent MDP with a sequential structure and can allow employing off-the-sheil single-agent rein- forcement learning (SARL) algorithms efficiently learn corresponding multi- agent tasks. After that, a decentralized policy can still be learned by distilling the "single-agent" policy. This framework retains the optimality guarantee of SARL algorithms into cooperative MARL. To instantiate this transformation framework. we propose a Transformed PPO, called T-PPO, which can theoretically perform optimal policy learning in the finite multi-agent MDPs and shows significant out- performance on a large set of cooperative multi-agent tasks.
INTRODUCTION
Cooperative multi-agent reinforcement learning (MARL) promising approach to a variety of real-world applications, such as sensor networks (Zhang & Lesser (011)) traffic light control (Van der Pol & Oliehoek] 2016), and multi-robot formation (Alonso- Mora et al. 2017). How- ever, "the curse of dimensionality" is one major challenge in cooperative MARL, since the joint state-action space grows exponentially with respect to the number of agents. To achieve higher scalability, the paradigm of centralized training with decentralized execution (CTDE) (Kraemer & Baanejeee 2016a) is wildly used, which allows agents to learn their local policies in a centralized way while retaining the ability of decentralized execution.
Recently, many CTDE algorithms have been proposed. For value-based methods, the joint Q value is factorized as a function of individual values of agents (for which they also called value- decomposition algorithms), and then standard TD-learning is applied. To enable scalability and decentralized execution, is critical to ensure the joint greedy action can be computed by selecting local greedy actions through individual Q functions, which is formalized as the Individual-Globe Max (IGM) principle (Son et al. 2019). Based on this IGM property, a series of factorized multi- agent Q-learning methods have been developed, including but not limited to VDN (Sunehag et al.) 2018). QMIX (Rashid et al.) 2018). QTRAN (Son et al., 2019). and QPLEX (Wang et al. 2021b). For multi-agent actor-critic methods, the joint policy is often factorized into the direct product of individual policies, each of which is learned through policy gradient updates. For example, COMA (Foerster al.) (018)) and DOP (Wang al.) 2021c) aim at the critic design for effective credit assignment, MADDPG (Lowe et al.) 2017) studies the situation with parameterized deterministic policies, and MAPPO Yu et al. 2021) applies PPO to multi-agent settings with parameter sharing.

---

Under review as a conference paper at ICLR 2023
Despite the promising performance in benchmark tasks, these CTDE methods do not have global optimality guarantee in general cooperative settings and may fail to achieve optimality even in simple matrix games (Section 3. It might be confusing since some algorithms like QPLEX (Wang et al. 2021b) have been proven to converge to the global optimum in some theoretical work (Wang et al, 2021a), which contradicts our experimental results. To understand this phenomenon, theoretical analysis for both actor-critic algorithms and value-decomposition algorithms. It shows that when the optimization method is taken into consideration, which prior analysis didn't t, neither algorithms can get out of local optimums, yet which
provide
actor-critic algorithms nor value-decomposte wildly exists in multi- multi-agent tasks (Section
To address this suboptimality issue, we present a transformation framework that reformulates a multi-agent MDP as a special "single-agent" MDP with a sequential decision-making structure among agents. With this transformation, any off-the-shelf single-agent reinforcement learning (SARL) method can be adopted efficiently learn coordination policies in cooperative multi-agent tasks by solving the transformed single-agent tasks with their global optimality guarantee retained. To enable decentralized execution, a decentralized policy is learned at the same time by distilling the "single-agent" policy. As instantiation of this transformation framework, Transformed PPO (T-PPO) is proposed, which can theoretically perform optimal policy learning in finite-mulin multte-nlt--aeentt MDPs and empirically shows significant outperformance on large set of cooperative multi-agent tasks, including SMAC (Samvelyan et al., 2019) and GRF (Kurach et al.) 2019) using attention mechanism (Vaswani et al. 20177)
2
PRELIMINARIES & RELATED WORK
2.1 RL MODELS
In single-agent RL (SARL), agent interacts with Markov Decision Process (MDP) to maximize its cumulative reward (Sutton & Bart 2018). An MDP is defined as a tuple (S,A, r, P, 7, so), where S and A denote the state space and action space. At each time step t, the agent observes the state 8 and chooses an action or E A. where a ~ (8+) depends on 8 and its policy π. After that, the agent will gain instant reward ra r(s,, at), and transit the next state 8t41 P(-sst, at)- is the discount factor. The goal of an SARL agent is to optimize a policy π that maximizes the expected cumulative reward, i.e., J [(T) = E.,,y-P(lee.tt
-000n" ('((,,, (s.))).
In MARL, we model a fully cooperative multi-agent task as Dec-POMDP (Olihhoek er al. 2016) defined by a tuple S, P,, P, f2, O, where A is a set of agents and S is the global state space, A is the action space, and is discount factor. At each time step, agent i E N has access to the observation o; E .2, drawn from the observation function O(s, i). Each agent has an action- observation history E _2x (.A x !2)* and constructs its individual policy IT [a: (T.). With each agent shared reward r R(s, a) and the next state s' according to the transition distribution P(s"|s, a). The formal objective of MARL agents is to find a joint policy π = (TI,.... TT) conditioned on the joint trajectories т = [r,]a-] that maximizes joint value function (*) = E Dr
i selecting an action a; E A, the joint action a = [a leads
s. - >rrelso s.. Another quantity in policy search the joint action-value function Q (s, a) = r(s, a) + E.. (V*(s)))
0c
To simplify our analysis, we present framework of Multi-agent MDPs (MMDP) (Boutilier 1996). a special case of Dec-POMDP, to model cooperative multi-agent decision-making tasks with full observations. MMDP is defined tuple S, P.r.)), where A S, A. P, and y the same agent set, state space, action space, transition function, reward function, and discount factor in Dec-POMDP, respectively. Due the full observations, each time step, the current state is observable to each agent. For each agent i, an individual policy म. (als) represents a distribution over actions conditioned on the state s. Agents aim find joint policy
(f .a.....,fe a,) that maximizes a joint value function i (s), where denoting t (s) = E 1Σ >'relsu = s, f].
2.2 POLICY FACTORIZATION AND CENTRALIZED TRAINING WITH DECENTRALIZED EXECUTION
In MARL, due to partial observability and communication constraints, a decentralized policy is required during execution, i.e., the joint execution policy ा test can be decomposed into product of
2

---

Under review as a conference paper at ICLR 2023
individual execution policies [m/est]e k=
called policy factorization:
VT test tee (alT)
II i=1
test (a:l7:)-
In order to effectively learn n test centralized training with decentralized execution (CTDE) be- comes popular paradigm of cooperative MARL (Oliehoek al., 2008; Kraemer & Banerjee 2016b). In CTDE, agents are trained in a centralized manner and are granted access to other agents' information or global state during the centralized training process. Denote the joint policy which is learned during training as π train Note that during centralized training, the constraint of policy factorization (see Eq. (T) is not necessary for π train and the agents can use joint policy Trrann to interact with the environments for collecting training data. However, most popular CTDE MARL
2021 de Witt er al. 2020; Sunnhaa et al. 2018 Rashid et al. 2018 8 Son et al. 2019 Wang et al., 202 encode the policy factorization defined in Eq. ①1) into the training joint policy ' trasn and these algorithms
algorithms (Foerster et al., 2018 Lowe al.] 2017: Wang et al., [222c]] Yu et al.,
can be divided into two categories: actor-critic and seclle--ccompsttiionn.
For multi-agent actor-critic algorithms (Foerster et al. 2018: Lowe et al. 2017 Wang et al. 202 Yu et al. 2021 de Witt et al. 2020), a joint (stochastic deterministic) policy represented as product of individual policies, i.e., <(aaT) II== (a (Ta), which corresponds to policy factor-
ization defined in Eq. (T). After that, some estimation of multi-agent policy gradient (Kuba et al.
2021 is calculated through the critic to update the policy.
For value-decomposition algorithms (Sunchag et al. 2018 Rashid et al. 2018 Wang et al. 202
the joint value is decomposed as function of local Q values with some parameter À A
et al. 2022
Q)(T,a)= = (mi
).T,
(2)
After that, standard TD-learning is applied, and the IGM (Individual Gaiiial---loo---Ma -Mxx principle (Son al., 2019) is enforced to realize effective TD-learning, which asserts the consistency between joint and local greedy action selections in the joint action-value Qtor (T, a) and local action-values (Q; a.) a=)) respectively:
VT : arg max Qzoe (T, aEA
arg max Q1) arg max Qu (Tn: Qn))
(3)
aLEA
en EA
Denote the greedy joint policy as T(a arg max Qroe(T, a) and the greedy individual policies as (a: = arg max QT az). We have T(a = II (Ta which is called policy factorization defined in Eq. 1 Although various value factorizations (Wang et al. 2021a Fu et al.) (022) are widely studied in the literature, to our best knowledge, this paper is the first to study the effect of CTDE from the perspective of optimal policy learning with optimization methods.
SUBOPTIMALITY OF CURRENT CTDE ALGORITHMS: INHERENT LOCAL-MINIMA STRUCTURE IN LOSS FUNCTION
In this section, we will formally analyze the suboptimality of multi-agent actor-critic and value- decomposition algorithms when taking the optimization method into consideration. short. the manner of centralized training adopted by multi-agent actor-critic and value-decomposition meth- ods creates inherent local-minima structures in their loss function, which makes gradient-descent methods lose optimality guarantee in general.
The main results this section are summarized as Theorem 3.1 and Theorem 3.2
These two theorems elucidate the existence of local minima in the loss function of both actor-critic and value- decomposition algorithms. For multi-agent actor-critic algorithms, any Nash's 's equilibrium of poli- cies always constitutes stationary point of the loss function of actors, regardless of the parameteri- zation of policy networks (c.g. sharing parameter (Cobbe et al., 2020) or not) and credit assignment in gradient calculation (Foerster et al. 2018), which implies multi-agent policy-gradic can reach
3

---

Under review as a conference paper at ICLR 2023
zero when current policies are not optimal. Consequently, it makes multi-agent actor- actor-critic al- gorithms lose optimality guarantee when gradient pessentt-bsse optimization methods are used. For calue-decomposstionn algorithms, we will prove that the loss function of any value-decomp celle-decommosttionn method could have exponentially many local optima as long as the Q-function class is complete for the IGM condition. In the research of of work (Sunchag et al. [2018) Rashid et al. 2018 Wang et al. (0211) to enrich the Q-function class and make it complete since incomplete function would diverge the process of TD-learning (Wang et al., 2021a). However, our result shows that the richness of Q-function class and the smoothness of the loss function cannot retain the same time under the IGM condition, which leads the gradient descent-based optimization methods to fail in this case.
great efforts have been made by series
Actor-Critic algorithms On the one hand, for aulti- actor-critic algorithms on MMDP, the ss; 0) II (a:|s; (Glss;), 0). And the actor loss a primitive function of policy gradient, thus the policy is updated via multi-agent policy gradient Leonardos et al. 2022). We can prove the following theorem:
actor represents decentralized stochastic policy тz (a|s;
Theorem 3.1. For multi-agent actor-critic algorithms, any Nash's 's Equilibrium of policies is a sta- tionary point of actor loss. Moreover, there exists family of single step-MMDP such that the actor loss function contains 92 ()) different local minimums for deterministic policy and infinite local minimums for stochastic policy.
This theorem suggests that multi-agent actor-critic algorithms create inherent local minimums for their actor loss functions, and may get stuck in any Nash's equilibrium of policy, which can be arbitrarily worse than optimal policy (Table The proof is presented in Appendix A.1
Table 1: Matrix Game with multiple Nash Equilibria: players (one selects a row and one selects column) coordinate to select an entry of the matrix representing the joint payoff. In this case, (0, 0), 1). (2 are three different Nash's Equilibria with different payoffs 10, 5, 1. Only (0, 0) is the globally optimal policy. However, policy (1, 1) and (2, 2) are two local minima of the actor loss, no matter what parameterizations of local policies are due to Theorem 3.1
10
-20
-20
-20
5
0
-20
0
Valoe-decomposition algorithms On the other hand, for a value-decomposition algorithm, the joint Q-value function is decomposed as Eq. (2) and updated by standard TD-loss. We are able to prove the following theorem:
Theorem 3.2. There exists family of MMDP, such that for any value valoe-decomposition algorithm with a complete Q-function class satisfying the IGM condition (Eq. 3 the TD-loss function contains
Q (IA) (S)) different local optima.
The term "complete O-function class" refers to that any function x|A"" is decomposable by the function fmix. like that in QPLEX (Wang et al.] 2021b). This theorem suggests that, for value- decomposition methods with IGM condition satis- fied, then either it has an incomplete function class (e.g. VDN (Sunehag et al.) 2018), QMIX (Rashid)
optimal
MAPPO vdn
qtran
T-PPO (ours)
qplex
HAPPO
qmix
Multi-task Matrix Game
Sum roward all 10 matricas
100
.95
et al.) 2018)) or it's loss function contains expo- nentially many local optimums (e-g- QPLEX, contains infinite local optimums (Proposition A.I.
85
worse than what claimed in Thcorem (.2). both
of which loses optimality guarantee when gradient- based optimization method adopted. The proof is presented in Appendix A.I
80
0.0
0.2
0.4
0.6
0.8
1.0
time(1e6)
Figure Learning curve of Multi-task Ma- trix Game
To give some experimental indication of our theo- rems, introduce multi-task matrix game here,
4

---

Under review as a conference paper at ICLR 2023
which is a simple 1-step game with 2 players and 10 matrices (see Appendix [B.11 for details). We demonstrate the sum reward of all matrices for our approach and baselines in Figure I Baseline algorithms get stuck in locally optimal solutions, which confirms the theorems we discussed above. And with the theoretical guarantee of global optimality, our method (see Section 4.2) converges to 100 immediately. Value-based methods VDN, QMIX, and QPLEX converge optimal point at the end of training. Taking benefit from the duplex dueling network architecture, QPLEX has a stronger representative ability than VDN and QMIX. Nevertheless, such a complex structure creates inherent local optima for its loss function (Theorem 3.2] (oopssitionA.1)) QTRAN (Son et al.] 2019) achieves convincing performance in some simple matrix games with a carefully designed regularizer tackling IGM. However, its discontinuous loss function will still hinder the globally optimal solution in this case (Appendix [A.I]. SOTA multi-agent actor-critic algorithms HAPPO (Kuba et al., [02T) and MAPPO get stuck in Nash's Equilibrium and cannot guarantee global optimality (Theorem 3.1
similar local
In this way, our approach dominates in our multi-task matrix
game.
4 A SEQUENTIAL TRANSFORMATION FRAMEWORK FOR MARL PROBLEMS
To achieve global optimality in cooperative MARL with the CTDE paradigm, we try to design a new manner of centralized training to fit decentralized policy better with gradient descent-basse opti- mization. Inspired by series of prior works on sequence modeling (Bertsekas) 2019; Angermuellr et al. 2020 Jain et al., 2022 Olivecrona et al. 2017 You et al. 2018), we found that breaking joint learning into sequential decision-making directly transfers properties single-agent algorithms into multi-agent ones. To formalize such "reduction" of algorithms under the perspective of optimality guarantee, we propose a transformation framework that allows us to employ any single-agent RL. (SARL) algorithm to efficiently learn corresponding multi-agent tasks with optimality guarantee of the SARL algorithm (if it has) kept.
From the theoretical perspective, also find that this transformation framework keeps the same mini-max sample complexity (Appendix A.4). However, in order to maintain sample efficiency un- der this framework, one main challenge deal with the long horizon and sparse reward (Appendix A.4. while they have been long-term challenges for the design of empirical reinforcement learning algorithms (Arjona-Mens Medina et al. 2018 Zheng et al.] 2018:; Gangwani et al. 2020). To tackle this challenge and instantiate our transformation framework. we propose a Transformed PPO, called T-PPO adopting the attention mechanism in network design, which incorporates the remarkable em- pirical ability of PPO (Schulman et al.) (b1 and the attention mechanism (Vaswani et al.) (017) as well as a theoretical optimality guarantee the finite MMDPs. In this way, our implementation of T-PPO also bridges the gap between theoretical analysis and empirical performance.
4.1 SEQUENTIAL TRANSFORMATION
In the training phase of CTDE, all n agents will coordinate to improve their joint policy. In particular, when joint action needs to be inferred, they coordinate to infer a (ai,'.., a,,) jointly. If we give these agents a virtual order, imagine they infer their individual actions one after another, that is, in the centralized training phase, when agent i infers its action a,, all "previously inferred" actions a, (j- < i) are known to i. As we shall see, this procedure of multi-agent decision-making is equivalent to a aaggle-agent one since all agents are homogeneous the centralized training phase. From a theoretical perspective, the discussion above states a transformation from MMDP into MDP in essence.
Definition 4.1 (Sequential Transformation I, informal). Given MMDP M with n agents, its sequential transformation is an MDP I (M), that (1) for every time step mod n = 1, the agent infers the action a and transit from a state to a virtual state (s, (.)) for every time step
t mod =i> >>>> 1, it infers an action a. ( and transit from virtual state (s, a (.))) (s, a())) for
(f) ) to state every time step mod n = 0, it infers an action on and transit from virtual state (s, azz)
s' according to the dynamics of MMDP M, at the same time, it gain a reward from M. f = t//n] here is the corresponding time step on M.
5

---

Under review as a conference paper at ICLR 2023
We present the formal definition in Definition A.1 for completeness. We then prove the equiva- Ience of the MMDP M and the MDP ((M) after transformation in the perspective of policy value, which is presented in appendix (Theorem A.II) due to the lack of space. This theorem also provides the conversion method between policy on ((M) and joint policy on MM.
This transformation allows to any SARL algorithm A, wrap the interface of the multi-agent environment to make run as if it is accessible to the interactive environment of I (M), and finally convert the policy learned by A joint policy on M. The sequential framework converting SARL algorithm A to MARL algorithm T-A is formally described in pseudo-code in Appendix (Algorithm
D
At last, we can claim the main theorem of this framework.
Theorem 4.1 (The transformation framework keeps the optimality). Using the sequential frame- work (Algorithm 7. if the SARL algorithm 2 is guaranteed to obtain an optimal policy on MDP, then the MARL algorithm 7-a is guaranteed to obtain an optimal policy on MMDP.
Moreover, thanks to the theoretical analysis for the global optimality of PPO with neural networks ((Liu al.) ) we are able to claim a suitable implementation of T-PPO attains the global optimality under the same mild assumptions in Liu et al. (2019).
Proposition 4.1 (Suitable implementation of T-PPO has optimality guarantee). T-PPO converges to global optimum, if Assumption 4.1, 4.2, and 4.3 in Liu et al. (2019) hold, in particular, if M is tabular.
The proof's of both propositions presented in Section A.3 and more analysis of the complexity of the transformed model is presented in Section A.4
4.2 T-PPO: EXTENSION TO DEC-POMDP
In practice many MARL benchmarks are partially observable. To apply our algorithms to partial- observable environments, we need to extend our algorithms to Dec-POMDP. To instantiate our trans- formation framework, 2017a). The Actor-Critic structure is shown in Figure 2 Following the sequential transformation framework discussed in Section 4. introduce previous agents' actions to each agent's actor and critic modules. However, this sequential transformed information increases with respect to the number of agents. To achieve scalability, we equip each agent's 's actor and critic with a multi-head attention (MHA) module.
propose Transformed PPO (T-PPO) based on PPO (Schulman et al.,
Intuitively, we believe considering too much information from previous agents' actions is harmful to learning since in most cases, we do not need that much information for single agent to make a decision. So we add regularization terms agents' actor and critic modules to encourage each (t) agent to extract critical information. As demonstrated by yellow modules in actor, policies Ti. used for training is combined with two parts: one part contains previous agents' actions as inputs for the MHA module, and the other part only takes the individual trajectory as input (IT(() (t)
(t) For regularization, add KL divergence between Timaiin and प. to decrease the influence of previous agents' actions. A similar structure is also implemented in the critic structure, as shown on the right side of Figure 2 with L1 norm for regularization. further distill the single-agent policy T. to a decentralized policy T optimizing the cross entropy loss independently for each agent, which is equivalent to minimizing
enable decentralized execution, we
(t) with behavior cloning by
the KL--divergence between the joint policy and the joint decentralized policy (see Appendix [B.2.3
for detail). Here we share GRU and the representation layer, whose inputs do not contain other agents' information.
5 EXPERIMENTS
We design experiments to answer the following questions: (1) Can the proposed sequential frame- work achieve the globally optimal policy on MMDP? (Section 3 and Section 5.1.Ip (2) Can our approach improve learning efficiency for pasee MARL algorithms? (Section 5.1 and Section

---

Under review as a conference paper at ICLR 2023
Evalluation
Training
Bolllation
morr
14
10
MUP
mean
11
MLP
N
WDs
MLP
Actor
MLP
Critic
WTT
Lof" a0
SotMMs
Figure 2: The architecture of combining our sequential transformation framework with PPO (T- PPO)
5.2 (3) Will distillation influence performance during decentralized execution? (Section
5.1 and
Section 5.2
We first use multi-task matrix game to demonstrate the global optimality of our single- policy compared multi-agent value-based methods (VDN, QMIX, QTRAN, QPLEX) and policy-based methods (MAPPO, HAPPO (Kuba et al. (021)) This part has been discussed in Section 3 Then, we use challenging tasks from the StarCraft Il micromanagement (SMAC) Benchmark(Samvedd
et al.]
2019) and Google Research Football (GRF) benchmark (Kurach et al. 2019) to further demonstrate and illustrate the outperformance of our approach. In each environment, variance of the performance for our method and baselines tested with three random seeds (seed O, 1, 2). For all baselines, we use the codes provided by the authors properly with the same hyper- parameters the original papers.
show the average and
5.1 STARCRAFT II
T-PPO (ours)
T-PPO-Distilation (ours)
MAPPO
HAPPO
MMM2
3652 vs 3662
6h vs 8z
90
90
Test Win
60
60
30
30
30
0
2
4
6
10
0
2
6
8
10
2
4
8
10
T (mil)
(mil)
T (mil)
corridor
3h vs 1b123h
1c3s52
90-
90
Test Win %
60
60-
60
30-
30
30
0
0
5.0
7.5
10.0
T (mil)
T (mil)
T (mil)
Figure 3: Learning curve of SMAC
Here we compare our approach with policy-based baselines on four super hard maps (MMM2, 3s5z_ vs_ 3s6z, 6h vs_ vs_8z, corridor), one easy map (1c3s5z), and one custom map (3h_va_1bi23h) based on the SMAC benchmark.
We illustrate the learning curve of StarCraft II in Figure 3 Our "single-agent" policy outperforms baselines on five out of six maps while performing similarly with MAPPO on _h_vv______________________e maps are typically hard-exploration tasks. However, taking benefit of our approach' global optimal- ity guarantee for MMDP, T-PPO can exploit better with the same exploration strategy as MAPPO (based the entropy of learned policies). We will highlight map 1c3s5z, where MAPPO con-
vs_ vs_82. Super hard

---

Under review as a conference paper at ICLR 2023
verges to locally optimal point but approach achieves global optimality with nearly 100% winning rate. This phenomenon once again demonstrates the advantage of our sequential transfor- mation framework. HAPPO can also achieve nearly 100% winning rate 1c3s52 but fails on other maps. We believe it is still because local optimality of Nash equilibrium learned by НАРPO. Meanwhile, compared with our approach and MAPPO, agents cannot share parameters in HAPPO, which significantly affects the training efficiency in complex tasks.
Table 2: Mean value and standard deviation of winning rate on the SMAC benchmark.
Task
Difficulty Super Hard
T-PPO
T-PPO-D
MAPPO
НАРРО
QPLEX
MMM2 3s5z vs 3s6z
81.6 (7.7)
82.5 (6.1)
68.5 (8.4)
83.9 (1.5)
74.8 (11.6)
Super Hard
85.5 (5.2)
82.7 (6.2)
78.3 (14.5)
26.0 (4.3)
75.8 (12.3)
6h vs 8z corridor
Super Hard
91.8 (1.1)
(4.1)
90.7 (0.7)
20.0 (13.3)
20.7 (14.7)
Super Hard
99.1 (0.3)
99.2 (0.1)
(0.4)
99.2 (0.2)
30.3 (41.3)
3h vs Iblz3h
Local Optimal
71.4 (20.7)
65.9 (17.2)
35.0
(1.4)
30.7 (23.2)
lc3s5z
Easy
99.8 (0.0)
99.8 (0.1)
73.3 (11.4)
99.9 (0.0)
98.7 (1.0)
We show the mean and standard deviation between the winning rates of the final policies trained on different random seeds in Table T-PPO-Distillation (T-PPO-D, decentralized policy) outperforms T-PPO in two maps while outperforming MAPPO in five out of six maps, indicating our approach's competitiveness in decentralized execution. Only in 6h vs 8z, T-PPO- Diot-Distlllation performs worse than T-PPO, demonstrating that correlation learned by T-PPO might be overly dependent on the sequential transformation even though we have added several normalization items. Although this phenomenon rarely occurs and depends on one special task, we will study this limitation future work.
5.1.1 ADVANTAGE OF SEQUENTIAL TRANSFORMATION FRAMEWORK IN SMAC
In this section, we will further analyze the lo- cal optimality of SMAC. Compared with the matrix game, the StarCraft II tasks are more complex with high dimensional state space. To verify whether our approach can drive agents out of local optimal points as in matrix games, we create a new StraCraft II map named 3h_vs_ 1b1z3h
Figure 4: Illustration of 3h w_svvss_i311
In 3h vs 1b1z3h, we control three Hydralisks, while our opponent controls three Hydralisks, one low-damage Zergling, and one Baneling with high area damage. The explosion of the Baneling can only be avoided if all agents gather fire to it instead of the nearer Zergling. However, gathering fire to the Zergling could be a suboptimal equilibrium, where no agents tend to change its policy.
Previous research has demonstrated that super- hard maps in SMAC require more exploration (Wang al. 2020 Li al. 2021a). How- ever, we find different experimental results on the maps that contain local optimal points, such as our own designed map ho__v_ibiz330 PPO, exploration is guaranteed by the entropy term in its loss function. As shown in Figure T-PPO and MAPPO's performance changes are divergent on different maps while tuning the related hyperparameter.
T-PPO lours)
MAPPO (entropy weight
ve (entropy weight: 0.01)
80-
TestWn
60
60
30
In
3h vs 1b1zah Timl)
0.0
2.5
5.0
waight 0.011
7.5
10.0
90
3h
0.0
1b113h (emrody weight: 0.0
2.5
T (ml))
5.0
7.5
10.0
Tost %.
60
2.5
5.0
7.5
10.0
6h vs vs_ increas- ing entropy weight will improve learning effi- ciency for both algorithms. It is in line with our expectations. On 3h_ vs_ 1b123h, increas- ing entropy weight will still improve the perfor- mance of T-PPO but will make the performance of MAPPO worse. We believe this phenomenon is related to the local optimality we discussed above.
6h_
Figure 5: Different changes caused by adjusting the exploration coefficients (entropy weight) be- tween T-PPO and MAPPO on 3h vs 1b123h and 6h_vs_8z
MAPPO has motion to drive agents to escape local optimal points, which leads to low exploita-
8

---

Under review as a conference paper at ICLR 2023
tion efficiency. Taking advantage of handling global optimality discussed in Section 4.1 approach achieves better exploitation under the same exploration strategy.
5.2 GOOGLE RESEARCH FOOTBALL
In this section, test our approach against policy-based baselines another MARI benchmark named Google Research Football (GRF). In the environment setting, we use sparse rewards with follow
both SCORING and CHECKPOINT for approach and all baselines. For observations, (Li et al. a using the simple 15-diimensional vector as the observation while removing the information irrelevant the current scenario. Meanwhile, we introduce the relative position for each agent instead of absolute coordinates to achieve a more realistic environment.
T-PPO (ours)
APPO-Distillation (ours)
MAPPO
НAРPO
vs with keeper
run pass and shoot with keeper
counterattack hard
100
15
Test Win %
10
0
0.0
2.5
5.0
7.5
10.0
0.0
2.5
5.0
7.5
10.0
0
20
40
T (mil)
(mil)
T (mil)
Figure 6: Learning curve of GRE
As shown in Figure our approach obviously outperforms baselines, achieving remarkable winning rate, while baselines almost learn nothing win in srademy_pass. _nd_aanno_____eeeeaaeeeeeeo___le wwwothhhhttteoee setott_wttt_gge heeperreeerrrre and academy_ coarlyy_couttraaaeeee waantterttttkaaaate _ardd GRF scenarios, agents must coordinate timing and positions to organize offense to seize fleeting opportunities. The cooperation between agents is difficult to coordinate because of the sparsity of agents' crucial movements. Our sequential transformation framework provides an optimal solution to MMDP by forcing agents to consider the information from previous ones, which promotes coordination among agents for achieving sophisticated co- operation. Compared with T-PPO, T-PPO-Distillation performs similarly, which ensures that algorithm can be executed in a wide range of environments.
CONCLUSION
In this paper, we study state-of-the-aar cooperative multi-agent reinforcement learning methods and observe that, even with full expressiveness, they may fail to converge an optimal solution in simple matrix games. To analyze this phenomenon, we generalize these MARL methods with a general model and find that their factorized policy structure combined with the gradient descent optimization one of the major causes of their suboptimality. To solve this issue, we propose a novel sequential transformation framework that allows employing off- off-the-shelf single-agent reinforcement learning methods to solve cooperative multi-agent tasks and retain their global optimality guarantee. Based on this framework, develop T-PPO that extends single-agent PPO multi-agent settings and significantly outperforms baselines on various benchmark tasks. It is an interesting future direction extend efficient value-based SARL methods to multi-agent settings through our transformation framework.
REFERENCES
Javier Alonso-Mora, Stuart Baker, and Daniela Rus. Multi-robot formation control and object trans- port in dynamic environments via constrained optimization. The International Journal of Roboties Research, 3609):1000-1021, 2017.
Christof Angermueller, David Dohan, David Belanger, Ramya Deshpande, Kevin Murphy, and Lucy Colwell. Model-based reinforcement learning for biological sequence design. In International

---

Under review as a conference paper at ICLR 2023
Conference Learning Representations, 2020. UtL/attps///pennrrreeeeett/////. id=Hk Hk1 xbgBKvx
Jose A. Arjona- Medina, Michael Gillhofer, Michael Widrich, Thomas Unterthiner, Johannes Brand- stetter, and Sepp Hochreiter. Rudder: Return decomposition for delayed rewards, 2018. URL
https://arx: wwg. wwwg////////ooooooooooo///oa 806.066000 07857
Dimitri Bertsekas. Multiagent rollout algorithms and reinforcement learning, 2019. URL https:
Craig Boutilier. Planning, learning and coordination in multiagent decision processes. In Proceed- ings of the 6th Conference on Theoretical Aspects of Rationality and Knowledge, pp. 195-210. Morgan Kaufmann Publishers Inc., 1996.
Karl Cobbe, Jacob Hilton, Oleg Klimov, and John Schulman. Phasic policy gradient, 2020, URL https:://axiv
04416
Christian Schroeder de Witt, Tarun Gupta, Denys Makoviichuk, Viktor Makoviychuk, Philip HS Torr, Mingfei Sun, and Shimon Whiteson. Is independent learning all you need in the starcraft multi-agent challenge? arXiv preprint arXiv:2011.00933, 2020.
Jakob N. Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson. Counterfactual multi-agent policy gradients. In AAAI, 2018.
Wei Fu, Chao Yu, Zelai Xu, Jiaqi Yang. and Yi Wu. Revisiting some common practices in coop- erative multi-agent reinforcement learning, 2022. URL htt.::t:/aax....org////o//// ottps///w....////22....... 07505
Tanmay Gangwani, Yuan Zhou, and Jian Peng. Learning guidance rewards with trajectory-space http://///aaaii.ooo///////////// abs/://0bb//20cc/ 12718
smoothing, 2020.
Moksh Jain, Emmanuel Bengio, Hexxnneena Garcia, Jarrid Rector-Brooks, Bonaventure F. P. Dossou, Chanakya Ekbote, Jie Fu, Tianyu Zhang, Micheal Kilgour, Dinghuai Zhang, Lena Simine, Payel Das, and Yoshua Bengio. Biological sequence design with gflownets, 2022. URL
https://arxx org/ abs 2203. 04115
Landon Kraemer and Bikramjit Banerjee. Multi-agent reinforcement learning as a rehearsal for decentralized planning. Neurocomputing, 190:82 94, 2016a.
Landon Kraemer and Bikramjit Banerjee. Multi-agent reinforcement learning as a rehearsal for decentralized planning. Neurocomputing, 190:82-94, 2016b.
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 arXiv:2 109. /251, 2021.
Karol Kurach, Anton Raichuk, Piotr Stanczyk, Michal Zajac, Olivier Bachem, Lasse Espeholt, Car- los Riquelme, Damien Vincent, Marcin Michalski, Olivier Bousquet, al. Google research football: A novel reinforcement learning environment. arXiv preprint 1rXiv:1907.11186. 2019.
Stefanos Leonardos, Will Overman, Ioannis Panageas, and Georgios Piliouras. Global convergence of multi-agent policy gradient in markov potential games. In International Conference on Learn- ing Representations, 2022. htLLttttt///:peeeeeeee
net. forumm 2
Chenghao Li, Chengjie WU, Tonghan Wang, Jun Yang, Qianchuan Zhao, and Chongjie Zhang. Cel-
ebrating diversity in shared reinfoormmmttii learning. arXiv preprint 2rXiv:2/06.002/95,
2021a.
Gen Li, Changxiao Cai, Yuxin Chen, Yuantao Gu, Yuting Wei, and Yuejic Chi. Is q-learning mini- max optimal? a tight sample complexity analysis, 202lb.
Boyi Liu, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural proximal/uut region policy optimiza- tion attains globally optimal policy, 2019. URL httphttps:///rra wttp:/wwwwwg///o////ooob/ 10306
10

---

Under review as a conference paper at ICLR 2023
Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, Pieter Abbeel, and Igor Mordatch. Multi-agent actor- critic for mixed cooperative-comper environments. Neural Information Processing Systems (NIPS), 2017.
Xiaoteng Ma, Yiqin Yang, Chenghao Li, Yiwen Lu, Qianchuan Zhao, and Yang Jun. Modeling the interaction between agents in cooperative multi-agent reinforcement learning. arXiv preprint arXiv:2102.06042, 2021.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning, 2013. URL
https://arxiv. http://axxvvrrra/a//ee./ 1012/1111.562
Frans A Olichoek, Matthijs TJ Spaan, and Nikos Vlassis. Optimal and approximate q-value func- tions for decentralized pomdps. Journal of Artificial Intelligence Research, 32:289-355 353, 2008.
Frans A Oliehoek, Christopher Amato, al. A concise introduction to decentralized POMDPs, volume 1. Springer, 2016.
Marcus Olivecrona. Thomas Blaschke, Ola Engkvist, and Hongming Chen. Molecular de novo design through deep reinforcement learning. 2017. /R//ttpsss//cxiivoor///////
07555
Tabish Rashid, Samvelyan, S.S.D. D. Witt, Gregory Farquhar, Jakob N. Foerster, and Shimon Whiteson. Qmix: Monotonic value function factorisation for deep multi-agent reinforcement learning. ArXiv, abs/1803.11485, 2018.
Mikayel Samvelyan, Tabish Rashid, C. S. D. Witt, Gregory Farquhar, Nantas Nardelli, Tim G. J. Rudner, Chia-Man Hung, Philip H. S. Torr, Jakob N. Foerster, and Shimon Whiteson. The starcraft multi-agent challenge. ArXiv, abs/1902.04044 2019.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov, Proximal policy optimization algorithms. ArXiv, abs/1107700634, 2017,,
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06344 2017b.
Kyunghwan Son, Dacwoo Kim, Wan Ju Kang, David Earl Hostallero, and Yung Yi. Qtran: Learn- ing to factorize with transformation for cooperative multi-agent reinforcement learning. ArXiv, 10000/00505,,8 2019.
Peter Sunehag, Guy Lever, Audrunas Gruslys, Wojciech M. Czarnecki, Vinícius Flores Zambaldi, Max Jaderberg, Mare Lanctot, Nicolas Sonnerat, Joel Z. Leibo, Karl Tuyls, and Thore Grae- pel. Value-decomposition networks for cooperative multi-agent learning, ArXiv, abs/ abs/1706.05296, 2018.
Richard Sutton and Andrew G Barto. Reinforcement leurning: An introduction. MIT press, 2018.
Elise Van der Pol and Frans A Oliehoek. Coordinated deep reinforcement learners for traffic light control. Proceedings of Learning, Inference and Control of Multi-Agent Systems (at NIPS 2016), 2016.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need, 2017. pRtppss:://axxi
/tr/abb/11706.00 03762
Jianhao Wang, Zhizhou Ren, Beining Han, Jianing Ye, and Chongjie Zhang. Towards understanding cooperative multi-agent q-learning with value factorization. Advances Neural Information Processing Systems, 34, 2021a.
Jianhao Wang, Zhizhou Ren, Terry Liu, Yang Yu, and Chongjic Zhang. Qplex: Duplex dueling multi-agent g-earnnin. ArXiv, abs/2008.01062. 2021b.
Tonghan Wang, Tarun Gupta, Anuj Mahajan, Bei Peng, Shimon Whiteson, and Chongjie Zhang. Rode: Learning roles to decompose multi-agent tasks. arXiv preprint 2rXi::2010.01523, 2020.
11

---

Under review as a conference paper at ICLR 2023
Yihan Wang, Beining Han, Tonghan Wang, Heng Dong, and Chongjie Zhang. Dop: Off-policy
multi-agent decomposed policy gradients. In ICLR, 2021c.
Jiaxuan You, Bowen Liu, Rex Ying, Vijay Pande, and Jure Leskovec. Graph convolutional policy
network for goal-directed molecular graph generation, 2018. URL https://arxiv.orrt
abs/ bos/1806. 02473
Chao Yu, Akash Velu, Eugene Vinitsky, Yu Wang, Alexandre Bayen, and Yi Wu. The surprising effectiveness ppo in cooperative, multi-agent games. arXiv preprint arXiv:2103.01955, 2021.
Chongjie Zhang and Victor Lesser. Coordinated multi-agent reinforcement learning in networked distributed pomdps. In Twenty-Fifth AAAI Conference Artificial Intelligence, 2011.
Zeyu Zheng, Junhyuk Oh, and Satinder Singh. On learning intrinsic rewards for policy gradient methods, 2018. URL https: /tttcpp://axxi...o/
arxiv. 0ttp://aaa....o////////....000 06459
12

---

Under review as a conference paper at ICLR 2023
A
APPENDIX
A.1 SUROPTIMALITY OF EXISTING CTDE ALGORITHMS
For multi-agent actor-critic algorithms, we recall Theorem 3.1
Theorem 3.1. For multi-agent actor-critic algorithms, any Nash's 's Equilibrium of policies is a sta- tionary point of actor loss. Moreover, there exists family of single step-MMDP such that the actor loss function contains Q ))) different local minimums for deterministic policy and infinite local minimums for stochastic policy.
Proof. Suppose (TB)) ... (T.)) is an NE, then by the definition of NE, we have Vi = 1,.,,, vO, I ( ,TTO,) 2 [ 50, m T0:11""" wo ;)
By denoting C' as the actor loss function, it's equivalent to Vi 1,..,,,,, n VO, C(01, .0,) s C(O).... 0i-1, 03, 01+1, ".+t,...,,0... ,0-)).
Suppose Ii : 80,
ac f O. Let 1 (0,
0, 0), we have 80,
AC
n-i
lim C( 0n) + ö1) C(O,, ,0n) =1112 + 0 6-20
81/712
Choose a sufficient small will constitute a contradiction of the definition NE. Thus we have ac Vi 88,
O.
After that, by applying the derivation rule of compound function,
ac
OC 00;
0
00
00; 00
we can address the situation where parameter-sharing is taken into consideration, which completes proof of the first part of the theorem.
For the second part of the theorem, we construct 2-agent matrix game here first. The payoff matrix M of the matrix game is
[A|
K
K
K
A
K
M
K
K
where K > is positive constant.
In this case, any entry the diagonal a local minimum. Let p. q the i-th one-hot probability
vector for some i = 1,. .A. The payoff of joint policy (p, q) is J (p, q) = pp Mq. Let's ss disturb the joint policy a little, such that p/: of E (1 - e, - e/2). Then denoting Ap = (p - p'), Aq =
(q q¹), the disturbed payoff is
p'T MT = (p Ap) T M(g Aq) T(p. - < <
for sufficiently small c. This means (p. q) is local minimum. This case is easy to extent to general MMDPs.
13

---

Under review as a conference paper at ICLR 2023
For value-decom dectoposccooooiiioonn algorithms, recall Theorem 3.2 Before prove the theorem, prove a stronger version for special case (QPLEX) first.
Proposition A.I. Assuming the neural network as a universal approximator, for any MMDP with no cycle, there are infinite many local optima of the TD-loss function of QPLEX.
Proof. We first expand the original formula of QPLEX Wang et al. 2021b
a) (soe(s) + a))
Ev. + Σ ((ssa))A((saa)
Σ (wo( (s))(()))++))))))) +b,())) + Σ ((ss,a)A((s,a)
where 8 - R,b 8 R,Q x R are neural networks, Vi()) max Q1 ) a,) =.), V.()).
By assuming the neural network as universal approximator and little abuse of notations, the original formula QPLEX can rewritten as follows:
Q(s, = b(s) + M1s. a)A.ss
where b, A, Q, are parameterized universal approximators, and A,,s, Qi(s, Qi(s,)) is the individual advantage function.
We explicitly specify the parameters used by each approximator here: b(s; (, a: oz), Qi(s, az; 0s). Denoting θ = (01, ,n, $1, Un, vb) as all parameters being used, the TD-loss function is
(TD = - (<
(TQ)(s
for some distribution fully supported on S x A", where T is the Bellman operator.
The distribution D does not matters that much here long as it is fully supported. We now further assume D to a uniform distribution. For D that is not uniform, the proof is essentially similar. We leave it to the reader.
Fix any non-degenerated 01.-..,0 Oz. which means Vi, 8, the greedy action of Qi(s,)) :) unique. Then sufficiently small neighborhood of θ won't change the greedy joint action due the con- tinuity of the function Therefore, we can fix as(s) = arg max ((s, for each state s (a (s) is abbreviated a' when there is ambiguity).
Denote ((8, a) (sQ a) as the current target in TD-loss.
We first consider the case when the MMDP is one-step game (i.e. y 0). Then T is constant tensor independent to current Q in this case. The TD-learning becomes a supervised learning task.
We try to optimize the TD-loss by minimizing [a(Q(s, a; () T(s, a))² for each
Then for any state s, denote = {a + a" T(s,, a) < T(s, (a T(s, a) > T(s,, a )u
{a"). We have
(0 -
10 a;) - T(s, + E a: 0) a()
aeL
aEG
Note that the continuity is naturally assumed, since need take the gradient of the loss function w.r.t.
14

---

Under review as a conference paper at ICLR 2023
Keeping ... 8n fixed, find v 01.-.. On such that
b(s; - G Σ max max
- T(s,a")
Vi: M(s, a: 6z) min(T(s,n)) a(s,a"),0) Σ A(
Plug these formula into the definition of mixing network, have
Va E L ([ a; T(s, a)
va G Q(
Σ a(s,a')
G
a'EG
It's easy to verify that
Σ aEL
T(s,
and
Σ aEG
min Σ 10 as),))
aEG
These further show that
min (TD(O)= QERISIXIAI Was" (s) ((a,)
which means θ is global minimum conditioning on that the greedy joint policy stays unchanged. Recall that there is a small neighborhood of such that the greedy joint policy stays unchanged, this finishes the proof of local optimality of θ in LTD-
This argument can be easily extended to acyclic MMDPs. We just need to calculate & by the reversal of topological order, then all formula above will be well-defined.
Now we are able to prove Theorem 3.2
Theorem 3.2. There exists a family of MMDP, such that for any value-decomppoition algorithm with a complete Q-function class satisfying the IGM condition (Eq. 3 the TD-loss function contains Ω (IA) (S1) different local optima.
Proof. Recall Fq. (2) the mixing network of any value-decoomosittinn algorithm on MMDP is in the following form
Q(s, a: θ) = (mi (.:
it's essential to to find series of ( such that (1) (() is globally optimal (w.r.t the TD-loss function) conditioning on that the greedy joint policy unchanged; (2) the greedy joint policy is unchanged in small neighborhood of (k))
Following the proof of Proposition A.1
Now we construct the MMDP as follows: a.
let
0: b. let r(s,a) =
i, 02 _... On = for all s E S. Since y = 0. the transition probability does not
otherwise
really matter.
15

---

Under review as a conference paper at ICLR 2023
TT m2 state. Note that [11| |A[|S]. (2), then we finish our proof.
Let II { 8 A
nn be the set of policies with non-zero value on each If we can show that there is ( for cach II satisfying (1) and
Fix any π E II, we construct ((.) as follows.
l1+|Al
a = T(s) m
2
First, let (m,
01 02
> T(8) for E N. an < T())1
a1
a = 02
0,
otherwise
By the completeness of Q-function class, we are able to find some m such that Q(s Qm) = as) By the uniqueness of greedy policy of fms we have Va, A (I(3.T(ss) 4 Qi(s, ag; )m.) for = I,...,." ,
By Bolzano Weierstrass Theorem we can find convergent subsequence {0m, 1im Take
the limit, we have mm + (m), By the continuity we have a(s,a; =
*(s)+|A] an
On 2 (()s1 On < (()1 and Va, A (s(s) 2
a1 0,
aj = 02 = otherwise
Qi(s, ag ((7) for i 1,... n.
(1) is obvious in this case. We can prove it by following the argument in the proof in Proposition A.
To prove (2), we need to prove the strict inequivalence in Va, E A ((); >
Qi(s, az; (.))). We prove it by contradiction.
Suppose that there are some 8, i, and as, such that Qi(s, (s); 0(x)) = Qi(s, as; (Z))). Then we have Q(s,, (s)1,.... .i.-.. ,T(s)as (()) max ((() x(e)+|A) by the IGM assump- tion, which contradicts to Q(s,, n (T) ... "r. "
=
Experimental Results for QPLEX has used some engineering tricks like "stop gradient" to modify the gradient of non-optimal points helping the algorithm to jump out of some local optimums. But these tricks are lack of theoretical guarantee, we can still construct cases that QPLEX is not able to reach global optimum, such as the following Matrix Game (Table3.
empirical design of the algorithm, we notice that QPLEX
-20
10
Table 3: Matrix Game 2, m
This Matrix Game has two global optimums (0, 1) and (1, and suboptimal solution (1, 1) with high reward. QPLEX will likely to initialize to the suboptimal solution (1, 1). and after that, it get confused since the manually modified gradient doesn't 't tell it the right direction. The learnt joint Q vibrates around the following matrix:
20
29/3 é
29/3 )
29/3
which can be proved to be local optimum of LTD according to the proof of Proposition A.
FBW Theorem claims that any bounded sequence in H has a convergent subsequence. It's sufficient to assume the boundedness for the purpose of understanding the main idea of the proof. For the unbounded cases, this theorem be extended a little bit to deal with unbounded sequence by detining the convergence extended convergence. This is standard technique in mathematical analysis, we omit it here
of x,/ /ral for conciseness.
Note that the continuity is naturally assumed, since need take the gradient of the loss function w.r.t.
16

---

Under review as a conference paper at ICLR 2023
QTRAN LTD in QTRAN is discontinuous, for everywhere the police switches may constitute a jump discontinuity, which may be harmful for gradient descent methods, since gradient descent methods assume the loss function to be differentiable. Unfortunately, theoretical analysis about QTRAN, either prove or disprove its optimality. We have only empirical results shown in Section to prove its potential suboptimality.
not able to give any
A.2 SEQUENTIAL TRANSFORMATION
We present the formal definition of sequential transformation here for completeness. Definition A.I (Sequential Transformation T). Given an MMDP M = (S,A, Prr,7: 80, N), its sequential transformation an MDP I (M) = P,
where S - A
is the state space, A is the same action space as the original MMDP M, P is the trans- formed transition fimction, where vk < N, = (s, 01 P((s, (ax)a (.))) = 1, and V3 (s, (5, aN-1) ) E S, E VuN A. we have P(s'[5,aN) = P(slls, (a1.... (a))), F is the transformed reward function, where vk < N. ( (8,01,''
.k-11 E S, Sax E A. we have
S, Vax A. we have 7(8, ax) O. and vs (s,a1,-.. .a-1) S, VaN / is transformed discount factor, and so is
A, have F(3,aN) r(s, (a1, (aa.))
the initial state.
A.2.1 PSEUDOCODE
FRAMEWORK WITH SEQUENTIAL TRANSFORMATION
Here we present pseudo-code of the sequential framework (Algorithm
Algorithm 1 The Sequential Framework
1: Input: An SARL algorithm 21, an oracle O- for interaction with an MMDP M.
2: while Simulating A do
3: if 21 asks for the initialization of environment then
4: Initialize = 0, a; 0 for i 1.... .N.
5: Call O for the initialization of M and obtain So
6: Return so to A.
7:
else if A asks for an interaction with the environment by providing an action a then
8:
at mod N+1 f- a if f mod N = N - then
9:
.Nn) Call OM for the interaction by providing action (a1,'.. .aN) to obtain reward r and
next state s'. + s'
11:
12:
Return and s' to 2.
13:
else
14:
Return O and (s, a., at mod N+1) to 2l
15:
end if
16:
6=
17:
else if I returns an policy π then
Convert the joint policy Tī on M.
19:
Break
end if
21:
end while
22:
Return Tjj.
A.2.2 THE EQUIVALENCE BETWEEN M AND AM AS WELL AS THE CONVERSION OF POLICIES
Here we state the theorem of equivalence between M and TM in perspective of policy value.
Theorem A.I. For any deterministic policy I (M), there is decentralized policy ny. (TI.... .T)) on M such that JM(TT) (1-n)/n (I(m))Jrr( where xi(s) T(s), Tx(s)
((ss, mi (8). F (s)))]fl for all k: 1.
17

---

Under review as a conference paper at ICLR 2023
For any stochastic policy y7 I (M), there is communicated policy The (m. MN) M
such that JM(Mj)) (11-n)/n FT(M)(1) (1), where m(ai|s) nya1ls), me(axls,a) a1 .0--1)
m(aulss,a)."" a1, for all k > 1, where a _0-11 actions selected by agents 1,... k-
And conversely, for any policy Ty on M, there is policy IM such that JM((TT)
(T(M)))))..)).
Proof. For deterministic policy:
(m)) = E
( Tp)) 8141 P(oc, mp)
E
7Th (((e, (1t), TT 1 8141 ~ P(st, mz))
8041
E
gutt (ell-nn=(((((s)) (((s ,Ts-1(s))), 81+1 (T))
k=0
F(sr x S4 p)
7 (T)
For stochastic policy the proof is similar,
(m( E
7 (r((8t,
81+1 P(s),
Σ ア"l ( m) gt7e P(ses mi) (h)t, (0) (-(( (-1(s1, (Q))
E
y n-t+k-nt1 ((0) ((., .1)
8141 P(s,, mp) p(st, a(t) ~11 (.1 (1(5,) (-((s)
E
7 F(sus 8841 8841 P(oy.n)
JI(M) (1)
For the converse part of the theorem, suppose Tд (TI.... Tn). it's sufficient to let
T ((ss, "., a(-1))== (s). The calculation of its value is similar to the above, we omit here.
A.3 OPTIMALITY OF TPPO
The proof of Theorem and Proposition 4.1 are directly followed by Theorem A.1 and Theorem
4.9 (Liu et 2019 which omitted here.
A.4 THE COMPLEXITY OF THE TRANSFORMED MODEL
By sequential transform, on the MDP to solve the MMDP. One natural question is, will such framework bring additional hardness of the task?
able convert any MMDP to MDP and run SARL algorithms
18

---

Under review as a conference paper at ICLR 2023
First of all, this framework obviously doesn't ' increase the minimax sample complexity of the task, since the MMDP M and the MDP I (M) can be transformed to each other with merely negligible additional cost in time and space (see A.66n Nevertheless, for concrete algorithm A (e.g. Q-learning), the sample complexity is not necessary to be the same after such transformation.
Let's take Q-learning after the transformation. It easy to see that the size of the state-action space of M ||) and that of its T (M) is oo
example. We first investigate the size of state-action space before and
= | 1-1 A- I 2|S||A| This implies that the sequential transform does not increase the complexity in the state-action space.
|S]|
==
However, if we take closer look here of the sample complexity, will find that the exact sample complexity bound of Q-learning is O |S||A|
((i et al. 2021b), which depends on not only (1-7)4<2
the size of state-action space, but also on the magnitude of 1-7" This implies that the sample complexity may increase for certain algorithms since I' (M) has longer horizon. Despite this unpleasant result, for Q-learning, still, this analysis leave out the structure of I' (MM): for every n steps in I' (M) there are deterministic transitions with reward 0. So fortunately, if we modify the original Q-learning a little bit, it will attain the same sample complexity as before (See Appendix A.5
A.5 AN EXTENSION OF Q-LEARNING
Here we introduce variant of Q-learning dealing with deterministic transitions (Algorithm ( to demonstrate the claim at the end of Appendix [A.4 we adopt this algorithm in our sequential transformation framework, it will have the same sample complexity as the original Q-learnnng on the original MMDP M.
We denote D : S x A - {0, 13 an oracle telling whether this state-action pair would result in deterministic transition.
Algorithm 2 QLDT (Q-learning for MDPs with deterministic transitions)
Access to: An oracle D S x A 10.
Initialize Q for L to T do f- 80 Initialize stack v. for each step of epoch t do
a <- SelectAction(m: 8) (e-greedy)
r + Reward(s, < NextState(s,a)
if D(s, a) then
Push (s, a, (,rr,' into v (deterministic transition]
Q(3, ā) t - max((3',))
else
(ss, a) as, afr + max Q(6(.)) a(),a))
while e is not empty do
Pop to get (8, á, 8')
(3, â) t + max (33,))
end while
end if s <- s'
end for end for
We have Proposition A.2
Proposition A.2. T-QLDT has the same sample complexity original Q-learning M.
Proof. One can view T-QLDT as the original Q-learning maintaining a max heap. where Q((s,a1,"*. a (k-1),as ax) max Q((s, (((s,,1,".. .ak)))) In this way, T-QLDT has exactly the
19

---

Under review as a conference paper at ICLR 2023
same behaviour the original Q-learning and does not change the sample complexity sequence.
A.6 THE MINIMAX SAMPLE COMPLEXITY OF THE SEQUENTIAL FRAMEWORK
Here we explain a bit more the claim of the minimax sample complexity in Appendix A.4
The minimax sample complexity here is the sample complexity of the "best" algorithm the "hardest" task. For any multi-agent algorithm A, we can always find a single-agent algorithm B, such that A = T-B. It is because that for any MDP M we can always compress n steps on M into one step, and then use corresponding multi-agent algorithm to solve as a multi-agent problem. In this way, T-B is exactly A, and thus not increase the minimax sample complexity. One should keep in mind that every n samples on MDP correspond to exactly one sample on MMDP. Particularly, the number of bits need to record every samples MDP are exactly what need to record one sample on MMDP.
B EXPERIMENTAL DETAILS
In this section, we provide more experimental results supplementary to those presented in Section 5 We also discuss details of the experimental settings of both our matrix game and the StarCraft II micromanagement (SMAC) benchmark.
B. MULTI-TASK MATRIX GAME
In section 3 design a multi-task matrix game to demonstrate the global optimality of sequen- tial transformation framework. In this section, we will first show the details of this environment and provide more evidence of our algorithms' advantage MMDP.
B.1.1 DETAILS OF MULTI-TASK MATRIX GAME
In multi-task matrix game, the return of the optimal strategy corresponding to each matrix is 10, which means the sum rewards of the global optimal strategy is 100. Two agents are initialized to one matrix uniformly at random, and the ID of a current matrix observable both them. They need to cooperate to select the entry with the maximum reward for the current matrix, after that, the game ends. Each matrix contains agent.
=
25 entries, which means A {0, 2, 3, 4) for each
All payoff matrices are listed Table 4 The optimal strategies' payoff all matrices is Matrices 1 5 are hand-crafted in order to create some hard NEs. Matrices 6 10 are drawn uniformly at random. It's i's worth noting that a random 5 5 matrix has 25/9 = 2.77 different NEs in expectation. And in opinion, the existence of suboptimal NEs is the main reason why existing algorithms fail.
B.1.2 VISUALIZATION OF LEARNED JOINT STRATEGIES
Table 5: Payoff matrix
Table 6: Toat of TPPO
Table 7: Teot of MAPPO
401
(22)
(()
(())
(2)
A
A (1))
A
(
02
(1)
8
-12
-12
(0)
1
0
. (1)
0
0
0
A12)
-12
0
A
0
(2)
0.2
0.2
A33
-12
A 13
0
0
39
0.3
0.3
To further illustrate our approach's ' ability to attach the global optimal point, we use the matrix game in (Wang et al.] 2021b; Ib; Ma et al. (222)) as a toy example (shown in Table [5.. Here we compare our approach T-PPO with MAPPO. Joint policies learned by T-PPO and MAPPO
shown in Table 6 and Table 7 MAPPO falls into local optimal points due to Theorem [3. while T-PPO obtains the optimal strategy. Taking this advantage, approach dominates in multi-task matrix game.
20

---

Under review as a conference paper at ICLR 2023
Table 4: Multi-task Matrix Game
Matrix
Matrix 2
A01
A(2)
A
A(4)
A
A01
A
A
A(4)
A
02
a2
A0
10
-10
10
10
-10
A01
10
-10
10
-10
10
A22)
-10
A A(2
-10
10
-10
10
-10
A(
-10
A A
10
-10
10
-10
10
A44
-10
0
A4)
-10
10
-10
10
-10
A (
-10
0
0
9
A (5)
10
-10
10
-10
10
Matrix 3
Matrix 4
01
A(1)
A(2)
A
A
(
01
A(1)
A(2)
A
A
A
02
02
A1)
-20
-20
-20
-20
10
A
-20
-20
-20
-20
10
22
-20
-20
-20
10
-20
-20
-20
10
(3)
-20
-20
10
A 18
-20
-20
10
14
-20
10
A
-20
10
A 10)
10
A A0)
10
Matrix 5
Matrix
a1
A(1)
A(2)
A(3)
A(1)
A(5)
a1
A(1)
A(2)
A(3)
A(1)
A
a2
a2
A
-20
-15
-10
-5
6
A
0.8
-16.0
-5.0
-10,9
-3.7
(22)
-20
-15
-10
7
5
A (2)
-9.2
-4.2
7.3
9.6
-3.0
A(3)
-20
-15
8
6
4
A (3)
-00.0
- -18.1
0.2
-4.3
9.0
(())
-20
9
7
5
3
A
11.9
-2.0
-17.7
-17.6
-0.8
10
8
6
4
2
A (
3.8
10
7.5
9.2
10.7
Matrix 7
Matrix 8
A(1)
2(2)
A(3)
((4)
5
A()
A
A(3)
A(4)
A
02
02
A0
-1.44
-15,8
1.5
-5,4
10
A
-1.4
-9.2
7.2
-5.5
7.4
A22)
-13.2
5.8
-8.7
-2,2
18.2
A
-18.5
20.0
14.4
11.6
-5.1
A3)
-5.9
-1900
-0.7
-2.0
-1955
A A3)
3.6
5.5
10
-13.3
-4,9
(4)
0.8
4.7
-14.8
2.5
-4.1
A
9.8
-12.3
0.6
-16.5
-13.0
A (5)
-11.3
-8.2
20.00
-17.3
-17.6
A
-11.8
-20.0
-2.4
7.1
-2.3
Matrix 9
Matrix 10
81
A(1)
A(2)
A(3)
(44)
(55
01
A11
A
A
A(4)
A
a2
02
(1)
-.5
-52
-8.4
-8.9
5.5
A
-8.4
-1.8
-0..0
7.3
-3.0
12)
12244
-9.5
8.8
5,4
4.4
A12)
-8.7
1.7
4.8
2.0
-7.8
A13)
-4.6
1.3
5.5
7.3
-6.8
A03)
-13.3
-3.2
0.7
-1.8
-00.7
14)
9.0
-1.77
18.2
-13.7
-8.2
A
9.8
-2.3
0.6
-6.5
13.0
10)
2.2
99.1
7.1
-20.0
A 10)
1.8
2.9
-1.1
10
8.2
B.2
STARCRAFT MICROMANAGEMENT (SMAC) TASKS
B.2.1
BENCHMARKING ON STARCRAFT II MICROMANAGEMENT TASKS
In section 5.1 have compared and discussed the advantage of our approach against baselines several representative maps. Here we further compare our reproach against baselines on all maps. The SMAC benchmark contains 14 maps that have been classified as easy, hard, and super hard. In
21

---

Under review as a conference paper at ICLR 2023
this paper, we design more map 3h vs ms_1bb whose difficulty is comparable with official super hard maps.
T-PPO (ours)
T-PPO-Distillaton (ours)
MAPPO
HAPPO
MMM2
3s5z vs 3s6z
6h vs 8z
90
90
Win %
60-
60
60
30
30
30
4
10
0
10
2
10
T (mil)
T (mil)
T (mil)
corridor
27m vs 30m
3h vs 1b123h
90
90
90
Test Win
60
60
60
30
30-
30
0
4
8
10
0
3
T
(mil)
(mil)
T (mil)
Figure 7: Comparisons between Our approach and policy-based baselines all superhard maps.
T.PPO (ours)
T.PPO-Dittllaton (ours)
MAPPO
vs 642g
36 5z
90
60
60
30-
30
2
4
T (mil)
[ml]
5m vs 6m
bane va bane
90
90-
60
30
2
0.0
0.4
0.8
0.8
T (mil)
(mll)
Figure Comparisons between Our approach and policy-based baselines on all hard maps.
we compare the performance of our approach with baseline algorithms on all super hard maps. We can see that T-PPO outperforms all the baselines, especially on 1155__s_33$$3 MMM2, and 3h s__vs__r rs__biz3h. These results demonstrate that T-PPO can handle challenging tasks more efficiently with theoretical guarantees of its sequential transformation framework. in line with our expectations of it. Meanwhile, our distilled policy T-PPO-Distillaati performs similarly to T-PPO, illustrating the competitiveness of our approach to fully decentralized evaluation. HAPPO performs poorly on 4 out of 6 super hard maps, demonstrating its limitation complex tasks.
In Figure. 7
Our approach maintains its out-performance on most hard and easy maps. Compared with MAPPO, our approach achieves better convergence points on 3s_ 3s_vs_5 5z and 1c3s5z, which confirms the experiment results and analysis in Section ??. In summary, T-PPO establishes a new state of the art SMAC benchmark by outperforming all policy-bascr baselines in 11 out of 15 scenarios. Meanwhile, the distilled strategy of T-PO performs as well as the original strategy, which maintains fairer comparison with baselines on fully decentralized execution.
22

---

Under review as a conference paper at ICLR 2023
T-PPO (ours)
T-PPO-Distilation (ours)
MAPPO
HАPPO
1c3s52
2s 1sc
10m vs 11m
90
90
90
Test Win %
60-
60
80
30-
30
30
0
2
6
2
T (mil)
(mil)
(mil)
2s3z
3s5z
90
Test Win
60
30
2
T (mll)
(mil)
Figure 9: Comparisons between Our approach and policy-based baselines on all easy maps.
B.2.2 HYPER-PARAMETERS
Our code is implemented based on MAPPO (https:/githu...oo//maa hwt.///eeeeennccanooooooooooooo share the same structure with MAPPO except improvement we mentioned in Section ?? to instanti- ate our transformation framework. Meanwhile, we share the same hyper--arameters with MAPPO Yu et al. 2021) only except: (1) We fine-tune the weight of entropy on three maps (0.03 on 3h vs 1bizSh, 6h vs 8z, and 5m 6m) for both approach and MAPPO. (2) The hyper- parameters of multi-head attention (MHA) modules. As for HAPPO, we use the officially released code and related hyper-parameters
We
Table 8: Common hyper parameters for our approach in the SMAC domain.
common hyperparameters
value
MHA heads
3
MHA latent dimension
4
MHA norm weight
0.001
entropy weight
0.01
B.2.3 DISTILLATION
The distillation is just independent behavioral cloning for each agent.
Denote the joint policy (Tp(-s)) and the decentralized policy for agent i as Tieen (=senn-|s;0) The independent behavioral cloning is equivalent to minimization of the KL divergence between the joint policy Tz (-1s) and the joint decentralized policy I[ Tooeon (-ls; (-1s;)).
KL Tzl Ta(-
II T (-1s;
Tt (a(ss)
Tin (als) log
Ti= Teecenn (as 18;
(a1 )nn)
B avm)(11))
log T (as1s5
H (TTT(e-1s)
entrupy (a constant)
behavioural cloning
23

---

Under review as a conference paper at ICLR 2023
B.3 GOOGLE RESEARCH FOOTBALL (GRF) TASKS
Because there are fewer agents in GRF compared with SMAC (3 in Academy_ 3_vs_____________________ 1__1___ wwwthhhh__.. Keeper and 4 in Academy Counterattack Hard, we slightly de- crease the number of MHA heads from to 2 as shown Table Other hyper- hyper-parameters remains the same as SMAC.
Table 9: Common hyper-paramette for our approach in the GRF domain.
common hyperparameters
value
MHA heads
MHA latent dimension
MHA norm weight
0.001
entropy weight
0.01
B.4 RUNNING TIME T-PPO
The sequential update does take longer time than the concurrent update the training phase, while in the testing phase, our algorithm doesn't 't take extra time since decentralized policy is already calculated by distillation.
Specifically, in the training phase, our framework takes times the time to do action inference, where n is the number of agents. However, it's worth mentioning that, the time action inference only part of the time doing whole training iteration, which also includes environment simu- lation and policy training. On the whole, the training time cost of our framework is 0.91 times more than MAPPO in SMAC environment 3m (3 agents), and 1.76 times more in SMAC environ- ment 10m vs 11m (10 agents). This result embodies trade-off between training time and training performance.
Specific time of each part is shown Table 10
Table 10: Comparison between TPPO and MAPPO training time
Env:
Action
Env
Env interaction:
Policy
The whole training phase:
3m (1M)
inference: 1y
simulation: is
L + is
Training: 1y-
f, + is tr
T-PPO
1694.6s
915.4s
2610s
233.75 7s
2843.7s
MAPPO
434.9s
904.5s
1339.4s 4s
151.9s
1491.3.
Ratio
3.9
1.01
1.95
1.54
1.91
Env:
Action inference: 1y
Env simulation: ts
Env interaction:
Policy
The whole training phase:
10m vs (LM)
6 + ts
Training: 1p
1, + ts tr
T-PPO
5011.7s
2065.5s
7077.2s
794.1s
7871.18
MAPPO
501.
2063.2s
2564.38
292.
2856.48
Ratio
10.0
1.0
2.76
2.72
2.76
B.5 COMPARISON BETWEEN T-PPO AND OTHER ACTOR-CRITIC BASELINES
We also compare T-PPO with two actor-critic methods DOP and FOP three superhard SMAC maps for completeness. The result is shown Figure I0
B.6 T-DQN RESULTS
We also implement the off-cy method T-DQN based on the single agent algorithm DQN (Miih et al.) 2013) for completeness. In Figure II We evaluate DQN a Markov Game (Matrix games with random transition), hard and a superhard SMAC maps to show that our framework is also compatible with off-policy methods.
24

---

Under review as a conference paper at ICLR 2023
(ours)
T-PPO-Distllation (ours)
MAPPO
FOP
corridor
90
Win
60
60
30
30
0-
10
(mil)
T (mil)
(mil)
Figure 10: Comparisons between T-PPO and other on-policy baselines on three superhard maps.
T-DON (ours)
QPLEX QMIX
VDN QTRAN
IQL
T-DQN- DDDN-DDisillation (ours)
Markov Game
2c_ys, 2c_vs_64zg
3h 1b123h
90
Test Win %
80
Return
30
30
60
0.0
1.0
1.5
2.5
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
1.5
2.0
(mil)
T
(mll)
(mil)
Figure 11: Comparisons between T-DQN and off-policy baselines on Markov Game, a hard and superhard SMAC maps.
B.7 LEARNED BEHAVIOUR OF THE SEQUENTIAL FRAMEWORK
We visualize the policy learned by our approach and compare with MAPPO MMM2. Based on the comparison, we notice an interesting phenomenon. The joint strategy trained by MAPPO usually conservative, only moving in a small area, and only two agents are left in the end. On the contrary, the joint strategy trained by our approach is more aggressive. Our agents pull back and forth frequently based on opponents' movement in a large-scale range while ensuring effective fire focus. We think this phenomenon is caused by sequential transformation framework, which enables each agent to fully understand the team strategy for more efficient coordination.
25


Reviews:
[{"review_id": "yFLNV7xtL5L", "reviewer": "Reviewer_fgdt", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "This paper studies centralized training with decentralized execution (CTDE) in cooperative multi-agent reinforcement learning (MARL). It first analyzes disadvantages of previous algorithms from an optimization perspective. Then, it proposes a framework that reduces a cooperative MARL problem to a single-agent RL problem and a corresponding algorithm called transformed PPO (T-PPO). This paper also presents experiment results on simple matrix games, Starcraft II and Google Research Football and show superior performance of the proposed T-PPO algorithm.", "summary_of_the_review": "This paper proposes a novel reduction from cooperative MARL problem to SARL problem and the correspondinng experiment results look promising. However, its current theoretical support is not solid enough and its writing also needs some improvement.", "strength_and_weaknesses": "### Strengths\nThe reduction from cooperative MARL problem to SARL problem is considered to be novel. Meanwhile, the experiment results also look promising.\n\n### Weaknesses\nOne of the major weakenesses of this paper lies in its theoretical support. In particular, although the problem of multi-agent games may contain many local minimums, it is not clear how this problem is resolved in the transformed MDP. Since the problem is in general non-convex, many local minimums may still exist in the transformed MDP. It will be better if it can provide an analysis that the proposed framework does resolve the problem of many local minimums even in some toy examples.\n\nMeanwhile, the proofs provided in Appendix seem to miss a lot of details, together with some hand-waving parts. For example, in the proof of Proposition A.1:\n- It will be better to state clear how the formulas from QPLEX are simplified.\n- In the first equation, $\\theta_1, \\dots, \\theta_n$ does not appear in the right-hand side.\n- The loss function $C$ is not clearly defined.\n- It is not clear what \"the best we can expect\" means.\n- The proposition claims to find some $\\phi$ such that $(\\theta_1, \\dots, \\theta_n, \\phi)$ is a local minimum of $C$, but the proof does not make clear how exactly $\\phi$ looks like.\n- It will also be better to add the omiited details of Theorem 3.2 back.\n\nThese hand-waving arguments and missing details make the theoretical claims in this paper less convincing.", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "l0fjAvQzzy", "reviewer": "Reviewer_SxZS", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "The authors propose a revision of the existing approach to Centralised Training Decentralised Executation (CTDE)  for the Cooperative AI problems. They propose a transformation from the MMDP to a MDP problem, thus allowing them to use Single Agent RL algorithms. This is motivated by observations (with theoretical justification) that current CTDE approaches with gradient based learners introduce a large set of local equilibria which restrict the ability to converge to optimal behaviour.\n\nThe authors then implement a simple of this transform (which amounts to transforming agents from taking simultaneous moves into sequential moves and using a single agent instead of a team). Implementation details are provided such as using Multi-Head Attention, KL Divergence and Distillation (although not all components are ablated). \n\nPerformance is measured on saturated benchmarks (SMAC) and so performance can only been seen to be a marginal improvement.\n", "summary_of_the_review": "Paper exposes a theoretical problem with CTDE which is a good contribution. \n\nThe solution proposes lacks motivation or compelling results to be taken seriously.", "strength_and_weaknesses": "### Strengths\n\nStrong theoretical work to show existing models are more susceptible to falling into local optima than the proposed method. \n\n### Weaknesses\n\n* Unclear why they only evaluate on 6 of the SMAC environments, there are many more. \n* They have not used any SMAC maps with > 10 agents\n* Do they provide other agents’ actions at test time (as suggested by Figure 2)? If so this makes this an entirely unfair comparison to CTDE.\n* I would like to understand the importance of the ordering of agents within the “virtual” episode.\n* I would like ablations to understand the importance of the MHA and KLD terms.\n* The MAPPO results are much lower than reported in the original paper - can you explain the performance difference\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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "M3xmyh3Dyym", "reviewer": "Reviewer_toNr", "summary": "", "questions": "", "limitations": "", "rating": 1, "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 mainly considers the transformation from centralized training with decentralized execution (CTDE) in multi-agent reinforcement learning (MARL) to single-agent reinforcement learning (SARL). Specifically, the authors reformulate a multi-agent MDP as a special \"single-agent\" MDP with a sequential decision-making structure among agents. In this way, SARL algorithms can be used during training, and a distilled policy is used during execution. Experiments show a good performance in a few scenarios in SMAC and GRF. ", "summary_of_the_review": "I think the authors should improve this paper with much effort. The current version is not satisfying in terms of both presentation and the core idea.", "strength_and_weaknesses": "Pros:\n\n- This paper takes on an interesting problem in MARL: the improvement of the CTDE scheme outside value decomposition and centralized critic.\n- The experiments are completed.\n\nHowever, I have several concerns here:\n- The paper is not well-written and not well-organized with many typos and confusing notation. It seems a hastily written paper.\n- The description of Theorem 3.1 is wrong, single step MDP is not MMDP. The proof of Theorem 3.1 is confusing. The example game is a pure coordination game, which has |A| pure strategy equilibria. However, it is the nature of the pure coordination game, which does not mean that multi-agent actor-critic algorithms create inherent local minimums.\n- The reason why the proposed method works in “Multi-task Matrix Games” as shown in Fig.1 is the agents are factually communicating to avoid miscoordination in such one-shot games You can check examples 3.2 and 3.3 in [1].\n- The order of actions matters.\n- If agent $i$ can know all previous agents’ actions, this case is a weak version of MARL communication or agent modeling. \n- The distillation is missing in the main part of this paper.\n\nMinor:\n\n- Reference in line 3 of page 3: missing parentheses\n- see eq. (1)/appendix/section/theorem/proposition/definition -> see Eq.1/Appendix/Section/Theorem/Proposition/Definition\n- $\\Gamma M$ in the last line of page 5: missing parentheses\n- Proposition 4.1 (suitable …) -> Proposition 4.1 (Suitable …)\n- In Prop. 4.1, “if Assumption 4.1, 4.2, 4.3 in Liu et al. (2019) holds” -> “if Assumption 4.1, 4.2, and 4.3 in Liu et al. (2019) hold”\n- So many typos, grammar mistakes, and irregular notations!!!\n\n\n[1] When Does Evolution Lead to Efficiency in Communication Games. 1994.\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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject