  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.
