{'fraction_non_alphanumeric': 0.037765799133569235, 'fraction_numerical': 0.012070504977016436, 'mean_word_length': 4.629188384214445, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
REVISITING PARAMETER SHARING IN MULTI-AGENT DEEP REINFORCEMENT LEARNING

“Nonstationarity” is a fundamental problem in cooperative multi-agent reinforcement learning (MARL). It results from every agent’s policy changing during learning, while being part of the environment from the perspective of other agents. This causes information to inherently oscillate between agents during learning, greatly slowing convergence. We use the MAILP model of information transfer during multi-agent learning to show that increasing centralization during learning arbitrarily mitigates the slowing of convergence due to nonstationarity. The most centralized case of learning is parameter sharing, an uncommonly used MARL method, specific to environments with homogeneous agents. It bootstraps singleagent reinforcement learning (RL) methods and learns an identical policy for each agent. We experimentally replicate our theoretical result of increased learning centralization leading to better performance. We further apply parameter sharing to 8 more modern single-agent deep RL methods for the first time, achieving up to 44 times more average reward in 16% as many episodes compared to previous parameter sharing experiments. We finally give a formal proof of a set of methods that allow parameter sharing to serve in environments with heterogeneous agents.


INTRODUCTION
Multi-agent reinforcement learning methods in cooperative environments seek to learn a policy (a function that takes observations and returns actions) that achieves the maximum expected total reward for all agents. As is common in MARL, the present work focuses on "decentalized" policies, where each agent has their own policy and can act without a central controller (Bu et al., 2008).
A nonstationary environment is one that changes during learning (Choi et al., 2000;Chades et al., 2012). While this can be beneficial when done intentionally (e.g., curriculum learning), it typically makes learning far more difficult as the policy's knowledge of the environment will become wrong over time (Bengio et al., 2009;Choi et al., 2000;Chades et al., 2012). Virtually all cooperative multiagent reinforcement learning suffers from very slow convergence due to nonstationarity (Matignon et al., 2012;Hernandez-Leal et al., 2017;Papoudakis et al., 2019). Consider an environment with two agents, "Alice" and "Bob", who must learn to work together. Alice's policy must have knowledge of Bob's policy, which from her perspective is a part of the environment (and vice versa for Bob's policy). At each step of learning, Alice learns about Bob's policy and the rest of the environment. Bob also then learns about the environment and Alice's policy, updating his policy. Alice's knowledge of Bob's policy is now slightly wrong, so Alice must now learn Bob's new policy and update her own, making Bob's knowledge of hers slightly wrong. This "ringing" of information can greatly slow convergence during learning, especially for highly coordinated tasks with many agents, and this specific form of nonstationarity is believed to be a fundamental reason why converging to good policies in multi-agent learning is so difficult Papoudakis et al. (2019).
The naive way for Alice and Bob to learn would be to concurrently learn separate policies for each with a single-agent RL method. As the above example illustrates, this is ineffective and experimentally is usually only able to learn toy environments (Matignon et al., 2012). This has motivated work on specialized multi-agent deep reinforcement learning (MADRL) methods, notably QMIX (Rashid et al., 2018), COMA (Foerster et al., 2018) and MADDPG (Lowe et al., 2017). These employ "centralization" techniques that allow Alice to learn about Bob's policy faster than just watching him in the environment (Papoudakis et al., 2019). Intuitively, this reduces the "ringing" delay, thus mitigating the nonstationarity.
MADDPG has a single shared critic network during learning, which acts on separate actor networks for each agent. Parameter sharing in MARL takes this to the extreme: learning a single shared policy simultaneously for multiple agents. This is clearly the most centralized case of learning, as there is only a single policy and no communication between policies. Note that centralization is used to refer to a handful of similar-but-distinct concepts in the MARL literature; here it refers to information transfer rates between policies during learning (formalized in subsection 2.3).
Parameter sharing, on the other hand, "bootstraps" single-agent RL methods to learn policies in cooperative environments, and was concurrently introduced by Gupta et al. (2017) for DDPG, DQN and TRPO and by Chu and Ye (2017) for a special case of DDPG. Their experimental results were not as remarkable as methods like MADDPG, and other similar methods have seen far more widespread adoption (Baker et al., 2019). However, DDPG, DQN, and TRPO were some of the first DRL methods; many newer ones exist which often have dramatically better performance and prior to our work have not been tested with parameter sharing.
On the surface, it seems like having one policy for every agent means that all agents must be identical (or "homogeneous"), and this was initially assumed to be the case (Gupta et al., 2017;Chu and Ye, 2017). However, by including the agent (or agent type) as part of the observation, a single policy can respond differently for each agent. This "agent indication" technique was first used by Gupta et al. (2017). Even with this, observation spaces of all agents must be the same size since there is a single neural network; however this can be resolved by "padding" the observations of agents to a uniform size. We can similarly "pad" action spaces to a uniform size, and agents can ignore the actions outside their "true" action space.

