Sample Complexity of Learning Heuristic Functions for Greedy-Best-First and A* Search
Greedy best-first search (GBFS) and A* search (A*) are popular algorithms for
path-finding on large graphs. Both use so-called heuristic functions, which
estimate how close a vertex is to the goal. While heuristic functions have been
handcrafted using domain knowledge, recent studies demonstrate that learning
heuristic functions from data is effective in many applications. Motivated by
this emerging approach, we study the sample complexity of learning heuristic
functions for GBFS and A*. We build on a recent framework called
\textit{data-driven algorithm design} and evaluate the
\textit{pseudo-dimension} of a class of utility functions that measure the
performance of parameterized algorithms. Assuming that a vertex set of size $n$
is fixed, we present $\mathrm{O}(n\lg n)$ and $\mathrm{O}(n^2\lg n)$ upper
bounds on the pseudo-dimensions for GBFS and A*, respectively, parameterized by
heuristic function values. The upper bound for A* can be improved to
$\mathrm{O}(n^2\lg d)$ if every vertex has a degree of at most $d$ and to
$\mathrm{O}(n \lg n)$ if edge weights are integers bounded by
$\mathrm{poly}(n)$. We also give $\Omega(n)$ lower bounds for GBFS and A*,
which imply that our bounds for GBFS and A* under the integer-weight condition
are tight up to a $\lg n$ factor. Finally, we discuss a case where the
performance of A* is measured by the suboptimality and show that we can
sometimes obtain a better guarantee by combining a parameter-dependent
worst-case bound with a sample complexity bound.