On Using Admissible Bounds for Learning Forward Search Heuristics

1 Introduction

Motivated by the success of Machine Learning (ML) approaches in various decision making tasks [Mnih et al., 2015; Silver et al., 2016], an increasing number of papers are tackling the problem of learning a heuristic function for forward state space search in recent years. Despite this interest, there has been little theoretical understanding of what these systems should learn, how to train them and why we do so. As a result, heuristic learning literature has adopted many different training targets (corresponding to either admissible heuristics [Shen et al., 2020], suboptimal solution costs [Arfaee et al., 2011; Ferber et al., 2022; Marom and Rosman, 2020] or optimal solution costs [Ernandes and Gori, 2004; Shen et al., 2020]) and training losses (e.g., square errors [Shen et al., 2020], absolute errors [Ernandes and Gori, 2004] and piecewise absolute errors [Takahashi et al., 2019]).

In this work, we try to answer these questions from a statistical lens, focusing on how to effectively utilize admissible heuristics in the context of heuristic learning. We argue that learning from poly-time admissible heuristics, such as hLMcut [Helmert and Domshlak, 2009], by minimizing mean square errors (MSE) does not provide any practical benefits, since its result is merely a noisy, inadmissible copy of a heuristic that is already efficient to compute. Then, if admissible heuristics should not be used as training targets, how can we leverage them? In order to answer this question, we first analyze the statistical implications behind the commonly used loss function, the MSE, which implicitly models the learned heuristic as a Gaussian distribution. Nonetheless, we contend that a better modeling choice for heuristics is given by the Truncated Gaussian distribution (Fig. 1), due to the existence of bounds on the values a heuristic can take (e.g., heuristics never take on negative values).

The main contribution of this paper is a theoreticallymotivated, statistical method for learning an inadmissible heuristic while exploiting an admissible heuristic. We propose to model the learned heuristic as a Truncated Gaussian, where an admissible heuristic provides the lower bound of this distribution, thus constraining heuristic predictions. This modeling choice results in a loss function to be minimized that is different from the standard MSE loss. We conduct extensive experimentation where both loss functions are applied to learning heuristics from optimal plan costs in several classical planning domains. Results show that those methods which model the learned heuristic as a Truncated Gaussian, i.e., which are trained with our novel loss function, learn faster and result in better heuristics than those which model it as an ordinary Gaussian, i.e., which are trained with the standard MSE loss. To the best of our knowledge, this is the first work that proposes the use of admissible heuristics to constrain heuristic predictions and improve learning. 1

2 Backgrounds

2.1 Classical Planning and Heuristics

We define a propositional STRIPS Planning problem as a 4-tuple ⟨P,A, I,G⟩ where P is a set of propositional variables, A is a set of actions, I ⊆ P is the initial state, and G ⊆ P is a goal condition. Each action a ∈ A is a 4-tuple ⟨PRE(a), ADD(a), DEL(a), COST(a)⟩ where COST(a) ∈ Z0+ is a cost, PRE(a) ⊆ P is a precondition and ADD(a), DEL(a) ⊆ P are the add-effects and delete-effects, respectively. A state s ⊆ P is a set of true propositions (all of P \ s are false), an action a is applicable when s ⊇ PRE(a) (read: s satisfies PRE(a)), and applying action a to s yields a new successor state a(s) = (s \ DEL(a)) ∪ ADD(a).

The task of classical planning is to find a sequence of actions called a plan (a1, · · · , an) where, for 1 ≤ t ≤ n, s0 = I, st ⊇ PRE(at+1), st+1 = at+1(st), and sn ⊇ G. A plan is optimal if there is no plan with lower cost-to-go ∑t COST(at). A plan is otherwise called satisficing. In this paper, we assume unit-cost: ∀a ∈ A; COST(a) = 1.

