# Quasi-Equivalence Discovery for Zero-Shot Emergent Communication

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 38 references that are in the map.
- First posted on arXiv 14 Mar 2021.

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

- [QMIX: Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1803.11485/) (2018)
- [Learning to Communicate with Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1605.06676/) (2016)
- [Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2003.08839/) (2020)
- [A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning](https://mlsanity.com/paper/1711.00832/) (2017)
- [The Complexity of Decentralized Control of Markov Decision Processes](https://mlsanity.com/paper/1301.3836/) (2013)
- ["Other-Play" for Zero-Shot Coordination](https://mlsanity.com/paper/2003.02979/) (2020)
- [Multi-Agent Cooperation and the Emergence of (Natural) Language](https://mlsanity.com/paper/1612.07182/) (2016)
- [Emergent Multi-Agent Communication in the Deep Learning Era](https://mlsanity.com/paper/2006.02419/) (2020)
- [Emergence of Language with Multi-agent Games: Learning to Communicate with Sequences of Symbols](https://mlsanity.com/paper/1705.11192/) (2017)
- [Emergence of Linguistic Communication from Referential Games with Symbolic and Pixel Input](https://mlsanity.com/paper/1804.03984/) (2018)
- [Natural Language Does Not Emerge 'Naturally' in Multi-Agent Dialog](https://mlsanity.com/paper/1706.08502/) (2017)
- [On the Pitfalls of Measuring Emergent Communication](https://mlsanity.com/paper/1903.05168/) (2019)
- [Emergent Communication through Negotiation](https://mlsanity.com/paper/1804.03980/) (2018)
- [Anti-efficient encoding in emergent communication](https://mlsanity.com/paper/1905.12561/) (2019)
- [Biases for Emergent Communication in Multi-agent Reinforcement Learning](https://mlsanity.com/paper/1912.05676/) (2019)
- [How agents see things: On visual representations in an emergent language game](https://mlsanity.com/paper/1808.10696/) (2018)
- [Emergent Linguistic Phenomena in Multi-Agent Communication Games](https://mlsanity.com/paper/1901.08706/) (2019)

## Built on by (most cited first, 19 of 19)

- [Collaborating with Humans without Human Data](https://mlsanity.com/paper/2110.08176/) (2021)
- [A Survey of Multi-Agent Deep Reinforcement Learning with Communication](https://mlsanity.com/paper/2203.08975/) (2022)
- [A Survey of Ad Hoc Teamwork Research](https://mlsanity.com/paper/2202.10450/) (2022)
- [Any-Play: An Intrinsic Augmentation for Zero-Shot Coordination](https://mlsanity.com/paper/2201.12436/) (2022)
- [Emergent Discrete Communication in Semantic Spaces](https://mlsanity.com/paper/2108.01828/) (2021)
- [A Review of the Applications of Deep Learning-Based Emergent Communication](https://mlsanity.com/paper/2407.03302/) (2024)
- [The Five Ws of Multi-Agent Communication: Who Talks to Whom, When, What, and Why -- A Survey from MARL to Emergent Language and LLMs](https://mlsanity.com/paper/2602.11583/) (2026)
- [Learning Robust Real-Time Cultural Transmission without Human Data](https://mlsanity.com/paper/2203.00715/) (2022)
- [Towards Human-Agent Communication via the Information Bottleneck Principle](https://mlsanity.com/paper/2207.00088/) (2022)
- [Assisting Unknown Teammates in Unknown Tasks: Ad Hoc Teamwork under Partial Observability](https://mlsanity.com/paper/2201.03538/) (2022)
- [Recommendations for Systematic Research on Emergent Language](https://mlsanity.com/paper/2206.11302/) (2022)
- [Quantifying Agent Interaction in Multi-agent Reinforcement Learning for Cost-efficient Generalization](https://mlsanity.com/paper/2310.07218/) (2023)
- [ELCC: the Emergent Language Corpus Collection](https://mlsanity.com/paper/2407.04158/) (2024)
- [Making Friends in the Dark: Ad Hoc Teamwork Under Partial Observability](https://mlsanity.com/paper/2310.01439/) (2023)
- [Learning Translations: Emergent Communication Pretraining for Cooperative Language Acquisition](https://mlsanity.com/paper/2402.16247/) (2024)
- [Portable Semantics, Private Dialects: Reuse and Negative Transfer in Latent Communication Between Language-Model Cells](https://mlsanity.com/paper/2609.11365/) (2026)
- [Multi-lingual agents through multi-headed neural networks](https://mlsanity.com/paper/2111.11129/) (2021)
- [Noisy Zero-Shot Coordination: Breaking The Common Knowledge Assumption In Zero-Shot Coordination Games](https://mlsanity.com/paper/2411.04976/) (2024)
- [Automated Semantic Rules Detection (ASRD) for Emergent Communication Interpretation](https://mlsanity.com/paper/2601.03254/) (2026)

## Abstract (arXiv)

Effective communication is an important skill for enabling information exchange in multi-agent settings and emergent communication is now a vibrant field of research, with common settings involving discrete cheap-talk channels. Since, by definition, these settings involve arbitrary encoding of information, typically they do not allow for the learned protocols to generalize beyond training partners. In contrast, in this work, we present a novel problem setting and the Quasi-Equivalence Discovery (QED) algorithm that allows for zero-shot coordination (ZSC), i.e., discovering protocols that can generalize to independently trained agents. Real world problem settings often contain costly communication channels, e.g., robots have to physically move their limbs, and a non-uniform distribution over intents. We show that these two factors lead to unique optimal ZSC policies in referential games, where agents use the energy cost of the messages to communicate intent. Other-Play was recently introduced for learning optimal ZSC policies, but requires prior access to the symmetries of the problem. Instead, QED can iteratively discovers the symmetries in this setting and converges to the optimal ZSC policy.