Learning Admissible Heuristics for A*:  Theory and Practice
Authors: Ehsan Futuhi
Nathan R. Sturtevant
Venue: ICLR 2026 Poster (2026)
Keywords: Admissible Heuristics
A* Search Algorithm
Optimal search
Generalization Guarantees
Rubik’s Cube
Primary area: other topics in machine learning (i.e., none of the above)
TL;DR: This paper investigates the learning of admissible heuristics, providing both theoretical analysis and empirical validation.

Abstract: Heuristic functions are central to the performance of search algorithms such as A*, where \emph{admissibility}—the property of never overestimating the true shortest-path cost—guarantees solution optimality. Recent deep learning approaches often disregard full admissibility and provide limited guarantees on generalization beyond the training data. We address both of these limitations. First, we pose heuristic learning as a constrained optimization problem and introduce \emph{Cross-Entropy Admissibility (CEA)}, a loss function that enforces admissibility during training. When evaluated on the Rubik’s Cube domain, our method yields heuristics with near-perfect admissibility and significantly stronger guidance than compressed pattern database (PDB) heuristics. On the theoretical side, we derive a new upper bound on the expected suboptimality of A*. By leveraging PDB abstractions and the structural properties of graphs such as the Rubik’s Cube, we tighten the bound on the number of training samples needed for A* to generalize to unseen states. Replacing a general hypothesis class with a ReLU neural network gives bounds that depend primarily on the network’s width and depth, rather than on graph size. Using the same network, we also provide the first generalization guarantees for \emph{goal-dependent} heuristics.

Published as a conference paper at ICLR 2026
LEARNING ADMISSIBLE HEURISTICS FOR A* *: THEORY AND PRACTICE
Ehsan Futuhi' Nathan R. Sturtevant
DDpaartment of Computing Science University of Alberta 2 Alberta Machine Intelligence Institute (Amii) [futuhi, nathanst @uaalerra..c
ABSTRACT
Heuristic functions are central to the performance of search algorithms such as A*, where admissibility the property of never overestimating the true shortest-pan path cost-guaranttes solution optimality. Recent deep learning approaches often dis- regard admissibility and provide limited guarantees on generalization beyond the training data. This paper address both of these limitations. First, we pose heuris- tic learning as a constrained optimization problem and introduce Cross- Eatsopy Admissibility (CEA), a loss function that enforces admissibility during training. On the Rubik's 's Cube domain, this method yields near-admissible heuristics with significantly stronger guidance than compressed pattern database (PDB) heuristics. Theoretically, study the sample complexity of learning heuristics. By leveraging PDB abstractions and the structural properties of graphs such as the Rubik's ' Cube, we tighten the bound on the number of training samples needed for A to generalize. Replacing a general hypothesis class with ReLU neural network gives bounds that depend primarily on the network's 's width and depth, rather than on graph size. Using the same network, we also provide the first generalization guarantees for goal-dependent heuristics.
INTRODUCTION
Heuristic search algorithms such as A (Hart et al., 1968) are widely used in pathfinding tasks (Yone- tani et al., 2021; Meng al., 2024; Kirilenko al., 2023), where the objective is to find a least-cost path from a start state to a goal state in a graph. These algorithms rely on a heuristic function that estimates the cost-to-go from a state to the goal. To guarantee optimality, A requires the heuristic to be admissible, meaning it must never overestimate the true cost, h" to the goal. If we wish to integrate machine learning with heuristic search algorithms like A we have several possible approaches: (1) We can adapt learning to meet the requirements of search algorithms (Samadi et al., 2008; Li et al., 2022), (2) we can adapt search algorithms to meet the properties of ML heuristics (Lelis et al., 2021), 1), (3) we can do a combination of both, or (4) we can abandon all theoretical guarantees, hoping for high quality solutions or fast search in practice (Orseau et al., 2023; Hazra et al., 2024; Chen et al., 2025; Huang et al., 2025). This paper studies the foundations of the first question: what is the sample complexity needed to learn admissible heuristics, what is an effective loss function for training, and how close we can get to optimal heuristics in practice?
Traditionally, admissible heuristic functions are computed from domain knowledge of the problem (Katz& & Keyder, 2022; Haslum al., 2005; Seipp. 2024). One prominent example is pattern databases (PDBs) (Korf, 1997; Culberson & Schaeffer, 1998). PDBs result from abstracting the problem and storing h- for all states in the abstract problem. Learning heuristics from data (Li et al., 2022; Agostinelli et al., 2021; Pándy et al., 2022; Shen et al., 2020; Chen et al., 2024b) has become increasingly popular for two main reasons: (1) designing good heuristics for complex environments challenging, and (2) data-driven deep learning algorithms have demonstrated outstanding performance in analogous tasks (Silver et al., 2017: Schrittwieser et al., 2020; Wurman et al., 2022: Touvron et al., 2023). While learned heuristic functions may outperform traditional heuristics, they typically lose admissibility and thus suboptimality guarantees (Agostinelli et al., 2019; Yonetani et al., 2021; Archetti et al., 2021; Kirilenko et al., 2023). Despite substantial empirical progress, the theoretical foundations of heuristic learning are relatively underexplored. central question is: How many training samples are required to ensure that the learned heuristic generalizes effectively the entire

---

Published as a conference paper at ICLR 2026
graph? Sakaue & Oki (2022) addressed this question for Greedy Best-First Search (GBFS) and A*, providing upper and lower bounds on the training samples necessary to ensure generalization.
We extend this work to the problem of learning admissible heuristics in two main directions. First, we analyze the sample complexity of learning heuristic functions from a given dataset. We introduce new upper bound for the expected suboptimality of A with reopenings. We then derive tighter generalization bounds by leveraging structural properties of the graphs of interest. We further incorporate neural networks as the heuristic model and derive generalization bounds that depend primarily on the size of the network rather than the size of the underlying graph. Notably, using neural networks, we establish the first generalization bounds for goal-dependent heuristics. Across all theoretical results, we demonstrate that leveraging PDBs instead of drawing training samples from the original graph leads to improved bounds.
Second, we formulate the optimization problem for learning admissible heuristics for search ap- plications. We propose a novel loss function, termed Cross Entropy Admissibility (CEA), along with training framework that satisfies all the constraints of the optimization problem. We evaluate our framework on several x Rubik's Cube pattern databases PDBs. The CEA loss function produces near-admissible heuristics, achieving inadmissibility rates around 1 x 10-6 across all DoBs-siinificanlly outperforming standard training based on the Cross Entropy (CE) loss. The strength of the learned heuristics exceeds that of same-sized PDBs obtained using classical compres- sion techniques; notably, for the 8-corner PDB, the CEA loss successfully learns the admissible PDB heuristic perfectly.
2 BACKGROUND
In heuristic search, the task is to find a path from a start state Sinse E V to a goal state goal E V in graph {G {V, E},, c, hJ, where c: E' + E specifies the cost for each edge and the heuristic function h(v) estimates the distance from any state to gool. A heuristic is called admissible if, for all E V, we have h(v) S (u), where h" (v) is the true shortest distance from to goal. heuristic function h is consistent if, for all states b E V such that (a, b) E E, we have h(a) S c(a, b) + h(b). In large state spaces, the graph G is represented implicitly and is generated dynamically during search by expanding states and exploring their neighbors. Although A* guarantees optimal solutions under an admissible heuristic, it can become less efficient if the heuristic is inconsistent, due to the potential for re-expanding nodes (Martelli, 1977; Felner et al., 2011; Helmert et al., 2019). For positive d}. Given vectors {x},... 1x......3 x') C Rd, we use superscripts to index the vectors and subscripts for coordinates, so x denotes coordinate j of vector i. For any real vector x, the operator [x] applies the ceil function coordinatewise. We use I(-) to denote the indicator function, which returns when the stated condition holds and otherwise. Let II denote the space of problem instances and let D be an unknown distribution supported on πΤ; write D for random instance. Each æ E II specifies start state Sinit from which the search is initiated. We make the following assumption on all instances.
integer d, write [d] == 21, 2,
Assumption 1 (Fixed graph and reachability). The state graph G and goal E V are fixed and shared across all instances E IT. For every instance with start state Sinit & gool, there exists at least one directed path from Sinit to gool.
A Algorithm. We use A denote an A algorithm that employs heuristic function h. This algorithm maintains two lists of states: OPEN for states that have been generated but not expanded, and CLOSED for states that have already been expanded. Additionally, we store a pointer to the parent of state 8, denoted as P Parent(s). which allows us to reconstruct the path to 8inat by tracing backward from s. Algorithm in Appendix B provides an overview of the procedure of Aj. Given an instance x E II, Aj, initializes its search by adding Sinit to OPEN. At each iteration, it selects from OPEN a state 8 with the minimum value of [s) = h(s) + g()). To ensure consistent performance bounds for A7, we impose the following assumption when ties occur.
Assumption If the state space V contains n vertices, we impose an arbitrary strict total order on V. For example, consider the order U1 < U2 < ... < Un. In this ordering. if two states and vj have the same lowest value, we select U, when i j. and v otherwise.
When expanding a state s, let Inew + g(s) + c(s. s') denote the generated cost of the path from the start through to its child s'. Three situations can arise for s' based gnew:
2

---

Published as a conference paper at ICLR 2026
1. If s' OPEN U CLOSED, then we add s' to OPEN.
2. If s' E OPEN and Inew < g(5)), then we update Parent(s') and g(s') to reflect the improved path.
3. If 5' E CLOSED and Jnew < g(s'). then update Parent(s') g(s"), and move s' from CLOSED back to OPEN.
Case 3 is only needed if the heuristic is inconsistent. After generating and evaluating all children of s, we remove from OPEN and place it in CLOSED. This procedure continues until the goal state is selected from OPEN for expansion, which point the algorithm terminates with a path to goal.
Abstraction-Base Based Heuristics. As a form of abstraction heuristics, Pattern Databases (PDBs) simplify graph V by applying a homomor- phic transformation to obtain reduced state space <VV). For example, a 3 x Rubik's Cube contains 26 cubics 12 edges, 8 corners, and 6 centers-as as illustrated in Figure 1. One can abstract away the edges and centers to construct an 8-corner PDB with 8! 3" states, in contrast to the 4.33 x 19 states in the original graph. Within this abstract representation, there is edge between i1 and in V. an edge will also be present between ((v1) and 6(02) in (VV). Thus, all distances are admissible, and all states from V that reduce to the same state in Φ(V) have identical heuristic values. More details regarding the reduction from states in V states Φ(V) are shown in Figure 3 in Appendix C. The PDB stores the perfect heuristic value (optimal distance to the abstract goal) for every abstract state, obtained by running an optimal search in the abstract state space. During the search, the current state is mapped to Φ(v). and ranking function (Myrvold & Ruskey, 2001) is used to assign a unique integer to the abstract state. This functions as an index in the lookup table to retrieve the the precomputed distance the abstract goal, which serves as the heuristic value hvv). Compression techniques (Felner et al., 2007: Helmert et al., 2017 7) reduce the size of the PDB by grouping entries and only storing the lowest heuristic value from the group, which maintains admissibility.
(a) Center (b)
Edge cubes.
Figure I: A solved 3 x 3 Rubik's Cube with each group of cubies shown separately: (a) center bies, (b) corner cubies, and (c) edge cubies.
Preliminaries for Sample Complexity Analysis. We use pseudo-dimension (Pollard, 1984), central concept for measuring the complexity of a class of real-valued functions, as the foundation of our analysis. The definition of pseudo-diment dimension as follows.
Definition 1. Let H C R be a set of functions mapping domain y into RR We say that subset (yi,..., [NN] y shattered by H if there exist target values ..,... such that
K (Uth((e)) 2
2 2N33)
hh 1 | =
The largest number of samples that can be shuttered by H is called the psendo-dimension of H. denoted by (H).
We use the following proposition (Theorem 11.8 in (Mohri et al., 2018)) that helps us to attain generalization bounds using the definition of pseudo-dimension.
Proposition 1. Let H > 0, H C [0, HJ" and be a probability distribution over y. Suppose we draw (yI,... ......., yN DNN i...d. Then, with probability at least 6 over this random draw, the following holds for all h E H:
N Σ
Pdim(H) log( N ( log(
EynD [h(y)] of "
h(y:)
In simpler terms, if the size of the training dataset is N = 22 H² (Pdim log H. + log f)) with a probability of 1 - 8, we can guarantee that the difference between true expectation over the entire graph and the emperical mean over the dataset is less than
3

---

Published as a conference paper at ICLR 2026
Performance measure. We need general definition of performance that cover various metries. Specifically, we measure the performance of Aj, on E E II using a utility function u, defined below: Assumption (Sakaue & Oki (2022, Assumption 3)). Let H O. A utility function u takes æ and a series of all OPEN, CLOSED, and Pa Parent() (.) generated during the execution of A3, on x E Il as input, and returns a sealar value in H.
With this definition, the utility function could, for instance, be the number of node expansions or the total running time, since both can be directly computed from the sizes of the OPEN and CLOSED lists. As shown in Proposition 1, we require a strict upper bound on these measures to ensure that all functions in the class 24 return positive, bounded values. This assumption explicitly we often set time memory constraints when running Aj, We denote by up : II + 10, H] the utility function that evaluates A performance on any instance x E II, and we define the class of such functions as 4 { U/,, II [0, H] h E }"
used in experiments,
Our goal is to determine the number of training instances needed to learn a heuristic function E IR" such that the AA, algorithm achieves optimal performance w.r.t the utility function all instances It ~ D. Concretely, we want to learn a heuristic function that attains optimal expected performance, EgEDD (ug [a)]. Because we only observe the performance of A on the training instances ri,..... FN,, namely un (x1).... ... Up (IN), we must ensure generalization to any x ~ D. To achieve this, we need to bound the difference between the empirical average performance and the expected performance,
N
(z:) EE-D jun (x)]
N
uniformly for all E IR". Establishing such a bound requires determining the pseudo-dimension of U. In the following section, use our theoretical tools to derive this result. Note that all proofs and an extended related work discussion are provided in the appendix.
3 SAMPLE COMPLEXITY ANALYSIS
In this section, we attain the Pdim(l)) for the A algorithm. To this aim, we need to discretize Th into regions such that all heuristics in region have the same performance: uh, Whg if h1, h2 E P. If we look at the Algorithm 1, the only part that the heuristic function impacts the performance is the node selection step from OPEN (line 3). However, in addition to h. the path cost from Sinst to each state v also matters to determine the total cost: f(r) = g(v) + h(v). If only h determines which node to expand, such as in GBFS,
know that only the total ranking given by h over all states v E V matters. So, the number of regions are the total number of different ordering among the states, which is n! (Sakaue & Oki, 2022; Chrestien et al., 2024). In the case of A* algorithm, we first need to define the cases when two different heuristics result in the same performance:
Let and h' be two heuristic functions in R² such that h((;)) h(u,) -h((,)) - (((,) for any two pairs of Us, Vj E V. Then, it follows that ux(x) us (x) for every E II.
Lemma 1.
Before presenting our main theorem, we require a more detailed examination of g-costs, which appear as one component of the f-oost. Formally, at each iteration of A?, g(v) tracks the cost of the shortest path discovered so far from Sinit to a vertex v. This cost may be updated if lower-cost path is found later in the search, implying that g(v) always represents an upper bound on the true cost from Sinit to u. To determine the number of distinct g(v) values a graph, we impose the following assumption, which holds for many combinatorial problems (e.g., the Rubik's Cube).
Assumption 4. Let {G = (V, E}, c, h} define our task. The edge cost c: E + {co} assigns a constant cost co to all edges.
Under Assumption 4, the number of distinct values that g(v) can take for any V is at most [V] Define Gv = (v.g(v) v E V}. which is the set of vertex-cost pairs. Hence, [Gv < n². Armed with these observations, we now establish upper bound on Pdim(U4) for A* in the following theorem. While our proof uses a different derivation technique, the resulting bound matches that of Sakaue & Oki (2022).
Theorem 1. Let A,, have parameters h E R", and let the graph G satisfy Assumption 4. Then, holds that Pd)m(U)) On logn).
4

---

Published as a conference paper at ICLR 2026
Extension to PDB Heuristics. In general, consider heuristic functions h R". However, for PDB heuristics, one can learn values on an abstracted state space whose size is m, which can be exponentially smaller than In that case, h effectively lives in R We next show that learning heuristic functions to approximate a PDB heuristic can further reduce Pdim(L)).
Theorem 2. Let G be a graph with |G] = n, and let P be a PDB dataset over with an induced graph of size m. Suppose A uses a heuristic h trained P and that G satisfies Assumption 4. Then, Pdlim(2f= = (m log n))
Remarks upper bounds for Pl) Sakaue & Oki (2022) provided the first upper bounds on Pdim For a general class of graphs, they proved an upper bound of O(n" logn), later refining it to On lo)(n)))) under the assumption that edge weights are bounded by constant W. In our setting, where graphs follow Assumption 4, we initially obtain an upper bound of O(n log n)). We then improve this bound Om log n) by utilizing learned PDB heuristics, with representing the size of the graph induced by the PDB.
3.1 UPPER BOUNDS ON THE EXPECTED SUBOPTIMALITY
we aim to achieve Plim for the A algorithm without imposing Assumption 4, the sample complexity scales the order of On log ni). Consequently, obtain tighter results, often restricts the class of graphs under consideration. The general class of performance measures defined carlier encompasses a wide range metrics related to the performance of the Ai algorithm, including runtime, the number of node expansions, and memory consumption. Rather than seeking tighter bounds for this general class, we focus on a special measure called the expected suhoptimality, which captures how far the solution returned by A is from the optimal solution. For given problem instance E II, let ((x) be the cost the path found by A*, and let C*((r) be the cost of an optimal path. We define the suboptimality as
(x) = Cx(x) - C²
Then, applying the bound on (l) together with Proposition 1, we obtain the following upper bound on the gap between the expected and empirical suboptimality on training data:
N S -(C(())- C*(a)) + o( H N
1
n log
EgnD (Cn(2) C*(+)]
To reduce the error term in Equation (1), we employ a worst-case bound on the quality of the solution returned by A+, Valenzano et al. (2014) proved that if A* does not reopen nodes (i.e., if we remove lines 13-14 in Algorithm 1), then the suboptimality can be bounded by the total inconsistency along the edges of optimal path. Importantly, this bound holds for any heuristic function- even if it is not admissible- as long as the following conditions are satisfied for all E V:
h(s) 2 O.
h(s) = 0 if s goal, and
h(s) # co whenever h²" (s)) + oc.
Coneretely, for any instance x E 11, if vo, ... Un an optimal path with cost C* then
Cx(x) (x) < LNCA 1341),
where, for every edge (p.c) E E, the inconsistency INC, is defined as INCA(p, c) = max h(p) h(c) c(p,c), c), 0}. Because (NC.(...) is always non-negative, the total inconsistency on any path can be estimated by summing the edge inconsistencies along that path. Sakaue & Oki (2022) further showed that this bound remains valid even when A reopen nodes from CLOSED upon discovering path with lower g cost. In Theorem 3, we show that the bound can be tightened when A allowed to reopen nodes.
5

---

Published as a conference paper at ICLR 2026
Theorem 3. Let II be problem instance, and let Popt vo, Ul..... Uk be its optimal solution path with cost (x). Suppose A is allowed to reopen nodes. Then the cost Cn((a) of any solution returned by A satiifies
Cx(x) - -C*(x) <
max we Popt
h(v)) - (w))
We use (x) = m Pops [b(v) - [w)] to represent the inadmissibility function parameterized by h for x. We define the class of all inadmissibility functions as li = , II + [0, H]] E R"),
where H is the bound the performance measure required by Assumption 3. In the following theorem, we bound the difference between the empirical inadmissibility over N training instances, namely N Σi= (x(),,, and the expected inadmissibility using Pdim(U). holds that Pdim(()) Onn and
Theorem 4. For the class ú of inadmissibility functions, function we can bound the generalization error by
(m)) + ÖHH n+log
E anD D
<
N
Now, looking the generalization error from Theorem and Theorem 3, we get a tighter upper bound for the expected suboptimality:
N (x;) +Ö H
+ log !
[C((t)) 20D
C*
E RND
S
(3)
N
3.2 SAMPLE COMPLEXITY USING NEURAL NETWORKS
So far, we have analyzed the sample complexity of heuristic functions h E I under the assumption that each vertex v E has a distinct value, and modifying the heuristic at one vertex does not affect the others. However, in many data-driven settings, these heuristics are realized by neural network rather than a simple mapping in RR". In this section, we derive sample complexity bounds for neural network-bass heuristic functions graphs that satisfy Assumption 4. To do so, first formalize both the mapping induced by these networks and our corresponding hypothesis class.
Definition (Neural networks Cheng al., Definition 2.4). Given any function RR R. o(xa)] E IRd. Let a
we will use the notation (xx for x E Rd to mean [x(x),, neural network with activation and architecture w [wo, Wi...., WL, WL+1] 2++2 a parameterized function class, parameterized by L + :R:: RR::-1 + R i + 1]} with TI+1 linear, is defined as the function affine transformations [T: :
+ and let L be a positive integer.
T141000 ....o.
denotes the number of hidden layers in the network, while w; signifies the width of the i-th hidden layer for E [L]. The input and output dimensions of the neural network are denoted by wo and WL+1. respectively. If T; is represented by the matrix A E _ 1gm;xw;-1 and vector b' E R i.e. T,(x) = A'x b' for i E [I. + 1). then the weights of neuron j [wx]] in the i-th hidden layer come from the entries of the j-th row of A' while the bias of the neuron is indicated by the j-th coordinate WI, denoted by U.
b'. The size of the neural network defined as w
With reference to Definition 2, family of neural networks is defined as N -8"0 x RWW + R where "h the input space, o is the activation function in hidden layers, and RW is the parameter space. The parameter space RRW is implicitly defined by all weight matrices A' and bias vectors b' for i E [L + 1] within the neural network. Each function No (x, w) defined for any x E R and E IR as
Nº (x, w) = T (T( ...))).
where each Т; is affine transformation that depends For the hidden layers, employ the ReLU activation, while the last layer uses the Softmax activation, consistent with treating heuristic learning a classification task.

