Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper analyzes the behavior of DNN-based best-first search for solving Sokoban planning problems and discovers "left heavy tails" on the running time distribution from hard Sokoban instances. The main contribution of this paper is to show the existence of left heavy tails and the abstract search tree model that characterizes such behavior. There are also relatively minor contributions, such as modifying the f(n) and systematic comparison of various search configurations.

strengths_and_weaknesses: The strength of this paper is through experiments on a very large number of Sokoban instances (over 10,000) and evaluations of various search configurations, which provides some evidence and explanations why search with DNN-based heuristic works well in practice.

The weakness of this paper is missing technical details.

questions: In policy guided search, how did you compute p(n | parent(n) ) ?

In network architecture and training details, can you explain each term in the loss function? 

On the contribution of this paper on the "uncertainty aware network," Is there some part in the paper other than Monte Carlo dropout (line 185-188) explaining the details? The conclusion is the drop-out ratio of 30% is the best after the grid search. If we choose other ratios, would it change the analysis on left-heavy tails? I cannot find how this selection effectively introduced randomization to search.

In the effectiveness of policy and value networks, I was not able to understand the last sentence (lines 214-217). Can you explain how to detect dead-end children? what does it mean by "predict a higher/lower policy/value to the child"?

In sample statistics about the heaviness of tails, how t^{\mathcal{S}} (lin 227) was given as an approximation of the optimal sample restart time?

In the abstract search tree model, is n the length of the plan for Sokoban problems or a total number of states?
What is the implication of the number of critical nodes being O( log(n) )? Are the critical nodes must be nodes along the path from the root to the goal?

The proof in the Appendix, as well as the abstract search tree model, assumes the number of critical nodes is in O( log(n) ) and the non-critical node has a search space of size O( poly(n) ). From this assumption, the optimal expected halting time with restart is shown to be O( poly(n) ).
Figure 1 also shows that the l^{\mathcal{S}} (yellow) is much smaller than the mean running time (red line). Figure 5 (caption is missing) shows the abstract search tree model matches the data. How to apply this idea to designing a random restarting strategy? Is it mandatory to have strong heuristics such as policy networks? Is this implies dead-end detection is more important than estimating the cost to go more precisely?

limitations: I think this work is not relevant to this section.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper investigates DNN-based best-first search with policy and value networks for Sokoban planning. First, the paper studies PHS and PHS* and a variant proposed in this paper and find that policy networks learn effective heuristics for search and can be further enhanced by the use of value networks. Then, the paper empirically studies left heavy tails from experiment data and develop an abstract model that show how left heavy tails can arise during the search.


----
I thank the authors for their response.

I think the paper would benefit from showing this phenomenon extends beyond a single domain and a single heuristic function, however I understand the limitation on computational resources and I think these results are of interest. I therefore increase my score by one point.

I think the paper should include a discussion on the previous works discussing left heavy tails (including conjectures).
strengths_and_weaknesses: Strengths:
- Interesting empirical results on effectiveness of DNN-based best-first search in Sokoban planning.
- The discovery of left heavy tails in DNN-based best-first search in Sokoban planning.
- A novel theoretical results that explains the occurrence of left heavy tails.


Weaknesses:
- The main weakness is the limited scope of work: 
	* The paper focuses on a single planning domain. Sokoban is a well-known planning domain but as the paper seems to suggest left heavy tails are likely to occur in other practical planning problems (right heavy tails have been observed in many problems), experiments on other domains would significantly strengthen the work.
	* Unlike the results on the effectiveness of DNN-based best-first search, the results on the left heavy tails are not shown for multiple evaluation functions and it they appear across different evaluation functions.
- In addition, I think some of the claims require further justification:
	* I think the claim that left heavy tails are shown for the first time needs to be more clearly justified in the paper as there are existing works that discuss left heavy tails (e.g., reference [18] in the paper).
	* I think the claim that the paper shows the importance of using uncertainty-aware networks in planning should be more carefully stated due to the narrow scope described above as well as the fact that experiments report results on only one dropout value (30%).
- Minor points:
	* I think the citation style in the paper ("[10] used ...", "[34] proposed ...") is hard to read and it would be better to use the author names.
	* The supplementary material has some missing references presented as "?" such as "Proof of ??", "By the result of (author?)"

questions: - Did you experiment with other domains?
- Did you find left heavy tails across different evaluation functions?
- Did you experiment with different dropout values?
limitations: I did not identify any issues related to limitations and potential negative societal impact.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper analyzes the performance of learned heuristics in best-first search for planning in Sokoban. The paper proposes a variant of the policy-guided best-first search for its experiments. The algorithm requires a node evaluation function and this paper proposes a simplified variant of the evaluation function in PHS* which requires, both, a value (distance to goal) prediction and an action prediction (P(n | parent(n))). The experimental setup uses a dataset of Sokoban instances designed by humans. Supervised training data for learning the distance to goal heuristic is generated by running an off-the-shelf Sokoban planner on these instances. A DNN with dropout (for randomization) (and policy and value heads) is used to learn the heuristic. The experiments compare different evaluation functions (with and without learned policies) and contain a number of interesting results. Using a learned policy significantly improves performance on hard Sokoban instances, outperforming the hand-crafted heuristic. Next, the use of action probability in the evaluation function improves performance over just using the learned values (distance to goal). Finally, the paper analyzes the runtimes for unsolved instances and discovers the existence of heavy tails on the left (mostly-long runs, few short runs). The paper develops some formalisms to characterize this behavior. The analysis and experiments suggest that a strategy involving more frequent restarts can improve overall performance in such cases.

---------

UPDATE: I thank the authors for their responses. After reading the other reviews, I'm more positively inclined towards the paper and have updated my scores to reflect this.
strengths_and_weaknesses: Strengths
  + The paper investigates into the performance of best first search with learned knowledge (DBFS) on challenging planning problems. This is an important and potentially impactful analysis of a popular learning to search method on a challenging problem.
  + The paper includes a small algorithmic contribution (simplified eval function), a number of empirical insights into the performance of DBFS in Sokoban and an analysis of the phenomena of left heavy tails to better understand the unsolved problem instances.
  + The DBFS algorithm can solve a significant fraction of hard problem instances, which the state of the art solver fails on. This seems like a significant performance improvement on hard Sokoban instances. (Right?)
  + The paper investigates the hardest Sokoban instances and discovers the existence of left heavy tails. This seems like a novel insight, as far as I can tell.

Weaknesses
  - One of the main claims of the paper is that the randomization injected by dropout is important. However, I was unable to find any supporting evidence for the claim other than a single sentence ("We did a grid search ... and found 30% reached the best performance") The size of the performance gap with and without dropout is unclear to me. What have I missed?
  - The paper is reasonably well written but I thought it didn't quite flow on my first reading. For example, the concepts of optimal speedup of Las Vegas algorithms and right heavy tails are briefly introduced early in the paper (Section 2) but only used to analyze the unsolved problem instances much later in Section 5. Introducing these concepts in Section 5 might improve the flow.
  - The empirical contributions of DBFS could be made clearer. For example, is there any other solver which does better than DBFS on the hard dataset task in Table 2?
questions:   1. How is the randomization introduced by dropout useful? (I'm guessing it allows exploring a different part of the search space after a restart. Is this correct?) How important is dropout to the overall approach? Are there any other randomization schemes that can be considered besides dropout? How might they perform?

  2. Besides Sokosolution and knowledge-guided BFS, are there any other known strong Sokoban solvers? (If not, this could be made clearer.)

  3. (Minor). Figure 5 (a,b) are missing their labels.
limitations: The authors have not discussed the limitations or social impact of the work. Since this work explores general search algorithms, I don't see any major negative social impact.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors attempt to understand the behavior of search in the planning domain when it is combined with a DNN-based heuristic function, namely in Sokoban. Their contributions include revealing the existence of left and right heavy tails, proposing an abstract tree model which explains this phenomenon and providing theoretical analysis. Their experiments show that policy networks can lead to avoiding exponentially large trees, which is an explanation to the efficiency of the DNN-based heuristic function. They finally show that random restarting plays an important role to avoid both tails. 

strengths_and_weaknesses: The heavy-tailed distribution is a well-known phenomenon observed in many combinatorial search domains including SAT and CSP. This paper has a very interesting observation which does not occur in those domains but which newly occurs in the planning domains.

One very minor comment is that the acronym of DBFS has been already used in the following paper well known in the planning community. Therefore, I would recommend them to use a different acronym if possible. 

https://ojs.aaai.org/index.php/AAAI/article/view/8004

As a side node, this DBFS (Diverse Best-First Search) uses randomization to avoid the plateau of search due to heuristic values. It uses neither the notions of the left-heavy tails nor critical nodes. But perhaps Diverse Best-First Search might have some relations (e.g., why does avoiding the plateau leads to an improvement?) to these notions investigated by the authors, which might generate some important future research.

In summary, this is a very interesting paper and I enjoyed reading it. 
questions: I do not have any specific question.

limitations: N/A
review_title: null

Meta-review: metareview: The reviewers found this empirical paper's observations and explanations regarding search guided by a DNN-based heuristic insightful and definitely worth publishing, despite the fact that the study was done on only one benchmark, Sokoban.
confidence: Certain
Decision: Accept