Boosting Multiagent Reinforcement Learning via Permutation Invariant and Permutation Equivariant Networks
Authors: Jianye HAO
Xiaotian Hao
Hangyu Mao
Weixun Wang
Yaodong Yang
Dong Li
YAN ZHENG
Zhen Wang
Venue: ICLR 2023 poster (2023)
Keywords: Multiagent Reinforcement Learning
Permutation Invariance
Permutation Equivariance

Abstract: The state space in Multiagent Reinforcement Learning (MARL) grows exponentially with the agent number. Such a curse of dimensionality results in poor scalability and low sample efficiency, inhibiting MARL for decades. To break this curse, we propose a unified agent permutation framework that exploits the permutation invariance (PI) and permutation equivariance (PE) inductive biases to reduce the multiagent state space. Our insight is that permuting the order of entities in the factored multiagent state space does not change the information. Specifically, we propose two novel implementations: a Dynamic Permutation Network (DPN) and a Hyper Policy Network (HPN). The core idea is to build separate entity-wise PI input and PE output network modules to connect the entity-factored state space and action space in an end-to-end way. DPN achieves such connections by two separate module selection networks, which consistently assign the same input module to the same input entity (guarantee PI) and assign the same output module to the same entity-related output (guarantee PE). To enhance the representation capability, HPN replaces the module selection networks of DPN with hypernetworks to directly generate the corresponding module weights. Extensive experiments in SMAC, Google Research Football and MPE validate that the proposed methods significantly boost the performance and the learning efficiency of existing MARL algorithms. Remarkably, in SMAC, we achieve 100% win rates in almost all hard and super-hard scenarios (never achieved before).

Published as a conference paper at ICLR 2023
BOOSTING MULTIAGENT REINFORCEMENT LEARN- ING VIA PERMUTATION INVARIANT AND PERMUTA- TION EQUIVARIANT NETWORKS
Jianye Hao! Xiaotian Hao', Hangyu Mao", Weixun Wang', Yaodong Yang', Dong L.P, Yan Zheng', Zhen Wang'
Coolleee of Intelligence and Computing, Tianjin University, ?Noah's Ark Lab, Huawei 'hh Chinese University of Hong Kong, "Northwestem Polytechnical University
ABSTRACT
The state space in Multiagent Reinforcement Learning (MARL) grows exponen- tially with the agent number. Such curse of dimensionality results in poor scal- ability and low sample efficiency. inhibiting MARL for decades. To break this curse, we propose unified agent permutation framework that exploits the permu- tation invariance (PI) and permutation equivariance (PE) inductive biases to re- duce the multiagent state space. Our insight is that permuting the order of entities in the factored multiagent state space does not change the information. Specifi- cally, we propose two novel implementations: Dynamic Permutation Network (DPN) and Hyper Policy Network (HPN). The core idea to build separate entity-wise PI input and PÉ output network modules to connect the entity-factored state space and action space in end-to-end way. DPN achieves such connections by two separate module selection networks, which consistently assign the same input module the same input entity (guarantee PI) and assign the same output module to the same entity-related output (guarantee PE). To enhance the repre- sentation capability, HPN replaces the module selection networks of DPN with hypernetworks to directly generate the corresponding module weights. Extensive experiments in SMAC, SMACv2, Google Research Football, and MPE validate that the proposed methods significantly boost the performance and the learning ef- ficiency of existing MARL algorithms. Remarkably, in SMAC, we achieve 100 % win rates in almost all hard and super-hard scenarios (never achieved before).
INTRODUCTION
Multiagent Reinforcement Learning (MARL) has successfully addressed many real-world problems (Vinyals et al., 2019; Berner et al., 2019; Hüttennaacch et al., 2017). However, MARL algorithms still suffer from poor sample-effiiencyy and poor scalability due to the curse of dimensionality. i.e., the joint state-action space grows exponentially as the agent number increases (Li et al., 2022). A way to solve this problem is to properly reduce the size of the state-action space (van der Pol et al., 2021; Li et al., 2021). In this paper, we study how to utilize the permutation invariance (PI) and permutation equivariance (PE)' inductive biases to reduce the state space in MARL.
Let G be the set of all permutation m of size m m and g be specific permutation matrix of G. function f X + Y where X = [æ1..... ... Øm]] is PI if permutation of the input com- ponents does not change the function output, i.e., f(g [ _mmll = f[ and Y [y) .y. ym]] is PE if
Vg E G.
In contrast, function f X Y where X {x) ... xm ..m permutation of the input components also permutes the outputs with the same permutation g. i.e.,
f( [ _mni1 ) denote them as permutation sensiiittiinnsssiiiieeeieee functions.
9 .......00 yml" Vg G. For functions that are not PI or PE, we uniformly
1 For brevity, we use PI/PE as abbreviation of permutation invariance/permutttion equivariance (nouns) or www.:rnniiniiiimmmtatttittoooooo
(adjectives) depending on the context. A permutation matrix has exactly single unit value in every row and column and everywhere else.

---

Published as a conference paper at ICLR 2023
A multiagent environment typically consists of individual entities, including learning agents and m n non-player objects. The observation og of each agent is usually composed of the features of the entities, i.e. [mm]. where zq E ' represents each entity's ' features and X the feature space. If simply representing o as a concatenation of [ar,.... Tm]] in fixed order, the observation space will be [X|=". A prior knowledge is that although there are m!! different orders of these entities, they inherently have the same information. Thus building functions that are insensitive to the entities' orders can significantly reduce the observation space by factor of 1 To this end, in ml-
this paper, we exploit both PI and PE functions to design more sample efficient MARL algorithms.
Take the individual Q-network of the StarCraft Multia- gent Challenge (SMAC) benchmark (Samvelyan et al., 2019) Q;(a; as an example. As shown in Fig. the input o; consists of two groups of entities: ally
agent
ally
enemy
enemy
enemy 3
input
group ofl and an enemy group o, o.memyy The outputs consist of two groups as well, i.c., Q-values for move actions Amtae and Q-values for attack actions A Given the same o, arranged in different orders, the Q- values of Amave should be kept the same, thus use PI architectures to make (AATooo))) learn more efficiently. For (A4tttick), since there exists one- to-one correspondence between each enemy's features in of meemy and each attack action in Abttackk, permuta- tions of of caemy should result in the same permutations Figure 1: A motivation example in SMAC.
Individual Network: Qe(arlo))
output action Q-values
attack
attack enemy
attack
Aquroee
Attlack
Permutation Invarient
Permutation Equiverient
of A so we can use PE architectures make Q:(Aqtuuck)o lo:) learn more efficiently.
To achieve PI, there are two types of previous methods. The first employs the idea of data augmen- tation, e.g., Yc et al. (2020) propose data augmented MADDPG, which generates more training data by shuffling the order of the input components and forcedly maps these generated data to the same output through training. But it is inefficient to train same value when taking features in different orders as inputs. The second type applics naturally PI architectures, such Deep Sets (Li et al., 2021) and GNNs (Wang et al., 2020b; Liu et al., 2020), to MARL. These models use shared input embedding layers and entity-wise pooling layers to achieve PI. However, using shared embedding layers limits the model's representational capacity and may result poor performance (Wagstaff al., 2019). For PE, to the best of our knowledge, it has drawn relatively less attention in MARL community and few works exploit this property.
iennuutattoo-sesstivv function to output the
In general, the architecture of agent's policy network can be considered as three parts: an input layer, @ a backbone network (main architecture) and @ an output layer. To achieve Pf and PE, follow the minimal modification principle and propose light-yet-efficient agent permutation framework, where we only modify the input and output layers while keeping backbone unchanged. Thus our method can be more easily plugged into existing MARL methods. The core idea is that, instead of using shared embedding layers, we build non-shared entity-wise PI input and PE output network modules to connect the entity-factored state space and action space in end-to-end way.
Specifically, we propose two novel implementations: a Dynamic Permutation Network (DPN) and Hyper Policy Network (HPN). To achieve PI, DPN builds separate module selection network, which consistently selects the same input module for the same input entity no matter where the en- tity is arranged and then merges all input modules' outputs by sum pooling, Similarly, to achieve PE, it builds a second module selection network, which always assigns the same output module to the same entity-related output. However, one restriction of DPN is that the number of network modules is limited. As result, the module assigned to each entity may not be the best fit. To relax the restriction and enhance the representational capability, we further propose HPN which replaces the module selection networks of DPN with hypernetworks and directly generates the network pa- rameters of the corresponding modules (by taking each entity's 's own features as input). Entities with different features processed by modules with -ptity-specifie parameters. Therefore, the model's s representational capability is improved while ensuring the PI and PE properties.
Extensive evaluations in SMAC, SMACV2, Google Research Football and MPE validate that DPN and HPN can be easily integrated into many existing MARL algorithms (both value-based and policy-based) and significantly boost their learning efficiency and converged performance. Re- markably, we achieve 100% win-rates in almost all hard and super-hard scenarios of SMAC,
2

---

Published as a conference paper at ICLR 2023
which has never been achieved before to the best of our knowledge. The code is available at http://gghhb.oommmllllaaaaaaaaaa
2 RELATED WORK
To highlight our method, we briefly summarize the related works that consider the PI or PE property.
Concatenation. Typical MARL algorithms, e.g., QMIX (Rashid et al., 2018) and MADDPG (Lowe et al., 2017) simply represent the set input as a concatenation of the entities' features in fixed order and feed the concatenated features into permutation--eesitivee functions, e.g., multilayer per- ceptron (MLP). As each entity's 's feature space size is 1 the size of the joint feature space after concatenating will grow exponentially to | thus these methods suffer sample inefficiency.
Data Augmentation. To reduce the number of environmental interactions, Ye et al. (2020) propose data augmented MADDPG which generates more training data by shuffling the order of [.1,... Tm and additionally updates the model based on the generated data. However, the method requires more computational resources and is more time-consuming. Besides, same information as the original one, they should have the same Q-value. But it is inefficient to train permutaaionn-senstivee function to output the same value when taking differently-orderee inputs.
the generated data contains the
Deep Set & Graph Neural Network. Instead of doing data augmentation, Deep Set (Zaheer et al., 2017) constructs a family of Pl neural architectures for learning set representations, Each component ar; is mapped separately to some latent space using a shared embedding layer ((x;). These latent representations are then merged by PI pooling layer (e.g. sum, mean) to ensure the PI of the whole function, e.g. [(X) = p 1 (x;)), where p can be any function. Graph Neural Networks (GNNs) (Veličković et al., 2018: Battaglia et al., 2018) also adopt shared embedding and pooling layers learn functions on graphs. Wang et al. (2020b); Li et al. (2021) and Jiang al. (2018); Liu et al. (2020) have applied Deep Set and GNN to MARL. However, due to the use of the shared embedding o(x,). the representation capacity is usually limited (Wagstaff et al., 2019).
Multi-head Self-Attention & Transformer. To improve the representational capacity, Set Trans- former (Lee et al., 2019) employs the multi-head self-attention mechanism (Vaswani et al., 2017) to process every 2; of the input set, which allows the method to encode higher-order interactions be- tween elements in the set. Most recently, Hu et al. (2021b) adopt Transformer (Vaswani et al., 2017) to MARL and proposes UPDeT, which could handle various input sizes. But UPDeT is originally designed for transfer learning scenarios and does not explicitly consider the PI and PE properties.
PE Functions in MARL. In the deep learning literature, some works have studied the effectiveness of PE functions when dealing with problems defined over graphs (Maron et al., 2018; Keriven & Peyré, 2019). However, in MARL, few works exploit the PE property to the best of our knowl- edge. One related work is Action Semantics Network (ASN) (Wang et al., 2019), which studies the different effects of different types of actions but does not directly consider the PE property.
3 PROBLEM STATEMENT
3.1 ENTITY-FACTORED MODELING IN DEC-POMDP
A cooperative multiagent environment typically consists of m entities, including n learning agents and m non-player objects. We follow the definition of Dec-POMDP (Olichock & Amato, 2016). At each step, each agent receives an observation O, E O2 which contains partial information of the state S, and executes action a, E A, according to policy n. (a.lo.). The environment transits to the next state s' and all agents receive a shared global reward. The target is to find optimal policies for all agents which can maximize the expected cumulative global reward. Each agent's 's individual action-valus value function is denoted as Q (o;, a.). Detailed definition can be found in Appendix B.
Modeling MARL in factored spaces is a common practice. Many recent works (Qin et al., 2022; Wang et al., 2020b; Hu al., 2021b; Long al., 2019; Wang et al., 2019) model the observation and the state of typical MARL benchmarks e.g., SMAC (Qin et al., 2022; Hu et al., 2021b), MPE (Long al., 2019) and Neural MMO (Wang et al., 2019), into factored parts relating the environment, agent itself and other entities. We follow such a common entity-factored setting that both the state space and the observation space are factorizable and can be represented entity-related features,
3

---

Published as a conference paper at ICLR 2023
Le., S S Rmxd and o E C Rmxd, where dg and do denote the feature dimension of each entity the state and the observation. For the action space, we consider a general setting that each agent's s actions are composed of two types: set of m entity-correlated actions Aequiv and of entity-uncorrelated actions Ainv, i.e. A, & (Aqquiv: Aiw.). The entity-correlated actions mean that there exists one-to-one correspondence between each entity and each action, e.g., 'attacking which enemy' in SMAC 'passing the ball which teammate' in football games. Therefore, Gequiv E Aequiv should be equivariant with the permutation of o and aav E A Anv should be invariant. Tasks only considering one of the two types of actions can be considered special cases.
3.2 OUR TARGET: DESIGNING PI AND PE POLICY NETWORKS
Let 9 E G be arbitrary permutation matrix. We define that y operates o, by permuting the orders of the m entities' features, i.e., go;, and that operates on a; = (Gequiv (inv) by permuting the orders of dequiv but leaving Ownv unchanged, i.e., ga; (gQequivv Oinv) ). Our target is to inject the Pl and PE inductive biases into the policy network design such that:
n., (a:loo;;) (a:lo))
(gT, (Acqqucuu a,,, TT ((inn)
G O
(I)
where y operates n; by permuting the orders of I (Requirls)) while leaving ny (a( (0:) unchanged.
METHODOLOGY
4.1 THE HIGH-LEVEL IDEA
Input layar
Backbone network
Output layer
Our target policy network architecture is shown in Fig.2. which consists of four modules: in- put module A, backbone module B which could be any architecture, for actions aun and O output module D for actions Gequiv- For brevity, we denote the in- puts and outputs of these modules as: A(oi), h4 B(z;), TT (o:) = C(h,), and Ti (aequii (o;) D(h;) respectively.
dp
C
Ainy
output module C
A
B
aequiv
Imput
Figure
The ideal PI and PE policy network.
To achieve equation 1, we have modify the architectures of {A, B, C, D} such that the outputs of C' are PI and the outputs of D are PE. In this paper, we propose to directly modify A to be PI and modify D to be PE with respect to the input og and keep the backbone module and output module C unchanged. The following Propositions show that our proposal is a feasible and simple solution.
Proposition 1 If we make module A become PI, the output of module C will immediately become PI without modifying module B and C.
Proof. Given two different inputs go, and og, Vg E G, since module is PI, then A(go,) = A(o;). Accordingly, for any functions B and C, we have (Co B A) (go.) = BC (o:) which is exactly the definition of PI.
Corollary 1. With module A being PI, if not modifying module D. the output of D will also imme- diately become PI, i.e., (Do Bo o A) (go,) = (D o A) (ot) Vy G.
Proposition 2 With module A being PI, to make the output of module D) become PE, we must introduce où as an additional input.
Proof. According to corollary 1, with module being PI, module also becomes PI. To convert module D into PE, we must have module D know the entities" order in Thus we have to add o; as an additional input to D. i.e., Te (eeqqqu (o;) = D(h,, o;). Then, we only have to modify the architecture of D such that D(hi, goz) D(,, 0;) = g (o:), Vi G.
Note that the size of Augui be smaller than i.e., only corresponding to subset of the entities (e.g.. enemies or teammates). We use here for the target of simplifying notations.
4

---

Published as a conference paper at ICLR 2023
A
C
Bjnv
W 2
matmul
sum
D
W
matmul
W
B
aequiv
KiCeeee Bil
2 W2
Input
1
matmul
W A
W3
MLP
MLP
In
FC Layer
Pout
Gumbel
FC-layer under submodule view
permutation invariant input
permutation equivariant output
Figure an FC-layer in submodule view (left); dynamic permutation network architecture (right).
Minimal Modification Principle. Although modifying different parts of {A, B, C. D} may also achieve equation the main advantage our proposal is that we can keep the backbone module B (and output module C)) unchanged. Since existing algorithms have invested a lot in handling MARL-specific problems, c.g., they usually incorporate Recurrent Neural Networks (RNNs) into the backbone module to handle the partially observable inputs, we believe that achieving PI and PE without modifying the backbone architectures of the underlying MARL algorithms is beneficial. Following this minimal modification principle, our proposed method can be more easily plugged into many types of existing MARL algorithms, which will be shown in section 5. In the following, we propose two designs to implement the PI module A and the PE module D.
4.2 DYNAMIC PERMUTATION NETWORK
As common practice adopted by many MARL algorithms, e.g.. QMIX (Rashid et al., 2018), MAD- DPG (Lowe al., 2017) and MAPPÓ (Yu et al., 2021), module A, and D are Fully Connected (FC) Layers and module B is Deep Neural Network (DNN) which usually incorporates RNNs to handle the partially observable inputs. Given an input o containing m entities' features, an FC-layer under submodule view is shown in Fig.3 (left), which has m independent weight matrices. If we denote Win [ir.... Win the weights of the FC-layer A, the output computed as*
where [j] indicates the j-th element. Similarly, we denote Waut = [W ..... Wout the weight matrices of the output layer D. The output Ti ("cqquiv o;)) is computed as:
ii (P = Wouol
Vj m..
(3)
PI Input Layer A. According to equation 2, permuting o,, i.e. of = go,, will result in different output z/. as the j-th input changed oi while the j-th weight matrix remains unchanged. To make an FC-layer become PI, we design PI weight matrix selection strategy for each o, such that no matter where [i] is arranged, the same o, [J] will always be multiplied by the same weight matrix. Specifically, we build a weight selection network of which the output dimension is m:
Pin ([wip.... Win] [o([]) = softmax (aatmaxMMLPPP (o.(1))
where the k-th output Pin (Win & (il))) indicates the probability that o:[5] selects the k-th weight matrix of Win Then, for each o: [i]. we choose the weight matrix with the maximum probability. However, directly selecting the argmax index is not differentiable. To make the selection process trainable, we apply a Straight Through Estimator (Van Den Oord et al., 2017) to get the one-hot encoding of the argmax index. We denote it as Pmm (o:(i)). The weight matrix with the maximum probability can be acquired by Pia (o; [i]) Wm. i.e. selecting the corresponding row from Wi. Over- all, no matter which orders the input 0; arranged, the output of layer A is computed as:
m
dbl (pm (o.)) Win)
of = go;, Vg E
(5)
'For brevity and clarity, all linear layers described without explicit bias term; adding does affect the analysis.
5

---

Published as a conference paper at ICLR 2023
Ciny
WT
clement-jaie sum
D
x
matmul
W'S C3
dequiv
Imput 0
matmul
WT
reshape
Hypernet
Hypernet
hp
PPaut
(A) parmutation invariant input
permutation equivariant output layer
Figure 4: PI and PE network with hypernetworks.
Since the selection network only takes each entity's ' features (, as input, the same o: will always generate the same probability distribution and thus the same weight matrix will be selected no matter where og[5] is ranked. Therefore, the resulting 2; remains the same regardless of the arranged orders of og, i.e., layer A becomes PI. An illustration architecture is shown in Fig.3 (right).
PE Output Layer D. To make the output layer achieve PE, we also build a weight selection network Poen (or (I) for each entity-related output. The j-th output of D is computed as:
Ts (Aqqquu [ (for (o((i) Woa)
of = go.,
go,, Vg E G, E m.
(6)
For V/g G, the j-th element of of will always correspond the matrix of Wour and thus the j-th output of Tty (aequiv of) will always have the same value. The input order change will result in the same output order change, thus achieving PE. The architecture is shown in Fig.3 (right).
4.3 HYPER POLICY NETWORK
The core idea of DPN is to always assign the same weight matrix to each o.] Compared with Deep Set style methods which use a single shared weight matrix to embed the input o,, i.e., [Win 1, DPN's representational capacity has been improved, i.e., Wmnl
However, the sizes of Wi and Won are still limited. One restriction is that for each oj[ we can only select weight matrices from these limited parameter sets. Thus, the weight matrix assigned to each o,15] may not be the best fit.
One question whether we can provide an infinite number of candidate weight matrices such that the solution space of the assignment is no longer constrained. To achieve this, we propose Hyper Policy Network (HPN), which incorporates hypernetworks (Ha et al., 2016) to generate customized embedding weights for each [j]. by taking [:] input. Hypernetworks (Ha et al., 2016) are family of neural architectures which use one network to generate the weights for another network. Since we consider the outputs of hypernetworks as the weights in Wi, and Woas the sizes of these parameter sets no longer limited to m. To better understand our motivations, we provide simple policy evaluation experiment in Appendix A. where we can directly construct an infinite number of candidate weight matrices, show the influence of the model's representational capacity.
PI Input Layer A. For the input layer A, we build hypemettork hp (o: = MLP (o,[7) to generate corresponding Win for each o,[5].
db hp (o.
= go,, Gg G
As shown in Fig.4, first feed all of[j]s (colored by different blues), into the shared hypernetwork hp. (o.[i)) (colored in yellow), whose input size is d, and output size is d,d, 5. Then, we reshape the output for each oj[j] to d, x d,, and regard it as the weight matrix Wn[j]. Different ofjis will generate different weight matrices and the same oj] will always correspond to the same one no matter where it is arranged. The output of layer A is computed according to equation 7. Since each ob]i] is embedded separately by its corresponding [m] and then merged by a PI 'sum' function, the Pl property ensured.
$d is the dimension of [i] and d, is the dimension of h,-

---

Published as a conference paper at ICLR 2023
HPN-GMIX
QMX
HPNAVN
VON
5m ou, dm (Paec)
der one Den (bard))
22, vM. Slag (haed)
12m (ouper hard)
Mexion Test Wer
0.0
800
03
64
12
NMME touper hwrd)
Sedr jugee hare))
For (NEee harrt)
77m. v8 30m Seper Tann
1.00
005
1.75
0.50
22
04
65
04
1.0
0.
3.
04
300
0.2
04
00
0.5
3.2
04
35
08
Enviioement Step
Figure 5: Comparisons of HIN--MMI, HPN-VDN against fine-tuned QMIX and fine-tuned VDN.
PE Output Layer D. Similarly, we build hypernetwork hp (o:(i)) = MLP (o, [i)) to generate
the weight matrices Wonr for the output layer D. The j-th output of layer D is computed as:
Ti [ = hap (d(ii)
of = Vg E e m}
(8)
By utilizing hypernetworks, the input 0gji] and the weight matrix [i] directly correspond one- to-one. The input order change will result in the same output order change, thus achieving PE. See Fig.4 for the whole architecture of HPN.
In this section, when describing our methods, we represent module A and D as networks with only one layer, but the idea of DPN and HPN can be easily extended to multiple layers. Besides, both DPN and HPN are general designs and can be easily integrated into existing MARL algorithms to boost their performance. All parameters of DPN and HPN are trained end-to-end with backpropa- gation according to the underlying RL loss function. Implementation details can be found in B.2.
5 EXPERIMENT
5.1 STARCRAFT MULTIAGENT CHALLENGE (SMAC AND SMACV2)
Setup and codebase. We first evaluate our methods in SMAC, which is an important testhed for MARL algorithms. SMAC consists of set of StarCraft II micro battle scenarios, where units are divided into two teams: allies and enemies. The ally units are controlled by the agents while the enemy units are controlled by the built-in rule-bases bots. The agents can observe the distance, relative location, health, shield and type of the units within the sight range. The goal is train the agents to defeat the enemy units. We evaluate our methods in all Hard and Super Hard scenarios. Following Samvelyan et al. (2019); Hu et al. (2021a), the evaluation metric is function that maps the environment steps to test winning rates. Each experiment is repeated using 5 independent train- ing runs and the resulting plots show the median performance as well as the 25%-75% percentiles. Recently, Hu et al. (2021a) a) demonstrate that the optimized QMIX (Rashid et al., 2018) 8) achieves the SOTA performance in SMAC. Thus, all codes and hyperparameters used in this paper are based on their released project PYMARL Detailed parameter settings are given in Appendix C. Except for SMAC, we also evaluate our HPN new challenging benchmark SMACv2. Due to the space limit, detailed settings and evaluation results are presented in Appendix A.10.
5.1.1 APPLYING HPN TO SOTA FINE-TUNED QMIX
We apply HPN to each (a,lo: of the fine-tuned QMIX and VDN (Hu et al., 2021a). The learning curves over 8 hard and super hard scenarios are shown in Fig.5. We conclude that: (1) HPN-QMII surpasses the fine-tuned QMIX by large margin and achieves 100% test win rates in almost all scenarios, especially Sm_vs_6m 3352.vs_3sh and 6h. which has never been achieved be- fore. Our HPN-QMIX achieves the new SOTA in SMAC; (2) HPN-VDN significantly improves the performance of fine-tuned VDN, and it even surpasses the fine-tuned QMIX in most scenarios, which minimizes the gaps between the VDN-based and QMIX-based algorithms: (3) HPN signif- icantly improves the sample efficiency of both VDN and QMIX, especially in 5m_vs_ (6m, MMM2, 355__8__$66 and 6h_vs_8z. In 5m_rs_6m, to achieve the same 80% win rate, HPN-VDN and HPN- QMIX reduce the environmental interaction steps by factor of 1 compared with the counterparts.
7

---

Published as a conference paper at ICLR 2023
HPNGGMIX OPN-MMXX
UPDST-QMIX
ASN-QMIX
GNI-GIMIX
SET-QWA -IMIXIIX
GILYE QMIX
DA-QMIX
5m
5m, (hard)
3552 3562 hard)
Med Teed
C4
34
C4
47
162
Envtronment Step
Figure 6: Comparisons of HPN and DPN against baselines considering the Pl and PE properties.
5.1.2 COMPARISON WITH PI AND PE BASELINES
The baselines we compared include: (1) DA-QMIX: According to (Ye et al., 2020), we apply data augmentation to QMIX by generating more training data through shuffling the input order and us- ing the generated data to additionally update the parameters. (2) SET-QMIX: we apply Deep Set (Li et al., 2021) ) to each Qi(a:lo;) of QMIX, i.e., all æ4s use a shared embedding layer and then aggregated by sum pooling, which can be considered as a special case of DPN, i.e., DPN(1). (3) GNN-QMIX: We apply GNN (Liu et al., 2020; Wang et al., 2020b) to each Q: (a,a;o0;) of QMIX to achieve PI. (4) ASN-QMIX (Wang et al., 2019): ASN-QMIX models the influences of differ- ent actions on other agents based on their semantics, e.g., move or attack, which is similar to the PE property considered in this paper. (5) UPDeT-QMIX (Hu et al., 2021b): recently MARL algorithm based on Transformer which implicitly considers the PI and PE properties.
The results are shown in Fig.6. We conclude that: HPN > DPN 2 UPDeT 2 ASN > QMIX > GNN xe SET R3 DA Specifically, (1) HIPN-QMIX achieves the best win rates, which validates the effee- tiveness of our PI and PE design; (2) HPN-QMIX performs better than OPN-QMIX. The reason is that HPN-QMIX utilizes more flexible hypernetworks to achieve PI and PE with enhanced repre- sentational capacity. (3) UPDET-QMIX and ASN-QMIX achieve comparable win rates with DPN- QMIX in most scenarios, which indicates that utilizing the PI and PE properties is important. (4) GNN-QMIX and SET-QMIX achieve similar performance. Although PI is achieved, GNN-QMIX and SET- SET-QMIX still perform worse than vanilla QMIX, especially in 3s52_vs_ This confirms that using shared embedding layer p(z;) limits the representational capacity and restricts the final performance.
and 6h 6h_vs_8c. 82.
(5) DA DA-QMIX improves the performance of QMIX in 3s5z_vs_ through much more times of parameter updating. However, its learning process is unstable and it collapses in all other scenarios due to the perturbation of the input features, which validates that is hard to make a learning curves of these PI/PE baselines equipped with VDN are shown in Appendix A.2, which have similar results. All implementation details are shown in Appendix B.2. Besides, in Appendix 1, we also test and analyze these methods via simple policy evaluation experiment.
function (c.g., MLP) achieve PI through training solely. The
5.1.3 ABLATION: ENLARGING THE NETWORK SIZE OF THE BASELINE
For HPN, incorporating hypernetworks leads to a 'bigger' model. To make a more fair compar- ison, we enlarge the network size of Q:(azlo:) in fine-tuned QMIX (denoted as BIG-QMIX) such that it has more parameters than HPN- QMIX. Besides, the UPDeT baselines already have comparable more parameters than HPN. The detailed sizes of these models are shown in Table 3 of Appendix A.3. From 7 we that simply increasing the parameter number cannot improve the performance. In contrast, it even leads to worse results. VDN-based results are presented in Appendix A.3.
2L Juper nad
Enohromam: Stop
Figure 7: Ablation studies.
5.1.4 ABLATION: IMPORTANCE OF THE PE OUTPUT LAYER AND INPUT NETWORK CAPACITY
(1) To validate the importance of the PE output layer, add the hypemnetwork-bar based output layer of HPN to SET-QMIX (denoted as OPN-SET-QMIX), From Fig.7, we see that incorporating a PE output layer could significantly boost the performance of SET-QMIX. The converged performance of HPN-SET-QMIX is superior to that of vanilla QMIX. (2) However, due to the limited represen-
'We use the binary comparison operators here indicate the performance order of these algorithms.
8

---

Published as a conference paper at ICLR 2023
tational capacity of the shared embedding layer of Deep Set, the performance of HPN-SET-QMEL is still worse than HPN-QMIX. The only difference between HPN-SET-QMIX and HPN-QMIX is the number of embedding weight matrices in the input layer. The results validate that improving the representational capacity of the PI input layer is beneficial.
5.1.5 APPLYING HPN TO MAPPO AND QPLEX
The results of applying HPN MAPPO (Yu et al., 2021) and QPLEX (Wang et al., 2020a)
HPN-OPLEX
OPLEX
HPNAMAPPO
MAPPO
Sm Fm
3a5y Jelo
in 5m.vs. 6m and 3s52.vs 3s6z shown in Fig.8. We see that HPN-MAPPO and HPN-
Median Tea
QPLEX consistently improve the performance of MAPPO and QPLEX, which validates that
04
HPN can be easily integrated into many types of
27
24
14
08
MARL algorithms and boost their performance. Full results are shown in Appendix A.4.
Enstrnment Step
Figure 8: Apply HPN to QPLEX and MAPPO.
5.2 MULTIAGENT PARTICLE ENVIRONMENT (MPE)
We also evaluate the proposed DPN and HPN in the cooperative navigation and the preyy
Coopestive Ow
scenarios of MPE (Lowe et al., 2017), where the actions only consist of movements. Therefore, only the Pl property needed. We follow the experimental settings of PIC (Liu et al., 2020) (which utilizes GNN achieve PI, i.e., GNN- MADDPG) and apply our DPN and HPN to the joint Q-function of MADDPG. We implement the code based on the official PIC codehase. The learning curves are shown in Fig.9. We see that our HPN-MADDPG outperforms the GNN-based PIC, DA-MADDPG and MADDPG baselines by large margin, which validates the superiority of our Pl designs. The detailed experimental settings and full results are presented in Appendix A.6.
Endiesment Stap 201
Figure 9: Apply HPN and DPN to MADDPG.
5.3 GOOGLE RESEARCH FOOTBALL (GRF)
Finally, we evaluate HPN in two Google Re- search Football (GRF) (Kurach et al., 2020) aca- demic scenarios: 3 vs 1 with keeper and coun- terattack hard. We control the left team players, which need to coordinate their positions to orga- nize attacks, and only scoring leads to rewards. The observations consist of 5 parts: ball infor- mation, left team, right team, controlled player and match state. Each agent has 19 discrete ac-
(ours)
acacamy So with kneper
wooterry On www.tersiacccccccoocco herd
Maen Tout
Endrronm Stip
Figure 10: Apply HPN GRF
tions, including moving, sliding, shooting and passing, where the targets of the passing actions correspond to its teammates. Detailed settings can be found in Appendix A.7. We apply HPN to QMIX and compare it with the SOTA CDS DDS-QMIX (Chenghao et al., 2021). We show the aver- age win rate across 5 seeds in Fig. 10. HPN can significantly boost the performance of QMIX and HPN-QMML outperforms the SOTA method CDS-QMIX by large margin in these two scenarios.
CONCLUSION
In this paper, we propose two PI and PF designs, both of which can be easily integrated into existing MARL algorithms to boost their performance. Although we only test the proposed methods in model-free MARL algorithms, they are general designs and have great potential to improve the performance of model-based (Yuan et al., 2022), multitask and transfer learning (Wu et al., 2023) algorithms. Besides, we currently follow the settings of (Qin et al., 2022; Wang al., 2020b; Hu et al., 2021b; Long et al., 2019), where the configuration of the input-output relationships and the observation/state structure are set manually. For future works, it is interesting to automatically detect such structural information.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
This work is supported by the National Natural Science Foundation of China (Grant No.62106172), the "New Generation of Artificial Intelligence" Major Project of Science & Technology 2030 (Grant No.2022ZD01 16402), and the Science and Technology on Information Systems Engineering Labo- ratory (Grant No. WDZC20235250409 No. WDZC20005250007),
We thank Zipeng Dai for the insightful discussions and helpful writing suggestions. We are very grateful for the valuable and constructive comments of all reviewers.
REFERENCES
Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sonzaez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint arXiv: 1806.0/261, 2018.
Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemystaw Debiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Chris Hesse, al. Dota 2 with large scale deep reinforcement learning. arXiv preprini 1912:.991.66660 2019.
Wendelin Böhmer, Vitaly Kurin, and Shimon Whiteson. Deep coordination graphs. In International Conference on Machine Learning, pp. 980-991, PMLR, 2020.
Li Chenghao, Tonghan Wang, Chengjie Wu, Qianchuan Zhao, Jun Yang, and Chongjie Zhang. Cel- ebrating diversity in shared multi-agent reinforcement learning. Advances in Neural Information Processing Systems, 34:3991-4002, 2021.
David Ha, Andrew Dai, and Quoe V Le. Hypernetworks. arXiv preprint arXiv:1609.09100 2016.
Jian Hu, Siyang Jiang, Seth Austin Harding, Haibin Wu, and Shih-wei Liao. Riit: Rethinking the importance of implementation tricks in multi-agent reinforcement learning. arXiv preprini
1rX:v:2102.03379, 2021a.
Siyi Hu, Fengda Zhu, Xiaojun Chang, and Xiaodan Liang. Updet: Universal multi-agent agent reinforce- ment learning via policy decoupling with transformers. In International Conference on Learning Representations, 2021b.
Maximilian Hüttennauch, Adrian Šošić, and Gerhard Neumann. Guided deep reinforcement learning for swarm systems. arXiv preprint arXiv: 06011, 2017.
Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterizztion with gumbel-softmax. arXiv preprint ar1iv:161 1.00 144, 2016.
Jiechuan Jiang, Chen Dun, Tiejun Huang, and Zongqing Lu. Graph convolutional reinforcement 2018.
learning. arXiv preprint
Nicolas Keriven and Gabriel Peyré. Universal invariant and equivariant graph neural networks. Advances in Neural Information Processing Systems, 32, 2019.
Karol Kurach, Anton Raichuk, Piotr Stańczyk, Michal Zajac, Olivier Bachem, Lasse Espeholt, Car- los Riquelme, Damien Vincent, Marcin Michalski, Olivier Bousquet, et al. Google research football: A novel reinforcement learning environment. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 4501 4510- 2020.
Juho Lec, Yoonho Lee, Jungtack Kim, Adam Kosiorek, Seungjin Choi, and Yee Whye Teh. Set transformer: A framework for btaeetioo-bbsed permutation-invariant neural networks. In Interna- tional Conference on Machine Learning, pp. 3744 3753. PMLR, 2019.
P. Li, H. Tang, T. Yang, X. Hao, T. Sang, Y. Zheng, J. Hao, M. E. Taylor, W. Tao, and Z. Wang- PMIC: improving multi-agent reinforcement learning with progressive mutual information col- laboration. In International Conference on Machine Learning, ICML. 2022, 17-23 July 2022, Baltimore, Maryland, USA, Proceedings of Machine Learning Research, pp. 12979-12997 2022.
10

---

Published as a conference paper at ICLR 2023
Yan Li, Lingxiao Wang, Jiachen Yang, Ethan Wang, Zhaoran Wang. Tuo Zhao, and Hongyuan Zha. Permutation invariant policy optimization for mean-fied field multi-agent reinforcement learning: A principled approach. arXiv preprini arXiv:2105.08220 2021.
lou-Jen Liu, Raymond A Yeh, and Alexander G Schwing. Pic: permutation invariant critic for multi- agent deep reinforcement learning. In Conference on Robot Learning, pp. 590-602. PMLR, 2020.
Qian Long, Zihan Zhou, Abhinav Gupta, Fei Fang, Yi Wu, and Xiaolong Wang. Evolutionary popu- lation curriculum for scaling multi-agent reinforcement learning. In International Conference on Learning Reprexentations, 2019.
Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, Pieter Abbeel, and Igor Mordatch. Multi-agent actor- critic for mixed cooperative-commpttiiee environments. arXiv preprint arXiv:1706.022753 2017.
Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. In International Conference on Learning Representations, 2018.
Frans A Oliehoek and Christopher Amato. A concise introduction to decentralized POMDPs.
Springer, 2016.
Rongjun Qin, Feng Chen, Tonghan Wang, Lei Yuan, Xiaoran Wu, Zongzhang Zhang, Chongjic Zhang, and Yang Yu. Multi-agent policy transfer via task relationship modeling. arXiv preprint arXiv:2203. 04482, 2022.
Tabish Rashid, Mikayel Samvelyan, Christian Schroeder, Gregory Farquhar, Jakob Foerster, and Shimon Whiteson. Qmix: Monotonic value function factorisation for deep multi-agent reinforce- ment learning. In International Conference on Machine Learning, pp. 4295-4304. PMLR, 2018.
Mikayel Samvelyan, Tabish Rashid, Christian Schroeder De Witt, Gregory Farquhar, Nantas Nardelli, Tim GJ Rudner, Chia-Man Hung, Philip HS Torr, Jakob Foerster, and Shimon Whiteson. The starcraft multi-agent challenge. arXiv preprint
2019.
Aaron Van Den Oord, Oriol Vinyals, al. Neural discrete representation learning. Advances in neural information processing systems, 30, 2017.
Elise van der Pol, Herke Hoof, Frans Oliehoek, and Max Welling. Multi-agent mdp homo- morphic networks. arXiv preprint arXiv:2 10.04495, 2021.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pp. 5998-6008, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
Oriol Vinyals, Igor Babuschkin, Wojeiech M Czarnecki, Michael Mathicu, Andrew Dudzik, Juny- oung Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature, 575(7782) 2019.
Edward Wagstaff, Fabian Fuchs, Martin Engeleke, Ingmar Posner, and Michael A Osborne. On the limitations of representing functions on sets. In International Conference on Machine Learning, pp. 6487-6494. PMLR, 2019.
Jianhao Wang, Zhizhou Ren, Terry Liu, Yang Yu, and Chongjie Zhang. Qplex: Duplex dueling multi-agent q-learning. arXiv preprint arXiv:2008.01062, 2020a.
Tonghan Wang, Liang Zeng, Weijun Dong. Qianlan Yang. Yang Yu. and Chongjie Zhang. Context- aware sparse deep coordination graphs. arXiv preprint arXiv:2106. 02886, 2021.
Weixun Wang, Tianpei Yang, Yong Liu, Jianye Hao, Xiaotian Hao, Yujing Hu, Yingfeng Chen, Changjie Fan, and Yang Gao. Action semantics network: Considering the effects of actions in multiagent systems. In International Conference Learning Representations, 2019.

---

Published as a conference paper at ICLR 2023
Weixun Wang, Tianpei Yang, Yong Liu, Jianye Hao, Xiaotian Hao, Yujing Hu, Yingfeng Chen, Changjie Fan, and Yang Gao. From few to more: Large-scale dynamic multiagent curriculum learning. In Proceedings of the AAAI Conference on Arlificial Intelligence, volume 34, pp. 7293-
7300, 2020b.
Jizhou Wu, Tianpei Yang, Xiaotian Hao, Jianye Hao, Yan Zheng, Weixun Wang, and Matthew E. Taylor. Portal: Automatic curricula generation for multiagent reinforcement learning. In Pro- ceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems, 2023.
Zhenhui Ye. Yining Chen, Guanghua Song, Bowei Yang, and Shen Fan. Experience augmenta- tion: Boosting and accelerating off-policy multi-agent reinforcement learning. arXiv preprint arXiv:2005.09453, 2020.
Chao Yu, Akash Velu, Eugene Vinitsky, Yu Wang, Alexandre Bayen, and Yi Wu. The surprising effectiveness of mappo in cooperative, multi-agent games. arXiv preprint arXiv:2103.0195. 2021.
Yifu Yuan, Jianye Hao, Fei Ni, Yao Mu, Yan Zheng, Yujing Hu, Jinyi Liu, Yingfeng Chen, and Changjie Fan. Fuclid: Towards efficient unsupervised reinforcement learning with multi-choice dynamics model. arXiv preprint arXiv:2210.00498, 2022.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander Smola. Deep sets, Advances in Neural Information Processing Systems, 30, 2017.
12

---

Published as a conference paper at ICLR 2023
A ADDITIONAL EXPERIMENTAL SETTINGS AND RESULTS
A.1 A SIMPLE POLICY EVALUATION PROBLEM.
present simple policy evaluation experiment to show the influence of the model's representa- tional capacity on the converged performance. We consider the following cermmuaationinvariiin (PI) models: O Deep Set, @ DA-MLP (apply data augmentation to permulation-senstiive MLP model), DPN (apply DPN to the same MLP model), 0 HPN (apply HPN to the same MLP model) and @ Attention (use self-attention layers and a pooling function to achieve Pl).
We
The experimental settings are as follows. There are agents in total. Each agent i only has one dimension of feature Ii. For the convenience of analyzing, we set that each z; is an integer and Ia E {1, 2.., .... 30), i.c., each agent i only has 30 different features. Thus the size of the joint state space (121, x2 after concatenating is 30 30 = 900. To make the policy evaluation task cormutatiio-invariian
we simply set the target value Y of each state [2] as I1 * 22.
In section 4.3, when introducing HPN, we asked a question that whether we can provide an infi- nite number of candidate weight matrices of DPN. In this simple task, we directly construct a separate weight matrix for each feature z₁- Since I; is discrete (which is enumerable), we can explicitly maintain parameter table and exactly record different embedding weight for each dif- ferent feature z₁. We denote this direct method as DPN((c), which means 'DPN with infinite weights'. Our HPN uses a hypernetwok to approximately achieve 'infinite weight' by generating a different weight matrix for each different input x4, We use the Mean Square Error (MSE) as the loss function to train these different models. The code for this simple experiment is also available at htts://github..om/jjjn Xiaotiaa / APe-Nerworkk (see 'Synthetic Policy Evaluation.py"
The comparison of the learning curves and the converged MSE losses of these different PI models are shown in Fig. 1I and Table respectively. We conclude that DPN(oc) HPN Attention >> DPN > DeepSet >> DA-MLP, where '>' means 'performs better than', which indicates that increasing the representational capacity of the model can help achieve much less MSE loss.
Table 1: The comparison of the converged MSE losses of these different PI models.
DA-MLP
Deep Set
DPN
Attention
HPN
DPN(co)
MSE
1495.55
1401.23
119.54
49.12
6.34
0.37
DPN(=)
HPN
DPN
Attention
DeepSet
DA-MLP
MSE loss in logt scale
Training Step
Figure 11: The comparison of the learning curves of different PI models.
If we keep each v; E 21, 30) and simply increase the agent number, the changes of the original state space by simple concatenation and the reduced state space by using Pl representations are shown in Table below. We see that by using Pl representations, the state space can be significantly reduced.
Table 2: Changes of the state space size with the increase of the agent number.
agent number
3
3
simple concatenation
900
27000
810000
24300000
Pl representation (percent)
465 (0.52)
4960 (0.18)
40920 (0.05) 278256 (0.01)
13

---

Published as a conference paper at ICLR 2023
HPN-VUN
DPNAVON
UPDe I-VON
GAN-VOO
SET-VON
DA-VON
VIN
Dm, (hard)
24
04
147
Step
Figure 12: Comparisons of VDN-based methods considering the PI and PE properties.
A.2 COMPARISON WITH VDN-BASED
BASED PI AND PE BASELINES
The learning curves of the PI/PE baselines equipped with VDN are shown in Fig. 12, which demon- strate that: HPN > DPN 2 UPDeT > VDN > GNN x SET ~ DA Specifically, (1) HPN-VDN and DPN-VDN achieve the best win rates; (2) Since UPDeT uses shared token embedding layer followed by multi-head self-attention layers to process all components of the input sets, the PI and PE properties are implicitly taken into consideration. The results of UPDeT-VDN also validate that incorporating PI and PE into the model design could reduce the observation space and improve the converged performance in most scenarios. (3) GNN-VDN achieves slightly better performance is maintained, GNN-VDN and SET VDN perform
than SET-VDN. Although permutation-invarin worse than vanilla QMIX, (especially in 3s5r_vs_3s66 and 6h_vs_8z, the win rates approximate 0%). This confirms that the use of a shared embedding layer (xx,) for each component I; limits the
representational capacities and restricts the final performance. (4) DA-VDN significantly improves the learning speed and performance of vanilla VDN 3s52 vs 3366 by data augmentation and much more times of parameter updating. However, the learning process is unstable, which collapses in all other scenarios due the perturbation of the input features, which validates that it hard to train a cetpuuttttio-ssnssttii function (e.g., MLP) to output the same value when taking different orders of features as inputs.
A.3 ABLATION STUDIES.
HPN-VDN
HPN-SET-VDN
SET-VDN 3s52_ vs. 3s6z (super hard)
BIG-VDN 6h. vs 8z (super hard)
VDN
5m vs 6m (hard)
Median Test Win %
1.0
0.8
0.8
0.8
0.6
0.4
0.4
0.2
0.2
0.0
0.2
0.4
0.8
0.8
1.0
0.0
0.2
0.4
0.8
0.8
1.0
0.0
0.2
0.4
0.8
0.8
1.0
107
167
167
Environment Step
Figure 13: Ablation studies. All methods equipped with VDN.
A.3.1 1 ENLARGING THE NETWORK SIZE.
We also enlarge the agent network of vanilla VDN (denoted as BIG-VDN) such that the number of parameters is larger than our VDNN. The detailed numbers of parameters are shown in Table 3. The results are shown in Fig. 13. We see that simply increasing the parameter number cannot always guarantee better performance. For example, in 5m vs 6m, the win rate of BIG-VDN is worse than the vanilla VDN. In 3x5z_vs_3s6z and 6h_vs_8, BIG-VDN does achieve better performance, but the performance of BIG-VDN still worse than our HPN-VDN in all scenarios.
A.3.2 IMPORTANCE OF THE PE OUTPUT LAYER AND THE CAPACITY OF THE PI INPUT LAYER
To validate the importance of the permutation-equivent hypernetwork-based output layer of HPN to SET-VDS (denoted HPN-SET-VDN), The results are shown in 13. We see that incorporating an APE output layer could significantly boost the
output layer, we also add the
We use the binary comparison operators here indicate the performance order of these algorithms.
14

---

Published as a conference paper at ICLR 2023
Table 3: The number of parameters of the individual Q-networks in VIN,, QMIX, BIG-VDN, BIG- QMIX, HPN-VDN, HPN-QMIX, UPDET-VDN and UPDeT-QMIX.
Parameter Size
VDN(QMIX)
BIG
HPN-VDNOMIX
UPDET-VDNOMIX
5m vs 6m
30.412K
T09.964K
72.647K
96.294K
38 vs 5z
29.707K
108.555K
81.031K
96.246K
8m vs 9m
32.911K
114.959K
72.839K
96,438K
corridor
39.262K
127.646K
76.999K
96.39K
3s5z.vs vz.ssz
36.175K
121.48KK
98.375K
96,582K
6h_vs_8z
32.206K
113.55K
76.935K
96.342K
performance of SET-VDN, and that the converged performance HPN-SET-VDE is superior the vanilla VDN in 5m-vs_6m and 3s5z.vs.3s6z.
However, due the limited representational capacity of the shared embedding layer of Deep Set, the performance of HPN-SET-VDN still worse than our HPN-VDN, especially in 6h_vs_8z. Note that the only difference between HPN-VDN and HPN-SET-VDN is the input layer, e.g., using hypernetwork-bane customized embeddings or a simply shared one. The results validate the im- portance of improving the representational capacity of the permutation-invariant input layer.
A.4 APPLYING HPN TO QPLEX AND MAPPO
HPN-OPLEX
QPLEX
5m 6m (hard)
8m vs 9m (hard)
3s_vs_5z (hard)
MMM2 (super hard)
1.00
0.75
0.75
0.75
0.75
Median Test Win %
0.50
0.60
0.50
0.00
3.00
0.00
0.00
0.0
0.2
0.4
0.
0.8
1.0
0.0
0.1
0.2
0.3
0.4
0.5
0.6
0.0
0.2
0.4
0.6
0.8
0.0
0.1
0.2
0.3
04
corridor (super hard)
3652 VS 3662 (super hard)
6h. VS. 8z (super hard)
27m vs. 30m (super hard)
1.00
1.00
1.00
0.75
3.70
0.75
0.5
0.00
3.00
0.00
0.0
3.1
0.2
0.3
0.4
0.5
0.0
0.1
0.2
04
0.5
0.5
0.7 0.8
0.6
0.8
0.0
0.2
Environment Step
The learning curves of HPN-QPLEX compared with vanilla QPLEX in the hard and super hard scenarios of SMAC.
Figure 14:
HPN-MAPPO
MAPPO
5m, (hard)
5z (hard)
8m 9m (hard)
1.00
0.75
0.70
0.75
Median Test Win %
0.00
0.50
0.50
0.25
0.25
0.0
0.6
1.0
0.4
0.2
107
167
167
3s52__v vs. 356z (super hard)
6h_ 8z (super hard)
MMM2 (super hard)
1.00
1,00
0.75
0.50
0.20
0.25
3.00
0.0
0.2
0.4
0.6
0.8
0.0
0.2
0.4
0.5
0.8
1.5
0.0
0.2
0.4
0.6
0.8
1.
107
Environment Step
107
167
Figure 15: The learning curves of HPN-MAPPO compared with the vanilla MAPPO in the hard and super hard scenarios of SMAC.
15

---

Published as a conference paper at ICLR 2023
To demonstrate that our methods can be easily integrated into many types of MARL algorithms and boost their performance, we also apply HPN to a typical credit-assinmentt method QPLEX (Wang et al., 2020a) (denoted as HPN-QPLEX] and policy-based MARL algorithm MAPPO (Yu et al., 2021) (denoted as HPN-MAPPO). The results are shown Fig. 14 and Fig. 15. We see that HPN significantly improves the performance of QPLEX and MAPPO, which validates that our method can be easily combined with existing MARL. algorithms and improves their performance (especially for super hard scenarios).
A.5 APPLYING HPN TO DEEP COORDINATION GRAPH.
Recently, Deep Coordination Graph (DCG) (Böhmer et al., 2020) scales traditional coordination graph based MARL methods to large state-action spaces, shows its ability to solve the relative over- generalization problem, and obtains competitive results on StarCraft II micromanagement tasks. Further, based on DCG, (Wang et al., 2021) proposes an improved version, named Context- SparsE Coordination graphs (CASEC). CASEC learns sparse and adaptive coordination graph (Wang et al., 2021), which can largely reduce the communication overhead and improve the perfor- mance. Besides, CASEC incorporates action representations into the utility and payoff functions to reduce the estimation errors and alleviate the learning instability issue.
Both DCG and CASEC inject the permutation invariance inductive bias into the design of the pair- wise payoff function q.y (a;, ay (0,,,,,,) They achieve permutation invariance by permuting the input order of [os, 0y] and taking the average of both. To show the generality of our method, we also apply HPN to the utility function and payoff function of CASEC and show the performance in Fig. 16. The httpg/ttti.oooouaaaaaaaooaao Network (see codee/sr/comfggllgsseessss yaml and code//vc/conffg/llg///n casec.yaml).
codes of CASEC and HPN-CASEC are also available at
Performance on 5m, vs. 6m
Median Test Win %
0.8
6.9
CASECC CASEC
50
02
04
0.6
0.5
1.0
14
1.6
18
20
Training Step (M)
Figure 16: The learning curves of HPN-CASEC and CASEC in Sm_vs_6m.
In Fig. 16, we compare HPN-CASEC with the vanilla CASEC in 5m_vs_6m 6m. Results show that HPN can significantly improve the performance of CASEC, which validate that HPN is very easy to implement and can be easily integrated into many existing MARL approaches.
A.6 MULTIAGENT PARTICLE ENVIRONMENT
We evaluate the proposed DPN and HPN on the classical Multiagent Particle Environment (MPE) (Lowe et al., 2017) tasks, where the actions only consist of movement actions. Therefore, only the permutation invariance property is needed. We follow the experimental settings of PIC (permutation- invariant Critic for MADDPG, which utilizes GNN to achieve PI, i.e., GNNMADDPG) (Liu et al., 2020) and apply our DPN and HPN to the centralized critic Q-function of MADDPG (Lowe et al., 2017). Each component 2; represents the concatenation of agent i's observation and action. The input set X, contains all agents' observation-aations. We implement the code based on the official PIC. The basclines we considered are PIC (Liu al., 2020), DA-MADDPG (Ye et al., 2020) and MADDPG (Lowe al., 2017). The tasks we consider are as follows:
Cooperative navigation: agents move cooperatively to cover L landmarks in the envi- ronment. The reward encourages the agents to get close to landmarks. An agent observes its location and velocity, and the relative location of the landmarks and other agents.
Cooperative predator-prey: n slower predators work together to chase M fast-moving prey. The predators get positive reward when colliding with prey. Preys environment
16

---

Published as a conference paper at ICLR 2023
controlled. A predator observes its location and velocity, the relative location of the L landmarks and other predators and the relative location and velocity of the prey.
The learning curves of different methods in the cooperative navigation task (the agent number n = 6) and the cooperative predator-pen prey task (the agent number = 33 are given in Fig.9. Besides, We fur- ther test HPN on two more cooperative navigation tasks with 100 and 200 agents respectively. The learning curves are shown in Figure 17. The results show that HPN-MADDPG can significantly im- prove the performance of vanilla MADDPG and achieves superior sample efficiency and converged performance than PIC. All experiments are repeated for five runs with different random seeds. We see that our HPN-MADDPG outperforms the PIC, DA-MADDPG and MADDPG baselines in these two tasks, which validates the superiority of our permutation-invarian designs.
HPN-MADDPG
PIC
DA-MADDPG
MADDPG
Cooperative Navigation (N - 100)
Cosperative Navigation (N 200)
Average Episode Rewards
-00000
-290353
-100000
-990303
-000303
-180000
-900003
0C
0.7
0.4
0.6
0.8
1.0
1.
0.05
0.10
0.15
0.20
0.25
0.30
Environment Step (M)
Figure 17: Comparisons of HPN-MADDPG against PIC, DA-MADDPG and MADDPG in cooper- ative navigation with 100 and 200 agents.
A.7 GOOGLE RESEARCH FOOTBALL
We evaluate HPN in two Google Research Football (GRF) academic scenarios: _sst__with__eppe and counterattack hard. In these tasks, we control the left team players except for the goalkeeper. The right team players are controlled by the built-in rule-based bots. The agents need to coordinate their positions to organize attacks and only scoring leads to rewards. The observations are factor- izable and are composed of five parts: ball information, left team, right team, controlled player information and match state. Detailed feature lists shown in Table 4. Each agent has 19 discrete actions, including moving, sliding, shooting and passing. Following the settings of CDS (Chenghao will
et al., 2021), we also make reasonable change to the two half-court offensive scenarios: lose if our players or the ball returns to our half-court. All methods are tested with this modification. The final reward is + 100 when our team wins, -1 when our player or the ball returns to our half-court, and 0 otherwise.
We apply HPN to QMIX and compare it with the SOTA CDS -MS- (Chenghao et al., 2021). In detail, when applying HPN to QMIX, both the PI actions, e.g., moving, sliding and shooting, and the PE actions, e.g.. long- high-pass and short_pass are considered. For each player, since the targets of these passing actions directly correspond to its teammates, to generate the Q-values of these passing actions, where the hypernetwork takes each ally player's features as input and generates the weight matrices for the passing actions. Besides, in the official GRF environment, as we cannot directly control which teammates the current player passes the ball to, take max pooling over all ally-related Q-values to get the final Q-values for the three passing actions. We show the average win rate across seeds in Fig. 10. HPN can significantly boost the performance of QMIX and our HPN-QMIX outperforms the SOTA method CDS by large margin in these two scenarios.
apply the PE output layer
A.8 GENERALIZATIONS CAN HPN GENERALIZE TO NEW TASK WITH DIFFERENT NUMBER OF AGENTS?
Apart from achieving PI and PE, another benefit of HPN is that it can naturally handle variable numbers of inputs and outputs. Therefore, as also stated in the conclusion section, HPN can be potentially used design more efficient multitask learning and transfer learning algorithms. For example, we can directly transfer the learned HPN policy in one task to new tasks with different numbers of agents and improve the learning efficiency in the new tasks. Transfer learning results of
17

---

Published as a conference paper at ICLR 2023
Ahsolute position
Player
Absolute speed
Left
Relative pesition
Observation
Relative speed
Relative position
Right
Relative speed
Absolale position
Ball
Belong to (leam ID)
Absolute position
Left team
Absolule speei
Player type
Ahsolate prssition
Absolute speed
Right
Player
Ahsolute positiion
Absolute speed
Ball
Absolute rotade speed
Belong fleam ID)
Belong to (player ID)
Table 4: The feature composition of the observation and the state in Google Research Football
12t comcarel won mean
PV7
0.8
0.6
0.4
100
150
200
(a) Transfer learning results on 12m. Red: reload the learned policy in 5m to 12m and then continuously train the policy. Blue: Icarn from scratch.
0.4
0.2
beseline
from__5m 2rom_5m_vs_000
13K
Transfer learning results on 80m. Red: reload the learned policy in 5m_vs 6m to 8m vs_ and then continuously train policy. Blue: learn from scratch.
35, Sz. curve compare test battle, wen mean
1.0
0.6
0.2
scratch reloed from Vs.
step
(c) Transfer learning results 3s vs_. Red: reload the learned policy in
3s 3z 3s. 5z and then continuously train the policy. Blue: learn from scratch.
Figure 18: Transferring the learned HPN-VDN policy one task to a new task with different number of agents.
18

---

Published as a conference paper at ICLR 2023
5m - 12m, 5m_vs66m - 3m_vs_11mm 3s_vs.3z - 38.v8.5z are shown in Fig.18. We see that the previously trained HPN policies can serve as better initialization policies for new tasks.
A.9 To ACHIEVE PI AND PE, WHAT IF WE JUST SORT THE ENTITIES ACCORDING TO DISTANCE FROM THE FOCAL AGENT?
(I) When we first started working on this project, we have also considered a similar baseline: we sort the entities according to (type, distance), i.e,, according to their types first and then the relative distances if two entities' types are same. But we found that this solution do not always work well. Here, we provide the learning curves of HPN, QMIX, VDN, SORT-QMIX, and SORT-VDN in 4 hard and super hard scenarios on SMAC in Figure 19, The results show that the sorting baseline can slightly improve the performance of vanilla QMIX/VDN in 5m_vs_6m and 3s5z.vs_s66r However, in 8m_vs, _s_9m and 68_ it harms the performance.
(2) The reason is that each entity has many types of features, e.g., relative x, relative y, relative distance, entity type, health point, shield, etc. Relative distance is just one of them. Simply sorting the entities by their relative distances while ignoring the influences of the other features may not be appropriate. Besides, different x and can have the same distance and different distances can have the same order, the same 0: [j]] may be arranged at different positions and be multiplied by different 'weight matrices' (according to =; ش o; Wi [i]). Therefore, learning may become unstable if we frequently reorder the inputs by distance only.
(3) Thus, our target is not only matching the observation and action belonging to the same entity but stabilizing the learning process by always assigning the same weight matrix Wnn [i], i.e., stable weight, to the same entity features 0; [j] no matter where o; [j] is arranged. In this paper, we propose DPN and HPN to achieve this.
HPNAVON
VON
SORT-VON
Am, vi, Bm (bard)
8m,, vol 9m (hwrr))
JadV vs. Jelr jupprr faed))
ch. vn. Br (super herd]
Modian Wot
1.2
3.25
500
Enstronment Step
(a) Comparisons of HPN- VDN, VDN, and a baseline that sorts the entities in observation according to their distances from the focal agent (denoted as SORT-VDN).
HPN-GMI
QIAIX
SORT-OMX
Om, Dm shand)
9m (hard)
365r, S60e
Gt. St (super
Modan Teat
1.00
Enwinonmnnt
S0ep
(b) Comparisons of HPN-QMIX. QMIX, and baseline that sorts the entities in observation according to their distances from the focal agent (denoted as SORT-QMIX).
Figure 19: Comparisons of HPN with the sorting based baseline.
A.10 EVALUATE HPN ON SMAC-v2
SMAC-v2 makes three major changes to SMAC: randomising start positions, randomising unit types, and restricting the agent field-of-view and shooting range to cone. These first two changes increase more randomness to challenge contemporary MARL algorithms. The third change makes features harder to infer and adds the challenge that agents must actively gather information (require more efficient exploration). Since our target is not to design more efficient exploration algorithms, we keep the ofld-of-view and attack of the agents a full circle as in SMAC.
Random Start Positions: Random start positions come in two different types. First, there is the surrounded type, where the allied units are spawned in the middle of the map, and
19

---

Published as a conference paper at ICLR 2023
surrounded by enemy units. This challenges the allied units to overeome the enemies ap- proach from multiple angles at once. Secondly, there are the reflect-position scenarios. These randomly select positions for the allied units, and then reflect their positions in the midpoint of the map to get the enemy spawn positions. Example figures are shown in Figure 20 below.
Random Unit Types: Battles in SMACv2 do not always feature units of the same type each time, they did in SMAC. Instead, units are spawned randomly according to certain pre-fixed probabilities. Units StarCraft II are split up into different races. Units from different races cannot be on the same team. For each of the three races (Protoss, Terran, and Zerg), SMACv2 three unit types. Detailed generation probabilities are shown in Figure 21.
Figure 20: Examples of the different types of start positions, opposite and surrounded. Allied units are shown in blue and enemy units in dark red.
Race
Unit
Generation Probability
Terran
Marine
0.45
Marauder
0.45
Medivac
0.1
Protoss
Stalker
0.45
Zealot
0.15
Colossus
0.1
Zerg
Zergling
0.45
Hydraliisk
0.45
Baneling
0.1
Figure 21: Detailed generation probabilities of the three types of units for the three races (Protoss, Terran, and Zerg).
Our HPN can naturally handle the two types new challenges. Thanks to the PI and PE prop- erties, our HPN is more robust to the randomly changed start positions of the entities. Thanks to the entity-wist modeling and using hypernetwork to generate customized weight matrix for each type of unit, HPN can handle the randomly generated unit types as well. The comparisons of HPN- VDN with VDN three difficult scenarios across the three races (Protoss, Terran, and Zerg) shown in Figure 22. Results show that our HPN significantly improves the sample efficiency and the converged test win rates of the baseline VDN.
20

---

Published as a conference paper at ICLR 2023
HPN-VDN VON
protooe
Sermen
Median Text Win %
Environment Stop
Figure 22: The learning curves of HPN-VDN and VDN in 3 difficult scenarios of SMAC-v2.
B TECHNICAL DETAILS
B.1 DECENTRALIZED PARTIALLY OBSERVABLE MDP
We model a fully cooperative multiagent task as Dec-POMID (Oliehoek & Amato, 2016), which defined as tuple (N O, A. P. R, 7) N is a set of n agents.
the set of global states.
O {O }, denotes the observation space for n. agents. A = AA x x An is the joint action space, where A, is the of actions that agent can take. At each step, each agent receives a private observation O; E O; according to the observation function [(s, S x A + O and produces action a; E A; by policy (a(a)):)) All agents' individual actions constitute joint action a = (a),..., an) E A. Then the joint action a is executed and the environment transits to the next state s' according to the transition probability P(s'ls, a). All agents receive shared global reward according to the reward function R(s, a). All individual policies constitute the joint policy 1i X ... X nu. The target is to find an optimal joint policy π which could maximize the expected return Rs- E 7'r (s*, a²), where y is discount factor and T is the time horizon. The joint action-value function is defined as Qr (St, as) = E,, [Re] St, ar). Each agent's 's individual action-value function is denoted as (o;,,,,).
B.2 IMPLEMENTATION DETAILS OF OUR APPROACH AND BASELINES
The key points of implementing the baselines and our methods are summarized here:
(1) DPN and HPN: The proposed two methods inherently support heterogeneous scenarios since the entity's 's 'type' information has been taken into each entity's 's features. And the sample efficiency can be further improved within homogeneous agents compared to fixedly-ordered representation. For MMM and MMM2, we implemented a only Medivac agent, which uses similar prior knowledge to ASN and UPDe'T, i.e., action semantics. To focus on the core idea of our methods, we omitted these details in the method section.
'rescue-action" module for the
The objective to train the weight selection network of PDN. As stated in the last paragraph of Section 4, all parameters of DPN are trained end-to-end with backpropagation according the RL loss function. The weight selection network and the other networks work cooperatively to minimize the overall RL loss function.
How is achieved of DPN. As described in Section 4.2, for each o,[i], the weight selection net- work outputs the probability of selecting each weight matrix. During the forward pass at training step f, given the parameter snapshot of the weight selection network, the output probability of se- lecting each weight matrix is fixed. For each o.Li]. we select the weight matrix with the maximum probability. However, directly selecting the argmax index is not differentiable. To make the selee- tion process trainable, we apply Straight Through Estimator [7] to get the one-hot encoding of the argmax index. We denote as Pm (o.(i) The weight matrix with the maximum probability can be acquired by P. (o.[i) W.. As selecting the weight matrix with the maximum probability is deterministic process, according to Equation (5), guaranteed.
Besides, to encourage more exploration at the beginning of training, we also add small gumbel noises (Jang al., 2016) to the 'logits' within the epsilon anneal time. Within this interval, PT cannot be strictly guaranteed. When the epsilon anneal schedule is over, PI will be strictly guaranteed. The Straight Through Estimator written in PyTorch is shown below:
21

---

Published as a conference paper at ICLR 2023
no op
randomily generated permutation matrix g1
attack e
X
enemyy
attack
randomly generated
attack @
permutation matrix
shuffle order of the original observation o to generate data
use the same permutation matrix 82 shuffle 'attack action'
and the 'avallable action mask of attack action'
Figure 23: Applying Data Augmentation (DA) to the SMAC benchmark.
def Beniight_trrughh (y_soft, dim)
# Straight Through Estimator.
index w_ max (dim, keepdim=True) [1]
y_hard = th zeross (y_soft) scatter_ (dim, index, 1.0) ret = y_hard y_soft.detach detach + y_soft
return ret
(2) Data Augmentation (DA) (Ye et al., 2020): we apply the core idea of Data Augmentation (Ye et al., 2020) to SMAC by randomly generating number of permutation matrices to shuffle the 'observation', 'state", 'action' and 'available action mask' for each sample simultaneously to generate more training data. An illustration of the Data Augmentation process shown in Fig. A noteworthy detail is that since the attack actions are the observation, the same permutation matrix My that is utilized to permute o enemy should also be applied to permute the 'attack action' and 'available action mask of attack action' as well. The code implemented based on PyMARL2 for fair comparison.
to the enemies in
(3) Deep Set (Zaheer et al., 2017; Li et al., 2021): the only difference between SET-QMIX and the vanilla QMIX is that the vanilla QMIX uses fully connected layer to process the fixedly- ordered concatenation of the m components in o; while SET-QMIX uses a shared embedding layer h ((x,) to separately process each component z; in o; first, and then aggregates all h,s by sum pooling. The code is also implemented based on PyMARL2 for fair comparison.
Following PIC (Liu et al., 2020) and DyAN (Wang et al., 2020b), we apply GNN to the individual Q-network of QMIX (denoted as GNN-QMIX) to achieve permutation-invarian The code is also implemented based on PyMARL2.
(4) GNN:
(5) ASN (Wang et al., 2019): we use the official code and adapt the code to PyMARL2 for fair comparison.
(6) UPDeT (Hu al., 2021b): use the official code and adapt the code to PyMARL2 for fair comparison.
(7) VDN and QMIX: As mentioned in Section 3, vanilla VIN/QMIX uses fixedly-ordered entity- input and fixedly-ordered action-output (both are sorted by agent/enemy indices). Although VDN and QMIX do not explicitly consider the permutation invariance and permutation equivariance prop- function to figure out the input-output relationships accord- ing to their fixed positions, which is implicit and inefficient.
erties, they train permutation-senstt
The codes for the baselines are also published http://iiilbb.oomluulllooooiiiit
22

---

Published as a conference paper at ICLR 2023
C HYPERPARAMETER SETTINGS
For all MARL algorithms we use in SMAC (Samvelyan al., 2019) (under the MIT License), we keep the hyperparameters the same in PyMARL2 (Hu et al., 2021a) (under the Apache License v2.0). We list the detailed hyperparameter settings used the paper below in Table to help peers replicate our experiments more easily.
Table 5: Hyperparameter Settings of VDN-based or QMIX-based Methods.
Parameter Name
Value
Exploration-related
selector
epsilon epsilon_greedy
epsilon_starr Start
1.0
_fiiion
0.05
epsilon anneal time
100000 (500000 for 6h vs 8z)
Sampler-related parallel
runner batch size run buffer size max
8 (4 for 3s5z vs 336z)
5000
10050000
Agent-related
hpn_mac for HPN, dpn_mac for DPN, set_mac for Deep Set, updet_ mac for UPDeT and n namac for others hpn rnn for HPN, dpn_rm rnn for DPN,
mac
agent HPN hidden dim HPN layer num
set rnn for Deep Set, updet rnn for UPDeT and rnn for others
64 (only for HPN)
2 (only for HPN)
permutation_net.dee
64 (only for DPN)
Training-relater
softmax tau learner mixer mixing. lekiingeembed... embed_diee dii
0.5 (only for DPN) learrer qmix or vdn
32 (only for qmix-based)
hypernet_emmn embed Ir lambaa optimizer
64 (only for gmix-bbsed) 0.001
0.6 (0.3 for 6h_vs_8t) adam
target.update interva
200
D COMPUTING ENVIRONMENT
We conducted our experiments on an Intel(R) Xeon(R) Platinum 8171M CPU 2.60GHz processor based system. The system consists of processors, each with 26 cores running 2.60GHz (52 cores in total) with 32KB of L1, 1024 KB of L2, 40MB of unified L3 cache, and 250 GB of memory. Besides, use 2 GeForce GTX 1080 Ti GPUs to facilitate the training procedure. The operating system is Ubuntu 16.04.
E LIMITATIONS
We currently follow the settings of (Qin et al., 2022; Wang et al., 2020b; Hu et al., 2021b; Long et al., 2019; Wang et al., 2019), where the configuration of the input-output relationships and the observation/state structures are set manually.
What if the observations are images or the structural information is not available?
The high-level idea of this paper is to leverage some formats of symmetries to reduce the size of the search space. Since typical MARL benchmarks represent observations factorizable vectors (which can provide more direct and compact information than images), we currently focus on the permutation symmetries, i.e., Pl and PF.
23

---

Published as a conference paper at ICLR 2023
For image inputs, the rotational reflectional symmetries more prominent characteristics. Thus, we could leverage rotation invariance or rotation equivariance to design better MARL algorithms, which is also novel research direction.
For vector inputs, when the structural information unknown, potential solution is:
(1) Learning action representations using forward model. We want to learn action repre- sentations that can reflect the effects actions on the environment and other agents. The effect of an action can be measured by the induced reward and the change in the states.
(2) Using all actions' representations as queries and using all entities" embedded features (potentially generated by HPN) as keys and values, leverage the self-attention mecha- nism to generate the Q-values of each action. Since the self-attention computation is invari- ant to the input entities' order, PI and PE are achieved. And the input-output relationships may be learned implicitly by the self-attention mechanism.
Automatically detecting such structural information is interesting and leave this as future works.
24


Reviews:
[{"review_id": "ucbnG92AKP", "reviewer": "Reviewer_RFWq", "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 permutation invariance (PI) and permutation equivariance (PE) for multi-agent reinforcement learning. Different from existing works which achieve PI and PE via shared embedding of graph nets, the authors proposed a hypernet-based architecture, which is referred to as Hyper Policy Network (HPN). With HPN, the authors built PI input and PE output modules which could be plugged into existing MARL architectures without modifying the backbone network. The proposed approach is evaluated on SMAC, Google Research Football and MPE. The results show that the proposed approach outperforms baseline in various tasks. \n", "summary_of_the_review": "In summary, the reviewer appreciates the proposed HPN, which nicely leverages the structural information of observation and builds the helpful inductive bias to achieve better performance. However, the reviewer thinks the limitations, such as assumption of the structural information of observation, should be more carefully discussed. In addition, empirical results on tasks with more agents are needed to support the claims.", "strength_and_weaknesses": "### Strength: \n\n1. While PI and PE for RL and MARL are widely studied, the idea of using hyper-net to output weight for different input and thus achieve PI and PE are new and interesting. \n\n2. The reviewer appreciates that the proposed approach could be applied to existing architecture without changing the backbone. This is an advantage over existing graph-based PE and PI MARL approaches. \n\n3. It is impressive that the proposed approach outperforms baselines on many super-hard SMAC tasks. \n\n4. The paper is well-written and easy to follow.    \n\n\n### Weakness / Questions:\n\n1. The reviewer has concerns on the assumption that the structural information of observations and the actions’ PI / PE property are available.  This is privileged information that is not used by baselines such as QMIX. This information may not be available in many real-world applications. For instance, suppose the observations are images or some feature vectors that are not interpretable. How do we apply the proposed approach? \n\n2. The reviewer has some concern regarding the scalability. Specifically, suppose there are 100 agents, does the hyper-net need to generate 100 different weights? \n\n3. While the paper highlights ‘break the curse of dimensionality’ and scalability as main contributions, the experiments only report results with few agents. For instance, in MPE, only six agents are considered. In contrast, baseline approaches such as PIC could actually scale to hundreds of agents. Results with more agents are needed to support the claims. \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": "enjSLnyL1B", "reviewer": "Reviewer_ZC3P", "summary": "", "questions": "", "limitations": "", "rating": 8, "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 looks at the intersection of representation learning and MARL. The authors aim to design network architectures that are permutation invariant to reordering of agents in the input representation layer of a MARL network and also consider how to develop some output units that are only equivariant to permutations. The authors propose two architectures towards this end (DPN and HPN) with the idea of keeping the backbone intact, allowing for reuse across a variety of different MARL algorithms. The authors demonstrate significant gains in sample efficiency using HPN and DPN across popular MARL environments and algorithms including on SMAC, MPE, and GRF. ", "summary_of_the_review": "As a reviewer, I found this paper to be a delight. It is clearly written, clearly motivated, and offers a focused yet potentially high impact solution. The experiments are also of extremely high caliber, really providing me with exactly what I would look for as a reviewer.  Ultimately, my consideration was more between strong accept and accept than it was considering that this paper should not be accepted. I believe it will make a nice contribution to the conference and believe it is likely to have a high impact on this subject area. My only concern, which is why I went with accept, is that the novelty of the proposed approach is really not that high in light of past work considering these topics in representation learning. However, I definitely think that this paper makes a strong contribution to the MARL community. \n\nUpdate After Author Feedback: \n\nI agree with the characterization provided by the authors of the source of novelty in their contribution and believe it is a nice addition to the community. ", "strength_and_weaknesses": "Strengths: \n- This paper is well aligned with the conference by demonstrating the value of improved representation learning in complex MARL domains. \n- The PI and PE inductive biases are indeed very common characteristics of MARL problems, making correctly encoding them a fundamental research direction. \n- The paper is clearly written and the proposed approach is clearly justified theoretically.\n- The experiments are very well done. The domains considered are large-scale and commonly used, relevant baselines are considered, important ablations are considered, and the approach is shown to be largely agnostic of the choice of MARL backbone. \n\nWeaknesses: \n- The DPN and HPN architectures are not tremendously novel and utilize well known concepts from the representation learning literature.", "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": "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": "YgEbSk8tKgF", "reviewer": "Reviewer_TTsq", "summary": "", "questions": "", "limitations": "", "rating": 6, "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 focuses on breaking the curse of dimensionality in multi-agent state space by exploiting the permutation invariance and permutation equivariance inductive biases. To achieve this, they proposed two implementations: Dynamic Permutation Network and Hyper Policy Network. A key property of this framework is that they only need to modify the input/output layer, leaving the backbone module unchanged. This property makes the work easy to add to other works. Finally, extensive experiments in SMAC, Google Football and MPE show some strength of this framework.", "summary_of_the_review": "This paper is interesting and the proposed method might be an easy way to be utilized to any other methods in the considered settings. However, the soundness and the empirical evaluations should be further verified. ", "strength_and_weaknesses": "**Strengths**\n\n1. The problem this paper considers is important. How to handle the exponentially increasing dimensionality of state space in MARL is critical and this paper provides a new method to solve it. \n2. The literature review is sufficient. Most previous works have been discussed and compared.\n3. This framework is well-motivated. To solve the curse of dimensionality in state space, using the properties of permutation invariance and equivariance in MARL might be a natural way. Though previous works have discussed these properties, this work has an advantage over others that it only needs to modify the input and output layer.\n\n**Weaknesses**\n\n1. The proposed method is not sound. (1) As discussed in Sec.2, Deep Set & GNN have limited representation capacity, due to the use of shared embedding. However, the proposed framework also uses a shared embedding $h_i$. In Sec.4.3, the hyper net $\\text{hp}_{\\text{in}}$ and module B are all shared. (2) In Sec.4.2, the observation of an entity chooses a weight matrix via probability. There is no guarantee that the entity can always choose the same weight matrix because the probability will change when this entity is in a different state. (3) HyperNet is also shared. What is the difference between $h(o_i,\\theta_h)^\\top\\cdot o_i$ and $f(o_i,\\theta_f)$?\n2. The empirical evaluation results can be improved. This work uses a complex method to match the observation and action belonging to the same entity. What if we just sort the entities according to distance from the focal agent? This might be a strong baseline. \n3. The results are not significant enough compared with baselines considering PI and PE properties, such as UPDeT-QMIX, in Figure 6. \n4. This paper does not provide any discussions of limitations. (1) Is there any observation space or action space that cannot be factored? (2) Do all actions in MARL belong to PI or PE? What if there is an action that can tie *two* enemies together with a rope? The entity-correlated action space might not be a general assumption. ", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "PmvLrU6TmZ", "reviewer": "Reviewer_JeYo", "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 addresses the curse of the dimensionality problem in multiagent reinforcement learning (MARL), where the state-action space grows exponentially as the number of agents increases. To address this challenge, this paper proposes two novel implementations that exploit the permutation invariance (PI) and permutation equivariance (PE) properties. Specifically, the authors introduce the dynamic permutation network (DPN) and hyper policy network (HPN) that can guarantee PI and PE properties. Evaluations in SMAC, Google Research Football, and MPD show that the proposed frameworks outperform competitive baselines. ", "summary_of_the_review": "I would like to initially vote for 6 (marginally above the acceptance threshold). After the authors' response to my concern and questions, I will make a final decision on the recommendation. ", "strength_and_weaknesses": "**Strengths:**\n1. The proposed frameworks can be applied to existing MARL methods by following the minimal modification principle and modifying the input and output layers only.\n2. Experiments are performed using the benchmark domains and show state-of-the-art performance compared to competitive baselines.\n3. The paper is generally well-written and explained clearly. \n\n**Weakness:**\nThis paper is built on three assumptions: 1) the observation and action space are factorized, 2) a different entity order in observation does not affect information (i.e., PI property), and 3) the agent has prior knowledge about the structures of its observation and action space (e.g., in Figure 1, the agent knows which information corresponds to ally and opponent agents and which actions correspond to PI and PE actions). While I agree with the authors that assumptions #1 and #2 generally hold in many MARL settings, assumption #3 can be a strong assumption and can limit the applicability of the proposed framework. For example, the deep set method exploits PI by requiring assumptions #1 and #2, which still hold in model-free MARL. However, to additionally exploit PE, this paper requires assumption #3, which is generally not available for model-free settings. If assumption #3 is strong, it would be beneficial to discuss which potential methods can be used to address assumption #3. \n\n**Questions:**\n1. The related work section states that the representation capacity of the deep set and GNNs is limited due to the use of the shared embedding layer. Do these methods have to use the shared embedding layer? If not, would it be easy to modify these baselines not to use the shared embedding layer and thus improve the representation capacity of these methods?\n2. The problem statement is based on Dec-POMDP, the standard framework for collaborative settings. However, this paper uses competitive setting examples, such as SMAC, so I wonder why the problem statement is based on collaborative settings.\n3. Regarding the PI Input Layer A in Section 4.2, the weight selection network is *learned* to select the corresponding weight matrix. Which objective is used to train the weight selection network? Also, because this network is learned, which can be noisy at the beginning of training, I would like to clarify how PI is guaranteed. ", "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": "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": {}}]

Author rebuttal:

Decision: Accept: poster