Multi-Agent MDP Homomorphic Networks
Authors: Elise van der Pol
Herke van Hoof
Frans A Oliehoek
Max Welling
Venue: ICLR 2022 Poster (2022)
Keywords: multiagent systems
reinforcement learning
equivariance
symmetry

Abstract: This paper introduces Multi-Agent MDP Homomorphic Networks, a class of networks that allows distributed execution using only local information, yet is able to share experience between global symmetries in the joint state-action space of cooperative multi-agent systems. In cooperative multi-agent systems, complex symmetries arise between different configurations of the agents and their local observations. For example, consider a group of agents navigating: rotating the state globally results in a permutation of the optimal joint policy. Existing work on symmetries in single agent reinforcement learning can only be generalized to the fully centralized setting, because such approaches rely on the global symmetry in the full state-action spaces, and these can result in correspondences across agents. To encode such symmetries while still allowing distributed execution we propose a factorization that decomposes global symmetries into local transformations. Our proposed factorization allows for distributing the computation that enforces global symmetries over local agents and local interactions. We introduce a multi-agent equivariant policy network based on this factorization. We show empirically on symmetric multi-agent problems that globally symmetric distributable policies improve data efficiency compared to non-equivariant baselines.

Published as a conference paper at ICLR 2022
MULTI-AGENT MDP HOMOMORPHIC NETWORKS
Elise van der Pol
Herke van Hoof
UvA-Bosch Deltalab University of Amsterdam
UvA-Bosch Deltalab
University of Amsterdam
e vanderpol@uvaa
v.nhoo aaaanoof@uva...
Frans A. Oliehoek
Max Welling
Department of Intelligent Systems Delft University Technologg www.eoekk@uddelll.....eeee ft..nf.ll
UvA-Bosch Deltalab
University Amsterdam
m. we 1 ng@uva .nl
ABSTRACT
This paper introduces Multi-Agent MDP Homomorphic Networks, class networks that allows distributed execution using only local information, yet is able to share experience between global symmetries in the joint state-action space cooperative multi-agent systems. In cooperative multi-agent systems, complex symmetries arise between different configurations of the agents and their local observations. For example, consider group of agents navigating: rotating the state globally results in a permutation of the optimal joint policy. Existing work on symmetries in single agent reinforcement learning can only be generalized to the fully centralized setting, because such approaches rely on the global symmetry the full state-action spaces, and these can result in correspondences across agents, To encode such symmetries while still allowing distributed execution we propose a factorization that decomposes global symmetries into local transformations. Our proposed factorization allows for distributing the computation that enforces global symmetries over local agents and local interactions. We introduce a multi-agent equivariant policy network based on this factorization. We show empirically on symmetric multi-agent problems that globally symmetric distributable policies improve data efficiency compared to non-equivariant baselines.
INTRODUCTION
Equivariant and geometric deep learning have gained trac- tion in recent years, showing promising results in super- vised learning (Cohen & Welling 2016 Winkels Cohen, 2018 Weiler et al. 2018] Weiler & Cesal 2019 Worrall
rotate
ct al. 2017 Fuchs al. 2020 Thomas et al. 2018). un- supervised learning (Dey et al.
2021) and reinforcement
learning (yan der Pol et al. 2020) Simm et al., 2021).
policy
policy
single agent reinforcement learning, enforcing equivari- ance to group symmetries has been shown to improve data efficiency, for example with MDP homomorphic networks (van der Pol et al.) 2020), trajectory augmen- tation (Lin et 2020 Mavalankar 2020), or symmetric locomotion policies (A Abbolhosssein et al. 2019). Equiv- ariance enables an agent to learn policies more efficiently within its environment by sharing weights between state- action pairs that are equivalent under transformation. As result of this weight sharing, the agent implicitly learns policy in a reduced version of the MDP. We are interested in cooperative multi-agent reinforcement learning, where symmetries exist both in the global environment, and be- tween individual agents in the larger multi-agent system.
permute
Figure Example of global multi- agent symmetry. When rotated state occurs in the environment the optimal policy is permuted, both between and within agents.
Existing work symmetries in single

---

