A Differentiable Loss Function for Learning Heuristics in A*
Authors: Leah Chrestien
Tomáš Pevný
Antonin Komenda
Stefan Edelkamp
Venue: Submitted to ICLR 2023 (2023)
Keywords: Differentiable Loss Function
a star
heuristic search

Abstract: Optimization of heuristic functions for the A* algorithm, realized by deep neural networks, is usually done by minimizing square root loss of estimate of the cost to goal values. This paper argues that this does not necessarily lead to a faster search of A* algorithm since its execution relies on relative values instead of absolute ones. As a mitigation, we propose a L* loss, which upper-bounds the number of excessively expanded states inside the A* search. The L* loss, when used in the optimization of state-of-the-art deep neural networks for automated planning in maze domains like Sokoban and maze with teleports, significantly improves the fraction of solved problems, the quality of founded plans, and reduces the number of expanded states to approximately 50%

Under review as a conference paper at ICLR 2023
A DIFFERENTIABLE Loss FUNCTION FOR LEARNING HEURISTICS IN A *
Anonymous authors Paper under double-blind review
ABSTRACT
Optimization of heuristic functions for the A algorithm, realized by deep neural networks, is usually done by minimizing square root loss of estimate of the cost goal values. This paper argues that this does not necessarily lead to a faster search of A* algorithm since its execution relies on relative values instead of absolute ones. As mitigation, we propose the L' loss, which upper-bounds the number of excessively expanded states inside the A search. The I,* loss, when used deep neural networks for automated planning in maze domains like Sokoban and maze with teleports, significantly improves the fraction of solved problems, the quality of founded plans, and reduces the number expanded states to approximately 50%.
the optimization of state-of-the
INTRODUCTION
Automated planning aims to find a sequence of actions that will reach a goal in model of the en- vironment provided by the user. Planning is considered to be one of the core problems Artificial intelligence and it is behind some of its successful applications Samuel (1967); Knuth & Moore (1975); [iiverr et al. (2017). Early analysis of planning tasks McDermott (996) indicated that op- timising the heuristic function steering the search for given problem domain can dramatically improve the performance of the search.
Learning in planning means optimizing heuristic functions from plans of already solved prob- lems and their instances. This definition includes selection of proper heuristics in a set of pat- tern databases Franco et al. (2017); Haslum al. (2007); Moraru al. (2019); [Edelkamp) (2006). a selection of a planner from a portfolio Katz et al. (2018). learning planning operators from instances Menager al. (2018); Wang (994). and learning for macro-operators and entangle- ments Chrpa (010)) Korl (1985). Recent years observe renewed interest in learning heuristic functions and this is fuelled by the success of deep learning and reinforcement learning in the same
area Shen et al. (2020); Groshev et al. (l,((201))) Ferber et al. (2020); [Bhardwaj et al. (2017).
In this work, we are interested optimising the heuristic function for A Hart al. (1968), which despite the popularity of Monte Carlo tree search Coulom (2006); [Silver et al. (2017) is interesting due to its guarantees on optimal solution. * is also optimally efficient in the sense that it expands the minimal number of states. Majority of prior art (Shen al. (2020); Toyer et al. (2000) Groshev ct al. (2018); Ferber et al. (2020); Bhardwaj et al. (017) optimises the heuristic function by mini- training set of problem instances where the error is measured by the L2 error function or its variant. L = 0 does not guarantee the optimal
mizing the eиror of the predicted cost to the goal
efficiency of A hence it gives false sense of security.
We propose a L' loss function tailored for A* which minimizes an upper bound on the number of expanded states. This is achieved by stimulating states an optimal path to have a smaller cost function f = + h than those off the optimal path. By this, I," effectively utilizes all the states generated during the exploration of A* providing much more information the learner. If L' on a given problem instance is equal to zero, it is guaranteed that A will expand only states on the optimal path, which under conditions on the training set as detailed below, implies optimal efficiency of A We emphasize that the optimal efficiency is retained even on problems with
'The training set contains solved problem instances, where the solution should be ideally found by search finding optimal solution, such as A with ideally admissible heuristic function.

---

Under review as a conference paper at ICLR 2023
exponentially many optimal paths Helmert & Röger 2008), therefore the heuristic function has to learn a beebrraking mechanism.
The proposed L is compared to state of the art on seven domains: Sokoban, Maze with teleports, Sliding tile puzzle, Blockworld, Ferry, Grippe, and N-Puzzle and on all of them it consistently outperforms heuristic functions optimizing L2-
2 PRELIMINARIES
We define search problem instance by directed weighted graph r = (S, E, u),, a distinct node 9o E S and a distinct set of nodes S* C. S. The nodes S denote all possible states E of the underlying transition system representing the graph. The set of edges & contains all possible transitions E & between the states in the form e = 8'). 80 E S is the initial state of the problem instance and S* S S is a set of allowed goal states. Problem instance graph weights (alias action costs) are mappings w : E + R20.
Let (e1, E2,.... e)., we call a path (alias plan) of length / solving task I' with so and S* iff π = ((s. 81), (81, $2),.... (81-1,81) 81)) and 81 E S An optimal path is defined as a minimal cost of problem instance S0, S" and is denoted x² together with its value f" w(x") w(ei) (w()))) +w(e)). We often minimize the cost of solution of a problem instance I,, 80, S*, namely n², together with its length 1" |x"]
2.1 A ALGORITIIM
Let's briefly recall how the A algorithm works. For consistent heuristics, where h(s) - h(s') < w(s, s') for all edges (s, s') in the w--eightted state space graph, mimics the working of Dijkstra's shortest-patt algorithm Dijkstra (1959) and maintains the set of generated but not expanded nodes in O (the Open list) and the set of already expanded nodes (the Closed list). works as follows.
1. Add the start node so to the Open list Oo.
2. Set g(so) = 0
3. Initiate the Closed list to empty, i.e. Co = 0.
4. For i L.... until O * 0
(a) Select the state s; arg min g(s) + h(s)
(b) Remove 8; from O;-1, O = 0,-1 \ {si}
(c) If 8; E S", i.e. it is goal state, go to 5.
(d) Insert the state s; to C,-1, C. C-11 U {st}
(e) Expand the state 8; into states s' for which hold (s;, s') E and for each
i. set g(s') g(s:) + wo(ss,
il if s' is in the Closed list as se and g(s') < g(sz) then s. is reopened (i.e., moved from the Closed to the Open list), else continue with (e)
ii.. if s' is in the Open list as 8, and g(5") g(s.) then so is updated (i.e., removed
from the Open list and re-added in next step with updated g(-)), else continue with (c)
iv. add s' into the Open list
5. Walk back to retrieve the optimal path.
In the above algorithm, g(s) denotes a function assigning an accumulated cost w for moving from the initial state (sq) to given state s. Consistent heuristics are called monotone because the estimated cost of a partial solution fs) g(s) + h(()) monotonically non-decraaiing along the best path to the goal. More than this, f is monotone on all edges (s,s'), if and only if h is consistent as we have f(²' = g(s') + h(s') Z g(s) + w[s 8') + h(s) wwss s') = f(s) and l((s) - h(s') = -(s)-((5)
f()) f(s)) + 5s, < w(s s'). For the case of consistent heuristics, no reopening (moving back nodes from Closed to Open) is needed, as we essentially traverse a state-space graph with edge weights w(s s') + h(s') - h((s) 0. For the trivial heuristic hy. we have (s(s) = 0 and for perfect heuristic h², we have f(s) = f = =g(s) + h² (s) for all nodes Both heuristics by and ht are consistent.
2

---

Under review as a conference paper at ICLR 2023
86
85
96
80
(a)
(b)
figuui (a), path 8o - 81 - 82 represents the optimal plan, states {sy. $4. / / 86 are off the optimal path but have / have not been generated by the A# sub-figure (b), path 80 + 81 - 82 - 84 and 80 + 81 + 83 + 84 represents the optimal plan, states 85/86 are off the optimal path but have have not been generated.
Figure 1: A visualization search space of an A algorithm.
Even if the heuristic is not consistent, algorithms like A even without the reopening, remain com- plete i.e. they find a plan if there one. Plans might not be provably optimal but are often very good in planning practice.
2.2 OPTIMIZING THE HBURISTIC
We consider heuristic function hg : S R220 mapping a state E S to a real non-negative value, where 0 E T holds parameters of ha- Using set of problem instances T (further called training set), we want to optimize parameters 0 of ha such that an A* search algorithm would find an (optimal) solution by expanding the least number of states. 2 This, in practice, means to solve the optimization problem
arg min EL(he,S): SET
(1)
where the loss function L should be such that smaller values imply better heuristic function hg as perceived by A
2.3
WEAKNESS OF L2 LOSS FUNCTION
Many prior art on optimizing heuristic function Shen et al. (2020): Groshev et al. (2018) Ferber et al. 20220); Bhardwaj et al. 2017)); Toyer et al. 2020 minimize the 1.2 loss function T (2a,, S)
E, (ho(s:) ya)² where the training set S consists of pairs {(s, 3) 3)) }== where is some state and yı is the length of the plan from s; to the goal state. We argue that zero L2 loss on a given problem instance for states the optimal path does not guarantee that A will be optimally efficient in the sense that it can expand more states than needed.
L2 does not utilize states off the optimal path. Imagine problem instance shown in Figure Ta where and 82 are the initial and goal states respectively and (sp, $1, s2) is the optimal path. When L2 loss is optimized, one needs know the exact cost-to-go values which are obtained by solving the problem instance. Thus, by solving the instance in Figure [ one obtains heuristic values for {su, $1, $2). But if L2 loss is equal to zero on them, does not say anything about estimates for states off the optimal path states {83, 84, 85, 86. This means that it can happen that f(sa) < (81),, which would lead to expanding the state 83 in A algorithm and hence to sub-optimality.
This issue can be fixed, if the training set is extended to contain heuristic values for all states off the optimal path ([83, 84,..., }6} in our example), which in practice requires solving all possible variants of the problem instances. This has been suggested in (Bhardwajj et al. (2017) but is infeasible due to excessive computational requirements. Therefore, in practice, it is assumed the training set to be large, thereby mitigating this problem.
Herr assumed that the number of expanded states is directly proportional the time taken to find solution, as the time to compute the value of he is independent of the value of e. While works use T.,, the properties discussed here for L.g holds for I, as well.
3

---

Under review as a conference paper at ICLR 2023
L2 loss provides false sense of optimality. Some problems can have large (even exponential) number of optimal solutions with the same cost Helmert & Röger (2008). In this case, minimizing estimate of cost-to-ge go of all states in the problem instance (to fix the problem mentioned above) does not guarantee that * will be optimally efficient. Consider an example in Figure with unit cost on edges. The algorithm starts by expanding state 8n 81 and 82. The heuristic is perfectly estimated and f(1)) = f32) = 3. Hence there are two states with the same value ff which means A has to decide, how the break this tie. The situation repeats after A expands either 81 or 53, since the open set will now contain state 83 with (s3) 3 and A needs to resolve ties again. See Helmert
& Röger 2008 for more examples.
Heuristic value for unreachable (dead-end) states should be infinite to ensure that they are never selected. An infinity in the L2 loss would always lead to an infinite loss which would then result in an infinite gradient. Hence, in practice, sufficiently large value for dead-end states has to be used.
3 L" LOSS
We explain the proposed L'loss function on single problem instance 1'= (S, E, w) (the extension set of plan is trivial through Equation equation[]] ( We assume to have (preferably optimal and shortest) plan π = ((so: $1) ). ($1, s2),.... (8,-1, S,,) with states from this optimal plan denoted as S {Su. $1 $2, ................................ s.): }. This plan can be found by A with some (admissible) heuristic functioon h, which does not have to coincide with the heuristic function hg that we are optimizing. We denote states off the optimal plan as S C C 8" where the subset exists because, in practice, S contains states generated by A* while solving the problem instance r. In the visualization in Figure Ta grey states are on the optimal path S", pink states are off the optimal path, and yellow states were not generated in the course of solving the problem instance. Hence, S {ss 16 S S = {s: The training sample for a L'is defined as a tuple = (,S,E,))SS.
= and
L' aims minimize the number of expanded states in the A algorithm. Recall that A always expands a state from an open list with smallest fe(s) = g(s) + hg(s). To be optimally efficient, states on the optimal path s' S should have always smaller [(6' than states off the optimal path 8" E S", i.e.
(A8' (Y6"" S")) + ha(s') <)(=") + h)((s))
On the optimal path, we might also impose monotonicity as
(V8,, E (i < (s(ss) + ho())) g(5))++o((s ho(s));
though does not affect the optimality of A We do this, since monotonic heuristic function implies A returning optimal solution. In Constraint equation 2 states not generated by A are ignored. But 5 will always contain all states of distance one from the optimal path, which is sufficient show that a loss equalling zero implies expanding states only on an optimal path (in the training set). To prevent confusion, we emphasize that conditions are designed for the heuristic he that is to be optimized, and not for the heuristic h that has generated the training set in the first place.
While Constraint equation 3 is true for every consistent heuristic, Constraint equation 2 is true only for perfect heuristics. Otherwise, we could have some earlier states in the exploration off the optimal path that have a smaller f-value than later ones in the optimal path. What seems to be restrrest,,, such that almost no heuristic function will ever fulfill, Constraint equation intentional.
The proposed L* loss minimizes the number of times each of the above constraints are violated as
1
Σ
Σ Ig(d') + hh((d) 2 g((") h+
S
#'ES"
""ES"
|8"1
i
1
El((s)) + ho(ss) > g(8;) + ho()))
S0 1)
1=1
where [:] is an Iverson bracket, which is equal to one the argument is true and zero otherwise. The first part of the loss function loosely upper bounds the number of non-optimal states the A expands while the second part ensures the monotonicity of the heuristic function along the optimal plan. In other words, the conditions equation 2 and equation encode the aim of consistent and
4

---

Under review as a conference paper at ICLR 2023
perfect heuristic. During training, we iterate many samples of A explorations which enlarges the scope L".
To set constraints for heuristic learning, we only need the partitioning of the set of explored nodes into the sets 5 and S",, computed via an optimal plan and set of all generated nodes, together with their g-values. Given the optimal heuristic, A will always find optimal solution. Up to tie-breaking, is optimally efficient and will expand only nodes with optimal merit f"
Loss function L does not distinguish between the Open and Closed lists in the exploration of A as long as it has access to the combined set of explored nodes. This way, we can take any optimal planner and just the heuristic search planners for training.
3.1 How L' ADDRESSES THE DEFICIENCIES OF Lg
L' utilizes all states generated during the A search used to create the training sample(s), which is in sharp contrast to L2 estimating cost-to-go. This propagates to hetter utilization of states in the training set. The experimental results show that given fixed and small number of training problems, models minimizing L achieves higher performance.
L' = 0 implies optimality. We state following theorem:
Theorem (Upper Bound) For a problem instance with states S S U U denote
R" {s" E S Es' E 5 A (g(s') ho(s') 2 g(s") + ho(s")))
(5)
the quantity [Ra| is an upper bound on the number of non-optimal states A expands during its search.
The proof is straightforward and it is included in supplementary for completeness. The quantity |R"| is exactly the quantity minimized by the L as defined in Equation equation 4 The following theorem is trivial consequence of this property.
Theorem 2 (Optimal efficiency) Let for a given training sample I and a heuristic function he [T" ho) = 0. Then A with heuristic function he will expand only states on the optimal path S So in I is optimal and shortest, A * will be optimally efficient.
The proof consequence of the property that L. (T, 0 implies that (R = The above theorem holds even on problems with multiple optimal solutions. In this case, L would be either equal zero, which means he includes tie-breaking mechanism and will be optimal, it will be greater than zero. Thus and unlike L2, its zero value implies optimal efficiency.
L. does not require heuristic value of unreachable (dead-end) states, which caused by the fact that L L'requires satisfaction of inequalities instead of estimation of some value. L loss does not force the heuristic to be goal aware, since discussed in Supplementary, this is not needed for the optimal efficiency of A*
RELATED WORK
In potential heuristics Seipp al. (015)) parameters of the heuristic functions are optimized by linear programming for a particular problem instance to satisfy constraints similar to those stated in this paper. The optimization assumes a particular structure of the heuristic, unlike here, where no structure is assumed. Ref. Takahashi et al. (2019) admits that the symmetry of T.2 (and of L,) loss does not promote admissibility of the heuristic. It recommends asymmetric T., with different weights on the left and right parts, but this does not completely solve the problems identified above in Section 2.3
In Ferber et al. (2020), neural networks estimate the number of expansions of GBFS search, though
the results are comparable to an estimation of cost-to-goal. In Bhardwaj et al. (017)) A is viewed a Markov Decision Process with value function being equal to the number of steps of A till it reaches the solution. While this detaches the heuristic values from cost-to-godt tosal cost, does not solve the problem with dead-ends, state efficiency, and ties.
5

---

Under review as a conference paper at ICLR 2023
Refs. Vlastelica et al. (2021); Yonetani et al. (2021) combine neural networks with discrete search algorithms, which become an inseparable part of the architecture. Orseau & Lelis (021) proposes a new search algorithm that uses both a heuristic function and policy networks minimize the search loss. Our setting is more classical where the heuristic is optimized for A* search but the execution of the search is independent of the training. This has the advantage that one (costly) execution of A# search algorithm is used many times during training to optimize weights.
A large corpus of literature Silver et al. (017)); Guez et al. (2018); Feng et al. (020); Anthony iet al. (0117) is devoted to improvements to Monte Carlo Tree Search. Since this work is concerned exclusively to A algorithm, we view these works independent to this. Nevertheless. we compare to some of them in the experimental section. Similarly, a lot of works [Shen et al. (2020); Toyer
al. 22200g ZZang & Geißer (202T); ; Groshev et al. (018); Chrestien et al.] (2021) : Ferber et al.
(2020); ; Bhhrdwaj et al. (201)) investigate architectures of neural networks for learning heuristic
function, ideally for arbitrary planning problems. These works are perpendicular to this one, which
investigate how to optimize these neural networks to perform well inside A*
5 EXPERIMENTAL EVALUATION
Heuristic functions optimized with respect to L* loss function are compared to those optimized with respect to L2 loss on seven domains. Due to lack of space, only Sokoban and Mazes with teleports are detailed below, and the remaining five are in supplementary material. This is supple- mented by the comparison with domain-indee indeaii-indeeeeennt planners: (1) SymBA* Torralba et al. (2014),
cost-optimal planner from International Planning Competition (IPC) 2014; (2) Delfi Katz et al. (2018); (3) Mercury 14 Katz & Hoffmann (2014), a satisfycing planner from IPC 2014; (4) Stone soupe Seipp & Röger (2018), and by solutions based on Monte Carlo Tree Search Guez et (2018)
and reinforcement learning Racanière et al. (201))) Guez et al. (2019). Ref. Toyer et al. (2020) admit does not work on Sokoban and [Shen al. (2020) works only on small Sokoban problems with two boxes, we do not compare to these works. All experiments involving neural networks have been repeated three times.
The Neural Network Neural networks (NN) implementing heuristic functions were adopted from Groshev et al. (2018) and Chrestien et al. (202T), where the latter is, to our best knowledge the state-of-the-art architecture for maze domains. It contains seven convolution layers Pi.... followed by four convolution-attention----iiiniii distant parts of the maze. The output tensor of the fourth CoAt block is "flattened" by global av- erage pooling over the and y dimension to vector, which is then fed to a fully connected layer (FC) which outputs scalar estimating the heuristic value. More details on the network can be found Chrestien et al. (202T) This network is further called "CoAt" after the CoAt blocks. We also studied the network of Groshev et al. (018) (without policy head), which has a similar structure, but instead of four CoAt blocks it has seven CNN layers. We refer to this network as to CNN. Both networks are by design scale-free, which means that they can be used on mazes of various sizes, as is shown below on the mazes with teleport domain. Since the Loloss as defined in Equation 4 is not differentiable, the Iverson bracket is replaced by a logistic loss function (z) = log(1 + exp (-)).
blocks, which allow correlating information from
Our experiments were implemented in Keras-2.4.3 with Tensorflow- 2.3.11 as the backend. For train- ing the neural networks, we used an NVIDIA Tesla GPU model V V100-SXM2-32GB; the evaluation was performed on the CPU ensure fair comparison to domain independent planners. The neural networks were trained by the Adam optimizer Kingma & Ba (2014) with a default learning rate of 0.001. Each mini-batch contained all states from one problem instance. Scripts reproducing our experiments together with mazes and solutions will be made available upon acceptance.
5.1 TRAINING FROM SOLVED MAZES
We generate mazes for the training set by running the A* algorithm using the heuristic function from Groshev et al. (2018) set of problem instances to identify set of states generated during the A search. All these sets form the training set. Since optimizing the heuristic by Ly loss requires knowing the true heuristic value (cost to reach the goal), have used SymBA* * Torralba et al. (2014) to find the optimal plan from each state in the training set. For states for which SymBA* doesn't find solution (dead-end states), the h value is replaced by very large value. This con-

---

Under review as a conference paper at ICLR 2023
CNN
CoAt
#6
SBA*
Delfi
Mere
FDSS
L2
L
L2
L
CL W.L
model
coverage
3
100
100
100
100
81
87
91
94
95
MCTSNet
84
4
100
100
81
100
74
80
89
93
94
12A
84
5
97
91
67
94
72
82
85
89
90
DRC (3,3) 10k
93
6
55
56
71
73
85
DRC (3.3) 900k
99
7
46
31
42
51
59
63
77
83
CoAt - L'"
97
8
32
59
CL CoAt L'
100
9
12
38
SBA*
100
(a)
(b)
Table I: Left: Fraction of solved mazes (in percents) of S(ym)BA* Delfi(l), Merc(ury14) FDSS (Fast Downward Stone Soup), CoAt and CoAt* on test data sets containing variable number of boxes. Column captioned #6 indicates the number of boxes in different categories. The standard deviation of all repeated experiments was between 0.004 and 0.008 and it is not shown to save space. Right: Fraction of solved mazes (in percents) from Boxoban dataset. DRC 900k DRC 10k optimizes on 10k levels. Results of MCTSNet Guez et al. (2018), 12A Racanière et al. (2017). and DRC al. (2019) have been copied from Table
Guez et al. (019).
struction, albeit very expensive, allows fair comparison, since the training of heuristic by L2 loss will also use states off the optimal path of the original problem instance for which the states were generated.
Sokoban's 's training set contained 10000 Sokoban mazes of size 10 x 10 with 3 boxes created using gym-sokoban [ccraderr (2018). The testing set contained 2000 mazes of the same size 10 x 10 but with 3, 4, 6, 7, 8, 9 boxes. The complexity increases with the addition of more boxes and therefore we can evaluate the ability to generalize outside training environments. We go step further and implement curriculum learning [Begiio al. (2009) by training from those mazes that are solved by our network during evaluation. We create a new training set containing all the solved mazes and re-train network in effort to improve the coverage of our network.
Size--iith-telepors's training set contained 5000 randomly generated mazes of size n X n = 15 x 15 with the agent in the upper-left corner and the goal in the lower-right corner. The mazes were generated using an open-source maze generator P where walls were randomly broken and pairs of teleports were randomly added the maze structure. The testing contained 2000 mazes generated by the same algorithm but (i) were bigger by up to 60 x 60 and (ii) were rotated by 90, 180, and 270 degrees which moved the start and goal states to positions not occurring in the training set.
5.2 RESULTS
Sokoban Table Ia shows the percentage of solved mazes of all compared planners on problem in- stances with a various number of boxes (recall that the NNs were optimized on instances with only three boxes). All planners were given a time limit of 10 minutes to solve each Sokoban instance. On mazes with 3 and 4 boxes, the optimal planners SymBA* (SBA* * and Delfi were able to solve all problem instances while the best performing architecture among the NNs, which is CoAt optimized with respect to I (CoAt L*), could solve 94% and 93% of the mazes respectively. On increasing the number of boxes, the A with NNs start outperforming classical planners. A with NNs optimiz- ing L is consistently better than those optimizing L2. The CoAt architecture proposed in Chrestien et al. (021)) with the proposed L is the only solver that can solve some mazes with 8 and boxes. Solutions found by CoAt optimizing L were close to optimum, on average by 1 step longer, which likely because the learnt heuristic is most of the times admissible (see Supplementary for details). The average number of expanded states in Figure 2a shows that NNs optimizing L "indeed expand smaller number of states than those optimizing Lg.
Since networks have never seen mazes with four or more boxes, extrapolation to eight and nine boxes impressive. To evaluate the potential for self-improvement, the training set of CoAt L'was
"This of course just an approximation, we can have simple problems with a large number of boxes thtps://gituu..oo///ra wtwp://wwww...eeaaeae//////aenee

---

Under review as a conference paper at ICLR 2023
Avg of expanded No boxes
Avg oxpanded states
CNNN-
3,000
CNN-Ia
3,000
CNN'L CoAt-L2 CoAI-1."
UNN-L
CoAt-L2 CoAI-1
NO OF EXPANOED
2,000
2,000
1,000
1,000
GLID
(a) Sokoban
(b) Maze with teleports
Figure 2: The average number of expanded states A for Sokoban (left) and Maze problems (right).
CNN
CoAt
Ti
SBA* * Delfi
Mere
FDSS
L2
L2 L
50
92
90
75
100
100
100
100
100
55
52
50
100
85
85
86
88
60
100
73
74
76
79
Table 2: Fraction of solved mazes with teleports of S(ym)BA* Delfi(1), Merc(ury14) 14), and A* algorithm with heuristic function implemented by CNN and CoAt networks optimized with respect to L2 and L," All solvers have solved all mazes of size 15-40, hence they are not shown Standard deviations of repeated experiments were between 0.005 and 0.008 are shown in Supplementary.
extended with mazes from the testing set it has already solved for fine-tuning. We refer to this as curriculum learning (CL. w. Lt) and the results are shown the last column of Table [a shows marginal improvement on mazes with 3-5 boxes but records significant improvement in performance over the vanilla I, on mazes exceeding 5 boxes.
Boxoban On unfiltered "Boxoban" levels from Guez al. (2019). A with heuristic implemented by CoAt network and optimized with respect to the proposed is compared to MCTSNet Guez et al.
(2018), Imagination augmented agent (I2A) Racanière et al. (017). and to DRC (3,3) network Guez al. 2019), with possible discrepancies, as results on the competing methods were taken from Guez
et al. 2019). CoAt was optimized on 10k mazes with boxes (it the same network as reported the previous paragraph), whereas others were optimized
900k mazes with 4 boxes. CoAt I. and MCTSNet knows the model, whereas DRC and I2A do not. The fraction of solved mazes shown in Table shows that CoAt L."trained 10k mazes is second best behind DRC (3.3) that is trained on 900k mazes, but DRC (3,3) trained on 10k mazes is already inferior. CoAt with one iteration of curriculum learning where the training set extended to contain previously solved mazes (from set used in previous paragraph) solves 100% of boxoban mazes. Needless to say that during optimization, DRC (3.3) used IG iterations of SGD, MCTSNets allowed 10M iterations of SGD, whereas CoAt optimized L "allowed just for 20k iterations, which is few magnitudes less.
Maze-withs-eeepoorts Fraction of solved mazes with teleports is shown in Table 2 A with heuristic implemented by NN was optimized on mazes of size 15 x 15 and has solved all mazes up to size 40 x 40 (not shown in the table) and beyond. The results mimic the results on Sokoban the sense that A with CoAt networks optimizing L is consistently outperforming those optimizing Lg.
All 2000 mazes in the training set were created such that the agent starts in the top left corner and the goal is in the bottom right corner. When mazes are rotated by 90", 180 and 270", the agent has to solve mazes with distributions very different to that on the training set, yet the fraction of solved mazes for CoAt L decreases by most 5% (see Table 3 in Supplementary). Average number of generated states in A with different heuristics is shown in Figure 2a Again, heuristics optimized with respect to T." expand smaller number of states during the search.
8

---

Under review as a conference paper at ICLR 2023
3000
4000
5000
6000
epoch
L
L2
L
L2
L
7.4
7.4
7.7
7.7
8.5
8.5
8.3
8.3
11
11
9.8
11
10
10
9.6
10
1000
3000
5000
15
18
11
16
12
18
14
16
epoch
L2
L
Lg
L
L2
L
31
19
19
15
62
69
36
49
48
42
45
29
35
18
20
62
75
44
75
57
73
34
66
2
45
68
39
51
34
34
67
77
51
80
61
80
49
77
69
83
59
67
41
59
63
76
62
80
74
82
50
86
84
90
78
83
66
75
(a) Sokoban
(b) Maze with teleports
Table 3: Fraction of solved mazes (in percents) when the networks optimized only mazes they have previously solved. First row corresponds to A with untrained network.
5.3 TRAINING FROM UNSOLVED MAZES
Let's now consider bootstrap protocol, where in each epoch, heuristic function implemented by the NN first used A to try to solve mazes from an available set of mazes (recall that we set 10min time limit for solving a maze) and then to optimize its parameters on a set of mazes it has solved. Similarly to reinforcement learning, if an un-optimized (which means uninformed) heuristics solves least a few mazes, can boot the learning.
In this experiment, the training set unsolved mazes is fixed. In the optimization of our NN over solved mazes, perform epoch. Hence the number of iteration and epoch coincide. Table shows percentages solved mazes on Sokoban and Maze with teleports for the first seven and four epochs (epoch number means that the network is untrained) for different sizes of the training set. The set of Sokoban mazes contained problems with three, four, and five boxes; the set of mazes with teleports contained problems of size 40 x 40.
We observe that the fraction of solved mazes increases with epochs and the speed of this growth significantly faster for heuristics optimized with respect to the proposed L*. To our surprise, the fraction of solved mazes does not grow faster when the number of initially unsolved set of mazes bigger. Yet we have observed that the fraction of solved unfiltered boxoban mazes increases as expected. A with the network optimized on the set of 6000 mazes could solve 96% of levels of unfiltered boxoban mazes after seven epochs. This agent has performed just 20.5k gradient descend steps, which is comparatively smaller than 1G steps of DRC (3,3) agent from Guez et al. (2018). Sections 5 and 6 in Supplementary contains additional evaluation five more domains (Sliding tile puzzle, Blockworld, Gripper, Ferry, and N-Puzzle) with the same conclusion: L is always better than L2.
CONCLUSION
This work has proposed I.* loss function for imitation learning in planning:it has been designed specifically maximize the efficiency of the A algorithm. L is zero, if and only if the basic monotonicity requirements on the f-value in A* are satisfied, so that the heuristic trained on this loss function is consistent and perfect. This enables A find the optimal solution an optimal time. has been shown that L2 does not have these guarantees. The experiments have verified the promises that A with heuristic functions optimized with respect L" always solve much higher number of problems, generate up 50% lesser states than those optimized with respect to the usual L2, and return nearly optimal solutions. By comparison to MCTSNets, we have shown that A with well trained heuristic can be competitive to Monte Carlo Tree Search. The training is also more efficient, as we use a much lesser number of SGD steps.
The proposed lososs well complements contemporary research, which pays lot of attention to the network architectures, as it can be used as a drop-in replacement for Lg. inspires us to design loss functions for other types of search algorithm and research neglected aspects, such as the construction of a representative training set. We see them as a limiting factor in the further endeavour to solve more difficult problem instances.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Thomas Anthony, Zheng Tian, and David Barber. Thinking fast and slow with deep learning and tree search. Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Gamett (eds.), Ad- vances Neural Information Processing Systems 30: Annual Conference on Neural In- formation Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp- 2017. URL /tts:://proooeeinnnss hewp:/oocceddioo..eeii.......... httpppsc.pppppp//....p/ Abstract html
Isabelle Guyon, Ulrike von Luxburg, Samy Bengio,
dBe @Be1344e21 2wl.4442275bbee http:////aaaoeeddddaeaaaaaaaaaaa
Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston. Curriculum learning. In ICML, pp. 41 41-48, 2009.
Mohak Bhardwaj, Sanjiban Choudhury, and Sebastian Scherer. Learning heuristic search via imita- tion. In Conference on Robot Learning. pp. 271-280. PMLR, 2017.
Leah Chrestien, Tomáš Pevný, Antonín Komenda, and Stefan Edelkamp. Heuristic search planning with deep neural networks using imitation, attention and curriculum learning. arXi::21
2021.
Lukás Chrpa. Combining learning techniques for classical planning: Macro-operators and entangle- ments. In ICTAI, pp. 79-86. IEEE Computer Society, 2010.
Rémi Coulom. Efficient selectivity and backup operators in monte-carlo tree search. In International conference on computers and games, pp. 72-83. Springer, 2006.
Edsger W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1: 269-271, 1959.
Stefan Edelkamp. Automated creation of pattern database search heuristics. In Model Checking and Artificial Intelligence, pp. 35-50, 2006.
Dieqiao Feng, Carla P. Gomes, and Bart Selman. Solving hard AI planning instances using curriculum-driven deep reinforcement learning. In Christian Bessiere (ed.), Proceedings of the Twenty-Ninte Ninth International Joint Conference Artificial Intelligence, IJCAI 2020, pp. 2198- 2205. ijcai.org 2020. doi: 10.24963iiccai.2220/004 URL /tttps://do..ooeo 24963/ ijcai. 2020/304
Patrick Ferber, Malte Helmert, and Jörg Hoffmann. Neural network heuristics for classical planning: A study of hyperparameter space. In ECAI, pp. 2346-2353, IOS Press, 2020.
Santiago Franco, Álvaro Torralba, Levi H. S. Lelis, and Mike Barley. On creating complementary pattern databases. In IJCAI, pp. 4302-4309, 2017.
Edward Groshev, Aviv Tamar, Maxwell Goldstein, Siddharth Srivastava, and Pieter Abbeel. Learn- ing generalized reactive policies using deep neural networks. 2018.
Arthur Guez, Théophane Weber, Ioannis Antonoglou, Karen Simonyan, Oriol Vinyals, Daan Wier- stra, Rémi Munos, and David Silver. Learning to search with metsnets. In International confer- ence on machine learning, pp. 1822-1831. PMLR, 2018.
Arthur Guez, Mehdi Mirza, Karol Gregor, Rishabh Kabra, Sébastien Racanière, Theophane Weber, David Raposo, Adam Santoro, Laurent Orseau, Tom Eccles, Greg Wayne, David Silver, and Tim- othy Lillicrap. An investigation of model-free planning. Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference
Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Ma- chine Learning Research, pp. press/v quez 9a htm
PMLR, 2019. URL http:////cceeeeeeeeeeeem mmr.
Peter E Hart, Nils J Nilsson, and Bertram Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE transactions on Systems Science and Cybernetics, 4(2):100-107, 1968.
10

---

Under review as a conference paper at ICLR 2023
Patrik Haslum, Adi Botea, Malte Helmert, Blai Bonet, and Sven Koenig. Nomain-indeeentee construction of pattern database heuristics for cost-optimal planning. In AAAI, pp. 1007-1012, 2007.
Malte Helmert and Gabriele Röger. How good is almost perfect? In AAAI, pp. 944.949. AAAI Press, 2008
Michael Katz and Joerg Hoffmann. Mercury planner: Pushing the limits of partial delete relaxation. IPC 2014 planner abstracts, pp. 43-47, 2014.
Michael Katz, Shirin Sohrabi, Horst Samulowitz, and Silvan Sievers. Delfi: Online planner selection for cost-optimal planning. IPC-9 planner abstracts, pp. 57-64, 2018.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv:1412.6980 2014.
Donald E Knuth and Ronald W Moore. An analysis of alpha-beta pruning. Artificial intelligence, 6 (4):293-326, 1975.
Richard E Korf. Macro-operators: A weak method for learning. Artificial intelligence, 26(1):35-77, 1985.
Drew V. McDermott. A heuristic estimator for means-ends analysis in planning. In AIPS, pp. 142- 149. AAAI, 1996.
David Ménager, Dongkyu Choi, Mark Roberts, and David W. Aha. Learning planning operators from episodic traces. In 2018 AAAI Spring Symposia. AAAI Press, 2018.
Ionut Moraru, Stefan Edelkamp, Santiago Franco, and Moisés Martínez. Simplifying automated pattern selection for planning with symbolic pattern databases. In KI, pp. 249-263. 2019.
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.
Sébastien Racanière, Théophane Weber, David Reichert, Lars Buesing, Arthur Guez, Danilo Jimenez Rezende, Adrià Puigdomènech Badia, Oriol Vinyals, Nicolas Heess, Yujia Li, et al. imagination-augmmente agents for deep reinforcement learning. Advances in neural information processing systems, 30:5690-5701, 2017.
Arthur L Samuel. Some studies in machine learning using the game checkers. recent progress. IBM Journal of research and development, 11(6):611-617, 1967.
Max-Philipp B. Schrader.
gym-sokoban.
ht http::///giibbb..cm/mmsshceaaae
gym- sokoban 2018.
Jendrik Seipp and Gabricle Röger. Fast downward stone soup 2018. IPC2018-Classicl Tracks, pp- 72-74, 2018.
Jendrik Seipp, Florian Pommerening, and Malte Helmert. New optimization functions for potential heuristics. In ICAPS, 2015.
William Shen, Felipe Trevizan, and Sylvie Thićbaux. Learning domain-indeependent planning heuristics with hypergraph networks. In ICAPS, volume 30, pp. 574-584, 2020.
David Silver, Julian Schritwieserr, Karen Simonyan, loannis 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):354-355 2017.
Takeshi Takahashi, He Sun, Dong Tian, and Yebin Wang. Learning heuristic functions for mobile robot path planning using deep neural networks. In ICAPS, volume 29, pp. 764-772, 2019.
2019,
Alvaro Torralba, Vidal Alcázar, Daniel Borrajo, Peter Kissmann, and Stefan Edelkamp. Symba*: A symbolic bidirectional a planner. In International Planning Competition, pp. 105-108, 2014.

---

Under review as a conference paper at ICLR 2023
Sam Toyer, Sylvie Thiébaux, Felipe Trevizan, and Lexing Xie. Asnets: Deep learning for gener- alised planning. Journal of Artificial Intelligence Research, 68:1-68, 2020.
Marin Vlastelica, Michal Rolinek, and Georg Martius. Neuro-algorithmic policies enable fast com- binatorial generalization. arXiv:2102.07456, 2021.
Xuemei Wang. Learning planning operators by observation and practice. In Kristian Hammond (ed.), pp. 335-340. AAAI, 1994.
Ryo Yonetani, Tatsunori Taniai, Mohammadamin Barckatain, Mai Nishimura, and Asako Kanezaki. Path planning using neural A search. International Conference on Machine Learning, pp- 12029-12033 PMLR, 2021.
Ziqi Zhang and Florian Geißer. Extending graph neural networks for generalized stochastic plan- ning. In Bridging the Gap Between Al Planning and Reinforcement Learning. 2021.
12


Reviews:
[{"review_id": "fALl8uWEOio", "reviewer": "Reviewer_8chY", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper proposes a new loss, called L* as opposed to L2 loss for training a heuristic to be used in A* search.\n", "summary_of_the_review": "In summary, I am not convinced that L2 loss is bad. In particular, DeepCubeA was able to solve Sokoban and Rubik's cube using L2 loss. To be really convincing, I would like to see a problem where DeepCubeA fails because of the L2 loss, but the L* loss is able to solve the problem. \n\n_____\n\nAfter reading the comment I have bumped my score a bit but still recommend reject because I would like to see direct comparisons with DeepCubeA. ", "strength_and_weaknesses": "I like the general direction of this paper. I could see how since L2 is not directly optimizing the main objective of being a good heuristic, a different objective could do better. \nHowever, I think that the framing does not compare L* to the current state of the art. \nIn particular, one main paper that was not cited is DeepCubeA. In that paper, they use the L2 loss, but use value iteration and curriculum learning to get around the problems laid out with L2 in this paper. So I would really like to see comparisons to DeepCubeA, where the L2 loss is swapped out with L*. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Slfr-RLLYDY", "reviewer": "Reviewer_oNqW", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper introduces a novel loss function L* for learning heuristic functions that attempts to shrink the size of the the A* search tree. While previous methods for learning heuristic functions relied on minimizing the L2 loss, this paper argues that L2 loss doesn't necessarily reduce the search tree size. Empirical results of Sokoban-like puzzles show that L* might indeed reduce the A* search effort.  ", "summary_of_the_review": "The paper introduces a novel and interesting loss function for learning heuristic functions for guiding the A* search. The results are somewhat preliminary and that is why I recommend rejection at this point. I do strongly encourage the authors to resubmit the paper if it is indeed rejected from this conference. The issues related to writing, lack of formalism, and missing important citations should all be easy to fix. The evaluation is the problem. The evaluation will be much stronger once L* is tested on more problem domains and compared with proper baselines. ", "strength_and_weaknesses": "Strength\n\nThis paper tackles one of the key weaknesses of learning heuristic functions to guide the A* search, which is the lack of a proper loss function. The L* loss seems to be a good step in the direction of having a loss function that is more correlated with the A* search effort.  \n\nWeaknesses\n\nWhile the problem the paper tackles is important and the idea for solving this problem is promising, the paper has several important weaknesses that might prevent it from being published at this point. \n\n1. The paper presents two types empirical evaluations. In the first, one uses classical planners to generate a training set from which a heuristic function is learned. In the second, the algorithm learns from the problems it is able to solve. The first setting is hardly interesting at all because it assumes the existence of a planner that is able to solve the problems. The second setting is the interesting one because it is general and it doesn't assume prior knowledge or a system for generating training data. I would have preferred an extensive evaluation on the second setting than the current mix of evaluations. \n2. The evaluation is somewhat week because the system is evaluated only on grid-based puzzles (Sokoban and Maze with teleports). Instead of showing results on the setting where classical planners generate a training set, I would have preferred to see results on more domains. \n3. The comparison of optimal classical planners with A* with a learned heuristic function is problematic as the planners are finding optimal solutions, while A* is finding suboptimal ones. Even if the solution costs are near optimal, the problems can be substantially easier if you lift the optimality requirement. MCTS and model-free methods aren't good baselines as they tend to be weak. MCTS suffers when planning on long horizons such as those of Sokoban (see [2]). Model-free methods are in disadvantage as they don't use the model to search, so one should expect that they perform rather poorly compared to search algorithms. \n4. A more fair comparison would be with satisficing planners, which don't have the guarantee of finding optimal solutions. Another baseline that should be included is WA* with a learned heuristic function with the L2 loss. WA* is surprisingly effective in the learning setting (see [5]). Levin tree search (LTS) [1][2] uses a policy to guide its search and it defines a loss function that is an upper bound on the size of the tree. One can then learn a policy that minimizes this loss. This is exactly what is done in this paper, but for a policy. It is natural to wonder how A* with the L* loss compares to LTS.   \n5. The paper misses important citations. Whenever talking about optimality of A*, the paper seems to be referring to [3]. The procedure described in Section 5.3 is called Bootstrap [4].\n\nReferences\n\n[1] Orseau, L.; Lelis, L.; Lattimore, T.; and Weber, T. 2018. Single-Agent Policy Tree Search With Guarantees. In Advances in Neural Information Processing Systems 31, 3201–3211. Curran Associates, Inc.\n\n[2] Orseau, Laurent and Levi H. S. Lelis. “Policy-Guided Heuristic Search with Guarantees.” AAAI (2021).\n\n[3] Rina Dechter and Judea Pearl. 1985. Generalized best-first search strategies and the optimality of A*. J. ACM 32, 3 (July 1985), 505–536. https://doi.org/10.1145/3828.3830 \n3.  \n\n[4] Arfaee, Shahab & Zilles, Sandra & Holte, Robert. (2011). Learning heuristic functions for large state spaces. Artif. Intell.. 175. 2075-2098. 10.1016/j.artint.2011.08.001. \n\n[5] Solving the Rubik's Cube with Deep Reinforcement Learning and Search. Forest Agostinelli*, Stephen McAleer*, Alexander Shmakov*, Pierre Baldi. Nature Machine Intelligence, Volume 1, 2019\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "74J8euTozOS", "reviewer": "Reviewer_ytHz", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The authors propose a novel loss function which is tailored specifically for learning A*-heuristics. $L$* captures (1) heuristic monotonicity and (2) optimal A*-search efficiency in terms of #node expansions. The authors motivates theoretically why $L$* overcome known limitations to L_p loss in terms of A* heuristics, and prove relevant theorems of $L$* to this end.\n\n$L$* is evaluated on 3 difficult problems (Sokoban, mazes with teleports and Boxoban levels). $L$* is shown to consistently outperform $L_2$-loss as well as other state-of-the-art methods. Good generalization to problem instances with increased complexity not trained on is shown. Finally, a novel application of curriculum learning for A*-heuristics is demonstrated to be highly effective, both in terms of performance and the small number of SGD-steps necessary. Learning $L$* from random initialization and by only training on solved problems for every epoch, show an amazing performance increase at a small fraction of the cost in SGD-steps, in comparison with what is necessary for competing methods to reach similar performance.", "summary_of_the_review": "The paper propose a simple but highly effective approach to learning good heuristics efficiently for A*-search in complex planning domains. The theoretical motivation is strong and well founded, the contributions significant, and the results well supported by a thorough empirical evaluation. If the demonstrated performance generalizes to other problem domains, then it is highly likely that the paper will have a high general impact.", "strength_and_weaknesses": "Strengths\n==========\n\nThe theoretical investigation on $L_2$ limitations and the desired and acquired properties of $L$*\n\nThe evaluation is very strong with respect to the selected problem domains.\n* $L_2$-loss is trained using the same training data as $L$*-loss (i.e. off the optimal path as well).\n* The use of an automatic planning method which is optimal (S(ym)BA*) as baseline.\n* Comparison with MCTS and model free methods DRC & I2A.\n* Learning with curriculum learning from random initiation with only training data produced by the method itself.\n\nLearning $L$* does not presuppose a distinction between open and closed sets. That is, the training data can be generated using other methods than search.\n\n\nWeaknesses\n==========\n\nSome parts of the paper, including equations, are not clear.\n* I can see no \\cdot but I interpret the $leq$ expression as an implicit indicator function (equivalent to the use of an Iverson bracket). I do however strongly suggest that you make this clear in the equation. E.g. by introducing an Iverson bracket explicitly, or by using the indicator function. Preferably something that is easy to *swap* out for $L_l(x)$.\n* \"During training, we iterate over many samples of A* explorations which enlarges the scope of L ∗ .\" - What does this mean? What is \"many samples of A* explorations\" exactly, is it over many different problem instances?\n* Theorem 2 and proof: \\bar should be over \\Gamma, not h_\\theta\n* \"the Iverson bracket is replaced by a logistics loss function $L_l(x) = $ ...\": This should be clarified, see the first bullet point.\n* \"could solve 96% of levels of unfiltered boxoban mazes after seven epochs.\": At epoch 8 then, which is not shown in Table 3? Please include it in Table 3.\n\n\nMinor things\n==========\n\n* \"The zero $L_2$ does not guarantee the optimal efficiency of A*\" -> \"$L_2$ = 0 does not ...\"\n* We propose a $L$* loss function\" -> \"We propose the $L$* loss function\"\n* A*-algorithm: \"go to 4\" -> \"go to 5\"?\n* \"Many prior art on\" -> \"Many prior works on\"\n* Footnote 3: $L_1$ and $L_2$ seem to be reversed in the second part of the sentence?\n* \"the extension to a set of plan is trivial\": Would be clearer for readers if it is fleshed out a bit more.\n* 4) \"the problems identified above in Section 2.3\": Be more specific here, e.g. what problems precisely (summarize).\n* \"DRC (3,3) allowed 1G iterations of SGD\" and other \"allowed\" in the same sentence: \"allowed\" -> \"used\"?\n* Table 3: Using a graph instead (i.e. $L_2$ and $L$* can use the same color for 3000, but one of them use line plot with '+' or similar) would give a better idea of rate of improvement, if shown as a function of epochs.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "1zckxwmQqF", "reviewer": "Reviewer_SoyE", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper deals with the problem of learning heuristic function for A*, a popular heuristic search algorithm that can guarantee optimality of solutions and expands the minimal number of states. The paper proposes L*, a loss function tailored for A* which minimizes an upper bound on the number of expanded states. The paper motivates L* by highlighting the problem of using L_2 loss function as done in previous work and present experimental analysis that shows that heuristic functions learned by L* have better coverage (i.e., number of solved instances in time limit) compared to heuristic learned by L_2 loss and by other selected baselines.", "summary_of_the_review": "Overall I think it is an interesting research direction and a well motivated approach that demonstrates nice experimental results. However, the paper is missing relevant literature, seem to have a conflict between the extensive focus on optimality and the actual theoretical guarantees the method provides, and lack of experimental results to experimentally support claims on optimality (i.e., analysis solution quality).", "strength_and_weaknesses": "Strengths:\n* Approach is well motivated, highlighting problems with using L_2\n* Experiments show improvement in coverage compared to the baselines\n\nWeaknesses:\n* Missing literature and baselines: there are many learning-based approaches for heuristic search that are not based on L_2 and are not cited in the paper [e.g., 1-4]. [1-2] have specifically focused on Sokoban. [3][4] are older works that avoid problems with L_2 by focusing on learning to rank.\n* Optimality: the paper seems to focus on A* and is motivated by the \"false sense of optimality\" in L2, however the proposed approach is, to my understanding, not optimal. Specifically:\n    - The theoretical optimality guarantees (Section 3.1) only hold for instances in the training set (i.e., to guarantee optimality in general, we would have to train on all possible instances).\n     - L* is not differentiable and there is no guarantee that training find optimal solution (even with respect to the training set).\n* Experimental results not sufficient to evaluate the proposed approach: Despite the focus on optimality, the experiments only focus on coverage and not on solution cost. Some of the baselines are not optimal, including Mercury 14, Stone soup, and the RL approach, as well as the proposed approach (to my understanding). It is therefore important to analyze what is the (average) obtained solution quality by each of the methods.\nGiven the lack of optimality and the comparison to non-optimal baselines, it would also be interesting to study the performance of the proposed L* heuristic function in greedy best-first search.\n* Proofs are said to be in the supplementary material, however I could not find such material (neither at the end of the document nor uploaded to OpenReview).\n\n\n[1] Orseau, Laurent, and Levi HS Lelis. \"Policy-guided heuristic search with guarantees.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 35. No. 14. 2021.\n\n[2] Feng, Dieqiao, Carla P. Gomes, and Bart Selman. \"The Remarkable Effectiveness of Combining Policy and Value Networks in A*-based Deep RL for AI Planning.\" (2021).\n\n[3] Garrett, Caelan Reed, Leslie Pack Kaelbling, and Tomás Lozano-Pérez. \"Learning to rank for synthesizing planning heuristics.\" Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. 2016.\n\n[4] Xu, Yuehua, Alan Fern, and Sungwook Yoon. \"Learning Linear Ranking Functions for Beam Search with Application to Planning.\" Journal of Machine Learning Research 10.7 (2009).", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject