Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper presents an algorithm –AdaSubS– that can be trained and configured to solve deterministic search problems. The key idea is to consider multiple lookaheads that would be explored with lower-level policy. The ablation study confirms the effectiveness of the idea in challenging domains.

strength_and_weaknesses: # Strengths

I'll be short here. See discussion below on my interpretation of the results.

- The paper is mostly well-organized and well written
- The ablation study confirms the role of the specific modules. 
	- I appreciated the detailed algorithms in the appendix
- The conclusions are very clear, at least for the domains and conditions where it was tested.

# Weaknesses

- Scholarship: I think that Czechowski et al. (2021) should be mentioned as a starting point. The manuscript seems timid about it. I think a stronger paper would make that clear. Here is two key quotes:
	- > "kSubS is the first general learned hierarchical planning algorithm shown to work on complex reasoning domains Czechowski et al. (2021) (called BF-kSubS there), attaining strong results on Sokoban and Rubik’s Cube, and INT. kSubS can be **viewED** as a non-adaptive version of AdaSubS realized by a suitable hyperparameters choice: a single subgoal generator and inactive verifier (t lo = 0,t hi = 1)."
	- > "Most of the hyperparameters, both for training and evaluation, follow from Czechowski et al. (2021). The most important parameter of AdaSubS is the set of k-generators to use and the number of subgoals each of them generate.
	- Czechowski et al. (2021) introduced the idea of a search to achieve the goal in k steps. The paper has multiple references on how they used the same parameter.
- Scholarship: the paper does not review the state of the art on this problem. If the state of the art is not in the same scope, then related work should be discussed anyway.
	- For instance, see Cameron et al, IJCAI 2021, below.
- BestFS is not explained well enough
	- (See before my comment on contrib 2 below)
	- Given this is the most important baseline, the paper must make sure that the algorithms was properly tuned.
	- It seems it's a simple modification respect to the others, but perhaps there are hyperparameters that would work better for BestFS in comparison with AdaSubS
- No limitations are discussed (see my first question below as an instance)

# Questions: PLEASE ANSWER THESE ONES

- Does the algorithm keep a list of close nodes?
	- Do you cache the result of evaluations in Alg 1 or Alg 2?
	- It seems Alg 2 migh run predictions multiple times on the same nodes.
	- If a node is visited with k = 8, would it also be visited by GET_PATH with k = 2?
