A New Formalism, Method And Open Issues For Zero-shot Coordination

Abstract

In many coordination problems, independently reasoning humans are able to discover mutually compatible policies. In contrast, independently trained self-play policies are often mutually incompatible. Zero-shot coordination (ZSC) has recently been proposed as a new frontier in multi-agent reinforcement learning to address this fundamental issue. Prior work approaches the ZSC problem by assuming players can agree on a shared learning algorithm but not on labels for actions and observations, and proposes other-play as an optimal solution. However, until now, this "label-free" problem has only been informally defined. We formalize this setting as the label-free coordination (LFC) problem by defining the label-free coordination game. We show that other-play is not an optimal solution to the LFC problem as it fails to consistently break ties between incompatible maximizers of the other-play objective. We introduce an extension of the algorithm, other-play with tie-breaking, and prove that it

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keytreutlein2021a

Related papers

• Noisy Zero-shot Coordination: Breaking The Common Knowledge Assumption In Zero-shot Coordination Games (2024)0.00
• "other-play" For Zero-shot Coordination (2020)0.00
• Cooperative Open-ended Learning Framework For Zero-shot Coordination (2023)0.00
• Tackling Cooperative Incompatibility For Zero-shot Human-ai Coordination (2023)0.00
• Knowpc: Knowledge-driven Programmatic Reinforcement Learning For Zero-shot Coordination (2024)0.00
• Towards Few-shot Coordination: Revisiting Ad-hoc Teamplay Challenge In The Game Of Hanabi (2023)0.00
• Cross-environment Cooperation Enables Zero-shot Multi-agent Coordination (2025)0.00
• Zero Shot Coordination For Sparse Reward Tasks With Diverse Reward Shapings (2026)0.00