# Learning to Search and Searching to Learn for Generalization in Planning

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Deep RL algorithms and representations, one of 15 directions in Deep reinforcement learning methods.
- Builds on 26 of its 53 references that are in the map.
- First posted on arXiv 25 May 2026.

## 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, 26 of 26)

- [Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model](https://mlsanity.com/paper/1911.08265/) (2019)
- [Hindsight Experience Replay](https://mlsanity.com/paper/1707.01495/) (2017)
- [Exploration by Random Network Distillation](https://mlsanity.com/paper/1810.12894/) (2018)
- [A Survey of Zero-shot Generalisation in Deep Reinforcement Learning](https://mlsanity.com/paper/2111.09794/) (2021)
- [RIDE: Rewarding Impact-Driven Exploration for Procedurally-Generated Environments](https://mlsanity.com/paper/2002.12292/) (2020)
- [The LAMA Planner: Guiding Cost-Based Anytime Planning with Landmarks](https://mlsanity.com/paper/1401.3839/) (2014)
- [Exploration via Elliptical Episodic Bonuses](https://mlsanity.com/paper/2210.05805/) (2022)
- [ASNets: Deep Learning for Generalised Planning](https://mlsanity.com/paper/1908.01362/) (2019)
- [Learning General Optimal Policies with Graph Neural Networks: Expressive Power, Transparency, and Limits](https://mlsanity.com/paper/2109.10129/) (2021)
- [Generalized Planning With Deep Reinforcement Learning](https://mlsanity.com/paper/2005.02305/) (2020)
- [Learning Domain-Independent Heuristics for Grounded and Lifted Planning](https://mlsanity.com/paper/2312.11143/) (2023)
- [Policy-Guided Heuristic Search with Guarantees](https://mlsanity.com/paper/2103.11505/) (2021)
- [Structure in Deep Reinforcement Learning: A Survey and Open Problems](https://mlsanity.com/paper/2306.16021/) (2023)
- [Learning Lifted STRIPS Models from Action Traces Alone: A Simple, General, and Scalable Solution](https://mlsanity.com/paper/2411.14995/) (2024)
- [Relational Abstractions for Generalized Reinforcement Learning on Symbolic Problems](https://mlsanity.com/paper/2204.12665/) (2022)
- [Symmetries and Expressive Requirements for Learning General Policies](https://mlsanity.com/paper/2409.15892/) (2024)
- [Learning More Expressive General Policies for Classical Planning Domains](https://mlsanity.com/paper/2403.11734/) (2024)
- [Graph Learning for Numeric Planning](https://mlsanity.com/paper/2410.24080/) (2024)
- [First-Order Representation Languages for Goal-Conditioned RL](https://mlsanity.com/paper/2512.19355/) (2025)
- [PushWorld: A benchmark for manipulation planning with tools and movable obstacles](https://mlsanity.com/paper/2301.10289/) (2023)
- [Beyond Single-Step Updates: Reinforcement Learning of Heuristics with Limited-Horizon Search](https://mlsanity.com/paper/2511.10264/) (2025)
- [Learning General Policies with Policy Gradient Methods](https://mlsanity.com/paper/2512.19366/) (2025)
- [Consolidating LAMA with Best-First Width Search](https://mlsanity.com/paper/2404.17648/) (2024)
- [Sketch Decompositions for Classical Planning via Deep Reinforcement Learning](https://mlsanity.com/paper/2412.08574/) (2024)
- [Learning Efficiency Meets Symmetry Breaking](https://mlsanity.com/paper/2504.19738/) (2025)
- [Weisfeiler-Leman Features for Planning: A 1,000,000 Sample Size Hyperparameter Study](https://mlsanity.com/paper/2508.18515/) (2025)

## Abstract (arXiv)

Combinatorial generalization remains a central challenge in Deep Reinforcement Learning (DRL). Classical planning provides a simple yet challenging setting to study this problem through explicit relational descriptions, without requiring learning from perception. In sparse-reward domains, standard RL exploration via real-time search is ineffective, and learning-based planning methods often rely on expert demonstrations, hindsight relabeling, or random walks from the goal state. In contrast, planners rely on best-first search methods such as A^star to solve problems from scratch. We propose a self-improving WA^star learning framework in combination with a value heuristic represented by a Relational Graph Neural Network: the heuristic guides search, and the resulting search data updates the heuristic via Q-learning. This loop yields heuristics that can function as general policies and solve new instances even without search, where DRL otherwise fails, as we show on puzzles such as Sokoban, PushWorld, The Witness, and the 2023 International Planning Competition benchmarks. Notably, we demonstrate strong zero-shot generalization: For example, heuristics trained on Blocksworld instances with fewer than 30 blocks successfully solve instances with 488 blocks without search.