Finding the Bandit in a Graph: Sequential Search-and-Stop

Pierre Perrault, Vianney Perchet, Michal Valko

Abstract

We consider the problem where an agent wants to find a hidden object that is randomly located in some vertex of a directed acyclic graph (DAG) according to a fixed but possibly unknown distribution. The agent can only examine vertices whose in-neighbors have already been examined. In this paper, we address a learning setting where we allow the agent to stop before having found the object and restart searching on a new independent instance of the same problem. Our goal is to maximize the total number of hidden objects found given a time budget. The agent can thus skip an instance after realizing that it would spend too much time on it. Our contributions are both to the search theory and multi-armed bandits. If the distribution is known, we provide a quasi-optimal and efficient stationary strategy. If the distribution is unknown, we additionally show how to sequentially approximate it and, at the same time, act near-optimally in order to collect as many hidden objects as possible.

Introduction: The Search-and-Stop Framework

Imagine troubleshooting a complex machine where checking a specific component requires disassembling several others first. These represent precedence constraints in a search task. If you have a fleet of such machines and a limited shift, you must decide when a particular search is taking too long and it is more efficient to abandon it and start fresh on a new machine.

This paper formalizes this as a "sequential search-and-stop" problem on a Directed Acyclic Graph (DAG). An agent seeks a "hider" located at a vertex, constrained by the graph's structure. The objective is to maximize the total number of hiders found within a fixed budget $B$. This framework bridges search theory (efficiently finding one object) and multi-armed bandits (optimizing rewards over time through learning).

Graph structure with precedence constraints represented as disjoint paths.

Offline Search with Known Distributions

When the probability of the hider's location is known, the challenge is determining the optimal search order. The authors demonstrate that a stationary policy—consistently using the same search sequence—is nearly optimal. They define an objective function $J(s)$ to minimize the ratio of expected cost to expected reward. By applying Sidney decomposition from scheduling theory, the optimal search sequence can be found in polynomial time for specific graph structures, such as series-parallel orders.

Online Learning: The CUCB-V Algorithm

In many scenarios, the hider's location distribution is unknown, requiring the agent to learn while searching. Standard Upper Confidence Bound (UCB) algorithms often struggle here because rewards are sparse; the probability of finding a hider at any single vertex is typically very small (around $1/n$).

To address this, the authors propose CUCB-V (Combinatorial Upper Confidence Bound with Variance estimates). By incorporating variance estimates (Bernstein-style bounds), CUCB-V generates tighter confidence intervals than standard UCB. This prevents the algorithm from being overly "optimistic" and wasting budget on high-cost, low-probability vertices.

Key Results and Empirical Performance

The theoretical contributions include proving that the stationary offline policy is quasi-optimal, achieving rewards within $n/J^*$ of an absolute oracle. In the online setting, CUCB-V achieves logarithmic regret $O(\log B)$, meaning the performance gap relative to the optimal strategy grows very slowly as the budget increases.

Regret performance (difference from oracle) vs. budget for various bandit algorithms.

Empirical simulations on edgeless graphs and disjoint paths validate these findings. As shown in the performance plots, CUCB-V and Thompson Sampling significantly outperform standard CUCB, which tends to over-explore and deplete the budget inefficiently.

Conclusion and Future Directions

This work introduces a strategic "stopping" mechanism to search theory, mapping it effectively to bandit learning. While the current model assumes a single hider and specific graph types, future work could extend this to multiple hidden objects or more complex DAG structures where finding the optimal order is NP-hard. Additionally, exploring Bayesian extensions like Thompson Sampling with Dirichlet priors remains a promising, albeit computationally challenging, frontier.

Summary updated

Abstract

We consider the problem where an agent wants to find a hidden object that is randomly located in some vertex of a directed acyclic graph (DAG) according to a fixed but possibly unknown distribution. The agent can only examine vertices whose in-neighbors have already been examined. In this paper, we address a learning setting where we allow the agent to stop before having found the object and restart searching on a new independent instance of the same problem. Our goal is to maximize the total number of hidden objects found given a time budget. The agent can thus skip an instance after realizing that it would spend too much time on it. Our contributions are both to the search theory and multi-armed bandits. If the distribution is known, we provide a quasi-optimal and efficient stationary strategy. If the distribution is unknown, we additionally show how to sequentially approximate it and, at the same time, act near-optimally in order to collect as many hidden objects as possible.
BibTeX
@inproceedings{perrault2019finding,
  author = {Pierre Perrault and Vianney Perchet and Michal Valko},
  title = {{Finding the Bandit in a Graph: Sequential Search-and-Stop}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2019},
  url = {https://openreview.net/forum?id=5P7cRK41YZ_},
}
Figure