The Yokai Learning Environment: Tracking Beliefs Over Space and Time

Constantin Ruhdorfer, Matteo Bortoletto, Johannes Forkel, Jakob Foerster, Andreas Bulling

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.

The YLE requires complex spatio-temporal belief tracking and reasoning about a partner's knowledge.

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:

  1. 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.
  2. 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.
  3. 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.
Linear probing shows that internal belief representations of card colors degrade significantly during cross-play (XP) compared to self-play (SP).
  • 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

Abstract

The ability to cooperate with unknown partners is a central challenge in cooperative AI and widely studied in the form of zero-shot coordination (ZSC), which evaluates an algorithm by measuring the performance of independently trained agents when paired. The Hanabi Learning Environment (HLE) has become the dominant benchmark for ZSC, but recent work has achieved near-perfect inter-seed cross-play performance, limiting its ability to track algorithmic progress. We introduce the Yokai Learning Environment (YLE) - an open-source multi-agent RL benchmark in which effective collaboration requires building common ground by tracking and updating beliefs over moving cards, reasoning under ambiguous hints, and deciding when to terminate the game based on inferred shared knowledge - features absent in the HLE, where beliefs are tied to hand slots and hints are truthful by rule. We evaluate the leading ZSC methods, including High-Entropy IPPO, Other-Play, and Off-Belief Learning, which achieve near-perfect inter-seed cross-play in the HLE, and show that in the YLE they exhibit persistent SP-XP gaps, degraded early-ending calibration, and weaker belief representations in cross-play, indicating failure to maintain consistent internal models with unseen partners. Methods that perform best in the HLE do not perform best in the YLE, indicating that progress measured on a single benchmark may not generalise. Together, these results establish YLE as a challenging new ZSC benchmark.
BibTeX
@misc{ruhdorfer2025yokai,
  author = {Constantin Ruhdorfer and Matteo Bortoletto and Johannes Forkel and Jakob Foerster and Andreas Bulling},
  title = {{The Yokai Learning Environment: Tracking Beliefs Over Space and Time}},
  year = {2025},
  eprint = {2508.12480},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2508.12480},
}
Figure