acceptodds
Under review as a conference paper at ICLR 2027

Learning Heuristic Functions via Policy Optimization for Symbolic Planning

Abstract

Tree search efficiency in deterministic symbolic planning critically depends on heuristic functions, which are difficult to design. Heuristics are therefore often learned, and one promising way to train them is with ranking losses, which teach the heuristic to rank the states in the open list, on problem instances whose solutions are known. We consider the opposite scenario, in which no solutions are available and the heuristic is trained on the searches it performs itself. The training data then depends on the heuristic, which turns learning into a policy optimization problem. We revisit heuristic learning from a policy optimization perspective and formulate symbolic planning search as a Markov Decision Process (Tree-MDP), where a state is a partially expanded search trees and an action selects a node for expansion. The Tree-MDP allows us to (i) optimize heuristics with standard reinforcement learning algorithms, which lets us compare the Tree-MDP with the standard formulation of planning as an MDP using the same algorithm, (ii) show that ranking losses are closely related to policy optimization in the Tree-MDP, and (iii) train the heuristic on the search configurations it visits itself rather than only on those along the best path found. Experiments on IPC 2023 learning track benchmarks support the theoretical connections : PPO performs better in the Tree-MDP than in the standard formulation, ranking losses and their policy counterpart perform alike, and training on the heuristic’s own search configurations yields the highest average coverage among the learned heuristics.

Primary area:
reinforcement learning
Keywords:
planning, RL, heuristic, search, policy, optimisation, symbolic

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_Ft9TOpenReview ↗
Rating
4
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper proposes a new approach to generate heuristic functions for Greedy Best-First Search (GBFS). Two approaches are presented, one where the planning process is modeled as an MDP where the actions are decisions to decide which planning node to expand next from the fringe. The second approach is inspired by the observations of the first one and consists of training a heuristic function using a novel supervised learning loss function that is based on the search experience generated by GBFS. Experiments show that the second approach allowed more planning instances to be solved on average, when comparing it against eight baselines.

Critical strengths

The paper presents a meaningful connection between RL and heuristic learning that can be used as a principled way to learn heuristics for symbolic planning. By modeling the problem of choosing the next node to expand as a sequential decision-making problem, the paper establishes a framework (independent of specific RL algorithms) that inspires a derivation and evaluation of a novel loss function used to train heuristic functions.

The evaluation includes a diverse set of baselines, both closer to the approach and classically used. Ten planning domains are evaluated and L_{po} has higher coverage in six out of ten domains, showing that it performs well in a range of problems. The proposed approaches also perform much better than other learned and traditional planning approaches. This provides encouraging empirical evidence of the practical value of the proposed learning objective. The authors also analyze the domain structures of cases where their approach is substantially better or worse than other approaches.

Critical weaknesses

None

Questions for authors

What explains the improvements of the proposed loss over existing ranking-based losses? Do you have an idea in which cases using the open lists encountered during search gives the approach a clear advantage?

2 comments
AuthorsOpenReview ↗

answer to question

Thank you very much for the positive review.

We believe the improvements come from replaying the expansions as they were encountered during search. LgbfsL_{gbfs} and its LgbfssoftmaxL_{gbfs}^{softmax} variant constrain only the states **at distance one(( from the best trajectory. Specifically at each step, the next state on the trajectory must be preferred over the other children of the states expanded so far. When the heuristic makes a mistake and expands a state off the trajectory (which during training can also happen because expansions are sampled from the policy) the children of that state enter the open list with heuristic values that the ranking losses have never constrained, and the search can keep expanding them. LpoL_{po} adds these open lists to the training set. A second effect is implicit weighting, as a mistake that costs many expansions contributes proportionally more to the loss.

When the search already follows the best trajectory, the ratio of expanded states to plan length is close to one (Figure 1 in the Appendix), the open lists seen by LpoL_{po} and LgbfsL_{gbfs} coincide, and the two losses are identical, which is what we observe in five domains. The advantage appears when the search explores states far from the trajectory early in training, and in domains with dead ends or traps where one wrong expansion is followed by many more, such as Floortile and Transport, where LpoL_{po} is much better. The 0/1 ablation reported to Reviewer 2 supports this: LpoL_{po} keeps a 5 point lead over the ranking losses regardless of the target, so the gain comes from the loss rather than from the choice of the best node.

Reviewer_Ft9TOpenReview ↗

Thanks

Thank you for the explanation. I still think this is a good paper, and I would like to see it published.

Reviewer_YVzuOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper revisits heuristic learning from a policy-optimization perspective, formulating symbolic planning search as an MDP (Tree-MDP) whose states are partially expanded search trees and whose actions select nodes for expansion. This enables standard RL algorithms such as PPO, and "reveals that ranking-based losses are closely related to policy optimization objectives". Building on this view, the authors propose a new loss "that combines RL principles with structural properties of symbolic search". Experiments are on the IPC 2023 learning track.

In my view, it's close to the bootstrap scheme of Arfaee, Zilles & Holte (2011), with GBFS in place of IDA* and ranking in place of cost-to-go regression. After each search, a single target node is chosen: the one with the most achieved goal atoms. The GNN heuristic is trained so that the tree path to this node becomes more likely under softmax(-h) over the open list. The new loss, L_po, places this term at every open list GBFS actually visits, not only along the path.

Critical strengths
  • The point that a GBFS heuristic should be trained against the whole open list, not against a node's siblings, is correct and clearly stated.

  • L_po is simple, plugs into unmodified GBFS, and is evaluated on all ten IPC 2023 domains with an appendix detailed enough to inspect the results.

  • Plan length / expansions ≈ 1 in Miconic and Spanner, if I'm getting this right, indicates that the heuristic in these two domain, acts as a general, greedy policy.

Critical weaknesses
  • The framing adds little (Tree-MDPs, Linear MDPs), and the way in which the work is positioned in the field is incomplete.
  • The target seems to be a form of hindsight relabeling based on goal counting, a choice that is neither named nor analyzed, and it is misleading in some cases, as when some goals need to be undone
  • Relaiton to HER (Andrychowicz et al. 2017), and a recent lifted version for planning (Ståhlberg & Geffner, AAAI 2026) should be discussed. Samewith Arfaee et al. as the source of the method itself.
  • The experimental protocol favors the proposed method. A 30-second limit penalizes LAMA, which rely on expensive preprocessing. GSP is re-implemented with a one-layer GNN, potentially very different than GSP
  • Little insight into why the method works where it does. Performance is very different across planning domains.
Questions for authors
  1. How do the results change with the standard IPC time limit?

  2. How do results change with a 0/1 objective instead of goal counting? Any testing in instances where goals need to be undone and then re-done?

  3. Am I getting it right that you are solving

  4. Is the learned heuristic nearly perfect in Miconic and Spanner? And this with a 1-layer GNN? Any explanation? ====

After rebuttal:

Thanks for the additional experiments. and explanations. The 0/1 ablation shows that the advantage of L_po does not depend on the goal-counting target, and the 30-minute results show that the comparison with LAMA does not hinge on the short time limit. After taking a second look at the paper, my understanding of the paper has changed a bit too (see below), so I'm increasing the recommendation to "weak accept".

About my reading of the paper, the framing, and what's is new and not that new:

  • Open-list normalization is not new. That a GBFS heuristic must rank the target against the whole open list, rather than among siblings, is the core of Chrestien et al. (2023), and relates to the observation of Orseau et al. (2018) that child-normalized policies fit tree search poorly. The advantage of Tree-PPO over Linear-PPO confirms this.

  • The Tree-MDP with on-policy imitation is not that new either, as you indicate. SaIL (Bhardwaj et al. 2017) uses the same solver state (open and closed lists) and actions (expanding an open node) to train a policy in the style of DAgger with labels coming from an oracle.

  • Ranking against the queue during the learner’s own search appears in Xu, Fern & Yoon (2009) and others.

What is new in the paper is L_po itself: oracle-free hindsight targets taken from the learner’s own searches, a softmax over the open lists actually encountered, best-first rather than beam search, and GNN heuristics that generalize across instances.

The rebuttal shows that the gains do not not come from the goal-count target, although it is concentrated in a few domains.

L_po, however, is not obtained by policy optimization. It is a supervised log-likelihood loss with hindsight labels and it can be derived directly without the RL formulation.

I suggest to present L_po as a learning-to-search method, discuss Xu, Fern & Yoon, DAgger and hindsight relabeling in more detail, and probably, tone down the claim that Tree-MDP establishes a link of L_po to policy optimization.

3 comments
AuthorsOpenReview ↗

Answer to rebuttal

Relation to HER

Thank you for pointing us to Ståhlberg and Geffner (AAAI 2026). The relation exists and we will state it in Section 4, where we will also name the criterion explicitly. We do not use HER as published in Andrychowicz et al. (2017): HER replaces the goal conditioning the network with a goal that was achieved, whereas our network is always conditioned on the original goal. What we share with the propositional HER of Ståhlberg and Geffner is the criterion: they relabel a subtrajectory with the largest subset of goal atoms satisfied at its end, and we select the node of the search tree with the largest number of satisfied goal atoms (shallowest on ties) and imitate the shortest path to it. This follows from how the problem is formulated, as finding a path to the state with the highest objective, and from the Tree-MDP reward, which is the improvement in the best objective in the tree.

0/1 objective

We agree that the criterion can be misleading when goals must be undone. To test this concern, we repeated the experiments with a 0/1 objective, which creates a training sample only on solved instances. The coverage (in percents, average over three seeds) together with goal-counting are summarized in below table

             │ lgbfs       │ lgbfs_soft  │   Lpo       │LAMA│ BFWS
             │ count   0/1 │ count   0/1 │ count   0/1 │    │ 
─────────────┼───────┬─────┼───────┬─────┼───────┬─────┼────┼──────
 blocksworld │   73  │ 64  │  75   │ 71  │  83   │ 70  │ 38 │   31
 childsnack  │   51  │ 38  │  51   │ 31  │  45   │ 40  │ 33 │   30
 ferry       │   68  │ 66  │  67   │ 66  │  67   │ 66  │ 67 │   45
 floortile   │   06  │  1  │   3   │  3  │  32   │ 25  │ 12 │   12
 miconic     │   74  │ 72  │  73   │ 72  │  73   │ 72  │ 89 │   76
 rovers      │   39  │ 38  │  38   │ 38  │  38   │ 38  │ 51 │   52
 satellite   │   60  │ 50  │  60   │ 50  │  61   │ 55  │ 73 │   56
 sokoban     │   31  │ 25  │  33   │ 28  │  34   │ 33  │ 38 │   48
 spanner     │   72  │ 72  │  72   │ 72  │  73   │ 72  │ 33 │   33
 transport   │   52  │ 45  │  49   │ 45  │  61   │ 51  │ 58 │   61
─────────────┼───────┼─────┼───────┼─────┼───────┼─────┼────┼──────
 average     │  52.6 │ 47.1│ 52.1  │ 47.6│ 56.7  │ 52.2│49.2│ 44.4

The results show that the goal-counting objective improves the ranking losses by 4 to 5 percentage points on average with the largest gains in Childsnack, Satellite, Blocksworld and Transport. The gain holds also in Blocksworld, Floortile and Sokoban, where goal atoms sometimes must be undone, so on these benchmarks the denser training signal on unsolved instances outweighs the cases where the criterion misleads. LpoL_{po} retains its advantage over the ranking losses under the 0/1 objective, so its gains do not depend on the choice of target. We will add these results to the Appendix and name and discuss the criterion in Section 4. In our view goal counting is the natural objective in our formulation, since the Tree-MDP reward is the improvement of the best objective in the search tree, and the ablation supports this choice empirically.

Bootstrap protocol

Regarding Arfaee et al. (2011): our bootstrap protocol follows it, which we cite in the introduction, the related work, and the protocol description in the appendix, and PHS (Orseau and Lelis 2021), our closest baseline, builds on it as well. Both learn only from instances the current heuristic solves. The 0/1 objective above is exactly this regime, and the comparison shows that the goal-count target on unsolved instances is not what sets our method apart; the Tree-MDP formulation and L_po are.

30min time limit

Experiments presented in the paper used time limit 30s to decrease the computational complexity of the results, since the bootstrap protocol repeatedly solves the problem and large time limit increases the time for experiments. We have repeated the experiments with ranking losses maximizing the goal-count with 30mins time limit. The coverage (in %) is shown below.

              lgbfs  lgbfssoft  Lpo   LAMA BFWS BFWS_pref  
─────────────────────────────────────────────────────
blocksworld      90     86     92     42   40     42 
childsnack       57     71     62     39   40     22 
ferry            74     73     76     78   78     76 
floortile        01     02     33     13   13     14 
miconic          98    100    100     100  100    100  
rovers           47     45     41     79   76     73 
satellite        76     61     65     100  73     70 
sokoban          28     30     33     44   53     59 
spanner          67     96     97     33   33     33 
transport        54     51     76     77   76     71 
─────────────────────────────────────────────────────
average:         59.2   61.5  67.5    61  58.2    56

LAMA indeed benefits from longer time, now being better by 2% on ferry, while previously it was equal. Overall, the proposed LPOL_{PO} is still on average better.

Thanks for the additional experiments. and explanations. The 0/1 ablation shows that the advantage of L_po does not depend on the goal-counting target, and the 30-minute results show that the comparison with LAMA does not hinge on the short time limit. After taking a second look at the paper, my understanding of the paper has changed a bit too (see below), so I'm increasing the recommendation to "weak accept".

About my reading of the paper, the framing, and what's is new and not that new:

  • Open-list normalization is not new. That a GBFS heuristic must rank the target against the whole open list, rather than among siblings, is the core of Chrestien et al. (2023), and relates to the observation of Orseau et al. (2018) that child-normalized policies fit tree search poorly. The advantage of Tree-PPO over Linear-PPO confirms this.

  • The Tree-MDP with on-policy imitation is not that new either, as you indicate. SaIL (Bhardwaj et al. 2017) uses the same solver state (open and closed lists) and actions (expanding an open node) to train a policy in the style of DAgger with labels coming from an oracle.

  • Ranking against the queue during the learner’s own search appears in Xu, Fern & Yoon (2009) and others.

What is new in the paper is L_po itself: oracle-free hindsight targets taken from the learner’s own searches, a softmax over the open lists actually encountered, best-first rather than beam search, and GNN heuristics that generalize across instances.

The rebuttal shows that the gains do not not come from the goal-count target, although it is concentrated in a few domains.

L_po, however, is not obtained by policy optimization. It is a supervised log-likelihood loss with hindsight labels and it can be derived directly without the RL formulation.

I suggest to present L_po as a learning-to-search method, discuss Xu, Fern & Yoon, DAgger and hindsight relabeling in more detail, and probably, tone down the claim that Tree-MDP establishes a link of L_po to policy optimization.

Thank you very much for increasing the score and pointing out to the paper of Xu, Fern & Yoon, DAgger. It is clearly related and we have put it into the related work in the revised paper.

Reviewer_7yMqOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes adopting Tree-MDP as a general formalism for learning a domain-dependent, instance-independent search policy / heuristic via reinforcement learning. A state of Tree-MDP is not the state in the environment defined by PDDL, but the entire state of a solver including open list and close list.

The paper first proposes L_GBFS^softmax, then improve it via policy-optimizing loss which addresses the off-policy mismatch between the GBFS-induced search policy and the best policy. It also links existing rank-based loss with this framework.

This is a neat work that proposes a clean framework for policy learning.

I identify a few minor weaknesses in this paper, nothing major.

One weakness is that it does not utilize the full potential of Tree-MDP. Tree-MDP is able to see the entire open/close list, thus able to utilize cross-state, history-dependent information required by novelty metric in Probe and BFWS.

Experiment-wise, the performance gain is sometimes weak per domain; L_po overlaps with L_gbfs is several domains.

Whether ranking-based training helps or not has not been universally agreed upon yet. For example, Núñez-Molina et. al. (IJCAI 2024) contains a comparison between Truncated-Gaussian heuristics vs L_GBFS trained on the same dataset and the same architecture, and demonstrates that Truncated-Gaussian heuristics can outperform the latter.

LAMA is a relatively old planner, and with 30 second time limit, agile planners such as BFWS are far more representative. I believe it is still a common assumption that machine-learning-based planners cannot outperform symbolic planners, so switching to a better-performing planner would not lose much.

[1] Núñez-Molina, Carlos, et al. "On using admissible bounds for learning forward search heuristics." IJCAI 2024

Critical strengths

This is a neat work that proposes a clean framework for policy learning.

Critical weaknesses

I mentioned several weaknesses in the paper summary, but they are not critical weaknesses. Nonetheless, I suggest authors to address the points I raised above.

Questions for authors

In section 4, how do you define and obtain the "best trajectory"? The paper says it is cheap to obtain, but this is not immediately clear to me. The objective function is basically a goal-count heuristic. Is the "best" defined by it? Please define formally (or did I miss it?) Is it an optimal solution? (It probably isnt, and the paper clearly says this paper does not use imitation learning from the optimal solution.)

5 comments
AuthorsOpenReview ↗

Answers to review

C1. One weakness is that it does not utilize the full potential of Tree-MDP. Tree-MDP is able to see the entire open/close list, thus able to utilize cross-state, history-dependent information required by novelty metric in Probe and BFWS.

We agree we do not use the full potential, but this decision was deliberate. Our focus is on the formulation of the loss function itself. The experiments are designed to remove other sources of influence, such as the neural network architecture. We left the architectures exploiting information from the search tree as future work (under the progress), because finding the right architecture with a good tradeoff between computational complexity and expressive is challenging, since even with a time limit of 30s, the resulting search trees can have more than 100k states.

C2. Experiment-wise, the performance gain is sometimes weak per domain; LpoL_{po} overlaps with LGBFSL_{GBFS} is several domains.

The reason why the experimental results of LpoL_{po} are close to those of LGBFSL_{GBFS} is that both loss functions are close in spirit. The difference is that LGBFSL_{GBFS} simulates the expansion of states on the best known path, whereas LpoL_{po} simulates the expansion of states as experienced by the search. Should the search expand only states on the path to the goal, the training sets of both losses coincide. In our experiments, the ratio of the plan length to the number of expanded states on training instances is close to one in many domains, as shown in Figure 1 in the Appendix (and discussed in lines 441-445).

C3. Whether ranking-based training helps or not has not been universally agreed upon yet. For example [1] contains a comparison between Truncated-Gaussian heuristics vs LGBFSL_{GBFS}...

Thank you for this reference; we were not aware of it, and we agree that it shows that the advantage of ranking losses is not universal. We note that in the comparison with LGBFSL_{GBFS} (Appendix G, Table 10 in the arXiv version of [1]), the truncated-Gaussian models learn a correction on top of h^FF and use h^LMcut as a lower bound, whereas LGBFSL_{GBFS}, like our heuristic, uses no hand-crafted heuristic as a base or a bound (in our losses, the goal count serves only to select the best node in the search tree). Our statement was based on the experimental results in [A], which compared the ranking-based loss (Table 1 in [A]) to the L2 loss (Table 6 in [A]) on 10 domains with 10 different encodings. In all completed experiments, the ranking loss was better than L2. We will tone down the claim and point to [1] in the paper.

Generally, we agree with [1] that combining existing polynomial-time heuristics with learning is interesting and deserves more research, as it can combine the best of both worlds.

C4. LAMA is a relatively old planner, and with 30 second time limit, agile planners such as BFWS are far more representative. I believe it is still a common assumption that machine-learning-based planners cannot outperform symbolic planners, so switching to a better-performing planner would not lose much.

Thank you for pointing us to BFWS. We have downloaded the planner from https://github.com/nirlipo/BFWS-public and run it on with the following command: bfws --domain domain.pddl --problem p01.pddl --output plan.ipc --DUAL-BFWS 1 To terminate the search after 30s, we used the Linux command timeout -k 5 30 and then read the statistics from the logs. In our settings, the LAMA planner was on average better except three cases (Sokoban, Transport, Rovers).


│ dataset.name│L_gbfs│ L_po │ LAMA │ BFWS │
├─────────────┼──────┼──────┼──────┼──────┤
│ blocksworld │ 0.73 │ 0.83 │ 0.38 │ 0.31 │
│ childsnack  │ 0.51 │ 0.45 │ 0.33 │ 0.30 │
│ ferry       │ 0.68 │ 0.67 │ 0.67 │ 0.46 │
│ floortile   │ 0.06 │ 0.32 │ 0.12 │ 0.12 │
│ miconic     │ 0.74 │ 0.73 │ 0.89 │ 0.77 │
│ rovers      │ 0.39 │ 0.38 │ 0.51 │ 0.52 │
│ satellite   │ 0.60 │ 0.61 │ 0.73 │ 0.57 │
│ sokoban     │ 0.31 │ 0.34 │ 0.38 │ 0.49 │
│ spanner     │ 0.72 │ 0.73 │ 0.33 │ 0.33 │
│ transport   │ 0.52 │ 0.61 │ 0.58 │ 0.61 │
├─────────────┼──────┼──────┼──────┼──────┤
│ average     │ 0.53 │ 0.57 │ 0.49 │ 0.45 │
└─────────────┴──────┴──────┴──────┴──────┘

Answers to questions:

Q1: The objective is indeed a goal-counting heuristic. The best state is the state with the highest objective value (goal-counting heuristic) with the shortest path from the root. It is cheap to obtain because it is extracted from the already built search tree by following parent pointers from the best node back to the root. It is not an optimal solution in general. Revisiting the section at line 407, we see that it is not clear, and we will update the manuscript.

[1] Núñez-Molina, Carlos, et al. "On using admissible bounds for learning forward search heuristics." IJCAI 2024

[A] Horčík, Rostislav, et al. "State encodings for GNN-based lifted planners." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 39. No. 25. 2025.

Reviewer_7yMqOpenReview ↗

BFWS results

Quick reply; will write a longer reply later.

Dual-BFWS appeared in IPC 2018 https://ipc2018-classical.bitbucket.io/#planners but it did not outperform LAMA, so it is a weaker baseline. What outperformed LAMA in IPC2018 is LAPKT-BFWS-Preference.

AuthorsOpenReview ↗

Results with the new planner

Dear Reviewer,

we have run the version of BFWS planner (denoted as BFWS_pref) according to your recommendation. Te results are below.


│ dataset.name│L_gbfs│ L_po │ LAMA │ BFWS │ BFWS_pref │
├─────────────┼──────┼──────┼──────┼──────┼───────────┤
│ blocksworld │ 0.73 │ 0.83 │ 0.38 │ 0.31 │      0.36 │
│ childsnack  │ 0.51 │ 0.45 │ 0.33 │ 0.30 │      0.20 │
│ ferry       │ 0.68 │ 0.67 │ 0.67 │ 0.46 │      0.67 │
│ floortile   │ 0.06 │ 0.32 │ 0.12 │ 0.12 │      0.12 │
│ miconic     │ 0.74 │ 0.73 │ 0.89 │ 0.77 │      0.77 │
│ rovers      │ 0.39 │ 0.38 │ 0.51 │ 0.52 │      0.48 │
│ satellite   │ 0.60 │ 0.61 │ 0.73 │ 0.57 │      0.52 │
│ sokoban     │ 0.31 │ 0.34 │ 0.38 │ 0.49 │      0.42 │
│ spanner     │ 0.72 │ 0.73 │ 0.33 │ 0.33 │      0.33 │
│ transport   │ 0.52 │ 0.61 │ 0.58 │ 0.61 │      0.52 │
├─────────────┼──────┼──────┼──────┼──────┼───────────┤
│ average     │ 0.53 │ 0.57 │ 0.49 │ 0.45 │     0.44  │
└─────────────┴──────┴──────┴──────┴──────┴───────────┘

While it is much better on Blocksworld and Ferry, it is way worse on other domains (Sokoban, Transport) and the net gain is slightly lower than Lama and BFWS.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.