Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: 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.  
strength_and_weaknesses: Strength

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

Weaknesses

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

1. 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. 
2. 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. 
3. 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. 
4. 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.   
5. 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].

References

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

[2] Orseau, Laurent and Levi H. S. Lelis. “Policy-Guided Heuristic Search with Guarantees.” AAAI (2021).

[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 
3.  

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

[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

clarity,_quality,_novelty_and_reproducibility: Clarity

The paper is mostly easy to understand. However, I do miss a more formal treatment with respect to A*'s optimality. I don't understand what it means to have a "false sense of optimality", for some definition of optimality. 

Quality

While the idea is promising and interesting, the execution is lacking (see my comments above).

Novelty

The loss function is novel, to the best of my knowledge. 

Reproducibility

The idea is simple enough (which is something very positive!) that should be easy for someone to reproduce the results of this paper. 
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.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.

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. 
However, I think that the framing does not compare L* to the current state of the art. 
In 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*. 

clarity,_quality,_novelty_and_reproducibility: I think the paper was well-written. To my knowledge, this is the first paper looking at different losses than L2 for heuristic search, so it is novel in that respect. It should be relatively reproducible. 
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. 

_____

After reading the comment I have bumped my score a bit but still recommend reject because I would like to see direct comparisons with DeepCubeA.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.
strength_and_weaknesses: Strengths:
* Approach is well motivated, highlighting problems with using L_2
* Experiments show improvement in coverage compared to the baselines

Weaknesses:
* 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.
* 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:
    - 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).
     - L* is not differentiable and there is no guarantee that training find optimal solution (even with respect to the training set).
* 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.
Given 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.
* 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).


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

[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).

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

[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).
clarity,_quality,_novelty_and_reproducibility: - The paper is mostly clear and easy to follow.

- The approach seems mostly novel, however there is missing literature (including techniques that do not rely on L_2 loss) that need to be cited and the difference and similarities to proposed approach should be highlighted. Details provided above.

- Reproducibility: the work seems reproducible and the author state that they will make "Scripts reproducing our
experiments together with mazes and solutions" available upon acceptance. However, I was not able to find the supplementary material that the paper mentioned should include the proofs and additional discussion.

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).
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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.

$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.
strength_and_weaknesses: Strengths
==========

The theoretical investigation on $L_2$ limitations and the desired and acquired properties of $L$*

The evaluation is very strong with respect to the selected problem domains.
* $L_2$-loss is trained using the same training data as $L$*-loss (i.e. off the optimal path as well).
* The use of an automatic planning method which is optimal (S(ym)BA*) as baseline.
* Comparison with MCTS and model free methods DRC & I2A.
* Learning with curriculum learning from random initiation with only training data produced by the method itself.

Learning $L$* does not presuppose a distinction between open and closed sets. That is, the training data can be generated using other methods than search.


Weaknesses
==========

Some parts of the paper, including equations, are not clear.
* 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)$.
* "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?
* Theorem 2 and proof: \bar should be over \Gamma, not h_\theta
* "the Iverson bracket is replaced by a logistics loss function $L_l(x) = $ ...": This should be clarified, see the first bullet point.
* "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.


Minor things
==========

* "The zero $L_2$ does not guarantee the optimal efficiency of A*" -> "$L_2$ = 0 does not ..."
* We propose a $L$* loss function" -> "We propose the $L$* loss function"
* A*-algorithm: "go to 4" -> "go to 5"?
* "Many prior art on" -> "Many prior works on"
* Footnote 3: $L_1$ and $L_2$ seem to be reversed in the second part of the sentence?
* "the extension to a set of plan is trivial": Would be clearer for readers if it is fleshed out a bit more.
* 4) "the problems identified above in Section 2.3": Be more specific here, e.g. what problems precisely (summarize).
* "DRC (3,3) allowed 1G iterations of SGD" and other "allowed" in the same sentence: "allowed" -> "used"?
* 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.
clarity,_quality,_novelty_and_reproducibility: As mentioned under Strength And Weaknesses, there are some clarity issues. However, the gist of the paper is clear. Most importantly, the theoretical and the empirical results (and methodology) are clear.
The quality is good (great if listed issues are fixed), novelty is very high and reproducibility is high.
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.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The reviewers agreed that the new loss function proposed in this paper is a novel and good idea.   There was some moderately substantial disagreement about the quality and and conclusiveness of the experimental results.

The major concerns were:
- An inconsistent use of "optimal".   A* and other planning algorithms are used to seek actual optimal solutions, but here due to lack of guaranteed admissibility of the heuristic, results are not necessarily optimal.  Also, experimental results compared both "optimal" and "satisficing" planners without clarity.  It seems that the authors are interested in finding cost-efficient, though not necessarily optimal solutions.  But most of the experimental results focused on planning efficiency not cost efficiency.  This needs to be made much clearer.
- A question of where the training data were to be obtained---it is somewhat less motivating if you have to be able to solve the very type of planning instances in training that you will eventually be testing on.
- A lack of comparison to closest competing approaches, such as Orseau et al or Feng et al
- Similarity of testing domains (grid worlds using a CNN to implement the learned heuristic) which might not be at all representative of the much larger space of planning problems.


justification_for_why_not_higher_score: There were very substantial concerns about the validation, including not a broad enough set of test problems.
Decision: Reject