  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.
