Diverse Conventions for Human-AI Collaboration
Authors: Bidipta Sarkar
Andy Shih
Dorsa Sadigh
Venue: NeurIPS 2023 poster (2023)
Keywords: Multi-Agent RL
Multi-Agent Coordination
Human-AI Coordination
TL;DR: We present CoMeDi, a technique for generating a diverse set of good-faith conventions in multi-agent coordination games, and demonstrate its utility for human-AI collaboration.

Abstract: Conventions are crucial for strong performance in cooperative multi-agent games, because they allow players to coordinate on a shared strategy without explicit communication. Unfortunately, standard multi-agent reinforcement learning techniques, such as self-play, converge to conventions that are arbitrary and non-diverse, leading to poor generalization when interacting with new partners. In this work, we present a technique for generating diverse conventions by (1) maximizing their rewards during self-play, while (2) minimizing their rewards when playing with previously discovered conventions (cross-play), stimulating conventions to be semantically different. To ensure that learned policies act in good faith despite the adversarial optimization of cross-play, we introduce mixed-play, where an initial state is randomly generated by sampling self-play and cross-play transitions and the player learns to maximize the self-play reward from this initial state. We analyze the benefits of our technique on various multi-agent collaborative games, including Overcooked, and find that our technique can adapt to the conventions of humans, surpassing human-level performance when paired with real users.

Diverse Conventions for Human-AI Collaboration
Bidipta Sarkar Stanford University bidiptas@stanford edu
Andy Shih
Dorsa Sadigh Stanford University
Stanford University andyshih@cs. stanford.
dorsaucs stanford.
Abstract
Conventions are crucial for strong performance in cooperative multi-agent games, because they allow players to coordinate on a shared strategy without explicit communication. Unfortunately, standard multi-agent reinforcement learning tech- niques, such self-play, converge to conventions that are arbitrary and non-diverse, leading to poor generalization when interacting with partners. In this work, we present a technique for generating diverse conventions by (1) maximizing their rewards during self-play, while (2) minimizing their rewards when playing with previously discovered conventions (cross-play), stimulating conventions to be se- mantically different. To ensure that learned policies act in good faith despite the adversarial optimization of cross-pla poosspply,, we introduce mixed-play where an initial state is randomly generated by sampling self self-play and cross-play transitions and the player learns to maximize the self-play reward from this initial state. We analyze the benefits of our technique Overcooked, and find that our technique can adapt to the conventions of humans, surpassing human-level performance when paired with real users."
various multi-agent collaborative games, including
Introduction
In multi-agent cooperative games, understanding the intent of other players is crucial for seamless coordination. For example, imagine game where teams of two players work together to cook meals for customers. Players have to manage the ingredients, use the stove, and deliver meals. As the team works together, they decide how tasks should be allocated among themselves resources are used effectively. For example, player 1 could notice that player tends to stay near the stove, so they instead spend more time preparing ingredients and delivering food, allowing player 2 to continue working at the stove. Through these interactions, the team creates a "convention" in the environment, which is an arbitrary solution recurring coordination problem [20, 3]. the context of reinforcement learning, we can represent specific convention as the joint policy function that each agent uses to choose their action given their own observation. we wish train an Al agent to work well with humans, also needs to be aware of common conventions and be flexible to changing its strategy adapt human behavior [2, 29].
One approach to training an Al agent in a cooperative setting, called self-play [33], mimics the behavior of forming conventions by training team of agents together increase their reward in the environment, causing each player to adapt to the team's 's behavior. Eventually, self-play converges to an equilibrium, where each player's policy maximizes the score if their team does not change.
Unfortunately, self-play results in incredibly brittle policies that cannot work well with humans who may have different conventions [29], including conventions that more intuitive for people to In the cooking task, self-play could converge to a convention that expects player 2 to bring onions to Al player from the right side. If human player instead decides bring onions from the left side to the AI player 1, the Al's policy may not react appropriately since this is not an interaction
'Supplemental videos be found website along with source code and anonymized user study data.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

that the agent has experienced under self-play One way to address this issue is to train diverse set of conventions that representative of the space of all possible conventions. With diverse set of conventions, we can train single agent that will work well with arbitrary conventions or adapt to new conventions when working with humans.
To generate diverse set of policies, prior works have used statistical divergence techniques that measure diversity as the difference in action distributions at each state between policies [9]. They assert that policies that result in different actions at each state will lead players tak- ing different paths in the environment, hence increasing diversity. However, is often easy to trick this proxy objective for diversity by tak- ing different actions that still lead to the same outcome. For example, in Fig. 1, we see two conventions that divide the task in the same way but differ in navigation. Even though this dif- ference does not interfere with the partner and the conventions are perfectly compatible with one another, statistical divergence metrics treat these two policies entirely different. There- fore, statistical diversity techniques do not fun- damentally capture whether the conventions fol- low genuinely different strategies.
Serving Counter
Onions
Dishes
Pots
Figure I: Example of conventions Overcooked.
Each team needs to (1) pick up onions, (2) drop them into pots, (3) fill up a dish, and (4) drop off at the counter. There are 2 conventions shown above, a red convention and an orange convention, which only differ in terms of navigation, they are compatible with one another.
We instead use the incompatibility of different conventions we already have a set of conventions and we want to add a new convention that different from all the conventions we have already found. We can measure the reward we would expect to receive if a player from this new convention played with another player from an existing convention, which we refer to the pross-play reward. If this convention has a high cross-play, adding this convention would be redundant, because a policy from one of the existing conventions would already work with this new convention. On the other hand, convention that has low cross-play with our set of conventions has a different strategy for the game and should be added to the set, because a human player might use that strategy.
measure of diversity [7, 8]. Suppose
Although directly minimizing cross-play rewards takes us closer to our goal of learning diverse con- ventions, it can result in poorly behaved conventions due to the adversarial nature of this optimization. In particular, a failure mode we refer to as handshakes occurs when policies intentionally sabotage the game upon realizing that the task rewards inverted. For example, that players should always pick up and place down a plate at the start of the game, which is considered handshake to establish one's 's identity without significantly decreasing its self-play reward. If player from this convention plays with a partner that does not execute the handshake, this player i can intentionally sabotage the game and achieve low cross-play score even if the fundamental strategies are similar. To fix this issue, we introduce mixed-play a setting where players start with "mixed-state generation" phase in which they sample actions from self-play or cross-play, but transition into pure self-play at random timestep with no notice. Since players receive a positive reward during self-play, handshakes cannot reliably indicate whether they should maximize their reward (self-play) or minimize it (cross-play), resulting in conventions that act in good faith.
convention could decide
We propose the CoMeDi algorithm, which stands for "Cross-pla play optimized, Mixed-pla -layy enforced Diversity." CoMeDi generates a sequence of conventions that minimize the cross-play play with the most compatible prior conventions in the sequence while using mixed-play to regularize the conventions. We evaluate our method on three environments: Blind Bandits, Balance Beam, and Overcooked [5, 34, 26]. We see that CoMeDi is able generate diverse conventions in settings where statistical diversity and naive cross-play fail. Finally, we evaluate our generated pool of conventions in user study by training an agent that is aware of the conventions in the pool and testing with human users in Overcooked. We find that CoMeDi significantly outperforms the pure self-play and statistical diversity baselines in terms of score and user opinions, surpassing human-level performance.

---

2 Preliminaries
We model cooperative games as a multiagent Markov decision process [3]. The MDP, M. is the tuple (S, A, P.r,, O, "; T"), where S is the (joint) state space and A = AA x A is the joint action space. Although we only analyze 2-player games in the main text, we detail an extension larger teams in Appendix A.5. The transition function, P: : S x A x S + [0, 1]. is the probability of reaching a state given a current state and joint action. The reward function, r : S x A + R. gives a real value reward for each state transition. The observation function, O : S - O' x O², generates the player-speciffr observations from the state. Finally, Y is the reward discount factor and T is the horizon.
Player i follows some policy (a') o'). At time i, the MDP is at state 8t E S, so the agents receive the observations (ot,0) ((s,) and sample action from their policy, of a (a; o1)- The environment generates the next time step as St+1 P(s a2, St+1) and the shared reward as r(s,, at). The trajectory is defined as the sequence of states and actions in the environment, which is T
(#o, 40: ... -1, @T-11 1,, 8T). The discounted return for a trajectory is R(()) = Ei' 75r(s1, a.). The expected return for a pair of agent-specific policies is J(x x²) = (=))
For simplicity of exposition, we assume that the agents in the environment are not ordered, so J (TT) =²) = J(x,, m²) for all x n², although our method directly handles situations where order matters.
We refer an instance of the joint policy of the agents n² x n² convention, following the definition of a convention as an arbitrary solution to a recurring coordination problem in literature [20, 3]. When the joint policy forms a Nash equilibrium, we refer as an equilibrium convention, based on some some stricter definitions of conventions in literature [13, 19]. In equilibrium conventions, neither player can get a higher expected score with the current partner by following different policy.
2.1 Problem Definition
In this paper, we study the problem of generating a diverse set D of conventions that are representative of the set of potential conventions in the environment at test time, Dies- To determine how well D generalizes to the test set, we can calculate a "nearest neighbor" score by finding which convention in 1) generates the highest reward for each convention in the test set, which corresponds to S in Eq. (I):
S(D)
[max J(T", [T]. D ED
E
(I)
In practice, we can also treat our generated set D as the set of training policies used to learn generalizable agent [21] for zero-shot coordination. We rely on off-the-shelf multitask training routines [6] for learning the generalizable agent, which have shown to be effective in learning an
agent that can coordinate with new test partners [27, 21J. In particular, given the set D of diverse conventions, we can train convention-awan agent using behavior-cloning [22, 17] in similar fashion to QDagger [1]:
((t,))=-(hh
Σ TED (o.a)~T
E [lo[(*((lo)),
(2)
D
where (o, ~ π represents the distribution of observation-action pairs sampled from self-play rollouts of æ, and is a tunable hyperparameter for the weight of the BC component. At evaluation time, we pair the convention-aware agent म with a new test partner and measure the task reward:
J(ft Dies)
E DE
[J m)]-
For both Eq. (1) and Eq. (3), the test agent distribution Diest may be too expensive to sample from during the training loop, e.g., when this test dataset is based on samples from human users. Instead, we would like to generate a high quality set of training agents that representative of the space of D Intuitively, more diverse D will improve the generalization of the convention-awant Å trained on the multi-task objective in Eq. (2).
A common recipe for generating diverse set D is to train individual agents via standard self-play, and propose a diversity regularization loss that encourages the set to be more "diverse" with respect to the regularization term:
C(D)
Σ [T(TT))] C(D).. RED
3

---

In Eq. (4), the overall loss of the set D is a combination of the diversity regularization C. (scaled by a) and the self-play rewards of the individual agents in the set D. The choice of regularization term C requires a difficult balance hetween tractable computation, alignment to the downstream objective (Eq. (1), Eq. (3)), and ease of optimization of Eq. (4). Section 2.2 and Section 2.4, we highlight some existing diversity metrics and their limitations.
2.2 Statistical Diversity
The majority of prior works on diversity in deep reinforcement learning are based on the principle of maximizing statistical divergence [11. 10, 21, 9, 15]. In the realm of zero-shot coordination, Trajectory Diversity (TrajeDi) [21] uses the
divergence between the trajectories induced by policies as a diversity metric. The method of learning adaptable agent policies (ADAP) [9] maximizes the Ki--divergence between the action distributions of two policies over all states. We compare against ADAP as a baseline by adding its diversity term in Eq. (5) to the MAPPO algorithm [36]:
CADAP (D) = E
E TID 5f
exp(-DKr. (T (s)][=(()))
(5)
While statistical divergence techniques are computationally simple, they do not use the task reward and thus can be poorly aligned with the downstream objectives in Eq. (1) and Eq. (3). For example, consider the introductory Overcooked example in Fig. There are many possible routes that
the players can take to complete their individual task, leading to distinct but semantically similar trajectories. Ideally, we want a diversity regularizer to penalize trivial variations that are irrelevant to the task at hand. Unfortunately, statistical diversity would fail to recognize these semantic similarities.
2.3 Cross-Play Minimization Diversity
Recent work on generating strong zero-shot agents in cooperative games have also used the idea of generating diverse set of conventions by minimizing cross-play. The LIPO algorithm [7] follows a similar approach our baseline cross-play minimization algorithm described in Section 3.1, but does not fundamentally tackle the issue of handshakes described in Section 3.2. The ADVERSITY algorithm [8] also follows an approach of minimizing cross-play scores, but addresses the issue of handshakes in Hanabi through a belief reinterpretation process using the fact that it is a partially observable game. Unfortunately, the ADVERSITY algorithm would not function in our fully observable settings since there is no hidden state for belief reinterpretation. We provide a more detailed comparison of our approach to these prior works in Appendix C.
2.4 Other Approaches to Diversity
Other prior works attempt to modify the training domain to induce variety of conventions [32, 35, 23]. A common aspect to modify is the reward, which can be randomized [32] or shaped by having an external agent try to motivate certain behavior [35]. This requires extra effort from an environment designer to specify the space of the reward function, which may be impractical in complex environments. Additional approaches using population-
training modify pre-specified aspects of the environment to generate set of agents [16], or generate agents using different random seeds but require human to manually select diverse agents [31]. Another set of work focuses on the easier setting of using imitation learning to learn to play with humans [18, 30, 28], but this assumes access to potentially expensive human behavioral data.
We do not explicitly compare CoMeDi to these other approaches in the main text because they assume access to the internal mechanisms of the environment or require external data, so they are not drop-in replacements for self-play, unlike CoMeDi or statistical diversity techniques.
3 Method
Given the drawbacks of current statistical diversity methods at penalizing semantically similar trajectories, we seek alternative diversity regularization terms that can recognize semantically diverse behavior from trivial variations in trajectory space. A good mechanism for identifying trivial variations

---

is through task reward: if swapping the behavior of two agents does not affect the attained task reward, then the differences between their behavior are likely irrelevant the task at hand. For example, consider the effect of the blue player following the red trajectory while the green player follows the orange trajectory in Fig. 1. The swapped teams will still attain the same high reward as the players following the same color trajectories, suggesting that these behaviors are not semantically different.
With this insight, we look to measure cross-play, the task reward attained when pairing together players that were trained separately. We propose a diversity regularization based on minimizing cross-play reward, and describe its benefits compared statistical diversity. However, pure cross-play faces an adversarial optimization challenge that we refer to as handshakes, making it difficult to optimize. In Section 3.3, we describe mixed-play, our novel technique for mitigating handshakes in cross-play while still retaining the benefits of reward-alignee diversity metrics.
3.1 Cross-Play Minimization
The idea of cross-play is simple: pair two agents from different conventions together and evaluate their reward on the task. If those two conventions are semantically different, then the cross-play reward should be low. On the other hand, the conventions of the two agents are similar, then their cross-play reward should be high, and it should be penalized by our diversity regularization term.
We can also derive the notion of cross play minimization by trying to maximize the nearest neighbors score SDD) from Eq. (I), Suppose we already have found n conventions in the set D and we wish to add a new convention n, to construct the new set D,, We can evaluate lower bound for the improvement of S as
S(D,) 2 P(TT) nn)
max [TTa, TT)),
(6)
T-
where p(T,) is the probability of choosing policy n. at test-time. We explore the algorithmic implications of p(a,) Section 3.2.
Using the result above, we extend cross-play minimization to a set of n agents by using the cross-play reward between each convention and the most compatible existing convention the regularization term Cx in Eq. (7). To determine which existing convention is the most compatible, we can simply collect cross-play buffers with all existing conventions and choose the convention with the highest expected return. Note that Cx is minimized, so rewards are inverted under cross-play.
CD) =
max J(A,, T"). ED
If we integrate Eq. (7) into the full loss function from Eq. (4), the cross-play loss is simply equal to the sum of the lower-bound expressions in Eq. (6) for all conventions in D when p(T,, is ignored.
3.2 Handshakes: Challenges of Optimizing Cross-Play
Recall that the downstream objective is to maximize the nearest neighbors score from Eq. (1), meaning that want policies that work well with the unseen test distribution. Unfortunately, directly minimizing cross-play can lead to undesirable policies for the downstream objective. In particular, policies optimized with pure cross-play often take illogical actions that would actively harm the task reward when they are in a cross-play setting while still performing well in self-play.
This sabotaging behavior is also observed in concurrent work in Hanabi [8]. They specifically analyze cases where players intentionally use unplayable cards to quickly end the game. Their "self-play worst response" policy, analogous to pure cross-play minimization strategy for T2, intentionally sabotages the game under cross-play, resulting in a brittle policy that identifies when it is under cross-play. To resolve this issue in Hanabi, ADVERSITY uses belief reinterpretation, similar to Off-Belief Learning [14], in order to construct a fictitious trajectory consistent with the observed trajectory. This prevents sabotaging behavior because observations equally likely to come from self-play or cross-play. Although this technique is very effective in partially observable environments, like Hanabi, this unfortunately does not solve the issue in our fully observable settings because there is no hidden state that can be reinterpreted to construct plausible self-play trajectories given a cross-play trajectory.
5

---

We hypothesize that the challenge with the op- timization of cross-play regularization arises when agents can easily discriminate between cross-play and self-play, as illustrated in Fig. For example, consider the earlier Overcooked example in Fig. I, where we now pair the red convention for the blue player and orange con- vention for the green player during cross-play. As we repeatedly update the policies based minimizing cross-play, the agents will learn to recognize when they are being evaluated under cross-play and deliberately sabotage the game. The blue player can learn develop hand- shake, like shown in Fig. 2, and sabotage the game based the green player's reaction. Note that the strategy after the handshake may be sim- ilar across both conventions, but they will still have a low cross-play due to intentional sabotage. As a result, these agents have fooled our cross-play diversity metric into treating their behaviors as semantically different.
Handshake acknoweedgdd
I'll work hard!
Play
Handshake: Place plate strange spot
Cross-Play
Hundshake
rejested! II Twon't help.
Figure 2: Example of handshake in Overcooked.
The blue player initiates a handshake by placing plate in a strange location. Under self-play, the green player will pick up the plate, but otherwise it will continue picking up onions. If the blue player sees that the plate has not moved, it will sabotage the game.
More generally, this problem occurs when there is a mismatch in observation distributions (or history distribution for recurrent policies) between self-play and cross- pross-play, which allows the agents to infer the identity of their partner and the inversion of rewards. In fact, a mismatch can be identified as early the second timestep: in the first timestep, both agents perform handshake reveal the identity of the players. If the handshakes match, then the two agents cooperate to solve the task. Otherwise, they sabotage the game, e.g., by doing nothing for the rest of the episode.
action intended to
Since a strong self-play policy is under-specified at many states, all of the mechanisms of handshake signalling and sabotaging can be encoded into policy with almost no reduction in self-play perfor- mance. We would not expect this type of behavior from a convention in the test set, so this policy, æ, would have very low p(π)) in Eq. (6) relative to other trained policies. The outcome of cross cross-play minimization procedure (Eq. (7)) plagued by handshakes is a set of agents who have high individual self-play, low pairwise cross-play, yet may still be using semantically similar conventions.
3.3 Mixed-Play
To mitigate the issues of handshakes, we pro- pose mixed-play, which improves cross-play regularization by expanding the valid distribu- tion of "self-play states" and reducing under- specification. Mixed-play rolls out episodes us- ing varying combinations of self-play and cross- play to enlarge state coverage. All the states in the coverage will be associated with the posi- tive rewards of self-play, so agents cannot infer reward inversion and sabotage the game. For example, if the cross-play situation from Fig. 2 becomes a valid state that self-play can continue from, the blue agent can no longer confidently sabotage the game when it encounters this state, since this harms the self-play score as well.
Initiate Himderaker Place plate strange spot
Cross-Play
Cross
Mixud-Pby?? shouldn't
sabotage
Figure 3: Visualization of how mixed-play resolves handshakes. Agents must act in good faith since they might switch self-play.
Mixed-play consists of two phases in each episode: mixed-state generation and self-play. We choose random timestep within the episode that represents the length of the first phase. Until this timestep occurs, we randomly sample the action from self-play or cross-plat for both players, but do not store these transitions in the buffer. For the rest of the episode, we perform the second phase: taking self-play actions and storing them in the buffer. When optimizing, we treat this new buffer the same as we would treat self-play, but modified with a positive weight hyperparameter, 3, representing the importance of mixed-play. Unlike ADVERSITY, our technique does not assume that the environment partially observable and does not require privileged access to the simulator, making applicable to our fully observable settings.

---

1.0-
1,0
R
0.8
6
Frequuse
0.6
0.4
0.2
0.2
0.0
0.0
10
20
30
40
50
0
10
20
40
50
Training Epoch
Training Epoch
Figure 4: The Blind Bandits environment with k = 2 steps. The solid lines indicate the first player's 's actions while the dashed lines indicate the second player's actions. The blue line rep- resents the conventions that converge to the S reward while the orange line represents the con- vention that converge to the G reward.
Figure Frequency of self-play scores during the optimization of the two conventions using CoMeDi. The left plot is the first convention while the right plot is the second convention. We choose k as the steps in the environment, and the shaded region indicates the frequency bounds from 10 independent initializations.
After training with mixed-play, the agent cannot determine the current identity of the partner. In particular, even if the partner fails the handshake in an earlier timestep, the setting might be mixed- play instead of cross-play, handshakes significantly harm the scores in the second phase of mixed-play and will learn to act in good faith all timesteps. In the following section, we present our full algorithm that incorporates mixed-pla play into our technique for generating diverse conventions.
visualized in Fig. 3. If large enough, the agent will learn that
3.4 CoMeDi: Self-play, Cross-play, and Mixed-play
So far, we have described how cross-play while mixed-play ensures that trained agents always act in good faith. In the full training regime, which we name CoMeDi, we (1) maximize self-play rewards to ensure that agents perform well in the environment, (2) minimize cross-play rewards with previously discovered conventions to ensure diversity, and (3) maximize rewards from the collected mixed-play buffers to ensure that conventions in good faith. Note that collect separate buffers for self-play, cross-play, and mixed-play to estimate their respective expected returns.
play is useful for constructing a reward-aligned diversity metric,
To train convention nn, the full loss function evaluate is
[(TT) [mm, m.) + JJ (Tn, B.MM
where IM represents the expected mixed-play reward, and n² is the most compatible convention to n" found in Da-1- We also have tunable parameters a and 3 representing the weight of the cross-play and mixed-play terms. Pseudocode and specific implementation details for the algorithm incorporating this loss, including the mixed mixed-play buffer generation, is presented in Appendix A.
4 Experiments
We now describe our experiments and results using three different environments: Blind Bandits environment, Balance Beam, and Overcooked [5, 34, 26). These three environments will help illustrate the differences between statistical diversity, cross-play diversity, and mixed-play diversity, In particular, the Blind Bandits highlight the importance of reward-alignment that is present in cross-play but not statistical diversity. The Balance Beam environment demonstrates the pitfall of handshakes during cross-pla minimization, and how this is mitigated with mixed-play. Finally, the Overcooked environments demonstrate the scalability of CoMeDi, and allow to evaluate the generated set of diverse agents by training convention aware policies to play with real human partners. More detailed descriptions of all experiments in the appendix.
4.1 Blind Bandits
In the Blind Bandits environment, we extend the classic multi-armed bandit problem into two-player game. The main twist that each agent cannot observe the actions their partner during the game, so they cannot change their strategy in reaction to their partner. It is collaborative 2-player game
7

---

SP
XP
HS J
PX
LS
RS
0.00
1.616
-0.392
0.16
0.00
1.128
-0.656
0.25
1.808
0,096
0.00
0.00
1.272
0,096
0.50
2.000
0.200
0.00
0.00
1.384
0.128
1.00
1.904
0.632
0.00
0.24
1.232
0.160
Table 1: Results of Mixed-Play in the Balance Beam Environment: SP is the self-play score. XP is the cross-play score with the first convention. HS (handshake) is the fraction of cross-play games where a player moves off the line, while PX (perfect XP) is the fraction of with a perfect 2.0 score. LS and RS are the scores under cross-play with the left-biased and right-biased hand-coded agents.
where each player takes steps, Is 2 2, and each step they have to choose to go left (L) or right (R). The possible trajectories when ko = 2 are represented in Fig. 4.
An important characteristic of the Blind Bandits environment is that all conventions that converge to S are compatible with one another while being incompatible with the only convention that converges
to G. Therefore, if we want diverse set of 2 conventions, we would like one convention to converge to S and another to converge to G.
Baseline Results for Blind Bandits. Existing statistical divergence techniques, like ADAP, typically converge to S conventions because it affords a larger space of policies. Even when trying to train more conventions, they could all converge to S conventions while still satisfying statistical diversity, since there are multiple possible distinct policies associated with S. Unfortunately, this gives a set of agents that diverse with respect trajectory metrics, but not with respect to the task, since the statistical diversity policies cannot lead to an agent compatible with the G convention.
CoMeDi Results for Blind Bandits. By minimizing cross-play, we can reliably train set of agents that converge to both the S and G conventions. First, we train a single agent via self-play to converge to one of the S conventions. Then, under the cross-play regularization (with a 1.0), the reward payoff for a second agent is a transformed environment where each self-play reward is subtracted by the cross-play reward with the first agent. All policies with a self-play score of S would have score of 0 in the transformed environment, but all policies with a self-play score of G would still have agent trained on this transformed environment
score of G' in the transformed environment, would converge to G. Indeed, as we see in right plot of Fig. 5, the second convention consistently converges G.
4.2 Balance Beam
The Balance Beam environment is a collabo- rative environment with two players that has locations with unit spacing. illustrated in Fig. 6. Both agents move simultaneously and they get a high reward if they land on the same space after their actions, but they must move from their current location at each timestep. As human- llke test set of policies, we hand hand-design left-biased agent and a right-biased agent. Fig. shows a visualization of the environment.
line
Soore
As opposed to Blind Bandits, the Balance Beam environment involves multiple timesteps and is prone to handshake formation. As we will show in the next section, mixed-play allows us to com- bat the handshake formation of cross-play diver- sity in the Balance Beam environment.
Figure 6: Example of the Balance Beam environ- ment. The agent with a white hat follows the left- biased policy. The blue agent has four different actions it can choose. If an agent steps off the line, the game ends with a large negative score.
Balance Beam Results. We train the first convention with base MAPPO, which converges to a self-play score of 2.0. The expected cross-play play of this first convention with the hand-coded left-biased
8

---

agent is 0.384 while the score is 1.368 with the right- fight-biased agent, so it acts very similar to the right-biased agent.
Ideally, we would want a second convention to have a high cross-play score with the left-biased agent and low cross-play score with the right-biased agent so it would ensure that human players from either convention could find a compatible AI partner. Its self-play score should be 2.0, indicating an optimal equilibrium convention. Also, should never take actions that are clearly incorrect, like stepping off of the line, which would result in a large negative score along with the early termination of the episode.
Although pure cross- cross-play minimization (3 = 0) results in the lowest cross- cross-play scores (as shown in Table 1), we notice signs of handshakes: 16% of the cross-play games result in the action of stepping off of the line, as indicated in the HS column. Moreover, pure cross-play minimization does not give perfect self-play scores, indicating that it takes suboptimal actions in some states to establish a handshake. When the mixed-play weight is set to a low value (3 = 0.25), the agent no longer steps off the line when the convention breached, but it still results in imperfect convention since it takes suboptimal actions to minimize cross-play. If the mixed-play weight is set to a high amount (3 = 1.0), the agent follows an identical trajectory the first convention in 24% of the games, indicating that it is overcorrecting the issue of handshakes. The best convention we found had 3 == 0.5 as shown in Table I, which was able to generate perfect convention that does not exhibit signs of bandshakes. This convention also has the highest cross-play with the left-biased agent, indicating that mixed-play enables us to generate an agent that is more aligned to human notions of "natural" conventions since this agent always acts in good faith instead of conducting handshakes.
From the results above, we empirically demonstrate that mixed- mixed-play addresses the issue of handshakes, generating pair of meaningfully diverse agents.
4.3 Overcooked
Overcooked is a fully cooperative game where two chefs controlled by separate players try to cook and deliver as many dishes of food as possi-
4x
ble in a given amount of time [5, 26]. The main
Dishes Servod
challenge is to coordinate by subdividing tasks and not interfering with each other's progress.
Time Let
For our experiments, we generate 2 baseline agents and 2 convention-aware agents using CoMeDi. The baselines are "SP" and "ADAP" which refer the base MAPPO algorithm and training a convention-awan agent on ADAP. Our agents are "XP" and "CoMeDi" which re- fer to the convention- where 3 0.0 (pure cross-play minimization) and B = 1.0 respectively.
SP ADAP XP CoMeDi
agents on CoMeDi
Vollow
Compriaa
Romendble
Resvmedded
Homass-8a
Suond
Winked
Results for the Coordination Ring: av- erage scores (top left), environment visualization (top right), and user survey feedback using the 7- point Likert scale (bottom). Higher average scores are better. The dashed line is the average score single-player human score while the solid line is the average score when paired with an expert hu- man. Higher is better for all but the last feedback score. Error bars represent the standard error.
Figure 7:
Overcooked User Study. In both the Blind Bandits and Balance Beam environments, could construct an artificial test set by design- ing human-like conventions. However, this is infeasible for Overcooked because humans can exhibit unpredictable dynamies, such as adapt- ing to partners. Therefore, we test the quality of our four agents by experimenting on a pop- ulation of 25 human users. The results of the user study the Coordination Ring environment are Fig. 7. this environment, players need to coordinate on strategy so they do not bump into one another. A full description of the environment, simulation results, and additional user-study results the Cramped Room layout are in the appendix. Videos of users interacting with each agent can be found our website.

---

2
3
5
8
0.50
0.00
0.25
0.00
0.00
0.05
0.04
0.15
Table 2: Frequency of each convention being the most likely in the encountered "convention- dependent" observations in Coordination Ring.
In terms of scores, we see that CoMeDi (score of 3.68) performs best, followed by XP (2.48), ADAP (2.24), and SP (2.08). The average score when playing with an expert human partner is 3.25, so only CoMeDi surpasses human-level performance (p- = 0.045). In terms of statistical significance, CoMeDi outperforms all baselines with p < 0.001. CoMeDi also was strongest across all metrics in the survey. Users wrote that CoMeDi "knew exactly what to do next," with one user even claiming that it "is GODLIKE" and "adapted to my moves like he can see into the future." Sentiments were mixed for XP with some users reporting that it was "doing great decisions, but sometimes he seemed confused." With ADAP and SP, users complained that the bots would "block" their progress often and "just stood around the onions and did nothing."
Diversity of the Human Test Set. Although users tended to favor CoMeDi across the metrics we measured, we wanted to determine why CoMeDi performed well. Specifically, we wanted to determine whether humans actually followed diverse set of conventions and whether CoMeDi's strength comes from finding a specific human-like convention covering a larger observation space.
To answer these questions, we conducted an experiment where we explicitly predict the probability of being in a CoMeDi convention conditioned on the observation. Since our usage of QDagger can be approximated as a gated mixture-of sarre-of-exppe of-experts model, we can explicitly train "gate" network as a classifier that determines which convention an observation belongs to. Out of the 5000 observations that CoMcDi encountered when working with users in Coordination Ring, 2349 of them were aligned with a specific convention with probability greater than 50%, which we refer to as "convention- specific" observations. The frequency of most likely conventions is reported Table 2.
Although convention 1, which is equivalent to the pure self-play policy, behaves well in 50% of the convention-specific observations, knowledge of other conventions still vital. Furthermore, all players aligned with convention 1. For instance, one player had 65% of their convention-specifie observations align with convention 8 while only 27% aligned with convention When calculating which convention each player followed a plurality of the time, 20 players followed convention 1, three followed convention 8, and two followed convention No user perfectly followed a single convention, indicating that understanding multiple conventions made CoMeDi more robust overall.
These results demonstrate that there is non-trivial diversity in the human distribution of conventions and that CoMeDi's strengths come from discovering multiple human-like conventions along with having more robust policy handle deviations from these conventions.
Conclusion
In this work, we introduce CoMeDi, algorithm for generating diverse agents that combines the idea of minimizing cross-play with existing agents to generate novel conventions, and the technique of mixed-play to mitigate optimization challenges with cross-play. Compared to prior work that defines the difference between conventions as a difference in generated trajectory distributions, our work uses cross-play measure of incompatibility between conventions. As seen in the Blind Bandits environment, cross-play gives more information than statistical diversity techniques since can identify whether conventions are redundant. In the Balance Beam environment, we show how mixed-play -lay addresses the issue of handshakes by incentivizing agents to act in good faith at each state in the environment. Finally, we analyze Overcooked and how convention-awee agent trained with CoMeDi outperforms prior techniques with users, achieving expert human-level performance.
Although we use simple BC-based algorithm for training a convention-awen aware agent, future work could utilize the diverse set of conventions generated by CoMeDi more effectively to create an agent that uses the history of past interactions to dynamically adapt to a user's convention.
10

---

Acknowledgements
This research was supported in part by AFOSR YIP, DARPA YIP, NSF Awards #2006388 and #2125511, I, and JP Morgan. We would also like to thank Jakob N. Foerster for his useful discussion with us regarding handshakes and Hengyuan Hu for clarifying the differences between CoMeDi and ADVERSITY.
References
[1] R. Agarwal, M. Schwarzer, P. S. Castro, A. C. Courville, and M. Bellemare. Reincarnating reinforcement learning: Reusing prior computation to accelerate progress. Advances Neural Information Processing Systems, 35:28955-28977 2022.
[2] N. Bard, J. N. Foerster, S. Chandar, N. Burch, M. Lanctot, Song. E. Parisotto, V. Dumoulin, S. Moitra, E. Hughes, et al. The Hanabi challenge: A new frontier for Al research. Artificial Intelligence, 280: 100:10 2020.
[3] C. Boutilier. Planning, learning and coordination in multiagent decision processes. In Proceed- ings of the 6th conference Theoretical aspects of rationality and knowledge, pages 195-210, 1996.
[4] K. Bullard, F. Meier, D. Kiela, J. Pineau, and J. N. Foerster. Exploring zero-shot emergent communication in embodied multi-agent populations. CoRR, abs/2010.15896, 2020. URL https://arxiv org/ abs /bss/2000 15896.
[5] M. Carroll, R. Shah, M. Ho, Griffiths, S. Seshia, P. Abbeel, and A. Dragan, On the utility of learning about humans for human-ai coordination. In Advances in Neural Information Processing Systems, pages 5175-5186, 2019.
[6] R. Caruana. Multitask learning. Machine learning. 28(1):41-75, 1997.
[7] R. Charakom, P. Manoonpong, and N. Dilokthanakul. Generating diverse cooperative agents by learning incompatible policies. In The Eleventh International Conference on Learning Representations, 2023. URL
[8] B. Cui, A. Lupu, S. Sokota, H. Hu, D. J. Wu, and J. N. Foerster. Adversarial diversity in hanabi. In The Eleventh International Conference Learning Representations, 2023. URL https: / https://openreee /tppr/eveeeeeeeeeee/emee
H_5.
[9] K. Derek and P. Isola. Adaptable agent populations via generative model of policies. In Advances Neural Information Processing Systems, 2021.
[10] B. Eysenbach, A. Gupta, J. Ibarz, and S. Levine. Diversity is all you need: Learning skills without reward function. CoRR, 2018. URL http://arxiv wwwg/aa/////eeeoeoo 06070.
[11] C. Florensa, Y. Duan, and P. Abbecl. Stochastic neural networks for hierarchical reinforcement learning. In International Conference on Learning Representations, 2017. URL https: / //openreview
[12) T. Greitemeyer and D. O. Mügge. Video games do affect social outcomes: A meta-analytic review of the effects of violent and prosocial video game play. Personality and Social Psychology Bulletin, (0)55578-5888 2014. doi: 00.177701141662213333
URL https: org/
10.117770116666211332000
PMID: 24458215.
[13] R. X. Hawkins, M. Frank, and N. D. Goodman. Convention-formall in iterated reference games. In Proceedings of the 39th Annual Meeting of the Cognitive Science Society, 2017.
[14] H. Hu, A. Lerer, A. Peysakhovich, and J. Foerster. "Other-play" for zero-shot coordination. In Proceedings of the 37th International Conference Machine Learning, ICML. 2020.
[15] A. Jacob, D. Wu, Farina, Lerer, A. Bakhtin, Andreas, and N. Brown. Modeling strong and human-like gameplay with kl-regularized search. ArXiv, 2022.

---

[16] M. Jaderberg. V. Dalibard, S. Osindero, W. M. Czarnecki, J. Donahue, A. Razavi, O. Vinyals, T. Green, I. Dunning, K. Simonyan, al. Population based training of neural networks, arXiv preprini arXiv: arXiv:171 1.09866, 2017.
[17] E. Jang, A. Irpan, M. Khansari, D. Kappler, Ebert, C. Lynch, S. Levine, and Finn. BC-Z: zero-shot task generalization with robotic imitation learning. CoRR, abs/2202.02005, 2022.
URL. https:tt////....... aarxiviivvvv...i org/ /2202. 02005.
[18] H. M. Le, Y. Yue, P. Carr, and P. Lucey. Coordinated multi-agent imitation learning. In International Conference on Machine Learning, pages 1995-20033. PMIR, 2017.
[19] A. Lerer and A. Peysakhovich. Learning existing social conventions via observationally augmented self-play. In Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society, pages 107-114, 2019.
[20] D. K. Lewis. Convention: A Philosophical Study. Cambridge, MA, USA: Wiley-Blackwell, 1969.
[21] A. Lupu. B. Cui, H. Hu, and J. Foerster. Trajectory diversity for zero-shot coordination. In International Conference Machine Learning, pages 7204-7213, PMLR, 2021.
[22] D. A. Pomerleau. Alvinn: An autonomous land vehicle in a neural network. In D. Touret- zky, editor, Advances in Neural Information Processing Systems, volume 1. Morgan- Kaufmann, 1988. URL https:ts://ppooee nww.eeerdddnnnnnnnne.eee..e..e.e wwtpc/ppee..llee/aaappeepeeeeppe 11116/220222760000055555eeeeee22 pdf.
[23] J. K. Pugh, L. B. Soros, and K. O. Stanley. Quality diversity: A new frontier for evolutionary computation. Frontiers in Robotics and AI, 3, 2016. ISSN 2296-9144, doi: 10.3389/frob..2016 00040. URL https: https:://www..e
frontiersin https://www.frrtiierrssss
wwtgg/rticlees//ee /1..://....3000. 3389/frobtffot.. 2016. 00040..
[24] B. Sarkar, A. Talati, A. Shih, and S. Dorsa. Pantheonrl: A marl library for dynamic training interactions. In Proceedings of the 36th AAAI Conference on Artificial Intelligence (Demo Track), 2022.
[25] J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: 100.00007777777 2017.
[26] B. Shacklett, L. G. Rosenzweig, Z. Xie, B. Sarkar, A. Szot, E. Wijmans, V. Koltun, D. Batra, and K. Fatahalian. An extensible, data-oriented architecture for high-performance, many-world simulation. ACM Trans. Graph., 42(4), 2023.
[27] A. Shih, A. Sawhney, J. Kondie, S. Ermon, and D. Sadigh. On the critical role of conventions in adaptive human-Al collaboration. In International Conference on Learning Representations, 2021.
[28] A. Shih. S. Ermon, and D. Sadigh. Conditional imitation learning for multi-agent games. In ACM/IEEE International Conference on Human-Rolee Robot Interaction, HRI, 2022.
[29] H. C. Siu, J. Peña, E. Chen, Y. Zhou, V. Lopez, K. Palko, K. Chang, and R. Allen. Evaluation of human-ai teams for learned and rule-based agents in hanabi. Advances in Neural Information Processing Systems, 34:16183 1111183--11.,,,11111111111111111 2021.
[30] Song, H. Ren, D. Sadigh, and S. Ermon. Multi-agent generative adversarial imitation learning. Advances in neural information processing systems, 31, 2018.
[31] D. Strouse, K. McKee, M. Botvinick, E. Hughes, and R. Everett. Collaborating with humans without human data. Advances in Neural Information Processing Systems, 34:1 44:14502-14515, 2021.
[32] Z. Tang, C. Yu, B. Chen, H. Xu, X. Wang, F. Fang, S. Da, Y. Wang, and Y. Wu. Discovering di- verse multi-agent strategic behavior via reward randomization. arXiv preprint 20X1v:2103.045564 2021.
12

---

[33] G. Tesauro. TD-Gammon, a Self- Seaf-ig Backgammon Program, Achieves Master-Level Play. Neural Computation, 6(2):215-219, 03 1994. ISSN 0899-76677 7667. doi: URI. wtw.hhttts:/dooo org/ //./g//.... httgg/...1...//..11 11162/necoo 1994. 6 2. 215.
[34] R. E. Wang, S. A. Wu, J. A. Evans, J. B. Tenenbaum, D. C. Parkes, and M. Weemann-Weinee Too many cooks: Coordinating multi-agent collaboration through inverse planning. Proceedings of the 19th International Conference Autonomous Agents and Multiagent Systems, AAMAS, 2020.
[35] W. Z. Wang, M. Beliaev, E. Biyik, D. A. Lazar, R. Pedarsani, and D. Sadigh. Emergent prosociality in multi-agent games through gifting. In 30th International Joint Conference on Artificial Intelligence (IJCAI), Aug. 2021. doi: 10.24 10.24963/jjci..22211
[36] C. Yu, A. Velu, E. Vinitsky, Y. Wang, A. Bayen, and Y. Wu. The surprising effectiveness of ppo in cooperative, multi-agent games. arXiv preprint arXiv:2103.01955 2021.
13

---

A CoMeDi Algorithm Details
A.1 Mixed-play Buffer Collection
Mixed-play consists of phases in each episode: mixed-state generation and self-play. The "input" policies are the policy for the convention we are currently training Ta and the partner policy used for cross-play optimization
(using the same notation from Eq First, we choose random timestep within the episode that represents the length of the first phase (Line 2). Until this timestep occurs, we randomly sample the action from self-play or cross-play for both players (Lines 5-9). We do not store any of these transitions in the training buffer. Instead, we use the state at the last timestep and pretend that this is the initial state of the environment. For the rest of the timesteps, we perform the second phase, by taking self-play actions and store that in the buffer (Lines 10-12), When optimizing, we treat this new buffer the same as we would treat self-play, but modified with a positive weight hyperparameter, 3, representing the importance of mixed-play.
Algorithm 1: Generating Mixed Play Buffer
Input: policies nn n,, MDP Output: Replay buffer from running mixed-play.
1 8o, R R
// start state, reward // length of mixed-state generation phase
I uniform(1, 7)
3 for i [0, T') do 0². o² + o(s;) if t then
T < Randomly choose T, or
IT2 < Randomly choose TT or x²
at, at + +mm (o-), Th (o²)
8141, - t Step in M with(a! az)
10
else
11
at, at +- n., (ot) (T
// self-play keep reward phase2
12
84117 Step in M with a?)
Return: Replay arr, ai. TeT)
A.2 Full CoMeDi Algorithm
Simplified pseudocode for the CoMeDi algorithm is presented below. Note that conventions generated in sequential order, with being trained with standard self-play and each being trained with the awareness of prior conventions, Di.i-1- The arg max operation line 4 estimated empirically by simulating fixed number of rounds of cross-play in the environment with each existing convention and selecting the convention with the highest cross-play as n*.
Algorithm 2:
Diverse Conventions with CoMeDi
Input: Number of policies to generate
Output: Diverse set of conventions
D <- (æ1,..., Jn), parameterized by (0) ..).
0x)
2 Train mi with standard self-play
3 for E (2....,n) n.) do
while policy π; has not converged do
T² +- arg max J J T*)
TSP + GetRollout [T,,
TXP GetRollout
TMP <- MixedPlayRollout(my.rr x*)
Estimate J(m,, mT), J (m,, n JMI x*) with TSP, TXP, TMP
10
0, - 0 + Vo, - m. n.) a a.. BJ (,,, "1),
Return:
14

---

A.3 Implementation Details
We base the implementation of our algorithm on the Multi-Agent PPO algorithm (MAPPO) [36]. MAPPO is an actor-critic method which, in standard self-play, trains a single actor network for the policy and single critic network for the value function [25]. To adapt MAPPO to train a pool of conventions using our proposed mixed-play algorithm, we train n actor networks, n. self-play critic networks, and n² cross-play critic networks, each representing cross-play pairing between the n conventions. We also use the PantheonRL. library [24] to design our environments and training algorithms since it designed handle dynamic training interactions like cross-play and mixed-play We have also integrated CoMeDi with a new GPU-accelerated simulation framework [26], which enables the collection of large batches of cross-play and mixed-play buffers in parallel with the collection of self-play buffers.
Moreover, instead of training the whole batch of diverse agents in parallel, in practice we se- quentially grow the set of agents one at a time, keeping the previous agents fixed. We find that sequential generation leads more stable training: since the previous agents are fixed, the diversity regularization term becomes a reward shaping term that is only a function of the policy of the current agent.
A.4 Practical Guidelines for Hyperparameter Tuning
There are some safe choices for hyperparameters that work well in general, which we used to tune the hyperparameters for our experiments. First, we observe that directly using the best MAPPO hyperparameters for the particular environment, like learning rate and the model architecture, transfers well to CoMeDi. To find the cross-play weight (at). fix the mixed-play weight to 0 and find the lowest value for the cross-play weight such that increasing it further does not significantly increase the self-play score or decrease the cross-play -lay score. If the cross-play weight is too high, this may cause training instabilities since the updates to increase the self-play score would be directly counteracted by the updates to decrease the cross-play score. Finally, choose the value of the mixed-play parameter such that the average mixed-play score (for the second half) is slightly less than half of the self-play score, which would indicate that self-play uil-p is able smoothly continue from any mixed -lay state.
The guidelines for choosing hyperparameters works well in general, but domain knowledge of the environments also helps. If your specific environment also has some indicators of handshakes, you can also use those to determine if handshakes are still happening. Furthermore, environments where partners' actions are not visible, like Blind Bandits, do not require mixed-play at all because hand- shakes are impossible. In practice, we have seen that CoMeDi is relatively robust to hyperparameters and it gives reasonable policies with a cross-play weight of 0.5 and a mixed-play weight of 1, even if they are not perfectly optimal.
Choosing a population size is also art, but due to the sequential nature of CoMeDi, prior conventions are unaffected by the generation of later conventions. The choice of algorithm for generating a "convention-aware agent" would likely influence the number of conventions use for the diverse set.
A.5 Extending to Larger Teams
When using CoMeDi for cooperative games with more than 2 players, we can follow the same algorithm presented in 2, but we have to be bit careful when collecting rollouts.
To collect the cross-play buffer between n, and an existing n² in a k-player game, we can randomly assign each player to one of the conventions but keep those assignments consistent throughout the duration of the episode. The same logic regarding the minimization of cross-play rewards still applies since semantically similar conventions would result in high reward even when the team contains mix of the conventions.
To collect the mixed-play buffer, we would randomly choose between the two conventions for each player at each timestep during the mixed-state generation phase. We would still treat self-play as normal by using the convention being trained as the convention for all players.
15

---

B Experiments
B.1 Choice of Baselines
Throughout this work, compare the performance of CoMeDi against pure MAPPO, modified version of ADAP, and a pure cross-play minimization baseline (CoMeDi with 8 = 0). We do not directly use ADAP because we find that generative capabilities from parameter sharing often limits the diversity of its agents, resulting in very high cross eliminate the confounding variables of the base PPO implementation and the parameter sharing in the original algorithm. We also do not directly compare against TrajeDi because a fundamental aspect of its algorithm the concurrent generation of a common best response agent, which implicitly optimizes for high cross-play within the "diverse set" policies. However, upon analyzing TrajeDi's diversity loss, we note that is very similar in practice to ADAP's loss. Therefore, we believe that our modified version of ADAP the fairest representative of statistical diversity approaches. Concurrent work that implements technique similar to pure cross-play minimization provides some other benchmarks with MAVEN and TiajeDi which show similar results to what we experienced with our modification of ADAP.
By adding diversity loss the MAPPO algorithm, cross-play between agents in the population.
We do not compare our work to those in section 2.3, because they require more assumptions regarding the training domain. In particular, the strength of reward shaping methods (and other domain engineering techniques) is highly dependent on the manual design of the appropriate environment parameter space. However, CoMeDi can be interpreted as an automatic technique for reward shaping to form diverse conventions, which can potentially eliminate the need to engineer the environment parameter space for domain randomization.
B.2 Hyperparameters
Table 3: Common hyperparameters for agents in Blind Bandits and Balance Beam
hyperparameters
value
fc layer dim
512
num fc activation
2
ReLU
network
mip
ppo epochs mini batch 1
15
Table 4: Hyperparameters in Blind Bandits
hyperparameters
value
buffer length
200
environment timesteps
10000
actor/critic Ir linear Ir decay entropy coef
2 x 10
False
0.01
ADAP a
0.2
CoMeDi
1.0
CoMeDi
0.0
16

---

Table 5: Hyperparameters in Balance Beam
hyperparameters
value
buffer length
1250
environment timesteps
50000
actor/critic linear Ir decay entropy coef ADAP a CoMeDi a CoMeDi (ablation)
2.5 x 10-5
True
0.01
0.05
0.3
0.0, 0.25, 0.5, 1.0
Table 6: Hyperparameters in Overcooked (only training set)
hyperparameters
value
CNN Kernel Size fe layer dim num fc activation rollout threads buffer length (per thread)
3 x 3
ReLU
50
200
environment timesteps
1000000
ppo epochs actor/critic Ir linear Ir decay entropy coef ADAP a
10
x 10
True
0.0
0.025
CoMeDi
0.5
CoMeDi B
0.0, 1.0
Table 7: Hyperparameters in Overcooked (convention-aware agents)
hyperparameters
value
CNN Kernel Size fc layer dim num activation rollout threads buffer length (per thread)
3
64
2
ReLU
50
200
environment timesteps (SP phase)
200000
ppo epochs (SP phase) Ir entropy coef
100
1 1 10
10-3
B.3
Compute Resources
We conducted our experiments with our lab's internal cluster. We only used the Intel Xeon Silver 4214R CPU for training Blind Bandits and Balance Beam. For the Overcooked experiments, we used additional NVIDIA TITAN RTX, which required around 3 hours per configuration. However, this time can be reduced significantly by disabling deterministic behavior in CUDA. Current work on optimizing performance with the GPU-accelerated simulator also shows that this time can be reduced.
17

---

B.4 Blind Bandits Environment Description
The Blind Bandits environment is a collaborative two-player MDP where each player takes l steps, k 2 2, and at each step they have to choose to go left (L) or right (R). Each player is given their own past history of actions in the episode, but cannot see the others' actions. There are two ways to get positive score. To get score of S. the first player's first step must be L, and the second player's last step must be L. To get a score of G > S, the first player's first step must be R, but all following steps by all players must be except for the second player's last step, which must be R. the players fail to coordinate, they get score of O.
The policies that converge S are all compatible with one another since all of them have agent start with and have agent 2 end with L (shown in blue). If two agents are playing randomly, there is a 0.25 probability that they will get reward of S. Meanwhile, only one trajectory will result in score of G (shown in orange), so there is only 2-2k chance that random agents will get a reward of G. Notice how these two conventions (S and G) are entirely incompatible with one another because their first and last moves must be different, and are therefore different equilibria, Ideally, we want to find a representative policy for both conventions using a technique that finds a diverse set of conventions.
B.5 Blind Bandits Baseline Results
1.0
1.0
0.8
0.8
Frequency
Freguency
0.6
0.6-
0.4
0.4
0.2
0.2
0.0
0.0
10
30 Training Epoch
20
40
50
10
30 Training Epoch
20
40
50
Figure 8: Frequency of self-play scores during the optimization of two conventions using statistical diversity (the ADAP loss) from 10 independent seeds. The blue line indicates an S convention, the orange line indicates G convention, and the black line indicates score of 0 (all other paths that lead to 0). With ADAP, neither convention converges to G. We choose k = 3 as the number of steps in the environment.
we see that using ADAP to train set of two agents almost always leads to them both converging to S. For this result, we used the ADAP diversity weight of 0.2, the most common value used in the original paper. Inereasing this weight sometimes results in discovering few G conventions, but this is inconsistent and results in more unstable training.
In Figure
In fact, training an agent to converge to the G convention is more difficult that it appears. Off-the-shelf MARL algorithms typically converge to the S convention as well. At the first training epoch, the actor chooses random actions, so it will get a score of S 1/4 of the time while it gets a score of G with probability of 2 2-2, The critic network (in both the decentralized and centralized setting) will learn that the value of choosing go left in the first state is S/2 while the value of choosing to go to the right is G G/2*. Therefore, the policy updates will favor the S convention in the first epoch long as S G/2t-1, and this separation gets larger until it fully converges to S convention.
Most existing zero-shot coordination (ZSC) algorithms would also converge to the S convention. The TrajeDi algorithm finds a common best response to set of conventions that have wide diversity in trajectory, but the G convention has only one trajectory so will never be chosen. The Off Belief Learning (OBL) algorithm would also only converge to the S convention because it acts on the belief that its partner is random agent. Higher levels of OBL will be stuck in the S convention since they assume that their partner is from a lower level of OBL. Note that the purpose of 7SC is to have high cross-play between independent runs of the same algorithm, so both of these techniques succeed in that manner, but this does not imply that these algorithms would have high cross-play with humans.
18

---

B.6 Balance Beam Environment Description
At the start of the game, the location of each player is randomly initialized. At each timestep. both players take simultaneous actions, and can move 1 or 2 locations to the left or right, but cannot stay still. If an action leads to them falling off the line, they get score of -1 multiplied by the number of remaining timesteps. Otherwise, they get a score of -d(s1, 82)/5 where d is the distance between the two player's 's locations. Finally, if both players are on the same spot at the end of their turn, they get an extra point. Each episode lasts two timesteps, and the players see the result of the first step's s actions before making their second move.
A perfect convention would always get a score of 2.0, because players can score +1 in each of the two timesteps. The worst score -2.0, which occurs when one player moves off of the line at the first time step.
We also hand-code some conventions see if CoMeDi discovers conventions that similar to those that humans follow. There are two simple conventions: a left-biased convention and a right-biased convention. These dictate how ties are broken when multiple actions are equally optimal. For example, if the distance between two players is I step, like in Figure 6 of the main text, the player from a left-biased convention would want move to the open space to the left since staying in one spot is not an option.
B.7 Balance Beam Baseline Results
We designed the Balance Beam environment to distill the issue of handshakes when minimizing cross-play. which is why the main text only emphasizes the impact the B hyperparameter in how it compares to the other CoMeDi. However, we also trained ADAP in this environment approaches.
The first trained convention gets score of 2.0, and gets an expected score of 0.768 and 1.1 12 when paired with the left and right-biased agents respectively.
The second trained convention gets score of 1.808, and gets an expected score of 1.048 and 0. 1,176 when paired with the left and right-biased agents respectively. Its cross play score with the first trained convention is 0.392.
When training the ADAP agents, observed very unstable training process resulting in very low self-play scores with typical values of the diversity weight parameter. For this reason, we had to choose relatively low value for the loss parameter (0.05) in order to make fair comparison with our technique.
B.8 Overeooked Agent Generation
For our experiments, we generated 2 baseline agents and 2 convention-awen agents using CoMeDi. The first bascline agent, which we refer to as "SP", was trained with pure self-play, and we tuned the hyprraarameters to maximize its self-play score. For all other generated agents, maintained the same hyperparameters that are inherent to MAPPO, but we would tune the diversity weights specific to each algorithm. Our second baseline, which we refer to "ADAP", is convention to population of 8 agents trained with ADAP with no parameter sharing and a diversity weight of 0.025. The XP agent was also convention-awee agent population of 8 agents trained with = 0.5 and 3 = 0.0. The CoMeDi agent was the same as XP, but its population was trained with 0.5 and / 1.0.
agent
For each layout of Overcooked, we can determine the expected number of dishes to be served by cach agent in self-play. In the Cramped Room, SP averages 4.36 dishes, ADAP averages 2.75 dishes, XP averages 4.68 dishes, and CoMeDi averages 5.52 dishes. Meanwhile, in the Coordination Ring, SP averages 3.47 dishes, ADAP averages 1.90 dishes, XP averages 3.06 dishes, and CoMeDi averages 5.36 dishes.
We can also calculate the expected reward for the best and worst performing agents in the training sets of ADAP, XP, and MP. In Cramped Room, ADAP's average rewards spanned 5.98, XP's rewards spanned 4.12 to 5.96, while MP's rewards spanned 5.0 to 5.88. In Coordination Ring, ADAP's average rewards spanned to 4.965, XP's rewards spanned 2.75 to 4.56, while MP's rewards spanned 4.92 to 5.99.
19

---

When training agents with ADAP. we would frequently see a few policies with very high expected returns with the remaining policies having low scores. We attempted tune ADAP's diversity weight to enable more balanced generation, but this issue continued to persist even with final diversity weight significantly lower than the values presented in the original paper.
B.9 Overcooked User Study Setup
The human-AI interaction portion of this research was approved by our IRB.
Our total population consisted of 25 paid participants with varying prior experiences in Overcooked, recruited through Prolific. We did not impose any conditions on participation through Prolific except for requiring "proficiency in English language." We paid $10.33 (US dollars) per participant for approximately 40 minutes of time, equivalent to $15.50 per hour, We titled the study "Playing with Al Agents in the Overcooked Video Game" with the following description:
"In this study, participants will play with 4 different AI agents in 2 settings of the Overcooked game. Our goal is to understand how well trained agents can work with humans in tasks that require coordination. Your task is to try to work with the Al to cook many "dishes of onion soup" within 40-second time limit. You will also fill out short surveys to judge the quality of the Al agents. You will play 20 games in total.
To play the game, you need to use a keyboard with arrow keys and a space bar. Desktops, laptops, and tablets with keyboards may be used. The Al agents runs on your browser and are designed to be lightweight so they should be compatible with most hardware.
The games will be fast-paced, and we may reject submissions that are consistently unable to score points in the game. As long as we can see that you are trying to score points, your submission will be accepted.
NOTE: Please only accept this study if you have at least GB RAM. The game will take up GB of RAM since we are loading models onto your computer you have a smoother experience. If the game freezes, please let us know and refresh the page. Please use Firefox, Chrome, or Safari."
To ensure that participants across the world are able to complete the study without excessive latency, run all models on the users' devices directly through tensorflow-js.
Each user played 2 games in a layout independently before playing each Al agent for two 40-second rounds in a random order. The users first played with all agents in the Cramped Room environment before playing with all agents in the Coordination Ring environment.
We also asked the users to fill out short survey with qualitative questions about each partner after playing both rounds in any configuration using the 7-point Likert scale.
We presented the following 8 statements (in order):
1. The Al followed my lead when making decisions.
2. The Al agent frequently blocked my progress.
3. The AI was consistent in its actions.
4. The Al always made reasonable actions throughout the game.
5. I would like to collaborate with this Al in future Overcooked tasks.
6. The Al's actions were human-like.
7. trusted the Al agent in making good decisions.
8. The Al agent was better than me at this game.
Note that a higher Likert score is better for all of the prompts except for the second question.
We also presented an optional free-response section with "Other comments or observations?" that users could fill out at the end of each survey.
To determine statistical significance, we use the paired Student t-test between the scores across different Al agents for each layout.
We also asked a smaller set of users (8 users) to play with an expert human player in- in-person after playing with all AI agents to determine what human-level performance would entail without allowing
20

---

explicit communication. This expert human player was trained to adapt to different play styles, and users reported that this human player was "very good" at the game, noting fast reflexes. This set of users was mutually exclusive from the Prolific set, since the games needed to be played in person. We determine there statistically significant difference between the Al agents and the human expert through the unpaired t-test.
B.10 Cramped Room Overcooked Results
Dishes Served
Time Scole:
SP
ADAP XP
CoMeDi
S
Score
2
1
Followed User
Consistent
Reasonable
Recommended
Human-like
Trustworthy
Strong
Blocked User
average scores (top left), environment visualization (top right), and user survey feedback using the 7-point Likert scale(bottom). Higher average scores are better. The dashed horizontal line indicates the average score when player is working alone while the solid horizontal line indicates the average score when paired with an expert human. Higher is better for all but the last feedback score. Error bars represent the standard error.
Figure 9: Results for the Cramped Room:
In the Cramped Room Environment, players have very small area to move around in, and they need coordinate around the management of ingredients and the usage of plates. Given the simplicity of the setting (relative to the Coordination ring). humans might be able to adapt quickly to Al players since the patterns of movement can be very clear after interacting for a short time. In particular, note that this layout has lower convention dependence than the Coordination Ring.
The results of the study in the Cramped Room environment are in Figure 9. In terms of scores, we see that CoMeDi (score of 4.72) performs the best, followed by XP (4.28), SP (3.68), and ADAP (3.36). In terms of statistical significance, CoMeDi outperforms all AT agents < 10-3) and the expert human (p < 10-4). XP also outperforms ADAP, SP, and the expert human (p < 0.01 for each).
We also analyzed the convention-speciine observations in the Cramped Room environment. Out of 5000 observations, 2124 observations were aligned to a specific convention with probability over 50%. We show the frequency each convention being the most likely one below:
0.05
0.25
0.00
0.01
0.45
0.11
0.04
0.09
Table 8: Frequency of each convention being the most likely in the encountered "convention- dependent" observations in Cramped Room.
When considering which convention each player followed a plurality the time, 16 players followed convention 5, players followed convention 2, and player followed convention 6.
21

---

B.11
User Free Response Feedback
User feedback for SP in the Cramped Room environment:
This AI trusted more than the others. He waited for me to get the plate and deliver the soup. The other bots rushed to it themselves.
could not understand what the Al was doing
The Al was slow in decision making
* Ai was bit hesitant sometimes
User feedback for ADAP in the Cramped Room environment:
The Al sometimes blocked me, He held the onion in his hands, and it was already cooked, and had the plate in my hands, but couldn't 't get to pick up the soup because he was blocking it. think he trying place the onion even tho there no space to place in.
Al was blocking me whole time
didnt like this one...
It was somehow worse than S, it blocked the plate for like 7 seconds
the ai seemed very confused
He tried do things right, but sometimes he seemed confused.
User feedback for XP in the Cramped Room environment:
This AI was more lazy. He only held the plate in his hand and waited for me to cook the soup. The other AI wasn't it that way (AI D). He cooked and adapted in getting the plate and everything. This bot did the exact opposite.
did not like the fact that it could not path find different way deliver the full plate.
The AI seems to be faster
ai was very good at this game
Once he picked up plate after got one plate, then he never stopped that action until I put the next 3 onions in the pot.
User feedback for CoMeDi in the Cramped Room environment:
This bot was by far the best. He was very consistent in everything he did, his moves were all correct and felt very good, working with him.
this one was not so bad
This AI could work by himself, literally, and get the same 100 score, believe.
User feedback for SP in the Coordination Ring environment:
The Al did the correct thing, but when it came to pressing the space bar, he struggled. Even tho he just needed to press the space bar, and he stood right in front it, and it was just one space bar away, he decided to wait in front of it for some seconds and then press it, which concluded us to make less soup overall.
the first soup was ok and then AI like "freeze".... ...it was weird.
ok this completly stood in my way while i was trying to get the plate he just stood there with an onion on his hand. Aside from the ai really likes this study and experiment and hope one day ill be able participate in one of them again!
At first it looked like the cooperation was working until when it just stopped doing anytihng and occasionally just blocked the way to the stoves. Towards the end it just standed in the corner doing nothing.
Yes it was consistenly bad
22

---

He didn't know what to do when picking plate and there were onions missing in pot.
User feedback for ADAP in the Coordination Ring environment:
This bot blocked me lot of times. He also just stood around the onions and did nothing, which stopped us both. He sometimes got a plate his hand and just went up and down all the time until he decided to play normally again. Would not play with this bot.
also didnt like this ai.
This one was very bad at making decisions and pathfinding
the AI slowed the process
Al was better than the other ones so far, but still got alot in the way which is frustrating to play with.
He was in the way lot and almost never knew what to do next, where to go.
User feedback for XP in the Coordination Ring environment:
He did very good in the first round, always clockwise. perfect. In the second round, he decided to be the lazy chef. He was too lazy to pick up an onion or the plate.
It's moves felt very scattered and didn't make sense me.
The Al kept getting in the way and got nothing done.
The Al was helpful
This one was doing great decisions, but sometimes he seemed confused. In general I liked
User feedback for CoMeDi in the Coordination Ring environment:
This bot GODLIKE! He did everything correct, he adapted to my moves like can see into the future. Just great playing with him. The most efficient by far.
it seems sometimes you get into flow, which the AI breaks after while
He knew exactly what to do next.
The experiment was very cool because every AI was unique. The best Al was Al M by far, my most favorite. If I was a chef, I would definetly hire him!
B.12 Additional Overcooked Simulation Experiments
Our Human-Al experiments only covered the Coordination Ring (random1) and Cramped Room (simple) environments, since these considered the canonical Overcooked layouts. However, also trained models for other layouts used in the original Overcooked-Al papery: Counter Circuit (random3), Asymmetric Advantages (unident_s), and Forced Coordination (randomO), To train the new models, we use the same hyperparameters as the other Overcooked models. We used the tensorflow-js versions of the PPO_BC and PBT models as held-out test conventions.
When paired with the PBT partner, we get the following average scores:
layout
CoMeDi
XP
ADAP
SP
PPO
BC
simple
4.55
3.49
2.79
4.36
3.75
random1
3.42
1.58
0.72
2.70
2.29
random3
1.19
0.49
0.03
0.33
1.17
unident_s
5.27
3.62
1.84
2.51
2.58
randomO
0.37
0.49
0.00
0.21
1.44
23

---

When paired with the PPO_BC partner, we get the following average scores:
layout
CoMeDi
XP
ADAP
SP
PBT
simple
4.91
4.46
2.77
4.51
3.75
randoml
3.43
1.81
1.10
2.38
2.29
random3
1.91
1.1
0.03
1.13
1.17
unident_s
2.94
3.16
2.59
4.52
2.58
randomO
1.56
0.88
0
0.25
1.44
From these results, we see that CoMeDi generally works well with unseen partners. It even surpasses the PPO BC agent under most layouts, which uses human data in its training process. Interestingly, the results are inconsistent the unident s and randomO environments. When analyzing the trajectories of the best-performing agents in these cases, it seems like the conventions used by the partners just coincidentally aligned with the other agents.
When evaluating under self-play, get the following average scores:
layout
CoMeDi
XP
ADAP
SP
PPO_BC
PBT
simple
5.52
4.68
2.75
4.36
4.83
4.93
random1
5.36
3.06
1.90
3.47
2.81
3.04
random3
3.83
1.13
0.0
5.72
2.20
3.99
unident_s
8.44
4.40
4.42
7.84
2.95
4.33
random0
4.67
2.95
0.0
5.98
2.06
4.30
These results generally are what we would expect. A pure self-play policy that does not need to consider diversity will likely have strong score, which is why we sometimes find scoring very high relative to the other baselines. However, CoMeDi often has a higher self-play score, because the additional diversity factor caused later conventions be better, like the Blind Bandits toy example.
C Related Work
Concurrent to our work, methods for training diverse agents with respect to reward have been proposed.
LIPO [7], they also consider cross-play as a diversity metric, but do not address the critical issue of handshakes that arise when minimizing cross-play. Their results reinforce observations when the mixed-play weight, 3, is set to 0. However, as we have noticed our Balance Beam simulation results and the Overcooked user study, mixed-play has large impact creating good-faith conventions.
The ADVERSITY [8] work considers zero-shot coordination framework in the game of Hanabi. They propose belief reinterpretation model to address a similar "sabotaging" behavior that we experienced. This model is designed tackle the issue of handshakes by finding plausible distribution of self-play states that would result in the same observation received from cross-play and use this while training so agents cannot discriminate between self-play and cross-play observations. However, it is unclear whether belief reinterpretation would help in the games we examine in this paper since cross play can potentially encounter observations that are completely impossible under self-play. Specifically, in Overcooked, all agents have access to the state from the prior frame, but conventions exist as way to manage the workload of tasks between partners. In Hanabi, core part of the game is predicting the underlying state of the game given the observation. As such, conventions are based around communicating information about the state implicitly through actions.
ADVERSITY uses the fact that multiple trajectories can generate the same action- obbeevvtionn history. which enables it to gain very strong results Hanabi. However, this technique would fail in our settings because there are observations that are only possible under cross-play and not self-play, so belief reinterpretation would not be helpful. Therefore, although ADVERSITY and CoMeDi both attempt address the problem of handshakes, their core assumptions are entirely different.

---

Since CoMeDi does not perform explicit belief reinterpretation, it will not be competitive with ADVERSITY on Hanabi, but it would still be able train a sequence of agents.
In games where implicit communication to predict the underlying state is the core task, ADVERSITY is strong choice for training diverse set of agents. However, CoMeDi would be more effective in tasks where a team needs to divide a workload or commit to a particular strategy for effective coordination. We believe that these scenarios are more similar to the tasks that one would encounter in robotics domain or typical video game setting.
D Limitations
Although our technique of creating convention-awe aware agent using CoMeDi was able to surpass human-level performance in Overcooked, this technique has some drawbacks. Since the policy has no memory, training a convention-awar agent on a diverse set may lead to the Al breaking conventions established with humans earlier in the game, which is why one user reported that the CoMeDi agent sometimes breaks the established flow in Coordination Ring. Also, the BC-based algorithm for generating the convention-awee aware agent is often unable to account for human suboptimalities or transitions between conventions. For instance, some agents in Cramped Room would pick up an onion and expect the human to pick up plate. If the human does not comply, it simply stands around instead of dropping off the onion and picking up a plate itself, because this type of action is never experienced under self-play for any convention.
On a theoretical level, CoMeDi does not provide any guarantees regarding the quality of agents. This is not unique to our algorithm, as statistical diversity techniques and reward shaping often changes the environment to the extent that "equilibrium conventions" are no longer guaranteed. Also, our solution to handshakes, mixed-play, implicitly assumes that re-establishing handshakes will come at some expense to the self-play scores. If this assumption is violated, as is the case with cheap-talk signals that aren't wen't necessary for coordination, handshakes can be re-established at every timestep, effectively bypassing the mixed-play optimization. The issue of cheap-talk is a very tricky case in general when attempting to define diversity or robustness, because signals have implicit meaning. In these cases, environment designers can remove extraneous cheap-talk signals or add nonuniform cost to communication, which has been effective in the realm of zero-shot communication [4].
E Broader Impact
We believe that CoMeDi can have a positive impact on game design and human-Al interaction in general. Being able to generate diverse conventions can allow game designers to understand the different strategies that players might try to use before extensive play-testing. Effective zero-shot coordination techniques would also help reduce the risk of misaligned conventions. We observe that, with proper tuning of the mixed-play weight, the convention-awe -watte agent trained with CoMeDi learns to follow the lead of the human player, as indicated by the "followed user" section of the user survey. This is important for safety-critical applications like human-robot interaction tasks, because an overly assertive robot could unintentionally harm human.
As tool, it can directly be used for harmful ends, such as making it easier to cheat in multi-player games or generally conduct harm on others. Another potential effect of developing effective artificial zero-shot collaborators is that it could lead to more social withdrawal. In particular, if people who play video games start to strongly prefer playing with super-human AI collaborators over other humans, we may see people play less games with other people, which could counteract the prosocial benefits of cooperative gaming [12]. We therefore urge potential game designers and publishers who want to use CoMeDi to generate Al partners to evaluate the impact that artificial agents would have on their community.
F Creative Assets
Custom assets for this paper were digitally created by the authors without the assistance of Al image generation models. Stylistic inspiration was drawn from the Overcooked figures [5] under the MIT license.
25


Reviews:
[{"review_id": "dgLNaC7j2g", "reviewer": "Reviewer_9YDu", "summary": "This paper introduces a new approach to dealing with poor generalisation performance in human-AI settings when actors may have developed different coordination conventions. ", "questions": "- The fact that there are two tunable parameters here $\\alpha$ and $\\beta$ could potentially become a difficult balancing act in other environments. Could the authors comment a little more on how they would suggest selecting these parameters outside of full on hyper parameter tuning? Or is this the only viable option?\n\n", "limitations": "I would have been interested to see where the algorithm may feel and if the authors could have stress tested it a little more than in the paper. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "In general, I think the work is original and very clear in its presentation. In addition, the paper attempts to challenge a very obvious and significant issue in the domain of human-AI collaboration and takes a well-formulated approach to the challenge. More specifically:  \n\n- I think the problem is well formulated, and in particular the related work in relation to diversity approaches in RL is strong.  \n- I found the method generally easy to follow, and enjoyed its presentation in terms of creating all of the building blocks towards the final algorithm.  \n- On the presented empirical evidence the results are strong.", "weaknesses": "Whilst the empirical evidence presented is strong, my concerns with this paper are with the extent of the results and how they actually go about answering the question of this paper. Therefore, my main concern is as follows:\n\n- The paper argues that their approach is able to handle an arbitrarily diverse set of other agent conventions. Whilst this may be true, I am unconvinced by the empirical results that may try to back this up. In my opinion, the problem with the experiments that were picked is that there just really do not exist that diverse a pool of conventions in the first place. In particular, in the Overcooked environment I would be amazed if any human player undertook a strategy that was not immediately obvious. Therefore, I would have been very interested in seeing some form of analysis that was able to show that the algorithm was being put up against a diverse set of conventions in its test set.  \n\nNote, I have played with the demo of the paper and I do think that it appears to be a strong approach even under strange conventions. However, my own testing is probably not a strong enough scientific argument to back this up. I'm happy to bump my score up for the paper if the authors can convince me that the above is not as much of an issue that I believe it might be.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thorough review of our paper! We’re glad that you played with the demo and think that our approach works well, even under strange conventions.\n\nWe hope that the responses below answer your questions about our technique.\n\n## Diversity of Overcooked’s Human test set\n\nWe agree that most conventions that humans would naturally converge upon feel obvious on the Overcooked test suite. In the Coordination ring specifically, most differences in conventions are based on the direction of motion, i.e. clockwise versus counterclockwise. Humans also tend to be able to adapt to conventions easily, so determining whether CoMeDi adapts to human’s conventions instead of requiring humans to adapt is unclear from purely looking at average scores.\n\nFrom the user survey results (Figure 7 of main text), we see that CoMeDi has a higher score for following the user’s lead, indicating that it is able to follow the conventions of users. Additionally, we see that an understanding of conventions has a large impact on final scores since the only difference between convention-aware agents is the set of self-play rollouts used for QDagger. Although human conventions seem very obvious to us, the failures of SP, ADAP, and XP indicate that these conventions are harder for the policy networks to understand.\n\nWe also ran a new experiment where we explicitly predict the probability of being in a CoMeDi convention conditioned on the observation of the current player. Since our usage of QDagger can be approximated as a gated mixture-of-experts model, we can explicitly construct a “gate” network by training a simple classifier that determines which convention an observation belongs to. Out of the 5000 observations (from 25 players * 200 observations/player) that CoMeDi encountered when working with users in the Coordination Ring, 2349 of them were aligned with a specific convention with a probability over 50%, which we refer to as “convention-specific” observations. Of these 2349 observations, we can calculate the frequency of each convention being the most likely one in the table below:\n\n|\t0 | 1 |\t2 | 3 | 4 |\t   5 |\t6 |   7 |\n|---|---|---|---|---|---|---|---|\n| 0.50 | 0 | 0.25 | 0 | 0 | 0.05 | 0.04 | .15 |\n\nAs you can see, convention 0 (the pure self-play policy) behaves well in around 50% of the convention-dependent states, but knowledge of the other states is still vital. In particular, we see that convention 2 and convention 7 also seem to align well with human conventions. For most players, convention 0 is the most likely convention, but this is not universal. For one player, 65% of the convention-specific observations aligned with convention 7 while only 27% aligned with convention 0. For another player, 44% of the convention-specific observations aligned with convention 2 while 39% aligned with convention 0. Overall, if we consider which convention each player followed a plurality of the time, 20 players followed convention 0, 3 players followed convention 7, and 2 players followed convention 2. However, there was never a case when the convention-aware agent only used information from a single convention, indicating that the understanding of multiple conventions made the policy more robust overall.\n\nWe also ran this experiment on the Cramped Room results, and we found that 2124 observations were aligned to a specific convention with probability over 50%. We show the frequency of each convention being the most likely one below:\n\n|\t0 |\t1 | 2 |\t3 |\t4 |\t5 |\t6 |   7 |\n|---|---|---|---|---|---|---|---|\n| 0.05 | 0.25 | 0 | 0.01 | 0.45 | 0.11 | 0.04 | .09 |\n\nWhen considering which convention each player followed a plurality of the time, 16 players followed convention 4, 8 players followed convention 1, and 1 player followed convention 5.\n\nTying back to your original question, within the scope of Overcooked we see non-trivial evidence of diversity among the human conventions.\n\n## How to select hyperparameters\n\nWe detailed some guidelines for hyperparameter tuning in the appendix section A.4. This process involves keeping the standard hyperparameters from self-play, and tuning the cross-play weight before tuning the mixed-play weight. In practice, we find that CoMeDi is pretty robust to hyperparameters and very often gives reasonable policies with a cross-play weight of 0.5 and a mixed-play weight of 1 (or 0 when handshakes are impossible).\n\n## Failure Modes of CoMeDi\n\nIn appendix section D, we examine some cases where CoMeDi will likely struggle. One issue is working with environments with cheap-talk channels or handshakes that are extremely easy to execute, because mixed-play only helps when executing handshakes negatively impacts the reward.\n"}, {"review_id": "8W9zgjpD9b", "reviewer": "Reviewer_ghEw", "summary": "The authors develop CoMeDi which optimizes a cross-play objective but avoids handshakes that can prevent cooperation using mixed play. The algorithm is evaluated in three environments of increasing complexity and on an Overcooked level with real human users. ", "questions": "We need more information about the overcooked results. How well does the final policy perform in simulation against other policies. Not just in terms of human performance but self-play & cross-play with the other computational agents? \n\nThis is a fast moving space, could the authors devote some words to how this approach differs from Adversarial Diversity in Hanabi or Generating diverse cooperative agents by learning incompatible policies. The latter seems very similar in approach.\n\nWere the experiments with people done under time pressure? I noticed when playing that game online that time ticked independently from my own moves. How does that differ from prior work on human evaluation?\n\nWhat does it mean to over-correcting conventions during mixed-play? What are the implications? How carefully do these parameters need to be balanced? Can the same hyper-parameters be used across all Overcooked scenarios?", "limitations": "Yes", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is written well and the ideas are well motivated both by filling gaps in the literature and by tackling key challenges that the authors introduce using conceptual examples as well as toy experiments. The quantitative and qualitative evaluation on Overcooked with real human participants is the gold-standard for studying Coordination. Furthermore, the CoMeDi algorithm is an elegant solution to the problem of generating diverse conventions and cleanly avoids many of the pitfalls that can arise from adversarial training. The authors have released a playable version of their agent to the web. ", "weaknesses": "The Overcooked analysis was only done with a single grid out of many. This leaves open the possibility that the algorithm doesn’t work well on the more varied set of environments that are typically studied. I would raise my score if the algorithm could be evaluated on the full Overcooked suite (either with people or with baseline agents). This is critical because otherwise, the results might have arisen from a cherry-picked experiment. \n\nNo formal analysis of the algorithm — how does this approach scale when the number of possible conventions or agents grows? \n\nLittle evaluation done on the Overcooked environment. Besides overall reward, how well do these agents fare? How far off are the cross-play and self-play rewards from the results with people? How many conventions were generated for the Overcooked environment?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thorough review of our paper! We evaluated our algorithm across the full Overcooked suite with baseline agents, as you recommended. We believe that some of your additional questions have been answered in the appendix (within the supplementary materials as Diverse_Conventions_Appendix.pdf), but we expand on each of your questions below.\n\n## Additional Overcooked Results + Details\n\nWe present the full suite of tests against baseline agents in the common rebuttal above. We also recommend looking at section B.8 in the appendix for more information about the generation of Overcooked agents in the Cramped Room and Coordination Ring environments. For ADAP, XP, and CoMeDi, we generate a population of 8 conventions. If you have other results you would like to see, we would be happy to provide them during the discussion period.\n\n## Scalability of Approach\n\nIn section A.5 of the appendix, we describe an approach for extending our algorithm beyond two players. However, we believe that deciding how exactly to collect the cross-play buffers in large team settings is still an open research question.\n\nWhen there are a large number of conventions, CoMeDi still greedily chooses the least compatible undiscovered convention, so it can handle these situations in theory. However, one practical issue is that the number of cross-play buffers and cross-play value functions needed grows linearly with the number of conventions, so over time CoMeDi becomes significantly slower than pure self-play. A possible alternative is to have multiple independent generations of CoMeDi, which may cover a wide range of conventions without consuming as much extra time or space, but this may result in a loss of diversity since independent invocations could rediscover similar conventions.\n\n## Comparison to ADVERSITY and LIPO\n\nIn section C of the appendix, we have a detailed comparison of CoMeDi to LIPO and ADVERSITY. At a high level, LIPO is similar to our baseline of pure cross-play with no usage of mixed-play. On the other hand, ADVERSITY proposes a solution to “sabotaging” behavior, similar to our description of handshakes, but their technique of belief reinterpretation is specifically designed for games where partial observability is a major component of working with conventions. In particular, ADVERSITY would not work in Balance Beam or Overcooked since these are fully observable. CoMeDi does not explicitly perform belief reinterpretation, so it will likely not be as strong as ADVERSITY in Hanabi. \n\n## Time Pressure\n\nWe use a similar experimental setup to the one used in the original Overcooked paper, but we reduce the time to 40 seconds. Overcooked requires that players wait for soup to finish cooking, so time has to tick independently from moves, which is common to all Overcooked human-AI experiments as far as we know.\n\n## Overcorrecting for Handshakes in Mixed-Play\n\nIn Balance Beam, we observe that when the mixed-play weight, beta, is set too high, conventions trained with CoMeDi learn to match the behavior of the original (pure MAPPO) convention. In general, having too high of a weight for mixed-play incentivizes agents to eliminate handshakes along with genuine differences in conventions. In practice, we find that choosing alpha=0.5 and beta=1.0 gives good results, and we only use these hyperparameters across all Overcooked environments.\n"}, {"review_id": "ExaycALFSD", "reviewer": "Reviewer_Dzgz", "summary": "The paper introduces a new approach for generating diverse conventions by using a training objective that balances increasing self-play performance and minimizing cross-play performance with previously discovered conventions. To avoid handshake mechanisms that can game the proposed objective, the technique also involves a mixed-play bonus/penalty, that leads the agents to be uncertain about whether they're currently playing in self or cross play. The advantages of the proposed method in recovering meaningfully distinct conventions (relative to prior work) are shown experimentally and with a user study.", "questions": "- There's one aspect of the paper that I don't understand (and might be worth clarifying more somewhere – unless I missed it). It seems like the whole paper is about generating diverse conventions, and so is the proposed method (e.g. in line 274 one tries to generate $\\pi_n$). However, at evaluation time (e.g. in Overcooked) one must only choose one policy for CoMeDi. How is that done? In the conclusion, you say \"we use a simple BC-based algorithm for training a convention-aware agent\", but I don't see this referenced elsewhere?\n\nMinor typos:\n- line 129 spacing between commas. Footnotes have a space before preceding periods or even come before period (e.g. 140, 96)", "limitations": "With real humans, there are cognitive biases that might have them deviate from optimality arbitrarily, leading them to conventions that wouldn't be discovered by CoMeDi. Will this method will only work when humans are close enough to optimal? It might be worth acknowledging this as a limitation.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "### Originality and significance\n\nAlthough this is not my main area of research, this approach seems novel and highly relevant to the community. There seems to be a lot of interest in conventions, especially in the context of human-AI collaboration. Given the empirical performance of the proposed method relative to prior approaches, this seems like a significant contribution to the subfield. The theoretical motivation to the method is an extra nice feature of the approach.\n\n### Quality and Clarity\n\nI found the approach as quite a clever way of choosing the space of possible conventions to consider (by restricting to ones that maximize self-play reward but minimize cross-play reward), avoiding the problems of assuming adversarial conventions. The concept of handshakes was well explained, and the idea of mixed-play seems like a good (although a little \"hacky\") solution.\n\nThe related work section was done well and the overall motivation for the paper was very well executed.\n\nOverall, the paper was well-written and easy to read.", "weaknesses": "- The authors do not compare to behavior cloning play (i.e. \"human-aware RL\" from [4]) or similar approaches because it assumes access to expensive human data. I think it would still be very interesting to make this kind of comparison, because one long-standing challenge is to be able to effectively collaborate with humans without human data [26]. It would be interesting to see how far diversity approaches such as the one presented can get us. In other words, this could even enable to answer interesting questions such as \"how much actual human data are these diversity approaches worth?\". This seems especially interesting given the qualitative user reports.\n- Rules of balance beam are pretty unclear – it might be worth trying to clarify them further \n- A relevant recent work that the authors might not be aware of is: Who Needs to Know? Minimal Knowledge for Optimal Coordination [Lauffer, 2023]", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thorough review of our paper!\n\nWe hope that the responses below answer your questions about our technique.\n\n## Choosing Convention-Aware Agent\n\nWe explain the generation of a convention-aware agent in Equation 2, within section 2.1 of the paper, but we will edit the paper to re-emphasize this point during the Overcooked section. We also provide a more detailed explanation of this choice in the Common Response above. \n\n## Comparison to BC-Play\n\nIn the Common Response above, we compare the BC-Play (labeled PPO_BC) to our techniques when testing against PBT. Interestingly, we find that CoMeDi outperforms BC-Play by significant margins in simple, random1, and unident_s, and CoMeDi slightly outperforms BC-Play in random3. However, BC-Play does significantly better than CoMeDi at random0. In the original paper, we see that both BC-Play and PBT do very poorly when working directly with humans in the random0 layout, so it is unclear whether the issue is CoMeDi’s policy or PBT’s inflexibility.\n\n## Rules of Balance Beam\n\nWe go into more detail on the description of Balance Beam in appendix section B.6, but we can incorporate some more information into the main text. If you have any additional questions regarding the Balance Beam environment, we would be happy to answer them during the discussion period.\n\n## Minimal Knowledge for Optimal Coordination\n\nThank you for sharing this paper! The idea of needing prior knowledge to resolve strategic ambiguity is very important for Human-AI interaction. Their experiment on the modified version of Coordination Ring seems to indicate that despite the existence of various strategies (what we would call conventions), there exists a single best-response policy (VSEC) that can effectively determine which convention to follow just from the current state. We believe that the ideas of this paper can be helpful in determining how to construct a strong best response, and our technique for generating diverse conventions could help when trying to approximate their approach on more complex environments.\n\n## Optimality of Humans\n\nIn our Overcooked experiments, we work with real users who often deviate from optimal policies, and our convention-aware agent was able to handle these well. Since our policy is not conditioned on history, the diversity of our set of conventions is enough to ensure sufficient state coverage to minimize out-of-distribution behavior. Furthermore, the convention-aware policy implicitly acts with the assumption that their partner will take the optimal action at the next timestep, which causes it to be an “optimistic” policy that is forgiving to non-stationary and noisy-rational human behavior. \n\nAs reviewer qsFc mentions in their testing, the optimistic behavior of QDagger may not be good when working with an uncooperative partner who intentionally takes no actions or blocks the other agents. However, alternatives to QDagger for using the diverse set of agents may be able to address more significant deviations from optimality.\n"}, {"review_id": "eBZWsQgbK5", "reviewer": "Reviewer_qsFc", "summary": "This work suggests employing cross-play rewards to improve the measure of diversity in human-agent collaboration tasks, and presents an innovative training paradigm, namely, mixed-play, to address the challenge during optimizing cross-play, referred to as the \"handshake\" by the authors. As a result, the developed agent CoMeDi demonstrated superior performance in comparison to other baseline agents when collaborating with humans in the OverCooked game.", "questions": "1. Why the CoMiDi agent is not as intelligent as expected for some relatively simple behaviors?\n\n2. How the proposed method performs compared to the SOTA methods on OverCooked?\n\n3. How does the CoMiDi agent perform in teams with different levels of humans?\n\n4. What is the training manner of the proposed method, is it sequence training or joint training?\n\n5. Did the author encounter any challenges other than Handshakes during training? ", "limitations": "As discussed above, this work lacks the comparison of SOTA methods, and the user studies are not sufficient, which would limit the reliability of the proposed method. Besides, the authors should have further discussion on the scalability of the proposed method, such as in more complex environments.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. This paper is well-written and readable, and provides detailed appendices and codes to supplement the paper's algorithms, experiments, and implementation details. \n\n2. This work tried to tackle an important problem domain - ad-hoc team play in human-agent collaboration research.\n\n3. The experimental section fully validated the problems and necessity of self-play, cross-play, and mixed-play. The results of user studies on overcooked show the effectiveness of the proposed CoMeDi approach.", "weaknesses": "1. The behavior of human players tends to be non-stationary and noisy-rationally[1]. I am particularly interested in how the CoMiDi agent reacts to a player exhibiting random actions (such as a novice), or how the proposed CoMiDi method resolves this issue at the algorithmic level. This is because, upon experiencing the CoMiDi agent on the webpage (random1, random3, and scenario1_s Layout), I found that when I either refrain from any operation or deliberately obstruct one side of the path, the agent appears to be unintelligent and would not go around from the other side. Such performance contradicts the authors' claim that the CoMiDi agent surpasses human-level performance. Does this imply a lack of diversity in training or is it due to insufficient training?\n\n2. The experimental section seems to resemble an ablation study process, with an absence of comparisons to state-of-the-art (SOTA) approaches, such as FCP[2], HSP[3]. While the authors assert that these SOTA methods are not drop-in replacements for self-play, I believe that the FCP and HSP approaches are not fundamentally distinct from SP, and they can be considered as improved methods of SP. I recommend that the authors conduct comparisons with these methods to make the proposed methods more solid.\n\n3. The experimental section only discusses the results of partnering with expert humans. I am curious whether the authors have evaluated the CoMiDi agent's performance in collaboration with humans of varying skill levels (such as novices). Moreover, do all human partners prefer to collaborate with the CoMiDi agent over other agents? I believe user studies are crucial in the human-agent collaboration domain. Consequently, I suggest that the authors allocate more space in the main text to discuss user studies.\n\n4. It is commendable that the author discusses the scenario where the number of teams exceeds two in the appendix. I am particularly intrigued by how the CoMiDi approach or the convention-based method can be extended to more intricate tasks, such as Google Football. It would be appreciated if the authors could offer insight in this respect.\n\n[1] Anirudha Majumdar, Sumeet Singh, et al. Risk-sensitive inverse reinforcement learning via coherent risk models. 2017.\n\n[2] DJ Strouse, Kevin R. McKee, et al. Collaborating with Humans without Human Data. 2021.\n\n[3] Chao Yu, Jiaoxuan Gao, et al. Learning zero-shot cooperation with humans, assuming humans are biased. 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thorough review of our paper!\n\nWe hope that the responses below answer your questions about our technique.\n\n## Explanation for unintelligent behavior in simple scenarios\n\nPlease refer to the “Clarification on the convention-aware agent” section in the common response above, where we clarify the intentions of the convention-aware agents.\n\nThere are two main reasons for the bad behavior when interacting with CoMeDi: (1) the policy model and (2) the choice of QDagger. \n\nIn our experiments, the policy network has no memory or recurrence, like the original Overcooked-AI paper; it simply chooses the action given the current observation. Therefore, if the partner chooses to stand still, the policy has no way of knowing how long the partner has been staying still. Correcting this behavior would result in a policy that randomly chooses to switch directions even when the partner is working correctly but slowly.\n\nThe choice of QDagger means that we are simply cloning the self-play behavior of the diverse set of conventions. This means that policies implicitly assume that partners will choose an optimal action at each timestep, which is why it seems overly patient with an adversarial or novice partner.\n\n## Comparison to FCP and HSP\n\nWe believe that both FCP and HSP have valuable contributions to solving the challenge of Human-AI collaboration in Overcooked, but their techniques are largely orthogonal to our main goal. In our work, we specifically aim to generate a diverse set of conventions and we use QDagger in our evaluation as the standard technique for creating a convention-aware agent.\n\nIn the Limitations and Future Work section of FCP, they write, “Our method currently relies on the manual process of initially training and selecting a diverse set of partners. This is not only time consuming, but also prone to researcher biases that may negatively influence the behavior of the created agent.” Similarly, in the Limitations and Future Work section of HSP, they write, “HSP requires domain knowledge to design a suitable set of events. [...]  So a future direction is to utilize learning-based methods to design rewards automatically.” Therefore, in terms of our goal of generating a diverse set of conventions, FCP requires manual selection and HSP requires domain knowledge to shape rewards (similar to other approaches to diversity that we discuss in section 2.3 and appendix B.1).\n\nHowever, we believe that using a technique like FCP could help create a better convention-aware agent than the QDagger algorithm, though we do not follow this direction in our experiments since it makes the answer to our central research question ambiguous.\n\n## Clarification on Human Experiments\n\nWe would like to clarify that our experiments when testing our AI agents were not with “expert humans” but paid participants with varying prior experiences in Overcooked, recruited through Prolific. There may be self-selection bias given the title of the study and description, but none of the participants have played our exact version of Overcooked prior to the study. However, the human-human studies had a single delegated expert human play with other participants who had varying levels of experience with Overcooked.\n\nAlso, not all partners prefer to collaborate with CoMeDi. In the Coordination Ring, 21 out of 25 users put it as their top choice (4 of which were tied with another agent). In the Cramped Room, 17 out of 25 users put it as their top choice (4 of which were tied with another agent).\n\n## Scalability to more Complex Environments\n\nWhen scaling to more complex environments, CoMeDi should be able to generate a diverse set of conventions if hyperparameters are well chosen for the first self-play convention. In particular, the choice of cross-play over statistical diversity means that our diversity metric will not be “tricked” by larger state spaces, and the choice of mixed-play means that our analysis of handshakes will still carry over to complex environments.\n\nHowever, one challenge of complex environments is sparse rewards. In particular, if rewards are very sparse, then cross-play minimization does not have a strong signal, so measuring diversity is more difficult. Also, complex environments may have low-cost handshakes, which is a problem described in the second paragraph of appendix section D.\n\n## Sequence vs Joint Training\n\nIn appendix section A.3, we explain why we chose sequential over joint training for the results in this paper. Sequential training ensured that we would not need to retrain from scratch if we wanted to increase the number of agents. However, it is possible to modify the algorithm to train jointly. Specifically, we can train all n conventions in parallel, but still ensure that each convention minimizes cross-play with the conventions of earlier indices to get a similar “cascading” effect present in sequential training.\n\n## Challenges other than Handshakes\n\nWhen developing the CoMeDi algorithm, we learnt that creating separate self-play, cross-play, and mixed-play value networks was very important for stability. Although in theory these can be combined, we find that the high variance of using a single network resulted in significant training instability.\n"}]

Author rebuttal:
We thank all the reviewers for their thoughtful feedback. We appreciate that all reviewers found the paper well-written while tackling key challenges in human-AI collaboration research. We are happy that reviewers found our algorithm “well-formulated” (9YDu) and “elegant” (ghEw) while “avoiding the problems of assuming adversarial conventions” (Dzgz) and that our experimental section “fully validated the problems and necessity of self-play, cross-play, and mixed-play.” (qsFc)

The reviewers asked a wide range of questions, which we respond to in detail in their individual responses. For the rest of the common response, we clarify the purpose of the convention-aware agent, highlight some new simulation experiments on the rest of the Overcooked suite, and present some minor corrections.

## Clarification on the convention-aware agent:

We define the process of creating a convention-aware agent in equation 2 of the problem definition section. This is essentially the QDagger algorithm, but instead of using expert human generated trajectories we treat the diverse set of conventions as the “experts” and collect their self-play rollouts. We can approximately treat this as a distilled mixture-of-experts model, where each “expert” is a generated convention, and they are gated by the probability of experiencing an observation in its self-play rollout.

We chose this definition of a “convention-aware agent” because it is a good proxy for answering our research question of whether a set of conventions is **diverse** and **high-quality**. For instance, if the set is not diverse but has high quality, this convention-aware agent will have a large space of out-of-distribution observations, leading to poor performance on the test set. If the set is diverse but has low quality, the agent will consistently take bad actions even when its observations are in-distribution. A set that is both diverse and high-quality would have a convention-aware agent that consistently takes good actions since its space of out-of-distribution observations is small.

Other techniques for generating an agent using a set of conventions, typically based around generating a common best response agent, do not serve as good proxies for answering our question due to the more complex dynamics involved with this process. In particular, a common best response agent to a set of very low quality partners will learn to never rely on their partner, resulting in an agent that never defers work to their partner but can get strong scores in environments where it can act alone. On the other hand, a common best response agent paired with a diverse set of extremely high quality partners may become too reliant on their partner, so it would not work well when partnered with novices.

## Experiments on Full Overcooked Suite:

Our human-AI experiments only covered the Coordination Ring (random1) and Cramped Room (simple) environments, because we considered them to be the canonical Overcooked layouts. However, since reviewer ghEw asked us to evaluate our algorithms on the full Overcooked suite against baseline agents, we trained models for the 3 other layouts used in the original Overcooked-AI paper: Counter Circuit (random3), Asymmetric Advantages (unident_s), and Forced Coordination (random0). To train the new models, we use the same hyperparameters as the other Overcooked models. We were unable to use the original BC or human-proxy models from the original Overcooked-AI work due to technical difficulties when working with outdated versions of python libraries, but we were able to use the tensorflow-js versions of their PPO_BC and PBT models.

When paired with the PBT partner, we get the following average scores:

| layout	| CoMeDi |   XP | ADAP |   SP | PPO_BC |
|---|---|---|---|---|---|
| simple	|   **4.55** | 3.49 | 2.79 | 4.36 |   3.75 |
| random1   |   **3.42** | 1.58 | 0.72 | 2.70 |   2.29 |
| random3   |   **1.19** | 0.49 | 0.03 | 0.33 |   1.17 |
| unident_s |   **5.27** | 3.62 | 1.84 | 2.51 |   2.58 |
| random0   |   0.37 | 0.49 | 0.00 | 0.21 |   **1.44** |

When paired with the PPO_BC partner, we get the following average scores:

| layout	| CoMeDi |   XP | ADAP |   SP | PBT |
|---|---|---|---|---|---|
| simple	|   **4.91** | 4.46 | 2.77 | 4.51 | 	3.75 |
| random1   |   **3.43** | 1.81 | 1.10 | 2.38 | 	2.29 |
| random3   |   **1.91** |  1.1 | 0.03 | 1.13 | 	1.17 |
| unident_s |   2.94 | 3.16 | 2.59 | **4.52** | 	2.58 |
| random0   |   **1.56** | 0.88 |	0 | 0.25 | 	1.44 |

From these results, we see that CoMeDi generally works well with unseen partners! It even surpasses the PPO_BC agent under most layouts, which uses human data in its training process. Interestingly, the results are inconsistent in the unident_s and random0 environments. When analyzing the trajectories of the best-performing agents in these cases, it seems like the conventions used by the partners just coincidentally aligned with the other agents. 

When evaluating under self-play, we get the following average scores:

| layout	| CoMeDi |   XP | ADAP |   SP | PPO_BC |  PBT |
|---|---|---|---|---|---|---|
| simple	|   **5.52** | 4.68 | 2.75 | 4.36 |   4.83 | 4.93 |
| random1   |   **5.36** | 3.06 | 1.90 | 3.47 |   2.81 | 3.04 |
| random3   |   3.83 | 1.13 |  0.0 | **5.72** |   2.20 | 3.99 |
| unident_s |   **8.44** | 4.40 | 4.42 | 7.84 |   2.95 | 4.33 |
| random0   |   4.67 | 2.95 |  0.0 | **5.98** |   2.06 | 4.30 |

These results generally are what we would expect. A pure self-play policy that does not need to consider diversity will likely have a strong score, which is why we sometimes find it scoring very high relative to the other baselines. However, CoMeDi often has a higher self-play score, because the additional diversity factor caused later conventions to be better, like in the Blind Bandits toy example.

## Minor Corrections:

We will fix the formatting issues brought up by Dzgz. We will also correct equation 2 by deleting the extra $\pi(a|o)$ term.


Meta-review: The authors study human-AI coordination in fully observable settings. 
Specifically, they train one agent as a best response to a pool of diverse agents, as is common practice in literature. 
They also build on adversarial cross play as an established method for driving meaningful diversity in multi-agent populations. 

The key contribution is a thorough experimental evaluation of a simplified version of ADVERSITY, adapted to the fully observable setting. 
Like adversity, the partner is either chosen to be cooperative or adversarial with a given probability to avoid "sabotaging" behaviour. 

I recommend this paper for acceptance, under the following conditions: 
1) "Our key insight is to instead use the incompatibility of different conventions as a measure of diversity" -> This claim needs to be removed form the paper, since both ADVERSITY and LIPO already use this mechanism for diversity. 

2) For the purpose of academic integrity, the section on "Handshakes: Challenges of Optimizing Cross-Play" needs to be rewritten to properly consider prior work (ADVERSITY) which extensively introduces (and solves) this problem.

3) The paper introduces Dec-POMDPs in the background section but only tests on fully observable environments. Claiming that the method is applicable to Dec-POMDPs is thus misleading. This is further supported by the paper using pi(a|o) in the paper, rather than conditioning on action-observation histories (tau) as necessary under partial observability.

4) The authors should explicitly compare and contrast to ADVERSITY and LIPO in the main body of the paper. ADVERSITY in particular contains an opponent mixing step which closely mirrors the mixed-play component of this work. Based on this, authors should also adapt their claims regarding the novelty of the mixed play algorithm.
Decision: Accept (poster)