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. Unlike traditional search problems, we introduce a "sequential search-and-stop" framework where the agent can choose to abandon a costly search and restart on a fresh instance to maximize the total number of objects found within a fixed budget. We provide a near-optimal offline strategy and an efficient online learning algorithm, CUCB-V, that leverages variance estimates to handle the sparse nature of hider locations.

Introduction

In many diagnostic scenarios, such as troubleshooting complex software systems or physical networks, components must be tested in a specific order due to precedence constraints. These constraints are naturally modeled as a Directed Acyclic Graph (DAG). A "hider" (e.g., a fault) is located at one of the nodes according to a probability distribution. Each test incurs a cost, and the primary goal is to find the hider efficiently.

A critical innovation in this work is the "sequential search-and-stop" capability. If a search becomes prohibitively expensive, it may be more efficient to abandon the current instance and start a new search on an identical, independent system. This introduces two main challenges: determining the optimal stopping point (the Offline Oracle) and learning the hider distribution when it is initially unknown (the Online Learning Problem).

The Offline Oracle and Precedence Constraints

The search environment is defined by a DAG where nodes represent components and edges represent dependencies. To search node $i$, all its ancestors in the DAG must have been searched first.

A disjoint path graph structure used to evaluate search strategies under precedence constraints.

When the hider distribution and search costs are known, the objective is to find a search sequence that minimizes the ratio of expected cost to expected reward. The authors demonstrate that this problem can be reduced to a classic single-machine scheduling problem with precedence constraints. Their proposed ORACLE algorithm identifies the optimal sequence and the precise index at which to stop and restart to maximize the long-term hider discovery rate.

Online Learning with CUCB-V

In practice, the hider distribution is often unknown and must be learned through repeated interactions. This is a multi-armed bandit problem with a combinatorial structure. Standard Combinatorial Upper Confidence Bound (CUCB) algorithms often struggle in this setting because hider locations are sparse—the probability $w_i$ of a hider being at node $i$ is typically very small (roughly $1/n$).

To address this, the authors propose CUCB-V, which incorporates variance estimates into the confidence intervals. By using Bernstein-style bounds, CUCB-V provides much tighter estimates for sparse rewards than standard UCB. This variance-aware approach is crucial for maintaining efficiency as the number of nodes $n$ increases, successfully bridging operations research (scheduling theory) with machine learning (multi-armed bandits).

Empirical Results

The performance of the proposed algorithms was evaluated using synthetic simulations on various graph structures, including disjoint paths and edgeless graphs. The experiments compared CUCB-V against standard CUCB, CUCB-KL, and Thompson Sampling.

Comparison of cumulative regret (measured as the gap to the optimal hider discovery rate) for various bandit algorithms.

As shown in the results, variance-aware methods (CUCB-V and CUCB-KL) and Thompson Sampling significantly outperform the standard CUCB algorithm. While Thompson Sampling shows strong empirical performance, CUCB-V offers robust theoretical guarantees, specifically a regret bound that scales with $\sqrt{n}$, which is shown to be the optimal dependence for this class of problems.

Conclusion

This paper introduces a novel framework for sequential search-and-stop in graphs. The introduction of variance-aware exploration via CUCB-V proves essential for handling the sparse rewards typical of hider-search scenarios. While the current model assumes a single hider per instance and relies on exact scheduling solvers, it provides a strong foundation for future research into multi-fault diagnostics and more complex feedback mechanisms in budgeted bandit settings.

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...
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