REVIEW 3 major objections 5 minor 43 references
Learning The Minimum Action Distance
T0 review · 3 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read Minimum action distance between states can be learned from pure state trajectories, with no rewards or actions, beating prior representation methods across discrete, continuous, and stochastic environments.
desk verdict Useful benchmark and a solid empirical case for a simple quasimetric, but the coverage gap and missing predecessor baseline keep it conditional. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the characterization of the minimum action distance as the unique solution of a constrained optimization problem: over the graph $(\mathcal{S}, R)$ whose edges are the one-step feasible transitions, $d_{\mathrm{MAD}}$ is the largest distance function satisfying identity, the bound $d(s, s') \le 1$ on every edge, and the triangle inequality, which in finite state spaces is exactly the all-pairs shortest-path metric with unit edge costs computed by Floyd-Warshall. The learning machinery converts this intractable program into a differentiable objective by building the triangle inequality into the distance function by construction: distances are $d_q(\varphi(s), \varphi(s'))$ for a learned embedding $\varphi$ and a quasimetric $d_q$, leaving only the one-step constraints to enforce. Trajectory pairs $(s_i, s_j)$ supply the upper bounds $j-i$, and the loss combines a scale-invariant regression term, a contrastive separation term, and a constraint term; TDMadDist additionally exploits the shortest-path Bellman identity $d_{\mathrm{MAD}}(s_i, s_j) = 1 + d_{\mathrm{MAD}}(s_{i+1}, s_j)$ with a target network. The paper's quasimetric $d_{\mathrm{simple}}(x, y) = \alpha \max(\mathrm{relu}(x - y)) + \frac{1-\alpha}{d} \sum_i \mathrm{relu}(x_i - y_i)$, a weighted blend of the maximum and the mean of the positive coordinate differences, carries the asymmetry, satisfying identity, non-negativity, the triangle inequality, and positive homogeneity without requiring symmetry.
What would settle it
Build a three-state line with a shortcut, $A \to B \to C$ plus a direct edge $A \to C$, and collect trajectories that only ever witness the pair $(A, C)$ two steps apart, never one step apart: every observed upper bound on $d_{\mathrm{MAD}}(A, C)$ is then 2 while the true value is 1. If MadDist trained on these data reports a distance near 2, the learned metric is exactly the largest quasimetric consistent with observed bounds, confirming that coverage of the one-step transition graph is what determines accuracy; if it reports a distance near 1, the model is recovering structure the loss never witnessed, which would point to inductive bias of the network rather than the bound objective as the source of accuracy.
Extended reading notes
Core claim
The paper's central claim is that the minimum action distance, the least number of decision steps needed to reach one state from another and equivalently the shortest path in the graph of one-step feasible transitions, is recoverable from state-only trajectory data, and that the recovered distances are accurate enough to guide downstream goal-reaching planning. The authors characterize $d_{\mathrm{MAD}}$ as the unique solution of a constrained optimization problem: maximize all pairwise distances subject to identity, unit upper bounds on one-step transitions, and the triangle inequality; in finite state spaces this is exactly the all-pairs shortest-path problem with unit edge costs. They make this program learnable by enforcing the triangle inequality by construction, computing distances as $d_q(\varphi(s), \varphi(s'))$ for a learned embedding $\varphi$ and a quasimetric $d_q$. Their MadDist objective regresses embedded distances toward the trajectory upper bound $j-i$ with a scale-invariant loss, adds a contrastive term that pushes random state pairs apart, and penalizes violations of the bound, while TDMadDist replaces the fixed target with the bootstrapped $1 + d_{\theta'}(s_{i+1}, s_j)$ through a target network. Across a purpose-built suite of environments with known ground-truth MAD, discrete and continuous, deterministic and stochastic, including directed transitions and noisy observations, the paper reports that MadDist achieves near-perfect rank and linear correlations and low ratio coefficients of variation, outperforming the QRL and Hilbert baselines, and attains high or perfect success on OGBench goal-reaching planning tasks, including 'stitch' datasets assembled from short trajectory fragments and 'explore' datasets collected by a random policy.
Load-bearing premise
The entire training signal is an upper bound, a state seen $j-i$ steps after another in a trajectory is at most $j-i$ actions away, so the learned metric can match the true minimum action distance only if the observed trajectories cover the one-step transitions that actually lie on shortest paths, and the paper states no coverage condition or sample-complexity bound that guarantees this.
Editorial extensions
If this is right
- The learned distances provide a dense progress signal for goal-conditioned agents: in the paper's random-shooting planning evaluation, MadDist distances yield high or perfect success across OGBench mazes, including Giant layouts whose shortest paths run up to roughly 1000 steps.
- Because $d_{\mathrm{MAD}}$ depends only on the support of the transition kernel, not on the probabilities, a learned MAD representation transfers across stochastic dynamics and probability shifts without retraining, as long as the set of reachable transitions is unchanged.
- The quasimetric formulation captures irreversible dynamics, such as key acquisition and cliff resets, that symmetric Euclidean embeddings cannot represent, so representation quality in those environments improves in kind, not just in degree.
- The scale-invariant loss prevents long-horizon pairs from dominating training, which the paper argues explains why accuracy holds across short and long distances alike.
Reading between the lines
- The recovery claim rests on an implicit coverage condition the paper does not state: because every training signal is an upper bound $j-i$, the learned metric is the largest quasimetric consistent with the observed bounds, and it can exceed the true $d_{\mathrm{MAD}}$ by exactly the length of any missing shortest-path shortcut; the paper's evaluations use full random or noisy-expert policies that
- The upper-bound framing opens a concrete sample-complexity question the paper leaves open: how many trajectories, collected by which policies, suffice to recover $d_{\mathrm{MAD}}$ to within additive error $\varepsilon$; a natural route would connect MadDist to shortest-path recovery on random subgraphs of the transition graph.
- The strong results on NoisyGridWorld, where Gaussian noise is appended to the true coordinates, hint that the embedding implicitly denoises the latent geometry; an untested sharper regime is noise that corrupts the transition support itself, where the upper-bound argument would need modification.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes two self-supervised algorithms, MadDist and TDMadDist, for learning the Minimum Action Distance (MAD) from state-only trajectories, without rewards or actions. The methods embed states and use a quasimetric distance function; the main loss matches embedded distances to trajectory-interval lengths, a contrastive term separates random pairs, and a constraint term penalizes violations of the trajectory upper bound. The paper also introduces a simple ReLU-based quasimetric, dsimple, and a benchmark suite with known or proxied MAD values. Experiments compare the proposed methods against QRL and Hilbert baselines using correlation, coefficient of variation, and downstream planning success rates.
Significance. If the central claim were established, this would be a useful contribution: action- and reward-free distance learning with asymmetric metrics, a clean finite-state characterization of MAD, and a controlled benchmark suite for evaluating MAD approximations. The paper is clearly written and includes several positive features: the proof that the exact MAD is the unique solution of the shortest-path LP for finite state spaces (Appendix A), the triangle-inequality proof for dsimple (Appendix B), the breadth of environments (stochastic, noisy, continuous, asymmetric), and a downstream planning evaluation that goes beyond correlation metrics. However, the central identification claim is currently not supported by the theory or the experimental protocol, which is the main reason for the requested revision.
major comments (3)
- [§4, §6.1, Eqs. (4)–(7)] The training objective does not implement the exact constrained optimization of Eq. (1), and no coverage condition links the sampled problem to the true MAD. In particular, Eq. (5) minimizes (dθ(si,sj)/(j−i) − 1)^2, so the trajectory interval j−i is used as a target, not merely as an upper bound. Since j−i can exceed the true MAD when the trajectory is not a shortest path, this objective actively inflates estimates. The only mechanism that can pull distances down to the shortest-path value is the triangle inequality applied through observed one-step transitions, and Eq. (7) constrains only pairs with index difference at most Hc (Hc=6 in all experiments, Appendix D). No coverage condition or sample-complexity bound is provided; Appendices A–C contain the exact finite-graph proof and a restatement of the loss heuristic, not an identifiability result for the sampled problem. In the partial-coverage regime, the learned metric can be arbitrarily larger than dMAD, so the abstract claim that embedded distances 'correspond to their MAD' is unsupported.
- [§7, Appendix G] The evaluation does not measure the true MAD in the continuous and noisy environments. In NoisyGridWorld the network observes (x,y,n1,n2) with independent Gaussian noise, so the transition relation on the observed state space depends on the noise components; the hidden-coordinate Manhattan distance is not the MAD of the observed MDP. For PointMaze and AntMaze, the stated ground truth is the Floyd-Warshall shortest path over a discretized grid, which is an approximation to the continuous-state MAD rather than the exact value. The reported correlations therefore validate agreement with these proxies, not recovery of the true MAD, and cannot resolve whether the method actually learns MAD in continuous or noisy domains.
- [§7, Appendix H] The experimental protocol does not describe any train/test split or held-out state evaluation. The correlation and CV metrics appear to be computed on states from the training trajectories, and the planning evaluation reuses the learned metric during simulated rollouts; without a holdout it is unclear whether the results reflect generalization to unseen states or memorization of the training set. A clear held-out evaluation protocol should be specified.
minor comments (5)
- [Appendix C.3] The notation D<Hc is used for the constraint-pair set, while Section 6.1 defines D≤Hc; the two should be made consistent.
- [§7, Appendix F] The number of random seeds is reported as three in Section 7, but Appendix F and the ablation captions refer to five seeds; this inconsistency should be resolved.
- [Appendix D] The statement that code 'will be provided upon acceptance' is a reproducibility concern; code and data splits should be released with the manuscript or a specific reason given for withholding them.
- [§4, Eq. (1)] Eq. (1) sums over S^2, which is not well-defined when S is continuous; the continuous case needs a measure-theoretic formulation or an explicit restriction to finite state spaces.
- [Appendix D.3] There is a typo in the first sentence: 'the the Adam optimizer' should read 'the Adam optimizer'.
Circularity Check
No circularity: loss targets are trajectory-derived upper bounds j−i, not fitted ground-truth MAD values; evaluation and uniqueness proof are self-contained.
full rationale
The paper's training signal is the trajectory index difference j−i, which the paper explicitly identifies as an upper bound on dMAD (Section 4: 'j−i is an upper bound on dMAD(si, sj)'), not as the ground-truth distance itself. The losses in Eqs. (4)-(9) fit the embedding distance to these data-derived bounds and penalize violations, while the reported evaluation compares the learned distances against independently computed ground-truth MAD values (Manhattan distance, Floyd-Warshall shortest paths) in environments where those values are known. The uniqueness theorem in Appendix A is proved in the paper for the optimization problem in Eq. (1) and is not imported from the authors' prior work. The only self-citation, Steccanella and Jonsson (2022), is used as a point of comparison for the older symmetric loss and is not load-bearing for the new quasimetric claims. TDMadDist bootstrapping from a target network is standard temporal-difference practice, not a definitional loop. The absence of a coverage condition or sample-complexity bound is a genuine identifiability and soundness limitation, since under partial transition coverage the learned metric can be inflated, but that is a correctness gap rather than circularity: the model outputs are not forced to equal the ground truth by construction.
Assumptions & free parameters
free parameters (6)
- d_simple mixing weight alpha =
not stated in paper
- contrastive loss weight w_r =
1 or 10
- constraint loss weight w_c =
0.1
- contrastive scale dmax =
100 or 500
- horizon cap H_c =
6
- target network smoothing tau =
0.005
assumptions (3)
- domain assumption For any trajectory pair (s_i, s_j) with i<j, j-i is an upper bound on d_MAD(s_i,s_j)
- domain assumption The dataset D sufficiently covers the one-step support relation R of the MDP
- domain assumption Observed state vectors determine the reachability structure despite added noise and continuous state spaces
Cite this review
Pith. "Pith review of Learning The Minimum Action Distance." pith.science (2026). https://pith.science/paper/7UQZDT6F
@misc{pith2026250609276,
author = {Pith},
title = {Pith review of: Learning The Minimum Action Distance},
year = {2026},
howpublished = {\url{https://pith.science/paper/7UQZDT6F}},
note = {Machine review of arXiv:2506.09276}
}
read the original abstract
This paper presents a state representation framework for Markov decision processes (MDPs) that can be learned solely from state trajectories, requiring neither reward signals nor the actions executed by the agent. We propose learning the minimum action distance (MAD), defined as the minimum number of actions required to transition between states, as a fundamental metric that captures the underlying structure of an environment. MAD naturally enables critical downstream tasks such as goal-conditioned reinforcement learning and reward shaping by providing a dense, geometrically meaningful measure of progress. Our self-supervised learning approach constructs an embedding space where the distances between embedded state pairs correspond to their MAD, accommodating both symmetric and asymmetric approximations. We evaluate the framework on a comprehensive suite of environments with known MAD values, encompassing both deterministic and stochastic dynamics, as well as discrete and continuous state spaces, and environments with noisy observations. Empirical results demonstrate that the proposed approach not only efficiently learns accurate MAD representations across these diverse settings but also significantly outperforms existing state representation methods in terms of representation quality.
Figures
Figures from the paper (8 more)
Reference graph
Works this paper leans on
-
[1]
R. S. Sutton and A. G. Barto. Reinforcement learning: An introduction. MIT Press, Cambridge, 1998
work page 1998
-
[2]
T. Wang, A. Torralba, P. Isola, and A. Zhang. Optimal Goal-Reaching Reinforcement Learning via Quasimetric Learning . In Proceedings of the 40th International Conference on Machine Learning, pages 36411--36430. PMLR, 2023 a
work page 2023
-
[3]
S. Park, D. Ghosh, B. Eysenbach, and S. Levine. HIQL : O ffline G oal- C onditioned RL with L atent S tates as A ctions. In Advances in Neural Information Processing Systems, volume 36, pages 34866--34891. Curran Associates, Inc., 2023
work page 2023
-
[4]
L. Steccanella and A. Jonsson. State Representation Learning for Goal-Conditioned Reinforcement Learning . In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 84--99. Springer, 2022
work page 2022
-
[5]
S. Park, O. a Rybkin, and S. Levine. METRA : S calable U nsupervised RL with M etric- A ware A bstraction. In Proceedings of the 12th International Conference on Learning Representations, 2024 a
work page 2024
-
[6]
S. Park, b Tobias Kreiman, and S. Levine. Foundation Policies with Hilbert Representations . In Proceedings of the 41st International Conference on Machine Learning, pages 39737--39761. PMLR, 2024 b
work page 2024
- [7]
-
[8]
J. Tarbouriech, R. Zhou, S. S. Du, M. Pirotta, M. Valko, and A. Lazaric. Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regret . In Advances in Neural Information Processing Systems, volume 34, pages 6843--6855. Curran Associates, Inc., 2021
work page 2021
Show all 43 references
-
[9]
L. P. Kaelbling. Learning to Achieve Goals . International Joint Conference on Artificial Intelligence, 2: 0 1094--1098, August 1993
1993
-
[10]
Hartikainen, X
K. Hartikainen, X. Geng, T. Haarnoja, and S. Levine. Dynamical Distance Learning for Semi-Supervised and Unsupervised Skill Discovery . In Proceedings of the 8th International Conference on Learning Representations, 2020
2020
-
[11]
Y. J. Ma, S. Sodhani, D. Jayaraman, O. Bastani, V. Kumar, and A. Zhang. VIP : T owards U niversal V isual R eward and R epresentation via V alue- I mplicit P re- T raining. In Proceedings of the 11th International Conference on Learning Representations, 2022
2022
-
[12]
Wang and P
T. Wang and P. Isola. Improved Representation of Asymmetrical Distances with Interval Quasimetric Embeddings . In NeurIPS Workshop on Symmetry and Geometry in Neural Representations. Curran Associates, Inc., 2022
2022
-
[13]
Dadashi, S
R. Dadashi, S. Rezaeifar, N. Vieillard, L. Hussenot, O. Pietquin, and M. Geist. Offline Reinforcement Learning with Pseudometric Learning . In Proceedings of the 38th International Conference on Machine Learning, pages 2307--2318. PMLR, 2021
2021
-
[14]
Agarwal, M
R. Agarwal, M. C. Machado, P. S. Castro, and M. G. Bellemare. C ontrastive B ehavioral S imilarity E mbeddings for G eneralization in R einforcement L earning. In Proceedings of the 9th International Conference on Learning Representations, 2021
2021
-
[15]
P. Dayan. Improving Generalization for Temporal Difference Learning: The Successor Representation . Neural Computation, 5 0 (4): 0 613--624, 1993
1993
-
[16]
Barreto, W
A. Barreto, W. Dabney, R. Munos, J. J. Hunt, T. Schaul, H. P. van Hasselt, and D. Silver. Successor Features for Transfer in Reinforcement Learning . In Advances in Neural Information Processing Systems, volume 30, pages 4055--4065. Curran Associates, Inc., 2017
2017
-
[17]
Eysenbach, T
B. Eysenbach, T. Zhang, S. Levine, and R. R. Salakhutdinov. Contrastive learning as goal-conditioned reinforcement learning. Advances in Neural Information Processing Systems, 35: 0 35603--35620, 2022
2022
-
[18]
Myers, C
V. Myers, C. Zheng, A. Dragan, S. Levine, and B. Eysenbach. Learning Temporal Distances: Contrastive Successor Features Can Provide a Metric Structure for Decision-Making . In Proceedings of the 41st International Conference on Machine Learning, pages 37076--37096. PMLR, 2024
2024
-
[19]
Y. Wu, G. Tucker, and O. Nachum. The L aplacian in RL : L earning R epresentations with E fficient A pproximations. In Proceedings of the 7th International Conference on Learning Representations, 2019
2019
-
[20]
M. C. Machado. Efficient Exploration in Reinforcement Learning through Time-Based Representations. PhD thesis, University of Alberta, 2019
2019
-
[21]
K. Wang, K. Zhou, Q. Zhang, J. Shao, B. Hooi, and J. Feng. Towards better laplacian representation in reinforcement learning with generalized graph drawing. In Proceedings of the 38th International Conference on Machine Learning, volume 139, pages 11003--11012. PMLR, 2021
2021
-
[22]
K. Wang, K. Zhou, J. Feng, B. Hooi, and X. Wang. Reachability-aware L aplacian representation in reinforcement learning. In Proceedings of the 40th International Conference on Machine Learning, volume 202, pages 36670--36693. PMLR, 2023 b
2023
-
[23]
R. Bellman. A M arkovian D ecision P rocess. Journal of Mathematics and Mechanics, 6 0 (5): 0 679--684, 1957
1957
-
[24]
R. S. Sutton and A. G. Barto. Reinforcement Learning: An Introduction. MIT Press, Cambridge, MA, 2018
2018
-
[25]
S. Yoon, A. Fern, and R. Givan. FF-Replan: A baseline for probabilistic planning . In Proceedings of the 5th International Conference on Automated Planning and Scheduling (ICAPS), pages 352--359, 2007
2007
-
[26]
R. W. Floyd. Algorithm 97: Shortest Path . Communications of the ACM, 5 0 (6): 0 345, June 1962. ISSN 0001-0782
1962
-
[27]
Warshall
S. Warshall. A Theorem on Boolean Matrices . Journal of the ACM, 9 0 (1): 0 11--12, January 1962. ISSN 0004-5411
1962
-
[28]
J. Fu, A. Kumar, O. Nachum, G. Tucker, and S. Levine. D4RL : D atasets for D eep D ata- D riven R einforcement L earning. arXiv preprint arXiv:2004.07219, 2020
2004 arXiv
-
[29]
S. Park, K. Frans, B. Eysenbach, and S. Levine. Ogbench: Benchmarking offline goal-conditioned rl. arXiv preprint arXiv:2410.20092, 2024 c
2024 arXiv
-
[30]
Loshchilov and F
I. Loshchilov and F. Hutter. Decoupled Weight Decay Regularization . In Proceedings of the 7th International Conference on Learning Representations, 2019
2019
-
[31]
Klambauer, T
G. Klambauer, T. Unterthiner, A. Mayr, and S. Hochreiter. Self-normalizing neural networks. Advances in neural information processing systems, 30, 2017
2017
-
[32]
Loshchilov and F
I. Loshchilov and F. Hutter. Decoupled weight decay regularization. arXiv preprint arXiv:1711.05101, 2017
2017 arXiv
-
[33]
Glorot, A
X. Glorot, A. Bordes, and Y. Bengio. Deep sparse rectifier neural networks. In Proceedings of the fourteenth international conference on artificial intelligence and statistics, JMLR Workshop and Conference Proceedings, pages 315--323, 2011
2011
-
[34]
D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. In Proceedings of the 3rd International Conference on Learning Representations. PMLR, 2015
2015
-
[35]
Andrychowicz, F
M. Andrychowicz, F. Wolski, A. Ray, J. Schneider, R. Fong, P. Welinder, B. McGrew, J. Tobin, P. Abbeel, and W. Zaremba. Hindsight Experience Replay . In Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017
2017
-
[36]
W. K. Newey and J. L. Powell. Asymmetric Least Squares Estimation and Testing . Econometrica: Journal of the Econometric Society, pages 819--847, 1987
1987
-
[37]
Kostrikov, A
I. Kostrikov, A. Nair, and S. Levine. Offline Reinforcement Learning with Implicit Q-Learning . In Proceedings of the 10th International Conference on Learning Representations, 2022
2022
-
[38]
V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski, et al. Human-level control through deep reinforcement learning. nature, 518 0 (7540): 0 529--533, 2015
2015
-
[39]
Van Hasselt, A
H. Van Hasselt, A. Guez, and D. Silver. Deep Reinforcement Learning with Double Q-Learning . In Proceedings of the AAAI conference on artificial intelligence, volume 30, 2016
2016
-
[40]
Hendrycks and K
D. Hendrycks and K. Gimpel. G aussian E rror L inear U nits ( GELU s). arXiv preprint arXiv:1606.08415, 2016
2016 arXiv
-
[41]
Pitis, H
S. Pitis, H. Chan, K. Jamali, and J. Ba. An Inductive Bias for Distances: Neural Nets that Respect the Triangle Inequality . In Proceedings of the 8th International Conference on Learning Representations. Curran Associates, Inc., 2020
2020
-
[42]
Jiang, T
Z. Jiang, T. Zhang, M. Janner, Y. Li, T. Rockt \"a schel, E. Grefenstette, and Y. Tian. Efficient planning in a compact latent action space. arXiv preprint arXiv:2208.10291, 2022
2022 arXiv
-
[43]
write newline
" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 gl...
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.