Left Heavy Tails and the Effectiveness of the Policy and Value Networks in DNN-based best-first search for Sokoban Planning
Authors: Dieqiao Feng
Carla P Gomes
Bart Selman
Venue: NeurIPS 2022 Accept (2022)
Keywords: rl

Abstract:  Despite the success of practical solvers in various NP-complete domains such as SAT and CSP as well as using deep reinforcement learning to tackle two-player games such as Go, certain classes of PSPACE-hard planning problems have remained out of reach. Even carefully designed domain-specialized solvers can fail quickly due to the exponential search space on hard instances. Recent works that combine traditional search methods, such as best-first search and Monte Carlo tree search, with Deep Neural Networks' (DNN) heuristics have shown promising progress and can solve a significant number of hard planning instances beyond specialized solvers. To better understand why these approaches work, we studied the interplay of the policy and value networks of DNN-based best-first search on Sokoban and show the surprising effectiveness of the policy network, further enhanced by the value network, as a guiding heuristic for the search. To further understand the phenomena, we studied the cost distribution of the search algorithms and found that Sokoban instances can have heavy-tailed runtime distributions, with tails both on the left and right-hand sides. In particular, for the first time, we show the existence of \textit{left heavy tails} and propose an abstract tree model that can empirically explain the appearance of these tails. The experiments show the critical role of the policy network as a powerful heuristic guiding the search, which can lead to left heavy tails with polynomial scaling by avoiding exploring exponentially sized subtrees. Our results also demonstrate the importance of random restarts, as are widely used in traditional combinatorial solvers, for DNN-based search methods to avoid left and right heavy tails.

Left Heavy Tails and the Effectiveness of the Policy and Value Networks in DNN-based best-first search for Sokoban Planning
Dieqiao Feng
Carla Gomes
Department of Computer Science Cornell University dqfengocs. cornell.
Department of Computer Science
Comell University gomesOcs cornell. edu
Bart Selman
Department of Computer Science
Cornell University
selman@cs. Balman@css.ornell.ccm
Abstract
Despite the success of practical solvers in various NP-complete domains such as SAT and CSP as well as using deep reinforcement learning to tackle two- player games such Go, certain classes of PSPACE-hard planning problems have remained out of reach. Even carefully designed domain-specialized solvers can fail quickly due the exponential search space on hard instances. Recent works that combine traditional search methods, such as best-first search and Monte Carlo tree search, with Deep Neural Networks' (DNN) heuristics have shown promising progress and can solve a significant number of hard planning instances beyond specialized solvers. To better understand why these approaches work, we studied the interplay of the policy and value networks of DNN-based best-first search on Sokoban and show the surprising effectiveness of the policy network, further enhanced by the value network, as a guiding hcuristic for the search. To further understand the phenomena, we studied the cost distribution of the search algorithms and found that Sokoban instances can have heavy-tailed runtime distributions, with tails both on the left and right-hand sides. In particular, for the first time, we show the existence of left heavy tails and propose abstract tree model that empirically explain the appearance of these tails. The experiments show the critical powerful heuristic guiding the search, which
role of the policy network lead to left heavy tails with polynomial scaling by avoiding exploring exponentially sized subtrees. Our results also demonstrate the importance of random restarts, as are widely used in traditional combinatorial solvers, for DNN-hased search methods to avoid left and right heavy tails.
Introduction
Combinatorial search is key domain for artificial intelligence. Unfortunately, combinatorial domains commonly have intractable theoretical complexity. such as NP-complete, PSPACE-compie complete, even undecidable. In the past few decades, we have observed tremendous progress for practical problem- solving in NP-hard domains with wide applicability in, for example, circuit design Hong et al. 2010 hardware verification Gupta al. [2006), and mathematical discovery Konev and Lisitsa [014]. SAT solvers based conflict-driven clause learning solve instances with thousands of variables
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

