The Remarkable Effectiveness of Combining Policy and Value Networks in A*-based Deep RL for AI Planning
Authors: Dieqiao Feng
Carla P Gomes
Bart Selman
Venue: ICLR 2022 Submitted (2022)

Abstract: Despite the tremendous success of applying traditional backtrack-style combinatorial search methods in various NP-complete domains such as SAT and CSP as well as using deep reinforcement learning (RL) to tackle two-player games such as Go, PSPACE-hard AI planning has remained out of reach for current AI planning systems. Even carefully designed domain-specific solvers fail quickly due to the exponential combinatorial search space on hard instances. Recent work based on deep learning guided search algorithms that combine traditional search-based methods, such as A\textsc{*} and MCTS search, with deep neural networks' heuristic prediction has shown promising progress. These methods can solve a significant number of hard planning instances beyond  specialized solvers. To better understanding why these approaches work we study the interplay of the policy and value networks in A\textsc{*}-based deep RL and show the surprising effectiveness of the policy network, further enhanced by the value network, as a guiding heuristic for A\textsc{*}. To further understand the phenomena, we study the cost distributions of deep planners and found  planning instances can have heavy-tailed runtime distributions, with tails both on the right-hand and left-hand sides. In particular, for the first time, we show the existence of {\textit{left}} heavy tails and propose a theoretical model that can explain the appearance of these tails. We provide extensive  experimental data supporting our model. The experiments show the critical role of the policy network as a powerful heuristic guiding  A\textsc{*}, which can lead to  left tails with polynomial scaling by avoiding exploring exponential size sub-trees early on in the search. Our results also demonstrate the importance of random restart strategies, as are widely used in traditional combinatorial solvers, for deep reinforcement learning and deep AI planning systems to avoid left and right heavy tails.

Under review as a conference paper at ICLR 2022
LEFT HEAVY TAILS AND THE EFFECTIVENESS OF THE POLICY AND VALUE NETWORKS IN DNN-BASED BEST-FIRST SEARCH FOR SOKOBAN PLANNING
Anonymous authors Paper under double-blind review
ABSTRACT
Despite the tremendous success of applying traditional combinatorial search meth- ods various NP-complete domains such 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 de- signed domain-speciffe solvers can fail quickly due to the exponential combinato- rial search space on hard instances. Recent work that combines traditional search methods, such as best-first search and Monte Carlo tree search, with Deep Neu- ral Networks' (DNN) heuristic prediction has shown promising progress. These methods can solve significant number of hard planning instances beyond spe- cialized solvers. To better understand why these approaches work, we studied the interplay of the policy and value networks in DNN-based best-first search the Sokoban domain and show the surprising effectiveness of the policy network, further enhanced by the value network, guiding heuristic for the search. To further understand the phenomena, we studied the cost distribution of the search algorithms and found that Sokoban planning instances can have heavy-tailed run- time 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 an ab- stract tree model that can empirically explain the appearance of these tails. We 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 sub-trees. Our results also demonstrate the importance of ran- dom restart strategies, as are widely used in traditional combinatorial solvers, for DNN-based search avoid left and right heavy tails.
INTRODUCTION
Combinatorial search is key domain for artificial intelligence. Unfortunately, combinatorial do- mains usually have intractable theoretical complexity, such as NP-complete, PSPACE--omplett, or even undecidable. the past few decades, we have observed tremendous progress for practical prob- lem solving in NP-hard domains with wide applicability in, for example, circuit design (Hong et al.) 2010,, hardware verification (Gupta et al. 2006), and mathematical discovery (Konev & Lisitsa 2014. SAT solvers based on conflict-driven clause learning can solve instances with thousands of variables and clauses in seconds, which demonstrates surprising scaling performance despite SAT being an NP-complete task (Silva & Sakallah 2003).
In contrast, practical combinatorial search in PSPACE-hard domains has remained a significant practical challenge. PSPACE-hard problems can be generally divided into two main categories: two-player games, such as Go, Chess, and Amazons (Lichtenstein & Sipser 1980; Fraenkel & Lichtenstein] 1981 Hearn 2005), and single-agent planning problems (a.k.a. combinatorial puz- zles), such as Sokoban and problems formalized by PDDL (Planning Domain Definition Language)
(Culberson, 1997 Bylander 1994). Recent achievements in the deep learning community inspired an approach of augmenting Monte Carlo tree search (MCTS) with Deep Neural Networks' (DNN) heuristic predictions. AlphaGo (Silver al. 2016) became the first Go software beat professional

---

Under review as a conference paper at ICLR 2022
human players in 2016, and its newer and more general version AlphaZero (Silver et al. (017) can achieve, tabula rasa, superhuman performance in many other challenging game domains.
These advances naturally raise the question of whether we can build general framework to learn different planning domains with minimum modifications. A key challenge is that hard planning instances often require intricate action sequences with hundreds of steps, and any deviation can lead to a dead-end state with no path to goal states. To address this issue, a more systematic and complete search, such as best-first search, is preferred over MCTS (Agostinelli et al. 2019). Traditional search methods augmented with neural networks' heuristics have shown promising progress in planning domains (Shen et al.] 2020; Rivlin et al.] 2020; Ferber et al., 2020, Feng et al. 2020a b). These methods can solve significant number of hard planning instances that specialized solvers cannot solve. To gain a better understanding of these approaches, we studied the interplay of the policy and value networks in ONN-based best-first search 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 DNN-based search. 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-studics 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 a reasonable time limit. The solver needs to be "lucky" and occasionally hit short run. In contrast, right heavy tails characterize mildly hard instances whose majority randomized runs have short runtime. Meanwhile, 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 empirically 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 ex exponentially sized sub-trees.
Randomized combinatorial solvers use various techniques, such as randomized tie- fiebbrakinn and ran- dom variable ordering, to carefully inject a controlled amount of randomization into a deterministic search procedure (Crawford& & Baker [994, 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 uncertainty-avaat nenworks (Huang et al.) 2017] Chua et al. 2018 Sedlmeier al. 2019; Malinin & Gales 2018) can provide just the right amount of controllable randomization into a deterministic search algorithm.
In this paper, consider Sokoban the background planning domain. The only domain knowl- edge neural networks and search algorithms receive is 1) input state representation; 2) state-action transition function; 3) deciding goal states. These three components are the minimum requirements to describe any planning domain and we did not use any other Sokoban-specific techniques, such as dead-end detection. We evaluated DNN based search on more than 10, 000 instances with signifi- cant variations in underlying combinatorial structure.
Our results also demonstrate the importance of random restart strategies, as are widely used in tradi- tional combinatorial solvers, for deep reinforcement learning (DRL) and deep Al planning systems 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 on DNN-based best-first search for the Sokoban domain. Our experiments show the surprising effectiveness of the policy network, further enhanced by the value network, as a guiding heuristic for the search.
2. We studied the runtime distribution on more than 10, 000 instances and propose distribution- independent statistics to quantify the heaviness of tails and effectiveness of random restarts. For the first time, we extensively studied left heavy tails from experiment data, introduce an abstract search tree model with critical nodes, and formally show how left heavy tails can arise during the search. Left heavy tails of runtime distributions are explained by the critical role of the policy network as a guiding heuristic. Polynomial runtime scaling can occur because the policy network helps avoid exploring exponentially sized sub-trees during the search.
3. We show the importance of using uncertainty aware networks in the planning domain and how it can add controllable amount of randomization to deterministic solver. We show how restart
2

---

Optimal speedup of Las Vegas algorithmss Let be a randomized algorithm that always outputs the correct answer when it halts but whose running time is random variable , - + R Luby al. (193) proved that when we have full knowledge about the distribution y-A the optimal strategy Under review as a conference paper at ICLR 2022
strategy improve DNN-based search's effectiveness. In particular, experiments show for larger budgets, more frequent restarts are more effective.
BACKGROUND AND RELATED WORK
Sokoban as a planning domain. Sokoban is a PSPACE complete puzzle whose goal is to push set of boxes into the same number of goal cells in grid maze with walls (Culberson 1997). Sokoban is among the most challenging known Al planning domains. The domain remains chal- lenging even for specialized solvers with significant human domain knowledge (Fern et al. 2011 Junghanns & Schaeffer, 200T). Due to its general search structure and hardness, we use Sokoban as our background domain throughout the paper.
that achieves the minimum expected time required to obtain an output from AA is to repeatedly run A for the same amount of time/ y- until it halts. To calculate 1 let
((t) = Ense M() E--E (1)
US
be the expected halting time of repeatedly running A with time limit t. Define 1 = inf I(t) and 1 is finite for any non-trivial distribution y i.e., (oo) < 1. Let 1 be any finite value of t
such that I(() 1 if such value exists, 1A
otherwise. Luby al. (193) also showed
that when p is unknown, the universal strategy that runs A for time limit
1, 2, 2, 1,
1, 1,,,,, 4,8,, 16,
achieve estimated halting time O(lAA log(!-)) for any randomized algorithm A. This bound is optimal among all universal strategies.
2005 observed randomized search on SAT and CSP can exhibit right heavy tails, in particular for so-called under-constrained instances, i... the majority of randomized runs the same instance halt in relatively short time while a non- negligible fraction of extremely long runs makes the average running time exponential. Gomes et al. 20000 formalized the runtime with the Pareto-Lévy form
Right heavy tails in randomized search. Gomes et al. 2000
P(X > x))
Ca x
and showed random restarts can dramatically reduce the runtime variance and potentially eliminate right heavy tails.
Uncertainty-aware network. There line of research on the uncertainty of neural networks reduce test error, provide confidence estimate, and improve model-based reinforcement learn- ing (Huang et al.] 2017); Chua et al.] 2018 [Selmeier et al.) 2019: Malinin & Gales 2018). Our method augments neural networks with Monte Carlo (MC) dropout to introduce randomization to deterministic search engines (Gal & Ghahramani 2016). MC dropout enables dropout layers during testing and the dropout rate can control the amount of randomization. For our experiment, the uncer- tainty comes from two main sources: (1) the distributional mismatch between the training and test datasets; (2) noises in the training data since the remaining distances (found by specialized solvers) are usually not optimal. See Section 3 for more details about data preparation.
3 FORMAL FRAMEWORK
guidd best-first search. Best-first search is an informed search algorithm, which explores a graph by expanding the most promising node chosen according to an evaluation function f(n) from the open set (scarch boundary nodes). fn) can use both the knowledge acquired so far while exploring the graph, denoted by g(n), and a heuristic function h(n). which estimates the remaining distance to the nearest goal state. Starting from the start state, best-first search gradually enlarges
ortps//occs.oor/AA 1821005

---

Under review as a conference paper at ICLR 2022
the current search graph by consecutively expanding new node which minimizes the evaluation function f() and adds 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) represents the depth of the node n. The heuristic function h(n) is estimated by a value
network, which is explained in further detail below.
Orseau & Lelis (2021) proposed Policy-guided Heuristic Search (PHS) to further learn policy network, which takes a state as input and outputs vector of action probabilities p with components p(als) for each valid action of 8. Specifically, they adapted the evaluation function to
(n) = p(si(so) ... pp( 1m f(n) g(n) + h(m)
π (n)
where (so, ..... 8m) is the sequence of states from the root node to n. Orseau & Lelis (022)) also
proposed PHS* a variant of PHS, that uses the evaluation function f(n)
gin] hin
((n) <M()/oA)))
Both PHS and PHS* require computing the cumulative product of probability predictions among the whole path from the root to In this paper, on the probability prediction of the incoming nodes of n:
new evaluation function which only depends
g(n) + h(n)
f(n) maxxcincoming nodes a p(n
Experiment data shows 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 real data. As an alternative, researchers heavily resort to procedurally generated instances highly structured problem domains (Taylor & Parberry [011]] Guez et al.] 2018). The randomly generated instances lack sufficient structure and their underlying combinatorial search space in some sense, regular.
Table I: Comparison with previous DRL works on Sokoban
Related works
avg width
avg height
avg size
avg boxes
T2As (Racanière al.
2017
T0
10
100
4
PHS (Orseau & Lehs
2021)
10
10
100
4
Feng et al. (2020a); Shoham & Elidan 2021
13
19
247
16
Our setting
12.0
13.6
183.5
20.2
To bridge this gap, we collected all the Sokoban instances from the Sokobano website resulting in 10871 instances in total. 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 also exhibit practical interest for humans to 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 I for Sokoban board statistics compared with previous works. Notice that the difficulty of Sokoban grows exponentially as the number of boxes increases.
To generate supervised training data, ran Sokolutior state-of-the of-tth--rttttttto Sokoban solver, to com- pute ground truth plans. Sokolution can solve 8272 out of 10871 total instances given a 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 to solve. 137 out from 200 instances remain unsolved and we collected these 137 instances as the hard set to further study the cost distribution of instances that are way harder than the training instances. For each found plan (Su, 01, $1...., an,, 8n) from the start state so to the goal state Sn, we generated training tuples (s,, 1s., v2,) with policy label lg, a,+1 and remaining distance label Us. n as training data.
Feng et al. (2020b) used PUSH as basic actions to achieve the state-of-the-as performance of DRL for the Sokoban domain. In this work, we use the more elementary action MOVE A PUSH action
http:////wkkoaoooodee////////.// http://cooeamallyis.ffiiss kooooaaaa
4

---

Under review as a conference paper at ICLR 2022
can be divided into two parts: 1) moving to the correct adjacent cell for pushing box; 2) pushing a box. As a result, PUSH requires more domain knowledge of Sokoban the framework needs to compute all reachable cells from the current player position and decide which boxes pushable. The number 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 is required to decide valid moves for any state. Using MOVE as basic actions will generate plans that are, on average, 3-4 times longer than ones generated with PUSH actions. The majority of instances considered in this paper have plans containing hundreds or thousands of moves, which provides great challenge for Al planning.
Network architecture and training details. For each board state of height H and width W, we create an input tensor of shape [4 H 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 a 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 multiple convolutional residual blocks and each block has two extra dropout layers to introduce randomization. See Appendix B for more details.
The parameters 0 of the deep neural network are trained with the following loss function:
(p. lh)( = o (s), loss = (log(h) - log(v,)) (v.)))))= log(pr.) c||0||
where e is the weight decay parameter controlling L2 weight regularisation.
4 THE INTERPLAY OF THE POLICY AND VALUE NETWORKS
Table Solver statistics of solved instances on the training and hard datasets (time limit: 10 mins).
Training dataset
Hard dataset time
expanded
time
solved
nodes per expanded
solved
Sokolution 191436
310s
100%
618
0%
DNN-based 13776
370
93%
37
18651
537
69 %
Table 3: Solving ratio on the test dataset with various evaluation function f(n) of best-first search, depending on depth d(n) (a.ka. g()),, estimated remaining distance h(n), estimated action proba- bility p(a(s). (), and cumulative path probability (n)). Columns represent different search budget.
Number of total node expansions (CPU runtime below)
Method
f
IK
2K
4K
8K
16K
32K
0.5 m 0.9 m 1.8 m
3.8 m
7.4 m
14.5 m
No Policy
Breadth first
d
0.32%
1.28%
1.92%
3.21% 21
6.73%
11.2%
Greedy
4.17%
8.01%
12.5%
15.1%
19.2%
19.6%
A
d h 2.0
5.77%
10.3%
13.5%
19.9%
21.5%
25%
WA*
6.09%
8.97%
14.7%
17.6%
19.6%
22.8%
With Policy
Pure Policy (ours)
1/p (d+ h)/TT 15.7%
28.2%
32.1%
36.9%
40.4%
42.9%
44.6%
PHS
19.9%
23.7%
26.3%
29.2%
31.4%
PHS*
(d+ (d+h)//T* ht//
28.5%
31.4%
38.5%
40.1%
44.9%
46.2%
p + Greedy (ours)
h/p (d+h)/p (d+200 2.0 h)/p
31.7%
32.4%
37.5%
38.8%
41.0%
41.3%
p A (ours)
32.4%
34.3%
38.8%
43.3%
46.2%
50.0%
p+ WA (ours)
31.7%
34.0%
39.4%
42.0%
45.8%
48.1%
Solver statistics. Table 2 above shows solver statistics of Sokolution, state-of-the-art solver of Sokoban, and ONNNbased A# We use cores of Xeon 6154 CPUs for profiling both solvers (neural networks the CPU mode for a fair comparison). Because of the cost of evaluating the deep net search guidance, DNN-based A expands significantly fewer nodes per second than Sokolution (about a factor of 17). Nevertheless, given 10 minutes, DNN-hased A can solve 69% hard instances
5

---

Under review as a conference paper at ICLR 2022
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.
Effectiveness of policy and value networks. Table 3 shows experiment results for different choices the evaluation function. As shown in the table, the policy heuristic has a significantly larger impact than the value heuristic. Specifically, the table shows that even the Pure Policy (using only the 1/p term, i.e., inversely proportional to the policy prediction) significantly boosts perfor- mance compared to all value heuristics-based search strategies without the policy guidance. (See the rows above "Pure Policy" in Table S With extra properly added depth and value terms, the performance of Pure Policy can further increase to obtain our best strategies with Policy + A* and Policy + Weighted A (WA*).
To further study why the policy network is more effective, we studied the performance of both networks in detect- ing dead-end states since dead-ends are one crucial factor that leads to exponential runtime. In particular, we ran-
Table 4: Dead-end detection accuracy
Train
Test
Hard
domly sampled 2000 board states from each dataset. For each state, we used Sokolution to detect dead-end suc- cessor states. The policy/value network is considered to successfully detect state if it predicts higher/lower pol- icy/value to the child on the ground truth plan than any other dead-end child. Table 4 shows that
Policy Value
93%
81 %
68 %
41%
38%
37%
the policy network significantly outperforms the value network at detecting dead-ends, and thus provide better search guidance.
5 ANALYSIS OF LEFT HEAVY TAILS
heavy tall
exponential 1D
log log plot of talls
3.0
mean
3.0
16"
7eary aeporential
6.8
0.5
8.6
10:
1.2
3.0
3.0
0.8
0.8
maan
mEaT
3.24
3.0
Figure 1: Each subplot shows DNN-based best-first search runtime statistics with MC dropout aug- mented on Sokoban instances. Each curve represents multiple runs on the same instance (instances might differ for different curves). We compare the runtime sample mean, optimal sample restart time i expected sample total runtime with restart 1 and expected total runtime of the universal strategy is as defined in Paragraph
thatting
Jeet
hadd
3.00
3.0
20
20
307
32
2.2
1.7
2.7
142
C100 2.7
107
Figure 2: Subplots show randomized DNN-based best-first search results for the training, test, and hard datasets. Each red dot represents a single instance. We perform 200 randomized searches on each instance with maximum of 300, 000 node expansions. The X-axis is 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.

---

Under review as a conference paper at ICLR 2022
Sample statisties about the heaviness of tails. Luby's optimal restart strategy requires the full knowledge about the runtime distribution r of a randomized algorithm A. Here we introduce sample statisties that can approximate the theoretical optimal values. Specifically, for each planning instance, we perform multiple randomized searches on it with maximum search budget M and collect runtime sample S. The runtime of failed searches is recorded as M. We approximate the optimal sample restart time g and expected sample total runtime with restart ( as
u. [S]
|S] Holo E 8 and S [83
t arg min NES
Kulu and v S u)
2, Let T (1, (, 1, 2, 4...) be the time limit sequence of the universal strategy. To approximate the expected total runtime t of the universal strategy on S, let aj be the expected total runtime of applying (T,, Ti+1, Ti+2...) on S and we have the constraint
S]
ac+1
S uuni 01
a, = aoue and v > T.H
We only need to calculate a, until the first i such that T, M and set the remaining a, zeros.
Figure shows runtime statistics for different types of tails. Both left and right heavy tails exhibit orders of magnitude reduction of ( and luniv over the runtime sample mean, which demonstrates the benefit of using random restarts. For exponential tails, the expected sample total runtime with restart very close the sample mean, and the universal strategy even has a negative effect.
To separate the two types of heavy tails, we compared the average runtime of solved instances v.s. the unsolved percentage as shown in Figure 2 An instance is viewed as a heavy-tailed run random restarts can reduce the expected runtime. We add further restrictions that a 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 2 shows the training dataset has almost the same number of left and right heavy-tailed instances, with the majority of instances not showing the heavy-tailed 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 left heavy tails occur more frequently when the underlying combinatorial structure becomes harder. Though random restarts can potentially 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 a distributed solving procedure in which any solution found by one of the processes can be shared and learned by the curriculum framework Weng 2020 Narvekar & Stone 2018 Narvekar et al. 2020
lap
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 is the constant probability of missing backdoor. In the right model, p is the constant probability of picking the right action to the goal.
Abstract search tree model. Chen et al. (2001) proposed an imbalanced tree model to empirically explain right heavy tails. Here we 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 (nn) where n is the problem size, and the search can assign these variables in any order. For planning domains, the search needs to assign actions in order from the start state to goal state with potentially maximum exponential length. Our proposed model hypothesizes the existence of (Iog(n)) critical nodes from which wrong child node selected by

---

Under review as a conference paper at ICLR 2022
the search will result in extra exponential search space. As shown in the following results, model does not depend on the actual choice of p as long as p is a constant value in range (0, 1).
Theorem 5.1
(The abstract tree model has exponential runtime almost surely). When restrict- ing plans to polynomial length on 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 Appendix A.I
Theorem 5.2 (Restart achieves polynomial expected halting time). The optimal expected halt- ing time with restart IA and expected halting time using the universal strategy 1 are both O(poly(n)). The proof is deferred to Appendix A.2
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 of left heavy tails.
Here is intuitive explanation of the abstract tree model. For the majority of the nodes the plan, the deep neural network either provides an accuracy heuristic to choose the right child node or makes small error of preferring wrong child node. As long the error is small the search can recover from it with extra polynomial steps since the evaluation function penalizes deeper nodes. For the Olog(n)) critical nodes, the error of estimated heuristics is large that exponential search is required to jump out from the local search space.
Two typical DNN-based best-first search graphs. We remove graph edges to form spanning tree for clearer illustration. The search graph is built from the left to the right. Red dashed path is the plan leading form the start state to one goal state, while blue circles are critical nodes, which have exponential sub-search tree underneath without near goal state.
Figure 4:
Structure of real search graphs. To empirically examine our abstract model, we plotted two typical search graphs generated by DNN-based best-first search as shown Figure 4 We found that the majority of nodes actually do not incur search. Networks' heuristics either directly lead the search to the correct child node, or only a very small wrong sub-tree (less than 5 nodes) is explored. Critical nodes (labeled as blue circles) are extremely rare in the search graph. However, when encountering such critical nodes, the search explores a large sub-tree with no near goal.
Whether AI planning systems find macro action routine, i.c., sequence of algorithmic actions to perform a sub-goal, has a great interest for researchers. To make a long plan, c.g., prove hard mathematical theorem, humans usually only make some critical choices of lemmas and schemes, and fill the remaining parts of the proof with little reasoning. Indeed, the number of required crucial intermediate lemmas prove mathematical theorem is quite small, even for challenging open problems. However, extensive and profound reasoning, search, and enumeration are needed to find 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 a real PUSH, the search algorithm needs to compute all reachable cells from the player's position and calculate the shortest path to the cell adjacent to the box to push. Such a long sequence of moves before performing an actual push can be viewed as a routine. in Figure 4 the algorithm can perform long chain of moves with little local search, which might suggest that macro action routines are implicitly learned as a part of neural networks' heuristics.
shown
Relation to backdoors. The proposed model has a close relation to backdoors to typical case com- plexity. To explain why solvers scale so well in areas such as planning and finite model-checking, Williams et al. (2003) examined various benchmarks and identified that for most practically solv- able problem instances, after assigning values to logarithmic variables, the remaining problem in- stance quickly becomes polynomially solvable by propagating constraints. This result illuminates
8

---

Under review as a conference paper at ICLR 2022
the prototypical patterns of the structure causing the empirical behavior observed in the International
Planning Competitions benchmarks Vallati et al. 2013 Cohen & Beck 2018 Meier et al. 2014).
(a) Subtree Size
(b) Unsolved ratio
Figure 5: (a) The total number of sub-trees of 300 randomly sampled instances v.s. the tree size (in log-log scale). (b) Unsolved fraction of instances with or without restarts. Given fixed amount of search budget (number of nodes allowed to expand), n-restart means to evenly divide the search budget into individual runs and union their solved instance sets as the final result.
More experiment data about the abstract tree model. To better illustrate the occurrence prob- ability of different sizes of sub-search space, we randomly sampled 300 solved instances from the test dataset and counted the number of dead sub-trees (no near goal exists) for each size. As shown in Figure Sa as the size of sub-trees grows exponentially, the number of sub-trees also decreases exponentially fast. The experiment data empirically confirms our abstract tree model that critical nodes which incur extra exponential search space have logarithmic occurrence. This is evidence about how left heavy tails occur in practical planning solving.
Hoffmann et 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, finding these critical nodes is not necessary for expand-style search algo- rithms. Left heavy tails not only caused by the underlying structure of practical instances but also affected by the mysterious generalization ability of neural networks. It is an interesting fu- ture research direction 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 sug- gests that a sequence of short runs instead of a single long run may make better use of a fixed amount of computational budget. We explored this idea by considering fixed number of total expanded nodes allowed for the search. dataset. The failure rate of single run drops the fastest for a 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 do- ing the figure shows there comes point where more frequent restarts are more effective. For example, with a 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 a larger fraction of hard instances, more frequent restarts become more effective.
the probability of not solving the instances for the test
CONCLUSION
We studied the use of policy (action selection) and value (remaining distance estimate) functions 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 amcertainty-awaa networks provide an effective way to introduce randomization into the search process leading increased efficiency. Our runtime distribution results show heavy-tailed distributions with tails on 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 are increasingly effective.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Forest Agostinelli, Stephen McAleer, Alexander Shmakov, and Piere Baldi. Solving the Rubik's cube with deep reinforcement learning and search. Nature Machine Intelligence, 1(8):356-663, 2019.
John L Bresina. Heuristic-biased stochastic sampling. In AAAI/IAAI, Vol. 1, pp. 271 271-278, 1996.
Tom Bylander. The computational complexity of propositional STRIPS planning. Artificial Intelli- gence, 69(1-2)1155204,, 1994.
Hubie Chen, Carla Gomes, and Bart Selman. Formal models of heavy-tailed behavior in combinato- rial search. In International Conference on Principles and Practice of Constraint Programming, pp. 408-421. Springer, 2001.
Kurtland Chua, Roberto Calandra, Rowan McAllister, and Sergey Levine. Deep reinforcement learn- ing in handful of trials using probabilistic dynamics models. arXiv preprint arXiv: 1.XXiv:880..1111 12114, 2018.
Eldan Cohen and J Christopher Beck. Fat-and heavy-tailed behavior in satisficing planning. In Whirty-Second AAAI Conference on Artificial Intelligence. 2018.
James M. Crawford and Andrew B. Baker. Experimental results on the application of satisfia- bility algorithms to scheduling problems. In Barbara Hayes-Roth and Richard Korf (eds.), Proceedings of the 12th National Conference on Artificial Intelligence, Seattle, WA, USA, July 31 August 4, 1994, Volume 2, pp. 1092-1097, AAAI Press The MIT Press, 1994. URL http: // /wwwww aaai wtt.:///rraaa///a/////1111
94 - 168. 68pphp
Joseph Culberson. Sokoban is PSPACE-complete. 1997.
Dieqiao Feng, Carla P. Gomes, and Bart Selman. Solving hard AI planning instances using curriculum-driven deep reinforcement learning. In Christian Bessiere (ed.). Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020, pp. 2198 2205. org, 2020a. doi: 10.24963fijcai.202003300 ijcai. 2020/304
htthpts::///ot org 249663
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 ECAI 2020, pp.
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-107, 2011.
Aviezri S Fraenkel and David Lichtenstein. Computing a perfect strategy for nx n chess requires time exponential in In International Colloquium on Automata, Languages, and Programming, pp. 278-293. Springer, 1981.
Yarin Gal and Zoubin Ghahramani. Dropout as a bayesian approximation: Representing model uncertainty in deep learning. In international conference machine learning, pp. 1050-1059. PMLR, 2016.
Carla P Gomes, Bart Selman, Henry Kautz, et al. Boosting combinatorial search through random- ization. AAAI/AAI, 98:431-433 1998.
Carla P Gomes, Bart Selman, Nuno Crato, and Henry Kautz. Heavy-tailed phenomena in satisfia- bility and constraint satisfaction problems. Journal of automated reasoning. 24(1):67-100, 2000.
Carla P Gomes, Cesar Fernández, Bart Selman, and Christian Bessicre. Statistical regimes across
constrainedness regions. Constraints, 10(4):317-337 2005.
Arthur Guez, Mehdi Mirza, Karol Gregor, Rishabh Kabra, Sebastien Racaniere, Theophane Weber, David Raposo, Adam Santoro, Laurent Orseau, Tom Eccles, et al. An investigation of model-free planning: boxoban levels, 2018
10

---

Under review as a conference paper at ICLR 2022
Aarti Gupta, Malay K. Ganai, and Chao Wang. SAT-based verification methods and applications in hardware verification. In Marco Bernardo and Alessandro Cimatti (eds.), 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, pp. 108 143. Springer, 2006. doi: 10.1007711757228)._5 URL /ttp:://aao...rrr/0...000///1/11
Robert A Hearn. Amazons is PSPACE-complete. arXiv preprint cs/0502013, 2005.
Jörg Hoffimann, Carla P Gomes, and Bart Selman. Structure and problem hardness: Goal asymmetry and DPLL proof' in SAT-based planning. In ICAPS, pp. 284-293, 2006.
Ted Hong, Yanjing Li. Sung-Boem Park, Diana Mui, David Lin, Ziyad Abdel Kaleq, Nagib Hakim, Helia Naeimi, Donald S Gardner, and Subhasish Mitra. QED: Quick error detection tests for effective post-silicon validation. In 2010 IEEE International Test Conference, pp. 1-10. IEEE, 2010.
Gao Huang, Yixuan Li, Geoff Pleiss, Zhuang Liu, John E Hoperoft, and Kilian Q Weinberger. Snapshot ensembles: Train get m for free. arXiv preprint 0rXiv:1704.00109 2017.
Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International conference on machine learning, pp. 448-456. PMLR, 2015,
Andreas Junghanns and Jonathan Schaeffer. Sokoban: Enhancing general single-agent search meth- ods using domain knowledge. Artificial Intelligence, 129(1-2):219 2001.
Boris Konev and Alexei Lisitsa. SAT attack on the erdós discrepancy conjecture. In International conference on theory and applications of satisfiability testing, pp. 219-226. Springer, 2014.
David Lichtenstein and Michael Sipser. Go is polynomial-space hard. Journal of the ACM (JACM), 27(2):393 401, 1980.
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. arXiv preprint 1rX1v:1711.05101, 2017.
Michael Luby, Alistair Sinclair, and David Zuckerman. Optimal speedup of Las Vegas algorithms. Information Processing Letters, 4774):173-180, 1993.
Andrey Malinin and Mark Gales. Predictive uncertainty estimation via prior networks. arXiv preprint arXiv:1802.1050) 2018
Andreas Meier, 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 18X2::811.000220 2018.
Sanmit Narvekar, Bei Peng, Matteo Leonetti, Jivko Sinapov, Matthew E Taylor, and Peter Stone. Curriculum learning for reinforcement learning domains: framework and survey, arXiv preprint arXiv:2003.04960, 2020.
Laurent Orseau and Levi HS Lelis. Policy-guided heuristic search with guarantees. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pp. 12382-12390, 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, al. Imagination- augmented agents for deep reinforcement learning. In Proceedings of the 31st International Con- ference Neural Information Processing Systems, pp. 5-9556947777 5705, 2017.
Or Rivlin, Tamir Hazan, and Erez Karpas. Generalized planning with deep reinforcement learning. arXiv preprint arXiv:2005.00 023005 2020.
11

---

Under review as a conference paper at ICLR 2022
Andreas Sedlmeier, Thomas Gabor, Thomy Phan, Lenz Belzner, and Claudia Linnhoff-PPon Popien.. Uncertainty-bra based disdiitribttionn classification in deep reinforcement learning. arXiv preprint arXiv:2001.00496. 2019.
William Shen, Felipe Trevizan, and Sylvie Thiébaux. Learning domain-independent planning heuristics with hypergraph networks. In Proceedings of the International Conference on Auto- mated Planning and Scheduling, volume 30, pp. 574-584, 2020.
Yaron Shoham and Gal Elidan. Solving Sokoban with Forward-Backward Reinforcement Learning. In Proceedings of the International Symposium on Combinatorial Search, volume 12, pp. 191- 193, 2021.
Joao P Marques Silva and Karem A Sakallah. GRASP-4 new search algorithm for satisfiability. In The Best of ICCAD, pp. 73-89. Springer, 2003.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonogiou, Veda Panncershelvam, Marc Lanctot, et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484 489, 2016.
David Silver, Thomas Hubert, Julian Schrittwieser, loannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. Mastering chess and shogi by self-play with a general reinforcement learning algorithm. arXiv preprint arXiv:1712.01815, 2017.
Joshua Taylor and Ian Parherry. Procedural generation of sokoban levels. In Proceedings of the International North American Conference on Intelligent Games and Simulation, 5-12, 2011.
Mauro Vallati, Lukas Chrpa, Marek Grzeš, Thomas Leo McCluskey, Mark Roberts, Scott Sanner, et The 2014 international planning competition: Progress and trends. Magazine, 36(3): 90-98, 2015.
Lilian Weng. 2020.
Curriculum for Reinforcement Learning. URL
ilfiaanwenngggthhbbboollllllggo -eaeenttteeerrr learni Setariing.haan html
curric um- for- re wwwooooeeettttoeoommmmmo
Ryan Williams, Carla P Gomes, and Bart Selman. Backdoors to typical case complexity. In IJCAI, volume 3, pp. 1173-1178, 2003.
12

---

Under review as a conference paper at ICLR 2022
A THE LMBALANCED TREE MODEL PROOFS
A.1 PROOF OF THEOREM 5.1
Lemma A.1 The abstract tree mode has palynomial runtime if and only all critical nodes pick the
right child.
Necessity comes from the structure of the model and any picking of left child will immediately result in exponential search space. For sufficiency, by the assumption, the depth of the tree model is bounded by ((poly(n)). (n)),, and the final sub-search space with all right child picking also (poly(n)). Then we have the total runtime (ppoly(n) + (ppoly(n)) = O(poly(n)) Q.E.D.
Proof of Lemma A.I
Proof of Theorem 5.1
By Lemma A.1
we have
lim Pr(model has poly runtime)
lim p ([lo((po)yyn))) n-
n=000
lim p
(-Iog(pol((a))
(for some constant C)
(0 < assumption).
As a conclusion, lim Pr(tree mode has exponential runtime) =
Q.E.D.
A.2 PROOF OF THEOREM 5.2
Proof. We can assume there exists least one non-critical node on the plan (if all nodes critical, we can augment extra non-critical node to the right child of the deepest critical node without affect other properties of the tree model). Let be the shallowest non-critical node and d be the depth of node u. We set the restart time I to be the size of the left sub-tree of d. 1 is poly(n) by the definition of the model. Let q = (1 p). So the expected runtime
lim 1 = lim (d (poly(nn)) n=000
Σ
q (1 9)th (k
k=
= lim (d (ppoly(n)) 1
n=*00
= O(poly(n))
By the result of Luby et al. (193), 1A 0 log((-)) Oppol((n)).
Q.E.D.
B NETWORK ARCHITECTURE AND TRAINING DETAILS
B.1 NETWORK ARCHITECTURE
A single input tensor of board states has shape [4 x H x W] and batch of board states can have different heights and widths. For each batch, we take the maximum and W of all state tensors as the batch height and width, and zero-pad the empty cells.
The network consists of single convolution block followed by residual blocks.
The convolutional block applies the following modules:
A convolution 128 filters of kernel size x 3 with stride
2. 2D batch normalization (Toffe Szegedy 2015
3. A ReLU nonlinearity
Each residual block applies the following modules sequentially to its input:
1. A channel-wise dropout layer with probability 30% of channel to zeroed.
2. A convolution of 128 filters of kernel size x 3 with stride
13

---

Under review as a conference paper at ICLR 2022
3. 2D batch normalization
4. A Relu nonlinearity
5. A channel-wise dropout layer with probability 30% of channel to be zeroed.
6. A convolution 128 filters of kernel size x 3 with stride
7. 2D batch normalization
8. A skip connection that adds the input to the block
9. A Relu nonlinearity
The output of the residual tower is then fed into two independent heads for computing the policy and value. Both heads contain an extra residual block followed by fully connected layer. The policy head outputs vector of size 4 and the value head outputs a single scalar.
B.2 TRAINING DETAILS
We use the A optimizer (Loshchilov & Hutter 2017) with weight decay 0.01 and an initial learning rate 0.001. We train the network with supervised training data for 200 epochs. The last 50 epochs use a learning rate of 0.0001. We set batch-size to 256. The whole training procedure took around 70 hours finish on 5 Tesla V100 GPU cards.
14


Reviews:
[{"review_id": "xxBo_y5ncg", "reviewer": "Reviewer_VVfA", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "# Thank you\n\nThank you for your comments. I see the new manuscript clarified many points.\nUnfortunately, I cannot honestly change my general opinion about the acceptance of the paper.\nThe Sokoban part per see is interesting, although not enough for acceptance.\nThe notion of left-heavy tail is something else. In figure 3-right, the problem can be just very hard to solve.\nFor many algorithms, there are classes of problems that generate a worst-case behaviour.\nI wonder if I could be deeply confused, and tried to challenge my understanding given the comments made and the improvement.\nI couldn't. If you insist this is important, please re-submit to a search-minded venue like Socs,\nor to a journal like the AIJ or JAIR.\n\n# Previous main review\nBefore examining the contributions, I feel obliged to clarify some points that I'd use in the rest of the review.\n\n1. The abstract does not mention that this empirical work is for one domain in particular: Sokoban. Two theorems are stated in the paper but without proofs. That means the observations must be circumscribed to the experiments that compare A* using\n\t- A very basic heuristic\n\t- PHS: DRL policy from previous work\n\t- PHS*: a variation of PHS proposed here.\n2. That leaves only two interesting cases in the experiments: PHS and PHS*. So, the observation about the distribution of complexity and the conjectures are circumscribed to Sokoban and these two related heuristics.\n3. The paper refers to heavy-trail distribution in SAT solving. That's an interesting connection, but it's important to consider that SAT solvers are general tools, not specialized algorithms for specific domains.\n4. Moreover, the paper seems to say that A* is a planning algorithm. The culture of the research community always mediates the name of techniques. Now, the search community –that publishes in SOCS, ICAPS, AAAI and IJCAI– would say that A* is a search algorithm that could be used for planning.\n\t- For instance, specialized algorithms for Sokoban use search algorithms like A*. The search community won't call them planners.\n\t- However, some DRL papers say that MCTS is a planning algorithm, while MCTS is a search algorithm like A*. I do respect that different communities might use different names.\n\t- For completing the picture: the planners that participate in the International planning competitions (IPC) are general solvers, like SAT solvers are. The simple class of problems in the IPC is PSPACE-complete. However, it doesn't mean that all the specific problems are PSPACE-complete. That leads me to the next point.\n5. The observations about the distribution depend on the distribution of the original problem. As shown in many combinatorial domains, algorithms tend to have strengths and weaknesses depending on the domain. For instance, in the SAT competitions, the winner of the industrial track tends to be different from the random track.\n6. That means that observations on the distribution of behaviour need to be grounded on the problem distribution and might not translate in the same way to other algorithms.\n\nThese six points above justify the summary I made about this paper: the paper is not about A* + DRL for policy/value. Instead, it's about Sokoban and two specific DRL techniques that end up having properties previously observed in SAT solving, and domain-independent planning as SAT.\n\nMoreover, the comparison between using A* with DRL heuristics and other methods is not trivial because of the following.\n\nTypically, non-ML based specialized search algorithms have very efficient node generation. For instance, the reference below discusses cases of over 1 million nodes expanded. On the other hand, DRL networks tend to have lower generation speed, but the training time is not accounted for and can provide an edge in certain instances. That means that neither of these metrics allow a complete picture of the comparison between non-ML vs NN-based heuristics:\n- Running time\n- Number of expansion.\nSo, in table 2, the no-policy versions might generate nodes much faster than the policy-based. On the contrary, it'd make sense to compare node expansions of PHS and PHS+.\n\nI'll finish this section of the review with some questions I'd like to answer in the rebuttal. Then I'll continue with some more comments about the paper.\n\n## Questions to be answered in rebuttal.\n\n0. Could some properties of the instance explain the left-tail? For instance, they could be mostly small instances or very easy to solve.\n1. How many nodes per second expands A* for the different configurations mentioned in Table 2?\n2. The use of SPFA reported before section 4 make it hard to compare the number of expanded nodes with previous work. It is also hard to compare the findings with previous work on A*. How do the experimental results look like if SPFA is not used?\n3. Page 2 says: *In fact, deep learning guided search algorithms that combine traditional search-based methods such as A star with deep neural networks heuristic prediction have shown promising progress. These methods can solve a significant number of hard planning instances that specialized solvers cannot solve.*\n\t- Please add concrete references and comment on the comparison.\n\t- Please take into account that specialized solvers tend to assume a higher running time, and that the good performance might depend on properties of the problem like size. For instance, A* + nontrivial non-ML heuristics might perform well in big environments where the agent needs to travel long distances to move between a few boxes.   \n4. What's the heuristics PureDistance?\n\t- Were other heuristics considered? Indeed, specialized solvers use heuristics too. \n5. How does  Sokosolution compares with the rest of the experiments? Please report running time, expanded nodes, and nodes per second.\n6. How costly is to train the DRL heuristics?\n\t- What parameters were used?\n\t- How were the hyper-parameters tuned? \n\n## Additional comments\n\npage 1: *Recent work based on deep learning guided search algorithms that combine traditional search-based methods, such as A and MCTS search, with deep neural networks' heuristic prediction has shown promising progress*.\nPlease add a reference. There is work all the way from TSP to game-playing. I'm not sure what previous work the paper should consider as relevant.\n\n#### Introduction\n\npage 1: *such as problems captured by the Planning Domain Definition Language (PDDL) (Bylander, 1994) and Sokoban*\nConfusing. I'd switch Sokoban and PDDL. By the way, Sokoban can be expressed in PDDL. Sometimes that's used as a homework: https://github.com/Tarrasch/sokoban-planner/blob/master/sokoban-pddls/sokoban-domain.pddl\n\npage 1: *(QBF), the canonical example of a PSPACE-complete problem*.\nYes. A reference, please\n\npage 2: *These advances naturally raise the question of whether the success in game domains can be transferred to PSPACE-hard planning domains.*\nAs I mentioned above, trained DRL for game-playing can play one kind of game. So, trained DRL can be compared with a specialized solver. However, suppose the same architecture can be trained in for multiple environments. In that case, they are more general than specialized solvers, depending on how hard they are to tune and the sample complexity. The main question is always how hard it is to generate a good algorithm in a new problem.\n\npage 2: *we explore and generalize the cost distribution profiles of search methods from NPhard domains to PSPACE-hard planning domains, and show heavy-tailed cost distributions exist ubiquitously among planning instances.*\nand page 2: *We identify heavy-tailed runtime distributions of PSPACE-hard planning problems*\nThis holds for Sokoban with these particular heuristics.\n\npage: *Such heavy-tailed distributions have been observed before in NP-hard domains, such as SAT and CSP (Gomes et al., 1997; 1998) but not in PSPACE settings.*\nNot true. See Eldan Cohen, J. Christopher Beck:\nFat- and Heavy-Tailed Behavior in Satisficing Planning. AAAI 2018: 6136-6143.\nSatisfying planning of classical planning is PSPACE. That includes Sokoban.\n \npage 2: *We study the interplay of the policy and value networks in A*-based deep RL. Our experiments show the surprising effectiveness of the policy network*\nWhy is this surprising?\n\npage 3: *We show how a restart strategy can improve the deep RL planner effectiveness. In particular, our experiments show how for a given search budget, there is an optimal restart strategy. For larger budgets, more frequent restarts are most effective.*\nThis depends on the algorithm. State of the art planners sometimes use variations of A* that use extra information from the domain or follow the heuristic more greedily. Search for \"greedy best first search\" and \"enforced hill-climbing\". See also the planner FastDownward: http://fast-downward.org. \n\n#### Background and Related Work\n\npage 3: *Luby et al. (1993) prove that when we have full knowledge about the distribution p A, the optimal strategy that achieves the minimum expected time*\nWhat about hard tasks that need more time than t_A?\n\npage 3: *figure 1 shows the comparison of heavy tails and exponential tails on various statistics.*\nIs this A* over Sokoban or a synthetic problem such that t_A can be defined analytically?\n\npage 4: *Orseau & Lelis (2021) add path probability π(n) to the minimizing term of A star search*\nWhat's the minimizing term of A*? It searches following the min f=g+h, where g is the cost and h is the heuristic value. Here \\pi(n) is a probability. How is that added?\nI see this explained in more detailed below. I suggest to say here that \"O&L divide the minimize value by \\pi(n)\" or weigth by 1/\\pi(n).\n\npage 4: *The search quickly degenerates into BFS when goals require a long plan since shallow nodes are always preferred by A star based on π(n). Our method modifies the term π(n) to p(s l|s l−1) to avoid exponential growth of the minimizing term of A* as the depth of nodes grows.*\nIt depends on the heuristic used. Is \\pi(n) as used a heuristic? An heuristic is an estimate of the cost of achieving the goal. Both terms of \\pi(n) would produce values < 1, while the usual cost in Sokoban is 1 per action.    \n\n#### Data preparation\n\npage 5: *remaining unsolved 2609 instances as the hard set to further study the cost distribution of instances that are way harder than the training instances.*\nThey could be slightly harder as it'd take 11 minutes to solve them. I suggest to sample a subset of them and try to solve in 30m or 2h.\n\npage 5: *move\" consists of four actions: upward, downward, rightward, and downward. The framework only needs to detect whether the four adjacent cells are empty, or whether the box is pushable if one occupies an adjacent cell.*\nAnother used alternative is to define push a requiring an adjacent box.\n\n#### Policy-guided A* search\n\npage 5: *We use the path length as the cost of A* search so that g(n) is the depth of node n.*\nI guess the implementation detects repeated nodes. Please clarify\n\npage 5]: PHS star is a significantly improved version*\nSay before that the change is called PHS*\n\npage 5: *We found the combinatorial search is so challenging that the model cannot reliably solve planning instances in the training set even has been trained on ground truth labels from it.*\nI think this argument does not follow. The negative empirical result does not imply that the problem is more or less challenging. I'd accept a weaker statement of the form \"The model couldn't solve instances used for training\".\n\npage 6: *As the evaluation time of deep networks heavily depends on hardware, we use the number of expanded nodes of A star as the runtime cost instead of the actual running time.*\nThis is standard in search research \n\npage 6: *We consider duplicate board detection so that various nodes with the same board will merge into a single node*\nSay this early to make sense of the cost being the path.\nMinor question: what if a shortest path if found later? Optimal A* reopens visited nodes/states, unless properties of the heuristic imply that's not necessary. In this case, optimality is not required. However, it'd be better to say it clear: \n- duplicate states are not expanded. \n- The cost of a node is the cost of the 1s path to it.\n\npage 6: *To increase the algorithm's efficiency and improve the evaluation metric, each time a node n is popped out from the open set (frontier nodes of the search), we do a local Shortest Path Faster Algorithm (SPFA) starting from n to ensure that no relaxation exists in the closed set at any stage of A star search, i.e., g(u) + 1 ≥ g(v) for each pair of adjacent nodes u, v while u is in the closed set.*\nThis is non standard. I hope an ablation study is done about the impact of this. This description is not enough for reproducing the results\n\n\n#### Heavy tails on the left\n\npage 6: *Our proposed model assumes the existence of O(log(n)) critical nodes among the plan from which a wrong child node selected by A star will result in extra exponential search space.*\nWhy log(n)? What's N in this case? For NP problems, the upper bound is O(n) because that's exactly the complexity in a non-deterministic Turing machine. \nIf this a conjecture, please say so. The conjecture would have value if the empirical results validate it. However, Sokoban is PSpace-complete, so I don't expect this conjecture to be validated in the Experiments section.\n\npage 6: *Theorem 4.1*\nProof of both theorems are not in the main body of the paper. There is no appendix\n\npage 7: *We empirically found that in the search graph of A, the majority of nodes do not branch — heuristics provided by the network is accurate enough to prefer the right child node with high confidence.*\nThis general statement is at odds with the idea of heavy right tail. It'd be inconvenient to change this statement to talk about the mean since that's not well defined for heavy-tail distribution. \n\npage 7: *To explain why SAT solvers work so well in practical instances, Hoffmann et al. (2006) examine various benchmarks and identify that for most practically solvable SAT instances, after assigning values to logarithmic variables, the remaining problem instance quickly becomes polynomially solvable by propagation rules.*\nHoffman et al examine planning instances solve by translation to SAT. Those propositional theory have a particular structures that might not apply directly to SAT. The backdoor conjecture was examined in previous work by the co-authors the Hoffman of that paper. \n\npage 7: *This result illuminates the prototypical patterns of the structure causing the empirical behavior observed in the International Planning Competitions benchmarks.*\nReference? In general, it'd be good to discuss other domains of the planning competition. Some of them have complexity analysis like the referred paper on Sokoban being PSpace-complete.\n\n#### Structure of real search graphs\npage 7: *Whether AI planning systems can find routine macro action, i.e., a sequence of algorithmic actions to perform a sub-goal, has a great interest for researchers.*\nThis phenomenon is fairly common in instances that are solved using A*, when the solution is found quickly. The paragraph after this sentences implies this phenomenon is specific to this experiment. Instead, the paper show report experiments using A and a non-DL heuristic to see if the same phenomena appear. The non-DL heuristic could be a specialized solver or a general automated planner, even if it scales to smaller instances.\n\n#### Effectiveness of policy and value networks\n\npage 8: *5.2 EFFECTIVENESS OF POLICY AND VALUE NETWORKS*\nWhat is Pure Distance? The effectiveness of A* depends strongly on the heuristic. If the heuristic is ill-informed, using WA* tends to degrade the performance.\n\nGeometric Mean? Why? It's hard to qualify the meaning of this result without comparison with other algorithms. \n\nThe experiments are in a region of a relatively low number of expansions. See for instance, Pereira et al below where the number of expansions goes all the way to 1 million nodes.\n\nMoreover, the conclusion about what's the best algorithm depends on how much time is available. The last full international planning competition (2018) included these tracks:\n- satisfying. Score if instance solved in less than 30m.\n- agile. Positive score proportional to speed until a limit of 5m.\nhttps://ipc2018-classical.bitbucket.io\n\nEven for the same algorithms, the best configurations is different depending on the speed required.\n\nAndré G. Pereira, Marcus Ritt, Luciana S. Buriol,\nOptimal Sokoban solving using pattern databases with specific domain knowledge,\nArtificial Intelligence,\nVolume 227,\n2015,\nPages 52-70,\nISSN 0004-3702,\nhttps://doi.org/10.1016/j.artint.2015.05.011.\n\npage 8: *(3) Weighted A start does not help.*\nThis observation was done in a relative low number of expanded node.\n\n#### Experiment data for the abstract model\n\npage 9: *Hoffmann et al. (2006) has given an explanation to STRIPS-style planning with backdoor models — after finding and assigning logarithmic variables the remaining problem solving becomes polynomial. In contrast, finding these critical nodes is not necessary for expand-style search algorithms*\nThis is for SATPLAN: classical planning as SAT\n\npage 9: *It is widely believed and experimentally confirmed that with polynomially increasing model size, deep networks can achieve\" exponential\" scaling power to unseen states*\nWidely believed by whom? I don't believe that myself as a general statement. It is an interesting hypothesis, but it needs to be studied. A source of confusion is the tension between solving single problems vs general solvers. It does make sense that some learning based algorithms might be more powerful than specialized solvers. But what worked in one domain might not translate into another one. \n\nEnd of the day, what matters is the resources necessary  to get the solutions. If the same domain is to be solved multiple times, like Go, training makes sense. On the other hand, if many variations are solved, it'd make more sense to have a general solver. \n\n#### References\n\npage 10: *Joseph Culberson. Sokoban is pspace-complete. 1997.*\nCheck the font case of the references. Pspace, sat and others are upcase. Rubin is a proper name. \n\npage 11: *Laurent Orseau and Levi HS Lelis. Policy-guided heuristic search with guarantees. arXiv preprint preprint arXiv:1802.10501, 2018. arXiv:2103.11505, 2021.*\nThis was accepted to AAAI 2021. Please avoid arXiv references when the paper has been accepted. \n\nFinally, here are two interesting references:\n- Yaron Shoham and Gal Elidan. \"Solving Sokoban with forward-backward reinforcement learning\". SOCS 2021. (Both in arXiv and in the socs website, where this is a video too).\n\t- This might be a good algorithm for comparison. \n\t- I still think that's fairly standard in search. In a sense, the left-tail was always there as. \n- This is an undergrad thesis. I cite it with the best of intentions. It showed up as I was looking for references. It discusses cases where Sokoban becomes harder for non-specialized planners (using PDDL).\n\t- https://ai.dmi.unibas.ch/papers/theses/haenger-bachelor-13.pdf\n- This is another relevant undergrad thesis\n\t- https://baldur.iti.kit.edu/theses/SokobanPortfolio.pdf\n\nSee below some extra problems that are also PSPACE-complete:\n- PSPACE-Completeness of Sliding-Block Puzzles and Other Problems through the Nondeterministic Constraint Logic Model of Computation. Robert A. Hearn, Erik D. Demaine\n- Aviezri S. Fraenkel and Elisheva Goldschmidt. 1987. PSPACE-hardness of some combinatorial games. J. Comb. Theory Ser. A 46, 1 (Sept. 1987), 21–38. DOI:https://doi.org/10.1016/0097-3165(87)90074-4\n", "summary_of_the_paper": "The paper study the behaviour of A* combined with Deep-RL (DRL) based heuristics in Sokoban, a PSPACE-complete problem, and an important domain in search, planning and RL. Experiments show a heavy-tail distribution on running time in some cases; that imply abundant cases where the problems are solved quickly –in polynomial time– or take a long time. Furthermore, the paper shows how previous search ideas can help solve more problems quickly: restarts and randomization.\n\nThe paper enumerates five contributions, but I am not convinced of their value. Instead of presenting them and then commenting about them, I will go over them and comment. That would lead me to a conclusion about the paper. I will recommend rejecting the submission as this needs further work.\n\nDespite my interest in this line of work, my recommendation is studying the interaction between search algorithms and ML-based heuristics, including DRL.", "summary_of_the_review": "In summary, I think the current manuscript extrapolates empirical observations in one domain -Sokoban– with a few related heuristics. For showing something specific about them, other heuristics or specialized solvers should be used. I wouldn't be surprised if different algorithms solve fast different kind of problems.\n\nI understand the intention of the contribution is about DRL-based heuristics exploiting the so-called left-tail. However, I don't want to made mistake I was pointing out. The question is whether that observation is a property of the DRL proposed here, or a fairly common situation that appears in other cases. Comparing with specialized solvers and other ML-based heuristics might help to answer this critical question. \n\nTherefore, I recommend to reject the paper for ICLR 2022.\n\nI think this paper would be a more appropriate for SOCS, ICAPS or a general conference like AAAI, IJCAI or ECAI.\n\nFor the sake of clarity, I'll react to the contributions:\n1. We study the interplay of the policy and value networks in A*-based deep RL. Our experiments show the surprising effectiveness of the policy network, further enhanced by the value network, as a guiding heuristic for A*.\n\t- This observation could be significant for solving Sokoban, but it's not. \n\t- This observation could be significant for DRL-based heuristics, but it's not. \n\t- Both possibilities would require comparison with other algorithms, including specialized solvers, unless other problems beyond Sokoban were considered.  \n2. We identify heavy-tailed runtime distributions of PSPACE-hard planning problems and propose a series of distribution-independent statistics to quantify the heaviness of tails and effectiveness of random restart. For the first time, we show and extensively study heavy left tails from experiment data, introduce an abstract tree search model with critical nodes, and formally show how heavy left tails can arise during the search.\n\t- The so-called left-tail phenomena appears in many techniques using search. See other papers about Sokoban mentioned here. The amount of instances tested could be smaller, but the high diversity of running time is consistent with the findings here.\n\t- In any case, given the experiments, this observation would be valid only for Sokoban, and the reader must wonder if there is something special on the DRL-based heuristics.\n3. The tails on the left of the runtime distribution are explained by the critical role of the policy network as a guiding heuristic. Polynomial runtime scaling can occur because the policy network helps avoid exploring exponential size sub-trees early on in the search. figure 3 visualizes the phenomena by revealing a small set of critical nodes in the early part of the search space.\n\t- This is also fairly common in search. I don't think this is a contribution. The same sentences \"Polynomial...\" Apply to the behaviour of a SAT solver.\n4. We show the importance of using uncertainty aware networks in the planning domain and how it can add a controllable amount of randomness to a backtrack-style solver.\n\t- This holds. The difference is of 4% absolute.\n5. We show how a restart strategy can improve the deep RL planner effectiveness. In particular, our experiments show how for a given search budget, there is an optimal restart strategy. For larger budgets, more frequent restarts are most effective.\n\t- This is an interesting observation. It's possible that DRL-based heuristics benefit more from restart in comparison with specialized solvers and generic domain-independent planners", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "h7-ub9JXfNV", "reviewer": "Reviewer_Lduu", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Strength: \n\t1. This paper created an abstract model which explains the right- and left- heavy tail issues for best-first search algorithms. \n\t2. Experiments seem to demonstrate the effectiveness of the proposed combination of policy, valuation, random-restart and uncertainty networks with no or small modification to the original proposal in the literature. \n\nWeakness \n\t1. No explicit description of the specific architectures of value network, policy networks, uncertainty aware networks used in this paper. This makes it difficult for the readers to replicate and evaluate the applicability of the approach used in this paper. \n\t2. The writing of the abstract model of heavy right- and left- tail problems need improvement to make it clear and mathematically solid. The notations and concepts need to be unified, be introduced formally and be referred in any usage. Also the abstract model seems to be a standalone contribution to the best-first search framework; and it doesn't need or make use of any properties of the deep nets heuristics or policy networks. Please clarify.\n\t\n\t\nDetails\n\n   1. Luby et al. (1993) seems to be an important component of your abstract model of understanding the left- and right- tail issues. Please considering moving the math definition to section 4. Also the notation of p in section 4.1 seems to be conflicting with section 4.1 and a few other places. Please use and define notation explicitly and carefully.\n\t2. Page 4, a typo? \\pai(n) = … p(s_l | s_l-1) , should l be n?\n\t3. Page 4, please definite critical nodes mathematically. \n\n\n\n", "summary_of_the_paper": "This paper studied A* style best-first search with deep networks guided value and policy functions. Theoretical framework was created for the analysis of heavy left- and right- tails problem in running time. This paper also claimed that according to the experiments policy network, random restarts, and uncertainty aware networks are import contributors of solving hard planning problems.  However, this paper did not provide its own version of the policy, valuation and uncertainty networks making it difficult to evaluate the validity of the approach and the theoretical analysis --- I need to guess from the literature which exact networks are used in the experiments and the theoretical analysis. \n", "summary_of_the_review": "This paper needs significant improvement in the writing clarity, mathematical soundness, and experimental validity to reach publication status. For example, this paper did not provide its own version of the policy, valuation and uncertainty networks making it difficult to evaluate the validity of the approach and the theoretical analysis --- It requires the readers guessing and jumping across the literature to get the important components neural net constructs, e.g. the valuation, policy and uncertainty aware networks. \n\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "O8ilw8KBpU2", "reviewer": "Reviewer_4bCR", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "## Strengths\n\n* There are a lot of interesting ideas raised in this work.\n* The topic areas are relevant to ICLR, although the paper may find a larger pool of interested readers in venues like AAAI, IJCAI, or ICAPS.\n* The abstract model proposed to explain the heavy-tailed distributions observed when planning with A* + learned policy and heuristic is interesting and provides helpful intuition.\n* The results in Table 2 support the conclusion that using the policy in the proposed way is a good idea. However, without the number of seeds/trials, it is difficult to assess whether these results are statistically significant.\n* Similarly, the results in Figure 4 are compelling. I would like to see more results in these directions, for example, in different domains.\n* I am not aware of prior work that uses uncertainty-aware NNs to learn policies/heuristics which are then used in combination with random restarts. I think this is a nice idea and could have general applicability.\n\n\n## Weaknesses\n\n* There are a large number of experimental details missing, so much so that it is difficult to interpret and evaluate the reported results.\n   * None of the standard hyperparameters for neural network training and architecture are reported.\n   * The way that the Sokoban states are encoded is not clear (there are many plausible possibilities).\n   * I am guessing that the actions are just encoded as the four options “up”, “down”, “left”, “right”. (A different approach would be to use the ground PDDL operators as the actions, which has been done in prior work [1].)\n   * The number of random seeds or trials does not seem to be reported. Was only one model trained?\n   * I am guessing that the value networks are trained by minimizing MSE on the distance labels, and the policy network is also trained by minimizing a classification loss on the action labels, but there definitely needs to be more explicit discussion and details about both.\n   * There are several other missing details -- overall, the paper needs a lot more information to reach the level where it would be possible to reproduce the results.\n* A supplemental PDF and code would help clear up some of the confusions above, but none were submitted.\n* The proposed model to explain left-hand heavy tails in section 4 is described informally. Formal definitions would help with clarity.\n* Theorems 4.1 and 4.2 are stated without proof. It is also unclear what $\\mathcal{A}$ is, in the context of the theorem statements. I am guessing it is a randomized algorithm that chooses a search node to expand with probabilities according to the model in Figure 2 (right), but that is a big leap, and the details are unclear.\n* There is a big gap between the scope of the paper as implied by the introduction and the actual scope of the results. The introduction discusses PSPACE-hard problems in a very general way, but the results are ultimately concerned with a specific planning algorithm in one specific domain with a specific learned search guidance strategy.\n* The references are missing connections to the learning for planning literature, which often appears in AAAI, IJCAI, or ICAPS. Some examples: [1-4]. Also, [5], but that one is not published. The connection to [1] is especially worth delving into. They propose a prioritization scheme that combines policy and value networks, similar to what is done here -- see their equation (22). It’s not exactly the same, so it would be interesting to explore the trade-offs.\n* I would be curious to see baseline comparisons with the method proposed in [4]. Rather than altering the heuristic function, that method proposes to use a policy by running it for several steps during node expansion. Similar rollouts are used in [1] too. Based on the discussion of “routine macro actions”, it seems like these rollouts would do well here.\n* There are a fair number of typos throughout. I noted some in the minor comments below.\n* Overall, the paper would benefit from additional focus. The paper strikes me as trying to explore too many research threads at once, and it does not do justice to any of the individual threads. The threads are all very interesting, though.\n\n\n[1] “Generalized Planning With Deep Reinforcement Learning.” Rivlin et al. (2020).\n[2] “Neural Network Heuristics for Classical Planning: A Study of Hyperparameter Space.” Ferber et al. (2020).\n[3] “Learning Domain-Independent Planning Heuristics with Hypergraph Networks.” Shen et al. (2020).\n[4] “Learning Control Knowledge for Forward Search Planning.” Yoon et al. (2008)\n[5] “Reinforcement Learning for Classical Planning: Viewing Heuristics as Dense Reward Generators.” Gehring et al (2021).\n\n\n\n## Minor Points\n\n* Typo: orders of magnitude *shorten* running time\n* “The randomly generated instances lack sufficient structure and their underlying combinatorial search space is, in some sense, too regular.” The first part and the second part of this sentence seem to contradict each other.\n* Grammatical typo: “the majority of instances have solution length contains hundreds or even thousands of moves”\n* Typo: “The policy heuristics has”\n* Typo: “in the training set even has been trained on”\n* Typo: “an accuracy heuristic”\n* The open quotation marks throughout the paper are usually facing the wrong direction\n* The second column of table 2 is titled “A* cost function”, but it may be better to title that something like “priority function”, because it’s not really A* unless g(n) + h(n) is the priority function. These methods are variations on heuristic search more generally, not A* search specifically.\n* Macro-actions are traditionally a sequence of actions that are executed open-loop. The “routine macro actions” described in section 5.1 sound more like a policy, since the actions will depend on the state.\n* This sentence is imprecise, and I don’t know if I believe it: “It is widely believed and experimentally confirmed that with polynomially increasing model size, deep networks can achieve ”exponential” scaling power to unseen states.” What does “exponential scaling power” mean?\n* It would be interesting to know what the states and actions at the critical nodes and the respective subtrees look like, qualitatively, in Sokoban. Are these “mistakes” similar to what a human would do in any way?", "summary_of_the_paper": "This paper considers A* planning with learned policy and value function approximations. After presenting empirical results for heavy-tailed distributions of guided search runtimes, the authors propose an abstract model to explain these distributions. They also propose to search with random restarts as a way to address the heavy tails; and to perform random restarts effectively, they propose to use uncertainty-aware NNs, specifically ones with test-time dropout. Empirical results are in Sokoban.", "summary_of_the_review": "This paper is somewhat extreme along multiple dimensions. On the one hand, there are many more interesting ideas than is typical for a single paper. On the other hand, there are many more experimental details missing than is typical even for rejected papers. The writing also needs to be more clear, precise and formal; the experiments and analysis need to go deeper; and the scope of the abstract and introduction needs to be narrowed. Overall, I think this could turn into a very good paper (or several papers), but the changes required will likely be too substantial to accept it for this conference.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "MW3EdsPn1PY", "reviewer": "Reviewer_whsB", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper empirically studies the behavior of the A* search when it is combined with the DNN heuristic generator (A*+DNN). This paper focuses on the Sokoban domain covering more than 10,000 instances available in the literature and presents some evidence that the running time distribution of A*+DNN may have left/right-heavy tails.\n\n#### Strength of this paper\n* large coverage of problem instances\n* offering a connection with PHS (Orseau & Lelis 2021) and many earlier works in SAT/CP on heavy-tail distributions of the running times.\n* intuitive explanations that may explain the results with the imbalanced tree model.\n\n#### Weakness\n* No information about DNN heuristic generator other than it used dropout 30% \n* Lack of supporting experiments or claims for the 5 contributions author claimed.\n\n#### General questions\n  * This paper studies the Sokoban domain. How does the observation made in this domain applicable to AI planning in general?\n  * How did you generate Figure 1? Did all 4 distributions come out from 1 Sokoban problem instance? Then, how did you process the running times to obtain the distribution?\n  * What is the Monte-Carlo dropout mentioned in Figure 1? \n  * Did you encounter memory limits during the experiments ? What fraction of the instances failed because of the memory and the rest because of the time limit?\n  * Considering forward state space search in AI planning that commonly relies on best-first search with various heuristics, or memory-bounded best-first search, or searches with look-ahead, or hybrid type of search that mixes dept-first and best-first type search strategies,  this paper explores the basic A* with skipping the efforts ensuring the optimality of the solution. Have you compared the result with modern AI search algorithms other than PHS in Table 2?\n  * What are the typical problem statistics? the length of plans, the size of the state space, etc?\n  * Dropping the admissibility, A* is a more or less greedy search algorithm. In this paper, it is treated like that by comparing with variants of the heuristics in Table 2. Why did you include weighted A*? It is normally applied in the context of any-time search that offers a faster sub-optimal plan with the guarantee on the solution quality. Here, I don't see any good fit for using WA*.\n  * The number of node expansions is very small (< 10^4) compared with the usual heuristic search (> 10^9). Is this because of the implementation limit? What was the time limit for the search? In this sense, the experiment may cover the cases when the search doesn't expand too many nodes.\n * What is the quality of heuristic estimates? How does a trajectory generated by DNN align well with the solution?\n * On page 8 under observation (1), did you see a case that supports your conjecture? \"the distance heuristics are trained from solution paths so it possesses strong locality property\".\n  * On page 8 under observation (2), can you clarify \"In theory, the depth term does not contain extra heuristic information about the search space\", can you point out what theory supports that statement?\n  * On page 9, can you provide references for the statement \"it is widely believed and experimentally confirmed that with polynomially increasing model size, deep networks can achieve \"exponential scaling power to unseen states\".\n  * Following the title of the paper, have you experimented with any other non-random AI planning domains?\n  * Thm 4.1, and Thm 4.2, how to prove them?\n\n* Comments on each contribution\n1. For me, it reads like \"the surprising effectiveness of the policy network\" is an improvement of the coverage from PHS that replaces $\\pi$ with $p$ in Table 2. Dividing the f with $\\pi$ or $p$ gives more weights on the trajectories likely to be generated by DNN. On the one hand, using $p$ may improve the numerical stability. I think this choice enforces the search to follow the trajectory generated by DNN. Then, A* offers minor fixes on the trajectories generated by DNN. If DNN heuristics gets weaker, would you expect to see similar trends?\n2. In the paper Figure 4. would be the only data that supports the empirical statement, which seems not sufficient. Do you have more results supporting this claim?\n3. Probably the model explains the observation. But still, this paper only shows 1, which is not sufficient.\n4. Can you provide the details on the network? I cannot find which part of the paper shows the importance of using uncertainty-aware networks.\n5. Figure 4. b supports this claim. But I think we need more elaboration on the experiment. The time interval of restarts, some additional separation within the training, test, and the validation set based on the length or difficulty or the number of dead-ends in the problems.\n\n\n\n\n\n", "summary_of_the_paper": "This paper empirically studies the behavior of the A* search algorithm with inadmissible neural network heuristics for solving Sokoban games. \n* The paper introduces related works in SAT/CP on the \"heavy-tail distribution\" of running times and briefly summarizes the neural network set up for heuristic functions. \n* This paper proposes an imbalanced tree model similar to the one shown in the context of SAT/CP and \nmakes some statements on the running time in Thm 1 and 2.\n* The experiment section compares the coverage of the problem instances and statistics on the search space from randomly selected instances.", "summary_of_the_review": "This paper shows interesting experiment results. However, we need clarification of the experiment setup and empirical results.\nThe idea is interesting and the approach is promising to understand the behavior of search with DNN. This is empirical work, so it's hard to make definite statements on the correctness. However, I think experiments don't support the claims well. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a mechanism for A* planning with learned policy and value functions. The experiments (restricted to the Sokoban domain) show that the runtime of guided search follows a heavy-tailed distribution, suggesting that in many cases, the problem is either solved quickly or takes a long time. An abstract model is proposed to explain this distribution, and a number of mechanisms are proposed to overcome its challenges.

The reviewers thought the paper had some interesting ideas but found the experimental section to be especially weak. While the paper starts out with quite general claims, the experiments only consider a single domain. Also, key details about the experiments were missing. Finally, the writing feels rushed -- the original submission had many typos and lacked proofs for two theorems. 

I agree with these objections and recommend rejection. Please revise the paper following the reviews and resubmit to a different deadline.
Decision: Reject