Escaping Path Mirages in Offline Goal-Conditioned Reinforcement Learning

AI summary

Overview

Research area: Offline goal-conditioned reinforcement learning (GCRL), with a focus on graph-based planning and stochasticity-aware value learning. Technical level: Advanced — the paper assumes familiarity with Markov decision processes, expectile regression (IQL), temporal-distance learning, and graph search. Scope: A single-paper summary of Branch-aware Graph Planning (BGP), a method that treats high-uncertainty branching points as graph landmarks and builds goal-conditioned edges to avoid deceptively promising trajectories ("path mirages") in offline, stochastic, long-horizon goal-reaching tasks, evaluated on OGBench.

What This Paper Is About

In offline goal-conditioned RL, an agent must learn to reach user-specified goals using only a fixed dataset, without further environment interaction. In stochastic, long-horizon environments, a single local decision can lead to several divergent futures, and rare lucky outcomes in the data make some trajectories look reliably goal-reaching when they are not. The authors call this failure mode path mirage — agents overcommit to these misleading paths and propagate overly optimistic value estimates through unreliable branches — and the paper's goal is to make planning explicitly aware of where and how trajectories branch.

Key Contributions

1. Formalizes "path mirage" as a distinct failure mode in offline GCRL: spurious success in offline data caused by stochastic branching, which is amplified over long horizons as local branching errors compound.
2. Branch-aware graph construction: identifies stochastic landmarks by scoring each state with a multi-step predictive uncertainty (a discounted sum of entropies from an autoregressive Transformer with Gaussian outputs), selecting the top-α percentile of high-uncertainty states, clustering them with K-means++, and defining each landmark as the dataset state closest to a cluster center.
3. Goal-conditioned edge design: instead of scoring a transition locally, edge cost e_g averages over all downstream branches reachable after visiting a candidate node, penalizing or effectively removing transitions that can lead into dead zones where the goal is unreachable.
4. Two-phase planning plus segmented learning: a pre-graph composes short-horizon value predictions into a reachability-based distance (replacing a single long-horizon value estimate), the branch-aware graph is used for Dijkstra waypoint planning, and value/policy training is restricted to windows of M consecutive trajectory segments split at cluster-assignment boundaries.

Main Findings

• Strong aggregate gains on OGBench: mean success rates of 91% on antmaze, 98% on pointmaze, and 86% on visual-antmaze, versus 70%, 20%, and 78% for the strongest prior graph-based baseline GAS, and 43%, 28%, and 44% for the primary baseline HIQL. Results are averaged over 5 seeds.
• Largest advantage in the teleport environment, where blackholes teleport the agent uniformly at random to one of several whiteholes: BGP reaches 90 / 92 / 93% on antmaze teleport navigate/stitch/explore, whereas the paper states that even methods explicitly targeting these challenges (such as TMD) achieve only 20–50% success.
• Not the top score in every individual row: on antmaze large-navigate BGP scores 90 ± 1 versus GAS at 93 ± 1 and HIQL at 91 ± 2; on visual-antmaze large-navigate BGP scores 80 ± 4 versus GAS at 87 ± 1. The headline claim is about consistency across the suite, not dominance in every cell.
• Edge design is the dominant factor: swapping in the prior edge e_p = -V_θ drops the average on antmaze-teleport navigate/stitch from 91.2 ± 1.3 to 44.3 ± 3.6, and using a direct value-based distance without the pre-graph drops it to 46.8 ± 5.2.
• Other ablations degrade but less severely: one-step uncertainty estimation 86.7 ± 1.3, no segmented learning 84.4 ± 6.2, random landmarks 69.4 ± 4.2 — confirming that uncertainty-guided landmark placement matters.
• Path-miracle evidence in planning visualizations: with the prior edge cost, all locally reachable transitions are treated as valid and the planner favors short teleport routes that fail, yielding success rates around 33%; the goal-conditioned edge disconnects dead-zone branches and selects stable paths.
• Robustness to increasing stochasticity: sweeping the number of blackholes B ∈ {0, …, 4} in antmaze-teleport, HIQL degrades sharply as B grows, while both BGP variants stay high; on stitch at B = 4, BGP reaches approximately 90% success and beats BGP without segmented learning by about 10 percentage points.
• Low sensitivity to the number of clusters N in [50, 100] across sweeps of N ∈ {50, 100, 150, 200}; the percentile threshold α is more sensitive, with smaller values preferable where branching is concentrated (sweep over α ∈ {1, 10, 20, 50}).
• Additional environments reported: the appendix reports results on humanoidmaze and manipulation tasks, hyperparameter analyses across more layouts, a budget-aware hyperparameter search following Jackson et al., and a computational cost analysis.

Methodology in Plain English

The starting point is a standard graph-based planner: pick a set of landmark states, connect them into a graph, and use shortest-path search to produce a sequence of waypoints the agent visits on the way to a goal.

Step 1 — Find the branching points. The authors train a small autoregressive Transformer to predict the next action and next state given the current state and its own previous predictions. At each dataset state they roll this predictor forward for n = 5 steps and add up the entropy of its predictions, discounted over time. High entropy means "the future from here is genuinely ambiguous" — exactly the branching regions that mislead planning. Landmarks are drawn from the top α percentile of these scores, then clustered, so landmarks crowd into branching regions and stay sparse where the future is predictable. The authors note landmarks are deliberately not required to be uniformly distributed.

Step 2 — Ask "where can this actually take me?" For a candidate transition from landmark v_i to landmark v_j, ordinary methods score the move by how close v_j looks. BGP instead looks at the set of all clusters reachable from v_j by any trajectory in the data, and computes how much distance-to-goal changes across that entire branch set, taking the positive part. If any branch makes things much worse or can never reach the goal, the edge gets a large cost or effectively disappears. The key consequence: teleport-like transitions are kept when the goal genuinely requires them and avoided when they are gambles.

Step 3 — Measure distance reliably. Rather than trusting one long-horizon value estimate, BGP builds a pre-graph whose edge weights are short-horizon value predictions between neighboring landmarks, and defines distance as the shortest-path sum of those local predictions via Dijkstra. This "compose short, trustworthy hops into a long distance" trick is what the goal-conditioned edge costs are computed with.

Step 4 — Train on short windows. Each offline trajectory is cut wherever the cluster assignment changes, and M consecutive segments are concatenated into a local training window. Both the sampled transitions and their goal targets come from the same window, which caps how far value information propagates and stops errors from leaking across stochastic boundaries. The underlying policy learner is the IQL-based HIQL.

The final agent runs Dijkstra on the branch-aware graph to get waypoints, then executes the policy to hit them in sequence.

Why This Matters

Impact on research. The paper reframes uncertainty in offline GCRL from something to penalize into something to structure with — entropy becomes a signal for where to place graph nodes, not just a penalty term. It also offers a concrete diagnosis (path mirage) for why offline agents that look good on average can fail persistently on hard goals, and shows that edge-cost design, not landmark placement, is the highest-leverage design choice.

Real-world applications (implied by the setting, not itemized in the paper):

• Legged and mobile robot navigation through terrain where the same footstep can lead to stable ground or a fall.
• Warehouse and logistics routing where congestion or hardware faults produce stochastic outcomes.
• Industrial process control and manipulation, where a "lucky" recorded recovery can make an unsafe policy look successful.
• Any deployment of learned control trained on logged data where further trial-and-error is expensive or unsafe.

Industry relevance. Offline RL is attractive precisely where data collection is costly or dangerous — the paper's framing of offline learning from static, unlabeled datasets without environment interaction maps directly onto log-based training pipelines in robotics and operations. The authors also report a cost analysis and a budget-aware hyperparameter search, which speaks to practical deployment concerns, though the actual overhead figures are in the appendix and not included in the main text.

Future Directions

1. Reducing hyperparameter burden: BGP adds a percentile threshold α and a cluster count N; the paper's ablation shows α can be highly sensitive in concentrated-branching environments, so adaptive or learned selection of these values is an open problem.
2. Better state representations for high-dimensional tasks: the authors state BGP remains effective on manipulation but that more sophisticated representations may further improve performance, and explicitly leave this to future work.
3. Quantifying and shrinking planning overhead: graph construction and Dijkstra planning add cost on top of training; the paper argues the overhead is modest but treats tighter integration as an open engineering question.
4. Extending branch-awareness beyond teleport-style failures: the paper notes that in large and giant layouts no explicit dead zones exist and planning reduces to selecting among many alternatives — a broader characterization of which stochastic structures require the full edge machinery is not yet established.

Target Audience

Researchers and graduate students working on offline RL, goal-conditioned RL, or hierarchical and graph-based planning; practitioners deploying learned policies from logged data in robotics or control where stochasticity and long horizons are unavoidable; and readers already comfortable with IQL/HIQL-style value learning who want a concrete, well-ablated treatment of how to make graph-based planning reliability-aware.

Authors’ abstract

Offline goal-conditioned reinforcement learning remains challenging in stochastic long-horizon settings, where compounding value estimation errors hinder reliable goal reaching. While prior methods have sought to address this challenge through various approaches, a key challenge remains path mirage, where agents overcommit to spuriously successful trajectories in offline datasets induced by stochasticity, often leading to failure on difficult tasks. To address this issue, we propose Branch-aware Graph Planning (BGP), which captures stochastic branching structures by identifying high-variability points as graph nodes and designing goal-conditioned edges with segmented learning to avoid unreliable branches and reduce unnecessary stochasticity along paths. As a result, BGP enables reliable goal reaching even in highly stochastic long-horizon environments, and experiments on diverse OGBench tasks show that it substantially outperforms prior state-of-the-art offline goal-conditioned RL methods. Our implementation is available at https://umlic.github.io/papers/BGP/.