Tree search improves with predictions of target location distribution
Tree Search With Distributional Predictions
Data Structures and Algorithms
Summary
Searching for a hidden target in a tree structure can be done faster if you have a guess about where the target might be. The authors study an approach that uses both a predicted guess and the real unknown distribution of the target’s location. Their method balances trusting the guess with being cautious, so it finds the target using fewer queries on average. They also prove that their method is nearly the best possible and test it on real and made-up trees.
What this means in practice
- •For network engineers: Optimize targeted queries to locate failures or devices in network trees using uncertain location predictions to reduce diagnostic overhead.
- •For game developers: Improve search algorithms in game trees by incorporating distributional predictions about opponent moves to reduce computational queries.
Authors
Michael Dinitz, Bob Dong
Abstract
Learning-augmented algorithms use machine-learned predictions to improve classical algorithmic guarantees when the predictions are accurate, while retaining rigorous performance guarantees when they are not. We study this paradigm for search on trees. Given a tree $T$ containing an unknown target vertex $t$, an algorithm may query any vertex $v$ and learn which neighbor of $v$ lies on the unique path from $v$ to $t$. The goal is to find $t$ using as few queries as possible. We consider the distributional setting, in which the target is drawn from an unknown distribution $p$ and the algorithm is given a predicted distribution $\widehat p$ of unknown quality. We give an algorithm with expected query complexity $O\left(H(p)+k\log η\right)$, where $H(p)$ is the Shannon entropy of the true distribution and $η$ is the earth mover's distance between $p$ and $\widehat p$ in the tree metric. We also provide a matching lower bound that shows our algorithm is asymptotically tight. Finally, experiments on real-world and synthetic trees show that our prediction-based algorithm can use substantially fewer queries than a simple baseline that trusts the prediction completely.