TL;DR
The paper introduces the Yōkai Learning Environment (YLE), a hardware-accelerated benchmark designed to stress-test Zero-Shot Coordination (ZSC) in cooperative AI. Unlike previous benchmarks that have been effectively "solved," YLE forces agents to track moving entities, interpret ambiguous communication, and make high-stakes decisions to end the game early. The authors demonstrate that state-of-the-art ZSC algorithms fail to generalize to these challenges, showing massive performance drops and completely reversed rankings compared to older benchmarks.
What Problem Does This Paper Address?
In cooperative AI, Zero-Shot Coordination (ZSC) challenges independently trained agents to successfully collaborate when paired together for the very first time. To do this well, agents must develop a "Theory of Mind" (ToM)—the ability to reason about what their partner knows, believes, and intends.
For years, the Hanabi Learning Environment (HLE) has been the undisputed gold standard for testing ZSC. However, recent algorithms have achieved near-perfect cross-play performance on Hanabi, saturating the benchmark and making it difficult to track further algorithmic progress.
The authors argue that Hanabi simplifies coordination in ways that don't mirror real-world complexity: its cards remain in static hand slots, and hints are perfectly truthful by design. YLE addresses this gap by introducing a benchmark based on the board game Yōkai, where information is localized, cards move dynamically across a grid, hints are inherently ambiguous, and agents must decide when they share enough common ground to risk ending the game early.
Methods
The authors developed YLE natively in JAX, allowing the entire game simulation to run end-to-end on GPUs for massive parallelization. They model the game state as a graph where vertices represent cards and hints, and edges represent spatial adjacency.
To evaluate the current state of ZSC research, they adapted three leading coordination algorithms to YLE:
- Other-Play (OP): This method prevents agents from developing quirky, partner-specific conventions by applying random symmetry transformations (such as permuting card colors or rotating the spatial grid) during training.
- Off-Belief Learning (OBL): This approach forces agents to optimize actions based on an explicitly learned belief model that assumes past actions were generated by a fixed reference policy. This paper presents the first-ever implementation of OBL outside of Hanabi.
- High-Entropy IPPO (HE): This algorithm uses entropy regularization to encourage diverse, symmetric policies that are more likely to compatible with unseen partners.
Additionally, the authors trained linear probes on the agents' recurrent hidden states to decode how accurately the models internally track card colors over time.
Datasets
The primary contribution is the Yōkai Learning Environment (YLE) itself, an open-source benchmark compatible with JaxMARL. YLE is highly configurable, featuring a simplified 9C variant (9 cards, 3 colors) and the full 16C variant (16 cards, 4 colors).
To anchor the AI performance, the authors also collected a small baseline dataset of human performance consisting of 25 games played by 5 human participants.
Key Insights and Ideas
- Benchmark Overfitting is Real: Algorithms that excel in Hanabi do not necessarily translate to YLE. In fact, the method rankings completely reversed: Other-Play outperformed High-Entropy IPPO and Off-Belief Learning in YLE, exposing a critical vulnerability to benchmark-specific overfitting in ZSC research.
- Spatio-Temporal Re-binding: In Hanabi, a card's identity is tied to a static hand slot. In YLE, cards move across a grid. Agents must dynamically re-bind their beliefs to moving entities, which proves to be a massive hurdle for current architectures.
- The Cost of Ambiguity: Because YLE hints can be multi-colored and are not forced to be strictly truthful, OBL's belief model must treat communication as unreliable evidence, making posterior estimation significantly harder than in Hanabi.
- Common Ground Dissolution: Linear probing revealed that while agents maintain highly accurate internal models of the board during self-play, these internal belief representations degrade drastically during cross-play with an unseen partner.
Key Results
- The SP-XP Gap: While standard Independent PPO (IPPO) achieves a strong self-play (SP) score of 7.5 in the 2-player 9C setting, its cross-play (XP) score plummets to 1.6 when paired with an independently trained seed.
- Algorithm Performance: Other-Play (OP) achieved the best cross-play return in the 2-player 9C setting (4.8 XP vs 6.6 SP), outperforming High-Entropy IPPO (4.1 XP) and all levels of Off-Belief Learning (which maxed out at 2.8 XP).
- High-Stakes Failure: High-Entropy IPPO completely collapsed in 3-player and 4-player settings, learning to terminate the game immediately to avoid penalties rather than attempting to coordinate under high uncertainty.
- Speed and Scalability: Thanks to its JAX implementation, YLE scales exceptionally well, reaching over 550,000 steps per second (SPS) for the 9C variant on a single Nvidia H100 GPU.
Limitations and Future Work
- Imperfect Memory Bottleneck: When perfect memory assistance is removed (forcing agents to rely entirely on recurrent networks like GRUs or Transformers to remember card histories), performance drops sharply. Current memory architectures struggle with the long-horizon tracking required by YLE.
- Scalability to Full Game: While the 9-card (9C) version is solvable in self-play, larger configurations like the full 16-card (16C) game remain completely unsolved even in self-play, representing a massive challenge for future MARL exploration.
- Extension to Ad-Hoc Teamwork: The authors suggest that once ZSC methods improve on YLE, it will serve as an excellent testbed for Ad-Hoc Teamwork (AHT), where agents must adapt online to completely novel partners.
Summary updated