acceptodds
Under review as a conference paper at ICLR 2027

A Heuristic for Regression Search in Learned Quasimetric Spaces with Conditional Bounded-Suboptimality Guarantees

Abstract

Classical planning tasks often require reasoning over large state spaces to achieve conjunctive goals. Regression search reasons backward over partial states and considers actions that can support the current subgoals, making it useful in a range of planning settings. Yet comparatively few informative heuristics have been designed for regression search. The classical family provides admissible estimates by evaluating the most expensive -fact subsets and returning their maximum, but this scalar aggregation can lose information when costs accumulate across many serial subgoals. We introduce **Partial-State IQE (PS-IQE)**, a learned heuristic that constructs a lower-bound representation of each partial state in the Interval Quasimetric Embedding (IQE) latent space. We extend QRL with a relative local constraint alongside its original absolute form and use log-sum-exp to emphasize large transition violations. When either local bound holds for every transition, regression search with A\* guided by PS-IQE satisfies the corresponding bounded-suboptimality guarantee. After transition-system-specific preprocessing, both the evaluation time and storage are polynomial in the number of grounded facts for any fixed subset order . As with , the cost grows exponentially in , and is small in practice. Experiments on tasks with serial subgoals show that PS-IQE remains tight at small subset orders, and that this tightness can translate into reduced regression-search effort.

Primary area:
applications to robotics, autonomy, planning
Keywords:
classical planning, learned heuristics, regression search, Behavior Trees

Reviews

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

The central idea in the paper is new and interesting, aimed at capturing an aggregation of h^m heuristic values over fact subsets in a learned vector space, taking a coordinate-wise max of lower-corner embeddings rather than a max of scalar values, so that costs of separate subgoals can add. The paper does not clearly explain why this should be informative. Read through the lens of cost partitioning, that is barely mentioned, it becomes clearer: with IQE-sum, the training constraint sum_i q_i(u, v) <= (1+eps)·w(u, v) splits each transition's cost among the components. PS-IQE is thus a learned, transition-level cost partitioning, with an h^m-like max inside each component. In this sense, It seems close to the additive h^m heuristic (Haslum et al. 2005), with the partition learned rather than chosen. The search results cover one instance per domain, and every step requires apparently the enumeration of the full state space, where exact costs are computable by a single backward Dijkstra. The idea is promising, but the paper is not fully mature for publication yet.

Critical strengths
  • The idea of vector-valued subset aggregation, with a route from a quasimetric architecture and edge constraints to a bounded-suboptimality guarantee, is novel and elegant.

  • On Gripper, the heuristic grows with C* (0.88–0.93 of C*) while h^2 and h^3 stay constant, and the authors verify the premise of the guarantee exhaustively, reporting also that it fails on Logistics.

Critical weaknesses
  • The method is not explained clearly and well. There is no worked example of the construction, and no account of why the lower corners, each a coordinate-wise minimum over a large fraction of the state space, should stay informative. The embeddings are never inspected. The cost-partitioning reading, which explains both admissibility and the gain over h^m, is missing.

  • The comparisons miss the central question. Given that reading, the question is whether a learned partition beats computed ones. Gripper is compared only with h^m and an additive h^2 whose partition degenerates to a single part (Appendix). There is no comparison or relation made with additive h^m under a sensible partition or with other additive, cost partitioning schemes

  • The setting seems to require solving the problem exactly over the full state space, so it doesn't apply to large state spaces if my understanding is correct.

Questions for authors
  1. Why should the lower corners z_T remain informative? Can you show, on a small task, the embeddings, corners and per-component contributions that make h^m_PS-IQE exceed h^m?

  2. Do you agree that IQE-sum with your edge constraint implements a cost partitioning over components? How does PS-IQE compare with additive h^m under a non-degenerate partition?

  3. In which setting would PS-IQE be useful, given that every current step requires enumerating a state space on which exact costs to the goal are computable by a single backward Dijkstra?

4 comments

We sincerely thank you for your time and constructive comments, which have provided valuable inspiration for improving our manuscript. Our responses to your review are provided below. If you have any questions or concerns, please share them with us. We would be glad to discuss them further. Please also let us know if we have misunderstood anything.

Revisions

  1. We strengthened the baseline implementations. To integrate the heuristics into our unified Python-based regression-search framework, we had to implement the baselines ourselves, which led to the issue you identified. Thank you for pointing out the partition degeneracy. After carefully examining the authors’ latest publicly available code, we replaced the simplified action partitioning for additive h^m with an iterative assignment procedure following HSP*. The updated partitions no longer degenerate to a single part in the evaluated tasks. For PDB-UCP and PDB-SCP, we refined invariant-based variable encoding and excluded actions unreachable under delete relaxation from the initial state. We also upgraded SCP from a single fixed order to multiple locally optimized orders, taking the maximum estimate. In addition, we updated the layout of the VHM experimental scenario to match that provided by the VirtualHome simulator, ensuring a fair evaluation. The latest experimental results have been incorporated into the revised manuscript. The conclusion of the paper remains unchanged. As shown in Figure 3, in the Grippers case study, PS-IQE provides a more accurate root-node heuristic estimate than the strengthened additive h^m baseline. And, PS-IQE shows competitive performance against the baselines on the vhm instances in search efficiency.
  2. We fully understand your concern that the mechanism behind PS-IQE was not well explained. The revised manuscript includes a Gripper example(Figure 4) illustrating how a lower corner in the latent space can remain informative for a partial state. However, beyond Proposition 2 (Dominance over scalar-level combination), we believe that substantial further work is needed both to explain why PS-IQE remains informative and to prove under what conditions it does so. As discussed in our clarification, we leave this analysis to future work.

Clarifications

  1. Cost Partitioning. We believe that, technically, aggregating distance information using IQE is not identical to existing cost partitioning over components in the planning literature. Cost partitioning first distributes the action costs of the original planning task among multiple heuristic components (e.g., abstraction or landmark heuristics); each component computes a heuristic lower bound under its allocated costs, and these heuristic values are then summed. Our proposed method instead first learns a state representation that preserves directed distances, and then extends IQE to partial goals through coordinate-wise min-max operations using an m-order fact-subset table. Although both approaches use relaxation and information combination to balance heuristic computation costs and search efficiency, they differ in what they combine and how their lower bounds are established. IQE computes component-wise distances from jointly learned state representations, whereas fact-subset table entries are combined coordinate-wise rather than evaluated as separate heuristics and summed. We believe that further formalizing this intuitive connection and comparing it with symbolic methods is not straightforward, and we would be very glad to explore it in future work.
  2. Dijkstra. Although training requires access to all transitions in the state space, PS-IQE embeds states and goals in a shared latent space, leading to several advantages, including reduced storage requirements, computational amortization, and the potential for generalization:
    1. Storage. PS-IQE can be trained on streamed transitions, so its fact subset table can be built. Only the trained network and the fact subset table need to be stored. By comparison, backward Dijkstra can require O(N)O(N) auxiliary space for a single planning task, even when predecessor states are generated on demand.
    2. Computational amortization. PS-IQE amortizes the cost of learning the heuristic across planning tasks. By contrast, the backward Dijkstra baseline computes exact distances separately for each distinct goal. With the classical Fibonacci-heap implementation, each run takes O(E+Nlog⁡N)O(E + N\log N) time in the worst case.
    3. Potential for generalization. Learning-based methods offer the potential for reuse across problem sizes. Graph neural network planners such as STRIPS-HGN and GOOSE have shown that models trained on smaller instances can generalize to larger ones. These results motivate studying the generalization of PS-IQE.
  3. Large State Spaces. We argue that PS-IQE can, in principle, be applied to large state spaces. The representational guarantees of IQE establish that, with a suitable encoder, IQE can approximate finite-valued quasimetrics on finite state spaces. Both neural network training and fact-subset table construction can be parallelized. A practical challenge we observed when training QRL is learning accurate distances between states that are far apart. Recent work such as Eik-HiQRL[1] builds on QRL in an effort to improve generalization and make long-horizon goal reaching more reliable.

[1]Giammarino, V., & Qureshi, A. H. (2026). Goal Reaching with Eikonal-Constrained Hierarchical Quasimetric Reinforcement Learning. In International Conference on Learning Representations (ICLR).

Thank you for the detailed responses and the strengthened baselines. Fixing the degenerate partition of additive h^m makes the comparison more meaningful, and the Gripper example (Fig. 4) helps. I also appreciate your sincere answer that why PS-IQE remains informative is still open.

On cost partitioning, my point concerns the mechanism behind the lower bound, not the procedure. For IQE-sum, d = Σᵢ qᵢ with each qᵢ a quasimetric, and training enforces Σᵢ qᵢ(u, v) ≤ (1+ε)·w(u, v) on every transition. The values qᵢ(u, v) thus split each transition’s cost among the components, and by the triangle inequality each qᵢ lower-bounds path costs under its share. This is exactly the argument that makes cost-partitioned heuristics admissible, with the partition in this case induced by learning.

This correspondence explains admissibility but not informativeness: on complete states, even a degenerate partition (all cost in one component) is exact. The heuristic is informative only if the learned coordinates are organized by “subgoals”, so that the coordinate-wise minima over completions preserve the relevant costs. The Gripper results suggest that QRL training can produce such a representation, which would be an interesting finding. Without an analysis of the learned embeddings, however, it remains a hypothesis.

The goal-independence of the learned quasimetric is a fair advantage, but in vhm 7o, preprocessing takes about 20 minutes on a graph on which Dijkstra woluld give exact costs to a given goal in a few seconds.

For these reasons, I keep my score. The idea is novel and interesting, but in its current form it is restricted to explicit graphs where exact costs are available, and its significance for search or representation learning sounds promising but remains to be shown.

Thank you for your detailed and constructive follow-up. We appreciate that you carefully reviewed our response and revisited the paper, and your further elaboration of the correspondence helped our understanding.

Based on the Gripper example, the key to PS-IQE remaining informative is that the learned latent coordinates are grouped according to fact subsets and exhibit patterns. However, in the classical planning setting with well-defined action models, we argue that it is natural for the learned IQE coordinates to exhibit patterns grouped by fact subsets, thereby preserving second-order subset interactions while implicitly preserving action costs. In the additional experiments in vhm_7o, PS-IQE provides an informative heuristic on three different tasks, including moving all seven objects into the fridge from either one shared starting location or two, as well as moving objects from a shared starting location to different destinations.

Regarding your concern about practicality, we report UCS search time in the paper. UCS solves the single-pair shortest path problem and, like Dijkstra, maintains a table of best-known distances during search; it returns as soon as it finds a solution satisfying init. In our comparison, UCS takes approximately 40 seconds per task. Our training takes 20 minutes, while the corresponding times for tasks A, B, and C are about 9 s, 11 s, and 0.1 s, respectively. Based on a rough estimate from these data, the break-even point for amortizing search time is approximately 36 runs, with some variation across tasks.

We would like to thank you again for your careful review and for your positive evaluation of our idea as novel and interesting. We would be very grateful if you would kindly reconsider raising the score.

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

The paper proposes a new learned heuristic for classical planning problems based on learning a quasimetric distance. The approach leverages the triangle inequality constraint to learn a useful shortest-path distance with appropriate edge costs, which is then used to guide a backward search algorithm.

Critical strengths
  • The main strength of the paper is that it is sound and easy to read. While the proposed approach to learning the heuristic is not completely novel, it is interesting and well motivated, and is adapted in a sound way to the specific structure and edge costs required to define an appropriate heuristic for backward search in classical planning domains.
Critical weaknesses
  • The main weakness I have with the paper is its limited novelty, particularly regarding the proposed heuristic learning formulation. The underlying approach of learning a distance function by maximizing distances between states while enforcing local transition constraints is already well established in prior work, including [1] [2] and [3]. These works have already studied how such learned distances can provide useful lower bounds and heuristics on Stochastic shortest-path distances. Although I agree that the extension to partial states and the rigorous extension to regression search for classical planning problems is an interesting contribution on it's own.

