Venue: ICAPS 2021 Workshop HSDIP

Reviews:

final_score: rating: Accept
review_content: The paper introduces a method that attempts to estimate the progress of a heuristic search algorithm by employing LSTM networks. Progress is measured in terms of the number of expanded states.

The authors use the heuristic value, branching factor, f and g values, and the serial number of states as input features of the net. This is extended with static features such as the minimal heuristic value seen so far. The net predicts the search progress.
The net architecture is based on some preliminary experiments.

The authors compare their approach to existing search progress measures that are not based on learning.

The paper is mostly well-written and fits the scope of HSDIP. 

Comments:
- I think the evaluation could be done in a more systematic manner. You analyse that in different phases of the search, your approach performs differently. Why not split the search into "start, middle, end" and look at these three phases individually. An analysis similar to Table 1 for each of the phases would be interesting!
- At the end of the evaluation, you say that ODTS outperforms SD because it is training on multiple domains. Couldn't it be that this is just because of more data being available to the training?
- I disagree with the first part of your conclusion. The known estimators are based on a very simple analysis of the search progress to be as general as possible. Since the features used are similar to the input of your nets, it is not surprising that your approach performs better in terms of prediction accuracy. In the end, the net can learn characteristics of the heuristic, which the previous approaches do not take into account.

Questions:
- LMcut is probably somewhat "friendly" for your approach, since it behaves quite consistently. Do you think that the results will carry over to heuristics that are based on abstractions or landmarks?
- Similarly, the behaviour of GBFS can vary significantly across instances of a domain. Do you expect your models to be able to capture this?
- Your approach seems to generalize quite well across different domains. What about using different heuristics (potentially only within a single domain, so SD)?
- How long does the training take?
- What's the motivation for using Pyperplan and its benchmark set? Why do you not use all IPC benchmarks? It seems like a larger training set could be beneficial.

Minor:
- Intro:
-- "black-box search problem*s*"
-- "before *the* search starts"
-- "we view the search algorithm as *a black* box"
- Search Progress Estimation: "has already expand*ed* Exp nodes"
- Learning to Predict Search Progress: 
-- "ancestors ** m layers up"
-- "number of successor* node*s*"
- Related work:
-- the indentation of the method descriptions looks a bit strange
-- VeSP: "Estimator (VeSP) estimator"
- What is "\^{c}"?
- expended => expanded (several times)
- Table 1 is too wide


review_title: The paper suggests to use LSTMs to estimate search progress and compares to hand-designed features

final_score: rating: Weak Accept
review_content: **Tittle:Learning To Estimate Search Progress Using Sequence Of States**

### Summary
The authors extract simple features from the last 30 nodes (and their 2 closest ancestors) expanded during the execution of a search algorithm. They use those features to train a recurrent neural network to predict how far the current search has already progressed. They compare themselves to other online search progress estimators and show that their approach produces better predictions (smaller absolute errors).

The authors present three different training regimes, training their estimator on instances of other domains, the same domain or training on instances of other domains and then fine tuning on few instances of the same domain. The approach with fine tuning performs best.

### Feedback
The prediction of the search progress is an interesting problem. In the extreme case, this could be used to probe how fast an algorithm is on a problem instances and to decide if the portfolio should continue with this algorithm or choose another one. I was surprised to see how uninformed all estimators were. 

I think the approach and results from this paper are interesting and fit wonderfully the workshop. The results should be presented and discussed. At the same time, I think that especially from a stylistic point of view the paper has to be improved a lot (see minor issues below).

One of my biggest issue is with Figure 3. It shows how the mean absolute prediction error changes during the search for three selected instances. Firstly, I think it is really hard to understand from the plots what is happening. We directly see that all estimators show a V shape (although this shape is more pronounced for some estimators). How is this happening? This V shape means that the estimators approximately predict a constant value during any point of the search. The closer the progress of the search comes to this constant prediction, the smaller becomes the error. But any estimator which predicts a constant is uninformed and useless for this setting. **Add a baseline which predicts a constant value.** This helps the reader to interpret the plots correctly. As the estimators estimate mostly a constant, I though about the best constant and found out that if you always predict 0.5 you obtain the minimum mean error of *0.25*. Without any learning I give you a baseline with an mean absolute error of 0.25. All other baselines (see table 1) have a greater error. Can you please elaborate on the baseline techniques and my baseline. Have I understood something wrong, is there an error in the table, or what is the difference in the setup of the baseline techniques that justifies their bad performance? This reinforced my opinion that I would like to see the offline approaches as baselines too. At least you algorithm is better than my trivial baseline.

### Questions
- Why did you ignore offline approaches? I imagine that an offline approach predicts the number of expansions expected to solve the problem. If this is the case, it is very simple to transform an offline approach to an online one. Just add a counter which counts the number of expanded states and the progress is measures as $max(1,\frac{counter}{\text{predicted expansions}})$.
- Observing that many baseline estimators are almost constants, means that they are uninformed. I did not read up the relevant literature. Was this also observed in the original papers? If not, do you have an idea what is the important difference in your and their settings?
- A neural network with 15+ layers seems pretty large from the relatively few input features. You stated that the parameters were manually tuned. Have you tried using fewer layers? If yes, what where the results? If no, why not?

### Minor Issues
- *Background, LSTM, first paragraph*: This is a very long introduction to LSTM with few relevant information.
- *Background, LSTM, remaining paragraphs*: Following the textual description of an LSTM is very hard. Considering that most researchers at the workshops are no experts in the field of neural networks, I think this section has to be reworked. My suggestion: Add a figure visualizing an LSTM and shorten the text a lot (the schema contains the same information).
- *Background, Heuristic Search*:
	- $A$ is not introduced
	- Explicitly state that 0 is included in the co-domain of an heuristic: $h: S \mapsto \mathbb{R}^+_{0}$
	- "We will use $f$, $g$ and $h$ [...]". Which of the two previously defined $f$ functions do you use? $f_{A*}$, $f_{GBFS}$, or always the $f$ function of the search algorithm used (in the later text it is written that this will be the $f$ function of the search algorithm. Please clarify this here)?
- *Definition 1*: I would used $\mathbb{E}_A$ instead of $Exp + Rem_A(Exp)$ in the denominator, but that is your choice.
- *Figure 1*: The caption writes: "following the parent pointers". The plot denotes the parents as *Father* and *Grandfather*. Please unify this. I would simply use "Parent(N-X)" and "Parent(Parent(N-X))"
- *Figure 2*:
	- Update label: Distribution of *what* in the data? E.g. 'Distribution of the required expansions over all IPC instances.'
	- y-label: "(required) node expansions" or just "expansions"
	- Remove title of the plot. It's content is already in the caption of the figure.
	- x-label: What are the instance numbers? I am not aware of an instance numbering across domains. Change this to just "instances" or remove this completely.
	- Alternative/Suggestion: Change the plot to show a cumulative distribution: x-axis = number of required expansions, y-axis = probability, caption= something with cumulative distribution function showing how many expansions are required to solve the given instances
- *Empirical Evaluation, Benchmarks*: LMCUT -> LM-Cut
- *Empirical Evaluation, Empirical Results:* "In the other 8 domains, [...]" Skip those 5 words, they are more confusing than helpful.
- *Table 1:*
	- do **not** use camel case (Mean Absolute Error for Each ...)
	- "Domain/Estimator Combination" -> domain and estimator combination
	- Remove the "Avg problem" line (and the sentence speaking about it). It is biased. I was glad reading how you averaged within a domain and across all domains to get rid of biases. Just focus on "Avg domain".
	- I would like to see the standard deviations, but I also think the table is already hard to parse. If you can do something about it, I would be very interested in seeing your solution :)
- *Empirical Evaluation, Empirical Results, 3rd paragraph*: 
	- This is about style. Figure 3 is just a plot, it does not have any intrinsic motivation. Thus, do not write that Figure 3 is evaluating something, but that YOU are evaluating it and Figure 3 shows the results.
	- State **in the text** the evaluated instances or at least that they are from different domains.
	- State how you selected the used instances for the evaluation.
- *Table 2:* Remove row "Avg problem"
- *Figure 3:* 
	- no camel case in the caption
	- add to the caption something like "for all three training regimes"
- *Figure 4:* try to reuse the same colors as in Figure 3 for the same labels and if possible use new colors for new labels.
- *References*: In the Pyperplan references you state the DOI thrice and in another reference you state the DOI twice. This is ugly and redundant. Please update those references.
review_title: Review

Meta-review: Both reviewers are positive about the paper and recommend acceptance. We ask the authors to address the comments raised by the reviewers in the camera-ready version.
Decision: Accept