{"id":"c77dadf4-4e83-453e-bd65-3d970b357c94","arxiv_id":"2506.09276","paper_version":4,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":6,"one_line_summary":"A state-embedding method learns asymmetric minimum-action distances from state-only trajectories and beats existing representation methods on tested environments.","lead":"This paper learns the minimum number of actions needed to travel between states, using only recorded state sequences and no rewards or action labels. The result is a distance metric that can guide goal-reaching and reward shaping in reinforcement learning.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No coverage condition links learned distances to true MAD; under partial transition coverage the loss admits arbitrarily inflated distances.","rationale":"Both the reader's weakest assumption and my stress-test converge on the same point: the training signal is an upper bound, and coverage of the transition support graph R is the unstated condition that makes the learned metric equal to the MAD. The paper's formal result (Appendix A, Theorem 1) establishes that dMAD is the unique maximizer when the constraints are imposed over the full relation R. The learning objective replaces those hard constraints with sampled, soft penalties and a regression toward j−i. There is no proof, bound, or even discussion of when the minimizer of L = Lo + wr Lr + wc Lc coincides with the MAD. The contrastive term Lr actively pushes distances upward for randomly sampled pairs, which is exactly the right direction only if the upper-bound constraints are already sufficiently constraining; without full coverage it inflates estimates. The empirical evaluation cannot rule this out: Pearson/Spearman correlations and Ratio CV are invariant to monotone scaling, and the reported planning success in Table 1 uses the learned distance as a heuristic, so even a systematically inflated metric can guide planning. The continuous environments compound the issue because the ground truth itself is only an approximation (discretized maze shortest paths). I therefore agree with the reader's conditional verdict. The concrete test on a minimal graph with a deliberately omitted edge would settle whether the method recovers the true MAD in the absence of full coverage; if it fails, the central claim needs to be restricted to settings with sufficient coverage and the paper should state a coverage condition or sample-complexity bound. I credit the paper for the clean formal characterization of MAD, the valid quasimetric construction, and the effort to build a benchmark suite; the gap is in the identifiability argument, not in the execution.","tokens_in":20281,"tokens_out":6543,"duration_ms":72163,"concrete_test":"Take a 3-state graph A→B→C (cost 1 each) plus a length-5 corridor A→·→·→·→·→C. Build a dataset containing only the 5-step trajectory A→C and the corridor states, omitting the edges A→B and B→C. Train MadDist with the paper's hyperparameters. If dθ(A,C) ≈ 5 (or dmax) rather than 2, the missing-edge failure is confirmed. For a stronger check, compute the largest metric consistent with all observed upper bounds by linear programming over the observed trajectory pairs, and verify that the learned embedding distances match this upper-bound-inflated metric rather than the true MAD. Repeat on the same graph with full edge coverage: if MadDist then recovers d(A,C) = 2, the discrepancy is attributable to coverage, not to optimization.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 4 observes that j−i is only an upper bound on dMAD(si,sj), yet the MadDist objective (Eqs. 4–7) targets this upper bound: Lo minimizes (dθ/(j−i) − 1)^2 and Lc only penalizes dθ exceeding j−i. The quasimetric's triangle inequality is the only mechanism that can pull distances down to the true shortest path, but it acts only through constraints on observed one-step transitions. If the dataset does not cover the full support graph R (no coverage condition or sample-complexity bound is given anywhere in the paper, including Appendices A–C), then the learned metric is free to be any metric consistent with the observed upper bounds — generically the largest one, further inflated by the contrastive Lr that pushes random pairs toward dmax. Such a metric can be arbitrarily larger than the true MAD. This is not merely formal: in NoisyGridWorld the network observes noisy 4-dimensional states while ground truth is defined on the hidden (x,y); continuous mazes use discretized-grid shortest paths as ground truth; and AntMaze Explore is collected by a random policy, so full edge coverage is implausible. Correlation and CV metrics are scale/rank-based and do not detect a constant or systematic inflation of distances. Thus the central claim that distances between embedded states correspond to MAD is unsupported in the partial-coverage regime.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":20533,"tokens_out":9043,"duration_ms":105680,"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":[{"comment":"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.","section":"§4, §6.1, Eqs. (4)–(7)"},{"comment":"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.","section":"§7, Appendix G"},{"comment":"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.","section":"§7, Appendix H"}],"minor_comments":[{"comment":"The notation D<Hc is used for the constraint-pair set, while Section 6.1 defines D≤Hc; the two should be made consistent.","section":"Appendix C.3"},{"comment":"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.","section":"§7, Appendix F"},{"comment":"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.","section":"Appendix D"},{"comment":"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.","section":"§4, Eq. (1)"},{"comment":"There is a typo in the first sentence: 'the the Adam optimizer' should read 'the Adam optimizer'.","section":"Appendix D.3"}],"recommendation":"major_revision","confidential_remarks":"The main risk is the identifiability gap: the loss uses trajectory intervals as targets and lacks any coverage condition, so the learned metric is not guaranteed to equal MAD. This is fixable by adding theoretical conditions or by substantially softening the claims, so I recommend major revision rather than rejection. The benchmark suite and empirical comparison are otherwise useful and should be preserved."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my take. The paper's real contribution is the benchmark suite with known asymmetric MADs and the evidence that a simple ReLU quasimetric plus a scale-invariant loss beats QRL and Hilbert on it. MadDist itself is a modest variant of Steccanella & Jonsson (2022) — scale-invariant objective and quasimetric — but that variant matters empirically, and TDMadDist's bootstrapped target is genuinely new even if it underperforms. The math in the appendices is sound: the MAD characterization as the maximal quasimetric under one-step constraints is correct, and d_simple provably satisfies the triangle inequality.\n\nThe soft spots are real but not fatal. The biggest is the coverage issue: the loss only enforces upper bounds j-i on observed trajectory pairs, and without a coverage condition on the support graph, the learned metric can be systematically larger than true MAD on unseen shortcuts. The correlation and CV metrics are scale-invariant, so they won't catch a constant inflation. That said, the experiments are plausible and the planning results in Table 1 give some indirect evidence that the learned distances carry useful global signal. I don't read this as a circular method — the targets are data-derived upper bounds, and the TD bootstrap is standard.\n\nMore concrete complaints: the paper never compares to the direct predecessor (Eq. 2 of Steccanella & Jonsson), which is the natural baseline for MadDist; code is promised only upon acceptance; the continuous environments use a grid-based proxy as ground truth; and there is no train/test split described, so it's unclear whether the reported correlations are on training states. The abstract also overclaims: it says the 'proposed approach' outperforms baselines, but TDMadDist noticeably underperforms MadDist and often QRL.\n\nBottom line: it's a credible empirical methods paper with a useful benchmark, worth a serious referee. The fixes are straightforward: release code, add the missing baseline, report a train/test split, and soften the summary claim to name MadDist. The coverage concern should be flagged to the authors — a formal or even informal coverage condition would strengthen the central claim considerably.","headline":"Useful benchmark and a solid empirical case for a simple quasimetric, but the coverage gap and missing predecessor baseline keep it conditional.","tokens_in":21109,"tokens_out":2838,"would_cite":true,"duration_ms":30967,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["minimum action distance","state representation learning","quasimetric","self-supervised learning","goal-conditioned reinforcement learning","state-only trajectories","temporal distance","offline learning"],"falsifier":"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.","tokens_in":20065,"feed_emoji":"🧭","tokens_out":16839,"duration_ms":142056,"temperature":0.7,"pith_summary":"This paper claims that an environment's structure is captured by the minimum action distance (MAD), the fewest actions needed to reach one state from another, and that this quantity can be learned from nothing but sequences of observed states, with no reward signals and no recorded actions. The proposed MadDist algorithm embeds states so that distances between embedded pairs approximate the true MAD, using only the fact that two states appearing $j-i$ steps apart on a trajectory are at most $j-i$ actions apart, and it can represent asymmetric distances through a simple ReLU-based quasimetric. A temporal-difference variant, TDMadDist, propagates distance information with bootstrapped targets. If the claim holds, goal-conditioned reinforcement learning and reward shaping gain a dense, interpretable measure of progress that is computable offline from arbitrary-quality data and is insensitive to stochastic dynamics that leave the set of possible transitions unchanged.","feed_headline":"State-only trajectories reveal the true minimum action distance","feed_subtitle":"MadDist predicts step counts better than QRL and Hilbert baselines and wins goal-reaching planning.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Provides the original trajectory-upper-bound loss (equation 2) that MadDist extends by scaling the target and swapping the symmetric metric for a quasimetric.","marker":"Steccanella and Jonsson (2022)"},{"why":"Defines QRL, the quasimetric reinforcement-learning baseline whose IQE-based distance the paper compares against and outperforms.","marker":"Wang et al. (2023a)"},{"why":"Defines the Hilbert representation baseline, the symmetric offline MAD-approximation method used as the main comparison point.","marker":"Park et al. (2024b)"},{"why":"Supplies the all-pairs shortest-path algorithm used to compute ground-truth MAD in KeyDoorGridWorld, PointMaze, and OGBench mazes.","marker":"Floyd, 1962; Warshall, 1962"},{"why":"Introduces Interval Quasimetric Embeddings, the quasimetric construction used by QRL and evaluated as an alternative distance head in ablations.","marker":"Wang and Isola (2022)"},{"why":"Provides the OGBench PointMaze and AntMaze environments, including the navigate, stitch, and explore datasets used in the planning evaluation.","marker":"Park et al. (2024c)"},{"why":"Supplies the D4RL PointMaze layouts whose discretized grids yield the shortest-path ground-truth distances.","marker":"Fu et al. (2020)"},{"why":"Defines the CliffWalking environment, whose cliff-reset shortcut produces the strong distance asymmetry used to test quasimetric recovery.","marker":"Sutton and Barto (1998)"}],"fun_headline_variants":["State-only paths reveal hidden action distances","MAD metric from trajectories beats baselines","Learn action distances without rewards or actions","Distance metric from state trajectories powers planning","Minimum action distance learned from unlabeled data"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["State-only paths reveal hidden action distances","MAD metric from trajectories beats baselines","Learn action distances without rewards or actions","Distance metric from state trajectories powers planning","Minimum action distance learned from unlabeled data"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000164,"raw_usage":{"total_tokens":1298,"prompt_tokens":1045,"completion_tokens":253,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":661,"completion_tokens_details":{"reasoning_tokens":190}},"tokens_in":661,"tokens_out":253,"duration_ms":2837,"temperature":1.0,"reasoning_tokens":190,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T04:53:17.284769+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}