acceptodds
Under review as a conference paper at ICLR 2027

Hierarchical Distance Decomposition for Minimum-Action-Distance Estimation

Abstract

Estimating how many actions an agent needs to move between distant states is difficult. The Minimum Action Distance (MAD) formalizes this quantity, but approximations learned from experience can be locally accurate yet unreliable over long horizons. We introduce *hierarchical distance decomposition*, a post-hoc method that improves long-range estimates by composing local predictions through a sparse graph of landmark states. It can be applied to any existing learned distance model without retraining. We present theoretical results that bound errors in the resulting distance estimates and establish order preservation for sufficiently separated state pairs. Empirically, the method improves both long-range distance estimation accuracy and downstream planning performance.

Primary area:
reinforcement learning
Keywords:
Representation Learning, Reinforcement Learning, Hierarchical Distance Decomposition

Reviews

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

This paper proposes \textbf{Hierarchical Distance Decomposition (HDD)}, a training-free post-hoc method that improves long-horizon distance estimates from an already learned quasimetric distance model. The key idea is to decompose long-range distance queries into compositions of short-range predictions. The method first builds a landmark set from an offline state-only trajectory dataset using a greedy two-sided δ\delta-net, where a state is retired only if an existing landmark is close to it in both forward and backward directions. It then constructs a directed landmark graph retaining only edges whose predicted distance is at most κδ\kappa\delta, computes all-pairs shortest paths via Floyd--Warshall, and at query time combines an entry leg, a landmark shortest path, and an exit leg. The estimator returns the base model's direct prediction when the closest forward and backward landmarks coincide, and otherwise minimizes over candidate landmark routes.

The paper provides a theoretical analysis under two assumptions: local accuracy of the base model and coverage of relevant reference paths by the dataset. Theorem~1 gives a two-sided bound: no underestimation beyond accumulated local error along the returned route, and bounded overestimation with a per-hop cost depending on $\delta$ and $\epsilon$. The paper also discusses why the two-sided landmark rule is necessary, gives a counterexample for one-sided nets, and extends the discussion to stochastic options.

Empirically, HDD is evaluated on PointMaze and AntMaze from OGBench, across medium, large, and giant sizes, with navigate and stitch splits, and additionally explore for AntMaze Medium. Three base distance models are used: MadDist, TDMAD, and HILBERT. HDD improves Spearman rank correlation with grid-geodesic distance as the evaluated range increases, and substantially improves downstream planning success rates, especially on giant mazes where flat base models often fail completely. Ablations over $\delta$ and $\kappa$ show that smaller $\delta$ and smaller $\kappa$ generally work best, with $\kappa$ having a stronger effect.
Critical strengths

1: Simple, training-free, and broadly applicable method. The proposed HDD is conceptually simple and easy to implement. It does not require retraining the base distance model or learning a new representation. It can be applied post-hoc to any locally accurate quasimetric distance model. This is consequential because it makes the method practical and easy to adopt. The empirical results show that it can turn near-zero planning success on giant mazes into high success rates, which is a substantial practical improvement.

2: Strong empirical gains on long-horizon tasks. The paper demonstrates consistent improvements in both distance-quality correlation and planning success rate across multiple environments, datasets, and base models. The gains are largest precisely where base models fail: on giant mazes and long-horizon tasks. This is consequential because it directly addresses the motivating problem of long-range distance degradation. The ablation over δ\delta and κ\kappa also provides useful practical guidance.

3: Theoretical analysis with clear assumptions and two-sided bound. The paper provides a formal analysis of the estimator's error, including a no-underestimation bound and a bounded-overestimation bound. The two-sided landmark construction is well motivated and the counterexample for one-sided nets is convincing. This is consequential because it gives the method a principled foundation and clarifies when it can be expected to work.

Critical weaknesses

1: Strong dependence on local accuracy of the base model, with limited practical guidance. The method's theoretical guarantees and empirical success depend on the base model being locally accurate. However, the paper does not provide a practical procedure to check whether this assumption holds for a given base model and dataset. In practice, if the base model is locally inaccurate, HDD may compose unreliable local estimates and produce poor long-range estimates. The paper acknowledges this as a limitation, but it is central to the method's applicability. A practical diagnostic or fallback mechanism would strengthen the paper.

2: Limited isolation of the source of planning gains. The planning results show large improvements, but the planner is deliberately weak and the hierarchical decomposition may act as a form of test-time search or subgoal selection. The paper does not fully disentangle whether the gains come from better distance estimates or from the hierarchical structure itself. This matters because the claimed contribution is a distance-estimation method, not a planner. Additional analysis, such as comparing against a planner that uses the same landmark graph but a different distance model, or measuring the correlation between distance error and planning success, would help.

3: Theoretical assumptions and constants are conservative and not empirically validated. The theoretical bound depends on assumptions that are difficult to verify in practice, and the constants are worst-case. The paper does not empirically validate the assumptions or the tightness of the bound. This limits the practical utility of the theory. It would be useful to report, for example, the empirical local error ϵ\epsilon of each base model and the coverage of reference paths by the dataset.

Questions for authors
  1. Practical verification of local accuracy: Can you provide a practical procedure to estimate whether a given base model satisfies Assumption~1 on a given dataset? For example, could one use held-out local pairs to estimate ϵ\epsilon? How would you recommend practitioners decide whether HDD is applicable?

  2. Disentangling planning gains: The planning improvements are large. Can you provide an ablation that isolates whether the gains come from improved distance estimates or from the hierarchical graph acting as a test-time search mechanism? For example, what happens if the planner uses the same landmark graph but with a random or constant distance model?

  3. Empirical validation of assumptions: Can you report empirical estimates of the local error ϵ\epsilon for each base model, and the coverage of reference paths by the dataset? This would help assess how often Assumptions1 and2 hold in practice.

  4. Sensitivity to κ\kappa and δ\delta: The ablation shows that smaller δ\delta and smaller κ\kappa are better, but smaller δ\delta increases the number of landmarks and preprocessing cost. Can you provide a more detailed cost-benefit analysis, including preprocessing time and memory, for the recommended settings?

  5. Stochastic environments: The paper discusses options-style abstraction for stochastic control but does not evaluate it. Can you provide at least a preliminary experiment on a stochastic navigation task to show whether the deterministic shortest-path approximation remains reasonable?

  6. Comparison to alternative post-hoc methods: The paper compares HDD to flat base models. Are there other post-hoc distance-improvement methods, such as graph-based smoothing or local averaging, that could serve as stronger baselines? How does HDD compare to these?

  7. Failure cases: Can you provide examples where HDD fails or degrades performance? Understanding the failure modes would help assess the method's robustness.

1 comment

Practical verification of local accuracy: Can you provide a practical procedure to estimate whether a given base model satisfies Assumption~1 on a given dataset? For example, could one use held-out local pairs to estimate ? How would you recommend practitioners decide whether HDD is applicable?

Without access to the ground truth, it is challenging to design a reliable procedure to estimate whether Assumption~1 is respected. In case one has access to the ground truth only on a small subset of the state space, practitioners could use held-out local pairs from this subset to empirically assess whether Assumption 1 is satisfied. In more realistic scenarios where such ground-truth information is unavailable, practitioners would need to assess the applicability of Hierarchical Distance Decomposition (HDD) empirically, as is common with many other algorithms, by evaluating whether it improves performance on downstream task benchmarks, such as goal-conditioned planning.


Disentangling planning gains: The planning improvements are large. Can you provide an ablation that isolates whether the gains come from improved distance estimates or from the hierarchical graph acting as a test-time search mechanism? For example, what happens if the planner uses the same landmark graph but with a random or constant distance model?

We would like to clarify that our method does not require any additional distance computations during test-time search. The distances between landmarks are computed when building the landmark graph and stored in the matrix DHD_H, which is then used at inference time. We also believe that the proposed experiment would provide limited additional insight, since the landmark graph is closely tied to the base distance model used to construct it. In particular, the graph is built using the (δ\delta)-net rule, where an edge between two landmark centroids is added only if their estimated distance is below (δκ\delta\kappa). As a result, the graph already implicitly captures information from the base distance model, and replacing it with a random or constant distance model would not reproduce the same graph structure or distance information.


Sensitivity to κ\kappa and δ\delta: The ablation shows that smaller δ\delta and κ\kappa smaller are better, but smaller increases the number of landmarks and preprocessing cost. Can you provide a more detailed cost-benefit analysis, including preprocessing time and memory, for the recommended settings?

In the revised version of the paper, we added Section 4.3, Computational Cost, where we provide a more detailed analysis of construction and querying time. We also want to highlight that most of the additional computational cost of our method comes during construction rather than at inference time. As discussed in the new section, we make several design choices to keep these costs manageable while still benefiting from smaller values of δ\delta and κ\kappa.


Comparison to alternative post-hoc methods: The paper compares HDD to flat base models. Are there other post-hoc distance-improvement methods, such as graph-based smoothing or local averaging, that could serve as stronger baselines? How does HDD compare to these?

To the best of our knowledge, there are currently no established post-hoc methods that directly address the problem we consider in our paper: improving the long-range estimates of an existing learned distance model without requiring further training. We discuss the most closely related prior work in the Related Work section. For example, Plan2Vec (Yang et al., 2020) uses graph-derived distance estimates to train a new representation, while Bagatella and Martius (2023) use graph-based aggregation to improve goal-conditioned value estimates for planning. Although these approaches share some methodological similarities with ours, they address different problems and are not directly comparable as general-purpose distance estimation methods.

Regarding the suggested alternatives of graph-based smoothing and local averaging, we are not aware of established methods that apply these techniques to improve learned temporal distance estimates. We would welcome references to any specific methods the reviewer has seen that use these ideas, particularly if they would help identify appropriate additional baselines. However, without a concrete existing method to compare against, such experiments would require developing and validating new algorithms from scratch rather than evaluating established and well-understood alternatives to our approach.

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

This paper examines estimating the minimum action distance (MAD), e.g. the minimum possible number of actions to move between two states in an MDP. The paper assumes an initially learned forward and backward estimators for distance between states and assumes this estimator has bounded error for states nearby, but may have arbitrarily poor estimation for distant states. The paper additionally assumes access to a dataset of state trajectories generated by an unknown, arbitrary behavior policy.

The primary contribution of the paper is an algorithm with associated theoretical guarantees, to provide bounded errors for distance estimates between any two pairs of states in the state space. To achieve this the paper proposes an algorithm to build a graph between a set of landmark states which cover all states observed in the trajectory dataset. Using these landmark states as nodes the algorithm creates a DAG where edges connect nearby landmarks and edge weights encode the distance between pairs.

Given the DAG the algorithm then computes and stores the shortest paths between all landmark pairs. Given this set of paths a new MAD estimate can be generated from state s to t by connecting s to nearby landmarks using the forward distance estimate and t to nearby landmarks using the backward distance estimate and then computing the shortest path between the two. This is quite as all paths between landmarks are pre-computed so only a few paths must actually be considered.

The theoretical analysis provides a worst case bound on the distance estimate provided by this hierarchical estimator, given the stated assumptions.

Empirical results show that the hierarchical algorithm improves distance estimation in a loco-navigation task, in terms of correlation to underlying graph distance which is not the true minimum distance, for three different local distance estimators. Importantly, the results show that distance estimation greatly improves as the ``ground truth'' distance between states increases. This validates for these domains the primary objective set out in the paper: improving long range MAD estimates given a locally good estimator.

The paper then presents planning results which uses the distance estimate to a goal state as the cost function. Results show significant improvements for success rate in both tested domains.

Critical strengths

The paper is clearly written and very easy to follow. It was a joy to read!

The theoretical results appear sound and provide support for using this approach over alternatives which lack such guarantees.

The empirical results support the utility of the approach. Most importantly it showed how the improved estimates can directly be leveraged to improve success on the downstream planning and control task, showing the benefits of the work extend beyond the theoretical results.

Critical weaknesses

None

Questions for authors

Could you pull out the planning result success plots for the different seeds? This would be better presented ideally as a scatter plot, or possibly separate bar graphs per seed. The +/- error bounds don't make sense for a bounded range of 0.0 to 1.0 where many of the samples are at the extrema.

It would be helpful to have an empirical experiment where the ground truth MAD distances were known, so that the accuracy/tightness of the bounds could more accurately be examined. I would suggest a simple 2D stochastic grid navigation task where the MAD between any two states would be simply the shortest path distance.

This test case could also be used to show, at least for simple tasks, what level of accuracy for the initial local estimator is reasonable. This analysis could be performed for varying levels of entropy in the transition dynamics, as I would suspect accuracy will decrease as noise in the dynamics increases for a set training set size.

5 comments

Question 1. Could you pull out the planning result success plots for the different seeds? This would be better presented ideally as a scatter plot, or possibly separate bar graphs per seed. The +/- error bounds don't make sense for a bounded range of 0.0 to 1.0 where many of the samples are at the extrema.

Thanks for the useful question, below we include the full table with the result of each seed.

