Beyond Single-Step Updates: Reinforcement Learning of Heuristics with Limited-Horizon Search
Gal Hadar Forest Agostinelli Shahaf S. Shperberg · 2025
Read Beyond Single-Step Updates: Reinforcement Learning of Heuristics with Limited-Horizon Search by Gal Hadar Forest Agostinelli Shahaf S. Shperberg (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-10264.txt.
Introduction
Gal Hadar, Forest Agostinelli, and Shahaf S. Shperberg improve how reinforcement learning trains heuristic functions for shortest-path search problems. A heuristic estimates the remaining cost to a goal, and recent methods learn it with deep approximate value iteration. Those methods update each state from its single best neighbor, a one-step view that can learn slowly and noisily.
Their generalization runs limited-horizon searches during learning. Each state's heuristic is updated from the true shortest path to the search frontier, combining the edge costs along that path with the frontier states' current heuristic values. Better state sampling accompanies the richer updates. The paper positions limited-horizon search as a principled upgrade over single-step Bellman updates for learning search guidance.
Catalog record
| CREATOR | Gal Hadar Forest Agostinelli Shahaf S. Shperberg |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 36 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-10264
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Beyond Single-Step Updates: Reinforcement Learning of Heuristics with Limited-Horizon Search Gal Hadar Forest Agostinelli Shahaf S. Shperberg Abstract Many sequential decision-making problems can be formulated as shortest-path problems, where the objective is to reach a goal state from a given starting state. Heuristic search is a standard approach for solving such problems, relying on a heuristic function to estimate the cost to the goal from any given state. Recent approaches leverage reinforcement learning to learn heuristics by applying deep approximate value iteration. These methods typically rely on single-step Bellman updates, where the heuristic of a state is updated based on its best neighbor and the corresponding edge cost. This work proposes a generalized approach that enhances both state sampling and heuristic updates by performing limited-horizon searches and updating each state’s heuristic based on the shortest path to the search frontier, incorporating both edge costs and the heuristic values of frontier states. Introduction Search algorithms have been fundamental to artificial intelligence (AI) since its inception, playing a central role in problem-solving and decision-making ( 28 ; 10 ) . Among them, heuristic search, guided by a heuristic function to estimate the cost from a given state to a goal, has been particularly influential. It enables efficient navigation of vast solution spaces in domains such as route planning, hardware verification, theorem proving, robotics, and computational biology ( 21 ) , many of which are often posed as reinforcement learning problems. The effectiveness of heuristic search hinges on the accuracy of the heuristic function. While domain-specific heuristics can be highly effective, they often require expert knowledge. To address this limitation, domain-independent methods such as pattern databases ( 17 ) have been developed. However, these approaches involve trade-offs between computational cost and heuristic accuracy, especially as problem complexity increases ( 1 ; 36 ) . Recent advancements leverage deep neural networks (DNNs) ( 40 ) and reinforcement learning (RL) ( 42 ) to learn heuristics directly from data. Although these methods lack theoretical guarantees, they offer scalable, domain-specific heuristics that have demonstrated success in solving problems such as the Rubik’s Cube ( 1 ) , chemical synthesis ( 13 ) , quantum algorithm compilation ( 47 ; 6 ) , and robotics ( 45 ; 23 ) , often producing optimal or near-optimal solutions. A common approach to learning heuristics through RL is approximate dynamic programming ( 7 ; 8 ) . This involves sampling states from the environment and applying a single-step Bellman update, where a state’s heuristic estimate is refined based on its best successor. DeepCubeA ( 1 ) exemplifies this strategy, training a DNN via approximate value iteration to predict cost-to-go estimates, which are then used with a batched version of weighted A* search ( 38 ) for efficient problem-solving. In this paper, we demonstrate and tackle limitations in single-step Bellman-based heuristic updates. First, sampling random states in isolation neglects the inherent structure of search processes. In practice, states are not explored randomly but are instead closely related, forming local regions within the search space. Single-step updates fail to capture these dependencies when training a heuristic function. Additionally, single-step Bellman updates typically rely on the transition cost of a single edge—the edge to the best successor—while primarily depending on potentially inaccurate heuristic estimates of successors. To address these challenges, we introduce Limited-Horizon Bellman-based Learning (LHBL), a method that performs limited-horizon searches from sampled states, leveraging the broader search context to generate training labels. Each state’s heuristic is updated based on the best descendant on the frontier, combining the full path cost to the descendant and its heuristic for more informative labels than single-step updates. Additionally, since training states come from search, not random sampling, they better reflect those seen during actual search. This results in improved training efficiency and faster, more reliable search across multiple domains, as demonstrated in our empirical evaluation. Background and Related Work Pathfinding is a fundamental concept in AI with diverse applications ( 28 ; 10 ) . A pathfinding problem instance, I=(G,c,\mbox{$\mathit{start}$},\mbox{$\mathit{goal}$}) , where G=(V,E) is a graph with states (vertices) V and transitions (edges) E\subseteq V\times V . The cost function c:E\rightarrow\mathbb{R}^{+} assigns a non-negative cost to each edge. The instance specifies a start state ( \mathit{start} ) and either a goal state ( \mathit{goal} ) or a goal predicate P:V\rightarrow\{0,1\} , which indicates whether a state satisfies the goal condition. The objective is to find a path in G that connects \mathit{start} to \mathit{goal} with minimal cumulative cost, determined by the sum of the costs of its edges, though in some cases, finding a high-quality path quickly is prioritized over optimality, especially for large-scale problems or time-sensitive scenarios. Heuristic search extends pathfinding by incorporating a heuristic function h:V\to\mathbb{R}^{+} , which estimates the cost of the shortest path from a state s to the nearest goal state, commonly referred to as the cost-to-go . The problem instance is then defined as I=(G,c,\mbox{$\mathit{start}$},\mbox{$\mathit{goal}$},h). Heuristics can be domain-specific, like Manhattan distance in grid navigation, or derived automatically using techniques like pattern databases (PDBs) ( 17 ) , state-space transformations ( 35 ) , and delete relaxations ( 11 ) . Batch Weighted A* A^{*} ( 28 ) is a widely used and foundational search algorithm that maintains a priority queue, OPEN, of nodes discovered during the search, with each node containing state n.s , g(n) , the accumulated path cost from the start state to n , and cost f(n)=g(n)+h(n.s) , where h(n.s) is the heuristic estimate of the remaining cost to a goal from state n.s . A^{*} iteratively removes and expands the node with the lowest cost ( f -value), until selecting a node associated with a goal state for expansion. When A* uses a learned heuristic function (e.g., a deep neural network), heuristic computation can become a bottleneck. To mitigate this, GPUs can be leveraged to expand the B lowest-cost nodes in parallel, computing their heuristic values simultaneously. Still, A* can still be time- and memory-intensive. Weighted A* search ( 38 ) mitigates this by adjusting the cost function: f(n)=\lambda g(n)+h(n.s), (1) where \lambda\in[0,1] balances path cost and heuristic guidance. Lower \lambda values bias toward heuristic-driven exploration, trading optimality for efficiency. Notably, the extreme case of \lambda=0 yields Greedy Best-first Search (GBFS), which abandons optimality to prioritize speed. Combining parallel expansion and weighting yields batch-weighted A* search (BWAS) , a generalization of A* where standard A* is recovered by setting B=1 and \lambda=1 . A* guarantees optimal solutions given an admissible heuristic, that is, a heuristic that never overestimates the cost of the shortest path: h(s)\leq h^{*}(s) for all s , where h^{*}(s) is the cost of a shortest path to a closest goal state from s ( 19 ) . Similarly, weighted A* and BWAS guarantee bounded suboptimality under the same condition ( 3 ; 31 ) . Although neural network-based heuristics are not necessarily admissible, research continues on developing admissible heuristics via deep learning ( 22 ; 3 ; 31 ) . Learning Heuristic Functions Research on learning heuristic functions has explored methods to enhance heuristic-based algorithms for over three decades. One approach is imitation learning, where cost-to-go values, often derived from domain knowledge or solvers, are used to train heuristics via