Quasi-Equivalence Discovery for Zero-Shot Emergent Communication

1 Introduction

• Cheap-talk channels permit many payout-equivalent protocols, but independently trained senders and receivers may use incompatible encodings at test time.For example, permuting channel bits and adapting the receiver preserves payouts but can make separately trained partners incompatible.Source: §1 · p. 1
• Combining variable message costs with nonuniform intent frequencies makes lower-energy actions encode common intents, yielding a unique solution to the ZSC problem.The paper identifies energy cost and nonuniform, including Zipfian, intent distributions as regularization mechanisms for ZSC.Source: §1 · p. 2
• Learning ZSC is challenged by the need to discover the latent protocol structure and by sender-receiver lock-in, while Other-Play requires symmetries to be supplied in advance.The interpretation of a message depends on the full policy, which can trap learning in local optima.Source: §1 · p. 2
• QED recovers equivalence mappings from optimal self-play policies, then uses them with Other-Play to train policies that reveal further equivalences.This iterative process is proposed to address the challenge of discovering the latent structure agents can coordinate on.Source: §1 · p. 2
• The proposed evaluation finds that QED converges to the unique ZSC policy and recovers Other-Play's performance when given ground-truth symmetries.The experiments use a costly-action referential game with and without energy degeneracy.Source: §1 · p. 2

2 Related Work

• Earlier emergent-communication work generally assumes symbolic cheap-talk channels and studies self-play, unlike this paper's zero-shot setting with costly messages and nonuniform intent priors.The cited literature includes work on emergent communication and grounded language for robots [Foerster et al., 2016, Lazaridou et al., 2017, Havrylov and Titov, 2017, Cao et al., 2018, Bouchacourt and Baroni, 2018, Eccles et al., 2019, Graesser et al., 2019, Chaabouni et al., 2019, Jaques et al., 2019, Lowe et al., 2019b; Steels et al., 2012, Spranger, 2016].Source: §2 · p. 3
• Unlike Ad-Hoc Teamwork, zero-shot coordination seeks a learning algorithm that lets independently trained agents coordinate on their first attempt, without a supplied team population.The passage also contrasts this setting with cognitive-hierarchy and focal-point approaches, which it says do not apply when messages lack grounded meanings and agents share no labels.Source: §2 · p. 3
• Pragmatic-reasoning approaches such as Frank and Goodman's are inapplicable here because messages have no a-priori grounded meaning, leaving a naive speaker uninformative.Source: §2 · p. 3
• Other-Play is the closest method, but it requires symmetries to be provided with the Dec-POMDP; this work instead learns them in a setting where communication actions have no prior grounded meaning.The paper distinguishes its focus on emergent communication from approaches that assume meaningful messages.Source: §2 · p. 3

3.1 Multi-Agent Reinforcement Learning

• A Dec-POMDP models agents with joint actions and observations, state transitions, rewards, and policies chosen to maximize expected long-term shared return.Source: §3.1 · p. 3

3.2 Zero-Shot Coordination and Other-Play

• Zero-shot coordination concerns independently trained partners coordinating at test time; Other-Play maximizes expected return over equivalence classes of policies sampled independently for players.Symmetry mappings preserve equivalent trajectories and returns under corresponding state and action permutations.Source: §3.2 · p. 4

3.3 Referential Games

• In a referential game, a sender observes an intent and sends a message for a receiver to interpret, while both agents share a cooperative payoff.The described training regime centralizes training but restricts agents at test time to local action-observation histories.Source: §3.3 · p. 4

3.4 Zipf Distribution

• The Zipfian prior is a discrete power law in which lower-ranked intents occur more frequently, providing agents a nonuniform monotonic distribution over intents.Source: §3.4 · p. 4

4 The Zero-Shot Communication Setting

• Costly actions and a non-uniform intent distribution let agents encode common intents with lower-energy actions and rarer intents with higher-energy actions.The paper presents this as the unique solution to its zero-shot communication problem.Source: §4 · p. 5
• In referential communication, the sender receives an intent and sends an action as a message, while the receiver observes it and predicts the intent.Cross-play evaluates senders and receivers trained independently.Source: §4.1 · p. 5, §4 · p. 5

4.1 Equivalences in Zero-Shot Communication

• When multiple actions are equivalent, self-play policies can break their symmetry differently, making independently trained agents incompatible at test time.Agents should therefore be prepared to partner with symmetry-equivalent policies.Source: §4.1 · p. 5
• Other-Play replaces the sender policy with a symmetry-transformed version, allowing the receiver to infer intent across an equivalence class of sender policies.This removes dependence on one specific training sender policy.Source: §4.1 · p. 5
• The Other-Play objective implies high mutual information between intents and equivalence classes of sender actions, making an action's class sufficient to infer the intent.The paper states I(G; A) = I(G; Φ(A)) ≫ 0.Source: §4.1 · p. 5

5 Discovering Equivalences

• Instead of finding every symmetry, QED seeks only mappings that produce equivalent but mutually incompatible optimal joint policies.The paper notes that general symmetry discovery in a Dec-POMDP is NP-hard.Source: §5 · p. 6
• Because symmetry-transformed versions of an optimal policy are also optimal and arise with the same probability across training runs, QED can discover mappings from learned policies.This avoids searching directly over Dec-POMDP symmetries.Source: §5 · p. 6
• QED iteratively trains optimal joint policies under current mappings, infers mappings from policy pairs, and stops when self-play and cross-play performance approximately agree.New mappings are retained when their loss is sufficiently low.Source: §5 · p. 6
• On energy degeneracy, QED significantly outperforms self-play; on no degeneracy, QED, Other-Play with ground-truth symmetries, and self-play perform comparably.The table caption attributes the energy-degeneracy advantage to discovering symmetries amid redundant actions without pre-coordination.Source: Table 1 · p. 7
• The ablations show that both common-knowledge constraints—energy costs and a non-uniform intent distribution—are critical for learning zero-shot communication policies.In three ablations, actions fall into one equivalence class and performance degrades.Source: Table 2 · p. 7

6.1 Experimental Setup

• The experiments compare SP, OP, and QED on two five-goal tasks, including a 17-action task with redundant equal-cost actions that makes zero-shot coordination more challenging.The No Degeneracy task instead has 10 actions with distinct energy values.Source: §6.1 · p. 7

6.2 Results

• On the Energy Degeneracy task, QED substantially outperforms filtered SP and matches OP with ground-truth action symmetries; on No Degeneracy, QED performs comparably to filtered SP and OP.Source: §6.2 · p. 9
• Both energy costs and a nonuniform goal distribution are critical for QED to learn zero-shot communication policies.Source: §6.2 · p. 9
• Energy Degeneracy admits multiple optimal SP policies through permutations of equivalent actions, whereas QED converges to a unique OP policy compatible with a novel partner.Source: §6.2 · p. 9

• The proposed setting combines costly messages and nonuniform intent priors, and QED iteratively discovers policy equivalence classes to learn optimal zero-shot policies.Source: §7 · p. 9
• The authors describe costly communication as an abstract proxy for embodied agents, and identify scaling to high-dimensional continuous actions and states as important for realistic applicability.Source: §7 · pp. 9–10
• The conclusion warns that suboptimal solutions in zero-shot coordination can cause complete coordination failure or lead QED to learn wrong equivalence classes.Source: §7 · p. 10

• Other-Play adapts the self-play objective to optimize over equivalence classes of policies; the derivation simplifies messages to individual actions.Source: §A.1 · p. 12
• For the referential task, the joint policy aims for accurate goal prediction and, with a costly channel, also minimizes communication cost.Source: §A.1 · p. 12
• The costly-channel Other-Play objective maximizes mutual information between goals and action equivalence classes, minimizes cross-entropy for sender actions, and penalizes sender-action cost.Source: §A.1 · p. 13

A.2 Task 2: Energy Degeneracy – Additional Results

• QED results are shown for zero-shot coordination because its training and novel-partner communication success are consistent; SP-baseline results show both separately.The additional figures compare protocols learned under different common-knowledge constraints.Source: §A.2 · p. 13
• Only QED policies trained with a nonuniform intent distribution and costly channel communicate successfully, while both conditions perform consistently with training and novel partners.Figure 4 compares cheap-talk and costly-channel protocols under a Zipfian intent distribution.Source: Figure 4 · p. 14
• With SP training and a cheap-talk channel, zero-shot communication is more challenging than communication with training partners, alongside divergent sender policies across pairs.Figure 5 shows SP and XP results separately.Source: Figure 5 · p. 15
• With SP training and a costly channel, zero-shot communication remains substantially harder than training-partner communication, but is slightly more successful than the no-energy-penalty baseline.Figure 6 reports the same qualitative trends as the comparison using QED.Source: Figure 6 · p. 16