Introduction
Zero-Shot Coordination (ZSC) represents a significant challenge in artificial intelligence: creating agents capable of effective collaboration with previously unseen partners, including humans. Traditional approaches, such as Self-Play (SP), often result in agents that develop highly specialized, idiosyncratic conventions. While these agents perform well with copies of themselves, they frequently fail when paired with partners who do not share those specific conventions—a phenomenon known as Cooperative Incompatibility (CI).
A common example of CI occurs in the collaborative game Overcooked. An agent trained solely through self-play might learn a rigid strategy, such as exclusively preparing onion soup. When paired with a human partner who attempts to make tomato soup, the agent's inability to adapt leads to a complete breakdown in coordination.
The COLE Framework
To address this, the Cooperative Open-ended LEarning (COLE) framework reframes cooperative tasks through the lens of Graphic-Form Games (GFGs). In a GFG, strategies are represented as nodes in a graph, and edge weights signify the quality of coordination between them.
Preference GFGs and Cooperative Centrality
Central to COLE is the concept of Preference GFGs (P-GFGs). In this subgraph, directed edges point from a node to its "preferred" partner—the strategy that yields the highest mutual reward. By treating "cooperatability" as a structural property of this graph, the framework identifies strategies with high centrality. An agent that is a preferred partner for many others is considered to have low cooperative incompatibility.
Solving for Incompatibility
The framework employs a Cooperative Incompatible Solver to identify the most difficult-to-collaborate-with strategies within a population. The authors propose two variants:
- $COLE_{SV}$: Utilizes a "Graphic Shapley Value" (incorporating PageRank-like centrality) to measure a strategy's cooperative contribution.
- $COLE_R$: A simplified version based on average rewards across the population.
Training for Robustness
The training objective in COLE is dual-purpose. Instead of merely maximizing self-play rewards, the trainer optimizes for individual performance while simultaneously acting as the "best response" to the most incompatible strategies identified by the solver. To prevent overfitting to specific partners, the framework implements SUCG (Sampled Upper Confidence Bound for Game Graph), a mechanism that balances exploration and exploitation during teammate selection.
Experimental Setup
The researchers evaluated COLE using the Overcooked benchmark across five diverse layouts: Cramped Room, Asymmetric Advantages, Coordination Ring, Forced Coordination, and Counter Circuit.
Beyond AI-proxy evaluations, the authors introduced the COLE-Platform, an online experimental pipeline for human-AI studies. They conducted a large-scale study involving 130 participants to assess both objective performance and subjective user experience.
Results
Experimental results demonstrate that COLE significantly outperforms state-of-the-art baselines, including Population-Based Training (PBT), Fictitious Co-Play (FCP), and Maximum Entropy Population (MEP).
Zero-Shot Performance
In AI-proxy tests, $COLE_{SV}$ consistently achieved higher coordination scores, particularly in complex layouts like Forced Coordination and Asymmetric Advantages where rigid strategies typically fail.
Human-AI Coordination
The human study revealed a strong preference for COLE agents. Participants rated COLE higher across three key subjective metrics:
- Fluency: The perceived smoothness of the coordination.
- Preference: The overall desire to play with the agent again.
- Understanding: The clarity of the AI's intent and actions.
Theoretically, the authors show that COLE converges toward a "local best-preferred strategy"—an agent that serves as the most desirable partner for the broader population, effectively resolving the "Onion vs. Tomato" dilemma.
Limitations and Future Work
While effective, the COLE framework faces certain challenges. The calculation of the Graphic Shapley Value is computationally intensive, requiring Monte Carlo sampling for scalability. Additionally, the framework's sensitivity to the ranking threshold parameter $k$ suggests a need for more automated tuning methods. Future research will focus on scaling COLE to high-dimensional environments and multi-agent scenarios involving more than two players.
Summary updated