A^* sampling with probability matching

Abstract

Probabilistic methods often need to draw samples from a nontrivial distribution. A^* sampling is a nice algorithm by building upon a top-down construction of a Gumbel process, where a large state space is divided into subsets and at each round A^* sampling selects a subset to process. However, the selection rule depends on a bound function, which can be intractable. Moreover, we show that such a selection criterion can be inefficient. This paper aims to improve A^* sampling by addressing these issues. To design a suitable selection rule, we apply Probability Matching, a widely used method for decision making, to A^* sampling. We provide insights into the relationship between A^* sampling and probability matching by analyzing a nontrivial special case in which the state space is partitioned into two subsets. We show that in this case probability matching is optimal within a constant gap. Furthermore, as directly applying probability matching to A^* sampling is time consuming, we design an approximate version based on Monte-Carlo estimators. We also present an efficient implementation by leveraging special properties of Gumbel distributions and well-designed balanced trees. Empirical results show that our method saves a significantly amount of computational resources on suboptimal regions compared with A^* sampling.

Tasks

Reproductions