1 Our full code and data can be found in github.com/pddl-heuristiclearning/pddlsl. We provide the Appendix in the Arxiv version of our paper: arxiv.org/abs/2308.11905.

A domain-independent heuristic function h in classical planning is a function of a state s and the problem ⟨P, A, I, G⟩. It returns an estimate of the shortest (optimal) path cost from s to one of the goal states (states that satisfy G), typically through a symbolic, non-statistical means such as deleterelaxation, a technique that ignores the delete-effects of actions in order to efficiently estimate the cost from s to G. The optimal cost-to-go, or a perfect heuristic, is denoted by h∗ . A heuristic is called admissible if it never overestimates it, i.e., ∀s; 0 ≤ h(s) ≤ h∗ (s), and inadmissible otherwise. Notable admissible heuristics include hLMcut , hmax and h+ [Helmert and Domshlak, 2009; Bonet and Geffner, 2001; Betz and Helmert, 2009], whereas hFF, hadd and hGC [Hoffmann and Nebel, 2001; Bonet and Geffner, 2001; Fikes et al., 1972] are prominent examples of inadmissible heuristics.

2.2 Task: Supervised Learning for Heuristics

Let p∗ (x) be the unknown ground-truth probability distribution of (an) observable random variable(s) x and let p(x) be our current estimate of it. Given a dataset X = {x(1) , . . . , x(N)} of N data points, we denote an empirical data distribution as q(x), which draws samples from X uniformly. While often q(x) may also be informally called a ground-truth distribution, q(x) is entirely different from either p(x) or p∗ (x) because it is a distribution over a finite set of points, i.e., a uniform mixture of dirac's delta δ distributions (Eq. 1). Our goal is to obtain an estimate p(x) that resembles p∗ (x) as closely as possible. To do so, under the Maximum Likelihood Estimation (MLE) framework, we maximize the expectation of p(x) over q(x). In other words, MLE tries to maximize the expected probability p(x) of observing each data point x ∼ q(x):

Typically, we assume p∗ (x) and p(x) are of the same family of functions parameterized by θ, such as a set of neural network weights or the trees in random forests, i.e., p∗ (x) = pθ∗(x), p(x) = pθ(x). This makes MLE a problem of finding the θ maximizing Eq(x)pθ(x). Also, we typically minimize a loss such as the negative log likelihood (NLL) - log p(x), since log is monotonic and preserves the optima θ∗ (Eq. 2). Furthermore, Eq(x) . . . is often estimated by Monte-Carlo sampling, e.g., Eq(x) - log p(x) ≈ 1N ∑Ni=1 -log p(xi), where each xi is sampled from q(x).

We further assume p(x) to follow a specific distribution such as a Gaussian distribution N (µ, σ):

We emphasize that the choice of the distribution determines the loss. When the model designer assumes p(x) = N(µ, σ), then the NLL is a shifted and scaled squared error:

Likewise, a Laplace distribution L(x|µ, b) = 1 2b e- |x-µ| b represents the absolute error because its NLL is |x-µ| b + log 2b.

The NLL loss is thus more fundamental and theoretically grounded than losses such as the Mean Squared Error, although it is "more complicated" due to the division 1 2σ2 and the second term. A reader unfamiliar with statistics may rightfully question why such complications are necessary or why σ is not commonly used by the existing literature. It is because many applications happen to require only a single prediction for a single input (point estimate): When we model the output distribution as a Gaussian N(µ, σ), we often predict µ, which is simultaneously the mean and the mode of the distribution and does not depend on σ.

