Reach-Pattern Anchors: Linear-Time State Graphs for Reward-Free Goal Reaching

Robots learning from logged data have to reach goals without anyone writing a reward function. One strong way to avoid hand-written rewards is to build a graph over the states in the dataset and reward the agent for shrinking its shortest-path distance to the goal. Two things break this at scale. First, building the graph costs time quadratic in the number of states. Second, and less often noticed, the graph gets shortcut edges: two states that look alike but are far apart in time get linked, for example the two sides of a wall, or a kitchen scene with a cabinet latched versus unlatched. A single shortcut edge can collapse the distance between opposite ends of a maze, and the shaped reward then points the agent into walls.

We propose to build the graph from anchors, a few hundred representative states, where two states share an anchor only if they lead to and come from the same places in the data, not merely if they look alike. The graph-learning literature has shown that when direct links join dissimilar nodes, the pattern of shared neighbors is still a reliable similarity signal. We carry that observation into sequential decision-making and compute it in linear time. The same construction gives multi-sensor fusion almost for free: every sensor stream shares the dataset's time index, so camera anchors and joint-angle anchors can be matched through the timesteps they cover, and no explicit graph-matching step is needed.

Core Claim

In graph-based self-supervised reward shaping, the harm from shortcut edges is at least as large as the harm from cost. The standard remedy for cost, clustering states into anchors by feature similarity, makes shortcut edges worse, because it merges states that look alike across barriers. We define anchors by reach-pattern similarity instead: two states are similar if their discounted visits to anchors over the next and previous $k$ steps agree. This removes shortcuts while keeping time and memory linear in dataset size. It also yields a view-agnostic state abstraction that works on raw pixels plus proprioception, with no hand-designed coordinates.

Here is the terminology, stated once. Homophily is the assumption that linked nodes are alike, and heterophily is its violation. In our setting the relevant "label" of a state is its position in time and reachability, so a shortcut edge is a heterophilous edge. An anchor graph is a bipartite graph linking $n$ samples to $m \ll n$ anchors. Such a graph acts as a low-rank stand-in for the full $n \times n$ graph.

Where This Sits

Three bodies of work supply the pieces, and each stops short in a specific way.

The reward-shaping mechanism comes from Learning Goal-Conditioned Policies Offline with Self-Supervised Reward Shaping. That paper trains a reachability network, builds a directed graph over offline states, and shapes rewards from graph shortest paths plus a local reachability term. It reports that directedness alone gave an 11% success gain on RoboYoga Walker. We keep its reward form and its directedness. We change how nodes are formed and linked, and we remove its quadratic pairwise reachability step.

The heterophily diagnosis motivates our similarity choice. Complete the Missing Half and Two Sides of the Same Coin show that averaging over neighbors is a low-pass filter that erases node identity when neighbors are dissimilar. SMHGC shows that on the 91%-heterophilous Texas graph, neighbor-pattern similarity $AA^\top$ is far more homophilous than the raw adjacency $A$. SMHGC reaches 71.3% clustering accuracy there versus 54.3% for DuaLGR, but it pays $O(n^2)$ to do so. We use the transition-graph analogue of $AA^\top$, computed against anchors rather than against all states.

Our reach pattern is a truncated successor representation projected onto anchors. The successor representation records how often a state is expected to be followed by each other state. This connects us to Eigenoption Discovery through the Deep Successor Representation, which takes eigenvectors of a learned successor representation to find bottleneck options, and to Reward-Predictive Clustering, which splits state clusters when their successor features differ. Neither uses these patterns to build a linear-size graph for goal-distance shaping, and neither handles multiple sensor views. Reward-predictive clustering also needs a reward signal to split on, and our setting has none. Reward-predictive clustering is the closest method in spirit, and we treat it as a baseline rather than wave it away.

The linear-time machinery comes from anchor multi-view clustering. Align then Fusion (FMVACC) shows that anchors learned separately per view do not correspond, and fixes this with a quadratic assignment solver. Alignment lifted LMVSC from 66.78% to 82.97% accuracy on UCI-Digit. Hierarchical Anchor Graph Learning and Centerless Multi-View K-means establish the $O(n)$ complexity. All of these assume symmetric, static feature affinities. We add direction, derived from time order. We also replace assignment-based alignment with alignment through shared timesteps, which is only possible because our samples come from trajectories.

Method

We start from an offline dataset of trajectories, each observed through $V$ views such as a 64×64 camera image and joint states. We initialize $m$ anchors per view by k-means on each view's encoder features. The encoders are pretrained with a next-frame or temporal-contrastive loss, so we use no hand-crafted coordinates.

Let $a(s)$ be the current anchor assignment of state $s$, and let $s_{i+t}$ be the state $t$ steps after $s_i$ in its own trajectory. The forward reach pattern of state $i$ is

$$F_{ij} = \sum_{t=1}^{k} \gamma^{t}\,\mathbb{1}[a(s_{i+t}) = j],$$

where $\gamma \in (0,1)$ is a discount and $k$ a horizon. The backward pattern $G_{ij}$ is defined the same way over the previous $k$ steps. Both are $n \times m$ sparse matrices built in $O(nk)$ time.

We then reassign each state to the anchor whose mean pattern $[\bar F_j, \bar G_j]$ is closest to $[F_i, G_i]$. Blending this with a small feature term keeps anchors visually coherent. We recompute the patterns and iterate, which is a k-means in reach-pattern space that costs $O(nmk)$ per round. The implied state-to-state similarity $FF^\top + GG^\top$ is never formed. It plays the role that $AA^\top$ plays in SMHGC.

For multiple views, we build each view's anchor-by-timestep incidence matrix. Two anchors from different views are matched by the overlap of the timesteps they own, and matched anchors are merged into a consensus anchor. This is a linear-time substitute for FMVACC's assignment problem.

The final directed anchor graph has an edge $j \to j'$ weighted by observed one-step transitions between anchors. Shortest paths on this $m$-node graph are cheap. The shaped reward for reaching goal $g$ from $s$ is minus the anchor-graph distance $d(a(s), a(g))$, plus a local within-anchor temporal-distance term, following Mezghani et al. We train the policy offline with IQL, which never queries actions absent from the data.

We add one diagnostic, reach homophily: the fraction of graph edges whose endpoints are within $h$ steps of each other under the true environment geodesic. The true geodesic is computable exactly in AntMaze and Maze2D from the maze layout. This measures shortcut edges directly, independently of downstream returns.

Research Program

The work has three stages.

The first stage is diagnostic, and it tests the premise. On D4RL Maze2D and AntMaze, we compare three graphs: feature-kNN anchors, Mezghani-style reachability graphs on subsampled nodes, and reach-pattern anchors. For each we measure reach homophily and the rank correlation between graph distance and true geodesic, as $m$ and $k$ vary. If feature anchors do not produce materially more shortcut edges than reach-pattern anchors, the core claim is wrong and we stop there.

The second stage asks whether shortcut removal turns into control. We run goal-conditioned offline training on AntMaze, on Mezghani et al.'s UMaze, RoboYoga Walker, and Pusher, and on pixel Franka Kitchen, with goals specified as observations and no environment reward used anywhere.

The third stage covers scaling and views. We measure wall-clock time and memory against dataset size up to the full AntMaze datasets, both with pixels only and with pixels plus proprioception. This tests whether timestep-based alignment matches or beats assignment-based alignment.

Baselines

The naive reference is IQL trained on a sparse goal-reached indicator with hindsight goal relabeling. This is what one gets with no shaping and no graph, and if it matches us, graph shaping is unnecessary here.

The most direct competitor is the self-supervised shaping method of Mezghani et al., run in two forms. The first is at the node budget its quadratic cost allows. The second is with random or k-means subsampling to the same $m$ nodes we use, so both methods see identical data, encoders, graph size, and IQL settings, with equal tuning grids over graph hyperparameters. The file gives no absolute success rate for it, only the relative +11% for directed over undirected graphs on RoboYoga Walker. Beating it means higher goal-reaching success at equal $m$ on the long-horizon mazes, together with higher reach homophily.

The second strong competitor is Reward-Predictive Clustering. We adapt it to be reward-free by splitting on successor-feature discrepancy only. It tests whether iterative partition refinement already achieves what reach-pattern anchors do.

For a reference point that uses the true environment reward, IQL reports a normalized score of 42.2 on antmaze-large-diverse versus 1.0 for CQL (IQL). MOTO reports 90.5% success on pixel Franka Kitchen Partial, versus 13.5% for DreamerV2. We do not expect to beat reward-using methods. Approaching them without reward on AntMaze-large would be the strong result.

The key ablation swaps reach-pattern similarity for feature similarity inside our own pipeline, keeping everything else fixed. This isolates the heterophily-aware ingredient. A second ablation replaces timestep alignment with FMVACC's assignment-based alignment, and a third drops the backward pattern $G$ to test whether directedness matters.

Why not just…?

Why not just subsample nodes and keep the reachability network? This is the real threat. A reachability network trained on temporal distance already rejects some shortcut edges, and subsampling solves cost. Our bet is that the network is least reliable exactly on look-alike states across barriers, because it judges pairs from appearance. The head-to-head at equal $m$, scored by reach homophily and success, settles this. If subsampled reachability graphs match ours, we will report that the linear-time gain is purely engineering.

Why not just add a high-pass filter to a feature graph, as filterbank networks do? FB-GNN keeps node identity during message passing, but shortest-path shaping does no message passing. A shortcut edge corrupts distances whether or not embeddings are sharpened. Filterbank coefficients also need per-dataset calibration. The feature-anchor ablation, given a learned high-pass correction, tests this directly.

Why not skip graphs and learn a temporal-distance embedding end to end? Contrastive goal-conditioned methods, analyzed in Demystifying The Mechanisms Behind Emergent Exploration in Goal-Conditioned RL, can learn goal distances without explicit graphs. The file reports no benchmark numbers for them, so we will include a contrastive embedding baseline under the same data and compute. Graphs earn their place only if explicit shortest paths stitch long routes better on AntMaze-large, which is the regime where stitching matters.

Why not concatenate the views and cluster once? Concatenation lets the dominant pixel view overwrite proprioception, the leakage effect reported in See More, Detect Less?. The concatenation ablation on pixel-plus-joint Franka Kitchen measures whether per-view anchors with timestep alignment actually help.

Decisive Checks

The proposal succeeds if three things hold. First, reach-pattern anchors show clearly higher reach homophily than feature anchors on AntMaze. Second, reward-free IQL with our shaping beats both subsampled reachability shaping and sparse-reward IQL on antmaze-large and RoboYoga Walker at equal graph size. Third, runtime grows linearly with dataset size where the full reachability graph does not.

It fails if the feature-to-reach-pattern swap changes reach homophily without changing success. That outcome would mean shortcut edges are not what limits graph shaping, and the heterophily framing would be refuted rather than rescued.