EnvironmentBase / DataFlat (seeds 0-4)Hier. (seeds 0-4)Delta
PointMaze MediumHILBERT / navigate0.30 0.38 0.38 0.70 0.281.00 1.00 1.00 1.00 1.00+0.592
PointMaze MediumHILBERT / stitch0.44 0.40 0.48 0.16 0.321.00 1.00 1.00 1.00 1.00+0.640
PointMaze MediumMAD / navigate0.54 0.56 0.58 0.60 0.481.00 1.00 1.00 1.00 1.00+0.448
PointMaze MediumMAD / stitch0.40 0.20 0.48 0.42 0.361.00 1.00 1.00 1.00 1.00+0.628
PointMaze MediumTDMAD / navigate0.48 0.52 0.26 0.36 0.321.00 1.00 1.00 1.00 1.00+0.612
PointMaze MediumTDMAD / stitch0.16 0.62 0.22 0.38 0.521.00 1.00 1.00 1.00 1.00+0.620
PointMaze LargeHILBERT / navigate0.12 0.10 0.00 0.06 0.001.00 1.00 1.00 1.00 1.00+0.944
PointMaze LargeHILBERT / stitch0.00 0.00 0.02 0.18 0.001.00 1.00 1.00 1.00 1.00+0.960
PointMaze LargeMAD / navigate0.18 0.56 0.20 0.26 0.421.00 1.00 1.00 1.00 1.00+0.676
PointMaze LargeMAD / stitch0.52 0.46 0.52 0.56 0.321.00 1.00 1.00 1.00 1.00+0.524
PointMaze LargeTDMAD / navigate0.36 0.30 0.32 0.16 0.401.00 1.00 1.00 1.00 1.00+0.692
PointMaze LargeTDMAD / stitch0.26 0.32 0.40 0.18 0.201.00 1.00 1.00 1.00 1.00+0.728
PointMaze GiantHILBERT / navigate0.00 0.00 0.00 0.00 0.001.00 1.00 1.00 1.00 0.96+0.992
PointMaze GiantHILBERT / stitch0.00 0.00 0.00 0.00 0.001.00 1.00 0.98 0.94 1.00+0.984
PointMaze GiantMAD / navigate0.12 0.00 0.18 0.04 0.020.94 1.00 1.00 0.98 1.00+0.912
PointMaze GiantMAD / stitch0.16 0.00 0.04 0.00 0.001.00 1.00 1.00 1.00 1.00+0.960
PointMaze GiantTDMAD / navigate0.00 0.00 0.00 0.10 0.041.00 1.00 1.00 1.00 1.00+0.972
PointMaze GiantTDMAD / stitch0.00 0.00 0.00 0.00 0.001.00 1.00 1.00 1.00 1.00+1.000
AntMaze MediumHILBERT / explore0.22 0.04 0.04 0.18 0.041.00 1.00 0.98 1.00 0.98+0.888
AntMaze MediumHILBERT / navigate0.18 0.20 0.18 0.20 0.360.98 0.96 0.86 1.00 0.98+0.732
AntMaze MediumHILBERT / stitch0.26 0.26 0.24 0.48 0.360.82 0.78 0.78 0.88 0.94+0.520
AntMaze MediumMAD / explore0.50 0.42 0.52 0.48 0.541.00 1.00 0.98 1.00 1.00+0.504
AntMaze MediumMAD / navigate0.44 0.46 0.44 0.58 0.501.00 1.00 1.00 1.00 1.00+0.516
AntMaze MediumMAD / stitch0.48 0.22 0.44 0.52 0.481.00 0.98 1.00 1.00 1.00+0.568
AntMaze MediumTDMAD / explore0.14 0.34 0.32 0.34 0.341.00 1.00 1.00 1.00 1.00+0.704
AntMaze MediumTDMAD / navigate0.16 0.36 0.32 0.18 0.161.00 0.98 1.00 1.00 1.00+0.760
AntMaze MediumTDMAD / stitch0.36 0.22 0.24 0.28 0.401.00 1.00 1.00 1.00 1.00+0.700
AntMaze LargeHILBERT / navigate0.02 0.02 0.00 0.02 0.120.72 0.56 0.66 0.32 0.42+0.500
AntMaze LargeHILBERT / stitch0.06 0.00 0.04 0.00 0.020.46 0.42 0.52 0.56 0.48+0.464
AntMaze LargeMAD / navigate0.46 0.32 0.34 0.30 0.280.98 1.00 0.94 0.98 0.96+0.632
AntMaze LargeMAD / stitch0.26 0.26 0.38 0.32 0.320.98 1.00 1.00 0.96 0.96+0.672
AntMaze LargeTDMAD / navigate0.38 0.28 0.36 0.28 0.340.98 0.98 1.00 0.98 0.98+0.656
AntMaze LargeTDMAD / stitch0.32 0.32 0.34 0.32 0.320.98 0.96 1.00 1.00 1.00+0.664
AntMaze GiantHILBERT / navigate0.00 0.00 0.00 0.00 0.000.50 0.58 0.68 0.40 0.54+0.540
AntMaze GiantHILBERT / stitch0.00 0.00 0.00 0.00 0.000.36 0.38 0.50 0.34 0.36+0.388
AntMaze GiantMAD / navigate0.02 0.00 0.00 0.00 0.001.00 1.00 0.96 1.00 1.00+0.988
AntMaze GiantMAD / stitch0.04 0.00 0.02 0.00 0.020.98 0.98 0.96 0.98 0.92+0.948
AntMaze GiantTDMAD / navigate0.00 0.00 0.00 0.00 0.000.98 0.98 1.00 0.96 0.98+0.980
AntMaze GiantTDMAD / stitch0.00 0.00 0.00 0.00 0.001.00 0.96 1.00 0.98 0.98+0.984

Question 2. It would be helpful to have an empirical experiment where the ground truth MAD distances were known, so that the accuracy/tightness of the bounds could more accurately be examined. I would suggest a simple 2D stochastic grid navigation task where the MAD between any two states would be simply the shortest path distance.

See the general comment on top. We included a cyclic Towers of Hanoi benchmark to answer this question.


Question 3. This test case could also be used to show, at least for simple tasks, what level of accuracy for the initial local estimator is reasonable. This analysis could be performed for varying levels of entropy in the transition dynamics, as I would suspect accuracy will decrease as noise in the dynamics increases for a set training set size.

We thank the reviewer for this suggestion. It is worth noting that the Minimum Action Distance (MAD) does not directly depend on the transition probabilities, but only on the support of the transition function, i.e. the set of possible next states.

This means that increasing the entropy of the transition dynamics does not change the true MAD as long as the set of possible next states remains the same. However, the entropy can impact the exploration strategy and ultimately how well these transitions are represented in the training data. If certain transitions become less likely, they may not appear in the collected trajectories, making it harder for the model to learn accurate local distances.

The table is a bit overkill, I was really suggesting something like a scatter plot for the paper. In general tables are much harder for the reader to parse and a thoughtful plot is much easier. Nevertheless this doesn't effect my overall opinion of the work, but I think there's still an opportunity for a clearer presentation.

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

This paper proposes a hierarchical, inference-time algorithm, that enables a performance improvement over planning with a given learnt distance function. The hierarchy is based on selecting subgoals from the dataset and using them to create a ‘discrete’ graph that approximately covers the state space. The states for that graph are selected based on a learnt distance function. At inference, the distance is calculated by getting from starting and final states to that discrete graph and then utilizing a precomputed distance function on that discrete graph. The paper proves theoretical guarantees of the proposed algorithm and it also seems to significantly improve the planning abilities in OGBench ant- and point-maze datasets.

Critical strengths
  • The paper is well written.
  • The proposed improvement is inference-time, meaning that it could be used independently of the RL algorithm.
  • The theoretical justification of the algorithm is quite good.
Critical weaknesses
  • The algorithm in the current version has some limitations that are not mentioned or properly evaluated in the paper:

    • The coverage of the dataset likely needs to be very good for this method to work,
    • The planning stage might be quite expensive and the authors haven’t demonstrated that an actor can be trained to select the actions,
    • While this is mentioned in conclusions, I believe an experimental evaluation to see how locally good does the value function needs to be is needed.
  • To be fair, the experimental evaluation should compare each method with the best planning algorithm for the given method, in particular if using the actor is optimal, an actor should be used.