and clauses in seconds, which demonstrates surprising scaling performance despite SAT being an NP-complete task (Silva and Sakallah [2003).
In contrast, practical combinatorial search in PSPACE-hard domains has remained a significant challenge. PSPACE-hard problems be generally divided into two main categories: 1wo-player
games, such as Go, Chess, and Amazons Lichtenstein and Sipser| [980], Fraenkel and Lichtenstein [981]. Hearn 2005]. and single-agent planning problems (a. combinatorial puzzles), such as Sokoban and problems formalized by PDDL (Planning Domain Definition Language) Culberson [997]. , Bylander 1994]. Recent achievements in the deep learning community inspired an approach of augmenting Monte Carlo Tree Search (MCTS) with Deep Neural Networks' (DNN) guidance. AlphaGo Silver et al.] [2016] became the first Go software to beat professional human players in 2016, and its newer and more general version AlphaZero [ilver et al. [2017] can achieve, tabula rasa, superhuman performance in many other challenging game domains.
These advances naturally raise the question of whether we can build a general framework to learn different single-agent planning domains with minimum modifications. A key challenge is that hard planning instances may require intricate action sequences with hundreds of steps, and any deviation can lead to a dead-end state with no path goal states. To address this issue, more systematic and complete search, such as best-first search, is preferred over MCTS Agostinelli et al. 2019). Crippa al. 2022]. Traditional search methods augmented with neural network guidance have shown promising progress in planning domains Shen et al. (2020). Rivlin et al. [2020), |Ferber et al. [2020).
Feng et al. 22200a b). These methods can solve a significant number of hard planning instances that specialized solvers cannot solve. To gain better understanding of these approaches, we studied the interplay of the policy and value networks in DNN-based Best-First Search (DBFS) algorithms. Our experiments show the surprising effectiveness of the policy network, further enhanced by the value network, as a guiding heuristic.
To further understand the phenomena, we also studied the cost distribution of DBFS. Specifically, we explored and generalized the cost distribution profiles of search methods from NP-hard domains to PSPACE-hard planning domains, and show heavy-tailed cost distributions exist ubiquitously among planning instances. For the first time, we found and characterized left heavy tails, which are different from well-studied right heavy tails (also abbreviated as heavy tails in the literature). Left heavy tails occur when instances become extremely hard and most runs cannot finish in reasonable time limit. The solver needs to be "lucky" to occasionally hit one short run. In contrast, right heavy tails characterize mildly hard instances whose majority randomized runs have short runtime. Nevertheless, the solver can be "unlucky" and occasionally hit an extremely long run, which makes the expected runtime exponential. We propose an abstract search tree model that can explain the appearance of left heavy tails and provide extensive experiment data supporting our model. The experiments show the critical role of the policy network as a powerful heuristic guiding the search, which can lead to left heavy tails with polynomial scaling by avoiding exploring exponentially sized subtrees.
Randomized combinatorial solvers use various techniques, such as randomized tie-breaking and random variable ordering, to carefully inject a controlled amount of randomization into deterministic Crawford and Baker [1994), [Bresina| [1996), Gomes et al. [1998]. The randomization step requires careful engineering and analysis of the solver since excess randomization can hamper the effectiveness of random restarts. In our approach, we found that imcertainty-awar
search procedureCrawforrd
networks Huang et al. [0017), Chua et al. [2018), Sedlmeier et al. [2019). Malinin and Gales (2018) can provide just the right amount of controllable randomization into a deterministic search algorithm.
While we focus on Sokoban in this paper. we stress that our approach only uses the minimum domain knowledge required to describe any planning problem, namely, the state representation, the state- action transition function, and the routine deciding goal states. To make our results more general, we evaluated more than 10, 000 Sokoban instances with significant variations in the underlying combinatorial structure.
Our results also demonstrate the importance of random restart strategies, as are widely used in traditional combinatorial solvers, for Deep Reinforcement Learning (DRL) to avoid left and right heavy tails. In summary, our overall contributions are as follows: (1) We studied the interplay of the policy and value networks in DBFS for Sokoban. Our experiments show the surprising effectiveness of the policy network, further enhanced by the value network, as a guiding hcuristic for the search.
(2) We studied the runtime distribution on more than 10, 000 instances and propose distribution-
2

---

independent statistics to quantify the heaviness of tails and effectiveness of random restarts. For the first time, we empirically studied left heavy tails from experiment data, introduce an abstract search Iree model with critical nodes, and formally show how left heavy tails can arise during the search. We explained the left heavy-tailed behavior of runtime distributions with the critical role of the policy network as guiding heuristic. Polynomial runtime scaling can occur because the policy network helps avoid exploring exponentially sized subtrees during the search. (3) We show the importance of using uncertainty- controllable amount randomization to a deterministic solver. We show how a restart strategy can improve DBFS's s effectiveness. In particular, our experiments show for larger budgets, more frequent restarts can be more effective.
networks in planning and how it can add
Background and Related Work
Sokoban as a planning domain. Sokoban is PSPACE-complete puzzle whose goal is to push boxes into the same number of goal cells in a grid maze with walls Culberson [197]]. Sokoban is among the most challenging known Al planning domains. The domain remains challenging even for specialized solvers with significant human knowledge Fern et al. [2011), I, Junghanns and Schaeffer (200T) Due to its general search structure and hardness, we use Sokoban as our background domain throughout the paper.
Optimal speedup of Las Vegas algorithms. Let A be randomized algorithm that always outputs the correct answer when it halts but whose running time is a random variable y - -> IR- Luby et al. 1993) proved that when we have full knowledge about the distribution yー the optimal strategy that achieves the minimum expected time required to obtain an output from A is to repeatedly run A for the same amount of time f until halts. To calculate t let
((t) Exse r (x)
(t ΣΣ (1) #<T DS
be the expected halting time of repeatedly running A with time limit t. Define 1 = inf I(t) and I is finite for any non-trivial distribution r i.e., (20) < 1. Let 1 be any finite value of t such that ((t) = A-, if such a value exists, or t = oo otherwise. Luby et al. [993 also showed that when A is unknown, the universal strategy that runs A for time limit
2, 1, 2,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
can achieve estimated halting time O log((A)) for any randomized algorithm A. This bound is optimal among all universal strategies.
Right heavy tails randomized search. Gomes et al. 2000 2005) observed randomized search on SAT and CSP can exhibit right heavy tails, in particular for so-called under-constrained instances, i.e., most randomized runs on the same instance halt in a relatively short time while non-negligible fraction of extremely long runs makes the average running time exponential. Right heavy tails have been observed in other domains such as theorem proving. planning, and scheduling |Miier et al. 2001), Cohen and Beck 22018). Gomes et al. [2000] formalized the runtime with the Pareto-Lévy form
P(X x) Cx- 0
and showed random restarts can dramatically reduce the runtime variance and potentially eliminate right heavy tails.
Uncertainty-aware network. There is a line of research on the uncertainty of neural networks reduce test error, provide confidence estimate, and improve model-based reinforcement learning Huang et al. [2017]. Chua et al. (2018), Sedlmeier et al. (201)) Malinin and Gales (2018). Our method augments neural networks with Monte Carlo (MC) dropout introduce randomization to deterministic search engines Gal and Ghahramani 2016). MC dropout enables dropout layers during testing and the dropout rate can control the amount of randomization. For our experiment, the uncertainty comes from two main sources: (1) the distributional mismatch between the training and test datasets; (2) noises the training data since the remaining distances found by specialized solvers are not optimal. See Section 3 for more details about data preparation.
hatps://ociisor//A1181..0
3

---

