# Test-Time Graph Search for Goal-Conditioned Reinforcement Learning

arXiv: https://arxiv.org/abs/2510.07257 · HTML: https://mlsanity.com/paper/2510.07257/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Placed in Deep RL algorithms and representations, one of 15 directions in Deep reinforcement learning methods.
- Builds on 33 of its 39 references that are in the map.
- First posted on arXiv 8 Oct 2025.

## Placed in

- Deep reinforcement learning methods / [Deep RL algorithms and representations](https://mlsanity.com/deeprl/deep-rl-algorithms-and-representations/)

## Builds on (most cited first, 30 of 33)

- [Conservative Q-Learning for Offline Reinforcement Learning](https://mlsanity.com/paper/2006.04779/) (2020)
- [D4RL: Datasets for Deep Data-Driven Reinforcement Learning](https://mlsanity.com/paper/2004.07219/) (2020)
- [Offline Reinforcement Learning with Implicit Q-Learning](https://mlsanity.com/paper/2110.06169/) (2021)
- [Learning Latent Dynamics for Planning from Pixels](https://mlsanity.com/paper/1811.04551/) (2018)
- [Hindsight Experience Replay](https://mlsanity.com/paper/1707.01495/) (2017)
- [Planning with Diffusion for Flexible Behavior Synthesis](https://mlsanity.com/paper/2205.09991/) (2022)
- [Deep Reinforcement Learning in a Handful of Trials using Probabilistic Dynamics Models](https://mlsanity.com/paper/1805.12114/) (2018)
- [Offline Reinforcement Learning as One Big Sequence Modeling Problem](https://mlsanity.com/paper/2106.02039/) (2021)
- [Is Conditional Generative Modeling all you need for Decision-Making?](https://mlsanity.com/paper/2211.15657/) (2022)
- [Temporal Difference Learning for Model Predictive Control](https://mlsanity.com/paper/2203.04955/) (2022)
- [Integrated Task and Motion Planning](https://mlsanity.com/paper/2010.01083/) (2020)
- [Contrastive Learning as Goal-Conditioned Reinforcement Learning](https://mlsanity.com/paper/2206.07568/) (2022)
- [OGBench: Benchmarking Offline Goal-Conditioned RL](https://mlsanity.com/paper/2410.20092/) (2024)
- [Semi-parametric Topological Memory for Navigation](https://mlsanity.com/paper/1803.00653/) (2018)
- [Search on the Replay Buffer: Bridging Planning and Reinforcement Learning](https://mlsanity.com/paper/1906.05253/) (2019)
- [HIQL: Offline Goal-Conditioned RL with Latent States as Actions](https://mlsanity.com/paper/2307.11949/) (2023)
- [Optimal Goal-Reaching Reinforcement Learning via Quasimetric Learning](https://mlsanity.com/paper/2304.01203/) (2023)
- [Learning from Reward-Free Offline Data: A Case for Planning with Latent Dynamics Models](https://mlsanity.com/paper/2502.14819/) (2025)
- [World Model as a Graph: Learning Latent Landmarks for Planning](https://mlsanity.com/paper/2011.12491/) (2020)
- [Inference-time Scaling of Diffusion Models through Classical Search](https://mlsanity.com/paper/2505.23614/) (2025)
- [Generative Trajectory Stitching through Diffusion Composition](https://mlsanity.com/paper/2503.05153/) (2025)
- [Sparse Graphical Memory for Robust Planning](https://mlsanity.com/paper/2003.06417/) (2020)
- [Stabilizing Contrastive RL: Techniques for Robotic Goal Reaching from Offline Data](https://mlsanity.com/paper/2306.03346/) (2023)
- [Option-aware Temporally Abstracted Value for Offline Goal-Conditioned Reinforcement Learning](https://mlsanity.com/paper/2505.12737/) (2025)
- [Physics-informed Value Learner for Offline Goal-Conditioned Reinforcement Learning](https://mlsanity.com/paper/2509.06782/) (2025)
- [Offline Imitation Learning Through Graph Search and Retrieval](https://mlsanity.com/paper/2407.15403/) (2024)
- [State-Covering Trajectory Stitching for Diffusion Planners](https://mlsanity.com/paper/2506.00895/) (2025)
- [Goal-Space Planning with Subgoal Models](https://mlsanity.com/paper/2206.02902/) (2022)
- [Value Memory Graph: A Graph-Structured World Model for Offline Reinforcement Learning](https://mlsanity.com/paper/2206.04384/) (2022)
- [Graph-Assisted Stitching for Offline Hierarchical Reinforcement Learning](https://mlsanity.com/paper/2506.07744/) (2025)

## Built on by (most cited first, 8 of 8)

- [Diffusion Subgoal Planning for Long-Horizon Offline Goal-Conditioned Reinforcement Learning](https://mlsanity.com/paper/2609.34575/) (2026)
- [Refining Compositional Diffusion for Reliable Long-Horizon Planning](https://mlsanity.com/paper/2605.03075/) (2026)
- [NFTR: From Provable Mode-Averaging to Geodesic Subgoal Selection in Offline Goal-Conditioned RL](https://mlsanity.com/paper/2607.07855/) (2026)
- [Beyond Success Rates: Trainability and Extractability for Offline GCRL](https://mlsanity.com/paper/2602.05459/) (2026)
- [GraSP-STL: A Graph-Based Framework for Zero-Shot Signal Temporal Logic Planning via Offline Goal-Conditioned Reinforcement Learning](https://mlsanity.com/paper/2603.29533/) (2026)
- [QHyer: Q-conditioned Hybrid Attention-mamba Transformer for Offline Goal-conditioned RL](https://mlsanity.com/paper/2605.01862/) (2026)
- [Metro-WM: Long-Horizon Latent Planning with Realisable Sub-Goals](https://mlsanity.com/paper/2609.31868/) (2026)
- [Learning Multiple Timescales for Goal-Conditioned Reinforcement Learning](https://mlsanity.com/paper/2610.00849/) (2026)

## Abstract (arXiv)

Offline goal-conditioned reinforcement learning (GCRL) often struggles with long-horizon tasks, where errors in value estimation accumulate and produce unreliable policies. It is typically assumed that effective long-term planning is infeasible without specialized training. In contrast, our work demonstrates that existing GCRL policies can complete long-horizon tasks when combined with a lightweight, training-free planning wrapper. We find that standard goal-conditioned value functions encode locally consistent geometric structure sufficient for planning. Our approach, Test-Time Graph Search (TTGS), constructs a graph over the offline dataset and employs an adaptive subgoal selection strategy. To address unreliable value estimates during shortest-path search, we propose a novel mechanism that softly penalizes long-distance transitions. Our method incurs negligible computational overhead and requires no additional supervision or parameter updates. On the OGBench benchmark, TTGS significantly boosts success rates across multiple base learners and tasks, with primary gains on challenging long-horizon locomotion tasks where some success rates are improved from near-zero to over 90%, often matching or outperforming methods that require complex auxiliary training. Code and videos can be found at https://ktolnos.github.io/ttgs.