The (Un)Scalability of Informed Heuristic Function Estimation in NP-Hard Search Problems
Authors: Sumedh Pendurkar
Taoan Huang
Brendan Juba
Jiapeng Zhang
Sven Koenig
Guni Sharon
Venue: Accepted by TMLR ()

Abstract: The A* algorithm is commonly used to solve NP-hard combinatorial optimization problems. When provided with a completely informed heuristic function, A* can solve such problems in time complexity that is polynomial in the solution cost and branching factor. In light of this fact, we examine a line of recent publications that propose fitting deep neural networks to the completely informed heuristic function. We assert that these works suffer from inherent scalability limitations since --- under the assumption of NP $\not \subseteq$ P/poly --- such approaches result in either (a) network sizes that scale super-polynomially in the instance sizes or (b) the accuracy of the fitted deep neural networks scales inversely with the instance sizes. Complementing our theoretical claims, we provide experimental results for three representative NP-hard search problems. The results suggest that fitting deep neural networks to informed heuristic functions requires network sizes that grow quickly with the problem instance size. We conclude by suggesting that the research community should focus on scalable methods for integrating heuristic search with machine learning, as opposed to methods relying on informed heuristic estimation.

Published in Transactions on Machine Learning Research (11/2023)
The (Un)Scalability of Informed Heuristic Function Estima- tion in NP-Hard Search Problems
Sumedh Pendurkar
swmedhpenddurarr@ttmm.. edu
Deportment of Computer Science and Engineering
Texas ABM University
Taoan Huang
Laoanhua Brssc.
Department of Compuler Science University of Southern California
Brendan Juba
bjuba @wsstl edu
Department of Computer Science and Engineering Washington University in St. Lowis
Jiapeng Zhang
jiapengs@usc..o edu
Department of Computer Science University of Southern California
Sven Koenig
skoeniggusc..ede
Department of Computer Science University of Southern California
Guni Sharon
guni edu
Department of Computer Science and Engineering Texas A&M Universiby
Reviewed on OpenReview: https: // openreview. net/ forum? id= Jl RRdycmLk
Abstract
The A algorithm is commonly used to solve NP-hard combinatorial optimization problems. When provided with a completely informed heuristic function, A can solve such problems in time complexity that polynomial in the solution cost and branching factor. In light of this fact, we examine a line recent publications that propose fitting deep neural networks to the completely informed heuristic function. We assert that these works suffer from inherent scalability limitations since under the assumption of NP P/poly
such approaches result in either (a) network sizes that scale super-polynomially in the instance sizes (b) the accuracy of the fitted deep neural networks scales inversely with the instance sizes. Com- plementing our theoretical claims, we provide experimental results for three representative NP-hard search problems. The results suggest that fitting deop neural networks to informed heuristic functions requires network sizes that grow quickly with the problem instance size. We conclude by suggesting that the research community should focus on scalable methods for integrating heuristic search with machine learning, as opposed to methods relying on informed heuristic estimation.
1 Introduction
Principal computational problems such as planning and schoduling (Wilkins 2014). routing Tothh & Vigo 2002), and combinatorial optimization (Papadimitrion & Steiglitz, 1998) are known be NP-Hard (NP- H) in their general form. Consequently, there known polynomial-time algorithms for solving them.

---

