Sample Complexity of Learning Heuristic Functions for Greedy-Best-First and A* Search
Authors: Shinsaku Sakaue
Taihei Oki
Venue: NeurIPS 2022 Accept (2022)
Keywords: sample complexity
data-driven algorithm design
heuristic search

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

Sample Complexity of Learning Heuristic Functions for Greedy-Best-First and A * Search
Shinsaku Sakaue The University of Tokyo
Taihei Oki The University of Tokyo Tokyo, Japan
Tokyo, Japan sakaue@mist. i.w-tokyo.ac....
oki @mist.m.......m.mm...imm..mtmmmt 1. .uutokyo jpp
Abstract
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 recent framework called data-driven algorithu design and evaluate the pseudo-dimension a class of utility functions that measure the performance of parameterized algorithms. Assuming that a vertex set of size fixed, we present On Ig n.) and (n²² ng upper bounds on the secudo-dimensions for GBFS and A*, respectively, parameterized by heuristic function values. The upper bound for A can be improved to ( Ig d) if every vertex has a degree of at most d and to O Ig n) if edge weights are integers bounded by poly(n). We also give (2(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 darameter-dependent worst-case bound with sample complexity bound.
Introduction
Given a graph with start vertex goal vertex f, and non-negative edge weights, we consider finding an s-t path with small total weight. The Dijkstra algorithm [16] finds an optimal path by exploring all vertices that are as close to l. It, however, is sometimes impractical for large graphs since exploring all such vertices is too costly. Heuristie search algorithms are used to address such situations; among them, greedy best-first search (GBFS) [17] and A search (A*) [24] are two popular algorithms. Both GBFS and A* use so-called heuristic functions, which estimate how close an input vertex is to t. GBFS/A* attempts to avoid redundant exploration by scoring vertices based on heuristic function values and iteratively expanding vertices with the smallest score. If well-suited heuristic functions available, GBFS/A
much faster than the Dijkstra algorithm. Furthermore, if * uses an admissible heuristic function, i.e., it never overestimates the shortest-patt distance to f, always finds optimal path [24]. Traditionally, heuristic functions have been made based domain knowledge; e.g., graphs are road networks, the Euclidean distance gives an admissible heuristic.
When applying GBFS/A* * to various woal-world problems, a laborious process is to handeraft heuristic functions. Learning heuristic functions from data can be a promising approach to overcoming the obstacle due to the recent development of technologies for collecting graph data. Researchers have demonstrated the effectiveness of this approach in robotics [1 32, 28, 36), computational organic chemistry [13], and pedestrian trajectory prediction [36]. With learned heuristic functions, however,
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

obtaining theoretical guarantees is difficult since we can hardly understand how the search can be guided by such heuristic functions. (A recent paper [1] studies learning of admissible heuristics for A+, but the optimality is confirmed only empirically.) Moreover, learned heuristic functions may be overfitting to problem instances hand. That is, even if GBFS/A * with learned heuristic functions perform well over training instances, they may deliver poor future performance. In summary, the emerging line of work on search algorithms with learned heuristic functions is awaiting a theoretical foundation for guaranteeing their performance in data-driven manner. Thus, natural question is: how many sampled instances are needed to learn heuristic functions with generalization guarantees on the performance of resulting GBFS/A #?
1.1 Our contribution
We address the above question, assuming that path-finding instances defined on a fixed vertex set of size n are drawn i.i.d. from an unknown distribution. Our analysis is based on so-called data-driven algorithm design [22, 4], a PAC-Iearning framework for bounding the sample complexity of algorithm configuration. In the analysis, the most crucial step is to evaluate the utility functions that measure the performance of parameterized algorithms. We study the case where GBFS/A* is parameterized by heuristic function values and make the following contributions:
of a class of
1. Section 3 gives O(n Ig n) and O n) upper bounds on the sseudo-dimension for GBFS and A#, respectively. The bound for A can be improved to O lg d) if every vertex has an at most d degree and to O n) if edge weights are non-negative integers at most poly(n).
2. Section 4 presents ((n) lower bounds the
for GBFS and A*, We prove this result by constructing (())) instances with unweighted graphs. Thus, our bounds for GBFS and A under the integer edge-weight condition are tight up Ig n factor.
3. Section 5 studies particular case of bounding the suboptimality of A*, We show that we can sometimes improve the guarantee obtained in Section by using an alternative O(n Ig n) bound on the ppeudo-dimensee of a class of geraaeter-dependder worst-case bounds [34].
An important consequence of the above results is the tightness up to a Ig factor for GBFS and A under the integer-weight assumption. Note that this assumption holds in various realistic situations. For example, the Internet network and state-space graphs of games are unweighted (unit-weight) graphs, and A is often applied to path-finding instances on such graphs.
1.2 Related work
Data-driven algorithm design. Gupta and Roughgarden [22] proposed a PAC approach for bound- ing the sample complexity of algorithm configuration, which is called data-driven algorithm design and has been applied broad family of algorithms, including greedy, clustering, and sequence alignment algorithms. We refer the reader to a nice survey [4). A recent line of work [5, 9, 10] has extensively studied the sample complexity of configuring branch-and-bool bound and branch-and-cod tree search are presented, which are most closely related to our results. Our upper bounds, which are obtained by using specific properties of GBFS/A*, are better than the previous bounds for general tree search, as detailed in Appendix A. Balcan et al. [8] presented a general framework for evaluating the -diudnddimnnion.. Their idea is to suppose that performance measures form class of functions of algorithm parameters, called dual functions, and characterize its complexity based on how they are piecewise structured. This idea plays a key role in the analysis of [9, 10], and our analysis of the upper bounds are also inspired by their idea. Its application to our setting, however, requires a close look at the behavior of GBFS/A* # Balcan et al. [7] showed that approximating dual functions with simpler ones is useful for improving sample complexity bounds, which is similar to our idea in Section 5. A difference is that while they construct simpler functions with dynamic programming algorithm, we can use a known worst-case bound on the suboptimality of best- first search [34]. Lower bounds on the aseudo-dimensee
methods, e.g.. for general
In [9, 10], upper bounds on the
for graph-search algorithms have not been well studied.
Heuristic search with learning. Eden et al. [18] theoretically studied how the average-case running time of * can be affected by the dimensions or bits of learned embeddings or labels of vertex features, based on which heuristic function values and computed. The sample complexity of learning heuristic functions, however, has not been studied.
2

---

2
Preliminaries
We present the background on learning theory and our problem setting. In what follows, we let Il() be a boolean function that returns 1 if its argument is true and 0 otherwise. We use H C RD to denote class of functions that map y to R S IR. For any positive integer m, we let [m] [l,...,m, m.
2.1 Background on learning theory
The following class of real-valued functions.
[29] is a fundamental notion for quantifying the complexity of a
Definition 1. Let H. C IR be a class of functions that map some domain y to I. We say a set (y1....-UN) UN C y is shattered by H if there exist target values, (,,-.., IN R, such that
(I(((())) 2 f1),... I(h(UN) 2 (x)) h H 2
The pseudo-dimension of H. denoted by Pdimm(L), is the size of largest set shattered by H.
If H is a set of binary-valued functions that map y to {0. 1}. the pscudo-dimension H coincides with the so-called VC-dimension [35], which is denoted by VCdim(H).
The following proposition enables us to obtain sample complexity bounds by evaluating the pseudo- dimension (see, e.g., [2, Theorem 19.2] and [27, Theorem 11.8)..
Proposition 1. Let H 0, H S [0, H and 'D be a distribution over Y. For any ô E (0,1). with probability of at least 5 over the ii.d. draw of (yi,... .UN] ~ DN, for all E H. it holds that
N N
1
N Pdim (H) lg Pdim(H)
lg
h(y:)
[h(v)] yaD
=0 H
N
In other words, for any 0, = 12 1f2 (Pdim(H) lg # + +1g b)) sampled instances are sufficient
to ensure that with probability of at least 1 8, for all & E H. the difference between the empirical average and the expectation over an unknown distribution D is at most e.
2.2 Problem formulation
We describe path-finding instances, GBFS/A* algorithm, and performance measures considered in this paper.
Path-finding instances. We consider solving randomly generated rath-finding instances repetitively. Let (V. E, (welegr: 8, f) be wath-finding instance, where (V, E) is simple directed graph with n vertices, [we beeg gegg. is a set of non-negative edge weights (sometimes called costs), s E V is start vertex, and E V is a goal vertex. We let II be class possible instances. Each instance E II is drawn from an unknown distribution D over II. We impose the following assumption on II. Assumption 1. For all x E II, the vertex set V and the goal node I are identical, and there always exists al least one directed path from F l to ie., every instance & E II is feusible.
Fixing V is necessary for evaluating the pseudo-dimension in terms of = |V]. Note that we can deal with the case where some instances in II are defined on vertex subsets V C V by removing edges adjacent to V V". The feasibility assumption is needed to ensure that GBFS/A always returns a solution, and + L simply rules out the trivial case where the empty set is optimal. In Appendix B, we discuss how extend our results to the case where f. can change depending on instances.
Algorithm description. We sketch algorithmic procedures that are common to both GBFS and A (see Algorithms and 2 for details, respectively). Let Ap be a GBFS/A* algorithm, which is parameterized by heuristic function values E R". Given an instance x E II, Ap starts from s and iteratively builds a set of candidate paths. These paths are maintained by OPEN and CLOSED lists, together with pointers p(-) to parent vertices. The OPEN list contains vertices to be explored, and the CLOSED list consists vertices that have been explored. In each iteration, we select vertex from OPEN, expand v, and move from OPEN to CLOSED.
3

---

Heuristic function values p are used when selecting vertices. For each v E V, the corresponding entry in p. denoted by Pv. represents an estimated shortest-pathe distance from a to t. (Although heuristic function values are usually denoted by I(()): we here use Pe for convenience.) In each iteration, we select vertex with the smallest score, which defined based on p as detailed later. We impose the following assumption on the vertex selection step.
Assumption 2. Define an arbitrary strict total order on for example, we label elements in V by U Un and define a total order <... < Un. When selecting a vertex with the smallest score, we break ties, if any, in favor of the smallest vertex with respect to the total order.
If we allow Ap to break ties arbitrarily, its behavior becomes too complex to obtain meaningful bounds on the ascudo-dimension
Assumption 2 is a natural rule to exclude such troublesome cases.
Performance measure. Let Ap be GBFS/A* * with parameters p E R.. We measure performance of Ap on x E II with a utility function u. We assume u to satisfy the following condition.
Assumption 3. Let H > O. utility function takes and a series of all OPEN, CLOSED, and p(-) generated during the execution of Ap on x E I1 as input, and returns a scalar value in [0, H).
We sometimes use Ap to represent the series of OPEN and CLOSED lists and pointers generated by Ap- Note that u meeting Assumption 3 can measure various kinds of performance. For example, since the pointers indicate an s-1 path returned by A p. can represent its cost. Moreover, since the series of OPEN and CLOSED lists maintain all search states, u can represent the time and space complexity of Ap- We let up II + [0, H] denote the utility function that returns the performance of Ap on any x E II, and define a class of such functions as U = { {up 11 - [0, HJ] | p E IR" j. The upper bound, H, is necessary to obtain sample complexity bounds with Proposition 1. Setting such an upper bound is usual in practice. For example, if u measures the running time, H represents a time-out deadline.
Generalization guarantees on performance. Given the above setting, we want to learn e values that attain an optimal EzzDD(u [xx)] value, where available information consists of sampled instances T NN and "z(()).... "p(xN) values for any E RR. To obtain generalization guarantees on the performance of Ag, we bound E up(2;) EE- [x)]] uniformly for all p R". Note that the uniform bound offers performance guarantees that are independent of learning procedures, e.g., manual or automated (without being uniform, learned f may be overfitting sampled instances). As in Proposition 1, to bound the sample complexity of learning P values, we need to evaluate the pseudo-dimension of U4 denoted by Pdim(l)), which is the main subject of this study.
Remarks on heuristic functions. While we allow heuristic function values p to be any point in R". the range of heuristic functions may be restricted some subspace of RR". Note that our upper bounds are applicable to such situations since restricting the space of possible p values does not increase Pdim(24). Meanwhile, such restriction may be useful for improving the upper bounds on Pdim(4);; exploring this direction is left for future work. Also, our setting cannot deal with heuristic functions that take some instance deepedddd features as input. To study such cases, we need more analysis that is specific to heuristic function models, which goes beyond the scope of this paper. Thus, we leave this for future work. Note that our setting still includes important heuristic function models on fixed vertex sets. For example, we can set using learned distances to landmarks [21], or we can let p be distances measured on some metric space by learning metric embeddings of vertices [37].
3 Upper bounds on the pseudo-dimension
We present details of GBFS and A and upper bounds on the pseudo-dimensions of U. In this section, we suppose that vertices in V are labeled by Ui,..., Un as in Assumption 2.
3.1 Greedy best-first search
Algorithm shows the details of GBFS Ap with heuristic function values p E R". When selecting vertices in Step 3, the scores are determined only by p. This implies an obvious but important fact. Lemma 1. Let p. p' E R be pair of heuristic function values with an identical total order up to ties on their entries, i.e. I(pe. S (e,)) = I(Pb, I Poy)) for all i.j E [n] such that i < j. Then, we have up(z) for all e II.

---

Algorithm GBFS with heuristic function values
1: OPEN = {s)) CLOSED = 9,, and p(s) None.
2: while OPEN not empty:
3: <- argmin Per u OPEN
D Break ties as in Assumption 2.
4:
for each child of v::
5:
c
6:
return s-f path by tracing pointers p(-), where p(t) = v.
7:
if c & OPEN U CLOSED
8:
P(c) v and OPEN + OPEN {c).
9:
Move from OPEN to CLOSED.
Algorithm 2 A x with heuristic function values p
OPEN = {s}, CLOSED 0), p(s) None, and 9.
2: while OPEN is not empty
3:
if f- argmin ge' + Put 1 OPEN).
Break ties in Assumption
4:
=
5:
return s-t path by tracing pointers p(-).
6:
for each child of v:
7:
Inew + De + W(..))- if & OPEN U CLOSED
8:
9:
9c t- Iuew pcc) < v, and OPEN +- OPEN U {c)-
10:
else if c OPEN and Inew < Ic
11:
Sc - Inew and p(c) f- v.
else c CLOSED and Inew < 9c
Steps 12-14 are for reopening.
13:
Gr. < Inew and p(c) <- V. Move from CLOSED to OPEN.
15:
Move v from OPEN to CLOSED.
Proof. For any E II, if p and p' have identical strict total order on their entries, vertices selected Step 3 are the same each iteration of Ap and Apr. Since this is the only step p and p' can affect, we have Ap = Ap' for all E II, hence "p(x)) upp (z). Moreover, this holds even if and/or p' have ties on their entries because of Assumption That is, the total order uniquely determines vertex selected in Step 3 even in case of ties. Therefore, the statement holds.
From Lemma 1, the behavior GBFS is uniquely determined once a total order on {polee is fixed. Thus, for any x E II, the number of distinet (x(x) values is at most n!, the number permutations of (po)oev- This fact enables us to obtain an O lg n) upper bound on the pscudo-dimension of U.
Theorem 1. For GBFS Ap with parameters p R", it holds that Pdim(()) O(n Ign).
Proof. Lemma implies that we can partition R" into n! regions. P1, P2...., so that for every P.. any pair of p. p. P; satisfies up(x) Up (x) for all x E II. Note that the construction of the regions, Pi, ..,.... does not depend on Thus, given any N instances Iı,..., ,,....,,N...... even if moves over whole TR.", the number distinct tuples of form (up(x1).... (x(xN)) most n!. To shatter N instances, n!! 2N must hold. Solving this for the largest yields Pdim(L[) O(nlgn). D
3.2 A search
Algorithm 2 is the details of A*, As with GBFS, p only affects the vertex selection step (Step 3). However, unlike GBFS, the scores, Iv + Pv. involve not only p but also {gu) Each ge is called g-cost and maintains a cost of some path from to e. As in Algorithm 2, when v is expanded and a shorter path e found, whose cost denoted by Snew. update the ge value. Thus, each go always gives an upper bound on the shortest- sattt distance from to u. For each E V, there are at most En= k! < (n- 1)! simple paths connecting to and thus yo can take at most (n 1)! distinct values. We denote the of those distinct values by G.. and define Gv {w, go)
go E G.)) the set of all pairs of vertex and its possible g-cost. It holds that |gvl < (n 1)! n!.
5

---

Note that once E II is fixed, G. for v E V and Gv are uniquely determined. To emphasize this fact, we sometimes use notation with references to x: (x)),, G,(z), and (v( As with the case of GBFS (Lemma 1), we can define total order on the scores to determine the behavior of A uniquely. Lemma 2. Fix any instance such that total orders on the sets of all possible scores, {9n(x) + Pv (v, (z())) E Gx))) } and (g)(t) + Po (c))) E Gv(x) ), are identical up to ties. Then, it holds that up(æ) up (2).
II. Let P.p' E R" be pair of heuristic function values
Proof. If the two sets of scores have an identical strict total order, we select the same vertex in Step 3 in each iteration of Ap and Ap' Thus, we have Ap = Apr for any fixed x. implying Up(x) upr We show that this holds even in the presence of ties by using Assumption 2. First, any two scores of the same vertices, 9u (2) + Pv and (x) + Pu. never have ties since Gn consists of distinct g-costs. Next, if 9v, (x) + Pe; gny (x) + Pey holds for some i < j. we always prefer oy to oj in Step 3 due to Assumption 2. Therefore, even in the presence of ties, select a vertex in Step 3 if the set of scores has a strict total order. Thus, if p and p' induce the same total order up to ties on the sets of possible scores, holds that uz(x) up (z).
By using Lemma 2, we can obtain an On Ig lg)) upper bound on the pseudo-dimension of U. Theorem 2. For A * Ap with parameters p E R", holds that Pdim(U) O(n² lg).
Proof. As with the proof of Theorem 1, we partition R" into some regions so that in each region, the behavior of A* unique. Unlike the case of GBFS, boundaries of such regions change over N instances. To deal with this situation, we use a geometric fact: for m 2 n 2 1, m hyperplanes partition Rn into O((em)") regions.'
Fix a tuple of any N instances (21,.....NN We consider hyperplanes in R" of form go, (2x) + +P = Ie, (æx) + Pv, for all k [N] and all pairs of (v%, (ax)), (1y, Ie, (xx)) E Gv such that i & j. These hyperplanes partition IR' into some regions, P1, .P..... so that the following condition holds:
for every P:, any P. p' E P. have the same total order on { (xx)) + Pa (v, (x())) E Gv } and { (xx) + P/ (v, 9. (2x)) E Gy (Ix)] } up to ties for all l E [N]. which implies up (p(xx) = Up (3x) for all k E [M] due to Lemma 2. That is, for every & E [N] if we see (z(#x) as function of p. it is piecewise constant where pieces are given by PI, P2,... Therefore, when p moves over whole R", the number of distinct tuples of form (up(z1)) ..... Mp((N)) is at most the number of the pieces. Note that the pieces are generated by partitioning IE" with EKEIN] (Svv(w)))) S N (2)) hyperplanes, which (())())) ") pieces. To shatter N instances, O (((N(()) ") 2 2 is
means there are at most O necessary. Solving this for the largest N yields Pdim(U) Onn Ign).
Compared with GBFS, the additional n factor comes from the bound of (n- ! on Gol. This bound may seem too pessimistic, but it is almost tight in some cases, as implied by the following example. Example 1. Let (V, E) be a complete graph with edges labeled as {e1...., , [EE }.- Set each edge weight We, to 2 for E [[E]]. Considering the binary representation of the edge weights, the costs of all simple s-v paths are mutually different for v E V, which implies | = En= 2 k! 2 (n 2)1.
This example suggests that improving the On lg n) bound is not straightforward. Under some realistic assumptions, however, we can improve it by deriving smaller upper bounds on |Gol.
First, if the maximum degree of vertices is always bounded, we can obtain the following bound. Theorem 3. Assume that the maximum dut-degrees of directed graphs E) of all instances in 11 are upper bounded by d. Then, it holds that Pdim(()) = O(n² lg)).
Proof. Under the assumption on the maximum degree, there are at most E dh < (n 1)dm-2 simple s-v paths, which implies |Gul < (n 1)d" for every V E V. Therefore, we have GGvl <
n (n- 1)dd Following the proof of Theorem 2, we can obtain an upper bound on Pdim(()) by
solving O Nº (n (n-11)dd" 1)d" a > 2 for the largest N, which yields Pdim(U[) O( Igd).
Even if some regions degenerate, from [23, Theorem 1.. I] and [12, Proposition A2.1 the number of all d- dimensional regions for d = 0, n is Ea En. (2=1) (.T.) S 2(em)". The fact has a close connection Sauer's lemma [30] (see [20]). In this sense, our analysis is in similar spirit to the general framework of [8].

---

8
8
4
4
371
2/2
J33
2/4
S
Figure 1: An illustration of the instances 21..... In-4 for 8. Each vertex is labeled by s, r, t, or i [n -3 3]. as shown nearby the vertex circles. The values in vertex circles represent p that makes Ap return suboptimal paths to 22 and T3, i.e., S = 32,3). The thick edges indicate returned paths.
Second, if edge weights are non non-neeative integers bounded by W, we can obtain the following bound. Theorem 4. Assume that edge weights [welner of all instances in are non-negative integers bounded by a constant W from above. Then, it holds that Plim(()) (g))))))
Proof. Under the assumption, every g-cost gv takes non-negative integer value most nW. Since Go consists of distinct g-cost values, Goll S nW holds, hence 19v| S n²W. Solving 0 Nm ("r("""
(""W) ") 2 2 for the largest N, we obtain Pdim(()) = O(n lg(nW)).
Note that if W (p)oy(nn)) holds, we have Pdlim(U) On n).
On reopening. A is usually allowed reopen closed vertices in Steps 12-14. This, however, causes 12(2") iterations general [26], albeit always finite [33]. A popular workaround is to simply remove Steps 12-14, and such A without reopening has also been extensively studied [34, 31, 14, 15). Note that our results are applicable to A# both with and without reopening.
Lower bounds on the pseudo-dimension
We present lower bounds on the pseudo-dimension for GBFS/A* We prove the result by constructing ((n) shatterable instances with unweighted graphs. Therefore, the On lg n) upper bounds for GBFS (Theorem 1) and * under the edge-weight assumption (Theorem 4) are tight up to a Ig factor. Theorem 5. For GBFS/A* Ap with parameters p E R", holds that Pdim((() ?(n).
Proof. We construct a series of n - instances, T1, Ti,..., 2n,...,2n.:: that can be shattered by 24 where each Up returns the length of an s-t path found by Ap- We label vertices in by s, r, t, E in 3] See Figure for an example with n 8. We define M = V {s, f). For each z; (i [n 4)) we draw edges (s, u) for E .M and (v, t) for e ( E M v' i}, which constitute optimal s-t paths of length 2. In addition, for each 2;, we draw edges (i,r) and (r, (). where + i r - ( is the only suboptimal path of length Letting I, 2.5 for i [n 4]. we prove that l can shatter those instances, i.e., Ap can return suboptimal solutions to any subset of .en...,nn44. by appropriately setting p.
Let S C In 4] indicate a subset of instances, to which we will make Ap return suboptimal solutions. We show that for any S, we can set p so that Ap returns + i-> to x; and only if S. We refer to the vertex labeled by n - as which we use to ensure that every instance has an optimal path s - m + We set p as follows: Ps = n (or an arbitrary value). Pr = Pt = 0, Pi = i E SU {m}. and p: (or sufficiently large value) if E [n - 4 \ S. If Ap with this is applied to wi, iteratively selects vertices S U {m) 3 increasing order of their labels until a vertex that has a child is selected. Once vertex with a child is expanded, it ends up returning + + / if i and - v for some e > if & We below confirm this more precisely, separately for
GBFS and A#.

---

We consider applying GBFS Ap to z; Ap first expands s and add vertices in M to OPEN. Since vertices in e E [n- 4 \ have sufficiently large scores of n, they are never selected before any vertex in S U [m]. Thus, Ap selects a vertex from S U {m] with the smallest score. If the selected vertex, denoted by v, satisfies v < i, there is no child of e; hence, nothing is added to OPEN, and we go back to Step 3. In this way, Ap iteratively moves v E S U {m] that has no child from OPEN to CLOSED. Consider the first time when the selected vertex V E S U {m} has a child с (this situation is guaranteed to occur since always has child). If i & S, we have + i since V is selected from U {m). Then, since v's child is c = i, Ap returns 8 + u - t with v f if E S, then i has the smallest score (p+ i + 2) among all vertices in S U {m] that have child. Thus, Ap selects and opens r. Now, r has the smallest score of p. = O. Therefore. Ap selects r and reaches t, returning i + + t. Consequently, Ap returns the suboptimal path if and only if E S.
GBFS.
A It first expands s and add M to OPEN. Since gu for all E M, only P values matter when comparing the scores, as with the case of GBFS. Therefore, A* iterates to move vertices in S U {m} from OPEN to CLOSED until vertex that has a child is selected. Consider the first time a selected vertex v has a child (so far, s is not reopened since 9. = 0). As with the case of GBFS, we have V A i and c = / if & S, or 0 = and c = r if E S. Now, every v' E OPEN {e} has a score of at least 4 since J.' = and per 2 3 for E M. Therefore, if & S, E OPEN has the smallest score of 2. Thus, Ap next selects / and returns 8 + v + 4, where v + i. If E S, since E OPEN has the smallest score of 9r + pr = 2 + 0 = 2, Ap selects and opens L. Then, since / has
ge + Pr = 2 +
the score of 9t + P: = 3 + 0 = 3, Ap selects t and returns s + + r - t. To conclude, Ap returns the suboptimal path if and only if i E S.
5 Toward better guarantees on the suboptimality of A
Given the results in Sections 3 and 4, major open problem is to close the Ö(n) gap" between the O(n² Ig n) upper bound and the (2)) lower bound for A in general cases. This problem seems very complicated, as we will discuss in Section 6. Instead, we here study a particular case where we want to bound the expected suboptimality of A*, which is an important performance measure since learned heuristic values are not always admissible. We show that a general bound obtained from Theorem 2 can be sometimes improved by using a p-dependent worst-case bound [34].
For any x E II, let Opt(z) and p(r) be the costs of an optimal solution and an s-l path returned by Ap. respectively, and let up = (ost - (ar) be the suboptimality. From Theorem 2 and Proposition 1, we can obtain the following high-probability bound on the expected suboptimality:
E [Costp(x) Opt(=)) S N Σ (Costpp(z) Opt(z)) + are
N
H
n
+
1g
That is, the expected suboptimality can be bounded from above by the empirical suboptimality over the N training instances (an empirical term) plus an Ö(H /n²/N term (a complexity term). While this bound is useful when N >> n²2, we may not have enough training instances in practice. In such cases, the complexity term becomes dominant and prevents from obtaining meaningful guarantees. In what follows, we present an alternative bound of the form "an empirical term + complexity term" that can strike a better balance between the two terms when N is not large enough relative n².
To this end, we use the notion of consistency. We say p is consistent if Po S Pe W((.)) holds for all (v. c) E E. p is consistent, A* without reopening returns an optimal solution. Valenzano et al. [34, Theorem 4.6) revealed that for any instance E II, the suboptimality of A can be bounded by the inconsistency accumulated along an optimal path (excluding the first edge containing 8) as follows:?
Costp(x) Opt(a)= S Ap(z)
Σ
max Pe Pc W(o.)) 0}.
(2)
(N.))ES'
where ('xx) C E' is an optimal solution to x (if there are multiple optimal solutions, we break ties by using the lexicographical order induced from the total order defined in Assumption 2). We call A (x) the inconsistency (of p on 5*(x)) (I:)
We use Ô and á to hide logarithmic factors of n and N for simplicity.
2 'The original theorem in [34] is applicable only to the case where A does not reopen vertices and = 0. These restrictions are unnecessary detailed in Appendix C. and thus our result holds regardless of reopening.
8

---

Given N instances 21....: NN, we can compute the empirical inconsistency, N E Ap(r;), at the cost of solving the N instances, which we will use as an empirical term. To define the corresponding complexity term, we regard pp(-) II -> [0, H) as an inconsistency function parameterized by p.
where we will discuss how large A > 0 can be later, and we let i = {Ap= IT - [0, #] IR")
The following theorem says that the class 2/ of inconsistency functions has a smaller pseudo-dimension than the class of general utility functions.
Theorem 6. For the class ú of inconsistency functions, it holds that Pdim(t)) Onllgn).
By using (2), Proposition 1, and Theorem 6, we can obtain the following the expected suboptimality, whose complexity term has better dependence than that of (1):
bound on
n lg N
E [Cottp Opt(x)] < xnD [1)((()]] E (z,) +0 x>D
H
This bound is uniform for all R", as with other bounds discussed so far. Thus, the bound holds even if we choose p to minimize the empirical inconsistency. Note that the empirical inconsistency convex in since Ap(z;) consists of maximum of a linear function of p and zero, hence casier to minimize than the raw empirical suboptimality in practice (and suitable for a recent online-convex- optimization framework [25]).
Before proving Theorem 6, we present a typical example to show that the inconsistency is not too large relative to the suboptimality.
Example 2. Suppose that every edge weight we is bounded to [0, W]. which ensures that the suboptimality upp is at most H W(n - 1) for any P R". For simplicity, we consider the following natural way to compute p values: compute an estimate v. E [0, W] of we for each e E E and let Pe be the cost of shortest v-t path with respect (we Then, p enjoys the consistency with respect to (weeeeg: i.e., Pe Pe (i((,c) for every (v,c) E E. Therefore, it holds that
Ap(x) S
Σ
maxf Pc ((v.)): 0}
Σ
(u((,e) W(nre))
(w,c)ES (t)
(v.6)ES
Hence Ap is at most A W(n 2), implying that Ap does not largely exceed the suboptimality. empirically accurate estimates uे, for e E S" (x) available, the inconsistency becomes small.
We prove Theorem 6 by using the general analysis framework by Balcan et al. [8]. To begin with, we introduce Assouad's 's dual class, which provides a formal definition of the class of functions of p.
Definition (Assouad [3]). Given class, H C R of functions h y R. the dual class of H. is defined as 7( = h 7 - R y E y) such that hy (h) = h(y) for each E y.
In our case, have y 11 and H. úi and each A úi* is associated with an instance x 11. The following definition will be used to capture the piecewise structure of the dual class Ui" Definition 3 (Balcan al. [8, Definition 3.2)). A class, H RR of functions is (F, B, -)iicceeis decomposable for a class [ {0, 1) of boundary functions and class J C R of piece functions the following condition holds: for every E H. there exist K boundary functions b(1), ...., ((K) E B and a piece function So for each binary vector E {0. 1} such that for all y E y, holds that h()))= fb,, (v) where by (b)))) ((k) E 1).
The following result of [8] provides an upper bound on the pseudo-dimension of class of functions via the piecewise structure of the dual class.
Proposition 2 (Balcan et al. [8, Theorem 3.3)). Let U C R.ll be a class of functions. IfU" C R is (F. B, K) -iieeewee decomposable with a class B C {0, 13" of boundary functionn and class F C RMd of piece functions, the pseudo-dimension of is bounded as follows:
Pdim(L)) (((dim((F))) VCdim(B*) lg (g(Pdim(F") + VCdim(B")) VCdim(B*) K).
Now, we ready prove Theorem 6.

---

Proof of Theorem 6. Since there is a one-to-one one correspondence between 4p E L and p E R", we below identify Ap with p for simplicity. Let B = (I((z, p) + +2) (zo. z) E R } S {0, 1) and
F F p) + 2u| (20, z) E *R**} S I be classes of boundary and piece functions, respectively. We show that Li* is (F; 13,
decomposable.
Fix any A E 21;; this also uniquely specifies instance z E II and an optimal solution (*) C E (due to the tie- tie-breaking), We consider K E Onn)) boundary functions of form b( (p) = I(p: Pc [(v,c) > 0) for all edges (v, c) E E. We below confirm that these boundary functions partition R" 9 p into some regions so that in each region, (p) can be written as a linear
function of p. which belongs to F. For each binary vector bp = (p) (p)) E {0, 1 we =1,
(p) = 1, f s s: that is, each (v. c) E Sp(z) satisfies + 8 and Pr. Pr: wi(v.)) > O. From the definition of Ap(x), we have (p) = Ap(x) = (e) P. ((v,c)). This is linear function of and thus we can choose piece function Sb, E F such that A = Stp- This relation holds for every bp E 10, and thus we have (p) = (p) for all p E R Hence ii* (F, B, (
define subset Sp(z) of (x) Sp(x) (v, E (a)) (())0()
decomposable.
Since F and B can be seen as classes of linear and halfspace functions of (zo, E g=+1, respectively, we have Pdim(F") VCdim((")) n + 1 (see also [6. Lemma 3.10], a preprint version of [8]). Therefore, from Proposition 2, we obtain Pdim((()= = O()lgn).
6 Conclusion and discussion
We have studied the sample complexity of learning heuristic functions for GBFS and A* on graphs with a fixed vertex set of size n. For GBFS and A*, we have proved that the pseudo-dimensions have shown that the
upper bounded by (n lg n) and ( n). respectively. As for A*, bound can be improved to O(n² Ig d) if every vertex has a degree of at most d and to O(n Ig n) if edge weights are bounded integers. We have also presented the (1)) lower bounds for GBFS and *+, implying that our bounds for GBFS and A under the integer-weipe
condition are tight up to a lg factor. Finally, we have discussed bounds on the suboptimality of A and obtained a guarantee with a better complexity term by evaluating the aseudo-dimente
of the class of inconsistency functions.
An open problem is to close the gap between the upper and lower bounds regarding A* for general cases. This, however, does not seem straightforward. We here discuss the reasons for the difficulty. As regards the upper bound, the bottleneck is the bound of (n 2) on |Go,, but this cannot be improved in general, as shown in Example 1. Considering this, the direct use of Sauer's lemma would not yield better upper bounds. Thus, we need to use some special structures of the hyperplanes (c.g., each has only two variables), which would require more complicated analysis. As for the lower bound, the construction of the (2(n) instances in Theorem relies on the fact that p has an n degree of freedom. In addition, Theorem 4 implies that we need to consider instances with non-integer edge weights (or exponentially large integer weights in n) to obtain a lower bound of 22(n²). Considering the above, we would need more involved techniques for constructing set of ²²(n²) shatterable instances.
Another interesting future direction is improve upper bounds on the pseudo-dimension by restricting heuristic functions to some classes. Appendix D will present an illustrative example where we can achieve polylog(1) upper bounds on the pseudo-dimension by assuming that heuristic functions with much fewer tunable parameters than n can be designed in an instance-specific manner.
We finally discuss limitations of our work. As mentioned in Section 2. we require every instance to be defined on (subsets of) a fixed vertex set. Also, our work does not cover the case where heuristic function values change depending on instance-dependent features. Studying how overcome these limitations would also constitute interesting future work.
Acknowledgements
The authors thank Siddharth Prasad for kindly telling a general result of [10] and anonymous reviewers for providing valuable suggestions, particularly on Appendix D. This work was supported by JST ERATO Grant Number JPMJER1990 and JSPS KAKENHI Grant Number J722K17853.
10

---

References
[1] Agostinelli, S. Mc Aleer, A. Shmakov, Fox, M. Valtorta, B. Srivastava, and P. Baldi. Obtaining approximately admissible heuristic functions through deep reinforcement learning and A* search. In Bridging the Gap Between Al Planning and Reinforcement Learning Workshop at ICAPS 2021, 2021. p.2
[2] M. Anthony and P. L. Bartlett. Neural Network Learning: Theoretical Foundations. Cambridge University Press, 1999. p.3
[3] P. Assouad. Densité dimension. Ann. Inst. Fourier, 33(3):233 282, 1983. 'p
[4] M.-F. Balcan. Data-driven algorithm design. In Beyond the Worst-Case Analysis of Algorithms, pages 626-645. Cambridge University Press, 2021. p.2
[5] M.-F. Balcan, T. Dick, T. Sandholm, and E. Vitercik. Learning to branch. In Proceedings of the 35th International Conference on Machine Learning (ICML 2018), volume 80, pages 344 4533. PMLR, 2018. P.2
[6] M.-F. Balcan, D. DeBlasio, T. Dick, C. Kingsford, T. Sandholm, and E. Vitercik. How much data is sufficient to learn high-performing algorithms? Generalization guarantees for data-driven algorithm design. arXiv:1908.0m (0K,::9900,02994, 02894, 2019. p.10
[7] M.-F. Balcan, T. Sandholm, and E. Vitercik. Refined bounds for algorithm configuration: The knife-edge of dual class approximability. In Proceedings of the 37th International Conference on Machine Learning (ICML 2020), volume 119, pages 580-590. PMLR, 2020. '1 p.2
[8] M.-F. Balcan, D. DeBlasio. T. Dick, C. Kingsford, T. Sandholm, and E. Vitercik. How much data is sufficient to learn high- perforrnro algorithms? Generalization guarantees for data-driven algorithm design. In Proceedings of the 53rd Annual ACM SIGACT Symposium Theory of Computing (STOC 2021). pages 919-932. ACM, 2021. p.2, p.6. p.9, p.10
[9] M.-F. Balcan, Prasad, and Sandholm. Sample complexity of tree search configuration: Cutting planes and beyond. In Advances in Neural Information Processing Systems 34 (NeurIPS 2021), pages 4015-4027. Curran Associates, Inc., 2021. p.2, p.14
[10] M.-F Balcan, Prasad, T. Sandholm, and E. Vitereik. Improved sample complexity bounds for branch-and-cut. In Proceedings of the 28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Schloss Dagstuhl Leibniz-Zentrum für Informatik,
2022. 'I p.2, 'I p0 p.14
[11] M. Bhardwaj. S. Choudhury, and S. Scherer. Learning heuristic search via imitation. In Proceedings of the 1st Annual Conference on Robot Learning (CoRL 2017), volume 78, pages 271-280. PMLR, 2017. ' p.l
[12] A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth. Learnability and the Vapnik- Chervonenkis dimension. J. ACM, 36(4): 965, 1989. p.6
[13] B. Chen, C. Li, H. Dai, and L. Song. Retro#; Learning retrosynthetic planning with neural guided A search. In Proceedings of the 37th International Conference on Machine Learning (ICML 2020), volume 119, pages 1608-1616 PMLR, 2020. 9p.1
[14] J. Chen and N. R. Sturtevant, Conditions for avoiding node re- re-expansions in bounded suboptimal search. Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI 2019), pages 1220-1226. IJCAI Organization, 2019. p.7
[15] J. Chen and N. R. Sturtevant. Necessary and sufficient conditions for avoiding reopenings in best first suboptimal search with general bounding functions. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI 2021), volume 35, pages 5688-3696. AAAI Press, 2021. 7p.7
[16] E. W. Dijkstra. A note on two problems in connexion with graphs. Numer Math., 1(1):269-271, 1959. 1.
[17] J. E. Doran, D. Michie, and D. G. Kendall. Experiments with the graph traverser program. Proc.
R. Soc. Lond. A Math. Phys. Sci., 294((437):235-253 1966. 1 1p.1
[18] T. Eden, P. Indyk, and H. Xu. Embeddings and labeling schemes for A* In Proceedings of the 13th Innovations Theoretical Computer Science Conference (ITCS 2022), volume 215, pages 62:1-62:19. Schloss Dagstuhl- Leibniz-Zentrum für Informatik, 2022. p.2
11

---

[19] R. E. Fikes and N. J. Nilsson. STRIPS: A new approach to the application of theorem proving to problem solving. Artif. Intell., 2(3): 208, 1971. pp.18
[20] B. Gärtner and E. Welzl. Vapnik-Chervan Chervonenkis dimension and
arrange-
ments. Discrete Comput, Geom.. 22(4):3994332 1994. 7.6
[21] A. V. Goldberg and C. Harrelson. Computing the shortest path: A search meets graph theory. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), pages 156-165. SIAM, 2005. p.
[22] R. Gupta and T. Roughgarden. A PAC approach to application-specific algorithm selection. SIAM J. Comput., pages 123-134, 2017. p.2
[23] D. Halperin and M. Sharir. Arrangements. In Handbook of Discrete and Computational Geometry, pages 723-762. CRC press, third edition, 2017. 7 p.6
[24] P. E. Hart, N. J. Nilsson, and B. Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Syst. Man Cybern. Syst. 4(2):100-107, 1968. 5I p.1
[25] M. Khodak, M.-F. Balcan, A. Talwalkar, and S. Vassilvitskii. Learning predictions for algorithms with predictions. arXiv:2202.03//2, 2022. 7.9
[26] A. Martelli. On the complexity of admissible search algorithms. Artif. Intell., 8(1):1-13, 1977.
p.7
[27] M. Mohri, A. Rostamizadeh, and A. Talwalkar. Foundations of Machine Learning. MIT Press, second edition, 2018. "1 p.3
[28] M. Pándy, R. Ying, G. Corso, P. Velickovic, J. Leskovec, and P. Liò. Learning graph search heuristics. In Physical Reasoning and Inductive Biases for the Real World Workshop at NeurIPS 2021, 2021. ppl
[29] D. Pollard. Convergence of Stochastic Processes. Springer, first edition, 1984. p.3
[30] N. Sauer. On the density of families of sets. J. Combin. Theory Ser. A, 13(1):145-147, 1972.
'I p.6
[31] V. Sepetnitsky, A. Felner, and R. Stern. Repair policies for not reopening nodes in different search settings. In Pruceedings of the 9th International Symposium on Combinatorial Seurch (SoCS 2016), volume 7, pages 81-88. AAAI Press, 2016. "I p.7, 'I p.14
[32] T. Takaaashi, H. Sun, D. Tian, and Y. Wang. Learning heuristic functions for mobile robot path planning using deep neural networks. In Proceedings of the 29th International Conference on Automated Planning and Scheduling (ICAPS 2019), volume 29, pages 764-772. AAAI Press, 2019. P.1
[33] R. Valenzano and F. Xie. On the completeness of best-first search variants that use random exploration. In Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI 2016),
volume 30. AAAI Press, 2016. p.7
[34] R. Valenzano, N. Sturtevant, and J. Schaeffer. Worst-case solution quality analysis when not re-expanding nodes in best-first search. In Proceedings of the 28th AAAI Conference on Artificial Intelligence (AAAI 2014), volume 28, pages 885-892. AAAI Press, 2014. 71 p.2, '1 p.7, p.8,
* p..4,, 7 p.15
[35] V. N. Vapnik and A. Y. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory Probab. Appl., 16(2):264 1971. 41 p.3
[36] R. Yonetani, T. Taniai, M. Barekatain, M. Nishimura, and A. Kanezaki. Path planning using neural A search. In Proceedings of the 38th International Conference on Machine Learning (ICML 2021), volume 139, pages 12029-12039. PMLR, 2021. 'p.11
[37] You, R. Ying, and J. Leskovec. Position-awand aware graph neural networks. In Proceedings of the 36th International Conference on Machine Learning (ICML 2019), volume 97, pages 7134-7143. PMLR, 2019, '1 p.4
Checklist
1. For all authors...
12

---

(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes] See Section 1.1 for details of our main claims.
(b) Did you describe the limitations of your work? [Yes] See Section
(c) Did you discuss any potential negative societal impacts of your work? [N/A] This is theoretical paper and no negative societal impacts expected.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section 2.2.
(b) Did you include complete proofs of all theoretical results? [Yes] Some complete proofs shown in the supplementary due the page limitation.
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "yqNw-wVhD7", "reviewer": "Reviewer_cPFZ", "summary": "The paper presents bounds on the sample complexity required for learning heuristic functions to guide greedy best-first search and A* search for solving the shortest path problem in a given graph. The classical approach to best-first search (and heuristic search in general) is to provide it with a handcrafted heuristic (which is typically obtained by solving a relaxed version of the original problem) in order to guide it more effectively towards the optimal solution. However, more recent work aims to learn the guiding heuristic directly from some training data which could be more appealing in some cases. Therefore, deriving bounds on how much data is required to learn a heuristic function with certain guarantees is called for.\n", "questions": "1. What are the practical implications of the proposed bounds? Many interesting domains for GBFS/A* search have exponentially large implicit search spaces (e.g., planning, probabilistic inference, games, etc.) which means that 'n' in this case could be extremely large and therefore one would require an exponentially large training dataset.\n\n[Post Rebuttal] Thanks for your answers. They have clarified my concerns.", "limitations": "see above", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is fairly well written and organised. The quality of the presentation is overall very good and therefore the paper is relatively easy to follow. Most of the concepts and technical details are introduced and discussed if a fairly clear manner. \n\nI think the paper needs a more detailed running example. Otherwise it's not very easy to follow the details especially for a reader who's not very familiar with this research area.\n\nMinor comments:\n\n- Definition 1: there is a typo, h(y_i) \\geq t_i instead of h(y_i) \\geq z_i\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "xF9sijer7F-", "reviewer": "Reviewer_YN2Q", "summary": "This paper studies the sample complexity for learning heuristic functions for GBFS/A* search on a graph with a fixed number of nodes n. The analysis uses PAC learning framework, and the main results show the upper and lower bound of pseudo dimensions of a class of utility functions in which each utility function associates a search task to a scalar value between 0 and H. The paper also continues to provide upper bounds on the expectation of gaps between the optimal costs and the suboptimal costs, where the expectation was taken over the search task sampled from some distribution D, and the bounds are given in terms of the number of samples and the number of nodes.\n", "questions": "I don't know very well about PAC analysis, but following the steps in the paper, the claims all make sense.\nAlthough the assumption is simplified to a very limited case, where the graph has the same terminal node\nand the sampling procedure ends up visiting roughly all the nodes in the graph (n and N in the equations),\nthe upper and lower bounds may characterize the theoretical limits for sample efficiency for learning heuristics.\n\nHow to use these bounds when we learn heuristics for solving graph search problems?\nCan you provide a concrete example with the theoretical bounds?\n ", "limitations": "I think this work is not relevant to this section.", "rating": 7, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths are mathematical analysis of the sample complexity for learning heuristic functions for graph search tasks using GBFS/A*.\n\nWeaknesses are that this analysis emphasizes theoretical aspects and missing practical implications of the upper bounds.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "pRkxp-LdAdb", "reviewer": "Reviewer_zGFs", "summary": "This theoretical paper presents sample complexity bounds for learning\nheuristics for A* and best-first search. It shows an O(nlogn) upper\nbound on the pseudo dimension of BFS and O(n^2logn) for A*, with\nOmega(n) lower bounds for both. It shows that the upper bounds are\nnearly tight, but can be improved for A* when bounding edge weights\nand variable degrees. Moreover, when learning a potentially suboptimal\nheuristic function, the paper gives an upper bound on the\nsuboptimality.\n", "questions": "None", "limitations": "No direct societal impact.", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is relatively straightforward, in the sense that it gives\nclear questions and clear answers. It is well written, and explains\nthe weaknesses of the results, namely the relatively big gap between\nthe bounds on the pseudodimension of A*, as well as give some\nexplanation why it is hard to bridge them.\n\nI don't see any major weaknesses. I would suggest that another\ninteresting direction here is looking at A* for planning. The graph is\nobviously exponentially large, so the bounds here are useless, but it\nhas a compact representation (e.g. the STRIPS model). Could some\nheuristics be learned efficiently in that setting?\n\n----------\n\nTypos, etc:\n\nDefn: you use t_1, ..., t_N for the values in the text and z_1...z_N\nin the formula\n\n107: disrtibution\n\n154: gaurantees\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept