#  ${\rm E}(3)$-Equivariant Actor-Critic Methods for Cooperative Multi-Agent
Reinforcement Learning

Dingyang Chen, Qi Zhang

###### Abstract

Identification and analysis of symmetrical patterns in the natural world have
led to significant discoveries across various scientific fields, such as the
formulation of gravitational laws in physics and advancements in the study of
chemical structures. In this paper, we focus on exploiting Euclidean
symmetries inherent in certain cooperative multi-agent reinforcement learning
(MARL) problems and prevalent in many applications. We begin by formally
characterizing a subclass of Markov games with a general notion of symmetries
that admits the existence of symmetric optimal values and policies. Motivated
by these properties, we design neural network architectures with symmetric
constraints embedded as an inductive bias for multi-agent actor-critic
methods. This inductive bias results in superior performance in various
cooperative MARL benchmarks and impressive generalization capabilities such as
zero-shot learning and transfer learning in unseen scenarios with repeated
symmetric patterns. The code is available at: https://github.com/dchen48/E3AC.

##  1 Introduction

It is widely believed by scientists that the organization and operation of our
universe follow certain symmetry patterns and principles. These symmetry
structures in physics lead to profound implications, such as the existence of
conservation laws [1]. When done properly, artificial intelligence (AI) can
and has already benefited tremendously from exploiting these symmetries, with
perhaps the most well-known example of convolutional neural networks (CNNs)
being translation invariant to the input images [2]. In this paper, we focus
on cooperative multi-agent reinforcement learning (MARL) problems, where
symmetry structures are also prevalent. Consider the example where a team of
agents aims to cover a number of landmarks, a cooperative MARL benchmark task
[3]. The agents’ best search directions should be rotated correspondingly if
we rotate all the agents and landmarks but will remain the same if we
translate them in the same direction. Although prevalent, multi-agent
symmetries are relatively underexplored with a few recent sporadic works [4,
5, 6]. Our research question arises naturally: how can we improve the learning
efficiency of cooperative MARL problems by exploiting the inherent symmetry
structures therein, if any?

Our work answers this question with a focus on Euclidean symmetries, i.e.,
distance-preserving transformations in Euclidean space such as rotations,
translations, reflection, etc. Intuitively, MARL problems exhibit Euclidean
symmetries whenever coordinate frames are used to provide references for the
agents and their environment, because Euclidean transformations (e.g.,
rotations) can be simply viewed as being applied to the reference frames,
without changing the essence of the agents and environment. Therefore,
Euclidean symmetries are prevalent in many applications situated in 2D/3D
spaces, such as multi-robot systems, video games, materials design, etc.

Specifically, our contribution is three-fold: (i) We rigorously formulate a
subclass of Markov games (MGs) [7], group-symmetric Markov games, using a
general notion of symmetries described by mathematical group transformations,
with Euclidean transformations being the special case of the (3D) Euclidean
group, ${\rm E}(3)$. (ii) We prove several main properties of a group-
symmetric Markov game, which include the group symmetries in its optimal value
functions and the existence of an optimal policy that is also group-symmetric.
Interestingly, we find the emergence of ${\rm E}(3)$ group-symmetries in MARL
agents when training the actors and critics based on vanilla multi-layer
perceptron (MLP) neural network architectures, which are consistent with the
properties. (iii) Motivated by the findings, we inject the inductive bias of
Euclidean group symmetries in multi-agent actor-critic architectures by
employing recent development in ${\rm E}(3)$-equivariant neural networks [8,
9, 10], which results in superior sample efficiency and generalization
performance in a range of benchmark MARL tasks.

##  2 Related work

In single-agent RL, the exploitation of symmetries has been originally
formulated by Ravindran and Barto [11] to reduce the redundancies in state and
action spaces. Recent work mostly focuses on the combination of symmetries and
deep RL. Some works [12, 13] utilize data augmentation, where an image-based
observation undergoes transformation such as rotation and translation, to
improve data efficiency. This approach mostly focuses on the invariant value
functions with respect to the transformed input. Instead of generating more
data through symmetric transformations which increases computation time, Van
der Pol et al. [14] build equivariant neural policies that directly satisfy
the symmetrical constraints.

Multi-agent symmetries are currently underexplored. Some work [15, 6] focus on
the permutation invariance of homogeneous agents, and build permutation
invariant value functions for better sample and computation efficiency. The
work by Li et al. [16] considers symmetries specific to multi-agent path
finding problem to reduce the search space. A recent work [5] considers more
general symmetries in MARL by extending the framework in single-agent
symmetry. However, it does not provide motivation why such symmetries result
in equivariant actors and critics, just as the counterparts proved in the
single-agent setting.

This work focuses on Euclidean symmetries commonly seen in practice, e.g.,
position and velocity in 3D space. Special neural architectures have been
proposed to directly incorporate geometric inductive bias. Some works [17, 18,
19, 20] preserve equivariancy by equivariant operations in the original 3D
Euclidean space. In contrast, other works lift the physical quantities from 3D
space to higher-dimensional spaces for more expressive power, either through
Lie algebra [21] or spherical harmonics [8] and message passing [10], which we
adopt in this paper for actor-critic architectures.

##  3 Preliminaries

###  3.1 Cooperative Markov games

We use the framework of cooperative Markov game (MG) [7] to formulate our
cooperative multi-agent setting, which consists of $N$ agents indexed by
$i\in\mathcal{N}:=\\{1,...,N\\}$, state space $\mathcal{S}$, joint action
space $\mathcal{A}=\mathcal{A}^{1}\times\cdots\times\mathcal{A}^{N}$ factored
into local action spaces, transition function
$P:\mathcal{S}\times\mathcal{A}\to\Delta(\mathcal{S})$, (team) reward function
$r:\mathcal{S}\times\mathcal{A}\to\operatorname{\mathbb{R}}$, and initial
state distribution $\mu\in\Delta(\mathcal{S})$, where we use
$\Delta(\mathcal{X})$ to denote the set of probability distributions over
$\mathcal{X}$. The MG evolves in discrete time steps: at each time step $t$,
all agents are in some state $s_{t}\in\mathcal{S}$ and each agent
$i\in\mathcal{N}$ chooses its local action $a^{i}_{t}\in\mathcal{A}^{i}$,
forming a joint action $a_{t}=(a^{1}_{t},...,a^{N}_{t})\in\mathcal{A}$ that
induces a transition to a new state at the next time step according to the
transition function, i.e., $s_{t+1}\sim P(\cdot|s_{t},a_{t})$, and the team
reward signal $r_{t}:=r(s_{t},a_{t})$. The state $s_{0}\sim\mu$ at time step
$0$ is drawn from the initial state distribution.

Full and partial observability. For ease of exposition, we will assume the
agents can fully observe the states until Section 4, and our methods (Section
5) and experiments (Section 6) accommodate the partial observability setting.
We shall consider a more general notion of full observability than directly
observing the raw state: each agent $i\in\mathcal{N}$ has access to a function
$o^{i}:\mathcal{S}\to\mathcal{O}^{i}$ that maps the state space to its local
observation space $\mathcal{O}^{i}$. The agents effectively fully observe the
state if and only if $o^{i}$ is bijective. We will use the notion of
$o=\\{o^{i}\\}_{i\in\mathcal{N}}$ and write
$o(s):=\left(o^{1}(s),...,o^{N}(s)\right)\in\mathcal{O}:=\times_{i\in\mathcal{N}}\Delta(\mathcal{O}^{i})$.
The MG is therefore defined by tuple
$\langle\mathcal{N},\mathcal{S},\mathcal{A},P,r,o\rangle$.

Policies and values. The general, state-based joint policy,
$\pi:\mathcal{S}\to\Delta(\mathcal{A})$, maps from the state space to
distributions over the joint action space. As the size of action space
$\mathcal{A}$ grows exponentially with $N$, the commonly used joint policy
subclass is the product policy,
$\pi=(\pi^{1},\cdots,\pi^{N}):\mathcal{S}\to\times_{i\in\mathcal{N}}\Delta(\mathcal{A}^{i})$,
which is factored as the product of local policies
$\pi^{i}:\mathcal{S}\to\Delta(\mathcal{A}^{i})$,
$\pi(a|s)=\prod_{i\in\mathcal{N}}\pi^{i}(a^{i}|s)$, each mapping the state
space only to the action space of an individual agent. Define the discounted
return from time step $t$ as $G_{t}=\sum_{l=0}^{\infty}\gamma^{l}r_{t+l}$. For
agent $i$, product policy $\pi=(\pi^{1},...,\pi^{N})$ induces a value function
defined as
$V_{\pi}(s_{t})=\operatorname{\mathbb{E}}_{s_{t+1:\infty},a_{t:\infty}\sim\pi}[G_{t}|s_{t}]$,
and action-value function
$Q_{\pi}(s_{t},a_{t})=\operatorname{\mathbb{E}}_{s_{t+1:\infty},a_{t+1:\infty}\sim\pi}[G_{t}|s_{t},a_{t}]$.
Following policy $\pi$, agent $i$’s cumulative reward starting from
$s_{0}\sim\mu$ is denoted as
$V_{\pi}(\mu):=\operatorname{\mathbb{E}}_{s_{0}\sim\mu}[V_{\pi}(s_{0})]$.
Under full observability, a state-based local policy can translate from and to
an observation-based policy with $\nu^{i}(o^{i}(s))=\pi^{i}(s)$ and the
corresponding observation-based product policy and its values are denoted as
$\nu(o(s))=(\nu^{1}(o^{1}(s)),...,\nu^{N}(o^{N}(s)))$, $Q_{\nu}$, and
$V_{\nu}$, respectively.

###  3.2 Groups and transformations

In mathematics, symmetry means a type of invariance: a property of an object
remaining unchanged after some transformation. This notion of symmetry can be
formally described by invariant functions. A function
$f:\mathcal{X}\to\mathcal{Y}$ is invariant under transformation operator
$T:\mathcal{X}\to\mathcal{X}$ if $f\left(T[x]\right)=f(x)$ for any
$x\in\mathcal{X}$. More generally, function $f:\mathcal{X}\to\mathcal{Y}$ is
equivariant under transformation operators $T:\mathcal{X}\to\mathcal{X}$ and
$T^{\prime}:\mathcal{Y}\to\mathcal{Y}$ if
$f\left(T[x]\right)=T^{\prime}\left[f(x)\right]$ for any $x\in\mathcal{X}$.
Most often, a symmetric object is invariant to not only one transformation but
a set of transformations. Such a set of symmetry transformations often forms a
(mathematical) group $G$, which is a set of elements equipped with a binary
operator satisfying the group axioms of closure, associativity, identity, and
inverse [22]. For function $f$ to be equivariant to group $G$, there exists
transformation operators $T_{g}$ and $T^{\prime}_{g}$, called group actions,
associated with each group element $g\in G$, such that
$f\left(T_{g}[x]\right)=T^{\prime}_{g}\left[f(x)\right]$ for any
$x\in\mathcal{X}$.