[1] State representation learning for goal-conditioned reinforcement learning.

[2] Learning the minimum action distance.

[3] Optimal Goal-Reaching Reinforcement Learning via Quasimetric Learning.

Questions for authors
  • See Weaknesses.

  • Please discuss and include in your paper the previous works [1] and [2].

[1] State representation learning for goal-conditioned reinforcement learning.

[2] Learning the minimum action distance.

2 comments

Thank you for your time and constructive comments. We appreciate your positive assessment of our work and especially encouraged that you found the manuscript sound and clear, and our adaptation of quasimetric learning to backward search interesting and well motivated. Thank you for pointing out the need to distinguish our contributions more clearly from prior work. We agree that learning a distance function by maximizing distances between states subject to local transition constraints is an established approach. We have revised the abstract, Introduction, and Section 4 to clarify that PS-IQE builds on this formulation and to place greater emphasis on our contributions in extending IQE to partial states and establishing bounded-suboptimality guarantees for regression search under stated conditions. Specifically, we cite [1] and [2] in Section 4.1 (“Learning the quasimetric”). We would be happy to discuss any further questions or concerns. Please let us know if we have misunderstood any of your points.

Thank you for revising the paper and adding the citations. I mantain my positive score.

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

This paper addresses regression search in classical planning, which reasons backward over partial states (states with unassigned variables) toward conjunctive goals. Learned heuristics are usually defined over complete states, so the paper proposes Partial-State Interval Quasimetric Embedding (PS-IQE): it turns a quasimetric learned over complete states into an interval representation for each partial state in an Interval Quasimetric Embedding (IQE) latent space, and uses its lower bound as a heuristic for regression search. The paper also extends Q-learning with a relative local constraint and log-sum-exp emphasis on large transition violations, and proves a conditional bounded-suboptimality guarantee: when either local bound holds for every transition, regression search with A* guided by PS-IQE satisfies the corresponding bounded-suboptimality guarantee. Evaluation is on a small set of cases (5 Gripper instances, 1 Logistics instance, and 1 VirtualHome task), with the main regression-search comparison on 2 instances, against classical heuristics including h^1, h^2, and h^max.

Critical strengths
  1. An elegant and well-motivated theoretical contribution to a genuinely under-served setting. Regression search needs a heuristic over partial states, and the interval construction is a principled way to reuse a complete-state quasimetric without discarding the uncertainty introduced by unassigned variables. The conditional guarantee is stated honestly as conditional, and Appendix D.1 reports measured edge-relaxation values that partially support the condition on the studied cases. 2. Evidence that the idea can help where it is intended to help. On the reported cases, PS-IQE is competitive with h^2 while expanding fewer nodes and returning optimal-cost plans, and on the VirtualHome case it expands fewer nodes than h^2 at the same plan cost. The paper also acknowledges its own scope limits, including a single transition system, retraining per system, and finite and unreachable-state issues.
Critical weaknesses
  1. The empirical validation is too narrow for an ICLR acceptance claim. The main evaluation covers only 5 Gripper instances, 1 Logistics instance, and 1 VirtualHome task, and the regression-search comparison rests on only 2 instances. There is no broad IPC-style benchmark, no systematic scaling in the number of unassigned variables m, and no comparison of total cost including learning and preprocessing, since reported search times are indicative only and exclude preprocessing and training time. 2. The headline guarantee is conditional in a way that is not shown to hold broadly. It depends on a local bound holding for every transition, which is verified only through measured values on the narrow cases above. Combined with the exponential cost in m in the worst case, the paper establishes an elegant construction and a conditional result, but not yet a generally useful heuristic whose advantage survives realistic problem sizes and total-cost accounting.
