Abstract

Planning with a learned model remains a key challenge in model-based reinforcement learning due to the compounding error problem. In decision-time planning, state representations are critical as they must support local cost computation while preserving long-horizon temporal structure. In this paper, we show that the Laplacian representation provides an effective latent space for planning by capturing state-space distances at multiple time scales. The Laplacian representation preserves meaningful distances and naturally decomposes long-horizon problems into subgoals, thus mitigate the compounding errors that arise over long prediction horizons. Building on these properties, we introduce ALPS, a hierarchical planning algorithm, and demonstrate that it outperforms commonly used baselines on a selection of offline goal-conditioned RL tasks from OGBench, a benchmark previously dominated by model-free methods.

Method

Overview of ALPS: In pre-training, ALPS (1) learns the Laplacian representation using the Augmented Lagrangian Laplacian Objective (ALLO), (2) learns a one-step forward model on top of the original state space, (3) learns the behavior prior π_prior using the scaled Laplacian representation, and (4) clusters the dataset using k-means in the scaled Laplacian space to generate the cluster graph. In planning, (5) ALPS takes the current state from the environment and uses the high-level planner to determine the next subgoal, then determines the next action towards this subgoal using the low-level planner.

Properties of Laplacian representation: (Left) The scaled Laplacian representation (ψ) is isometric to the commute-time distance in the data graph, so distances in ψ-space reflect how hard it is to navigate between states. (Right) k-means clustering in ψ-space groups states into topologically connected regions used as subgoal waypoints.

Videos

Results

Success rate (%) on each of the locomotion and manipulation tasks from OGBench considered. The results are averaged over 8 seeds (4 seeds for pixel-based tasks), and we report the standard deviation after the ± sign. ALPS outperforms the model-free GCRL algorithms with p < 0.001 using a Holm-Bonferroni-corrected two-sided Wilcoxon signed-rank test. Values in bold denote the largest mean in each row as a visual aid.

BibTeX

@inproceedings{shehmar2026alps,
  title     = {Laplacian Representations for Decision-Time Planning},
  author    = {Shehmar, Dikshant and Schlegel, Matthew and Taylor, Matthew E.
               and Machado, Marlos C.},
  booktitle = {International Conference on Machine Learning(ICML)},
  year      = {2026},
}