"Other-Play" for Zero-Shot Coordination

In plain words

Two players who have never met must act together without talking. Players trained only by playing against copies of themselves tend to invent private habits, such as a signal only they understand. Those habits break as soon as they meet a stranger who learned on their own.

The paper's fix is to train each player in a world where the labels have been shuffled at random, for example where "red" and "blue" have been swapped for each player. A habit that depends on a label can then not survive, and the player is pushed toward choices that any stranger could also make. The authors test this on the card game Hanabi, where players must cooperate without seeing their own cards, and report that the resulting agents work better with unseen AI partners and with people.

TL;DR

Other-play (OP) is a change to self-play training. Each agent sees a random relabelling of states, observations and actions drawn from the game's known symmetries, so it cannot count on conventions that only work with its own copy. The paper gives a short argument that this is the best outcome for the learner, then implements it with an existing Hanabi method (SAD) and reports higher cross-play and human scores. Results are author-reported, and the method needs the symmetries to be given in advance.

Problem

Self-play (SP) agents trained together can break symmetries in arbitrary ways that work for the pair but not for a new partner §3 §4. The paper calls this the zero-shot coordination problem: partners must coordinate at test time without having trained together §1. In Hanabi, SP agents built with the method of Hu et al. (SAD) reach a high self-play score but fail to coordinate with other independently trained SAD agents §6.4 tab. 1.

In Hanabi, players cannot see their own cards and must learn what their partner means from the partner's actions and hints §6.2.

The method assumes the symmetry set Φ of the Dec-POMDP is known and given to the algorithm. Discovering symmetries is named as future work §8.

Method

Setting. A fully cooperative, partially observed game with N agents sharing one reward, a Dec-POMDP §3. An equivalence mapping φ is a bijection on states, observations and actions that leaves transitions, rewards and observations unchanged §3. Φ is the set of all such mappings. A mapping acts on trajectories and on policies by relabelling inputs and outputs together, so the return of a policy and its relabelled copy are identical §3.

Self-play objective (baseline) §4, eq. 1:

\mathbf{\pi}^* = \arg\max_{\mathbf{\pi}} J(\pi^1, \pi^2) \qquad [\text{eq. 1}]

Other-play objective §4, eq. 2: agent 1 is trained against a randomly relabelled copy of agent 2, with the relabelling drawn uniformly from Φ:

\mathbf{\pi}^* = \arg\max_{\mathbf{\pi}}\; \mathbb{E}_{\phi \sim \Phi}\, J(\pi^1, \phi(\pi^2)) \qquad [\text{eq. 2}]

The paper's theory §4:

1. Lemma 1 §4: the return is unchanged when both policies are relabelled by the same φ, because the game is invariant to φ.
2. Lemma 2 §4: composing a fixed φ with every element of Φ gives Φ again.
3. Proposition 1 §4: the expected OP return of a joint policy equals the return of each player playing the uniform mixture of its relabelled policies, i.e. its own relabelling over Φ.
4. Corollary 1 §4: the policy OP produces is that uniform mixture, and it has the highest return among such mixtures.
5. Proposition 2 §4: if one agent uses OP as its learning rule, OP is also a payoff-maximising rule for the partner, and two OP agents form the best meta-equilibrium over learning rules.

Deep RL implementation §5. OP is applied on top of any SP algorithm. At the start of each training episode, every agent i draws its own relabelling φ_i uniformly and independently from Φ. Agent i observes and acts through φ_i. The environment itself is not relabelled. The paper calls this a specific form of asymmetric domain randomisation §5.

# Other-play training loop  [§5]
# Input:  env, symmetry set Phi (sample uniformly), one policy per agent
# Output: trained policies for all agents

def train_other_play(env, agents, symmetries):
    # Repeat until the training budget is spent  [§5]
    while training:
        # Draw an independent relabelling for each agent  [§5]
        relabellings = [
            sample_uniform(symmetries)
            for agent in agents
        ]
        # Agent i sees and acts through its own relabelling phi_i; the
        # underlying MDP is unchanged  [§5]
        trajectories = run_episode(env, agents, relabellings)
        # Apply the base self-play update (SAD in Hanabi)  [§5] [§6.3]
        for agent, trajectory in zip(agents, trajectories):
            update(agent, trajectory)
    return agents

Hanabi symmetry §6.2. Assuming no side information, a permutation of the card colours leaves the game unchanged, so colour permutations are the class of symmetries used. The paper says OP uses only the problem's features and no action labels §1.

Lever game §1 §6.1 fig. 1. Ten levers; a pair scores 1 if both pick the same lever. In the second variant one lever pays 0.9 and the rest are unchanged §1. Under the symmetry view, the 1.0 levers are interchangeable, so two players who pick at random among them coordinate poorly. OP selects the 0.9 lever. The paper states the expected returns as 0.1 and 0.11 §1.

Symmetry-breaking intuition §3 fig. 2. The paper's gridworld example has two axes of symmetry for a robot that moves in four directions, and the figure is a sketch without a caption fig. 2.

Hyperparameters

Hyperparameters of the base SAD method are not restated in this paper; the authors say they used most of the SAD settings §6.3. Values below are the ones the paper gives.

Results

Author-reported. Hanabi cross-play, SAD family (Hanabi score; cross-play is the non-diagonal mean of each 12-model grid) tab. 1 fig. 4:

Setup: 12 models per row from 4 architectures × 3 seeds, 10k games per pair §6.2 §6.3 fig. 4. The table reports ± values; the paper does not say whether they are standard errors or standard deviations tab. 1.

Lever game §6.1 fig. 3: OP agents coordinate on the 0.9 lever in training and at test time. SP agents reach 1.0 in training but do not coordinate with independently trained SP agents. 30 seeds, shaded band is the s.e.m.

Humans in Hanabi §6.5: 20 participants each played one game with two bots in random order, with the deck shared between the two bots:

Per-seed comparison: OP scored higher in 15 of 20, tied in 2, lower in 3; p = 0.004 by exact binomial test, as the paper states §6.5. The authors call these results preliminary.

Other approaches tried (cognitive hierarchy, K-level, population training) produced low cross-play in Hanabi, which the authors treat as a necessary condition for zero-shot play §7 tab. 2 tab. 3 tab. 4 app. A. Cognitive hierarchy and K-level reached cross-play scores of 2.48 and 6.87 at their best levels (author-reported) tab. 2 tab. 3.

Paper vs code

No official code. The paper points only to a Colab notebook for the lever game (https://bit.ly/2vYkfI7, resolving to a Google Colab file) §6.1, which needs a sign-in and could not be read. GitHub searches for "other-play" returned no repository from the authors' organisation. Other results were third-party: a review (slcnvly/Other-play-for-Zero-Shot-Coordination-Review, MIT) and a reimplementation of the lever game (MWeltevrede/lever-game, no license). Neither was used. The paper's base method, SAD, has a public repository under facebookresearch (hanabi_SAD, archived, license listed as "Other"); the paper says it used that code §6.3, but I did not clone it because its license could not be verified as permissive, and it is not the code for this paper's method.

Pitfalls

• Symmetry set must be given. OP needs Φ as input. The paper assumes it is known §8; there is no procedure for finding it, and a wrong or incomplete Φ is not tested.
• Symmetries are not the same as all relabellings. Relabellings must preserve transitions, rewards and observations §3. The Hanabi choice of colour permutations is valid only when colours carry no side information §6.2.
• OP does not remove conventions. The paper reports that the worst OP partner still uses colour hints in secretive ways §6.4 fig. 5. The method reduces label-based conventions, not all conventions.
• Relabelled trajectories in the update. The paper gives the per-episode sampling and says OP sits on top of SAD §5 §6.3, but does not state how the gradient update treats the relabelled trajectories. Compare against the base method's update before implementing.
• Theory assumptions. The equilibrium claim §4 (Proposition 2) relies on the learning rule not using action or state labels. The proof sketch is brief, and the paper's own experiments only test OP in the lever game and Hanabi.
• Cost of the base method. The paper uses 2 simulation GPUs instead of 1 §6.3; the OP ensemble needs 12 models per method for cross-play, so evaluation grows with the number of seeds and architectures §6.3.
• Evaluation proxy. Cross-play among same-method agents is a proxy for human play, not a measure of it. The human study uses 20 people and a single game each §6.5.
• Score convention. Players keep the score at a bomb-out in the human study, which the authors call more appropriate here §6.5. This differs from the standard Hanabi score convention.

Lineage

• Builds on: self-play §1 §4; SAD (Hu et al.), the base algorithm §6.3; asymmetric domain randomisation, which the paper says OP amounts to §5.
• Compared against: SAD and SAD + AUX (self-play) tab. 1; cognitive hierarchies and K-level reasoning, and population-based training §7 app. A.
• Superseded by: not stated in the paper.