Moreover, the MSE is a special case of the NLL that can be derived from it. To derive the MSE, we first simplify the loss into the squared error (x-µ)2 by setting σ to an arbitrary constant, such as σ = 1 √2 , because the variance/spread of the prediction does not matter in a point estimation of µ. As a result, we can also ignore the second term which is now a constant. We then compute the expectation Eq(x)(x - µ)2 with a MonteCarlo estimate that samples N data points x1, . . . xN ∼ q(x), predict µ = µθ(xi) for each xi using a machine learning model µθ, and compute the average: 1N ∑Ni=1 (xi - µθ(xi))2 . In other words, the MSE loss is nothing more than the Monte-Carlo estimate of the NLL loss of a Gaussian with a fixed σ = 1 √2 . In contrast, distributional estimates represent the entire p(x); e.g., if p(x) = N(µ, σ), then the model predicts both µ and σ.

The MLE framework can be applied to the supervised heuristic learning setting as follows. Let q(s, x) be the empirical data distribution, where s is a random variable representing a state-goal pair (from now on, we will implicitly assume that states s also contain goal information) and x a random variable representing the cost-to-go (regardless of whether it corresponds to a heuristic estimate, optimal or suboptimal cost). Then, the goal is to learn p∗ (x | s) where:

and µθ(s) is the main body of the learned model, such as a neural network parameterized by the weights θ. Supervised heuristic learning with distributional estimates is formalized similarly, where the only difference is that an additional model (e.g. a neural network) with parameters θ2 predicts σ:

2.3 The Principle of MaximumEntropy

The discussion above models p(x) as a Gaussian distribution. While the assumption of normality (i.e., following a Gaussian) is ubiquitous, one must be able to justify such an assumption. The principle of maximum entropy [Jaynes, 1957] states that p(x) should be modeled as the maximum entropy (max-ent) distribution among all those that satisfy our constraints or assumptions, where the entropy is defined as Ep(x)⟨- log p(x)⟩. A set of constraints defines its corresponding max-ent distribution which, being the most random among those that satisfy those constraints, minimizes assumptions other than those associated with the given constraints. Conversely, a non max-ent distribution implicitly encodes additional or different assumptions that can result in an accidental, potentially harmful bias. For example, if we believe that our random variable x has a finite mean, a finite variance and a support/domain/range equal to R, then it must be modeled as a Gaussian distribution according to this principle because it is the max-ent distribution among all those that satisfy these three constraints.

In other words, a person designing a loss function of a machine learning model must devise a reasonable set of constraints on the target variable x to identify the max-ent distribution p(x) of the constraints, which automatically determines the correct NLL loss for the model. This paper tries to follow this principle as faithfully as possible.

3 Utilizing Bounds for Learning

In the previous section, we provided some statistical background on heuristic learning. We now leverage this background to analyze many of the decisions taken in the existing literature, sometimes unknowingly, putting particular focus on how admissible heuristics are used during training. Based on this analysis, we argue that the proper way of utilizing the information provided by admissible heuristics is using them as the lower bound of a Truncated Gaussian distribution representing the learned heuristic.

We previously explained that the heuristic to be learned is modeled as a probability distribution (e.g., a Gaussian), instead of a single value: The ML model is unsure about the true heuristic value h∗ associated with a state s. When it predicts µ, it believes not only that µ is the most likely value (the mode) for h∗ , but also that other values are still possible. The uncertainty of this prediction is given by σ: The larger this parameter is, the more unsure the model is about its prediction. The commonly used MSE loss is derived from the ad-hoc assumption that σ is fixed, i.e., independent from s, which means that the model is equally certain (or uncertain) about h∗ for every state s. This is unrealistic in most scenarios: it is generally more difficult to accurately predict h∗ for states that are further from the goal, for which the uncertainty should be larger. Therefore, the model should predict σ in addition to µ, i.e., it should output a distributional estimate of h∗ instead of a point estimate.

