Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This work proposes a method for search, considering the transition model is given. The proposed framework works as follows: given a state, a subgoal predictor is used to predict subgoals k-steps ahead. A policy network is used to get the actions to reach those subgoals and a value function is used to judge the value or benefit of being in a state. All of these are trained on an expert set of demos. Empirical results show that this algorithm performs better than BestFS or MTCS. 
main_review: - I understand that the Low-level policy, value function, and subgoal predictor are learned using expert data. The subgoal is trained to predict the state k-steps from now. Is the predictor deterministic? How do you get multiple subgoals for a single current state. Also, what is the beam-search in Algorithm 3 optimizing?

- If I have to compare with just BestFS or MCTS at a very high level, then the proposed method basically breaks down the next action into two parts - generate subgoals, and then get actions to go those subgoals. It is not clear to me exactly why this is helping the search process? This is mentioned in Line 131, but with no solid intuition behind it.

- Subgoals have been studied in the past for policy learning [A] and efficient imitation learning [B], except, the proposed method is applied to a special case of the settings considered in these works. The authors should discuss and compare the novelty w.r.t. these works.

- What is the sensitivity of the proposed method to the number of expert demos?

[A] Automatic Goal Generation for Reinforcement Learning Agents, ICML 2018
[B] Learning from Trajectories via Subgoal Discovery, NeuIPS 2019
limitations_and_societal_impact: It is not clear to me why adding a subgoal predictor would help. My thought is that it should have been inherently learned by the network. Also, comparisons/discussions with some subgoal-based methods are missing.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper introduces a subgoal generator to accelerate the search
process to solve a given task. 
main_review: The present paper introduces an algorithm that uses a
subgoal-generator to generate subgoals which are then driven to by a
local policy, and demonstrates its use in the context of Sokoban,
Rubik's Cube, and INT (theorem prover).

The algorithm is relatively straightforward and simple to implement
and shows good improvement compared to existing methodologies.

The reviewer found it not obvious to understand how the subgoal
generator generates its subgoals. What does the prediction refer to?
Where does the reference come from? There is some implicit mentioning
of expert training, however, that means that the algorithm needs some
seeding. More discussion is now needed to make clear what the
advantage of using such an algorithm is. It is mentioned that there is
some out-of-distribution generalization ability, which is probably the
most interesting aspect of the study, but here more details as to how
that emerges/works might have been useful in addition to experimental
benchmarking, especially in a conference such as NeurIPS.

- line 131: it is crucial for the understanding of the algorithm to
  explain what is being predicted. There is only some mentioning of
  expert data collection, but this is the core part of the algorithm
  and needs to be more detailed. Note that Algorithm 3 is not much
  more illuminating - what does the Beam_Search do here, and what does
  the probabilities bookkeeping do?
- Footnote 3: AlphaZero spelling
- Fig. 4: "increase the distance" - I would treat "12%" as a plural

limitations_and_societal_impact: Limitations appropriately discussed. 

At this stage of discussion, I do not consider the Societal Impact discussion relevant to this paper.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper developed a subgoal search approach, called kSubS, for identifying subgoals of complex reasoning tasks. Leveraging the developed search approach, a few systems were developed, including two that were referred to as MCTS-kSubS and BF-kSubS in the paper. The systems were tested using domains of Sokoban, Rubik's cube and INT. Results showed that the developed system outperformed baselines of AlphaZero and BestFS. 
main_review: Overall, the paper is technically sound, and the results to some extent showed the effectiveness of the proposed methods. The three benchmark problems are well selected. There are a few issues. 

It's believed that the developed approaches' performance highly depends on the quality of the collected expert data. To make a strong case, it's necessary to compare the proposed methods to those from the literature that also leverage expert data, and show that the proposed methods require less data, are robust to low-quality data, or can better utilize the data to improve the search process. 

It's unclear from the paper how SubS and kSubS (used interchangeably in the paper) are different from each other. 

There is the following 2021 paper that learns imagined subgoals for RL. Since the paper is very new, it's not a problem of not citing the paper -- just a reference.  Goal-Conditioned Reinforcement Learning with Imagined Subgoals, ICML 2021   Also, the reviewer is curious if possible the developed subgoal search methods can be applied to RL-based problem solving methods. For instance, the following paper showed that RL methods can be effective to Rubik's cube (one of the three domains of this paper) as well.  "Solving the Rubik's Cube with Approximate Policy Iteration". ICLR 2018

It's not evident that how to utilize training data from experts to speed up the search process is a non-trivial problem. Intuitively, the subgoals decompose a complex problem into subproblems that are easier, c.f., the original problem. So the idea is quite simple, which is not a problem by itself. But the reviewer is curious if there are more competitive baselines from the literature that can be included to improve the experiment section. If this is really the first work of using supervised learning methods to identify subgoals for problem decomposition, then it's necessary to make it clear in the paper. 
limitations_and_societal_impact: Adequate.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper considers the problem of finding a sequence of actions that, starting at an initial state, achieve a goal. The search graph is known in this problem: transition model is known, states are fully observable and actions are deterministic. That means any search algorithm could solve the problem for graphs like Breadth First Search, Best First Search or A*.

The paper proposes to abstract the transition function by mapping a state into a set of steps $k$ steps ahead. When $k=1$, the abstraction corresponds to a subset of the states that can be achieved by applying one action.

The use of lookahead well-established idea in the search community, in different forms, but it seems under-explored for data-driven methods for search. So, the line of work is original.

I celebrate that the paper focuses on deterministic observable known models because this setting allows understanding better the relationship between "search" and "learning". That relationship is a the core of the tension between data-driven and model/reasoning-driven methods.

The research question about the value of predicting $k$ steps ahead is interesting. On the one hand, data-driven methods are combined with search because they perform better than following predictions greedily. AlphaZero is "exhibit A". On the other hand, bounded-length predictions are more likely to remain within the practical scope of data-driven methods.

I do have a serious problem with the use of the word "**analog**" across the paper. I think we cannot write papers about "analog of human intuition" because "analog" implies similarity or comparison. It's a very strong word. I could accept "inspired by an aspect of human intuition", but I find it unacceptable because it sounds like we know what human intuition is. I might be wrong. If that's the case, please justify that using the relevant literature. Otherwise, please just state how the manuscript would be revised so this expressions have a lower tone.

The findings are very interesting. Fig 2 is the most insightful.

However, I think the manuscript have some confusions that make the contributions less clear. 
Only three domains are considered. Two use the same setting with a shared family of hyperparameters. A third one uses a different setting.

main_review: I am confused by the wording of the contributions. Therefore, let me summarize them using the same numbers as in the paper. 

1. Subgoal Search using transformer + search algorithm is strong.
2. Same transformer per se is strong.
3. The value functions used in the paper are weak.

The main issue is that they confound the algorithms used with the research question. The 3rd contribution is not about *value functions* in general but about the value function used in the paper. The other two contributions get diluted by 

* Using different setup in Sokoban vs the other two domains.
* The lack of comparison with search algorithms.

A minor weakness is

* Given the effort devoted to tuning the algorithms, it becomes relevant to try planning algorithms suitable for this deterministic setting.

This is NeurIPS, so this illustration might be pertinent for this setting, deterministic and where the model is known.

* If the states are atomic, then both search and goal-conditioned RL solves the problem of finding a sequence of actions.
* A state space is factored when any state can be described a set of factors, like predicates+objects. For instance, for sokoban, it could be agent-at(1, 3), block(3,4), etc. In this setting, classical planners find a solution. They receive a high-level description of the model or a simulator like an OpenAI gym.  

The evaluation is done in three benchmarks:

* Rubik's cube. Well studied in the search community. 
* Sokoban. Well studied in the search and planning communities.

A simulator-based planner is compatible with this setting, so a strong paper must compare with it. I won't ask for that in a conference submission, but planning algorithms cannot be ignored.

REQUIRED: in a related work section, please comment on these two lines of work:

* Classical Planning in Deep Latent Space: Bridging the Subsymbolic-Symbolic Boundary. Masataro Asai, Alex Fukunaga. This one is more flexible than required because it can deal with raw signals.
* Frances, Guillem, et al. "Purely declarative action descriptions are overrated: Classical planning with simulators." IJCAI 2017. This one requires a factored state. They test with Sokoban.

However, the research question is compatible with a simple question that would make the contribution aligned with the research question: is "k step prediction making the difference?"




REQUIRED: 
* Please clarify what if BestFS is and what it shares with BF-kSubs. 
* Is BestFS equivalent to "k=1"?

REQUIRED: Please make sure the manuscript or your comments report experiment results for the following variations. (They might already be in the paper, depending on what is BestFS implementing).

1. Other values of $k$ for the other two domains besides Sokoban. Otherwise, this statement of page 3 is misleading: "We show, perhaps surprisingly, that this simple objective is an efﬁcient way to improve planning, even for small values of k, i.e. $k \in \{ 2, 3, 4, 5 \}$". 
2. When possible, report complete results using Dijkstra. (Sect 4.5 implies part of the work is done)
3. $k=1$
4. $k=1$ and algorithm 3, sub_generate, generates all the states. That is setting $C_3 = C_4 = \infty$. Adjust the sokoban generation B.2 accordingly. In this scenario, get_path should always return the action that is possible. Given that the actions are coming from the policy $\pi$, I don't take that for granted.

This possible lack of information on the points 3 and 4 is the weakest aspect of the paper, as that's the main research question.

REQUIRED:
* Please focus 3rd contribution on the observation about value errors. The importance of subgoal search is covered in the other two contributions.

---- 

Thank you for your comments. I let my comments in the discussion. Just updating the scores.
limitations_and_societal_impact: N/A
review_title: null

Meta-review: This paper presents an interesting approach to problems with long decision horizons, by generating and planning to subgoals on the path to the full solution.
After a discussion largely around clarifying some points in the paper, the reviewers all felt that this paper should be accepted.
The authors should update the descriptions in the paper as suggested by the reviewers.
Decision: Accept (Poster)