MAIN CONTRIBUTIONS
In section 3, we use the MAILP model to mathematically formalize the above intuition that more centralization during learning mitigates nonstationarity in MARL and allows for faster convergence. Parameter sharing is the most centralized MARL method possible, so this theory also provides an explanation for experimental performance variations in MADRL methods: that "full" parameter sharing does better than fully independent single-agent learning (the most decentralized case). Furthermore, we prove a lower bound showing that cases of highly decentralized learning methods take a fantastically long time to converge due to nonstationarity.
In section 4, we empirically replicate the predictions of our theorems by applying both parameter sharing and fully independent learning applied to 11 single-agent DRL methods on the Gupta et al.
(2017) benchmark environments, finding that parameter sharing consistently performs the best. Eight of the single-agent RL methods we apply parameter sharing to are more modern than those previously tested with parameter sharing. With these, we achieved the best documented performance on every environment from Gupta et al. (2017), achieving up to 44x more average reward in as little as 16% as many episodes compared to previously documented parameter sharing arrangements; we also outperform MADDPG and QMIX on all three environments. The policies learned by parameter sharing also orchestrate basic emergent behavior.
In section 5, we introduce the aforementioned "observation padding" and "action space padding" methods to allow parameter sharing to learn in environments with heterogeneous agents. We also offer proofs that these and agent indication allow parameter sharing to learn optimal policies. Based on a preprint version of this work, these methods have been successfully experimentally used in Terry et al. (2020b) and built into the SuperSuit set of multi-agent wrappers so that anyone can easily use them (Terry et al., 2020a).

BACKGROUND
2.1 REINFORCEMENT LEARNING Reinforcement learning (RL) methods seek to learn a policy (a function which takes the observation and returns an action) that achieves the maximum expected total reward for an environment. Singleagent environments are traditionally modeled as a Markov Decision Process ("MDP") or a partiallyobservable MDP ("POMDP") (Boutilier, 1996). An MDP models decision making as a process where an agent repeatedly takes a single action, receives a reward, and transitions to a new state (receiving complete knowledge of the state). A POMDP extends this to include environments where the agent may not be able to observe the entire state.

MULTI-AGENT REINFORCEMENT LEARNING
In multi-agent environments, Multi-agent MDPs ("MMDPs") (Boutilier, 1996) extend MDPs by allowing for a set of actions to accommodate multiple agents. However, MMDPs assume all agents receive the same reward. Stochastic Games (sometimes called Markov Games), introduced by Shapley (1953), extends this by allowing a unique reward function for each agent.
Partially-Observable Stochastic Games ("POSG") (Lowe et al., 2017), defined below, extend Stochastic Games to settings where the state is only partially observable (akin to a POMDP), and is the model we use throughout this paper. Definition 1 (Partially-Observable Stochastic Game). A Partially-Observable Stochastic Game (POSG) is a tuple S, N, • S is the set of possible states.
• N is the number of agents. The set of agents is [N ].
• A i is the set of possible actions for agent i.
• Ω i is the set of possible observations for agent i.

PARAMETER SHARING
The notion of parameter sharing exists is common throughout deep learning. In multi-agent reinforcement learning, it refers to a learning algorithm acting on behalf of every agent, while using and making updates to a collective shared policy (Gupta et al., 2017).

MULTI-AGENT INFORMATIONAL LEARNING PROCESSES
Introduced by Terry and Grammel (2020), the Multi-Agent Informational Learning Process (MAILP) model very generally describes the propagation of information through multi-agent systems during learning. In the model, each agent i ∈ [N ] has information I i ∈ [0, 1]. With an optimal policy, a certain fraction of its information must depend on the environment, while the rest of the information may depend on different agents or groups of agents, with the total amount of information summing to 1. The fraction of i's information that relates to a group of agents G ⊆ [N ] \ {i} is referred to as the coordination coefficient, and is denoted by C i,G ; C i,env denotes the fraction of i's information that relates to the environment. After each step of learning, the agent's information increases by: where χ ∈ 2 [N ]\{i} ∪ {env} represents either the environment (env) or a group of agents G ⊆ [N ] \ {i}; Λ is the learning function with the property that Λ(x) ≤ x for all x ∈ [0, 1]; and K i,χ is the centralization coefficient, which simply scales how fast information can transfer between entities during learning. Given arbitrary Λ, C, K, this can capture any learning process as long as the rate at which agents gain information stays the same or decreases as the agents gains more information.
The coordination and centralization coefficients between each combination of agents are collected into respective "tensor sets", which are properties of the environment, indexed as above. After each step, agents also lose some information about the other agents, which depends on how much they need to know about the other agent (the coordination coefficient) and how much the other agent learned, described in (1). This is nonstationarity: as the other agent learns new things, a portion of knowledge an agent has about them will inherently be wrong.
Summing (1) and (2) thus gives the total change in information for each agent after every step: Learning is said to be complete when I i (t) ≥ 1 − for all agents i ∈ [N ], where > 0 is some small constant. I 0 := I(0) is also used to denote the initial information that the agent has. We will often denote by I −1 (x) the earliest time step t in which I(t) ≥ x, so that we may write I −1 (1 − ) to indicate the number of time steps needed to finish learning.

LEARNING CENTRALIZATION AND NONSTATIONARITY
Based on the intuition about nonstationarity outlined in section 1, we use the MAILP model to prove MARL converges slowly under normal circumstances due to nonstationarity, and that centralization during learning arbitrarily improves this (with parameter sharing having the most centralization).
As a baseline, we first analyze the convergence of a single agent environment. Here C env = 1, and as there are no other agents we drop the subscripts for I. Our key result for the single-agent setting is Theorem 1, the proof of which is in Appendix A. Theorem 1. For single-agent learning with learning rate K env and initial information I 0 , we have In the multi-agent setting, we derive a bound for an environment where each of the N agents' knowledge depends on the behaviors of each of the other N − 1 agents in equal proportions. All agents pairs have the same coordination and centralization coefficients. This is typical of many real world environment requiring a high degree of coordination.
We use C to denote the coordination value for each pair of agents Further, as C i,env is the same for all agents i ∈ [N ], we will simply denote this as C env . C env is very small, so behavior predominantly depends on the actions of policies of other agents. K denotes the centralization coefficient between every pair of agents. Using these, the information update function for each agent looks like: To focus on nonstationarity and simplify the proof, we start with each agent having full knowledge of the environment (I i,env (0) = (1 − )C env ). Because C env is near 0, this is a reasonable simplification (and can only decrease the bound). Since all agents are identical, Thus, we denote the information an agent has about another agent at time t as I , (t). Finally, we let I 0 , := I , (0). Given all this, we state Theorem 2, proof in Appendix A.
This is a bound on the convergence rate of multi-agent learning. We illustrate this bound in Figure 1, which shows how low centralization rates increase convergence time. Compared to the single agent case (Theorem 1), we can see that nonstationarity can make multi-agent learning intractable. We can also see that for highly centralized learning, this problem becomes vanishingly small.
Since in parameter sharing, all agents share the same neural network, the agents always have the most up-to-date information about the behavior of all other agents. Thus, it achieves the theoretically best value K = 1. Theorem 3 (proof in Appendix A) describes the precise convergence rate when K = 1, which is not meaningfully worse than the single agent limit.

Number of Steps
Convergence Rates Over K Figure 1: The number of steps needed for convergence for different values of K , as given by Theorem 2. We use C env = 0.1, = .001, I 0 = 0.01, N = 3. This illustrates how larger values of K (which correspond to higher degrees of centralization) can dramatically improve convergence times, and how smaller values of K can dramatically lengthen them.
The lower bound on convergence for multiple agents is larger than in the single-agent case. We note also that it is a looser bound than the single agent case. One can see from the proof of Theorem 1 that if Λ(x) = x, then the bound is tight. This is not the case for Theorem 2, which is not tight even when Λ(x) = x. Because of this, we have a strict gap on the convergence rate for multiple agents compared to a single agent; that is, we have an upper bound on convergence for a single agent, and a lower bound for the convergence of multiple agents.

EXPERIMENTAL RESULTS
Parameter sharing has previously only been used experimentally with relatively simple DRL methods (plain DQN, plain DDPG, and TRPO) (Gupta et al., 2017;Chu and Ye, 2017). This raises the question of how parameter sharing performs when applied to more recent and advanced DRL methods. Accordingly, we tested parameter sharing with 11 DRL methods (8 for the first time in the literature) on the MARL benchmark environments from Gupta et al. (2017).
We use three MARL benchmark environments from Gupta et al. (2017), shown in Figure 2. In pursuit, 8 red pursuer agents must work together to surround and capture 30 randomly moving blue evader agents. The action space of each agent is discrete (four cardinal directions and "do nothing"). The observation space is a 7 × 7 box centered around an agent, depicted by the orange box. In waterworld, there are 5 purple agents, 5 green food targets and 10 red poison targets, and agents must learn to eat food and avoid colliding with poison or other agents. The action space of each agent is a 2-element vector indicating thrust in each direction, and the observation space is a 122-element vector of "antennae" outputs indicating the position of objects in the environment. In multiwalker, there is a package placed on top of 3 pairs of robot legs that must work together to move the package as far as possible to the right without dropping it. The action space of each agent is a 4-element vector of the torque to be applied to each leg joint, and the observation space of each agent is a 31-element vector of positions and velocities of elements of the walker with noise applied. More information about the environments is available in Appendix B. Figure 3 shows the massive performance impact of newer DRL methods for parameter sharing both in terms of convergence time and average reward, achieving up to a 44x performance improvement on pursuit. These policies achieved the highest documented average total reward for these benchmark environments, and orchestrate basic emergent behavior. This unrealized potential in parameter sharing may account for why it was not been popularly used before. We reproduced the results from Gupta et al. (2017) to account for any discrepancies caused by our tooling rather than the algorithms, shown in Figure 3, finding no major differences.
We then benchmarked the performance of all these single agent methods learning fully independently, the results of which are included in Figure 4. All methods performed worse than parameter sharing methods, reinforcing our theoretical results in section 3 on the importance of centralization in MARL. All learning was done with RLlib (Liang et al., 2017). All code, training log files, and the best trained policies for each method game combination are available at github.com/parametersharingmadrl/parametersharingmadrl. All hyperparameters are also included in Appendix D. We used the same MLP as Gupta et al. (2017), with a 400followed by a 300-node hidden layer. Note that we computed rewards as the sum of all agent's reward after every step. Additionally, in Appendix C we compare the results of our best performing policies to MADDPG and QMIX, achieving superior performance for all three environments.

PARAMETER SHARING FOR HETEROGENEOUS AGENTS
Given the apparent performance benefits of parameter sharing, it is desirable to be able to apply it to as many types of environments as possible. The two main limitations of parameter sharing are that it can only apply to cooperative environments (or cooperative sets of agents in an environment), and that it can only work for "homogenous" sets of agents (Gupta et al., 2017).   Figure 3, but with fully independent learning instead of parameter sharing. The maximum average total reward, as well as convergence times, are worse, as predicted by our theoretical work in section 3.
A group of agents is homogeneous if the policy of one can be traded with another without affecting outcomes. Formally, homogeneous agents are agents which have identical action spaces, observation spaces, and reward functions, and for which the transition function is symmetric with respect to permutations of the actions. If agents are not homogeneous, they're said to be heterogeneous. However, the challenge of heterogeneous groups of agents can be addressed, as per our intuition in section 1. The first challenge is that the policy must have an idea what agent (or kind of agent) it's seeing. This can be done by overlaying the agent on an image, appending the value to a vector observation, vel sim.
The following theorem, proven in Appendix A, states that an optimal policy can be learned when the observation spaces for agents are disjoint (and thus individual agents can clearly be distinguished).
which is optimal for all agents; i.e. ∀i ∈ [N ], ω ∈ Ω i , a ∈ A i , we have π * (ω, a) = π * i (ω, a), where π * i is an optimal individual policy for agent i. Now we formalize "agent indication" to prove that even in the case of non-disjoint observation spaces, a single shared policy can be learned by "tagging" observations with an indicator of the agent. Theorem 5. For every POSG, there is an equivalent POSG with disjoint observation spaces.
where Ω i and O i are derived from Ω i and O i respectively, as described below.
For each agent i, we define Ω i = Ω i × {i} = {(ω, i) | ω ∈ Ω i }. Intuitively, we "attach" information about the agent i to the observation. Now, for each agent s, ω). This is equivalent to G in the sense that there is a family of bijections The next issue is handling agents with differing heterogeneous observation sizes or action sizes. While this is not an issue theoretically (in terms of formulation of the POSG), it does pose important implementation issues. This can simply be resolved by "padding" the observations to to a uniform size. Similarly, if we have heterogeneous action spaces, we can utilize a method akin to an inverse of what we propose for homogenizing observation sizes. Assuming that all actions are converted into a common type, we can pad all the action spaces to the size of the largest, and discard actions outside of the "real" range in a reasonable manner. We formally define our methods for observation padding and prove that the methods allow for an optimal policy to be learned in Appendix A. Based on a preprint version of this work, all three methods are included as wrappers for multi-agent environments in SuperSuit (Terry et al., 2020a). Similarly based on a preprint, all three methods were successfully experimentally together and separately in (Terry et al., 2020b).

CONCLUSION, LIMITATIONS AND FUTURE WORK
We derived a lower bound in the MAILP model on the convergence of single agent learning, and a larger lower bound on the convergence of multi-agent learning. Moreover, when Λ(x) = x, we have an upper bound on the convergence for single agent learning, demonstrating a proper gap in the convergence times in this case. We expect this gap to be even larger when Λ(x) < x. Furthermore, as parameter sharing is the most centralized form of learning, we show it bypasses nonstationarity in multi-agent reinforcement learning.
We further showed parameter sharing to be able to achieve up to 44 times more total average reward in as few as 16% as many episodes by bootstrapping modern DRL methods in the benchmark environments from Gupta et al. (2017), achieving the best documented results on those environments. We did this by using parameter sharing with 8 more modern DRL methods for the first time. We also outperformed MADDPG and QMIX on all environments tested. This shows parameter sharing to hold far more potential than previously realized for MARL.
We additionally show parameter sharing to be compatible with all forms of agent heterogeity. In the case of functional heterogeity, we prove that "agent indication" from Gupta et al. (2017) allows parameter sharing to learn policies for heterogeneous agents. In the cases of heterogenous action or observation spaces, we introduce methods of "observation padding" and "action space padding," and prove they all allow parameter sharing to converge to optimal policies. Based on a preprint version of this work, these methods have been successfully experimentally and are included in a set of multi-agent wrappers so that anyone can easily use them.
Our work is limited in that, due to the computational resources required, we didn't compare a host of MADRL methods with learning centralization in between parameter sharing and fully independent learning (such as shared critic methods); the level of variance between runs at that level necessitate many runs of each method and hyperparameter searches to get clear results. Furthermore, our bound for Theorem 1 is only tight when Λ(x) = x (leave exploring alternative forms of Λ(x) as future work). We finally hope that, motivated by the work, parameter sharing is attempted in a variety of real world cooperative multi-agent scenarios.
We state the lemma as an inequality since it matches the way in which we will utilize it in the proofs of Theorem 1 and Theorem 2 below. However, note that the above proof also holds when we have strict equality; i.e. if g(t) = g(t − 1) + α(C − g(t − 1)), then (0)).
Proof of Theorem 1. We first write out the update equation for the agent. Note that since there are no other agents, only information about the environment needs to be learned. Thus, I(t) = I env (t).
Next, let t * = log( )−log(1−I 0 ) log(1−Kenv) and consider I(t * ): Note that since the inequality only arises from upper bounding Λ(x) ≤ x, and Lemma 1 holds for equality, Theorem 1 actually gives an exact result for convergence time in the case when Λ(x) = x (note, however, that this is not a realistic Λ for real-world algorithms).
Proof of Theorem 2. We begin by considering the function I i,j (t), which will be the same for all pairs of agents i, j.
In order to further expand ∆ ↓ I i,j (t), we must first write out ∆ ↑ I j (t) as below.
To allow us to simplify these expressions further, we note that since all agents are modeled identically in this setting, I i,j is the same for all agents i, j. We will denote thus denote by I , (t) this value (thus, I i,j (t) = I , (t) for all i, j ∈ [N ]). Thus, we get ∆ ↑ I j (t) = (n − 1)K Λ(C − I , (t − 1)).
This gives us the full expansion of ∆ ↓ I i,j (t) below.
Proof of Theorem 3. We examine the limit as K → 1.
, Ω i = Ω j for all i = j), then any collection of policies {π i } i∈ [N ] can be expressed as a single policy π [N ] : which, from the perspective of any single agent i, specifies a policy equivalent to π i . 1 Proof of Lemma 2. Let Ω = i∈[N ] Ω i be the set of all observations across all agents, and similarly define A = i∈[N ] A i to be the set of all actions available to agents.