Another crucial decision involves selecting what to learn, i.e., the target / ground truth to use for the training. It is easy to see that training a model on a dataset containing a practical (i.e., computable in polynomial time) heuristic, admissible or otherwise, such as hLMcut or hFF, does not provide any practical benefits because, even if the training is successful, all we get is a noisy, lossy, slow copy of a heuristic that is already efficient to compute. Worse, trained models always lose admissibility if the target is admissible. To outperform existing poly-time heuristics, i.e., achieve a super-symbolic benefit from learning, it is imperative to train the model on data of a better quality, such as h+ as proposed in [Shen et al., 2020] or optimal solution costs h∗ . Although obtaining these datasets may prove computationally expensive in practice, e.g., h+ is NP-hard, we can aspire to learn a heuristic that outperforms the poly-time heuristics by training on these targets.

If poly-time admissible heuristics are not ideal training targets, are they completely useless for learning a heuristic? Intuitively this should not be the case, given the huge success of heuristic search where they provide a strong search guidance toward the goal. Our main question is then how we should exploit the information they provide. To answer this question, we must revise the assumption we previously made by using squared errors: That x = h∗ follows a Gaussian distribution N(µ, σ). The issue with this assumption is that N(µ, σ) assigns a non-zero probability p(x) to every x ∈ R, but we actually know that h∗ cannot take some values: Given some admissible heuristic like hLMcut , we know that hLMcut ≤ h∗ holds for every state; therefore p(x) = 0 when x < hLMcut . Analogously, if for some state s we know the cost hsat of a satisficing (non-optimal) plan from s to the goal, then hsat acts as an upper bound of h∗ .

According to the principle of maximum entropy, which serves as our why, if we have a lower l and upper u bound for h∗ , then we should model h∗ using the max-ent distribution with finite mean, finite variance, and a support equal to (l, u), which is the Truncated Gaussian distribution T N(x|µ, σ, l, u) as proven in [Dowson and Wragg, 1973], formalized as Eq. 8:

l is the lower bound, u is the upper bound, µ is the pretruncation mean, σ is the pre-truncation standard deviation, and ERF is the error function. T N has the following NLL loss:

Modeling h∗ as a T N instead of N presents several advantages. Firstly, T N constrains heuristic predictions to lie in the range (l, u) given by the bounds of the distribution. Secondly, T N generalizes N as T N (µ, σ, -∞, ∞) = N (µ, σ) when no bounds are provided. Finally, T N opens the possibility for a variety of training scenarios for heuristic learning, with a sensible interpretation of each type of data, including the satisficing solution costs.

In this work, we focus on the scenario where an admissible heuristic h is provided along with the optimal solution cost h∗ for each state, leaving other settings for future work. In this case, h acts as the lower bound l of h∗ , which is modeled as a T N(x = h∗ |µ, σ, h,∞), where µ and σ are predicted by an ML model. Note that we cannot use h∗ as T N(h∗ |µ, σ, h∗ , h∗ ) since, during evaluation/test time, we do not have access to the optimal cost h∗ . Also, this modeling decision is feasible even when no admissible heuristic is available (e.g., when the PDDL description of the environment is not known, as in Atari games [Bellemare et al., 2013]) since we can always resort to the blind heuristic hblind (s) or simply do l = 0, which still results in a tighter bound than the one provided by an untruncated Gaussian N (µ, σ) = T N (µ, σ, -∞, ∞).

Finally, our setting is orthogonal and compatible with residual learning [Yoon et al., 2008], where the ML model does not directly predict µ but rather a residual or offset ∆µ over a heuristic h, where µ = h + ∆µ. Residual learning can be seen as initializing the model output µ around h which, when h is a good unbiased estimator of h∗ , facilitates learning. This technique can be used regardless of whether h∗ is modeled as a T N or N because it merely corresponds to a particular implementation of µ = µθ(s), which is used by both distributions. Residual learning is analogous to the data normalization commonly applied in standard regression tasks, where features are rescaled and shifted to have mean 0 and variance 1. However, residual learning is superior in the heuristic learning setting because target data (e.g., h∗ ) is skewed above 0 and because the heuristic used as the basis for the residual can handle out-of-distribution data due to its symbolic nature.

3.1 Planning with a Truncated Gaussian

