aiqbench analysis
This paper addresses a critical flaw in standard deep reinforcement learning for heuristic search, where mean-squared error training often produces overestimations that violate admissibility and compromise solution optimality. By introducing an underestimating Admissible Bellman Operator, an asymmetric loss function, and a post-hoc calibration offset, the authors achieve zero observed admissibility violations while significantly reducing search node expansions on combinatorial puzzles. The approach offers a robust framework for ensuring theoretical guarantees in neural heuristic search without sacrificing practical efficiency.
Learning Empirically Admissible Neural Heuristics for Combinatorial Search
arXiv:2606.04860v1 Announce Type: new Abstract: Finding optimal solution paths for combinatorial puzzles like the Rubik's Cube, sliding tile puzzles, and Lights Out remains a classical challenge in artificial intelligence. Heuristic search algorithms, such as A* , guarantee path optimality only when using an admissible heuristic-one that never overestimates the true remaining cost-to-go. Deep reinforcement learning (RL) methods like DeepCubeA train deep neural networks to approximate cost-to-go heuristics. However, standard mean-squared error (MSE) training regularly yields overestimations, violating admissibility and compromising solution optimality. In this paper, we introduce a generalizable framework for learning validation-calibrated admissible neural heuristics. We train a value network using an underestimating Admissible Bellman Operator combined with an Asymmetric Loss function to penalize overestimation. To account for residual neural function approximation errors, we propose a post-hoc calibration safety offset computed over validation scrambles. We demonstrate that our calibrated neural heuristics achieve no observed admissibility violations under the evaluation protocol and preserve path optimality in practice while reducing search node expansions by up to 83.0% on a 2 by 2 Rubik's Cube, 19.9% on a 3 by 3 Lights Out grid, and 1.9% on an 8-Puzzle compared to standard analytical baselines.
Abstract:Finding optimal solution paths for combinatorial puzzles like the Rubik's Cube, sliding tile puzzles, and Lights Out remains a classical challenge in artificial intelligence. Heuristic search algorithms, such as A* , guarantee path optimality only when using an admissible heuristic-one that never overestimates the true remaining cost-to-go. Deep reinforcement learning (RL) methods like DeepCubeA train deep neural networks to approximate cost-to-go heuristics. However, standard mean-squared error (MSE) training regularly yields overestimations, violating admissibility and compromising solution optimality. In this paper, we introduce a generalizable framework for learning validation-calibrated admissible neural heuristics. We train a value network using an underestimating Admissible Bellman Operator combined with an Asymmetric Loss function to penalize overestimation. To account for residual neural function approximation errors, we propose a post-hoc calibration safety offset computed over validation scrambles. We demonstrate that our calibrated neural heuristics achieve no observed admissibility violations under the evaluation protocol and preserve path optimality in practice while reducing search node expansions by up to 83.0% on a 2 by 2 Rubik's Cube, 19.9% on a 3 by 3 Lights Out grid, and 1.9% on an 8-Puzzle compared to standard analytical baselines.
Machine Learning (cs.LG); Artificial Intelligence (cs.AI)
arXiv:2606.04860 [cs.LG]
(or arXiv:2606.04860v1 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2606.04860 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 284 words
Related coverage
A Quantum Method of Types
arXiv · Sep 2, 2026
Self-Supervised Combinatorial Optimization with Constraints via Frank-Wolfe
arXiv · Sep 24, 2026
Perceptual Refinement of an End-to-End Video Streaming Pipeline via Generative AI Layers
arXiv · Sep 18, 2026
AFA-BANDIT: Provably Near-Optimal Online Multi-Feature Classification Under Budget Constraints
arXiv · Oct 7, 2026