Zero-Shot Coordination via Semantic Relationships Between Actions and Observations
Authors: Mingwei Ma
Jizhou Liu
Samuel Sokota
Max Kleiman-Weiner
Jakob Nicolaus Foerster
Venue: ICLR 2022 Submitted (2022)
Keywords: multi-agent communication
multi-agent reinforcement learning
attention mechanism
zero-shot coordination

Abstract: An unaddressed challenge in zero-shot coordination is to take advantage of the semantic relationship between the features of an action and the features of observations. Humans take advantage of these relationships in highly intuitive ways. For instance in the absence of a shared-language, we might point to the object we desire or hold up fingers to indicate how many objects we want. To address this challenge, we investigate the effect of network architecture on the propensity of learning algorithms to make use of these relationships in human-compatible ways. We find that attention-based architectures that jointly process a featurized representation of the observation and the action, have a better inductive bias for exploiting semantic relationships for zero-shot coordination. Excitingly, in a set of diagnostic tasks, these agents produce highly human-compatible policies, without requiring the symmetry relationships of the problems to be hard-coded.

Under review as a conference paper at ICLR 2022
ZERO-SHOT COORDINATION VIA SEMANTIC RELA- TIONSHIPS BETWEEN ACTIONS AND OBSERVATIONS
Anonymous authors Paper under double-blind review
ABSTRACT
An unaddressed challenge in zero-shot coordination (ZSC) regards taking advan- tage of the semantic relationship between the features an action and the features of observations. Humans take advantage of these relationships in highly intuitive ways. For instance, we might point to the object we desire or hold up fingers to indicate how many objects we want. This work investigates the effect of network architectures on the propensity of learning algorithms to make use of these rela- tionships in human-compatible ways. We find that attention- that jointly process a featurized representation of the observation and the action have better inductive bias for exploiting semantic relationships for zero-shot co- ordination. Excitingly, in a set of diagnostic tasks, these agents produce highly human-compatibl policies, without requiring the symmetry relationships of the problems to be hard-coded.
architectures
INTRODUCTION
Successful collaboration between agents requires coordination (Tomasello et al. 2005 Misyak et al. 2014 Kleiman- Weiner et al.) 2016), which is challenging because coordinated strategies can be arbitrary (Lewis) [ Young 1993 Lerer & Peysakhovich 2018). A priori, one can neither deduce which side of the road drive, nor which utterance use refer to ? (Pal al.) 2020). In these cases coordination can arise from actors best responding to what others are already doing i.e. following a convention. For example, Americans drive on the right side of the road and say "heart" to refer to & while Japanese drive on the left and say "shinzo". Yet in many situations prior conventions may not be available and agents may be faced with entirely novel situations or partners. In this work we study ways that agents may learn to leverage abstract relations between observations and actions to coordinate with agents they have had no experience interacting with before.
To illustrate, consider the following situations where people can figure out how to coordinate without prior experienced or shared conventions. Imagine a store that sells strawberries and blueberries. You want to buy strawberries but you don't 't share any common language with the clerk. You are however wearing a red hat and you wave the hat at the clerk to hint that the strawberries are what you want. The clerk has two baskets of strawberries remaining, and so you raise single finger to indicate that you only want one of the baskets. The clerk produces a paper and plastic bag and you point to the paper bag to indicate that you want the paper one. These examples are so simple that they seem obvious: the red hat matches the colors of the strawberries, the number of fingers matches the number of baskets you want, and you extend finger in the direction of the desired packaging Grrie 1975). While obvious to people, who rely on theory-of -frorr-oo--mind in understanding others, we will show that these inferences remain challenge for multi-agent reinforcement learning agents.
Less obvious examples are common in the cognitive science literature. Consider the shapes in Fig. When asked to assign the names "Boubo" and "Kiki" to the two shapes people name the jagged object "Kiki" and the curvy object "Boubo" (Köhler 1929). This finding is robust across different linguistic communities and cultures and is even found in young children (Maurer et al., 2006). The causal explanation is that people match a "jaggedness" ffeaturre and "curvey" -featre in both the visual and auditory data. Across the above these cases, there seem to be a generalized mechanism for mapping the features of the persons action with the features of the desired action. All are examples of where in the absence of norms or conventions, people minimize the distance between features when making choice. This basic form of zero-shot coordination predates verbal

---

Under review as a conference paper at ICLR 2022
behavior (Tomasello et al., 2007) and this capability has been hypothesized key predecessor to more sophisticated language development and acquisition (Tomasello et al. 2005). Modeling these capacities is key for building machines that can robustly coordinate with other agents and with people (Kleiman-Weide et al. 2016 Dafoe et al. (020).
Figure I: When asked to assign the names "Boubo" and "Kiki" to these two shapes, people systematically assign the name "Boubo" to the jagged object on the left and "Kiki" to the curvy object on the right.
However, as we will show, naively training reinforcement learning (RL) agents with self-play fails learn coordinate even in these obvious ways. Instead, they develop arbitrary private languages that are uninterpretable to both the same models trained with different random seed as well as to human partners (Hu et al. 2020). For instance in the examples above, they would be equally likely to wave a red-hat to hint they want strawberries as they would to indicate that they want blueberries.
These problems also emerge at scale the decentralized partially observable Markov decision pro- cess (Dec-POMIP) benchmark Hanabi (Bard et al. 2019). When agents are trained with self-play using standard architectures they do not develop strategies that take into account the correspondence between the features of the actions (colored and numbered cards) and the observation of the game state (other colored and numbered cards). Unfortunately, describing the kind of abstract knowledge that these agents lack in closed form is challenging. Rather than attempting to do so, take learning-baa based approach. Our aim is to build an agent with the capacity to develop these kinds of abstract correspondences during self-play such that they can robustly succeed during cross-play or during play with humans.
follows: (1) We extend Dec-POMDDPs to allow actions and observations to be represented using shared features and develop novel human-interpretablc environment for studying coordination in this setting. (2) We evaluate the role of neural network (NN) architectures including feedforward, recurrent, and attention mechanisms on both cross-play generalization and ability to create human-inte inntranntterrettblee conventions. (3) We show that an attention architecture which takes both the action and observations as input allows the agent to exploit the semantic relation- ships for coordination, resulting in strong cross-play and human compatible policies that outperform baseline ZSC methods. This model also demonstrates sophisticated coordination patterns that ex- ploit mutual exclusivity and implicature, two well-known phenomena studied in cognitive science (Markman & Wachtel 1988 Grice 1975).
Our contributions
RELATED WORK
The standard method for training multi-agent reinforcement learnin (MARL) agents in fully cooperative, partially observable settings is self (SP). However, the failure of SP policies in cross-play (XP) has been recently explored. Carroll et al. (2019) used grid-world MDPs to show that both SP and population-based training fail when paired with human collaborators. In Hanabi, agents trained via SP develop conventions that fail to generalize to independently trained
Cooperative MARL.
agents from the same algorithm with different random seeds (Bard et al. 2019 Hu et al. 2020).
Zero-Shot Coordination. To address this issue, Hu et al. (2020) formally introduced the zero- shot coordination (ZSC) framework, where the goal is to maximize the XP returns of independently trained agents, allowing them to coordinated at test time. Thus formulated, ZSC is an alternative ad-hoc teamplay, framework for measuring coordinated team success when faced with players with unknown behavior (Stone et al. 2010 Barrett et al. 201 Tb, which can be formalized as playing a best response to a distribution of a-priori known agents.
A few methods have attempted to address the ZSC framework. Other-Play (OP) (Hu et al., 2020) exploits the symmetries in given Dec-POMDP to prevent agents from learning equivalent but mutually incompatible policies. OP prohibits arbitrary tie-breaking, thereby preventing equivalent conventions from forming. However, OP requires experimenter-code such symmetries is computationally challenging. In contrast, our learning based approach requires no experimenter-coding Another recent method, Off-Beliet Learning (OBL) (Hu et al., (02T). regularizes agents' ability make inferences based the behavior of others. Compared to prior
symmetries, and discovering
2

---

Under review as a conference paper at ICLR 2022
work Hanabi where SP scores were high but XP scores were near chance, both of OP and OBL drastically improve XP scores and show promising preliminary results in play with people. However, neither of these algorithms can exploit the correspondences between features of an action and the observation of the state as we show in this work, unless this falls out of the environment dynamics.
Attention for Modeling Input-Output Relationships. Attention (Vaswani al. 2017 Bahdanau eet al. 2015 Xu et al. (016) is an important tool for large sequence models, and exploiting semantic relationships between imputs and outputs via an attention-based model has been studied in the deep learning literature. In natural language processing, such an idea is commonly applied to question answering models (dos Santos et al., 2016 Tan et al.) 2016 Yang al., 2016). For instance. Yang et al. (2016) form a matrix that represents the semantic matching information of term pairs from a question and answer pair, and then use dot-product attention to model question term importance. For regression tasks, Kim et al. (2019) proposed Attentive Neural Processes (A (ANP) that use dot-product attention to allow each input location to attend to the relevant context points for the prediction, and applied ANP to vision problems. However, to our knowledge, we are the first to apply attention to exploit shared features of actions and observations in a Dec-POMDP setting for coordination.
Human Coordination. Our work is also inspired by how humans coordinate in cooperative settings. Theory-of-mint the mechanism people use to infer intentions from the actions of others, plays key role in structuring coordination (Wu et al., 202 Shhm et al., 2019). In particular, Rational Speech Acts (RSA) is a influential model of pragmatic implicature (Frank & Goodman, 2012 Goodman & Stuhlmüller 2013). At the heart of these approaches are probabilistic representations of beliet which allow for the modeling of uncertainty and recursive reasoning about each others belief', enabling higher-order mental state inferences. This recursive reasoning step also underlies the cognitive hi- erarchy and level-K reasoning models, and is useful for explaining certain focal points (Camerer) 2011 Stahl& & Wilson| 1995 Camerer et al.] (004). However, constructing recursive models of play- ers beliefs and behavior is computationally expensive as each agent must construct an exponentially growing number of models of each agent modeling each other agent. As a result, recursive models are often limited to one or two levels of recursion. Furthermore, none of these approaches can by itself take advantage of the shared features across actions and observations.
BACKGROUND
Dec-POMDPS. We use decentralized partially observable Markov decision processes (Dec- POMDPs) to formalize our setting (Nair et al. 2003). In a Dec-POMDP, each player i observes the underlying state s partially through an observation function (2) E O', and takes action a² E A'. Players receive common reward R(s, a) and the state follows the transition function T(s, a). The historical trajectory is denoted as = (81, 01 (x)), Player i's action-observation history (AOH) is denoted as (12(s)) and outputs a distribution over actions, denoted by T' (a" TT)). The joint policy is denoted by
. 2t (sx)). The policy for player i takes as input an AOH
Dot-Product Attention. Given a sequence of input vectors (Ir,,..., Im). dot-product attention uses three weight matrices (Q, V) to obtain triples (Qx,, Kx,, Vx,) for each E (1....,,,, m,) called query vectors, key vectors, and value vectors. We abbreviate these as (g:, K;, v1). Next, for each j. dot- dot-produet attention computes logits using dot products qi ky. These logits are in turn used to compute an output matrix
[softmax(g: kt..mm.......................... km/ Am//m)) Uysles
We denote this output matrix as (1e,ntion(11.......1
4 DEC-POMDPS WITH SHARED ACTION AND OBSERVATION FEATURES
It is common to describe the states and observations in Dec-POMDPss using features, e.g. in games each card has a rank and a suit. These featurized observations can be readily exploited by function approximators. In contrast, in typical implementations the actions are outputs of the neural network and the models do not take advantage of features of the actions. In the standard representation of Dec-POMDPs, actions are defined solely through their effect real world environments they are commonly grounded and can be described with semantic features referring to the object they action on, e.g. "I pull the red lever".
the environment. In contrast, in
3

---

To allow action features be used by the models, we first formalize the concept of observation and action features in Dec-POMMPs. We say a Dec-POMDP has observation features if for at least one player i, object O2 = fu. is described by at most n 2 nj features. Each of these features Sū. where k 1 .... nyj exists in feature space Fk. Similarly, Dec-POMDP has action features if one can factor the representation of the actions. In this case, at time t. the action player i takes can be represented as a: = (fi.....fe fm). where each action feature f. E Fr. = ..., m. and F, is the action feature space. Note that this representation typically is function of the current state, e.g- Under review as a conference paper at ICLR 2022
factor the observation (s)(s) into objects (s) (O) ................................ Or). where each
an agent might always have 5 actions available (pulling given lever), but the color of the levers available is contextual.
In some Dec-POMDPss the actions can further be described using some of the same features that describe the observations, for example when an agent can both observe the "red" light and pull the "red" lever. In these cases there is a non-empty intersection between F& and F, ('shared action- observation features") which can be exploited for coordination. We note that in generality the action space may also include actions that act on sets of objects. While our formalism can be naturally extended to cover this, we will omit it here for brevity since it's not needed for our examples.
THE HINT-GUESS GAME
Implicature
Exact Match
Feature Similarity
Mutual Exclusivity
similarity + Exclusivity
1 AA
2
1
3 C
1
3
2
Hinter
A
1
2
2
3
1
2
Guesser
B
A
B
Figure 2: Example scenarios in the bint-guess game. The Hinter and Guesser are dealt hand of cards where each card has a randomly sampled letter [A-C] and number [1-3]. All cards are visible to both players. Only the Hinter knows which of the Guesser's cards is the target card, outlined with a dotted red line above. The goal of the game is for the Guesser to select the target card but the only actions the /finter can take is to point to one of their own cards. Shown above are four hand crafted scenarios that test distinct dimensions important for zero-shot coordination. The highlighted yellow card corresponds
human interpretable choice. The two right scenarios require agents to reason about implicatures, i.e., the interpretable choice has zero feature overlap with the target card. Model performance is shown in Table 2
We develop novel Dec- POMDP with shared actions and observation features study coordination in this setting. Our environment is two player game called the "hint-guess" game where players must coordinate in order successfully guess target card. The game consists of a Hinter and Guesser. Both players are given a hand of N cards, Hi = {C),... ...C.N for the Hinter and H₂ = {C?....CC for the Guesser. Each card marked by two features f2) where fi E F1 and f2 E F2. Cards in each hand are drawn independently and randomly with replacement, with equal probability for any feature combination. Both hands, H1 and Hz. are public information and are exposed both players. Before the game starts, one card of the Guesser, C? is randomly chosen to be the target card and its features are revealed to the Hinter, but not the Guesser.
In the first round, the Hinter (who observes H1, H2, CP) chooses a card of its own, call it CJ, to show to the Guesser. And in the second round, the Guesser (who observes H1, H2 and the features of C}) guesses which of its cards is the target. Both players receive common reward 1 if the features of the card played match those of the target, and otherwise r =
Figure 2 shows some simple scenarios that probe key dimensions of coordination with N = 2, FT, 2, 3} and F2 = {A, B, C). Each of these scenarios have a human- -amaaninterpretabble solution. The first scenario (Exact Match) is the most simple, the Hinter has a copy of the target card, 2B, so they can just hint 2B. Note that while this strategy is humaa interpretable, the opposite convention would work in this particular case. The next scenario (Feature Similarity) requires reasoning about
4

---

Under review as a conference paper at ICLR 2022
the features under some ambiguity since none of the cards in the two hands are direct match. In this case, both cards in the Hinter's 's hand share one feature with the Guesser. The cumaa--nterpretabbe strategy would be to match the cards that share features to each other. Although like before the exactly opposite strategy would also work well.
We also develop stimuli that require more sophisticated inferences (labeled implicatures in Figure 2 Implicatures require understanding the action embedded within its context. The third scenario (mu- tual exclusivity) invokes simple kind of implicature: mutual exclusivity. In this scenario, human- interpretable reasoning follows the logic of: "if the target card was IB, the Hinter would choose IB that means 1B taken and 3C should correspond to 2A even though they share zero feature overlap. The final scenario combines feature similarity and mutual exclusivity. These scenarios are particularly interesting because deep learning models often struggle effectively grapple with mutual exclusivity (Gandhi & Lake 2020).
6 THE EFFECT OF ARCHITECTURE CHOICE ON ZERO-SHOT COORDINATION
We consider the following architectures to investigate the effect of policy parameterization on the agents' ability to exploit shared action-and observation features for ZSC.
Deep Q-Learning (DQN). We first use standard DQN with feedforward neural networks (NN), All observations are concatenated and fed into an NN, which outputs the estimated Q-value for each action. There is no explicit representation of obstev-ibbervation relationships in this model, since observations are inputs and actions are outputs. E.g. for multi-layer perceptrons (MLP) the inputs and outputs can be permuted arbitrarily whiteout changing the learning problem.
Recurrent Deep Q-Learning (RDQN). In the RDQN model, we feed objects in the observation (namely, vectors representing cards) sequentially to long short-term memory (LSTM) network (Hochreiter Schmidhuber, 1997). To improve trainability we concatenate all hidden states from each step and use that as input to feedforward NN, noting that this is unconventional. Like the MLP, the LSTM does not explicitly model the relationship between action and observation features.
Attention Mechanisms. The core of attention is the dot product, which is fundamentally compar- ative operator. As such, it is natural to explore attention for ZSC in our setting and in the following present three different options for attention-based architectures. While the attention mechanism the same for all three architectures, they differ in terms of their overall design and we will see that these differences are highly relevant for the learning outcomes. Let Attention(-) denote the attention layer as introduced in Section 3
Attention for Observation (Obs). The first model feeds observations into the attention layer, then the flattened output is passed through a simple ReLU feedforward layer and produces the estimated Q-values for all actions an output.
S = Attention
P RS)
where are the estimated Q-values for of the actions.
Attention with Action as Output (Action-Out). In order to more explicitly represent the relational structure, we take the dot product of a linear transform of the attention layer and an embedding vector for each of the actions.
S Attention(O,......)
P = Linear(S) Linear(A),
where Linear(X (X) XW b, where W is the weight matrix and b is the bias term.
Attention with Action as Input (Action-In). Next we extend this architecture to take advantage of shared features between observations and actions. We feed feature based representation for given action (one at a time) into the attention mechanism along with the observation. This outputs single scalar value at time, the estimated Q-value for the specific action being fed into the network.
S = Attention CointtionnOn...... (O,...., On, As) for l: 1,...,m
P = Linear(S.) Linear (-m))
5

---

Under review as a conference paper at ICLR 2022
To be clear, this architecture will take N forward passes (one per action) to calculate the Q-values for all actions.
EXPERIMENTS
We evaluate the architectures in the hint-guest game mentioned Section 5 size N = and the features be Fi = {1, 3) and F2 {A, B, C). As shown in Appendix A.4 similar results can be obtained with a larger or smaller hand size. We use a two-hot vector to represent the features of each card. The observation input is concatenation of these representations for both hands, H1 and 2, with the vector representing the target card, C and hinted card Cj- We evaluate the agents' performance and behavior in both self-play, zero-shot coordination setting, and ability to match the human interpretable response in four scenarios.
We fix the hand
We train agents in the standard self-play setting using independent Q-learning (Tan 1993) where the Hinter and Guesser are jointly trained to maximize their score in 4M randomly iittaaizeed games. To avoid giving the set- set-based attention architectures an unfair advantage, we independently permute the cards observed by the agents so they are not able to coordinate using the position of the cards. More details about training setup and the model architectures can be found in Appendix A.
RESULTS
CROSS-PLAY PERFORMANCE.
DON
NOON Gemei
Obs (N) Game))
Acsen-OLe Gemet
Acsoedo thui Gamal
AzenerAgert
Tayer
GumoerAgert
Hlgor Gusaua Apert
DON (Sams condiion
isae laad 1..
iSama Hand Consi
Actlen-Du Same landiioctionn ond 12
Actien-in (Seme lland 21
2.3
Payer 2: Guesser Agen
Raye 2. GammerAgene
Payer 2. GLEESE Agun:
Raye GasterrAger
Flyer Guester Ago
Figure 3: Cross-play performance. Visualization of paired evaluation of different agents trained under the same method. The top row is the result for the full hint-guess game and the bottom row the result for simplified game where the Hinter and Guesser agents always dealt the exact same hand. The y-axis represents the agent index of the Hinter and the x-axis represents the agent index of the Guesser. Each block in the grid is obtained by evaluating the pair of agents on 10K games with different random seeds. Numerical performance is shown in Table
First, we evaluate model performance for each architecture in the cross-play (XP) setting. In this set- ting, agents from independent training runs with different random seeds are paired together. Clearly, high XP performance is prerequisite or necessary (but not sufficient) condition for coordinating with other Al agents or humans. If agents trained from independent runs using the same model and training algorithm cannot coordinate with each other, it is highly unlikely they will be able to coor- dinate with agents built with different architectures trained using different procedures and even less likely they will be able to coordinate with people (Hu et al. 2020).
Figure the scores obtained by each pair of agents, where the diagonal entries are the within- pair SP scores and the off-diagonal entries are XP scores. The bottom row shows the same results for simplified version of the game, where both Hinter and Guesser have the same hand. In the

---

Under review as a conference paper at ICLR 2022
simplified game, optimal and intuitive strategy exists, which is to always hint the target card and then guess the card that is hinted. Table summarizes average SP and XP scores across agents.
From the top row of Figure 3 (i.c., the full game setting), one immediately notices that while the XP performance all architectures except Action-In lack an interpretable pattern. Most of the archi- tectures at chance. However, the XP matrix for the Action-In model splits into two clusters. Within the clusters, agents show XP performance almost identical to SP, implying that they coor- dinate nearly perfectly with other agents trained with a different seed, whereas outside the clusters they achieve a return close to O. As we will show in the next section, the upper cluster that has higher average XP score corresponds to the strategy where agents maximize the "similarity" between the target card and the hint card, as well as between the hint card and the guess card. In the lower, sec- ond cluster, agents try to do the opposite. They try to hint/guess cards that ideally share no common feature with the target/hint cards. In the rest of the paper, we will refer to the cluster where agents try to maximize the similarity between cards as Cluster 1, and the cluster where agents try to maximize the dissimilarity as Cluster 2. However, just maximize/minimize feature similarity; they also demonstrate more sophisticated coordination patterns that exploit mutual exclusivity and implicature.
shall see in section 8.3 the Action-In agents do not
In the bottom row of Figure (i.e., the same hand condition). DQN and RDQN also have better scores than they are in the full game. This is likely because in the simplified setting, optimal so- lution that always guarantees reward exists, and therefore the agents do not need to take advantage of features converge to that solution. Action-In still splits into clusters; cluster 1 (hint "similar") has perfect scores for SP and XP since it is the optimal solution, and cluster 2 (hint "disimilar") is sub-optimal as agents may not tie-break when there are multiple cards the can hint/guess.
The top rows of and RDQN do not take explicit advantage of shared action and observation features which results in agents that perform well in SP but have XP scores close to chance. As we shall show shortly, they exploit features arbitrarily, resulting in miscoordination in XP. The Obs agent behaves similarly to the DQN/RDQN agents. The Action-Out and Action-In agents, on the other hand, have lower SP scores that are close to their XP scores. This is because they learn simpler conventions using common features in the observations and actions. In other words, they achieve SP-XP trade-off using the inherent inductive bias in the attention architecture.
XP and SP scores across model architectures. We see that DQN
Full Game
Same Hand Condition
Method
Cross-Play
Self-Play
Cross-Play
Self-Play
DQN
0.27 4 0.13
0.85 + 0.02
0.79 + 0.09
0.98 0.08
RDQN
0.30 + 0.15
0.86
0.02
0.68 + 0.10
0.98 0.03
Obs
0.27 + 0.12
0.87 0.03
0.29 + 0.14
0.03
Action-Out
0.26 0.10
0.76 0.05
0.27 0.16
0.82 0.08
Action-In
0.37 0.35
0.76 0.05
0.45 0.47
0.90
Action-In (Cluster I)
0.77 0.02
+.02
1.00 +.00
1.00
In (Cluster 2)
0.71
0.72
0.73 - 0.03
0.73
OP
0.35 4 0.02
0.35
+ 0.02
0.84 0.02
0.95 + 0.01
OBL (level 1)
0.27 + 0.05
0.29
- 0.06
0.30 - 0.05
0.29 0.05
OBL (level 2)
0.28 + 0.04
0.28 - 0.05
0.27 + 0.05
0.29 + 0.05
Table 1: Cross-play performance. We show results for both the full hint-guess game and the same hand condition. Each entry is the average performance is of 20 pairs of agents that are trained with different random seeds. Please refer to Fig. 3 for visualization of performance for each individual pair. Cross-Play score is the nondiagonal mean of each grid. Self-Play score is the diagonal mean, i.e. the score attained when agents play with the peer they are trained with.
8.2 COMPARISON WITH ZSC BASELINES.
In the bottom rows of Table methods Other-Play (OP) (Hu et al. 2020) and Off-Belief Learning (OBL) (Hu et al. 202T). For details and implementation of the baselines, see Appendix. A.3.
also show the SP and XP results for two recent baseline ZSC
7

---

Under review as a conference paper at ICLR 2022
We that the XP scores for OP agents only show marginal improvement over DQN agents. By preventing arbitrary symmetry breaking, OP improves XP performance, but only to limited extent. In contrast, the OBL agents fail to obtain scores beyond chance. This is expected as OBL explicitly avoids cheap talk, which is the key for coordination in the hint-guess game.
8.3 POLICY EVALUATION.
Paym Hee
Paym Hil
Pey
Nemn1 For Younga
for
Paye Dana Call
Payer Gane
Payer Gene Call
Gene
Flar Camo
Figure 4: Policy Evaluation. The top row shows the conditional probability for the Hinter to hint a particular card (X-axis) when the target card is the card on the y-axis. The bottom row is the conditional probability matrix for the Guesser to guess particular card (x-axis) when the hinted card is the card on the y-axis, Each subplot the sample average of 20 agent-pairs with different seeds for IK games within pair.
Next, we evaluate the policies of agents in more detail. In Figure 4 we provide the conditional probability for the Hinter to hint a card given the target card it sees (top row) and the conditional probability for the Guesser to guess a card given the hint card it sees (bottom row).
We analyze whether agents assign different probabilities actions based on the features they share with the observation. We see that for DQN, RDQN and Obs, the probability matrices for both target-hint and hint-guess are nearly uniform. The probability for the Hinter to hint LA is the same no matter the target card is exactly 1A, or 3C' that shares no feature in common with 1 A across seeds. This implies that the SP policies across seeds each form their own private language for arbitrary and undecipherable coordination.
In contrast, for Action-Out, the probability matrix visually less uniform (although still quite noisy). Indeed, in the target-hint matrix we can see that the Hinter will tend to hint 14 if it has 1A, 2B it has 1B, 1C if it has 1C, etc. In sum, Action-Out agents relatively prefer actions that more "similar" to the observation.
For the two clusters of the Ic model this tendency is much stronger. For cluster we see that both the Hinter and the Guesser prioritize acting with the card that is exact match of the target/hint. If the exact match is not available, they turn to cards that share one feature in common. Hence, cluster agents are solving max Eie(, T(fe = fi). where II is the indicator function, fa / f. are the two observation and action features. For cluster we see that agents do exactly the opposite they solve min E (1.)) I(f: = fi), and therefore put equal probability on cards that share nothing in common with the target/hint cards. In summary, the two clusters represent two equilibria Action- In agents converge in this game maximizing or minimizing the feature -imuurr-immilaitty between the observation and the action.
8.4 SCENARIO ANALYSIS
We move on to examine in a fine-grained way whether the agents in the two clusters of the Action- In models exhibit more sophisticated behavior beyond simply minimizing/maximizing the distance between features. Here we run simulations on the four scenarios shown in Figure 2 and described in Section 5 We find that the agents in cluster of Action-In demonstrate coordination patterns that are nearly identical to the human human-interpe interpretable response. These results are surprising given that our models have never been trained with any human data. Furthermore, mutual exclusivity was thought
8

---

Under review as a conference paper at ICLR 2022
Self-Play (cluster 1)
Cross- Cross-Play (cluster 1)
Self-Play (cluster 2)
Cross-Play Play (cluster 2)
Scenario
% Human
% Win
Human
% Win
% Human
% Win
% Human
Win
Exact match
100.0%
100.0%
100.0%
100.0%
0.0%
100.0%
0.0%
100.0%
Feature similarity
100.0%
100.0%
100.0%
100.0%
0.0%
100.0%
0.0%
100.0%
Mutual exclusivity
100.0%
100.0%
100.0%
100.0%
9.3%
91.2%
9.3%
92.2%
Similurity Exclusivity
92.0%
91.7%
97.9%
99.5%
3.2%
98.4%
0.0%
99.9%
Table 2: Behavioral analysis for the Action-In model in the Figure 2 scenarios. We randomly chose
10 agent-pairs from each cluster and simulated the same scenario IK times. % Human denotes the fraction of games where the Hinter hints the card that corresponds human interpretable choice (highlighted in yellow in Fig. 2 and % Win denotes the fraction of games where the Guesser correctly guesses.
to be hard for deep learning models to learn (Gandhi & Lake 2020). In contrast, agents in cluster always perform actions that are the opposite the human interpretable policy.
8.5 HUMAN- LUMAN-BASED EXPERIMENTS
We recruited 10 university students to play the hint-guess game. Each subject played as Hinter for 15 randomly generated games, totaling 150 different games. These subjects are then cross crossematched to play Guessers with the hints they generated. The human hints are also fed into randomly chosen Guesser agents from Action-In Cluster and DQN models to test Al performance against human partners. Throughout the experiment, measures are taken to ensure that agents play zero-shot, and further details of the experiment design are available in Appendix A.2
Human/human (#linter/Guesser)) obtained an average score of 0.75 (s.e. 0.04), and human/Action In obtained an average score of 0.77 (s.e. 0.05). In contrast, the DQN agents obtained a score of 0.30 (s.e. 0.03). In 121 (80.7%) of the 150 games, Action-In Guessers chose the same guesses as human guessers, whereas in only 40.7% of the time the DQN Guessers agreed with humans. In summary, the Action-In Guessers perform comparable to human Guessers when given the same human-generated hints, and in most cases, both types agree on the same guesses.
CONCLUSION AND FURTHER RESEARCH
We investigated the effect of network architectures on the ability of learning algorithms to make use of the semantic relationships between shared features across actions and observations in the context of zero-shot coordination. We compared the behavior of agents with feedforward, recurrent, and attention-base architectures and find that attention-based architectures that jointly process a featurized representation of the observation and the action have a better inductive bias for exploiting this relationship. This results in high cross -lay performance as well as numan-compatte in our novel hint-guess game, which we introduced
policies test bed for coordination.
Our work points to a number of exciting future research directions. First, while we have focused on the hint-guest game, which is specifically designed challenge for exploiting features for coordina- tion, our attention-basee method can also be tested with humans in more complex settings, e.g. in the benchmark games Hanabi Overcooked (Carroll et al. 2019). Second, currently assume that action features are provided as part of the problem setting. However, we believe that it would be interesting for future work learn to discover these features from high dimensional inputs, such as images and texts. Third, humans are able to use similarity across different modalities (vision and phonetic sound in the "Bouba" and "Kiki" example) using abstract representations of learned features, and how Al can do this represents another direction for future work. Finally, we observe that, as an emergent behavior, the Action-In agents form two clusters and it would be interesting for future work to investigate the mechanisms behind cluster formation and whether clusters with different behavioral patterns would emerge in games with different dynamics.
To summarize, we believe our work shows early, intriguing results and also opens number of exciting directions for future research to explored by the community.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning align and translate. International Conference on Learning Representations, 2015.
Nolan Bard, Jakob N Foerster, Sarath Chandar, Neil Burch, Mare Lanctot, H Francis Song, Emilio Parisotto, Vincent Dumoulin, Subhodeep Moitra, Edward Hughes, lain Dunning, Shibl Mourad, Hugo Larochelle, Mare G Bellemare, and Michael Bowling. The hanabi challenge: A new frontier for ai research. Artificial Intelligence, 2019. doi: 10.1016/f.artint.200 2019.10316..
Samuel Barrett, Peter Stone, and Sarit Kraus. Empirical evaluation of ad hoc teamwork in the pursuit domain. In AAMAS, pp. 567-574, 2011.
Colin Camerer. Behavioral game theory: Experiments in strategic interaction. Princeton univer- sity press, 2011.
Colin F Camerer, Teck-Hua Ho, and Juin-Kuan Chong. cognitive hierarchy model of games. The Quarterly Journal of Economics, 119(3)8611889) 2004.
Micah Carroli, Rohin Shah, Mark K Ho, Tom Griffiths, Sanjit Seshia, Pieter Abbeel, and Anca Dragan. On the utility of learning about humans for human-ai coordination. Advances Neural Information Processing Systems, 32:5174-5185, 2019.
Allan Dafoe, Edward Hughes, Yoram Bachrach, Tantum Collins, Kevin R McKee, Joel Z Leibo, Kate Larson, and Thore Graepel. Open problems in cooperative ai. arXiv preprint arXiv:2012.086630, 2020.
Cícero Nogueira dos Santos, Ming Tan, Bing Xiang, and Bowen Zhou, Attentive pooling networks. CoRR, abs/1602.03669, 2016. URL http: /ttppi///axiv....
03609
Michael C Frank and Noah D Goodman. Predicting pragmatic reasoning in language games. Sci- ence, 336(6084):998 99889998999999999999999988998..9 2012.
Kanishk Gandhi and Brenden M Lake. Mutual exclusivity as a challenge for deep neural networks. Advances in Neural Information Processing Systems, 33, 2020.
Noah D Goodman and Andreas Stuhlmüller. Knowledge and implicature: Modeling language un- derstanding as social cognition. Topics in cognitive science, 5(1):133-184, 2013.
Herbert P Grice. Logic and conversation. In Speech acts, pp. 41-58. Brill, 1975.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural Comput., 9(8): doi: 10. 20.116//eeo0.19999...
1735- November 1997. ISSN 0899-7667.
URL
https://don /11 11 621111/////e wwtpee/....ee.eeo/oee/oeeoeeeae 1997.9.8..7335
Hengyuan Hu, Adam Lerer, Alex Peysakhovich, and Jakob Foerster. "Other-Play" for Zero-Shot Coordination. International Conference on Machine Learning, 2020.
Hengyuan Hu, Adam Lerer, Brandon Cui, Luis Pineda, David Wu, Noam Brown, and Jakob Foerster. Off-belief learning. International Conference Machine Learning, 2021.
Hyunjik Kim, Andriy Mnih, Jonathan Schwarz, Marta Garnelo, Ali Eslami, Dan Rosenbaum, Oriol Vinyals, and Yee Whye Teh. Attentive neural processes. International Conference on Learning Representations, 2019.
Max Kleiman- Weiner, Mark K Ho, Joseph Austerweil, Michael Littman, and Joshua Tenen- baum. Coordinate to cooperate or compete: abstract goals and joint intentions in social interac- tion. In CogSci, 2016.
W Köhler. Gestalt psychology. Liveright, 1929.
Adam Lerer and Alexander Peysakhovich. Learning social conventions in markov games. arXiv preprint arXiv: 10071, 2018.
David K Lewis. Convention: A Philosophical Suddy. Blackwell, 1969.
10

---

Under review as a conference paper at ICLR 2022
Ellen M Markman and Gwyn F Wachtel. Children's 's use of mutual exclusivity to constrain the meanings of words. Cognitive Psychology, pp. 121-157, 1988.
Daphne Maurer, Thanujeni Pathman, and Catherine J Mondloch. The shape of boubas: Sound-shape correspondences in toddlers and adults. Developmental science, 9(3): (13:326-.2,, 2006.
Jennifer B Misyak, Tigran Melkonyan, Hossam Zeitoun, and Nick Chater. Unwritten rules: virtual bargaining underpins social interaction, culture, and society. Trends in cognitive sciences, 18(10): 512-519, 2014.
Nair, M Tambe, M Yokoo, D Pynadath, and Marsella. Taming decentralized pomdps: Towards efficient policy computation for multiagent settings. International Joint Conferences Artificial Intelligence, pp. (01-711,222 2003.
Avik Pal, Jonah Philion, Yuan- Hong Liao, and Sanja Fidler. Emergent road rules in multi-agent driving environments. In International Conference on Learning Representations, 2020.
Michael Shum, Max Kleiman- Weeiman-Weiner, Michael Littman, and Joshua Tenenbaum. Theory of minds: Understanding behavior in groups through inverse planning. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pp. 6163-6170, 2019.
Dale O Stahl and Paul W Wilson. On playersmodels of other players: Theory and experimental evidence. Games and Economic Behavior, 10(1):218-25) 254, 1995.
Peter Stone, Gal A Kaminka, Sarit Kraus, and Jeffrey S Rosenschein. Ad hoc autonomous agent teams: Collaboration without pre-coordination. In Twenty-Fourth AAAI Conference on Artificial Intelligence, 2010.
Ming Tan. Multi-agent reinforcement learning: Independent vs. cooperative agents. Proceedings of the tenth international conference machine learning, pp. 330-337, 1993.
Ming Tan, Cicero Dos Santos, Bing Xiang, and Bowen Zhou. Improved representation learning for question answer matching. Annual Meeting of the Association for Computational Linguistics (ACL), pp. 464 473, 01 2016. doi: 10.18653/v 1/P16 1044.
Michael Tomasello. Malinda Carpenter, Josep Call, Tanya Behne, and Henrike Moll. Understanding and sharing intentions: The origins of cultural cognition. Behavioral and brain sciences, 28(5): 675-691, 2005.
Michael Tomasello, Malinda Carpenter, and Ulf Liszkowski. new look at infant pointing. Child development, 78(3):705-722, 2007.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention Is All You Need. Advances in Neural Information Processing Systems, 2017.
Sarah A Wu, Rose E Wang, James A Evans, Joshua B Tenenbaum, David C Parkes, and Max Kleiman-Weiner. Too many cooks: Bayesian inference for coordinating multi-agent collabora- tion. Topics in Cognitive Science, 13(2):414432, 2021.
Kelvin Xu, Jimmy Ba, Ryan Kiros, Kyunghyun Cho, Aaron Courville, Ruslan Salakhutdinov, Richard Zemel, and Yoshua Bengio. Show, attend and tell: Neural image caption generation with visual attention. International Conference on Machine Learning, 2016.
Liu Yang, Qingyao Ai, J. Guo, and William Bruce Croft. ammm: Ranking short answer texts with attention-based neural matching model. Proceedings of the 25th ACM International on Confer- ence on Information and Knowledge Management, 2016.
H Peyton Young. The evolution of conventions. Econometrica: Journal of the Econometric Society, pp. 57-84, 1993.
11

---

Under review as a conference paper at ICLR 2022
A APPENDIX
A.1 TRAINING AND MODEL ARCHITECTURE DETAILS
Training Setup. We use standard experience-replay with replay memory of size 300K. For optimization, we use the mean squared error loss, stochastic gradient descent with learning rate set to 10-4 and minibatches of size 500 each. To allow more data be collected between training steps, we update the network only after receive 500 new observations rather than after every observation. We use the standard exponential decay scheme with exploration rate cm (Eo- Em) exp(-n/K), where n is the number of episodes, cm 0.01, éo 0.95, and = 50, 000. All experiments were run on two computing nodes with 256GB of memory and a 28-Core Intel 2.4GHz CPU. A single training run takes roughly hours for the Action-In model and 2 hours for all other models. All Hinters and Guessers have the same model structure.
Tranning play!
Figure 5: Training performance of dif- ferent architectures for the hint-guess game. The x-axis is the number of episodes and y-axis is the mean training reward. Solid line is the mean, shading is the standard error of the mean (s.e.m) across 20 different seeds.
RDOM
Accissin
302
3.00
2.0
The model architecture details are as follows:
Deep Q-Learning (DQN). The DQN agent is a feedforward ReLU NN with 3 hidden layers (width 128).
Recurrent Deep Q-Learning (RDQN). The RDQN agent has an LSTM layer with 128 LSTM units followed by two fully-connecteo layers with 128 ReLU units. The input of the RDQN agent the same as that of the DQN agent but vectors representing the cards are fed in sequentially to the LSTM before we concatenate hidden states from each step and use that as input
feedforward NN.
Attention Models. All three attention-based models share the same single-head attention layer with size determined by the shapes of the input and output. We do not add position encoding. In Obs, we add a feedforward ReI.U NN with 3 hidden layers (width 128) after the attention layer. In Action-Out and Action-In, In, we do not add extra ReLU layers.
12

---

Under review as a conference paper at ICLR 2022
A.2 DESIGN OF HUMAN-BASED EXPERIMENTS
In this section we provide details of the design of human-based experiments.
We recruited 10 individuals who are undergraduate and master students university. The instruc- tions they received include: (i) rules of the hint-guess game; (ii) that they need to assume they are playing against Guesser who is an ordinary human (they are not told that they would play against AI bots); (iii) that the position of the cards are permuted so they cannot provide/interpret hints based on card position, and (iv) if two cards have the same features they are effectively the same,
After they showed understanding of the instructions, the subjects were asked to act as Hinters. Each subject was provided with 15 randomly generated games with F1 2, 2), F2 {A, C" and N = 5. They were presented with both hands and the target card and were asked to write down their hints. sample question they received was:
Playable card is: 2B
Your (hinter) hand is: 1C, 1B, 3B, 2C, 1A
Guesser hand is: 1B, 2C, 2B, 2C, 2B
Please choose hint card from YOUR OWN hand!
After the subjects provided hints, they were given no feedback to ensure that they could not learn about the agent they are playing with; this would ensure that their actions are zero-shot.
Then we used the hints provided by the subjects to obtain human/human (Hfitter/uuesser) and hu- man/Al scores. To obtain human/human scores, we randomly mix-matched the subjects so that each subject would now act the Guesser for 15 games generated by another human subject. This time, they were provided with both hands and the human hint, and were ask to choose one card to play. Same before, they did not receive any feedback about their guesses to ensure zero-shot.
To obtain human//Acion-- and human/DQN scores, we reproduced the 150 games and fed human hints to randomly sampled Action-In/DQN Guesser agents.
13

---

Under review as a conference paper at ICLR 2022
A.3 DETAILS OF ZSC BASELINES
In this section we provide implementation details of Other-Play (Hu et al. 2020) and Off-Belief
Learning (Hu et al. 202T), IWO recent zero-shot coordination (ZSC) methods that we use base- lines.
Other-Play (OP). The goal of OP is to find strategy that robust partners breaking symmetries in different ways. To achieve this, it uses reinforcement learning to maximize returns when each agent matched with agents playing the same policy, but under random relabeling of states and actions under known symmetries of the Dec-POMDP (Hu et al. (020). To apply OP, we change the objective function of the hinter from the standard self-play (SP) learning rule objective
arg max J (m², ,x?)
To the OP objective
n arg max E ( (T²))
(2)
where the expectation is taken with respect to a uniform distribution on Φ. where & describes the symmetries in the underlying Dec-POMDP (in the hint-and-play games, the symmetries are the two features).
As OP only changes the objective function, can be applied on top of any SP algorithm. We choose to apply OP on top of the DQN architecture, using the same training method as detailed in Appendix. A. and change the objective the OP objective. In implementation, this means that the guesser will receive a feature-permuted version of the game, i.e. feature 1 and feature 2 (the letters and the numbers) of the hands and the hint that the guesser receives will be a permuted version of what the hinter originally receives.
Off-Belief Learning (OBL). OBL (Hu et al. 2021) regularizes agents' ability to make inferences based the behavior of others by forcing the agents optimize their policy Ti assuming past actions were taken by given fixed policy To. while in the same time assuming that future actions will be taken by गi In practice, OBL can be iterated in hierarchical order, where the optimal policy from the lower level becomes the input to the next higher level.
We apply OBL on DON agents and keep the training setup the same in Appendix A.I At the lowest level (level 1), OBL agents assume To is the policies where actions are chosen uniformly at random, And OBL level 2 assumes the policy from OBL level I is the new To and forth.
14

---

Under review as a conference paper at ICLR 2022
A.4 EFFECT OF HAND SIZE ON PERFORMANCE
In this section we analyze the effect of hand size on agents' self-play and cross-play performance.
We fix the features to be Fi {1, 2, 3) and F2 {A, B, C} and run experiments with hand size N = {3, 7), as opposed to = 5 in the main text. As shown in the following Table 3 SP and XP results largely confirm our findings for = 5.
Full Game (N 3)
Same Hand Condition
Method
Cross-Play
Self-Play
Cross-Play
Self-Play
DQN
0.47 = 0.19
0.92 = 0.01
0.87 = 0.11
0.98 = 0.04
RDQN
0.47 # 0.20
0.01
0.70 = 0.12
0.99 = 0.01
Obs
0.47 + 0.17
0.92
0
0.95 + 0.03
Action-Out
0.38 0.14
0.81 0.01
0.46
0.88 0.12
Action-In
0.43 + 0.36
0.45 0.80 0.01
0.95
Action-In (Cluster
0.81 0.02
1.00 1.00
Action-In (Cluster 2)
0.80 + 0.01
0.80=
0.89
0.90
OP
- 0.55
0.54 0.04
0.90
0 = 0.01
OBL (level 1)
0.47 0.07
0.44 = 0.06
0.47 = 0.03
0.48 0.03
OBL (level 2)
0.47 + 0.04
0.46 0.06
0.47 + 0.05
0.47 + 0.05
Full Game (N = 7)
Same Hand Condition
Method
Cross-Pla Play
Self-Play
Cross-Play
Self-Play
DQN
0.22 4 0.08
0.72 0.03
0.77 + 0.10
0.96 + 0.08
RDQN
0.25 + 0.09
0.76
0.62 0.14
0.95 0.05
Obs
0.24 + 0.09
0.03
0.24 0.08
0.93 0.01
Action-Out
0.22 + 0.11
0.22 +
0.80 = 0.09
Action-In
0.37 + 0.33
0.70
0.40 0.38
0.89 1.191.111
Ac (Cluster 1)
0.78 0.01
0.78
1.00
+
Action-In (Cluster 2)
0.67 + 0.02
0.67
0.67 0.03
0.67 0.02
OP
0.32 + 0.02
+.31
0.00
0.95 0.02
OBL (level 1)
0.21 + 0.04
0.22 = 0.03
0.22 0.03
0.22 - 0.04
OBL (level 2)
0.24 + 0.03
0.22 + 0.03
0.22 + 0.03
0.25 + 0.02
Table 3: Cross-play performance for card number N and N = 7. We show results for both the full hint-guess game and the simplified version where both agents have the same hand. Fach entry is the average performance is of 20 pairs of agents that trained with different random seeds. Cross-Play score is the nondiagonal mean of each grid. Self-Play score is the diagonal mean, i.e. the score attained when agents play with the peer they are trained with.
15


Reviews:
[{"review_id": "ezsQo8nHQZ", "reviewer": "Reviewer_JS7v", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "\nThe paper shows that in the case of the proposed new game, that\n\"attention-based architectures that jointly process a\nfeaturized representation of the observation and the action\" performed\nbetter. The evidence shown supports this claim.\n\nThis paper is quite far from my expertise, and there are a number of\nconfusions I had about the paper:\n- What is special about the new hint-guess game? Does it feature some aspect that\n  the games used in current experiments ignore?\n- Why is it called zero-shot coordination, when there is considerable training\n  using training data that seems virtually identical to the proposed task?\n- What can we generalize from the game/experiments that is valuable for other\n  tasks? In particular, given the goal of having 'human-compatible' learning,\n  how is this addressed?\n- Figure 5 shows the  probability of proposed 'hints' given\nall possible target 'answers'. Is is surprising that they are largely uniform, given that any\npossible card could be the appropriate answer depending on the configuration of the other\ncards?\n\n- In Fig 5, I don't see the connection between the card-selection probabilities\nand the conclusion of 'private languages'. They seem to be 2 different questions and\nI don't see how the results in Fig 5 connects them.\n- Section 8.3 says: \"We find that the agents in cluster 1 of Action-In demonstrate\ncoordination patterns that are nearly identical to the human-interpretable response.\"\nThere are no human-based experiments, and I'm unclear what the evidence is that supports\nthis claim even if there was some human data.\n- The final discussion says \"relies on a majority vote\". I did not see any mention of\na voting mechanism previously.\n- Should the first formula on page 6 be S_k = instead S_i =\n- Do any of the observations from the analysis of the Hint-Guess game apply to other\ncollaboration games?\n- Why were 5 cards chosen as the configuration? Do results vary with other numbers?\n- What is the intuition behind each proposed attention mechanism?\n", "summary_of_the_paper": "This paper explores several architectures for reinforcement-learning in the\ncontext of a newly proposed card game (Hinter-Guesser).\nA number of the architectures seem to have poor performance on the game.\nMoreover, whatever they learn is not compatible with what other learners learn,\nso that they cannot mutually understand Hints & Guesses. The stated aim is:\n\"to build an agent with the capacity to develop these kinds of abstract correspondences during\nself-play such that they can robustly succeed during cross-play or during play with people.\"\nThe architectures generally succeed (70-90%) at playing against themselves (with the shared learned\npolicy) but perform badly when playing with independently trained agents,\nexcept when trained with the desired action as part of the input (unclear how\nthis can be tested on unknown cases when 'answer' is given as part of the\ninputs).\n\n", "summary_of_the_review": "The proposed approach works for this bespoke game. It would be good to have more evidence that the approach is generally useful.", "strength_and_weaknesses": "", "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": "TOliz1VbG8b", "reviewer": "Reviewer_CXsY", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "Strengths:\n* The introduction is nicely written and introduces ample motivation from multiple backgrounds.\n* The proposed task is very clearly described, as well as scenarios of interests / challenges.\n* Experiment visualization is very informative, showcasing interesting dichotomy of self-play vs cross-play performances.\n* The experiments seem to have enough details and reproducible.\n\nWeakness:\n* I feel like section 3 and 4 a bit verbose. Even for me, someone not in the specific field of multi-agent RL, the text seems a bit redundant.\n* Notation in section 4 is not really clear, with some notation overloading / ambiguity. For example, the number of players n is overloaded with each object's number of feature n. \n* No baseline in ZSC is considered. In related work, it's mentioned that prior work needs some experimenter-coded input. But I don't see why similar baseline can't be examined here, either as a baseline or an upper-bound.\n* The motivation behind having same-hand setup is unclear to me.", "summary_of_the_paper": "The paper introduces a new Zero-shot Coordination (ZSC) task which involves a Hinter and a Guesser and a set of explicit features shared between the two. The paper evaluates several methods and conclude that an attention mechanism that put attention on both observation and action features is helpful to produce agents that are successful in cross play.", "summary_of_the_review": "Though I'm not an expert in multi-agent RL, I think the work will be interesting to the field. \nThe paper offers an interesting study showing that action and observation information should both be leveraged to form interesting communication / coordination strategy.\nHowever, the paper is limited by the features are explicitly available, making strategy generation less impressive.", "strength_and_weaknesses": "", "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": "NNksS68YBIL", "reviewer": "Reviewer_rNES", "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": "The paper presents a nice conceptual overview about the need for human compatibility of actions associated with observations in zero shot coordination scenarios. They list the problems that arise when statistically independent actions are assigned to observations. The resulting disconnect not only affects human interpretability, but also lacks consistency during cross-play in cooperative games such Hanabi.\n\nThe proposed approach for zero-shot coordination learns to assign actions to observations in a semantically meaningful way. To produce semantic actions, the action feature is embedded along with the observation to predict contextualized action. The method itself is not new, and is a standard technique employed in many language and vision tasks such as matching models, where the query is concatenated with the featurized responses before passing them through a classification network that predicts the responses. It is surprising that the idea has not been explored in POMDP networks before, and a more comprehensive related work section could help in understanding why this is the case.\n\nThe paper points to several logical primitives used in the game play by humans, such as exact match, similarity, implicatures such as mutual exclusivity and similarity + exclusivity. There could be several other strategies used during game-play. How many of these strategies are actually learnt by the algorithm? How did the authors find one-to-one correspondence between the human designed strategies, and the statistically learnt strategies? \nA related question is how does the model choose diverse strategies at different times during the game-play. There are no regularizations on policy selection, so one can assume that the model might collapse to learn a single simple strategy e.g., exact match instead of the diverse logic plays. \n\nGiven the the action featurization is weak (just a one-hot vector), how does the method ascertain that the action features are not leaking into the contextualized policy prediction? This looks likely when we look at the clustered results from Action-In experiments, where the model shows two modes - exact similarity and exact dissimilarity. Would the model still work (or probably work better) if higher order embeddings are added to reduce the actual feature distance between input action and output?\n\nThe action-observation relationship is achieved by concatenating the features before passing them through an attention model. The paper does not explain why concatenation + attention module is an ideal choice for modeling the logic, or if any competing designs are worth exploring. Could the features be modeled differently such as within a Bayesian framework, or through deep generative models?  A few methods are mentioned in the related work, but none of them are used as a baseline technique.\n\n\n", "summary_of_the_paper": "The paper proposes an approach for zero-shot coordination that learns to assign actions to observations in a semantically meaningful way. The authors show that semantic actions have a better inductive bias leading to increased consistency in cross-play. Their proposed method is a learning based approach where an attention model jointly processes featurized representation of the observation and the action. The evaluations show that the agents produce human-compatible policies on a simplified Hanabi card game play. \n", "summary_of_the_review": "Strengths:\n1. Topical: Looks into a relatively new problem of generalization during cross play after training using self-play.\n2. Strong conceptual overview and motivation with examples.\n3. Use of attention based embedding for contextualized policy prediction seems to be new in POMDPs, although it has been used in vision and NLP applications before.\n\nWeaknesses:\n1. Weak literature review with very general coverage of the problem space.\n2. Lack of strong baselines - The related work mentions Bayesian/causal reasoning based approaches that are considered too expensive. It might help to show the performance-accuracy tradeoff of those methods vis-a-vis currently proposed approach.\n3. The quantitative evaluations are not well explained / justified. E.g., \n  (a) why does the baseline DQN (simplest model) perform remarkably well for the same hand condition, while the proposed approach has significantly worse accuracy? \n  (b) Why does the proposed approach always converge into two clusters of related cross-plays?\n  (c) How is the diversity of the learnt policies measured? \n\nOverall, although the problem itself is novel, the treatment is not convincing enough and does not meet the bar for an ICLR acceptance yet.\n", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "D4Kgpf4ZICF", "reviewer": "Reviewer_Ba9g", "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": "Strengths:\n1) The paper is well organized. The idea and method are clearly presented. The experiments are conducted in a novel environment (proposed Hint-and-Guess game).\n2) The paper proposes a novel method to extend Dec-POMDP with shared feature representations for both observations and actions.\n3) The paper develops a novel Hint-and-Guess game for evaluating effects of different deep learning architectures.\n\nWeaknesses:\n1) Some details of the experiment setting may need further explanation. It is not clear why the paper fixes hand size N=5 (and feature size) for the game, and how different hand sizes may affect the performance.\n2) More analysis of the results is needed. Why the 13 agents tend to make two clusters with two groups of coordination types? Why these agents form different clusters for the two versions of full game and same hand condition?\n3) What would your method work in other zero-shot coordination games other than your proposed game?", "summary_of_the_paper": "The paper exploits semantic relationships between features of observations and an action for zero-shot coordination in multi-agent reinforcement learning. It extends decentralized partially observable Markov decision process (Dec-POMDP) by representing observations and actions with shared features. Technically it uses attention mechanism of deep learning to exploit the semantic relationships between observations and actions. Besides, the paper develops a novel human interpretable environment for analysis.", "summary_of_the_review": "In summary, the problem tackled in the paper sounds interesting and the idea and method are reasonable and easy to follow. While more explanations and analysis are preferred for the experiments, my current rating leans to acceptance.", "strength_and_weaknesses": "", "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": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The author response addressed some reviewer concerns, and generally reviewers increased their scores. However, there are important, and unanswered concerns about the generalization of the model. The discussion raised the concerns that despite the paper claim of "a specific class of higher order reasoning" emerging, the result suggests relatively simple strategies. This might not be a limitation of the approach, but of the evaluation scenario. So, this either requires a more nuanced view of the findings, and further empirical evidence to support the claim.
Decision: Reject