mlsanityData to 7 Oct 2026

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

arXiv 2310.19463 ↗First posted 30 Oct 2023cs.AI cs.LGcited by 10

On the map: Offline RL and imitation learning from data → Imitation learning methods

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.

Key facts. Cited by 10 papers in the map (data through 7 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.

Builds on

15 of 61 references.

References · 15

  1. 2020AdaBelief Optimizer: Adapting Stepsizes by the Belief in Observed Gradientscited by 282
  2. 2017Thinking Fast and Slow with Deep Learning and Tree Searchcited by 245
  3. 2020Path Planning using Neural A* Searchcited by 51
  4. 2019Learning Domain-Independent Planning Heuristics with Hypergraph Networkscited by 50
  5. 2019ASNets: Deep Learning for Generalised Planningcited by 42
  6. 2017Learning Generalized Reactive Policies using Deep Neural Networkscited by 39
  7. 2021Learning General Optimal Policies with Graph Neural Networks: Expressive Power, Transparency, and Limitscited by 38
  8. 2017Learning Heuristic Search via Imitationcited by 34
  9. 2018Learning to Search with MCTSnetscited by 32
  10. 2016Learning to Rank for Synthesizing Planning Heuristicscited by 22
  11. 2018Single-Agent Policy Tree Search With Guaranteescited by 22
  12. 2021Policy-Guided Heuristic Search with Guaranteescited by 20
3 more
  1. 2021Neuro-algorithmic Policies enable Fast Combinatorial Generalizationcited by 11
  2. 2020Solving Hard AI Planning Instances Using Curriculum-Driven Deep Reinforcement Learningcited by 10
  3. 2021Heuristic Search Planning with Deep Neural Networks using Imitation, Attention and Curriculum Learningcited by 6

Built on by

Cited by year

Citing papers per year: 2024: 6; 2025: 4.

10 papers.

  1. 2024WorldCoder, a Model-Based LLM Agent: Building World Models by Writing Code and Interacting with the Environmentcited by 99
  2. 2024Return to Tradition: Learning Reliable Heuristics with Classical Machine Learningcited by 19
  3. 2024Graph Learning for Numeric Planningcited by 5
  4. 2025Leveraging Action Relational Structures for Integrated Learning and Planningcited by 4
  5. 2024Graph Neural Network Based Action Ranking for Planningcited by 3
  6. 2024Deep Learning for Generalised Planning with Background Knowledgecited by 2
  7. 2025Learning Efficiency Meets Symmetry Breakingcited by 2
  8. 2025Learning Admissible Heuristics for A*: Theory and Practicecited by 2
  9. 2024Graph Learning for Planning: The Story Thus Far and Open Challengescited by 0
  10. 2025GammaZero: Learning To Guide POMDP Belief Space Search With Graph Representationscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2018Truncated Horizon Policy Search: Combining Reinforcement Learning & Imitation Learning
  2. 2022A Ranking Game for Imitation Learning
  3. 2019Reward-Conditioned Policies
  4. 2019Leveraging Experience in Lazy Search
  5. 2022Travel the Same Path: A Novel TSP Solving Strategy
  6. 2019Learning from Trajectories via Subgoal Discovery
  7. 2021Leveraging Experience in Lazy Search
  8. 2024Imitating Cost-Constrained Behaviors in Reinforcement Learning