Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.

strengths_and_weaknesses: Strengths are mathematical analysis of the sample complexity for learning heuristic functions for graph search tasks using GBFS/A*.

Weaknesses are that this analysis emphasizes theoretical aspects and missing practical implications of the upper bounds.

questions: I don't know very well about PAC analysis, but following the steps in the paper, the claims all make sense.
Although the assumption is simplified to a very limited case, where the graph has the same terminal node
and the sampling procedure ends up visiting roughly all the nodes in the graph (n and N in the equations),
the upper and lower bounds may characterize the theoretical limits for sample efficiency for learning heuristics.

How to use these bounds when we learn heuristics for solving graph search problems?
Can you provide a concrete example with the theoretical bounds?
 
limitations: I think this work is not relevant to this section.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.

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. 

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

Minor comments:

- Definition 1: there is a typo, h(y_i) \geq t_i instead of h(y_i) \geq z_i

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.

[Post Rebuttal] Thanks for your answers. They have clarified my concerns.
limitations: see above
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This theoretical paper presents sample complexity bounds for learning
heuristics for A* and best-first search. It shows an O(nlogn) upper
bound on the pseudo dimension of BFS and O(n^2logn) for A*, with
Omega(n) lower bounds for both. It shows that the upper bounds are
nearly tight, but can be improved for A* when bounding edge weights
and variable degrees. Moreover, when learning a potentially suboptimal
heuristic function, the paper gives an upper bound on the
suboptimality.

strengths_and_weaknesses: The paper is relatively straightforward, in the sense that it gives
clear questions and clear answers. It is well written, and explains
the weaknesses of the results, namely the relatively big gap between
the bounds on the pseudodimension of A*, as well as give some
explanation why it is hard to bridge them.

I don't see any major weaknesses. I would suggest that another
interesting direction here is looking at A* for planning. The graph is
obviously exponentially large, so the bounds here are useless, but it
has a compact representation (e.g. the STRIPS model). Could some
heuristics be learned efficiently in that setting?

----------

Typos, etc:

Defn: you use t_1, ..., t_N for the values in the text and z_1...z_N
in the formula

107: disrtibution

154: gaurantees

questions: None
limitations: No direct societal impact.
review_title: null

Meta-review: metareview: Strong paper studying the sample complexity of learning heuristic functions for GBFS and A*. The reviewers were especially impressed with the theoretical results and find the paper a worthwhile contribution to this conference.
confidence: Less certain
Decision: Accept