Table 1: Comparison with previous DRL works Sokoban
RELATED WORKS
AVG WIDTH
AVG HEIGHT
AVG SIZE
AVG BOXES
12AS RAASIICERRRR AL.
2017
10
10
100
4
PHS ORSEAU AND LELIS
202T
10
100
FENG ET AL 2020AJ.
SHOHAM AND ELIDAN
2021
19
247
16
OUR SETTING
12.0
13.6
183.5
20.2
3 Formal Framework
Policy-guided best-first search. Best-first search is an informed search algorithm, which explores graph by expanding the most promising node chosen according an evaluation function f() from the open set (search boundary nodes). f(z) can use both the knowledge acquired so far while exploring the graph, denoted by g(n), and heuristic function h(n). which estimates the remaining distance to the nearest goal state. Starting from the start state, best-first search gradually enlarges the current search graph by consecutively expanding function (n) and moves n to the closed set (expanded nodes). The search considers duplicate state detection and merges different nodes with the same state into single node. Sokoban has unit cost so that (n) equals the depth of n. The heuristic function ((n) is estimated using a value network, which is explained in detail below.
node that minimizes the evaluation
Orseau and Lelis [021] proposed Policy- Policy-guided guided Heuristic Search (PHS) to further learn a policy network, which takes state input and outputs vector of action probabilities p with components p(a|s) s) for each valid action a s. Specifically, they adapted the evaluation function to
f(n) g(n) + h(n) (n)) = p(s1(so) ... ((Sm|sm-))
(n)
where (No.... 8m)) is the sequence of states from the root node n. Orseau and Lelis 2021 also proposed PHS* a variant of PHS, that uses the evaluation function f(n)
g pin|+Ain
((n) +a())
Both PHS and PHS* require computing the cumulative product of probability predictions among the whole path from the root n. In this paper, the predicted probability of the parent node of n:
evaluation function that only depends
g(n) + h(n)
f(m)
p(n parent(n))
Experiments show using this simpler evaluation function can consistently solve more instances.
Data preparation. The study of the complexity and practical performance of search methods is greatly hampered by the difficulty in collecting realistic problem instance data. As an alternative, researchers heavily resort procedurally generated instances highly structured problem domains
Taylor and Parberry [2011]. Guez et al. [2018). The randomly generated instances lack sufficient structure and their underlying combinatorial search space is, in some sense, too regular.
To bridge this gap, we collected all the 10, 871 Sokoban instances from the Sokobano website All these instances were designed by different human authors in the past few decades, have great variation in the underlying structure, serve as the benchmark for specialized solvers, and exhibit practical interest for humans solve. The dataset is orders of magnitude larger than the ones used in previous works on DRL and provides a great challenge for deep heuristic learning. See Table for Sokoban board statistics compared with previous works. Note that the difficulty of Sokoban grows exponentially as the number of boxes increases.
To generate supervised training data, ran Sokolution state-of-the-art Sokoban solver, to compute ground truth plans. Sokolution can solve 8272 out of 10871 total instances given 10-minute time limit. We randomly divided the solved 8272 instances into training set (7435 instances) and a test set (827 instances). For the remaining unsolved 2609 instances, we randomly sampled 200 instances and reran Sokolution with extended 2-hour time limit. 137 out of the 200 instances remained
http://wwww.ooooeeeee///wee..// http://coodeaaalliis htossooon

---