The Euclidean group ${\rm E}(3)$. We are mostly interested in group ${\rm
E}(3)$ that comprises the group actions of translations, rotations,
reflections, and finite combinations of them in 3D. Therefore, it has as its
subgroups the 3D translation group ${\rm T}(3)$, and the orthogonal group
${\rm O}(3)$ for 3D rotations and reflections. The group actions of ${\rm
O}(3)$ can implemented by multiplying square matrices, called representation
matrices. For example, for the group element of $g=(\alpha,\beta,\gamma)$ that
rotates a 3D vector $x=\mathbf{x}\in\operatorname{\mathbb{R}}^{3}$ by
$\alpha$, $\beta$, and $\gamma$, about $x$-, $y$-, and $z$\- axes
respectively, the rotation can be represented by matrix multiplication as
$T_{g}[x]=\mathbf{R}_{\alpha,\beta,\gamma}\mathbf{x}$, where
$\mathbf{R}_{\alpha,\beta,\gamma}\in\operatorname{\mathbb{R}}^{3\times 3}$ is
the 3D rotation matrix.

##  4 Group-symmetric Markov games with Euclidean symmetries

With the notions introduced, we are ready to define group-symmetric MGs by
asking the transition, reward, and observations functions to be equivariant
under group actions, as formally stated in Definition 1.

######  Definition 1 ($G$-symmetric MG).

Consider MG $\langle\mathcal{N},\mathcal{S},\mathcal{A},P,r,o\rangle$ and a
(mathematical) group $G$ equipped with group actions
$\\{L_{g}:\mathcal{S}\to\mathcal{S},K_{g}^{s}:\mathcal{A}\to\mathcal{A},I_{g}^{s,a}:\operatorname{\mathbb{R}}\to\operatorname{\mathbb{R}},H_{g}^{s}:\mathcal{O}\to\mathcal{O}\\}_{g\in
G}$. The MG is $G$-symmetric if, for any $s,s^{\prime}\in\mathcal{S}$,
$a\in\mathcal{A}$, and $g\in G$, we have

$\displaystyle
P(s^{\prime}|s,a)=P\left(L_{g}[s^{\prime}]~{}|~{}L_{g}[s],K_{g}^{s}[a]\right),~{}r\left(L_{g}[s],K_{g}^{s}[a]\right)=I_{g}^{s,a}\left[r(s,a)\right],~{}o\left(L_{g}[s]\right)=H_{g}^{s}\left[o(s)\right]$

i.e., $P$, $r$, and $o$ are equivariant to the group actions.

Definition 1 is general enough to accommodate arbitrary symmetries in MGs. For
example, choosing the group actions to be permutations of $\mathcal{N}$ (i.e.,
$G={\rm S}(N)$) can describe permutation invariance between homogenous agents
[15, 6]. In this work, we focus on 3D Euclidean symmetries in MGs, i.e.,
$G={\rm E}(3)$. For ease of exposition, we will ground our discussion with a
running example of Cooperative Navigation, a popular cooperative multi-agent
benchmark task [3].

Cooperative Navigation and its symmetries. In Cooperative Navigation, $N$
agents move as a team to cover $N$ landmarks in a 2D space. The landmarks are
randomly initialized at the beginning of an episode and fixed throughout the
episode. The reward functions determine the reward for all agents according to
the distances between all agents and the landmarks to encourage coverage, as
well as penalties to discourage collisions if any. Under full observability,
the observation of an agent contains its own absolute location and velocity,
the relative locations and velocities of all other agents, and the relative
locations of all the nearest landmarks. Figure 1 (left) shows the case where
$N=3$ and illustrates the rotational symmetry therein. The states and actions
can be represented as 2D vectors under a global reference frame (e.g., agent
$i$’s position, $\mathbf{x}_{i}$), whereas each agent’s observation are 2D
vectors referenced to its local frame (e.g., agent $i$’s velocity relative to
agent $j$, $\mathbf{v}^{j}_{i}=\mathbf{v}_{i}-\mathbf{v}_{j}$). Upon a
rotation of all entities, which is shown in Figure 1 (left) as a rotation of
the reference frames, the states, actions, and observations are rotated
accordingly, yet the essence of the entities remain unchanged, and therefore
the transition, reward, and observation functions are equivariant/invariant.
Similarly, it is easy to see that Cooperative Navigation also exhibits
translational and reflectional symmetries, as shown in Figure 1 (middle and
right, respectively). Further, it is straightforward to extend these
symmetries from 2D to 3D, thus making Cooperative Navigation ${\rm
E}(3)$-symmetric.

Figure 1: Illustration of Cooperative Navigation ($N=3$) and its Euclidean
symmetries.

With the intuition from Cooperative Navigation, we now formally define ${\rm
E}(3)$-symmetric MGs in Definition 2, where we will represent states and
observations as 3D point clouds and specify the corresponding group actions
applied to them.

######  Definition 2 (${\rm E}(3)$-symmetric MGs).

MG $\langle\mathcal{N},\mathcal{S},\mathcal{A},P,r,o\rangle$ is ${\rm
E}(3)$-symmetric if the following conditions hold.

  1. (i)

A state is a 3D point cloud consisting of agents $\mathcal{N}$ and other
uncontrollable entities $\mathcal{M}$, i.e.,
$s=\\{(\mathbf{x}_{v},\mathbf{f}_{v})\\}_{v\in\mathcal{V}}$, where
$\mathcal{V}=\mathcal{N}\cup\mathcal{M}$ is the set of all entities,
$\mathbf{x}_{v}\in\operatorname{\mathbb{R}}^{3}$ is the 3D position vector of
entity $v$ with feature vector
$\mathbf{f}_{v}\in\operatorname{\mathbb{R}}^{d_{v}}$.

  2. (ii)

The local action spaces are Euclidean spaces, i.e.,
$\mathbf{a}^{i}\in\mathcal{A}^{i}=\operatorname{\mathbb{R}}^{d_{\mathbf{a}^{i}}},\forall
i\in\mathcal{N}$.

  3. (iii)

Agent $i$’s observation is represented by a 3D point cloud consisting of the
entities in its own view,
$o^{i}(s)=\\{(\mathbf{x}_{v}^{i},\mathbf{f}_{v}^{i})\\}_{v\in\mathcal{V}}$
where $\mathbf{x}_{v}^{i}\in\operatorname{\mathbb{R}}^{3}$ is the 3D position
vector of entity $v$ with feature vector
$\mathbf{f}_{v}^{i}\in\operatorname{\mathbb{R}}^{d_{\mathbf{f}_{v}^{i}}}$,
both relative to agent $i$.

The MG’s $P$, $r$, and $o$ are equivariant (cf. Definition 1) to ${\rm E}(3)$
group actions specified as follows:

  1. (iv)

Under translation, the state is transformed with only the entities’ positions
being translated, i.e.,
$s=\\{(\mathbf{x}_{v},\mathbf{f}_{v})\\}_{v\in\mathcal{V}}~{}\to_{g}~{}s=\\{(\mathbf{x}_{v}+\mathbf{t}_{g},\mathbf{f}_{v})\\}_{v\in\mathcal{V}}$
where $\mathbf{t}_{g}\in\operatorname{\mathbb{R}}^{3}$ is the 3D translation
for $g\in{\rm T}(3)$, while actions and observations remain unchanged.

  2. (v)

Under rotations or reflections, all vectors in states, local actions, and
observations are transformed according to their respective group
representations. For example, the state transforms as
$s=\\{(\mathbf{x}_{v},\mathbf{f}_{v})\\}_{v\in\mathcal{V}}~{}\to_{g}~{}s=\\{(\mathbf{D}_{g}^{\mathbf{x}}\mathbf{x}_{v},\mathbf{D}_{g}^{\mathbf{f}}\mathbf{f}_{v})\\}_{v\in\mathcal{V}}$
where $\mathbf{D}_{g}^{\mathbf{x}}$ and $\mathbf{D}_{g}^{\mathbf{f}}$ are the
representation matrices of $g\in{\rm O}(3)$ for the vector spaces of
$\mathbf{x}_{v}$ and $\mathbf{f}_{v}$, respectively.

In essence, Definition 2 requires the states and observations to be
represented as 3D point clouds with the entities being the points with
corresponding features, which are transformed according to Euclidean
symmetries that are intuitively just changes of the reference frames. The
actions can be understood as features associated with the subset of agents
that also are transformed accordingly. In the example of Cooperative
Navigation, the point feature vector for an entity $v\in\mathcal{V}$ include
its entity type to differentiate from agent vs landmark, which in our
experiments is represented by a one-hot vector of two classes,
$\mathbf{f}_{v}\in\operatorname{\mathbb{R}}^{2}$; the local action of agent
$i\in\mathcal{N}$ includes its velocity,
$\mathbf{a}^{i}=\mathbf{v}_{i}\in\mathcal{A}^{i}=\operatorname{\mathbb{R}}^{3}$
with dummy $z$ values.

Examples of ${\rm E}(3)$-symmetric MGs. Besides Cooperative Navigation, all
other scenarios in MPE are examples of ${\rm E}(3)$-symmetric MGs. Further, by
Definition 2, any MG involving multiple entities interacting in a 2D/3D space
is ${\rm E}(3)$-symmetric. Another example is StarCraft Multi-Agent Challenge
(SMAC), also a popular MARL benchmark involving two competing teams of
StarCraft units in a 2D space. We give more details and more examples in the
appendix.

We are now ready to derive the main properties of group-symmetric MGs: since
the transition, reward, and observation functions are group-symmetric, if the
policy is also group-symmetric, then we can expect its value functions are
invariant under the group actions. For example, under a rotation angle
$\alpha$ if all agents in Cooperative Navigation always choose their
velocities with the same rotation angle $\alpha$, then the policy value
remains unchanged. Definition 3 formally states this requirement in general
$G$-symmetric MGs for both state-based and observation-based policies.

######  Definition 3 ($G$-invariant MG policies).

Let $\pi:\mathcal{S}\to\Delta(\mathcal{A})$ be a state-based policy in a
$G$-symmetric MG. We say $\pi$ is $G$-invariant if it is invariant to the
group actions of $G$, i.e., for any $s\in\mathcal{S}$, $a\in\mathcal{A}$, and
$g\in G$, $\pi(a|s)=\pi(K_{g}^{s}[a]~{}|~{}L_{g}[s])$. Similarly, an
observation-based policy
$\nu:\mathcal{O}\to\times_{i\in\mathcal{N}}\Delta(\mathcal{A}^{i})$ is
$G$-invariant if $\nu(a|o(s))=\nu(K_{g}^{s}[a]~{}|~{}H^{s}_{g}[o(s)])$ for any
$s\in\mathcal{S}$, $a\in\mathcal{A}$, and $g\in G$.

It is easy to see that, under bijective observation functions, a state-based
$G$-invariant policy induces an observation-based policy that is also
$G$-invariant, and vice versa. Therefore, we only state the properties for
state-based $G$-invariant policies in Theorem 1 below, and observation-based
policies will also share the same properties.

######  Theorem 1 (Main properties of $G$-symmetric MGs).

For a $G$-symmetric MG,

  1. (i)

The optimal values are $G$-invariant, $V_{*}(s)=V_{*}(L_{g}[s])$,
$Q_{*}(s,a)=Q_{*}(L_{g}[s],K_{g}^{s}[a])$.

  2. (ii)

There exists a $G$-invariant policy $\pi$, such that
$V_{\pi}(s)=V_{*}(s),Q_{\pi}(s,a)=Q_{*}(s,a)$.

Further, suppose policy $\pi:\mathcal{S}\to\Delta(\mathcal{A})$ is
$G$-invariant.

  1. (iii)

For any $s\in\mathcal{S}$, $a\in\mathcal{A}$, and $g\in G$,
$V_{\pi}(s)=V_{\pi}(L_{g}[s]),Q_{\pi}(s,a)=Q_{\pi}(L_{g}[s],K_{g}^{s}[a])$.

  2. (iv)

If $\pi$ is parameterized by $\theta$ as $\pi_{\theta}$ and differentialble,
then
$\nabla_{\theta}\pi_{\theta}(a|s)=\nabla_{\theta}\pi_{\theta}(K^{s}_{g}[a]~{}|~{}L_{g}[s])$.

A full proof is in the appendix. Theorem 1 establishes the properties our
method will exploit next.

##  5 ${\rm E}(3)$-equivariant multi-agent actor-critic methods

The properties stated in Theorem 1 naturally prompt us with the idea of
adopting group-invariant architectures for cooperative MARL. In this work, we
consider multi-agent actor-critic methods, such as MADDPG [3] and MAPPO [23].
Specifically, properties (i) and (ii) in Theorem 1 suggests that we can reduce
the search of optimality within group-invariant functions for actors and
critics. Moreover, properties (iii) and (iv) imply that group-invariant actors
enjoy symmetric policy gradients:

$\displaystyle\nabla_{\theta}\pi_{\theta}(a|s)\cdot
Q_{\pi_{\theta}}(s,a)=\nabla_{\theta}\pi_{\theta}(K^{s}_{g}[a]~{}|~{}L_{g}[s])\cdot
Q_{\pi_{\theta}}(L_{g}[s],K_{g}^{s}[a])$

which suggests that the optimization landscape is symmetric and therefore can
be more efficiently optimized via gradient-based search [24, 25].

Figure 2:  Emergence of rotation- and translation-invariancy in MLP-based
actors trained on Cooperative Navigation ($N=3$).

This idea is further motivated with our empirical analysis that finds
emergence of group-invariancy in traditional actor-critic architectures that
have no guaranteed invariancy. Specifically, we train the agents in
Cooperative Navigation ($N=3$) via MADDPG with MLP-based actors and critics.
Figure 2 plots the degree of the (observation-based) actors,
$\\{\nu^{i}\\}_{i\in\mathcal{N}}$, being invariant to rotations and
translations, respectively, during training. For rotations, we select a finite
set of angles, $A=\\{30^{\circ},60^{\circ},\cdots,330^{\circ}\\}$, and
quantify the corresponding invariancy measure in state $s$ as

$\displaystyle\textstyle\frac{1}{|A|N}\sum_{i\in\mathcal{N}}\sum_{\alpha\in
A}\cos\left({\rm rot}_{\alpha}[\nu^{i}(o^{i}(s)],~{}\nu^{i}(o^{i}({\rm
rot}_{\alpha}[s]))\right)$ (1)

where ${\rm rot}_{\alpha}[\cdot]$ performs the rotation by $\alpha$ and
$\cos(\cdot,\cdot)$ measures the cosine similarity. We measure the translation
invariancy similarly.

###  5.1 ${\rm E}(3)$-equivariant message passing

In this work, we implement ${\rm E}(3)$-equivariant/invariant actor-critic
architectures with ${\rm E}(3)$-equivariant message passing neural networks
(E3-MPNNs) [8, 9, 10], a type of graph neural networks that process 3D
Euclidean graphs, graphs where vertices are located at 3D positions, as an
${\rm E}(3)$-equivariant function. Formally, an input Euclidean graph is
represented as a tuple $G^{\rm
in}=(\mathcal{V},\mathcal{E},\mathbf{x},\mathbf{f}^{\rm in})$ where
$\mathcal{V}$ is a set of vertices with 3D positions
$\mathbf{x}_{v}\in\operatorname{\mathbb{R}}^{3}$,
$\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}$ is a set of edges, and
$\mathbf{f}^{\rm in}$ is a set of feature vectors, each associated with a
vertex or an edge. The backbone of E3-MPNNs is ${\rm E}(3)$-equivariant
message passing layers, denoted as $\texttt{E3-MP}(\cdot)$, maps the input
Euclidean graph to an output Euclidean graph by updating only the feature set,
$G^{\rm out}=(\mathcal{V},\mathcal{E},\mathbf{x},\mathbf{f}^{\rm out})$, in an
${\rm E}(3)$-equivariant manner, $\texttt{E3-MP}(T_{g}^{\rm in}[G^{\rm
in}])=T_{g}^{\rm out}[\texttt{E3-MP}(G^{\rm in})]$ for $g\in{\rm E}(3)$, where
$T_{g}^{\rm in}$ and $T_{g}^{\rm out}$ include Euclidean transformations
(i.e., translation, rotation, etc.) applied to the vertices and features in
the input and output graph, respectively. After the message passing layers,
E3-MPNNs produce the final output $y\in\mathcal{Y}$ using a graph readout
layer, $\texttt{E3-Readout}(\cdot)$, which is also ${\rm E}(3)$-equivariant,
$\texttt{E3-Readout}(T_{g}^{\rm out}[G^{\rm
out}])=T_{g}^{\mathcal{Y}}[\texttt{E3-Readout}(G^{\rm out})]$ for $g\in{\rm
E}(3)$. This ensures the overall equivariancy from the input graph to the
final output.

###  5.2 Integration into multi-agent actor-critic algorithms

In order to use E3-MPNNs for multi-agent actor-critic architectures, we need
to first represent state $s$, state-action pair $(s,a)$, and observation
$o^{i}(s)$ as Euclidean graphs for centralized state-value critic $V(s)$,
action-value critic $Q(s,a)$, and observation-based actor $\nu^{i}(o^{i}(s))$,
respectively. This is straightforward for ${\rm E}(3)$-symmetric MGs, because
by Definition 2 the states and observations are represented as 3D point clouds
which can be directly cast into 3D Euclidean graphs if edges are added. In our
experiments, we use some heuristics to add edges, e.g., each vertex is
connected with all others as a complete graph or with a fixed number of its
nearest neighbors. For a state-action pair, we simply treat the actions as
additional feature vectors of individual agent vertices. Figure 3 illustrates
the resulting ${\rm E}(3)$-equivariant action-value critic and observation-
based actor for MADDPG, where modules $G_{s,a}(\cdot,\cdot)$ and
$G_{o}(\cdot)$ generate the corresponding Euclidean graphs.

Figure 3: Architectures for ${\rm E}(3)$-equivariant MADDPG.

We below highlight several implementation considerations. More details are
provided in the appendix.

SEGNN. For our actor-critic architecture, we employ steerable ${\rm E}(3)$
equivariant GNNs (SEGNNs), a recently developed E3-MPNN model that has
superior performance on supervised learning tasks in computational physics and
chemistry [10]. SEGNNs split the input set of feature vectors into vertex
feature vectors and edge feature vectors, $\mathbf{f}^{\rm
in}=(\mathbf{f}^{\rm node},\mathbf{f}^{\rm edge})$, which comprises so-called
steerable feature vectors concatenated by $(2l+1)$-dimensional vectors with
$l=0,1,...$, often representing properties of the nodes (i.e., vertices) and
edges. For example, in Cooperative Navigation, the node feature vector of
agent $i$ is $\mathbf{f}^{\rm
node}_{i}=[\mathbf{v}_{i},\left\lVert\mathbf{v}_{i}\right\rVert,\mathbf{a}_{i},\left\lVert\mathbf{a}_{i}\right\rVert,\rm
node\\_type]$, which is the concatenation of $(2l+1)$-dimensional vectors with
$l\in\\{0,1\\}$.

Observability. We adopt the paradigm of centralized training and decentralized
execution, where the centralized critic can fully observe the state, while the
local actors are observation-based with partial observability in general. For
instance, in Cooperative Navigation, the velocities of other agents are not
observable. To enforce uniform dimensionality required by SEGNN, we handle
missing quantities for certain nodes due to partial observability by padding
dummy vectors of zeros.

##  6 Experiments

Environments. We choose the popular cooperative MARL benchmarks Multi-Agent
Particle Environment (MPE) and more challenging StarCraft Multi-Agent
Challenge (SMAC) to evaluate the effectiveness of our ${\rm E}(3)$-equivariant
multi-agent actor-critic methods described in 5. In MPE, there are three
scenarios, Coopertive Navigation, Coopertive Push, and Predator and Prey,
where the collective goals of the controllable agents are to navigate the
landmarks, push a ball to a target location, and catch all the preys,
respectively. All scenarios in MPE fully satisfy the requirements of ${\rm
E}(3)$-symmetric MGs. In SMAC, a group of controllable ally agents fights
against enemy agents. The selected scenarios are 8m_vs_9m with hard difficulty
and 6h_vs_8z with super hard difficulty.

Baselines. In MPE, we choose MADDPG as the framework of the algorithms. We
consider the classic implementation of both actor and critic by MLPs as the
baseline. Another baseline [15] achieving state-of-the-art performance in MPE
implements the critic by a graph convolutional neural network (GCN) that has
no guarantee of being ${\rm E}(3)$-invariant. Our algorithms incorporate ${\rm
E}(3)$-invariancy in critic and/or actor by SEGNN-based implementations. We
denote the algorithms in the format of [<critic_type>, <actor_type>], with the
baselines being [MLP, MLP] and [GCN, MLP] and our algorithms [SEGNN, SEGNN]
and [SEGNN, MLP]. In SMAC, the framework of the algorithms is MAPPO, where
both actor and critic are commonly implemented by recrrent neural networks
(RNNs) to incorporate trajectory-level information. However, group-
equivariancy in RNNs needs further technical treatments so here we focus on
non-recurrent MLP-based baselines, denoted as MAPPO-[MLP, MLP]. Another
popular baseline we consider is QMIX [26] with recurrency, i.e., the value
function is implemented by a RNN. Due to the categorical nature of SMAC’s
action space, our algorithm only incorporates ${\rm E}(3)$-invariancy in the
critic, denoted as MAPPO-[SEGNN, MLP].

Results overview. In MPE, the results show that the SEGNN-based critic and/or
actor outperforms the baselines. Further, since the SEGNN-based architecture
can deal with point clouds with an arbitrary number of points, the capability
of zero-shot learning and transfer learning is empirically verified in MPE.
Moreover, the emergence of invariancy of the baselines is proved in all
scenarios of MPE. In SMAC, the experiments show that even the environment only
partially satisfies the requirements of ${\rm E}(3)$-symmetric MGs, our SEGNN-
based architecture can still be better performed in 6h_vs_8z. However, in
SMAC, there is no obvious emergence of invariancy in MLP-based architectures.

###  6.1 Results on MPE

Figure 4: Learning performance of our SEGNN-based actor-critic methods against
baselines.

Performance of SEGNN-based algorithm against baselines. In MPE, Figure 4 shows
the learning curves comparing our SEGNN-based architecture described in
Section 5 against the baselines of MLP and GCN-based architecture. The result
clearly illustrates the effectiveness of the SEGNN-based algorithm.
Specifically, by only using the SEGNN-based critic, i.e., [SEGNN, MLP] shown
in the green curve, the learned architecture has already outperformed the
baselines [GCN, MLP] and [MLP, MLP], shown in the blue and orange curves,
respectively, in all scenarios in MPE. There is a further performance boosting
in Push_N3, Prey_N3, Navigation_N6, and Prey_N6 if we also use SEGNN-based
actor, i.e., [SEGNN, SEGNN] shown with the red curves.

Capabilities of zero-shot/transfer learning.

Figure 5: Performance of zero-shot and transfer learning (black curve).

Since SEGNN-based architectures can deal with point clouds of variable numbers
of points, it is a natural question if they can perform well in different
scenarios with similar setups, i.e., zero-shot learning. To answer this
question, we test the performance of the SEGNN-based actors learned in
Navigation_N3, Push_N3, and Prey_N3 in Navigation_N6, Push_N6, and Prey_N6,
respectively, which are scenarios with more agents but with the same
corresponding goals. The performance is normalized by linear mapping according
to the performance of [SEGNN, SEGNN], whose initial performance is set to 0,
and the final performance is set to 1. The result is averaged across all seeds
and scenarios, plotted in Figure 5. Figure 5 illustrates that the SEGNN-based
architecture learned in the scenarios with 3 agents shown in the black curve
is better performed at step $0$, which empirically proves its good capability
of zero-shot learning. Further, we can continue training the SEGNN-based
architecture learned in scenarios with 3 agents in the corresponding 6 agents
scenarios to show its capability of transfer learning. As shown in Figure 5,
the effectiveness of transfer learning is empirically verified by the
transferred architecture’s faster convergence rate than the non-transferred
counterpart.

Emergence of Euclidean invariancy. The GCN- and MLP-based architectures are by
construction neither invariant to rotations nor translations with general
weights. However, they may gradually adapt to have such abilities after
training with a large number of data with invariant transformation, as shown
in some previous works on data augmentation [27] and contrastive learning
[28]. Translation invariancy for actors is already achieved in SMAC due to the
missing absolute positions in the observation, so it is not included here. Due
to space limit, we only show part of the results in Figure 6 and Figure 8, and
the complete results are in the appendix. The invariancy measures similar to
Equation (1) are also described in the appendix. By construction, the larger
the values of those measurements are, the closer the behaviors of the non-
SEGNN-based architectures are compared to those of the SEGNN-based
architectures in terms of their invariancy to the corresponding
transformations.

Figure 6: The emergence of invariancy and equivariancy in non-SEGNN-based
critic and actor, respectively, in Navigation_N3 in MPE.

In Navigation_N3 in MPE, as illustrated in Figure 6, the GCN-based critic with
permutation invariancy has better rotation- and translation-invariancy for the
whole training process. One possible reason is that for certain configurations
of the state, permutation invariancy is a special type of Euclidean
invariancy, e.g., 6 agents whose positions are in a circle with $60^{\circ}$
between adjacent ones, which displays a rotation-invariancy of
$\rm{rot}_{60^{\circ}}$. However, there is no increase in rotation- and
translation-invariancy for both GCN- and MLP-based critics, which may explain
why actors learned with SEGNN-based critics have better performance. On the
other hand, the actor learned with a SEGNN-based critic emerges better
rotation- and translation-invariancy than the MLP and GCN baselines. The actor
learned with a GCN-based critic achieves similar rotation-invariancy but worse
translation-invariancy than the one learned with a MLP-based critic. Note that
the translation-invariancy for actors is initially high, because in the
observation only the agent’s own position is absolute and can be modified by
translation, whereas all other values are relative and translation-invariant.
The randomly initialized actors will therefore output similar actions based on
similar observations.

###  6.2 Results on SMAC

Performance of SEGNN-based algorithm against baselines. The scenarios in SMAC
[29] are competitve in nature, so the invariancy of the game breaks due to the
non-invariant behaviors of the uncontrollable enemies. Another possible reason
of breaking invariancy is that the categorical actions in SMAC are not
Euclidean spaces, as required by ${\rm E}(3)$-symmetric Markov game.
Therefore, we may not observe the big increase of performance as the ones
shown in MPE, especially in the non-competing ones navigation and push. We
indeed see a mixed of performance in Figure 7 that the SEGNN-based critic
helps learn a better performed actor in 6h_vs_8z but not in 8m_vs_9m.

Figure 7: Comparison of our SEGNN-based architecture with baselines. The last
actions are disabled. MAPPO is the non-recurrent version, and the QMIX is the
recurrent version.

Emergence of Euclidean invariancy. In SMAC, the invariancy measures are
similar to the counterparts in MPE, defined in the appendix. As illustrated in
Figure 8, there is no obvious emergence of the rotation-invariancy for both
actor and critic. This can be caused by the competitive nature of the
scenarios in SMAC, where we also see a decrease of actors’ translation-
invariancy in competitive scenarios Prey_N3 and Prey_N6, as shown in the
appendix. Another possible reason is that some of the categorical actions, the
move directions {north, south, east, west}, are only rotation-equivariant to
multiples of $90^{\circ}$ instead of arbitrary angles and threfore break the
overall invariancy of the game.

Figure 8: The emergence of invariancy and equivariancy in non-SEGNN-based
critic and actor, respectively, in 6h_vs_8z and 8m_vs_9m in SMAC.

##  7 Conclusion

In this paper, we have developed formalisms and methods for exploiting
symmetric structures in cooperative multi-agent reinforcement learning, with a
focus on ${\rm E}(3)$ Euclidean symmetries. Specifically, we have formulated
the novel notion of group-symmetric Markov games and derived its key
properties that admit group-symmetric optimal values and policies. Consistent
with these properties, we have discovered the emergence of Euclidean
symmetries in vanilla MLP-based multi-agent actor-critic architectures. Then,
we have developed ${\rm E}(3)$-equivariant message passing actor-critic
architectures that specifically suit group-symmetric Markov games, which
results in superior sample efficiency and generalization capabilities.

Limitations. We observe two limitations of this work. First, the proposed
method requires knowledge and annotation of strict symmetries inherent in the
multi-agent task, which might not be easily available. This prompts future
work of automatic discovery of symmetries, which can even be approximate.
Second, we are restricted to memory-less, non-recurrent architectures in this
work even under partial observability. This is because realizing group-
equivariancy in recurrent neural networks needs further technical treatments,
which can be another future work direction.

## References

  * [1] Wikipedia contributors.  Noether’s theorem — Wikipedia, the free encyclopedia.  https://en.wikipedia.org/w/index.php?title=Noether%27s_theorem&oldid=1098483832, 2022\.  [Online; accessed 21-July-2022].
  * [2] Ian Goodfellow, Yoshua Bengio, and Aaron Courville.  Deep Learning.  MIT Press, 2016.  http://www.deeplearningbook.org.
  * [3] Ryan Lowe, Yi I Wu, Aviv Tamar, Jean Harb, OpenAI Pieter Abbeel, and Igor Mordatch.  Multi-agent actor-critic for mixed cooperative-competitive environments.  In Advances in neural information processing systems, pages 6379–6390, 2017.
  * [4] Yaodong Yang, Rui Luo, Minne Li, Ming Zhou, Weinan Zhang, and Jun Wang.  Mean field multi-agent reinforcement learning.  In International Conference on Machine Learning, pages 5571–5580. PMLR, 2018.
  * [5] Elise van der Pol, Herke van Hoof, Frans A Oliehoek, and Max Welling.  Multi-agent MDP homomorphic networks.  In International Conference on Learning Representations, 2022.
  * [6] Dingyang Chen, Yile Li, and Qi Zhang.  Communication-efficient actor-critic methods for homogeneous markov games.  In International Conference on Learning Representations, 2022.
  * [7] Lloyd S Shapley.  Stochastic games.  Proceedings of the national academy of sciences, 39(10):1095–1100, 1953.
  * [8] Nathaniel Thomas, Tess Smidt, Steven Kearnes, Lusann Yang, Li Li, Kai Kohlhoff, and Patrick Riley.  Tensor field networks: Rotation-and translation-equivariant neural networks for 3d point clouds.  arXiv preprint arXiv:1802.08219, 2018.
  * [9] Mario Geiger and Tess Smidt.  e3nn: Euclidean neural networks, 2022.
  * [10] Johannes Brandstetter, Rob Hesselink, Elise van der Pol, Erik J Bekkers, and Max Welling.  Geometric and physical quantities improve e(3) equivariant message passing.  In International Conference on Learning Representations, 2022.
  * [11] Balaraman Ravindran and Andrew G Barto.  Symmetries and model minimization in markov decision processes, 2001.
  * [12] Misha Laskin, Kimin Lee, Adam Stooke, Lerrel Pinto, Pieter Abbeel, and Aravind Srinivas.  Reinforcement learning with augmented data.  Advances in neural information processing systems, 33:19884–19895, 2020.
  * [13] Denis Yarats, Ilya Kostrikov, and Rob Fergus.  Image augmentation is all you need: Regularizing deep reinforcement learning from pixels.  In International Conference on Learning Representations, 2021.
  * [14] Elise Van der Pol, Daniel Worrall, Herke van Hoof, Frans Oliehoek, and Max Welling.  Mdp homomorphic networks: Group symmetries in reinforcement learning.  Advances in Neural Information Processing Systems, 33:4199–4210, 2020.
  * [15] 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, pages 590–602. PMLR, 2020.
  * [16] Jiaoyang Li, Daniel Harabor, Peter J Stuckey, Hang Ma, Graeme Gange, and Sven Koenig.  Pairwise symmetry reasoning for multi-agent path finding search.  Artificial Intelligence, 301:103574, 2021.
  * [17] Víctor Garcia Satorras, Emiel Hoogeboom, and Max Welling.  E(n) equivariant graph neural networks.  In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 9323–9332. PMLR, 18–24 Jul 2021.
  * [18] Kristof Schütt, Oliver Unke, and Michael Gastegger.  Equivariant message passing for the prediction of tensorial properties and molecular spectra.  In International Conference on Machine Learning, pages 9377–9388. PMLR, 2021.
  * [19] Bowen Jing, Stephan Eismann, Patricia Suriana, Raphael JL Townshend, and Ron Dror.  Learning from protein structure with geometric vector perceptrons.  arXiv preprint arXiv:2009.01411, 2020.
  * [20] Tuan Le, Frank Noe, and Djork-Arné Clevert.  Representation learning on biomolecular structures using equivariant graph attention.  In The First Learning on Graphs Conference, 2022.
  * [21] Marc Finzi, Samuel Stanton, Pavel Izmailov, and Andrew Gordon Wilson.  Generalizing convolutional neural networks for equivariance to lie groups on arbitrary continuous data.  In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 3165–3176. PMLR, 13–18 Jul 2020\.
  * [22] David S Dummit and Richard M Foote.  Abstract algebra, volume 1999.  Prentice Hall Englewood Cliffs, NJ, 1991.
  * [23] Chao Yu, Akash Velu, Eugene Vinitsky, Jiaxuan Gao, Yu Wang, Alexandre Bayen, and Yi Wu.  The surprising effectiveness of ppo in cooperative multi-agent games.  Advances in Neural Information Processing Systems, 35:24611–24624, 2022.
  * [24] Bo Zhao, Nima Dehmamy, Robin Walters, and Rose Yu.  Symmetry teleportation for accelerated optimization.  In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022.
  * [25] Bo Zhao, Iordan Ganev, Robin Walters, Rose Yu, and Nima Dehmamy.  Symmetries, flat minima, and the conserved quantities of gradient flow.  In The Eleventh International Conference on Learning Representations, 2023.
  * [26] Tabish Rashid, Gregory Farquhar, Bei Peng, and Shimon Whiteson.  Weighted qmix: Expanding monotonic value function factorisation for deep multi-agent reinforcement learning.  Advances in neural information processing systems, 33:10199–10210, 2020.
  * [27] Luis Perez and Jason Wang.  The effectiveness of data augmentation in image classification using deep learning, 2017.
  * [28] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton.  A simple framework for contrastive learning of visual representations.  In International conference on machine learning, pages 1597–1607. PMLR, 2020.
  * [29] Mikayel Samvelyan, Tabish Rashid, Christian Schroeder de Witt, Gregory Farquhar, Nantas Nardelli, Tim G. J. Rudner, Chia-Man Hung, Philip H. S. Torr, Jakob Foerster, and Shimon Whiteson.  The starcraft multi-agent challenge, 2019.
  * [30] Sahand Rezaei-Shoshtari, Rosie Zhao, Prakash Panangaden, David Meger, and Doina Precup.  Continuous MDP homomorphisms and homomorphic policy gradient.  In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022.

##  Appendix A Proof of Theorem 1

We first prove property (iv) in Section A.1 and then properties (i), (ii), and
(iii) in Section A.2.

###  A.1 Proof of property (iv)

This property can be directly derived by the definition of $G$-invariant MG
policies:

$\displaystyle\nabla_{\theta}\pi_{\theta}(a|s)=$
$\displaystyle\lim_{\Delta\theta\to
0}\frac{\pi_{\theta+\Delta\theta}(a|s)-\pi_{\theta}(a|s)}{\Delta}$
$\displaystyle=$ $\displaystyle\lim_{\Delta\theta\to
0}\frac{\pi_{\theta+\Delta\theta}(K^{s}_{g}[a]~{}|~{}L_{g}[s])-\pi_{\theta}(K^{s}_{g}[a]~{}|~{}L_{g}[s])}{\Delta}$
$\displaystyle=$
$\displaystyle\nabla_{\theta}\pi_{\theta}(K^{s}_{g}[a]~{}|~{}L_{g}[s])$

where the second equality holds because we assume $\pi_{\theta}$ is
$G$-invariant for any $\theta$.

###  A.2 Proof of properties (i), (ii), and (iii)

These properties can be established by extending the notion of single-agent
MDP homomorphism and its properties to MGs.

######  Definition 4 (MG homomorphism).

An MG homomorphism $(l,k_{s},h_{s})$ is a surjective map from an MG
$\langle\mathcal{N},\mathcal{S},\mathcal{A},P,r,o\rangle$ onto an abstract MG
$\langle\mathcal{N},\overline{\mathcal{S}},\overline{\mathcal{A}},\overline{P},\overline{r},\overline{o}\rangle$
by surjective maps $l:\mathcal{S}\to\overline{\mathcal{S}}$,
$k_{s}:\mathcal{A}\to\overline{\mathcal{A}}$, and
$h_{s}:\mathcal{O}\to\overline{\mathcal{O}}=\overline{\mathcal{O}}^{1}\times\cdots\times\overline{\mathcal{O}}^{N}$,
such that

$\displaystyle r(s,a)=\overline{r}(l(s),k_{s}(a))$ $\displaystyle\forall
s\in\mathcal{S},a\in\mathcal{A}$ (2) $\displaystyle
P([s^{\prime}]_{l}|s,a)=\overline{P}(l(s^{\prime})|l(s),k_{s}(a))$
$\displaystyle\forall s,s^{\prime}\in\mathcal{S},a\in\mathcal{A}$ (3)
$\displaystyle o(l(s))=h_{s}(o(s))$ $\displaystyle\forall s\in\mathcal{S}.$
(4)

######  Definition 5 (Policy lifting in MG homomorphisms).

We define policy lifting for state-based and observation-based policies
separately, assuming full observability:

  * •

State-based MG policy lifting. Let
$\pi_{\uparrow}:\mathcal{S}\to\Delta(\mathcal{A})$ and
$\overline{\pi}:\overline{\mathcal{S}}\to\Delta(\overline{\mathcal{A}})$ be
two state-based policies in the actual and abstract MGs, respectively. We say
$\pi_{\uparrow}$ is a lift of $\overline{\pi}$, denoted as
$\pi_{\uparrow}=\texttt{lift}(\overline{\pi})$, if $\sum_{a\in
k_{s}^{-1}(\overline{a})}\pi_{\uparrow}(a|s)=\overline{\pi}(\overline{a}|l(s))$
for any $s\in\mathcal{S}$ and $\overline{a}\in\overline{\mathcal{A}}$.

  * •

Observation-based MG policy lifting. Let
$\nu_{\uparrow}=\\{\nu_{\uparrow}^{i}:\mathcal{O}^{i}\to\Delta(\mathcal{A}^{i})\\}_{i\in\mathcal{N}}$
and
$\overline{\nu}=\\{\overline{\nu}^{i}:\overline{\mathcal{O}}^{i}\to\Delta(\overline{\mathcal{A}}^{i})\\}_{i\in\mathcal{N}}$
be two observation-based policies in the actual and abstract MGs,
respectively. We say $\nu_{\uparrow}$ is a lift of $\overline{\nu}$, denoted
as $\nu_{\uparrow}=\texttt{lift}(\overline{\nu})$, if $\sum_{a\in
k_{s}^{-1}(\overline{a})}\nu_{\uparrow}(a|o(s))=\overline{\nu}(\overline{a}|h_{s}(o(s)))$
for any $s\in\mathcal{S}$ and $\overline{a}\in\overline{\mathcal{A}}$.

######  Theorem 2 (Value equivalence in MG homomorphisms).

Consider an MG homomorphism $(l,k_{s},h_{s})$ from MG
$M=\langle\mathcal{N},\mathcal{S},\mathcal{A},P,r,o\rangle$ with bijective
observation functions to abstract MG
$\overline{M}=\langle\mathcal{N},\overline{\mathcal{S}},\overline{\mathcal{A}},\overline{P},\overline{r},\overline{o}\rangle$.
We have

$\displaystyle V_{*}(s)=\overline{V}_{*}(l(s)),\quad
Q_{*}(s,a)=\overline{Q}_{*}(l(s),k_{s}(a))\quad\text{for any
$s\in\mathcal{S},a\in\mathcal{A}$.}$ (5)

For a state-based abstract policy $\overline{\pi}$ with its lift
$\pi_{\uparrow}$, we have

$\displaystyle V_{\pi_{\uparrow}}(s)=\overline{V}_{\overline{\pi}}(l(s)),\quad
Q_{\pi_{\uparrow}}(s,a)=\overline{Q}_{\overline{\pi}}(l(s),k_{s}(a))\quad\text{for
any $s\in\mathcal{S},a\in\mathcal{A}$.}$ (6)

For an observation-based abstract policy $\overline{\nu}$ with its lift
$\nu_{\uparrow}$, we have

$\displaystyle
V_{\nu_{\uparrow}}(o(s))=\overline{V}_{\overline{\nu}}(h_{s}(o(s))),\quad
Q_{\nu_{\uparrow}}(s,a)=\overline{Q}_{\overline{\nu}}(h_{s}(o(s)),k_{s}(a))\quad\text{for
any $s\in\mathcal{S},a\in\mathcal{A}$.}$ (7)

###### Proof of Theorem 2.

For state-based policies, we use similar proof techniques for single-agent MDP
homomorphisms [11, 30].

Under bijective observation functions, we can prove (7) by first translating
them into state-based policies and then applying (6). ∎

#### Proof of properties (i) and (iii).

We first establish that a $G$-symmetric MG induces a MG homomorphism, where
$G$-invariant MG policy can be viewed as lifted from the induced abstract MG.
Then, properties (i) and (iii) directly follow from Theorem 2.

Specifically, consider a $G$-symmetric MG as defined in Definition 1. Define
maps $(l,k_{s},h_{s})$ as follows, such that the state-action-observation
tuples in the same orbit under $G$ map to the same abstraction:

$\displaystyle l(s)=l(L_{g}[s]),\quad
k_{s}(a)=k_{L_{g}[s]}(K^{s}_{g}[a]),\quad
h_{s}(o(s))=h_{L_{g}[s]}(o(L_{g}[s]))=h_{L_{g}[s]}(H^{s}_{g}[o(s)])$

for any $s\in\mathcal{S},a\in\mathcal{A},g\in G$. It is easy to verify that
maps $(l,k_{s},h_{s})$ are surjective and satisfy conditions (2), (3), and (4)
in Definition 4, and therefore maps $(l,k_{s},h_{s})$ induce an MG
homomorphism. Property (i) then directly follows from (5).

Under this an MG homomorphism, a $G$-invariant policy induces an abstract
policy,
$\pi(a|s)=\pi(K^{s}_{g}[a]~{}|~{}L_{g}[s])=\overline{\pi}(\overline{a}|\overline{s})$,
where
$(\overline{s},\overline{a})=(l(s),k_{s}(a))=(l(L_{g}[s]),k_{L_{g}[s]}(K^{s}_{g}[a]))$.
Because $K^{s}_{g}[\cdot]$ is reversible via $K^{s}_{g^{-1}}[\cdot]$, $k_{s}$
is actually bijective. To see this, we can pick an arbitrary state-action pair
in every state-action orbit as the canonical state-action pair for that orbit,
then the mapping of any state-action pair can be done via two steps, from the
state-action pair to the canonical state-action pair and then to the
abstraction, with both steps being bijective. Thus, we have
$\sum_{a^{\prime}\in
k_{s}^{-1}(\overline{a})}\pi(a^{\prime}|s)=\pi(a|s)=\overline{\pi}(\overline{a}|\overline{s})$,
and therefore $\pi$ is a lift policy from $\overline{\pi}$. Property (iii)
then directly follows from (6).

#### Proof of property (ii).

This policy can be induced from the optimal $G$-invariant value function.
Letting $Q_{*}$ be the optimal action-value function that is $G$-invariant,
the existence of which has been proved as property (i), which induces a
deterministic optimal policy $\pi_{*}$ as the greedy policy with respect to
$Q_{*}$, i.e., $\pi_{*}(s)=\operatorname*{arg\,max}_{a}Q_{*}(s,a)$ for any
$s\in\mathcal{S}$. Since $Q_{*}$ is $G$-invariant, it is easy to see that
$\pi_{*}$ is also $G$-invariant, $K^{s}_{g}[\pi_{*}(s)]=\pi_{*}(L_{g}[s])$.

##  Appendix B Examples of group-symmetric MGs

###  B.1 ${\rm E}(3)$-symmetric MGs

