Hierarchical Distance Decomposition for Minimum-Action-Distance Estimation

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.