Published as a conference paper at ICLR 2022
agent reinforcement learning can only be generalized to the fully centralized multi-agent setting, because such approaches rely on the global symmetry in the full state-action spaces and these can result in correspondences across agents, shown in Figure Thus, such approaches cannot be used in distributed multi-agent systems with communication constraints. Here, we seek to be equivariant global symmetries of cooperative multi-agent systems while still being able to execute policies in distributed manner.
Existing work in deep multi-agent reinforcement learning has shown the potential of using permutation symmetries and invariance between agents (Liu et al. 2019 Jiang et al. 2020 Sunehag et al. 2017
Robbel al., 2016; Böhmer al. 2020 2020 Sukhbaatar et al. 2016 van der Pol & Oliehoek 2016) Such work takes an anonymity view of homogeneous agents, where the agent's ' observations matter for the policy but not its identity. Using permutation symmetries ensures extensive weight sharing between agents, resulting in improved data efficiency. Here, we go beyond such permutation symmetries, and consider more general symmetries of global multi-agent systems, such as rotational symmetries.
In this paper, we propose Multi-Agent MDP Homomorphic Networks, class of distributed policy networks which are equivariant to global symmetries of the multi-agent system, as well as to standard permutation symmetries. Our contributions are as follows. (i) We propose a factorization of global
symmetries in the joint state-action space of cooperative multi-agent systems. (ii) We introduce a multi-agent equivariant policy network based on this factorization. (iii) Our main contribution is an approach to cooperative multi-agent reinforcement learning that is globally equivariant while requiring only local agent computation and local communication between agents at execution time. We evaluate Multi-Agent MDP Homomorphic Networks on symmetric multi-agent problems and show improved data efficiency compared non-equivariant baselines.
RELATED WORK
Symmetries in single agent reinforcement learning Symmetries in Markov Decision Processes have been formalized by Zinkevich & Balch (200T); Ravindran & Barto (2001). Recent work
symmetries in single agent deep reinforcement learning has shown improvements in terms of data
efficiency. Such work revolves around symmetries in policy networks (van der Pol al. 2020 Simm
et al. 2021), symmetric filters (Clark & Storkey (2015), invariant data augmentation (Laskin et al.
2020 Kostrikov al.) 2021 or equivariant trajectory augmentation (Lin al., 2020 Mavalankar
2020 Mishra et al. (2019) These approaches are only suitable for single agent problems or centralized
multi-agent controllers. Here, we solve the problem of enforcing global equivariance while still allowing distributed execution.
Graphs and permutation symmetries in multi agent reinforcement learning Graph-based methods in cooperative multiagent reinforcement learning are well-explored. Much work is based around coordination graphs (Guestrin et al. 2002b Kok & Vlassis 2006), including approaches that approximate local Q O-functions with neural networks and max- plus find a joint policy (van der networks to find joint policies value functions JJing al. 2020 Sukhbaatar al. 2016). In deep learning for multi-agent systems, the use of permutation symmetries is common, either through explicit
Pol & Oliehock 2016 Böhmer et al.) 2020). and approaches that use graph-structune
formulations (Sunchag al. 2017 Böhmer et al. 2020) or through the use of graph or message
passing networks (Liu et al., [019 Jiang et al. 2020 Sukhbaatar et al.) (2016). Policies in multi-agent systems with permutation symmetries between agents are also known as functionally homogeneous policies (Zinkevich & Balch (001)) or policies with agent anonymity (Robbel et al. [2066] Varakan tham et 20.120 Here, we move beyond permutation symmetries a broader group of symmetries in multiagent reinforcement learning.
Symmetries in multi agent reinforcement learning Recently, Hu et al. (2020) used knowledge of symmetries to improve pero-shot coordination in games which require symmetry- -rreatt...b Here, we instead use symmetries in cooperative multi-agent systems to improve data efficiency by parameter sharing between different transformations of the global system.
2

---

Published as a conference paper at ICLR 2022
91
92
93
Figure 2: The orbit of global traffic light state under the group of 90 degree rotations.
BACKGROUND
In this section we introduce the necessary definitions and notation used in the rest of the paper.
3.1 MULTI-AGENT MDPS
We will start from the definition of Multi-Agen MDPs, class of fully observable cooperative multi-agent systems. Full observability implics that each agent can execute the same centralized policy. Later
will define distributed variant of this type of decision making problem.
Definition A Multi-Agent Markov Decision Process (MMDP) (Boutilier 1996) is tuple (N, S, A,T, R) where N a set of m agents, is the state space, A A x... X Am is the joint action space of the MMDP, T S x A x ... x Am x - [0, 1] is the transition function, and A x x Am + R is the immediate reward function.
The goal of an MMDP, as in the single agent case, is to find joint policy that maps states to probability distributions over joint actions, π S - (AA), (with A(A) the space of such distributions) to maximize the expected discounted return of the system, R = BB k== **+++++1] with E [o. 1] discount factor. An MMDP can be viewed as a single-agent MDP where the agent takes joint actions.
3.2 GROUPS AND TRANSFORMATIONS
In this paper will refer extensively group symmetries. Here, will briefly introduce these concepts and explain their significance to discussing equivalences of decision making problems.
group G with binary operator that obeys the group axioms: identity, inverse, closure, and associativity. Consider as running example the set of 90 degree rotations (0",90" 1800, 270" J. which we can write rotation matrices:
cos f
sin sin 0 cos 0
R(0)
with 0 E (0, 2, 3x Composing any two matrices this set results in another matrix in the set, meaning the is closed under composition. For example, composing R(5) and R(x) results in another member the set, in this case R( 3オ Similarly, each member of the set has inverse that is also in the set, and R(0) is an identity element. Since matrix multiplication is associative, the group axioms are satisfied and the set a group under composition.
group action is function G x X - X that satisfies exr x (where is the identity element) and (g. h)a = g. (hæ). For example, the group of 90 degree rotation matrices acts on vectors to rotate them. Similar to the action of this group vectors. can define action of the same group image space: e.g., the NumPy (Harris et al. 2020) function np rot9 acts on the set images. will consider group actions the set of states represented image observations, We match these with group actions on policies. Since we consider discrete action spaces, a group element g acting on policy will be represented
matrix multiplication of the policy with permutation matrix.
When discussing symmetries decision making problems, we identify sets of sate-action pairs that equivalent: if the state is transformed, the policy should be transformed well, but potentially

---

Published as a conference paper at ICLR 2022
with different representation of the transformation. See Figure I We are interested in the case where the reward and transition functions are invariant in the orbit of state-action pairs under a symmetry group. The orbit of point E V, with V vector space, is the set of all its transformations (c.g. all rotations of the point), defined as (w) = {gulvg E G). The orbit of a point under group forms an equivalence class. See Figure for example of orbit of traffic light state.
DISTRIBUTING SYMMETRIES OVER MULTIPLE AGENTS
Consider the cooperative traffic light control system in Figure 1 that contains transformation- equivalent global state-action pairs. We first formalize global symmetries of the system similarly to symmetries in single agent MDP. Then we will discuss how we can formulate distributed symmetries in distributed MMDP. Finally, we introduce Multi-Agent MDP Homomorphic Networks.
4.1 SYMMETRIES IN MMDPS
We define symmetries in an MMDP similar to an MDP with symmetries (van der Pol et al. 2020).
Definition 2 An MMDP an MMDP with symmetries if reward and transition functions are invariant under a transformation group G. That is, the MMDP has symmetries if there is at least one non-trivial group G of transformations Lg
and for every s, K2 -> A such that
R(s, a) = R[Lg Kglal) T(s, a,, - I Ki
(g]aa)
Vg E S, Vg G,s,s E E,
(3)
If two state-action pairs s, and [s] K2 obey Eq. 2 and then they are equivalent (van der Pol et al. 2020). Consider as example the symmetries Figure These symmetries can resull in correspondences across agents, for example when the observation of agent is mapped by the symmetry another agent j that is arbitrarily far away and with which there is no communication channel. In the next section, we will resolve this problem by defining distributed symmetries in terms of local observations and the communication graph defined by the state.
If we have an MMDP with symmetries, that means that there are symmetric optimal policies, i.e. if the state of the MMDP transforms, the policy transforms accordingly. The above definition of an MMDP with symmetries is only applicable to the centralized setting. If we want to be able to execute policies a distributed manner, we will need to enforce equivariance in distributed manner.
4.2 DISTRIBUTED MULTI-AGENT SYMMETRIES
In distributed MMDP, agents make decisions based local information only, i.c. the local states they observe, and the communications they receive from neighbors, defined as follows:
Definition A Distributed Multiagent Markov Decision Process (Distributed MMDP) (W. S, A. T, R) is MMDP where agents communicate specified by graph g G-V.& -V.E) with one node 0 E V per agent and an edge (i.j) E E if agents i and j can communicate. Thus, = (1S.)ieNs (Ee (G.jEe)) with S; the of state features observable by agent i, which may include shared global features, and Fij the set of edge features between i and j. In a distributed MMDP, each agent's 's action can only depend on the local state and the communications it receives
Here, we focus on Distributed MMDPs which have a spatial component, i.e. each agent has a coordinate in some space, and the attributes of the edges between the agents in the communication graph contain spatial information as well. For instance, the attributes eij E for edge (i,j) might be the difference vector between agent and agent j's coordinates. Since both agent observations and interaction edges have spatial features, a global symmetry will affect both the agent observations, the agent locations, and the features on the interaction edges. See Figure
To allow a globally equivariant policy network with distributed exccution, we might naively decide to restrict each agent's 's local policy network to be equivariant to local transformations. However, this
CCommunication is constrained, i.e. agents cannot simply share their full observations with each other.
4

---

Published as a conference paper at ICLR 2022
permute observations
transform edges
rotate observations
original
symmetric
Figure 3: Example of how global transformation of a distributed traffic light control state be viewed as I) permutation of the observations over the agents, 2) permutation of the interaction edges, 3) transformation of the local observations.
does not give us the correct global transformation, as joining the local transformations does not give us the same the global transformations, illustrated in Figure
Instead, to get the correct transformation as shown in the left side of Figure the local state is transformed, but also its position is changed, which be the agents and their neighbors. To give an example of the equivariance constraint that we want impose: the lower left agent (before transformation) should select an action based on its local state and communication received from its northern and eastern neighbor, while the top left agent (after transformation) should select the transformed version of the action based on its rotated local state and communication from its eastern and southern neighbor.
permutation of
Since the agent has no other informa- tion about the system, if the local ob- servations are transformed (e.g. ro- tated), and the messages receives transformed similarly, then from a local perspective the agent is in an equivalent state and should execute the same policy, but with an equiva- lently transformed action.
From the perspective our agent and all its neighbors, the equivalence holds for this local subgraph as well: if the observations and local interac- tions rotate relative to each other, then the whole subgraph rotates. See Fig- ure 3 Thus, long as the transfor- mations are applied the full set of observations and the full set of com- munications, we have a global sym- metry. We therefore propose the following definition of Distributed MMDP with Symmetries.
Figure 4: Example of the difference between global trans- formation the global state, and a of local transforma- lions on local states. On the left we rotate the entire world by 90 degrees clockwise, which involves rotating crossings and streets. On the right we perform local uncoordinated transformations only at the street level. The latter not symmetry of the problem.
Definition Let s = ([siheNs (egTG.EEE). Then a Distributed MMDP with symmetries a Distributed MMDP for which the following equations hold for at least one non-trivial set of group transformations Lg + S and for every s, Kg > A such that
R(s, a) = R(T. (s), KT(al)
Vg G,
(4)
T(s, a,s') = [() K Kyla),,,sss))
Vg G,s,s' E S,
(5)
where equivalently to acting on with Lg. we can act on the interaction and agent features separately with Lg and Ug. end up in the same global state:
[s (L.l(in)) [U (U, (ess)o..)e)))
(6)
for T.g S, Sr. Ug E E,, and P3 and Pe the state and edge permutations.
5

---

Published as a conference paper at ICLR 2022
Here, E is the set of edge features. The symmetries acting the agents and agent interactions in the Distributed MMDP are a class of symmetries we call distributable symmetries. We have now defined class of Distributed MMDPs with symmetries for which distribute global symmetry into set of symmetries on agents and agent interactions. This distribution allows us to define distributed policies that respect the global symmetry.
4.3 MULTI-AGENT MDP HOMOMORPHIC NETWORKS
We have shown above how distributable global symmetries can be decomposed into local symmetries on agent observations and agent interactions. Here, we discuss how implement distributable symmetries in multi-agent systems in practice.
4.3.1 GENERAL FORMULATION
We want to build a neural network that 1) allows distributed execution, so that we can compute policies without centralized controller 2) allows us to pass communications between agents (agent interactions), to enable coordination and 3) exhibits the following global equivariance constraint:
(L(L)())) = Hy [s()
with H. 11 + II. Thus, the policy network ने that outputs the joint policy must be equivariant under group transformations of the global state. To satisfy 1) and 2), i.c. allowing distributed execution and agent-to-agent communication, as well as permutation equivariance, formulate the network message passing network (MPN), but with global equivariance constraints.
H [ MPN [L. i$))
(8)
Since network is end-to-end equivariant if all its layers equivariant with matching representa- tions (Cohen & Welling 2016), we require layer-wise equivariance constraints on the layers. A single
layer in an MPN is given by a set of node updates, i.e. f((+1) = tu (J IMAil &m (ee) (e)):,))))
with 13 the current encoding of agent j layer I, dm the message function that computes mi based the edge eij and the current encoding of agent j, and Φ. the node update function that updates agent i's current encoding based on f!" and the aggregated received message m. Since the layer is given by set of node updates, the equivariance constraint on the node updates. In other words, &u must be an equivariant function of local encoding f!") and aggregated message m!
Pg (o m [P]] ou (EaLf L,(mm!
Thus, the node update function du is constrained to be equivariant to transformations of inputs (1) and m!) Therefore, to conclude that the outputs of Φ., transform according Pg. we only need to enforce that its inputs Sa and my transform according to Lg. Thus, the subfunction di.. that computes the messages m (1) must be constrained to be equivariant as well. Since &m takes as input the previous layer's 's encodings well as the edges Cij. this means that 1) the encodings must contain geometric information about the state, e.g. which rotation the local state is in and 2) the edge attributes contain geometric information well, i.e. they transform when the global state transforms (Appendix B
IAGI
Lg
m
oi (Ug (eg)) (0)
(10)
Note that this constraint is satisfied when om is equivariant, since linear combinations of equivariant functions are also equivariant (Cohen & Welling 2017). Putting this all together, the local encoding f: for each agent is equivariant to the set of edge rotations and the set of rotations of encodings in the previous layer. For more details, see Appendix B Thus, we now have the general formulation of Multi-Agent MDP Homomorphic Networks. At execution time, the distributed nature of Multi- Agent MDP Homomorphic Networks allows them to be copied onto different devices and messages exchanged between agents only locally, while still enforcing the global symmetries.

---

Published as a conference paper at ICLR 2022
4.3.2 MULTI-AGENT MDP HOMOMORPHIC NETWORK ARCHITECTURE
Multi-Agent MDP Homomorphic Networks consist of equivariant local observation encoders Φe S - R ( where Gs the group, |G] is its size, and D the dimension of the encoding, equivariant local message functions 6m & x R
x + R [ where F is dimension of the message encoding, equivariant local update functions dw. R G x R ||G|XF + RIG|XD and equivariant local policy predictors Φx R G + II..A.) Take the example of multi-agent traffic light control with 90 degree rotation symmetries, which we evaluate on in Section [5]
In this setting, we wish to constrain de to be equivariant to rotations Rg of the local observations. We will require the outputs of Φe. to
permute according to L whenever the input rotates by Rg.
by [o. de [s:]) E
(1I)
This has the form of a standard equivariance constraint, which allows conventional approaches to enforcing group equivariance, e-g. (Cohen & Welling, 2016). In this paper, we will enforce group equivariance using the Symmetrizer (van der Pol et al., 2020). Before training, the Symmetrizer enforces group (e.g. rotational) symmetries by projecting neural network weights onto an equivariant subspace, and then uses SVD to find basis for the equívariant subspace. Then, during and after training, the weight matrix of the neural network is realised as a linear combination of equivariant basis weights, and the coefficients of the linear combination PPO (Schulman et al. 2.17). We use ReLU non-linearinn lincaritiiies and regular representations. For more details on the Symmetrizer, refer the reader to van der Pol et al. (2020).
updated during training with
After encoding the input observations with the equivariant encoding function de. we have an equivari- ant encoding of the local states that has compositional form: the rotation of the state is represented by the ordering of group channels (see yan der Pol et al. (2020)) and the other state features are repre- constrain the message update functions to
sented by the information in those channels. Similarly, be equivariant to the permutation Lg in the group channels of the state encodings and the rotation U. of a difference vector eij. representing the edge (i.j):
Lg @m (cs).,9)) = oi (Ug Lg [150]
(12)
Since linear combinations of equivariant functions are equivariant as well (Cohen & Welling 2017 the aggregated message m. = Σ/ [4Gil mj-.; is equivariant too.
While egy and , transform under the same group G, they do not transform under the same group action: esy is a vector that transforms with a rotation matrix, whereas f/ transforms with a permutation of group channels. The question arises how build group equivariant layers that transform both the edge and the agent features appropriately. The method we use is to build equivariant layers using direct sum representations, where the representations Ug and L.g are combined follows:
Tg = U, + Ly = Ug
(13)
Lg
where O represents a zero-matrix of the appropriate size. Consider a weight matrix W acting on Eeg
The equivariance constraint then becomes W Lg LW)
To preserve the geometric information coming from the messages, the node update function is similarly constrained to be equivariant. Importantly, the permutation on the outputs of &n must match the permutation on the inputs of the next layer's @m (i.e. the output of one layer must use the same group representation as the input of the next layer). This ensures that we can add multiple layers together while preserving the geometric information. In practice, it is convenient to use a single representation Ly for all permutation representations.
Lg @u (t.) .m.!) = du 1,
(14)
Finally, after M layers (M message passing rounds), we output local equivariant policies based on the state encodings at layer M using local policy network æ::
Ln [ [] Pa (F! [S(
(15)
Here, Py is the permutation representation on the actions of the individual agent, e.g. if in a grid world the state is flipped, Pa is the matrix that permutes the left and right actions accordingly.
7

---

Published as a conference paper at ICLR 2022
Batuur
Standard
Standard
Augmented
Augmenced
susmented
Augmented
200
400
000
500 1000
0
202
400
500
800
1000
Time steps
Time shaps 500)
(a) agents.
(b) agents.
Figure 5: Results for the distributed drone wildlife monitoring task. 25% 50% and 75% quantiles shown over 15 random seeds. All approaches tuned over 6 learning rates.
EXPERIMENTS
The evaluation of Multi Agent MDP Homomorphic networks has singular goal: to investigate and quantify the effect of distributed versions of global equivariance symmetric cooperative multi-agent reinforcement learning. We compare to three baselines. The first is non non-homomorphic variant of our network. This is a standard MPN, which is a permutation equivariant multi-agent graph network but not equivariant global rotations. The other two variants with symmetric data augmentation, in the spirit of (Laskin et al. 2020; Kostrikov et al., (202T). For stochastic data augmentation baseline, on each forward pass one of the group elements is sampled and used transform the input, and appropriately transform the output as well. For a full augmentation baseline, every state and policy augmented with all its rotations in the group. For evaluation,
use the common centralized training, decentralized execution paradigm (Kraemer & Banerjee 2016 Olichock et al. (2008) (see Appendix[A]ic for more details). We train which will adjust the coefficients of the weight matrices in the network. The information available to the actors and crities their local information and the information received from neighbors. We first evaluate a wildlife monitoring task, variant of predator-prey type problems with pixel-based inputs where agents can have information none the other agents have. Additionally, we evaluate the networks the more complex coordination problem of traffie light control, with pixel-based inputs. We focus on C4 as the discrete group to investigate whether equivariance improves aulti-agent systems, C4 has been shown to be effective in supervised learning and single-agent settings.
centralized fashion, with PPO (Schulman
2017).
5.1 WILDLIFE MONITORING
Setup We evaluate on a distributed wildlife monitoring setup, where set of drones has to coordinate trap poachers. To trap poacher, one drone has to hover above them while the other assists from the side, and for each drone that assists the team receives +1 reward. Two drones cannot be in the same location at the same time. Since the drones have only cameras mounted at the bottom, they cannot see each other. The episode ends when the poacher is trapped by at least 2 drones, or 100 time steps have passed. On each time step the team gets -0.05 reward. poacher) can stand still move in the compass directions. The poacher samples actions uniformly. We train for 500k time steps. The drones can send communications to drones within a by 3 radius around their current location, meaning that the problem is distributed MMDP. Due to changing agent locations and the limited communication radius, the communication graph is dynamic and change between time steps. The observations are 21 by 21 images representing a agent-centric view of 7 by 7 toroidal grid environment that shows where the target is relative to the drone. While the grid toroidal, the communication distance is not: the edges of the grid, communication is blocked. This problem exhibits 90 degree rotations: when the global state rotates, the agents' local policies should permute, and so should the probabilities assigned to the actions in the local policies.
agents (including the
Results Results for this task are shown in Figure 5] with on the y-axis the average return and on the x-axis the number of time steps. In both the 3-agent and 4-agent case, using Multi-Agent
8

---

Published as a conference paper at ICLR 2022
MDP Homomorphic Network improves compared using MPNs without symmetry information, and compared to using symmetric data augmentation. We conclude that in the proposed task, our approach learns effective joint policies in fewer environment interactions compared to the baselines.
5.2 TRAFFIC LIGHT CONTROL
For second experiment, we focus on a more complex coordination problem: reducing vehicle wait times in traffic light control. Traffic light control constitutes a longstanding and open problem (see Wei et al.] (2019) for an overview): not only is the optimal coor- dination strategy non-obvious, traffic light control is problem where wrong decisions can quickly lead to highly suboptimal states due to congestion. We use this setting to answer the following question: does enforcing symmetries help in complex coordination problems?
Standard MPN
Setup We use a traffic simulator with four traffic lights. On each of eight entry roads, for 100 time steps, a vehicle enters the simulation on each step with probabil- ity 0.1. Each agent controls the lights of single intersection and has local action space of (grgr, rgrg), indicating which two of its four lanes get red or green light. Vehicles move rate of one unit per step, unless they are blocked by a red light or a vehicle. If blocked, the vehicle needs step to restart. The goal is reducing the av- erage vehicle waiting time. The simulation ends after all vehicles have exited the sys- tem, or after 500 steps. The team reward is 1000 è Eeeo w(c), with C' the vehicles
16-
Stoch, Augmented MPN Full Augmented MPN Equivariant MPN
Average Weit Time
200
400
600
800
1000
Time: stops 500)
Figure 6: Average vehicle wait times for distributed set- tings of the traffic light control task. Graphs show 25%, 50% and 75% quantiles over 20 independent training runs. All approaches tuned over 6 learning rates.
in the system and wcc) vehicle c's cumulative waiting time.
Results We show results in Figure While the standard MPN architecture had reasonable perfor- mance on the toy problem, it takes many environment interactions to improve the policy in the more complex coordination problem presented by traffic light control. Adding data augmentation helps slightly. However, we see that enforcing the global symmetry helps the network find an effective policy much faster. In this setting, the coordination problem is hard to solve: in experiments with centralized controllers, the standard baseline performs better, though is still slower to converge than the cquivariant centralized controller. Overall, enforcing global symmetries in distributed traffic light control leads to effective policies in fewer environment interactions.
6 CONCLUSION
We consider distributed cooperative multi-agent systems that exhibit global symmetries. In particular, we propose a factorization of global symmetries into symmetries on local observations and local interactions. On this basis, we propose Multi-Agent MDP Homomorphic Networks, class of policy networks that allows distributed execution while being equivariant to global symmetries. We compare non- euuivvaaaai distributed networks, and show that global equivariance improves data efficiency on both predator-pres variant, and on the complex coordination problem of traffic light control.
Scope We focus on discrete groups. For future work, this could be generalized by using steerable representations, at the cost of not being able to use pointwise nonlinearities. We also focus on discrete actions. This might be generalized by going beyond action permutations, e.g., for 2D continuous worlds continuous rotation of the actions. Furthermore, our approach uses group channels for each layer (regular representations). For small groups this is not issue, but for much larger groups this would require infeasible computational resources. Finally, this work has focused on exact symmetries and considers imperfect symmetries and violations of symmetry constraints promising future topic.

---

Published as a conference paper at ICLR 2022
7 ACKNOWLEDGMENTS
We thank lan Gemp, Pascal Mettes, and Patrick Forré for helpful comments.
F.A.O. received funding from the European Research under the European Union's Horizon 2020 research and innovation programme (grant agreement No. 758824 INFLUENCE).
Council
(ERC)
erc
8 ETHICS STATEMENT
Our work has several potential future applications, e.g. autonomous driving, decentralized smart grids or robotics. Such applications hopefully have positive societal impact, but there are also risks of negative societal impact: through the application itself (e.g. military), labor market impact, or by use in safety-critical applications without proper verification and validation. These factors should be taken into account when developing such applications.
REPRODUCIBILITY STATEMENT
To ensure reproducibility, we describe our setup the Experiments section and we include hy- perparameters, group actions, and architecture details in the Appendix. Our code is available at https://github. wtt.ccoom/meeee ccmm//iisseeaaderro////e homomorphic networks
REFERENCES
Farzad Ahdolhosseini, Hung Yu Ling, Zhaoming Xie, Xue Bin Peng, and Michiel van de Panne. On learning symmetric locomotion. In ACM SIGGRAPH Motion, Interaction, and Games, 2019.
Wendelin Böhmer, Vitaly Kurin, and Shimon Whiteson. Deep coordination graphs. International Conference on Machine Learning. PMLR, 2020.
Craig Boutilier. Planning, learning and coordination in multiagent decision processes. In Proceedings of the 6th Conference Theoretical aspects of rationality and knowledge, 1996.
Christopher Clark and Amos Storkey. Teaching deep convolutional neural networks to play Go. International Conference on Machine Learning, 2015.
Taco Cohen and Max Welling. Group equivariant convolutional networks. In International Conference on Machine Learning. 2016.
Taco S. Cohen and Max Welling. Steerable CNNs. In International Conference on Learning Representations, 2017.
Neel Dey, Antong Chen, and Soheil Ghafurian. Group equivariant generative adversarial networks.
In International Conference Learning Representations, 2021. URL /RLp:ttpp////oeeeeewiie
net put/fooae www.uoorumdiooo Ig
Fabian B Fuchs, Daniel E Worrall, Volker Fischer, and Max Welling, SE (3)-transformers: 3d roto- translation equivariant attention networks. Advances in Neural Information Processing Systems, 2020.
Carlos Guestrin, Daphne Koller, and Ronald Parr. Multiagent planning with factored MDPs. In Advances in Neural Information Processing Systems, 2002a.
Carlos Guestrin, Michail Lagoudakis, and Ronald Parr. Coordinated reinforcement learning. Interna- tional Conference on Machine Learning, 2002b.
Charles R. Harris, K. Jarrod Millman, Stéfan J van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel J. Smith, Robert Kern, Matti Picus. Stephan Hoyer, Marten H. van Kerkwijk, Matthew Brett, Allan Haldane, Jaime Fernández del Río. Mark Wiebe. Pearu Peterson, Pierre Weckesser, Hameer Abbasi, Christoph Gohlke, and Travis Oliphant. Array programming with NumPy. Nature, 585, 2020.
Kevin Sheppard, Tyler Reddy, Warren
10

---

Published as a conference paper at ICLR 2022
Hengyuan Hu, Adam Lerer, Alex Peysakhovich, and Jakob Foerster. "Other-play" for zero-shot
coordination. International Conference on Machine Learning, 2020.
Jiechuan Jiang, Chen Dun, Tiejun Huang, and Zongqing Lu. Graph convolutional reinforcement
learning. In International Conference Learning Representations, 2020.
Jelle R Kok and Nikos Vlassis. Collaborative multiagent Journal of Machine Learning Research, 7, 2006.
religgentriinnoreemmmnt reinforcement learnn by payoff propagation.
Ilya Kostrikov, Denis Yarats, and Rob Fergus. Image augmentation is all you need: Regularizing deep reinforcement learning from pixels. International Conference on Learning Representations, 2021.
Landon Kraemer and Bikramjit Banerjee. Multi-agent reinforcement learning as a rehearsal for decentralized planning. Neurocomputing, 190, 2016.
Lior Kuyer, Shimon Whiteson, Bram Bakker, and Nikos Vlassis. Multiagent reinforcement learning for urban traffic control using coordination graphs. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases. Springer, 2008
Michael Laskin, Kimin Lee, Adam Stooke, Lerrel Pinto, Pieter Abbeel, and Aravind Srinivas. Reinforcement learning with augmented data. Advances in Neural Information Processing Systems, 2020.
Yijiong Lin, Jiancong Huang. Matthieu Zimmer, Yisheng Guan, Juan Rojas, and Paul Weng. Invariant transform experience replay: Data augmentation for deep reinforcement learning. IEEE Robotics and Automation Letters, 2020.
Iou-Jen Liu, Raymond A. Yeh, and Alexander G. Schwing. PIC: Permutation invariant critic for multi-agent deep reinforcement learning. In Conference on Robot Learning, 2019.
Aditi Mavalankar. Goal-conditioned batch reinforcement learning for rotation invariant locomotion. arXiv preprint 200hv:2004.08356 2020.
Shruti Mishra, Abbas Abdolmaleki, Arthur Guez, Piotr Trochim, and Doina Precup. Augmenting learning using symmetry in a biologically-inspieee domain. arXiv preprint arX1v:1910.00528, 2019.
Frans A Oliehoek, Matthijs TJ Spaan, and Nikos Vlassis. Optimal and approximate Q-value functions for decentralized POMDPs. Journal of Artificial Intelligence Research, 32, 2008.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary De Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in PyTorch. In NIPS Autodiff Workshop, 2017.
Balaraman Ravindran and Andrew G. Barto. Symmetries and model minimization in Markov decision processes. Technical report, University of Massachusetts, 2001.
Philipp Robbel, Frans A Oliehoek, Mykel J Kochenderfer, et al. Exploiting anonymity in approximate linear programming: Scaling to large multiagent MDPs. Thirtieth AAAI Conference on Artificial Intelligence, 2016.
Victor Garcia Satorras and Max Welling, Neural enhanced belief propagation on factor graphs. In International Conference on Artificial Intelligence and Statistics. PMLR, 2021.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.08 063477 2017.
Gregor NC Simm, Robert Pinsler, Gábor Csányi, and José Miguel Hernández-Lobato Symmetry- aware actor-critic for 3d molecular design. International Conference on Learning Representations, 2021.
Adam Stooke and Pieter Abbeel. rlpyt: A research code base for deep reinforcement learning in Pytorch. In
2019.
11

---

Published as a conference paper at ICLR 2022
Sainbayar Sukhbaatar, Arthur Szlam, and Rob Fergus. Learning multiagent communication with backpropagation. In Advances in Neural Information Processing Systems, 2016.
Peter Sunehag, Guy Lever, Audrunas Gruslys, Wojciech Marian Czarnecki, Vinicius Zambaldi, Max Jaderberg, Mare Lanctot, Nicolas Sonnerat, Joel Z Leibo, Karl Tuyls, et al. Value-decomposition networks for cooperative multi-agent learning. arXiv preprint (oxXi::706.05222. 2017.
Nathaniel Thomas, Tess Smidt, Steven Kearnes, Lusann Yang, Li Li, Kai Kohlhoff, and Patrick Riley. Tensor field networks: Rotation-and cunslation-equivaatie neural networks for 3d point clouds. arXiv preprint arXiv: 1802.08/00 2018.
Elise van der Pol and Frans A Oliehoek. Coordinated deep reinforcement learners for traffic light control. Proceedings of Learning, Inference and Control of Multi-Agent Systems (at NIPS 2016), 2016.
Elise van der Pol. Daniel E. Worrall, Herke van Hoof, Frans Oliehoek, and Max Welling, MDP homomorphic networks: Group symmetries in reinforcement learning. In Advances in Neural Information Processing Systems, 2020.
Pradeep Varakantham, Yossiri Adulyasak, and Patrick Jaillet. Decentralized stochastic planning with anonymity in interactions. In Proceedings of the AAAI Conference on Artificial Intelligence. volume 28, 2014.
Hua Wei, Guanjie Zheng, Vikash Gayah, and Zhenhui Li, A survey on traffic signal control methods. arXiv preprint arXiv: 1904.09441111111 17, 2019.
Maurice Weiler and Gabriele Cesa. General E())-equivariant steerable CNNs. In Advances in Neural Information Processing Systems, 2019.
Maurice Weiler, Mario Geiger, Max Welling, Wouter Boomsma, and Taco Cohen. 3D steerable CNNs: Learning rotationally equivariant features volumetric data. Advances Neural Information Processing Systems, 2018.
Marysia Winkels and Taco S. Cohen. 3D G-CNNs for pulmonary nodule detection. In Medical Imaging with Deep Learning Conference, 2018.
Daniel E. Worrall, Stephan J. Garbin, Daniyar Turmukhambetov, and Gabriel J. Brostow. Harmonic networks: Deep translation and rotation equivariance. IEEE Conference on Computer Vision and Pattern Recognition, 2017.
KiJung Yoon, Renjie Liao, Yuwen Xiong, Lisa Zhang, Ethan Fetaya, Raquel Urtasun, Richard Zemel, and Xaq Pitkow, Inference in probabilistic graphical models by graph neural networks. In 2019 53rd Asilomar Conference on Signals, Systems, and Computers. IEEE, 2019.
Martin Zinkevich and Tucker Balch. Symmetry in Markov decision processes and its implications for single agent and multi agent learning. International Conference on Machine Learning. 2001.
12

---

Published as a conference paper at ICLR 2022
A MESSAGE PASSING NETWORKS, COMMUNICATION, AND DISTRIBUTION
Message passing algorithms are commonly used to coordinate between agents while allowing for factorization of the global decision making function (Guestrin et al. 2002b; Kuyer et al., 2008 van der Pol & Oliehock 2016 Böhmer et al. 2020). Message passing networks approximate such message passing algorithms Yoon et al. 2019; Satorras & Welling, 2021). Thus, we can view message passing networks type of learned communication between coordinating agents. Message passing networks can be executed using only local communication and computation. To see that this the case, consider the equations that determine the message passing networks in this paper:
(0)
(si))
(16)
m j-+ om Pesle.:FF 1111)
(1)
(17)
IM
m = Σ mg++i
(18)
f(++1) (, (1) m (1)
(19)
for all agents i and layers (message passing rounds) 1. In Eq. 16 each agent encodes its local observation 8; into a local feature vector ,,") In Eq. 17 each agent j computes its message to agent i using its own local feature vector f10 and its shared edge features eij
Zz. After agent i receives its neighbors' messages, it aggregates them in Eq. [8] Finally, in aggantt updates its local feature vector using the aggregated message and its local feature vector. Clearly, every step in this network requires only local computation and local communication, therefore allowing the network to be distributed over agents at execution time.
B EQUIVARIANCE OF PROPOSED MESSAGE PASSING LAYERS
Recall that Eij = Ii (the difference between the locations of agent i and agent j). Therefore, Uglesy] = Ug [2: =z5] U, [ma] - Ug(1)))
(20)
So, when both agent i and agent are moved to location transformed by Ug. the edge features esj are transformed by Ug as well. If all agent positions and observations rotate by the same underlying group, this means the full system has rotated. In this paper, we place equivariance constraints on the message function:
K2 Σ om (cis, f)ll -->==
= om L.
(21)
This means that the messages are only permuted by Kg if both the local features ff and the edge features Gij are transformed (by Ly and Ug respectively). To see that the proposed message passing layers are equivariant to transformations on agent features and edge features, consider the following example. Assume we have message passing layer e consisting of node update function &. and message update function Φm. such that with agent features {fi). and edge features {eig], the output for agent is given by
( (Leig) (83)) = du (Si, mi)
(22)
= Du
Sz. E om (eig:
(23)
Assume du and om are constrained to be equivariant in the following way:
Pylou (1) = &n (L (L,l, K [m,]) K,1 Σ> pm (Cij) fz) = Σ pm Sn, (ey)). (f1)
(24)
(25)
13

