Source-linked AI summary
Bayesian Action Decoder for Deep Multi-Agent Reinforcement Learning
Jakob N. Foerster, Francis Song, Edward Hughes, Neil Burch, Iain Dunning, Shimon Whiteson, Matthew Botvinick, Michael Bowling
TL;DR
Cooperative partially observable multi-agent RL still struggles to discover effective communication protocols and conventions, especially when actions themselves convey information. BAD uses a public-belief MDP with deterministic partial policies and approximate Bayesian updates, achieving state-of-the-art two-player Hanabi performance while reducing uncertainty about private hands by around 40%.
Problem
Cooperative partially observable multi-agent RL must discover communication protocols and conventions, while existing methods often rely on cheap-talk channels that do not apply when communication actions affect the environment.
Method
BAD uses an approximate Bayesian update to compute a public belief over private features and selects deterministic partial policies that map private observations to environment actions.
Results
24.174 points: BAD achieved state-of-the-art mean performance in two-player Hanabi and surpassed previously published learning-agent results by around 9 points.
Takeaways & Limitations
BAD demonstrates that Bayesian reasoning over public beliefs can support informative actions, convention discovery, and scalable learning in cooperative partially observable settings.
Takeaways & Limitations
Factorised beliefs are only approximate and can be inconsistent because private features such as card holdings interact.
Abstract
from arXiv · showhide
When observing the actions of others, humans make inferences about why they acted as they did, and what this implies about the world; humans also use the fact that their actions will be interpreted in this manner, allowing them to act informatively and thereby communicate efficiently with others. Although learning algorithms have recently achieved superhuman performance in a number of two-player, zero-sum games, scalable multi-agent reinforcement learning algorithms that can discover effective strategies and conventions in complex, partially observable settings have proven elusive. We present the Bayesian action decoder (BAD), a new multi-agent learning method that uses an approximate Bayesian update to obtain a public belief that conditions on the actions taken by all agents in the environment. BAD introduces a new Markov decision process, the public belief MDP, in which the action space consists of all deterministic partial policies, and exploits the fact that an agent acting only on this public belief state can still learn to use its private information if the action space is augmented to be over all partial policies mapping private information into environment actions. The Bayesian update is closely related to the theory of mind reasoning that humans carry out when observing others' actions. We first validate BAD on a proof-of-principle two-step matrix game, where it outperforms policy gradient methods; we then evaluate BAD on the challenging, cooperative partial-information card game Hanabi, where, in the two-player setting, it surpasses all previously published learning and hand-coded approaches, establishing a new state of the art.
1. Introduction
Cooperative partially observable multi-agent RL must discover communication protocols and conventions, but many existing methods target cheap-talk channels and miss the information conveyed by actions themselves. BAD addresses this with a public-belief MDP and Bayesian action decoding, outperforming policy-gradient methods on a toy game and reaching state-of-the-art two-player Hanabi performance.
- Cooperative partially observable multi-agent RL requires agents to discover communication protocols while learning policies.
- Existing communication methods mainly backpropagate through cheap-talk channels, limiting their applicability when communication actions affect the environment.
- Actions carry information about agents’ private states beyond the state transitions they induce, supporting convention formation in Hanabi.
- BAD computes a public belief over private features and defines a public belief MDP whose actions are deterministic partial policies mapping private observations to environment actions.
- 24.174 points: BAD surpassed previously published learning-agent results by around 9 points in two-player Hanabi and approached 24.9-point open-hand gameplay.
- BAD outperformed policy-gradient methods on a proof-of-principle two-step matrix game.
2. Background and Setting
The setting is a cooperative, partially observable multi-agent environment in which agents share public features but observe different private features. Policies are trained centrally but executed decentrally, with recurrent networks commonly used to summarize action-observation histories.
- Agents act in a partially observable environment with public features shared by all agents and private features visible to at least one agent.
- The environment transitions from the current state according to the joint action and provides a cooperative per-timestep team reward.
- Centralised training is allowed, but execution must be decentralised, and the agents’ policies are known to all agents.
- Multi-agent RL seeks policies that maximise expected episode return, while deep RL commonly uses recurrent networks to encode action-observation histories.
- The formalism assumes a turn-based setting in which one agent acts per step.
3. Method
BAD replaces recursive reasoning about nested agent beliefs with a public belief over private features and acts through deterministic partial policies. Factorised approximate beliefs make the approach tractable in large spaces, while iterative re-marginalisation improves self-consistency when feature interactions matter.
- Exact beliefs over hidden multi-agent states can be intractable, while recursive interactive-POMDP reasoning over nested beliefs is often computationally infeasible.
- BAD maintains a public belief: a posterior over private features conditioned only on publicly available features, so every agent can compute the same belief.
- Sampling deterministic policies supports both low-entropy communication and exploration without relying on high-entropy policy actions.
- The public belief MDP state combines the public observation and belief, while each action is a deterministic partial policy mapping private observations to environment actions.
- Factorising the policy distribution reduces dependence on the number of possible private observations from exponential to linear under the stated independence restriction.
- Factorised beliefs approximate per-feature distributions and assume independence, making otherwise intractable card-game state spaces representable and learnable by sampling likelihood terms.
- Factorisation can produce inconsistent beliefs because private features interact, so BAD iteratively re-marginalises features to improve self-consistency and stops after a fixed number of iterations.
4. Experiments and Results
BAD outperforms policy-gradient baselines in a two-step matrix game and achieves state-of-the-art two-player Hanabi performance. Its Bayesian and counterfactual beliefs support conventions that convey substantial information beyond grounded card information.
- Matrix game: The two-step matrix game requires informative actions and conventions for optimal reward because Player 2 observes Player 1’s action before acting.The game gives each player a private card and uses a payoff tensor over cards and actions.
- Matrix game: BAD outperforms vanilla policy gradient on the matrix-like game, with and without counterfactual gradients.The comparison averages results over 1000 games, with shaded standard errors of the mean.
- Matrix game: Additional improvement from counterfactual gradients is minor compared with the initial gain from using a counterfactual belief state.This comparison is made in the small exact matrix-game setting.
- Hanabi beliefs: The V0 belief uses public card counts and hint masks, while V1 iteratively accounts for interactions between hints across slots.V1 updates candidate counts using beliefs about cards held across other slots.
- Hanabi beliefs: The final V2 belief interpolates Bayesian and V1 beliefs with α = 0.01, using 3,000 sampled hands during training and 20,000 during final testing.The authors also report that α = 0.1 worked.
- Hanabi results: BAD achieves a mean score of 24.174 in two-player Hanabi, surpassing previously published learning results by around 9 points and establishing state-of-the-art performance.Under strict error-token scoring, the same agent achieves 23.917 ± 0.009 s.e.m.
- Hanabi results: BAD’s learned conventions include using red or yellow hints to signal that the newest card is playable, followed by playing that card in over 80% of cases.Hinting white or blue is followed by discarding the newest card in over 25% of cases.
- Hanabi results: Counterfactual beliefs produce a much greater reduction in per-card cross entropy than the iterated belief update, and roughly 40% of information comes through conventions.The remaining information comes from grounded information and card counting.
5. Related Work
Prior work includes cheap-talk communication methods, hand-coded and search-based Hanabi agents, and belief-state methods for poker. BAD differs by targeting grounded communication in cooperative partial-information settings and by using approximate Bayesian beliefs with learned policies.
- Communication methods: Many emergent-communication methods use differentiable cheap-talk channels, whereas this work studies communication through grounded hinting actions and observable environment events.Cheap-talk channels can be modeled as continuous variables during training.
- Hanabi methods: Earlier Hanabi approaches include encoding schemes, Monte Carlo tree search, and rule-based methods, with reported performance below BAD’s two-player result.The cited encoding approach achieves 17.8 points in the two-player setting.
- Hanabi methods: FireFlower was the best reported two-player Hanabi result found by the authors, averaging 23.37 points and 52.6% perfect games as a hand-coded bot.Its performance is compared with learning-based BAD elsewhere in the paper.
- Belief-state methods: Continual re-solving also uses belief states and Bayesian updates, but targets two-player zero-sum games with exact belief updates and value-based training.Unlike BAD, it requires a joint policy space small enough to enumerate.
6. Conclusion and Future Work
BAD uses an approximate, factorised belief state to learn informative actions and conventions in cooperative partially observable settings. It outperforms policy gradients in a matrix game and reaches state-of-the-art Hanabi performance, while future work targets broader settings and more learnable components.
- Conclusion: BAD uses a factorised approximate belief state to learn informative actions and discover conventions.The method explicitly computes beliefs rather than relying only on implicit beliefs.
- Conclusion: BAD outperforms policy gradients in a proof-of-principle matrix game and achieves 24.174 average points in Hanabi.The Hanabi result is reported as state-of-the-art performance.
- Conclusion: Around 40% reduction in uncertainty across Hanabi private hands follows from using the Bayesian update.This result concerns uncertainty reduction in the private-hand beliefs.
- Future Work: Future work will apply BAD to games with more players and learn more components, including the V0-belief.The authors also plan extensions to value-based methods and collaboration with human players.
A. Parameterising and Sampling from the Distribution over Partial Policies
BAD parameterises a distribution over deterministic partial policies from public belief states. A shared random seed converts action distributions into samples of complete deterministic partial policies.
- Parameterising Policies: BAD represents a probability distribution over partial policies using a deep neural network.The network maps public states into probabilistic partial policies.
- Parameterising Policies: Fixing a public belief state yields a probabilistic partial policy mapping each private observation to action probabilities.This partial policy is produced deterministically from the public state through network parameters.
- Sampling Policies: BAD requires a differentiable distribution over deterministic partial policies rather than a deterministic map to probabilistic policies.This distinction lets the agent sample policies while retaining differentiability.
- Sampling Policies: Conditioning action sampling on a common random seed effectively samples an entire deterministic partial policy.The seed is shared knowledge across the relevant action choices.
B. Hyperparameters and Training Details
The implementation combines MLPs, LSTMs, masked actions, and population-based training across BAD and baseline agents. Training uses specified optimisers, sampled hyperparameters, and Hanabi-specific belief-sampling settings.
- Training Details: The toy matrix game used batch size 32 and Adam with default TensorFlow settings without hyperparameter tuning.These settings applied to all runs in that experiment.
- Architectures: V0-LSTM and V1-LSTM BAD agents used a 256-unit MLP followed by a two-layer 256-unit LSTM.The policy used a softmax readout, while the baseline incorporated the agent’s own hand during centralised training.
- Architectures: The Hanabi BAD agent used two 384-unit MLP hidden layers, with the policy input masking the agent’s own hand.The baseline included that hand in its input.
- Optimisation: Illegal actions were masked before sampling, and Hanabi used RMSProp with ε = 10^-10, zero momentum, and decay 0.99.Learning rates and entropy regularisation were sampled from separate ranges for LSTM and BAD agents.
- Hanabi Training: Hanabi BAD training used 100 self-consistent iterations, γ_BAD = 1, 3000 sampled hands, and acceptance of the first 3000 legal hands.Five times as many hands were sampled to handle deck-incompatible combinations.
C. Self-Consistent Belief Approximation for Hanabi
The Hanabi belief approximation represents public information with card counts and hint constraints, then updates per-card beliefs iteratively. It averages over sampled hands before normalising, making the computation approximate but tractable.
- Belief Representation: The public Hanabi feature vector contains remaining-card counts and a binary hint mask over possible cards in each slot.The hint mask records which cards remain compatible with the hints received.
- Belief Update: The basic per-card belief is normalised so probabilities across possible card values sum to one.β_i denotes the normalisation factor.
- Iterative Update: Conditioning on other cards reduces the candidate counts before applying the iterative belief update.The update uses M(f[i]) = HM(f[i]) × L(f[i]) as a notational shorthand.
- Factorisation: The factorised belief assumption decomposes the belief across card features for tractable computation.The derivation then uses product-sum rules to simplify the expression.
- Approximation: Averaging across sampled hands before normalising is approximate but tractable, unlike normalising before averaging, which is exact but intractable.This ordering is the central approximation in the self-consistent belief update.
D. Anecdotal Analysis
The section introduces anecdotal commentary from FireFlower’s creator about conventions discovered by the BAD agent. The authors frame this commentary as suggestive rather than systematic evidence.
- David Wu, creator of the FireFlower bot, provides commentary on the BAD agent’s gameplay.The comments are presented verbatim from an email exchange.
- The authors describe the commentary as anecdotal evidence offering insight into the gameplay BAD discovers.
D.1. Communicating Playables
BAD develops conventions that communicate playable cards through hint choices, target-card selection, and ordering patterns. These conventions can encode multiple plays and delayed playability information.
- Communicating Playables: BAD also uses direct hints to the newest card to indicate playability, including both color and number hints.
- Communicating Playables: When a hint identifies multiple playable cards, conventions often specify an ordering, with R/Y hints tending newest-to-oldest and direct hints tending oldest-to-newest.The observed ordering was not fully consistent, and the sample was insufficient to determine precise rules.
- Communicating Playables: Direct hints to older cards can communicate that those cards are one step from playable, allowing later belief updates to support play without another suggestion.
- Communicating Playables: R and Y hints can simultaneously communicate the newest card’s playability and additional or delayed plays elsewhere in the hand.Other conventions include varying ordering for delayed hints and occasionally singling out an unhinted card as playable.
D.2. Communicating Protection
BAD’s conventions communicate protection, discard preferences, and additional card information through actions and hints. The commentary also identifies strong gameplay patterns alongside occasional tactical and endgame weaknesses.
- Communicating Protection: G hints that miss the first card appear to signal that the newest card is dangerous and should not be discarded.The examples may specifically involve 5s, but the commentary leaves that interpretation uncertain.
- Communicating Protection: The bot defaults to discarding its newest card but protects a dangerous newest card, such as a 5 or last remaining copy, with multiple hint types.Failure to protect can lead the partner to infer that the newest card is safe.
- Communicating Protection: Protection is not urgent when the player has a common-knowledge-safe discard, because the bot prefers discarding that card instead.Consequently, a partner cannot always infer that the newest card is safe from delayed protection.
- Communicating Protection: The bot’s conventions attach incidental information to actions, including hints or discards that imply properties of another player’s card.Such extra information is usually limited because excessive attached conventions would constrain frequent play and discard actions.
- Communicating Protection: The bot is described as highly effective at early-game conventions and tracking inferred card information over time.By midgame, both players often know nearly all relevant information about their hands.
- Communicating Protection: The commentary identifies occasional tactical weakness near zero hints and slight endgame mistakes.Examples include unnecessary discards or hints when direct play was apparently available, though some explanations remain speculative.