TTGS in Action
We illustrate the effect of TTGS on a long-horizon humanoid locomotion task. The frozen HIQL policy struggles to reach the distant goal in one shot, while TTGS decomposes the task into a sequence of short, reliable hops that the same policy can follow to the goal.
HIQL (baseline). The frozen policy fails to reach the distant goal, getting stuck on this long-horizon humanoid locomotion task.
TTGS + HIQL. The same frozen policy now reaches the goal. We show the dataset samples, the selected subgoals, and the guiding path that steers the agent.
Abstract
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.
Motivation and Method
We visualize the core challenge that GCRL agents face. In long, complex tasks like maze navigation, agents that attempt to reach far-away goals can get stuck or run off course. However, for shorter horizons, they tend to be reliable.
From this observation, we derive the simple key idea behind TTGS: rather than asking a policy to solve a long-horizon task in one shot, we decompose it into short, reliable hops. We do so by equipping test-time planning with a distance signal over states, selecting a compact set of representative states from an offline dataset, and connecting them into a graph whose edges reflect predicted step costs. At test time, we plan in this graph by computing a shortest path between the start and the goal, then feed the policy a small number of intermediate subgoals along this path. The agent queries all points along the shortest path that are within a certain threshold from the current state, and picks the closest to the goal.
(left) HIQL policy fails to reach a distant goal on antmaze-giant-stitch-v0, with multiple attempts failing to exit the starting area and two attempts running out of time due to inefficient path. (right) TTGS finds a guiding path using dataset observations. On each step it selects a subgoal which is within a predefined radius from the agent. We mark all data points on the guiding path in gray, and the actual path traversed by the agent in blue. (bottom) Different agents' policy performance decreases as steps required to reach the goal increase. By providing a policy with close subgoals, TTGS improves reliability and efficiency of reaching the goal.
Using the distance predictor, which for value-based base agents can be derived by mapping predicted values into distance, we build a graph with vertices sampled from the states of pretraining dataset and weights obtained by clipping the distances and applying a superlinear penalty to long connections. This graph is goal-agnostic, which means it can be reused for different goals an agent might want to achieve in the environment.
To find the path to a given goal, the agent first precomputes the shortest path from the vertex closest to the starting state to the vertex closest to the goal state. After that, the agent selects subgoals from this guiding path which are within distance T from current step, or next after the closest vertex on the path if all other potential subgoals are too far.
Results
We evaluate TTGS on OGBench using five strong offline GCRL base learners: QRL, GCIQL, and HIQL from the benchmark, together with SAW and < class="has-text-primary" href="https://arxiv.org/abs/2505.12737">OTA to broaden the evaluation. For each dataset we compare the success rate of the frozen base policy with and without TTGS. TTGS uses distances derived from the base agent’s value function, so it relies only on information available at test time. TTGS generally improves or maintains success across all evaluated environments, with the largest gains on giant layouts where one-shot execution is difficult. On pointmaze-giant-stitch-v0, TTGS raises HIQL from 0.0% to 80.9% and GCIQL from 0.0% to 98.0%. On humanoidmaze-giant-stitch-v0, HIQL is improved from 4.4% to 78.1%. These cases highlight how sequences of short, reliable hops help frozen policies traverse large mazes that require stitching behaviors from disparate parts of the dataset. Notably, TTGS boosts even HIQL, SAW, and OTA, which already include a learned high-level controller, suggesting that explicit planning can provide more reliable subgoals than a purely learned subgoal policy in long-horizon settings. We further observe improvements on several pixel-based tasks, indicating that value-derived distances can offer a strong planning signal even when domain-specific metrics are difficult to define.
BibTeX
@inproceedings{opryshko2026testtimegraphsearchgoalconditioned,
title={Test-Time Graph Search for Goal-Conditioned Reinforcement Learning},
author={Evgenii Opryshko and Junwei Quan and Claas Voelcker and Yilun Du and Igor Gilitschenski},
booktitle={Proceedings of the 43rd International Conference on Machine Learning (ICML)},
year={2026},
series={Proceedings of Machine Learning Research},
volume={306},
publisher={PMLR},
url={https://arxiv.org/abs/2510.07257},
}