Published in Transactions on Machine Learning Research (11/2023)
Moreover, for many of these NP-H problems (belonging to the NP-Complete class), it is unknown if polynomial-imme solver is attainable. This complexity gap, known as the P vs. NP problem (Cook) 2003) remains one of the biggest open computer science questions to date (2023).
Recognizing the gaalllnggs/unattainaalin on reducing the exponential complexity of known solvers using heuristic functions (Pearl 1984.. One promi- nent example of an optimization algorithm that utilizes such heuristics is the A algorithm (Hart et all 1968). A line of publications (Goldenberg et al. 2014 Feiner et al., 2018 exhibited this algorithm's 's ability to achieve exponential reductions in computational time when paired with an informative heuristic function. Morcover, it is casy to show that given completely informed hcuristic function, A can solve NP-H problems in time complexity that is polynomial in the solution cost (depth) and the branching factor. This fact has two major implications that are discussed in this paper.
of polynomial complexity solvers, many researchers are focusing
1. Attaining sufficiently accurate heuristic function estimator (fitted to a completely informed heuris- tie function) could enable scalable solutions to a large class of NP-H problems.
2. If NP g P/poly then the memory complexity for such sufficiently accurate heuristic function esti- mator grows super-polynomialyy with instance sizes !
We show that obtaining a sufficiently accurate heuristic function estimator that represents a completely informed hcuristic function is possible using common machine learning approaches (specifically, universal function approximators (Hornik et al.) 1989)) for problems that can be reduced to a discrete search space. This fact along with implication motivales a line of publications (MeAleer et al., 2018 Agostinelli et al., 2019 2021b) to train such approximators estimate completely informed heuristic functions. However, we assert that, given implication 2, these methods are not 'scalable' in nature. That is, the memory size of boolean circuits (Arora & Barak 2009) required to represent sulficiently accurate heuristic estimators scales polyoopolyyymillly with increasing instance sizes. Our formal discussion places previous publications in an appropriate context. Namely by showing that the applicability of heuristic approximations is inherently limited due to scalability barriers.
Complementing our theoretical claims, we provide experiments examining the minimal fully connected neural network that is required to fit a completely informed heuristic function of three NP-H problems with state- of-the-art gradient- based optimization methods to various levels of precision. These results expand the initial discussion on the scalability of heuristic estimators (Pendurkar et al. 2022a b) by providing theoretical justifications. The reported results suggest that, as expected, the minimum number of required parameters grows quickly with the instance size 2
2 Preliminaries
The class of problems that are solvable in polynomial time by a deterministic Turing machine is denoted by P. NP is the class of problems for which a solution can be verified in polynomial time. These problems are solvable in polynomial time by a non-deterministic Turing machine. NP-Hard (NP-H) is the class of problems to which every problem in NP can be reduced in polynomial time. Further, NP-Complete (NP-C) is class of problems that belong to both NP and NP-H. P/poly is the class of problems that can be solved by polynomial-sized (boolean) circuits. Similar to the P = NP question, NP C P/ ppolyy is another important open question; the Karp-Lipton Theorem (Karp & Lipton 1980) established that NP C P/poly would imply the collapse of the polynomial-time hierarchy. Following this result, we assume that NP g P/poly as it is widely believed that polynomial-time hierarchy does not collapse (Arora & Barak 2009
Assumption 1. NP & P/poly
A large set of NP-H problems can be reduced to a least cost path problem over an appropriate graph, G [V In such cases, each edge (e E E) is affiliated with a positive cost (c: E++ R*). Consequently,
This also has implications on the time complexity, as in general, time complexity is no loss than the memory complexity. For our code and dataset see http://gtttubbccce httbb/.co//Pi-s.... Star- lab/unscalable-eeuree hewristirr---- heurssttic-ppppooittttt approximator)
The reduction function is specilic to each domain (Rultean et al. 2015 Cormen al. 2009 Gupta & Nau 1992..
2

---

Published in Transactions on Machine Learning Research (11/2023)
the least cost path is defined p == arg ming'Ce Eesr d(e) subject to E' is ordered set of edges leading from given start vertex (v, E V) to defined goal vertex (Vg E V). The resulting p is a solution to the original NP-H problem. Note that, multiple optimal solutions to the objective can exist. Despite this, the least cost path problem is not NP-H as, for all known reductions from a NP-H problem, the size of the resulting graph scales exponentially with the problem instance size. That is, the reduction to the least cost path problem is not of polynomial complexity.
The resulting least cost path problems commonly solved using the A algorithm. A searches for the least cost path over the graph without constructing the full graph explicitly. The cost function g V + R+ estimates the cumulative cost from the start vertex to any vertex E V. A is also guided by a heuristic function, h: V + R, defined distinctly for each problem, that estimates the least cost path from any vertex in the search graph, 8 E V, to a goal vertex. We denote the cost of any valid path p' from a given start vertex to the goal vertex as cost(p'). Note, the cost function is considered a part of least cost path problem. The vertices of the search graph are denoted states hereafter, and the set of all states is denotod by S.
For each state it generates, the A* algorithm stores the least cost of reaching it from the start state, that is the 9 value. A stores a list denoted 'fringe' of generated states that are not yet expanded. At each iteration, A expands a state from its fringe with minimal f(s) g(s) + h(s) value. If the expanded state is not the goal, then each of its yet unvisited neighbors is generaled, i.e., it is added to the A fringe along with its computed g and h values. A was shown (Pearl 1984) to expand the minimal number of vertices that is required for finding and proving an optimal (least cost) solution
Given a completely informed heuristic function h" V + R. where (s) is the true minimal cost between and goal state, A would expand only the states along the least cost path. This holds when the tics in the f-values are broken in favor of higher g values. That is, the complexity of computing the least-cost path is polynomial in the solution cost and branching factor (the maximum degree of the vertices in the search graph). As such, attaining h² is highly beneficial. While current, domain-specific heuristic functions were shown to result in orders of magnitude speedups (Helmert & Mattmüller 2008) for NP-H problems, they lack sufficient accuracy to allow polynomial time complexity. Atlempting to close this gap, a recent body of work suggested fitting a universal function approximator (Higgins) 2021 e.g., deep neural networks, to ht.
3 Related Work
3.1 Heuristic search and machine learning
One of the initial works on fitting a completely informed heuristic function was done by Arraee et al. (2010) which we refer to as Bootstrap Learning Heuristic (BLH). They proposed an iterative method ('bootstrap learning") that starts with a known baseline (usually very weak) heuristic estimator and performs a search with A while storing the expanded states along with their minimal cost to the goal (h*). The resulting dataset is used to fit a new heuristic estimator in process that continues iteratively until convergence. Recently, McAleer et al. (2018) proposed to apply reinforcement learning (RL) algorithms on top of a Monte Carlo Tree Search (MCTS) to solve Rubik's 's Cube instances. They learn the value function (negative of the houristic function) using temporal difference lcarning (bootstrapping), with a neural network as the value function approximator, and MCTS as the search algorithm. Following, Agostinelli et al. (2019) presented the DeepCubeA algorithm which learns a heuristic function similar to (McAleer et al.) 20188). but replaces MCTS with weighted * (Ebendt & Drochsler 2009) and uses adjusted state distribution to perform bellman updales. To generate the training samples, they propose laking random walks from the goal stale, and updating all the states visited along the path with a bootstrapping method. DeepCubeA presents state- of-the-art results on various NP-H domains like Rubik's 's cube, Sliding Tile Puzzle, Sokoban, and Lights Out in terms of solution quality and run time complexity (number of generated states).
Another line of work focused on learning a policy (Orseau et al., 2018: Orscau & Lelis 2021 b, where a policy is a function that maps states (vertices in the search graph) operators (edges in the search graph). The optimal policy maps states to edges that follows the least cost path to the goal state. Orseau et al. (0188)
4This claim assumes an admissible and consistent heuristic function Pearl 1984
3

---

Published in Transactions on Machine Learning Research (11/2023)
proposed using policy-guided search algorithm (denoted LevinTS)) and provided theoretical guarantees the number of states expanded. Policy-guided Heuristic. Search (PHS) (Orseau & Lelis 2021 | uses a heuristic function along with a policy. PHS presented a strictly better upper bound on expansions compared to TS under certain conditions, as well as better empirical results for more general cases.
3.2 Universal function approximators
There are various universal approximators that can approximate any well behaved function to arbitrary precision. A 2-layer feedforward neural network, with a non-polynomial activation function and a sufficient number of neurons the intermediate hidden layer, is one such universal function approximator (Cybenko 1989 Hornik et al., 1989 Pinkus
1999). Another universal function approximator is a neural network with non-affine continuous activation function and fixed number of neurons per layer but with sufficient, number of such layers (Kidger & Lyons 2020 In the experimental section, consider these two representative
neural network structures as universal approximators.
3.3 Complexity of STRIPS planning
BBylander 1994), initially proved that determining the existence of a solution for given least cost problem with STRIPS formulation is PSPACE-complete. Further, Jonsson (1999) showed that the least cost path problem (formulated as propositional planning instance) is PSPACF- hard with tight approximability bounds. Aghighi et al. (2016) showed approximating the delete relaxation heuristic (within approximability bounds) requires an exponential amount of time under the assumption that the exponential time hypothesis is true. We extend these previous results for problem-specifie sufficiently accurate heuristic estimators that fitted to completely informed heuristic functions.
4 The Feasibility of Estimating h*
Given the universal function approximation theorem (Hornik et al. 1989). fitting a universal function ap- proximator to h' seems promising. That is, given h- with discrete input (state) space and bounded function range, a universal function approximator (like a two-layer neural network) can fit. h- to arbitrary precision. A algorithm with such a fitted universal function approximator as a heuristic function would run in time complexity that is polynomial in the optimal solution cost and branching factor. This is because, when breaking ties in favor of larger 9 values, A would expand only the states along an optimal path while generating their successors. Despite this positive result, Theorem 1 shows that memory required for any sufficiently accurate heuristic estimator (represented by boolean circuits) grows super-polynoomially To prove Theorem [ we first formally define the promise (decision) problems corresponding to (NP-H) least cost path problems.
Definition (k-cost-path). subset of instances of the decision problem A-cost-pathi(C, s, k), where S C 10, for some n, goal stale, g E S, and la is an inleger represented in unary (1*0), where
least cost path problem is a promise problem given by a (possibly strict)
1. C is Boolean circuit computing function (0, 13"h (0,1) representing the expansion operation by mapping state to the list of at most d adjacent states.
2. k-cost-poth(C, s.g, k) is YES instance if there is valid path p from to g where cost(p) S k
3. there erists at. least one volid poth from to g-
The NP-H least cost path problems are least cost poth problems that contain the image of a polmoomial-time mapping (Karp) reduction for each problem in NP.
As examples, please see the decision versions of the cost minimization problems pancake sorting, traveling salesman, and blocks world, which are NP-C (Soe Bultcau et al. (2015). Cormen al.] (2009), Gupta & Nau [1992) respectively). Note that we may view costs that are multiples of some known unit > integers without loss of generality.
4

---

Published in Transactions on Machine Learning Research (11/2023)
Definition 2 (sufficiently accurate heuristic function estimator). A heuristic function estimator h is defined to be sufficienlly accurale, for a least cost path problem of a given instance size if the following condition holds:
max
(s) 1/2 SES
where all edge costs are assumed to be inlegers.
A sufficiently accurate heuristic function estimator is equivalent to a completely informed heuristic function and can be obtained by rounding h to the nearest integer.
Lemma 1. If a problem F E NP-C, also belongs to P/poly then NP S P/poly.
Proof. If F is in NP-C, then by definition for any problem B E NP, there exists a Karp reduction from F to B. Thus, if F E P/poly then NP C P/poly.
Theorem Given Assumplion 1, the size of the circuils required for sufficienlly accurale heuristic function estimator for every single NP-C k-cost-path problem grows huper-polynomially with the instance sizes.
Proof. By contradiction. Assune a sufficiently accurate heuristic function estimator can be represented by polynomial size circuits. Given this fact, the A algorithm with sufficiently accurate heuristie function estimator can find solution in polynomial time. Thus, the problem is in P/ P/poly. However, given NP-CL k- cost-path also belongs in P/ P/poly, Lemma implies that NP S P/poly. This fact contradicts our Assumption of NP g P/poly. Thus, the size of a sufficiently accurate heuristic function estimator must grow super polynomially with the instance sizes.
iimplees
Theorem implies that sufficiently accurate heuristic estimator is not scalable in nature. For example, consider an artificial neural network a universal function approximator. Querying such network using forward propagation (a single evaluation of h(s) for any s E S) has a complexity of O(n²t) where >> 1 is the maximal layer width and 2 the number of hidden layers. Thus, along with the size of the neural network, the querying complexity grows super-polynomially with instance sizes.
4.1 Is such high precision truly required?
Heuristic estimation results from previous work (Agostineli et al. 2019 suggest that these algorithms might not converge to the completely informed heuristic function. As depicted in Figure 3 (on the right-hand side) within the study conducted by Aggstinelli et al. (2019), there is evident evidence of an underestimation bias present in the learned heuristic estimator. Nonetheless, the DeepCubeA algorithm reports solving the Rubik's cube while expanding fewer states compared to state-of-the-art, domain-specific heuristics (denoted as PDBs* that papor). These results lead to the following question. "Could be that one does not nood to attain a heuristic estimator with high precision to get sufficiently good (polynomial) A runtime? And, if so, then perhaps these heuristics are casier learn?"
The answer to the first question 'No' for the general case. Helmert & Röger 2008 specifically addresses this issue. They show that "general search algorithms such A must necessarily explore exponential number of scarch nodes even under the optimistic assumption of almost perfect heuristic estimators, whose heuristic error is bounded by a small additive constant".. This implies heuristic estimators that are not accurate enough result in exponential time complexity with search algorithms like A regardless the ease of learning to such precision.
4.2 Loss function
The training process of a function estimator is usually defined as an optimization problem over an appropriate objective/loss function. Given that all edge costs multiple of constant 0, parameterized (0) heuristic
5

---

Published in Transactions on Machine Learning Research (11/2023)
estimator that is sufficiently accurate (Definition 2 over set of finite states, D (51, 8n is achieved when Eq 1 equals zero.
(D;0) 1 D
Σ RED
0 if - - < c/2
(1)
otherwise
Notice that Eq [ returns the fraction of states with hcuris- tic approximation error larger than the allowed (e/2) bound. We are not aware of closed form solution that solves arg ming 1D;0). Moreover, given that is not differentiable (around [s)(s) h*)) e/2) and has no meaningful gradi- ents (VI= 0 for its entire domain), it is impractical to apply gradient descent (GD) optimization methods, which are com- mon for training neural networks. As a result, we propose a novel c-bounded error loss function denoted le- We construct this loss function to be (a) differentiable, (b) provide meaning- ful gradients, and (c) have optimal solutions (minimums) that align with the true loss function, 1 (Eq 1b Our proposed 1, is described in Eq 2
PP-MSE
3.0
2.5
1.5
1.0
L(D:0) D
22 exp -c (-c((2)22-))
(2) Figure 1: Loss values (y-axis) for differ- ent loss functions with respect to errors in the heuristic approximation (z-axis). The green line the true loss function, 1. 1 shows loss values for loss with specific value of the e parameter.
4 the product of squared error, denoted by x² (s ht (s))² and sigmoid activation function that tends to 1 as the absolute error exceeds the error bound ((2x/e)² > 1) and
tends to 0 otherwise. с is a hyperparameter that can be used to change the smoothness the loss I around the error bound value c/2.
Figure I illustrates three loss variants as function of the estimation error (x = [h(ss hs)))) with c/2 = is casy to see that both loss functions (Eq [ and le (Eq 2 are optimized (minimized) when = (00:0)=((D)))
= O. These plots also demonstrate the tradeoff presented by the e hyperparameter. When setting c= = 00, any solution (0) that results I(D;0) = 0 must also result in ()) 0 and vice versa. However, such a e value will produce extreme (+20, 00, or 0) gradient values which commonly lead to inefficient or even diverging learning. On the other hand, setting which is strictly convex and usually results in more stable learning yet has a single optimum (minimum) hence it might fail to detect solutions for the original loss function (1 0).
will lead to the classical MSE loss
5 Experiments
The empirical study aims to investigate the minimal size of the deep neural networks (as universal function approximators) required to fit a fixed sized dataset of (s, (s)) pairs with gradient-descent basee opti- mization methods. Our evaluation focuses on neural networks as universal function approximators following recent publications that leverage neural networks as the heuristic function (Agostinelli et al., 2019 2021a
Orseau & Lelis 2021).
Let n denote the size (number of parameters) of neural network used to estimate an informed heuristic function. The experimental study is specifically designed to address the following questions.
How does n scale with the instance size of NP-H problems?
(a) Does such an estimator exhibit ineffective learning due memorization of the training data (overfitting)?

---

Published in Transactions on Machine Learning Research (11/2023)
2.
Does the scalability trends of change with variation in the target approximation precision?
Does the scalability trends of change with the choice of loss function?
5.1 Experimental limitations
Providing empirical evidence supporting the theoretical claims is challenging due to practical limitations. The limitations are listed below:
Obtaining the minimal size of a sufficiently accurate neural network is challenging. This is because computing the global optimal parameter assignment for a non-convex optimization problem within practical compulation limitations still an open question.
Training on the entire state-space of NP-H search problems is impractical because (a) the size of the state space grows exponentially and (b) attaining labels (h* values) for the entire state space is impractical for NP-H search problems as the time required optimally solve them (using known algorithms) grows exponentially with instance size.
Given these limitations, we report evaluation of the minimal size of sufficiently accurate neural net- work, which is (1) based on common (gradient-based) optimization techniques; (2) trained on fixed size datasets as opposed to training on the entire state space. Given this, the experimental section should not be viewed as empirical support for our theoretical claims but rather as a study the impact of our theoretical claims on neural network based heuristic estimators trained over fixed sized datasets as commonly used in literature (Agostinclli
2019 Orseau et al. 2018 Orseau & Lelis 2021
5.2 Universal function approximators
As universal function approximators, we use the two artificial neural network structures described in Sec- tion 3.2 First, a 2-layer neural network (1 hidden layer), with Rectified Lineor Unit (ReLU) (Nair & Hinton 2010) as the activation function P We refer to this approximator rons in the hidden layer may vary, but the number of layers is fixed. Telgarsky (2016) showed the benefits of exponential reductions in neural network size can be obtained when considering deeper networks. As a result, our second setting considers a fixed width per layer but allows any mumber of layers. As in the previous sctting, we use ReLU as the activation function for each layer. Similarly, we refer to this structure as 'ixed width'. We used residual connections (He et al., 2016 and batch normalization (Toffe & Szegedy, 2015) to mitigate issues such as vanishing gradients that we observed during optimization. Our fixed width architecture follows that of Agostinelli et al. (2019), with two differences. First, reduce the number of neurons per layer to allow more gradual increase in the number of parameters following the addition of layers. Following theoretical constraints on the minimal layer size presented by Kidger & Lyons (2020), the size of each layer was set as the number of input dimensions + 3. Second, we have one or two linear layers before the residual blocks (as opposed to a fixed number two layers). This enables us to have an odd as well as even number of layers. Doing so also contributes a more gradual increase in the number of parameters.
'fixed depth' where the number of neu-
2021b we only consider the 'fixed depth' and 'fixed width' structures. Other variants of neural networks, like convolutional neural networks used by Orscau & Lelis (2021), are not considered as they make specific assumptions regarding the state feature space (e.g., spatial locality) which do not. hold in the domains used in our experiments.
Following previous work (Arface et al. 2010 Agostinelli et al. 2019
5.3 Setup
Fitting Criterion: For a model to be considered as 'fitting', we train the model on fixed size training dataset until a certain number of epochs and check whether follows a 'fitting criterion!. For the first. set.
RReL activation function satisfics the propertics required by the universal function approximation theorem Sonoda & Murata 2017).
Hesidaal networks are also universal function approximators Lin & Jegelka 2018

---

Published in Transactions on Machine Learning Research (11/2023)
of experiments, use = (Eq. as the fitting criterion and set maximum of 3,000 epochs to achieve it. For the second set of experiments, we use l, S T with = 0 (i.e., MSF) as the fitting criterion and set a maximum of 300 epochs to achieve it (faster convergence was observed for the relaxed criterion when compared to the I 0 criterion). We use different threshold values (T) to relax the fitting criterion. This relaxation is required because perfectly fitting the data (1=0) 0) usually requires extreme neural network sizes which grow quickly with the size of the training sets. Note that, for the second set of experiments, the fitted models are not guaranteed to be admissible!!
the loss function. We later, use l with c c= 0 (i.c., MSE) as the loss function as relax the fitting criterion. MSE loss results are of interest as this loss function was commonly used in previous work (Agostinelli et al. 2019 2021a by.
Loss Function:
For the initial experiments use (Section 1.2)
Datasets: For all domains, the training set (D) included 3,000 random training samples, each of the type (s, (s)),, in cases where the fitting critcrion was set
0. When the fitting criterion was relaxed, the training set was set to 8 10s samples. The discrepancy in training set sizes is due scalability issues when considering fitting to the strict fitting criterion (I 0). We also sample a separate test set that is used to verify if such estimators suffer from memorization (Question (a)) and thus, minimizing test loss should be not viewed as a goal of the experimental section. For all cases, the test set was set to 2 x 10 random samples.
Optimization: We optimize the neural networks using the Adam optimizer (Kingıaa & Ba 2015). Note that Adam not guaranteed to converge on the global optimum. However, it is widely used the litera- ture (Agostinelli et al. 2019 Orseau & Lelis 2021 as usually leads to "close to optimal" solutions (Böleskei ct al. 2017). To mitigate the impact of local minima, we train cach neural network 5 times and report the lowest loss. The entire dataset could fit in the memory, result, batch size was set to the size of the dataset.
Finding the minimum number of parameters to fit D: Note, if a neural network with a 1-hidden layer of size n can a given function, it must. be that a neural network with n + neurons the hidden layer can also fit (by simply setting the additional weights as 0). Similarly, for the fixed width case, if neural network with layers can fit function, it also fit it with
layers, by setting the weight matrix of the added layer as the identity matrix. Following these understandings, number of neurons (fixed depth) or layers (fixed width) to effectively approximate the minimum number of neurons or layers required to fit D.
perform binary search the
5.4 Domains
B
4
2
1
Flip
2
Move
1
State: (0 1010100011
State: [1 100010001]
State: [0 10122 12201 1200000
State: (0 1 2
State: (0 123]
(a) Pancake
(b) TSP
(c) Blocks World
Figure 2: Examples of a problem state for each of three domains along with state encoding d(s).
We choose domains in which the number of states grows relatively slowly to have a comparison over a larger range of instance sizes. Following these reasons, we choose pancake sorting (Pancake), traveling salesman problem (TSP), and blocks world (Blocks World). Our choice does not follow previous work which focused on the Tile puzzle and Rubik's cube domains as the state space for both domains scales with a relatively high exponent. Nonetheless, Tile Puzzle and Rubik's Cube are NP-H (Demaine
2018
Ratner Warmuth,
7 "Admissiiilitty important guarantee optimal solutions with search algorithms like A'. A heuristic function is said be admissible if Ms) & (s(s)) holds Vs
8

---

Published in Transactions on Machine Learning Research (11/2023)
1990) and their corresponding decision version follows Definition [ thus the main results from this paper also apply in those domains. We use a domain-specific encoding, @, and use (ø(s), h² h*()) to fit the neural network. The cost per operation is multiple of small constant which is 1 for pancake and blocks world, and 0.1 for TSP. An illustrative example of the domains along with their encodings can be scen in Figure 2 Additional details about. the domains are in Appendix
5.5 Results
5.5.1
Scaling neural networks for increasing instance size:
Pancake
TSP
Blorks World
10a
Num Parameters (log scale)
model params
Num Faramdtors (log scale)
model params
10
model params
1.0
10
test
0.88
0.8
10>
0.8
10
0.6
Num Parameters
10
0.8
10a
0.4
0.4
20*
0.2
0.2
10
0.0
0.0
6
10 :2
16
6
10
10 12
Problem
Problem
Proolem
Figure 3: Increase in the minimum mumber parameters (log scale) for a 'fixed depth' network architecture required to fit problems with increasing instance sizes on loss with c = 10. On the x-axis, we have the instance sizes for each of the domains. On the y-axis to the left, we have the number of parameters on a log scale. On the y-axis to the right, we have an error which is a fraction of states where (ho(s) h" (s) c/2.
10a
Panca ce
TSP
Blocks World
1.0
Nim Atrameters loq ocale)
I05:
train eroor
model
-0.5
Num Peremoters (log soale)
train error
perams
1.75
10*
madel
train error
0.8
20a
lest
1.25
best
0.6
10
10"
10
10>
0.75
10a
-0.2
0.25
10a
10e
102
0.0
5
10
10
Proolem Size
Problem
Prostem Size
Figure 4: Increase in the minimum number of parameters (log scale) for a 'fixed depth' network required to fit problems with increasing instance sizes on le loss with c 0 (MSE). On the x-axis, we have the instance sizes for each of the domains. On the y-axis to the left, we have the number of parameters on a log scale. On the y-axis to the right, we have MSE values. Loss thresholds are 0.2, 0.35, and 0.2 for pancake, TSP, and blocks world respectively.
To address Experiment Question 1, we report the (empirically) smallest number parameters (weights and biases) that are able to fit the dataset I(D; 0) for increasing instance sizes. Figure 3 shows plots for the number of parameters on log scale for fixed depth estimator. The loss function was set to the L, loss with 10. For blocks world, the trend shows that the minimum number of parameters grows quickly increase the instance size. The observed trend can be explained by super- soper-polynomial growth (notice that the y-axis is in log scale), following our theoretical claims. For pancake and TSP, we can see similar trend until certain instance size and then a decrease in the minimun number of required parameters. This suggests that, after a certain point, the estimator (neural network) starts overfitting, denoting that the neural network expressive enough to memorize the entire training set. For instance, we consider the pancake domain, the rise is steep until instance size 7, and after that it starts decreasing, suggesting memorization of the training samples. We see similar trend for instance size for TSP.
9

---

Published in Transactions on Machine Learning Research (11/2023)
Num Parameters (log scale)
model params
Pancake
1.0
Num Paramdtuss (lon stalo
10
model params
10*
model parame
Blocks World
0.29
20a
test
train arror
-0.8
10a
test error
train error
2.5
train error
last
0.15
0.6
200
10
1.5
0.10
10.
101
0.5
Num
102
0.05
8
12 Problem Size
16
0.0
12 0.00
Probiem Size
Problem Sizo.
Figure 5: Increase in the minimum number of parameters (log scale) for a 'fixed width' network required to fit problems with increasing instance sizes on l. loss with c= 0 (MSE). On the x-axis, we have the instance sizes for each of the domains. On the y-axis to the left, we have the number of parameters on a log scale. On the y-axis to the right, we have MSE values. Loss thresholds are 0.2, 0.35, and 0.02 for pancake, TSP, and blocks world respectively.
We observe an unintuitive phenomenon once overfitting begins, the required number of parameters declines with the instance size. We believe that this due to the added dimensionality the state space. Our belief follows from (Chen et al.) (007)) who state that "any two finite sets of data with empty overlap in original input space will become linearly separable in an infinite dimensional feature space". This statement suggests that with sufficient state dimensions (instance size) even linear heuristic approximation (neural network with no hidden layers) should suffice for overfitting the training set.
For the rest of the paper, as mentioned in Section 5.3 we relax the fitting condition to le with c = 0 (i.e., MSE), and use the same loss for training. Figure 4 shows a plot for MSE with different error thresholds. The trends are very similar to Figure 3 but we see the overfitting starts at later instance sizes for pancake and TSP. We also see an increase in the number of parameters required as we use the larger (1 million) dataset. We similar patterns for the fixed width case as shown in Figure 5 The plots are noisier than Figure 4 adding another layer of size increases the number of parameters by n² extra weight and extra bias parameters, making it challenging to observe a continuum of the number of parameters. We can see that the number of parameters required to fit is similar across the fixed depth and fixed width cases (~ 5 x 109) at the point when memorization begins.
To validate our overfitting hypothesis (Question 1a), we include a test error for each estimator size in Figure 3 Figure 4 and Figure 5 In Figure 3 we use Eq. as the test error metric whereas for Figure 4 we use MSE, It is casy to see that while the minimal reported network size stagnates past some instance size (for pancake and TSP), the test error continues to increase which is common indicalor of overfitting. For blocks world, by contrast, we do not see rise in test error but also no stagnation.
These results also show that neural networks fail to find good latent structures for NP-H problems unlike in text and image based data. This suggests that a sufficiently accurate heuristic function for NP-hard problems might not have a meaningful latent structure and thus require memorization. As a result, the scalability of heuristic estimator follows that of a naive lookup table, which grows very quickly with the instance size.
5.5.2 Invariance to e:
It seems enticing to think that h" can easily be fitted if the acceptable loss threshold is high enough. Although it is true that fitting to larger loss threshold is easier than fitting to low threshold, we see that, even for larger thresholds, the number of parameters still grow very quickly with the instance size. Figure shows the growth in the number of parameters across instance sizes and for various representative loss thresholds. Although the number of parameters required for lower precision is lower, the required number of parameters still grows very quickly. We can also see that, as we increase the threshold, the point where overfitting begins changes. For instance, for the pancake problem, we see that for threshold 0.6, the curve is growing quickly until instance size 17. Similar our results the previous subsection, we begin to see overfitting when have minimum of 5 x 10 parameters, across differrntt thresholds and domains.
10

---

Published in Transactions on Machine Learning Research (11/2023)
Pancake
TSP
Blocks World
Num Parameters (lop scale)
10
threshold 0.075
10"
10
threshold
Num Paremeters (log
Nurn Parameters (log
10"
threshold
10
10
10a
threshold=0.1
threshold=0.2
threshold-O. 0.2
threshold-O..
10a
10a
threshold-0.6
104
t00
6
8
10
12
14
16
8
10
12
6
10
12
Problem
Problem
Problem
Figure 6: Increase in the minimum number of parameters (log scale) required to fit problems with increasing instance sizes for different loss thresholds on le loss with = 0 (MSE). On the x-axis, we have the instance sizes for each of the domains. On the y-axis, we have the number of parameters on a log scale. For each of the three domains, we use three different thresholds.
These results suggost that the answer to Question 2: "Is the scalability trend of n sensitive to variation in the target approximation precision?" is 'No..
5.5.3
Invariance of unscalability trends to loss objectives:
Pancake: Scaled
Entropy
Num Parameters (log scale)
Num Parameters (log scale)
10
10a
10a
10
10a
10a
10a
10a
10a
10a
10
14
12
14
16
8
Problem Size
Problem Size
Problem Size
Figure 7: Increase in the minimum number of parameters (log scale) required to fit problems with increasing instance sizes on various loss functions for the Pancake problem. On the x-axis, we have the instance sizes. On the y-axis, we have the number of parameters on log scale. The thresholds used for scaled loss, accuracy threshold for cross-entropy loss, and Huber loss are 0.001, 90%, and 0.1.
Beyond the initial variants of lg loss, we now report results for three additional loss functions.
categorical cross entropy loss by viewing the heuristic estimation as classification problem.
Scaled loss defined as: EN
ko(ac)) (=()))
3. Huber loss (Hbee 1992 with delta. 1.
The motivation behind the scaled loss variant is as follows. In many cases, the suboptimality factor of the A algorithm is governed by the relative error in he and not the absolute error. The weighted-A" algorithm Ebendt & Drechsler (2009) is prominent example.
Figure 7 shows a plot for three loss functions for the pancake problem using the 'fixed depth' network structure (similar trends were observed for the other domains and network structure). These results suggest fitting neural network followed
that the trend of a quick increase the minimum number parameters by stagnation (suggesting overfitting) agnostic to the choice of the loss functions. Thus, the answer Question 3 "Is the scalability trend of sensitive to the choice of loss function?" is Noo
11

---

Published in Transactions on Machine Learning Research (11/2023)
6 Conclusion
In this paper, we invostigate the unscalability of hcuristic estimators for NP-hard scarch problems. We provide theoretical justifications for our claim of the unscalabiltty of universal function approximators as heuristic estimators by showing the size of such sufficiently accurate heuristic estimators must grow super- polynomially if NP g P/poly. We support these theoretical results empirically using a common universal function approximator neural network in two settings. The experiments (with conventional practices) suggest that irrespective of the architecture of neural network, choice of optimization objective, and required precision, the number of parameters needed to fit completely informed heuristic function grows quickly with the problem instance size, highlighting the limitations of the current state-of-the-ard approaches. The main conclusion drawn from this paper is that heuristic search algorithms that propose to fit the completely informed heuristic function for NP-Hard search problems are inherently not scalable. We expect that our paper will impact the research community by (1) shifting its research efforts to other/additional ways of inlegrating heuristic search with machine learning (2) roducingg scalability as an important criterion of evaluation for future research in the area of heuristic search and machine learning. We believe our study would assist rescarchers in developing machine learning based approaches that outperform the state-of-the-
art classical planning based solutions (for example see Flatland Challenge (Li et al. 2021 where current classical methods are state-of-the-art).
References
Meysam Aghighi, Christer Bäckström, Peter Jonsson, and Simon Ståhlberg. Analysing approximability and heuristics in planning using the exponential-tine hypothosis. In European Conference on Artificial Intelligence, pp. 184 192, 2016.
Forest Agostinelli, Stephen McAleer, Alexander Shmakov, and Pierre Baldi. Solving the Rubik's cube with deep reinforcement learning and search. Nature Machine Intelligence, 1(8), 2019.
Forest Agostinelli, Stephen McAleer, Alexander Shmakov, Roy Fox, Marco Valtorta, Biplav Srivastava, and Pierre Baldi. Obtaining approximately admissible heuristic functions through deep reinforcement learning and A* search. Bridging the Gap between Al Planning and Reinforcement Learning workshop at International Conference on Automated Planning and Scheduling, 2021a.
Forest Agostinelli, Alexander Shmakov, Stephen McAleer, Roy Fox, and Pierre Baldi. A search without expansions: Learning heuristic functions with deep Q-networks. arXiv preprint arXiv:2102.04514 2021b.
Shahab Jabbari Arface, Sandra Zilles, and Robert Holte. Bootstrap learning of heuristic functions. In Annuaal Symposium on Combinatorial Search, 2010.
Sanjeev Arora and Boaz Barak. Compulational complexity: a modern approach. Cambridge University Press, 2009.
Helmut Bölcskei, Philipp Grohs, Gitta Kutyniok, and Philipp Petersen. Memory-optimal neural network approximation. In Wavelets and Sparsity XVII, volume 10394, pp. 157-168. SPIE, 2017.
Laurent Bultcau, Guillaume Fertin, and Irena Rusu. Pancake flipping is hard. Journal of Computer and System Sciences, 81(8), 2015.
Tom Bylander. The computational complexity of propositional STRIPS planning. Artificial Intelligence, 69 (1-2):165-20) 1994.
Degang Chen, Qiang He, and Xizhao Wang. On linear separability of data sets in feature space. Neurocom- puting, 70(13-15), 2007.
Stephen Cook. The importance of the P versus NP question. Journal of the ACM, 50:27-29, 2003.
Thomas Cormen, Charles Leiserson, Ronald Rivest, and Clifford Stein. Introduction to algorithms. MIT press, 2009.
12

---

Published in Transactions on Machine Learning Research (11/2023)
George Cybenko. Approximation by superpositions of sigmoidal function. Mothematics of Control, Signals and Systems, (1)):33--144, 1989.
Erik Demaine, Sarah Eisenstat, and Mikhail Rudoy. Solving the Rubik's cube optimally NP-complete. In Symposium on Theoretical Aspects of Computer Science, 2018.
Rüdiger Ebendt and Rolf Drechsler. Weighted A search - unifying view and application. Artificiol Intelli- gence, 173(14) 1342, 2009.
Ariel Felner, Jiaoyang Li, Eli Boyarski, Hang Ma, Liron Cohen, TK Satish Kumar, and Sven Koenig. Adding heuristics to conflict-based search for multi-agent path finding. In International Conference on Aulomaled Planning and Scheduling, 2018.
Meir Goldenberg, Ariel Felner, Roni Stern, Guni Sharon, Nathan Sturtevant, Robert Holte, and Jonathan Schaeffer. Enhanced partial expansion A*. Journal of Artificial Intelligence Research, 50:141 50:141-187, 2014.
Naresh Gupta and Dana Nau. On the complexity of blocks-world planning. Artificial Intelligence, 56(2-3): 223 254, 1992.
Peter Hart, Nils Nilsson, and Bertram Raphael. formal basis for the heuristic determination minimum cost paths. IEEE Transactions on Syslems Science and Cybernelics, 4(2):100 107, 1968.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In IEEE Conference on Computer Vision and Pattern Recognétion, 2016.
Michael Held and Richard Karp. A dynamic programming approach to sequencing problems. Journal of the Society for Industrial and Applied Mathematics, 10(1):196 210, 1962.
Malte Helmert. Landmark heuristics for the pancake problem. In Annual Symposium on Combinatorial Search, 2010.
Malte Helmert and Robert Mattmüller. Accuracy of admissible heuristic functions in selected planning domains. In National Conference on Artificial Intelligence, pp. 938 943, 2008.
Malte Helmert and Gabriele Röger. How good is almost perfect? In Proceedings of the 23rd National Conference on Artificial Intelligence, 2008.
Trina Higgins. Generalizing universal function approximators. Nature Machine Intelligence, 3(3):192-199) 2021.
Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are universal approximators. Newral Networks, 2(5):359 366, 1989.
Peter J Huber. Robust estimation of location parameter. In Breakthroughs in statistics: Methodology and distribution, pp. 492 518. Springer, 1992.
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International Conference on Machine. Learning, 2015.
Peter Jonsson. Strong bounds on the approximability of two pspace-hard problems in propositional planning, Annals of Mathematics and Artificial Intelligence, 26, 1999.
Richard M Karp and Richard J Lipton. Some connections between nonuniform and uniform complexity classes. In Proceedings of the twelfth annual ACM symposium on Theory of computing, pp. 302 309, 1980.
Patrick Kidger and Terry Lyons. Universal approximation with deep narrow networks. In Conference on Learning Theory, 2020.
Diederick Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations, 2015.
13

---

Published in Transactions on Machine Learning Research (11/2023)
Jiaoyang Li, Zhe Chen, Yi Zheng, Shao-Hung Chan, Daniel Harabor, Peter J Stuckey, Hang Ma, and Sven Koenig. Scalable rail planning and replanning: Winning the 2020 flatland challenge. In Proceedings of the International Conference on Automated Planning and Scheduling, volume 31, pp. 477 485, 2021.
Hongzhou Lin and Stefanie Jegelka. Resnet with one-neuron hidden layers is universal approximator. Aduances in Newral Information Processing Systems, 2018.
Stephen McAleer, Forest Agostinelli, Alexander Shmakov, and Pierre Baldi. Solving the Rubik's cube with approximate policy iteration. In International Conference on Learning Representations, 2018.
Vinod Nair and Geoffrey Hinton. Rectified linear units improve restricted Boltzmann machines. In Interna- lional Conference on Machine Learning, 2010.
Laurent Orseau and Levi Lelis. Policy-guided heuristic search with guarantees. In AAAI Conference Arlificial Intelligence, 2021.
Laurent Orseau, Levi Lelis, Tor Lattimore, and Théophane Weber. Single-agent policy tree search with guarantees. Advances in Neural Information Processing Systems, 2018
Christos Papadimitriou and Kenneth Steiglitz. Combinatorial oplimization: Algorithms and complecity Courier Corporation, 1998.
Judea Pearl. Heuristics: Intelligent search strategies for computer problem solving. Addison-Wesley, Wesley, 1984.
Sumedh Pendurkar, Taoan Huang, Sven Koenig, and Guni Sharon. discussion on the scalability of heuristic approximators. In Annual Symposium on Combinatorial Search, 2022a.
Sumedh Pendurkar, Taoan Huang, Sven Koenig, and Guni Sharon. The (un)scalability of heuristic approx- imators for NP-Hard search problems. In Can't Believe It's Not Better Workshop: Understanding Deep Learning Through Empirical Falsification, 2022b.
Allan Pinkus. Approximation theory of the MLP model in neural networks. Acta Numerica, 8:143-195, 1999.
Daniel Ratner and Manfred Warmuth. The (n² 1)-puzele and related relocation problems. Journal of Symbolic Computation, 10(2):111-13) 1990.
John Slaney and Sylvie Thiébaux. Blocks world revisited. Artificial Intelligence, 125 153,, 2001.
Sho Sonoda and Noboru Murala. Neural network with unbounded activation functions is universal approx- imator. Applied and Computational Harmonic Analysis, 43(2):233-2P) 22--2288328,2-- 2017.
Matus Telgarsky. Benefits of depth in neural networks. In Conference on Learning Theory, pp- 1517-1539. PMLR, 2016.
Paolo Toth and Daniele Vigo. The vehicle routing problem. SIAM, 2002.
David E. Wilkins. Pructical planning: exlending the classical AT planning paradigm. Flsevier, 2014.
14


Reviews:
[{"review_id": "zUNgOZWvmK", "reviewer": "Reviewer_6bhh", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths.\n\n- Theorem 1 is an interesting result. The proof is brief but clear and convincing.\n\n- Sections 2 and 3 are a good survey of previous theoretical work on the capabilities of search algorithms.\nThe explanations are well-organized and easy to understand.\n\n- Probably, this paper without section 5 is already good.\n\nWeaknesses.\n\n- The connection between section 5 and the rest of the paper is not clear.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The ability of a heuristic search such as the A* search depends on both the heuristic function and the search algorithm.\nIf we had a completely informed heuristic function, A* search could solve many NP-hard problems rapidly.\nHowever, Theorem 1, the main result of the first half of this paper, proves that such a heuristic function cannot be computed in polynomial time using polynomial-sized circuits.\n\nIn the second half of the paper, the authors evaluated the performance of neural-network-based heuristic functions for several real-world problems. They conducted experiments to evaluate the size of neural networks that achieve a given accuracy as the problem size increases.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I want the authors to clarify whether the experimental results and analysis in section 5 are really related to the theoretical results in section 4. However, I do not know what kind of revision would be best.\nI have the following question and would appreciate the authors answering it.\n\nIn many problems, there is a large bias in the value of $h^*$.\nFor example, in the 8-puzzle (3x3 sliding puzzle), there are only two states where $h^* = 1$, and the ratio of the states with $h^* <= 10$ is very small.\nIf we randomly select 3,000 training data from all possible 8-puzzle states, most of them would have an h^* value between 18 and 26 and likely cause overfitting.\n\nHowever, the bias is not so clear for the 2x2 or 2x3 sliding puzzle.\nThus, the smaller the problem, the less likely it may be to overfit.\n\nIn other words, some of the results observed in the experiments in Section 5 may\nnot be due to the nature of P/poly but are simply a phenomenon caused by the difficulty of training the model due to the bias of the h^* distribution.\nTo resolve this question, I would like to see the distribution, or at least the histogram, of the h^* of the training data.", "broader_impact_concerns": "I find no concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "nfELD7hEiu", "reviewer": "Reviewer_oyZD", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The results are not surprising, but they are worth writing down.\n\nThe paper is relatively clear, although, due to my background, I do not understand all the discussion about the different DNN design choices. However, it is reasonable for TMLR.\n\nThere are a few pages of results. The discussion does not clearly convey why they are all meaningful.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper shows that if a NP-hard problem is encoded as a pathfinding problem on a graph of super-polynomial size, then learning a good enough heuristic function to solve the problem optimally in polynomial time requires a deep neural network of super-polynomial size. The authors define a custom-made loss function that closely approximates the real loss function, but is differentiable. Experiments on three NP-hard problems show the increase in size and error.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Throughout the paper, the style used to cite papers is not readable, because the list of authors is not placed between brackets, but the paper itself is not written to accommodate this style of citation. Please fix this.\n\nPage 1, implication 2, why is there an implication on the memory complexity, and not on the time complexity? Is the assumption that the heuristic function is only looking up a value in a table, or must be a large DNN? Please clarify this point.\n\nAt this point of my read (end of page 2), there seems to be an assumption that there is a single least-cost path. However, this is not true in general, and I’m worried it may affect the results. If this is an assumption that can be made without loss of generality, please make it clear from the beginning. (I see on page 4 that breaking ties in favour of larger g values is mentioned, but no explicit link is made).\n\nAfter reading Section 3, I am left wondering whether DNNs provide an admissible and consistent heuristic. If yes, how? If no, is it a problem? If no, why? If yes, how is it handled? Furthermore, it may be useful to define admissible and consistent.\n\nIn Definition 1, the cost function is used in the definition to qualify a YES-instance, but it is written that it is part of the input.\n\nI think it’d be best not to refer to Figure 3 on page 5, as it is on page 8.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "eROSgs8jGN", "reviewer": "Reviewer_scU8", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The writing is clear and the theoretical statements tell a story that is paired well with empirical results.\n- The proposed loss function is sensible, intuitive, and novel to my knowledge.\n- The experiments specifically address the questions raised by the authors.\n\nWeaknesses:\n- The neural network training does not appear to vary two important dimensions that can improve the learned model's performance: 1) training set size and 2) number of training epochs. It would make intuitive sense that larger problem instances need larger networks, larger training sets, and longer training times to succeed.\n- There are other classical loss functions from the literature that may make sense here. I do not expect them to change the qualitative results, but they are an alternative to inventing your own: a) Huber loss and b) $\\epsilon$-insensitive loss (used for support vector regression).\n\nThe authors conclude that this work suggests exploring an alternative approach, but it is unclear if their findings are enough to suggest they would generalize to other problem classes. In some sense, substituting neural networks for completely-informed heuristic functions pushes the problem of heuristic function design to the neural network level of architecture design and training protocols. Neural network training is NP-hard itself (i.e., it is generally a non-convex optimization problem), and so we are trading one NP-hard problem for another. That being said, if one takes the time and has the expertise to carefully design and train a neural network for a given task, the past decade has shown numerous empirical success (e.g., the deep-RL references you cite) on enormous problem instances. Why argue against an approach that has already seen great success on large problem instances?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In prior theoretical work, $A*$ search was shown to solve NP-hard problems in polynomial time assuming it has access to a completely-informed heuristic function. This result supports the exploration of training neural networks (as universal function approximators) to accurately match a completely-informed heuristic function on a finite training set for a specific class of problem instances. This work examines whether this approach scales to larger and larger problem instances. Theoretically, they show that if this approach does scale, it contradicts expected results in complexity theory (NP $\\not\\subseteq$ P / poly). Empirically, they show that exponentially larger neural networks are required to learn completely-informed heuristic functions on larger problem instances from a variety of least-cost path problems. They find that this empirical result holds across the choice of loss function used to train the network as well as the desired target precision. They conclude that research should look towards other techniques for scaling to large problem instances.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- I would suggest trying to vary the training set size and number of training epochs.\n- I would suggest exploring one additional classical loss, e.g., Huber loss, $\\epsilon$-insensitive loss or other.\n\nMinor:\n- Can you reconcile section 4.1 against definition 2 and its implication? In other words, why do we not set $\\epsilon=1$ always?\n- What minibatch size do you use for training the neural networks?\n- For your fitting criterion, do you measure loss using minibatches or the full dataset?\n- In Figure 5, is the right y-axis measuring MSE values?\n- Please add a mention of the pancake problem in Figure 7's caption.", "broader_impact_concerns": "I have no broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work is reviewed by three reviewers with diverse expertise. The authors have provided thorough responses to address the diverse concerns raised by all reviewers. After two rounds of rebuttals, two reviewers (scU8 and oyZD) vote for a clear accept, and one reviewer (6bhh) leans toward reject.

According to comments in the official recommendation, reviewer 6bhh likes this work's theoretical analysis but finds the experimental results unconvincing. On the other hand, this reviewer also mentions they are leaning toward accept if the experiment section is omitted, agree with the author's comment "However, these results do not contradict our theoretical claims", and believe "supporting a theoretical claim in computational complexity with empirical results is generally very challenging". 

I read the paper in detail and agree with all reviewers that this work is well written, the theoretical results are clear and convincing, and at least some individuals in the TMLR audience will find this work interesting. However, the concerns raised by reviewer 6bhh on the experimental study are also valid and valuable. Several claims made in the original experiment section are indeed overstated and should be carefully revised. Given the authors have already successfully addressed some of reviewer 6bhh's concerns and have provided a reasonable response to the issues left, I think the remaining concerns can be addressed via a minor revision, and hence recommend **accept with minor revision**.   

In the revised paper, I expect the authors to 

+ Carefully revise the experiments section (section 5) and make sure all the claims are solid and well-supported. In addition, make sure all discussions provided in the responses are well incorporated into the revised paper.

+ I suggest the authors clearly discuss all the assumptions and limitations for their experimental settings early in section 5 (e.g., a separate subsection might be appropriate). This explicit discussion can avoid any misleading information or misunderstanding from the reader. 

In addition, I also have a question on the discussion of future research direction, which will not affect my decision:

+ In the conclusion section, the authors expect the research community should "(shift) its research efforts to other/additional ways of integrating heuristics search with machine learning" due to the unscalability of informed heuristic function estimation as discussed in this work. However, according to Bengio et al. [1], in practice, the learning-based approaches usually do not aim to solve the whole NP-Hard problem (e.g., all TSPs) but only care about a small subset of instances with a specific pattern (e.g., the pizza delivery problem in a small town, with daily different but similar patterns). In this case, will we still need an exponentially large model to learn a good model-based solver? This question is also related to the easy subset example provided by reviewer 6bhh and the NP-hard trade-off example provided by reviewer scU8. 


[1] Yoshua Bengio, Andrea Lodi, Antoine Prouvost, Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon, European Journal of Operations Research 2020.
Decision: Accept (poster)