Robust Zero Shot Coordination with Unseen Partners

788 concepts389 papers4 proposals

When multi-agent reinforcement learning (MARL) agents are trained via self-play, they achieve remarkable success by co-adapting to their own strategies. However, this success hides a fundamental flaw: self-play agents develop highly specialized, brittle conventions that fail catastrophically when the agent is paired with a stranger or a human collaborator.

Overcoming this "partner-specific overfitting" requires moving toward Zero-Shot Coordination (ZSC) and Ad Hoc Teamwork—paradigms where agents must cooperate effectively with entirely novel partners without the benefit of prior joint training or pre-established communication protocols.

The Curse of Co-Adaptation

To understand why zero-shot coordination is difficult, we must first understand why standard training fails. In a purely cooperative environment, there are often many equally valid but mutually incompatible ways to coordinate. For example, in the cooperative card game Hanabi, breaking game symmetries arbitrarily (e.g., deciding that hinting "red" means "play your oldest card") works perfectly if both agents share that exact convention.

During self-play, agents co-adapt and lock into these idiosyncratic, arbitrary protocols. As Tieleman et al. observe, this creates a "curse of co-adaptation," where agents develop specialized communication strategies that are completely non-transferable. When paired with an independently trained partner or a human proxy, the coordination collapses because the stranger does not share these arbitrary rules. Canaan demonstrates that self-play agents overfit to the specific, highly predictable cues of their clones, rendering them incapable of handling the less consistent or sub-optimal strategies common in broader populations.

The scale of this challenge is highlighted by benchmarks like the Overcooked Generalisation Challenge (Ruhdorfer et al.; The Overcooked Generalisation Challenge: Evaluating Cooperation with Novel Partners in Unknown Environments Using Unsupervised Environment Design), which show that state-of-the-art self-play agents frequently perform no better than random movement when paired with novel partners in unfamiliar spatial configurations.

Forcing Generalization via Partner Diversity

The core intuition behind solving partner overfitting is simple: if an agent is trained against a single partner configuration, it will overfit; if it is forced to cooperate with a vast, diverse population of partners during training, it must abandon arbitrary conventions and instead learn robust, generalized cooperative behaviors.

To achieve this, researchers focus on generating training pools that prevent the emergence of fragile, shared secrets:

  • Symmetry Invariance: The authors of "Other-Play" for Zero-Shot Coordination introduce a paradigm that randomizes game symmetries during training. This forces agents to only rely on "grounded" strategies that do not depend on arbitrary label choices, ensuring compatibility with independent agents who also avoid arbitrary conventions.
  • Maximum Entropy Populations: Rather than relying on human data, Zhao et al. propose Maximum Entropy Population-based training (MEP). By maximizing a population entropy objective, the framework generates a diverse set of training partners, forcing the primary agent to become a robust "best responder" capable of handling unpredictable human-like behaviors.
  • Predictability and Style Sampling: Nguyen et al. utilize a Theory of Mind observer to deliberately vary the predictability of training partners, ranging from highly structured to erratic. Similarly, Osa et al. use mutual information objectives paired with adversarial sampling to focus training on the most challenging partner styles.
  • Generative Teammate Creation: To scale up behavioral variety, Li et al. leverage Large Language Models (LLMs) to translate natural language coordination descriptions into executable reward functions, creating a semantically diverse library of training partners.

On-the-Fly Partner Modeling

While a diverse training pool creates a robust base policy, true ad hoc teamwork requires an agent to actively adapt during deployment. When dropped into a game with a stranger, the agent must treat its teammate's hidden strategy as an unobserved state variable and infer it in real-time.

One prominent approach is to project the vast space of possible partner behaviors into a compact, manageable latent space. For instance, the Role Play framework (Long et al.) maps partner policies into a "role space" based on psychological metrics like Social Value Orientation (SVO), allowing the agent to predict partner intent and adjust its strategy within a single interaction. To handle fluid environments where team composition changes dynamically, Gu et al. model teamwork situations as continuous latent variables under partial observability, while Rahman et al. utilize Graph Neural Networks (GNNs) to explicitly disentangle the agent's own environmental impact from the actions of its changing teammates.

Alternatively, when explicit policy modeling is too expensive, agents can treat partner actions as dynamic constraints. Liu et al. demonstrate that in heterogeneous teams with varying physical capabilities, an ad hoc agent can achieve zero-shot coordination simply by feeding basic teammate status updates into an LLM-based reasoning loop, treating those updates as boundaries for its own task selection.

Information Regularization and Readability

A final, elegant mechanism for zero-shot coordination focuses on information theory. Instead of trying to guess what a partner will do, an agent can optimize its own policy to be inherently "readable" or independent of specific partner states.

Strouse et al. introduce information-theoretic regularizers that maximize the mutual information between an agent's actions and its goals. This forces the agent to "exaggerate" its movements, effectively communicating its intentions through physical actions so that any reasonable partner can easily coordinate with it.

Conversely, to prevent partner-specific overfitting from occurring in the first place, the authors of Mutual-Information Regularized Multi-Agent Policy Iteration use mutual information as a penalty to discourage agents from over-relying on the specific states or actions of their training partners. By minimizing this informational dependency, the resulting policies remain robust and generalizable across dynamic team compositions.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 424 papers
  2. Version 1 · 2026-10-04 · 360 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_ad_hoc_teamwork_d5c54efb,
  title = {ad hoc teamwork},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/ad-hoc-teamwork/rdr_d5c54efb6a8d469eb27748a7d5d816dc},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 2, frozen text):

@misc{lacuna_ad_hoc_teamwork_d5c54efb_v2,
  title = {ad hoc teamwork},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/ad-hoc-teamwork/rdr_d5c54efb6a8d469eb27748a7d5d816dc/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake