# Learned Belief Search: Efficiently Improving Policies in Partially Observable Settings

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 29 references that are in the map.
- First posted on arXiv 16 Jun 2021.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model](https://mlsanity.com/paper/1911.08265/) (2019)
- [Dueling Network Architectures for Deep Reinforcement Learning](https://mlsanity.com/paper/1511.06581/) (2015)
- [Deep Recurrent Q-Learning for Partially Observable MDPs](https://mlsanity.com/paper/1507.06527/) (2015)
- [DeepStack: Expert-Level Artificial Intelligence in No-Limit Poker](https://mlsanity.com/paper/1701.01724/) (2017)
- ["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)
- [Online Planning Algorithms for POMDPs](https://mlsanity.com/paper/1401.3436/) (2014)
- [Rethinking Formal Models of Partially Observable Multiagent Decision Making](https://mlsanity.com/paper/1906.11110/) (2019)
- [Improving Policies via Search in Cooperative Partially Observable Games](https://mlsanity.com/paper/1912.02318/) (2019)
- [Diverse Agents for Ad-Hoc Cooperation in Hanabi](https://mlsanity.com/paper/1907.03840/) (2019)
- [Joint Policy Search for Multi-agent Collaboration with Imperfect Information](https://mlsanity.com/paper/2008.06495/) (2020)
- [Evaluating and Modelling Hanabi-Playing Agents](https://mlsanity.com/paper/1704.07069/) (2017)

## Built on by (most cited first, 10 of 10)

- [Modeling Strong and Human-Like Gameplay with KL-Regularized Search](https://mlsanity.com/paper/2112.07544/) (2021)
- [K-level Reasoning for Zero-Shot Coordination in Hanabi](https://mlsanity.com/paper/2207.07166/) (2022)
- [Scalable Online Planning via Reinforcement Learning Fine-Tuning](https://mlsanity.com/paper/2109.15316/) (2021)
- [AssistanceZero: Scalably Solving Assistance Games](https://mlsanity.com/paper/2504.07091/) (2025)
- [Learning Robust Real-Time Cultural Transmission without Human Data](https://mlsanity.com/paper/2203.00715/) (2022)
- [Human-AI Coordination via Human-Regularized Search and Learning](https://mlsanity.com/paper/2210.05125/) (2022)
- [Generalized Beliefs for Cooperative AI](https://mlsanity.com/paper/2206.12765/) (2022)
- [The Update-Equivalence Framework for Decision-Time Planning](https://mlsanity.com/paper/2304.13138/) (2023)
- [GlobeDiff: State Diffusion Process for Partial Observability in Multi-Agent Systems](https://mlsanity.com/paper/2602.15776/) (2026)
- [Reinforcement Learning on Human Decision Models for Uniquely Collaborative AI Teammates](https://mlsanity.com/paper/2111.09800/) (2021)

## Abstract (arXiv)

Search is an important tool for computing effective policies in single- and multi-agent environments, and has been crucial for achieving superhuman performance in several benchmark fully and partially observable games. However, one major limitation of prior search approaches for partially observable environments is that the computational cost scales poorly with the amount of hidden information. In this paper we present Learned Belief Search (LBS), a computationally efficient search procedure for partially observable environments. Rather than maintaining an exact belief distribution, LBS uses an approximate auto-regressive counterfactual belief that is learned as a supervised task. In multi-agent settings, LBS uses a novel public-private model architecture for underlying policies in order to efficiently evaluate these policies during rollouts. In the benchmark domain of Hanabi, LBS can obtain 55% ~ 91% of the benefit of exact search while reducing compute requirements by 35.8 × ~ 4.6 ×, allowing it to scale to larger settings that were inaccessible to previous search methods.