At planning time, we must obtain a point estimate of the output distribution, which will be used as a heuristic to determine the ordering between search nodes. As a point estimate, we can use any statistic of central tendency, thus we choose the mean. It is important to note that the µ parameter of T N(µ, σ, l, u) is not the mean of this distribution since µ corresponds to the mean of N(µ, σ) (i.e., the mean of the distribution before truncation) and does not necessarily lie in the interval (l, u). The mean of a Truncated Gaussian is obtained according to Eq. 10. Note that a naive implementation of this formula results in rounding errors (See the Appendix for a numerically stable implementation).

Eq. 10 satisfies l ≤ E[x] ≤ u. This means that, when a lower bound l is provided (e.g., by an admissible heuristic), the heuristic prediction returned by the model will never be smaller than l. Analogously, when an upper bound u is also provided (e.g., by a satisficing solution cost), the model will never predict a heuristic value larger than u. With this, we hope that the use of a T N during planning helps the model make predictions that are closer to h∗ than the bounds themselves, potentially helping it achieve a super-symbolic improvement over admissible heuristics.

In contrast, the mode argmaxx p(x) of T N is uninteresting: While we could use it as another point estimate, it is the same as the untruncated mean µ when the predicted µ is within the bounds, and equal to one of the upper/lower bounds otherwise (see Fig. 1). However, this inspires a naive alternative that is applicable even to N, which is to clip the heuristic prediction E[x] (equal to µ for N) to the interval [l, u]. We expect only a marginal gain from this trick because it only improves really bad predictions, i.e., those which would lie outside [l, u] otherwise, and does not affect predictions that correctly lie inside [l, u]. In our experiments, we show that this approach is inferior to our first method.

We re-emphasize that despite the use of admissible heuristics during training the learned heuristic is inadmissible, just like any learning-based heuristics proposed so far. In case a distributional estimate is used, i.e., when the ML model also learns to predict σ, we could discuss likely-admissibility [Ernandes and Gori, 2004; Marom and Rosman, 2020]. However, this extension is left for future work.

4 Experimental Evaluation

We evaluate the effectiveness of our new loss function under the domain-specific generalization setting, where the learned heuristic function is required to generalize across different problems of a single domain. Due to space limitations, we focus on the high-level descriptions and describe the detailed configurations in the Appendix.

Data Generation. We trained our system on four classical planning domains: blocksworld-4ops, ferry, gripper, and visitall. Using PDDL domains as benchmarks for evaluating planning performance is a standard practice, as exemplified by the International Planning Competitions (IPCs) [Vallati et al., 2015]. For each domain, we generated three sets of problem instances (train, validation, test) with parameterized generators used in the IPCs. We provided between 456 and 1536 instances for training (the variation is due to the difference in the number of generator parameters in each domain), between 132 and 384 instances for validation and testing (as separate sets), and 100 instances sampled from the test set for planning. The Appendix describes the domains and generator parameters. Notably, the test instances are generated with larger parameters in order to assess the generalization capability. To generate the dataset from these instances, we optimally solved each instance with A∗ [Hart et al., 1968] and hLMcut in Fast Downward [Helmert, 2006] under 5min runtime / 8GB memory (train,val) and 30min runtime / 8GB memory (test). Whenever it failed to solve a instance within the limits, we retried generation with a different random seed for a maximum of 20 times until success, thus ensuring a specified number of instances were generated. We also discarded trivial instances that satisfied the goal conditions at the initial state. For each state s in the optimal plan, we archived h∗ and the values of several heuristics (e.g., hLMcut and hFF). Therefore, each instance was used to obtain several data points.

