A randomized restart strategy is a simple trick from combinatorial search. You run a randomized solver for a short while. If it has not finished, you kill the run and start again with fresh randomness. This works when run times are heavy-tailed: most runs take forever, but a few finish almost immediately, so many short tries beat one long one. Neural planners for Sokoban, a box-pushing puzzle whose general form is PSPACE-hard, show this pattern strongly. Yet the networks that guide these planners are trained with ordinary losses that were never designed with restarts in mind. Those losses have a scale bias. The value network regresses distance-to-goal with squared error, so states hundreds of moves from the goal dominate its gradients. The policy network's cross-entropy is summed over training states, so puzzles with long solutions dominate. The same bias is well documented in vision: plain pixel or coordinate losses let large objects drown out small ones, and losses that normalize per object or per instance fix it.
This note proposes treating the training loss as a control knob on the runtime distribution under restarts. We will train Deep Best-First Search heuristics with losses that are invariant to the scale of the instance and of the target. The value network gets a log-relative distance loss with an explicit dead-end class. The policy network gets a per-instance normalized cross-entropy with a tunable exponent. We then measure how each choice reshapes the fast left tail of short successful runs that restarts exploit. The question is one no prior work asks: does the loss used to train a search heuristic change how much restarts help, and can a scale-invariant loss make restarts help more on the hardest instances?
Core Claim
In Deep Best-First Search (DBFS), a node $n$ is ranked by $f(n) = (g(n) + h(n)) / p(n \mid \text{parent}(n))$. Here $g$ is the cost so far, $h$ is the value network's estimate of remaining cost, and $p$ is the policy network's probability for the move that produced $n$. Two consequences follow from that formula.
First, what shapes search order is the relative error in $h$, not its absolute error. An error of 5 moves matters a great deal near the goal and hardly at all 300 moves out. Squared error spends most of the network's capacity on the far, irrelevant states.
Second, following the bound of Single-Agent Policy Tree Search With Guarantees, which proves that policy-guided best-first search expands roughly $g/\pi$ nodes, the search cost on an instance grows roughly as the inverse of the policy's probability $\pi$ for the solution path. That probability is a product over the solution's decisions. A few "critical" decisions, the moves after which the puzzle becomes unsolvable, play the role that tiny objects play in detection. They are rare in the training data but decisive for cost.
We claim that a scale-invariant loss will raise $p(c)$ on hard, long instances even if it slightly lowers average one-step accuracy. Here $p(c)$ is the probability that a single randomized run solves an instance within a cutoff of $c$ node expansions. Under a fixed-cutoff restart policy, expected cost is bounded by
$$\mathbb{E}[T] \le \frac{c}{p(c)},$$
because every failed run costs at most $c$ and the number of runs is geometric with success probability $p(c)$. Raising $p(c)$ at small $c$ is exactly what makes restarts pay. The loss therefore should be judged by its effect on this quantity, not by held-out cross-entropy.
Relation to Prior Work
The restart side supplies the phenomenon and the tools. Heavy-Tailed Distributions in Combinatorial Search characterized power-law runtime tails. Boosting Combinatorial Search Through Randomization showed that randomization plus cutoffs yields finite expected cost. The Effect of Restarts on the Efficiency of Clause Learning established the Luby sequence as a restart schedule that needs no knowledge of the runtime distribution. All three treat the solver's heuristic as fixed and tune only the schedule. We instead change how the heuristic is trained.
Two papers motivate the gap directly. Left Heavy Tails and the Effectiveness of the Policy and Value Networks in DNN-based best-first search for Sokoban Planning and The Remarkable Effectiveness of Combining Policy and Value Networks in A*-based Deep RL for AI Planning introduced DBFS and found the left heavy tail. On these instances most runs time out, but a few runs randomized by Monte Carlo dropout finish fast. Monte Carlo dropout means keeping dropout switched on at test time, here at a 30% rate, so each run takes different branches. These papers also found the value network much worse at spotting dead ends than the policy network. They trained both networks with standard losses and did not ask whether the loss causes that gap. Rapid Randomized Restarts for Multi-Agent Path Finding Solvers adds a constraint: restarts only help when the heuristic is informative enough. That makes heuristic quality, and therefore its training objective, the lever that decides whether restarts work.
The scale-invariant side supplies the method. Towards Size-invariant Salient Object Detection: A Generic Evaluation and Optimization Approach computes the loss per object so small and large objects count equally. We transplant this as per-instance normalization of the policy loss. Learning High-Precision Bounding Box for Rotated Object Detection via Kullback-Leibler Divergence damps gradients with $\log(\text{KLD}+1)$ so they self-adjust across extreme aspect ratios. We borrow the log damping for distance targets that span orders of magnitude. Supervised Fitting of Geometric Primitives to 3D Point Clouds weights every surface equally regardless of point count. It is the clearest evidence that equal-weight objectives recover small structure that thresholded methods miss.
None of these vision works involves search or runtime distributions. No paper in our search combines the two directions.
Research Program
We will build three training variants on the DBFS pipeline and hold everything else fixed: architecture, data, dropout rate, and search code.
The value loss replaces squared error on distance $d$ with a log-relative loss plus a dead-end head. Solvable states use
$$\ell_v = \big(\log(1+\hat h) - \log(1+d)\big)^2,$$
where $\hat h$ is the predicted distance. Known dead-end states are trained with a separate binary cross-entropy head rather than being squeezed into a large capped distance. At search time a dead-end probability above a threshold inflates $h$.
The policy loss weights instance $i$'s summed cross-entropy by $|\tau_i|^{-\beta}$, where $|\tau_i|$ is its solution length. Setting $\beta=0$ recovers standard training, which by the path-probability argument minimizes the sum of log search costs. Setting $\beta=1$ makes every puzzle count equally, in the manner of per-object losses. We sweep $\beta \in \{0, 0.5, 1\}$ because the path-probability argument says the right weighting may depend on the node budget. This is a hypothesis to test, not assume.
The diagnostics are the real product. For each instance we run 200 randomized runs and record the empirical distribution of run length. From it we estimate $p(c)$ at cutoffs from 500 to 32,000 nodes and fit the survival-function tail exponent in the style of Gomes et al. We then compute the best fixed-cutoff restart cost and the Luby-schedule cost. This tells us whether a loss moves mass into the fast left tail, or merely improves the median run.
We will also address the tension that equal weighting might dilute the policy network's dead-end pruning. We will measure dead-end detection accuracy for both networks under every variant, using the hard-set protocol of Feng et al.
Baselines
The naive reference is deterministic DBFS with standard losses and no dropout at test time, given one continuous run of the full budget. This is the "do nothing" point that every restart claim must beat.
The strongest existing method is DBFS with standard losses, Monte Carlo dropout, and restarts, exactly as in Left Heavy Tails and the Effectiveness of the Policy and Value Networks in DNN-based best-first search for Sokoban Planning. The file reports the following figures for it. On the Sokobano test set it reaches a solving ratio "up to 50.0%" at 32,000 node expansions, against 31.4% for Policy-guided Heuristic Search (PHS) and 46.2% for PHS*. It solves 69% of the 137-instance Hard set within 10 minutes, a set the specialized solver Sokolution could not solve even in 2 hours. Its policy network detects dead ends with 68% accuracy, against 37% for the value network. It is the strongest competitor because it already exploits the left tail with a tuned restart count.
To keep the comparison fair, we will retrain it ourselves on the same 7,435 training instances with the same architecture, number of epochs, and hyperparameter search budget as our variants. We will re-tune its dropout rate and restart schedule with the same grid we give our models, and report our reproduction next to the published figures. Beating it means a statistically significant gain in solving ratio at matched node budgets of 5,000 and 32,000, and on the Hard set at 10 minutes. The gain must hold after each method's restart schedule is tuned separately.
Two ablations isolate the key ingredient. The first applies only the value-loss change. The second applies only the policy reweighting, across the $\beta$ sweep. A further control applies the new losses but runs deterministically without restarts. It checks whether the gains depend on restarts, as claimed, or would appear anyway.
Why not just…?
Why not just tune the restart schedule and dropout rate harder? This is the most serious threat. If a better cutoff schedule or dropout rate closes the gap, the loss is irrelevant. Restart theory in Boosting Combinatorial Search Through Randomization and the Luby results in The Effect of Restarts on the Efficiency of Clause Learning show that a schedule can only exploit whatever $p(c)$ the solver already has. It cannot raise $p(c)$. Our design gives every model an identical schedule-and-dropout tuning grid and compares the $p(c)$ curves directly. If the tuned standard model matches our $p(c)$ at small $c$, we will report that the loss does not matter.
Why not just use hard-example mining or a focal-style loss? Reweighting states by their current loss also upweights the rare critical decisions. It is a real alternative to scale-based weighting. The difference is what drives the reweighting. Focal weighting reacts to difficulty. Scale-invariant weighting reacts to instance length and target magnitude, which the path-probability bound ties directly to search cost. We will include a focal-loss policy variant with a matched tuning budget as an extra baseline. If it wins, the lesson is that difficulty matters more than scale, and we will say so.
Why not just give the single run a larger budget? The evidence already argues against this. Feng et al. found that at 5,000 nodes, five restarts beat one continuous run. Sokolution failed on the Hard set even with a 12-fold longer time limit. Cohen et al. found that several short runs dominated one long run for 170 agents in warehouse path finding. Our deterministic-no-restart control rechecks this under each loss.
Why not just normalize the value targets, for example by predicting log distance? Predicting log distance with squared error is essentially our value loss. What is new is not the transform but the dead-end head and the claim that the transform changes restart behavior. The value-only ablation tests exactly that claim.
Proposed Experiments
All experiments use the Sokobano collection: 7,435 training and 827 test instances, averaging about 20 boxes. The decisive tests use its 137-instance Hard subset. The primary metrics are solving ratio at 5,000 and 32,000 node expansions, Hard-set solve rate within 10 minutes of wall-clock time, and dead-end detection accuracy. The distributional metrics are the estimated $p(c)$ curves, the fitted tail exponent, and the expected restart cost at the best fixed cutoff and under Luby.
The first decisive check stratifies test instances by solution length. If the scale-bias story is right, gains from the log-relative value loss should concentrate on long-solution and Hard instances. They should appear as higher $p(c)$ at small $c$ rather than a lower median run length. Gains spread evenly across lengths would count against the mechanism.
The second decisive check tests the value network's dead-end accuracy. If the 37% figure reflects the squared-error loss rather than a limit of value networks in general, the dead-end head should raise it substantially without lowering the policy network's 68%. A drop in policy pruning accuracy under $\beta=1$ would confirm the dilution worry and argue for $\beta$ near 0.5.
The third check tests the budget dependence predicted by the path-probability bound. The best $\beta$ should shift with the node budget, with more scale-invariant weighting paying off at small cutoffs where restarts are frequent. A single best $\beta$ at every budget would simplify the recommendation and weaken the theoretical story.
A null result is also informative. If every variant yields the same $p(c)$ curves after schedule tuning, restart effectiveness in neural planning is set by the randomization scheme rather than the training objective. That would redirect effort toward learned restart policies such as Learning Restart Strategies.
References
- Single-Agent Policy Tree Search With Guarantees
- Heavy-Tailed Distributions in Combinatorial Search
- Boosting Combinatorial Search Through Randomization
- The Effect of Restarts on the Efficiency of Clause Learning
- Left Heavy Tails and the Effectiveness of the Policy and Value Networks in DNN-based best-first search for Sokoban Planning
- The Remarkable Effectiveness of Combining Policy and Value Networks in A*-based Deep RL for AI Planning
- Rapid Randomized Restarts for Multi-Agent Path Finding Solvers
- Towards Size-invariant Salient Object Detection: A Generic Evaluation and Optimization Approach
- Learning High-Precision Bounding Box for Rotated Object Detection via Kullback-Leibler Divergence
- Supervised Fitting of Geometric Primitives to 3D Point Clouds
- Learning Restart Strategies