Cross-environment Cooperation Enables Zero-shot Multi-agent Coordination
Authors: Kunal Jha
Wilka Carvalho
Yancheng Liang
Simon Shaolei Du
Max Kleiman-Weiner
Natasha Jaques
Venue: ICML 2025 oral (2025)
Keywords: Zero-shot Coordination
Human-AI Collaboration
Multi-agent Interactions
Primary area: reinforcement_learning->multiagent
TL;DR: Learning to generalize to novel coordination tasks with one partner lets you generalize to novel partners as well

Abstract: Zero-shot coordination (ZSC), the ability to adapt to a new partner in a cooperative task, is a critical component of human-compatible AI. While prior work has focused on training agents to cooperate on a single task, these specialized models do not generalize to new tasks, even if they are highly similar. Here, we study how reinforcement learning on a **distribution of environments with a single partner** enables learning general cooperative skills that support ZSC with **many new partners on many new problems**. We introduce *two* Jax-based, procedural generators that create billions of solvable coordination challenges. We develop a new paradigm called **Cross-Environment Cooperation (CEC)**, and show that it outperforms competitive baselines quantitatively and qualitatively when collaborating with real people. Our findings suggest that learning to collaborate across many unique scenarios encourages agents to develop general norms, which prove effective for collaboration with different partners. Together, our results suggest a new route toward designing generalist cooperative agents capable of interacting with humans without requiring human data.

Cross-enviromment Cooperation Enables Zero-shot Multi-agent Coordination
Kunal Jha'
Wilka Carvalho 2 Yancheng Liang'
Simon S. Du
Max Kleiman-Weinee
Natasha Jaques
Abstract
1999; "leiman-Weined al., 2016; Shum al., 2019; Wu et al., 2021). This ability to effectively represent collective tasks allows cooperation to transfer across both partners and environments. For instance, after mastering a family recipe with their parents, a novice chef can easily cook the same dish (and much more) at home with their spouse. These cognitive mechanisms may be important for building AI that coordinates novel scenarios. However, current rein- forcement learning (RL) methods have yet to address this challenge (Wang al., 2024). Cooperation across partners on a single problem has been studied, but agents that can zero-shot coordinate (ZSC) with new partners in unfamiliar environments will unlock flexible, human-comee commanccompatble AI agents in range of applications: household robots, adaptive educational assistants, or autonomous vehicles (Ma et al., 2023; Stone al., 2010b; Atchley et al., 2024; Dinneweth et al., 2022; Ribeiro et al., 2021).
Zero-shot coordination (ZSC), the ability to adapt to a new partner in a cooperative task, is a criti- cal component of human-comme compatill AL While prior work has focused on training agents to co- operate on single task, these specialized mod- els do not generalize to new tasks, even if they are highly similar. Here. we study how rein- forcement learning on a distribution of environ- ments with a single partner enables learning general cooperative skills that support ZSC with many new partners on many new problems. We introduce two Jax-based, procedural genera- tors that create billions of solvable coordination challenges. We develop new paradigm called Cross- Coos--Eaviromment Cooperation (CEC), and show that it outperforms competitive baselines quantitatively and qualitatively when collaborat- ing with real people. Our findings suggest that learning to collaborate across many unique scenar- ios encourages agents develop general norms, which prove effective for collaboration with dif- ferent partners. Together, our results suggest a new route toward designing generalist coopera- tive agents capable of interacting with humans without requiring human data. Code for environ- ment, training, and testing scripts and more can be found at https: //jhaa22 git hub. ic/ publicatioon/coos-eenttt coop.
Prior work on ZSC has mainly focused on the challenge of adapting to novel partners, including novel human partners. Typical RL approaches use methods like population based training (PBT) and variations on self-play (SP), approaches which helped algorithms such as AlphaStar achieve superhu- man performance in zero-sum games (Vinyals et al., 2019). These approaches work by leveraging "partner diversity." during training time. They simulate diverse training part- ners with the idea that these varied experiences will be sufficient for agents to generalize to human partners (Yan et al., 2023; Carroll et al., 2020; Strouse et al., 2018; Sarkar et al., 2023). Although agents trained under this paradigm often do adapt new partners, this adaptation is limited to the single environment they are trained on. PBT, it is often deployed (and similar approaches), fails to generalize when faced with even slight variation of the same problem. Thus, current PBT--aaed approaches must be retrained every time there is a slight variation in the environment or task. This is not recipe which can scale well to the real world (Yan et al., 2023). If agents only successfully cooperate with others on the specific environment they were trained on, such as household robot which can only interact with people in one bedroom rather than the entire house, they lack a more general notion of cooperation - the ability to flexibly interact in a broad range of scenarios with many people.
1. Introduction
Humans excel at ad-hoc cooperation, readily adapting to new partners and environments by attending jointly to rel- evant objects, reasoning about shared intentions, and play- ing their role within an implicit collective plan (Tomasello,
'Equal contribution 'Department of Computer Science, Uni- versity of Washington, Seattle, WA 'Kempner Institute for the Study of Natural and Artificial Intelligence, Harvard Univer- sity, Cambridge, Massachusetts. Correspondence to: Kunal Jha <kjha @uhhauu..du>>
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
In this work, we investigate the following question: how can

---

Cros-cnnvrooment Cooperation Enables Zero-shot Multi-agent Coordination
Population Bapslation-Based Training
Cros--nnviromment Cooperation
Evaluation
(PBT)
(CEC)
Many Partners
One Pariner
Coordization Tack
PBT
CBC
Trains cooperate with
Trains cooperate with
Novel Partners, Same Environment
Zero-shot Courdination
Zero-shot Coordination
Leurning Agent
Leurning Agent
Many Environments
Partner, Nonel Environments
Coordiaation Failure
X
Zero-shot Coordination
One Environment
Trains to cooperate Un
Trains to coaperate
Novel Partners, Novel Environmennts
Courdination Failure
X
Zero shot Coordination
Figure 1. Overview of learning general coordination through Cross-environment Cooperation (CEC). By training agents in self-play on a large distribution of environments, we find that agents develop the ability to coordinate with novel partners and novel problems, contrasting with prior work which suggests self-play is insufficient for leaming general norms for cooperation.
we train AI agents capable of zero-shot collaboration with novel partners in novel tasks? To investigate this, we focus on two main sources of variation during training: partner diversity and environment diversity. While PBT methods focus on partner diversity to encourage agents adapt to different strategies on single-task. we hypothesize that training across diverse environments will instead foster richer understanding of the task structure itself, enabling agents to generalize to novel partners and settings.
ronmental exposure translate well to human-Al interactions.
The main contributions of this work are:
1. Cross-Environment Cooperation: A paradigm for ZSC that replaces partner diversity with environment diversity. Via procedural environment generation, we eliminate the need for partner populations while train- ing a single policy to cooperate across diverse tasks.
2. Algorithmic infrastructure:
(1) Fast Jax- eax-based proce- dural generation for Overcooked (1.16 x 10 layouts, 10M steps/min); (2) A toy benchmark isolating envi- ronmental vs. partner diversity, demonstrating CEC's partner and environment generalization over PBT.
To systematically test our hypothesis and isolate the impact of environment variation compared to partner variation, we present a new paradigm, Cross-environment Cooperation (CEC), in which agents are trained via self-play (with single partner) to cooperate across wide variety of proce- durally generated tasks. To evaluate CEC, we first test on both a toy environment to illustrate key principles, and then scale up to the human-Al coordination benchmark, Over- cooked. Overcooked is a 2-player, cooperative 2D cooking game where an AI agent collaborates with an AI or human partner to prepare a recipe (Carroll al., 2020; Wu" al., 2021; Strouse et al., 2022; Zhao et al., 2022; Sarkar et al., 2023). We design procedurally generated Overcooked en- vironment implemented in Jax, enabling high performance and efficient training speeds of up to 10 million steps per minute on a single GPU. Unlike previous work, which stud- ies at most five handcrafted Overcooked levels (Carroll et al., 2020; Strouse et al., 2018; Zhao et al., 2021; Myers et al., 2025), our generator creates up to 1.16 x 10 diverse and solvable kitchen configurations.
We find that environment diversity outperforms part- ner diversity in eross-play performance. Through analyzing generalization to different agents in cross- play, and via Empirical Game Theorett analysis, we show CEC outperforms PBT and other baselines.
4. Human-AI cooperation insights: Human studies re- veal CEC outperforms PBT in cooperation score and state-of-the-art methods in qualitative evaluations by participants, demonstrating its success in realistic co- operative scenarios.
2. Related Work
Building agents that can coordinate with novel people quickly has the potential for broad impacts across robotics (Breazeal et al., 2005; Sheridan, 2016), digital assistants (Guo et al., 2024; Poddar et al., 2024; Ying et al., 2024), and other scientific domains (Ghazimirsaeid et al., 2023; Roche et al., 2008; Castelfranchi, 2001).
Our experiments intriguingly reveal that by training on di- verse environments, agents learn to consistently improve generalization to new partners (see Figure 1). We conduct extensive simulated and human experiments to evaluate the performance of CEC agents against sfate-of-the-ar (SOTA) baselines. Our human study reveals that CEC agents out- perform PBT on performance and outperform all methods on subjective measures of cooperation, suggesting that the generalized cooperative skills learned through diverse envi-
Self-Play (SP) has been highly successful in zero-sum games because there is only single mixed strategy equi- librium (Xia et al., 2018; Silver et al., 2017; Vinyals et al., 2019; Zhou et al., 2020). However, when applied to co- operative games self- often converges to a brittle and inflexible policy that struggles with unfamiliar partners that
2

---

Cros--nnvirommntt Cooperation Enables Zero-shot Multi-agent Coordination
Initial State
Goal States
Randomized Initial States
can be suboptimal, and that regret-based sampling enables agents to efficiently learn compete in novel scenarios with novel partners (Samvelyan et al., 2023a; 2024). McKee et al. (2022) find environment diversity improves agents' ability to collaborate on novel levels in the ZSC setting, but they do not demonstrate the benefits of this approach with ad-hoc partners such as humans, the effects of combining partner with environment diversity, the relative benefits of environ- ment diversity compared to partner diversity, or deeper qualitative understanding of the effect of environment diver- sity on learned cooperation strategies. Related to our work, Ruhdorfer et al. (2024) study unsupervised environment design (UED) in the context of Overcooked. However, their work does not prevent the generation of impossible coor- dination challenges (Dennis et al., 2021; Mediratta et al., 2023; Li et al., 2023) and their results reveal poor general- ization performance to new partners held-out levels. In contrast, we show training across many coordination tasks with the same partner still can improve generalization to novel partners.
n. Fixed Task
b. Procedural Generation
Figure 2.
The Dual Destination Problem. In the fixed task (a), players start in opposite squares and must enter different green squares from each other to receive reward. In the procedurally generated variation (b), the initial positions of the green goal cells and agents are randomized.
play in novel ways (Strouse et al., 2022; Ma et al., 2023). In- tuitively, when training in self-play in a zero-sum game, the training procedure provides a continuous curriculum of di- verse experience as the model is continuously rewarded for exploiting their opponent. In cooperative games with multi- ple equilibria, the situation is reversed. Once an equilibrium is found, neither player has an incentive to unilaterally ex- plore other equilibria. Thus, diverse experiences are not generated through self-play in this context.
3. Technical Preliminaries
A two-player cooperative Markov Game is defined tuple (S, A, T, R, H). where S are states, A are actions (shared by both agents), T is the deterministic function T : 5 x A x A + S, rewards are R S x A x A -> IR, and the game horizon is H. Both the transition and re- ward functions are assumed to be unknown. We investigate the problem of training a cooperator policy ge which can achieve high reward when paired with many different part- ner policies म. P, where P represents distribution of possible partners, analogous to the distribution of humans an agent might need to assist. We assume that cooperation also takes place across many different environments. Here we define each environment, or cooperation task, as drawn from set of possible tasks m -M. The task m defines the initial state distribution, p(so (m). but tasks share transition dynamics T and reward function R. Each different task m is analogous to a new environment layout that may signif- icantly alter the space of effective coordination strategies that will lead to high reward. We define the score obtained in the cooperative game obtained by summing the joint per- timestep rewards when the cooperator ae plays partner "p in task m as:
Population-based training (PBT) has been explored as way to combat the shortcomings of self-play in coopera- tive games. PBT trains cooperator agent to learn a best response to a diverse pool of partners and thus experience multiple equilibria of the game (Vinyals et al., 2019). PBT- based methods generally outperform self-play in zero-shot Human-AI coordination. In Overcooked, previous works (Carroll al., 2020; Strouse et al., 2022; Zhao et al., 2022: Sarkar al., 2023) induced partner diversity training time through variations in neural network initializations or auxiliary loss functions. While PBT allows agents to train against different strategies for single task, it is compu- tationally expensive since each task requires first training a sizable population of agents. In contrast, our approach systematically varies the environment instead of the partner distribution, eliminating the need train multiple policies.
Procedural Environment Generation. Recent work has demonstrated that procedurally generated environments can improve the generalization of reinforcement learning (RL) methods in single and multi-agent settings (Cobbe et al., 2020; 2019; Fontaine et al., 2021: Carion et al., 2019; Chen al., 2023: Samvelyan et al., 2023b). These studies show that exposure a large and diverse set of samples enhances generalization (Cobbe et al., 2020). However, they typically evaluate agents with the same team seen during training, which doesn't 't address the core challenge of zero-shot co- ordination (ZSC). There has been work in the zero-sum setting showing environment diversity and partner diversity are not completely orthogonal axes and prioritizing either
S(Tp; TC, m) = E
sg so a² a²>xx woCC
Σ R(s,, of ag)
The objective of cross-play (XP) evaluation is to test how well a cooperator policy To performs when paired with a novel partner policy dp in an environment m, L.c evaluate S(Tp. Re, m). In line with prior work (Strouse et al., 2022; Zhao et al., 2021; Yan
Cross-Play (XP) Evaluation:
3

---

Cross-nnvirommnnt Cooperation Enables Zero-shot Multi-agent Coordination
al., 2023), we simulate novel partners for XP evaluation by training multiple agents using the same algorithm with different initial random seeds. Doing results in different network initializations and exploration patterns, causing agents to learn arbitrarily different, yet successful, ways to coordinate on a problem (Carroll et al., 2020), Collaborating with novel initializations of the same learning algorithm is referred as the Zero-shot Coordination (ZSC) setting (Hu et al., 2020). We evaluate all agents in ZSC, but also study cooperation in settings where agents must collaborate with novel partners that trained with different learning algorithms, also referred to as "Ad-hoc Teamplay" (Stone et al., 2010a).
100 Procedurally Generated Tasks
Fixed Task
Normalized XP Reward
0.8
0.4
0.0
IPPO FCP CEC Algorithm
IPPO FCP CEC Algorithm
Figure 3. Evaluation of TPPO and FCP baselines the Fixed and Procedurally generated versions of the Dual Destination problem (error bars show the standard error of the mean). CEC generalizes better in both cases (p < 0.001 for t-tests comparing CEC to both FCP and IPPO).
Population-based based training (PBT): (e.g. (Strouse et al., 2022; Zhao et al., 2021; Liang et al., 2024)) aim to con- struct a diverse set of simulated partner policies P {TI, m...... n } to simulate various human behaviors, but focus training on a single task m. Thus, they optimize:
blue) begin on the opposing sides of a grid without any walls. They are both given a +3 reward for moving to opposing green grid cells. In the basic setup, these grid cells are equidistant from each other and the agents' original starting position, as illustrated in Figure 2(a). The agents receive a -1 step cost and can move up, down, left, right, or stay in place. The state is fully observable.
J(TC) = E (S( TC, m)]
(1)
For example, Fictitious Co-Play (FCP) is a popular PBT- based method, where single cooperator agent tries to learn best-response policy to a population of self-play agents at different points of their learning progress (Strouse et al., 2022).
We hypothesize that self-play (SP) agents will have poor cross-play (XP) performance in this game, because they will pick convention (red agent goes up, blue goes down) that will not generalize to different SP agents which found different convention. PBT methods like FCP may learn more general strategy, such as "go up if someone goes down, and down if they go up." However, these policies are still brittle: if the goal location is shifted by even a few squares or the agents begin in a novel state, the FCP-trained agent will not have experience training this environment, and thus, we hypothesize that it will fail.
4. Cross-Enviromment Cooperation Improves Partner Generalization
The core hypothesis in our work is that enhancing the diver- sity of training tasks will improve agents' ability to gener- alize to both new tasks, and new cooperation partners. Our approach, Cross-Environmen Cooperation (CEC), trains a cooperator policy, TC. by sampling diverse tasks from broad distribution of tasks, m ~ MM. To isolate the effect of task diversity from partner diversity, train the CEC cooperator policy. The objective of CEC is thus defined as:
To test whether cross-environment training can ameliorate these shortcomings, we train CEC model on the Dual Destination game by randomizing the agent starting and goal positions at the beginning of new episode. We show examples of potential initial states in Figure 2(b). We ensure that the train task used for the other methods ('Fixed Task') is held out from the CEC train distribution. We then IPPO, a SOTA multi-agent SP algorithm (de Witt et al., 2020), to train agents to optimize the CEC objective in Eq. 2. The CEC model was trained without a population of other agents or any additional auxiliary losses.
self-play to
((TC) =
Te, m.)l
(2)
By sampling diverse tasks, CEC encourages the cooperator policy to generalize its behavior to handle a variety of coop- erative scenarios. Unlike PBT, which requires maintaining a large pool of partner policies, CEC simplifies the training process because only requires training a single policy. We investigate whether using CEC to optimize Eq. 2 can ac- tually provide ZSC performance gains over using PBT to optimize Eq. 1.
AI-AI ZSC Evaluation. We compare the ZSC performance between SP (IPPO), FCP, and CEC in the Dual Destina- tion tasks shown in Figure 2, and include the task used to train the SP and FCP methods ('Fixed Task'), as well as 100 novel procedurally generated tasks. We first measure how well models generalize cooperation to novel partners (cross play performance with novel partners). Second, we measure how well they generalize to novel partners novel
Dual Destination Game. To gain intuition for the existing gap in the ability of multi-agent reinforcement learning methods to collaborate with partners they have not seen during training (Lowe et al., 2017), we design a simple gridworld environment as follows: two agents (red and
4

---

Cros--nnvirommnt Cooperation Enables Zero-shot Multi-agent Coordination
environments (XP performance with novel partners in novel environments).
Figure 3 illustrates the pitfalls of training a naive cooperator in self-play: even with just two options to choose from in response to another's actions, agents cannot adapt well at test-time to a novel partner's strategy and thus fail to coor- dinate even on the tasks they's 've seen during training. FCP does better by learning adapt strategies within a single level by training against diversity of partners. However, Figure 3 shows that it fails to complete similar tasks with mi- nor structural differences. In contrast, CEC agents perform better with novel partners in the Dual Destination Game on an evaluation layout it has never seen during training (Figure 3). For context, an oracle agent that perfectly responds the two optimal strategies in Figure 2 would re- quire steps of receiving 11 step cost move the target location before receiving a (3 positive step cost) reward for 97 steps, equating to 0.955 normalized reward. CEC scored 0.931 normalized reward with a standard error of 0.013, indicating it underperforms the oracle's ' cross play performance by about 2.5%.Moreover. Figure indicates that CEC models also generalize 100 new initial state configurations and new partners using the same amoun! of compute the vanilla single-task IPPO baseline. We extended our analysis in the Appendix to include partially observable and multi-task variations of the Dual Destination problem (Appendices A.2 and A.3, respectively). Our find- ings consistently show that even with imperfect information and task uncertainty, CEC agents outperform population- based and naive self-play methods in cooperating with novel partners novel problems, mirroring the trends observed in the fully observable ZSC case.
Figure 4, Five original Overcooked layouts. Left to right: Asym- metric Advantages, Coorlination Ring, Counter Circuit, Cramped Room, Forced Coordination.
Figure 5. Sample from the billions of solvable, diverse Overcooked tasks created by our procedural environment generator.
objects are sampled. We ensure tasks remain solvable by placing essential objects in reachable areas from the layouts in Figure 4 and detailed in A.1. We introduce additional environment diversity by sampling additional goal locations, plate piles, pots, and onion piles on unoccupied walls. The grids are also rotated randomly to encourage better represen- tation learning. For example, if an agent learned to complete task on very wide layout, should be able to do that same task if it is rotated vertically by performing simple mapping from the left/right actions to up/down, and vice versa.
Our procedural generator creates new coordination chal- lenges in Overcooked, shown in Figure 5. Moreover, Jax allows us to run the entire training and evaluation pipeline, from the environment generation the neural network up- dating of agents, /0 million steps per minute on a single GPU. We leverage this speed to train CEC agents, and all other baselines, for 3 billion steps. By standardizing the training duration for all algorithms, we can directly compare whether it is better to invest compute in training on more environments or in methods like PBT.
These findings suggest that investing in training cooperative agents on a large distribution of environments is potentially much more effective than training across a large distribution of partners. just as prior work has suggested this kind of pro- cedural generalization (or domain randomization) improves generalization in the single-agent setting in robotics (Jakobi, 1997; Sadeghi & Levine, 2016; Tobin et al., 2017).
5. Experiments
Procedurally Generated Overcooked. To test whether these findings replicate in a more scaled-up scenario, we extend the Overcooked environment from the JaxMARI. project to support a wider variety of levels (Rutherford et al., 2023).
From this point on, we will refer to agents trained to coop- erate across multiple coordination challenges by optimizing Eq. 2 as CEC, agents trained on a single task as ST, the self-play performance of the agents as SP, and the cross-play performance of the agents as XP. Our primary focus is on the XP setting, which measures how well agents collaborate with novel partners on tasks they have never seen before.
Previous work on Overcooked has focused on five layouts that possess diverse coordination challenges (Carroll et al., 2020; Strouse et al., 2022; Zhao et al., 2021; Yan et al., 2023). For our new enviromment, we uniformly sample the wall structure from each of these five layouts, then ran- domly generate features like goals, plates, pots, and onions within the grid. Doing structures the generation process and introduces variable complexity depending where the
When evaluating AI-AI and Human-Al coordination, we aim to answer the following research questions:
increasing environment diversity more effective than increasing partner diversity for ZSC?
Compared to ST methods, how well do CRCs general-
5

---

Cros--nnvirommnn Cooperation Enables Zero-shot Multi-agent Coordination
100 Procedurally Generated Grids
has generalize to new partners and environments. To- wards mitigating the bias against our method and answering Research Question 3, we study the effects of trading off generalization for specialization in CEC models. After train- ing a single CEC agent on a distribution of environments created by the procedural generator, we create five copies of the model, one corresponding to each of the original five layouts in Figure 4 which were held out during training. For each copy of the CEC agent, we perform additional 100 million steps of training on a single layout with reduced learning rate, again in self-play using IPPO. We call this approach "CEC-Finetune (CEC-FT)."
5 Heldout Grids
XP Reward
160
80
TPPO
FCP CECCEC-FT IPPO E3T FCP CECCEC-FT Algorithm
Algorithm
Figure 6. Evaluation of baselines on (left) original Overcooked layouts vs. (right) 100 procedurally generated held-out layouts (standard error bars). Single-task methods and PBT struggle in both settings, while CEC agents generalize effectively. Finetuning CEC on a single grid improves XP performance original layouts (outerforming FCP and IPPO; < 0.01, t-test) but reduces generalization on novel layouts. CEC sigmificantly surpasses all baselines in procedural generalization tasks (p < 0.0001, t-test).
Human Studies. Due to the expense of human evalua- tions, our Human-AI evaluations only looked at the two most challenging grids of the original five, Counter Circuit and Coordination Ring. We recruit 80 human participants for our study using Prolific, where 40 participants com- plete each layout. Our study follows a protocol approved by our university's IRB. During the study, each user plays multiple rounds of Overcooked with a partner via a web interface, where in each round the partner is controlled by one of the models, in randomized order. We sample a new model trained with a different random seed for each of the game rounds. Subjects played with agents for 200 timesteps and the entire experiment took approximately 30 minutes. After each round, the user answered questions about their subjective experience playing with the agent using a Likert scale (Likert, 1932). This survey allows us to quantify the factors that most heavily influence overall per- formance and users' preferences for coordination partners. All of our Human-Al experiments and surveys utilized the NiceWebRL Python package (https: / ht//ggtttuuu com/ wcarvalho/ n cewebrl), 1), which leverages Jax's 's paral- lelizability to efficiently crowd-source participant data on reinforcement learning environments.
ize cooperative strategies to novel environments?
3. How close can CEC come to fftte-of-the-ane perfor- mance with novel humans for a single task it has never seen before through environment diversity alone?
Baselines. For single-task baselines, we train six seeds for three different agents for each of the original five layouts in Figure 4, one with vanilla IPPO (de Witt et al., 2020), one with FCP (Strouse et al., 2022), and one with Efficient End- to-End Training (E3T) (Yan et al., 2023). E3T is the state-of- the-art algorithm for single-task ZSC in Overcooked. It is a SP method that achieves high XP performance by adding randomness to one of the partner's policies during training, and training an auxiliary network which tries to predict the actions of other agents in the world. We test CEC's cross-play performance with novel partners on each of the single-tasks FCP and E3T were trained on.
Evaluation Protocol. Following prior work (Zhao et al., 2021; Carroll et al., 2020; Yan et al., 2023; Strouse et al., 2022), we first evaluate the ability of all models to generalize to new partners on the five original Overeooked Layouts Note that we hold out those five layouts from the CEC generator, so that when we evaluate CEC on these layouts are able test generalization across both partners and tasks. Second, we introduce an additional evaluation setting where we have the Overcooked procedural environment generator create 100 coordination challenges that neither the ST baselines nor any of the CEC agents have seen during training and assess how well the different approaches can generalize to both novel partners and novel environments. We train six seeds for each type of agent. The architectural details are included in A.7.
6. Results
Q1: Is increasing environment diversity more effective than increasing partner diversity of ZSC? Figure 6 shows the XP performance of the baseline models aver- aged across the five original Overcooked layouts. Although ST approaches are capable of adapting to partner strate- gies during training time, they fall short in XP compared to CEC models. Fine-tuning CEC agents on a single grid layout resulted in a substantial improvement in cross-play generalization performance. While it is unsurprising that training in the test environment helps performance, even without training in the test layout or using any strategies to enhance partner diversity, CEC outperforms all baselines in terms of XP. The success of CEC and CEC-Finetune in XP indicates the benefits of both broad pre-training with task specific adaptation. More importantly, we obtain evi- dence support an affirmative answer to research question
Cous--Envrrommet Cooperation as Pre-training Step. Holding out the original five layouts from the CEC genera- tor puts CEC at a disadvantage compared to ST baselines, which only have to generalize to novel partners, while CEC
6

---

Cros--nnvirommnt Cooperation Enables Zero-shot Multi-agent Coordination
1: increasing environment diversity can actually be more effective at improving cross-partner generalization, than training on a single environment with many partners.
CEC Finetune
CEC Finetune
CEC Finetune
0.5
One challenge with assessing coordination using the single- task levels is that it does not control for the possibility that all seeds just happen to play the same strategy (e.g., "always rotate clockwise."". This would result in high cross play scores without the ability generalize to novel partners. Therefore, compute cross-algorithm cooperation scores, shown in Figures 21 and 22, to control for this possibility and evaluate agents in the Ad-hoc Teamplay setting. Us- ing this cross-algorithm performance matrix to represent a meta- game, we conduct an empirical game-theoretic anal- ysis where players choose model types rather than actions. Essentially, players in the meta-game choose a model (like CEC vs. FCP) in order to maximize cross-play score. This can also be see as treating Figures 21 and 22 as a payoff matrices, and analyzing the equilibria of these games. This approach allows us to interpret how a simulated popula- tion of agents would adopt different strategies over time, revealing attractors, equilibria, and cyclic behaviors that may not be apparent from simple win rates or Elo ratings (Wellman et al., 2024). Following the approach outlined in (Tuyls et al., 2018; Serrino* et al., 2019), Figure 8 shows the gradient of the replicator dynamic in these meta-games as a way of assessing the dynamics and equilibrium of the meta- game. For both the five original tasks and the 100 procedurally generated tasks, the direction of the gradient towards either CEC or CEC-Finetune. This shows that CEC trained models generalize robustly across different algorithms.
FCP
IPPO
CEC
FCP
E3T
IPPO
5 Original Tossis
CEC
CEC
CEC
1.0
0.5
FCP
iPPO
CEC-Rratune
FCP
E3T
IPPO
100 Procedurally Generated Thsks
Figure 8. Empirical game-thcorett evaluation of cross cross-algorithm play on the (a) five original and (b) 100 procedurally generated Overcooked tasks. Arrows show the gradient of the replicator dynamic on the cross-algorithm meta-game. Vectors flow towards CEC and CEC-Finetune indicate they are likely equilibria.
reveals that FCP and E3T completely fail generalize to novel tasks, receiving 0 reward on any of the 100 test tasks, While both methods try to increase partner strategy coverage in self-play by adding entropy to the partner policy, they fail to generalize to similar, procedurally generated layouts due to insufficient enviromment coverage. Without encountering the same task in diverse scenarios, agents learn low-level sequences (e.g., "move the third cell from the left and in- teract") rather than higher-level task structures (e.g.. "cook onions and deliver them"), hindering environment general- ization.
We also assess how well humans can collaborate with ST single-task agents playing layout they have never seen during training. We call the IPPO and FCP versions of these agents IPPO and FCP respectively. Just as in simulation, we find that models only optimized to cooperate on one task cannot generalize to new tasks with ad-hoc partners (Figure 9), and are consistently rated the most frustrating to play with by humans (Figure 27). Taken together with the FCP cross-play performance, this provides strong evidence that ST methods cannot generalize at all to novel, similar cooperative settings whereas CEC agents can.
Q2: Compared to single-task methods, how well do CECs generalize their cooperative strategies to novel environments? Similar to the Toy environment, the eval- uation on the held-out Overcooked layouts created by the procedural environment generator, as depicted in Figure 6,
Reward
100
Interestingly, Figure 6 shows CEC-Finetune did not perform as well as vanilla CEC on the novel procedurally generated layouts. This highlights a tension between generality and specialization in agent training. While CEC fine-tuning demonstrates that pre-training on diverse problems provides solid foundation for learning to collaborate on a specific problem with new partners (Figure 6), it also results in loss of the ability to generalize to novel levels.
0
10
15
20
25
30
Training Progress (100M steps)
SP Training
XP Coord Ring
XP Asymm Advantages
XP Cramped Room
XP Forced Coord
XP Counter Circuit
Figure 7. CEC SP Training Performance compared to XP Perfor- mance on 5 held-out levels. Despite the distribution sampling each layout predicate uniform, CEC gets better at different layouts at diffcrent rates as it consistently improves across all tasks.
In Appendix A.4, we explored whether combining partner and environmental diversity enhances agents' ZSC abilities. We trained E3T agents within the CEC framework and eval- uated their XP performance on unseen tasks with unfamiliar
7

---

Cros-cnvironment Cooperation Enables Zero-shot Multi-agent Coordination
Average Rating # +Scccssess
FCP models, but fall short of E3T, which is the state-of- the-art method for single level ad-hoe single level ad-hoc collaboration performance with humans. While reward is an important metric to optimize, past work (Carroll et al., 2020) has shown that it can obfuscate frustrating behaviors, such as forcing the human to adapt to the agent's 's strat- egy, or completing the task effectively but independently, while not truly cooperating with the human. Therefore we must also consider human subjective preferences as equally important in assessing an agents' human-AI cooperation abilities. In Figure 9, we show that across 7 different met- rics of human enjoyment, CEC consistently outperforms all baselines, with CEC-FT significantly surpassing E3T (p < 0.01, / 3.1233).
IPPO
FCP-
IPPO
CEC-FT
N
IPPO
FCP
IPPO
FCP Algarithm
E3T
CEC
CEC-FT
Figure 9. (Top) Average success rates of algorithms cooperating with ad-hoc human partners Counter Circuit and Coordination Ring, with standard error bars. CEC outperforms PBT methods and approaches E3T's performance, despite only training diverse layouts. Using 2-sided t-test, CEC significantly outperforms FCP (p < 0.001, t-test). (Bottom) Human ratings of algorithms' cooperative ability across 7 metrics, averaged over Counter Circuit and Coordination Ring evaluations, with standard error bars. CEC and
So how is it that CEC obtains such high ratings, but less than SOTA score in the tasks? A closer look at users' quali- tative assessments of playing with the different models in Figures 27 gives us partial explanation for why this may be the case. We see that CEC models were ranked highest by users in terms their ability to adapt to the participant's behaviors, while also being the least frustrating to work with and most consistent in their actions. Moreover, CEC was rated most enjoyable cooperate with and best in terms of ability to coordinate. We synthesize the correlation between different users' qualitative ratings to establish hierarchy of factors most relevant to human's 's perception of effective cooperation in Overcooked, and show our findings in Fig- ure 10. We report Cronbach's alpha score as 0,874, and use this as a strong signal to validate using qualitative met-
are preferred partners despite lower rewards. CEC-Finetune significantly outperforms FCP (p < 0.01, t-test) and E3T (p 0.01, t-test).
partners. As Figure 16 illustrates, introducing novel partners while learning in a constantly changing environment did not improve agents' ZSC capabilities. This suggests further research is needed to determine how best integrate these two forms of diversity to realize their combined benefits.
Last, we analyze XP performance at different points in the learning trajectory of CEC agents. Figure 7 shows the CEC SP training reward and the corresponding XP evaluation reward on each of the five layouts at the same point in training. We find that CBC XP performance improves at different rates across layouts. This can partly be explained by the diversity in optimal coordination strategies across the original five layouts (Figure 4). In both Cramped Room and Coordination Ring, the spatial constraints lead agents to discover cooperative strategies more quickly. However, for layouts such as Counter Circuit, where agents have many options for where to pass items along the middle border, whether rotate around the middle wall clockwise counter clockwise, etc., CEC's XP performance improves slower but increases steadily. It could potentially be driven even higher with more training.
1.0
1.00
0.000.223
0.59
0.31
0.38
In My Way
0.23
1.00
0.59
0.58
Consistent
0.59
0.41
1.00
0.000.50000
0.50
0.66
Frustrating
0.5
0.31
0.51
0.50
1.00
0.61
Human-like
0.33
0.49
0.57
0.61
0.000.68..77
Adaptive
0.35
0.52
0.
0.67
0.68
1.00
Enjoyed
0.38
0.58
0.60
0.67 0.71 0.79 1.00
Coordination
In My Way
Consistent
Frustrating
Human-like like
Adaptive
Enjoyed
Coordination
Q3: How close can CEC come to state-of-the-are perfor- mance with novel humans for a single task it has never seen before through environment diversity alone? To answer this question, analyzed how well CEC agents can collaborate with new people novel tasks under the Ad-hoc Teamplay setting. As Figure 9 demonstrates, when evaluated in terms score the cooperation task, on lev- els that ST methods have seen during training. CEC and CEC-finetune are able collaborate better than IPPO and
Figure 10. Heatmap depicting the Pearson's Correlation Coeffi- cient between users' qualitative rating of different Al collaborators in Overcooked. By clustering based on correlation degree, we categorize the factors most indicative of what makes good collaborator. We report a Cronbach's 's alpha score 0.874
8

---

Cros--nnvrroment Cooperation Enables Zero-shot Multi-agent Coordination
* Collisions
Acknowledgments
50
25
We would like to thank the Cooperative AI Foundation, the Foresight Institute, the Amazon+UW Science Gift Hub, the UW Tsukuba NVIDIA Amazon Cross-Pacific AI Initiative and the Sony Resarch Award Program for their generous support of our research. This work was additionally sup- ported by NSF CCF 2212261, NSF IIS 2229881. the Alfred P. Sloan Research Fellowship, and the Schmidt Sciences AI 2050 Fellowship. We are also grateful for this work being supported by a gift from the Chan Zuckerberg Ini- tiative Foundation establish the Kempner Institute for the Study of Natural and Artificial Intelligence. Lastly, would like express our gratitude to our colleagues the Social Reinforcement Lab and the Computational Minds and Machines Lab for inspiring conversations and insights during the course of this project.
IPPO-
FCP
IPPO
FCP Algorithm
E3T
CEC
CEC-FT
Figure/ 11. Average number of collisions between humans and AT partners on Counter Circuit and Coordination Ring. with standard error bars shown. CEC achieves the lowest average collision rate.
rics, in addition to reward, as an indicator of CEC's success compared to other baselines.
We also note that CEC's increased proclivity to adapt its behaviors to people can lead to lower rewards if participants are playing suboptimal strategy. On the other hand, E3T, which has seen the environment during training it is eval- uated on, is rated as less adaptive (see Figures 28 and 29), and instead may focus too much on optimizing score. In playing with the agents, we observed that CEC is much better at avoiding collisions and getting out of the player's s way, even though this may lead to less reward. Figure 11 quantifies the frequency of collisions between humans and different AI collaborators. The results indicate that, despite achieving lower rewards than the SOTA method E3T, CEC has fewer collisions with humans on average. This aligns with participants' subjective assessments of model behavior (Figure 27). We hypothesize that this collision-avoidance behavior reflects a general norm learned by CEC, which enhances performance across wide range of cooperative tasks. This supports our hypothesis that cross-environment training helps agents learn more generalized cooperative strategies that work not only in a range of environments, but with range of partners.
Impact Statement
This paper presents novel approach to training agents to collaborate with people it has not seen before. As such, it has the ability to improve the lives of many applications as household robotics, autonomous driving, or language assistants. To provide evidence for the merits of our ap- proach, we conducted studies with human participants. We made sure to follow all ethical practices described under the instructions of university's 's Institutional Review Board (IRB), including but not limited to compensating partici- pants at minimum wage and receiving informed consent. As a final point, while the work in this paper described how to build a general cooperative AI, is not clear or well studied if a similar approach could be used to create machine capable of harming humans it has not seen before in a wide range of cases. Future works should try establish whether this is the case and how to mitigate these potential risks.
References
7. Discussion
Nicegui nicegui.io. https:/nniceuui.io. [Accessed 26-09- 2024].
We introduce enoosoenvirr Cooperation, a novel ap- proach to 7SC in multi-agent reinforcement learning. Cross- environment training helps agents learn more generalized cooperative strategies that work not only in range of envi- ronments but with range of partners. Although trained in self-p self-play, they zero-shot coordinate with new partners and in new environments never seen during training. We show that CEC succeeds in cooperating with current state-of-the the art baselines and with human users. These results challenge the prevailing wisdom that self-play is insufficient for ZSC and Ad-hoc Teamplay in cooperative games. Future work will explore composing CEC with other training algorithms. For cooperative AI agents to work effectively with us in our offices and homes, agents must rapidly adapt to a wide range of diverse environments and partners.
Atchley, P., Pannell, H., Wofford, K., Hopkins, M., and Atchley, R. A. Human and Al collaboration in the higher education environment: opportunities and con- cerns. Cognitive Research: Principles and Implica- tions, 9())200, April 2024. ISSN 2365-7464. doi: URL https:: /doi. 024 00547-92
10.1188664123550044-0033 org/10. 1100:/.1111///111
Bonnet, C., Luo, D., Byrne, D., Surana, S., Abramowitz, S.,
Duckworth, P., Coyette, V., Midgley, L. I., Tegegn, E., Kalloniatis, T., Mahjoub, O., Macfarlane, M., Smit, A. P., Grinsztajn, N., Boige, R., Waters, N., Mimouni, M. A., Sob, U. M., de Kock, R., Singh, S., Miveloo-Bllano,, D.,

---

Cros-cnvirooment Cooperation Enables Zero-shot Multi-agent Coordination
Le, V., Pretorius, A., and Laterre, A. Jumanji: diverse suite of scalable reinforcement learning environments in jax, 2024. URL https: http:a////aaiii..g/a/b////////// 09884.
Dennis, M., Jaques, N., Vinitsky, E., Bayen, A., Russell, S., Critch, A., and Levine, S. Emergent complexity and zero- shot transfer via unsupervised environment design, 2021. URL https::////... arxiv. orq/ abs 2012. 22096. 02096.
Breazeal, C., Kidd, C., Thomaz, A., Hoffman, G., and Berlin, M. Effects of nonverbal communication on efficiency and robustness in human-robot tcamwork. pp. 708 - 713, 09 2005. ISBN 0-7803-8912-3. doi: 2005. 200.00000
Dinneweth, J., Boubezoul, A., Mandiau, R., and Espié, S. Multi-agent reinforcement learning for autonomous vehicles: a survey. Autonomous Intelligent Systems, 2(1): 27, November 2022. ISSN 2730-616X. doi: 10.1007/
$43684-002-000445-2 URL https: /ttp///oioooooooooooooooo /ttp:////oooo/...//////////// org/10. 0007/s43684-022- 00045--200
Carion, N., Synnaeve, G., Lazaric, A., and Usunier, N. A structured prediction approach for generalization coop- erative multi-agent reinforcement learning, 2019. URL ht https://arxae
Fontaine, M. C.,, Hsu, Y.-C., Zhang, Y., Tjanaka, B., and Nikolaidis, On the importance of environments in human-robot coordination, 2021. URL https:// a arxiv. www.bbgg///b.oooooooooo........a /t.bb////6... 2206. 2106.10853.
org/ wttg/bs////// abs/19/0.111111 08809.
Carroll, M., Shah, R., Ho, M. K., Griffiths, T. I.., Seshia, S. A., Abbeel, P., and Dragan, A. On the utility of learning about humans for human-ai coordination, 2020. URL https: /twxxv.vvvvoo//a hwtgg//b//// wtt.p////11....1 057889
Ghazimirsacid, S. S., Jonban, M. S., Mudiyansclage. M. W. Marzband, M., Martinez, J. L. R., and Abu- sorrah, A. Multi-agent-based energy management of multiple grid-connected green buildings. Journal of Building Engineering, 74:106866, 2023, ISSN 2352- 7102. doi: htts::/ooiogg///0001............ com/ URL.
Carvalho, Nicewebrl: framework for comparing hu- mans and ai across many domains, 2025. URL https: //github.
Castelfranchi, C. The theory of social functions: challenges for computational social science and multi-agent learning. Cognitive Systems Re- search, 2(1):5-38, 2001. ISSN 1389-0417. doi:
Guo, T., Chen, X., Wang, Y., Chang, R., Pei, S., Chawla, N. V., Wiest, O., and Zhang, X. Large language model based multi-agents: A survey of progress and chal- lenges, 2024. URL https: http:://axxxvv.r///ee// 1402.01680.
URL htttp::/www..ccinnces ocieeneeaartiicle/ii///39901111
com/
Chen, Y., Tang. C., Tian, R., Li, C., Li, Tomizuka, M., and Zhan, W. Quantifying agent interaction in multi- agent reinforcement learning for cost-efficient generaliza- tion, 2023. URL https:::/ :/ /twxxviivvi/////////aa/////aa http://orrgabb//1...0 07218.
Henrich, J., Heine, S. and Norenzayan, A. The weirdest people in the world? Behavioral and Brain Sciences, 33 (2-3):61-88) 2010. doi: 00.1017/5014055500999 152X.
Hu, H., Lerer, A., Peysakhovich, A., and Foerster, J. "Other- play" for zero-shot coordination. III, H. D. and Singh, A. (eds.), Proceedings of the 37th International Confer- ence Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 4399-44100 PMLR. 13-18 Jul 2020. URL httht:::: WRLLtttps///rrceeeeeeees /ptp/eeeeceeessssse .mlr. press v11 1 hh: html.
Cobbe, K., Klimov, O., Hesse, C., Kim, T., and Schulman, J. Quantifying generalization in reinforcement learning. In Chaudhuri, K. and Salakhutdinov, R. (eds.), Proceed- ings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learn- ing Research, pp. 1282-1289, PMLR, 09-15 Jun 2019. htRphtts:: /ttp:ttps//prrceeddiiie http///pooceeeeeeseeeeeee mlr www......r........ press/v97/ cobbe19ts 9a. html.
Jakobi, N. Evolutionary robotics and the radical envelope-
of-noise hypothesis. Adaptive Behavior, 6(2):325-368, 1997. doi: 10.1177/1059911239700666000 URL https: / //doi.org/10. wTw...11170001111110100000000000
Cobbe, K., Hesse, C., Hilton, J., and Schulman, Lever- aging procedural generation to benchmark reinforcement learning, 2020. URL http:::tp///o //tppp::////xvv.///////ss org/ abs/ 1912. 01588.
Kleiman-Weinet M., Ho, M. K., Austerweil, J. L., Michael L, L., and Tenenbaum, B. Coordinate co- operate compete: abstract goals and joint intentions in social interaction. In Proceedings of the 38th Annual Conference of the Cognitive Science Society, 2016.
de Witt, C. S., Gupta, T., Makoviichuk, D., Makoviychuk, V., Torr, P. H. S., Sun, M., and Whiteson, S. Is in- dependent learning all you need in the starcraft multi- agent challenge? CoRR, abs/2011.0953. 2020. URL https::/arre www.ivv.org///aae wwt.///g//bbbbbooo http:///////11..55...3
Li, W., Varakantham, P., and Li, D. Generalization through diversity: Improving unsupervised environment design.
10

---

Cros--nnirromentt Cooperation Enables Zero-shot Multi-agent Coordination
In Elkind, E. (ed.), Proceedings of the Thirty-Second In- ternational Joint Conference Artificial Intelligence, IJCAI-23, pp. 5411-5441 International Joint Confer- ences on Artificial Intelligence Organization, 8 2023. doi: 10.249665/iccai222233000 URL https:://// /to..org/////ooooooooooo..o.ooo. ww..24963jjcaaao
Myers, V., Ellis, E., Levine, S., Eysenbach, B., and Dra- gan, A. Learning to assist humans without inferring rewards, 2025. URL https://arxiv. / 2411.02623.
601. Main Track.
Nikulin, A., Kurenkov, V., Zisman, I., Agarkov, A., Sinii, V., and Kolesnikov, S. Xland-minigrid: Scalable meta- reinforcement learning enviromments in jax, 2024. URL 12044
Liang, Y., Chen, D., Gupta, A., Du, S. S., and Jaques, N. Learning to cooperate with humans using generative agents, arXiv preprint arXiv:2411.33944 2024.
Poddar, S., Wan. Y., Ivison, H., Gupta, A., and Jaques, N. Personalizing reinforcement learning from human feedback with variational preference learning, 2024. URL https: / wat.iviiiiivv///iia//aaaaaaaaiva http://awwwwiioaa////ooooooo http:///bb/2200.000.000 10075.
Likert, R. A technique for the measurement of attitudes. Archives of Psychology, 140:1-55, 1932.
Lowe, R., Wu, Y., Tamar, A., Harb, J., Abbeel, P., and Mor- datch, I. Multi-agent actor-critic for mixed cooperative- competitive environments. CoRR, abs/ 706.02275, 2017. URL /tttp::/arxxvv.or.t
Rabinowitz, N., Perbet, F., Song, F., Zhang, C., Eslami, S. A., and Botvinick, M. Machine theory of mind. In International conference machine learning, pp. 4218- 4227. PMLR, 2018.
abs al/ 1706. 02275.
Lu, C., Beukman, M., Matthews, M., and Foerster, Jaxlife: An Open-Ended Agentic Simulator, volume ALIFE 2024: Proceedings of the 2024 Artificial Life Conference of Artificial Life Conference Proceed- ings. July 2024. doi: 10. 10.1162/isal URL
Ribeiro, T., Gonçalves, F., Garcia, S., Lopes, G., and
Ribeiro, A. Charmie: collaborative healthcare and home service and assistant robot for elderly care. Applied Sciences, 11(16):7248, 2021.
https: http://oo.oooeooo httpp//cc/...1//ssalseee... eprint: p
Roche, B., Guégan, J.-F., and Bousquet, F. Multi- agent systems epidemiology: a first step for com- putational biology in the study of vector-borne dis- ease transmission. BMC Bioinformatics, 9(1):435, October 2008. ISSN 1471-2105. doi: 10.1186/ 1471-2105-9-435. URL https://doi. org/10. 1186/1471-2105-9-1
Ma, M., Liu, J., Sokota, S., Kleiman-Weiner M., and Foer- ster, N. Learning intuitive policies using action features. In International Conference Machine Learning, pp. PMLR, 2023.
Matthews, M., Beukman, M. Ellis, B., Samvelyan, M., Jackson, M., Coward, S., and Foerster, J. Craftax: A lightning-fan benchmark for open-ended reinforcement learning, 2024. URL https: / /aaxiviiivvv////ii//.aa////avavv org/ abs/ 1:02.16800
Ruhdorfer, C., Bortoletto, M., Penzkofer, A., and Bulling, A. The overcooked generalisation challenge. 2024. URL hbtpg//bb/224000
attps::/arxisn h 17949.
Rutherford, A., Ellis, B., Gallici, M., Cook, Lupu, A., Ingvarsson, G., Willi, T., Khan, A., de Witt, C. S., Souly, A., Bandyopadhyay, S., Samvelyan, M., Jiang, M., Lange, R. T., Whiteson, S., Lacerda, B., Hawes, N., Rocktaschel, T., Lu, C., and Foerster, J. N. Jaxmarl: Multi-agent rl environments in jax. arXiv preprint arXiv:2311.10094 2023.
McKee, K. R., Leibo, J. Z., Beattie, C., and Everett, R. Quantifying the effects of environment and popu- lation diversity in multi-agent reinforcement learning. Autonomous Agents and Multi-Agent Systems, 36(1); 21. March 2022. ISSN 1573-7454. doi: 10.1007/ $10458-022-095448 URL pttttp::/doo..ogg/// 1007/s10458 02200022-2220 09548-8.
Sadeghi, F. and Levine, S. (cad)S Real single- image flight without a single real image. CoRR, abs/1611.04200 2016. URL abs/16111 04201.
Mediratta, I., Jiang, M., Parker-Holder. J., Dennis, M., Vinitsky, E., and Rocktäschel, T. Stabilizing unsuper- vised environment design with a learned adversary. In Chandar, S., Pascanu, R., Sedghi, H., and Precup, D. Lifelong
(eds.), Proceedings of The 2nd Conference Learning Agents, volume 232 of Proceedings of Machine Learning Research, pp. 270-291 PMLR, 22-25 Aug 2023. URL https: httpa/::///pppppppeeeeee mlr.a. press/ v2.32/ medi ratta23a html.
Samvelyan, M., Khan, A., Dennis, M., Jiang, M., Parker- Holder, J., Foerster, J., Raileanu, R., and Rocktäschel, T. Maestro: Open-ended environment design for multi-agent reinforcement learning, arXiv preprint arXiv:2303.0337 2023a.

---

Cross-nnviromentt Cooperation Enables Zero-shot Multi-agent Coordination
Samvelyan, M., Khan, A., Dennis, M., Jiang, M., Parker- Holder, J., Foerster, J., Raileanu, R., and Rocktäschel, T. Maestro: Open-ended environment design for multi- agent reinforcement learning, 2023b. URL https:// arxiv.org abs 2..33.0.337
Strouse, D., McKee, K. R., Botvinick, M., Hughes, E., and Everett, R. Collaborating with humans without human data, 2022. URL https::/aaaaaaee /awxiv..rvvv.//aa///// org/ wwwp/rrg/////ee/eeee...o/eeeeeee abs/2110. 08176.
Tobin, J., Fong, R., Ray, A., Schneider, J., Zaremba, W., and Abbeel, P. Domain randomization for transferring deep neural networks from simulation to the real world, 2017. URL https: / wwwiaaaivvvooo org/ abs / 1703. 06907.
Samvelyan. M., Paglieri, D., Jiang, M. Parker-Holder, J., and Rocktäschel, T. Multi-agent diagnosties for robustness via illuminated diversity. arXiv preprint arXiv:2401. 13460, 2024.
Tomasello, M.
The cultural origins of human cognition. The cultural origins of human cognition. Harvard University Press, Cambridge, MA, US, 1999. ISBN 0-674-00070-6 (Hardcover). Pages: vi, 248.
Sarkar, B., Shih, A., and Sadigh, D. Diverse conventions for human-ai collaboration, 2023. URL htttt::///aaxit org/ abs/2310, 231111141...
Serrino* J., Kleiman-Weiner*, M., Parkes, D. C., and Tenenbaum, J. B. Finding friend and foe in multi-agent games. In Advances in Neural Information Processing Systems, volume 32, 2019.
Tuyls, K., Pérolat, J., Lanctot, M., Leibo, Z.,, and Graepel, T. A generalised method for empirical game theoretic analysis. CoRR, abs/ 803.06676 2018. URL http: //arxive org/ abs 06376
Sheridan, T. B. Human-robo interaction: Status and chal- lenges. Human Factors, 58(4):525- 532,, 2016. doi: 10. 1177/00187228816444666 URL https:t/p////...... aeoi.orgg 10. 10..1177001112081664488
Vinyals, O., Babuschkin, I., Czarnecki, W. M., Mathieu, M.,
Dudzik, A., Chung, Choi, D. H. Powell, R., Ewalds, T., Georgiev, P., Oh, J., Horgan, D., Kroiss, M., Danihelka, I., Huang. A., Sifre, L., Cai, T., Agapiou, J. P., Jaderberg, M., Vezhnevets, A. S., Leblond, R., Pohlen, T., Dalibard, V., Budden, D., Sulsky, Y., Molloy, J., Paine, T. L., Gulcehre, C., Wang. Z., Pfaff, T., Wu, Y., Ring, R., Yogatama, D., Wünsch, D., McKinney, K., Smith, O., Schaul, T, Lillicrap, T., Kavukcuoglu, K., Hassabis, D., Apps, C., and Silver, D. Grandmaster level in StarCraft II using multi-agent reinforcement learning. Nature, 575(7782); 350-354 November 2019. ISSN 1476-4687. doi: 10. 10.1038/
PMID: 27098262.
Shum* M., Weinann-Weierr* M., Littman, M. L.., and Tenenbaum, J. B. Theory of minds: Understanding behav- ior in groups through inverse planning. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pp. 6170, 2019.
Silver, D., Schritwieser, J., Simonyan, K., Antonoglou, I., Huang, A., Guez, A., Hubert, T., Baker, L., Lai, M., Bolton, A., Chen, Y., Lillicrap. T., Hui, F., Sifre, I.., van den Driessche, G., Graepel, T., and Hassabis, D. Mastering the game of Go without human knowledge. Nature, 550(7676):354-399 October 2017. ISSN 1476- 4687. doi: 10. 10.10///uuuue222270 URL https: org 10. 1 1038 naturee2270.
URL https: http://oooooooooog 1724-z
Wang. J. X., Kurth-Nelson, Z., Kumaran, D., Tiru- mala, D., Soyer, H., Leibo, J. Z., Hassabis, D., and Botvinick, M. Prefrontal cortex as meta-reinforcement learning system. Nature Neuroscience, 21(6))860~ ISSN 1546-1726. doi: 10.1038/
868, June 2018.
Stone, P., Kaminka, G., Kraus, S., and Rosenschein, J. Ad hoc autonomous agent teams: Collaboration without pre- coordination. Proceedings of the AAAI Conference on Artificial Intelliggence, 24(1):1504 1509, Jul. 2010a. doi: 10. 1..00//aaii.2241..552222. URL http:: aaai. org/ trggindex..phg AAAT /ttp///////ttteeeeeeee/eee/e
URL https::/ddat /doii /ttp////oo.......///// org/10. 1038/ s41593 018- 0147-8.
011597-018-0177-8
Wang, X., Zhang, S.. Zhang, W., Dong, W., Chen, J., Wen, Y., and Zhang, W. Quantifying zero-shot coor- dination capability with behavior preferring partners, 2024. URL https: /ttp//////e/eeeeeeeeeeeeeeeeeeee / id=wTRp
net/ forum?
Stone, P., Kaminka, G. A., Kraus. S., and Rosenschein, J. Ad hoc autonomous agent teams: collaboration without pre-coordination. In Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence, AAAI 10, pp- 1504-1509. AAAI Press, 2010b
Wellman, M. P., Tuyls, K., and Greenwald, A. Empiri- cal game-theoretic analysis: A survey. arXiv preprint arXiv:2403. 04018, 2024.
Strouse, D., Kleiman- Weiner, M., Tenenbaum, J., Botvinick, M., and Schwab, D. Learning to share and hide intentions using information regularization. In Advances in Neural Information Processing Systems, volume 31, 2018.
Wu+, S. A., Wang*, R. E., Evans, J. A., Tenenbaum, J. B., Parkes, D. C., and Kleiman- Weiner, M. Too many cooks: Bayesian inference for coordinating multi-agent collabo- ration. Topics Cognitive Science, 13(2):414 432, 2021.
12

---

Cros-cnvirroment Cooperation Enables Zero-shot Multi-agent Coordination
Xia, G.-S., Bai, X., Ding, Zhu, Z., Belongie, S., Luo, J., Datcu, M., Pelillo, M., and Zhang, L.. Dota: A large-scale dataset for object detection in acrial images. In 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 3974-3983, 2018. doi: 10. 109/ 2018.00418.
Yan, X., Guo, J., Lou, X., Wang, J., Zhang, H., and Du, Y. An efficient end-to-end training approach for zero-shot human-Al coordination. In Thirty-seventh Conference on Neural Information Processing Systems, 2023. URL https:://penreeveew... net/ forum? id=6ePsuwXOwf.
Ying, L., Jha, K., Aarya, S., Tenenbaum, J. B., Torralba, A., and Shu. T. Goma: Proactive embodied cooperative communication via goal-oriented mental alignment, 2024. URL https: / /ttpaa/avvv////////a///aa//a.wta org/ abs/ 2403. 11075.
Zhao, R., Song, J., Hu, H., Gao, Y., Wu, Y., Sun, Z., and Wei, Y. Maximum entropy population based training for zero-shot human-ai coordination. CoRR, abs/2112.11701, 2021. URL htt.ttsss//arxiv.oo abs/2112.11704
Zhao, R., Song, J., Yuan, Y., Haifeng, H., Gao, Y., Wu, Y., Sun, Z., and Wei, Y. Maximum entropy population- based training for zero-shot human-ai coordination, 2022. URL https: //arxivv..v//////////eeeeeaaaav. org/ 22112. 11701.
Zhou, Y., Li, J., and Zhu, J. Posterior sampling for multi- agent reinforcement learning: solving extensive games with imperfect information. International Conference on Learning Representations, 2020, URL https://
13

---

Cros--nnvrrommnnt Cooperation Enables Zero-shot Multi-agent Coordination
Asymmetric Advantages
Coordination Ring
Counter Circuit
Cramped Room
Forced Coordination
Figure 12. Five original Overcnoked layouts. The crosses on each of the layouts indicate "unreachable" locations. When sampling layouts in the procedural generation process, make sure to sample at least one of the plate piles, onion piles, pots, and goals on walls that are reachable
A. Appendix
A.1. Procedurally Generated Overcooked
In this section, we provide additional details for how create many solvable coordination challenges in Overcooked. We first sample which of the five layouts we would like to use base predicate. Next, we remove all items and agents from the layout so that we are left with just walls and free spaces. We begin by first sampling a set of plate piles (three white circles in triangle shape in Figure 12), onion piles (three yellow circles in triangle shape in Figure 12), pots (Darker black rectangle with lid embedded within gray wall in Figure 12), and goals (green squares in Figure 12) to be on a wall not in the regions marked with a red cross in Figure 12. We then sample an additional set of each of the aforementioned items on any of the remaining walls that are not occupied by other objects.
Next, we sample initial agent locations. In the Coordination Ring, Counter Circuit, and Cramped Room layouts, we can sample both of the agents in any of the available free spaces. However, in Asymmetric Advantages and Forced Coordination this can be problematic since a divider prevents agents from moving between two halves of the grid. As such, if all task-relevant items are sampled on inaccessible walls, the agents will not be able to complete the tasks. To avoid this issue, for these layouts only we make sure to sample initial agent locations in free spaces on separate halves of the grid. That is, the red agent's initial location will be sampled on a free cell in the left half of the grid and the blue agent's initial location will be sampled on the right half of the grid, vice versa.
By guaranteeing at least one set of items relevant to the task are reachable and accessible by at least one agent, we can create a new, solvable coordination challenge. We randomly sample whether we will rotate the sampled grid 90 degrees clockwise, and embed the resulting state in a larger 9x9x26 observation space by padding additional cells as just being walls. After making this 9x9x26 grid, we compare it to held-out levels to see whether the goal positions, pot positions, plate pile positions, and onion pile positions are the same. they are, we resample a new grid. We provide pseudocode for our approach in Algorithm 1.
A.2. CEC in Partially Observable Environments
We modified the Dual Destination problem to give agents a 3x3 visibility window instead of the fully observable 5x5 window from the results in Figure 3. Then, we trained CEC, FCP, and IPPO using the same architectures in the fully observable setting and 300 million steps of training. The challenge of breaking handshakes when learning multi-agent policies is even more pronounced in the partially observable case, as agents may form arbitrary conventions to handle high uncertainty about the state of the world. From our results in Figure 13, we find the same conclusions in the partially observable setting as we did in the fully observable results described in the paper: CEC has high cross-play performance in ZSC with other agents on novel environments (0.74), outperforming population based methods (0.61) and naive self-play (0.03).
A.3. CEC in Multi-task Environments
We explored whether CEC would be beneficial for cross-partner and tross-environmen generalization when there are multiple solutions to a task. The intuition here is that with multiple possible optimal responses a team of agents could have for collaboration, PBT or self- self-play methods with sufficient exploration might be able to form robust, object-oriented
14

---

Cros--nvirromennt Cooperation Enables Zero-shot Multi-agent Coordination
Algorithm 1 Solvable Overcooked Coordination Challenge Generation
Input: Layout set C [Coordination Ring, .... Forced Coordination), Held-out set of evaluation levels G). Sample Tauss (C) (Discrete uniform distribution)
Initialize grid G + LoadWalls( Luss))
G G {objects U ]gents}
Phase 1: Mandatory Object Placement
for Vog E 0 = (PlatePile, OnionPile, Pot, Goal] do
Let = {w E Gwalls w & P
G +- G for (or(dad((V)))
end for
Phase 2: Supplemental Object Placement
for Vo, E O do
V remainnng = {w E V w & G}
G + G for (rand (emmining)))
end for Agent Positioning
if Liase E {Asymmetric Advantages, Forced Coordination) then
pos; U(fc E FreeSpaces
pos2 u(fc E FreeSpaces,ghu
else
posi ~ L (FrreSpaace))
pos2 ~ (FreeSpaces \ {poss})
end if
Post-Processing
if u ((0, 1)) > 0.5 then
G Rotate(G,990))
end if
G < Pad(G, walls, 9 x 9)
if G & G₁ then Return Valid configuration challenge
else
Repeat generation process
end if
representations without the need for CEC.
To test this, extended the Dual Destination environment to have two possible valid solutions to reward agents (Figure 14.) Now, agents are rewarded if they are on opposite green opposite pink squares. As shown in Figure 15, in the multi-task variant both valid squares remain equidistant from the agents so that there are now 4 strategies which could be rewarded. For the procedural generator, just as in the original Dual Destination problem we randomly shuffle agent and goal locations so that they all lie on unique grid cells. We show even in the multi-task setting, CEC agents (0.404) outperform PBT methods (0.251) and naive self-play (0.083) when collaborating with novel partners on tasks PBT and naive self-play method swerve trained on. Just as in the single-task setting, PBT (0.005) and naive self-play (0.004) cannot generalize to novel partners novel environments, whereas CEC can (0.446), albeit with slight performance reduction from the single-task setting in Figure 3 of our paper (CFC=00993 and 0.966 on fixed and procedurally generated single-task problems respectively). This finding illustrates that additional work is needed to understand the impacts of task complexity and procedural environment generation.
A.4. Combining Partner and Environment Diversity
We tested the impact of combining partner diversity with environment diversity by training E3T agents under the CEC paradigm. We set the partner policy randomness to 0.5, consistent with human experiments and E3T's original design. Results in the ZSC setting in simulation (Figure 16) show CEC-E3T performs worse than other models on Overcooked's ' five original layouts (CEC=130.51, CEC-E3T=28.21) but outperforms CFC-Finetune on 100 held-out grids (CEC-FT=41.73,
15

---

Cros-cnvirroment Cooperation Enables Zero-shot Multi-agent Coordination
100 Procedurally Generated Tasks
Fixed Task
Normalized XP Reward
0.6
Figure 13. the partially observable setting, CEC 7SC performance the Dual Destination problem replicates findings from the fully observable case, suggesting it has promise for other games with imperfect information and the need for dynamic conventions, such Hanabi.
0.3
0.0
IPPO
FCP CEC
IPPO FCP CEC Algorithm
Algorithm
100 Procedurally Generated Tasks
Fixed Task
Normalized XP Reward
Initial State
Goal States
0.4
0.2
0.0
IPPO FCP CEC IPPO FCP CEC Algorithm
Algorithm
Figure 14. Overview of the Multi-Task Dual Destination problem. Agents rewarded for going either opposite pink squares opposite green squares.
Figure 15. Even in this multi-task setting. CEC outperforms population-base based methods when tasked with collaborating with novel partners novel problems. Just in the singlettakk setting, naive self-play and PBT methods fail to achieve substantial re- wards environments they have not during training, whereas CEC can.
CEC-E3T=58.15 13). The learning curves (Figures 17 and 18) from a checkpoint billions steps into training reveal that noisy partners introduced additional training noise, which, combined with dynamic environments, likely requires larger networks and longer training times for convergence compared vanilla CEC.
A.5. Necessity of Recurrent Networks for CEC
We include recurrent networks with CEC to enable a basic meta-lcarning algorithm (Wang et al., 2018: Rabinowitz et al., 2018). We tested whether it is possible for CEC to retain reasonable performance without using recurrent policies. In Overcooked and the Dual Destination problem, agents without recurrence failed converge adapt effectively. As shown in the learning curves for the Dual Destination problem, CEC with LSTMS successfully converged (Figure 19), while the non-recurrent version couldn't 't even achieve positive rewards (Figure 20).
A.6. Nice WebRL. for Jax-based Human Experiments
Reinforcement Learning has experienced accelerated progress recently due to the adoption of Jax-based environments that enable tackling single-agent (Bonnet et al., 2024; Nikulin et al., 2024; Matthews et al., 2024) and multi-agent (Rutherford et al., 2023; Lu et al., 2024) problems at millions of steps per second on academic-seale compute. From. To that effect, an open question within the fields of cognitive and computer science is how can these advances in environment design help us progress our understanding of individual and collective agency in humans and machines. For our human experiments we
16

---

Cros-cnvironment Cooperation Enables Zero-shot Multi-agent Coordination
100 Procedurally Generated Grids
Heldout Grids
160
XP Reward
80
0
IPPO
E3T
FCP
CEC Algorithm
CEC-FTCEC-E31
IPPO
E3T
FCP
CEC Algorithm
CEC-FTCEC-E3T
Figure 16. CEC with E3T exhibits lower cross play performance the 7SC setting than any other method on the original 5 Overcooked layouts, but exhibits hetter generality the 100 held out procedurally generated layouts than CEC fine-tuned on of the original 5
Reward
Reward
80
140
100
60
20
1.90
1.92
1.94
1.96
1.9
1.90
1.94
1.95
1:98
2.00
169
Steps
Figure 17. CEC on its own is able to achieve very high rewards during training across novel environments
Figure 18. Combining CEC with a partner diversity method (E3T) leads training curve which achieves half the reward as CEC on its own in the same amount of training time
used NiceWebRL. (Carvalho, 2025), a unified tool for evaluating Lingle-Human Human-AL, and Human Human performance in turn-based simultaneous-actionn games.
NiceWebRL is built top of the NiceGUI nic Python package, and leverages server-side environment parallelization to make a seamless client-side study experience for any single or multi-agent game based in Jax. It precompiles the environment reset and step functions, as well as the code to render the state as a pixel-based image. To ensure minimal latency, Nice WebRL then simulates future possible states and stores an image representing each possible future-world client-side. Then, when the active Human actually takes an action in game, renders the corresponding state and simulates forward in time during the few milliseconds before the human can select another action.
Not only does NiceWebRL provide an intuitive way to load in environments and AI models conduct human experiments it also gives researchers an accessible method for collecting and saving participant data thanks NiceGUI's large variety of survey options. Moreover, it provides a seamless way to deploy experiments on the web from laptop: even running Human-Al experiments with complex models on a laptop with few cpu cores, we were able to host several simultaneous user studies across the globe with low latency. The authors of the package originally included just single-agent support, and we extended that package evaluate human-Al and numan-human gameplay.
17