Model Configurations. We evaluated three different ML methods to show that our statistical model is implementationagnostic. Neural Logic Machine (NLM) [Dong et al., 2019] is an architecture designed for inductive learning and reasoning over symbolic data which has been successfully applied to classical planning domains for learning heuristic functions [Gehring et al., 2022] with Reinforcement Learning (RL) [Sutton and Barto, 2018]. STRIPS-HGN [Shen et al., 2020, HGN for short] is another architecture based on the notion of hypergraphs. Lastly, we used linear regression with the hand-crafted features proposed in [Gomoluch et al., 2017], which comprise the goal-count [Fikes et al., 1972] and FF [Hoffmann and Nebel, 2001] heuristics, along with the total and mean number of effects ignored by FF's relaxed plan.

We analyze our learning & planning system from several orthogonal axes. Gaussian vs. Truncated: Using µ(s) as the parameter of a Gaussian N (µ(s), σ(s)) or Truncated Gaussian T N(µ(s), σ(s), l,∞) distribution. Learned vs. fixed sigma: Predicting σ(s) or using a constant value σ(s) = 1 √2 , as it is done for the MSE loss. Lower bounds: Computing the lower bound l with the hLMcut heuristic. When we use a Gaussian distribution, l is used to clip the heuristic prediction E[x] = µ(s) to the interval [l,∞). Ablation studies with l = hmax (s) [Bonet and Geffner, 2001] and l = hblind (s) are included in the Appendix. Residual learning: Either using the model to directly predict µ(s) or to predict an offset ∆µ(s) over a heuristic h(s), so that µ(s) = ∆µ(s) + h(s). We use h = hFF as our unbiased estimator of h∗ , as proposed in [Yoon et al., 2008]. In the Appendix, we conduct experiments with hLMcut as the basis of the residual.

Training. We trained each configuration with 5 different random seeds on a training dataset that consists of 400 problem instances subsampled from the entire training problem set (456-1536 instances, depending on the domain). Due to the nature of the dataset, these 400 problem instances can result in a different number of data points depending on the length of the optimal plan of each instance. We performed 4 × 104 weight updates (training steps) using AdamW [Loshchilov and Hutter, 2017] with batch size 256, weight decay 10-2 to avoid overfitting, gradient clip 0.1, learning rate of 10-2 for the linear regression and NLM, and 10-3 for HGN. All models use the NLL loss for training, motivated by the theory, but note that the NLL of N(µ, σ = 1/√2) matches the MSE up to a constant, as previously noted. For each model, we saved the weights that resulted in the best validation MSE metric during the training. On a single NVIDIA Tesla V100, each NLM training took ≈ 0.5 hrs except in visitall (≈ 2 hrs). HGN was much slower (≈ 3 hrs except ≈ 15 hrs in blocksworld). Linear models trained much faster (12-20 minutes).

Evaluation Scheme. We first report two different metrics on the test set: "MSE" and "MSE+clip". Here, MSE is the mean square error between h∗ (si) and h(si) = E[x], i.e., 1N ∑Ni=1 (h(si) -h∗ (si))2 , for i-th state si of N states in the test dataset. E[x] of T N is given by Eq. 10 while E[x] of N is simply µ. "+clip" variants are exclusive to N and they clip µ to l, i.e., use max(µ, l) in place of µ to compute the MSE. We also obtained the MSE for h = hFF and h = hLMcut .

We then evaluate the planning performance using the point estimate provided by each model as a heuristic function to guide a search algorithm. Since the learned heuristic is inadmissible, we evaluate our heuristics in an agile search setting, where Greedy Best-First Search [Bonet and Geffner, 1999, GBFS] is the standard algorithm. We do not use A∗ because it does not guarantee finding the optimal (shortest) plan [Russell and Norvig, 2010] with inadmissible heuristics and it is slower than GBFS in the agile search as it must explore all nodes below the current best f = g + h value, which is unnecessary for finding a satisficing solution. In our experiments, we evaluate search performance as the combination of the number of solved instances and the number of heuristic evaluations required to solve each instance, with a limit of 10000 evaluations per problem. We do not use runtime as our metric so that results are independent of the hardware and software configuration. Additionally, we evaluated GBFS with the off-the-shelf hFF heuristic as a baseline. The planning component is based on Pyperplan [Alkhazraji et al., 2020].