Table 2: Search statistics of solved instances the training and hard datasets (time limit: 10 mins).
TRAINING DATASET
HARD DATASET
EXPANDED
TIME
SOLVED
NODES PER SEC
EXPANDED
TIME
SOLVED
SOKOLUTION
191436
3
100%
618
0%
DBFS
13776
S
93%
37
18651
537
69%
unsolved. We then collected these 137 instances as the hard set to further study the cost distribution of instances much harder than the training instances. For each found plan (so; 01; 81, On 8n) from the start state so to the goal state Sn, we generated training tuples le, Us with policy label
l, = 0++1 and remaining distance label Us.
as training data.
Feng et al. [2026)] used PUSH as basic actions and achieved the state-of-the-art performance of DRL for Sokoban. In this work, we use the more elementary action MOVE. One PUSH action can be divided into two parts: 1) moving to the correct adjacent cell for pushing a box; 2) pushing a box. As result, PUSH requires more domain knowledge of Sokoban the framework must compute all reachable cells from the current player position and decide which boxes are pushable. The number of valid PUSH actions can grow linearly on the number of boxes. In contrast, MOVE only consists of four actions (four directions), and way less domain knowledge needed to decide valid moves for any state. Using MOVE basic actions will generate plans that are, average, 3-4 times longer than ones generated with PUSH actions. Most instances considered in this paper have plans containing hundreds thousands of moves, which provides a great challenge for AI planning.
Network architecture and training details. For each board state of height and width W, we created an input tensor of shape [4 H x W| with four multi-hot feature maps encoding the player position, box positions, goal cells, and player reachable cells (ignoring all boxes), respectively. The policy head outputs vector of length four representing the probability distribution among four moving directions. The value head outputs a single scalar representing the logarithm of the estimated remaining distance. The network consists of multiple convolutional residual blocks and each block has two extra dropout layers to introduce randomization. See Appendix for more details.
The parameters 0 of the deep neural network are trained with the following loss function:
loss = (log(h) log(v log(pt.) + c|0/
where e is the weight decay parameter controlling L2 weight regularization.
Monte Carlo dropout. To introduce uncertainty, we used the same dropout- architecture
from Gal and Ghahramani [2016). We did grid search for the dropout ratio and found 30% reached the best performance. The level of randomization is consistent and insensitive among > 100, 000 instances. We thus used dropout ratio 30% as the default setting for all experiments in the following sections.
4 The Interplay of the Policy and Value Networks
In this section, we first show the performance comparison between DNN-guided search and special- ized solvers, and further show how different evaluation functions affect the overall performance.
Sbble search statistics of Sokolution, state-of-the-arr solver of Sokoban, hh()+ and DBFS with the evaluation function (n) p(n pa)) We used cores of Xeon 6154 CPUs for profiling both solvers and ran networks on the CPU mode for a fair comparison. DBFS expands significantly fewer nodes per second than Sokolution (about factor of 17) due to the heavy cost of heuristic evaluation. Nevertheless, given 10 minutes, DBFS can solve 69% hard instances that Sokolution cannot solve even given a 2-hour time limit. So, the trained deep net provides much superior search guidance than the hand-crafted guidance in Sokolution.
Search statistics.
Effectiveness of policy and value networks. Table 3 shows experiment results for different choices of the evaluation function. Term p. h, and d represent policy, value, and depth information, respectively. As shown in the table, the policy hearistic has significuntly larger impact than the value heuristic. Specifically, the table shows that even the Pure Policy (using only the 1/p term, i... inversely proportional to the policy prediction) significantly boosts performance compared to
5

---

Table 3: Solving ratio the test dataset with various evaluation function f(n) of best-first search,
depending on depth d(n) (equal to g(n)), estimated remaining distance h(n), estimated action probability p(als), and cumulative path probability (n.). Columns represent different search budget.
NUMBER OF TOTAL NODE EXPANSIONS (CPU RUNTIME BELOW)
METHOD
1. 000
2,000
4, 000
8,000
16, 000
32, 000
0.5 MINS
0.9 MINS
1.8 MINS
3.8 MINS
7.4 MINS
14.5 MINS
No Policy
BREADTH HRST
d
0.32%
1.28%
1.92%
3.21%
6.73%
11.2%
GREEDY
h
4.17%
8.01%
12.5%
15.1%
19.2%
19.6%
DEPTH VALUB
d+
5.77%
10.3%
13.5%
19.9%
21.5%
25%
DEPTH VALUE
d
6.09%
8.97%
14.7%
17.6%
19.6%
22.8%
With Policy
Pure Policy
1/p
28.2%
32.1%
36.9%
40.4%
42.9%
44.6%
PIIS
(d 1 b
15.7%
19.9%
23.7%
26.3%
29.2%
31.4%
PIIS
(d 1
28.5%
31.4%
38.5%
40.1%
44.9%
46.2%
POLICY GREEDY
h/p
31.7%
32.4%
37.5%
38.8%
41.0%
41.3%
OURS
(d h)/P
32.4%
34.3%
38.8%
43,3%
46.2%
50,0 %
OURS
(d + 2.0 1t)p
31.7%
34.0%
39.4%
42.0%
45.8%
48.1%
exponential ta
plant both tails
2.0
6.8
5.6
1.7
201
1.7
1.7
1.7
177
121
107
30"
107
1.77
307
107
1.7
10'
3.8
3.0
heawy expeoveniall
2.8
0.5
16
107
307
107
300
307
Figure 1: Each subplot shows runtime statistics of DBFS with MC dropout augmented Sokoban instances. Each curve represents multiple runs on the same instance (instances differ for different curves). We compare the runtime sample mean, optimal sample restart time t expected sample total runtime with restart ! and expected total runtime of the universal strategy iS univ as defined in Section 5
all value (the h term) heuristics-based search strategies without the policy guidance. (See the rows above "Pure Policy" Table 3 With extra properly added depth and value terms, the performance of Pure Policy can further increase to obtain our best strategies.
To further study why the policy network more effective, we studied the performance of both networks in detecting
Table Dead-end detection accuracy
dead-end states. Detecting dead-end states is erucial to avoid exponential run times because the search has to recover from exploring those states. In particular, we randomly sampled 2000 board states from each dataset. For each state, used Sokolution detect dead-end successor states. The policy/value network is considered successfully detect a state if it predicts a higher/lower policy/value to the child on the ground truth plan than any other dead-end child. Table Table that the policy network significantly outperforms the value network detecting dead-ends, providing better search guidance.
Train
Test
Hard
Policy Value 41%
93%
81 %
68 %
38%
37%
Analysis of Left Heavy Tails
In Section 4 31% % instances of the hard dataset remained unsolved. We increased the search budget and studied the runtime distributions of these challenging instances and found they possess heavy tails on the left-hand side. In this section, study this behavior in further detail.

---

sohied rantima
Figure 2: Subplots show results of randomized DBFS for the training, test, and hard datasets. Each red dot represents single instance. We perform 200 randomized searches each instance with maximum of 300, 000 node expansions. The X-axis the average runtime of all solved runs and the Y-axis is the unsolved percentage. Purple areas represent instances with left heavy tails while cyan areas represent right heavy tails.
Sample statistics about the heaviness of tails. Luby's optimal restart strategy requires full knowl- edge about the runtime distribution r- of a randomized algorithm A. Here we introduce sample statistics that can approximate the theoretical optimal values. Specifically, for each planning instance, we performed multiple randomized searches on it with maximum search budget M and collected a runtime sample S. The runtime of failed searches was capped as M. We approximated the optimal sample restart time t and expected sample total runtime with restart 1 as
u |S]
1 arg min aES
Holu E S and < uHl'
Hulu E S and 1S
Let == 21,1,2,1,,1,,444 be the time limit sequence of the universal strategy. To approximate the expected total runtime is of the universal strategy on S, let a, be the expected total runtime of applying (T,T T:+2...) on and we have the constraint
a,+1 [S]
a =T H S and > T.H univ
a1
We calculated until the first such that T; 2 .M and set the remaining a; to zeros.
Figure T shows runtime statisties for different types of tails. Both left and right heavy tails exhibit orders of magnitude reduction of 1S and Ss unis over the runtime sample mean, which demonstrates the benefit of using random restarts. For exponential tails, the expected sample total runtime with restart is very close to the sample mean, and the universal strategy even has a negative effect.
To separate the two types of heavy tails, for each instance, compared the average runtime of solved randomized runs v.s. the unsolved ratio, as shown in Figure 2 We added further restrictions that right/left heavy tail requires the unsolved ratio to be less/greater than 10%/90%. For experiment budget concerns, we only plotted 10% randomly sampled instances from the training and test datasets. Figure shows the training dataset has similar number of left and right heavy-tailed instances. with most instances not showing the heavy- behavior. For the hard dataset, the percentage of right heavy tails decreases significantly. with more instances shifting to the top side of the figure and entering the left heavy-tailed area. We hypothesize that left heavy tails occur more frequently when the underlying combinatorial structure becomes harder. Though random restarts eliminate heavy tails on both sides, left heavy tails provide further intuitions and implications for curriculum learning for DRL. In particular, they can benefit from distributed solving procedure in which any solution found with one process can be shared and learned by the curriculum framework Weng 2020 Narvekar and Stone [2018), Narvekar et al. 20200.
Abstract search tree model. Chen et al. 2001 proposed an imbalanced tree model to empirically explain right heavy tails. Here propose abstract tree model to empirically characterize left heavy tails. See Figure for the description for both models.
Search models for planning problems differ from ones for SAT and CSP. For NP domains, the number of unassigned variables is fixed with O(n) where n the problem size, and the search can assign these variables in any order. For planning domains, the search must assign actions in order from
7

---

Magst
lop
Figure 3: Left panel: imbalanced tree model for right heavy tails. Right panel: our proposed model for left heavy tails. In the left model, p the constant probability of missing backdoor. the right model, p is the constant probability of picking the right action to the goal.
Figure 4: Two typical search graphs of DBFS. We removed graph edges form spanning tree for clearer illustration. The search graph was built from the left to the right. The red dashed path the plan leading from the start state to one goal state, while blue circles are critical nodes, which have exponential sub-search tree underneath without a near goal state.
the start state to goal state with potentially maximum exponential length. Our proposed model hypothesizes the existence of (log(n)) critical nodes from which a wrong child node expanded by the search will result in extra exponential search space. As shown in follows, our model does not depend on the actual choice of p as long as p is a constant value the range (0, 1).
Theorem 5.1. (The abstract tree model has exponential runtime almost surely). When restricting plans to polynomial length the input size n, the probability that the abstract tree model has exponential runtime converges to I as n goes infinite. The proof is deferred to Appendix
Theorem 5.2. (Restart achieves polynomial expected halting time). The optimal expected halting time with restart A and expected halting time using the universal strategy 1-A inss are both (pply(n)).. The proof is deferred to Appendix
Theorem 5.1 states the runtime of the model is exponential on the input size n almost surely, and Theorem 5.2 shows that the cost distribution has polynomial estimated runtime with restarts. These two theorems combined show the occurrence left heavy tails. For most nodes on the plan, the deep neural network either provides accuracy heuristics to expand the correct child node makes a small error of preferring one wrong child node. As long as the error small, the search can recover from with extra polynomial steps since the evaluation function penalizes deeper nodes. For the ( (n)) critical nodes, the eтror of predicted heuristics is so large that exponential search needed to jump out from the local search space.
Structure real search graphs. To empirically examine our abstract model, we plotted two typical search graphs generated by DBFS as shown in Figure We found that most nodes actually do not incur search. Networks' heuristics either directly lead the search to the correct child node, or only small wrong subtree (less than 5 nodes) is expanded. Critical nodes (labeled blue circles) are extremely rare in the search graph. However, when encountering such critical nodes, the search expands large subtree with near goal.
Whether AI planning systems can discover macro action routines, i.e., sequence of algorithmic actions to perform sub-goal, has great interest for researchers. To make long plan, e.g., prove a hard mathematical theorem, humans usually only make some critical choices lemmas and schemes, and fill the remaining parts of the proof with little reasoning. Indeed, the number of required crucial intermediate lemmas to prove a mathematical theorem is quite small, even for challenging open problems. However, extensive and profound reasoning, search, and enumeration needed to find

---

(b) Unsolved fraction of instances with without restarts. Given fixed amount of search budget (number of nodes allowed to expand), n-restart means to evenly divide the search budget into n individual runs and union their solved instance sets as the final result.
(a) Subtree size v.s. total number of occurrence 300 randomly sampled instances (in log-log scale).
Figure 5: Two plots about the details of the search.
such lemmas. The small number of critical lemmas compared with the long proof length reflects the prototype of such search graphs. In our experiment setting, we use MOVE as basic actions. To perform real PUSH, the search algorithm must compute all reachable cells from the player's position and calculate the shortest path to the cell adjacent to the box to push. Such long sequence of moves before performing
actual push can be viewed as routine. As shown in Figure 4 the algorithm can perform a long chain of moves with little local search, which suggests that macro action routines might be implicitly learned part of neural networks' heuristics.
Relation backdoors. The proposed model has close relation to backdoors of typical case complexity. To explain why solvers scale well in areas such as planning and finite model-checking, Williams et al. (2003) examined various benchmarks and identified that for most practically solvable problem instances, after assigning values to logurithmic variables, the remaining problem instance quickly becomes polynomially solvable by propagating constraints. This result illuminates the prototypical patterns of the structure causing the empirical behavior observed in the International Planning Competitions benchmarks Vallati et al. (2015). Cohen and Beck [2018) Meier et al. [2014)
More experiment data about the abstract tree model. To better illustrate the occurrence proba- bility of different sizes of sub-search space, we randomly sampled 300 solved instances from the test dataset and counted the number of dead subtrees (no near goal exists) for each size. As shown in Figure 5a in log-log scale, the size of subtrees and occurrence have a near-linear correlation. The figure empirically confirms our abstract tree model that critical nodes that incur extra exponential search space have logarithmic occurrence. And shows how left heavy tails occur in practical planning solving.
Hoffmann al. (2006) explained SATPLAN, classical planning as SAT, with backdoor models. In particular, after finding and assigning logarithmic variables, the remaining problem solving becomes polynomial. In contrast, identifying these backdoors not required for expand-style search algorithms in planning. Left heavy tails are not only caused by the underlying structure of practical instances but also affected by the mysterious generalization power of neural networks. is an interesting future research direction to understand the surprising scaling performance of various heuristics, from conflict-driven clause learning for SAT solving to DNN-based search methods.
Solving more instances with random restarts. The theory of heavy-tailed cost distribution suggests that sequence of short runs instead of single long run make better use of fixed amount of computational budget. We explored this idea by considering fixed number of total expanded nodes allowed for the search. Figure 55b) shows the probability of not solving the instances for the test dataset. The failure rate of a single run drops the fastest for small amount of computational budget. With more total expanded nodes, random restarts gradually achieve better performance. Specifically, to solve more instances, the solver needs to increase the total number of compute cycles. When doing so, the figure shows there comes a point where more frequent restarts are more effective. For example, with budget of around 2,000 nodes, the strategy with 2 restarts becomes more effective than no restarts. At around 5,000 nodes, 5-restart becomes more effective than 2-restart. So, to solve larger fraction of hard instances, more frequent restarts become more effective.

---

Conclusions
We studied the use of policy (action selection) and value (remaining distance estimate) functions as well as randomization methods for solving hard planning instances using best-first search. Our experiments show the remarkable effectiveness of the policy network and random restarts for the search. The value network provides additional global search guidance.
We show that uncertainty-aware networks provide effective way to introduce randomization into the search process leading to increased efficiency. Our runtime distribution results show heavy-tailed distributions with tails both the left and right-hand sides. Left heavy tails have not been observed in combinatorial search before. We also introduce an abstract computational model that explains left heavy tails. Finally, we show how random restarts can improve the overall search effectiveness. With larger search budgets, restarts can be increasingly effective.
10

---

References
Forest Agostinelli, Stephen McAleer, Alexander Shmakov, and Pierre Baldi. Solving the Rubik's cube with deep reinforcement learning and search. Nature Machine Intelligence, 1(8):356-363, 2019.
John I. Bresina. Heuristic-biand stochastic sampling. In AAAI/IAAI, Vol. 1, pages 271-278, 1996.
Tom Bylander. The computational complexity of propositional STRIPS planning. Artificial Intelli- gence, (9(112):163 25:1622204 1994.
Hubie Chen, Carla Gomes, and Bart Selman. Formal models of heavy-tailed behavior in combinatorial search. In International Conference on Principles and Practice of Constraint Programming, pages 408-421. Springer, 2001.
Kurtland Chua, Roberto Calandra, Rowan McAllister, and Sergey Levine. Deep reinforcement learning in handful of trials using probabilistic dynamics models. Advances in Neural Information Processing Systems, 31, 2018.
Eldan Cohen and J Christopher Beck. Fat-and heavy-tailed behavior in satisficing planning. In Thirty-Second AAAI Conference Artificial Intelligence, 2018.
James M Crawford and Andrew Baker. Experimental results on the application of satisfiability algorithms to scheduling problems. In AAAI, 1994.
Mattia Crippa, Pier Luca Lanzi, and Fabio Marocchi. An analysis of Single- Monte Carlo Tree
Search performance Sokoban. Expert Systems with Applications, 192: 16224, 2022.
Joseph Culberson. Sokoban is PSPACE-complete. 1997.
Dieqiao Feng, Carla P. Gomes, and Bart Selman. Solving hard Al planning instances using curriculum- driven deep reinforcement learning. In Christian Bessiere, editor, Proceedings of the Twenty-Ninth International Joint Conference Artificial Intelligence, IJCAI 2020, pages 2198 2205. ijcai.org, 2020a. doi: 00224963/jcai,
URL htttt:////dot org/ 100. 24963/ijcai... 2020/.20233344
Dieqiao Feng, Carla P Gomes, and Bart Selman. A novel automated curriculum strategy to solve hard sokoban planning instances. Advances in Neural Information Processing Systems, 33, 2020b.
Patrick Ferber, Malte Helmert, and Jörg Hoffmann. Neural network heuristics for classical planning: A study of hyperparameter space. In ECA/ 2020, pages
IOS Press, 2020.
Alan Fern, Roni Khardon, and Prasad Tadepalli. The first learning track of the international planning competition. Machine Learning, 84(1-2):81 2011.
Aviezri S Fraenkel and David Lichtenstein. Computing a perfect strategy for nx chess requires time exponential in n. In International Colloquium on Automata, Languages, and Programming, pages 278 773..99..00 Springer, 1981.
Yarin Gal and Zoubin Ghahramani. Dropout as a bayesian approximation: Representing model uncertainty in deep learning. In international conference on machine learning. pages 1050-1059, PMLR, 2016.
Carla P Gomes, Bart Selman, Henry Kautz, et al. Boosting combinatorial search through randomiza- tion. AAAI/IAAI, 98:431 437,, 1998.
Carla P Gomes, Bart Selman, Nuno Crato, and Henry Kautz. Heavy-tailed phenomena in satisfiability and constraint satisfaction problems. Journal of automated reasoning, 24(1):67-100, 2000.
Carla P Gomes, Cesar Fernández, Bart Selman, and Christian Bessiere. Statistical regimes across constrainedness regions. Constraints, 10(4)337-337, 2005.
Arthur Guez, Mehdi Mirza, Karol Gregor, Rishabh Kabra, Sebastien Racaniere, Theophane Weber, David Raposo, Adam Santoro, Laurent Orseau, Tom Eccles, al. An investigation of Model-free planning: boxoban levels, 2018.

---

Aarti Gupta, Malay K. Ganai, and Chao Wang. SAT-basee verification methods and applications in hardware verification. In Marco Bernardo and Alessandro Cimatti, editors, Formal Methods for Hardware Verification, 6th International School on Formal Methods for the Design of Computer. Communication, and Software Systems, SFM 2006, Bertinoro, Italy, May 22-27, 2006, Advanced Lectures, volume 3965 of Lecture Notes in Computer Science, pages 108- 143. Springer, 2006. doi: 10. 1757283L.. URL hattps://doi.
Robert A Hearn. Amazons is PSPACE-complete. arXiv preprint cs/0502013, 2005.
2005.
Jörg Hoffmann, Carla P Gomes, and Bart Selman. Structure and problem hardness: Goal asymmetry and DPLL proofs in SAT-based planning. In ICAPS, pages 284-293, 2006.
Ted Hong, Yanjing Li, Sung-Boem Park, Diana Mui, David Lin, Ziyad Abdel Kaleq, Nagib Hakim, Helia Naeimi, Donald $ Gardner, and Subhasish Mitra. QED: Quick error detection tests for effective post-silicon validation. In 2010 IEEE International Test Conference, pages 1-10. IEEE, 2010.
Gao Huang, Yixuan Li. Geoff Pleiss, Zhuang Liu, John E Hoperoft. and Kilian Q Weinberger. Snapshot ensembles: Train get for free. arXiv preprint arXiv: /704. 00109, 2017.
Sergey Toffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International conference on machine learning, pages 448-456 PMLR, 2015.
Andreas Junghanns and Jonathan Schaeffer. Sokoban: Enhancing general single-agen search methods using domain knowledge. Artificial Intelligence, 129(1-2):219--2) 251,, 2001.
Boris Konev and Alexei Lisitsa. A SAT attack on the erdós discrepancy conjecture. In International conference on theory and applications of satisfiability texting, pages 219-226. Springer, 2014.
David Lichtenstein and Michael Sipser. Go is polynomial-space hard. Journal of the ACM (JACM), 27 1980.
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. arXiv preprint 17X1501711.05101, 2017.
Michael Luby, Alistair Sinclair, and David Zuckerman. Optimal speedup of Las Vegas algorithms. Information Processing Letters, 17-4)0173-180, 1993.
Andrey Malinin and Mark Gales. Predictive uncertainty estimation via prior networks. arXiv preprint 180.v:1802.10501, 2018
Andreas Meier, Carla Gomes, and Erica Melis. Heavy-tailed behavior and randomization in proof planning. In Workshop on Model-Based Validation of Intelligence on AAAI Spring Symposium, 2001.
Andreas Mcier, Carla P Gomes, and Erica Melis. Randomization and restarts in proof planning. In Sixth European Conference on Planning, 2014.
Sanmit Narvekar and Peter Stone. Learning curriculum policies for reinforcement learning, arXiv preprint arXiv: 11882200288 2018
Sanmit Narvekar, Bei Peng. Matteo Leonetti, Jivko Sinapov, Matthew E Taylor, and Peter Stone. Curriculum learning for reinforcement learning domains: A framework and survey. arXiv preprint 04X100 2020.
Laurent Orseau and Levi HS Lelis. Policy-guided heuristic search with guarantees. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pages 12382- 2021.
Sébastien Racanière, Théophane Weber, David Reichert, Lars Buesing, Arthur Guez, Danilo Rezende, Adria Puigdomenech Badia, Oriol Vinyals, Nicolas Heess, Yujia Li, et al. Imagination- augmented agents for deep reinforcement learning. In Proceedings of the 3 International Conference Neural Information Processing Systems, pages 5694-5705, 2017.
12

---

Or Rivlin, Tamir Hazan, and Erez Karpas. Generalized planning with deep reinforcement learning. arXiv preprint arXiv:2005.023000 2020.
Andreas Sedlmeier, Thomas Gabor, Thomy Phan, Lenz Belzner, and Claudia Linnhoff-Popi Popien.. Uncertainty-base out-of-distribution classification in deep reinforcement learning. arXiv preprini arXiv:2001.00499 2019.
William Shen, Felipe Trevizan, and Sylvie Thiébaux. Learning domain-independent planning heuristics with hypergraph networks. In Proceedings of the International Conference Automated Planning and Scheduling, volume 30, pages 574-584, 2020.
Yaron Shoham and Gal Elidan. Solving Sokoban with Forward-Backwerr Reinforcement Learning. In Proceedings of the International Symposium on Combinatorial Search, volume 12, pages 191-193, 2021.
Joao P Marques Silva and Karem A Sakallah. GRASP- a new search algorithm for satisfiability. In The Best of ICCAD, pages 73-89. Springer, 2003.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, loannis Antonoglou, Veda Panncershelvam, Mare Lanctot, et al. Mastering the game go with deep neural networks and tree search. nature, 529(7587):484444) 489, 2016.
David Silver, Thomas Hubert, Julian Schrittwieser, Toannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, al. Mastering chess and shogi by self-play with a general reinforcement learning algorithm. arXiv preprint 17X1011712.01885, 2017.
Joshua Taylor and Ian Parberry. Procedural generation of sokoban levels. In Proceedings of the International North American Conference on Intelligent Games and Simulation, pages 5-12, 2011.
Mauro Vallati, Lukas Chrpa, Marek Grzeš, Thomas Leo McCluskey, Mark Roberts, Scott Sanner, et al. The 2014 international planning competition: Progress and trends. Ai Magazine, 36(3): 90 98, 2015.
Lilian Weng. log. 2020. -aarraaauu-u--fr-rrreeooreeeeeee
Curriculum for Reinforcement Learning. hilianweng.eithubbioitit
URL https://1Slinnweng saanwenngggthhb. wwtggg....tttiiii... 1o/111111g//2220001/22
html
Ryan Williams, Carla P Gomes, and Bart Selman. Backdoors typical case complexity. In IJCAI, volume 3, pages 1173-1178, 2003.
13


Reviews:
[{"review_id": "ZXQT4z_Q54x", "reviewer": "Reviewer_1Asc", "summary": "This paper analyzes the behavior of DNN-based best-first search for solving Sokoban planning problems and discovers \"left heavy tails\" on the running time distribution from hard Sokoban instances. The main contribution of this paper is to show the existence of left heavy tails and the abstract search tree model that characterizes such behavior. There are also relatively minor contributions, such as modifying the f(n) and systematic comparison of various search configurations.\n", "questions": "In policy guided search, how did you compute p(n | parent(n) ) ?\n\nIn network architecture and training details, can you explain each term in the loss function? \n\nOn the contribution of this paper on the \"uncertainty aware network,\" Is there some part in the paper other than Monte Carlo dropout (line 185-188) explaining the details? The conclusion is the drop-out ratio of 30% is the best after the grid search. If we choose other ratios, would it change the analysis on left-heavy tails? I cannot find how this selection effectively introduced randomization to search.\n\nIn the effectiveness of policy and value networks, I was not able to understand the last sentence (lines 214-217). Can you explain how to detect dead-end children? what does it mean by \"predict a higher/lower policy/value to the child\"?\n\nIn sample statistics about the heaviness of tails, how t^{\\mathcal{S}} (lin 227) was given as an approximation of the optimal sample restart time?\n\nIn the abstract search tree model, is n the length of the plan for Sokoban problems or a total number of states?\nWhat is the implication of the number of critical nodes being O( log(n) )? Are the critical nodes must be nodes along the path from the root to the goal?\n\nThe proof in the Appendix, as well as the abstract search tree model, assumes the number of critical nodes is in O( log(n) ) and the non-critical node has a search space of size O( poly(n) ). From this assumption, the optimal expected halting time with restart is shown to be O( poly(n) ).\nFigure 1 also shows that the l^{\\mathcal{S}} (yellow) is much smaller than the mean running time (red line). Figure 5 (caption is missing) shows the abstract search tree model matches the data. How to apply this idea to designing a random restarting strategy? Is it mandatory to have strong heuristics such as policy networks? Is this implies dead-end detection is more important than estimating the cost to go more precisely?\n", "limitations": "I think this work is not relevant to this section.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The strength of this paper is through experiments on a very large number of Sokoban instances (over 10,000) and evaluations of various search configurations, which provides some evidence and explanations why search with DNN-based heuristic works well in practice.\n\nThe weakness of this paper is missing technical details.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "OHsfZHpx-Da", "reviewer": "Reviewer_TbFG", "summary": "The paper analyzes the performance of learned heuristics in best-first search for planning in Sokoban. The paper proposes a variant of the policy-guided best-first search for its experiments. The algorithm requires a node evaluation function and this paper proposes a simplified variant of the evaluation function in PHS* which requires, both, a value (distance to goal) prediction and an action prediction (P(n | parent(n))). The experimental setup uses a dataset of Sokoban instances designed by humans. Supervised training data for learning the distance to goal heuristic is generated by running an off-the-shelf Sokoban planner on these instances. A DNN with dropout (for randomization) (and policy and value heads) is used to learn the heuristic. The experiments compare different evaluation functions (with and without learned policies) and contain a number of interesting results. Using a learned policy significantly improves performance on hard Sokoban instances, outperforming the hand-crafted heuristic. Next, the use of action probability in the evaluation function improves performance over just using the learned values (distance to goal). Finally, the paper analyzes the runtimes for unsolved instances and discovers the existence of heavy tails on the left (mostly-long runs, few short runs). The paper develops some formalisms to characterize this behavior. The analysis and experiments suggest that a strategy involving more frequent restarts can improve overall performance in such cases.\n\n---------\n\nUPDATE: I thank the authors for their responses. After reading the other reviews, I'm more positively inclined towards the paper and have updated my scores to reflect this.", "questions": "  1. How is the randomization introduced by dropout useful? (I'm guessing it allows exploring a different part of the search space after a restart. Is this correct?) How important is dropout to the overall approach? Are there any other randomization schemes that can be considered besides dropout? How might they perform?\n\n  2. Besides Sokosolution and knowledge-guided BFS, are there any other known strong Sokoban solvers? (If not, this could be made clearer.)\n\n  3. (Minor). Figure 5 (a,b) are missing their labels.", "limitations": "The authors have not discussed the limitations or social impact of the work. Since this work explores general search algorithms, I don't see any major negative social impact.\n", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n  + The paper investigates into the performance of best first search with learned knowledge (DBFS) on challenging planning problems. This is an important and potentially impactful analysis of a popular learning to search method on a challenging problem.\n  + The paper includes a small algorithmic contribution (simplified eval function), a number of empirical insights into the performance of DBFS in Sokoban and an analysis of the phenomena of left heavy tails to better understand the unsolved problem instances.\n  + The DBFS algorithm can solve a significant fraction of hard problem instances, which the state of the art solver fails on. This seems like a significant performance improvement on hard Sokoban instances. (Right?)\n  + The paper investigates the hardest Sokoban instances and discovers the existence of left heavy tails. This seems like a novel insight, as far as I can tell.\n\nWeaknesses\n  - One of the main claims of the paper is that the randomization injected by dropout is important. However, I was unable to find any supporting evidence for the claim other than a single sentence (\"We did a grid search ... and found 30% reached the best performance\") The size of the performance gap with and without dropout is unclear to me. What have I missed?\n  - The paper is reasonably well written but I thought it didn't quite flow on my first reading. For example, the concepts of optimal speedup of Las Vegas algorithms and right heavy tails are briefly introduced early in the paper (Section 2) but only used to analyze the unsolved problem instances much later in Section 5. Introducing these concepts in Section 5 might improve the flow.\n  - The empirical contributions of DBFS could be made clearer. For example, is there any other solver which does better than DBFS on the hard dataset task in Table 2?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "2xIBQHtPNDX", "reviewer": "Reviewer_LGQB", "summary": "The authors attempt to understand the behavior of search in the planning domain when it is combined with a DNN-based heuristic function, namely in Sokoban. Their contributions include revealing the existence of left and right heavy tails, proposing an abstract tree model which explains this phenomenon and providing theoretical analysis. Their experiments show that policy networks can lead to avoiding exponentially large trees, which is an explanation to the efficiency of the DNN-based heuristic function. They finally show that random restarting plays an important role to avoid both tails. \n", "questions": "I do not have any specific question.\n", "limitations": "N/A\n", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The heavy-tailed distribution is a well-known phenomenon observed in many combinatorial search domains including SAT and CSP. This paper has a very interesting observation which does not occur in those domains but which newly occurs in the planning domains.\n\nOne very minor comment is that the acronym of DBFS has been already used in the following paper well known in the planning community. Therefore, I would recommend them to use a different acronym if possible. \n\nhttps://ojs.aaai.org/index.php/AAAI/article/view/8004\n\nAs a side node, this DBFS (Diverse Best-First Search) uses randomization to avoid the plateau of search due to heuristic values. It uses neither the notions of the left-heavy tails nor critical nodes. But perhaps Diverse Best-First Search might have some relations (e.g., why does avoiding the plateau leads to an improvement?) to these notions investigated by the authors, which might generate some important future research.\n\nIn summary, this is a very interesting paper and I enjoyed reading it. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "-zR845f0fvi", "reviewer": "Reviewer_7B9C", "summary": "The paper investigates DNN-based best-first search with policy and value networks for Sokoban planning. First, the paper studies PHS and PHS* and a variant proposed in this paper and find that policy networks learn effective heuristics for search and can be further enhanced by the use of value networks. Then, the paper empirically studies left heavy tails from experiment data and develop an abstract model that show how left heavy tails can arise during the search.\n\n\n----\nI thank the authors for their response.\n\nI think the paper would benefit from showing this phenomenon extends beyond a single domain and a single heuristic function, however I understand the limitation on computational resources and I think these results are of interest. I therefore increase my score by one point.\n\nI think the paper should include a discussion on the previous works discussing left heavy tails (including conjectures).", "questions": "- Did you experiment with other domains?\n- Did you find left heavy tails across different evaluation functions?\n- Did you experiment with different dropout values?", "limitations": "I did not identify any issues related to limitations and potential negative societal impact.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Interesting empirical results on effectiveness of DNN-based best-first search in Sokoban planning.\n- The discovery of left heavy tails in DNN-based best-first search in Sokoban planning.\n- A novel theoretical results that explains the occurrence of left heavy tails.\n\n\nWeaknesses:\n- The main weakness is the limited scope of work: \n\t* The paper focuses on a single planning domain. Sokoban is a well-known planning domain but as the paper seems to suggest left heavy tails are likely to occur in other practical planning problems (right heavy tails have been observed in many problems), experiments on other domains would significantly strengthen the work.\n\t* Unlike the results on the effectiveness of DNN-based best-first search, the results on the left heavy tails are not shown for multiple evaluation functions and it they appear across different evaluation functions.\n- In addition, I think some of the claims require further justification:\n\t* I think the claim that left heavy tails are shown for the first time needs to be more clearly justified in the paper as there are existing works that discuss left heavy tails (e.g., reference [18] in the paper).\n\t* I think the claim that the paper shows the importance of using uncertainty-aware networks in planning should be more carefully stated due to the narrow scope described above as well as the fact that experiments report results on only one dropout value (30%).\n- Minor points:\n\t* I think the citation style in the paper (\"[10] used ...\", \"[34] proposed ...\") is hard to read and it would be better to use the author names.\n\t* The supplementary material has some missing references presented as \"?\" such as \"Proof of ??\", \"By the result of (author?)\"\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept