Anytime Anyspace AND/OR Best-First Search for Bounding Marginal MAP


  • Qi Lou University of California, Irvine
  • Rina Dechter University of California, Irvine
  • Alexander Ihler University of California, Irvine


graphical models, marginal MAP, inference, search, bounds


Marginal MAP is a key task in Bayesian inference and decision-making. It is known to be very difficult in general, particularly because the evaluation of each MAP assignment requires solving an internal summation problem. In this paper, we propose a best-first search algorithm that provides anytime upper bounds for marginal MAP in graphical models. It folds the computation of external maximization and internal summation into an AND/OR tree search framework, and solves them simultaneously using a unified best-first search algorithm. The algorithm avoids some unnecessary computation of summation sub-problems associated with MAP assignments, and thus yields significant time savings. Furthermore, our algorithm is able to operate within limited memory. Empirical evaluation on three challenging benchmarks demonstrates that our unified best-first search algorithm using pre-compiled variational heuristics often provides tighter anytime upper bounds compared to those state-of-the-art baselines.




How to Cite

Lou, Q., Dechter, R., & Ihler, A. (2018). Anytime Anyspace AND/OR Best-First Search for Bounding Marginal MAP. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1). Retrieved from



AAAI Technical Track: Reasoning under Uncertainty