4.1 Heuristic Accuracy Evaluations

We focus on the results obtained by the NLM models, as our conclusions from the Linear and the HGN models (See Appendix) were not substantially different. Table 1 shows the MSE metric of the heuristics obtained by different configurations evaluated on the test instances (which are significantly larger than the training instances). Compared to the models trained with the NLL loss of N, those trained with our proposed T N loss often result in significantly more accurate heuristics. For example, in ferry and gripper, some N models completely fail to learn a useful heuristic, as shown by the large heuristic errors (e.g., the base N/fixed/none model on ferry obtains an MSE of 118.59). In these situations, the clipping trick often reduces errors significantly (e.g., the N + clip/fixed/none model on the same domain obtains an MSE of 10.50). However, this simply indicates that the N models are falling back to the hLMcut heuristic for those (many) predictions which are smaller than hLMcut . This is why, even with clipping, N models fail to match the accuracy of T N models in many cases: For example, the MSE of N+clip/learn/none on gripper is 7.7 points larger than the one of T N/learn/none. This confirms our hypothesis that admissible heuristics such as hLMcut should be used as the lower bound of T N, instead of simply to perform post-hoc clipping of heuristic predictions.

Additional detailed observations follow. First, T N tends to converge faster during training, as shown in Fig. 2. Second, residual learning often improves accuracy considerably, thus proving to be an effective way of utilizing inadmissible heuristics. Third, we observed that the trained heuristics, including those that use residual learning from hFF, tend to be more accurate than hFF. This rejects the hypothesis that residual learning is simply copying hFF values. Fourth, learning σ helps T N exclusively. For every N and T N model, Table 1 contains 2 comparisons related to σ (learn/none vs. fixed/none and learn/hFF vs. fixed/hFF) across 4 domains, resulting in a total of 8 comparisons. Out of 8, learning σ degrades the MSE of N in 5 cases, while it improves the MSE of T N in 7 cases. This happens because σ affects the expected value E[x] of T N used as the heuristic prediction but it does not for N. In other words, T N models requires both µ and σ in order to achieve good heuristic accuracy. This explains why T N/fixed/hFF is not as competitive as N/fixed/hFF: fixed/hFF is an ill-defined configuration for T N .

4.2 Search Performance Evaluations

We compared the search performance of GBFS using heuristic functions obtained by the different models as well as the State-of-the-Art off-the-shelf hFF heuristic. We included our proposed learn/hFF configuration and the baseline fixed/none configuration. Results for learn/none and fixed/hFF can be found in the Appendix. Table 2 shows the average±stdev of the ratio of problem instances solved (i.e., coverage), where a value of 1 means all instances are solved, and the average number of node evaluations per problem over 5 seeds. The second metric is introduced to differentiate between methods that solve most or all of the instances.

We observed that, with our proposed learn/hFF configuration, the learned heuristics significantly outperform the offthe-shelf hFF heuristic. Additionally, T N outperforms N and N+clip in every domain when both the ratio of solved instances and number of node evaluations are considered (the second metric is used to break ties in the first one).

Conversely, with the traditional but less ideal fixed/none configuration, several learned heuristics are surpassed by hFF and, also, T N is outperformed by N or N+clip in some cases. These results align with those shown in Table 1. Firstly, N models which do not use clipping sometimes learn dismal heuristics (e.g., in gripper, N/fixed/none fails to solve any instance). Secondly, T N models need to predict σ (in addition to µ) in order to learn heuristics of good quality.

5 RelatedWork

