Coordination Scheme Probing for Generalizable Multi-Agent Reinforcement Learning
Authors: Hao Ding
Chengxing Jia
Cong Guan
Feng Chen
Lei Yuan
Zongzhang Zhang
Yang Yu
Venue: Submitted to ICLR 2023 (2023)
Keywords: reinforcement learning
multi-agent reinforcement learning
agent modeling

Abstract: Coordinating with previously unknown teammates without joint learning is a crucial need for real-world multi-agent applications, such as human-AI interaction. An active research topic on this problem is ad hoc teamwork, which improves agents' coordination ability in zero-shot settings. However, previous works can only solve the problem of a single agent's coordination with different teams, which is not in line with arbitrary group-to-group coordination in complex multi-agent scenarios. Moreover, they commonly suffer from limited adaptation ability within an episode in a zero-shot setting. To address these problems, we introduce the Coordination Scheme Probing (CSP) approach that applies a disentangled scheme probing module to represent and classify the newly arrived teammates beforehand with limited pre-collected episodic data and makes multi-agent control accordingly. To achieve generalization, CSP learns a meta-policy with multiple sub-policies that follow distinguished coordination schemes in an end-to-end fashion and automatically reuses it to coordinate with unseen teammates. Empirically, we show that the proposed method achieves remarkable performance compared to existing ad hoc teamwork and policy generalization methods in various multi-agent cooperative scenarios.

Under review as a conference paper at ICLR 2023
COORDINATION SCHEME PROBING FOR GENERALIZ- ABLE MULTI- AGENT REINFORCEMENT LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Coordinating with previously unknown teammates without joint learning is a crucial need for real-world multi-agent applications, such as human-Al interaction. An active research topic on this problem is ad hoc teamwork, which improves agents' coordination ability in zero-shot settings. However, previous works can only solve the problem of single agent's coordination with different teams, which is not in line with arbitrary group-to-group coordination in complex multi- agent scenarios. Moreover, they commonly suffer from limited adaptation ability within an episode in zero-shot setting. To address these problems, we introduce the Coordination Scheme Probing (CSP) approach that applies disentangled scheme probing module to represent and classify the newly arrived teammates beforehand with limited pre-collected episodic data and makes multi-agent control accordingly. To achieve generalization, CSP learns a meta-policy with multiple sub- policies that follow distinguished coordination schemes in an end-to-end fashion and automatically reuses it to coordinate with unseen teammates, Empirically, we show that the proposed method achieves remarkable performance compared existing ad hoc teamwork and policy generalization methods in various multi-agent cooperative scenarios.
INTRODUCTION
Multi-Agen Reinforcement Learning (MARL) (Gronauer & Diepold, 2021) holds promise in numer- ous cooperative domains, including resource management (Xi et al., 2018), traffic signal control (Du et al., 2021), and autonomous vehicles (Zhou al., 2020). number of methods (Lowe al., 2017; Wang et al., 2020b; Papoudakis et al., 2019; Christianos et al., 2021) have been proposed to deal with joint policy learning and scalability issues. However, previous works commonly assume fixed team composition, where agents only need to coordinate with training partners and do not consider generalization. Such a process not in line with real-world applications that require agents to cooperate with unknown teammates whose coordination schemes may not be explicitly available. When coordinating with distributed teammates, co-trained agents may fail (Gu et al., 2022).
Another research domain dedicated to this need is ad hoc teamwork (Stone al., 2010), which stands at single agent's perspective to adapt to different teams in a zero-shot fashion. However, current methods exist three significant limitations: (1) The differences between teammates could be very subtle and lie in only few critical decisions. In this case, zero-shot coordination is not always feasible. As shown in the example in Fig. teammate's behaviors indistinguishable before the final critical action. (2) The information for identifying different teams is collected by the same policy that aims to maximize coordination performance. Thus, the ixplorationnexploiineee will cause adverse effects on both sides. (3) Ad hoc teamwork stands at single agent's 's perspective, which cannot deal with arbitrary group-to-group generalizations in complex multi-agent scenarios.
dilemma
To overcome these limits and achieve generalizable coordination, we propose a multi-agent learning framework called Coordination Scheme Probing (CSP). Instead of doing zero-shot coordination, CSP tries to capture the unknown teammates' coordination scheme beforehand with limited pre- collected episodic data. Concretely, we start with generating a set of teams with high performance and diversified behaviors to discover different solutions to the task. After that, the scheme probing module learns to interact with these teams to reveal their behaviors and represents their policies with dynamics reconstruction (Hospedales al., 2021) at the team level. Finally, discover coordination

---

Under review as a conference paper at ICLR 2023
Training phase
Zero-shot coordination
teammates
000
Indistinguishable segment
should go Up!
00OS
Targets
What should I do?
ad hoc agent
should go Down!
Figure I: An example from Overcooked (Carroll et al., 2019a), where the chef in the blue hat needs to cooperate with chefs in other colors. Different chefs put the dishes in different positions after they are done cooking. For example, during training, the chefs in the green and orange hats put their dishes in the red and blue pentagrams their last action, respectively. When chef in the pink hat comes, how should the chef the blue hat work with him? Since the first four actions for different chefs are indistigguisable, how to detect his type and coordinate with him challenging.
schemes as clusters of the representations and train a multimodal meta-polics to adapt to them, with each sub-policy dedicated to unique coordination scheme.
The whole learning framework of CSP learns multiple coordination schemes from a given task in end-to-end fashion and automatically reuses the most suitable scheme recognized by the scheme probing module to coordinate with unknown partners. To validate our method, we conducted experiments on four challenging multi-agent cooperative scenarios and found that CSP achieves more effective and robust generalization to unknown teammates compared to various baselines. Our visual analysis further confirms that CSP acquires multiple coordination schemes that are clearly distinguishable and can be precisely recognized. Meanwhile, our ablations show the necessity of probing unknown teammates in advance well as using a multimodal policy for adaptation.
2 RELATED WORK
Reinforvement Learning (MARL). Fully cooperative MARL methods (Foerster et al., 2018) mainly focus on deploying fixed team with centralized training and decentralized execution (CTDE) setting (Oliehoek al., 2008). Value factorization methods (Sunehag et al., 2018; 8; Rashid et al., 2018; Wang et al., 2020a) are adopted widely in the CTDE process to solve the instability of teammates in the training process. Our work also utilizes the CTDE setting to learn policies collaborating with others. However, such learning process may converge not coordinate well with unseen teammates trained elsewhere. To deal with the issue, Tang et al. optimal policy by reward randomization.
Multi-Agent
fixed modal and may
(2021) propose method that could find hard-to-seane In game-theoretic methods, PSRO (Lanctot et al., 2017) aims at tackling the overfitting problem by learning meta-strategies, and a-PSRO (Muller et al., 2020) further utilizes o-Rank as alternative for Nash solver to avoid equilibrium selection issues and improve efficiency. In this work, we borrow the idea of breaking local optima to mine diverse coordination behaviors from the environment, instead of training single optimal policy.
Ad Hoe Teamwork. Ad hoc teamwork aims learn a single autonomous agent that cooperates well with other agents without pre-coordination (Stone et al., 2010; Mirsky et al., 2022). Their methods include population based training (Strouse et al., 2021; Jaderberg et al., 2017; Carroll et al., 2019a; Charakorn et al., 2021) 1), Bayesian belief update (Barrett et al., 2017; Albrecht et al., 2016), experience recognition (Barrett al., 2017; Grover et al., 2018b; Chen et al., 2020), and planning (Bowling & McCracken, 2005; Ravula et al., 2019). A recent work ODITS (Gu et al., 2022) introduces an information based regularizer to automatically approximate the hidden of the global encoder with the local encoder. However, they are limited to leam single ad hoc agent and only makes zero-shot adaptation. We take step further to develop a framework for more complex ceam-to-team coordination under few-shot setting.
Policy Representation. is a well studied topic in multi-agent scenarios to anticipating others' behaviors and weaken the non-stationary issue (Albrecht & Stone, 2018). DRON (He et al., 2016)
2

---

Under review as a conference paper at ICLR 2023
uses modeling network to reconstruct the actions of opponents from full history. Grover al. (2018b) adopt the concept of interaction graph (Grover et al., 20) to lear a contrastive style representation with prepared policy class. DPIQN (Hong et al., 2018) learns "policy features" of other agents and incorporates them into the Q-network for better value estimation. LJAM (Papoudakis et al., 2021a) aims at estimating teammates' current actions and observations based on learning agent's local history alone. Inspired by dynamics- we use an architecture that directly reconstructs the policy-dynamics. of a team policy, instead of predicting their temporal behaviors, to get a compact and precise representation.
(Raileanu et al., 2020) in meta-learning,
BACKGROUND AND PROBLEM FORMALIZATION
Cooperative Task. We formalize the problem as a Dec-POMDP (Olichoek Amato, 2016) with a controllable group, defined as MM- = SN 1 {-,) S2 P. R, y; do. G²), where A = (1.....n.) n is the set of agents, S is the set of global states, O is agent i's observation space, A,; is agent i's action space, ? E [0. is the discount factor, and d, denotes the initial state distribution. At each timestep, agent E . acquires a local observation 0; E O, with observation function (2ss i) and chooses action 0₂ E AA; via individual policy म; (T)[T)). where TÜ denotes input history. The joint action a = (d1,.... an)) transitions the system to next global state 8 according to the transition function P(s' s, a), and all agents get shared reward range at test time, where G S N is the subset of controllable agents, and its complementary G contains uncontrollable teammates that G should adapt to. We denote join observation, action and policy for G as o² = (os). a = (az). π = (Tr)), i E G and the corresponding parts for G-1 are defined similarly. Thus, the (global) joint policy can be written as π (T²² ,
R(s, a). The group describes control
Coordination Scheme. We define this term to better describe generalization. Let I be the set of all joint policies with high coordination performance. Coordination scheme C = {cs} is defined partition of y Each coordination scheme is a set of joint policies, where nc, = 0, if + j and USec C 1ly. We assume that the coordination performance can be guaranteed all the agents are in the same coordination scheme, even if they have minor differences. Otherwise, no such guarantee exists generally. Intuitively, C determined by the coordination task itself, different elements in which reflect different unique high-level joint behaviors. We may use words like "follows" or "is under" in this paper to describe the same thing as π E c for ease in expression.
Problem Formalization. Our aim is to control G² to coordinate with G-1 under any co- ordination scheme e E C. We assume that G-1 has no adaptation ability and will stick to fixed scheme no matter what G behaves. With little abuse of notations, т E c to denote π E c and ा -- is its slice for G-1. Formally, the optimal pol- icy n parameterized by 0 for G is to maximize the discounted cumulative reward: Ø* P.d... P,,
use
where T++1 is the shared reward at timestep 1 and H is the episode length. Since we do not have direct access to the true scheme set C, create set of diverse policies Irrain and directly sample - from it as a surrogate of the two-factor sampling, and rewrite the objective as: 0"
arg max, Ex 1EC,CE ElE 7fre+1 (a',a-))~~ (TT), π "),, P.
arg max, F. Ell Σドー >'r++1 (a --1) ~ (mb; π -1), , P, do} Another diverse set T is created to evaluate the generalization performance.
4 METHOD
This section describes how the CSP framework addresses the generalizable coordination problem in an end-to-end manner (Fig. 2). When given cooperative task, CSP learns with three stages: (1) It generates a diverse population of team policies to discover multiple feasible coordination schemes. (2) It trains scheme probing module efficiently represent different teams by self-supervised team-dynamics reconstruction. (3) It discovers the underlying coordination schemes by clustering the representations and trains multimodal meta-policy adapt them.
3

---

Under review as a conference paper at ICLR 2023
Diverse Teom Population
Sample
SP Policy
Probe
Encoder
Represont
Coordination Scheme Embedding Space
i-meens
Meto policy
Releforrement learning
Clossijy
Diversity Objective
Self- supervised learning
Outer
Represent
loop
Ricoestru
Scheme Probing
TXg
Module
JEJ
stops
Somple
loop
Env
Team pollcy
population
Env
Stage 1: Diverse Team Pooulation
Stage Scheme Probing Module
Stage Multimddal Coordination Policy
Figure 2: Overall framework of CSP, where SP is short for "scheme probing".
Algorithm CSP: Brief Training Process
1: Initialize training population I = - n scheme probing module (Ee, De), Tap
and multimodal meta-policy Timeta (T],,.., Tk
2: Train each team policy π'' E IItarin for quality and diversity.
>> (Fig. 2, Stage 1)
Train (E,, Da) to represent teammates, and Tap to probe teammates.
>> (Fig. 2, Stage 2)
4: Represent teams in Ierain and discover coordination schemes as k clusters.
>> (Fig. 2, Stage 3)
5: Train Tmeta for generalization by each sub-policy acquiring unique scheme.
6: return Tueta
4.1 DIVERSE TEAM POPULATION
We first need to use a set diverse team policies to simulate the coordination schemes required for the training and evaluation phases. Instead of letting each team acquire diversity with different initial- izations (Carroll et al., 2019a; Strouse et al., 2021) alone, we propose the Soft- Value Diversity (SVD) objective and alternate optimization process to gain diversity explicitly. We maintain population with M independent multi-agent teams, each learning with an MARL method (VDN (Sunehag et al., 2018) in this work). While each team performs independent "inner loop" learning, the population periodically performs centralized "outer loop" updates for all teams to maximize SVD:
((.D(( = Er,a Σ [ID(T. a)(TT.)-DDpp (I(TTa))i -
where 8, denotes the Q-network's 's parameters for the i-th team's 's policy, T and denote indi- exp (Qo,
vidual observation and action, a) Earea exp (T,,)))))) is the normalized value esti- mation obtained by performing the Boltzmann softmax operator (Asadi & Littman, 2017), and D(T,a) a) 1 Σ M D,(T, a) the average observation-action value estimation for all policies in the population II. We use the Monte Carlo method to estimate the expectation based on recent collected trajectories in the replay buffer. In this stage, agents (i.e., N G¹ UG!! 1) for each team are trained jointly, but we only store -- corresponding to G for further use.
M
Maximizing SVD encourages teams within the population to have different value estimations of each observation-actio pair by increasing the gap between their current values and the mean. This diversity in value estimation reflects various local optima caused by different joint decisions in multi-agent scenarios, where the same action will have different outcomes when teammates' actions change. The "inner" and "outer" loops in the framework are designed to improve individual team performance and diversity among different teams. We set hyper- parameter to control the learning frequency of these two loops, which is a trade-off off between the quality and diversity policies the population. We obtain Turain and II independently via this process.
4

---

Under review as a conference paper at ICLR 2023
4.2 SCHEME PROBING MODULE
After having a diverse team population Irain. we train the scheme probing module upon it to efficiently reveal and represent different teams' coordinating policies. It has two main parts. One is the scheme probing policy spp which interacts with team for an entire episode and gathers the trajectory 7ep = {&,, ) that reveals the current teammates' coordination scheme. The other is the team-dynamies autoencoder (Ee; Dc), which learns representation 2, of team policies based on Tap in self-supervised manner. Start from here, we only train policies for G and let G-1 switch within Iraiin The teammates can thus be viewed as a non-stationary part of the environment.
Team- -eam-dynamics Autoencoder. The encoder E, is parameterized as an LSTM (Hochreiter & Schmid- huber, 1997) which takes as input Tap and outputs an embedding vector Ze. The decoder De is feed-forward network that takes as input both 2g. and current state 8t, and predicts teammates' next joint action distribution a, Formally,
Ze = Ee (Tapi Oo), à = Do St, Rei 6e).
(2)
The parameters 0g and &e are jointly optimized minimize the cross entropy loss (i.e., reconstruction eгror in Fig. 2) of a, and a, averaged over the entire trajectory Tspi
Lio 1 Σ Cprea(t)
1 Σ log De(a;" St. Φc).
We call this approach team- cram-dynamicss reconstruction for the following reasons. Firstly. D. receives no historical information, so cannot infer a team's behaviors based on the temporal ordering of states and joint actions. In this case, F,, is forced to embed information about this team's 's dynamícs into 2, to make a good reconstruction. Additionally, since 8, already input of De. F.c has no motive to embed any information about states. Thus, the embedding contains only information about the policy and not the environment, making a compressed and precise representation of a team.
Scheme Probing Policy. Instead of collecting information passively, we expect Tap to actively guide teammates' behaviors and reveal their coordination schemes. To this end, we introduce the reconstruction loss above each timestep intrinsic reward for Tap, which is added to the original environmental reward ruu:
rt + (t)red
where a is adjustable hyperparameter to achieve a trade-off between coordination performance and information gain through probing. This additional term encourages Te to explore states with the large behavioral uncertainty across different kinds of teammates, which is considered helpful in determining their identities and representing their coordination policies.
4.3 MULTIMODAL COORDINATION POLICY
When the scheme probing module is well trained, is fixed and used guide downstream scheme- specific control. Common context-based methods (Hausman et al., 2018; Yang et al., 2020) use embeddings augmentation of the agent's input space. However, in scenarios of coordination generalization, the behaviors under different coordination schemes can vary greatly and conflict with each other. Such processes require single network acquire multimodal behaviors as the context changes, which increases learning complexity and instability. As a comparison, we use embeddings to automatically group similar team policies discover different schemes and solve each distinct group with an independent sub-policy to avoid conflicts.
Scheme Discovery. We first use the learned scheme probing module to probe and represent all teams in Traain N times, which generates embedding set Z of size | = NM. Repeating it N times is to get the distribution of a team's 's representation rather than single sample point when the environment and policy stochastic. Then perform k-means clustering based Euclidean distances Z to get & clusters with centers μ = .p....... ...). We use the Silhouette method (Rousseeuw, 1987) to automatically determine the most suitable k and details can be found in App. A.2.
These clusters reflect the natural structure of coordination schemes, as behaviors under the same scheme should not vary too much to ensure coordination. The number of clusters & will be approxi- mately equal to the number of environmental coordination schemes CC) if I already covers all possible schemes. So enlarging the size of Thrain will not infinitely increase the learning complexity.
5

---

Under review as a conference paper at ICLR 2023
Meta-Policy Learning. We initialize multimodal meta-poligg with & sub-policies, where each sub-policy takes local observation history as input:
(5) During training or deploying, when confronted with a team, we first let the scheme probing policy Tsp interact with it to get trajectory Tap and get the representation 2e ET(p)) Then, we classify the team into one of the k classes (discovered schemes) according to the distance of &e and all cluster centers μe. Once we have done the classification, we choose the corresponding sub-policy to do the rest of the control. Formally,
T meta = (a -=)
Ta (a) T, Tap) n.. (a [) where i' = arg min; [[ -4 mill2-
(6)
This structural design takes advantage of multimodality to be highly expressive, allowing end-to- end learning of several vastly distinct coordination schemes simultaneously without affecting each
other. Moreover, each sub-policy (a(a)) only needs to acquire unique and stationary coordination scheme. Compared to common context-based methods that use single policy т (a. T, 2) to acquire all schemes, it reduces learning complexity and improves stability.
EXPERIMENTS
In the section, we design experiments to answer the following questions: (1) How well does CSP perform when generalizing to unknown partners in multiple complex scenarios (Sec. 5.1)? (2) Can the proposed scheme probing process get meaningful and distinguishable representations (Sec. 5.2)? (3) Does the team population really have multiple coordination schemes (Sec. 5.3)? (4) What the impact of each component of CSP (Sec. 5.4)?
We select four multi-agent cooperative environments with six scenarios as benchmarks: Level-based Foraging (LBF) (Papoudakis et al., 2021b) needs agents to find food randomly distributed on the map and eat it together. Predator-Prey (PP) (Böhmer et al., 2020) is a more challenging version of LBF that allows each prey move randomly at each timestep. Overcooked (Strouse et al., 2021) requires two players coordinate to cook and deliver food to target locations. We use standard layout Coordination Ring and modified layout Forced Coordination Hard that enhances penalties for miscoordination. SMAC (Samvelyan et al., 2019) is a commonly used MARL benchmark that focuses on coordinated micromanagement. We use a standard map /c3s5z and customized map Fork specially designed with multiple coordination schemes.
Six wate-of-the-art approaches from three related fields are chosen for comparison. (1) Meta- learning: PEARL (Rakelly et al., 2019) uses recently collected context to infer probabilistic variable describing the task. (2) Policy representation: LIAM (Papoudakis et al., 202 1a) is an MARL method that predicts tcammates' current behaviors based on local observation history, and FIAM (Papoudakis et al., 2021a) enhances LIAM by replacing local observations with global states. (3) Ad hoc teamwork: PBT (Carroll et al.,, 2019b) uses domain randomization to train an ad hoc agent with a population of pre-trained partners. FCP (Strouse et al., 2021) draws on the practice of FSP (Heinrich et al., 2015) in games by constructing training sets with teammates' historical checkpoints. ODITS (Gu al., 2022) applies a centralized "teamwork situation encoder" for end-to-end learning.
Notice that PEARI., PBT, FCP, and ODITS originally designed for single-agent settings. To make them compatible with multi-agent scenarios, we implement them upon an MARL framework VDN (Sunchag et al., 2018) that follows the CTDE paradigm to learn team policies for G1. Other multi-agent methods (i.c., CSP, LIAM, and FIAM) also choose VDN as their base MARL framework for a fair comparison. and only did self-play during training, while PBT, FCP and ODITS used several teams with different random seeds and initializations to construct training populations, which may be unstable and difficult to compare. To standardize comparison, we reuse the same Iraiin generated in CSP's stage 1 for all baselines, thus reducing the chance of outcome due to randomness of population generation. More details of each scenario and bascline are shown in App. B-C.
addition, the original versions of LIAM and FIAM did not use populations
5.1 EVALUATION OF PERFORMANCE
We first investigate how CSP and other baselines perform when coordinated with unknown diverse teammates. Fig. 3 shows the average performance of coordinating with all teams in Neyal during

---

Under review as a conference paper at ICLR 2023
Overcooked Coord.
0.1
6-4
4.5
0.2
10
1.5
0.0
Smesteps
Smestepe
Ovancodked Coard. Ring
SMAC 163852
12
Tost Rosuum Mean
4
100
0.4
smesteps
CSP (Ours)
LIAM
FIAM
PBT
FCP
ODITS
PEARL
Figure 3: Mean generalization performance on eeval of all methods.
training. Since CSP always collects a probing trajectory Tap before adapted coordination, we use the average score of the two trajectories as CSP's performance metric for fair comparisons. All experiments are done with five random sceds, and all curves are marked with 95% confidence intervals in the shaded area.
In general, CSP outperforms PEARL, PBT, FCP, and LIAM consistently and is better or at least comparable to FIAM and ODITS according to the tasks. In LBF, where each agent has strictly limited observation range, FIAM has a clear advantage because it utilizes global information at each timestep help make decisions. The comparable result of CSP shows that it is possible achieve near-optimal control with pre-identified coordination scheme information alone, eliminating the need for global states throughout the entire episode. In PP, Overcooked, and SMAC Fork, the cooperative tasks are challenging and contain several vastly different coordination schemes, which require the coordinator change its behaviors aggressively and precisely. All baselines here have a clear gap with CSP. We believe the superiority comes from the fact that CSP uses multimodality to isolate the expression of different coordination schemes to avoid mutual interference. a comparison, in SMAC lc3s5z, CSP and all baselines converge to roughly equivalent performance. The reason that without a specially designed symmetry like Fork, the optimal policy this task is reflected in focusing fire on the enemy and retreating when its health is low. The optimal decision under each state is sure with no ambiguity of different coordination schemes, and all methods acquire this optimal policy after training long enough. Although PEARL uses additional context data, it performs worse than CSP. We believe is because PEARL learns to encode context into a meaningful variable in end-to-end manner directly maximize cumulative reward, which is relatively inefficient. It is worth noting that CSP trains A sub-policies but still has comparable or even better sample efficiency baselines, verifying that isolating different schemes stabilizes training and avoids conflict schemes from affecting each other.
5.2 SCHEME REPRESENTATION ON SMAC
A meaningful and distinguishable representation of coordination schemes is the basis of CSP's adaptation ability. To demonstrate this, we visualize the embeddings of our scheme probing module with experiments on SMAC Fork (Fig. 4). We let our scheme probing module interact with all teams II IItain Ieval for 64 episodes. One of the baselines, LIAM, which does agent modeling at every timestep, also runs in parallel as a comparison.
Let's first make a brief understanding of the Fork task. There are two symmetrical points at Up and Down sides guarded by several enemies. If all the teammates choose to attack the same point, they will have enough force to eliminate all the enemies there and get a high reward. Otherwise, neither point will have firepower advantage, and all the teammates will be destroyed and fail. Therefore, we can roughly claim that there are two basic coordination schemes C' {Up, Down) in this task. Screenshots at timesteps 10 and 30 (Fig. 4a-b) indicate the early and middle stages of one episode.
Asynchronous decision makings occur in (a) and (b) for G and G respectively to select a direction (Up Down) attack, and coordination succeeds if their choices the same. Since G-1 may be
7

---

Under review as a conference paper at ICLR 2023
Different choice direetion
Group (scammate) moves right beginning game
Upr2
(c) sNN emboddingg 20
(LIAM at 10)
e-SNE emboedins (CSP)
(o) Fork at timestep 10
LIAM
(b) Fork at timestep 30
USEE embeddings (LIAM 30)
Reconstruction
Figure 4: (a)() SMAC Fork at timesteps 10 and 30, when G (left) and G (right) make decisions respectively to attack enemies at point Up (red arrow) or Down (blue arrow). (c)(d) LIAM's embeddings of different teams at timesteps 10 and 30. (e) CSP's embeddings of different teams. (f)
CSP and LIAM's mean reconstruction accuracy of G-1's joint action a, throughout one episode.
controlled by various policies in II, which will make different decisions, G has make the right choice based on the partners it meets.
The t-SNE projection of CSP's scheme embeddings is shown in Fig. 4e, where different colors represent different teams in IT (named by their scheme observed) and each point represents single run. There are two main phenomenons: (1) Each color forms relatively compact cluster. (2) Clusters with similar colors (lighter or darker) tend to be close together, while deeper and lighter colors are farther apart. The former indicates that CSP's representations are highly consistent with low variance, which is beneficial for stabilizing downstream MARL learning. The latter shows that the embedding space holds semantically meaningful information, where teams with similar coordination schemes can be packed together. As comparison, LIAM's embeddings at timesteps 10 and 30 are shown in Fig. 4c-d. We can observe that different teams are mixed up at the early stage, and a few local clusters emerge time goes by but still cannot distinguish well between teams. As illustrated in the screenshots (white arrow), G will always move right in the first few dozen steps, so the trajectories of differrnt teams during this period are similar and hold insufficient information. is impossible for LIAM to distinguish teams based on it, let alone make the right choice in the beginning.
Fig. 4f presents the mean reconstruction accuracy of G-1's joint actions throughout one episode. We can observe that CSP has consistently higher accuracy than LIAM, especially at timesteps close to 30. As described above, the observation segment before is not informative enough, in which case LIAM will fail to predict teammate behaviors when sudden uncertainty occurs. By contrast, CSP has a comprehensive view of the teammates coordinates with after the probing phase in advance, so can fully guarantee its scheme prediction throughout the coordination phase. More results other benchmarks are shown in App. D.I.
5.3 SCHEME DIVERSITY
To verify populations generated in stage 1 do hold multiple coordination schemes, we perform Cross- Play (Hu et al., 2020) experiments on Overcooked's Coordination Ring and SMAC Fork (Fig. Sa). Teams in II I UTeaal are paired to play the role of G¹ and G for all combinations.
Firstly, we can find that values on the diagonal from the top left to the bottom right corner are generally larger than others. This indicates that each team coordinates well with itself, as they always in the same coordination scheme. As comparison, the relatively lower performance of other points indicates the inability coordinate across different schemes. Interestingly, the performance
8

---

Under review as a conference paper at ICLR 2023
Overcooked Coord. Ring
SMAC Fork
200
CDP
COPAC
+3
27
20
67
66
22
Noma Qnd Peeforaace
Aggn CoNuy
15
47
Cooun
21
66
16
17
42
11
<Z
11
Group
Agent Group
80
(a) Cross-Play performance full population II, normalized to [0, 100).
(b) Ablations.
Figure 5: (a) The scores of cross- cross-play on the Overcooked Coordination Ring and SMAC Fork benchmarks. (b) Final generalization performance of CSP and ablations for each component.
on SMAC Fork shows that it has two basic coordination schemes, where each team coordinate with exactly half of the teams in II that have the same coordination scheme. This phenomenon is aligned with our understanding of the task, described above in Sec. 5.2. More results on other benchmarks are provided in App. D.2.
5.4 ABLATION STUDY
We perform ablations on SMAC and Overcooked to demonstrate the importance of CSP's different components: UNI removes multimodality and only has a single sub-policy x(7); POP(z) uses single context-based policy ((,, z) instead of sub-policies; CSP(z) extends each sub-policy to be (T, 2); SP does not Ilarain and learns with self-play alone. We report the mean generalization performance with Leval and eτror bars indicating the 95% confidence interval as shown in Fig. 5b.
Firstly, we can observe that SP generally does the worst and has large variance. This means that without being exposed to diverse partners during training, the policy can only find a single coordination scheme and is hard to generalize. UNI has lower variance but still performs poorly, which indicates that using domain randomization helps make the policy robust to partner changes, but it cannot be specialized to each scheme without a specially designed adaptability module. The relatively lower performance of POP(z) compared to CSP confirms our claim earlier that it is difficult make adaptations within a single network based on different scheme embedding. In complex multi- agent scenarios, each coordination scheme can imply highly different and even opposite behaviors, where using multiple sub-poli policiilcce helps to isolate these schemes and makes each consistent. Finally, CSP(z) does not outperform the original version. This phenomenon shows that our scheme grouping process already fully uses the information contained the embedding. Further use of as additional input longer results in a boost but may increase learning difficulty.
6 CLOSING REMARKS
To achieve generalizable coordination in complex multi-agent scenarios and address limitations of ad hoc teamwork, this paper considers learning a coordination scheme probing module for teammates recognition and meta-policy consisting of multiple sub-policies for few-shot coordination with unseen diverse teams. With the help of this probing module, we can reduce few-shot coordination to multi-task RL problem by clustering the representation space. A multimodal policy is then end-to-end trained to solve it directly. Sufficient experiments compared against strong baselines on various benchmarks validate the effectiveness of our proposed method. We point out limitations and interesting future work: (1) Co-evolution of the population would be more general interaction setting, such Quality Diversity (Parker-Holder et al., 2020). (2) Effective knowledge transfer between submodules, such as Soft Modularization (Yang et al., 2020). could be considered to improve sample efficiency. Finally, instead of training alongside artificial agents, we also hope study the human-in -itta----the-ooop setting to adapt to people's dynamic needs and preferences.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Stefano V Albrecht and Peter Stone. Autonomous agents modelling other agents: A comprehensive survey and open problems. AAAI Conference on Artificial Intelligence (AAAI), 2018.
Stefano V Albrecht, Jacob W Crandall, and Subramanian Ramamoorthy, Belief and truth in hypothe- sised behaviours. AAAI Conference Artificial Intelligence (AAAI), 2016.
Kavosh Asadi and Michael Littman. An alternative softmax operator for reinforcement learning. In International Conference on Machine Learning (ICML), 2017.
Samuel Barrett, Avi Rosenfeld, Sarit Kraus, and Peter Stone. Making friends on the fly: Cooperating with new teammates. AAAI Conference on Artificial Intelligence (AAAT), 2017.
Wendelin Böhmer, Vitaly Kurin, and Shimon Whiteson. Deep coordination graphs. In International Conference Machine Learning (ICML), 2020.
Michael H. Bowling and Peter McCracken. Coordination and adaptation in impromptu teams. In AAAI Conference on Artificial Intelligence (AAAI), 2005.
Micah Carroll, Rohin Shah, Mark K. Ho, Tom Griffiths, Sanjit A. Seshia, Picter Abbeel, and Anca D. Dragan. On the utility of learning about humans for human-Al coordination. In Advances in Neural Information Processing Systems (NeurIPS), 2019a.
Micah Carroll, Rohin Shah, Mark K. Ho, Tom Griffiths, Sanjit A. Seshia, Pieter Abbeel, and Anca D. Dragan. On the utility of learning about humans for human-ai coordination. In Advances in Neural Information Processing Systems (NeurIPS). 2019b.
Rujikorn Charakorn, Poramate Manoonpong, and Nat Dilokthanakul. Learning to cooperate with unseen agent via meta-reinforcement learning. arXiv preprint arXiv:2111.034311 2021.
Shuo Chen, Ewa Andrejezuk, Zhiguang Cao, and Jie Zhang. Aateam: Achieving the ad hoc teamwork by employing the attention mechanism. In AAAI Conference on Artificial Intelligence (AAAI), 2020.
Filippos Christianos, Georgios Papoudakis, Muhammad A Rahman, and Stefano V Albrecht. Scaling multi-agent reinforcement learning with selective parameter sharing. In International Conference on Machine Learning (ICML), 2021.
Xin Du, Jiahai Wang, Siyuan Chen, and Zhiyue Liu. Multi-agent deep reinforcement learning with spatio-temporal feature fusion for traffic signal control. In European Conference on Machine Learning (ECML), 2021.
Jakob N. Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson. Counterfactual multi-agent policy gradients. In AAAI Conference on Artificial Intelligence (AAAI), 2018.
Sven Gronauer and Klaus Diepold. Multi-agent deep reinforcement learning: A survey. AAAI Conference on Artificial Intelligence (AAAI), 2021.
Aditya Grover, Maruan Al-Shedivat, Jayesh K. Gupta, Yuri Burda, and Harrison Edwards. Evaluating generalization in multiagent systems using agent-interaction graphs. In International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 1944-1946, 201 8a.
Aditya Grover, Maruan Al-Shedivat, Jayesh K. Gupta, Yuri Burda, and Harrison Edwards. Learning policy representations in multiagent systems. In International Conference on Machine Learning (ICML), pp. 1797-1806. 2018b.
Pengjie Gu, Mengchen Zhao, Jianye Hao, and An. Online hoc teamwork under partial observability. In International Conference Learning Representations (ICIR), 2022.
Karol Hausman, Jost Tobias Springenberg, Ziyu Wang, Nicolas Heess, and Martin Riedmiller. Learning an embedding space for transferable robot skills. In International Conference on Learning Representations (ICIR), 2018.
10

---

Under review as a conference paper at ICLR 2023
He He, Jordan Boyd-Graber, Kevin Kwok, and Hal Daumé, III. Opponent modeling in deep
reinforcement learning. In International Conference on Machine Learning (ICML), 2016.
Johannes Heinrich, Marc Lanctot, and David Silver. Fictitious self-play in extensive-form games. In International Conference Machine Learning (ICML), 2015.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Advances in Neural Information Processing Systems (NeurIPS), 1997.
Zhang-Wei Hong, Shin-Yang Su, Tzu- Yun Shann, Yi-Hsiang Chang, and Chun-Y Yi Lee. A deep policy inference Q-network for multi-agent systems. In International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2018.
Timothy M Hospedales, Antreas Antoniou, Paul Micaelli, and Amos J Storkey. Meta-learning in neural networks: survey. IEEE International Conference on Soft Robotics (RoboSoft)lEEE Transactions Aerospace and Electronic Systems, 2021.
Hengyuan Hu, Adam Lerer, Alex Peysakhovich, and Jakob N. Foerster. "other-play" for zero-shot coordination. In International Conference on Machine Learning (ICML), 2020.
Max Jaderberg, Valentin Dalibard, Simon Osindero, Wojciech Czarnecki, Jeff Donahue, Ali Razavi, Oriol Vinyals, Tim Green, lain Dunning, and Karen Simonyan. Population based training of neural networks. arXiv preprint arXivv 2017.
Mare Lanctot, Vinícius Flores Zambaldi, Audrunas Gruslys, Angeliki Lazaridou, Karl Tuyls, Julien Pérolat, David Silver, and Thore Graepel. A unified game-theoretic approach to multiagent reinforcement learning. In Advances in Neural Information Processing Systems (NeurIPS), pp. 4190-4203, 2017.
Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, Pieter Abbeel, and Igor Mordatch. Multi-agent actor-critic for mixed ceoperative-compettiiee environments. In Advances in Neural Information Processing Systems (NeurIPS), 2017.
Reuth Mirsky, Ignacio Carlucho, Arrasy Rahman, Elliot Fosong, William Macke, Mohan Sridharan, Peter Stone, and Stefano V Albrecht. A survey of ad hoc teamwork: Definitions, methods, and open problems. arXiv preprint arXiv:2202. 10450, 2022.
Paul Muller, Shayegan Omidshafiei, Mark Rowland, Karl Tuyls, Julien Pérolat, Siqi Liu, Daniel Hennes, Luke Marris, Marc Lanctot, Edward Hughes, Zhe Wang, Guy Lever, Nicolas Heess, Thore Graepel, and Rémi Munos. A generalized training approach for multiagent learning. In International Conference Learning Representations (ICLR), 2020.
Frans A Oliehoek and Christopher Amato. A Concise Introduction Decentralized POMDPs. Springer, 2016.
Frans A. Oliehoek, Matthijs T. J. Spaan, Shimon Whiteson, and Nikos Vlassis. Exploiting locality of interaction in factored dec-pomdps. In International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2008.
Georgios Papoudakis, Filippos Christianos, Arrasy Rahman, and Stefano V Albrecht. Dealing with non-stationarity multi-agent deep reinforcement learning. arXiv preprint arXiv: 04737, 2019.
Georgios Papoudakis, Filippos Christianos, and Stefano V. Albrecht. Agent modelling under partial observability for deep reinforcement learning. In Advances in Neural Information Processing Systems (NeurIPS), 2021a.
Georgios Papoudakis, Filippos Christianos, Lukas Schäfer, and Stefano V. Albrecht. Benchmarking multi-agent deep reinforcement learning algorithms in cooperative tasks. Advances in Neural Information Processing Systems (NeurIPS), 2021b.
Jack Harker-Holder, Aldo Pacchiano, Krzysztof Marcin Choromanski, and Stephen J. Roberts. Effective diversity in population based reinforcement learning. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
11

---

Under review as a conference paper at ICLR 2023
Roberta Raileanu, Max Goldstein, Arthur Szlam, and Rob Fergus. Fast adaptation to environ- ments via policy-dynaminn value functions. In International Conference on Machine Learning (ICML), 2020.
Kate Rakelly, Aurick Zhou, Chelsea Finn, Sergey Levine, and Deirdre Quillen. Efficient off-policy meta-reinforceemen learning via probabilistic context variables. In International Conference on Machine Learning (ICML), pp. 5331-5340, 2019.
Tabish Rashid, Mikayel Samvelyan, Christian Schroeder, Gregory Farquhar, Jakob Foerster, and Shi- mon Whiteson. QMIX: Monotonic value function factorisation for deep multi-agent reinforcement learning. International Conference on Machine Learning (ICML), 2018.
Manish Ravula, Shani Alkoby, and Peter Stone. Ad hoc teamwork with behavior switching agents. In International Joint Conference on Artificial Intelligence (IJCAI), 2019.
Peter Roussceuw. Silhouettes: graphical aid to the interpretation and validation of cluster analysis. Journal of Aerospace Computing, Information, and Communication, 1987.
Mikayel Samvelyan, Tabish Rashid, Christian Schroeder de Witt, Gregory Farquhar, Nantas Nardelli, Tim GJ Rudner, Chia-Man Hung. Philip HS Torr, Jakob Foerster, and Shimon Whiteson. The Star- Craft agent challenge. In International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2019.
Peter Stone, Gal A. Kaminka, Sarit Kraus, and Jeffrey S. Rosenschein. Ad hoc autonomous agent teams: Collaboration without pre-coordination. In AAAI Conference Artificial Intelligence (AAAI), 2010.
DJ Strouse, Kevin R. McKee, Matt M. Botvinick, Edward Hughes. and Richard Everett. Collabo- rating with humans without human data. Advances in Neural Information Processing Systems (NeurIPS), 2021.
Peter Sunehag, Guy Lever, Audrunas Gruslys, Wojeiech Marian Czarnecki, Vinícius Flores Zambaldi, Max Jaderberg. Mare Lanctot, Nicolas Sonnerat, Joel Z. Leibo, Karl Tuyls, and Thore Graepel. pocoooiecoooooiiioon networks for cooperative multi-agent learning based team reward. In International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2018.
Zhenggang Tang, Chao Yu, Boyuan Chen, Huazhe Xu, Xiaolong Wang. Fei Fang, Simon Shaolei Du, Yu Wang, and Yi Wu. Discovering diverse multi-agent strategic behavior via reward randomization. In International Conference on Learning Representations (ICI.R, 2021.
Jianhao Wang, Zhizhou Ren, Terry Liu, Yang Yu, and Chongjie Zhang. QPLEX: Duplex dueling multi-agent q-laamiing. In International Conference on Learning Representations (ICLR), 2020a.
Yihan Wang, Beining Han, Tonghan Wang, Heng Dong, and Chongjie Zhang. DOP: Off-policy multi- agent decomposed policy gradients. In International Conference on Learning Representations (ICLR), 2020b.
Lei Xi, Jianfeng Chen, Yuehua Huang, Yanchun Xu, Lang Liu, Yimin Zhou, and Yudan Li. Smart generation control based on multi-agent reinforcement learning with the idea of the time tunnel. Energy, 2018.
Ruihan Yang, Huazhe Xu, Yi Wu, and Xiaolong Wang. Multi-task reinforcement learning with soft modularization. Advances in Neural Information Processing Systems (NeurIPS), 2020.
Ming Zhou, Jun Luo, Julian Villella, Yaodong Yang, David Rusu, Jiayu Miao, Weinan Zhang, Montgomery Alban, Iman Fadakar, and Zheng Chen. Smarts: Scalable multi-agent reinforcement learning training school for autonomous driving. arXiv preprint arXiv:2010.09776, 2020.
12

---

Under review as a conference paper at ICLR 2023
A
IMPLEMENTATION DETAILS OF CSP
A.1 ALGORITHMS
We now give more detailed pseudocode corresponding to different stages of CSP.
Algorithm 2 CSP: Training Stage
Initialize teammate policies =I= {TT) ....,,"'' MM
2:
while not done do for inner loops do
3:
4: for π E IT parallel do Control G-G with n², Train X² with any MARL algorithm
5: end for
6:
7: end for
8: for outer loops do
9: Update all π E II maximize JsVD (Eq. 1)
10: end for
11: end while
return II
Algorithm 3 CSP: Training Stage 2
1: Input: Teammate policy population I
2: Initialize scheme probing policy Tsp. autoencoder (Ee, De), and replay buffer B
3: while not done do
4: for X² E II do
5: Control G' with Tap and G-1 with π generate Tap for, at )
6:
B t B U {Tpp}
7:
Sample trajectories 'D from B
8: Compute (Epred [ based on 'D and update (Fe, De) (Eq. 3)
9: Train sTp by any MARL algorithm, with 7/ = rrt + (t)oal(t) (Eq. 4)
10: end for
11: end while
12: return Tap. E.
Algorithm 4 CSP: Training Stage 3
1: Input: Ireai Tap. E.
2: Initialize team embedding set Z; multimodal meta-policy Tmeta { T
3: for n² E IItraiin do
4: for N do
5: Control G with Tep and G with _ to generate Tsp for,
6: Get team embedding 2e = ET(Ta)) + Z {2c)
7: end for
8: end for
9:
Compute best with the Silhouette method on Z (Eq. 8)
10: Compute centers = (u....,, (2) with k-means clustering on Z
while not done do
12: for T E IIrain do
Control G with Tpp and G-1 with म generate Tap {or, a
14:
Get team embedding R. Ex(Tsp)
15:
Pick sub-policy TH. based on i* = arg min; I| - mill (Eq, 6)
Control G with ग.. and G with n². Train Fe with any MARL algorithm
17:
end for
end while
19:
return (MI,..., (A)); Mmeta ( 3x)
13

---

Under review as a conference paper at ICLR 2023
Algorithm 5 CSP: Deploying
1: Input: Tap: Ec μ (M1,... Ux), Tmeta {T...... m new policy seew to adapt
2: Control G¹ with Tap and G with new to generate Tap {or, a
3: Get team embedding 2e (Tsp)
4: Pick sub-policy म.- based on 1" arg min; || - M4 (Eq. 6)
5: Execute म.. to coordinate with neww
A.2 SILHOUETTE METHOD
We use the Silhouette method (Rousseeuw, 1987) to automatically determine the most suitable &t for the embedding set Z. The intuition that a higher Silhouette value for data point indicates that this point is placed in the correct cluster. Therefore, cluster number & with the highest mean Silhouette value for all points in a dataset is desirable. Concretely, for the embedding set Z, the Sihouette value SV (a) for each data point i that belongs to I-th cluster Z, is defined as:
(1) (i) SV())= = max (dout (f), din
if Z7 1,
if
Zz 1,
where (i) denotes the mean distance between data point i and other points in the same cluster, and dout(() (i) denotes the smallest mean distance of data point to all points in any other cluster. They are defined as (t) where d(i, j) is the Euclidean distance between data points i and j. We implemented an automatic selection approach by linear searching for the maximum mean Silhouette value of all data points:
12, i2 Eje d(i, and fout(1)
1
min [Zy] EiEEezz d(t.j),
k- arg max
Σ
iEZ SV
(8)
RSM
7
A.3 HYPERPARAMETERS AND ARCHITECTURE
In Stage 1, "inner loops" and "outer loops" are set to 32 and 5. respectively. MARL refers to any multi-agent reinforcement learning method, and we choose VDN (Sunehag et al., 2018) here. Population size M [Itrrin| [lvavll is 4 for all scenarios but Ic3s5z, which is set to 5 instead. In Stage 2, a is set to 1 x 10 and [D] is set to 32, In Stage 3, is set to 64.
Details of neural network architectures used by CSP are provided in Fig. 6. Each policy used in CSP (i.c., teammate policy x' E II. probing policy Tap- and each sub-policy in {oI,.... T }) is a form of "GRU policy" with local observation history as input and outputs value estimation across its action space. The MARL framework VDN adds up all agents' local utility di to form Quot. which updated to approximate the global discounted return.
Ey-nomalltaaion
a;1
9.C (Fu)
Qua (a,1r;)
FC: 64 Ir.l
ReLu
FC: [ouc]
FC: 64 jou!!
FC: 64 64
LeakyRelL
(a Ire))
1T
FC: 256 - 256
GRU: 64 64
Local utility network
Local utility network
LSTM: 64 - 64
LeakyReLL
FC: [in] - 256
FC: [ix] - 64
Tu (Pror)
(Pror)
FC: [Ix] 64
(5.)7)
[ouee)
(5az) Encoder
Decoder D.
GRU policy
framework
Figure 6: Network architectures of CSP, where o,, and a,,, represent the local observation and action for agent at timestep and Ti is the trajectory of agent i's local observations until timestep
14

---

Under review as a conference paper at ICLR 2023
B DETAILS OF ENVIRONMENTS
Figure 7: All the environments used in this paper. The first row from left to right: Level-based Foraging (LBF), Overcooked Forced Coordination Hard, SMAC Fork. The second from left to right: Predator-Prey (PP), Overcooked Coordination Ring, SMAC 1c3s5z.
Level-based Foraging (LBF) (Papoudakis et al., 2021b). We use an instance of LBF, where the environment a 20 20 grid world with agents and 4 food. Each agent has self-centered 5 observation range and a discrete action space for moving in four directions and collecting food. The goal of each agent to collect all the food on the map. When food is collected, the environment returns shared reward proportional to the food level with total reward normalized to 1. An episode terminates if all the food collected or reaches 50 total timesteps. To enhance the requirement for cooperation, we set the extra constraint that each food can only be collected if both agents are adjacent and perform the "collect" action simultaneously. We let CSP or baselines control one player and teammates from II control another. The variability of coordination schemes in this environment reflected the order of eating all 4 food.
Predator-Pres Prey (PP) (Böhmer et al., 2020). This environment can be considered more complex version of LBF, where 2 predators with 5 x observation range are expected to hunt prey in 10 10 grid world. An episode ends when all prey is captured, 200 timesteps have passed. The extra difficulty comes from the fact that each prey moves randomly throughout the game, so predators must constantly jointly chase the prey. We simplify the task by removing the "capture" action, and predators can capture prey with only a siege. Therefore, there will be no miss-capturing punishment. The coordination schemes in this environment are reflected the order of chasing prey and the respective division of labor in the roundup of prey.
Overcooked (Strouse al., 2021). There are agents the environment sharing 6-dimensional discrete action space: moving in four directions, interacting with the object facing, and doing nothing. Cooking a dish requires a series of actions and a waiting period. Delivering dish requires picking up, moving to the correct delivery point, and putting it down. The goal of both agents is to complete as many delivery orders as possible within 400 timesteps. We set CSP or baselines to control the blue player and teammates from II to control the green player. In the layout Coordination Ring (lower), the passage is narrow, and the two agents may clash in their pathfinding. In the layout Forced Coordination Hard (upper), only the green agent touch the cookware, and only the blue agent reach the delivery point. Coordination forced this layout since no agent can finish the task alone, and they have to adapt teammates' preferences.
15

---

Under review as a conference paper at ICLR 2023
SMAC (Samvelyan et al., 2019). It is widely used as multi-agent benchmark for its high complexity of control. Each agent can move in four cardinal directions, stop, do nothing, or select an entity to interact (heal or attack according to its type) each timestep. Therefore, if there are na allies and n. enemies in the map, the action space for each unit contains na + ne + 6 discrete actions, and the joint action space size is (m, nh 6)^,. The map 1c3s5z is standard map that requires control of 9 agents. We set CSP or baselines to control the first 4 agents, and teammates in II control the reset 5 agents.
We specially designed a map called Fork (Fig. 8) for this work which requires strong coordination and has very different coordination modes. has 2 ally spawn points on the left and middle left sides of the map and enemy spawn points on the upper right and lower right corners. At the beginning of episode, each ally spawn point generates marines (Iong-range attack unit), and each enemy spawn point generates 6. We let CSP or baselines control allies at point 1 and teammates from II to control allies at point 2. If both groups choose attack the same group of enemies, it will be 8 versus 6 and is easy to win. By contrast, if two groups of teammates attack different groups of enemies, respectively, it will be 4 versus 6, and neither group will be able to defeat. Thus, intuitively there are two main kinds of cooperation modes, which refer attack enemies in the corresponding direction first. The population II is trained with CSP's stage 1. In order to make the population unbiased in attacking directions, we manually pick policies from the original population with 4 Ups and 4 Downs to form the balanced population.
Up and Down in this work, indicating
Ally
Ally Point
Point
Figure 8: New SMAC map Fork.
C DETAILS OF BASELINES
We compare CSP against six baselines. All of them are implemented with a similar GRU agent and VDN framework as CSP (Fig. 6). except that the input of GRU agents is T, = {(o,, 2e)o:1} which has additional embedding =, at each timestep, so we mainly focus on how they build with components shown in Fig. 9.
PEARL (Rakelly et al., 2019). This baseline comes from single-agent and meta-learnin settings. It aims to represent the environments by hidden representations. utilizes the history-data as context to inference the feature of the environment, which is modeled by product of Gaussians. Since we use the Dec-POMDD setting, the PEARL module is adopted and optimized on each individual policy.
Population based trainin (PBT). This baseline uses simple domain randomization to train G' against all the teams in Hrrsin- The training set Ilrain is required from CSP's stage 1. We think fixing this population increases the faimess of the comparison.
Ficticious co- co-play (FCP) (Strouse et al., 2021). This baseline uses similar domain randomization approach like PBT to train G¹, except that the training population is extended version of IIrain- Checkpoints at one-third and two-thirds of the total training timesteps are added to Im indicating teammates with different levels of ability.
16

---

Under review as a conference paper at ICLR 2023
Local information agent model (LIAM) (Papoudakis et al., 2021a). This baseline equips each agent with an encoder-decoder structure to predict other agents' observations o, and actions a; at current timestep based on its own local observation history T {on=)). The encoder and decoder optimized to minimize the mean square error of observations plus the cross-entropy error of actions. The original version of LIAM considers only single controllable agent, and predictions upon this agent's ' local observation. To fit in MARL's centralized training, we let all controllable agents make predictions based on their observations and calculate their loss, and use the mean of their loss as the final loss.
made
Full information agent model (FLAM) (Papoudakis et al., 2021a). This baseline a variant of LIAM by replacing the input trajectory of local observations T {oo:e] with the trajectory of global states 72 = )
Online adaptation via inferred teamwork situations (ODITS) (Gu et al., 2022). Unlike the previous two methods that predict the actual behaviors of teammate agents, ODITS improves zero- shot coordination performance in end-to-end fashion. It has two variational autoencoder pairs, one global and one local. The global encoder takes in state trajectory T. = { and outputs the mean and variance of Gaussian distribution. A vector ze indicating "global teamwork situation" then obtained by sampling from it. The global decoder uses 2e to build the parameters 24 of a hyper-network that maps the ad hoc agent's local utility Qi into global utility Quoi approach the global discounted return. The local encoder has a similar structure as the global encoder, except that its input is replaced with local trajectory 7 {oo.t)- It is updated by maximizing the mutual information of its output & and the global ze. The local decoder further maps & into a variable &e used the ad hoc agent's input. The whole training end-to-end by maximizing global return and mutual information of be and že. Similar to LIAM, ODITS only considers a single ad hoc agent setting. We modified the loss to the mean of all controllable agents' individual loss to make it fit in MARL.
To ensure fairness in the use of hidden variables, we make CSP and all baselines have the same width for &e in each environment. Concretely, [=e] is set to 8 for Overcooked, LBF, and PP, and 64 for Fork.
Z, or 2,
071 a,"
Resample
Zn
Softmax
mean
var
FC: 64 - |x_|
FC: 64 - Jout]|
FC: 64 |ouz|
FC: 66 [out]
FC: 64 - 2/zz|
ReLU
ReLU
ReLU
RelU
FC: 64 64
FC: 64 64
LSTM: 64 ~ 64
FC: 64 64
FC: 64 -> 64
RelU
ReLU
RelU
ReLU
LSTM: [ix] 64
FC: |in| 64
|ix]
FC: [ix] - 64
FC: [án] - 64
To
Zc
T2 ODITS's global / local encoder
7, ODITS's global decoder
a, ODITS's local decoder
Encoder LIAM/ FIAM
Decoder UAM / FIAM
Figure 9: Network architectures of baselines.
D MORE EXPERIMENT RESULTS
D.1 EMBEDDINGS ON EACH ENVIRONMENT
To measure the quality of our scheme embedding, Fig. 10 adopts t-SNE to visualize the embedding of distinguished teams. Each color in four t-SNE sub-figures represents the embedding of distinguished teams. It shows that our scheme embedding can cluster the same coordination scheme and classify the different schemes, which shows high quality property for team recognition and sub-policy selection.
17

---

Under review as a conference paper at ICLR 2023
LBF
PP
Overcocked Forced Goord.
Overcooked Coord. Reg
gdit
eval.
ova
ova
evaal
Irain 0
train 1
train
Irain 3
Figure 10: t-SNE of CSP's coordination scheme embeddings in different environments.
D.2 CROSS-PLAY OF DIVERSE TEAMMATES
To measure the quality and diversity of our SVD population generation in training stage 1. We concatenate all the teams the training set Irain and the evaluation set Iovall together and make cross play with each other. In LBE, Overcooked, PP, and SMAC, Itaain and eeat are both while that of SMAC lc3s5z is 5. We normalize the score to [0, 100) for each scenario and show them in heatmaps in Fig. 11. In most benchmarks, agents in the population cannot coordinate with others, as the values on the diagonal (i.c. self-play) are much higher. Fork mainly contains two coordination schemes as comparison. The heatmaps show that our SVD method can generate diverse population to simulate the underlying coordination schemes.
LBF 20x20-2s
Overcooked Forced Coord.
SMAC Fork
21
25
60
20
95
Aeent Group
Apenti Group
2:34
Agent tarupp1 PP 2p4s
Agent Group -1
Agent Group -1
Overcoaked Coord. Ring
SMAC 1c3s5z
Agart Group
Agast Grop
Ague
C5
S1
x
Agent Group -1
Agent Group -1
Agent Group -1
Figure 11: Cross-play performance of II Itrain U Ieval in all scenarios.
To further support that Ieall trained with SVD is better benchmark for testing generalization perfor- mance compared to randomly trained teammates, we train another 10 teams independently without SVD for PP and SMAC Fork each. Fig. 12a illustrates their cross-play performance. Compared to the original teams with SVD as shown in Fig. 11, we can find two major phenomenons: (1) It seems that not only the locations at the diagonal have high values, indicating that each team is able to coordinate with some other teams apart from itself. As we have claimed in Sec. 3, coordination performance across different schemes is generally not guaranteed. It is clear that there are multiple teams following the same coordination scheme in the population, which is redundant and makes the population less diverse. (2) We can still see the clear 2-scheme structure for SMAC Fork, but the distribution is biased (7 for and 3 for the other). An ideal benchmark should be unbiased for all the underlying coordination schemes to best match our goal. SVD encourages different teams to behave differently as possible, which naturally weakens the potential bias for particular scheme.
18

---

Under review as a conference paper at ICLR 2023
We also tested the performance of CSP and baselines these populations trained without SVD as shown Fig. 12b. In this case, CSP still performs better, but the relative advantage less sigmificant. The result verifies the performance of CSP under random coordination settings, and is also in line with what we claimed above. Since our goal is to train policy that can coordinate under any scheme, using a more diverse and less redundant eval trained with SVD makes sense.
PP (without SVD)
SMAC Fork (without SVD)
Test Performnnce (without SVD)
0.7
-0
Ageent Gr.g
66
80
25
26
90
35
34
33
03
08
Agent Group
Agent Group
SMAC FOr
(a)
(b)
Figure 12: (a) The cross-play matrix populations trained without SVD. (b) Generalization perfor- mance of CSP and baselines the two SVD populations.
D.3 EXTRA COST OF CSP COMPARED TO ZERO-SHI SHOT METHODS
As newly proposed few-shot framework, CSP takes envirommental interactions and training steps in its additional Stage 2 compared to zero-shot baselines. We draw the learning curves of the self-supervised autoencoder pair (E,, Da) in Fig. 13 show how much extra cost is actually required. As can be seen from the plots, the cross- cross-entropy loss between reconstructed teammate actions and the ground truth drops rapidly in the early stage and slowly decreases as training moves on. This phenomenon indicates that the self-supervised learning process in Stage 2 is much more sample-efficient than reinforcement learning. Therefore, although we let Stage the environment many timesteps Stage in our experiments, it actually only requires small portion of interactions to make a good representation. We will further investigate how to compress this additional cost in future work.
interact with
SMAC
2.4
Entropy
3.5
1.2
1.8
8.0
12
0M
SM
SM
10M
5M
2M
BM
10M
0M
4M
5M
timesteps
Simesstepe
PP
Overcooked Coord. Ring
SMAC 1c3e52
1.5
1.2
0.8
0.8
1.2
0.3
0.4
0.6
0.0
0.0
0.0
DM
3M
4M
6M
12M
0.MM
0.MM
1.2M
1.MM
2.4M
S.0M
Smmesaps
Sme-slaga
limestega
CSP Stage
Figure 13: Learning curves of (Ec, De) in CSP's Stage 2.
19


Reviews:
[{"review_id": "pxcMg66lnJJ", "reviewer": "Reviewer_yqCj", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "Instead of following zero-shot coordination adopted in existing work, the proposed method CSP improves group adaptation using limited interaction data. CSP first trains a set of diverse teammate policies, then train a scheme probing policy to detect the patterns of teammates. By interacting with the teammates, the embeddings of the trajectories of the scheme probing policy encode the information of teammates' patterns (coordination schemes). By clustering the embeddings, CSP obtains the possible coordination schemes. Then CSP trains a meta-policy, which uses each sub-policy to deal with each coordination scheme. In execution, CSP first acts scheme probing policy to interact with the new teammates and then chooses the sub-policy with the closest embedding distance from the scheme probing policy.", "summary_of_the_review": "More baselines and experiment settings as mentioned above are required. The difference between the proposed method and existing work including policy representation and meta-learning methods should be justified. In its current form, the paper is below the bar of ICLR.  ", "strength_and_weaknesses": "## Strength\n\n* Coordinating with new teammates is an important problem in multi-agent reinforcement learning.\n* The proposed method seems reasonable.\n* The experiments are performed on a variety of multi-agent tasks.\n\n## Weaknesses\n### minor issues \n* In problem formulation, the agents under control are denoted by $G^1$ and the teammates are denoted by $G^{-1}$. In Stage 1, do you train the team population of $G^{-1}$ or $G^1 \\cup G^{-1}$? I think in multi-agent environments, it is not reasonable to train $G^{-1}$ only, but Stage 1 in Figure 2 is confusing. And I suggest distinguishing $G^1$ and $G^{-1}$ clearly in the method section.\n\n* Interacting with different teammates, the intrinsic reward $L_{pred}$ of scheme probing policy is different. Would the non-stationary reward damage the learning of the scheme probing policy?\n\n* I am curious about whether the team policies in Stage 1 are diverse enough or just collapse to a few modes. The paper claimed that \"the number of clusters k will be approximately equal to the number of environmental coordination schemes if $\\Pi_{train}$ already covers all possible schemes. \" It is important to run experiments with different M (size of $\\Pi$) and show the relationship between k and M.\n\n* The intrinsic reward of the scheme probing policy $L_{pred}$ is an important part of CSP. Ablation studies about $L_{pred}$ are necessary to verify the effectiveness.\n\n### major issues\n* The problem setting is similar to the meta-learning problem. Thus, meta-learning baselines should be included for comparison, e.g., PEARL [1].\n*  The scheme probing module is used to differentiate the embeddings of the trajectories when playing with different teammates. Thus, policy representation methods should also be included as baselines, e.g., [2]. \n* The proposed method may not be scalable. It seems all coordination schemes should be covered in the training set. Otherwise, the generalization to unseen schemes is not guaranteed. In the current experiments, the settings are essentially two-agent cases (even for SMAC where one agent controls 4 units and another controls 5). What about the case of more than two agents? This should be included as least empirically.\n\n[1] Rakelly et al., Efficient Off-Policy Meta-Reinforcement Learning via Probabilistic Context Variables, ICML 2019.\n\n[2] Grover et al., Learning Policy Representations in Multiagent Systems, ICML 2018.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "kPCJh119W2e", "reviewer": "Reviewer_d7jH", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper focuses on the ad-hoc teaming aspect of coordination. Unlike most previous works it focuses on coordination of different groups of agents rather than a single-agent with different teams. Moreover they show adaption ability in the context of within an episode as well in various multi-agent cooperative scenarios. Their solution has three major components: 1) a bilevel optimization formulation for obtaining a _diverse_ population of teams, 2) a disentangling coordination scheme probing module to classify new teammates with limited episodic data with its own policy optimized for probing actions, and 3) hierarchical policy that chooses the appropriate sub-policy for distinguished coordination scheme to coordinate with other agents. ", "summary_of_the_review": "The paper comes up with a very effective pipeline for solving a super practically important problem of ad-hoc teaming.", "strength_and_weaknesses": "**Strengths**\n\nThis is a fantasic paper and it's great to see it go all the way towards a practical solution for this problem (albeit computationally expensive). The shared code is also fairly easy to follow and would definitely make it easier to try alternative ideas in this space. The three steps make total sense. While individual one of these may have been tried, this paper bring it together as a strong pipeline for a very practically useful class of problem. SMAC Fork turns out to be surprsingly effective understandable environment as well.\n\n**Weaknesses**\n\nOnly unsatisfying part of the solution is the separate step of clustering/grouping which the paper shows was important for effective training. In principle it should be possible to force such clustering by the probing module or be figured out by the conditioned policy.\n\nGiven the bilevel framing, it's surprising that PSRO [1] and $\\alpha$-PSRO [2] don't even see a mention. Similarly would be useful to mention [3] and [4] when it comes to conditioned policies for multi-agent adaption and their generalization evaluation. \n\n[1] https://arxiv.org/abs/1711.00832\n\n[2] https://openreview.net/forum?id=Bkl5kxrKDr\n\n[3] https://proceedings.mlr.press/v80/grover18a.html\n\n[4] https://www.ifaamas.org/Proceedings/aamas2018/pdfs/p1944.pdf", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "hr4enH-uc6", "reviewer": "Reviewer_27TM", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper aims to address two weaknesses in current multi-agent coordination methods - they tend to focus on a single agent's ability to coordinate with teams in a zero-shot setting, which ignores team to team coordination and limits the ability to adapt to teammates. The paper addresses these shortcomings using a three step framework:\n1) Learn coordination schemes from a diverse set of trained teams by maximizing a Soft-Value Diversity objective, or the variance of softmax normalized value estimates for all policies in a population. \n2) Train a module to embed information about teammates' policies using an action autoencoder. The data for this module is collected from one episode of team interaction using a separate probing policy, trained to maximize reconstruction loss of the autoencoder, effectively searching for uncertain states. \n3) Classify the teammate embedding within coordination strategies using k-means and learn a meta-policy to select among coordination schemes during evaluation. ", "summary_of_the_review": "Overall, this paper proposes an interesting but fairly complex method. While there are some weaknesses, the thorough experiments and results provide evidence for the effectiveness of the method. ", "strength_and_weaknesses": "Strengths:\n* The paper addresses an important question of team-to-team coordination and fast adaptation of the policy. \n* The method generally matches or exceeds state of the art on all tasks. \n* The paper is generally well written and polished. \n\nWeaknesses:\n* This paper seems to be solving a \"simple\" problem - finding a coordination policy for a particular team - by first solving the much harder problem of finding all possible coordination policies. It's not clear that the SVD objective presented in this paper would be effective in uncovering enough diversity in policies to coordinate well with a general team, as the partner agents are all drawn from the same (evaluation) population and trained with the same method, while prior works have shown that the choice of algorithm can result in substantially different zero-shot coordination ability. It would be interesting to see how the method performs when drawing teams from different populations or partially-trained populations. I would also like to see an ablation of the SVD outer objective during training.\n\n* While there are six different, coordination tasks explored in this paper, most based on prior work, they range of coordination strategies is relatively limited. In the Fork environment for example, there are essentially only two choices strategies, up or down, while in Overcooked Ring the choices are clockwise or counterclockwise. On the opposite extreme, there is no particular strategy to learn for 1c3s5z, to the best of my knowledge. I would be interested in seeing some environments with less clearly defined coordination strategies, such as Hanabi. \n\nQuestions:\n* Are baselines trained and evaluated on the same populations, trained with the same SVD objective? \n* Is the algorithm used QMIX (Section 4.1) or VDN (Section 5)? \n\nMinor:\n* Section 3/Problem Formalization - \"we\" -> \"We\"\n* Section 4/ Meta-Policy Learning - \"reset\" -> \"rest\"\n* Appendix C/PBT - \"tixing\" -> \"fixing\"(?)", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "158JZzSqSZ", "reviewer": "Reviewer_td12", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper addresses the problem of group-to-group coordination in multi-agent scenarios, where agents need to coordinate with newly arrived teammates. The proposed CSP approach (1) simulates diverse teams, (2) autoencodes teams' behavior trajectories, and (3) clusters trajectory representations into groups, each of which learns a separate sub-policy. Finally, given a new team to coordinate with, its behavior trajectory is observed and assigned the closest cluster and sub-policy. On four multi-agent cooperative environments, the paper demonstrates zero-shot coordination generalization to unknown teams.", "summary_of_the_review": "The paper has a good amount of strengths but lacks several details, which limit its understandability, and consequently, a proper evaluation is hard. The empirical evaluation does not yet seem to incorporate the potentially special assumptions made by the paper. If these issues are addressed or clarified, I would be happy to engage in a discussion and raise my score.", "strength_and_weaknesses": "## Strengths\n- The problem of group-to-group coordination requiring generalization to new teammates is interesting and seems novel.\n- The idea of separately probing a newly introduced team makes sense, as a probing policy can explore the parts of the state which bring out coordination schemes. Then, the resultant trajectory would be a good representation of what the team can do in different scenarios. Thus, while solving the task, the policy can look into the potential \"future\" coordination behavior (assumed to be deterministic though) through the trajectory representation. This eliminates the non-Markovian nature of the problem originating due to the unknown team of agents.\n- On careful inspection and understanding, the method and the different proposed stages make sense as a solution to the proposed problem.\n- The ablation study is crucial and tests the different variations of the method, albeit in 2 environments.\n\n## Weaknesses\n- **Paper writing**:\n    + Overall, the paper was hard to follow as someone unfamiliar with the details of ad hoc teamwork. Ideally, the paper could have been written in a way that anyone with a working knowledge of RL and some Multi-agent RL should be able to follow the build-up of the paper. But there were many specialized terms (ad hoc, coordination scheme, etc) introduced without enough details, which made it hard to follow the flow of writing. It took me 2 full reads to even understand what the paper was trying to convey.\n    + It is difficult for a reader to distinguish the problem and the solution in the paper. For example, \"coordination scheme\" is used sometimes as part of the problem formulation and sometimes as part of the approach (e.g. the unsupervised discovered latents are coordination schemes).\n\n- **Unclear definitions**\n    + *Coordination scheme definition*: Section 3 just defines coordination schemes as \"different ways to solve the task\". This is very open-ended and not a concrete definition, which makes it hard to understand the central point of the paper. It leaves many unanswered questions, such as:\n        * What is a coordination scheme $c \\in C$ exactly? Does it fully define all the sets of optimal behaviors for each agent in the task?\n        * Why is the set of coordination schemes C discrete?\n        * What does it mean for a policy $\\pi^c$ to be derived by a scheme $c \\in C$? Is this defined for deterministic policies only?\n    + *Problem Formulation*: The formulation of cumulative reward is not explained well. For instance, what does $(\\pi^c)^{-1}$ come from and what does it mean? What is the surrogate that is being replaced here?\n    + *Assumptions*: The method just lists down the process that CSP follows, but does not first list down the assumptions that the problem setup makes. This makes it hard to understand what an ideal baseline would be. For instance,\n        * Why is it assumed that the training can be split into such different stages with full control over the teams that can be sampled and tested?\n        * Are the agents at test time also new or only the team compositions are new and expect generalization?\n        * Why can't the coordination schemes be different from the training clusters? What if a new coordination scheme is required at test time that none of the clustered policies actually solve well directly, but interpolation is better (i.e. coordination schemes lie on a continuous plane)? In this case, in fact, the POP(z) or CSP(z) ablations should surely work better?\n\n- **Empirical Evaluation**\n    + The first (generating diverse team populations and training MARL) and second stages (learning scheme probing policy) of CSP require interaction with the environment. Are these extra environment steps accounted for while plotting the results in Figure 3? It seems from the description in Section 5 that the baselines PBT, FCP, and ODITS do not require Stage 2 interactions; and LIAM, and FIAM do not require Stage 1 or 2 interactions. If that is correct then for a fair comparison of learning efficiency, Figure 3 should account for the extra steps taken by CSP and baselines in stages 1 and 2. I am also curious how many timesteps are currently being dedicated to these stages for the 6 scenarios.\n    + While I appreciate the ablation study, it is a bit little unsettling that the POP(z) ablation suffers so much. It could be that the current set of environments and coordination schemes are too simple and discrete that they can be modeled by separate sub-policies. However, for more complex and realistic environments, intuitively the context-based approach, i.e., POP(z) or CSP(z) should be better, as they can model the continuity in coordination schemes and interpolate in its latent representations accordingly. I am curious as to what the authors' thoughts are on this.\n\n## Clarifications\n- The introduction mentions: \"The information for identifying different teams is collected by the same policy that aims to maximize coordination performance\" will suffer from the exploration-exploitation dilemma. Is this validated by comparison to any baseline?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject