K-level Reasoning for Zero-Shot Coordination in Hanabi

Brandon Cui, Hengyuan Hu, Luis Pineda, Jakob Nicolaus Foerster

This paper presents a novel approach to one of the "holy grails" of multi-agent reinforcement learning: Zero-Shot Coordination (ZSC). While AI agents have mastered games like Chess and Go through self-play, they often fail miserably when paired with a new partner or a human because they develop "secret handshakes"—arbitrary conventions that only their specific training partner understands. The authors demonstrate that by modernizing a classical game theory concept—k-level reasoning—and training it synchronously, they can create agents that coordinate effectively with strangers and humans in the complex cooperative card game Hanabi.

The Challenge of Zero-Shot Coordination

In cooperative games, "Self-Play" (SP) is the standard training recipe. However, SP agents are like twins who have developed a private language; they work perfectly together but are incomprehensible to anyone else. In Hanabi, a game of hidden information where players see everyone's cards except their own, this manifests as "conventions." For example, an agent might learn that "hinting 'Blue'" actually means "play your third card."

The challenge is Zero-Shot Coordination: training an agent that can walk up to a total stranger (or a human) and play effectively on the first try. Previous solutions like Other-Play (OP) require researchers to manually identify all symmetries in a game to "blur" them during training, which is computationally exhausting. Other methods like Off-Belief Learning (OBL) require deep access to the game simulator's internal logic. This paper seeks a simpler, more scalable way to force agents to rely on "grounded" information—logic derived from the rules of the game rather than arbitrary agreements.

Synchronous K-Level Reasoning

The authors build upon k-level reasoning (KLR). In a standard KLR hierarchy:

  • Level 0 ($\pi_0$): Plays randomly.
  • Level 1 ($\pi_1$): Learns the best response to $\pi_0$.
  • Level $k$ ($\pi_k$): Learns the best response to Level $k-1$.

The paper introduces two critical innovations to this classical framework:

  1. Synchronous Training: Traditionally, KLR is trained sequentially (finish L1, then start L2). The authors found that this causes L2 to "overfit" to the specific quirks of L1. By training all levels simultaneously in parallel, the lower levels are constantly shifting. This acts as a regularizer, forcing higher-level agents to be robust to a distribution of behaviors rather than a single static policy.
  2. SyKLRBR (Synchronous k-level reasoning with a Best Response): They add a final "Best Response" agent trained against the entire hierarchy (weighted toward the top levels). This hybrid approach allows the final agent to adapt on-the-fly to various skill levels.
Comparison of training architectures: Sequential KLR, Synchronous KLR, Synchronous CH, and SyKLRBR.

Key Insights and Results

To test how well the AI plays with humans, the authors used a dataset of over 200,000 games from the Board Game Arena to train a "Clone Bot" as a proxy for human playstyles.

Instability as a Feature: In most RL, we want stable targets. Here, the "instability" of synchronous training is the secret sauce. Because $\pi_{k-1}$ is changing, $\pi_k$ cannot rely on a "secret handshake" because the handshake might mean something different tomorrow. It is forced to rely on the "grounded" logic of the cards.

The "Bomb Out" Metric: The authors found that sequential agents often "bomb out" (lose all lives) when playing with new partners because they take risks assuming their partner understands their secret conventions. Synchronous agents are much more cautious and successful because they don't assume the partner is a mind-reader.

State-of-the-Art Performance: * Human-AI Coordination: SyKLRBR achieved a score of 16.59 when paired with the human-proxy Clone Bot, nearly doubling the performance of the previous leading algorithm, Other-Play (8.55). * Cross-Play Stability: In "Cross-Play" (pairing agents from different training runs), Synchronous KLR maintained a score of ~22.14, whereas Sequential KLR dropped significantly to ~17.17 due to overfitting. * Simplicity: The method matches or exceeds the performance of much more complex, "simulator-heavy" algorithms like OBL using only standard game observations.

Limitations and Future Work

While SyKLRBR is a leap forward, a gap still exists between "Self-Play" scores (where agents know each other perfectly) and "Cross-Play" scores. The agents can still be somewhat brittle when faced with a bot that has a completely alien convention.

The authors suggest that future work should explore different graph structures for the hierarchy—perhaps agents shouldn't just look at the level below them, but a wider variety of "ancestor" policies to further increase robustness. They also suggest investigating how to evaluate agents "off-distribution" during the training process itself to catch potential handshakes before they become ingrained.

Summary updated

Abstract

The standard problem setting in cooperative multi-agent settings is \emph{self-play} (SP), where the goal is to train a \emph{team} of agents that works well together. However, optimal SP policies commonly contain arbitrary conventions (``handshakes'') and are not compatible with other, independently trained agents or humans. This latter desiderata was recently formalized by \cite{Hu2020-OtherPlay} as the \emph{zero-shot coordination} (ZSC) setting and partially addressed with their \emph{Other-Play} (OP) algorithm, which showed improved ZSC and human-AI performance in the card game Hanabi. OP assumes access to the symmetries of the environment and prevents agents from breaking these in a mutually \emph{incompatible} way during training. However, as the authors point out, discovering symmetries for a given environment is a computationally hard problem. Instead, we show that through a simple adaption of k-level reasoning (KLR) \cite{Costa-Gomes2006-K-level}, synchronously training all levels, we can obtain competitive ZSC and ad-hoc teamplay performance in Hanabi, including when paired with a human-like proxy bot. We also introduce a new method, synchronous-k-level reasoning with a best response (SyKLRBR), which further improves performance on our synchronous KLR by co-training a best response.
BibTeX
@inproceedings{cui2021k,
  author = {Brandon Cui and Hengyuan Hu and Luis Pineda and Jakob Nicolaus Foerster},
  title = {{K-level Reasoning for Zero-Shot Coordination in Hanabi}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=Nb03vOtUfz},
}
Figure