On Using Admissible Bounds for Learning Forward Search Heuristics

Thank you very much for your valuable feedback and questions. We are pleased to know you believe our method is well-motivated, _"simple"_ and _"elegant"_. We now answer the questions and concerns you have raised. > The choice of using Greedy Best-first Search (GBFS) needs more justification as it is not guaranteed to find optimal solutions. Can the authors explain why they did not choose to experiment with A*? The reason for choosing GBFS over A\* is that the learned heuristic $\hat{h}$ is not guaranteed to be **admissible**, regardless of the ML method employed (NLM, LR or HGN) and how the heuristic is modelled ($\mathcal{N}$ vs $\mathcal{TN}$). An admissible heuristic is one that never exceeds the optimal plan cost $h^*$ for any state: $\forall s \in S, \hat{h}(s) \leq h^*(s)$. Unlike symbolic algorithms, machine learning methods (e.g., neural networks) do not provide such guarantees in general. It is important to note that this issue is not particular to our approach since, to the best of our knowledge, **all heuristics learned by ML methods lack admissibility**. The A\* algorithm is guaranteed to return an optimal plan *only when* the heuristic used to guide the search is admissible (Russell and Norvig, 2010, pp. 94-95). Since $\hat{h}$ is inadmissible, we cannot guarantee solution optimality regardless of the search algorithm employed (A\* or GBFS). Therefore, we disregard plan length altogether and evaluate search performance as the number of node evaluations needed to find a solution, i.e., focus on satisficing planning. In satisficing planning, A\* is known to often be slower than WA\* and GBFS (corresponding to WA\* with $W\rightarrow\infty$) because it needs to explore all the nodes below the best current $f=g+h$ value, while WA\* and GBFS do not. This is the main reason why our work and many others in the heuristic learning literature (Ferber et al., 2022; Gehring et al., 2022; Yoon et al., 2008) employ GBFS instead of A*. **A* is not an appropriate baseline for the satisficing setting.** > Overall the empirical results are quite weak. While the negative log-likelihood (NLL) and MSE losses improve, the downstream search performance, i.e., the average number of node evaluations, compared to baselines (either the non-truncated Gaussian or using directly) is not convincing. We address this concern in the common answer to all reviewers (additional tiebreaking experiments). > A popular direction for evaluating the effectiveness of a learned heuristic is to test how well it generalizes to larger instances of a class of problems. The current evaluations focus only on problems generated with the same set of parameters. Adding this kind of generalization experiment would demonstrate the practical value of the proposed approach better. We have performed new experiments where we test the generalization abilities of the learned heuristics on larger problems. An overall analysis of the results obtained can be found in the common answer to all reviewers. > The three classical planning problems should have sufficiently detailed descriptions. We have added detailed descriptions for the three domains (blocksworld, logistics and satellite) used in our paper, along with their PDDL encodings. This information can now be found in Appendix I. > Can the authors add the standard deviation numbers for the average number of node evaluations to Table 2? We have added the std of node evaluations, as requested. This new information can be found in Appendix F. We hope to have successfully addressed all your questions and concerns with our answers and paper additions.

Thank you very much for your encouraging words and valuable feedback. We are deeply pleased to know you have enjoyed our paper and found it _"well-written"_, _"convincing"_ and note that _"the empirical results further support it"_. We are delighted with your statement that _"this is a great paper that successfully challenges the accepted wisdom of using MSE when learning heuristics"_.

Thank you very much for your valuable feedback and insightful comments. We are pleased to know you found our method _"novel"_ and _"principled"_. We address your comments and concerns below. > a new approach for learning heuristic for forward search (specifically, for greedy best-first search) Just a small clarification. The heuristic learned with our method is not tailored to any specific search algorithm (e.g., GBFS) and can in principle be applied to other algorithms such as A\*. We use GBFS in our experiments because the heuristic learned with our approach (or any other ML method) is never guaranteed to be admissible and, thus, regardless of the search algorithm plan optimality is not guaranteed. Therefore, we disregard plan length altogether and focus on satisficing planning, i.e., finding a solution with as few node evaluations as possible. In satisficing search, A\* is slower than WA\* and GBFS (which corresponds to WA* with $W\rightarrow\infty$) because A\* must explore all nodes below the current best $f=g+h$ value. > Missing comparison with (Chrestien et al., 2022) Thank you for highlighting this interesting work. We would like to note that (Chrestien et al., 2022) follows the learning-to-rank approach initiated by (Garrett et al., 2016) which learns the relative quality between states, with an additional loss for enforcing heuristic monotonicity. We believe the method proposed in (Chrestien et al., 2022) corresponds to a learning-to-rank approach because the proposed L\* loss function tries to rank the states expanded by A\* before those which are not (as well as ranking them according to monotonicity), modeling the learning task as a binary classification rather than a regression as in our work. We want to emphasize that **learning-to-rank methods deviate significantly from the cost-to-go learning literature** (which our work belongs to), both empirically and theoretically, as they pursue a different goal (correct node ordering vs correct cost-to-go estimation) and, thus, are significantly outside the scope of our work. Our paper aims at addresssing the lack of formal understanding in the cost-to-go learning literature and, in section 3, paragraph 8, we explicitly state that our goal is to learn the cost-to-go $p^*(x|s)$. Learning-to-rank methods directly optimize search performance by learning the node ordering. On the other hand, cost-to-go approaches learn to estimate the distance from some particular state to the goal, a unique capability missing from ranking-based methods. Being able to estimate the cost-to-go is useful in many practical applications, e.g., knowing the estimated travel time to destination in a mobile navigation app (e.g., Google Maps), as opposed to just knowing which direction to go at every intersection (equivalent to ranking the directions). Applying our theoretical intuition from $\mathcal{TN}$ to the learning-to-rank approach is an interesting direction for future work. > In the experiments, it looks that the standard $h^{FF}$ baseline outperforms the proposed approach in terms of problem solved in two out of the three domains. We address this concern in the common answer to all reviewers (new tiebreaking experiments). > There is no analysis of performance vs. problem size. It would be very useful to see if the patterns depend on problem size. We have performed new experiments where we test the generalization abilities of the learned heuristics on larger problems. An overall analysis of the results obtained can be found in the common answer to all reviewers. > in Section 3, the description of learning heuristic ignores the goal Thank you for bringing this oversight to our attention. It has now been corrected in the revision, by stating that heuristics depend on both states and goals.

