# K-level Reasoning for Zero-Shot Coordination in Hanabi

arXiv: https://arxiv.org/abs/2207.07166 · HTML: https://mlsanity.com/paper/2207.07166/

## Key facts

- Cited by 32 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 50 references that are in the map.
- First posted on arXiv 14 Jul 2022.

## Builds on (most cited first, 22 of 22)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Deep Reinforcement Learning with Double Q-learning](https://mlsanity.com/paper/1509.06461/) (2015)
- [Prioritized Experience Replay](https://mlsanity.com/paper/1511.05952/) (2015)
- [Dueling Network Architectures for Deep Reinforcement Learning](https://mlsanity.com/paper/1511.06581/) (2015)
- [QMIX: Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1803.11485/) (2018)
- [Population Based Training of Neural Networks](https://mlsanity.com/paper/1711.09846/) (2017)
- [On the Utility of Learning about Humans for Human-AI Coordination](https://mlsanity.com/paper/1910.05789/) (2019)
- [StarCraft II: A New Challenge for Reinforcement Learning](https://mlsanity.com/paper/1708.04782/) (2017)
- [Distributed Prioritized Experience Replay](https://mlsanity.com/paper/1803.00933/) (2018)
- [A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning](https://mlsanity.com/paper/1711.00832/) (2017)
- [Human-level performance in first-person multiplayer games with population-based deep reinforcement learning](https://mlsanity.com/paper/1807.01281/) (2018)
- [The Complexity of Decentralized Control of Markov Decision Processes](https://mlsanity.com/paper/1301.3836/) (2013)
- ["Other-Play" for Zero-Shot Coordination](https://mlsanity.com/paper/2003.02979/) (2020)
- [The Hanabi Challenge: A New Frontier for AI Research](https://mlsanity.com/paper/1902.00506/) (2019)
- [Off-Belief Learning](https://mlsanity.com/paper/2103.04000/) (2021)
- [Bayesian Action Decoder for Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1811.01458/) (2018)
- [Simplified Action Decoder for Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1912.02288/) (2019)
- [Continuous Coordination As a Realistic Scenario for Lifelong Learning](https://mlsanity.com/paper/2103.03216/) (2021)
- [Pick Your Battles: Interaction Graphs as Population-Level Objectives for Strategic Diversity](https://mlsanity.com/paper/2110.04041/) (2021)
- [Ridge Rider: Finding Diverse Solutions by Following Eigenvectors of the Hessian](https://mlsanity.com/paper/2011.06505/) (2020)
- [Adversarially Guided Self-Play for Adopting Social Conventions](https://mlsanity.com/paper/2001.05994/) (2020)
- [Learned Belief Search: Efficiently Improving Policies in Partially Observable Settings](https://mlsanity.com/paper/2106.09086/) (2021)

## Built on by (most cited first, 30 of 32)

- [Language Instructed Reinforcement Learning for Human-AI Coordination](https://mlsanity.com/paper/2304.07297/) (2023)
- [Mastering the Game of No-Press Diplomacy via Human-Regularized Reinforcement Learning and Planning](https://mlsanity.com/paper/2210.05492/) (2022)
- [LLM-Powered Hierarchical Language Agent for Real-time Human-AI Coordination](https://mlsanity.com/paper/2312.15224/) (2023)
- [Learning Zero-Shot Cooperation with Humans, Assuming Humans Are Biased](https://mlsanity.com/paper/2302.01605/) (2023)
- [PECAN: Leveraging Policy Ensemble for Context-Aware Zero-Shot Human-AI Coordination](https://mlsanity.com/paper/2301.06387/) (2023)
- [Equivariant Networks for Zero-Shot Coordination](https://mlsanity.com/paper/2210.12124/) (2022)
- [Coordination with Humans via Strategy Matching](https://mlsanity.com/paper/2210.15099/) (2022)
- [Learning General World Models in a Handful of Reward-Free Deployments](https://mlsanity.com/paper/2210.12719/) (2022)
- [Seven Security Challenges in Cross-domain Multi-agent LLM Systems](https://mlsanity.com/paper/2505.23847/) (2025)
- [Towards Few-shot Coordination: Revisiting Ad-hoc Teamplay Challenge In the Game of Hanabi](https://mlsanity.com/paper/2308.10284/) (2023)
- [Human-AI Coordination via Human-Regularized Search and Learning](https://mlsanity.com/paper/2210.05125/) (2022)
- [RaidEnv: Exploring New Challenges in Automated Content Balancing for Boss Raid Games](https://mlsanity.com/paper/2307.01676/) (2023)
- [Efficient Human-AI Coordination via Preparatory Language-based Convention](https://mlsanity.com/paper/2311.00416/) (2023)
- [ROTATE: Regret-driven Open-ended Training for Ad Hoc Teamwork](https://mlsanity.com/paper/2505.23686/) (2025)
- [A Generalist Hanabi Agent](https://mlsanity.com/paper/2503.14555/) (2025)
- [Improving Cooperation in Language Games with Bayesian Inference and the Cognitive Hierarchy](https://mlsanity.com/paper/2412.12409/) (2024)
- [Communication-Efficient Desire Alignment for Embodied Agent-Human Adaptation](https://mlsanity.com/paper/2505.22503/) (2025)
- [The Yokai Learning Environment: Tracking Beliefs Over Space and Time](https://mlsanity.com/paper/2508.12480/) (2025)
- [High entropy leads to symmetry-equivariant policies in Dec-POMDPs](https://mlsanity.com/paper/2511.22581/) (2025)
- [Implicitly Aligning Humans and Autonomous Agents through Shared Task Abstractions](https://mlsanity.com/paper/2505.04579/) (2025)
- [Shaping Zero-Shot Coordination via State Blocking](https://mlsanity.com/paper/2605.11688/) (2026)
- [Towards a Unifying Model of Rationality in Multiagent Systems](https://mlsanity.com/paper/2305.18071/) (2023)
- [Strategy Game-Playing with Size-Constrained State Abstraction](https://mlsanity.com/paper/2408.06202/) (2024)
- [K-Level Policy Gradients for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2509.12117/) (2025)
- [Is Inter-Seed Cross-Play Enough? Evaluating the Robustness of Zero-Shot Coordination Algorithms to Implementation Details](https://mlsanity.com/paper/2608.03644/) (2026)
- [Combining a Meta-Policy and Monte-Carlo Planning for Scalable Type-Based Reasoning in Partially Observable Environments](https://mlsanity.com/paper/2306.06067/) (2023)
- [On the Complexity of Learning to Cooperate with Populations of Socially Rational Agents](https://mlsanity.com/paper/2407.00419/) (2024)
- [Noisy Zero-Shot Coordination: Breaking The Common Knowledge Assumption In Zero-Shot Coordination Games](https://mlsanity.com/paper/2411.04976/) (2024)
- [Towards Real-time Adaptation of Embodied Agent in Human-Robot Collaboration](https://mlsanity.com/paper/2412.00435/) (2024)
- [Efficient Reinforcement Learning for Zero-Shot Coordination in Evolving Games](https://mlsanity.com/paper/2511.11083/) (2025)

## Abstract (arXiv)

The standard problem setting in cooperative multi-agent settings is self-play (SP), where the goal is to train a 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 Hu et al. 2020 as the zero-shot coordination (ZSC) setting and partially addressed with their 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 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) Costa Gomes et al. 2006, 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.