# Reinforcement Learning for Classical Planning: Viewing Heuristics as Dense Reward Generators

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 91 references that are in the map.
- First posted on arXiv 30 Sep 2021.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Continuous control with deep reinforcement learning](https://mlsanity.com/paper/1509.02971/) (2015)
- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [Asynchronous Methods for Deep Reinforcement Learning](https://mlsanity.com/paper/1602.01783/) (2016)
- [Deep Sets](https://mlsanity.com/paper/1703.06114/) (2017)
- [Relational inductive biases, deep learning, and graph networks](https://mlsanity.com/paper/1806.01261/) (2018)
- [Deep Reinforcement Learning that Matters](https://mlsanity.com/paper/1709.06560/) (2017)
- [RL2: Fast Reinforcement Learning via Slow Reinforcement Learning](https://mlsanity.com/paper/1611.02779/) (2016)
- [Agent57: Outperforming the Atari Human Benchmark](https://mlsanity.com/paper/2003.13350/) (2020)
- [Neural Logic Machines](https://mlsanity.com/paper/1904.11694/) (2019)
- [Learning Domain-Independent Planning Heuristics with Hypergraph Networks](https://mlsanity.com/paper/1911.13101/) (2019)
- [PDDLGym: Gym Environments from PDDL Problems](https://mlsanity.com/paper/2002.06432/) (2020)
- [Generalized Planning With Deep Reinforcement Learning](https://mlsanity.com/paper/2005.02305/) (2020)
- [Learning to Rank for Synthesizing Planning Heuristics](https://mlsanity.com/paper/1608.01302/) (2016)
- [Online Planner Selection with Graph Neural Networks and Adaptive Scheduling](https://mlsanity.com/paper/1811.00210/) (2018)
- [Automatic Induction of Bellman-Error Features for Probabilistic Planning](https://mlsanity.com/paper/1401.3847/) (2014)
- [Meta-Reinforcement Learning for Heuristic Planning](https://mlsanity.com/paper/2107.02603/) (2021)

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

- [Learning Domain-Independent Heuristics for Grounded and Lifted Planning](https://mlsanity.com/paper/2312.11143/) (2023)
- [How Can LLM Guide RL? A Value-Based Approach](https://mlsanity.com/paper/2402.16181/) (2024)
- [PG3: Policy-Guided Planning for Generalized Policy Generation](https://mlsanity.com/paper/2204.10420/) (2022)
- [Language Models For Generalised PDDL Planning: Synthesising Sound and Programmatic Policies](https://mlsanity.com/paper/2508.18507/) (2025)
- [On Using Admissible Bounds for Learning Forward Search Heuristics](https://mlsanity.com/paper/2308.11905/) (2023)
- [Graph Learning for Numeric Planning](https://mlsanity.com/paper/2410.24080/) (2024)
- [Scale-Adaptive Balancing of Exploration and Exploitation in Classical Planning](https://mlsanity.com/paper/2305.09840/) (2023)
- [Understanding Sample Generation Strategies for Learning Heuristic Functions in Classical Planning](https://mlsanity.com/paper/2211.13316/) (2022)
- [Curiosity-Driven Imagination: Discovering Plan Operators and Learning Associated Policies for Open-World Adaptation](https://mlsanity.com/paper/2503.04931/) (2025)
- [Hierarchical Reinforcement Learning with AI Planning Models](https://mlsanity.com/paper/2203.00669/) (2022)
- [Exploration Policies for On-the-Fly Controller Synthesis: A Reinforcement Learning Approach](https://mlsanity.com/paper/2210.05393/) (2022)
- [A Review of Symbolic, Subsymbolic and Hybrid Methods for Sequential Decision Making](https://mlsanity.com/paper/2304.10590/) (2023)
- [TW-CRL: Time-Weighted Contrastive Reward Learning for Efficient Inverse Reinforcement Learning](https://mlsanity.com/paper/2504.05585/) (2025)
- [Weisfeiler-Leman Features for Planning: A 1,000,000 Sample Size Hyperparameter Study](https://mlsanity.com/paper/2508.18515/) (2025)
- [Few-Shot Neuro-Symbolic Imitation Learning for Long-Horizon Planning and Acting](https://mlsanity.com/paper/2508.21501/) (2025)
- [Don't Solve, Just Compare: Tiny Advisors for Runtime Intervention in LLM Agents](https://mlsanity.com/paper/2608.21027/) (2026)
- [Reinforcement Learning-based Heuristics to Guide Domain-Independent Dynamic Programming](https://mlsanity.com/paper/2503.16371/) (2025)
- [Abstract Interpretation for Generalized Heuristic Search in Model-Based Planning](https://mlsanity.com/paper/2208.02938/) (2022)
- [Exploiting Symbolic Heuristics for the Synthesis of Domain-Specific Temporal Planning Guidance using Reinforcement Learning](https://mlsanity.com/paper/2505.13372/) (2025)
- [Graph Contextual Reinforcement Learning for Efficient Directed Controller Synthesis](https://mlsanity.com/paper/2512.15295/) (2025)
- [Build on Priors: Vision--Language--Guided Neuro-Symbolic Imitation Learning for Data-Efficient Real-World Robot Manipulation](https://mlsanity.com/paper/2604.03759/) (2026)

## Abstract (arXiv)

Recent advances in reinforcement learning (RL) have led to a growing interest in applying RL to classical planning domains or applying classical planning methods to some complex RL domains. However, the long-horizon goal-based problems found in classical planning lead to sparse rewards for RL, making direct application inefficient. In this paper, we propose to leverage domain-independent heuristic functions commonly used in the classical planning literature to improve the sample efficiency of RL. These classical heuristics act as dense reward generators to alleviate the sparse-rewards issue and enable our RL agent to learn domain-specific value functions as residuals on these heuristics, making learning easier. Correct application of this technique requires consolidating the discounted metric used in RL and the non-discounted metric used in heuristics. We implement the value functions using Neural Logic Machines, a neural network architecture designed for grounded first-order logic inputs. We demonstrate on several classical planning domains that using classical heuristics for RL allows for good sample efficiency compared to sparse-reward RL. We further show that our learned value functions generalize to novel problem instances in the same domain.