Quasi-Equivalence Discovery for Zero-Shot Emergent Communication

Kalesha Bullard, Douwe Kiela, Franziska Meier, Joelle Pineau, Jakob Foerster

TL;DR

Emergent communication often fails when agents encounter new partners because their learned protocols are based on arbitrary conventions. This paper introduces Quasi-Equivalence Discovery (QED), an algorithm that enables zero-shot coordination by discovering environmental symmetries and grounding communication in physical costs and intent frequency.

What Problem Does This Paper Address?

In multi-agent reinforcement learning, agents often develop "emergent communication" to solve tasks. However, most research uses "cheap-talk" channels—discrete symbols that have no inherent meaning or cost. Because these symbols are arbitrary, two agents trained independently will almost certainly develop incompatible protocols (e.g., Agent A uses "0" for "apple," while Agent B uses "1").

This creates a massive barrier for Zero-Shot Coordination (ZSC), where agents must coordinate with novel partners at test time. While an existing method called "Other-Play" (OP) can solve this, it requires researchers to manually hard-code the symmetries of the environment beforehand. The authors of this paper ask: Can agents discover these symmetries themselves and use them to form a universal communication protocol?

Methods

The authors propose a two-pronged approach involving a new problem setting and a new algorithm:

  1. The Costly-Channel Setting: Instead of cheap talk, communication is grounded in physics. As shown in Figure 1, a sender (like a robot) must move to a location to send a message. Different locations have different energy costs (distance traveled). Figure 1: Costly-Channel Referential Game setup.

  2. Zipfian Intent Distribution: The things agents want to talk about (intents) are not equally likely. They follow a Zipf distribution, where a few intents are very common and most are rare—similar to human language.

  3. QED Algorithm: QED is an iterative algorithm designed to find symmetries.
  4. It first trains a set of policies using standard self-play.
  5. It then compares these policies to find "equivalence mappings"—actions that are interchangeable because they have the same cost (energy degeneracy).
  6. Finally, it uses these discovered symmetries within the Other-Play objective to force agents to ignore arbitrary differences and coordinate on the underlying structure (e.g., "always use the cheapest available action for the most common intent").
Figure 1: Costly-Channel Referential Game. Sender agent (robot) must take costly physical actions to move to target locations on the grid. The energy cost incurred corresponds to the number of steps traversed. Receiver agent (camera) observes final location of sender and must predict what intent the action taken implicitly communicates.

Datasets

The researchers evaluated their approach using synthetic Referential Games:

  • No Degeneracy Task: 10 actions, each with a unique energy cost. This is a baseline where ZSC is relatively easy because there is only one way to be energy-efficient.
  • Energy Degeneracy Task: 17 actions where groups of actions share the same energy cost. This is much harder because agents must decide which of the equally-cheap actions to use without being able to talk about it beforehand.

Key Insights and Ideas

  • Cost + Frequency = Grounding: By combining energy costs with a non-uniform distribution of intents, the "optimal" protocol becomes unique. Just like Morse code uses the shortest signal for the most common letter ('E'), agents naturally gravitate toward using low-energy actions for high-frequency intents.
  • Symmetry Discovery vs. Hard-coding: The "Quasi" in QED refers to the fact that we don't need to find all mathematical symmetries of a game—only the ones that cause independently trained agents to disagree.
  • Breaking Energy Degeneracy: The biggest challenge in ZSC is when multiple actions are equally good. QED treats these as an "equivalence class," essentially telling the agents: "If you can't distinguish between these actions based on cost, don't rely on them for specific meanings."

Key Results

The results demonstrate that QED successfully bridges the gap between self-play and zero-shot coordination.

  • Cross-Play (XP) Performance: In the difficult Energy Degeneracy task, standard Self-Play (SP) agents failed miserably when paired with new partners, achieving only 24% accuracy. In contrast, QED achieved 93% accuracy, matching the performance of Other-Play even though QED had to discover the symmetries from scratch.
  • Visualizing Coordination: Figure 2 (SP) shows that while agents coordinate perfectly with their original partners (diagonal line in the middle), they fail with new ones (scattered blocks on the right). Figure 3 (QED) shows a clean diagonal for both, proving the protocol is universal.

Figure 2: Self-Play (SP) fails to generalize to novel partners. Figure 3: QED achieves consistent coordination across novel partners.

Limitations and Future Work

  • Scalability: The current experiments use discrete, low-dimensional action spaces. Scaling QED to high-dimensional, continuous robot control remains a significant challenge.
  • Sub-optimal Traps: The algorithm relies on agents finding "near-optimal" policies. If the initial training phase gets stuck in a poor local optimum, QED might discover incorrect equivalence classes, leading to a total coordination breakdown.
  • Real-world Grounding: While "energy cost" is a great proxy, real-world ZSC with humans involves complex social and linguistic priors that go beyond simple energy minimization.

Summary updated

Abstract

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.
BibTeX
@misc{bullard2021quasi,
  author = {Kalesha Bullard and Douwe Kiela and Franziska Meier and Joelle Pineau and Jakob Foerster},
  title = {{Quasi-Equivalence Discovery for Zero-Shot Emergent Communication}},
  year = {2021},
  eprint = {2103.08067},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2103.08067},
}
Figure