---

Cros--nvirroment Cooperation Enables Zero-shot Multi-agent Coordination
Reward
-20
-40
-100
2.0
0.0
0.5
1.0
2.0
255
3.0
Steps
108
Figure In 300 million timesteps, CEC with LSTM con-
Figure 20. In 300 million timesteps, CEC without an LSTM cannot achieve positive reward on Dual Destination problem.
verged to the maximum reward on the Dual Destination problem.
A.7. Agent Training Details
A.7.1. NETWORK ARCHITECTURE
For all IPPO, FCP, and CEC agents, we the architecture in Table consisting of three main components: observation encoder, a recurrent core, and separate actor-critic heads.
Component
Layer
Details
Conv1
2x2 kernel, 64 filters, orth(v2), ReLU activation
Conv2
2x2 kernel, 32 filters, orth(v/), ReLU activation
Observation Encoder
FC1
Fully-connected, 512 units, orth( ReLU activation
FC2
Fully-connected, 512 units, orth( ReL.U activation
Recurrent Core
LSTM
Feature size: 256, state resets at episode boundaries
FC1
Fully-connected, 256 units, orth(2), ReLU activation
FC2
Fully-connected, 192 units, orth(2), ReLU activation Fully-comnected, 128 units, o2th(2), ReLU activation
Actor Head
FC3
FC4
Fully-connected, 64 units, orth(2) [Overcooked only], ReLU activation
Output
Fully-connected, for Overcooked, for Dual Destination Problem) units (logits for discrete actions), orth(0.01)
FC1
Fully-comnected, 512 units, orth(2), ReLU activation
FC2
Fully-comnected, 256 units, orth(2), ReLU activation
Critic Head
FC3
Fully-connected, 192 units, orth(2) [Overcooked only], ReLU activation
FC4
Fully-connected, 128 units, orth(2) [Overcooked only], ReLU activation
Output
Fully-connected, unit (value prediction). orth(1.0)
Table Agent Architecture for IPPO, FCP, and CEC agents. All layers use orthogonal weight initialization with layer-specifir scaling factors (orth(scale)) and zero bias initialization.
For E3T, we use the architecture described in (Yan et al., 2023), with the randomness parameter for the partner policy = 0.55
A.7.2. PPO PARAMETERS
We use the parameters in Table 2 for training all PPO agents:
A.8. Cross-Algorithm Analysis
Agents trained with each of the different algorithms in the single-task setting (IPPO, FCP, E3T) play each other and the two CEC models on both the five original and 100 procedurally generated held-out Overcooked grids. We show the results in
18

---

Cros-cnvirooment Cooperation Enables Zero-shot Multi-agent Coordination
Parameter
Value
Description
LR
3 x 10
Initial learning rate for policy optimization
NUMSTEPS
256
Number of steps to collect per environment
before updating
TIMESTES
3 x 10
Total number of environment steps for train- ing
UPPATTEEEOCHE
4
Number of epochs to update policy per col-
lected batch
NUM MINIBATCAT
Number of minibatches split collected data into
GAMMA
0.99
Discount factor for future rewards
GAEBLA
0.95
Lambda parameter for Generalized Advan-
tage Estimation
CLIP EPS
0.2
PPO clipping parameter for policy loss Entropy coefficient for encouraging explo- ration
ENT.COBE
0.005
VFLCOEF
1.0
Value function loss coefficient
MAX GRAD_NORS
0.5
Maximum gradient norm for gradient clip- ping
ANNEAL LR
True
Whether to use learning rate annealing
Table 2. PPO Hyperparameters
Figures 21 and 22. From these heatmaps, we that CEC can collaborate with agents trained with different algorithms with PBT methods, indicating that it is truly learning how to adapt rather than follow a single strategy (Question 1). We use the values in Figures 21 and 22 as the payoff matrices for our Empirical Game Theory analyses in Figure 8.
We additionally include the AI-AI XP performance for agents across each of the original 5 layouts in Figure 23, which shows that CEC or CEC-Finetune perform better than all other models 4 out layouts and competitively with other methods the layout it did not do as well in.
A.9. Limitations
The learning curves in Figure 7 show that CEC has not yet converged from SP training or plateaued terms of XP performance on any level. Due cost and time constraints, we were not able train for longer than 3 billion steps per model, leaving open questions for future research: 1. What is upper-ceiling on XP performance for IPPO CEC agents, balance the bias towards adaptation introduced in CEC with greedier policies which maximize reward
and 2. How beyond CEC-Finetune.
Moreover, our human experiments filtered for participants capable of fluently speaking English. This can bias our results, as speaking English typically comes with its own set of cultural practices which impact participants' abilities to play the game and also their assessments agents' cooperative abilities (Henrich al., 2010).
A.10. Qualitative Analysis of Learned Norms
In this section, we provide additional intuition for the success of CEC in comparison to single-task methods. We examine Counter Circuit (see Figure 4), a layout with large amount of strategy diversity. In Figures 24, 25, and 26, we compare the frequency of different locations visited by IPPO and CEC agents in Counter Circuit. The prevalence of darker regions for the IPPO agents indicates that they visit certain areas less frequently and tend follow fixed route when completing the task. Such strategies can be brittle if people try moving in the opposite direction around the center block, potentially forcing agents into unfamiliar locations where they lack experience acting. In contrast, CECs have a more uniform distribution over the cells they visit. This does not inherently mean CECs are capable of better adaptation, as agents uniformly sampling actions would theoretically also have uniform state coverage. However, we observe that the cells closest to both pots, both onion piles, the plate pile, and the goal location receive the highest concentration of visitations by CEC agents. In contrast, the IPPO agents seem to visit at most one pot. This leads us infer that CEC agents have developed a richer representation
19

---

Cros--nvirromennt Cooperation Enables Zero-shot Multi-agent Coordination
Normalized Reward
Normalized Reward
IPPO
IPPO
0.51
0.29
0.77
0.47
0.49
0.00
0.00
0.13
0.03
E3T
0.29
0.43
0.41
0.38
0.33
E3T
0.00
0.00
0.00
0.18
0.06
0.4
0.6
Algorithm
Algorithm
0.3
FCP
0.77
0.41
0.55
0.58
0.71
FCP
0.00
0.00
0.16
0.05
0.5
-0.2
CEC-Finetuue CEC
CEC-Finetune Finettne CEC
0.47
0.38
0.58
0.61
0.67
0.13
0.18
0.16
0.56
0.33
0.4
0.49
0.33
0.71
0.67
0.78
0.03
0.05
0.33
0.14
0.3
IPPO
E3T
FCP Algorithm
CEC CEC-Finetune
IPPO
E3T
FCP Algorithm
CEC CEC-Finetune
Figure 21. Heatmap comparing different algorithms playing each other in the single-task setting, averaged across the original 5 layouts. Brighter yellow regions indicate better performance.
Figure 22. Hcatmap comparing different algorithms playing each other on 100 held-out procedurally generated Overcooked layouts. Brighter yellow regions indicate better performance.
of the different subtasks involved in cooking, and may be more capable of adapting users' actions if forced by the humans to play a different role within the collective plan (i.e. cook items in different pot, pickup cooked items instead of pass onions, etc.).
A.11. User Assessments of Partners from Human-Al Experiments
At the end of every episode a participant plays with different RL agent, we provide them with survey to assess the agent they just played with. We ask 7 questions that participants respond to with a rating on the Likert scale (Likert, 1932). The questions, and corresponding participant ratings different models, averaged across the two human-Al experiments we ran (Counter Circuit and Coordination Ring) are included in Figure 27.
We also include the responses averaged across participants for each individual experiment in Figures 28 and 29.
IPPO
XP Reward
240
E3T
FCP
160
CEC
CEC-Finetune
80
Asymm Advantages
Forced Coord
Coord Ring Layout
Cramped Room
Counter Circuit
Figure 23. Comparison of model performance across each of the original Overcooked layouts, with standard error bars shown. CEC CEC-Finetune achieve the highest mean reward 4 out of 5 layouts.
20

---

Cros-cnvironment Cooperation Enables Zero-shot Multi-agent Coordination
Visit Frequancies
Visit Frequencies
10
Visit Frequencies
1.0
00
0.8
0.8
0.0
Figure 26. CEC Seed Counter Circuit which can coordinate with IPPO seeds from Figures 24 and 25. By focusing it's attention on task-relevant objects rather than arbitrary strategies. able effec- tively cooperate with novel partners on novel problems.
Figure IPPO Seed Counter Circuit which has converged upon an optimal strategy rotating clockwise and the agent at the top doing more of the work. Struggles playing with seed depicted Figure 25.
Figure 25, IPPO Seed Counter Circuit which has converged upon an optimal strategy of rotating counterclockwise and the agent at the bottom doing more of the work. Struggles playing with seed de- picted in Figure 24.
IPPO-
FCP-
IPPO
FCP
Rating
E3T
CEC
CEC-FT
Adaptive Consistent Human-like In My Way Frustrating Enjoyed Coordination Question
Figure 27. Participant assessments of different models across 7 different metrics averaged across Counter Circuit and Coordination Ring.
A.12. Al Collaboration Success Per Layout
We plot the success of different models playing with humans in study in Figures 30 and 31. We show the results of Counter Circuit and Coordination Ring respectively.
21

---

Cros-cnvirooment Cooperation Enables Zero-shot Multi-agent Coordination
4
3
IPPO
Rating
FCP
2
IPPO
FCP
E3T
1
CEC
CEC-Finetune
0
Adaptive
Consistent
Human-like
In My Way Question
Frustrating
Enjoyed
Coordination
Figure Participant assessments different models across different metrics for the experiment Counter Circuit.
4
3
IPPO-
Rating
FCP-
2
IPPO
FCP
E3T
1
CEC
CEC-Finetune
0
Adaptive
Consistent
Human-like
In My Way Question
Frustrating
Enjoyed
Coordination
Figure 29, Participant assessments of different models across different metrics experiment Coordination Ring.
22

---

Cros-cnvirromentt Cooperation Enables Zero-shot Multi-agent Coordination
# Recipes Made
Recipes
FCP Algorithm
Finetune
IPPO-
FCP-
IPPO
FCP Algarithm
E3T
CÉCCEC-Finetune
Figure Success rates different algorithms playing Counter Circuit with humans.
Figure 31. Success rates of different algorithms playing Coordina- tion Ring with humans.
23


Reviews:
[{"review_id": "vKyYQVo7Ov", "reviewer": "Reviewer_mZRU", "summary": "This paper proposes Cross-Environment Generalization (CEC) as a way of improving agents’ generalization to unseen agents (the ad hoc teamwork problem) and unseen environments.\nThe proposed method consists of a procedurally generator that varies Overcooked initial states, over which an IPPO team learns via self-play. \nThe method is evaluated on Overcooked, and demonstrates improved task generalization compared to FCP and E3T, and generalization to human teammates that improves over FCP, but is equivalent to E3T.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their detailed feedback and recognition of our work’s novelty and clarity. Below, we address key concerns and how we plan to integrate this feedback:\n# Experiments Beyond Overcooked\nTo help address your suggestions, we have conducted **3 new experiments showing that our method generalizes beyond Overcooked.** First, we would like to highlight the “Dual Destination” environment (Section 4, Figures 2-3 of the submission), where rewards are only given when both occupy separate green squares. For the rebuttal, we have conducted new experiments in a [partially observable version of this environment](https://rb.gy/iwg3wx), and found that CEC once again achieved high cross-play performance in novel environments (0.74), outperforming population-based methods (0.61) and naive self-play (0.03).\n# Combining Task and Partner Diversity\nFollowing your suggestion, we tested [combining partner diversity algorithms with environment diversity](https://rb.gy/g015me) using E3T under the CEC paradigm. Results showed CEC-E3T performed worse than other models on Overcooked’s five original layouts (CEC=130.51, CEC-E3T=28.21) but outperformed CEC-Finetune on 100 held-out grids (CEC-FT=41.73, CEC-E3T=58.13). The linked learning curves reveal that noisy partners combined with dynamic environments introduced additional noise, suggesting larger networks and longer training times for convergence may be needed compared to vanilla CEC.\n# New experiments without RNNs\nPer reviewer SmWr, we ablated RNNs in CEC (used for meta-learning per Wang et al, 2018; Rabinowitz et al, 2018). In Overcooked and Dual Destination, non-recurrent agents failed to converge or adapt. [Learning curves](https://rb.gy/nti7xf) show CEC with LSTMs converged successfully, while non-recurrent versions could not achieve positive rewards.\n# DR generates unsolvable environments\nWe also appreciate the opportunity to clarify the distinction between CEC and standard domain randomization (DR). While CEC uses environment randomization, it employs a procedural generator to ensure all tasks are solvable, unlike naive randomization, which we found in our experiments often produces unsolvable layouts and poor learning signals. This mirrors the conclusions of the Overcooked Generalisation Challenge (Ruhdorfer et al., 2024), which shows that random/UED approaches often fail to generate solvable layouts or train agents capable of completing tasks. This highlights the need for structured procedural generation like ours.\n# Computational Feasibility of CEC\nWe acknowledged that CEC’s 3 billion training timesteps exceed the computational budget of prior work like CoMeDi for a single layout. However, Population-based training (PBT) scales poorly when the goal is to cooperate on many levels: training eight agents (5M steps each) plus an ego cooperator (10M steps) results in a 50-million-step budget per layout. Scaling to 100 layouts would require 5 billion steps but still only generalize to fixed levels. CEC generalizes better to thousands of unseen layouts with lower total compute costs (Figures 3,6,9), making it more efficient for broad adaptability. We also note that for our experiments, we ensure that all algorithms are able to use the same compute budget of 3 billion steps, and we find that CEC is able to better use this compute to improve performance.\n\nWe agree that **formalizing procedural generators** for naturalistic settings is a challenging direction for future work. One idea could involve combining program induction with procedural generation, as in WorldCoder (Tang et al., 2024), where LLMs generate OpenAI Gym-like environments with unknown dynamics. For CEC, inferred dynamics could be encoded into simulators like Unity before generating diverse scenes for RL training—a form of real-to-sim-to-real transfer (Torne et al., 2024).\n# CEC and related work\nThank you for highlighting MAESTRO and MADRID, which we will include in our related works section. MAESTRO complements our work by focusing on zero-sum settings, and showing that in that case, jointly considering environment and partner diversity is optimal, while focusing on either leads to suboptimal outcomes. While we used uniform sampling over grids irrespective of the agent’s abilities during training, we will add to our discussion about how future work can explore autocurricula for partners and tasks to improve sample efficiency through strategies such as regret minimization ala MADRID and MAESTRO.\n# Analyzing CEC’s Norms\nThe reviewer astutely questions how CEC learns human-like norms without explicit instructions. As noted in Section 6, we believe these norms reflect principles for cooperation in dynamic environments, such as “stay out of each other’s way.” These norms may be perceived as more human-like because humans also follow them.\n\n**Figures 13 and 14** show cross-play scores across all algorithms, forming the payoff matrix used to create Figure 8. The diagonal reflects results from Figure 6.", "claims_and_evidence": "- **Key Claim**: training agents in across procedurally generated, randomized environments, improves agents’ ability to generalize to new environments and new cooperation partners.\n    \n    - This is the core hypothesis/claim of the paper, but I think it is overstated. The experiments only analyze CEC’s performance on Overcooked, and do not consider any other environments. The efficacy of environment randomization in inducing diverse partner strategies might be specific to Overcooked, so I think the authors should weaken their claims.\n        \n- **Secondary Claim**: The authors claim that their procedural generation enviornment generation method is superior to randomly generating Overcooked environments, due to the problem of generating unsolveable environments.\n    \n    - However, there is no empirical evidence provided that shows that random level generation is problematic. Can the authors empirically test what percentage of randomly generated environments would be unsolvable in Overcooked?\n        \n- **Secondary Claim**: training on large set of procedurally generated environments is easier/results in a more computationally efficient algorithm than training a population of agents on a small set of environment configurations:\n    \n    - CEC is trained for 3 billion steps on Overcooked. Isn’t this a much larger training duration than conventional teammate generation approaches such as LIPO and CoMeDi (generally around a couple million timesteps, with a population size < 10) on Overcooked?", "methods_and_evaluation_criteria": "The proposed method, CEC is framed as an algorithm for training ad hoc agents, but environment diversity seems somewhat orthogonal from teammate diversity, even if environment diversity can induce teammate diversity. As such, it seems unfair to evaluate FCP/E3T on environment generalization. I am also wondering how CEC would perform if combined with a teammate diversity method such as E3T.", "theoretical_claims": "N/A", "experimental_designs_or_analyses": "Overall, the empirical design/analysis is strong, other than the issues I described in Claims/Evidence.", "relation_to_broader_scientific_literature": "The authors cite all relevant work that I am aware of, but they could improve the contextualization of their work w.r.t the UED literature, in particular, with respect to MAESTRO (Samvelyan et al. 2023) and Domain Randomization (Tobin et al. 2017) (already cited in the paper).\n\n- MAESTRO: MAESTRO examines both environment and co-player autocurricula in 2p0s game settings, and is a prioritized-level-replay style method that leverages a randomized environment generator. How do the insights from MAESTRO relate to this paper. which addresses the fully cooperative setting?\n    \n- Domain Randomization: it’s not clear to me that the proposed environment randomization in this paper is any different from domain randomization.\n    \n\nThe author should also discuss the MADRID paper (Samvelyan et al. 24), which also examines environment diversity as a way of exposing weaknesses in teammate policies.\n\nSamvelyan, Mikayel, Davide Paglieri, Minqi Jiang, Jack Parker-Holder, and Tim Rocktäschel. 2024. “Multi-Agent Diagnostics for Robustness via Illuminated Diversity.” arXiv. [http://arxiv.org/abs/2401.13460](http://arxiv.org/abs/2401.13460).", "essential_references_not_discussed": "MADRID (Samvelyan et al. 24) - see above for citation.", "other_strengths_and_weaknesses": "- Strengths:\n    \n    - The paper is clear and well-written.\n        \n    - Statistical significance tests are provided\n        \n    - Core finding that environment randomization improves both task and cooperative generalization ability is interesting and somewhat surprising.\n        \n    - Method is evaluated with humans, and performs strongly\n        \n- Weaknesses:\n    \n    - Method is specific to overcooked, and cannot be applied out-of-the-box on other domains, without a procedural generator. Can the authors discuss what would be needed for their method to apply more broadly?\n        \n    - Method is extremely computionally expensive, requiring training for 3B steps, compared to conventional teammate generation methods.\n        \n    - No formal characterization of the relationship between environment layout diversity and strategic diversity in Overcooked, which might explain why increasing environment diversity leads to improved ZSC.\n        \n    - No explanation of why humans find CEC more enjoyable/adaptive compared to baseline agents", "other_comments_or_suggestions": "- Typo on Line 161: “In contrast, we how…”\n- Figure 3: the discussion of this figure on pg 4, right is very confusing because I’m not sure if the discussion refers to the right or left subfigure in Fig. 3. Can the authors also specify what the “Fixed Task” is in Fig. 3, left?", "questions_for_authors": "1. How is the procedural environment generation method proposed in this paper different from domain randomization (Tobin et al. 2017)?\n    \n2. CEC is implemented using a self-play algorithm to isolate the effect of task diversity and partner diversity. Have the authors considered an algorithm that combines task and partner diversity?\n    \n3. Human-evaluation experiments (Q3): in these experiments, CEC falls short of E3T in cooperation with humans, but scores highest (by a small margin) according to human preferences. According to the analysis fo Figure 19, the authors state that this occurs because CEC is more adaptable to user behaviors, more strategically consistent, and better at avoiding collisions (Figure 11). However, the training process for CEC does not include any human data, so why would it learn any human norms?\n    \n4. Figure 13: why is it that the self-play score of each algorithm (on the diagonal) is no higher than any of the cross play scores, on the original 5 layouts? Typically, the algorithm self-play score is higher than algorithm cross-play scores.\n    \n\nTobin, Josh, Rachel Fong, Alex Ray, Jonas Schneider, Wojciech Zaremba, and Pieter Abbeel. 2017. “Domain Randomization for Transferring Deep Neural Networks from Simulation to the Real World.” In *2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)*, 23–30. [https://doi.org/10.1109/IROS.2017.8202133](https://doi.org/10.1109/IROS.2017.8202133).", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "GblHaKz8xo", "reviewer": "Reviewer_11py", "summary": "This paper studies a novel multi-agent training paradigm, Cross-Environment Cooperation (CEC), where the learning agent learns to work with a single partner across different variations of the environment. This is in contrast with prior work in the literature that focuses on training an agent that can adapt to unseen partners/strategies under a fixed environment. Despite not training with diverse partners, the CEC agents outperform state-of-the-art baselines under fixed and procedurally generated layouts. Additionally, the paper utilizes a newly developed Jax based procedural 2-player Overcooked environment for efficient training.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your interest in our work and recognizing the novelty of our training and evaluation approaches. We are glad you found our writing to be clear and our experiment section to be thorough. Your idea for framing cross-environment cross-partner evaluations as a novel contribution is one we will take on board in our revision of the paper, and we feel this will make our paper even stronger. We would now like to address some of their questions below:\n# Combining Task and Partner Diversity\nFollowing your suggestion, we tested the impact of [combining partner diversity with environment diversity](https://rb.gy/g015me) using E3T under the CEC paradigm. We set the partner policy randomness to 0.5, consistent with human experiments and E3T’s original design. Results in simulation showed CEC-E3T performed worse than other models on Overcooked’s five original layouts (CEC=130.51, CEC-E3T=28.21) but outperformed CEC-Finetune on 100 held-out grids (CEC-FT=41.73, CEC-E3T=58.13). The attached learning curves reveal that noisy partners introduced additional training noise, which, combined with dynamic environments, likely requires larger networks and longer training times for convergence compared to vanilla CEC. While the vanilla E3T struggled in simulation, it excelled in human trials, outperforming all other models in terms of reward.\n# Fixed Task Oracle\nIn Figure 3 of the paper, we report the score in Dual Destination normalized by the theoretical maximum possible score which would be achieved if both agents spawned on the correct goals in the first timestep. Figure 3 plots these normalized cross-play rewards for CEC, FCP, and IPPO. To obtain the **oracle score that you suggested on the Fixed Task,** we calculate that **an oracle agent** that perfectly responds to either optimal strategy would require 3 steps of receiving a -1 step cost to move to the target location before receiving a (3 positive - 1 step cost) reward for 97 steps, equating to (2*97 - 3) = 191 / 200 = **0.955 normalized reward**. **CEC scored 0.931 normalized reward** with a standard error of 0.013, indicating it underperforms the oracle’s cross play performance by about 2.5%.\n# CEC in Partially Observable Environments\nWe tested [CEC with partial observability](https://rb.gy/iwg3wx), by modifying the Dual Destination problem. We trained CEC, FCP, and IPPO using the same architectures and 300 million steps of training. The challenge of breaking handshakes when learning multi-agent policies is even more pronounced in the partially observable case, as agents may form arbitrary conventions to handle high uncertainty about the state of the world. **From our results below, we find the same conclusions in the partially observable setting as we did in the fully observable results described in the paper: CEC has high cross-play performance in ZSC with other agents on novel environments (0.74), outperforming population based methods (0.61) and naive self-play (0.03).** We believe this finding strengthens our paper, and thank the reviewer for providing this suggestion.\n# New experiments with no RNN\nFollowing reviewer SmWr’s suggestions, we provide new experiments ablating the use of an RNN for CEC, where the RNN is used to provide a simple meta-learning algorithm (Wang et al, 2018; Rabinowitz et al, 2018). We find that in Overcooked and the Dual Destination problem, agents without recurrence failed to converge or adapt effectively. As shown in the [learning curves for the Dual Destination problem](https://rb.gy/nti7xf), CEC with LSTMs successfully converged, while the non-recurrent version could not achieve positive rewards.\n# E3T performance difference in cross-play performance in simulation vs with humans\nDuring training, E3T uses a partner policy defined as π_p = (1-ε) * learned_policy + ε * uniform_policy, maintaining entropy to induce greater strategy coverage without requiring diverse co-players like population-based methods. Yan et al. (2023) found ε = 0.5 most effective for collaborating with humans, which we used for our baseline. For AI zero-shot coordination, ε = 0.3 performed best, while ε = 0.0 excelled in low-exploration layouts like Forced Coordination.\n\n**The code will be open sourced, from the environment code to training scripts to the human evaluation interface, which supports running experiments on arbitrary Jax-based reinforcement learning environments.**", "claims_and_evidence": "All the claims are well supported by convincing evidence.", "methods_and_evaluation_criteria": "The proposed method is technically sound and has strong implication to the MARL literature. The evaluation protocol is clear and reasonable. All methods use the same or similar computation budget for a fair comparison.", "theoretical_claims": "N/A", "experimental_designs_or_analyses": "All experiments are well designed and provide good intuition for the reader. The analyses are sound and based on best statistical practices.", "relation_to_broader_scientific_literature": "The findings in this paper will be impactful in the field of ad-hoc teamwork and multi-agent reinforcement learning in general. The idea of positive transfer between the two axes of generalization (environment and partner) is an intriguing finding. This paper serves as a good first step towards achieving jointly environment and partner generalization.", "essential_references_not_discussed": "-", "other_strengths_and_weaknesses": "Strengths\n- The paper is well written and easy to follow.\n- The core idea of the paper is novel, simple and very effective.\n- The toy example provides good intuition.\n- The experiments are well designed and thorough.\n\nWeaknesses\n- The environments used in this work are limited and relatively simple.", "other_comments_or_suggestions": "Suggestions\n- I really like the idea of training the learning agent across variation of environments, which has not been investigated much, if at all, in the literature. I think the authors could also go as far as claiming cross-environment cross-play evaluation as a novel evaluation setup, which would serve as another contribution of the paper. In its current form, the paper reads like CEC is purely a novel training paradigm.\n- In Section 4, since there are only two possible strategies, it would be beneficial to include a fixed task oracle baseline. The oracle cooperator would be trained against the two strategies. This would make it clear to the reader how much environment diversity helps partner generalization relative to this oracle (which is trained with \"maximally diverse partners\"). \n- Is it possible to show some combination of a partner diversification method (e.g., FCP) and CEC? Analyzing if the diversity generated from the two sources are additive or redundant would provide a very valuable insight\n-  Since the Overcooked environment used in the paper has only one recipe, It is quite straightforward to see why varying environment helps: the agents learn to do the recipe in different orders/combinations under different environment variants. I wonder if CEC would work well in environments with multiple solutions (e.g., multiple recipes in Ovecooked [1,2,3]).\n\ntypos\n- line 161: \"In contrast, we how training ...\"\n\n\n[1] Wu, Sarah A., et al. \"Too many cooks: Bayesian inference for coordinating multi‐agent collaboration.\" Topics in Cognitive Science 13.2 (2021): 414-432.\n[2] Charakorn et al. \"Generating diverse cooperative agents by learning incompatible policies.\" ICLR. 2023.\n[3] Yu, Chao, et al. \"Learning Zero-Shot Cooperation with Humans, Assuming Humans Are Biased.\" ICLR. 2023.", "questions_for_authors": "- There are two axes of generalization considered in this paper. It shows that environment diversity helps partner generalization. I wonder if the opposite is true: Does training with diverse partners help environment generalization?\n- Why E3T has lower evaluation XP performance than IPPO in Fig. 6 (left)?\n- How come E3T gets the lowest XP reward while perform best with humans?\n- Will the code be open source?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YsJAbiPYvr", "reviewer": "Reviewer_SmWr", "summary": "This work presents cross-environment coordination as an alternative to population based training for enabling smooth coordination with unseen partners. They find that (pre-)training on a diverse set of environment configurations on Overcooked with a single learning partner enables agents to work in new environments with new partners. A human-AI user study demonstrates the effectiveness of their training approach for human-AI coordination.\n\n## Updates after Rebuttal\n\nThe authors have clarified the ZSC vs AHT distinction I emphasized in my original review, and added new results to demonstrate that CEC requires an RNN to train. The experimental results in this paper are very interesting, so I strongly recommend this paper be accepted.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their thoughtful and constructive feedback on our paper, and address your comments below:\n\n# ZSC vs Ad-hoc Teamplay\n\nWe sincerely thank you for clarifying the distinction between these two evaluation settings. From our understanding, our use of the empirical game theoretic analysis to compare how agents trained with different algorithms cooperate with each other, as well as our human study, both fall within the ad-hoc teamplay setting. However, we acknowledge  that some of our experiments (particularly Figures 3, 5, and 7) address the ZSC setting, where we evaluate performance against the same algorithm with different random seeds. We will follow your suggestions to clarify our references and experimental analysis to distinguish between the two, and make a more nuanced characterization of the conclusions we can draw. We will also make sure to reference \"Other-Play.”\n\n# CEC in Partially Observable Environments\n\nFollowing your suggestions, we tested [CEC with partial observability](https://rb.gy/iwg3wx), by modifying the Dual Destination problem. We trained CEC, FCP, and IPPO using the same architectures and 300 million steps of training. The challenge of breaking handshakes when learning multi-agent policies is even more pronounced in the partially observable case, as agents may form arbitrary conventions to handle high uncertainty about the state of the world. **From our results below, we find the same conclusions in the partially observable setting as we did in the fully observable results described in the paper: CEC has high cross-play performance in ZSC with other agents on novel environments (0.74), outperforming population based methods (0.61) and naive self-play (0.03).** We believe this finding strengthens our paper, and thank the reviewer for providing this suggestion. \n\n# New experiments with no RNN\n\nWe include recurrent networks with CEC to enable a basic meta-learning algorithm  (Wang et al, 2018; Rabinowitz et al, 2018). Following your suggestion, we tested whether it is possible for CEC to retain reasonable performance without using recurrent policies. In Overcooked and the Dual Destination problem, agents without recurrence failed to converge or adapt effectively. As shown in the [learning curves for the Dual Destination problem](https://rb.gy/nti7xf), CEC with LSTMs successfully converged, while the non-recurrent version couldn't even achieve positive rewards.\n\n# Combining Task and Partner Diversity\n\nFollowing reviewer mZRY and 11py’s suggestion, we tested [combining partner diversity algorithms with environment diversity](https://rb.gy/g015me) using E3T under the CEC paradigm. Results showed CEC-E3T performed worse than other models on Overcooked’s five original layouts (CEC=130.51, CEC-E3T=28.21) but outperformed CEC-Finetune on 100 held-out grids (CEC-FT=41.73, CEC-E3T=58.13). The linked learning curves reveal that noisy partners combined with dynamic environments introduced additional noise, suggesting larger networks and longer training times for convergence may be needed compared to vanilla CEC. \n\n# Learned Conventions in CEC\n\nYou raised an interesting point about learned conventions from CEC. As noted in our qualitative analysis, conventions like \"move out of the way\" emerged from CEC agents trained across diverse environments. Unlike fixed strategies (e.g., \"red agent cooks onions while blue delivers\"), this adaptability reflects a general form of learned convention that enhances transferability and generalization to novel scenarios.\n\nWe appreciate your attention to detail in pointing out the typos and suggestions for improving our Markov Game tuple definition. We will address these in our revision.\n\nWe thank you for recognizing the strengths in our work, particularly the demonstration of cross-environment coordination's benefits for ad-hoc coordination, the principled human-AI experiments showing strong transfer to human partners, and the creative use of empirical game-theoretic analysis to demonstrate cross-algorithm performance. We thank the reviewer again for their valuable feedback, which will help us improve the clarity and rigor of our paper. \n\nRef: \nRabinowitz, N., Perbet, F., Song, F., Zhang, C., Eslami, S. A., & Botvinick, M. (2018, July). Machine theory of mind. In International conference on machine learning (pp. 4218-4227). PMLR.\nWang JX, Kurth-Nelson Z, Kumaran D, Tirumala D, Soyer H, Leibo JZ, Hassabis D, Botvinick M. Prefrontal cortex as a meta-reinforcement learning system. Nat Neurosci. 2018 Jun;21(6):860-868. doi: 10.1038/s41593-018-0147-8. Epub 2018 May 14. PMID: 29760527.", "claims_and_evidence": "I detail specific claims that I find problematic in later sections of the review.", "methods_and_evaluation_criteria": "- This may just be a misunderstanding, but it is incorrect to claim that training multiple agents using the “same algorithm” suffices for XP evaluation. For instance, the first cited work in the XP Evaluation section (Strouse et al., 2022) measures performance by explicitly testing against a held-out set of agents (H_proxy, diverse SP, and random agents) and does not test against the same algorithm being trained.\n     - Cross-seed XP on the same algorithm is only valid in the ZSC setting, not ad-hoc teamplay (see my comments in “other comments or suggestions” for the distinction).", "theoretical_claims": "N/A", "experimental_designs_or_analyses": "The experiments and analyses are valid (with the exception of the issue mentioned earlier in the evaluation criteria)", "relation_to_broader_scientific_literature": "The key contribution is applying domain randomization to the multi-agent setting for the purposes of ad-hoc coordination, which is novel to my understanding.", "essential_references_not_discussed": "The related works section is comprehensive (assuming the setting is ad-hoc coordination and not ZSC)", "other_strengths_and_weaknesses": "Strengths:\n- This is a very interesting work, demonstrating strong results for cross-environment coordination helping for ad-hoc coordination.\n- The human-AI experiments are principled and demonstrate strong transfer to human partners.\n- The empirical game-theoretic analysis is a very creative and interesting way to demonstrate cross-algorithm performance.\n\nWeaknesses:\n- The most critical weakness is the confounding of ZSC and ad-hoc coordination. It seems like this paper motivates itself under the (harder) ad-hoc coordination paradigm but evaluates itself under the (easier) ZSC paradigm.\n    - I would typically request using held-out partners for these results (i.e. the human BC model used for evaluation in Overcooked on earlier works), but the human user study is sufficient. I’d instead like to see the ZSC vs ad-hoc coordination point clarified throughout the text.\n- This work only studies fully observable, simultaneous action settings, but coordination challenges occur in partially observable settings (like Hanabi) so we cannot generalize the results of this paper to the broader ZSC community.", "other_comments_or_suggestions": "- I think the references to ZSC should be replaced with ad-hoc coordination, based on conventions from the MARL literature. Although similar, ZSC refers to the setting where we assume partners follow the same algorithm and attempt to maximize cross-play across initializations, while ad-hoc coordination refers to the ability to adapt to new partners who may not share the same learning algorithm. In the context of human-AI coordination, it seems like this paper cares more about the latter. Please refer to “‘Other-Play’ for Zero-Shot Coordination” in ICML 2020 for more information.\n- Line 161 column 1: “we how training” typo\n- A should not be duplicated in the Markov Game tuple definition. The horizon should also be defined in the Markov Game tuple, especially since it is used in the score definition (though I would advise against using T for both transitions and horizon).", "questions_for_authors": "- My interpretation of the key results is that the pair of agents trained via CEC do not learn consistent “conventions” across environments, so they “give up” and don’t learn any conventions. Are there experiments to indicate that CEC models do have some underlying conventions consistently across environments?\n    - In particular, I am wondering about settings where forming conventions is more strictly necessary (i.e. settings with partial observability), and whether CEC helps create consistent conventions.\n- Given that Overcooked is fully observable, how important is the recurrent core for performance and generalization? This seems to be a key difference between this work and (Yan et al., 2023), and this may be hurting the human-AI performance of your methods since it is easier to move off distribution at test time with recurrent inputs.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "abGdTbz2Qo", "reviewer": "Reviewer_H4DQ", "summary": "This paper proposes to train agents in self-play on a large-distribution of environments to enhance the agents' coordination ability with unseen teammates in unseen environments. Experiments on a toy grid-world game and Overcooked demonstrate the effectiveness of the proposed method.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and effort in reviewing our paper, and for recognizing its strengths in clarity, empirical validation, and the intriguing insights it provides.\n\n# New experiments\n\nBased on your suggestions, we’ve added the following results to broaden the experimental scope to more complex scenarios, and improve the analytical strength of our work:\n\n- **[CEC in Partially Observable Environments](https://rb.gy/iwg3wx).** Testing CEC in a partially-observed version of the Dual Destination problem yielded similar results: CEC achieved high cross-play performance on novel environments (0.74), outperforming population-based methods (0.61) and naive self-play (0.03).\n- **Combining Task and Partner Diversity.** Following reviewer mZRY and 11py’s suggestions, we tested combining [CEC with E3T](https://rb.gy/g015me). While it performed poorly on the original Overcooked layouts (CEC=130.51, CEC-E3T=28.21), it outperformed CEC-Finetune on held-out grids (CEC-FT=41.73, CEC-E3T=58.13). We hypothesize the E3T partner noise will require larger networks and more training time when combined with CEC’s diverse environments.\n- **Analyzing the effect of RNNs in CEC.** Following reviewer SmWr’s suggestions, we provide new experiments ablating the use of an RNN for CEC, where the RNN is used to provide a simple meta-learning algorithm (Wang et al, 2018; Rabinowitz et al, 2018). In Overcooked and the Dual Destination problem, agents without recurrence failed to converge or adapt effectively. As shown in the [learning curves for the Dual Destination problem](https://rb.gy/nti7xf), CEC with LSTMs successfully converged, while the non-recurrent version could not even achieve positive rewards.\n\n# Overcooked benchmark\n\nFollowing many prior papers published at top conferences like ICML (Li et al (2023); Mahlau et al. (2024)), NeurIPS (Carroll et al. (2020), Strouse et al. (2022), Yan et al. (2023),  Sarkar et al. (2023), Myers et al. (2024), Liang et al. (2024)) and ICLR (Yu et al. (2023), Gessler et al. (2025)), we focus on the Overcooked benchmark as a challenging human-AI cooperation task. *A core strength of Overcooked is that it enables real-time evaluation with actual human players, and shows that even for the simplest layouts coordinating with heterogenous and unpredictable human players requires a level of robustness that even state-of-the-art AI algorithms typically do not achieve.* **Since your review did not mention our human-study results** (Figures 9-11), **we would like to draw your attention to the fact that CEC achieves performance equivalent to state-of-the-art techniques in real human evaluations *without using population-based training,*** a surprising finding that contradicts much of the human-AI coordination literature. \n\n# Novelty\n\nWhile multi-task RL is well-established (Tobin et al., 2017), **our work is, to our knowledge, one of the first to show that environment diversity can outperform partner diversity for human-AI coordination, challenging the dominance of Population-Based Training (PBT) in ZSC** (Vinyals et al., 2019; Carroll et al., 2020; Strouse et al., 2022; Zhao et al., 2022; Sarkar et al., 2023; Liang et al., 2024). To support this claim, we reference Reviewer 11py’s comment, “I really like the idea of training the learning agent across variations of environments, which **has not been investigated much, if at all, in the literature. I think the authors could also go as far as claiming cross-environment cross-play evaluation as a novel evaluation setup, which would serve as another contribution of the paper.”**\n\n# Methodological details\n\nOur task sampling strategy is described in Section 4 and Appendix A.1. Figure 12 details how we determine which items to sample to create solvable environments, and how this leads to   procedural generation of over $1.16 * 10^{17}$ diverse, solvable coordination challenges by sampling wall structures and randomizing features like goals, plates, pots, and onions. \n\nOur paper provides several **insights into how and why training in multiple environments enhances coordination with many partners:**\n\n- **Real Human Experiments:** Quantitative and Qualitative assessments (Section 6, Figures 9-11, 16-21) indicate agents learn to \"adapt to partners in service of completing the task.\"\n- **Heat maps** (Figures 16-18) visualize the frequency of states covered by naive IPPO agents and CEC. CEC agents are able to adapt to novel partner strategies better by covering a greater distribution of states in self-play.\n- **Empirical game-theoretic analysis** (Section 5) demonstrates CEC agents forming more robust equilibria with novel partners.\n- **Learning curves** (Figure 7) illustrate how CEC agents improve differently on held-out tasks based on optimal strategy diversity.\n \nThank you again for your feedback, which will help us improve the final version of our paper.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "There is no formulated theoretical claims in this paper.", "experimental_designs_or_analyses": "Yes. I checked Section 5. Experiments and Section 6. Results.", "relation_to_broader_scientific_literature": "The key contributions extend and refine ideas from MARL, cooperative AI, game theory, robustness in machine learning, emergent communication, theory of mind, and open-ended learning. By addressing the challenge of generalization to unseen partners and environments, this paper advances these fields and provides a framework for developing more adaptable and collaborative AI systems.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "### Strengths  \n1. **Clarity and Simplicity:** The paper is well-written and easy to follow. The proposed method, CEC, is presented in a simple and straightforward manner, making it accessible to readers.  \n2. **Empirical Validation:** The paper provides extensive experimental results that demonstrate the effectiveness of CEC in enhancing coordination generalization.  \n3. **Interesting Insight:** The observation that training on multiple environments (initial states) improves coordination with unseen teammates is intriguing and potentially impactful for zero-shot coordination (ZSC) tasks.  \n\n### Weaknesses\n1. **Lack of Analysis:** The fundamental reason why training on multiple environments enhances coordination generalization remains unclear. The paper would benefit from a more rigorous theoretical analysis or analytical experiments to explain this phenomenon. Without such analysis, it is difficult to assess whether CEC can generalize to more complex tasks.  \n2. **Limited Novelty:** The proposed method appears to be a direct application of multi-task RL to ZSC, which lacks significant novelty. Additionally, key methodological details, such as the task sampling strategy, are not clearly explained.  \n3. **Narrow Experimental Scope:** CEC is evaluated only on two simple discrete grid-world environments, where enumerating initial states is straightforward. In more complex scenarios, the cost of creating diverse environments may outweigh the benefits of training with unseen teammates, potentially limiting the practical applicability of CEC.", "other_comments_or_suggestions": "None.", "questions_for_authors": "See Weaknesses.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: After engaging in discussions with the authors, all reviewers feel the paper should be accepted to ICML.  The authors are strongly encouraged to find a way to add the additional results provided in the discussion phase to the paper -- reviewers were quite happy with them.
Decision: Accept (oral)