# Probabilistic DAG Search

arXiv: https://arxiv.org/abs/2106.08717 · HTML: https://mlsanity.com/paper/2106.08717/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 24 references that are in the map.
- First posted on arXiv 16 Jun 2021.

## Builds on (most cited first, 3 of 3)

- [Gaussian Processes for Big Data](https://mlsanity.com/paper/1309.6835/) (2013)
- [Expectation Propagation for approximate Bayesian inference](https://mlsanity.com/paper/1301.2294/) (2013)
- [Feature selection as Monte-Carlo Search in Growing Single Rooted Directed Acyclic Graph by Best Leaf Identification](https://mlsanity.com/paper/1811.07531/) (2018)

## Built on by (most cited first, 4 of 4)

- [Differentiable DAG Sampling](https://mlsanity.com/paper/2203.08509/) (2022)
- [Uncertainty-Guided Likelihood Tree Search](https://mlsanity.com/paper/2407.03951/) (2024)
- [Optimistic Optimization of Gaussian Process Samples](https://mlsanity.com/paper/2209.00895/) (2022)
- [Doubly Robust Monte Carlo Tree Search](https://mlsanity.com/paper/2502.01672/) (2025)

## Abstract (arXiv)

Exciting contemporary machine learning problems have recently been phrased in the classic formalism of tree search -- most famously, the game of Go. Interestingly, the state-space underlying these sequential decision-making problems often posses a more general latent structure than can be captured by a tree. In this work, we develop a probabilistic framework to exploit a search space's latent structure and thereby share information across the search tree. The method is based on a combination of approximate inference in jointly Gaussian models for the explored part of the problem, and an abstraction for the unexplored part that imposes a reduction of complexity ad hoc. We empirically find our algorithm to compare favorably to existing non-probabilistic alternatives in Tic-Tac-Toe and a feature selection application.