Bayesian Probing on Graphs
2026-06-08 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors propose a new model called Bayesian Probing to study how to choose edges in a graph when the endpoints have uncertain but related states. Each edge can be checked at a cost, which reveals whether its connected points are active, updating what is known about the network. Their goal is to find a smart way to pick edges that maximizes rewards while staying within a cost limit. This model generalizes previous problems and helps address the Bayesian Active Search problem, where the aim is to find special items efficiently. They provide algorithms that approximately solve this problem for important types of prior information.
stochastic probingBayesian updateknapsack constraintadaptive policygraph correlationsBayesian Active Searchapproximation algorithmsprior distribution
Authors
Anupam Gupta, Benjamin Moseley, Rudy Zhou
Abstract
We introduce a stochastic probing problem with correlated items. In our model, which we call Bayesian Probing, the correlations are modeled by an underlying graph $G$. Each vertex is independently active with a known probability. Each item corresponds to an edge in the graph. Probing an edge has some cost, gives some reward if both endpoints are active, and also reveals the state of its endpoints. Hence a probe induces a Bayesian update on the remaining edges. The goal is to adaptively probe items/edges subject to a knapsack constraint to maximize the expected total reward obtained from the probed edges. Bayesian Probing generalizes stochastic knapsack and stochastic probing by allowing correlations between items. Moreover, it gives a tractable model for the Bayesian Active Search problem, a popular problem considered in the machine learning community. In Bayesian Active Search, the goal is to find items in a particular class by adaptively probing at most, say $k$, items. Given a prior distribution over items, we want to compute a Bayesian policy to maximize the number of such items found. For this general problem with arbitrary priors, there are strong lower bounds on efficiently computing good policies. In this paper, we design efficient approximation algorithms for Bayesian Probing. These results give the first efficient approximation algorithms for Bayesian Active Search, for a class of practically-relevant prior distributions.