It is quite common that in the 3D physical world, entities’ positions and some
other physical quantities are described with respect to an arbitrary reference
whose change has no impact on the behaviors of the entities. Such scenarios
can be described as an ${\rm E}(3)$-symmetric MGs. Examples include traffic
with vehicles, team sports, surveillance with drones, and games such as SMAC
and MPE.

Below we highlight three MARL benchmark games to show the generality of ${\rm
E}(3)$-symmetric MGs.

#### Multi-Agent Mujoco.

In Multi-Agent Mujoco, a given single robotic agent is split into several sub-
parts (agents). Each (sub-part) agent can be viewed as a point in the 3D point
cloud, with the its centroid as the 3D position. The ${\rm E}(3)$-equivariant
features can be velocities, forces, etc, and the ${\rm E}(3)$-intvariant
features can be id, unit_type, etc. The actions are the forces applied to each
sub-parts.

#### Google Research Football (GRF)

In GRF, each unit in the field, such as a player and a ball can be viewed as a
point in the 3D point cloud, with ${\rm E}(3)$-equivariant features such as
the velocity and ${\rm E}(3)$-invariant features such as the unit_type. The
actions are categorical, with movement actions and some other non-movement
actions such as shooting and passing. The non-movement actions are ${\rm
E}(3)$-invariant. If the player can move to any direction, i.e., the movement
actions are continuous, then the game satisfies the requirement of the action
space in (ii). The scenarios in GRF are competitive where the (uncontrollable)
enemies are viewed as part of the environment. The game is an ${\rm
E}(3)$-symmetric MGs if the enemies’ policies are ${\rm E}(3)$-invariant.

#### SMAC

In SMAC, each unit in the combat can be view as a point in the 3D point cloud,
with dummy $z$ coordinate. There are some competitive scenarios in SMAC, where
the controllable agents are fighting against some (uncontrollable) enemies
which are viewed as part of the environment. Therefore, similar to GRF,
whether the game is an ${\rm E}(3)$-symmetric MGs or not depends on the ${\rm
E}(3)$-invariancy of the uncontrollable enemies’ policies. The actions are
also categorical including movement actions and some other ${\rm
E}(3)$-invariant non-movement actions such as attacking.

###  B.2 ${\rm S}_{N}$-symmetric MGs

Besides the Euclidean transformation, the permutation is another common
transformation in the physical world. Intuitively, for homogeneous entities
with the same exact behaviors, permute them will have no impact. Such multi-
agent symmetries can be captured by the symmetric group ${\rm S}_{N}$ with
permutations as the group actions. The Homogeneous MGs, which is ${\rm
S}_{N}$-symmetric MGs under our definition, is formallly defined by the work
[6] with the permutation transformation defined on state, action, observation,
and the transition and the reward function. The benefit of enforcing
permutation-invariancy has been found beneficial by [6, 15]. Our definition of
the ${\rm G}$-symmetric MGs is general enough to cover it.

The examples include MPE tasks with homogeneous agents, SMAC scenarios with
homogeneous ally units, team sports with homogeneous players (assume players
have the same capabilities), traffic with homogeneous vehicles, and
surveillance with homogeneous drones.

##  Appendix C Experiment details

Below we describe in general notation of states and observations in scenarios
in MPE and SMAC.

###  C.1 MPE

Multi-Agent Particle Environment (MPE) with the efficient implementation by
[15] is a classical benchmark with homogeneous agents for multi-agent
reinforcement learning, each of which has versions with $N=3,6$ agents,
respectively. These MPE environments can be cast as ${\rm E}(3)$-Symmetric
MGs, where we have dummy $z$ coordinate. Below we describe the general form of
state and observation in all scenarios of MPE, and the corresponding state-
action based point cloud and observation-based point cloud which are processed
by SEGNN-based critic and actor, respectively, and also the details of each
scenarios in MPE.

Notation We denote the set of agents, landmarks, and preys, which are basic
units in scenarios of MPE, as $\mathcal{N}^{a}=\\{1,...,N^{a}\\}$,
$\mathcal{N}^{l}=\\{N^{a}+1,...,N^{l}\\}$, and
$\mathcal{N}^{p}=\\{N^{a}+N^{l}+1,...,N+N^{l}+N^{p}\\}$, where
${N^{a}},{N^{l}}$, and ${N^{p}}$ are the number of agents, landmarks and
preys, respectively. Here only the agents are controllable so $N^{a}=N$. The
set of nodes
$\mathcal{V}=\mathcal{N}^{a}\cup\mathcal{N}^{l}\cup\mathcal{N}^{p}$. The
absolute positions associated with $\mathcal{N}^{a},\mathcal{N}^{l}$ and
$\mathcal{N}^{p}$ are
$\mathbf{x}^{a}=\\{\mathbf{x}_{i}\\}_{i\in\mathcal{N}^{a}},\mathbf{x}^{l}=\\{\mathbf{x}_{v}\\}_{v\in\mathcal{N}^{l}}$
and $\mathbf{x}^{p}=\\{\mathbf{x}_{v}\\}_{v\in\mathcal{N}^{p}}$, respectively.
Let $\mathbf{x}=\mathbf{x}^{a}\cup\mathbf{x}^{l}\cup\mathbf{x}^{p}$, which is
the set of positions associated with the set of nodes $\mathcal{V}$. The
absolute velocities associated with $\mathcal{N}^{a}$ and $\mathcal{N}^{p}$
are $V^{a}=\\{\mathbf{v}_{i}\\}_{i\in\mathcal{N}^{a}}$ and
$V^{p}=\\{\mathbf{v}_{v}\\}_{v\in\mathcal{N}^{p}}$, respectively. The
landmarks are fixed, so the associate velocities is
$V^{l}=\\{\mathbf{0}\\}_{i\in\mathcal{N}^{l}}$. Let $V=V^{a}\cup V^{l}\cup
V^{p}$, which is the set of velocities associated with the set of nodes
$\mathcal{V}$.

State The state consists of the positions $\mathbf{x}$ of the set of entities
$\mathcal{N}$, with the associated features
$\mathbf{f}=\\{\mathbf{f}_{v}=\mathbf{v}_{v}\\}_{v\in\mathcal{V}}$. The state
is therefore a point cloud
$\\{(\mathbf{x}_{v},\mathbf{f}_{v})\\}_{v\in\mathcal{V}}$, which satisfies the
requirement (i) of ${\rm E}(3)$-symmetric MGs.

Observation The agent $i$’s local observation consists of the relative
positions
$\mathbf{x}^{i}=\\{\mathbf{x}_{i}^{i}=\mathbf{x}_{i}\\}\cup\\{\mathbf{x}^{v}_{i}=\mathbf{x}_{v}-\mathbf{x}_{i}\\}_{v\in\mathcal{N}\setminus\\{i\\}}$
of the set of entities $\mathcal{N}$, with the associated (relative) features
$\mathbf{f}^{i}=\\{\mathbf{f}_{i}^{i}=\mathbf{v}_{i}\\}\cup\\{\mathbf{f}_{v}^{i}=\mathbf{0}\\}_{v\in\mathcal{V}\setminus\\{i\\}}$.
(Other agents’ velocities are not observable). The agent $i$’s local
observation is therefore a point cloud
$\\{(\mathbf{x}_{v}^{i},\mathbf{f}_{v}^{i})\\}_{v\in\mathcal{V}}$ from agent
$i$’s perspective, which satisfies the requirement (iii) of ${\rm
E}(3)$-symmetric MGs.

Action The local action spaces are absolute velocities, and are therefore
Euclidean spaces which satisfies the requirement of (ii). Denote the set of
actions for the controllable agents as
$A^{a}=\\{\mathbf{a}_{i}\\}_{i\in\mathcal{N}^{a}}$.

The details of each scenarios in MPE is as the following.

Cooperative Navigation: The collective goal of agents is to cover all the
landmarks. There are two versions with $N^{l}=3,6$ landmarks for $N=3,6$
agents, respectively. There are no preys so $N^{p}=0$.

Cooperative Push: The collective goal of agents is to push a large ball to a
target position. There are two versions with $N^{l}=2,2$ landmarks for $N=3,6$
agents, respectively. There are no preys so $N^{p}=0$.

Predator-and-Prey: The collective goal of slowly moving agents (predators) is
to capture some fast moving preys. The preys are pre-trained and controlled by
the environment. There are $N^{p}=1,2$ preys and $N^{l}=2,3$ landmarks
(blocks) for $N=3,6$ agents (predators), respectively.

###  C.2 SMAC

The StarCraft Multi-Agent Challenge (SMAC) [29] has become one of the most
popular MARL benchmarks. All scenarios in SMAC can be described by ${\rm
E}(3)$-symmetric Markov games in a similar way to MPE, as detailed described
in the Appendix. We choose the Hard scenario 8m_vs_9m and Super Hard scenario
6h_vs_8z to evaluate our proposed algorithm, which has 8 agents and 6 agents,
respectively.

Notation We denote the set of controllable ally agents and uncontrollable
enemies, which are basic units in scenarios of SMAC, as
$\mathcal{N}^{a}=\\{N+1,...,N^{a}\\}$ and
$\mathcal{N}^{e}=\\{N^{a}+1,...,N^{a}+N^{e}\\}$, where ${N}^{a}$ and ${N^{e}}$
are the number of agents and enemies, respectively. Here only agents are
controllable and so $N^{a}=N$. The set of nodes
$\mathcal{V}=\mathcal{N}^{a}\cup\mathcal{N}^{e}$. The absolute positions
associated with $\mathcal{N}^{a}$ and $\mathcal{N}^{e}$ are
$\mathbf{x}^{a}=\\{\mathbf{x}_{i}\\}_{i\in\mathcal{N}^{a}}$ and
$\mathbf{x}^{e}=\\{\mathbf{x}_{v}\\}_{v\in\mathcal{N}^{e}}$, respectively. The
local action spaces of the controllable ally agents are categorical, which is
the union of the set of move directions, attack enemies, stop and no
operation, i.e., $\mathcal{A}^{i}=\\{\text{north, south, east,
west}\\}\cup\\{\text{attack[enemy\\_id]}\\}_{\text{enemy\\_id}\in\mathcal{N}^{e}}\cup\\{\text{stop,
no-op}\\}$. The health associated with $\mathcal{N}^{a}$ and $\mathcal{N}^{e}$
are $H^{a}=\\{\text{h}_{i}\\}_{i\in\mathcal{N}}$ and
$H^{e}=\\{\text{h}_{v}\\}_{v\in\mathcal{N}^{e}}$, respectively. The cooldown
of the weapons associated with $\mathcal{N}^{a}$ and $\mathcal{N}^{e}$ which
is not applicable are $CD^{a}=\\{\text{cd}_{i}\\}_{i\in\mathcal{N}}$ and
$CD^{e}=\\{\textbf{0}\\}_{v\in\mathcal{N}^{e}}$, respectively. The shield
associated with $\mathcal{N}^{a}$ and $\mathcal{N}^{e}$ are
$SH^{a}=\\{\text{sh}_{i}\\}_{i\in\mathcal{N}}$ and
$SH^{e}=\\{\text{sh}_{v}\\}_{v\in\mathcal{N}^{e}}$, respectively. Let
$H=H^{a}\cup H^{e}$, $CD=CD^{a}\cup CD^{e}$, $SH=SH^{a}\cup SH^{e}$, which are
the sets of health, cooldown, and shield of the allies’ and enemies’ agents
associated with the set of nodes $\mathcal{V}$.

