# On Using Admissible Bounds for Learning Forward Search Heuristics

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 55 references that are in the map.
- First posted on arXiv 23 Aug 2023.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Decoupled Weight Decay Regularization](https://mlsanity.com/paper/1711.05101/) (2017)
- [Deep Reinforcement Learning that Matters](https://mlsanity.com/paper/1709.06560/) (2017)
- [Reinforcement Learning for Solving the Vehicle Routing Problem](https://mlsanity.com/paper/1802.04240/) (2018)
- [Agent57: Outperforming the Atari Human Benchmark](https://mlsanity.com/paper/2003.13350/) (2020)
- [Neural Logic Machines](https://mlsanity.com/paper/1904.11694/) (2019)
- [NeuroLKH: Combining Deep Learning Model with Lin-Kernighan-Helsgaun Heuristic for Solving the Traveling Salesman Problem](https://mlsanity.com/paper/2110.07983/) (2021)
- [Learning Domain-Independent Planning Heuristics with Hypergraph Networks](https://mlsanity.com/paper/1911.13101/) (2019)
- [Heuristic-Guided Reinforcement Learning](https://mlsanity.com/paper/2106.02757/) (2021)
- [Learning Optimal Resource Allocations in Wireless Systems](https://mlsanity.com/paper/1807.08088/) (2018)
- [Generalized Planning With Deep Reinforcement Learning](https://mlsanity.com/paper/2005.02305/) (2020)
- [Action Schema Networks: Generalised Policies with Deep Learning](https://mlsanity.com/paper/1709.04271/) (2017)
- [Learning to Rank for Synthesizing Planning Heuristics](https://mlsanity.com/paper/1608.01302/) (2016)
- [Reinforcement Learning for Classical Planning: Viewing Heuristics as Dense Reward Generators](https://mlsanity.com/paper/2109.14830/) (2021)
- [Minimizing Safety Interference for Safe and Comfortable Automated Driving with Distributional Reinforcement Learning](https://mlsanity.com/paper/2107.07316/) (2021)
- [Towards learning domain-independent planning heuristics](https://mlsanity.com/paper/1707.06895/) (2017)
- [Learning Search-Space Specific Heuristics Using Neural Networks](https://mlsanity.com/paper/2306.04019/) (2023)

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

- [Learning Admissible Heuristics for A*: Theory and Practice](https://mlsanity.com/paper/2509.22626/) (2025)
- [Extreme Value Monte Carlo Tree Search for Classical Planning](https://mlsanity.com/paper/2405.18248/) (2024)
- [Graph Learning for Planning: The Story Thus Far and Open Challenges](https://mlsanity.com/paper/2412.02136/) (2024)
- [AAC: Admissible-by-Architecture Differentiable Landmark Compression for ALT](https://mlsanity.com/paper/2604.20744/) (2026)
- [LLM-Evolved Pattern Generators for Optimal Classical Planning](https://mlsanity.com/paper/2606.02438/) (2026)

## Abstract (arXiv)

In recent years, there has been growing interest in utilizing modern machine learning techniques to learn heuristic functions for forward search algorithms. Despite this, there has been little theoretical understanding of what they should learn, how to train them, and why we do so. This lack of understanding has resulted in the adoption of diverse training targets (suboptimal vs optimal costs vs admissible heuristics) and loss functions (e.g., square vs absolute errors) in the literature. In this work, we focus on how to effectively utilize the information provided by admissible heuristics in heuristic learning. We argue that learning from poly-time admissible heuristics by minimizing mean square errors (MSE) is not the correct approach, since its result is merely a noisy, inadmissible copy of an efficiently computable heuristic. Instead, we propose to model the learned heuristic as a truncated gaussian, where admissible heuristics are used not as training targets but as lower bounds of this distribution. This results in a different loss function from the MSE commonly employed in the literature, which implicitly models the learned heuristic as a gaussian distribution. We conduct experiments where both MSE and our novel loss function are applied to learning a heuristic from optimal plan costs. Results show that our proposed method converges faster during training and yields better heuristics.