Questions for authors
  • Why is it important for the distance to have the ability of being asymmetric?
  • Can this algorithm be extended to settings where the state space might not be covered, because it’s simply too large?
  • Would this algorithm enable finding shorter paths for an environment with a huge state space as for instance the Rubik’s Cube?
  • Do the authors see a way of extending their algorithm to enable online adaptation after the offline pretraining?
  • How efficient is the proposed algorithm? How much more expensive does the inference get? Would it be cheap enough to utilize in an online setup?
  • Could this improved distance estimation improve the actual training, or is it only expected to improve the inference?
  • How do the methods without the added inference-time layer fail? Do they fail because the agent runs into walls and can’t get out?
  • If we took dθd_\theta to be very bad, at which point would the proposed algorithm start to work? In particular, I’m curious what happens if dθd_\theta is the hilbert approximation with added gaussian noise. And then, I wonder what happens if we take dθ(s,c)=∣∣s−c∣∣2d_\theta(s,c)= ||s - c||_2
  • The theoretical bound doesn’t match the experiments. While it is clearly specified in the paper why that might work, I’d like to see an example of when the landmarks don’t lie densely enough near the reference path.
  • The experimental evaluation is limited to navigation environment, would it work in manipulation environments?
  • What happens to the inference cost as the action dimensionality grows?
6 comments

Question 1.

The Minimum Action Distance (and other notions of temporal distance) are not necessarily symmetric: reaching some state gg from state ss may require a different number of actions than travelling in the opposite direction. This arises in an obvious way when solving navigation tasks with one-way routes, but also in more subtle ways (but nonetheless significant) in a broader range of problems --- for instance, in continuous control problems, a robot's momentum, acceleration, and other physical constraints can make movements difficult to reverse immediately. In all such cases, if a distance-learning method is unable to capture the inherent asymmetry of the MAD, this will lead to approximation errors and degradation in any downstream application that uses its distance estimates.

The approach proposed in this paper explicitly supports asymmetric distances, and we evaluate it using both asymmetric (e.g., MadDist and TDMAD) and symmetric (e.g., HILBERT) base models.


Question 2.

Our method does not require complete coverage of the state space. Indeed, our experiments involve environments with continuous state spaces, which cannot be exhaustively covered by finite datasets and, therefore, require generalisation to produce distance estimates for unseen states. Assumption 2 requires only that at least one shortest path between a pair of queried states is covered by nearby landmarks, rather than requiring coverage of the entire environment. The method can, therefore, generalise beyond observed states and trajectories, provided that the base distance model is sufficiently accurate locally around the landmarks on the shortest path between a queried pair of states (with our theoretical results explicitly bounding distance estimation error in terms of this local accuracy).

Our experiments also demonstrate strong performance in settings where the state-only trajectory dataset provides more limited coverage of the state-space. In particular, the OGBench stitch datasets contain short, non-overlapping trajectories that must be composed and generalised to more distant states to solve longer-horizon tasks; the proposed approach performs well in this setting.

As with any method that learns from experience, performance can degrade when the available data provides insufficient information about a pair of queried states. In our case, this may affect both the accuracy of local distance estimates learned by the base model and the availability of paths on the landmark graph. One promising extension to address this is to update the base distance estimates and landmark graph online as the agent explores novel regions of its environment. We discuss this possibility further below, in our response to Question 4.


Question 3.

Our experiments suggest that hierarchical distance decomposition remains effective as environments grow, with the largest improvements over the base models observed on the largest environments tested.

Rubik's Cube is an interesting example because, despite its huge state space, the maximum shortest-path distance between any two states is only 20 moves (the so-called "God's number"). Therefore, the size of its state space does not necessarily imply that long-horizon distance estimation will be difficult. In principle, though, our method could be applied to this problem without issue, provided that the base distance model is sufficiently locally accurate and that the landmark graph adequately covers paths between states we might query. Importantly, the proposed approach does not require explicit enumeration of the entire state space; its computational cost instead depends on the number of landmarks selected, which is typically much lower than the total number of states.

Improved distance estimates could then help a downstream agent (e.g., through planning or reward shaping) identify shorter solutions, although we have not evaluated this particular problem.


Question 4.

We thank the reviewer for raising this important direction for future work.

Yes, we see a clear route to extending the proposed approach to support online, incremental learning after offline pretraining. Existing base distance-learning methods, such as METRA (Park et al., 2024) and TDMAD (Steccanella et al., 2026), already provide mechanisms to learn or update distance estimates using newly collected experience. Alongside updating the base distance model, an online version of hierarchical distance decomposition could incrementally extend its landmark graph by adding landmark states outside of its existing coverage. The graph's edges, weights, and shortest-path distances could then be updated periodically to incorporate these new landmarks and reflect changes in the underlying distance model. Together, these updates would allow the approach to adapt as the agent explores previously unseen regions, including states not represented in the original pretraining dataset.

Although we have not evaluated this extension empirically, we see a clear and compelling path towards supporting online adaptation. We consider this a promising and important direction for future research, and will include a discussion of it in the Conclusion section of the paper.


Question 5.

The proposed approach separates the computational cost of constructing the landmark graph from that of querying distances. The main preprocessing cost is computing all-pairs shortest paths on the landmark graph using the Floyd-Warshall algorithm, which has complexity O(∣C∣3)O(|\mathcal{C}|^3) on a landmark graph with set of landmarks C\mathcal{C}. Importantly, the number of landmarks (controlled by the spacing parameter δ\delta) is typically orders of magnitude smaller than the number of states in the state space, and this preprocessing is performed only once in the offline setting. Furthermore, the proposed method requires no retraining of the underlying distance model whatsoever.

At inference time, for a queried pair of states (s,g)(s, g), the method evaluates the distance from ss to each landmark and then from each landmark to gg, using the base distance model dθd_{\theta}. This requires O(∣C∣)O(|\mathcal{C}|) distance evaluations to identify suitable entry and exit landmarks. The method then considers up to k2k^2 combinations of these landmarks (with k=5k=5 in our experiments), using the precomputed shortest-path distances to obtain the final distance estimate. Importantly, note that no additional graph search is required at inference time.

For an online version of the method, the landmark graph and its shortest-path distances could be updated periodically. So, the one-off preprocessing cost in the offline setting would become a periodic cost, amortised over the many queries performed between updates. The computational cost would depend on the number of landmarks (as in the offline case) and the frequency of these updates. These updates could be triggered according to any number of criteria, such as when a fixed number of time steps has passed, when a certain number of new states are observed outside the existing landmark coverage, or when the underlying distance model's predictions have changed sufficiently. In any case, updates to the landmark graph could be performed relatively infrequently, keeping the amortised cost low. The inference procedure and its computational complexity would remain the same as in the offline setting.


Question 6.

The main contribution of our paper is a method for improving the long-range distance estimates produced by an existing learned distance model, without requiring any retraining of that model. Our experiments show that these improvements not only increase distance estimation accuracy, but also translate into better downstream planning performance.

We chose planning tasks as our downstream evaluation setting because it allows us to isolate the benefits of improved distance estimates without introducing additional factors associated with policy learning. However, these improved distance estimates could absolutely be used to support reinforcement learning agents, for example through reward shaping or as the basis of goal-conditioned policies.


Question 7.

We thank the reviewer for this question, which gets to the heart of the motivation for our approach.

The primary reason that the agents using the base distance models alone struggle to reach their goals is that their distance estimates become increasingly inaccurate as the separation between queried states grows. In our experiments, the planner uses the model's distance estimates to select actions that are predicted to bring the agent closer to its goal. When the estimates are inaccurate, the planner may select actions that make little progress (e.g., causing the agent to become stuck near obstacles).

Crucially, these same base models can often still provide accurate local distance estimates. Our method exploits this by composing accurate short-range predictions through the landmark graph to obtain more accurate long-range predictions. The planner can therefore evaluate its progress towards a distant goal using a chain of more reliable local distance estimates between nearby landmarks, rather than relying on a single, potentially inaccurate long-range prediction.


Question 8.

The assumptions underlying our theoretical analysis are designed to characterize precisely when hierarchical decomposition can improve a base distance model and when its performance may deteriorate.

In particular, an inaccurate base model can affect the hierarchical estimator in two distinct ways. First, it may underestimate the distance between states that are actually far apart, introducing spurious shortcut edges into the landmark graph. Since Floyd–Warshall selects minimum-cost paths, these incorrect shortcuts may be exploited and lead to substantial underestimation. Second, the model may overestimate distances between genuinely nearby states, causing the graph construction to discard valid local connections and potentially introducing detours or disconnecting parts of the landmark graph.

Assumption 1 (Local accuracy) explicitly addresses both failure modes. It requires the base model to have bounded error whenever either the predicted or the true distance is below the local threshold. Importantly, the method does not require accurate predictions between distant state pairs, provided that these pairs are also recognized as distant by the model.

Consider perturbing the Hilbert distance with Gaussian noise of increasing variance. For small perturbations, we expect the hierarchy to remain effective as long as the local distance estimates are sufficiently reliable. As the noise variance increases, however, erroneous local connections and missing valid edges become increasingly likely.


Question 9.

Theorem 1 relies on Assumption 2 (Coverage). This assumption is important because the theoretical upper bound is established by constructing a feasible route through landmarks that cover successive waypoints along the reference path.

The theoretical bound does not contradict the stronger empirical results because it is a conservative worst-case guarantee. It constructs a particular route through covering landmarks, charging a detour cost at every hop, whereas the actual algorithm selects the shortest available route in the landmark graph. In practice, when landmarks are distributed densely along useful trajectories, the selected route may incur much smaller detours than those allowed by the theoretical analysis.


Question 10.

Yes, the proposed method is not tied to navigation problems, and could be applied to robotic manipulation tasks in the same manner. It requires only an existing base distance model and a dataset of state-only trajectories, making it applicable to a broad range of sequential decision problems.


Question 11.

The inference cost of the proposed method does not directly depend on action dimensionality. Hierarchical distance decomposition operates entirely on state-only trajectories and uses an existing base distance model to estimate distances between nearby states. As discussed in our response to Question 5, the inference cost introduced by this approach depends on the number of landmarks and is not directly influenced by the dimensionality of the action space.

Of course, action dimensionality may affect the computational cost of downstream planners or reinforcement learning algorithms, as well as the difficulty of collecting state-only trajectories that provide reasonable coverage of the state space. However, the impact of action dimensionality will vary considerably depending on the specific planning, learning or data-collection methods used. Importantly, these choices are independent of the method proposed in our paper, which addresses the specific problem of long-horizon distance estimation.

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

This paper addresses long-range Minimum Action Distance (MAD) estimation in reinforcement learning: learned distance models are locally accurate but unreliable over long horizons. It proposes hierarchical distance decomposition, a post-hoc method that can be applied to any existing learned distance model without retraining. The method selects a sparse set of landmark states from an offline dataset using a greedy two-sided delta-net, builds a directed graph whose edges connect only nearby landmarks (within kappa times delta), precomputes all-pairs shortest paths with Floyd-Warshall, and then estimates a query distance by composing local predictions through the landmark graph, with k = 5 nearest landmarks in each direction and a same-landmark fallback to the direct local prediction. Theory gives two-sided error bounds and an order-preservation result for sufficiently separated state pairs, under local-accuracy and dataset-coverage assumptions. Experiments on PointMaze and AntMaze from OGBench (medium, large, and giant sizes; navigate, stitch, and, for AntMaze Medium, explore datasets) use three base distance models (MAD, TDMAD, and HILBERT) and report Spearman rank correlation with grid-geodesic distance and downstream planning success over 50 episodes and five seeds.

Critical strengths
  1. A simple, general, and genuinely useful post-hoc idea with theory that matches its motivation. Because the hierarchy reuses only short-range predictions that the base model can be trusted on, it does not require retraining or a new distance model, and it is evaluated exactly as a flat-versus-hierarchical comparison using the same underlying base model. The theory is also honest about its conditions (local accuracy and coverage) and about the fixed per-hop cost in the upper bound. 2. Large and consistent downstream gains where the base model fails. On giant mazes in Table 1, several flat planners score 0.000 and reach 0.960-1.000 with the hierarchy (for example, PointMaze Giant with HILBERT on stitch, and MAD on navigate), and Spearman correlation improves with distance, with the largest gains at long range. Results are reported over five seeds with standard deviations.
Critical weaknesses
  1. Scope is narrow and the main distance metric is a proxy, not the true MAD. All experiments are on PointMaze and AntMaze navigation in OGBench, and the distance-quality metric is Spearman correlation with grid-geodesic distance, which the paper itself notes is not the exact MAD, particularly in AntMaze where maze topology does not capture embodied dynamics and control effort. The theory also depends on local accuracy and dataset coverage that are not verified on held-out state pairs, and the paper acknowledges that the method depends on a base model with sufficient local accuracy. On the hardest AntMaze tasks the hierarchy helps less: for example, HILBERT on AntMaze Giant navigate rises only from 0.000 to 0.548, versus near-perfect scores on several PointMaze Giant cases. 2. Cost, sensitivity, and reproducibility are under-reported. The paper does not report landmark-graph construction time, Floyd-Warshall cost as the number of landmarks grows, or query-time cost relative to the flat model, and it does not systematically vary delta, kappa, and k. The reproducibility statement says code will be released only upon acceptance of the paper, so the results cannot yet be independently reproduced.
Questions for authors
  1. How sensitive are the results to the spacing delta, the edge-threshold multiplier kappa, and the neighborhood size k, and what are the construction and query-time costs as the landmark set grows? 2. Could the authors validate the distance estimates against true action distances (or a closer proxy than grid-geodesic distance) on a subset of state pairs, and test the method outside maze navigation, where state spaces are not grid-like? 3. What happens when the local-accuracy or coverage assumptions fail, for example when query states are far from any landmark or when the base model is weak locally, and can the method detect and fall back gracefully in those cases?
2 comments

Question 1. How sensitive are the results to the spacing delta, the edge-threshold multiplier kappa, and the neighborhood size k, and what are the construction and query-time costs as the landmark set grows?

We provide an ablation study of the spacing parameter δ\delta and the edge-threshold multiplier κ\kappa in Appendix E, evaluating δ∈{4,6,9,12}\delta\in\lbrace4, 6, 9,12\rbrace and κ∈{2,3,4,6,8}\kappa\in\lbrace2, 3, 4, 6, 8\rbrace across all three base distance models in the largest PointMaze and AntMaze environments. We find that smaller values of both parameters generally produce more accurate distance estimates, with the strongest results obtained using δ=4\delta=4 and κ=2\kappa=2. However, smaller values of δ\delta also increase the number of landmarks, affecting both construction and inference costs (each discussed below). We use k=5k=5 entry and exit candidates throughout our experiments and have found this value provides strong results across a range of environments and problem sizes.

The main construction cost comes from computing the all-pairs shortest paths using the Floyd-Warshall algorithm, which has time complexity O(∣C∣3)O(|\mathcal{C}|^3) and memory complexity O(∣C∣2)O(|\mathcal{C}|^2) for a graph based on landmark set C\mathcal{C}. In the ablation in Appendix E, increasing the landmark spacing δ\delta from 4 to 6 for TDMAD on AntMaze Giant reduced the number of landmarks from 13,85813{,}858 to 4,3634{,}363, which would have reduced the theoretical cubic Floyd-Warshall runtime cost by approximately thirtyfold with little loss in distance estimation accuracy. Importantly, this construction is performed only once, so its cost will be amortised over all subsequent distance queries.