State The state consists of the positions $\mathbf{x}$ of the set of entities
$\mathcal{N}$, with the associated features
$\mathbf{f}=\\{\mathbf{f}_{v}=(\text{h}_{v},\text{cd}_{v},\text{sh}_{v})\\}_{v\in\mathcal{V}}$.
The state is therefore a point cloud
$\\{(\mathbf{x}_{v},\mathbf{f}_{v})\\}_{v\in\mathcal{V}}$, which satisfies the
requirement (i) of ${\rm E}(3)$-symmetric MGs.

Observation Agent $i$’s observation $o^{i}(s)$ only contains information of
itself and some other observable entities, denoted as
$\mathcal{V}^{i}\subseteq\mathcal{V}$. The information of the non-observable
entities are padded as $\mathbf{0}$. From agent $i$’s perspective, denote the
visibility of the entities as
$VI^{i}=\\{\text{vi}_{v}=1\\}_{v\in\mathcal{V}^{i}}\cup\\{\text{vi}_{v}=0\\}_{v\in\mathcal{V}\setminus\mathcal{V}^{i}}$,
and denote the set of (one-hot) move directions $\in\\{\text{north, south,
east, west}\\}$ as
$MD^{i}=\\{\text{md}_{i}\\}\cup\\{\mathbf{0}\\}_{v\in\mathcal{V}\setminus\\{i\\}}$.
(only its own move direction is observable). Then, $o^{i}(s)$ consists of the
relative positions
$\mathbf{x}^{i}=\\{\mathbf{x}_{i}^{i}=\mathbf{0}\\}\cup\\{\mathbf{x}^{v}_{i}=\mathbf{x}_{v}-\mathbf{x}_{i}\\}_{v\in\mathcal{N}\setminus\\{i\\}}$
of the set of entities $\mathcal{N}$, with the associated (relative) features
$\mathbf{f}^{i}=\\{f_{i}^{i}=(\text{agent\\_id}=i,\text{md}_{i},\text{vi}_{i}=1,\|\mathbf{x}_{i}^{i}\|=0,\mathbf{x}_{i}^{i}=\mathbf{0},\text{h}^{i},\text{sh}^{i}\\}\cup\\{f_{v}^{i}=(\text{agent\\_id}=0,\text{md}_{v}=\mathbf{0},\text{vi}_{v},\|\mathbf{x}_{v}^{i}\|,\mathbf{x}_{v}^{i},\text{h}^{v},\text{sh}^{v})\\}_{v\in\mathcal{V}\setminus\\{i\\}}$.
(Other entities’ ids are not observable, so padded as 0). The agent $i$’s
local observation is therefore a point cloud
$\\{(\mathbf{x}_{v}^{i},\mathbf{f}_{v}^{i})\\}_{v\in\mathcal{V}}$ from agent
$i$’s perspective, which satisfies the requirement (iii) of ${\rm
E}(3)$-symmetric MGs.

Action Each agent $i$’s action space is categorical, which is the union of the
sets of move directions, attack enemies, stop and no operation, i.e.,
$\mathcal{A}^{i}=\\{\text{north, south, east,
west}\\}\cup\\{\text{attack[enemy\\_id]}\\}_{\text{enemy\\_id}\in\mathcal{N}^{e}}\cup\\{\text{stop,
no-op}\\}$. Obviously, $\mathcal{A}^{i}$ is not a Euclidean space and
therefore does not satisfy the requirement of (ii).

The details of the two scenarios in SMAC we test our algorithm is as the
following.

8m_vs_9m: 8 controllable ally agents of type Marines are fighting against 9
uncontrollable enemies of type Marines. Shield is not applicable for Marines
so both ${SH}^{a}$ and ${SH}^{e}$ are $\emptyset$.

6h_vs_8z: 6 controllable ally agents of type Hydralisks are fighting against 9
uncontrollable enemies of type Zealots. Shield is not applicable for
Hydralisks so ${SH}^{a}=\emptyset$.

##  Appendix D Implementation details

As described in 5.1, the input to SEGNN is an input Euclidean graph is
represented as a tuple $G^{\rm
in}=(\mathcal{V},\mathcal{E},\mathbf{x},\mathbf{f}^{\rm in})$ where
$\mathcal{V}$ is a set of vertices with 3D positions
$\mathbf{x}_{v}\in\operatorname{\mathbb{R}}^{3}$,
$\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}$ is a set of edges, and
$\mathbf{f}^{\rm in}$ is a set of feature vectors, each associated with a
vertex or an edge. Precisely, the input feature $\mathbf{f}^{\rm in}$ can be
further decomposed into node feature, node attribute, and edge attribute,
i.e., $\mathbf{f}^{\rm in}=(\mathbf{f}^{\rm node}_{\rm
feature},\mathbf{f}^{\rm node}_{\rm attribute},\mathbf{f}^{\rm edge}_{\rm
attribute})$. Note that in MPE and SMAC, entities are in a 2D world, so we pad
the dummy $z$ coordinate of $0$ for them to be in a 3D space whenever
applicable, e.g. velocities, positions, etc.

Below we describe in details, whichever applicable, how to represent state
$s$, state-action pair $(s,a)$, and observation $o^{i}(s)$ as Euclidean graphs
for centralized state-value critic $V(s)$, action-value critic $Q(s,a)$, and
observation-based actor $\nu^{i}(o^{i}(s))$, respectively, in MPE and SMAC.

###  D.1 MPE

In MPE, we build our architecture based on MADDPG, where the critic is based
on state and action pair and therefore we construct state-action based
Euclidean graph processed by ${\rm E}(3)$-invariant critic. We also construct
a observation based Euclidean graph processed by an ${\rm E}(3)$-equivariant
actor.

State-action based Euclidean graph Based on the information in the state
$s=\\{(\mathbf{x}_{v},\mathbf{f}_{v})\\}_{v\in\mathcal{V}}$, $\mathcal{V}$ and
$\mathbf{x}$ have already been well-defined. The graph $\mathcal{E}$ is
densely connected, i.e.,
$\mathcal{E}=\\{(v_{1},v_{2}):v_{1}\in\mathcal{V},v_{2}\in\mathcal{V},v_{1}\neq
v_{2}\\}$. We can pad the dummy $\mathbf{0}$ action for non-controllable
entities, i.e., landmarks and preys, to have actions for all entities:
$A=\\{\mathbf{a}_{i}\\}_{i\in\mathcal{N}^{a}}\cup\\{\mathbf{0}\\}_{v\in\mathcal{N}^{l}}\cup\\{\mathbf{0}\\}_{v\in\mathcal{N}^{p}}$.
We can then design the node feature $\mathbf{f}^{\rm node}_{\rm feature}$,
node attribute $\mathbf{f}^{\rm node}_{\rm attribute}$, and edge attribute
$\mathbf{f}^{\rm edge}_{\rm attribute}$ based on the information in the input
features $\mathbf{f}^{\rm
in}=\mathbf{f}=\\{\mathbf{v}_{v}\\}_{v\in\mathcal{V}}$ and actions $A$. The
node feature of each node consists of its own absolute velocity, the $l_{2}$
norm of its own absolute velocity, its own action, and $l_{2}$ norm of its own
action. Specifically, $\mathbf{f}^{\rm node}_{\rm
feature}=\\{[\mathbf{v}_{v},\left\lVert\mathbf{v}_{v}\right\rVert,\mathbf{a}_{v},\left\lVert\mathbf{a}_{v}\right\rVert]\\}_{v\in\mathcal{V}}$.
We can specify the ${\rm E}(3)$-equivariancy of both absolute velocities and
actions, and ${\rm E}(3)$-invariancy of the associated $l_{2}$ norms in SEGNN
to preserve physical constraints. The node attribute is the set of node_types
$\in\\{\text{agent, landmark, prey}\\}$, i.e., $\mathbf{f}^{\rm node}_{\rm
attribute}=\\{[\text{node\\_type}(v)]\\}_{v\in\mathcal{V}}$. The node types
are ${\rm E}(3)$-invariant. The edge attribute is the set of relative
positions, i.e., $\mathbf{f}^{\rm edge}_{\rm
attribute}=\\{[\mathbf{x}_{v_{1}}-\mathbf{x}_{v_{2}}]\\}_{(v_{1},v_{2})\in\mathcal{E}}$,
which is ${\rm E}(3)$-equivariant.

Figure 9: Illustration of state-action based point cloud and observation-based
point cloud for a scenario in MPE with agent, landmark and prey.

Observation based Euclidean graph The relative positions in the observation
can be restored to the absolute location, i.e.,
$\mathbf{x}^{i}=\\{\mathbf{x}_{i}^{i}=\mathbf{x}_{i}\\}\cup\\{\mathbf{x}_{v}-\mathbf{x}_{i}\\}_{v\in\mathcal{N}\setminus\\{i\\}}\longrightarrow\\{\mathbf{x}_{i}^{i}=\mathbf{x}_{i}\\}\cup\\{\mathbf{x}_{v}-\mathbf{x}_{i}+\mathbf{x}_{i}\\}_{v\in\mathcal{N}\setminus\\{i\\}}$.
Then we can generate the observation based point cloud in almost the same way,
with two differences. The first difference is that due to partial
observability, the velocities of other agents and preys are not available, so
we have
$V^{a}=\\{\mathbf{v}_{i}\\}\cup\\{\mathbf{0}\\}_{j\in\mathcal{N}\setminus\\{i\\}}$
and $V^{p}=\\{\mathbf{0}\\}_{\mathcal{N}^{p}}$. Another difference is that the
observation based point cloud does not condition on actions, so
correspondingly the node features do not contain action related elements and
is only velocity related, i.e., $\mathbf{f}^{\rm node}_{\rm
feature}=\\{[\mathbf{v}_{v},\left\lVert\mathbf{v}_{v}\right\rVert]\\}_{v\in\mathcal{V}}$.

###  D.2 SMAC

In SMAC, we build our architecture based on MAPPO, where the critic is based
on state only and therefore we construct state based Euclidean graph processed
by ${\rm E}(3)$-invariant critic. The action space in SMAC is categorical and
therefore we use a traditional MLP-based actor to process the observation.

State based Euclidean graph Based on the information in the state
$s=\\{(\mathbf{x}_{v},\mathbf{f}_{v})\\}_{v\in\mathcal{V}}$, $\mathcal{V}$ and
$\mathbf{x}$ have already been well-defined. The graph $\mathcal{E}$ is a
nearest neighbor graph degree $k$, i.e.,
$\mathcal{E}=\\{(v_{1},v_{2}):v_{1}\in\mathcal{V},v_{2}\in\mathcal{V},v_{1}\in\text{neighbor}(v_{2},k)\\}$.
We can then design the node feature $\mathbf{f}^{\rm node}_{\rm feature}$,
node attribute $\mathbf{f}^{\rm node}_{\rm attribute}$, and edge attribute
$\mathbf{f}^{\rm edge}_{\rm attribute}$ based on the information in the input
features $\mathbf{f}^{\rm
in}=\mathbf{f}=\\{\mathbf{v}_{v}\\}_{v\in\mathcal{V}}$. The node feature of
each node consists of its health, cooldown, and shield. Specifically,
$\mathbf{f}^{\rm node}_{\rm
feature}=\\{[\text{h}_{v},\text{cd}_{v},\text{sh}_{v}]\\}_{v\in\mathcal{V}}$.
All quantities in node features are ${\rm E}(3)$-invariant. The node attribute
is the set of node_types
$\in\\{\text{[Team,Type]}\\}_{\text{Team}\in\\{\text{ally,
enemy}\\},\text{Type}\in\\{\text{Marines, Hydralisks, Zealots}\\}}$, i.e.,
$\mathbf{f}^{\rm node}_{\rm
attribute}=\\{[\text{node\\_type}(v)]\\}_{v\in\mathcal{V}}$. The node types
are ${\rm E}(3)$-invariant. The edge attribute is the set of relative
positions, i.e., $\mathbf{f}^{\rm edge}_{\rm
attribute}=\\{[\mathbf{x}_{v_{1}}-\mathbf{x}_{v_{2}}]\\}_{(v_{1},v_{2})\in\mathcal{E}}$,
which is ${\rm E}(3)$-equivariant.

##  Appendix E Supplementary results

###  E.1 Invariancy Measure in MPE

In MPE, the metrics for measuring invariancy for actor and critic in terms of
rotation and translation are defined in the following:

$\displaystyle\textstyle{\rm{Invariancy_{Q}^{rot}}}=-\frac{1}{|A|}\sum_{\alpha\in
A}|Q(s,a)-Q({\rm rot}_{\alpha}[s],{\rm rot}_{\alpha}[a])|$ (8)

$\displaystyle\textstyle{\rm{Invariancy_{Q}^{transl}}}=-\frac{1}{|L|}\sum_{l\in
L}|Q(s,a)-Q({\rm transl}_{l}[s],{\rm transl}_{l}[a])|$ (9)

$\displaystyle\textstyle{\rm{Invariancy_{\nu}^{rot}}}=\frac{1}{|A|N}\sum_{i\in\mathcal{N}}\sum_{\alpha\in
A}\cos\left({\rm rot}_{\alpha}[\nu^{i}(o^{i}(s)],~{}\nu^{i}(o^{i}({\rm
rot}_{\alpha}[s]))\right)$ (10)

$\displaystyle\textstyle{\rm{Invariancy_{\nu}^{transl}}}=\frac{1}{|L|N}\sum_{i\in\mathcal{N}}\sum_{l\in
L}\cos\left({\rm transl}_{l}[\nu^{i}(o^{i}(s)],~{}\nu^{i}(o^{i}({\rm
transl}_{l}[s]))\right)$ (11)

,where ${\rm rot}_{\alpha}[\cdot]$ and ${\rm transl}_{l}[\cdot]$ performs the
rotation by $\alpha$ and translation by $l$, respectively, and
$\cos(\cdot,\cdot)$ measures the cosine similarity. $A$ is the list of angles
which we use $[30^{\circ},60^{\circ}\cdots,330^{\circ}]$, $L$ is the list of
translations which we use $[(-l_{x},0),(-0.5l_{x},0),(0.5l_{x},0),(l_{x},0)]$
for translations along $x$ axis and
$[(0,-l_{y}),(0,-0.5l_{y}),(0,0.5l_{y}),(0,l_{y})]$ for translations along $y$
axis (the size of the map is $l_{x}$ by $l_{y}$, where $l_{x}=l_{y}=1,1.5,1$
for the scenarios of push, navigation, and prey, respectively). We calculate
these four metrics by averaging over state and observation collected in
different time steps in $200$ episodes. The ranges of those metrics are not
important. By construction, the larger the values of
${\rm{Invariancy_{Q}^{rot}}},{\rm{Invariancy_{Q}^{transl}}},{\rm{Invariancy_{\nu}^{rot}}},$
and ${\rm{Invariancy_{\nu}^{transl}}}$ are, the closer the behaviors the non-
SEGNN-based architecture are compared to those of the SEGNN-based
architecture, which has the largest possible values for those metrics, in
terms of their invariancy to the corresponding transformations.

###  E.2 The emergence of invariancy in MPE.

Figure 10: The emergence of invariancy and equivariancy in non-SEGNN-based
critic and actor, respectively, in different scenarios.

###  E.3 Invariancy Measure in SMAC

The critic used by MAPPO is a value function, so the invariancy for critic is
defined in terms of $V$ instead of $Q$. The action of controllable ally agents
in SMAC is categorical, so we use KL divergence instead of cosine similarity
to measure the difference between two probability distributions. The action is
the union of the set of move directions, attack enemies, stop and no
operation, i.e., $A^{a}=\\{\text{north, south, east,
west}\\}\cup\\{\text{attack[enemy\\_id]}\\}_{\text{enemy\\_id}\in\mathcal{N}^{e}}\cup\\{\text{stop,
no-op}\\}$. Under rotation, only move directions will be changed. Its hard to
measure how the move direction will change for an arbitrary rotation angle, so
we only consider (counter clockwise) rotation angles of
$[90^{\circ},180^{\circ},270^{\circ}]$, which will roll the move direction
accordingly. For example, for a (counter clockwise) rotation angle of
$90^{\circ}$, move to the north will change to move to the west. The
translation for actor is already achieved in scenarios in SMAC due to the
missing of absolute positions in the observation, so it is not included here.

$\displaystyle\textstyle{\rm{Invariancy_{V}^{rot}}}=-\frac{1}{|A|}\sum_{\alpha\in
A}|V(s)-V({\rm rot}_{\alpha}[s])|$ (12)

$\displaystyle\textstyle{\rm{Invariancy_{V}^{transl}}}=-\frac{1}{|L|}\sum_{l\in
L}|V(s)-V({\rm transl}_{l}[s])|$ (13)

$\displaystyle\textstyle{\rm{Invariancy_{\nu}^{rot}}}=\frac{1}{|A|N}\sum_{i\in\mathcal{N}}\sum_{\alpha\in
A}{\rm KL}\left({\rm
rot}_{\alpha}[\nu^{i}(\cdot|o^{i}(s)],~{}\nu^{i}(\cdot|o^{i}({\rm
rot}_{\alpha}[s]))\right)$ (14)

, where ${\rm rot}_{\alpha}[\cdot]$ and ${\rm transl}_{l}[\cdot]$ performs the
rotation by $\alpha$ and translation by $l$, respectively, and ${\rm
KL}(\cdot,\cdot)$ measures the KL divergence. $A$ is the list of angles which
we use $[90^{\circ},180^{\circ},270^{\circ}]$, $L$ is the list of translations
which we use $[(-l_{x},0),(-0.5l_{x},0),(0.5l_{x},0),(l_{x},0)]$ for
translations along $x$ axis and
$[(0,-l_{y}),(0,-0.5l_{y}),(0,0.5l_{y}),(0,l_{y})]$ for translations along $y$
axis (the normalized size of the map is $l_{x}$ by $l_{y}$, where
$l_{x}=l_{y}=1$ for the scenarios in SMAC. We calculate these four metrics by
averaging over state and observation collected in different time steps in $32$
episodes. The ranges of those metrics are not important. By construction, the
larger the values of
${\rm{Invariancy_{V}^{rot}}},{\rm{Invariancy_{V}^{transl}}},$ and
${\rm{Invariancy_{\nu}^{rot}}}$ are, the closer the behaviors the non-SEGNN-
based architecture are compared to those of the SEGNN-based architecture,
which has the largest possible values for those metrics, in terms of their
invariancy to the corresponding transformations.

###  E.4 The emergence of invariancy and equivariancy in SMAC.

Figure 11: The emergence of invariancy and equivariancy in non-SEGNN-based
critic and actor, respectively, in SMAC.

##  Appendix F Hyperparameters

###  F.1 MPE

Table 1: Hyperparameters for MPE

Hyperparameter | Value
---|---
Episode length | 25
Number of training episodes | 60000
Discount factor | 0.95
Batch size from replay buffer for [MLP, MLP] and [GCN, MLP] | 1024
Batch size from replay buffer for [SEGNN, MLP] and [SEGNN, SEGNN] | 128
Actor’s learning rate for [MLP, MLP] and [GCN, MLP] | 1e-4
Acror’s learning rate for [SEGNN, MLP] in ordered scenarios | 3e-4,3e-4,1e-4,3e-4,3e-4,3e-4
Acror’s learning rate for [SEGNN, SEGNN] in ordered scenarios | 1e-4,3e-4,3e-5,3e-5,3e-4,3e-4
Critic’s learning rate for [MLP, MLP] and [GCN, MLP] | 1e-3
Critic’s learning rate for [SEGNN, MLP] in ordered scenarios | 1e-3,3e-4,1e-3,1e-3,1e-3,1e-3
Critic’s learning rate for [SEGNN, SEGNN] in ordered scenarios | 1e-3,1e-3,1e-3,1e-3,1e-3,1e-3
Actor’s and critic’s learning rates for transfer learning in Navigation | 2e-4,1e-3
Actor’s and critic’s learning rates for transfer learning in Push | 3e-5,1e-3
Actor’s and critic’s learning rates for transfer learning in Prey | 3e-4,1e-3
Hidden size | 128
Graph used by SEGNN for 6h_vs_8z | complete graph
#episodes per evaluation | 200
seeds | 1,2,3,4,5

The ordered scenarios are: Navigation_N3, Navigation_N6, Push_N3, Push_N6,
Tag_N3, Tag_N6.
Unless specified, the mentioned hyperparameter is applied to all scenarios in
MPE.
Actors’ learning rates are searched in [1e-4, 3e-5, 1e-5].
Critics’ learning rates are searched in [1e-3, 3e-4, 1e-4].

###  F.2 SMAC

Table 2: Hyperparameters for SMAC

Hyperparameter | Value
---|---
Episode length | 400
Number of training episodes | 2e7
Discount factor | 0.99
#Rollout threads | 8
#Training threads | 1
PPO epoch for 8m_vs_9m, 6h_vs_8z | 5,10
# mini-batch for 8m_vs_9m, 6h_vs_8z | 1,4
The degree of nearest neighbor graph used by SEGNN for 8m_vs_9m | 4
The degree of nearest neighbor graph used by SEGNN for 6h_vs_8z | 13 (complete graph)
Acror’s learning rate for all algorithms | 5e-4
Critic’s learning rate for all algorithms | 5e-4
Hidden size | 64
#episodes per evaluation | 32
seeds | 1,2,3,4,5

Unless specified, the mentioned hyperparameter is applied to both 6h_vs_8z and
8m_vs_9m.
Actors’ and critics’ learning rates are the default ones used by original
MAPPO [23]

##  Appendix G Computing resources

The code is implemented by PyTorch, and runs on NVIDIA Tesla V100 GPUs with 32
CPU cores. For MPE, a single run with [MLP, MLP], [GCN, MLP], [SEGNN, MLP],
[SEGNN, SEGNN] takes approximately 2 hours, 3 hours, 7 hours, 10 hours to run,
respectively. For SMAC, [MLP, MLP] and [SEGNN, MLP] takes approximately 8
hours and 4 days to run, respectively. Each algorithm is run with 5 seeds.