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

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 $h^m$ family provides admissible estimates by evaluating the most expensive $m$-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 $m$. As with $h^m$, the cost grows exponentially in $m$, and $m$ 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.