---

Published as a conference paper at ICLR 2026
ReLU:
The Rectified Linear Unit (ReLU) activation ReLU IR Rz0 is given by (e) = max(0, x}.
Softmax: The Softmax activation TR + (0, 1)
is applied coordinatewise: exp(x;;) Σラ= exp(xy)
Softmax(z;)
i= I...,,
The parameterization induced by the neural network No is shown as s No. where a is the hidden-layer activation function and o' is the activation function in the final layer. This gives rise to
the performance class U {un: II - H0 h 1h=4pt =p No.e' E RR). In the following theorem, we derive Pdim((4).
Theorem 5. Let G be graph with [VI and let P be PDB dulaset over G whose induced graph has size m. Assume satisfies Assumption 4, and let + [0, DJ be a heuristic function trained via neural network. Then, Pdim(U) (n). Moreover, if h is trained on P. it follows that Pdim(())= = ((m).
The bound in Theorem depends on the size of the graph, which may be large. Ideally, we want to leverage neural networks obtain tighter bound in terms of the network's s size. The proposed approach from Balcan et al. (2021a) is not guaranteed to remain valid under neural network's parameterization. So, we first define representation function and then derive a bound on Pdim(U)) that accounts for the parameters of the neural network.
Definition 3.
For each instance I E I. we define a representation function Rep(I) = x, where is the feature vector fed into the neural network. This representation encompasses all relevant features of an instance, including any common across instances.
Our definition of Rep(!) must encompass all the information required to find path from the start state to the goal. However, we cannot simply include all states in each instance, since computing h for all states is itself the ultimate goal of training. Instead, for each instance, states encountered by running a search from the start state for that instance to the goal using h This approach allows to capture only the necessary data without relying all possible states.
include set B of
Theorem 6. Let G be graph with |V|= n, and let P be a PDB dataset over G whose induced graph has size m. Assume G satisfies Assumption 4, and let h V [0, D) be heuristic function trained via a neural network. Then, Pdim(lf) (LW log (U f) + log (L 1))). Moreover, if h is trained on P, it follows that Pdim(U) = O (LW log (U + e') + Wlog (f') (T (1))
Instance-dependent framework. So far, analysis of sample complexity has focused heuristic functions that can be used for all instances, under the assumption that each instance shares the same goal state, and thus the same heuristic values. However, we can also view instances Sinà pairs, where changing the goal requires a different heuristic. To address this, we adopt neural networks as the learning framework, enabling heuristic values that adapt to instanc--ppecific features.
Theorem 7. Let be a gruph with [V] n, and gruph has size Assume that G satisfies Assumption 4, and let h V + [0, D] be a heuristic function trained via neural network, capable of estimating heuristic values for varying goal G. Then, Pdim(()) O (LW log (U + E) W log (nLL 1))). Moreover, h is trained on P. it follows that Pd) = (LW log (U + (') W log (e') ['[mmL[ 1))).
be a PDB dataset over G whose induced
TRAINING FRAMEWORK
Our goal is to learn a heuristic that can be queried many times during A search while satisfying three key requirements: (1) Perfect admissibility: the heuristic must satisfy h(s) S hi' (s) for every state & E V: (2) High average value: among admissible heuristics, those with higher mean values, defined as [ST Exes (sss,, provide stronger guidance for search; and (3) Fast inference: the size of the model to calculate h. denoted as [f], should be as small as possible to minimize per-call latency and memory overhead during search. These objectives can be expressed as the optimization problem
7

---

Published as a conference paper at ICLR 2026
max
1 S
Σ h(s) SES
s.t. 1 (Vs S),
[h] is minimized.
(4)
Framing the Task Ordinal Classification. Under Assumption 4 the problem can be treated as classification task where each heuristic value 0, ,...., forms a class. The cross-entropy (CE) loss,
exp(xk (
(8) log Pk
(8)
CE =
Vk
Pk
Σj=1 )
optimises accuracy but ignores the order among classes and treats under- and over-estimation equally. Because we prefer underestimation to overestimation, we introduce new loss function called Cross-Entropy Admissibility (CEA):
N
CEA
log
(3) Pk
+ n1 log log (0)
(5)
N
R
The first term reallocates probability mass to all classes & < hC;: the weight (k//tt)* decreases as k moves farther below the true class. The parameter /3 > 0 balances admissibility (smaller (9) against heuristic strength (larger (3). The second term is CE penalty, scaled by r, that sharpens the distribution around the true class. It discourages the model from assigning high probability to an inadmissible class even when most mass lies on admissible ones. Choosing
that 7j maintains the dominance of the first (admissibility) term while still penalizing low probability on the true class.
(5) for every sample, fulfilling both With this loss, the unique global optimum is achieved when Piç admissibility and maximal average heuristic.
Delta heuristic. PDBs can have imbalanced distributions of states and heuristic values. In the 6-edge Rubik's s-Cube PDB, more than 86% the states fall in classes and 8. Because these classes have large heuristic values, model that over-predicts them is likely violate admissibility states with lower heuristics. This can be improved using a delta heuristic ha (Sturtevant et al., 2017) Instead of storing distances in single PDB, we store small base PDB with pattern that a subset of the full PDB and store only the difference between these PDBs A = Marge /hase- At inference time, the final heuristic reconstructed Marge (s) Musse (s) A (s). Table (Appendix G) shows that subtracting a 4-edge PDB from the 6-edge PDB significantly shifts the class imbalance.
5 EXPERIMENTS
In this section, we aim to answer the following key questions: (1) How effective is the proposed training framework in learning strong admissible heuristics? (2) How robust is the proposed loss function to hyperparameter choices? (3) What is the trade-off between model complexity and the strength of the learned heuristic? (4) How does the bound generalization error behave as the number of training instances increases?
To evaluate these questions, we focus the 3 x 3 Rubik's Cube, where, to our knowledge, no previous machine learning methods have learned an admissible heuristic. We selected four PDBs with distinct characteristics: 8- 8-Corner, A(6, 4) -))4)e 6 6-Edge, and 7-Edge. All PDBs soureed from the HOG2 repository'. The summary statistics for the PDBs are presented in Table 1, and the complete heuristic distributions are provided in Table 3 (Appendix G). For learning heuristic models, we adopt a neural network architecture based on the ResNet model (He et al., 2016). A complete description of the model architecture and the selected hyperparameters presented in Appendix G.
'https://4 http:://wg....ccco.aaaaaatttt/t/
8

---

Published as a conference paper at ICLR 2026
Training and Sampling Strategy. Looking the PDB heuristic distributions in Table 3 (Ap- pendix G), there is a massive class imbalance in all PDBs. we uniformly sample training batches, the model overfits the most populated classes. To avoid this, we handle imbalance the sampling stage. Mini-batches are constructed by uniformly sampling within each heuristic class, and the number of sampled states from each class is proportional to its size. Our setting also differs from standard supervised learning. In a typical setup, we train on a subset and aim to generalize to a small test set that represents much larger unseen population. Here, each PDB contains all states of graph, and a ranking function maps every Rubik's 's Cube state uniquely to a PDB state. If model predicts an admissible heuristic for every state the PDB, we obtain a fully admissible heuristic for Rubik's s Cube. Therefore, the goal is to compress the information in this large dataset into small model while losing as little information as possible. full dataset for fixed number of epochs. Many individual states are never seen during training, due to both dataset size and randomness in sampling, but training still reflects the full data distribution.
this end, we sample training batches from the
Post-hoc weight pruning. One of the constraints in Equation 4 is the model size |/l, since fast heuristic evaluation during search is essential. A common approach for improving inference efficiency is post-hoc weight pruming and related compression techniques (Han et al., 2015; Micikevicius et al., 2017; Krishnamoorthi, 2018) 8). In our work, we adopt a simple but effective variant: we train all models in 32-bit precision but perform inference in 16-bit precision, substantially reducing latency during search. We also experimented with 8-bit quantized inference; however, the accuracy loss was significant, so we chose not to consider it further.
Table I: Summary statistics for the PDBs.
PDB 4-edge
Avg. Heuristic
Number of States
PDB Size (MB)
6.75
3,041,280 42,577.922 ,920
1.52
6-edge
7.65
21.29
8-corner
8.76
88,179,840 510,935,040
44.09
7-edge
8.51
255.47
Table 2: Comparison between learned neural network heuristics and compressed PDBs.
Heuristic Type
Pattern
Avg. Heuristic
Overestimation Rate
Model Size (MB)
Compression Rate
NN CEA loss
7.45
2 10-5
3.75
68.12x
NN + CE loss
7-edge
8.44
1.4 x 10-2
3.75
68.12x
Compressed PDB
6.83
3.65
70.00
NN + CEA loss
8.76
3 10-7
1.89
23.32
NN CE loss Compressed PDB
8-corner
8.76
2 x 10-3 0
1.89
23.32 x
6.84
1.91
23.00
NN + CEA loss
6.92
9 x 10-5
1.95
10.91 x
NN CE loss
6-ddge
7.46
9 10-2 0
1.95
10.91 x
Compressed PDB
6.68
1.93
11.03x
NN + CEA loss
1.31
3 10-6
3.20
6.65
NN CE loss
1.89
15 10
3.20
6.65x
Compressed PDB
1.05
0
3.04
7.00x
Evaluating Learned Heuristics. We compare the heuristic learned with CEA loss function against two baselines: (1) the learned heuristic using CE loss, and (2) compressed PDB constructed using the min compression technique. The compression factor was chosen so that the compressed PDB and both NN models occupy the same amount of memory. For the NN models, hyperparameters and allocated the same number of training epochs for both loss functions. The CEA-specific parameters, and 1), tuned per model; Appendix J details general tuning procedure applicable to any model.
used the same
The most critical property of learned heuristic for achieving optimality is its overestimation rate, which should ideally be zero. However, assigning zero to all states, though admissible, offers no useful guidance. Our goal, therefore, is to learn heuristic that is both admissible and highly

---

Published as a conference paper at ICLR 2026
informative. Our results are summarized in Table 2. We achieved overestimation rate which is nearly zero, indicating a fully admissible heuristic, for the 8-comnr and A 4)-Edge PDBs, and only a few thousand overestimated states for the 6-edge and 7-edge PDBs. The CEA loss achieved fully admissible heuristic in the 8-corner PDB while matching the average heuristic of the original PDB, demonstrating information loss. Across all PDBs, the overestimation rate for our loss function is nearly 10 x smaller than that obtained with the CE loss. The comparison of the distributions of overestimated states for both loss functions across all PDBs presented in Figures 6- 9 in Appendix H. These findings suggest that CE loss is ill-suited for learning admissible heuristics in domains satisfying Assumption 4, where the heuristic learning problem can be formulated as a classification task. We attribute the challenges faced by the CE loss in learning admissible heuristics to two main factors: (1) the dataset's large size and (2) the sparse representation each state, which includes only the location and rotation of each cubie. In deep learning classification tasks for large datasets (Sun et al., 2017), there are usually no constraints on model size, and the representation for each state is richer.
Compared to a compressed PDB built with the min-compression technique, CEA achieves a signifi- cantly higher average heuristic on all PDBs, even though a few thousand overestimated states remain in the 6-edge and 7-edge cases. This suggests that CEA preserves more information than classical compression methods such min-compression. For the 8-corner PDB, when the learned model is used in search to assess its strength, the number of nodes generated was less than half of that for the size-matched compressed PDB heuristic (Futuhi & Sturtevant, 2025). To evaluate how far we can reduce model size while maintaining admissibility and accuracy, we conduct an experiment on the 8-corner PDB (Appendix 1). Remarkably, we achieve a 51x compression relative to the original PDB while maintaining performance comparable to the results in Table 2.
Empirical analysis of the generalization error. Up
generalization error vs N
to this point, our experiments have focused on the final overestimation rate of the learned heuristic. Since our sample-complexity analysis establishes a relationship be- tween the generalization error term and the number of
generalizate Ineralization erer
1.75
1.50
1.25
1.00
0.75
training instances, we conduct an additional experiment to empirically examine this behavior. Specifically, we evaluate how the generalization error associated with the inadmissibility functions in Theorem 4 changes with num- ber of training instances. Figure presents the results for 8-corner PDB. We observe that the generalization error decreases the number of training instances N increases, following a sublincar decay pattern that aligns with the
0.50
0.00
40
60
N (millions)
Figure 2: Generalization error vs. train-
ing size for the 8-comner PDB.
theoretical rate of Ō ( ((n + log(1/6))/N). This confirms the expected 1/vN decay predicted by our sample-complexity analysis.
6 CONCLUSION AND FUTURE WORK
This paper lays foundation for learning admissible heuristics that are both effective in practice and backed by theory. We formulate heuristic learning as an optimization problem with explicit constraints on model size, heuristic strength, and admissibility. We introduce Cross- Eatos-- Admissibility (CEA), loss that improves accuracy while directly penalizing any admissibility error. In experiments on 3 x 3 Rubik's s-Cube PDBs, CEA reduced the ratio of inadmissible states to below 10 6 and matched or outperformed classical compression techniques On the theory side, we tightened the sample- complexity bounds by leveraging the exponential reduction offered by PDB abstractions and the graph structure commonly seen in heuristic-searde tasks. When the hypothesis class is restricted to neural networks, the bound depends primarily network depth and width rather than graph size. We provide the first generalization guarantees for goal deaendennndn heuristics. We also introduce a new bound on expected suboptimality using the maximum inadmissibility encountered at any state on the optimal path. The focus of future work will be on finding the most effective ways adapt both search and learning work together while providing solution quality guarantees.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENTS
This work was supported by the National Science and Engineering Research Council of Canada Discovery Grant Program and the Canada CIFAR AI Chairs Program.
REFERENCES
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):356-363, 2019.
Forest Agostinelli, Stephen McAleer, Alexander Shmakov, Roy Fox, Marco Valtorta, Biplav Sri- vastava, and Pierre Baldi. Obtaining approximately admissible heuristic functions through deep reinforcement learning and A search. In Bridging the Gap between AI Planning and Reinforcement Learning, 2021.
Forest Agostinelli, Shahaf Shperberg, Alexander Shmakov, Stephen McAleer, Roy Fox, and Pierre Baldi. Q search: Heuristic search with deep q-networks. 2024.
Alberto Archetti, Marco Cannici. and Matteo Matteucci. Neural weighted a:: Learning graph costs and heuristics with differentiable anytime a. In International Conference on Machine Learning, Optimization, and Data Science, pp. 596-610, 2021.
Patrick Assouad. Densité et dimension. Ann. Inst. Fourier, 33(3):233-282) 1983.
Maria-Florina Balcan, Dan DeBlasio, Travis Dick, Carl Kingsford, Tuomas Sandholm, and Ellen Vitercik. How much data is sufficient to learn high-performing algorithms? Generalization guarantees for data-driven algorithm design. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2021), pp. 119-932. ACM, 2021a.
Maria-Florina Balcan, Siddharth Prasad, Tuomas Sandholm, and Ellen Vitereik. Improved sample complexity bounds for branch-and-cur. In 28th International Conference on Principles and Practice of Constraint Programming, 2022.
MariiaFForina F Balcan, Siddharth Prasad, Tuomas Sandholm, and Ellen Vitercik. Sample com- plexity of tree search configuration: Cutting planes and beyond. Advances in Neural Information Processing Systems, $4:4015-4022 2021b.
Peter Bartlett, Vitaly Maiorov, and Ron Meir. Almost linear ve dimension bounds for piecewise polynomial networks. Advances in neural information processing systems, 11, 1998.
Rafael Bettker, Pedro Minini, André G Pereira, and Marcus Ritt. Understanding sample generation strategies for learning heuristic functions in classical planning. Journal of Artificial Intelligence Research, 80:243-221 271, 2024.
Dillon Z Chen, Sylvie Thićbaux, and Felipe Trevizan. Learning domain-independeer heuristics for grounded and lifted planning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. (0078-00066,, 2024a.
Dillon Z Chen, Felipe Trevizan, and Sylvie Thiébaux. Return tradition: Learning reliable heuristics with classical machine learning. Proceedings of the International Conference on Automated Planning and Scheduling, volume 34, pp. 68-76, 2024b.
Dillon Z. Chen, Johannes Zenn, Tristan Cinquin, and Sheila A Mcllraith. Language models for generalised pddl planning: Synthesising sound and programmatic policies. arXiv preprint arXiv:2508. 18507, 2025.
Dillon Ze Chen, Sylvie Thiébaux, and Felipe Trevizan. Goose: Learning domain-independdnt heuristics. In NewrIPS 2023 Workshop on Generalization in Planning, 2023.
Hongyu Cheng, Sammy Khalife, Barbara Fiedorowicz, and Amitabh Basu. Sample complexity of algorithm selection using neural networks and its applications to branch-and-cut. In The eighth Annual Conference Neural Information Processing Systems.

---

Published as a conference paper at ICLR 2026
Sanjiban Choudhury. Mohak Bhardwaj. Sankalp Arora, Ashish Kapoor, Gireeja Ranade, Sebastian Scherer, and Debadeepta Dey. Data-driven planning via imitation learning. The International
Journal of Robotics Research, 37(13-144:16322165) 2018.
Leah Chrestien, Tomas Pevny, Antonin Komenda, and Stefan Edelkamp. A differentiable loss function for learning heuristics a. arXiv preprint arXiv:2209.05206 2022.
Leah Chrestien, Stefan Edelkamp, Antonin Komenda, and Tomas Pevny. Optimize planning heuristics to rank, not to estimate cost-to-goal. Advances in Neural Information Processing Systems, 36, 2024.
Joseph C Culberson and Jonathan Schaeffer. Pattern databases. Computational Intelligence, 14(3): 318-334, 1998.
Ariel Felner, Richard E Korf, Ram Meshulam, and Robert C Holte. Compressed pattern databases. Journal of Artificial Intelligence Research, 30:213-247, 2007.
Ariel Felner, Uzi Zahavi, Robert Holte, Jonathan Schaeffer, Nathan Sturtevant, and Zhifu Zhang. Inconsistent heuristics in theory and practice. Artificial Intelligence, 17500-10)1150--1603 2011
Dieqiao Feng, Carla P Gomes, and Bart Selman. Left heavy tails and the effectiveness of the policy and value networks in dnn-based best-first search for sokoban planning. Advances in Neural Information Processing Systems, 35:36295-36307, 2022.
Patrick Ferber, Malte Helmert, and Jörg Hoffmann. Neural network heuristics for classical planning: A study of hyperparameter space. In ECA/ 2020, pp. 2346 2353. IOS Press, 2020.
Patrick Ferber, Florian Geißer, Felipe Trevizan, Malte Helmert, and Jörg Hoffmann. Neural network heuristic functions for classical planning: Bootstrapping and comparison to other methods. In Proceedings of the International Conference on Automated Planning and Scheduling, volume 32, pp. 583,587, 2022.
Ehsan Futuhi and Nathan R Sturtevant. A parallel cpu-gpu framework for batching heuristic operations in depth- first heuristic search. arXiv preprint arXiv:2507.11916 2025.
Caelan Reed Garrett, Leslie Pack Kaelbling, and Tomás Lozano-Pére: Learning to rank for syn- thesizing planning heuristics. In Subbarao Kambhampati (ed.), Proceedings of the Twenty-Fifth International Join! Conference Arlificial Intelligence, IJCAI 2016, New York, NY, USA, 9- 15 July 2016, pp. 3089-3095. LUCAV/AAI Press, 2016. URL http: /www ijcai org/ Abbstrac/16// 438.
Pawel Gomoluch, Dalal Alrajeh, Alessandra Russo, and Antonio Bucchiarone. Learning neural search policies for classical planning. In Proceedings of the International Conference on Automated Planning and Scheduling, volume 30, pp. 522 530. 2020.
Matias Greco, Pablo Araneda, and Jorge A Baier. Focal discrepancy search for learned heuristics. In Proceedings of the International Symposium on Combinatorial Search, volume 15, pp. 282-284, 2022.
Song Han, Huizi Mao, and William J Dally. Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding. arXiv preprint 15 49, 2015.
Mingyu Hao, Felipe Trevizan, Sylvie Thiébaux, Parick Ferber, and Jörg Hoffmann. Learned pairwise rankings for greedy best-first search. In Proc. ICAPS Workshop on Reliable Data-Drive Planning and Scheduling, 2024.
Peter E Hart, Nils Nilsson, and Bertram Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE transactions on Systems Science and Cyberneties, 4(2): 107, 1968.
Patrik Haslum, Blai Bonet, Héctor Geffner, et al. New admissible heuristics for domain-indeppenden planning. In AAAI, volume pp. 9-13, 2005.
Rishi Hazra, Pedro Zuidberg Dos Martires, and Lue De Raedt. Saycanpay: Heuristic planning with large language models using learnable domain knowledge. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 20123-20133 2024.
12

---

Published as a conference paper at ICLR 2026
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Daniel Heller, Patrick Ferber, Julian Bitterwolf, Matthias Hein, and Jörg Hoffmann. Neural network heuristic functions: Taking confidence into account. In Proceedings of the International Symposium on Combinatorial Search, volume 15, pp. 223-228, 2022.
Malte Helmert, Nathan Sturtevant, and Ariel Felner. On variable dependencies and compressed pattern databases. In Proceedings of the International Symposium Combinatorial Search, volume 8, pp. 129-133, 2017.
Malte Helmert, Tor Lattimore, Levi H. S. Lelis, Laurent Orseau, and Nathan R. Sturtevant. Iterative budgeted exponential search. International Joint Conference on Artificial Intelligence (ICAI), 2019. URL htttps:/wwebdose
cs haaleertaacc///netheeetttttt wwwpaaannttppppppppeeesse BBBEEe///BBBB... pdf.
ca/
Sukai Huang, Trevor Cohn, and Nir Lipovetzky. Chasing progress, not perfection: Revisiting strate- gies for end-to-ent LLM plan generation. In Proceedings of the 35th International Conference on Automated Planning and Scheduling (ICAPS), Melbourne, Victoria, Australia, November 2025.
Michael Katz and Emil Keyder. A search and bound-sensitive heuristics for oversubscription planning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 9813-9820, 2022.
Soonkyum Kim and Byungchul An. Learning heuristic a: Efficient graph search using neural network. In 2020 IEEE International Conference on Robotics and Automation (ICRA), pp. 9542-9547. IEEE, 2020.
Danii Kirilenko, Anton Andreychuk, Aleksandr Panov, and Konstantin Yakovlev. Transpath: Learn- ing heuristics for grid- pathfinding via transformers. Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pp. 12436-12443, 2023.
Richard E Korf. Finding optimal solutions rubik's cube using pattern databases. In AAAI/IAAI, pp- 700-705, 1997.
Raghuraman Krishnamoorthi. Quantizing deep convolutional networks for efficient inference: A whitepaper. arXiv preprint 1xX.v:8806.08344 2018
Levi Lelis, Richard Valenzano, Gabriel Nazar, and Roni Stern. Searching with a corrupted heuristic. Proceedings of the International Symposium on Combinatorial Search, 7(1):63-71, Sep. 2021. doi: 10. wot.://ooooo7..1333033 URL https: /ojjs aaai. aaaai.org//aeee /ergg//iin wiw/x.indnx////////// phpp SSC///OCSS///// http://sss/ariiiicccccc artiile/ view/18394
Tianhua Li, Ruimin Chen, Borislav Mavrin, Nathan Sturtevant, Doron Nadav, and Ariel Felner. Op- timal search with neural networks: Challenges and approaches. In Proceedings of the International Symposium on Combinatorial Search, volume 15, pp. 109-117, 2022.
Alberto Martelli. On the complexity of admissible search algorithms. Artificial Intelligence, 8(1): 1-13, 1977.
Silin Meng, Yiwei Wang, Cheng-Fu Yang, Nanyun Peng, and Kai- Wei Chang. LLM-A Large language model enhanced incremental heuristic search on path planning. In Yaser Al-Onaizan, Mohit Bansal, and Yun-Nung Chen (eds.), Findings of the Association for Computational Lin- guisties: EMNLP 2024, Miami, Florida, USA, November 12-16, 2024, pp. 1087-1102. Asso- ciation for Computational Linguistics, 2024. URL https: /tt///clccc/ hol www.oollyooooooooooooooooo// org/2024. findi merdings-emmlpe 60.
Paulius Micikevicius, Sharan Narang, Jonah Alben, Gregory Diamos, Erich Elsen, David Garcia, Boris Ginsburg, Michael Houston, Oleksii Kuchaiev, Ganesh Venkatesh, et al. Mixed precision training. arXiv preprint arXiv: 17100.77,, 2017.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning.
MIT Press, second edition, 2018
13

---

Published as a conference paper at ICLR 2026
Wendy Myrvold and Frank Ruskey, Ranking and unranking permutations in linear time. Information Processing Letters, 79(6):281-288 2001.
Danilo Numeroso, Davide Bacciu, and Petar Veličković. Learning heuristics for a. arXiv e-prints, pp. arXiv-2208 2022.
Carlos Núfez-Molina, Masataro Asai, Pablo Mesejo, and Juan Fervández-Olivares. On using admissible bounds for learning forward search heuristics. In Proceedings of the Thirty-Thine International Joint Conference on Artificial Intelligence, IJCAI 2024, Jeju, South Korea, August 3- 9, 2024, pp. 6761-6769. ijeai.org. 2024. URL https: /tpp:///wwwe www.. ijcai wtt. httg///occeeenns..oooo 2024/747.
Peter Orlik and Hiroaki Terao. Arrangements of hyperplanes, volume 300. Springer Science & Business Media, 2013.
Laurent Orseau and Levi HS Lelis. Policy-guided heuristic search with guarantees. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 12382-12390, 2021.
Laurent Orseau, Marcus Hutter, and Levi H. Lelis. Levin tree search with context models. In Edith Elkind (ed.), Proceedings of the Thirly-Second International Join! Conference Artificial Intelligence, IJCAI-23, pp. 5622-5630. International Joint Conferences on Artificial Intelligence Organization, 8 2023. doi: 00.24963/jcaii222336663 URL httph::////// wtt.oooooo......ee...
ijjcai 2023 624,
Main Track.
Michal Pándy, Weikang Qiu, Gabriele Corso, Petar Veličković, Zhitao Ying, Jure Leskovec, and Pietro Liò. Learning graph search heuristics. In Learning on Graphs Conference, pp. 10-1. PMLR, 2022.
David Pollard. Convergence of Stochastic Processes. Springer, first edition, 1984.
Shinsaku Sakaue and Taihei Oki. Sample complexity of learning heuristic functions for greedy- best-first and A search. Advances Neural Information Processing Systems, 35:2889-229 2901, 2022.
Mehdi Samadi, Maryam Siabani, Ariel Felner, and Robert Holte. Compressing pattern databases with learning. In Proceedings of the 2008 Conference on ECA/ 2008: 18th European Conference on Artificial Intelligence, pp. 495-499, NLD, 2008. IOS Press. ISBN 978 9781586038915.
Julian Schrittwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, et al. Mastering atari, go, chess and shogi by planning with learned model. Nature, 588(7839):604-609) 2020.
Jendrik Seipp. Dissecting scorpion: Ablation study of optimal classical planner. In ECAI 2024,
pp. 39-42. IOS Press, 2024.
William Shen, Felipe Trevizan, and Sylvie Thiébaux. Learning domain-independent planning heuristics with hypergraph networks. In Proceedings of the International Conference on Automated Planning and Scheduling, volume 30, pp. 574-584, 2020.
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. nature, 550(7676)3354-3333 359, 2017.
Nathan Sturtevant, Ariel Felner, and Malte Helmert. Value compression of pattern databases. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017.
Chen Sun, Abhinav Shrivastava, Saurabh Singh, and Abhinav Gupta. Revisiting unrea- sonable effectiveness of data in deep learning era. Proceedings of the IEEE Inter- national Conference on Computer Vision (ICCV), pp. 843-852, 2017. URL https: //openaccess thecvf. com/ wtt.tttett_coo_1111/aaee Unreasonable__ffeeee www.iveeesseeeevveeeeee ICC__Iccv____ hac_aaaoocoooo_eee__eeee paper html.
Sun Revisiting
Richard S Sutton. Learning to predict by the methods of temporal differences. Machine learning, 9-44, 1988.
14

---

Published as a conference paper at ICLR 2026
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open foundation and fine-tuned chat models. arXiv e-prints, pp. 2tXiv
Jes ús Virseda, Daniel Borrajo, and Vidal Alcázar. Learning heuristic functions for cost-based planning. Planning and Learming, 4, 2013.
Richard Valenzano, Nathan Sturtevant, and Jonathan Schaeffer. Worst-case solution quality analysis when not re-expanding nodes in best-first search. Proceedings of the AAAI Conference on Artificial Intelligence, volume 28, 2014.
Rishi Veerapaneni, Muhammad Suhail Saleem, and Maxim Likhachev. Learning local heuristics for search- based navigation planning. In Proceedings of the International Conference on Automated Planming and Scheduling, volume 33, pp. 634 638, 2023.
Rishi Veerapaneni, Jonathan Park, Muhammad Suhail Saleem, and Maxim Likhachev. data efficient framework for learning local heuristics. In Proceedings of the International Symposium on Combinatorial Search, volume 17, pp. 223-222-- 227, 2024.
Peter Wurman, Samuel Barrett, Kenta Kawamoto, James MacGlashan, Kaushik Subramanian, Thomas J Walsh, Roberto Capobianco, Alisa Devlic, Franziska Eckert, Florian Fuchs, et al. Outracing champion gran turismo drivers with deep reinforcement learning. Nature, 602(7896): 223-228, 2022.
Ryo Yonetani, Tatsunori Taniai, Mohammadamin Barekatain, Mai Nishimura, and Asako Kanezaki. Path planning using neural A search. In International conference on machine learning, pp. 12039, PMLR, 2021.
Liu Yu, Ryo Kuroiwa, and Alex Fukunaga. Learning search-space specific heuristics using neural network. In ICAPS Workshop Heuristics and Search for Domainindependen Planning, pp. 1-8,
2020.
15

---

Published as a conference paper at ICLR 2026
Appendix
CONTENTS
Related Work
16
B Pseudocode for the A Algorithm
17
Comparing the PDB Abstraction to the Full Graph
18
Proofs for Heuristic Functions in R"
18
E Expected suboptimality of A* with reopenings
19
Proof of theorems using neural networks
21
Experimental Setup
25
G.1 State Representation
25
Overestimation Distribution
25
I Model Size Heuristic Quality
26
J Dynamics of (8, During Training
26
A RELATED WORK
There has been significant effort to learn good heuristics for heuristic search algorithms (Chen et al.,
2023; Numeroso al., 2022; Greco et al., 2022; Chen et al., 2024b; Ferber et al., 2020; Yu et al.,
2020; Kim & An, 2020; ús Virseda et al., 2013; Heller et al., 2022; Agostinelli et al., 2019; Kirilenko al., 2023; Chen al., 2024a; Hao al., 2024; Bettker et al., 2024). One branch of work uses Graph Neural Networks to better learn the heuristic function by exploiting the graph structure of the problem (Pándy et al., 2022; Shen et al., 2020). heuristic search problems, the heuristic value of a state can often be approximated from its neighbors' values, they differ only by the cost of the connecting edge. Consequently, one can employ bootstrapping methods such as TD-Iearing (Sutton, 1988) to learn the heuristic value for each state (Ferber al., 2022: Agostinelli al., 2024). Veerapaneni et al. (2023) take a different approach than learning the global cost-to-go values, since these can be time-consuming train and difficult generalize new problems. Instead, Veerapaneni al. (2023) train local heuristics that estimate the cost to escape from small regions for the robot, and later combine these local heuristics with global heuristic to reduce node expansions. Because data collection for the local heuristic can be slow for large graphs, Veerapaneni et al. (2024) propose an efficient data collection approach that leverages the combinatorial nature tasks. Another branch of work considers directly learning the policy that decides which node to expand next rather than learning heuristic values (Orseau & Lelis, 2021: Gomoluch et al., 2020; Feng et al., 2022; Choudhury al., 2018). For instance, Choudhury et al. (2018) train policy using imitation learning that bases its decisions solely on the portion of the search space uncovered so far.
Garrett al. (2016) propose focusing the ordering of states induced by the heuristic, rather than learning exact heuristic values. They employ Rank Support Vector Machines (RankSVM) by using the number of incorrectly ordered pairs of states in each problem the loss function. Later on, Chrestien et al. (2024) provide theoretical proof that training heuristic functions to produce correct rankings is sufficient for optimal performance, and explain why learning the exact cost-to-go values
16

---

Published as a conference paper at ICLR 2026
State Space
State Space
8-corner PDB
8-comerr PDB
Abstract
State
90 clockwise
A(A) =
quarter turn
quarter tur
(11) = (KB) (CC) S min(A(A), A(B))
State B
kBB
90" anti clockeiie
Figure 3: Comparison between the full state- space graph of the 3 x 3 Rubik's 's Cube and the abstraction generated using only the eight corner cubies.
Algorithm A algorithm
1: OPEN = {smatt CLOSED 0, Parent (Smitt) = null and g = 0.
2: while OPEN is not empty
3: f (argmin(g(v)) h(v)lu e OPEN]
> selection step.
4: if
goal
5:
return solution path using (arent(s) recursively.
6:
for each child 5 sf
7:
Inew + -s(s) + c(s,s'). if s' & OPEN CLOSED:
8:
9:
g(s') t Jnew, and OPEN +- OPEN U (s'}.
10:
else if s' OPEN and Inew < g(8):
11:
g(s') + Inew and Parent(s)) + 8.
else if s' CLOSED and Inew g(s'):
13:
g(s') + Juew and Parent (s' + S.
Move s' from CLOSED OPEN.
node reopening.
15:
Move s from OPEN to CLOSED.
via mean-squared error regression can be unnecessarily difficult; their experiments on a wide range of tasks also show that ranking-based based loss functions outperform regression-based ones. Subsequently. Chrestien et al. (2022) propose the L* loss, which upper-bounds the number of expanded nodes by ensuring that states the optimal path have lower heuristic values than those off it. Li et al. (2022) and Agostinelli et al. (2021) investigate the admissibility of learned heuristics, guaranteeing full and approximate admissibility, respectively. Moliz-MMliia al. (2024) model the learned heuristic as a Truncated Gaussian, with admissible heuristic serving the lower bound. Balcan et al. (2021a) introduce theoretical framework that provides generalization guarantees for data-driven algorithms by bounding the performance gap between training data and unseen data for algorithms relying on learned parameters. This framework is further applied to establish sample-complexity bounds for general tree-search algorithms (Balcan et al., 202 2022) and for GBFS/A* (Sakaue & Oki, 2022). Cheng et al. address the sample complexity of branch-and-on problems by modeling the parameter space with neural networks. They also derive sample complexity bound for learning instance-dependent parameters.
B PSEUDOCODE FOR THE A ALGORITHM
In this section, we provide overview of the general procedure of AJ, shown in Algorithm
17

---

Published as a conference paper at ICLR 2026
C COMPARING THE PDB ABSTRACTION TO THE FULL GRAPH
Figure 3 compares the abstracted state space (8-corner PDB) with the main graph and highlights Iwo basic properties. First, all states in the main graph that map the same abstract state receive the same heuristic value-namely, the shortest-path distance in the abstracted space to the abstract goal-whise
a lower bound on their true distances; thus admissibility is guaranteed. Second, if two states are connected by move in the main graph, then their images in the abstracted space are either the same state or adjacent states by the same move, so connectivity is preserved under the abstraction.
D PROOFS FOR HEURISTIC FUNCTIONS IN R"
In this section, we provide proofs for theoretical results that assume h R".
Proof of Lemma 1. Suppose we have two heuristic functions h and h' that satisfy the condition of Lemma 1. Consider two states i and By such that 4J, selects vs for expansion before vy. By definition of the selection rule, this implies one of the following:
1. g(v)) + h(e,) < g(0;) + h(0;),
2. g(v)) + h((:) = g(wy) + h(vz)) and, under the tie-breaking rule specified by Assumption 2,
A% chooses vn over U/.
In either case, we derive: g(v;) + h(u;) - h(e;)) < g(u;). By Lemma 1, we have h(v;) - h((r)) =
h' (((v)) h((u,). Substituting this into the above inequality gives
g(v.) N'(w)) h'(,,) S g(0y) = g(v:) + h(())) S 9(0y) + hwy)).
Hence, under Aj. the same selection decision is made, choosing v; instead of Since this reasoning applies to all selection steps, A% and A% perform identical, implying un (z) uw (x) for every r E II.
Proof of Theorem 1. From Lemma 1, any two heuristic functions that induce the same pairwise value differences for every pair of vertices in V result in identical performance. Our aim is thus to partition Rn into regions which the relative differences h(v;) - h((;;) remain consistent for all vertex pairs (va, Uj), guaranteeing the same performance for any E II. Recall that vertices in the open list OP EN are ranked by their f values, where f(v) = g(v) + h(v). Under Assumption with co = 1, consider scenario in which (
2 and g(u2) 4. Then any heuristic satisfying h(v1) h(02) 2 2 will favor 2j over U/ in OPEN. However, suppose a different instance or an update in the search reduces g(1)) ) from 2 to 1. In this case, h(va) h(v2) 3.5 favors on, whereas h(v)) - h(02) 2.5 favors U2, even though both heuristic differences exceed 2. To capture all such distinctions, we consider 2n hyperplanes for each ordered pair vy):
h(())) h(v;) tlen, #200
Between any two of these hyperplanes, the ordering between vi and considdeiiin all feasible g()) values-remaine unchanged. Above a boundary hyperplane such h(v;)) f((1,) noo. no further hyperplanes are necessary, since values cannot exceed neg. Consequently, we have in total 2n (2) hyperplanes. By the Shi arrangement (Orlik & Terao, 2013), these hyperplanes partition T.th into ((2n+ + 1)") regions. Each region corresponds to unique assignment of heuristic differences for all vertex pairs, which in turn induces unique ranking of vertices in OPEN, thus unique performance outcome on any instance æ E 11. To shatter instances, we require at least 2 such unique (Ma, MZz:.... ..., x tuples; hence, ((2n + 1)*) 2 2 Solving for the largest N in terms of n yields the upper bound Pdim On log
Proof of Theorem 2. The dataset partitions the set V of n vertices into m groups Mr,M2,.. Mms each containing vertices that correspond 0; quently, the trained heuristic satisfies h(v;)) = h(v,) V v, Uy E M for any M E P. To compute
the same abstract state. Conse-
P2)m((I), one might naively substitute m for n in Theorem 1; however, the g values still come from G. so there remain 2n hyperplanes for any pair of vertices. Total number of hyperplanes is 2n (*)
18

---

Published as a conference paper at ICLR 2026
because there groups, and all vertices within the same group have the same g cost. These hyperplanes partition the space R" into ((2n + 1)"" regions. To shatter N instances, we require at least 2d such regions. Setting ((2n + )) z 2 and solving for N in terms of n yields Pdlm((()) = O (m log
To compare the bound achieved by PDB dataset with the one in Theorem 1, we need to examine the effect of replacing the main graph G with the PDB graph P. In the worst-case scenario, where the PDB does not abstract away any features (i.c., G [P] or m n), there is no improvement over the On log n)) bound. However, PDBs often yield an exponential reduction in the size of the graph, so that m = V.) In this case, the resulting bound improves to O v log n.). For instance, in exponential state space with branching factor and depth d, where bd, the root index is bounded by (dd)
E EXPECTED SUBOPTIMALITY OF A WITH REOPENINGS
In this section, we provide the proof of Theorem 3, restated below. Before beginning the proof, we introduce the necessary terminology. We have already defined INC, (p, c) for edge from p to as the inconsistency of the heuristic h for this edge: IP, c) max h(p) - h(c)) c(p, c), 0}- For simplicity, assume that for every h E R", we have ((goal) = 0. Let g (n) denote the cost of an optimal path from Msttrtt to n. With this notation, g (n. m) the cost of an optimal path from n to m. Throughout the search, the g-costs maintained by the algorithm are upper bounds on the true optimal costs. Hence, if (T) is the g-cost for vertex n after iterations, we have ge (n) Z g gn().. We define
(m). the difference between ga (n) and g" (n) as the g-cost error, denoted of (n) = 9r (1)
Because we only update (((n) when we discover a strictly better path to n, both (n) and gi (n) are non-increasing for every
V.
Theorem. Let TI be problem instance, and let Popt vo, 01 ..... Uk be its optimal solution path with cost C* (x). Suppose A + is allowed to reopen nodes. Then the cost Cn(r)) of any solution returned by A satisfies
Cx( - (²(x))
< max h(v) - h0()).
w Popt
Proof. To prove the above theorem, we first state the following lemma from Hart et al. (1968), We omit its proof, which is straightforward and appears in the original work.
Lemma Let Popt be an optimal solution path to a given problem. At any time prior to the expansion of goal node by * there is node from Papt which is in OPEN.
Suppose that for problem instance E I1, the optimal path is Popt to Ul..... Uk. and that the goal node en is selected for expansion at iteration Let u; be the node from Popt in OPEN at this time. Since select iq instead of u; we have:
f(v:) > f(vk),
(1)
g((0;) h(v.) g((xx) + h(ve),
(2)
((1:)+ + h(v,) > g((xx)
(3)
g'(v:) + (1x) + +h::)
+h*((;)) h(²)) (ca)-)((()) C,
(4)
C* +((,) h(())) h²(v,)) C,
(5)
C-C" < < + [h(+)) (v:)))
(6)
(3) follows from the definition of g (-), and (5) uses the fact that the optimal path can be split at any node n E Popt into the optimal path from nsttrt to n and from n to 0g. Inequality (6) thus indicates that the suboptimality can be bounded by the sum of the g-cost error for nę and the difference h(n:)) h2 (n:).
Here, (2) follows from the definition of f(.),
19

---

Published as a conference paper at ICLR 2026
Valenzano et al. (2014) showed that for A without reopening, have
(nx))
INCA (1g, 19+1),
M(ns) - 1:: (n,) s
INC, (1y, 1941).
j=i
k
(n,) + h(ms)) - h:- (m,))) -
(N, 1y+1).
To complete the proof of Theorem 3, we must show that if A allows reopening nodes, then of (n)) = In that case:
C - C (m:) + [h(n.) - h- (m:))
(7)
C C [h(n,) h² (m:)),
(8)
C C max [h(v) h" (v)].
(9)
UEPape
Inequality (9) follows from the definition of the max function. The next theorem implies this condition and thus completes the proof of Theorem 3.
Theorem Let Popt = Vo , Uk be an optimal solution path a given problem. If iteration t the goal node vn is selected for expansion, there will be node vi from Popt which is in OPEN such that of (u,) = O.
The proof is by induction on the number of iterations (i.e., node expansions), denoted by If and the goal is selected for expansion, it means Popt = and the statement is vacuously true. If f = 1, we have OPEN = (children of no) and CLOSED = (Mo)- Since the goal is selected for expansion, it must be one of to 's children. Now, if P up. 21, the statement is correct since ei from the optimal path is in OPEN and of (vi) 0. Suppose the goal does not appear immediately after un in Popt. this case, 81 is not the goal, but connects on to the rest of Popt- Since edge (vo, v1) is on P Popt: we can conclude that (v1) = 9 (Vo. 01) c(vo, V1), and thus the statement is correct.
We assume that for all iterations from to if the goal is selected for expansion, there is node v; from Popt in OPEN such that of (v;) 0. Now consider iteration n + where the goal Fg is selected for expansion. This shows that the node expanded at iteration node at iteration n is not v;, then the statement remains correct for iteration + 1 as well, because U; from the previous iteration is still in OPEN. If the expanded node is v; it is moved CLOSED, and there are three cases for its child 0441 on Pope:
not the goal. If the expanded
Us+1 is already on OPEN.
U141 is not explored. In this case, we add 0/41 to OPEN.
Us+1 is already on CLOSED. In this case, we move 0/41 back to OPEN.
In all three cases, we update the g-cost of 0:+1 using ws's g-cost. This is because every subpath on Popt between any nodes p, has the optimal g-cost 9 (p, e). As result, 1++1 will have the optimal g-cost, Having handled all scenarios for iteration + 1, the statement is correct by induction.
Proof of Theorem 4. To apply Proposition 1 to út we require V,(+) II [0. H.. This is not always possible if the heuristic function can assign h(v) = oo to some vertex e. To avoid this, we assume that Vo V, M(v) + xo if h² (v) oo, which means the learned heuristic cannot treat
20

---

Published as a conference paper at ICLR 2026
any node from which the goal is reachable dead-end. We know that H is not greater than the upper bound derived on expected suboptimality without reopening. In Valenzano et al. (2014), a worst-case graph and Martelli's subgraphs (Martelli, 1977) show that without reopenings, the bounds on expected suboptimality are tight. Hence, H is not too large relative to suboptimality. For this theorem, measuring the pscudo-dimension of H. directly is challenging, while it is simpler to measure it for the dual class of H. We introduce Assouad's dual class of H as follows.
Definition& 4 (Assouad (1983)). Given class, H. C R.' functions h: y - R. the dual class of H. defined as "H- ht H I y y such that (i)hh) h(y) for each y y
We now introduce class known as (F, K) -pieceise decomposable, which has piecewise structure as formalized in Definition 5. If the dual class of 7 is (F, ",,,KKK, ---iiceewsse decomposable, we can use Proposition
bound the gpeudo-dimension of H.
Definition 5 (Balcan et al. (2021a, Definition 3.2)). A class, H. C PR' of functions is (F,B.K) piecewise decomposable for class B (0. of boundary functions and class F R. of piece functions if the following condition holds: for every E H. there exist K boundary functions ((2), ....,b()) E B and a piece function fo for each binary vector b E ={0,1}* such that for all y E y. it holds that hyy) fo, (v) where by =
((10 =[0,1**
Proposition (Balcan et al. (2021a, Theorem 3.3)). Let u C. IR.L be a class of functions. IfU" C B (F, B, K) K)>piecewise decomposable with a class B C {0, 13 of boundary functions and a class F S RMd of piece functions, the pseudo-dimension of is bounded as follows:
Pdlim(()) = -((Pdim((")) + +Cddim(")) log(Pdim(F") + VCdim((")) + VCdim(B") log K).
Now, we begin our proof by defining the function classes B and F. We consider that B
(ii, ;ú 1) h E Ik"" 20 R C 10, and F { { -
C T
to be classes of boundary and piece functions, respectively. We first prove that is (F, B, (())- piecewise decomposable. Fix any - E út" This choice determines unique instance E II and its optimal solution Popt (x) S E. Let K |V| = O(n). We define K boundary functions of the form ((0) (h) = I(h, - h > 0) for each vertex v E V. These boundary functions partition IR" into regions such that, in each region, V (h) is expressible as function in h. which belongs to F. Specifically, for given binary vector by = (h)) DEV E {0, define Ph (x S Popt (z) by (x) {u E (x) (60) (h) = 1]. Hence v E Px()) whenever h2 h > O. From the definition of (x), piecewise linear in h, we can pick for E F such that (h) = for (h) in that region. Since this holds for every by in {0, 1] we conclude (h) = for (h) for all h E R". Therefore, ú" is (F, B, (ie))-eecewess decomposable. Since B is the set of single-coordinate threshold functions in R", we have VCdim(B*) functions on R=,, each function can shatter at most n instances. By (Balcan et al., 2021a, Lemma 3.10), we know Pdim((") < Pdim(F) n. Consequently, from Proposition 2, it follows that Pdim(([)= = On logn).
obtain (h)
(=) max Pr.()) (hr ht). This quantity is
VB) n. For F, which is a family of max
Although we introduced framework with fewer boundary functions, the bound here is not sharper than that of (Sakaue & Oki, 2022). The key limitation is that, even F contained only constant functions, the dimension would still be constrained by VCdim(B).
F PROOF OF THEOREMS USING NEURAL NETWORKS
In this section, we provide proofs for the theorems that use neural networks to represent the heuristic function.
Proof of Theurem 5. In many planning domains such as the Sliding Tile Puzzle (STP), TopSpin, and Rubik's 's Cube-the the primary applications considered in this work-all the assumptions from
Theorem 5 hold. By these assumptions, there are D possible heuristic values. This allows us to
21

---

Published as a conference paper at ICLR 2026
define As, with the heuristic h = R,RLU, P.ReLu,softmax R x XRW
+ RF, where l
p Since each
vertex can only take of & heuristic values, the total number of possible heuristic functions is 8 Thus, there are at most t distinct performance measures. Setting ((e)) 2 2 and solving for N in terms of n gives Pdim((4) P. which reduces the induced graph size to m, similar argument shows that Pdim(()) = (m). Note that both bounds are derived under the assumption that the model is sufficiently expressive to realize all possible f or n heuristic combinations, respectively.
(12). Moreover, the neural network trained on the PDB dataset
For the next proofs, we first introduce the necessary auxiliary lemmas and definitions.
Lemma 3 (Lemma A.I in (Cheng al.)). For any 21,... per,,,,nnn A > 0, the following inequalities hold:
I1
A1 (7))
log 0ı S
+ log
(10)
A
Lemma 4 (Theorem A.2 in (Cheng al.)). Let P C and let fi...., ft R + with 2 f be functions that are polynomials of degree m when restricted to P. Then
(isgn(((())....ss((((((()))))))) : P]
0,
e+1
(()sgn(f())).......l.lll : PPP))
m =
(++
(2etm
((ssp(((())) :PE))
m. 2
Lemma 5 (Lemma A.3 in (Cheng et al.)). h: I x - B define parameterized function class with P S RR, and let H be the corresponding hypothesis class. Let m E N and R N - N be function with the following property: for any E N and II...., E I, there exist R(t) subsets Pi..... PR()) Pf such that P = - P; and, for all E [R(t)] and j E [t). h([;, p) restricted to P. a polynomial function of degree most m depending on at most E' of the coordinates. In other words, the map
+ (h(I1, (h(I,.))....
is a piecewise polynomial map from P to Ip. with at most R(t) pieces. Then,
[2et(m +
Pdim & sup 1 RRtt
Lemma 6 (Lemma A.4 in (Cheng et al.)). Let NRELU, Rdd RRW. - RC be a neural network function with ReL.U activation and architecture w (d,wi..... w1. E] (Definition 2). Then for every natural number t > LW, and any x!....,''' E Rd, there exists subsets Wi....,Wp of LW
R.W with Q < 2/ (2st Et_ (ime))
whose union is all of RW, such that N N(x), w) restricted to E W; is polynomial function of degree at most L - 1 for all (i, [Q] x [t].
LW
Proof. The proof of Lemma 6 is provided in Section 2 of (Bartlett et al., 1998), and the proof of Lemma 5 presented in Section of (Cheng al.).
Proof of Theorem 6. Our goal is to apply Lemma 5 to heuristic functions parameterized by p= RW Specifically, we must show that for any E N and instances .I....,I, I, there exist R(t) subsets Pl...., PRie) of P such that P [((() P, and, for all E [A(()) and j E [t]. u(I;, p) restricted to P. is a polynomial function of degree at most m depending on at most E < & of the coordinates.
Partitioning R wW Hidden Layers and Final Layer. We first split R into two parts: W' (the pa- rameters for the hidden layers) and IR ex (the parameters for the final layer and its activation). There a one-to-one correspondence between I and W x &x where W' = W W--fe -Ewz. By Lemma 6,
w'
the number of regions for W' is polynomial function of degree most + for all j E [1].
eet W7
so within each such region, ReLU (Rep(L,), w) is
22

---

Published as a conference paper at ICLR 2026
Analyzing the Final Layer. Next, analyze Softmax(A**1) (z"), the output of the final layer, where denotes the hidden-layer output for the instance I in a given region of W Let A Ieewe be the weight matrix of the final layer. Then
exp Σ
i=1 A
l++1 z ve, Ex=
(Softmax (oollmax(ALtt22) (
h: = I....,
Ex= exp
1.+11 k/'s z2.)
Define
Oui cxxp(Attt)) so that
exp( app(Attt xi) = (0ks)
Thus, we can rewrite:
(Oks) x M I1
(Softmax(A" 1 (2))))xx(
Arg Max Operation for Heuristic Prediction. h(T,) = arg max (5oftmax(A/+t)) Iskst
The heuristic is chosen by:
Because the exponential function is strictly increasing, softmax preserves the ordering of its inputs. Hence, the softmax function itself does not alter the partitioning of R RÉxu needed for counting regions. We consider arg max (ox(SS)tmmx(()) effectively as arg A A Following Theorem
use 26- (B)) hyperplanes
h(w))) h(v;) +1 co: +2co: +eco A (1,, E B,
to partition R.. These hyperplanes keep the coordinate order fixed within each region, implying a constant A* performance in each region. In other words, if we define polynomial functions vi,..., v for all AL+1 such that
vi (arg max(SSllmax( (A (A"tt)))))). (ary max(Solt 1 22)))
have the same signs, then
U(L (w, A u u NRaLU Sootmax (Rep(L;)))
remains constant. Since the softmax preserves order, each argmax(Softmax(444 can be viewed as a polynomial of degree uz 0g.. The hyperplanes vi.... vf each have degree 1. The total number of such functions across all training instances, i.c. vi{ (arg max ( vi (arg max max(AL+1x)) for E [t], it.
Number of Regions. By Lemma 4, we can partition Txxer into at most
2e FT. ÉWL
Barz
S 2
2etT 2(2011)
fuz
regions, within each of which u (I,, (w, AL+1)) is constant as function of (w, A4+1). Combining this with the regions from the hidden layers W', the total number of regions W is at most
Zet L (iw.) R(t) 2t
2 2eer
F++1
2e00
[2e
Fure
LW
Within each region, uu u(I, (w A1-1)) is polynomial of degree most L 1. Applying Lemma 5, Pdim(l() is bounded by the largest t N such that
LW
Ewr.
W (2ot (20t((+t1)
2 s 21+ 2010
2eer
Taking logarithms on both sides:
< (L+1) + LW log
201U W
+ Ewr, log
200T {
+ W log (e+(L+1)
W
23

---

Published as a conference paper at ICLR 2026
= 1) + (LW + Ewr + W) logt + [W log (W) + fwr log log(2 (2() + W log(
2e (2(T
W
Using inequality (10) from Lemma 3, with I1 and appropriate A, we get:
t + log (=
logt - A
Substituting and setting À = 8 (LW + lwr + W), after simplification we obtain:
(1
1 log
I (L+ +
(IW + Eur + W)
log
(BWW+ew2++W)
log 2
+ LW loga
20l W
lwe log2
2e (q4)
W log2
2e (L+1)
W
Solving for 1, we conclude:
= O(L + Ew7 + W) log(U + + W log(T(L + +1))
Hence,
OLW log(U +6) + w log (og(T((L-)) + 11))
Pdim(U))
= Training on the Main Graph. When training on the main graph G, we have = 22- (()) = =
Substituting this gives:
Pdim(l() = (LW log(U +0 + W (o
Training on the Graph Induced by P. If we train the graph induced by P, the only modified parameters are B' and &' In this abstracted graph, the heuristic values and the numher of generated nodes during search are bounded by those in the original graph. Thus, let B' be the number of states needed to represent each training instance, and l' be the number of heuristic classes, A similar argument shows:
Pli OLW log(U +l) + W log(L' (B' (L+
Proof of Theorem 7. When the goal state can vary for each instance, the number of states required per instance and the number of hyperplanes in the neural network's 's final layer both change accordingly. Consider a fixed instance Re with start state $y. If goal were fixed. we would need |B] states to represent this single instance. However, in this setting, the goal state can be any of the n states E V for E [n].
Because heuristic values for distinct (s, - 9:) pairs are generally independent, we must account for separate hyperplanes for each such pair. Therefore, we have these hyperplanes set for every instance:
For (sj 91): h(v:)) h(v;) #1 co. #2co. =cco
(1t 0/) B1,
For (8j - 92): 1((u)) h(v;)) = +1 +1,, +2co teco
A (ve U3) E B2,
For (s, - -.)): M(.)) h(v;)) = 1 co, +2cp,
tlco
(w,, Bn,
Hence, the total number of hyperplanes is
[18]]
r 2
The rest of the analysis follows the same approach as the fixed-goal case. For the original graph G, we obtain:
Pdim(U) OLL W log(U +() + w log( (en [B|(L+)))
and with same argument for the graph induced by dataset P:
Pdim(U) O (LW log (U E') + W log +1)).
24

---

Published as a conference paper at ICLR 2026
ReLU
Softmax
ReLU
ReLU
ReLU
Input
Con2I)
FC1
FC2
Residual Blocks
Heuristic classes
36 (3*3)
64 (2*2)
Figure Neural Network structure.
G EXPERIMENTAL SETUP
Our experiments use a ResNet architecture (He et al., 2016) (see Figure 4); the full set of training prper-parameters appears Table Table present the details for all PDBs. All runs were carried out on a server with 32-core AMD Ryzen Threadripper 2950X CPU and two NVIDIA GeForce RTX 2080 Ti GPUs (CUDA 12.4). The NN model sizes and performances reported in Table correspond to the 16-bit precision models used during search.
G. STATE REPRESENTATION
For each PDB, we use one-hot encodings tailored to the type of cubies included:
3-Corner PDB. Each face encoded using six 3x3 channels- one per color-rreultingg in total of 6
36 channels. All non-corner cubies assumed be in the solved state.
Edge PDBs. For PDB with edges, construct 3n-channel input of size 4x3, con- sisting of: (i) location-4 one-hot map over the 12 possible edge positions; (ii) rotation- a one-hot indicator set if the cubie is correctly oriented; and (iii) goal position a fixed map encoding the target location for each edge.
Table 3: Heuristic distributions for the PDBs.
h
8-corner
7-edge
6-edge
6-4 (delta)
0
1
1
1,076.354
18
15
15
11,389.507
243
191
184
21,759.383
2,874
2,455
2,256
7,581,788
28,000
30,519
25,909
742,213
205,416 5
356,462
266,101
28,240
6
1,168,516
3,766,700
2,239,790
428
5,402,628
32,719.467
12,567,043
20,776,176
186,297.009
24,415,346
45,391,616
274,719.633
3,061,105
10
15.139.616
13,042,507
170
64,736 11
81
H OVERESTIMATION DISTRIBUTION
In this section, we present the distribution of overestimated states for neural network models trained with both the CEA and standard CE loss functions. The distributions are shown in Figures 6-9, Each figure illustrates the number of overestimated states for both loss functions within specific PDB. We depict the distribution by showing the number of overestimated states at each true heuristic value in the PDB, along with the range of predicted classes which these overestimated states assigned.
25

---

Published as a conference paper at ICLR 2026
Table Training hyperparameters for each PDB.
Hyperparameter
8-corner
7-edge
6-edge
A PDB
Optimizer
Adam
Learning rate
1 X 10-3
3 10-3
Batch size
1 10s
5 10a
10a
B
1.0 0.01
0.6
0.7
0.9
?
0.001
ResNet blocks
3
As the overestimation rates are also reported Table 2, is evident that the number of overestimated states for CEA loss is approximately 10 smaller than that for the CE loss across all PDBs.
MODEL SIZE & HEURISTIC QUALITY
key question is how small model can be while still preserving admissibility and heuristic strength. We investigated this through a scaling experiment with networks of different sizes. To make the comparison fair, we kept the overall architecture- layer types and counts the same as the network used for the 8-corner PDB in Table 2. In particular, every model keeps the initial convolutional layer unchanged, so their representation learning is identical; we vary only the number of neurons in the fully connected layers and residual blocks. We focus the 8-corner PDB because our reference model for already achieves nearly 100% admissibility and the exact average heuristic. Table represents each model's size, structure, and performance. All models were trained for the same number of iterations, although additional training would improve the smaller ones. As model size decreases, performance drops: the estimmatnt rate rises monotonically and is about 10 times higher in Model 5 than in Model 1. Nevertheless, Model 3 achieves almost the same performance as Model while using fewer than half as many parameters, yielding a 51 x compression relative the original PDB.
Table Summary of architectural details and performance for models used in the scaling experiment on the 8-corners PDB.
Model
FC Layer Neurons
Residual Block Neurons
Size (MB)
Avg. Heuristic
Overestimation Rate
Model 1
1000
300
1.89
8.76
3 x 10-1 7
Model 2
800
250
1.28
8.76
3 10-7
Model 3
600
200
0.86
8.75
3 10-7
Model 4
400
150
0.51
8.57
2 2 10-5
Model 5
200
100
0.24
8.24
1 x 10-3
J DYNAMICS OF (3,1) DURING TRAINING
We divide the training process into multiple phases. In the first phase, we set the hyperparameters to and 1) = 0.1, encouraging the model to approximate the true heuristic as elosely as possible. We monitor both the loss and the overestimation rate throughout training. If the model stops making progress (i.e., neither the loss nor the overestimation rate continues to decrease), this indicates that the model cannot learn the exact heuristic across all states. At this point, by gradually adjusting the hyperparameters toward more admissibility (i.e., decreasing 3 and 7)). We repeat this refinement process until the model reaches the desired overestimation rate.
to the next phase
The values used for the hyperparameters and 7 for each PDB are presented in Figure 5. For the 8-corner PDB, did not need to adjust these parameters, the initial values already yielded
26

---

Published as a conference paper at ICLR 2026
perfect heuristic. Our approach is to reduce both parameters whenever there is progress in the loss or the overestimation rate. We monitored these metrics throughout training, and whenever progress stalled, lowered both parameters to promote stronger admissibility, As result, the number of training epochs between each reduction is not fixed. One strategy is to automatically halve both parameters every epochs when no improvement is observed. This provides general heuristic for adapting CEA to other models and domains.
6-edges
7-edges
0.200
-1
0.10
0.175
0.08
0.150
0.125
0.06
0.100
1: (8=1, 0.2)
0.04
(8-0.7, (-0.1)
2: (8=0.5, 0=0.2)
2: (8=0.3, g=0.05)
0.050
3: (f=0.1, n=0.01)
(8=0.1, n=0.01)
0.025
4: (8-0.05, -=0.002)
(8-0.05, (-0.001)
5: ($=0.05, 7=0.001)
5: (p=0.01, 7=0.001)
0.000
0.00
0.2
0.4
0.6
0.8
1.0
0.0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
B
(a) 6-ddges.
(b) 7-edges.
B-corners
A(6, Aedge)-edge
0.011
0.30
(8-0.7, n=0.3)
0.0104
0.25
2: (8=0.7, 4=0.1)
3: (8=0.4, n=
0.0102
(8-0.2, n00.01)
5: (8-0.05. g=0.001)
0.0100
0.15
(8-0.02, 0.0001
0.10
0.05
0.0096
0.00
0.96
0.98
1.00
1.02
1.04
0.0
0.2
0.3
0.4
0.6
0.7
B
(c) 8-corners.
(d) (dee
Figure 5: The (n: 3) values used throughout the training for each PDB.
27

---

Published as a conference paper at ICLR 2026
Overestimated Predictions per Cost-to-Go
9
n 2458
n=907
8
Predicted Class
n=1030
7
n=295
6
n=35
n=1
1
n=0
n=0
n=0
n=0
4
3
4
True Cost-to-Go
(a) CEA loss.
Overestimated Predictions per Cost-to-Go
10
k= 10
n= 0=1.61 M
n=11
M 10
n=21.3 k
n= M
Predicted Class
n=0
n=201 n=3.7
n=0
n=27
4-
n=6
n=1
3
1
9
10
True Cost-to-Go
(b) CE loss.
Figure Distribution of overestimated predictions per true cost-to-go for CEA and CE edges PDB. Each box represents the spread of predicted values, while indicates the number of overestimation states for each class.
28

---

Published as a conference paper at ICLR 2026
Overestimated Predictions per Cost-to-Go
11
n=78
n=21
n=1
10
n=
n=11
Predicted Class
9
n=59
6-
n=21
5
n=2
n=0
n=0
n=0
4-
4
10
True Cost-to-Go
(a) CEA loss.
Overestimated Predictions per Cost-to-Go
k= 10
n=5,8 k
10
M 10
n=154
n=59.0 k
Predicted Class
8
n= 126.3 k
7
n= 14.2 k
n=
n=18
n=225
n=4.8
n=26.31 k
4-
n=1.8
n=1
2-
2
3
&
10
11
True Cost-to-Go
(b) CE loss.
Figure Distribution of overestimated predictions per true cost-to-go for CEA and CE 8- corners PDB. Each box represents the spread of predicted values, while n indicates the number of overestimation states for each class.
29

---

Published as a conference paper at ICLR 2026
Overestimated Predictions per Cost-to-Go
4
n= 3
n=16
Predicted Class
n=67
n=
n=0
n=0
n=
True Cost-to-Go
(a) CEA loss.
Overestimated Predictions per Cost-to-Go
k= 10
M= 10
n=3.4 M
n=177.6 k
n=774
n=7
Predicted Class
n=3.0 M
n=0
n=0
3
n=88.6
2
1
True Gost-to-Go
(b) CE loss.
Distribution of overestimated predictions per true cost-to-go for CEA and CE in (6 4)-edge PDB. Each box represents the spread of predicted values, while n indicates the number overestimation states for each class.
Figure
30

---

Published as a conference paper at ICLR 2026
Overestimated Predictions per Cost-to-Go
n=10898
n= 2945
Predicted Class
8
n=126
n=0
n=0
n=0
n=0
n=0
n=11
n=0
n=0
n=0
3
10
11
True Cost-to-Go
(a) CEA
Overestimated Predictions per Cost-to-Go
10
n 8.8 M
n=23.4
10
5= k
n=43.1 M
Predicted Class
n= 58.3 k
7-
n=0
n=1.3
n=
6
5
n=6
4-
n=2
n=1
&
10
11
True Cost-to-Go
(b) CE loss.
Figure 9: Distribution of overestimated predictions per true cost-to-go for CEA and CE in 7- edge PDB. Each box represents the spread of predicted values, while n indicates number of overestimation states for each class.
31


Reviews:
[{"review_id": "Ppg9iaCvwJ", "reviewer": "Reviewer_KNcH", "summary": "This paper introduces a new loss function, Cross-Entropy Admissibility (CEA), for learning A* heuristics that are both strong and nearly admissible. The authors show that CEA explicitly favors underestimation while still concentrating probability on the true heuristic value, yielding more effective heuristics than compressed pattern databases in domains such as the Rubik’s Cube. \n\nOn the theoretical side, the paper provides generalization guarantees for learned (including goal-dependent) heuristics in A*, deriving improved sample complexity bounds by analyzing inadmissibility along optimal paths. Overall, the work makes both practical and theoretical contributions to learning heuristics for search, bridging a gap between empirical performance and provable guarantees.", "questions": "The authors mention that the CE and CEA models use the same parameters. Could the authors clarify how these parameters were chosen? For a fair comparison, it may be helpful to tune both loss functions under the same hyperparameter-search budget. It would also be valuable to report the tuning ranges, the best-found values.\n\nWhile comparing the NN heuristic with a compressed PDB under an equal memory budget is a meaningful and reasonable fairness criterion, may I ask whether memory alone is sufficient to capture the trade-offs between these approaches? Would it be possible to also comment on the differences in training cost and inference time, as these aspects are often relevant for practical deployment?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Novel loss function tailored to A*: The proposed CEA loss directly encodes admissibility preferences, addressing a key limitation of prior heuristic-learning approaches that treat over- and under-estimation symmetrically.\n\nStrong empirical performance: Experiments (e.g., on Rubik’s Cube) demonstrate that the learned heuristics are nearly admissible while significantly outperforming compressed PDB heuristics of equal memory footprint, showing both practical effectiveness and scalability.\n\nTheoretical contribution with improved sample complexity bounds.", "weaknesses": "Fairness of experimental comparison could be improved: While the comparison with compressed PDBs under equal memory budget is meaningful, it overlooks other relevant dimensions such as training cost, inference time, and tuning effort. In particular, CEA models were tuned, whereas the CE baseline shares hyperparameters without comparable tuning, which may bias results in favor of CEA.\n\nCEA introduces additional tuning complexity\n\nLimited domain diversity in evaluation: Experiments focus primarily on the Rubik’s Cube domain. It remains unclear how well the method generalizes to other search domains with different structure, branching factors, or cost models.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "WfBlY7Is8G", "reviewer": "Reviewer_BkY5", "summary": "The paper presents a method, called cross-entropy admissibility (CEA), to learn heuristic functions which, in the context of pathfinding on a weighted directed graph, map states to an estimate of the cost-to-go to a closest goal state. CEA focuses on learning heuristic functions that are admissible, meaning they never overestimate the cost of a shortest path. CEA formulates heuristic learning as a classification task, where each possible heuristic value is treated like a class, and more emphases is put on penalizing overestimation. The paper focuses on the Rubik’s cube, where all transition costs are one and, therefore, all possible true cost-to-go values are integers. Results with neural networks on learning heuristic values from PDBs show that the proposed method learns heuristic values that have significantly fewer underestimations than regular cross entropy (CE) while having a slightly less or similar average heuristic value.", "questions": "Does the theory presented in the paper say anything about drawbacks from prioritizing admissibility?\n\nFor Table 2, has using mean-squared error been tried?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "As machine learning continues to be used to learn heuristic functions, admissibility guarantees become more important. The paper contains important theoretical analyses and proposed practical approaches for learning heuristic functions that are largely admissible.\n\nWhen compared to compressed PDBs, both the CEA and CE have higher average heuristic values while maintaining similar compression rates. However, CE, has overestimation rates on the order of 1o^-3 to 10^-2. On the other hand, CEA has compression rates on the order of 10^-7 to 10^-5. The average heuristic value of CEA when compared to CE ranges from slightly lower to having the same value.", "weaknesses": "The paper discusses the benefits of admissibility, but it is not clear at what the cost of prioritizing admissibility on problem solving ability. If a neural network uses more of its representational capacity to prevent overfitting, then it may stand to reason that it may perform relatively poorly on higher cost-to-go values. This could make finding paths more time consuming in practice due to the lower overall heuristic value. Table 2 indicates this could be the case due to CEA having a slightly lower average heuristic value compared to CE.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "FNzms9mTYR", "reviewer": "Reviewer_1RCQ", "summary": "This paper tackles a core challenge at the intersection of machine learning and heuristic search: **how to learn powerful heuristic functions that preserve the optimality guarantees of algorithms like A***.\n\nThe authors make contributions on both theoretical and practical fronts:\n\n*   **New Loss Function:** They propose a Cross-Entropy Admissibility (CEA) loss, a new training objective designed to enforce the admissibility constraint directly.\n\n*   **Strong Empirical Performance:** Evaluated on the 3*3 Rubik's Cube, the approach demonstrates remarkable success, learning heuristics that are nearly perfectly admissible while providing stronger search guidance than traditional baselines.\n\n*   **Theoretical Analysis:** The work provides a sample complexity analysis for learning heuristics. By leveraging problem structure and abstractions like Pattern Databases, the authors derive tighter generalization bounds for A*. They also establish a theoretical guarantee for learning goal-dependent heuristics.\n\nIn summary, this work introduces a framework for learning reliable heuristics, effectively bridging data-driven learning and classical search algorithms.", "questions": "- **Comparison with Standard Cross-Entropy Loss:** The paper clearly shows that the CEA loss achieves a much lower overestimation rate than the standard CE loss. However, beyond this crucial metric, did you compare the **resulting A\\* search performance** (e.g., number of node expansions, wall-clock time) when using heuristics trained with these different losses? \n- **Connection Between Theory and Experiment**: Could you share more details on how the theoretical insights guided the experimental design? For instance, did the theory influence the choice of neural network capacity or the amount of training data needed?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "- **Strong Empirical Validation:** The work demonstrates compelling empirical results. On the challenging benchmark of the 3x3 Rubik's Cube, it achieves near-perfect admissibility while learning a heuristic stronger than classically compressed alternatives.\n- **Noteworthy Theoretical Scope:** The paper provides a significant theoretical analysis of sample complexity. Its most original contribution is extending this framework to establish the first generalization guarantees for *goal-dependent* heuristics, moving beyond standard fixed-goal analyses.", "weaknesses": "- **Limited Empirical Scope:** The empirical evaluation is exclusively conducted on the 3*3 Rubik's Cube. The performance and effectiveness of the proposed CEA loss on other combinatorial puzzles or planning domains remain unknown.\n- **Limitations of Theoretical Claim**: The claim that sample complexity is governed by network parameters and independent of graph size may not translate to practical advantages, as it relies on strong assumptions that may fail in real-world problems.\n- **Unvalidated Theoretical Extension:** While establishing the first theoretical guarantees for goal-dependent heuristics is a notable contribution, this significant claim is unsupported by empirical evidence. The experiments only address a fixed-goal setting.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "o4I11vmJxr", "reviewer": "Reviewer_bBv4", "summary": "This paper addresses the challenge of learning admissible heuristics for A* search. Many current deep learning approaches often do not consider admissibility but focus on predictive strength, losing theoretical guarantees on optimality. The authors propose new sample complexity bounds for learning such heuristics, that exploit graph structural properties and PDB abstraction. They also derive bounds for neural network that depend on the networks size rather than the problem size. From a practical point of view, the paper frames the heuristic learning as a constrained optimization problem and further reduce it to a classification task that uses a new loss function called cross-entropy admissibility. Empirical results show the method has low overestimation rate without sacrificing informativeness.", "questions": "1. Have you quantified A* search impact in terms of running time on your test problems?\n2. Have you empirically evaluated your methods on other domains? How does it perform?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The formalization of heuristic learning as a constrained optimization and reduce it to a classification task guided by a new loss function is novel.\n2. The tighten sample complexity bounds seem to be a good contribution.\n3. The paper addresses a gap between ML-based heuristics and rigorous admissibility requirements for optimal search.\n4. The paper is well-presented.", "weaknesses": "I wasn't able to check the theory thoroughly, the weaknesses listed below are mainly from empirical study.\n\n1. Experiments are on Rubik’s Cube domain, it is a good benchmark but requires at least of couple more for the empirical results to be fully convincing. The practical value of CEA would be clearer if demonstrated in another admissible-heuristic domain (e.g., sliding-tile puzzle).\n2. The paper didn’t describe how the hyper parameters \\beta and \\eta are tuned, if the author could provide a principled process, it would help reproducibility. \n3. There is no runtime measurements in the experiments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "RKoj51n9R1", "reviewer": "Reviewer_zAZ1", "summary": "This paper aims to learn admissible heuristics for A*, combining theoretical generalization analysis with practical training improvements. It incorporates a new loss function, called Cross-Entropy Admissibility (CEA), that enforces admissibility during training and analyzes the sample complexity of learning admissible heuristics. Experiments on the Rubik’s Cube show that CEA produces nearly admissible heuristics with very low inadmissibility rates and stronger guidance against compressed pattern databases (PDBs).", "questions": "Please refer to the weakness.", "limitations": "", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. This paper introduces CEA as a principled loss to enforce heuristic admissibility is both theoretically sound and practically effective.\n2. It provides theoretical analysis and derives tighter generalization bounds, incorporating neural networks as the heuristic with  generalization bounds analyzed primally on network size.\n3. Experimental results demonstrates strong results on Rubik’s Cube domains, showing measurable gains over traditional PDBs.", "weaknesses": "1. The experiments results are limited to a single domain(the Rubik's Cube). The claims of the paper would be significantly stronger if supported by results on other classic planning domains.\n2. The theoretical analysis relies on Assumption 4, while this holds for the Rubik's Cube but is not universal. How do the bounds change for graphs with variable edge costs? \n3. The proposed method is evaluated on several 3 × 3 Rubik’s Cube pattern databases, where  the performance and data requirements for larger graphs remain unclear.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "epCSBXP4Sj", "reviewer": "Reviewer_ntxk", "summary": "This paper extends existing theoretical analyses on the sample complexity of\nlearning admissible heuristics, then proceeds to define a new loss function\nto achieve such admissibility.\nThe contributions in this work are\n\n-   Thm2: Extension of Sakaue & Oki 2022's result on Pdim to PDB's abstracted states\n-   Thm3: a tighter suboptimality bound when A\\* with is allowed to reopen nodes &#x2013; extension of Valenzano '14,\n-   Thm4: Eq. (3) which has O(sqrt(n)) instead of O(n) in Eq (1) = Prop 1 + Sakaue & Oki 2022.\n-   Thm5: Extension of Sakaue & Oki 2022's result on Pdim to NNs, with/without PDBs\n-   Thm6: Extension of Thm5 to NNs with specific sizes\n-   Thm7: Extension of Thm6 to different goals\n-   proposing CEA loss.\n\nI have a mixed impression about this work. While the paper is tackling an important problem,\nthe paper appears to be written by two authors without a necessary organic integration,\nwhich is a common phenomenon &#x2014; one symbolic author and one machine learning author failing to understand each other, stuck in their own worldview.\nThis might be causing inconsistent math notations (e.g. log vs. lg, $\\ell$ vs. $D$),\noverlapping symbols ($W$ as cost upper bound vs parameter size),\nand an apparent disconnect between the theoretical result and the empirical result described below.\n\nThe paper did excellent work coverint the backgrond on the sample complexity analysis.\nHowever it is light on proofs, which are largely deferred to the appendix,\nand has several minor notation issues which must be fixed.\n\nI also have a bigger concern about the practical part of this paper: CEA, and the empirical evaluation.", "questions": "Q1. Confirm the input format is PDB abstract state representation, factored. (yes/no)\n\nQ2. Confirm the target value is really h\\* and is obtained by solving x optimally. (yes/no)\n\nQ3. Did you use the entire abstract states in the PDB without subsampling? (yes/no)\n\nQ4: The author claims that Eq.(3) is tighter than Eq.(1) with no explanation.\nI assumed O(sqrt(n)) vs O(n) is what they implied. Am I correct? (yes/no)\n\nAlso, please add a sentence that explains conceptually why this reduction is achieved.\n(E.g., in sorting literature, radix sort can run faster than O(n log n) &#x2014; why?\nit is because it can use more information than comparison sort.)\nI assume that this is in line with something like: it uses the max in Thm3,\ntherefore only one element along the path affects the error,\nwhile the first error term in Eq.(1) is essentially a double summation (sum over paths, sub over states on the path)", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "The paper did excellent work covering the backgrond on the sample complexity analysis.", "weaknesses": "## Issue 1: CEA\n\nAs discussed in [Nunez-Molina 2024] cited in this work,\nthe choice of the loss function must directly correspond to the statistical representation of the output.\nCategorical target random variable yields the cross-entropy loss naturally as a negative log likelihood.\nThe proposed CEA loss does not have a corresponding distribution.\nIf the author wishes to impose some mathematical property on the prediction target,\nthe right way to design a machine learning model is to idenfity the correct representation of the target as a random variable,\nthen derive the loss function naturally from its pdf.\n\nOne such alternative as a baseline for comparison against CEA I suggest is **ordinal logistic regression** for ordinal variables.\nOrdinal regression [1] is a classical method for predicting ordinal random variables,\nwhich naturally address the lack of orders in the categorical prediction (classification).\nIf the model believes that the output is larger than k,\nthen the model architecture must hard-code the invariance that the output is also larger than k-1, k-2, and so on.\n\n[1] McCullagh, Peter (1980). \"Regression Models for Ordinal Data\"\n\nOne of its simplest implementation uses the cumulative binary logistic loss,\nwhich outputs a single scalar with a NN, subtract monotinically increasing threshold values,\napply a sigmoid, then train the output with binary cross entropy.\n\nparameters:\n\n-   A scalar output neural network $f$ (the last layer does not need the bias)\n-   A bias vector $\\mathbf{b} \\in R^k$ for prediction over $\\{0, 1, ... k\\}$\n\nhow:\n\n-   input $x$\n-   target value $h^* \\in ｛0, 1, ... k｝$\n-   binary prediction target $\\mathbf{y} \\in ｛0,1｝^k$:\n    -   $y_h = 1$ if $h > h^*$ ;\n    -   $y_h = 0.5$ if $h=h^*$ ; \n    -  0 otherwise.\n    -  For example, it looks like $[0,0,0,0,0.5,1,1,1]$ when $h^*=4$ and $k=7$.\n-   scalar logit $l = f(x)$\n-   thresholds $\\mathbf{\\theta}$\n    -   $\\theta_0 = b_0$\n    -   $\\theta_h = \\theta_{h-1} + softplus(b_h)$\n        -   This ensures $\\theta_h > \\theta_{h-1}$\n-   output: vector $\\mathbf{p}\\in [0,1]^k$, where\n    -   $p_h = \\sigma( l - \\theta_h )$\n    -   $p_h$ represents $p(h^* < h | x)$ , and this framework guarantees $p(h^* < h | x) < p(h^* < h+1 | x)$ .\n-   loss: $\\sum_h CE( y_h, p_h )$\n\nNotice that the final loss naturally penalizes the misprediction of $p(h^* < h | x)$ the further $h$ is away from $h^*$.\n\nFor example, when $h^*=4$ and $p_6$ is smaller than 0.5, the framework ensures that $p_4, p_5$ are even smaller, resulting in three times or more penalty.\nThis has a similar characteristics as the first term of the CEA, while maintaining the natural statistical interpretation.\n\nYou may however return a rebuttal: Then how do we interpret the tunable &beta; in CEA, and the fact that it only applies to the overestimation?\n\nMy answer: As cumulative binary logistic loss is a sum of losses for a series of binary predictions,\nwe can achieve the same effect by multiplying a set of coefficient to each loss.\nThis is a common practice for addressing a class imbalance (although our purpose is different)\nand it is mathematically equivalent to oversampling/undersampling a subset of the dataset.\n(Well, there may indeed be a class imbalance.\nsee the next section blow.)\nConcretely, use the loss as follows:\n\n-   loss: $\\sum_h w_h CE( y_h, p_h )$\n\nYou are free to choose any $w_h$, e.g. $w_h = g(h, h^*)$ for some formula g that increases as $h$ overestimates.\nSo, there is no ad-hoc tricks; It simply artificially increases the penalty to the overestimation.\n\n\n## Issue 2: PDB learning\n\nI found that the method section and the evaluation section is quite ambiguous about the training data.\nI struggled to discover what is the input representation to the NN, what is the taget value, and how many data points are used.\nPlease add a separate section titled \"data collection\" which details what goes in the pipeline.\nI initially had 4x2 = 8 possible interpretations:\n\n-   Input x to the NN:\n    -   Raw state representation, factored\n    -   Raw state representation, in a form of state id\n    -   PDB abstract state representation, factored (\\*)\n    -   PDB abstract state representation, abstract state id\n-   Target data:\n    -   optimal solution cost $h^*(x)$ obtained by search from x using admissible PDB\n    -   admissible heuristic $h(x)$ from the PDB &#x2014; which is an optimal path cost in the abstract state space\n-   The number of data points\n\nThe detail of the input representation is only given in the appendix.\nWhile the full detail is not necessary, the main paper must at least mention\nthat it is the factored abstract state representation of PDB.\n\nWhat's more important is the target data.\nI know you used $h^*$ in Eq.5, but I don't have a good confidence because\nthere is no mention of how it was collected.\n\nI could not find any information about the number of data points.\nDid you use the entire abstract states in the PDB without subsampling?\nIf so, the dataset is hugely imbalanced, as you pointed out in the paper.\nThe standard practice is oversampling, undersampling, and bagging. See [1].\nThese standard measures completely normalizes the number of samples per class.\n\nThe lack of mention to how the author addressed the class imbalance imply a danger that\nthe perceived improvement from the CEA loss could be just an artifact of **accidentally** somewhat addressing\nthe class imbalance in an ad-hoc way.\n(As said above, multiplying $(k/h^*)^\\beta$ to the loss is mathematically equivalent to oversampling.)\n\nThe authors also mentioned delta-PDB, which would shift h's distribution and also somewhat reduces the class imbalance,\nbut the Table 3 shows that the entire dataset still contains a massive class imbalance.\n\n[1] Wallace, Byron C., et al. \"Class imbalance, redux.\" 2011 IEEE 11th international conference on data mining. Ieee, 2011.\n\n## Issue 3: Disconnect between theoretical results vs experiments\n\nThe theoretical and the empirical results in this paper are, while individually interesting, quite disconnected.\n\n\n### theorem 4\n\nFirst, the paper does not empirically verify Theorem 4.\nI expected an experiment that estimates the LHS of eq.3 using a validation set as a surrogate or the entire (abstract) state space,\nsubtract the first term of Eq.3, then plot the remaining value to confirm that it grows $O(\\sqrt(n))$.\n\nTheroem 4 does not require factored state representation, Rubiks cube, PDBs or the CEA loss function.\nInstead, theorem 4 is a function of the graph size n and the sample size N.\n\nIn other words, while section 3.1 is by itself an interesting contribution,\nits empirical confirmation must be done separately using a state space whose size is configuratble,\ne.g., not in Rubik cube, but in artificial random graphs such as those studied by Cohen & Beck [AAAI17, AAAI18, IJCAI18]\nwhose $n$ can be configured.\n\n-   Problem Difficulty and the Phase Transition in Heuristic Search, AAAI17\n-   Local Minima, Heavy Tails, and Search Effort for GBFS, AAAI18\n-   Fat- and Heavy-Tailed Behavior in Satisficing Planning, IJCAI18\n\n\n### theorem 7\n\nAnother main theoretical results in this paper is the sample complexity in theorem 7.\nI expected that the empirical analysis verifies this by one of these experiments:\n\n-   Experiment 1: Given a fixed network, compute this upper bound Pdim(U) with\n    Thm7. Then gradually reduce the dataset size by subsampling. See what happens\n    if the dataset size goes below Pdim(U)\n-   Experiment 2: Given a fixed dataset, reduce the number of weights in NN to reduce Pdim(U).\n    See what happens if Pdim(U) goes below the dataset size.\n\n\n## Issue 4: Runtime analysis of using the NN\n\nWhile the paper claims that it tries to find a smaller NN (Eq.4),\nit does not do anything about it actually.\nThe evaluation focuses on accuracy and admissibility,\nand never compares the actual runtime or the number of node evaluations\nbetween the sota solver against A\\* guided by the heuristics learned by this method.\n\nIn other words, as is often the case with many machine learning papers,\nI suspect that this paper obtained a quite accurate heuristic that is too slow\nto compute to use in practice.\n\n\n## Minor comments and questions\n\n-   line 80 : b should be a neighbor of a?\n-   l.77-91: floor and indicator functions are not used in the paper?\n-   l.165-173: better to have a consistency in the choice of letters. H -> U?\n-   l.173: h suddenly becomes a real vector. I know this is an array from a state to R, but this is inconsistent to the previous notation h(s) of state s.\n-   l.213: $|G_v| <= n^2$ I suppose.\n-   l.215: same regarding h.\n-   l.215: add \"derived from S & Oki 2022\".\n-   l.216: same reagarding h.\n-   l.234: \"general class of performance measure\", provide examples, e.g., runtime, memory, node evals, etc.\n-   l.252: Results in Valenzano 14 holds regardless of admissibility, which is surprising.\n    Although it is not wrong not to mention it (because nothing more is not assumed than stated),\n    due to the strong association between A\\* and admissibility,\n    I strongly suggest the authors to explicitly state that the entire section 3.1 does not depend on the admissibility of h.\n-   l.268: $\\hat{H}$ undefined.\n-   l.270: lg n vs log n.\n-   l.302: sum of $w_1 \\ldots w_n$ is denoted by U. U -> W?\n-   l.305: Indeed, here the number of parameters is W.\n-   l.317: the number of output classes is $\\ell$. It was $H$ before. or $\\hat{H}$. wtf?\n-   l.326: this time the number of output classes is $D$. wtf?\n-   l.333: Rep(I) is not used at all elsewhere in the paper. maybe appendix. please remove it or move it to the appendix, if used there.\n-   l.343: $\\ell$ and $D$ used at the same time. Also, U and W are used at the same time. $\\ell'$ undefined.\n-   l.364: $|h|$ is never explicitly optimized. I doubt Eq.4 is necessary.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "zutdlOQLn1", "reviewer": "Reviewer_BWMp", "summary": "The paper develops theory and practice for learning admissible A* heuristics. It tightens sample-complexity bounds under equal-cost edges and gives a sharper suboptimality guarantee that bounds A*’s error by the maximum inadmissibility on the optimal path, with extensions to neural-network and goal-dependent settings.\nPractically, it introduces the Cross-Entropy Admissibility (CEA) loss, which shifts probability mass onto admissible classes and sharpens around the true class.\nOn Rubik’s-Cube PDBs, CEA-trained models achieve near-admissibility and match or exceed the average heuristic of same-size compressed PDBs", "questions": "* How was the data split for the empirical study? How many samples are used for training?\n* Can the CEA loss be extended to settings with non-uniform edge weights?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "* The theory derives tighter generalization bounds that incorporate neural network width/depth and handle goal-dependent heuristics.\n* Heuristic learning is cleanly framed as a constrained optimization problem.\n* The suggested CEA loss seems to effectively encourage admissibility in the provided experimental results.\n* Overall, the paper is well written.", "weaknesses": "* The theoretical results mostly assume equal-cost edges (Assumption 4). While this is common for toy problems like Rubik’s Cube it limits immediate transfer to domains with varied costs.\n* While the CEA loss suggested in Equation 5 seems conceptually plausible, it lacks a clear motivation why this specific function was chosen. The goal of shifting some probability mass towards admissibility could be expressed through other loss functions as well, for example by minimizing the kl divergence between the predictions and a suitably defined target distribution. Were other loss functions considered? If so, why was this specific one chosen?\n* Some details of the experimental results are vague. No details on how the data is split into train/validation/test splits is provided.\n* As the theory in section 3 derives the sample complexity for learning heuristics, an ablation study that measures the heuristics performance as a function of the training set size would strengthen the connection between the works theoretical and empirical sections.\n* The CEA loss introduces β and η as additional hyperparameters that are adjusted in stages during training, which adds complexity to the training process.\n\nWhile the theoretical results and novel CEA loss are contributions, I do think these weaknesses currently outweigh the strengths of the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)