Learned Belief Search: Efficiently Improving Policies in Partially Observable Settings
This addresses a bottleneck in scaling search methods for partially observable games, enabling applications in larger settings previously inaccessible.
The paper tackles the computational inefficiency of search in partially observable environments by introducing Learned Belief Search (LBS), which uses an approximate auto-regressive counterfactual belief to reduce compute requirements by 35.8x to 4.6x while achieving 55% to 91% of the benefit of exact search in Hanabi.
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.