Using admissible heuristics as lower bounds of a T N distribution may appear trivial in the hindsight. Existing work use T N for machine learning most often in the context of safety-aware planning, where the upper/lower bounds are arbitrary constraints imposed by the environment or by a domain expert. For example, [Murray et al., 2023] uses T N to model a Simple Temporal Network with Uncertainty (STNU) which can model a distribution of time within a specific start time / deadline. [Eisen et al., 2019] uses T N to optimize wireless device allocations, where the truncation encodes the range of signal power. In robotics, T N is often used to limit the measurement uncertainty [Kamran et al., 2021].

In contrast, the admissible heuristics used as lower bounds in our work are formal bounds automatically proved by symbolic algorithms. For example, hLMcut is computed by deriving a so-called landmark graph, and then reducing the costs on the edges that constitute a cut of the graph. To our knowledge, our work is the first to show that such formally derived bounds for combinatorial tasks can be combined with T N.

For instance, in applications of machine learning to Operations Research problems (e.g., Vehicle Routing Problem, TSP), existing work often tries to learn to solve them without the help of heuristics [Nazari et al., 2018]. Although [Xin et al., 2021] uses the optimal solution obtained by a traditional optimal method (e.g. Concorde solver) for training and combines it with existing admissible heuristics (LKH heuristic) during testing, it does not use the heuristic for training.

In the context of heuristic learning in automated planning, off-the-shelf heuristics have only been used as a training target [Shen et al., 2020], or as a residual basis [Yoon et al., 2008].

In RL [Sutton and Barto, 2018], it is a common practice to accelerate the training through reward shaping, which is theoretically equivalent to residual learning [Ng et al., 1999]. An extension of reward shaping [Cheng et al., 2021] utilizes hand-crafted heuristics. [Gehring et al., 2022] used hFF to shape rewards for classical planning. However, to our knowledge, none has leveraged admissible heuristics as lower/upper bounds. [Cheng et al., 2021] also discussed the pessimistic and admissible heuristics as desirable properties of RL and planning heuristics, but their method does not explicitly use the upper/lower bound property for training.

6 Conclusion and FutureWork

In this paper, we studied the problem of supervised heuristic learning under a statistical lens, focusing on how to effectively utilize the information provided by admissible heuristics. Firstly, we provided some statistical background on heuristic learning which was later leveraged to analyze the decisions made (sometimes unknowingly) in the literature. We explained how the commonly used MSE loss implicitly models the heuristic to be learned as a Gaussian distribution. Then, we argued that this heuristic should instead be modeled as a Truncated Gaussian, where admissible heuristics are used as the lower bound of the distribution. We conducted extensive experimentation, comparing the heuristics learned with our truncated-based statistical model versus those learned by minimizing squared errors. Results show that our proposed method improves convergence speed during training and yields more accurate heuristics that result in better planning performance, thus confirming that it is the correct approach for utilizing admissible bounds in heuristic learning.

Our findings serve to answer the three important questions we raised in the introduction: What should the model learn? To achieve super-symbolic benefits, we should use expensive metrics such as h∗ , not poly-time heuristics or sub-optimal plan costs. How should we train the model? We maximize the likelihood of the observed h∗ assuming a Truncated Gaussian distribution lower bounded by an admissible heuristic. Why so? The principle of maximum entropy: the Truncated Gaussian distribution encodes our prior knowledge without any extra assumptions that may cause harmful bias.

In future work, we will extend our proposed method to other learning settings. One interesting scenario is given by iterative search algorithms [Richter et al., 2010; Richter et al., 2011], where the cost of the best solution found so far could be used as the upper bound of a Truncated Gaussian. Another avenue for future work is to explore the RL setting where a value function is learned instead of a heuristic, extending the work on residual learning for RL [Gehring et al., 2022].

Acknowledgements

This work has been partially funded by the Grant PID2022-142976OB-I00, funded by MICIU/AEI/ 10.13039/501100011033 and by "ERDF/EU", as well as the Andalusian Regional predoctoral grant no. 21-111PREDOC-0039 and by "ESF Investing in your future".