Approximate Inference in Discrete Distributions with Monte Carlo Tree Search and Value Functions
This addresses the challenge of efficient inference in AI and engineering for researchers and practitioners, but it is incremental as it builds on existing reinforcement learning and MCTS techniques.
The paper tackles the problem of approximate inference in discrete probabilistic models under a limited budget of density oracle calls, proposing the TreeSample algorithm which adapts Monte Carlo Tree Search and neural networks to guide the search, and empirically shows it outperforms standard methods on synthetic factor graphs.
A plethora of problems in AI, engineering and the sciences are naturally formalized as inference in discrete probabilistic models. Exact inference is often prohibitively expensive, as it may require evaluating the (unnormalized) target density on its entire domain. Here we consider the setting where only a limited budget of calls to the unnormalized density oracle is available, raising the challenge of where in the domain to allocate these function calls in order to construct a good approximate solution. We formulate this problem as an instance of sequential decision-making under uncertainty and leverage methods from reinforcement learning for probabilistic inference with budget constraints. In particular, we propose the TreeSample algorithm, an adaptation of Monte Carlo Tree Search to approximate inference. This algorithm caches all previous queries to the density oracle in an explicit search tree, and dynamically allocates new queries based on a "best-first" heuristic for exploration, using existing upper confidence bound methods. Our non-parametric inference method can be effectively combined with neural networks that compile approximate conditionals of the target, which are then used to guide the inference search and enable generalization across multiple target distributions. We show empirically that TreeSample outperforms standard approximate inference methods on synthetic factor graphs.