Source-linked AI summary
"Other-Play" for Zero-Shot Coordination
Hengyuan Hu, Adam Lerer, Alex Peysakhovich, Jakob Foerster
TL;DR
Zero-shot coordination asks agents to cooperate with novel partners despite self-play’s tendency to create conventions that fail across independently trained agents. The paper introduces other-play, which trains against symmetry-transformed partner policies, and reports theoretical guarantees plus improved coordination in AI and human Hanabi pairings. The authors also frame OP as a promising direction rather than a universal solution and note that its current formulation assumes known symmetries.
Problem
Zero-shot coordination requires agents to quickly cooperate with novel partners, while standard self-play can produce specialized conventions that do not transfer to independently trained partners.
Method
Other-play enhances self-play by maximizing reward against agents following the same policy under random relabelings of states and actions from known symmetries.
Results
The paper characterizes OP theoretically, implements it with deep reinforcement learning, and evaluates it in Hanabi with AI and human partners.
Takeaways & Limitations
OP constructs agents that are better able to zero-shot coordinate with unseen AI and human partners within the reported Hanabi experiments.
Takeaways & Limitations
The approach currently assumes that the environment’s symmetries Φ are provided to the algorithm, while discovering them remains a separate optimization problem.
Abstract
from arXiv · showhide
We consider the problem of zero-shot coordination - constructing AI agents that can coordinate with novel partners they have not seen before (e.g. humans). Standard Multi-Agent Reinforcement Learning (MARL) methods typically focus on the self-play (SP) setting where agents construct strategies by playing the game with themselves repeatedly. Unfortunately, applying SP naively to the zero-shot coordination problem can produce agents that establish highly specialized conventions that do not carry over to novel partners they have not been trained with. We introduce a novel learning algorithm called other-play (OP), that enhances self-play by looking for more robust strategies, exploiting the presence of known symmetries in the underlying problem. We characterize OP theoretically as well as experimentally. We study the cooperative card game Hanabi and show that OP agents achieve higher scores when paired with independently trained agents. In preliminary results we also show that our OP agents obtains higher average scores when paired with human players, compared to state-of-the-art SP agents.
1. Introduction
Zero-shot coordination requires agents to quickly cooperate with unfamiliar partners, but self-play can produce specialized conventions that fail to transfer. Other-play (OP) uses known symmetries to seek robust strategies, with theoretical and Hanabi evaluations supporting its coordination benefits.
- Zero-shot coordination places independently constructed agents with novel partners who must coordinate quickly to earn high payoffs.
- Self-play can produce inhuman, specialized strategies that coordinate with the training partner but fail with separately trained agents.
- OP trains agents against randomly relabeled states and actions under known symmetries, seeking robustness to partners who break symmetries differently.
- In the lever game, random selection among 10 equally rewarding levers yields an expected reward of 1/10 = 0.1 without prior coordination.
- When one lever pays 0.9 and the others pay 1.0, OP selects the 0.9 lever because the 1.0 levers are symmetric and cannot be coordinated upon.
- OP is a meta-strategy equilibrium, and unlike self-play methods such as VDN or SAD, it uses problem features rather than action labels.
- The paper contributes OP, characterizes it as a highest-payoff meta-equilibrium, develops a deep-RL implementation, and evaluates it in Hanabi.
2. Related Work
Related work addresses cooperative equilibrium selection, ad-hoc teamwork, human modeling, focal points, domain randomization, and symmetry-based abstractions. Zero-shot coordination differs by requiring fixed policies to cooperate without prior shared context or adaptation at test time.
- Self-play can reach cooperative equilibria, but related work often focuses on improving payoff or efficiency within agents trained together.
- Ad-hoc teamwork typically learns partners’ policies during interaction, whereas pure zero-shot coordination allows no time to update the fixed policy.
- Other work uses observed test-time behavior to select an existing social convention or build a human model, unlike the pure zero-shot setting.
- Focal-point approaches rely on meaningful exogenous features or action labels, while zero-shot coordination lacks shared exogenous features.
- Theoretical work on evolving coordination generally studies long-run outcomes within one learning group rather than engineering agents for novel partners.
- Human decision models could support zero-shot coordination if they accurately predict counterpart actions, reducing the task to learning a best response.
- OP resembles domain randomization by making policies invariant to how partners break symmetries, while symmetry-based abstractions pursue different goals such as state compression or Nash-equilibrium computation.
3. Zero-Shot Coordination
The paper formalizes zero-shot coordination in fully cooperative, partially observed Dec-POMDPs where independently trained agents must interact without prior strategy coordination. It defines environment symmetries and motivates policies robust to partners’ different symmetry breaking.
- The environment is a fully cooperative, partially observed Dec-POMDP in which agents share rewards conditioned on states and joint actions.
- Zero-shot coordination assumes independent designers construct policies without prior coordination and then deploy them in novel Dec-POMDP interactions.
- Equivalence mappings Φ are bijections over states, observations, and actions that leave the Dec-POMDP unchanged.
- A gridworld example illustrates symmetry operations that invert axes while correspondingly relabeling actions such as up and down.
- These symmetries preserve trajectories and rewards because states and actions lack payoff-relevant labels.
- Separately trained self-play agents may break symmetries differently and fail dramatically when paired, motivating policies robust to this failure mode.
4. Other Play
Self-play optimizes performance with a matched policy but can select multiple symmetry-breaking optima that do not coordinate across independent training runs. Other-play instead optimizes against randomly symmetry-transformed partner policies, yielding permutation-invariant equilibria with strong theoretical guarantees.
- Self-play: Self-play optimizes joint return, and deep reinforcement learning can approximate this objective in non-tabular Dec-POMDPs.
- Self-play: Multiple self-play optima may use coordinated symmetry breaking, so separately trained self-play agents need not achieve their self-play payoff when paired.
- Other-play: Other-play maximizes expected return against a randomly symmetry-equivalent partner policy rather than a particular partner policy.
- Other-play: The symmetry distribution is uniform over Φ, whose transformations preserve the underlying Markov decision process.
- Theory: The expected OP return equals the expected return obtained when each player independently plays a policy component under the uniform mixture of transformed policies.
- Theory: OP produces the uniform mixture πΦ with the highest return J(πΦ).
- Theory: When one agent uses OP, it is payoff-maximizing for the partner, and both agents using OP form the best possible meta-equilibrium.
5. Implementing Other Play via Deep RL
The authors adapt other-play to deep reinforcement learning by randomizing each agent’s representation with independent environment symmetries. This asymmetric training produces permutation-invariant equilibria corresponding to the other-play objective.
- Deep RL implementation: Deep RL optimization of other-play is implemented as a specific form of asymmetric domain randomization.The adaptation targets local maxima of the other-play objective in non-tabular settings.
- Deep RL implementation: Each agent independently receives a uniformly sampled permutation of the state, observation, and action spaces during every training episode.Agents act in different permutations of the same environment.
- Deep RL implementation: This randomized environment is equivalent to other-play because each policy becomes a best response to the uniform mixture of symmetry-permuted partner policies.The resulting fixed points are permutation-invariant equilibria.
- Scope: Other-play is compatible with any optimization strategy whenever the underlying Markov decision process has symmetries.The method is not restricted to a particular learning algorithm.
6. Experiments
Experiments compare self-play and other-play in a lever game and Hanabi, including cross-play among independently trained agents and preliminary tests with human partners. Other-play improves zero-shot coordination, while self-play can favor specialized conventions that fail across partners.
- 6.1. Lever Game: Other-play agents select the unique 0.9-point lever during training and testing, enabling successful zero-shot coordination with other other-play agents.The lever game has ten possible actions per player, and performance is measured in training self-play and test-time zero-shot coordination.
- 6.1. Lever Game: Self-play agents obtain 1.0 points in training but entirely fail to coordinate with independently trained self-play agents.The result illustrates the gap between partner-specific training performance and zero-shot coordination.
- 6.2. Hanabi with AI Agents: Hanabi uses color permutations as symmetries because, without side information, permuting card colors leaves the game unchanged.Hanabi requires players to rely on information from partners because they cannot see their own cards.
- 6.4. Evaluation: Cross-play evaluates independently trained agents by pairing models within the same method and measuring their game scores.Figure 4 visualizes individual pairings, while Table 1 reports within-method averages and self-play scores.
- 6.4. Evaluation: SAD coordinates with itself but fails with other SAD agents, whereas SAD with other-play significantly improves cross-play, especially for limited-representation models.As networks become more complex, different strategies emerge and cross-play performance drops.
- 6.4. Evaluation: Policy-response matrices reveal that paired SAD agents develop differing, hard-to-understand conventions, while other-play removes these convention types and tends to use more interpretable color hints.A large matrix difference indicates that partners respond differently to the same actions, creating a recipe for miscoordination.
- 6.5. Hanabi with Humans: Humans scored 15.75 with the other-play bot and 9.15 with the self-play bot, while bomb-out rates were 45% and 85%, respectively.These preliminary results report significantly better performance for the other-play bot when paired with humans.
- 6.5. Hanabi with Humans: The authors caution that other-play may not work in every zero-shot coordination setting involving human cooperation.They characterize the human results as encouraging but preliminary and as support for further research.
7. Other Attempts
The authors tested several alternatives to other-play for Hanabi, but none produced high cross-play performance with previously unseen agents.
- The study examined multi-agent RL adaptations of cognitive hierarchies, k-level reasoning, and population-based training.
- These approaches were motivated by the expectation that they could reduce arbitrary symmetry breaking or regularize communication protocols.
- The reported comparison used an exact binomial test of whether OP had a higher score than the control group.
- None of the tested approaches produced high cross-play performance in Hanabi.
- The authors treat high cross-play performance as a necessary condition for high zero-shot performance with humans.
8. Conclusion
The paper presents other-play as an extension of self-play for zero-shot coordination and validates it theoretically, algorithmically, and experimentally in Hanabi. The authors report robust coordination with AI agents and humans, while emphasizing that OP is not universal and currently assumes known symmetries.
- Other-play extends self-play to construct agents that better coordinate with partners they have not seen before.
- The paper proves theoretical properties of OP, implements it with deep reinforcement learning, and evaluates it in Hanabi.
- Hanabi experiments show that OP constructs robust agents that can play with other AI agents as well as humans.
- OP is not claimed to solve every zero-shot coordination problem.
- The current algorithm assumes that the problem’s symmetries are provided, while discovering them remains an open optimization problem.
A. Details on Other Attempts
The paper evaluates cognitive hierarchies, K-level reasoning, and population-based training as alternatives for improving zero-shot coordination. These approaches face substantial computational costs, non-monotonic progress, or apparent cross-play success that does not resolve symmetry-breaking problems.
- Cognitive hierarchies: Cognitive hierarchies train a sequence of agents, with each agent best responding to a pool of earlier, less capable agents.The initial agent acts randomly, while later agents are intended to learn progressively more useful behavior.
- Cognitive hierarchies: Cognitive hierarchies converge slowly and require prohibitive time and computation for complicated tasks such as Hanabi.Five levels normally take several days, whereas SAD and other-play reach 23 points in self-play in less than 20 hours under the same settings and hardware.
- K-level reasoning: K-level reasoning was evaluated with K = 10, but its improvements across levels were non-monotonic and retained high time and sample complexity.The method reduced the self-play/cross-play gap relative to cognitive hierarchies, but remained costly.
- Population-based approaches: Population-based training pairs distinct agents simultaneously and can achieve decent cross-play scores across separately seeded populations.The reported populations used four differently initialized agents each, but their hyper-parameter diversity was smaller than in the Figure 4 comparison.
- Population-based approaches: Population agents often avoid color hints, allowing cross-play success without solving the color-symmetry problem that other-play targets.Their color-hint usage differs greatly between populations and is qualitatively difficult for humans to play with.