# A New Formalism, Method and Open Issues for Zero-Shot Coordination

arXiv: https://arxiv.org/abs/2106.06613 · HTML: https://mlsanity.com/paper/2106.06613/

## Key facts

- Cited by 33 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 50 references that are in the map.
- First posted on arXiv 11 Jun 2021.

## Builds on (most cited first, 10 of 10)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Asynchronous Methods for Deep Reinforcement Learning](https://mlsanity.com/paper/1602.01783/) (2016)
- [Counterfactual Multi-Agent Policy Gradients](https://mlsanity.com/paper/1705.08926/) (2017)
- [The StarCraft Multi-Agent Challenge](https://mlsanity.com/paper/1902.04043/) (2019)
- [On the Utility of Learning about Humans for Human-AI Coordination](https://mlsanity.com/paper/1910.05789/) (2019)
- ["Other-Play" for Zero-Shot Coordination](https://mlsanity.com/paper/2003.02979/) (2020)
- [Equivalence Between Policy Gradients and Soft Q-Learning](https://mlsanity.com/paper/1704.06440/) (2017)
- [Bayesian Action Decoder for Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1811.01458/) (2018)
- [Adversarially Guided Self-Play for Adopting Social Conventions](https://mlsanity.com/paper/2001.05994/) (2020)
- [Policy Gradient With Value Function Approximation For Collective Multiagent Planning](https://mlsanity.com/paper/1804.02884/) (2018)

## Built on by (most cited first, 30 of 33)

- [Learning Zero-Shot Cooperation with Humans, Assuming Humans Are Biased](https://mlsanity.com/paper/2302.01605/) (2023)
- [The Boltzmann Policy Distribution: Accounting for Systematic Suboptimality in Human Models](https://mlsanity.com/paper/2204.10759/) (2022)
- [PECAN: Leveraging Policy Ensemble for Context-Aware Zero-Shot Human-AI Coordination](https://mlsanity.com/paper/2301.06387/) (2023)
- [Law Informs Code: A Legal Informatics Approach to Aligning Artificial Intelligence with Humans](https://mlsanity.com/paper/2209.13020/) (2022)
- [Towards Few-shot Coordination: Revisiting Ad-hoc Teamplay Challenge In the Game of Hanabi](https://mlsanity.com/paper/2308.10284/) (2023)
- [AssistanceZero: Scalably Solving Assistance Games](https://mlsanity.com/paper/2504.07091/) (2025)
- [Ad-Hoc Human-AI Coordination Challenge](https://mlsanity.com/paper/2506.21490/) (2025)
- [For Learning in Symmetric Teams, Local Optima are Global Nash Equilibria](https://mlsanity.com/paper/2207.03470/) (2022)
- [Cooperative AI via Decentralized Commitment Devices](https://mlsanity.com/paper/2311.07815/) (2023)
- [Assisting Unknown Teammates in Unknown Tasks: Ad Hoc Teamwork under Partial Observability](https://mlsanity.com/paper/2201.03538/) (2022)
- [Who Needs to Know? Minimal Knowledge for Optimal Coordination](https://mlsanity.com/paper/2306.09309/) (2023)
- [Observation Interference in Partially Observable Assistance Games](https://mlsanity.com/paper/2412.17797/) (2024)
- [Computing Game Symmetries and Equilibria That Respect Them](https://mlsanity.com/paper/2501.08905/) (2025)
- [The Yokai Learning Environment: Tracking Beliefs Over Space and Time](https://mlsanity.com/paper/2508.12480/) (2025)
- [High entropy leads to symmetry-equivariant policies in Dec-POMDPs](https://mlsanity.com/paper/2511.22581/) (2025)
- [Symmetry-Breaking Augmentations for Ad Hoc Teamwork](https://mlsanity.com/paper/2402.09984/) (2024)
- [Robust and Diverse Multi-Agent Learning via Rational Policy Gradient](https://mlsanity.com/paper/2511.09535/) (2025)
- [Training Generalizable Collaborative Agents via Strategic Risk Aversion](https://mlsanity.com/paper/2602.21515/) (2026)
- [Shaping Zero-Shot Coordination via State Blocking](https://mlsanity.com/paper/2605.11688/) (2026)
- [Benchmarking the Limits of In-Context Reinforcement Learning for Ad-Hoc Teamwork](https://mlsanity.com/paper/2605.24423/) (2026)
- [Ad Hoc Teamwork in the Presence of Adversaries](https://mlsanity.com/paper/2208.05071/) (2022)
- [Making Friends in the Dark: Ad Hoc Teamwork Under Partial Observability](https://mlsanity.com/paper/2310.01439/) (2023)
- [Is Inter-Seed Cross-Play Enough? Evaluating the Robustness of Zero-Shot Coordination Algorithms to Implementation Details](https://mlsanity.com/paper/2608.03644/) (2026)
- [Testing Interchangeability in LLM Agent Teams](https://mlsanity.com/paper/2609.05279/) (2026)
- [Multi-lingual agents through multi-headed neural networks](https://mlsanity.com/paper/2111.11129/) (2021)
- [The Benefits of Power Regularization in Cooperative Reinforcement Learning](https://mlsanity.com/paper/2406.11240/) (2024)
- [On the Complexity of Learning to Cooperate with Populations of Socially Rational Agents](https://mlsanity.com/paper/2407.00419/) (2024)
- [Noisy Zero-Shot Coordination: Breaking The Common Knowledge Assumption In Zero-Shot Coordination Games](https://mlsanity.com/paper/2411.04976/) (2024)
- [CooT: Learning to Coordinate In-Context with Coordination Transformers](https://mlsanity.com/paper/2506.23549/) (2025)
- [Efficient Reinforcement Learning for Zero-Shot Coordination in Evolving Games](https://mlsanity.com/paper/2511.11083/) (2025)

## Abstract (arXiv)

In many coordination problems, independently reasoning humans are able to discover mutually compatible policies. In contrast, independently trained self-play policies are often mutually incompatible. Zero-shot coordination (ZSC) has recently been proposed as a new frontier in multi-agent reinforcement learning to address this fundamental issue. Prior work approaches the ZSC problem by assuming players can agree on a shared learning algorithm but not on labels for actions and observations, and proposes other-play as an optimal solution. However, until now, this "label-free" problem has only been informally defined. We formalize this setting as the label-free coordination (LFC) problem by defining the label-free coordination game. We show that other-play is not an optimal solution to the LFC problem as it fails to consistently break ties between incompatible maximizers of the other-play objective. We introduce an extension of the algorithm, other-play with tie-breaking, and prove that it is optimal in the LFC problem and an equilibrium in the LFC game. Since arbitrary tie-breaking is precisely what the ZSC setting aims to prevent, we conclude that the LFC problem does not reflect the aims of ZSC. To address this, we introduce an alternative informal operationalization of ZSC as a starting point for future work.