Learned Belief Search: Efficiently Improving Policies in Partially Observable Settings

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

22 citations recorded by the source corpus.

Search is an important tool for computing effective policies in single- and multi-agent environments, and has been crucial for achieving superhuman performance in several benchmark fully and partially observable games. However, one major limitation of prior search approaches for partially observable environments is that the computational cost scales poorly with the amount of hidden information. In this paper we present \emph{Learned Belief Search} (LBS), a computationally efficient search procedure for partially observable environments. Rather than maintaining an exact belief distribution, LBS uses an approximate auto-regressive counterfactual belief that is learned as a supervised task. In multi-agent settings, LBS uses a novel public-private model architecture for underlying policies in order to efficiently evaluate these policies during rollouts. In the benchmark domain of Hanabi, LBS can obtain 55% ~ 91% of the benefit of exact search while reducing compute requirements by $35.8 \times$ ~ $4.6 \times$, allowing it to scale to larger settings that were inaccessible to previous search methods.

Subfields: Artificial Intelligence, Management Science and Operations Research, 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 Management Science and Operations Research

In Reinforcement Learning

Citations in the corpus

Off-Belief Learning (2021, methodology): “We use the public-LSTM architecture (Hu et al., 2021) the LSTM sub-network conditions only on the public part of the observation so that the input to the LSTM is consistent across normal transitions and ﬁctitious transitions.”
The Surprising Effectiveness of MAPPO in Cooperative, Multi-Agent Games (2021, background): “(Hu et al., 2021) (2)Reported in communication with authors Figure 3.”