Improving Policies via Search in Cooperative Partially Observable Games

By Adam Lerer, Hengyuan Hu, Jakob N. Foerster, Noam Brown. 2019

88 citations recorded by the source corpus.

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 of 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.

Subfields: Artificial Intelligence, Management Science and Operations Research

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 Management Science and Operations Research

Citations in the corpus

Learned Belief Search: Efficiently Improving Policies in Partially Observable Settings (2021, methodology): “, 2017; Brown & Sandholm, 2017; 2019) and the cooperative game Hanabi (Lerer et al., 2020), as well as large improvements in Bridge (Tian et al.”
"Other-Play" for Zero-Shot Coordination (2020, methodology): “We asked each individual to play a game of Hanabi with two bots, in random order, using the user interface open-sourced by (Lerer et al., 2019).”
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 [30, 6, 7], Hanabi [17, 28], general EFGs [47, 29, 12], Dec-POMDPs [45, 50], and one-sided POSGs [20].”
Joint Policy Search for Multi-agent Collaboration with Imperfect Information (2020, background): “Recently, [24] shows strong performance in Hanabi using collaborative search with a pre-defined common blueprint policy.”