SPD: Synergy Pattern Diversifying Oriented Unsupervised Multi-agent Reinforcement Learning
Authors: Yuhang Jiang
Jianzhun Shao
Shuncheng He
Hongchang Zhang
Xiangyang Ji
Venue: NeurIPS 2022 Accept (2022)
Keywords: Unsupervised Reinforcement Learning
Multi-agent Reinforcement Learning

Abstract: Reinforcement learning typically relies heavily on a well-designed reward signal, which gets more challenging in cooperative multi-agent reinforcement learning. Alternatively, unsupervised reinforcement learning (URL) has delivered on its promise in the recent past to learn useful skills and explore the environment without external supervised signals. These approaches mainly aimed for the single agent to reach distinguishable states, insufficient for multi-agent systems due to that each agent interacts with not only the environment, but also the other agents. We propose Synergy Pattern Diversifying Oriented Unsupervised Multi-agent Reinforcement Learning (SPD) to learn generic coordination policies for agents with no extrinsic reward. Specifically, we devise the Synergy Pattern Graph (SPG), a graph depicting the relationships of agents at each time step. Furthermore, we propose an episode-wise divergence measurement to approximate the discrepancy of synergy patterns. To overcome the challenge of sparse return, we decompose the discrepancy of synergy patterns to per-time-step pseudo-reward. Empirically, we show the capacity of SPD to acquire meaningful coordination policies, such as maintaining specific formations in Multi-Agent Particle Environment and pass-and-shoot in Google Research Football. Furthermore, we demonstrate that the same instructive pretrained policy's parameters can serve as a good initialization for a series of downstream tasks' policies, achieving higher data efficiency and outperforming state-of-the-art approaches in Google Research Football.

SPD: Synergy Pattern Diversifying Oriented
Unsupervised Multi-agent Reinforcement Learning
Yuhang Jiang, Jianzhun Shao, Shuncheng He, Hongchang Zhang, Xiangyang Ji
Department of Automation
Tsinghua University, Beijing, China
{jiangyh19, sjz18, hesc16, hc-zhang19 wtt.ammaaaainnnge.eeee edu. xyji@tsinghua edu.
Abstract
Reinforcement learning typically relies heavily well-designed reward signal, which gets more challenging in cooperative multi-agent reinforcement learning. Alternatively, unsupervised reinforcement learning (URL) has delivered its promise in the recent past to learn useful skills and explore the environment without external supervised signals. These approaches mainly aimed for the single agent to reach distinguishable states, insufficient for multi-agent systems due to that each agent interacts with not only the environment, but also the other agents. We propose Synergy Pattern Diversifying Oriented Unsupervised Multi- Reinforcement Learning (SPD) to learn generic coordination policies for agents with no extrinsic reward. Specifically, we devise the Synergy Pattern Graph (SPG), a graph depicting the relationships of agents at each time step. Furthermore, we propose episode-wise divergence measurement to approximate the discrepancy of synergy patterns. To overcome the challenge of sparse return, we decompose the discrepancy of synergy patterns to per-time-step pseudo-reward. Empirically, we show the capacity SPD to acquire meaningful coordination policies, such as maintaining specific formations in Multi-Agent Particle Environment and pass- and-shoot in Google Research Football. Furthermore, we demonstrate that the same instructive pretrained policy's parameters serve good initialization for series of downstream tasks' policies, achieving higher data efficiency and outperforming state-of-the-art approaches in Google Research Football.
Introduction
Deep reinforcement learning (RL) has exhibited excellent capabilities in tackling complex tasks, including Go [40 36), poker (27 and simulated robotic tasks (37 13). However, one of the key
challenges in deploying RL algorithms is to devise an elaborate reward signal for eliciting desired behaviour of agents [14. Due to the sharing of the team reward, the situation gets more complicated for cooperative multi-agent reinforcement learning (MARL), especially in real-world applications such as coordination of robot swarms [16] and autonomous vehicle teams [52], where verifying the effectiveness of the designed reward can be prohibitively costly.
As for the single agent, unsupervised learning has been incorporated into RL to acquire diverse skills for the agent without extrinsic reward from the environment, and this scenario is known as unsupervised reinforcement learning (URL). Recent advances URL [0]
38 have demonstrated the potential of the agent to explore the environment and learn useful skills with no supervision. Moreover, when endowed with the task-related extrinsic reward in downstream tasks, these skills exhibit significant generalizability. leading to efficient adaptation. An important
15
20 3T
Equaa contribution.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

hypothesis explaining the phenomenon is made by DIAYN [0] that the higher the coverage of learned skills over the set of possible behaviour, the greater the probability of gaining effective skills.
Above mentioned URL approaches mostly depict the diversity of skills by the diversity of visited states, however, insufficient for MARL. due to the neglect of interactions with other agents. Intuitively, this coordination "skill" in MARL corresponding to the skill in single-agent URL should be taken into consideration as well. We term the coordination "skill" the Synergy Pattern, which is the perennial coordinated behaviour of agents induced by interactions of joint policies and the environment. In retrospect, the coordination of agents are usually modeled by graphs, such as coordination graphs [2] 4 [50] and graph neural networks [77 (1]. Nevertheless, these graph-based approaches are mainly tasked for communication and deploying the graphs directly to unsupervised MARL can be challenging.
We diversify the synergy patterns of agents by bridging the graphs and unsupervised MARL.. Specifi- cally, we devise the Synergy Pattern Graph (SPG), in which there is a vertex for each agent and the weight of the edge is derived from the function depicting the relations of agents, as the per-time-step instance of the synergy pattern. Our method Synergy Pattern Diversifying Oriented Unsupervised Multi-agent Reinforcement Learning (SPD) focuses on obtaining diverse synergy patterns while following the same hypothesis in URL. To this end, we approximate the Discrepancy of Synergy Patterns by quantifying the divergence between two SPG batches, which are sampled from the distributions of different synergy patterns respectively. The first step is to measure the discrepancy between two SPG elements. This problem is essentially to measure the similarity of graphs, which has been well-studied in the field of graph matching 39 26 32 9. and one of the promising approaches the Gromov- Wasserstein discrepancy [6] [11. With the adoption of the Gromov- Wasserstein discrepancy as the pair-wise measurement, we then formulate the discrepancy of synergy patterns as an episode-wise measurement and deploy it as the pseudo episode return for unsupervised MARL.
Our contributions for SPD, a general framework for unsupervised MARL, are summarized as follows: i) we devise SPG with general formulation as the instance to depict the synergy patterns of agents; íi) we propose an episode-wiss divergence measurement to estimate the discrepancy of synergy patterns; iii) we derive the formulation for the decomposition of the pseudo episode return to alleviate the problem of the sparse return; iv) The empirical results demonstrate that SPD achieves better performance in MARL. compared to conventional URI. approaches and shows great potentials to learn synergy patterns with generalizability for downstream tasks.
2 Related works
Multi-agent reinforcement learning (MARL) has shown great potential in solving multi-agent cooperation tasks. A popular paradigm in MARL is the centralized training with decentralized execution (CTDE) that combines the advantage of independent Q-learning [44] and joint action learning 77. Centralized training makes agents cooperate better while decentralized execution benefits the flexible deployment capability. We mainly focus on the value-based CTDE methods. Following the CTDE paradigm, a series of works concentrate on distributing the team reward to all agents by value function factorization
principle for 335 Another bunch of works introduce roles or skills to agents for 48 5 However, these methods usually suffer from poor generalization
43
34 , and deriving the Individual -oooaallggoll-mmiio
policy optimality analysis [2 46
better team cooperation 24
ability and have considerable performance drop when transferred to unseen scenarios. Wang et al. 49 reports agents' generalization by splitting the action space, but the method relies heavily on the handcrafted papee-parameter. The concept of agents' forming graph is also widely used to represent agents' cooperation in MARL, including the coordination graph [4 (0) and graph neural networks 21). But these methods are usually designed for communication, which brings extra costs for decentralized exccution. In contrast to these methods, our proposed method uses the synergy graph to train team skills without rewards from the environment, which brings the agents strong generalization ability in downstream tasks, and takes no extra cost in execution.
Unsupervised reinforcement learning (URL) has been particularly intriguing in the context of RL, consider the high cost of real-world rollouts with delicately designed reward signal. This paper is concerned about unsupervised behaviour learning for deep RL that requires learning with only the aank-agi intrinsic reward. Early works [T I mainly focuses on controlling the visited states via regulating latent variable Z, where the mutual information is maximized with visited
2

---

states. DIAYN [0] demonstrates the exceptional performance of URL by maximizing (Z: while simultaneously minimizing T(Z;A[S) The recent studies have also shown interests on adapting pre-trained skills on MDPs from aspects of the initial state 3 and the dynamics model [38] Besides, WURL [.5] adopts the idea of optimal transport and increases the discrepancy of learned skills by enlarging the distance of visited state distributions estimated by Wasserstein distance. These approaches aiming for achieving easily distinguishable states, however, they are deficient to solve the growing size of joint observation space in multi-agent systems. By contrast, our method devise graph to depict the relative relations between agents which alleviate the growing size challenge. There also works encouraging diversity for effective exploration [19 23 30 53], while they mostly enhance single policy's 's diversity or the inter-agent diversity and do not get rid of the dependence of the task-related reward. We follow similar hypothesis to that in Eysenbach et al. [TO] to learn diverse synergy patterns for gaining useful coordination policies.
3 Preliminaries
3.1 Notation
We consider a Dec-POMDP (29 for the fully cooperative multi-agent task with n agents, defined by tuple AS P, R, O.I, S2 n, 7). where E S and a' E AA denote the true state of the environment and the discrete action chosen by agent E I discount factor. The dynamics of the environment can be formulated as the state transition function P(s'|s, a): S x A x S - [0, 1] and the reward function R(s, a) : S x A + IR shared by all agents, where a A AA denotes the joint action. Each agent only has access its own observation of E O derived from the observation function (2(s, i) S x I - O, due to the partial observability.
n2., respectively.
E [0, 1) is the
At each time step agent resolves execute the action at according a stochastic policy x (a(a'(7' ('): T A + [0, 1]. where r' E T = (O x A)" denotes the action-observation history of the agent i. The goal of MARL is to find an optimal joint policy π = II n² satisfying the condition: Q" (s, a) 2
Q* a), Vq and (s, a) E S x A, where Q* (8r, a.) E E 1: 01 joint action-value function induced by joint policy æ
x
0 T' 92, ar is the
We adopt the paradigm of centralized training with decentralized execution (CTDE). During training the true state and the joint algorithm, while each agent i selects an action based on the policy conditioning only on its own action-observation history 7³ during testing (execution).
history = {r'H J==1
accessible to the learning
3.2 Optimal transport and Gromov-Wasserster Wasserstein discrepancy
Optimal transport (OT) is a general problem moving one distribution of mass to another as ef- ficiently possible. Likewise, the distinction of two given graphs can be regarded as an optimal transport problem to find the correspondence between their vertices and edges. Previous work (6) pro- posed Gromoy- Wasserstein Discrepancy, which is extended from as a measure for the divergence of the graphs.
distance 225
Definition 3.1. 6 57) (Gromov- Wasserstein discrepancy) Denote a measure graph as G(V, W.H). M where V = {(o:3 1= is the set of vertices, Wij E W is the weight of the undirected edge {i,}} between vertices U; Uj E V, and
[nu] E V is a Borel probability measure defined on V. Vp E [o] and each Gu, Ge E G, where G denotes the collection of measure graphs, the Gromov- Wasserstein discrepancy between G, and G2 can be derived as
Σ Σ (EE
dgw (G), == min TEl(Hoaee))
Wii wirl TwoT3s
iSEV s'.''..
where II (In, T T1 = py, T 1 = }s3
In general, the comparing the differences of the edges' relationship in one graph to that in the other. We refer the reader to Mémoli (25) Chowdhury & Mémoli (6), Peyré et al. [33 for mathematical foundations.
discrepancy measures the divergence between two graphs by
3

---

4 Methodology
This section is organized as the following: Sec. 4.1 we delineate the concept of Synergy Pattern and propose novel structure of graph as the instance of it, namely Synergy Pattern Graph. We then carefully derive the formulation for Discrepancy of Synergy Patterns and make an approximation of it for convenience in practice in Sec. 4.2 In Sec. 4.3 our unsupervised framework SPD is depicted in
detail and the mechanism for the decomposition the pseudo reward explained. Sec. [.4 provides the implementation details for solving the optimization problem.
4.1 Synergy pattern
With the awareness of interactions between agents' actions, we describe the perennial coordinated behaviour of agents by the Synergy Pattern. Previous methods [12] 4 17 21] utilize the structure of graph to depict it, whereas most of them focus on the local relationship between agent pairs towards specific task. To get rid of the extrinsic reward signal, we propose Synergy Paltern Graph (SPG), the vertex for agent i and the weight wij E W of edge j is derived from synergy pattern patternfunctioo function which could depict agents' relative relations:
denoted as (V, W. Jr, S), where i
<(r',T)) x R
The synergy pattern function follows a general formulation any function with range R5- for instance, the information-theoree munication messages 4 It can depend on more than merely the observations and joint actions as well, whereas we omit this for simplicity. At each time step, SPG varies depending on the history of the multi-agent system rather than being predefined before training. We will use G2 to denote GeP (V. W. p. () at time step in the following part of this paper for ease of notation.
influence [7]: ((T",=") -=)==== := MT o' a²) or the com-
Accordingly, the synergy pattern can be described by the distribution of SPG obtained by deploying a joint policy in the environment: IP TT with domain A, where A is the collection of all SPG.
4.2 Discrepancy of synergy patterns
We use the discrepancy between two distributions of SPG: IP( (T) and IP TT2 to denote the discrepancy between two synergy patterns. This process can be decomposed into two phases: measuring the distance between two samples from each distribution respectively; ii) extending the metric for pair of samples to that for distributions. The former one is essentially estimate the discrepancy between graphs. We adopt the Gromov- Wasserstein discrepancy of graphs, as mentioned in section 3.2. to measure this distance. Besides, we solve the latter one by applying optimal transport on SPG distributions.
This whole process leads to the following definition:
T2) be two distributions of SPG induced by joint polices Hi and π2, respectively. Denote an joint distribution E ['P1.Pa) as bijective plan transporting probability mass from Pı to P2, where I'[p1, [2] is the set of all distributions on product space A A with pı and p2 as their marginal probabilities. Then the discrepancy of synergy patterns is defined as
Definition 4.1. (Discrepancy of Synergy Patterns) Let = P(G (T)) and p2 = F
dsp(p1,P2)= inf seT|pr.pa)
dG= (maa) de
where dyw is the Gromov- Wasseeettess discrepancy according to Eq. T Besides, we show that dap a legitimate pseudometric on and the proof deferred to Appendix A.
However, solving Eq. (2) for the discrepancy of synergy patterns is almost intractable. In practice, collect two SPG batches to approximate the discrepancy of synergy patterns. Here, give the definition for this approximation:
Definition 4.2. (Proximal Discrepancy of Synergy Patterns) Denote x = [GT+ B ~ P(G*: (m) }Ba
and T {G Je=0 P m2) sampled from the distributions of SPG, where B1, By N*.
Assume B < Bg by symmetry. Let D [dgw GRt) VO ti < B1, < to S B

---

min Σ De.
Σ
Dr.i
p())
dgw
Matrix
Figure I: Illustration for the process of obtaining proximal discrepancy of synergy patterns dap (left) and the process of computing pseudo reward (right).
be the cost matrix. Suppose that injective function p (I,...., B1} + (1..... B2) denotes an matching function. By minimizing the total cost, an approximation for the discrepancy of synergy patterns is:
B1
(
min
Dt.(()
t=U
is vital to point out that the SPG from X corresponding to G may not be G. since the relations of agents may be analogous at different time steps. Hence, search the whole A for G that is relatively adjacent to G,, based on the Gromov- Wassersten discrepancy.
p(t)
4.3 Synergy pattern diversifying oriented unsupervised multi-agent reinforcement learning
Based on the discrepancy of synergy patterns, we can now delineate the framework for SPD. Suppose that Z E N+ denotes the number of different synergy patterns. Our goal is to learn set of joint policies { with diverse synergy patterns explore the environment sufficiently when there no extrinsic reward. To increase the divergence among synergy patterns, we formulate the pseudo episode return for the episode data T= produced by the joint policy N.:
(T (TR))
min 1skg2
(Am (**),
(4)
where 1 S Z, and A= is the SPG set derived from T.. Besides, obtain AT by sampling batch of data from the replay buffer Tæ and ensure A have more elements: { > [
Our method to maximize the expected return: max ([ {T&))I, resulting tion of each discrepancy of one synergy pattern to its nearest counterpart. However, the pseudo episode return Eq. (4) depending on the whole episode data т. is sparse since it only derives single final reward for one episode. This imposes the trouble for MARL algorithms to learn accurate action-value function Q* (s, a.) and tends to impair the performance value-based MARL algorithms. To bypass this predicament, intuitively, the pseudo episode return (T, (Tx}) can be decomposed into pseudo rewards for every time step according the optimal matching function p". Concretely, the pseudo reward at time step can be formulated as:
maximiza-
Fr(T., (T+}) (G G G
G G
E AT= AM Gr E A
where p" is the optimal solution dap (A*= A by Eq. and ks denotes the id of the synergy pattern with minimal discrepancy A according Eq. (4) In other word, the pseudo reward is the Gromov-Wasserster Wasserstein discrepancy of the SPG at current time step and the SPG from the counterpart of another synergy pattern.
We discriminate the concepts we proposed Appendix D for a clearer understanding. The visualiza- tion for the pscudo reward derivation is shown in Fig. [
5

---

4.4 Implementation
We implement SPD with QMIX (44, learning a set of joint policies that maximize the discrepancy of synergy patterns to each other. QMIX is designed to have mixing network structure. learning 8f
global action-value function Q := tQtot tot (T, a) f. (r))).)))..... Q" , aa))
aQ
Z
0, (+,,) :) E IR] which satisfies the IGM principle 42 to accomplish the cooperative task agents.
During unsupervised learning. we select I = S for the synergy pattern at the start of each episode randomly in turn, and interact with the environment according to the joint policy я throughout the episode. In practice, the Euclidean distance of o² and o² is adopted as the weight wij of edge { to build the SPG, i.e., the formulation of synergy pattern function is ((T", will show in Sec. that, even with such synergy pattern function grab the simple information of relationships of agents, SPD can still learn useful synergy patterns such as pass-and-shoot in Google football Research and accelerate the learning procedure when endowed with the task-related reward.
I|o - 22 We
Since solving for the -aanoo-Wassersteein discrepancy between two measure graphs in Eq. ( is a computationally costly process, we adopt [5]]ss 's Regularized Proximal Gradient method to estimate it. We set in Eq. T in our experiments. As for the probability measure, we set n since the agents assumed to have equal contributions, where is the number of agents vertices in synergy patterns and 1, is size n vector of ones. In the m-th iteration, the current optimal transport ((m) can be updated by
(m++1) argmin TeD(ppd)))
Σ Σ
Ji/s - way 12 ((m))(m)
" + (T((T))()))
LJEV V'E.
(6)
argmin (LWW,, We, T(n)), T) + {KI((T)T(m)
TEN((A)))))
where L(W,, We, (()) Wo M. + In W 2W,TW and Kullback-Leibler (KL) divergence is added the proximal term. (..-) denotes the inner product of two matrices and a convergence 2 by the Sankhorn-Knoppe algorithm 41 g) As soon as (()) converges stable optimal transport T, the estimation of the Kromov-Wassersee discrepancy can be calculated by plugging T into Eq. (1.
to balance two items. The Eq. (6) can then be solved with nearly-linear
To solve Eq. 3 we utilize Kuhn-M Munkres algorithm 28 which could solve such an assignment problem polynomial time, to obtain the optimal matching funciton p". Therefore, the complete formula for pseudo reward at time step i is below:
A((T,, (T&)) (G G
Σ Σ
-w wh (
1 Tie
iJEVT '''EV'
(7)
where G. E A Gp E Ae and ke denotes the id of the synergy pattern with minimal discrepancy to A according to Eq. 44. The whole framework summarized in Algorithm
Experiments
In this section, we first compare properties SPD with that of other URL baselines on Multi-agent Particle Environment (MPE) 22 in Sec. 5.1 And in Sec. S.c. we evaluate the generalization ability
of our method on downstream tasks on Google Research Football (GRF) [18] Our code is available at bttph:::/// thub. com/ com/thu-rrlab/SS
5.1 Synergy pattern diversifying
We demonstrate that our method SPD is capable of capturing more inherent properties of multi-agent systems such as the impacts from other agents, comparing conventional URL algorithms. In order

---

Algorithm SPD
Input: Z, sant Empty graph buffers {D&) -1. Empty replay buffers {D 12 The synergy
pattern function described in section 4.1
Maximal time steps for each episode maa
Parameter: joint policy networks {To, 1==1
1: Initialize temy 0, (0k 10x
2: for each episode do
3: Select randomly in turn, T2 0. 0:
4: while not done do
5: Interact with the environment by n, to get the tuple (s, a, s');
6:
Ts f Ts U {(s, a, s')}.
7:
Build SPG with ((T=); A t- a UUG), D= t D-
8:
9:
tem t- Lewv +1;
10:
end while
if fenv 2 Estar then
12:
for each k + do A DDx.
14:
# via Sinkhorn Knopp algorithm
15:
Obtain dg G*v) according to Eq. (6) as well as Eq. D
16:
# via Kuhn Munkres algorithr thm
17:
Obtain dip (A*,, \ar) by solving Eq. for p":
18:
end for
19:
k-" + argming dip:
20:
Calculate i by plugging k* pp into Eq. 7
21: DRL t- DRL U (T=, {f) {f)
22:
Use an MARL algorithm to train 02 with D
end
24: end for
to verify this claim, we first evaluate the diversity of coordination policies learned by SPD and URL baselines in Multi-agent Particle Environment (2 45 We customize the scenario Simple'Tag, which is predator-prey environment, for URL experiments by discarding the extrinsic reward from the environment. Instead, we are concerned about the diversity of agents' formations driven by learned coordination policies. The detailed description of the scenario please refer to Appendix B.1.
Baselines and evaluation We compare our method SPD with several conventional single-agent URL approaches. Here is the details about the implementation of URL algorithms, which we carried out to learn policies without external reward:
SPD: we follow the narration of the implementation details Sec. is derived via Eq.
4.4 The pseudo-reward
Diversity Is All You Need (DIAYN) 10: The joint policy л ( T =) is conditioned on discrete latent variable z sampled from pre-defined categorical distribution p(z): p(z). The pseudo-reward with formulation inspiring agents to visit states that can be distinguished easily, where {o 1) is learned discriminator. In experiment, replace the actor network xaa T shared by all coordination policies with Z individual networks ) { observation space and action space.
:= log qs [o'
l(z)(z) is used for
considering the large
The pseudo-reward is designed to enhance the distance between different policies, and it obtained by estimating the Wasserstein distance of the induced state distributions: Ts W Tk), where T2 is the trajectory driven by current joint policy π (alTz) and Fx is sampled batch from another joint policy π..
Wasserstein Unsupervised Reinforcement Learning (WURL.) 15]:

---

The URL algorithms are implemented with QMIX to learn diverse joint policies { and we set Z 10 in practice. The hyper-parameters are kept to be the same, and please refer to Appendix B.2 for details, For evaluation, each algorithm is carried out with 5 different random seeds and trained with 10 steps interacting with the environment. All the intrinsic pseudo-rewards are derived based on the positions of agents, which is part of the original observation space.
Since DIAYN and WURL are designed for the single agent case, we deploy them by regarding all agents as single agent. Concretely, we use observations from all agents to create the features that DIAYN and WURL need.
Method
DSR(%)
Normalized dap
DIAYN WURL
59.9 = 0.9
(4.0 2.7) 10
58.7 + 1.5
(3.9 + 3.6) x 10-3
We evaluate these algorithms following the same protocol: (i) collect sample transitions except trinsic reward using each joint policy ==(as (a(TT) T)
SPD (Ours)
58.6 + 0.7
1.0 + 0.1
Table 1: The discriminator success rate (DSR) and normalized proximal discrepancy of synergy patterns dap for URL methods DIAYN, WURL and SPD (Ours).
(ii) calculate the pseudo-rewards } for each time step and then assign them to the trajectory T
(iii) employ learned joint policies once the train- ing procedure is completed to collect {T!! )==1
for evaluation. We use two metrics to evaluate how diverse are the learned joint policies from different aspects: the diversity of states and the discrepancy among relative relationships of agents induced by (x { As for the former one, we adopt the structure the discriminator {2| }===) from DIAYN, which is learned neural network to classify each policy я= from state samples in (7fina) ) 2= and use the success rate of the discriminator to measure how diverse are the states, namely Discriminator Success Rate (DSR). As discussed in Sec. 4.2] the discrepancy of synergy patterns dep according to Eq. 2 is an effective measure for the latter one. Table | shows that the performance of all algorithms
DSR is close, whereby SPD significantly outperforms the others on the discrepancy of synergy patterns. Such results demonstrate that SPD can inspire agents to visit comparably identifiable states as the conventional URL approaches, while further motivating agents to explore diverse coordination policies in the meanwhile.
Ablation study We examine the following com- ponents of our method in detail to show their ef- fects: (i) Reward scale 3,: we multiply the pseudo- reward in Eq. (5) with a factor vary in {0.1, 1.0, 10.0) to change the scale of the final returns received by agents, and 10.0 is the default value in the aforemen- tioned experiments. (ii) Sparse return Rg: To eval- uate the effect of the decomposition of the pseudo- return in Eq. ( we directly use it as the pseudo- reward of the last step in the episode. (iii) On-policy p(t) t: As discussed in Sec. 4.2 that the SPG from x= corresponding to G may not be G.²,. To verify this claim, we set p(l) = directly and the pseudo-reward becomes to p2(00 /(lec)/ (T [Tx
8 10.0 (delaut))
1-10
Sparse retum & Suboptiaa
200
600
700
(G. GG ,G ). where G.* E Ax=, G E A (iv) Sub-optimal p: The matching function p² is ob- tained by Luhn-Munkre the precision is influenced by the number of iterations, which defaults to Aoter = 100 in the experiments. lower number of iterations MiM = 25 is used to show the influence from the precision of the matching func- tion.
T (xx10²)
algorithm (28). Therefore,
Figure 2: Ablation study. We change the scal- ing factor 8r multiplying the pseudo-reward from [0.1, 1.0, 10.0]. "Sparse return R, " means using Eq. 4 as final the reward di- rectly. "On-policy p(t) t" means we ap- ply no optimal transport and set p(t) t in Eq. ( to suit the on-policy manner comput- ing pseudd-reward on-the-fly. And we reduce the precision of the solution for Eq. (6) in "Sub-optimal p"
We use dep as the evaluating indicator and the results shown Fig. 2 The curves start from the time step that the exploration rate epsilon has stopped annealing. We can summarize that the reward scale plays an important role in learning good synergy patterns. Canceling the optimal transport for
8

---

Htalhcourts
Helicourt
Fut rul-ccurt: Possmmton can change
Room
1900
Figure 3: Compare the performances of using one model trained by URL algorithms as the parameter initialization for four different tasks with learning by traditional MARL algorithms directly.
matching decreasing its accuracy both harm the performance. And the "Sparse return R." " curve shows that amortizing the episode return to each time step simplifies the training.
5.2 Generalizability of learned synergy patterns
In this part we demonstrate the generalization ability of the models trained by SPD. Specifically, we first train SPD on the complicated MARL environment: Google Research Football [18] without environment reward. Then we use the trained model as the initialization for different tasks with specific rewards, and use common MARL algorithms to train it.
Task description We choose the map "academy 3 vs 1_wtth_ keeper" with the setting from CDS [5], where three players need to cooperate to shoot and get a score under the defense of an opposing player and goalkeeper. To simplify the training. the original environment ends episode the ball or the player return to the left half-court. Players always start at the same place. Losing the control of the ball also cause the failure. The team is rewarded 100 the end of an episode when there is a goal, otherwise -1 On the basis of this scenario which we call "Half-court; Fixed Init", we design series of tasks with more difficulty. (i) We initialize the agents randomly in circle with 5% court width's ' radius, which increases the difficulty by introducing more randomness. (ii) We remove the restrictions on the left-half court, which greatly increases the exploration space. (iii) The possession change will not end the episode, which may increase the percent of the bad samples in the replay buffer, since at the beginning of training the ball is easily robbed by the preset Al opponent.
Utilizing SPD model We first train the models by SPD with == 20 on the "Half-court; Possession can change" scenario without the environment reward for 10 time steps, as well as WURL [T5] and DIAYN 100. Then we use the same trained parameters as the initialization for QMIX 34 on
four different downstream scenarios. In contrast to the manual selection of the synergy patterns, we test them on the downstream task before MARL training, choosing the parameters of the model with the highest average return as the model initialization. We show the results in Fig. 3 together with the SOTA on GRF including QMIX (34), QPLEX [46] and CDS [5]. The results show that using the model learned by conventional single-agent URL methods (WURL and DIAYN) as the initialization mostly performs similarly to the baseline QMIX, while WURL slightly outperforms QMIX on the "Full-court" maps. In contrast, SPD learns faster and finally gets higher winning rate on all scenarios, demonstrating the effectiveness of dap agents' relationship and showing that SPD embeds the model with stronger generalization ability. Actually, one difference between SPD and these URL methods is that SPD encourages the diversity of the relationship among agents while these diversity methods encourages the diversity visited states. Therefore, the models trained by WURL may reach diverse states on the 'Full-court' maps which need more exploration and we believe this accounts for the slightly better performance.
evaluation metric for the difference of
Visualization of the learned synergy patterns To comprehensively evaluate SPID, we visualize the trajectories of all the skills and show three of them in Fig. 4 The trajectories of other skills can be found in Appendix C. We find that agents can perform some meaningful behavior from a human perspective, even without the supervision of the environment reward. Agents can dribble for a long
The videos for all synergy patterns be found at: https://sites. www.:/oolll....o//////oeo/eee//e

---

Current
Position
Time Order
History
Position
Agent
Movement
Ball Passing
&Shooting
(a)
(b)
Figure 4: Visualization of the learned synergy patterns without environment reward. (a) Dribbling and long passing. (b) Passing and shooting. (c) Running back to play defense.
distance, pass between teammates, shoot, and run back together in different skills. our concern that the different performance of different joint policies learned by SPD are only due to the randomness of the GRF environment itself not the inter-policy diversity we want, we deploy each learned joint policy for 10 episodes and visualize them. The results show that each joint policy exhibits the similar coordination behavior across episodes. The visualization shows that making the team coordinate more diverse drives agents to learn meaningful behaviour, which is favorable for downstream tasks.
6 Discussion
6.1 Limitations
There are still some limitations or difficulties with further applications. Though the discriminator success rate (DSR) used in Sec. [5. not a good measure for relationships of agents, it does evaluate the diversity of visited states in some ways. The results on DSR show that all of the URL approaches, including our method SPD, are far away from satisfying, implying that there still space for improvement. Furthermore, synergy pattern function Ç that embeds more information than the one used in this paper is tend require higher computational cost. Moreover, incorporating hiversity-based exploration technique with SPD may improve the intra-agent diversity as well as inter-policy diversity. These limitations may suggest further research directions.
6.2 Negative societal impact
Due to the domain gap between virtual environments and real-world scenarios, applying our method directly to real-world applications, such traffic management, is risky and may result in damage to the system. To avoid harmful operations, human supervision is required to restrict the learned models.
7 Conclusion
this work, we propose a general unsupervised framework Synergy Pattern Diversifying Oriented Unsupervised Multi-agent Reinforcement Learning (SPD) to learn useful synergy patterns for agents. Synergy pattern graph (SPG) is devised to depict the relationship among all agents. Furthermore, upproximate the discrepancy of synergy patterns by applying optimal transport the batches sampled from the distributions of SPG. In our experiments, we show that SPD surpasses conventional URL approaches capturing the relative relations of agents and learns useful synergy patterns with no task-related reward. We also empirically demonstrate that the learned policies can accelerate the downstream training procedure and outperform sate-of-theearr algorithms in GRE
8 Acknowledgement
This work was supported by the National Key R&D Program of China under Grant 2018AAA0102301,, National Natural Science Foundation of China under Grant 61620106005.
10

---

References
[1] Achiam, J., Edwards, H., Amodei, D., and Abbeel, P. Variational option discovery algorithms. arXiv preprint 1xX7v 2018.
[2] Altschuler, J., Niles-Weed. and Rigollet, Near-linear time approximation algorithms for optimal transport via sinkhorn iteration. Advances in neural information processing systems, 30, 2017.
[3] Baumli, K., Warde-Farley, D., Hansen, S., and Mnih, Relative variational intrinsic control. arXiv preprint arXhv:2012.078277 2020.
[4] Böhmer, W., Kurin, V., and Whiteson, S. Deep coordination graphs. In International Conference on Machine Learning, pp. 980-991. PMLR, 2020.
[5] Chenghao, L., Wang, T. Wu, C., Zhao, Q. Yang. J., and Zhang, C. Celebrating diversity in shared aulti- reinforcement learning. Advances in Neural Information Processing Systems, 34, 2021.
[6] Chowdhury, S. and Mémoli, F. The wrsserswass distance between networks and stable network invariants. CoRR, abs/1808 1001188..040 008.04337, 2018. URL http::/arxiv... wwwp:/ivvvrrgg///..o//ooo
04337
[7] Claus, C. and Boutilier, C. The dynamics of reinforcement learning in cooperative multiagent systems. In AAAI Conference on Artificial Intelligence (AAAI), 1998.
[8] Cuturi, M. Sinkhorn distances: Lightspeed computation of optimal transport. Advances in neural information processing systems, 26, 2013.
[9] Dong, Y. and Sawin, W. Copt: Coordinated optimal transport on graphs. Advances in Neural Information Processing Systems, 13:19717-19338, 2020.
[10] Eysenbach, B., Gupta, A., Ibarz, J., and Levine, S. Diversity is all you need: Learning skills without a reward function. In International Conference on Learning Representations, 2019. URL htt.tttt/t//peereeieeeee// htt.:eeeeoeooommdddderr3...
[11] Gregor, K., Rezende, D. J., and Wierstra, D. Variational intrinsic control. In 5th International Conference Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Workshop Track Proceedings, 2017.
[12] Guestrin, C., Lagoudakis, M. G., and Parr, R. Coordinated reinforcement learning. In Sammut, C. and Hoffmann, G. (eds.), Machine Learning, Proceedings of the Nineteenth International Conference (ICML 2002), University of New South Wales, Sydney, Australia, July 8-12, 2002, pp. 227-234. Morgan Kaufmann, 2002.
[13] Haarnoja, T., Zhou, A., Hartikainen, K., Tucker, G., Ha, S., Tan, J., Kumar, V., Zhu, H., Gupta, A., Abbeel, P., et al. Soft actor-critic algorithms and applications. arXiv preprint arXiv:1812.05905,, 2018.
[14] Hadfield-Menell, D., Milli, S., Abbeel, P., Russell, S. J., and Dragan, A. Inverse reward design. Advances neural information processing systems, 30, 2017.
[15] He, S., Jiang, Y., Zhang, H., Shao, J., and Ji, X. Wasserstein unsupervised reinforcement learning, arXiv preprint arXiv:2110.079440 2021.
[16] Hüttennauch, M., Šošic, A., and Neumann, G, Guided deep reinforcement learning for swarm systems. arXiv preprint arXiv: / /709.0601. 2017.
[17] Jiang, J., Dun. C., Huang. T., and Lu, Graph convolutional reinforcement learning. arXiv preprint 1rX1v:1870.09202, 2018.
[18] Kurach, K., Raichuk, A., Staúczyk, P., Zajac, M., Bachem, O., Espeholt, L., Riquelme, C.,
Vincent, D., Michalski, M., Bousquet, O., al. Google research football: novel reinforcement learning environment. arXiv preprint 1907. 2019.

---

[19] Lee, L.. Eysenbach, B., Parisotto, E., Xing, E., Levine, S., and Salakhutdinov, R. Efficient exploration via state marginal matching. arXiv preprint arXiv:1906.052770 2019.
[20] Liu, H. and Abbeel, P. Behavior from the void: Unsupervised active pre-training. Advances in Neural Information Processing Systems, 34, 2021.
[21] Liu, Y., Wang, W., Hu, Y., Hao, J., Chen, X., and Gao, Y. Multi-agent game abstraction via graph attention neural network. In AAAI Conference on Artificial Intelligence (AAAT), 2020.
[22] Lowe, R., Wu, Y. L., Tamar, A., Harb, J., Abbeel, O. P., and Mordatch, I. Multi-agent actor-critic for mixed pupperraivvecoopptttyv environments, In Advances in neural information processing systems (NeurIPS), 2017.
[23] Lupu, A., Cui, B., Hu, H.,, and Foerster, J. Trajectory diversity for zero-shot coordination. In International Conference Machine Learning, pp. 7204-7213. PMLR, 2021.
[24] Mahajan, A., Rashid, T., Samvelyan, M., and Whiteson, S. Maven: Multi-agent variational
exploration. Advances in Neural Information Processing Systems, 32, 2019.
[25] Mémoli, F. Grssov-wasserstiin distances and the metric approach to object matching. Foun- dations of computational mathematcs. 11(4):417-487, 2011.
[26] Mena, G., Belanger, D., Linderman, S., and Snoek, Learning latent permutations with gumbel-sinkhorn networks. arXiv preprint arXiv:1802.0860 08665, 2018.
[27] Moravčík, M., Schmid, M., Burch, N., Lisý, V., Morrill, D., Bard, N., Davis, T., Waugh, K., Johanson, M., and Bowling, M. Deepstack: Expert-level artificial intelligence in heads-up no-limit poker. Science, 356(6337):508- 501355133)) 2017.
[28] Munkres, J. Algorithms for the assignment and transportation problems. Journal of the society for industrial and applied mathematics, 5(1):32-38, 1957.
[29] Oliehoek, F. A., Amato, C., et al. A concise introduction to decentralized POMDPs. Springer, 2016.
[30] Parker-Holder, J., Pacchiano, A., Choromanski, K. M., and Roberts, J. Effective diversity in population based reinforcement learning. Advances Neural Information Processing Systems, 33:18050-18062. 2020.
[31] Pathak, D., Gandhi, D., and Gupta, A. Self-supervised exploration via disagreement. In International conference on machine learning, pp. 5062-5071. PMLR, 2019.
[32] Petric Maretic, H., El Gheche, M., Chierchia, G., and Frossard, Got: an optimal transport framework for graph comparison. Advances in Neural Information Processing Systems, 32, 2019.
[33] Peyré, G., Cuturi, M., et al. Computational optimal transport: With applications to data science. Foundations and Trends@ in Machine Learning, 11(5-6)3355600 2019
[34] Rashid, T., Samvelyan, M., De Witt, C. S., Farquhar, G., Foerster, J., and Whiteson, S. Qmix: Monotonic value function factorisation for deep multi-agent reinforcement learning. arXiv preprint arXiv: 11455, 2018.
[35] Rashid, T., Farquhar, G.. Peng. B., and Whiteson, Weighted qmix: Expanding monotonic value function factorisation. arXiv e-prints, pp. arXiv-2006, 2020.
[36] Schrittwieser, J., Antonoglou, I., Hubert, T., Simonyan, K., Sifre, L., Schmitt, S., Guez, A., Lockhart, E., Hassabis, D., Graepel, T., et al. Mastering atari, go, chess and shogi by planning with learned model. Nature, 588(7839):604 609, 2020.
[37]
J., Levine, S., Abbeel, P., Jordan, M., and Moritz, P. Trust region policy optimization. In International conference on machine learning, pp. 1889-1897. PMLR, 2015.
J.,
[38] Sharma, A., Gu, S., Levine, S., Kumar, V., and Hausman, K. Dynamics-aware unsupervised discovery of skills. arXiv preprint 197.0.790. 2019.
12

---

[39] Shervashidze, N., Vishwanathan, S., Petri, T., Mehlhorn, K., and Borgwardt, K. Efficient graphlet kernels for large graph comparison. In Artificial intelligence and statistics, pp. 488- 495. PMLR, 2009.
[40] Silver, D., Schrittwieser, J., Simonyan, K., Antonoglou, I., Huang, A., Guez, A., Hubert, T., Baker, L.. Lai, M., Bolton, A., et al. Mastering the game of go without human knowledge. nature, 550(7676):354-333
2017.
[41] Sinkhorn, R. and Knopp. P. Concerning nonnegative matrices and doubly stochastic matrices. Pacific Journal of Mathematics, 21(2):343-348, 1967.
[42] Son, K., Kim, D., Kang, W. J., Hostallero, E., and Yi, Y. Qtran: Learning to factorize with transformation for cooperative multi-agent reinforcement learning. In International Conference on Machine Learning (ICML), 2019.
[43] Sunchag, P., Lever, G., Gruslys, A... Czarnecki, W. M., Zambaldi, V. F., Jaderberg, M., Lanctot, M.. Sonnerat, N., Leibo, J. Z.,, Tuyls, K., et al. Value-decomposition networks for cooperative multi-agent learning based on team reward. In International Conference on Autonomous Agents and MultiAgent Systems (AAMAS), 2018.
[44] Tan, M. Multi-agent reinforcement learning: Independent vs. cooperative agents. In Interna- tional Conference on Machine Learning (ICML), 1993.
[45] Terry, J., Black, B., Grammel, N., Jayakumar, M., Hari, A., Sullivan, R., Santos, L. S., Dief- fendahl, C., Horsch, C., Perez- Perez-Vicente,, R., et al. Pettingzoo: Gym for multi-agent reinforcement learning. Advances in Neural Information Processing Systems, 34:1 5432-15555 2021.
[46] Wang, J., Ren, Z., Liu, T., Yu, Y., and Zhang, C. Qplex: Duplex dueling multi-agent q-learning. arXiv preprint arXiv:2008. 00062, 2020.
[47] Wang, T., Wang, J., Wu, Y., and Zhang, C. Influence-based multi-agent exploration. arXiv preprint arXiv: 1910.055 12, 2019.
[48] Wang, T., Dong, H., Lesser, V., and Zhang, C. Roma: Multi-agent reinforcement learning with emergent roles. In International Conference on Machine Learning (ICML), 2020.
[49] Wang, T., Gupta, T., Mahajan, A., Peng, B., Whiteson, S., and Zhang, C. Rode: Learning roles to decompose multi-agent tasks. arXiv preprint arXiv:2010.01533 2020.
[50] Wang. T., Zeng, L., Dong, W., Yang, Q., Yu, Y., and Zhang, C. Context-aware sparse deep coordination graphs. arXiv preprint arXiv:2106.028 02886, 2021.
[51] Xu, H.. Luo, D., and Carin, L. Scalable gromov wasserstein learning for graph partitioning and matching. Advances in neural information processing systems, 32, 2019.
[52] Xu, Z., Lyu, Y., Pan, Q., Hu, J., Zhao, C., and Liu, S. Multi-vehicle flocking control with deep deterministic policy gradient method. In International Conference on Control and Automation (ICCA), 2018.
[53] Zhou, Z., Fu, W., Zhang. B., and Wu, Y. Continuously discovering novel strategies via reward- switching policy optimization. arXiv preprint arXiv:2204.0m 022246, 2022.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes].
(b) Did you describe the limitations of your work? [Yes] See Sec. 6.1
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See
Sec. 6.2
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes].
13

---

2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes].
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix A.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL.)? [Yes] We have opened the source code.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they chosen)? [Yes]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work existing assets, did you cite the creators? [Yes].
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're using/curating? [Yes].
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A].
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A].
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A].
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A].
14


Reviews:
[{"review_id": "u28Klj0ZQE", "reviewer": "Reviewer_tpzu", "summary": "\nThis work proposes a novel unsupervised reward labeling method called SPD, which rewards a population of agents when they have a relationship graph (synergy patten graph) that different to other populations. The \n\nConcretely, this work first builds \"synergy pattern graph\" of a given population and then uses the SPG discrepancy between populations as the metric to encourage inter-agent diversity. \n\nExperiments show that the proposed method can (1) learn diverse synergy patterns and (2) improve the generalizability on downstream tasks.\n\nGenerally, I like this work. I will raise my score if the writing can be improved and more convincing evaluation results, both qualitatively and quantitatively, can be provided.\n\n\n# Update after responses\n\nI am happy to see the authors revise the paper to make it more clear. I raised my score.\n", "questions": "\n### Questions on experiments\n\n\nI saw StartCraft2 SMAC environment is supported in your code. Why don't put its result in the paper?\n\nIn Figure 2 (a), the d_sp is computed based on the Gromov-Wasserstein discrepancy between different populations. How you compute this for DIAYN and WURL? IIUC they only has one population. I think this figure is not convincing to stand for the claim \"SDP captures the relative relations of agents\" (line 338) and \"SPD can inspire agents to visit identifiable states while further encouraging agents to explore with other types of coordination policies\" (line 291). I expect more convincing evidence to show that after SPD pre-training the models already \"learns useful synergy patterns\" (line 338).\n\nCan you plot the test performance of SPD population while conducting the unsupervised learning? If we can see performance improvement then it shows that SPD can learn policy without reward at all!\n\n\n\n\n\n\n### Questions on method\n\nIf I understand correctly, there exists Z populations of policies and the population that actually involve in each episode is uniformly sampled from the pool of Z populations. Correct? \n**Is it possible that this is the reason why SPD is working? This is similar to league training and ensemble method, which have shown can improve generalization.**\nThis is an important question. Please point out existing exp result in the paper if I miss it.\n\nA question related to this is that do the Z populations really diverse? Figure 2 (a) shows the d_sp \n\n\n---\n\nCurrent method labels transitions with pseudo reward and stores them into replay buffer for QMIX training. Therefore the reward might be outdated in the process of training. Is it necessary to relabel those reward based on latest policies?\n\n\n---\n\n\nRelated to above question, is it possible to compute the proposed pseudo reward based on truncated episode? For example, to generalize your method to on-policy RL algorithm like independent PPO, the reward should be computed on-the-fly before the episode is terminated.\n\n\n\n### Other questions\n\n\nWhy the webpage is empty? If you don't prepare it, don't post it.\n\n---\n\nSome typos:\n\n* CSD paper has wrong citation format.\n* Algorithm 1 Line 14: Update d_gw according to Eq (6) as well as Eq (1).\n* Line 139: \"about how to [solving] the optimization problem\"\n* Line 244: \"which could solve such [a] assignment\"\n* Line 288: can add a reference to d_sp\n\n\n---\n\nI don't think Figure 1 is informative.\n\n---\n\nFigure 2 (a) and (b) are in quite different styles. And the legend of Fig2(b) is sketchy. This could be improved.\n\n---\n\nAppendix C figure 1 is good, but can be improved. Agents in different teams should have clear difference. For example, opponent, ball and guard should use different shape rather than circle. I actually prefer to watch video, but unfortunately you don't provide video nor webpage.\n\n---\n\nProposition 4.1 is boring. Maybe we can move it to appendix.\n", "limitations": "\n\nIn Appendix D, the authors describe the limitations. \n\nI think a limitation is that, supposing URL methods (including SPD) perform bad when simply deploying the learned models to the test tasks without further fine-tuning, how to make URL method works in a complete reward-free setting. Previous works in single-agent RL, like DIAYN, shows that we can learn policy without any reward. This also relates to the next limitation.\n\nThe second limitation is that, I think we can incorporate diversity encouraging technique in single-agent with the SPD. By doing this, we can improve the intra-agent diversity as well as inter-agent diversity.\n\n\n\n", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\n### Strengths\n\n* This work formulates the diversity between agents in the perspective of \"synergy pattern graph\". This formulation of inter-agent diversity is novel. It encourages the **diversity in relationship**, which stands higher than simply computing diversity based on agents within one group or computing diversity based on single-agent information.\n* The continuity and completeness of the writing is good. There are no obvious flaws and disconnected notations. \n* I am very happy to see that code is provided. The code is provided with detailed documents and function description. This is a very big plus. \n\n\n### Weaknesses\n\n* The evaluation results do not provide a full view on the effectiveness of the proposed method. See questions.\n* Writing clarity can be further improved since the notations are a bit overwhelmed. I think the terms like SPG, SPG batch, SPG element, Discrepancy of SP and so are messed. It would be better to simplify them if don't have enough space to clarify define and introduce them. Also, I expect to see a concrete form of reward in implementation section, rather than a notation that refers to another notation that refers to third notation.\n* Besides, the connection between paragraphs and sections is not smooth enough, which creates huge burden in understanding. A good idea is to draw an illustrative diagram showing the relationship between concepts (I don't think Figure 1 is informative.). \n \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "fSIreI3VbMa", "reviewer": "Reviewer_8Kca", "summary": "The paper presents a method for unsupervised multi-agent reinforcement learning which uses diversity bonuses as an intrinsic reward.  The SPD method rewards diversity between _synergy pattern graphs_, which measure the similarity of the full set of agents' behavior.  The paper argues that diversity as measured between these graphs can capture the dependencies between agents better than promoting diversity in the state space alone.  The paper demonstrates improved performance in the Google Research Football (GRF) benchmark.\n\n# Update after author response\n\nThank you for the well-considered responses and updated experiments.  The updated results provide a stronger support for the SPD method, and I have raised my score to reflect them.", "questions": "Related to my concern above, what do you expect the relationship between $d_{sp}$ and downstream task performance to be?  Did I misunderstand why it should be a good metric on its own?  My rating depends mostly on this point, because the approach seems promising and the results are good on one benchmark, but it could be possible to achieve these results with more straightforward diversity methods.  Arguments in the paper suggest reasons why we should expect DIAYN and WURL to perform worse, but there is no experiment to back this up.  Since this is a major claim of the paper, I'd like to see it supported.", "limitations": "The authors address the limitations and potential societal impact well in the appendix.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Originality\n - To the best of my knowledge, the SPD method is a novel approach that combines diversity-based unsupervised RL approaches with a graph-based representation of agent interactions.\n\n### Quality\n - The comparisons between SPD, DIAYN and WURL in section 5.1 use $d_{sp}$ as an evaluation metric, which seems incomplete.  Without establishing that $d_{sp}$ correlates with, say, better down-stream task generalization performance, it is difficult to be confident in conclusions drawn using it as a metric.  I would have liked to see these baselines (DIAYN and WURL) used in the experiments in section 5.2 as well.  Can we attribute the improved performance of SPD demonstrated in figure 3 to diversity bonuses in general, or specifically to the diversification of synergy patterns?\n\n### Clarity\n - Although the SPD method is complex, the authors do a good job describing the approach, including describing the necessary background for understanding SPD. \n - The discussion of the ablation experiments in section 5.1 and figure 2 is very light on details.  I am not sure what the reward scale is, what the precision on the solution means, and why these are relevant ablations to consider.\n - A diagram illustrating $G^{sp}$ and $d_{sp}$ could aid understanding, even though the descriptions are clear.\n\n### Significance\nThe significance of the approach is hard to judge given the current experiments.  The approach seems to make advances on the state of the art in CTDE MARL approaches on GRF, but the concerns raised in the Quality section of this review above make it hard to know what to attribute the performance to.  ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Zp_EbVpYHIV", "reviewer": "Reviewer_tFW2", "summary": "This paper proposes an unsupervised framework SPD to discover diverse policies for agents with no extrinsic reward. SPD uses synergy pattern graph to represent the joint policy for agents and discovers diversity policy by applying optimal transport. The experiments show that SPD outperforms some MARL algorithms in some environments. The contributions of this work are designing a new method to represent the joint policy for agents by considering other agents in MARL and proposing to explore skills by optimal transport. ", "questions": "\nQuestions:\n1. Why is CDS performance worse than QMIX?\n\n2. Why not compare with some other methods of URL on google football? Although these URL methods are not designed for the MARL algorithms, they are needed for comparison.\n\n\n\nSuggestions:\n\nI think the auther should discuss some works that are designed to encourage diversity [1] [2] [3]. \nFurthermore, I believe the baselines that are compared in this work are weak. Specifically, some MA exploration works are not considered, and the baseline with the best performance in the experiments (i.e., football game) is QMIX. The authors need to consider some effective MA exploration works [1].\nIn addition, the experiments do not compare URL methods on google football and more URL methods should be taken into consideration, e.g., [4] [5].\nFinally, SPD is compared on some environments and more environments need to be considered, such as SMAC, MAMUJOCO.\nFor example, on some SMAC or on Google football environments used by CDS. Thus a more comprehensive experiments could significantly improve the paper.\n\n\n[1]: Zhou Z, Fu W, Zhang B, et al. Continuously Discovering Novel Strategies via Reward-Switching Policy Optimization[J]. arXiv preprint arXiv:2204.02246, 2022.\n\n[2]: Parker-Holder J, Pacchiano A, Choromanski K M, et al. Effective diversity in population based reinforcement learning[J]. Advances in Neural Information Processing Systems, 2020, 33: 18050-18062.\n\n[3]: Lupu A, Cui B, Hu H, et al. Trajectory diversity for zero-shot coordination[C]//International Conference on Machine Learning. PMLR, 2021: 7204-7213.\n\n[4]: Lee L, Eysenbach B, Parisotto E, et al. Efficient exploration via state marginal matching[J]. arXiv preprint arXiv:1906.05274, 2019.\n\n[5]: Liu H, Abbeel P. Aps: Active pretraining with successor features[C]//International Conference on Machine Learning. PMLR, 2021: 6736-6747.", "limitations": "Limitations should be discussed more adequately in the main body of the paper. Societal impact is likely minimal.", "rating": 4, "confidence": 4, "soundness": 1, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. This work provides an interesting and novel idea on the use of graphs to represent the joint policy for MARL.\n\n2. The paper is well written.\n\nWeaknesses:\n\n1. There is no support for the conclusion that SPD is better than other URL methods in terms of performance.\n\n2. Some standard benchmarks used in the MARL community need to be considered. Some of the results are very confusing to me, such as CDS does not work at all. \n\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "41ubI2mpq4w", "reviewer": "Reviewer_meoo", "summary": "The authors proposed a MARL algorithm to learn generic coordination policies for agents with no extrinsic reward called Synergy Pattern Diversifying Oriented Unsupervised MARL (SPD). They utilized a graph representing the relationships of agents at each time step called Synergy Pattern Graph (SPG), and an episode-wise divergence measurement to approximate the discrepancy of synergy patterns. Results showed the capacity of SPD to acquire meaningful coordination policies, such as maintaining specific formations in Multi-Agent Particle Environment and pass-and-shoot in Google Research Football. Furthermore, they demonstrated that the same instructive pretrained policy’s parameters can serve as a good initialization for a series of downstream tasks’ policies, achieving higher data efficiency and outperforming state-of-the-art approaches in Google Research Football.", "questions": "* L 84: no extra cost?\n* L 244: utilize/an assignment?\n* Algorithm 1 L15: Is eq. (2) correctly eq. (3)?\n* The performances of CDS (Li et al. 2021, NeurIPS) in Figure 3 may be worse than expected (in the paper, CDS outperformed QMIX and QPLEX). I previously ran their code and it worked well. I know the experimental condition was different, but I want to know the reason (were there no code and hyperparameters for CDS?).\n* There was no video at https://sites.google.com/view/spd-umarl.\n* L328-329: “To avoid the effect of randomness, we repeat the visualization for 10 times for each skill.” It was not clear to me. What did the authors do?\n* Appendix L83: The results show that none of the URL approaches, including our method SPD, achieve more than 75% on DSR. The values in Fig. 2 a seem to be 60%. Why did the authors mention 75%?\n", "limitations": "The limitations and potential negative societal impact were described in Appendices D and E, respectively.\n", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The strength of this paper is as follows:\n* The proposed unsupervised MARL algorithm seems to be original, and they used the synergy graph to train team skills without rewards from the environment, which brings the agents good generalization ability in downstream tasks, and takes no extra cost in execution. \n* The experimental results demonstrate that SPD achieves better performance in MARL compared to conventional unsupervised RL approaches and shows great potential to learn synergy patterns with generalizability for downstream tasks.\n\nThe weakness of this paper is as follows:\n* The presentation was sometimes unclear (please see below)\n* The experiment descriptions were sometimes unclear (please see below)\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept