Bayesian Action Decoder for Deep Multi-Agent Reinforcement Learning

By Jakob N. Foerster, H. Francis Song, Edward Hughes, Neil Burch, Iain Dunning, Shimon Whiteson, Matthew Botvinick, Michael H. Bowling. 2018

170 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Biomedical Engineering, Reinforcement Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Biomedical Engineering

In Reinforcement Learning

Citations in the corpus

OpenSpiel: A Framework for Reinforcement Learning in Games (2019, neutral): “Game Reference(s) Backgammon Wikipedia Breakthrough Wikipedia Bridge bidding Wikipedia Catch [51] and [59, Appendix A] Coin Game [64] Connect Four Wikipedia Cooperative Box-Pushing [70] Chess Wikipedia First-price Sealed-bid Auction Wikipedia Go Wikipedia Goofspiel Wikipedia Hanabi (via HLE) Wikiped”
Continuous Coordination As a Realistic Scenario for Lifelong Learning (2021, background): “In recent years, there has been rapid progress on novel MARL algorithms that are based on centralized training with decentralized execution (Self-Play) as a training paradigm (Sunehag et al., 2017; Foerster et al., 2017; Hong et al., 2017; Foerster et al., 2019; Hu & Foerster, 2019).”
Learned Belief Search: Efficiently Improving Policies in Partially Observable Settings (2021, methodology): “Inspired by other public-private methods (Foerster et al., 2019; Kovaˇr´ık et al., 2019; Hor´ak & Boˇsansk`y, 2019), we exploit that the public trajectory in combination with the current private observation contains the same information as the entire private trajectory and only feed the public…”
Simplified Action Decoder for Deep Multi-Agent Reinforcement Learning (2019, methodology): “While not making the above argument explicitly, the Bayesian Action Decoder (BAD) (Foerster et al., 2019), resolves this issue by shifting exploration to the level of deterministic partial policies, rather than action-level, and tracking an approximate Bayesian belief.”
The Hanabi Challenge: A New Frontier for AI Research (2019, methodology): “DeepStack) introduced function approximators that represent belief-conditional values and explicitly representing and reasoning about manipulating agents’ beliefs [13], similar to the approach of BAD [38]. 21 6. Conclusion The combination of cooperative gameplay and imperfect information make Hanabi”
"Other-Play" for Zero-Shot Coordination (2020, methodology): “In particular, because OP is a modi-ﬁcation of the SP algorithm, it can be combined with many of the algorithmic innovations that have been developed to improve SP in various games (Lanctot et al., 2017; Foerster et al., 2018a; Lowe et al., 2017; Foerster et al., 2017).”
On the Utility of Learning about Humans for Human-AI Coordination (2019, methodology): “For instance, agents trained to play the collaborative game Hanabi learned to use the hint “red” or “yellow” to indicate that the newest card is playable, which no human would immediately understand [12].”
Rethinking Formal Models of Partially Observable Multiagent Decision Making (2019, background): “Indeed, we have recently seen breakthroughs in a number of problems that were made computationally feasible by decomposition based on public knowledge — examples include poker [28, 4, 5], Hanabi [15, 26], general EFGs [41, 27, 10], Dec-POMDPs [40, 44], and one-sided POSGs [18].”
Joint Policy Search for Multi-agent Collaboration with Imperfect Information (2020, methodology): “Note that this is quite surprising since the original solutions obtained from BAD are not great but JPS can boost them substantially.”
Promoting Coordination through Policy Regularization in Multi-Agent Deep Reinforcement Learning (2019, methodology): “A popular framework for MARL is the use of a Centralized Training and a Decentralized Execution (CTDE) procedure [24, 8, 14, 7, 28].”
Diverse Agents for Ad-Hoc Cooperation in Hanabi (2019, methodology): “…a pool of very high-performing self-play agents with sophisticated conventions (such as the ones developed in [20], [21] or learned by Reinforcement Learning in [8], [18]) might resemble more a puzzle-solving challenge where the exact convention in use must be identiﬁed to achieve good performance.”
Deep Reinforcement Learning for Multiagent Systems: A Review of Challenges, Solutions, and Applications (2018, background): “[65] proposed a Bayesian action decoder (BAD) algorithm for learning multiple agents with cooperative partial observable settings.”
Re-determinizing Information Set Monte Carlo Tree Search in Hanabi (2019, methodology): “2018 [30] use Deep Reinforcement Learning to learn conventions”
Learning to Communicate Implicitly by Actions (2018, methodology): “The recent work of (Foerster et al. 2018) solves an imperfect information problem as considered here from a different angle.”
On the link between conscious function and general intelligence in humans and machines (2022, background): “While multi-agent research is a large ﬁeld (Albrecht & Stone, 2018), systems which try to explicitly model the policies of other agents (Rabinowitz et al., 2018; Foerster et al., 2019) could be an important step towards the developments of agents with models of themselves as well.”
Multi-agent deep reinforcement learning: a survey (2021, methodology): “Foerster et al. (2019) used all publicly available observations in the environment to calculate a public belief over agents’ local information.”