- 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
-
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?
-
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?
-
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
Clarifications
- 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.
- 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:
- 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 auxiliary space for a single planning task, even when predecessor states are generated on demand.
- 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 time in the worst case.
- 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.
- 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.
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