B DETAILED ENVIRONMENT DESCRIPTIONS
In the pursuit environment, shown in Figure 2a, there are 30 blue evaders and 8 red pursuer agents, in a 16 × 16 grid with an obstacle in the center, shown in white. The evaders move randomly, and the pursuers are controlled. Every time the pursuers fully surround an evader, each of the surrounding agents receives a reward of 5, and the evader is removed from the environment. Pursuers also receive a reward of 0.01 every time they touch an evader. The pursuers have a discrete action space of up, down, left, right and stay. Each pursuer observes a 7 × 7 grid centered around itself, depicted by the orange boxes surrounding the red pursuer agents. The environment ends after 500 steps.
In the waterworld environment, there are 5 agents (purple), 5 food targets (green) and 10 poison targets (red), as shown in Figure 2b. Each agent has 30 range-limited sensors, depicted by the black lines, to detect neighboring agents, food and poison targets, resulting in 212 long vector of computed values about the environment for the observation space. They have a continuous action space represented as a 2 element vector, which corresponds to left/right and up/down thrust. The agents each receive a reward of 10 when more than one agent captures food together (the food is not destroyed), a shaping reward of 0.01 for touching food, a reward of −1 for touching poison, and a small negative reward when two agents collide based on the force of the collision. The environment ends after 500 steps.
In the multiwalker environment, shown in Figure 2c, there is a package placed on top of 3 pairs of robot legs which you control. The robots must learn to move the package as far as possible to the right. Each walker gets a reward of 1 for moving the package forward, and a reward of −100 for dropping the package. Each walker exerts force on two joints in their two legs, giving a continuous action space represented as a 4 element vector. Each walker observes via a 32 element vector, containing simulated noisy lidar data about the environment and information about neighboring walkers. The environment ends after 500 steps.

C EMPIRICAL COMPARISON TO MADDPG AND QMIX
We present additional results in Figure 5 comparing the performance of the best parameter sharing method against MADDPG and QMIX. We use the reference implementation of MADDPG from Lowe et al. (2017) and QMIX from Samvelyan et al. (2019) (improved implementation by authors of Rashid et al. (2018)). For QMIX, we also had to adapt the continuous action spaces to discrete by assigning discrete values to uniformly random action space samples. We adapted the network architecture to be the same in our other experiments, and hyperparameters were left to their default values in the reference codebase except those standard across all experiments. The full list of hyperparameters is in Appendix D. QMIX was adapted to continuous actions via binning, the original MADDPG supports it natively.
These results are insufficient to conclusively comment on the utility of the underlying strategies taken by QMIX and MADDPG that differ from vanilla parameter sharing. Doing so would require very large experiments involving different learning methods, environments, and hyperparameters. Rather our experiments offer a simple performance compression to more widely known methods, and demonstrate the apparent utility of vanilla parameter sharing from the perspective of a practitioner.

D HYPERPARAMETERS
Hyperparameters for various RL methods and for various games are given in Tables 1, 3, and 2. Some hyperparameter values are constant across all RL methods for all games. These constant values are specified in Table 4.