---

Published as a conference paper at ICLR 2022
for group elements 9 G. Then, for layer d:
Pg 0000 (Height()))) = Pg Ldu (fi. m.)l
(26)
Pg
Qu fis E
om (eis, (ew)
(27)
Lig [i], Kg Σ Dm (esp) 1)
vu
(using Eq.
24
(28)
vn
Lg [ill E pm (U, (ergl, Lg (GD)
(using Eq. 25
(29)
s (1U' leglh (ug Lf(l)
(30)
C DISCRETE ROTATIONS OF CONTINUOUS VECTORS
Here outline how to build weight matrices equivariant to discrete rotations of continuous vectors. Let Cij I. 2; be an arbitrary, continuous difference vector between the coordinates of agent and the coordinates of agent Then this difference vector transforms under 90 degree rotations using the group of standard 2D rotation matrices of the form
cos 0 sin 0
sin cos 0
Rg = R(0)
(31)
for 0 E [0, 7, n, 3r1 A weight matrix W is now equivariant to 90 degree rotations of eig if
W eij W eggi
(32)
with (Kg) e.g. permutation matrix representation of the same group. So,
W = W=K,
(33)
which we can solve using standard approaches.
D EXPERIMENTAL DETAILS
For all approaches, including baselines, we at least 15 random seeds for 6 different learning rates, (0.001, 0.003, 0.0001, 0.0003, 0.00001, 0.000.00000 0.00003), and report the best learning rate for each. Other hyperparameters taken default in the codebase (Stooke & Abbeel 2019 van der Pol et al.) 2020
D.1 LEARNING RATES REPORTED
After tuning the learning rate, we report the best one for each approach. See Table
Distributed Settings
Standard MPN
Augmented MPN
Equivariant MPN
Drones, 3 agents
0.001
0,0003
0.001
Drones, 4 agents
0.0003
0.001
0.001
Traffic, 4 agents
0.0001
0.0001
0.0001
Table 1: Best learning rates for distributed settings
14

---

Published as a conference paper at ICLR 2022
X
X
G-CNN
11
V
G-CNN
2
Equivariant Message Passing
112
V/2
G-CNN
11
V/3
G-CNN
NN
VN
Figure 7: General overview of Multi-Agent MDP Homomorphic Networks. G-CNN refers to group-equivariant CNN encoder. Equivariant message passing refers the proposed equivariant message passing networks. Encoding local states with group-CNNs ensure the state encodings are group-equivariant. The locations 2; are input to the equivariant message passing network.
D.2
ASSETS USED
Numpy Harmis al. 2020
1.19.2: BSD 3-Clause "New" "Revised" License;
PyToorch Paszke al.
2017
1.2.0: Modified BSD license;
RLPYT Stooke & Abbeel 2019): MIT license;
MDP Homomorphic Networks & Symmetrizer (van der Pol et al. 2020): MIT license.
ARCHITECTURAL DETAILS
Architectures are given below and were chosen to be as similar as possible between different approaches, keeping the number of trainable parameters comparable between approaches. We chose 2 message passing layers to allow for 2 message passing hops. For the message passing networks, we Ll-normalization of the adjacency matrix.
E.1 ARCHITECTURAL OVERVIEW
The global structure our network is given in Figure] 7
E.2
ARCHITECTURES
E.2.
WILDLIFE MONITORING
Listing I: Equivariant Network Architecture for Centralized Drones
EqConv2d (repp_iii channels_in-a repr_out=4, channels_out-11: _ filter_size= (7, 7), stride=2, padding=0)
ReLU()
EqCenv2d (repp_ channels_in= V repr_out=4, channels_out- filter_size=de 5), stride=1, padding=0)
RcLU()
GlobalMaxPool
( channels_in-1 in- repr_out=4, channels_out-1]
ReLU()
10
EqLinear (repr_in=4, channels_in- 128 v ropr_out=5, channels 64
11
ReLU()
12
ModuleList ( (|Egiieea (zepr_in=4, channels Litamels_ii__00 G4 v repr_out=5,
13
channels_out=:) for in range (m) ]]
14
EqLinear (repr_inst) channels in= [ repr_out=l, channels_outes
15

---

Published as a conference paper at ICLR 2022
Listing 2: CNN Architecture for Centralized Drones
Conv channels_out-16,
filter_size= (7, 7), stride-2, padding-0)
ReLU()
filter_ 5), stride=1, padding=O)
ReLU()
Gl
Linear (channels_in--3,, channels_out-2555
R)LU()
10
Modulelist [Linear (channels in=256, -
channels _ for i in range (m) in=256,
Linear (channell in=226, channels_out=1)
Listing 3: Equivariant Network Architecture for Distributed Drones
(repr_ channels_irg in=1, repr_ pop_ouu=4, bhannels_outt[10 Filter_aize- (7, 7), stri stride-2, padding-0)
ReIU()
EgCen22((repr_in-4, caannels_in= 1 repr_out=4, channels_out-- #blter_size=(5 5), stride=l, padding=0)
ReLU()
GlobalMaxPool ()
channels iin_iin=____ 32 Vi. repr_out=4,
channels_out-[[]
ReLU()
11
Eghesssseaasshnyyyerrrrzzzz (zepr in=4+4+2, in channels_out-1(11 [1
channels in- 64 V
repr repr_out=4,
12
13
ReLU()
14 EddessssgPaasingiayeer (repr. (repr in=4, channels_ing [
repr_out=5,
15
channell_out=i))
16
EgVessagePassnngayee (repr_in=4, channels in-
[ repr_out=1,
17
Shannels_outer
Listing 4: MPN Architecture for Distributed Drones
(canne( in=1, channels_outee
filter_she "iiter_size=(? (7, 7), stride=2, padding=0)
()
Conv2d (cav@@lchannela_in115 channels_out-32,
filter_aize- 5), stride=l, padding-0)
ReLU()
GlobalMaxPool() ()
(esagpppssssodaayeerrraamaae.ass channels_out=644 ReLU()
10
channels_out=69
11
ReLU()
Linear (channels_ineg i_ channels_out-5)
Linear (channels 6 channe1s_out-
E.2.2
TRAFFIC LIGHT CONTROL
Listing 5: Equivariant Network Architecture for Centralized Traffic
(ecoo_2d(repp_iin) channels_ime s_in=3, repr_out=4, channels s_uttsloss_s filter_size=(? (7, 7), stride=2, padding=0)
J
(eLU()
EqConv2d (repr_ channels channels_in=[11 1 repr_out=4, channels_one fi1ter_aize-1 5), stride=l, padding-0)
[
()
16

---

Published as a conference paper at ICLR 2022
GlobalMaxPoo1
EqLinear (zepr_ channels_in= repr_out=4, channels_ 128
()LU()
10
128 EqLinear (repr_in=4, channels_in- v
rep=_out=5, channols_out-l
11
()IU()
12
EqLinear (repr_in=4, channels_in-
v7 repr_out=8, channels_out=1)
18
EqLinear (repr_in=d channels_ in=
V
64
repr spp__ou==,, channels_out=1]
Listing 6: CNN Architecture for Centralized Traffic
I s_in=3, laaanels_ouutiie
Filter_size= (7, 7), stride=2, padding-0)
(eIU()
filter_size=-S, 5), stride=1, padding=0)
()
G1obbaMaxPool1
Linear 3 channels_outt-255)
ReIU()
10
Linear Setannels_in22555 channels_out-8)
Linear cchannels_in=256 channels_out=i)
Listing 7: Equivariant Network Architecture for Distributed Traffic
Eg in=l, channels in=3, _n=n,, repz_ out=,, channels [ 74- filter_size=(1 (7, 7), stride=2, padding-0)
(eIU()
Egcenv2d(reprr_nn44 channels_in- 1 repr_out=4, channels_out-! silter_size-ee 5), stride=1, padding=0)
ReLU()
GlobalMaxPool()
EgdessagePPssnnttyyee (xap_ in=4+4+2, channels in- A repr_out=4,
channels_out-1(11
10
ReLU()
11
trapssggepPaannggaaaeeeppppppee (repr channels_in-l [ repr_out=4,
12
channels [attneess_ott____ LV1
13
(eLU()
14 EgMessagePassingiayer (repr_in-k) channels_in-1i vil. repr_out=2,
15
caaanelssout=11
16
EglessagePassnngayer (repr (repr_in=4, channels in= [ repr_out=1,
17
channels_outes
Listing 8: MPN Architecture for Distributed Traffic
Conved inn3,, Shannels_out=i0 filter_size=77, (7, 7), stride=2, padding-0)
ReLU()
(cranndesanneeneeeee in=16, channels_out=32, filter_size=S5, 5), stride=l, padding=0)
ReLU()
GlobalMaxPool()
MessagePassingiayer
channels_out=64)
Rel.U()
10
MessagePassingiane
channels (
ReLU()
Linear (channels in=64, channels (
13
Linear Schannelssinn6. channels_out=:)
17

---

Published as a conference paper at ICLR 2022
E.3
GROUP ACTIONS
Here we list the group actions used in different equivariant layers throughout our experiments. For all equivariant layers, we use the Symmetrizer (van der Pol et al. 2020) to find equivariant weight bases.
Rotation-equivarian Filters For all equivariant encoder networks, we create 90 degree rotation- cquivariant filters using np. rot 90.
E.3.1
GROUP ACTIONS FOR WILDLIFE MONITORING
Linear layers
Permutation matrices representing the following permutations:
e 1,3,3
9I
3,0,
2,
93 [,,2,3,0]
Policy layers, centralized
Permutation matrices representing the following permutations:
e 1,,1,23,,4 9l 00,,,,,,11
S2 0,3, 1,2
93 [,,4,1,2,3]
Value layers, centralized
Permutation matrices representing the following permutations:
e
Ø1
9
93
Message Passing Layers
Acting state features, permutation matrices representing the following
permutations:
e 1,,
1,
Ge
1,
03 1,2,3,00
Acting on edge features, the following rotation matrices:
e=np.eye (2)
gi=np.array (110, -11, [1, 0]1)
@emp..araay ([[-1, 0]. [0, -11l)
@s=np. array [[,, 11, [-1, 0]1)
Policy layers, distributed 1,,,,,
Permutation matrices representing the following permutations:
91 00,2,3,4,1
92 0,3,4,1,2 0,,4,
G3
Value layers, distributed Permutation matrices representing the following permutations:
[1]
91
93
18

---

Published as a conference paper at ICLR 2022
E.3.2
GROUP ACTIONS FOR TRAFFIC LIGHT CONTROL
Linear layers
Permutation matrices representing the following permutations:
e 1,,1,
91 330,1,2
92 2,3,0,1
93 [1
Policy layers, centralized
Permutation matrices representing the following permutations:
1., 3, 5, 6]
0,4,1,0,7,6,33
6,7,4,5,2,80 f2
93
3,2, 6, 0,5,5,4
Value layers, centralized
Permutation matrices representing the following permutations:
e
91
92
93
Message Passing Layers
Acting on state features, permutation matrices representing the following
permutations:
e = [0, 1,233
01 1,0,
92 0,
Ø3 [1,2,3,0]
Acting on edge features, the following rotation matrices:
=np. aapp.ey. eye (2)
91 =np array ([[O, -11, [1, 0]])
g2 =n- array ([[-1, 01, [0, -1]])
Ø3 =u- array ([[O, 11, [-1, 01])
Policy layers, distributed
Permutation matrices representing the following permutations:
e 00, 1
91 [1.0]
S2 00,
93 11
Value layers, distributed
Permutation matrices representing the following permutations:
e [1]
91
J2
93
19


Reviews:
[{"review_id": "sKUfdQw8Zh", "reviewer": "Reviewer_xEvs", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "Strengths:\n\n1- The paper is clearly written and easy to follow.\n\n2- The illustrative examples in figure 1 and 4 are helpful.\n\n3- The related work is comprehensive. \n\nWeaknesses:\n\n1- The authors gave a detailed analysis of how to achieve distributed symmetries in Sec 4. However, how to perform the training of policies is not given. Though it is briefly mentioned that the authors used CTDE (centralized training and decentralized execution), I would appreciate it if the authors could provide details of the backbone algorithms and details for training and execution. For example, is the algorithm Q-learning based or Actor-critic based; what are the information available to the actions and critics respectively? \n\n2- the experimental results are not sufficient. I expect to see the comparisons to some multi-agent algorithms, such as PIC[ Liu2019]. Dependent on the answers to Question 1, it is possible that more baselines need to be added. \n", "summary_of_the_paper": "This work considers the symmetries properties in cooperative multi-agent systems. \nBy decomposing global symmetries into local transformations, this work introduces a multi-agent equivariant policy network based on this factorization. Empirical results show that  on symmetric multi-agent problems, distributed execution of globally symmetric policies improves data efficiency compared to non-equivariant baselines. \n", "summary_of_the_review": "This paper is in general well written and easy to follow. The method is well motivated. My major concern is that the paper lacks comparisons to existing algorithms that are either permutation invariant or not. And the information of training and execution is missing. \n", "strength_and_weaknesses": "", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "i7o_DA6swgi", "reviewer": "Reviewer_Z7zL", "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": "The problem this paper considers is very interesting, but the proposed method confuses the reviewer.\n\n(1) The novelty of this paper.  Is Multi-Agent MDP Homomorphic Network a simple combination of Graph Neural Networks and Symmetrizer? What are the main challenges to exploiting symmetry in MARL?\n\n(2) The writing is not clear. Why is there a $|G|$ in $\\phi_e$'s output in Sec. 4.3.2? Can the authors use framework diagrams instead of codes in Appendix D to show the architectural details?  These obscurities are very confusing, especially when some definitions in the code are not defined in this paper. The reviewer strongly recommends the authors not omit some details (although the details can be found in *MDP Homomorphic Networks: Group Symmetries in Reinforcement Learning*). \n\nBut in general, the idea of exploiting symmetry in MARL is timely and interesting. The reviewer hopes the authors could provide a running example to explain how the proposed method works, including training and executing. And the author also should clarify what the main contributions are. ", "summary_of_the_paper": "This paper tries to exploit the global symmetries in the joint state-action space of cooperative multi-agent systems. To allow distributed execution using only local information, this paper introduces Multi-Agent MDP Homomorphic Networks that use a factorization of global symmetries into symmetries on local observations and local interactions. They further compare the proposed networks with non-equivariant distributed networks, and show that global equivariance improves data efficiency on two games. ", "summary_of_the_review": "This paper is not well-written and very confusing. Refinement is needed.\n", "strength_and_weaknesses": "", "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": {}}, {"review_id": "RpDnIYwB0At", "reviewer": "Reviewer_Jvcy", "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": "### Strengths:\n- The authors identify symmetries which arise in multi-agent settings and identify ways to exploit them.  \n- The type of symmetry identified in Figure 1 is more interesting than those in MDP Homomorphic networks.  It is similar to the type of actions considered in Steerable CNN, in which the group acts on both a spatial base space and on a fiber space as well.  \n- The method is well-motivated and well-designed in that the architecture reflects and enforces both the global permutation symmetries and local rotational symmetries the authors identify in the problem.  \n- The experiments show a clear improvement in data efficiency which is quite important in RL. \n- The scope section in the conclusion does a nice job identify limitations in the current work and pointing the way to interesting future work. \n\n### Weakness/Limitations: \n- The symmetry in Figure 1, while interesting, is not really outside the framework of MDP with symmetry.  By simply assuming full communication and making a single centralized agent, we can still consider this symmetry by permutation/rotation as an MDP symmetry of a single-agent MDP with symmetries.    \n- The test domains are both fairly simple and feel a bit contrived.  In particular the traffic light scenario is only symmetric because the traffic lights have exactly symmetric lay out.  City grids notwithstanding, actual road segments are usually distinguishable in the real world.  \n- The authors point out they only use discrete groups, but the work is actually more limited than that.  They only use permutation actions and the discrete rotation group $C_4$.  Since the method is formulated to work with many groups, I’d like to see it tested with more groups.  In particular, for image data, $C_4$ is a best case for equivariant networks.  Using different groups would involve more complexity and potential downsides.   \n- It seems like data augmentation only involved randomly transforming each sample.  In practice, often additional samples are used with many transformations.  The argument could be made that this is not really less data efficient although it takes longer to train.  It might be good to compare to augmentation with additional samples.  \n\n### Questions\n- The action in equation (6) is only each local state and edge attribute.  So the new local state at node $i$ is computed in terms of the old local state at node $i$.   But the permutation action as in Figure 1 also permutes the local states.  Is some permutation missing from this defn?   \n- If the MPN has M layers and M is sufficiently large, then how distributed or constrained is communication practically?  For example, in the traffic light setting, I assume the lights can talk to their neighbors, so after M layers of an MPN, can’t all lights effectively communicate?  So isn’t that the same as a centralized control?  From the definition of MMDP, it seems logical that the information sharing constraint is per action step not per layer.   \n- What is the advantage of using Symmetrizer?  It seems a basis of linear $G$-intertwiners here would not be difficult to derive analytically (as most authors do). \n- In general, an MPN is fully permutation equivariant and, moreover, equivariant to permutation of node labels independent of actions or other features.  So using an MPN would seem to give too much symmetry.  In the traffic light setting, you want to be equivariant only to simultaneous cyclic permutations of agents and rotations of features.  However, I believe the edge features do the job of breaking the full symmetry of MPN and give exactly the symmetry you want.  Is this the case?  If so, can it be made more explicit or proved? \n- I assume the non-linearities are pointwise and applied only to regular representations?  If so, it should be explained. \n- Since only $C_4$ symmetry is used, I assume the Equivariance error is very small for the fully equivariant method.  Did you empirically verify this?  Also, how small is the equivariance error for the other baselines?  \n\n### Small Notes:\n\n- Sec 3.1/ para 3: what is $\\Delta(A)$? \n- Sec 3.2/ para 3: $e$ is not defined.  Also it seems a bit strange to be explicit with $\\cdot$ for composition but only use juxtaposition for the group action. \n- Sec 3.2/ para 3: this is a nitpick, but it is not “the same group action” if it is on a different space\n- Page 3 last para/ Page 4: The notion of “equivalent” state-action pairs doesn’t seem precisely defined to me.  In particular, it’s not clear to me what the sentence after Defn 2 is saying.  \n- Page 6, sentence after eqn 10: this is a nitpick, but linear combinations of equivariant functions are only equivariant if the output space is a group representation.  This would not hold for arbitrary equivariant functions between spaces with non-linear actions.   \n- Eqn 14.: Is $H_g$ defined? \n\n\n\n", "summary_of_the_paper": "The authors give a generalization of MDP Homomorphic Networks (van der Pol, 2020) to multi-agent distributed settings.  This is not a special case of previous work as the agents are not assumed to be able to communicate freely.  The symmetry constraints of the single-agent case generalize to the multi-agent case with the twist that the group action also induces a permutation of the agents.  To create a neural network which matches this symmetry, the authors use a message-passing NN with equivariance constraints.  The method shows improved sample efficiency relative to networks which are only permutation equivariant trained with and without augmentation.  Only the discrete 90-degree rotation group is considered.  \n\n", "summary_of_the_review": "Overall, I tend towards accept.  The work appears to be sound and the method is well-motivated and well-designed.  I feel the extension from MDP Homomorphic Networks is not so large.  I believe the symmetries considered here may also be essentially considered as symmetries in the setting of van der Pol, 2020.  I feel the experiments are also somewhat limited.  They consider only the group $C_4$, compare only to versions of the proposed model, and the domains seem a bit contrived.  It is thus hard to evaluate how useful the method would be in practice.      \n", "strength_and_weaknesses": "", "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": "Ixsl-yLq_D6", "reviewer": "Reviewer_XJk1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\n- The observations made about symmetry in MMDPs are reasonable. The intuition behind these observations are well illustrated by giving a concrete example of a cooperative traffic light control system. \n\n- The network structure is well-explained and appears to be able to better leverage local symmetry.\n\n- While the code is not yet made public, the experiments section in the Appendix is sufficiently detailed and the results appear to be replicable.\n\nWeaknesses:\n\n- I am unfamiliar with the area, but it seems the baselines compared against are limited. Since the paper is empirical in nature, could the authors comment more on what are other related works on applied MMDP that could be used for the same task? Can the authors show that the proposed method outperforms other algorithms, that perhaps only make use of graphs or permutation symmetries?", "summary_of_the_paper": "The paper introduces the notion of symmetry in MMDPs and proposes an empirical algorithm that could leverage symmetry in MMDPs. By decomposing distributable global symmetries into local symmetries, the paper proposes a new neural network structure that empirically outperforms existing MPN models.", "summary_of_the_review": "Overall, the paper introduces an interesting observation on certain real-world MMDP tasks and proposes a novel network structure that performs well under two different tasks, one with real-world data and the other with simulations.", "strength_and_weaknesses": "", "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": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes some interesting ideas about decomposing the global symmetries of multi-agent MDP to local symmetries using a method called the Homomorphic Networks. The paper is well-writing and can be followed easily. However, there are a number of weaknesses of the paper. Below, we list some of the outstanding ones.

(1) Both some of the reviewers and the AC find there are some clarity issues in the paper, for instance, it is hard to see why using keeping relative communication and local transformation would guarantee symmetry (it would be good to show this with a theorem); it is hard to understand the algorithmic structure due to the use of codes instead of diagram in Appendix D, especially when some definitions in the code are not defined in this paper; the AC also finds it is hard to understand how communication is performed during both training and executing. After the rebuttal, the structure of the paper has been improved but we encourage the authors to keep improving the presentation.

(2) Another weakness is the experiment implementations, which the reviewers found were a bit too simple and contrived -- the traffic light example may not be symmetric in the real world. It might be good to demonstrate the effectiveness of the setting in a more realistic setting -- perhaps show that the method also works with a slight violation of symmetry.

That being said, the contribution of the paper remains significant, and the AC recommends borderline but slightly leaning toward acceptance.
Decision: Accept (Poster)