At inference time, for a queried pair of states (s,g)(s, g), the method evaluates the distance from ss to each landmark and then each landmark to gg, using the base distance model dθd_{\theta}. This requires O(∣C∣)O(|\mathcal{C}|) distance evaluations to identify suitable entry and exit landmarks. The method then considers up to k2k^2 combinations of these landmarks, using the precomputed shortest-path distances to obtain the final distance estimate. Importantly, notice that no additional graph search is required at inference time.

See general comment and Section 4.3 added in the paper for a more detailed answer to the inference time cost.


Question 2. Could the authors validate the distance estimates against true action distances (or a closer proxy than grid-geodesic distance) on a subset of state pairs, and test the method outside maze navigation, where state spaces are not grid-like?

See general comment above. We introduce the cyclic tower of Hanoi environment to answer this question.

AuthorsOpenReview ↗

On Source Code Availability

Weakness 2. The reproducibility statement says code will be released only upon acceptance of the paper, so the results cannot yet be independently reproduced.

We have now made an initial version of our implementation publicly available in an anonymous repository: https://anonymous.4open.science/r/HDD-FDC1/ .

While the current release does not yet include the comprehensive documentation and comments we would expect to accompany the final version, we will continue to improve these aspects and make the fully documented repository available upon acceptance.

Comments on the paper

1 comment

We thank all reviewers for taking the time to read our paper and leave thoughtful comments in their reviews.

Here we include some new results and general answers to questions raised by multiple reviewers. We also note that we have updated the manuscript based on our discussions with each reviewer, and that this updated version is now available above.


Updated planning implementation and corresponding results.

In the revised manuscript, we have refined a design choice in the original implementation of our hierarchical distance decomposition approach.

Specifically, when no path existed in the landmark graph between the start and goal landmarks in the landmark graph, the original implementation fell back to the base model's distance estimate. However, because the base models tend to underestimate long distances, these fallback estimates were often much smaller than the distances obtained through valid paths on the landmark graph. As a result, the planner could be encouraged to navigate towards states for which no path existed to the goal landmark on the landmark graph.

This issue was particularly pronounced in AntMaze Giant Navigate, where the training dataset contains trajectories in which the ant is flipped upside down. Such states are often associated with dead-end regions of the landmark graph. The underestimated fallback distances encouraged the planner to navigate towards these regions, sometimes guiding the ant into configurations where it flipped over.

We have now modified the fallback behaviour to return a distance estimate of infinity when no path exists on the landmark graph, which completely prevents this failure mode.

We reran our experiments with this change and found that it primarily affected planning performance in AntMaze Giant Navigate. The updated results are summarised below:

Base / DataOriginalUpdated
MAD / navigate0.620 ± 0.3790.992 ± 0.016
TDMAD / navigate0.572 ± 0.1780.980 ± 0.013

These updated results show that the refined method achieves even stronger planning performance in the affected environments, without requiring changes to the underlying distance-learning models or hierarchical decomposition approach.


Empirical experiment with known MAD ground truth distance and strong asymmetry.

To answer questions raised by multiple reviewers around (1) comparing to the true reference MAD and (2) evaluating the impact of asymmetry, we included a new Cyclic Towers of Hanoi environment that features a large discrete state space of 2,1872,187 states and highly asymmetric dynamics, meaning that the minimum action distance between two states can differ depending on the direction.

Unlike PointMaze and AntMaze, where we use grid-geodesic distance as an approximation of MAD, in Cyclic Towers of Hanoi we can compute the exact MAD for every pair of states. This allows us to evaluate our method directly against the ground truth instead of some reasonably aligned proxy (e.g., the grid-geodesic distance in PointMaze and AntMaze), as several reviewers have requested.

The results show that our hierarchical approach substantially improves long-range distance estimates in this setting. We also evaluate how well the models capture the asymmetry of the MAD. Both MAD and TDMAD, along with their hierarchical versions, are able to capture this asymmetry. In contrast, HILBERT remains symmetric by construction, even after applying our method.

We believe these additional experiments strengthen our results by showing that the improvements are not limited to the maze environments or to evaluations based on approximate ground-truth distances. The full results are included in Appendix I, with the asymmetry results shown in Figure 3.

Computational overhead of the proposed approach.

In Section 4.3, we have introduced a new analysis of the computational overhead of the hierarchy, distinguishing between the offline cost incurred during construction (BUILD HIERARCHY phase) and the inference cost associated with querying distances (QUERY DISTANCE phase).

We carefully design our Hierarchical Distance Decomposition taking advantage of the structure of the base distance models we used; each base distance used in our paper is composed of a fixed state encoder ϕθ(s)\phi_{\theta}(s) and a simple distance function in the latent space: dsimple(ϕθ(s)−ϕθ(g))d_{\text{simple}}(\phi_{\theta}(s) - \phi_{\theta}(g)) for MADdist and TDMADdist, and ∥ϕθ(s)−ϕθ(g)∥2\lVert \phi_{\theta}(s) - \phi_{\theta}(g) \rVert_2 for Hilbert. This structure allows us to simply store the latent representation ϕθ(c)\phi_{\theta}(c) for every landmark centroid during construction. When querying distances, we only need to encode the query states and perform inexpensive operations in the latent space to compute their distances to the centroids, without repeatedly evaluating the encoder for every landmark. This significantly reduces the computational overhead of querying the hierarchy.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.