# Improving Policies via Search in Cooperative Partially Observable Games

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

## Key facts

- Cited by 33 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Dec 2019.

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

- [Beyond Autoregression: Fast LLMs via Self-Distillation Through Time](https://mlsanity.com/paper/2410.21035/) (2024)
- [MALT: Improving Reasoning with Multi-Agent LLM Training](https://mlsanity.com/paper/2412.01928/) (2024)
- [DouZero: Mastering DouDizhu with Self-Play Deep Reinforcement Learning](https://mlsanity.com/paper/2106.06135/) (2021)
- [Optimizing Language Models for Inference Time Objectives using Reinforcement Learning](https://mlsanity.com/paper/2503.19595/) (2025)
- [Modeling Strong and Human-Like Gameplay with KL-Regularized Search](https://mlsanity.com/paper/2112.07544/) (2021)
- [Evaluation of Human-AI Teams for Learned and Rule-Based Agents in Hanabi](https://mlsanity.com/paper/2107.07630/) (2021)
- [Communicating Natural Programs to Humans and Machines](https://mlsanity.com/paper/2106.07824/) (2021)
- [Student of Games: A unified learning algorithm for both perfect and imperfect information games](https://mlsanity.com/paper/2112.03178/) (2021)
- [Any-Play: An Intrinsic Augmentation for Zero-Shot Coordination](https://mlsanity.com/paper/2201.12436/) (2022)
- [What is the Solution for State-Adversarial Multi-Agent Reinforcement Learning?](https://mlsanity.com/paper/2212.02705/) (2022)
- [Scalable Online Planning via Reinforcement Learning Fine-Tuning](https://mlsanity.com/paper/2109.15316/) (2021)
- [Solving Common-Payoff Games with Approximate Policy Iteration](https://mlsanity.com/paper/2101.04237/) (2021)
- [PerfectDou: Dominating DouDizhu with Perfect Information Distillation](https://mlsanity.com/paper/2203.16406/) (2022)
- [Learned Belief Search: Efficiently Improving Policies in Partially Observable Settings](https://mlsanity.com/paper/2106.09086/) (2021)
- [Common Information based Approximate State Representations in Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2110.12603/) (2021)
- [Human-AI Coordination via Human-Regularized Search and Learning](https://mlsanity.com/paper/2210.05125/) (2022)
- [Ad-Hoc Human-AI Coordination Challenge](https://mlsanity.com/paper/2506.21490/) (2025)
- [On-the-fly Strategy Adaptation for ad-hoc Agent Coordination](https://mlsanity.com/paper/2203.08015/) (2022)
- [Reinforcement Learning in Practice: Opportunities and Challenges](https://mlsanity.com/paper/2202.11296/) (2022)
- [Abstracting Imperfect Information Away from Two-Player Zero-Sum Games](https://mlsanity.com/paper/2301.09159/) (2023)
- [Generalized Beliefs for Cooperative AI](https://mlsanity.com/paper/2206.12765/) (2022)
- [Partner Modelling Emerges in Recurrent Agents (But Only When It Matters)](https://mlsanity.com/paper/2505.17323/) (2025)
- [Is Vanilla Policy Gradient Overlooked? Analyzing Deep Reinforcement Learning for Hanabi](https://mlsanity.com/paper/2203.11656/) (2022)
- [The Update-Equivalence Framework for Decision-Time Planning](https://mlsanity.com/paper/2304.13138/) (2023)
- [Augmenting the action space with conventions to improve multi-agent cooperation in Hanabi](https://mlsanity.com/paper/2412.06333/) (2024)
- [Self-Explaining Deviations for Coordination](https://mlsanity.com/paper/2207.12322/) (2022)
- [Towards automating Codenames spymasters with deep reinforcement learning](https://mlsanity.com/paper/2212.14104/) (2022)
- [Behavioral Differences is the Key of Ad-hoc Team Cooperation in Multiplayer Games Hanabi](https://mlsanity.com/paper/2303.06775/) (2023)
- [In Pursuit of Predictive Models of Human Preferences Toward AI Teammates](https://mlsanity.com/paper/2503.15516/) (2025)
- [Enabling Rapid Shared Human-AI Mental Model Alignment via the After-Action Review](https://mlsanity.com/paper/2503.19607/) (2025)

## Abstract (arXiv)

Recent superhuman results in games have largely been achieved in a variety of zero-sum settings, such as Go and Poker, in which agents need to compete against others. However, just like humans, real-world AI systems have to coordinate and communicate with other agents in cooperative partially observable environments as well. These settings commonly require participants to both interpret the actions of others and to act in a way that is informative when being interpreted. Those abilities are typically summarized as theory f mind and are seen as crucial for social interactions. In this paper we propose two different search techniques that can be applied to improve an arbitrary agreed-upon policy in a cooperative partially observable game. The first one, single-agent search, effectively converts the problem into a single agent setting by making all but one of the agents play according to the agreed-upon policy. In contrast, in multi-agent search all agents carry out the same common-knowledge search procedure whenever doing so is computationally feasible, and fall back to playing according to the agreed-upon policy otherwise. We prove that these search procedures are theoretically guaranteed to at least maintain the original performance of the agreed-upon policy (up to a bounded approximation error). In the benchmark challenge problem of Hanabi, our search technique greatly improves the performance of every agent we tested and when applied to a policy trained using RL achieves a new state-of-the-art score of 24.61 / 25 in the game, compared to a previous-best of 24.08 / 25.