Boosting Sample Efficiency and Generalization in Multi-agent Reinforcement Learning via Equivariance

Thank you for your response and praise in strengths! We added some additional plots in the global response. Let us know if you have any questions regarding those additional results.

Thank you for your response. We have updated our charts, and discuss the novelty further below. We hope you will consider increasing the score given the updates and content.

1. See the common rebuttal for an additional baseline. [3] is not a MARL algorithm. we attempted to replicate [2], but failed to see any improvement over standard PPO. [1] is only relevant to discrete action spaces and discrete observation spaces. However, we will add citations to [1,3] (we already cite [2]) in the related works section: with the following statement)

2. Entropy baselines, while potentially helpful are not the standard for MARL (see questions below), and our goal was to compare with standard MARL approaches. Additionally, our contribution was not limited to addressing the exploration bias of EGNN, it was also our contribution to apply EGNN to complex MARL environments leading to improved sample efficiency and generalization.

3. We believe many tasks will have some form of symmetry, but that symmetry may be inexact, or only partially symmetric. Our approach here cannot currently address those types of problems. However, we are excited to attempt to pursue this in future works.

4. This seems to be the first work applying EGNN to MARL, and the first work to successfully apply any equivariant neural networks to the common MARL SMACv2 benchmark. See questions section for discussion of trajectory prediction

5. These are common benchmarks in MARL. We did not design any new features, we used the standard outputs of these environments.

6. see lines 265-266

7. See below in questions. for discussion about the gaussian. The goal is not necessarily to only enhance exploration. The goal was to apply Equivariant Neural networks to MARL problems. In the process of using EGNN we noticed that it’s bias was causing a problem in exploration. Thus we had to modify EGNN to improve it’s performance in MARL.

8. We believe this approach to be fairly reproducible. We knew we may not get permission to release our code. To that end, we specifically used open source libraries for everything we did. The RL code is the open source library RLLIB. We used the code from the EGNN paper for the neural networks. The environments are also open source, as are the features of the environments.

9. We applied EGNN in 2 dimensions, because our problems (standard benchmarks in MARL literature) were in 2 dimensions. It could certainly be applied to more depending on the problem.

Questions

1. MARL and trajectory prediction are related but fairly different. MARL is attempting to control a set of agents to achieve some objective. This entails learning a value function to approximate the value of each state in achieving that overall objective and a policy to control the agents to achieve that objective. Trajectory prediction is focused on predicting the next step of dynamics. Trajectory prediction is relevant to model-based RL algorithms. but in this case we are focused on model free algorithms

2. We used the gaussian output for the policy, because that is common practice in the field. Common RL code libraries such as stable baselines https://stable-baselines.readthedocs.io/en/master/, RLLIB all use gaussian parameterized policies. See also: ”...outputting the mean of a Gaussian distribution, with variable standard deviations, following [Sch+15b; Dua+16]” from original PPO paper ”The two most common kinds of stochastic policies in deep RL are categorical policies and diagonal Gaussian policies.” https://spinningup.openai.com/en/latest/spinningup/rl intr We wanted our approach to be as broadly applicable as possible so wef ocused on common practices.

3. see lines 265-266

4. I think that is an interesting idea, and one worth exploring in future efforts.

Thanks for responding!

1. Note that our paper was written contemporary to [20]. We had much of our results before they published. However, we did add an empirical comparison with [20] and note that our approach E2GN2 (see the pdf in the common rebuttal) greatly outperforms E3AC [20] on all of the SMAC benchmarks. On terran and protoss in particular, we more than double their final win rate (~0.6 vs ~0.3), and have much faster learning: ie E2GN2 learns a win rate of 0.3 in near 1e6 time steps, while E3AC [20] takes 1e7 time steps to learn that win rate. On MPE [20] is much slower, taking 4 hours to train. We believe our improvements are significant (due to using EGNN, E2GN2 and section 4.3) and should be shared with the community.

Much of the analysis in [20] is only a small extension from prior analysis in Van der pol's work. Van der pol established the theory for adding equivariance to multi-agent MDPs (albiet very simple grid world environments), the work in 20 did not add too much to this in terms of theory. Since van der pol had established this theory we chose not to focus on it as it would not be novel. Instead we focused on more practical applications and improvements.

Regarding SEGNN, it is not necessarily an improvement over EGNN as it is very slow. We initially decided to use EGNN specifically because SEGNN and related networks (ie those using spherical harmonics, wigner-D matrices, etc) tend to be slow. Looking at the original SEGNN paper it is 10x slower than EGNN. MARL experiments are already too slow, so we did not want to exacerbate this problem. In our global response we did observe that this results in much slower training times for the results from [20]

Note that [20] was not able to get competitive results on SMAC. We were able to greatly improve learning on SMAC due to our approach described in section 4.3. Additionally, this solution in section 4.3 is not to only change the movement actions to be continuous, it is to decompose the discrete action outputs such that each node for each enemy is outputting one component of that action. This is crucial for retaining the GNN locality structure and allowing us to scale agents without retraining.

2. It is true that E2GN2 loses translation equivariance guarantees. However it retains translation invariance guarantes* see below. For MARL policies translation invariance is useful [see 20] but translation equivariance is harmful. We certainly observed that in practice translation equivariance was harmful (for one our results demonstrate E2GN2 out performs EGNN). As a simple example. if you have an agent at the position (0,-1) Perhaps the optimal action for agent 1 is to move up: (0,1). Now shift this down by 100, so now this agent's position is at (0,-100). A translation equivariant network will shift the action by -100, leading to the action of (0,-99). This means the agent will always move down, which is not optimal! This is not desirable for many MARL environments. When testing in MPE and SMAC, this may not cause a large problem, as the inputs are often normalized to be near (-1 ,1), but it can still potentially affect performance.

• we can add a full proof to the appendix, on E2GN2 being translation invariant (just not equivariant), but briefly, we did not modify the equation for computing $h_i$ and are still using the output of $h_i$ for the invariant components.

If we translate the input by $b$, that will translate the output by $\phi_u(m_{ij}) b$ ie $u_i^l + \phi_u(m_{ij}) b = u_i^{l-1} + b$ then the output of $h_i^{l+1}$ is translation invariant if $|| u_i -u_j ||$ is translation invariant, and $|| u_i + \phi_u(m_{ij}) b - (u_j^{l} + \phi_u(m_{ij}) b ) ||$ = $|| u_i -u_j ||$ so we retain translation invariance.

3. For the citation concerns, we have mentioned we will add the citations you mentioned here (as well as others, some reviewers mentioned). We will add the content from these reviews going more in-depth on the differences between our on [19,20,21] (similar to the global rebuttal). We are not certain we understand the rest of this comment. We were not seeking to change the exploration structure of the MARL learning problem. We were seeking to ameliorate a problem we noted in the EGNN structure (that of bias). We presented an in depth analysis of this bias and compared the EGNN vs E2GN2 across a variety of benchmarks (figure 3,5,6) demonstrating that the exploration bias of EGNN caused worse performance.

There are indeed many methods to attempt to improve a RL algorithm's exploration performance (such as the many papers on curiosity driven exploration). However, our focus was on modifying EGNN to improve common practices in MARL environments/bechmarks (stable baselines, rllib, etc). To that end, we focused on using the common gaussian parameterization of the policy (see our previous comment, Q2 for those citations). EGNN's biased will likely harm any biased exploration.

3 continued) Note also that the paper in question [1a] regarding entropy-based exploration does not outperform the benchmarks on dense-rewards, it only outperforms the benchmarks on sparse-reward environments. All of our environments (the standard benchmarks in MARL) have dense rewards, which seems to see little to no improvement from their approach. Furthermore, they do not show how to apply it to actor-critic algorithms such as PPO (what we use here and is one of the best/fastest commonly used algorithms for MARL [2a, rllib])

Entropy-based exploration seems rather niche and has not become a mainstay or mainstream, especially not in MARL. Most of the state of the art papers and libraries use gaussian parameterized policies [2a, rllib, stablebaselines, etc].

1a Cooperative Exploration for Multi-Agent Deep Reinforcement Learning 2a The surprising effectiveness of multi-agent PPO

(continuing discussion on point 1 under weaknesses)

To further clarify, the issue with the discrete action space was not necessarily maintaining exact continuous equivariance (we will clarify this in 4.3). The problem is that the SMACv2 action space has an equivariant component (movements) and an invariant component (shoot). The outputs for the equivariant component of EGNN/E2GN2 are continuous values, mapping these values to logits is not straightforward. Furthermore, they would need to be mapped onto the same distribution of logits being represented by the shoot commands. We solve this problem by having three distributions output by the GNN structure: the continuous/equivariant movement gaussian distribution, the discrete/invariant distribution, and a third distribution that determines whether we should move or shoot (described 290-292). After the RL sampling from each distribution is performed for the actions, then the three components of the action can be converted to the final action for either a mixed discrete-continuous action space or a discrete action space.

Thank you for your thorough, in depth response! Our replies are below:

Weaknesses

1. Note that we added a new comparison with [20] demonstrating ours outperformed the results from [20]. Regarding SEGNN, we initially decided to use EGNN specifically because SEGNN and related networks (ie those using spherical harmonics, wigner-D matrices, etc) tend to be slow. Looking at the original SEGNN paper it is 10x slower than EGNN. MARL experiments are already too slow, so we did not want to exacerbate this problem. However, we did add a global response, addressing adding SEGNN from [20] to our comparisons.

Regarding the action space, please see the global rebuttal response. We showed this method is still relevant to SMAC when using discrete actions. Note that E2GN2 and EGNN outperform the baselines in with the discrete action space as well. Our method in 4.3 was crucial for achieving this result.

Note that [20] was not able to get competitive results on SMAC. Additionally, this solution in section 4.3 is not to only change the movement actions to be continuous, it is to decompose the discrete action outputs such that each node for each enemy is outputting one component of that action. This is crucial for retaining the GNN locality structure and allowing us to scale agents without retraining.

2. I agree it would be interesting to explore the use case in other domains.. However, our focus in this paper is improving MARL, so perhaps we can explore this in the future.

3. Okay. We will update our paper accordingly

4. The results from [20] demonstrate that translation invariance is important. Our observation is wrt translation equivaraince We certainly observed that in practice translation equivariance was harmful. As a simple example. if you have an agent at the position (0,-1) Perhaps the optimal action for agent 1 is to move up: (0,1). Now shift this down by 100, so now this agent's position is at (0,-100). A translation equivariant network will shift the action by -100, leading to the action of (0,-99). This is not desirable for many MARL environments. When testing in MPE and SMAC, this may not cause a large problem, as the inputs are often normalized to be near (-1,1).

Questions

1. Thank you for catching this. The orange circle should say "All learnable functions constrained by data".

2. This is an interesting question to explore in the future.

3. On the theoretical results 3b I see how that is confusing. We will update to use just $i$ instead of $k$ 3c The definition of $s_k^{eq}$ is the component of the action space that is equivariant, we will formalize this definition. 3d Yes, that is an assumption that originates with EGNN.

4. How a policy is represented:

   4a) The input graph is described in appendix B (we will change the word choice from "connections" to "edges"). For MPE we use a complete graph. For SMACv2 we use a graph such that it is complete between all friendly nodes. Each friendly node has an edge to each of the enemy nodes. There are no edges between enemy nodes. This was an attempt to model what we imagine a real world type world to look like (you see the enemies, communicate with your allies, but don't see the enemies communications).

   4b) This is partially in appendix B (we reference the width of the MLPs as 32), we can improve the wording by referencing the specific notation, and add details for each environment. For the intermediate GNN layers $u^i_l$ has a dimensionality of 32. For MPE the input $u^0_i$ is the id (pursuer, evader, or landmark). For SMACv2 $u^0_i$ is made up of the features: health, shield unit type, and team.

   4c) This is described in section 4.3 and is key to our approach. For smacv2, the discrete logits for attack targets are the outputs of each node corresponding to the attack target. The logit for attacking agent j is the output for $h_j^L$. Since the output of each individual node $h_j^L$ is invariant, these will then remain invariant. These logits are concatenated from each of the nodes to compose the final action. This allows us to scale to larger numbers of agents without retraining.

5. We did not spend much discussion on the value function approximation, as it has been discussed in prior works [19,21]. The value function is fairly straightforward, we simply used an EGNN/E2GN2 for the value function. The ouput of the own node's invariant component was the value function output ie $u_i^L$ for agent $i$. We will add this to appendix B

6. On the experiments

   6a) We will add this to the appendix. We used the same GNN as the EGNN paper: Specifically, we use equations 1 and 3, but update equation 1 to be $m_{ij} = \phi(h_i, h_j, x_i,x_j)$.

   6b) A standard GNN layer is permutation equivariant [24]. It also has a local structure that enables adding/removing nodes without needing to retrain the layers. For example, [1a] demonstrates using a GNN to train N agents, then to control $N+n$ agents without retraining. However, this example did not operate with discrete or mixed action spaces as we do with SMAC.

   Our formulation in 4.3 enables us to retain the permutation equivariance of a GNN. An alternative to our approach is to add an MLP at the end of the GNN to convert the GNN outputs to the mixed action spaces. This will lose the scalability/locality of the neural network. For example, if you add two more enemies how do you modify the final MLP to expand the action space? In our formulation, whenever an new enemy $i$ is added to the environment, we can simply add the node $N+1$ to the graph. The action space of the GNN will now be supplemented with $u_{N+1}^L$ allowing us to expand the action space without retraining.

New Citations: [1a] Learning Transferable Cooperative Behavior in Multi-Agent Teamhttps://arxiv.org/abs/1906.01202 (GNN)

Thanks for the reminder. Here are the responses to those points.

3a. See lines 457 and 469 (I tried copying it here, but the latex kept breaking)

6b That is a good point to bring up. For clarity, the difference between MAPPO and PPO is that MAPPO uses a centralized critic that takes in the observations and actions of all agents. We believe E2GN2 would improve MAPPO, and we hope to eventually apply this to MAPPO. We use independent PPO because 1) MAPPO performance can vary depending design of the centralized critic [see figure 4 in 1a]. 2) For many cases IPPO is comparable to MAPPO [1a] Since we used parameter sharing [2a], all of our agents were using the same critic. Since we had fully observable environments, the critic had all observations as an input. So using IPPO with parameter sharing and full observability is a fairly close approximation. 3) We wanted to use existing commonly used public libraries to increase reproducibility and utility to the community. We selected RLLIB since it seemed to be a popular benchmark, RLLIB does not have MAPPO built-in, it must be added on your own and implementations can vary (reducing reproducibility)

One more clarification on point 4 of the weaknesses section. E2GN2 is still translation invariant (just not equivariant). We can add a full proof to the appendix, but briefly, we did not modify the equation for computing $h_i$ and are still using the output of $h_i$ for the invariant components.

If we translate the input by $b$, that will translate the output by $\phi_u(m_{ij}) b$ ie $u_i^l + \phi_u(m_{ij}) b = u_i^{l-1} + b$ then the output of $h_i^{l+1}$ is translation invariant if $|| u_i -u_j ||$ is translation invariant, and $|| u_i + \phi_u(m_{ij}) b - (u_j^{l} + \phi_u(m_{ij}) b ) ||$ = $|| u_i -u_j ||$ so we retain translation invariance.

1a https://arxiv.org/abs/2103.01955 2a https://arxiv.org/abs/2005.13625

For E3AC, we used the model and observation processor from the E3AC github repo, so no, E3AC was not using the three-distribution technique we introduced here (since that was part of the novelty of our work). They did not have an observation processor for SMAC in their git repo. We wrote the SMAC observation processor by modifying their MPE observation processor according to the details in their appendix. Note that since E3AC was unable to resolve the difficulty with the SMAC action space (using SEGNN), they opted to use an MLP for the policy and an SEGNN for the value function.

The third distribution is invariant, the logits are output from $h_i^L$ for agent $i$ (ie the invariant part of the output node corresponding to that agent)

https://github.com/dchen48/E3AC

Thank you for the response and for upgrading the score! We appreciate you taking the time to carefully consider this work.

To clarify are the significant concerns the two listed in your comment? (i and ii?)

For i: Our greatest rationale for using EGNN (over SEGNN or other architectures) is the speed in computation (see the charts in the main rebuttal pdf) it takes 40 minutes to train vs SEGNN taking 4 hours for E2GN2 to train. This makes a big difference for MARL practitioners. This is why we stick with EGNN and then need to fix the exploration bias. We also note that while SEGNN outperformed EGNN in the original SEGNN paper, here we see that for MPE simple tag EGNN seems to outperform SEGNN.

For ii: while this novelty may be fairly straightforward, we have demonstrated it was critical for MARL in scalability and performance on the much more complex SMAC environment (and opening the door for other MARL envs with discrete or mixed action spaces and both equivariant and invariant components). There are many novelties (such as the resnet paper with their skip connections) that were simple in concept, but very important for improving performance, as we see in this paper

iii: We believe a third novelty of this paper was applying EGNN to MARL. This did not exist in the literature prior, and EGNN is more feasible than SEGNN (or related formulations) for usage in MARL due to the quicker training time (in hours). This may be the key to broader usage of equivariant networks by the MARL community.

One quick note (re novelty) we had much of our results before [20] was published, and did not find it until much of our paper was written.

Thank you for your thorough review. We appreciate the time you took to dive into the details of our work and provide specific advice for improving these results.

We tried to take your feedback into account in our updated results. We increased the number of seeds up to 10, and we added a new baseline (see the global rebuttal for those charts) from [20]. We will remove the language regarding "up to 10x improvement in sample efficiency" and replace it with simply "in many cases we see a significant improvement in sample efficiency over GNN and MLP networks". Perhaps that is worded better?

Clarity Thank you for this feedback. We will make the recommended changes to the mathematical depiction, improve the definitions for equations 1,2,3 and add the theorem 2 pointer to a proof.

Experiments:

• On further baselines: We addressed the concerns regarding the baselines [19, 20,21] in the global rebuttal. We added the baseline [20] to our comparisons, and discussed further [19,21]. Let us know if you have any other thoughts on these. Before the original submission we did attempt to use [21] as a baseline, but when we tried to implement their approach we did not see any improvement over the standard PPO approach for MPE. (we tried various hyperparameters, and learning rates as well). The experiments in [19] are similar to a grid-world type environment. The input to the traffic control is a 8x8 grid and the cars move one grid per timestep. Their wildlife monitoring environment is a 7x7 grid where the agents move around the grid. Extending their specific approach from a gridworld (discrete number of states) to SMACv2 would likely require further innovations.

• On the shaded regions in the experiments: in the submitted paper these regions are the 95% confidence error calculations computed by bootstrapping using python's seaborn. Per your comment on standard errors, the updated plots (see global rebuttal) use standard error instead.

• On the number of seeds, we now have 10 seeds for each run. We note that due to the higher run time of MARL experiments, other MARL papers use around 10 seeds [1a,2a]

Q1: On why SMACv2 is more complex: the units are heterogenous with different capabilities (with different attack ranges, total health, and sometimes action spaces). The unit types are randomized at the beginning of the scenario. The actions include more components than simply movement (such as in MPE), agents can move and attack. The goals are more complex as well. Instead of simply navigating cooperatively as in MPE, the agents must learn attack formations and strategies. Sometimes it may be optimal to sacrifice health or allies in the purpose of the greater strategic objective. (see lines 278-286)

Q2: Van der Pol's approach is to find the basis for a specific group (ie rotations). Once the find the basis they make the neural network weights a linear combination of the basis vectors. I don't believe their network would have a bias, but it has the limitation of being applied only to discrete grid-world like environments (see global rebuttal for a further discussion on this).

Q3: In the experiments on SMACv2 (using mixed discrete-continuous actions) EGNN does indeed adapt the suggested solution in 4.3, as does the GNN network. In fact, using the method described in section 4.3 is why GNN was able to increase the number of agents without retraining (Table 2)

Limitations We plan to add a further discussion on limitaitons. It is true that the more symmetry in the environment the greater the improvement we would see from EGNN/E2GN2. I will note these environments weren't necessarily hand-picked. MPE and SMAC are the standard/go to environments for MARL. For example, [1a] uses SMAC and MPE and it has 1000 citations. The SMACv2 paper identified problems with the original SMAC environment, which is why we use SMACv2. That said, E2GN2/EGNN could be overly restrictive in environments where symmetries are inexact or unclear. If EGNN is assuming an exact symmetry, but that symmetry is inexact, this could cause a loss in performance as the inductive bias is keeping the network from learning the optimal solution.

Other citations

1a https://arxiv.org/abs/2103.01955 2a https://arxiv.org/abs/1706.05296

As the discussion period is coming to a close we would like to thank you for your time in the original review. To recap, we have added further discussion on the related works, added more seeds to our experiments, and added a related baseline [20] which our approach continues to outperform. We are eager to hear if our additions have addressed your concerns, and if there is anything else to add to this discussion.

Although we added more seeds to the training charts, we had not yet updated the tables with more seeds (and standard errors). Here we present these:

Table 1 (with 10 training seeds)

Table 1 (with 10 training seeds)

Furthermore, one question raised was whether the tips and tricks from [1a] would improve the performance of our approach. First, we clarify that we largely used the majority of their tips and tricks, especially relevant to performance (3 of 5 of their tricks were using a large training batch size, few numbers SGD of iterations, and small clip size. We used all of these). Due to space in the rebuttal, we couldn't include this explicitly, but if you look at figure 1 from the rebuttal pdf and compare that to figure 5 from the paper, you may notice a difference between the performance of E2GN2 and EGNN. In Figure 1 of the rebuttal, all of the approaches used value normalization from [1a], in the paper that is not necessarily true. In fact, value normalizaiton was critical for E3AC learning at all. Thus we do observe that adding value normalization does indeed improve the results for MPE tag. We did not see an improvement with any other environment (and [1a] didn't see an improvement for other environments either).

Finally, in our blurb on limitations below we discussed how equivariance may be impartial or incomplete in the real world. We also want to add that our approach would need improvements to be applied to environments with angular momentum and mechanics, which are not included in these benchmarks (though to reiterate, these are the standard MARL benchmarks). Note that the total improvement from these approaches will likely depend on the amount of rotational symmetry applicable in the observations. Additionally, this approach is not directly compatible with environments using vision-based observations.

We note the reviewer initially wrote they would raise the score if we adjusted the language, addressed limitations, and added more seeds. The reviewer also mentioned raising the score more if we added a new baseline to strengthen the claims and the generalizability to stronger approaches is demonstrated. We hope we addressed your concerns sufficiently, let us know what other concerns you may have.

1a the surprising effectiveness of Multi-agent PPO

Thank you for your review and comments.

1. There is no MLP on the output of the GNN, EGNN, or E2GN2. Adding an MLP to the output would cause us to lose the guarantee of equivariance as well as the ability to add more agents without retraining.

The output is similar to what is shown in the diagram. It is composed of outputs from various nodes. The outputs all come from the $L$th layer of the network. For agent $i$, the movement component of the action will output from the own node's equivariant component $u_i^L$. For SMAC, the invariant component of the action (ie the logits for determining which target to attack) will be output from the invariant component of that target's node: $h_j^L$ where $j$ is the potential target/enemy. (see lines 232-239 and 290-293). I hope that helps clarify things.

(we will add this to Appendix B), we use a separate networks for the policy and value function. The value function output is comes from the invariant component of the agent's node of final layer of the EGNN/E2GN2. In other words the value function is: $h_i^L$ Where $L$ is the final layer, $i$ and is the agent in making the decision.

2. That is a good point to bring up. We believe E2GN2 would improve MAPPO, and we hope to eventually apply this to MAPPO. We use independent PPO because 1) MAPPO can be more difficult for one to one comparisons [1], as it depends on how the centralized critic is shaped. 2) for many cases IPPO is comparable to MAPPO [1] 3) we wanted to use common public libraries for more reliable open source comparisons. we selected RLLIB since it seemed to be a popular benchmark, RLLIB does not have MAPPO built in, it must be added on your own, and implementations can vary.

3. This is an input variable to SMACv2. A user can change the variable 'partially_observable' to False to make it fully observable. Note that we did also do a preliminary comparison with partially observable observations (per SMACv2 standard) and saw surprisingly good performance (see appendix)

Citation

1. The surprising effectiveness of multi-agent PPO