- How would AdaSubS behave in the following case?
	- Suppose a degenerated search space where 
		- There are two action applicable actions in each state, but at least one of them always leads to a dead end.
		- Suppose further that there is actually only one path to the goal.
		- For a state in the path to the goal, there are two childs: one to the next state in the plan, the other one child that leads to a dead end by a short binary subtree, all of the deadends.
	- Suppose the same list of k used in Sokoban: [8, 4, 2]
	- Suppose that all the models are not very good. They choose uniformly over their options. Let's disable the verifier.
	- It seems that AdaSubS would expand multiple times the nodes in the subtrees that lead to deadends? Moreover, Alg 2, GET_PATH doesn't seem to have any memory. So, if the models are expensive this could grow quickly.
	- (If this example doesn't work, please attempt to provide another example where AdaSubS might deteriorate)
- Would you comment on the following paper published in IJCAI 2021?
	- Efficient Black-Box Planning Using Macro-Actions with Focused Effects. Cameron Allen, Michael Katz, Tim Klinger, George Konidaris, Matthew Riemer, Gerald Tesauro. https://arxiv.org/abs/2004.13242
	- Macro-actions are sequences of low-level actions. They create them by attempting to change a few variables in the problem.
	- They test in Rubik's cube.
	- They tested reusing macros in the same domain.
- Why does the evaluation support the 2nd main contribution?
	- End of sect 1 says: "We present a comprehensive study of adaptive methods, showing that they typically outperform non-adaptive ones". But given the lack of comments about other potential algorithms, this might not be true in general. 
	- I'd accept something like "they outperform similar algorithms without the adaptation". It seems that the argument is that given that BestFS and the studied algorithms share common elements, then the value of the contributions is justified.
- How were the hyperparameters set? 
	- I see the values in appendix F, but I don't see how they were set. Page 19:
		- > Based on experimental results, we have chosen generators of 8, 4, and 2 steps for Sokoban, 4, 3, and 2 steps for the Rubik’s Cube, and 4, 3, 2, and 1 step for INT. In the first two domains, the longest generator match the one used for kSubS.
	- Explaining that would help readers to understand the effort of using the algorithms in another setting.
	- Please clarify the computation cost of arriving at these hyperparameter values? For instance, how expensive is to realize that a set of hyperparameter values are not the most adequate?
- Are the hyper-parameters of BestFS set in the best possible way?
- Would you mention the multi-queue algorithms in a revised version of the paper? Where? (See that in my section "Scholarship on search and planning")

# Other changes

- Please mention the number of subgoals generators and the values of k early in the paper. 
	- Table 1 shows that the list k is one of the most important factors for performance.
	- The number of goals generated changes fundamentally the search space. 
- In the main body, it should say that BestFS with a trained policy, and how it's implemented. (See my comment on contribution 2)

# Minor questions or comments

- Page 5: > Rubik’s Cube is a celebrated 3D puzzle with over 4.3 × 10 18possible configurations.
	- Please cite Korf's paper
- Page 9. Verifier: precision and recall
	- I’d say the verifier increase accuracy only in a small budget in INT.
- Page 6: "Shaded areas indicate 95% confidence intervals." How many trials?
- Page 15, Sect "Computational budget analysis" 
	- says: Tables 3, 2 and 4 present the number of calls to each component per 1000 episodes.
	- Is this testing or during training?
	- Are those 1000 instances the same for all the algorithms?
	- Is that the total number for 1000 episodes? The common practice in deterministic search is to report numbers per episode.
- page 17:
	- > Rubik’s Cube. To construct a single successful trajectory we performed 20 random permutations on an initially solved Rubik’s Cube and took the reverse of this sequence. Using this procedure we collected 10 7trajectories"
	- are there symmetric movements? Are these optimals path? See comment by Clemens et al.
- Page 18: 
	- > "ρ BFSworks in the following way. First, it uses a trained policy network to generate actions to investigate. Specifically, for INT we use beam search to generate high probability actions (it is necessary as for INT we represent actions as sequences, following Czechowski et al. (2021)). Then, it uses these actions to get a state that follows a given action (note that all our environments are deterministic). Finally, we treat returned states as our new subgoals, which are easily found in one step by the low-level policy."
	 - It's not clear what happens in other domains. 
- page 15: please say this in the main body, not just in the appendix:
	- > used for sampling predictions from the subgoal generators – the only component that outputs a set of predictions.

clarity,_quality,_novelty_and_reproducibility: The work is novel and insightful. The significance can be lower if the algorithm were harder to configure. The interaction of the attempted lookahead with the subgoal generation is interesting. The paper is clear enough, except for what I commented above.

Now I discuss at length some connections with related literature.
(This aspect is a weak point of the manuscript)

# Scholarship on search and planning

This is, I think, the 2nd time I see this paper submitted. I'm glad about the changes. I finally have an interpretation of what's going on. The unpacking of the algorithms in the appendix really helps. In general, I'm not very interested in the verifier. The interesting part is the depth.

Let me first discuss multi-queue in comparison with search algorithms used for planning.

First, PDDL-based planners are not comparable with the algorithms proposed here because of two reasons:
- They don't have the chance to train. Instead, they recieve the problem in PDDL, a high-level language for planning. For the planner, it's the first time they see that problem. Rubik's cube and Sokoban could be expressed there.
- Hyper-parameter tuning is only about the search and heuristics. Moreover, the evaluation tends to focus on finding the parameters that would solve multiple domains. PDDL-based planners intend to be autonomous tools, not human tuning involved.
- So, PDDL-based planners offer a lower bound on performance.
	- I don't think it's necessary to review those numbers here, but I'd expect so in a journal version of the paper.  

Second, work on heuristic search –like Korf cited in the paper– it's the opposite of domain-independent. The heuristics are heavily adapted to the domain. So, they are not comparable but they offer an upper bound for learning-based algorithms. 

Now, IterativeMixing is similar to alternation queues used in heuristics search algorithms used for PDDL-based planners. 

That was first proposed by LAMA.
- Richter, Silvia, and Matthias Westphal. “The LAMA Planner: Guiding Cost-Based Anytime Planning with Landmarks.” Journal of Artificial Intelligence Research 39 (September 21, 2010): 127–77. https://doi.org/10.1613/jair.2972.

Nowadays, LAMA is usually tested as a configuration of the very flexible Fast Downward.
- Helmert, M. “The Fast Downward Planning System.” Journal of Artificial Intelligence Research 26 (July 12, 2006): 191–246. https://doi.org/10.1613/jair.1705. Sect 6.4 Multi-Heuristic Best-First Search
	- > "As an alternative to greedy best-ﬁrst search, Fast Downward supports an extended algorithm called multi-heuristic best-ﬁrst search. This algorithm differs from greedy best-ﬁrst search in its use of **multiple heuristic** estimators, based on our observation that different heuristic estimators have different weaknesses. It may be the case that a given heuristic is sufﬁcient for directing the search towards the goal except for one part of the plan, where it gets stuck on a plateau. Another heuristic might have similar characteristics, but get stuck in another part of the search space.
	- > "Various ways of combining heuristics have been proposed in the literature, typically adding together or taking the maximum of the individual heuristic estimates. We believe that it is often beneﬁcial not to combine the different heuristic estimates into a single numerical value. **Instead, we propose maintaining a separate open list for each heuristic estimator, which is sorted according to the respective heuristic. The search algorithm alternates between expanding a state from each open list**. Whenever a state is expanded, estimates are calculated according to each heuristic, and the successors are put into each open list.

Fast downward is very flexible:
- https://www.fast-downward.org/PlannerUsage
- https://www.fast-downward.org/Doc/SearchEngine

Other search engines for planning also incorporate multiple queues.
- https://lapkt-dev.github.io/docs/modules/

Actually, LAPKT has priorities over queues:
- https://github.com/LAPKT-dev/LAPKT-public/blob/d54b68fcc67d5d75ea40b3921220c29f49c71814/include/aptk/at_bfs_dq_mh.hxx#L353

Some planner "preferred operators", choose first a queue that tends to have fewer notes. If that's empty, they use the other one.

**That's similar to what AdaSubS is doing, as it always tries to expand over more steps first.** 

Others algorithms can also be seen from this perspective.
Strongest-first  behaves more like selecting from the queue, breaking by k. (Can actual V values be the same for two different nodes?)
Longest-reachable becahse more hierarchical, like options.

## Some references on Sokoban and Rubik's cube

- Sokoban: https://github.com/AI-Planning/pddl-generators/tree/master/sokoban
- npuzzle, simpler to understand: https://github.com/AI-Planning/pddl-generators/tree/master/npuzzle
	- Rubik is a variation of that one. It's a challenging problem for planning
- A Comparison of Abstraction Heuristics for Rubik's Cube. Clemens Büchner, Patrick Ferber, Jendrik Seipp, Malte Helmert. https://icaps22.icaps-conference.org/workshops/HSDIP/
	- Uses pattern DBs, like use by Korf, but as planning
	- > None of the heuristics is able to solve problems where the optimal solution requires more than 13 rotations. Ac- cording to Rokicki et al. (2014), this restriction allows us to solve only 0.0001% out of the 4.3 · 1019 possible states of Rubik’s Cube. In comparison, Korf (1997) was able to optimally solve tasks at least 18 rotations away from the goal.1 The set of initial states with optimal cost 18 or less makes up approximately 98% of all possible initial states for Rubik’s Cube (Rokicki et al. 2014).
- Büchner, Clemens. “Abstraction Heuristics for Rubik’s Cube,” n.d., 44.
	- See here is a demo on the 3x3x3 (seems to be an undergrad project)
		- Muppasani, B., Pallagani, V., Lakkaraju, K., Srivastava, B., & Agostinelli, F. (2022). Solving the Rubik’s Cube with a PDDL Planner.
		- https://www.researchgate.net/profile/Bharath-Muppasani/publication/362555735_Solving_the_Rubik's_Cube_with_a_PDDL_Planner/links/62f13f8388b83e7320bb63c0/Solving-the-Rubiks-Cube-with-a-PDDL-Planner.pdf
	- Rubik's 2x2x2: https://wu-kan.cn/2019/11/21/Planning-and-Uncertainty/

I suggest the authors participate in the Planning and Learning competition that was just announced. https://ipc2023-learning.github.io
summary_of_the_review: The ideas are novel, the components of the algorithm are well-studied to understand their role, and the benchmarks are appropriate.

I recommend acceptance, but I might lower my scores depending on the answer to my questions.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper introduces a new algorithm Adaptive Subgoal Search (AdaSubS), which aims to generate the prospective sub-goals iteratively to generate a good action plan. The system has innovative components of a subgoal generator, Conditional low-level policy (CLLP) to find action steps and a verification algorithm to swiftly prune the faulty sub-goals obtained.

The authors present comprehensive results to show that adaptive methods work.

strength_and_weaknesses: Strengths:
● The paper is well-structured and easy to read.
● Introduction of novel search algorithm benefiting from both the planning and
learning methods.
● The experimental section is very well organized and provides good insights into
the complexity of the domains considered.
● State-of-the-art results on inequality theorem prover INT.

Weakness:
- Although the paper shows advancement in learning-based planning, the results are not surprising given that there is a large body of work in search-based planning to show that adaptive action selection / heuristic selection is beneficial in planning. See work like "Real-Time Adaptive A*" or historical perspective in a planning book like Ghallab et al. See also recent dissertation titled "Adaptive Search Techniques in AI Planning and Heuristic Search" by Maximilian Fickert. 
- A problem with this like of work is that the algos are not complete. They are not guaranteed to  always produce a plan even if such a plan exists. This point should be highlighted. 
* A system architecture diagram depicting the flow of the algorithm would have
been more comprehensible. It is hard to understand if all the chosen sub-goals
at a given node are being explored.
● It is mentioned that the verifier network is a binary classification model, and
if the network fails to predict the feasibility of the sub-goal, the algorithm
falls back on to CLLP to decide whether to keep or discard a given subgoal. But
it is not clear how CLLP is used for this purpose as it generates an action
plan between two given states. Does an empty sequence from CLLP mean the
sub-goal is being rejected?
● The authors commented on the out-of-distribution generalizability of the
inequality theorem prover INT, however, it could have been interesting to see
the status of the other domains.
clarity,_quality,_novelty_and_reproducibility: The work is well-written and clear. The experimental settings are well explored and
the comparative analysis of the different algorithms gives a better understanding of
the performance on the complex domains. The two main blocks of the algorithm (the
sub-goal generator and the verifier network) are inspired by the existing works which
are clearly mentioned in the related work section.

summary_of_the_review: The paper introduces a new algorithm called Adaptive Subgoal Search (AdaSubS). It covers related work and provides extensive experimental results provided which give an overall insight into the performance of the algorithm on the different problems chosen. However, the paper needs to add details justifying the need for multiple blocks for sub-goal verification and contextualize the properties of the planner. The entire flow of the algorithm needs to be summarized in a flow chart format. The memory and time usage details of the algorithm needs to be mentioned.

The paper should also connect with well known results in search-based planning on adaptive action selection and heuristic selection. Otherwise, it is re-discovering known behaviors in a new setting.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The authors proposed an algorithm for planning that uses learned components for generating subgoals (states up to k steps away), generating one low-level action between two states (conditional low-level policy, CLLP), verifying whether CLLP can find an action between two states, and predicting the distance between current state and goal state. The novelty from previous work (kSubS) is that multiple subgoal generators are used to adapt the planning horizon based on states. The modules are trained on offline datasets of puzzles with a large state space. Experiment results show that their algorithm is able to solve the problem of visiting fewer states. 
strength_and_weaknesses: The idea of learned subgoal generators with adaptive planning horizons is novel. The authors performed large-scale experiments on hard planning problems, comparing their methods both with baselines and also on out-of-distribution problems. That's very good efforts.

Before authors' rebuttal, the paper lacks important details in the main text for understanding. Though the authors stated the size of their training dataset. It's unclear how many problems were used for the results from Figure 2 and Figure 3. It would be helpful to state that in section 4.1 to make the results more convincing. It's also unclear whether the total wall time in Table 2-4 in the Appendix is from solving one problem or multiple problems, and how they compare to BestFS baseline. Without context, 3-26 hours seems too long for the title of the paper to be called "fast and precise." 
clarity,_quality,_novelty_and_reproducibility: The writing is sometimes too concise, leaving many implementation and experiment details in the appendix. The method and experiment design are novel. It's great that the authors have provided links to their codebase, which enables researchers to validate their approach and build upon their work.
summary_of_the_review: Overall it's an exciting paper, tackling hard planning problems with a novel learning-based algorithm. With more details provided about their evaluation, it would make a very strong submission.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper presents Adaptive Subgoal Search (AdaSubS), an approach to learning-driven search that uses proposed subgoals and a novel "verifier" network to make more direct and rapid progress towards the target state. The approach builds upon recent progress in this space, notably the BF-kSubS, by proposing subgoals thought to be reachable a distance "k" from the current state towards the goal (for multiple values of k). Combining this multi-distance subgoal generation with a verifier network to prune subgoal not expected to be easily reachable, the approach makes faster progress towards the goal and is more successful at solving state-space search problems than competitive baselines. The authors study a Sokoban and Rubik's Cube domain and "INT" a theorem proving domain.
strength_and_weaknesses: High-level comments
- [strong] The paper improves upon the state of the art. Search finds the goal in problem challenging problem instances including longer INT problems than are feasible for other approaches in this space. The results are solid and the analysis is comprehensive. This is a central strength of the paper.
- [strong] The choice of experiments is good and appropriate for the work.
- [weak] There is no discussion of optimal paths and the quality of the generated paths between the different approaches. For the INT domain, this is perhaps not possible, but for the other two domains, it would be very helpful to understand if the proposed approach improves success at the expense of plan quality, and the extent to which this tradeoff is made. While I do not believe inclusion of this discussion is essential, the paper would be improved by the inclusion of such a discussion.
- [weak] Sec. 4.5 (analyzing the quality of individual components) seems to omit a key piece of analysis: how well AdaSubS will perform without the verifier or how well the kSubS baseline will perform with the addition of the verifier. The central distinctions between the two strategies are (1) one versus multiple subgoal generators and (2) the inclusion of the verifier network. I do not believe there are any experiments that seek to understand how impactful the verifier. It could therefore be the case that the low level policy network is not particularly capable and that all of the performance improvement comes from the addition of the verifier, which bypasses that process. Some discussion or additional experiments (or a pointer to where these experiments exist) would be incredibly helpful for understanding.

Smaller comments, questions, and typos:
- Abstract: Though the abstract makes sense after having read the paper, the first couple sentences are not particularly clear on their own. Consider revising those to provide a clearer picture of what the central, unique insight is.
- Sec. 1: The figure in the introduction, while informative, is perhaps somewhat misleading, since robot motion is not studied in this work. Perhaps it would be more appropriate to use the Sokoban domain instead.
- Sec. 2: Typo (I believe) "variable environment variable complexity".
- In Sec. 3, the discussion of the thresholds could be clearer; it was not clear to me until later on that there were two thresholds.
- Algorithm 1: The 'return' statement may not find a path, in which (I believe) the procedure is to keep looping through paths if a feasible path is not found.
- Algorithm 1: Also, the first 'for' loop that pushes elements into T appears erroneous. There are not yet multiple values of 'k', since the subgoal network has not been queried; should this simply use k=0 and push the starting state into T?

clarity,_quality,_novelty_and_reproducibility: - [Clarity & Quality] the paper is very well written. There are a few gramatical issues (some mentioned below), but otherwise the paper is very easy to follow. The overall approach is well-motivated and clear. Moreover, the appendices are rich with detail and will be no doubt helpful for those who which to implement the approach for themselves.
- [Novelty] The paper grows the state of the art . The approach is novel, though the amount of novelty is not particularly significant.
- [Reproducibility] The authors have included all source code and documentation. The paper appears to be fully reproducible.
summary_of_the_review: This is a solid paper with a somewhat small theoretical contribution bolstered by impressive results in a challenging domain and clear and comprehensive analysis. There are still a few open questions that I believe the paper should address pertaining to the importance of a few of the components and comparison to baselines.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper presents an algorithm for adaptive subgoal horizons.  This appears to be a novel technique with significant potential.  Inititial concerns about scholarship have been addressed by the authors with updates to the paper.  There was considerable discussion between the reviewers and the authors and the paper has been generally improved as a result.

The main weakness is perhaps that the results are not surprising given that the value adaptivity in planning is well established.  But important ideas often look easy or trivial in retrospect.
justification_for_why_not_higher_score: I have given the highest score.
justification_for_why_not_lower_score: The only reason for giving this a lower score might be that it is not of sufficient interest to the general ICLR community to justify an oral.  However, the idea is novel and the empirical results seem strong on meaningful (not toy) applications.
Decision: Accept: notable-top-5%