Questions for authors
  1. Could the authors evaluate PS-IQE on a substantially larger and more diverse benchmark (for example, multiple IPC-style domains and many instances per domain) and report total time including learning and preprocessing, so that the benefit over h^2 can be judged on total effort rather than search time alone? 2. How does PS-IQE scale as the number of unassigned variables m grows, in both time and node expansions, and at what value of m does it cease to be competitive with h^2? 3. Can the authors provide evidence, beyond the cases in Appendix D.1, that the local-bound condition underlying the bounded-suboptimality guarantee holds (or fails) on held-out instances, and what happens to plan quality when it fails?
2 comments

We sincerely thank you for your time and constructive comments, which have provided valuable inspiration for improving our manuscript. Our responses to your review are provided below. If you have any questions or concerns, please share them with us. We would be glad to discuss them further. Please also let us know if we have misunderstood anything.

Revisions

  1. We added experiments and report prepocessing times. Given constraints on both computing resources and time, as well as the difficulty of generating states for our data-driven training from PDDL rules in some IPC domains, we found it challenging to evaluate PS-IQE on broad IPC-style benchmarks. To broaden our evaluation, we added tasks in the seven-object vhm_7o setting, including moving all seven objects into the frige from either one shared starting location or two starting locations, as well as moving objects from a shared starting location to different destinations. We also report preprocessing times, including neural network training.

    The results show that PS-IQE is competitive with the baselines in search efficiency and node expansions, and that it outperforms both hmh^m and additive hmh^m on every task in this evaluation. PS-IQE achieves search efficiency comparable to that of SCP, the strongest baseline, while offering a different preprocessing trade-off. While the SCP baseline uses a per-instance preprocessing budget to search for effective orderings of the pattern database heuristics, PS-IQE incurs most of its preprocessing cost once per transition system and reuses the resulting model and fact-subset table across planning instances. We hope these additional experiments address your concerns.

  2. We refined the conditions for bounded suboptimality while retaining most of the proof. For a given task, the bounded-suboptimality guarantee holds if there exists an optimal plan along which the estimated distance of every transition is at most the relaxed action cost. We then exhaustively measured transition-bound violations in two larger transition systems: Logistics and the nine-object vhm_9o scenario, as shown in Appendix D.1. Using a relaxed bound of 1.11.1 times the action cost (ϵ=0.1), the mean percentages of violating edges across three seeds are 0.001474% for Logistics and 0.000167% for vhm_9o, with maximum learned-distance-to-cost ratios of 1.126942 and 1.120826, respectively. We then evaluated 10,000 sampled (init,goal)(\mathrm{init},\mathrm{goal}) tasks per scenario, with 100 partial goals and 100 initial states per goal. Averaged across three seeds, at least one optimal path contains at least one violating edge in 0.8333% of Logistics tasks and 0% of \texttt{vhm_9o} tasks, while every optimal path contains at least one violating edge in 0.15% and 0% of tasks, respectively.

    Below is the discussion. As a learning-based method, PS-IQE does not guarantee that the learned distances satisfy the transition bounds on every edge in every training run. Applying the theoretical guarantees therefore requires verifying the relevant transition bounds. Based on the experimental results, we believe that how such violations affect search depends on the transition system. Training techniques such as prioritized experience replay could be explored to further reduce the magnitude and frequency of relaxation violations, which we leave to future work.

clarification

order m. In the classical critical-path heuristic hmh^m, mm is the largest number of facts considered jointly in the relaxation. In our proposed PS-IQE, mm is the maximum size of the fact subsets used to construct the representation of a partial state. In both methods, the number of subsets considered grows combinatorially with mm, which makes the heuristic more expensive to compute but yields better estimates. At small mm, hmh^m can underestimate the cumulative cost of achieving serial subgoals. On the instances with serial subgoals in our experiments, PS-IQE captures more of this cost than hmh^m and additive hmh^m, at small subset orders.

We interpret your question about when PS-IQE ceases to be competitive with h2h^2 as asking at which subset order the additional evaluation cost outweighs the savings from fewer node expansions. In our current experiments, PS-IQE with m=2m=2 often achieves the lowest total search time among the PS-IQE configurations tested. If you had a different comparison in mind, we would appreciate your clarification.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.