# Optimize Planning Heuristics to Rank, not to Estimate Cost-to-Goal

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Placed in Imitation learning methods, one of 13 directions in Offline RL and imitation learning from data.
- Builds on 15 of its 61 references that are in the map.
- First posted on arXiv 30 Oct 2023.

## Placed in

- Offline RL and imitation learning from data / [Imitation learning methods](https://mlsanity.com/offlinerl/imitation-learning-methods/)

## Builds on (most cited first, 15 of 15)

- [AdaBelief Optimizer: Adapting Stepsizes by the Belief in Observed Gradients](https://mlsanity.com/paper/2010.07468/) (2020)
- [Thinking Fast and Slow with Deep Learning and Tree Search](https://mlsanity.com/paper/1705.08439/) (2017)
- [Path Planning using Neural A* Search](https://mlsanity.com/paper/2009.07476/) (2020)
- [Learning Domain-Independent Planning Heuristics with Hypergraph Networks](https://mlsanity.com/paper/1911.13101/) (2019)
- [ASNets: Deep Learning for Generalised Planning](https://mlsanity.com/paper/1908.01362/) (2019)
- [Learning Generalized Reactive Policies using Deep Neural Networks](https://mlsanity.com/paper/1708.07280/) (2017)
- [Learning General Optimal Policies with Graph Neural Networks: Expressive Power, Transparency, and Limits](https://mlsanity.com/paper/2109.10129/) (2021)
- [Learning Heuristic Search via Imitation](https://mlsanity.com/paper/1707.03034/) (2017)
- [Learning to Search with MCTSnets](https://mlsanity.com/paper/1802.04697/) (2018)
- [Learning to Rank for Synthesizing Planning Heuristics](https://mlsanity.com/paper/1608.01302/) (2016)
- [Single-Agent Policy Tree Search With Guarantees](https://mlsanity.com/paper/1811.10928/) (2018)
- [Policy-Guided Heuristic Search with Guarantees](https://mlsanity.com/paper/2103.11505/) (2021)
- [Solving Hard AI Planning Instances Using Curriculum-Driven Deep Reinforcement Learning](https://mlsanity.com/paper/2006.02689/) (2020)
- [Neuro-algorithmic Policies enable Fast Combinatorial Generalization](https://mlsanity.com/paper/2102.07456/) (2021)
- [Heuristic Search Planning with Deep Neural Networks using Imitation, Attention and Curriculum Learning](https://mlsanity.com/paper/2112.01918/) (2021)

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

- [WorldCoder, a Model-Based LLM Agent: Building World Models by Writing Code and Interacting with the Environment](https://mlsanity.com/paper/2402.12275/) (2024)
- [Return to Tradition: Learning Reliable Heuristics with Classical Machine Learning](https://mlsanity.com/paper/2403.16508/) (2024)
- [Graph Learning for Numeric Planning](https://mlsanity.com/paper/2410.24080/) (2024)
- [Leveraging Action Relational Structures for Integrated Learning and Planning](https://mlsanity.com/paper/2504.20318/) (2025)
- [Graph Neural Network Based Action Ranking for Planning](https://mlsanity.com/paper/2412.04752/) (2024)
- [Deep Learning for Generalised Planning with Background Knowledge](https://mlsanity.com/paper/2410.07923/) (2024)
- [Learning Efficiency Meets Symmetry Breaking](https://mlsanity.com/paper/2504.19738/) (2025)
- [Learning Admissible Heuristics for A*: Theory and Practice](https://mlsanity.com/paper/2509.22626/) (2025)
- [Graph Learning for Planning: The Story Thus Far and Open Challenges](https://mlsanity.com/paper/2412.02136/) (2024)
- [GammaZero: Learning To Guide POMDP Belief Space Search With Graph Representations](https://mlsanity.com/paper/2510.14035/) (2025)

## Abstract (arXiv)

In imitation learning for planning, parameters of heuristic functions are optimized against a set of solved problem instances. This work revisits the necessary and sufficient conditions of strictly optimally efficient heuristics for forward search algorithms, mainly A* and greedy best-first search, which expand only states on the returned optimal path. It then proposes a family of loss functions based on ranking tailored for a given variant of the forward search algorithm. Furthermore, from a learning theory point of view, it discusses why optimizing cost-to-goal hstar is unnecessarily difficult. The experimental comparison on a diverse set of problems unequivocally supports the derived theory.