Source-linked AI summary
Improving Policies via Search in Cooperative Partially Observable Games
Adam Lerer, Hengyuan Hu, Jakob Foerster, Noam Brown
TL;DR
Cooperative partially observable games require agents to interpret partners’ actions and coordinate around limited communication. The paper proposes single- and multi-agent search around an agreed-upon blueprint policy, with a fallback when belief computation is too expensive. In Hanabi, search improves every tested policy and sets a new two-player score record, while the paper proves a bounded expected-value guarantee.
Problem
In cooperative partially observable environments with limited communication, agents must infer partners’ behavior and account for how their own actions affect others.
Source: Introduction · p. 1Method
SPARTA applies single-agent search against a shared blueprint or common-knowledge multi-agent search, using retrospective belief updates to fall back to the blueprint when needed.
Source: Introduction · p. 1, Retrospective Belief Updates · p. 4Results
24.61 / 25 on 2-player Hanabi versus the previous-best 24.08 / 25; search improved every tested policy and cannot lower expected value beyond an error that shrinks with more Monte Carlo rollouts.
Source: Introduction · p. 2, Conclusions · p. 7Takeaways & Limitations
The approaches improve arbitrary blueprint policies while retaining a theoretical expected-value guarantee up to an error that decreases with more Monte Carlo rollouts.
Source: Conclusions · pp. 6–7If multiple agents independently search while assuming others follow the blueprint, policy improvement is not guaranteed and empirical performance is poor.
Source: Single-Agent Search · p. 3
Abstract
from arXiv · showhide
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.
Introduction
The paper brings search to cooperative partially observable games by improving an agreed-upon blueprint policy. It presents single- and multi-agent approaches, motivated by how people infer partners’ behavior while choosing actions.
Introduction
- Human coordination motivates the approach: people infer why partners acted and how their own actions may shape partners’ future behavior, then search for a good action.Hanabi is presented as a setting where people start with a convention and individually search assuming partners will follow it.Source: Introduction · pp. 1–2
- Single-agent search assumes other agents follow the blueprint, while multi-agent search simulates their search and can fall back to the blueprint when belief computation is too expensive.Retrospective belief updates enable the fallback and can reduce computation while preserving multi-agent search in most situations.Source: Introduction · p. 1
- SPARTA improves performance from blueprint to single-agent to multi-agent search, with increased computation, and its expected value is no lower than the blueprint’s except for an error that decays with more Monte Carlo rollouts.The introduction states both the empirical progression and the theoretical guarantee.Source: Introduction · p. 1
Related Work
- Search has advanced competitive zero-sum games, including chess, Go, and poker; belief-based search was key to professional-level poker performance.The paper positions its approach as most similar to the search used by the poker bot Pluribus, which searches with presumed agent beliefs and blueprint policies.Source: Related Work · p. 2
- Hanabi research includes handcrafted convention bots, information-theoretic hat-coding, reinforcement learning, and ad-hoc play evaluated against varied teammates.The Simplified Action Decoder established the most recent state of the art among learned Hanabi policies (Hu and Foerster 2020).Source: Related Work · p. 2
Background
- The framework models a cooperative Dec-POMDP in which agents condition policies on action-observation histories and seek to maximize expected return, assuming a common-knowledge deterministic blueprint.The paper represents uncertainty explicitly with beliefs over possible trajectories.Source: Background · pp. 2–3
Method
SPARTA searches over an agreed blueprint in cooperative partially observable games, either with one designated searcher or coordinated agents. Retrospective updates defer expensive range-search, while a theorem bounds search’s expected-value loss against the blueprint by an error that shrinks with rollout count.
Single-Agent Search
- Single-agent search treats the fixed, common-knowledge blueprint of all other agents as part of the environment and uses beliefs and rollouts to choose its next action.The experiments use 1-ply search: after the selected action, all agents follow the blueprint for the rest of the game.Source: Single-Agent Search · p. 3
Multi-Agent Search
- Agents replicate the acting agent’s search across plausible AOHs so resulting policies remain consistent; if the AOH range exceeds MR, the acting agent follows the blueprint.Range-search can be infeasible when the range approaches 10 million AOHs, and multi-agent search may run on fewer turns than single-agent search.Source: Multi-Agent Search · pp. 3–4
Retrospective Belief Updates
- Retrospective updates delay range-search until later observations shrink an earlier AOH range, enabling search on 86.0% of two-player Hanabi timesteps at MR = 10,000.Agents follow the blueprint until earlier ranges are resolved; at MR = 0, the method is identical to single-agent search.Source: Retrospective Belief Updates · p. 4
Soundness and Convergence Bound for Search
- Vπs − Vπb ≥ −2T∆|A|N^-1/2: Theorem 1 bounds search’s expected-value loss against the blueprint under bounded rewards and game length.The error term decreases with the number of Monte Carlo rollouts N.Source: Soundness and Convergence Bound for… · pp. 4–5
Experimental Setup
Experiments evaluate SPARTA in Hanabi self-play using handcrafted, reinforcement-learning, and search-imitation blueprint agents. The section also describes Hanabi belief construction, rollout reduction, and imitation-based bootstrapping.
Experimental Setup
- Hanabi experiments focus on self-play and compare handcrafted WTFWThat and SmartBot with RLBot and CloneBot blueprint strategies.RLBot is generated with deep reinforcement learning; CloneBot is generated by imitation learning on single-agent search over SmartBot.Source: Experimental Setup · p. 5
Implementing SPARTA for Hanabi
- Hanabi beliefs are distributions over possible hands, updated using card counts and hints; search samples states from beliefs and compares rollout values for legal actions.Public beliefs in two-player Hanabi factor into independent hand distributions; private beliefs adjust card counts for privately observed cards.Source: Implementing SPARTA for Hanabi · p. 5, Figure 1 · p. 6
Estimating Action Expected Values via UCB
- 10× fewer rollouts per timestep: UCB skips actions outside two standard deviations after 100 samples per action, while a threshold can retain the blueprint action.The deviation threshold in the experiments is 0.05.Source: Estimating Action Expected Values via… · p. 5
Bootstrapping Search-Based Policies via Imitation Learning
- CloneBot is trained by imitation learning on single-agent search over SmartBot, approximating search’s effect with a policy that is cheaper to execute.Repeated search-and-learning could extend search benefits, but the process is not guaranteed to converge to an optimal policy, even with perfect function approximation.Source: Bootstrapping Search-Based Policies… · p. 5
Results
SPARTA improves Hanabi performance, reaching a new two-player state-of-the-art score; broader multi-agent search increases coverage but requires substantially more rollouts. Search predictions also rise over the course of a game.
Results
- 24.61 / 25 is the new two-player Hanabi state of the art, versus the previous best of 24.08 / 25.Much of the improvement comes from single-agent search, with a further substantial improvement from multi-agent search.Source: Results · p. 6
- Single-agent search improves state-of-the-art scores in 3-, 4-, and 5-player Hanabi; multi-agent search becomes more expensive as player count grows.The strongest agent achieves perfect scores 75.5% of the time in two-player Hanabi, while reliable top-human statistics are unavailable.Source: Results · p. 6
- A perfect score is impossible for some deck shuffles, and the highest possible average score is unknown.Source: Results · p. 6
- As max range increases, search is conducted more often; multi-agent search runs on 86% of timesteps, although two-player Hanabi’s maximum possible timestep range is nearly 10 million, and requires about 1,000× as many rollouts as single-agent search.Source: Results · p. 6
- Across game turns, predicted expected scores start at the blueprint score and increase monotonically as search is applied at each move.Figure 2 plots average MC search predictions for two blueprints; error bars are too small to see.Source: Results · p. 6, Figure 2 · p. 6
Conclusions
The conclusions report improved Hanabi performance and a rollout-dependent guarantee against underperforming the blueprint, subject to computational costs and a perfect-model assumption.
Conclusions
- SPARTA uses about 2 × 10^6 policy evaluations per game, roughly 4 × 10^4 games’ worth of evaluations, with cost dominated by search rollouts.Source: Conclusions · p. 6
- SPARTA reaches 24.61 / 25 in two-player Hanabi versus the previous best of 24.08 / 25, and its expected-reward guarantee has an error term that shrinks with more MC rollouts.The guarantee is relative to the blueprint policy; Table 1 reports monotonic performance improvements with single-agent and multi-agent search.Source: Conclusions · p. 7, Table 1 · p. 7
- Hanabi belief tracking involves up to 10 million probabilities, and rollout needs scale with belief-space size, leaving larger partially observable instances as a challenge.Source: Conclusions · p. 7
- The approach assumes perfect knowledge of other agents’ policies; the paper identifies imperfect partner models and robustness to their errors as future work.The authors describe the assumption as reasonable in centralized-planning, decentralized-execution settings such as company-created self-driving cars or factory teams.Source: Conclusions · p. 7
Search Algorithm Listing
The listings describe single-agent search over beliefs and a retrospective multi-agent procedure that tracks common-knowledge beliefs and selects when search is allowed.
Search Algorithm Listing
- Single-agent search samples a belief state, evaluates candidate actions with policy rollouts, and returns the action with the highest accumulated score.Source: Search Algorithm Listing · p. 10
- The multi-agent listing initializes common-knowledge beliefs and tracks the current searcher and actions awaiting belief updates during play.Source: Search Algorithm Listing · p. 11
- The single-agent listing observes the environment and whose turn it is, then updates the agent’s beliefs before selecting a move.Source: Search Algorithm Listing · pp. 10–11
Learning
The RL blueprint uses an Ape-X DQN implementation trained on the Hanabi Learning Environment, with customized actor execution and input features.
Learning
- The RL baseline is an Ape-X DQN implementation on the Hanabi Learning Environment, using asynchronous actors, prioritized replay, and a centralized learner.Source: Learning · p. 12
- The implementation uses 80 actors, each batching 20 environments on GPU, instead of the original paper’s 360 single-environment CPU actors.Actors synchronize with the learner every 10 mini-batches rather than every 400 environment steps.Source: Learning · p. 12
- The agent replaces HLE’s card-knowledge input with V0-Belief and uses a three-layer, 512-neuron network with value and advantage output streams.Training uses batches of 512 transitions, discount factor 0.999, and Adam with learning rate 6.25 × 10^-5.Source: Learning · p. 12
Applied to Search
The authors distill single-agent-search behavior into a supervised policy trained on search-generated examples. Its objective favors high-value actions while retaining the blueprint action as an inference-time input.
- Training examples pair AOHs with actions from 1.3 million games where single-agent search was applied to the SmartBot blueprint.Source: Applied to Search · p. 12
- The 2-layer, 128-unit LSTM receives both the AOH and blueprint action; the action input is crucial and presumably helps the model fall back to the blueprint.Source: Applied to Search · p. 12
- The clone outputs a softmax policy trained to maximize expected reward under action Q-values, then selects its highest-probability action at test time.Source: Applied to Search · p. 12
- This objective produced a stronger agent than either direct Q-value prediction with MSE loss or action prediction with cross-entropy loss.Source: Applied to Search · p. 12
Additional Results
Additional experiments examine search-threshold and pruning choices, independent multi-agent search, and search over a hard-coded hat-counting policy. Search improves the latter policy across 3-, 4-, and 5-player Hanabi.
- A blueprint-deviation threshold of 0.05 improves total score even with many rollouts, while UCB pruning reduces rollouts per turn without affecting average score.Source: Additional Results · p. 12
- Independent joint search sweeps partner-strategy uncertainty and deviation thresholds; some settings beat the blueprint (22.99), but none outperform single-agent search.Source: Additional Results · pp. 12–13, Table 4 · p. 13
- Single-agent search improves the WTFWThat hat-counting policy and yields state-of-the-art results in 3-, 4-, and 5-player Hanabi.The policy is hard-coded and does not use grounded information.Source: Additional Results · p. 13, Table 5 · p. 13
Proof of Main Theorem
The proof analyzes Monte Carlo search from an agent’s trajectory beliefs, with other agents following the blueprint after the candidate action. It bounds rollout-estimation errors and uses induction over the search horizon.
- From its trajectory belief, the agent takes N/|A| independent reward rollouts per action, assuming blueprint play thereafter, and selects the action with the largest estimated Q-value.Source: Proof of Main Theorem · p. 14
- The proof compares the selected action’s true value with its rollout estimate and the blueprint action’s value to bound their difference.Source: Proof of Main Theorem · p. 14
- Bounded rewards yield subgaussian rollout errors, which concentration results control; induction over time extends the argument through the bounded game horizon.Source: Proof of Main Theorem · pp. 14–15