Thank you very much for your valuable feedback and comments. We are glad you enjoyed reading our work. We now answer the questions and concerns you have raised. ### Re: Question 1 Firstly, we would like to clarify a point of a slight confusion. Your comment mentions as follows: > In my view, ... to use the NLL as their training loss **instead of** MSE, ... > In section 3 ... the importance of using NLL loss function **instead of** MSE. Let us clarify that "use NLL **instead of** MSE" involves a slight misnomer, as the MSE is indeed a NLL for $\mathcal{N}(\mu, \sigma=1/\sqrt{2})$. In our paper, we wrote: > [Main paper, Section 2, Paragraph 5] We emphasize that the choice of the distribution determines the loss. This means that there is a 1-to-1 correspondence between the distribution used and the loss to minimize, i.e., they are **_two sides of the same coin_**. Therefore, as to the question > ... does this truncated Gaussian technique play the major role ... instead of the choice of loss function? We answer that _the choice of our loss function is a direct consequence of choosing the truncated Gaussian distribution_, therefore it is not possible to choose them separately. For example, using a truncated Gaussian while minimizing a standard MSE loss is impossible/contradicting (minimizing MSE implies using $\mathcal{N}(\mu, \sigma=1/\sqrt{2})$). Likewise, switching modelling assumptions during training and evaluation (e.g., train the model with $\mathcal{N}(\mu, \sigma)$, then reuse the network for $\mathcal{TN}(\mu, \sigma, l, \infty)$) is highly ad-hoc and should not be done. In addition, regarding this comment: > the authors can only claim that $\mathcal{TN}$ obtains around 40 percent lower MSE than $\mathcal{N}+clip$ on (geometric) average, ... we would like to mention that predictions from the $\mathcal{N}+clip$ model are never worse than those of $\mathcal{N}$, since $\mathcal{N}+clip$ prevents incorrect heuristic predictions that are smaller than the admissible heuristic. Therefore, we can not only claim that $\mathcal{TN}$ is better than $\mathcal{N}+clip$, but also claim that it is better than $\mathcal{N}$ too. ### Re: Question 2 Next, regarding the question > And what is the statistical intuition behind it? and a related weakness comment: > ... the reason for using Gaussian distribution by giving the principle of maximum entropy, but the reason for using Truncated Gaussian seems missing and unconvincing. We emphasize that, as explained in Section 4 of our paper, $\mathcal{N}$ and $\mathcal{TN}$ are both maximum entropy (max-ent) distributions, but for different sets of initial constraints/assumptions (Dowson & Wragg, 1973). They both assume a finite mean and variance, but $\mathcal{N}$ assumes its support is $\mathbb{R}$ whereas $\mathcal{TN}$ assumes it is an interval $(l, u)$. We know that the value of the optimal heuristic $h^{\ast}$ is always larger or equal to that of an admissible heuristic $h^{\downarrow}$. Therefore, according to the max-ent principle, $h^{\ast}$ should **not** be modelled as a $\mathcal{N}$, but as a $\mathcal{TN}$ with lower bound $l=h^{\downarrow}$. This modelling choice results in significantly better heuristics (see Tables 1 and 2). ### Re: Weaknesses: More parameters? > NLL adds the prediction of $\sigma$ ... the model will predict better with more parameters. Our improvement is not due to an increase in the number of parameters. In order to predict $\sigma$, the neural network (NLM) needs to have two outputs, but this only affects the size of the last linear layer of the network, which is negligible compared to the size and parameters of the entire network. Moreover, in our preliminary experiments, doubling the total number of model parameters (NLM width) did not significantly affect the performance. The reason why our NLL loss outperforms the standard MSE is due to the underlying modelling assumptions: standard MSE models $h^*$ as $\mathcal{N}(\mu,1/\sqrt{2})$, which is bad; the "MSE with learned sigma" models it as $\mathcal{N}(\mu,\sigma)$, which is better but still bad; finally, our NLL models it as $\mathcal{TN}(\mu,\sigma,lb=h^{\downarrow},\infty)$, which is the best model both empirically and theoretically (max-ent distribution). This is easy to check by looking at Table 1 in our main paper. It can be observed that $\mathcal{TN}$ for the _fixed/none_ and _fixed/_ $h^{FF}$ configurations obtains better accuracy (_MSE_ rows) than $\mathcal{N}$ for _learn/none_ and _learn/_ $h^{FF}$. This means that an ML model that only predicts $\mu$ (_fixed_ configurations) and is trained with our custom NLL outperforms another model that predicts both $\mu$ and $\sigma$ (_learn_ configurations) but is trained with the standard MSE. We believe our answers address all your questions and concerns.