Subgoal Search For Complex Reasoning Tasks
Authors: Konrad Czechowski
Tomasz Odrzygóźdź
Marek Zbysiński
Michał Zawalski
Krzysztof Olejnik
Yuhuai Wu
Łukasz Kuciński
Piotr Miłoś
Venue: NeurIPS 2021 Poster (2021)
Keywords: search
deep learning
hierarchical planning

Abstract: Humans excel in solving complex reasoning tasks through a mental process of moving from one idea to a related one. Inspired by this, we propose Subgoal Search (kSubS) method. Its key component is a learned subgoal generator that produces a diversity of subgoals that are both achievable and closer to the solution. Using subgoals reduces the search space and induces a high-level search graph suitable for efficient planning. In this paper, we implement kSubS using a transformer-based subgoal module coupled with the classical best-first search framework. We show that a simple approach of generating $k$-th step ahead subgoals is surprisingly efficient on three challenging domains: two popular puzzle games, Sokoban and the Rubik's Cube, and an inequality proving benchmark INT. kSubS achieves strong results including state-of-the-art on INT within a modest computational budget.

Subgoal Search For Complex Reasoning Tasks
Konrad Czechowski"
Tomasz Odrzygózdı* University Warsaw tomaszo@impan. ppl
University of Warsaw
k. w.c.chowskiii Smimuw.edee pl
Marek Zbysiński
Michal Zawalski University Warsaw wwwalski @uw edu, pl
Krzysztof Olejnik University of Warsaw k. ollejnnkk s student. uw. edu. pl
University of Warsaw 2.zyssinnsi@
students wwmmmmmmmmmmmmmmmmmmmmmm..mmmmm. edu. pl
Yuhuai Wu University of Toronto, Vector Institute
Lukasz Kuciński Polish Academy of Sciences 1kucinski @impan. pl
Piotr Mitoš
Polish Academy of Sciences, University of Oxford, deepsense.ai
toronto.......... ywuocs.toronto edu
pmilos@impan. pl
Abstract
Humans excel in solving complex reasoning tasks through mental process of moving from one idea to a related one. Inspired by this, we propose Subgoal Search (kSubS) method. Its key component is learned subgoal generator that produces a diversity of subgoals that are both achievable and closer to the solution. Using subgoals reduces the search space and induces a high-level search graph suitable for efficient planning. In this paper, we implement kSubS using transformer- based subgoal module coupled with the classical best-first search framework. We show that simple approach of generating k-th step ahead subgoals is surprisingly efficient on three challenging domains: two popular puzzle games, Sokoban and the Rubik's Cube, and inequality proving benchmark INT. kSubS achieves strong results including state-of-the-ee on INT within a modest computational budget.
Introduction
When confronted with complicated task, humans' thinking process often moves from one idea to related idea, and the progress is made through milestones, subgoals, rather than through atomic actions that are necessary to transition between subgoals [15]. During this process, thinking about one subgoal can lead to possibly diverse set of subsequent subgoals that are conceptually reachable and make promising step towards problem's 's solution. This intuitive introspection backed by neuroscience evidence [20], and in this work, present algorithm that mimics this process. Our approach couples a deep learning generative subgoal modeling with classical search algorithms to allow for successful planning with subgoals. We showcase the efficiency of our method on the following complex reasoning tasks: two popular puzzle games Sokoban and the Rubik's 's Cube, and an inequality theorem proving benchmark INT (55), achieving the state-of-the of-te---tte-rrt results in INT and competitive results for the remaining two.
Reasoning is often regarded as a defining property of advanced intelligence 40 18
The deep learning revolution has brought spectacular advancements in pattern recognition techniques and models. Given the hard nature of reasoning problems, these are natural candidates to provide
equal contribution
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

search heuristics [4.
Indeed, such a blend can produce impressive results 44 approaches seek solutions using elementary actions. Others, e.g. [30
45
37 I. These
34
24
utilize variational
subgoals generators to deal with long-horizon visual tasks. We show that these ideas can be pushed further to provide algorithms capable of dealing with combinatorial complexity.
We present Subgoal Search (kSubS) method and give its practical implementations: MCTS-kSubS and BF-kSubS. kSubS consists of the following four components: planner, subgoal generator, low-level policy, and a value function. The planner is used to search over the graph induced by the subgoal generator and is guided by the value function. The role of the low-level policy to prune the search tree as well as to transition between subgoals. In this paper, we assume that the generator predicts subgoals that are l step ahead (towards the solution) from the current state, and to emphasize this we henceforth add k to the method's ' abbreviation. MCTS-kSubS and BF-kSubS differ in the choice of the search engine: the former uses Monte- Canto Tree Search (MCTS), while the latter backed by Best-First Search (BestFS). We provide two sets of implementations for the generator, the low-level policy, and the value functions. The first one uses transformer architecture (49) for each component, while the second utilizes a convolutional network for the generator and the value function, and the classical breadth-firs. search for the low-level policy. This lets us showcase the versatility and effectiveness of the approach.
The subgoal generator lies at the very heart of Subgoal Search, being an implementation of reasoning with high-level ideas. To be useful in broad spectrum of contexts, the generator should be imple- mented as a learnable (generative) model. As a result, it expected be imperfect and (sometimes) generate incorrect predictions, which may turn the search procedure invalid. Can we thus make planning with learned subgoals work? In this paper, we answer this question affirmativel:: we show that the autoregressive framework of transformer-based neural network architecture 49 leads to superior results in challenging domains.
We train the transformer with the objective to predict the k-th step ahead. The main advantages of this subgoal objective are simplicity and empirical efficiency. We used expert data to generate labels for supervised training. When offline datasets are available, which is the case for the environments considered in this paper such an approach allows for stable and efficient optimization with high- quality gradients. Consequently, this method is often taken when dealing with complex domains or when only an offline expert available Furthermore, we found evidence of out-of-distribution generalization.
(see e.g. 42 52
Finally, formulate the following hypothesis aiming to shed some light why kSubS is successful: we speculate that subgoal generation may alleviate errors in the value function estimation. Planning methods based on learning, including kSubS, typically use imperfect value function-based information to guide the search. While traditional low-level search methods are susceptible to local noise, subgoal generation allows for evaluations of the value functions at temporally distant subgoals, which improves the signal- -ooiie ratio and allows a "leap over" the noise.
To sum up, contributions are:
1. We propose Subgoal Search method with two implementations: MCTS-kSubS, BF-kSubS. We demonstrate that our approach requires a relatively little search or, equivalently, is able to handle bigger problems. We also observe evidence of -iittii-iitiittiionn generalization.
2. We provide evidence that a transformer-basee autoregressive model learned with a simple supervised objective to predict states k-th step ahead is an effective tool to generate valid and diverse subgoals.
3. We show in our experiments that using subgoal planning help to might mitigate the negative influence of value function errors on planning.
We provide the code of our method and experiment settings at httpp://githubb.co com/ hwwpraasaarrceassaa-aaaaaa and a dedicated website htttp:://sits. google. com/ search
'The dataset for INT Sokoban be easily generated are publicly available. For the Rubik's Cube, we use random data or simple heuristic (random data are often sufficient for robotic tasks and navigation.) Foor example, the INT engine can easily generate multiple proves of random statements, but cannot prove a given theorem.

---

2
Related work
In classical AI, reasoning is often achieved by search (40) Search rarely can be exhaustive, and a large body of algorithms and heuristics has been developed over the years, [40] Section 3.5]. It is hypothesized that progress can be achieved by combining search with learning [ Among notable
successful examples of this approach are Alpha Zero 43 or solving Rubik's cube using learned
heuristic function to guide the A algorithm (see (
An eminent early example of using goal-directed reasoning is the PARADISE algorithm (153)). In deep learning literature, [25] was perhaps the first work implementing subgoal planning. This was followed by a large body of work on planning with subgoals in the latent space for visual tasks
(24 31 34
30 21 35)) or mandmark-based navigation methods ([41
46 56 23).
The tasks considered in the aforementioned studies are often quite forgiving when comes to small emrrr in the subgoal generation. This can be contrasted with complex reasoning domains, in which even a small variation of a state may drastically change its meaning or render invalid. Thus, neural networks may struggle to generate semantically valid states (44 Section 6.1)).
Assuming that this problem was solved, generated subgoal still remains to be assessed. The exact evaluation may, in general, require exhaustive search access to oracle (in which case the original problem is essentially solved). Conseguently, it is unlikely that a simple planner (e.g., one unrolling independent sequences of subgoals [9]) will either produce informative outcome, could be easily improved using only local changes via gradient descent [3.. or cross-entropy method (CEM) 33 34] B5). Existing approaches, which are based on more powerful subgoal search methods, have their limitations, on the other hand. [33 is perhaps the closest to our method and uses MCTS to search the subgoal-induced graph. However, it
predefined (not learned) predicate function as a subgoal generator, limiting applicability to the problems with available high-quality heuristics. Learned subgoals are used in [32], method of hierarchical planning. That said, the subgoal space needs to be relatively small for this method to work (or crafted manually to reduce cardinality). To the best of our knowledge, our algorithm is the first domain agnostic hierarchical planner for combinatorially complex domains.
More generally, concepts related to goals and subgoals percolated to reinforcement learning early on, leading, among others, to prominent ideas like hindsight [22]. hierarchical learning 448 7 or the Horde architecture [47). Recently, with the advent of deep reinforcement learning, these ideas have been resurfacing and scaled up to deliver their initial promises. For example, (51) implements ideas of 7 and very successful hindsight technique 2 is already considered to be a core RL method. Further, a recent paper (36) utilizes a maximum entropy objective to select achievable goals in hindsight training and (50] uses meta-learned subgoals to discover options in multi-task RL settings. Apart from the aforementioned hierarchical planning, the idea to use neural networks for subgoal generation was used to improve model-free reinforcement learning agents
6 and
imitation learning algorithms [33]
3 Method
Our method, Subgoal Search (kSubS), is designed for problems, which can be formulated as a search over graph with a known transition model. Formally, let G (S,E) be a directed graph and $ c S be the set of success states. We assume that, during the solving process, the algorithm can, for a given node determine the edges starting at g and check if g E S.
Subgoal Search consists of four components: planner, subgoal generator, low-level policy, and value function. The planner, coupled with a value function, is used to search over the graph induced by the subgoal generator. Namely, for each selected subgoal, the generator allows for sampling the candidates for the next subgoals. Only these reachable by the low-level policy are used. The procedure continues until the solution is found or the computational budget is exhausted. Our method searches over graph G ES,E.), with the edges &, given by the subgoal generator. Provided reasonable generator, paths S are shorter in G than in G and thus easier to find.
In this paper we provide BestFS- and MCTS- backed implementations kSubS. Algorithm | presents BF-kSubS; see Algorithm 4 in Appendix A. for MCTS-kSubS.
3

---

For INT and Rubik's Cube, we use transformer models (see Appendix [.I1 in all components other than the planner. For Sokoban, we use convolutional networks (see Appendix B.2). While transformers could also be used in Sokoban, we show that a simplified setup already achieves strong results. This showcases that Subgoal Search general enough to work with different design choices. In Section 4.2 we describe datasets used train these neural models.
Algorithm Best-First Subgoal Search (BF-kSubS) Algorithm Low-level conditional policy
Require: C₁
max number of nodes
Require:
C2
steps limit
V
value function network
π low-level conditional
SOLVED
predicate of solution
policy network
function SOLVE(S,)
M model of the environment
T.PUSH((V(so)) 8o))
& T is priority queue paths is dict of lists
function GET GET_PATH(SO: subgoal)
paths(so]
step +- 0 <- So
Seen.ADD(so)
> seen set Ci do
while (T) and LEN())en)
action Baation_pathae +
8 + T.EXTRACT_MAXX
while step < C2 do
subgoals SUB_GENERATE($)
action + T.PREDICT(s, subgoal) action ppt.ta..PPED//cctioon
see Algorithm
for s' in subgoals do
M.NEXT STATE(s, action)
if s' in seen then continue seen.ADD(s')
if's s = subgoal then return accain__taattteeeeeeeee
actions <- GET_PATH((s,
step <- step +
see Alg Alg
return
if aattions.EMPTN then
continue
(APUS)((((s')))5)) paths + ppttssss actions if SOLVED(s') then
return paths[s']
return False
Subgoal generator Formally, it is a mapping p: S + P(S), where P(S) is a family of probability distributions over the environment's state space S. More precisely, let us define a trajectory sequence of state-action pairs (sp, a0). (s1, a.),..., (Sn, an), with (8;, 0:) E S x A, where A stands for the action space and is the trajectory's 's length. We will say that the generator predicts k-step ahead subgoals, if at any state it aims predict smin((+k.n)- We show, perhaps surprisingly, that this simple objective an efficient way to improve planning, even for small values of k. i.e. k E (2,3, 5,
Operationally, the subgoal generator takes as input an element of the s and returns subgoals, set of new candidate states expected to be closer to the solution and is implemented by Algorithm| 3 works as follows: first, we generate C's subgoal candidates with SUB SUB_NET NET GENERATE. Then, we prune this set to obtain total probability greater than C4.
For INT and Rubik's Cube, represent states sequences modeled with transformer. Following the practice routinely used in language modeling, [49], SUB SUB_NET_ GETERATEE employs beam search generate a of high likelihood outputs With the same goal in mind, for Sokoban, we another method described Appendix C.T SUB LEE_ENE_EEENE LL__NEE_EERETTT which is trained in supervised way on the expert data, with training examples being: 8, (input) and Rm) (label), see Appendix D for details.
GENERATE uses the subgoal generator network,
Low-level conditional policy Formally, it is mapping S x S A". It is used to generate sequence of actions on how to reach a subgoal starting from a given initial state. Operationally, may return empty sequence if the subgoal cannot be reached within C2 steps, see Algorithm 2 This is used as a pruning mechanism for the subgoals set in Algorithm
'In language modeling, typically. only one beam search output is used, In our case, however, we utilize all of them, which turns out be diverse of subgoals.

---

In INT and Rubik's Cube, we use Algorithm which utilizes low-level policy network æ. Similarly to the subgoal generator, it is trained using expert data in supervised fashion, i.c. for pair (st, Smin((+i,n)) with i S k, its objective is to predict ag.
When the branching factor is small, the low-level policy can be realized by a simple breadth-first search mech- anism, see Algorithm| 2 in Appendix, which we illustrate on Sokoban.
Algorithm Subgoal generator
Require:
C3
number of subgoals
C target probability
P
subgoal generator network
function SUB CUB_GENERATT(SS
Value function Formally, it is a map- ping V S + R, that assigns to each state a value related to its distance to the solution, and it is used to guide the search (see Algorithm | and Al- gorithm 4 For its training, we use expert data. For each state the train- ing target is negated distance to the goal: & where n denotes the end step of trajectory that se belongs to.
subgoals f 0
states, probs +
SEB_NET_ GENERATE(P, s; C3)
D (states, probs) is sorted wrt probs
total p +
for state, p E (states, do totall_ > C4 then break
ADDsoals total_p <- total_p +
return subgoals
Planner This is the engine that we use search the subgoal-induced graph.
In this paper, we use BestFS (Algorithm and MCTS (Algorithm I in Appendix A.1) The former is classic planning method, which maintains priority queue of states waiting be explored, and greedily (with respect to their value) selects elements from it (see, e.g., [40]). MCTS is search method that iteratively and explicitly builds search tree, using (and updating) the collected node statistics (see, e.g., (5). In this paper, we use an AlphaZero-like (42 algorithm for single-player games.
We note that the subgoal generator can be combined with virtually any search algorithm and can ben- efit from additional structure. For example, for domains providing factored state representation, the width-based methods [26] 12 would likely be stronger search mechanisms.
Experiments
In this section, empirically demonstrate the efficiency of MCTS-kSubS and BF-kSubS. In particular, we show that they vastly outperform their standard ("non-subgoal") counterparts. As testing ground, we consider three challenging domains: Sokoban, Rubik's Cube, and INT. All of them require non-trivial reasoning. The Rubik's s Cube is a well-known 3-D combination puzzle. Sokoban is complex video puzzle game known to be NP-hard and thus challenging for planning methods. INT (55) is recent theorem proving benchmark.
4.1 Training protocol and baselines
Our experiments consist of three stages. First, we collect domain-specific expert data, see Section 4.2 Secondly, we train the subgoal generator, low-level conditional policy, and value function networks using the data and targets described in Section 3 For more details see Appendix D) Eventually, evaluate the planning performance MCTS-KS kSuS and BF-kSubS, details of which are presented below. In the second step, network initialization, see details in Appendix D.1.3
supervised learning, which makes our setup stable with respect to
As baselines, we use BestFS and MCTS (being a Langle-playe implementation of AlphaZero). In INT and Rubik's Cube, both the algorithms utilize policy networks (trained with behavioral cloning, on the same dataset, which we used to train kSubS). Note that distribution over actions induces distribution over states; thus the policy nerwork can be regarded as a subgoal generator for & More details about the basclines can be found in Appendix
5

---

4.2 Search Domains and Datasets
Sokoban is a
complex game in which player controls an agent whose goal to place boxes on target locations solely by pushing them; without crossing any obstacles or walls. Sokoban has recently been used to test the boundaries in RI [I6 29]. Sokoban is known to be hard [TO], mainly due to its combinatorial complexity and the existence of irreversible states. Deciding if given Sokoban board solvable is an NP-hard problem [].
We collect the expert dataset consisting of all successful trajectories occurring during the training of MCTS agent (using an implementation of (29]). These are suboptimal, especially in the early phases of the training or for harder boards. For both expert training and kSubS evaluation, we generate Sokoban boards following the approach of [38.
Rubik's 's Cube is a classical 3-dimensional puzzle. is considered challenging due to the fact that the search space has more than 4.3 x 10 configurations. Similarly Sokoban, Rubik's Cube has been recently used as testing ground for RI. methods []]
To collect the expert dataset, we generate random paths of length 30 starting from the solved cube and take them backward. These backward solutions are highly sub-optimal (optimal solutions are proven to be shorter than 26 [39]).
INT: Inequality Benchmark for Theorem Proving. INT provides generator of inequalities, which produces mathematical formulas along with their proofs, see [55] Section 3.3]. Proofs are represented as sequences of consecutively applied mathematical axioms (there are К 18 axioms in total). An action in INT is tuple containing an axiom and its input entities. The action space in this problem can be very large, reaching up to 10 elements, which significantly complicates planning.
The INT generator constructs paths by randomly applying ax- ioms starting with trivial statement. Such a path taken back- ward constitutes the proof of its final statement (not guaranteed be optimal). The proof length, denoted by L, an important hyperparameter regulating the difficulty- we use 5, 10, 15.
INT
Sokoban
Rubik
4
Ci
400
5000
1500
C2
For more details on datasets Appendix C
C3
4
4
3
C1
0.98
4.3 Main results
Table 1: BF-kSubS hyperparameters.
In this section, we present our most important finding: Sub- goal Search enables for more efficient search and consequently scales up to problems with higher difficulty. Specifically, MCTS-KSubS and BF-kSubS perform significantly better than the respective methods not using subgoals, including state-of-the-art on INT.
In Figure we present the performance of Subgoal Search. We measure the success rafe as function of the search budget. The success rate is measured on 1000 instances of a given problem (which results in confidence intervals within =0.03). For BF-kSubS the search budget is referred size and includes the number of nodes visited by Algorithm ! For INT and Rubik's s Cube, we include both the subgoal generated by _UUB_GENEAATE and the nodes visited by GET CATH (as they induce significant computational cost stemming from using lowel policy π in Algorithm 2}. For Sokoban, use Algorithm 9 to realize GET_PATH: as it has negligible cost (less than 1% of the total runtime of Algorithm I), we do not include these nodes into graph size.
graph
For MCTS, we report MCTS passes, which is common metric for MCTS, see details in Appendix A.1
Below we discuss the results separately for each domain. We provide examples of solutions and generated subgoals in Appendix H
INT The difficulty of the problems in INT increases fast with the proof length L and the number of accessible axioms. W used K 18; all of available axioms. We observe, that BF-kSubS scales to proofs of length L = 10 and L = 15, which are significantly harder than 5 considered [53], see Table The same holds for MCTS-KSubS, see Appendix A.2
We check also that MCTS-kSubS vastly outperforms the baseline- AlphaZero algorithm, see Figure | (top, left). An MCTS-basse agent also evaluated in [55]. Its implementation uses graph neural

---

MCTS (AlphaZero) MCTS-KSubS (ours)
INT (MCTS)
INT (BestFS)
BF-kSubS (ours)
1.0
0.88
0.9
0.91
1.0
0.91
0.91
0.8
0.8
0.6
0.48
0.6
0.36
0.39
0.38
0.4
0.4
0.24
0.2
0.2
0.09
0.0
0.0
5
15
50
100
400
MCTS passes
Graph size
BestFS
BestFS
Sokoban
Rubik's cube
BF-kSubS (ours)
BF-kSubS (ours)
1.0
0.93
0.938
0.833
0.8
0.662
0.698
Success rate
0.8
0.6
Success
0.4
0.4
0.153
0.2
0.095
0.008
0.0
0.0
50
500
5000
400
2000
6000
Graph size
Graph size
Figure 1: The performance of Subgoal Search. (top, left) comparison on INT (with the proof length 15) to AlphaZero. (top, right) BF kSubS consistently achieves high performance even for small computational budgets. (bottom, left) similarly Sokoban (board size 12x12 with boxes) the advantage of BF-kSubs is clearly visible for small budget. (bottom, right) BestFS fails solve Rubik's Cube, while BF-kSubS can achieve near-perfect performance.
Proof length
10
15
Method
BestFS
BF-kSubS (ours)
BestFS
BF-kSubS (ours)
BestFS
BF-kSubS (ours)
Graph size
50
0.82
0.99
0.47
0.97
0.09
0.38
100
0.89
0.99
0.64
0.99
0.24
0.91
200
0.92
0.99
0.67
0.99
0.35
0.91
400
0.93
0.99
0.72
0.99
0.47
0.91
Table 2: INT success rates for various proof lengths and graphs sizes.
networks architectures and achieves 92% success rate for -= 5. Our transformed-basee baseline is stronger solves over 99% instances on the same problem set.
Sokoban Using BF-kSubS allows for significantly higher success rates rates within the same compu- tational budget, see Table Our solution scales well to the board size as big as 20 x 20; note that 10 x 10 boards are typically used in deep RL research [16] 38). Importantly, we observe that already for small computational budget (graph size 1000) BF-kSubS obtains higher success rates than the expert we used to create the dataset (these are 78%, 67%, 60% for the respective board sizes).
We also tested how the quality of BF-kSubS depends the size of the training dataset for Sokoban, the results can be found in Appendix
Rubik's Cube BF-kSubS solves nearly 100% of cubes, BestFS solve less than 10%, see Figure I (bottom, right). This perhaps the most striking example of the advantage of using subgoal generator instead of low-level actions. We present possible explanation in Appendix K

---

Board size
12 12
16 x
20 20
Method
BestFS
BF-kSubS (ous)
BestFS
BF-kSubS (ours)
BestFS
BF-kSubS (ours)
Graph size
50
0.15
0.66
0.04
0.42
0,02
0,46
100
0.46
0.79
0.23
0.62
0.10
0.55
1000
0.75
0.89
0.61
0.79
0,47
0.70
5000
0.83
0.93
0.69
0.85
0.58
0.77
Table 3: Sokohan success rates for various board sizes (each with 4 boxes).
Out-of-distribution (OOD) generalization OOD generalization is considered to be the crucial ability to make progress in hard combinatorial optimization problems [4] and automated theorem proving [55]. The INT inequality generator has been specifically designed to benchmark this phenomenon. We check that Subgoal Search trained on proofs on length 10 generalizes favourably to longer problems, Figure Following (55), speculate that search a computational mechanism that delivers OOD generalization.
It might be hard to compare computational budgets between various algorithms and their versions. In Appendix E we measure that BF-kSubS and MCTS- offer very practical benefits, sometimes much as 7x faster exccution.
4.4 Analysis of (subgoal distance) parameter
The subgoals are trained to predict states & steps ahead of the current one. Higher & should make planning easier as the search graph is smaller. However, as k increases, the quality of the generator may drop, and thus the overall effect is uncertain. Similarly, the task of the low-level conditional policy becomes more difficult as l increases. The optimal value of l is 3 and 4 for INT and Rubik's Cube, respectively. In these environments, increasing further degrades performance. we observe monotomic improvement up to k = 10. This is perhaps because low-level conditional policy (Algorithm 9 based on breadth-first search) never fails to fill the path from a state to the valid subgoal. The running cost of Algorithm quickly becomes unacceptable (recall that for k = 4, which we used in the main experiment, it has still a negligible cost below < 1% of the total runtime).
Sokoban,
Rubik's
0.8
0.8
0.6
0.6
0.4
0.0
0.4
8.2
0.2
0.2
10
10a
16a
10a
10
10F
10"
Graph size Blog scale)
Graph shte (log scalo)
Graph site (log scale)
Figure 2:
BF-kSubS suceess rates for different values of k. Black curves represent the values of used in the main experiments (that for Rubik's Cube and Sokoban and 3 for INT).
4.5 Quality of subgoals
The learned subgoal generator is likely to be imperfect (especially in hard problems). We study this on 10 10 boards of Sokoban, which are small enough to calculate the true distance dist the solution using the Dijkstra algorithm. In Figure 3 we study A := dist,, dist,y, where $1 is a sampled state and $2 is subgoal generated from $1- Ideally, the histogram should concentrate on & = 4 used training. We see that in slightly more than 65% of cases subgoals lead to an improvement.
The low-level conditional policy in A provides provides additional verification of generated states. We check that in INT and Rubik's Cube, about 50% of generated subgoals can be reached by this policy (the rest is discarded).
8

---

BP -o-iissss (ouns)
Poley
INT
044
0.99
0.94
Frequency
02
Succonso tette
0.8
0.77
0.57
0.12
0.03
0.01
0.50
0.00
0.4
00
0.0
Distance
Proof langth
Figure Histogram of Note that 17% sub- goals increases the distance. Additional, 5% leads to unsolvable "dead states" present in Sokoban.
Figure 4: Out-of-distribution generalization to
longer proofs. We compare with the behavioral cloning agent (Policy) studied in (55)
4.6
Value errors
There might be various explanations for the success of our method. One of them is that Subgoal Search better handles errors of learned value functions. In this section, discuss this using synthetic grid world example and performing statistical analysis on the real value function trained to approximate the distance the solution (as described in Section 3
Grid world example Consider a grid world with the state space = (I....., n)",. with (0, (O.....0) .0)
being the initial state and (n,.... ..... n) the goal state. A pair of states is connected by edge if they are at distance from each other. Let:
Synthetic value function: the negative distance the goal plus i.i.d Gaussian noise No0, o²),
Let Bg(x) be the states within distance k from We return C3 1 states sampled uniformly from (s) and a one "good subgoal" being a state in By(s) with the minimal distance to the solution.
Synthetic SUB_ 1ee__GENERAT (instead Algorithm 3
Node expansion in BestFS (baseline): implemented as SUB JUB_GENERATE above with I =
In this setup, one easily sees that the probability that the good subgoal will have the highest value estimation among the generated states grows with k. Consequently, kSubS can handle higher levels of noise than the baseline BestFS, see Table
0
BestFS
BF-kSubS
3
0.999
1
10
0.142
1
Value monotonicity Imagine a solution path from the starting state to the goal state. Due to the errors, the value estimates on the path may not be monotonic. This an undesirable property, which is likely to hinder search and make finding the path harder. Now con- sider the subpath consisting of consecutive states spaced k actions apart, can be constructed by Subgoal Search. For this version, the value estimates are more likely to be monotonic and easier find.
20
0.006
0.983
Table 4: Success rates on the grid world (m 6, n 10), depend- ing the value function noise scalc. We use the search budget of 500 nodes and = 4 for kSubS. To illustrate this, we measure monotonicity on solution paths found by our algorithm for INT. The probability that value decreases when moving steps ahead drops from 0.32 when k to mere 0.02 for k 4 (see Table in Appendix).
Overoptimism Alternatively, one can consider that erroncously positive values misguide search method (a phenomenon known as over-optimism (19). To illustrate this, consider S3(s), the set of all states having the same distance the solution and within distance 3 from s. Intuitively, Ss(s) contains similar states with respect to the difficulty of solving. In Sokoban, the standard deviation of value function prediction for Sz(s) is equal to 2.43 (averaged over different on Sokoban boards). This is high when compared to the average increase of value for moving one step closer to the solution, which is only 1.34. Consequently, it likely that Sz(s) contains a suboptimal state, e.g., having higher value than the best immediate neighbors of (which by properties of the game will be closer to solution in Sokoban). Indeed, we measure that the probability of such an event 64%. However, drops significantly to 29% if one considers states closer by 4 steps (say given by subgoal generator).

---

Limitations and future work
In this section, we list some limitations of our work and suggest further research directions.
Reliance on expert data this version, we use expert data to train learnable models. As kSubS improves the performance, speculate that training akin AlphaZero can be used, i.e. in planner-learner loop without any outside knowledge.
Optimality and completeness kSubS searches over reduced state space, which might produce suboptimal solutions or even fail to find them. This is arguably unavoidable if we seek an efficient method for complex problems.
Subgoals definition We use simple k-step ahead subgoals, which perhaps not always optimal. Our method can be coupled with other subgoal paradigms. Unsupervised detection of landmarks (see e.g. [56) seems an attractive future research direction.
More environments In future work, we plan to test kSubS on more environments to understand its strengths and weaknesses better. In this work, we generate subgoals in the state space, which might be limiting for tasks with high dimensional input (e.g., visual).
Reliance model of the environment We perfect model of the environment, which is common practice for some environments, e.g., INT. Extending kSubS to use learned (imperfect) models is an important future research direction.
Determinism Our method requires the environment be deterministic.
OOD generalization A promising future direction is to investigate and leverage the out-of- distribution generalization delivered by method and compare (somewhat contradictory) findings
of 17 55
Classical plamning methods For many search problems, the state space be represented in factored fashion (or such representation can be learned (3)). such cases, the search can be greatly improved with madth-based methods [26 12] It is an interesting research direction to combine kSubS with such methods.
Conclusions
We propose Subgoal Search, a search algorithm based on subgoal generator. We present two practical implementations ACTSSkSubb, and BF-kSubS meant to be effective in complex domains requiring reasoning. We confirm that indeed our implementations excel in Sokoban, Rubik's Cube, and inequality benchmark INT. Interestingly, a simple &o step ahead mechanism of generating subgoals backed up by transformer-based architectures performs surprisingly well. This evidence, let us hypothesize, that our methods (and related) can be further scaled up to even harder reasoning tasks.
Acknowledgments and Disclosure of Funding
The work of Konrad Czechowski, Tomasz Odrzygóždž and Piotr Mitoš was supported by the Polish National Science Center grant UMO-201 7/26////TT/00022.. This research was supported by the PL-Grid Infrastructure. Our experiments were managed using htttps:/neepune. ai We would like thank the Neptune team for providing us access the team version and technical support.
References
[1] Forest Agostinelli, Stephen McAleer, Alexander Shmakov, and Pierre Baldi. Solving the rubik's cube with deep reinforcement learning and search. Nature Machine Intelligence, 1(8):356-363, 2019.
[2] Marcin Andrychowicz. Dwight Crow, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, Pieter Abbeel, and Wojciech Zaremba. Hindsight experience replay, In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 4-9 December 2017, Long Beach, CA, USA, pages 5048-5058 2017.
10

---

[3] Masataro Asai and Alex Fukunaga. Classical planning in deep latent space: Bridging the bubsymbolie-symbone boundary. In Thirty-Secone AAAI Conference on Artificial Intelligence. 2018.
[4] Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: a methodological tour d' horizon. European Journal of Operational Research, 2020.
[5] Cameron B Browne, Edward Powley, Daniel Whitehouse, Simon M Lucas, Peter Cowling, Philipp Rohffshagen, Stephen Tavener, Diego Perez, Spyridon Samothrakis, and Simon Colton. A survey of monte carlo tree search methods. IEEE Transactions on Computational Intelligence and Al in games, 4(1):1-43, 2012.
[6] Elliot Chane-Sane Cordelia Schmid, and Ivan Laptev. Goal-conditioned reinforcement learning with imagined subgoals. In International Conference on Machine Learning, pages 1430-1440.
PMLR, 2021.
[7] Peter Dayan and Geoffrey E. Hinton. Feudal reinforcement learning. Stephen Jose Hanson, Jack D. Cowan, and C. Lee Giles, editors, Advances in Neural Information Processing Systems December 3, 1992], pages
5. [NIPS Conference, Denver, Colorado, USA, November 30
271-278. Morgan Kaufmann, 1992.
[8] Dorit Dor and Uri Zwick. Sokoban and other motion planning problems. Geometry, 13(4):215-228 1999.
Computational
(9] Kuan Fang, Yuke Zhu, Animesh Garg, Silvio Savarese, and Li Fei-Fei. Dynamies learning with cascaded variational inference for multi-step manipulation. arXiv preprint 1910. 13395, 2019.
[10] Alan Fern, Roni Khardon, and Prasad Tadepalli. The first learning track of the international planning competition. Machine Learning. 84(1-2):81-107, 2011.
[11) Carlos Florensa, David Held, Xinyang Geng, and Pieter Abbeel. Automatic goal generation for reinforcement learning agents. International conference on machine learning, pages 1515-1528. PMLR, 2018.
[12] Guillem Frances, Miquel Ramírez Jávega, Nir Lipovetzky, and Hector Geffner. Purely declarative action descriptions are overrated: Classical planning with simulators. In IJCAI 2017. Twenty-Sixth International Joint Conference on Artificial Intelligence; 2017 Aug 19-25; Melbourne, Australia. (Californaa IJCAI 2017. p. 4294-301, International Joint Conferences on Artificial Intelligence Organization (UCAD), 2017.
[13] Thomas Gabor, Jan Peter, Thomy Phan, Christian Meyer, and Claudia Linnhoff- Popien. Subgoal- based temporal abstraction in Monte-Carlo Tree Search. In IJCAI, pages 5562-5568, 2019.
[14] Wei Gao, David Hsu, Wee Sun Lee, Shengmei Shen, and Karthikk Subramanian. Intention-net: Integrating planning and deep learning for goal-directed autonomous navigation. In 1st Annual Conference on Robot Learning, CoRL. 2017, Mountain View, California, USA, November 13-15, 2017, Proceedings, volume 78 of Proceedings of Machine Learning Research, pages 185-194. PMLR, 2017.
[15] Timothy Gowers. The importance of mathematics. Springer- Verlag, 2000.
[16] Arthur Guez, Mehdi Mirza, Karol Gregor, Rishabh Kabra, Sébastien Racanière, Théophane Weber, David Raposo, Adam Santoro, Laurent Orseau, Tom Eccles, et al. An investigation of model-free planning. In International Conference on Machine Learning, pages 2464-2473. PMLR, 2019.
[17] Jessica B. Hamrick, Abram L. Friesen, Feryal Behbahani, Arthur Guez, Fabio Viola, Sims Witherspoon, Thomas Anthony, Lars Holger Buesing, Petar Velickovic, and Theophane Weber. On the role of planning in model-based deep reinforcement learning. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021.
[18] Demis Hassabis, Dharshan Kumaran, Christopher Summerfield, and Matthew Botvinick. Neuroscience-inspire artificial intelligence. Neuron, 95(2):245-258 2017.
[19] Hado Hasselt. Double learrnngg. Advances neural information processing systems, 23:2613- 2621, 2010.

---

[20] Jeffrey R Hollerman, Leon Tremblay, and Wolfram Schultz. Involvement of basal ganglia and orbitofrontal cortex in goal-directed behavior. Progress in brain research, 126:193-211 2000.
[21] Dinesh Jayaraman, Frederik Ebert, Alexei A. Efros, and Sergey Levine. aane-tgoottic pre- diction: Predicting predictable video frames. In 7th International Conference on Learning Representations. ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
[22] Leslie Pack Kaelbling. Learning to achieve goals. In Ruzena Bajesy, editor, Proceedings of the 13th International Joint Conference on Artificial Intelligence. Chambéry, France, August 28 September 3, 1993, pages 1094-1099. Morgan Kaufmann, 1993.
[23] Junsu Kim, Younggyo Seo, and Jinwoo Shin. Landmark-guided subgoal generation in hierar- chical reinforcement learning. In Thirty-Fifth Conference on Neural Information Processing Systems, 2021.
[24] Taesup Kim, Sungjin Ahn, and Yoshua Bengio. Variational temporal abstraction. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Bur Buc, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 11566- 1155, 2019.
[25] Thanard Kurutach, Aviv Tamar, Ge Yang. Stuart J. Russell, and Pieter Abbeel. Learning plannable representations with causal infogan. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi and Roman Garnett, editors, Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal. Canada, pages 8747- 8758, 2018.
[26] Nir Lipovetzky and Hector Geffner. Width and serialization of classical planning problems. In ECAI 2012, pages 540-545. IOS Press, 2012.
[27] Kara Liu, Thanard Kurutach, Christine Tung. Pieter Abbeel, and Aviv Tamar. Hallucinative topological memory for zero-shot visual planning. In Proceedings of the 37th International Conference Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 6259 6270. PMLR, 2020.
[28] Yinhan Liu, Jiatao Gu, Naman Goyal, Xian Li, Sergey Edunov, Marjan Ghazvininejad, Mike Lewis, and Luke Zettlemoyer. Multilingual denoising pre-training for neural machine translation. CoRR, abs/2200..822
2020.
[29] Piotr Milos, Lukasz Kuciñiski Konrad Czechowski, Piotr Kozakowski, and Maciek Klimek. Uncertainty-sensitive learning and planning with ensembles. arXiv preprint arXiv: 1912.9999. 2019.
[30] Suraj Nair and Chelsea Finn. Hierarchical foresight: Self-supervised learning of long- horizon tasks via visual subgoal generation. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
[31] Soroush Nasiriany, Vitchyr Pong, Steven Lin, and Sergey Levine Planning with goal- conditioned policies. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' d'Alché-Buc, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8- 14, 2019, Vancouver, BC, Canada, pages 18814-14822 2019.
[32] Giambattista Parascandolo. Lars Buesing, Josh Merel, Leonard Hasenelever, John Aslanides, Jessica B Hamrick, Nicolas Heess, Alexander Neitz, and Theophane Weber. Divide-and-conquer monte carlo tree search for goal-directed planning, arXiv preprint 11Xiv:2004.11410, 2020.
[33] Sujoy Paul, Jeroen Vanbaar, and Amit foy-Chowdhury, Learning from trajectories via subgoal discovery. Advances in Neural Information Processing Systems, 32:8411-8422 2019.
[34] Karl Pertsch, Oleh Rybkin, Frederik Ebert, Shenghao Zhou, Dinesh Jayaraman, Chelsea Finn, and Sergey Levine. Long-horizon visual planning with goal-conditioned hierarchical predictors. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan- Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
12

---

[35]
Karl Pertsch, Oleh Rybkin, Jingyun Yang, Shenghao Zhou, Konstantinos G. Derpanis, Kostas Danilidiis, Joseph Lim, and Andrew Jaegle. Keyframing the future: Keyframe discovery for vi- sual prediction and planning. In Alexandre M. Bayen, Ali Jadbabaie, George J. Pappas, Pablo A. Parrilo, Benjamin Recht, Claire J. Tomlin, and Melanie N. Zeilinger, editors, Proceedings of the 2nd Annual Conference on Learning for Dynamics and Control, LADC 2020, Online Event, Berkeley, CA. USA. 11-12 June 2020, volume 120 of Proceedings of Machine Learning Research, pages 969-979. PMLR, 2020.
[36] Silviu Pitis, Harris Chan, Stephen Zhao, Bradly C. Stadie, and Jimmy Ba. Maximum entropy gain exploration for long horizon multi-goal reinforcement learning. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020. 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 7750-7761. PMLR, 2020.
[37] Stanislas Polu and Ilya Sutskever. Generative language modeling for automated theorem proving.
arXiv preprint arXiv:2009.0333 2020.
[38] Sébastien Racanière, Theophane Weber, David P. Reichert, Lars Buesing, Arthur Guez, Danilo Jimenez Rezende, Adrià Puigdomènech Badia, Oriol Vinyals, Nicolas Heess, Yu- jia Li, Razvan Pascanu, Peter Battaglia, Demis Hassabis, David Silver, and Daan Wierstra. iiagination-augmenter agents for deep reinforcement learning. In NIPS, 2017.
[39] Tomas Rokicki and M Davidson. God's number is 26 the quarter- metric, 2014.
[40] Stuart Russell and Peter Norvig. Artificial intelligence: A modern approach. ed. 2010.
[41] Nikolay Savinov, Alexey Dosovitskiy, and Vladlen Koltun. Semi- parametric topological mem- ory for navigation. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenRe-
view.net, 2018.
[42] David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifree, George Van Den Driess- che, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mas- tering the game of go with deep neural networks and tree search. nature, 529(7587):484 489, 2016.
[43] David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Thore Graepel, Timothy Lillicrap, Karen Simonyan, and Demis Hassabis. A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play. Science, 1144:1 144::1144-144, 2018.
[44] David Silver, Thomas Hubert, Julian Schrittwieser, loannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, Timothy P. Lillicrap, Karen Simonyan, and Demis Hassabis. Mastering chess and shogi by self- eelf-play with general reinforcement learning algorithm. ArXiv, 11.011112.11..... 2017.
[45] David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, Yutian Chen, Timothy Lillicrap, Fan Hui, Laurent Sifre, George Van Den Driessche, Thore Graepel, and Demis Hassabis. Mastering the game of Go without human knowledge. Nature, 2017.
[46] Gregory J. Stein, Christopher Bradley, and Nicholas Roy. Learning over subgoals for efficient navigation of structured, unknown environments. In 2nd Annual Conference on Robot Learning. CoRL 2018, Zürich, Switzerland, 29-31 October 2018, Proceedings, volume 87 of Proceedings of Machine Learning Research, pages 213-222. PMLR, 2018
[47] Richard S. Sutton, Josephh Modayil, Michael Delp, Thomas Degris, Patrick M. Pilarski, Adam White, and Doina Precup. Horde: scalable real-time architecture for learning knowledge from unsupervised sensorimotor interaction. In Liz Sonenberg, Peter Stone, Kagan Tumer, and Pinar Yolum, editors, 10th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2011), Taipei, Taiwan, May 2-6, 2011, Volume 1-3, pages 761-768. IFAAMAS, 2011.
[48] Richard S. Sutton, Doina Precup, and Satinder P. Singh. Between mdps and semi-mdps; A framework for temporal abstraction in reinforcement learning. Artif. Intell., 1121-21)181--111 1999.
[49] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman
13

---

Garnett, editors, Advances in Neural Information Processing Systems 30; Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA. pages 5998-6008, 2017.
[50] Vivek Veeriah, Tom Zahavy, Matteo Hessel, Zhongwen Xu, Junhyuk Oh, lurii Kemaev, Hado van Hasselt, David Silver, and Satinder Singh. Discovery of options via meta-learned subgoals. arXiv preprint arXiv:2102.06741, 2021.
[51] Alexander Sasha Vezhnevets, Simon Osindero, Tom Schaul, Nicolas Manfred Otto Heess, Max Jaderberg, David Silver, and Koray Kavukcuoglu. Feudal networks for hierarchical reinforcement learning. ArXiv, abs/1703.0116.: 2017.
[52] Oriol Vinyals, Igor Babuschkin, Wojciech M. Czarnecki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung, David H. Choi, Richard Powell, Timo Ewalds, Petko Georgiev, Junhyuk Oh, Dan Horgan, Manuel Kroiss, Ivo Danihelka, Aja Huang, Laurent Sifre, Trevor Cai, John P. Agapiou, Max Jaderberg, Alexander S. Vezhnevets, Rémi Leblond, Tobias Pohlen, Valentin Dalibard, David Budden, Yury Sulsky, James Molloy, Tom L.. Paine, Caglar Gulcehre, Ziyu Wang, Tobias Pfaff, Yuhuai Wu, Roman Ring, Dani Yogatama, Dario Wünsch, Katrina McK- inney, Oliver Smith, Tom Schaul, Timothy Lillicrap, Koray Kavukcuoglu, Demis Hassabis, Chris Apps, and David Silver. Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature, 575(7782)3300335, Nov 2019.
[53] David Wilkins. Using patterns and plans in chess. Artif. Intell., 14(2):165-205, 1980.
[54]
Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, and Jamie Brew. Huggingface's transformers:
State-of-the-an natural language processing. CoRR, abs/1910.03771, 2019..
[55] Yuhuai Wu, Albert Jiang, Jimmy Ba, and Roger Grosse. Int: An inequality benchmark for evaluating generalization in theorem proving. arXiv preprint arXiv:2007. .02924, 2020.
[56] Lunjun Zhang, Ge Yang, and Bradly C. Stadie. World model as graph: landmarks for planning. CoRR, abs/201 0oss/011.12491,, 1,191 2020.
Learning latent
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] In the Section
(c) Did you discuss any potential negative societal impacts of your work? [Yes] In Section
??
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full of assumptions all theoretical results? [N/A]
(b) Did you include complete proofs of all theoretical results? [N/A]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] We include the
URL to the code repository in Section []
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Appendix sections B D and
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] In Appendix L
4. If you using existing assets (c.g., code, data, models) or curating/releasing assets...
14

---

(a) If your work uses existing assets, did you cite the creators? [Yes] For one of domains
we generate expert data with implementation of MCTS agent published with work 29]
as noted in Section 4.2
(b) Did you mention the license of the assets? [N/A] The implementation noted above is
made available on github, without any licence.
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes] We release our code, the URL is in Section []
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "wUTdAq0hgl4", "reviewer": "Reviewer_t8oJ", "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. ", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "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": "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. \n\nIt'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. \n\nIt's unclear from the paper how SubS and kSubS (used interchangeably in the paper) are different from each other. \n\nThere 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\n\nIt'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. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Adequate. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1.5"}, "extra_text": {}}, {"review_id": "iSaHZVggORL", "reviewer": "Reviewer_txcJ", "summary": "The paper introduces a subgoal generator to accelerate the search\nprocess to solve a given task. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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": "The present paper introduces an algorithm that uses a\nsubgoal-generator to generate subgoals which are then driven to by a\nlocal policy, and demonstrates its use in the context of Sokoban,\nRubik's Cube, and INT (theorem prover).\n\nThe algorithm is relatively straightforward and simple to implement\nand shows good improvement compared to existing methodologies.\n\nThe reviewer found it not obvious to understand how the subgoal\ngenerator generates its subgoals. What does the prediction refer to?\nWhere does the reference come from? There is some implicit mentioning\nof expert training, however, that means that the algorithm needs some\nseeding. More discussion is now needed to make clear what the\nadvantage of using such an algorithm is. It is mentioned that there is\nsome out-of-distribution generalization ability, which is probably the\nmost interesting aspect of the study, but here more details as to how\nthat emerges/works might have been useful in addition to experimental\nbenchmarking, especially in a conference such as NeurIPS.\n\n- line 131: it is crucial for the understanding of the algorithm to\n  explain what is being predicted. There is only some mentioning of\n  expert data collection, but this is the core part of the algorithm\n  and needs to be more detailed. Note that Algorithm 3 is not much\n  more illuminating - what does the Beam_Search do here, and what does\n  the probabilities bookkeeping do?\n- Footnote 3: AlphaZero spelling\n- Fig. 4: \"increase the distance\" - I would treat \"12%\" as a plural\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations appropriately discussed. \n\nAt this stage of discussion, I do not consider the Societal Impact discussion relevant to this paper.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "SG5vi3HHI8", "reviewer": "Reviewer_RAfv", "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. ", "questions": "", "limitations": "", "rating": 7, "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": "- 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?\n\n- 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.\n\n- 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.\n\n- What is the sensitivity of the proposed method to the number of expert demos?\n\n[A] Automatic Goal Generation for Reinforcement Learning Agents, ICML 2018\n[B] Learning from Trajectories via Subgoal Discovery, NeuIPS 2019", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "CS4oCeoL3J7", "reviewer": "Reviewer_raVp", "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*.\n\nThe 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.\n\nThe 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.\n\nI 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.\n\nThe 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.\n\nI 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.\n\nThe findings are very interesting. Fig 2 is the most insightful.\n\nHowever, I think the manuscript have some confusions that make the contributions less clear. \nOnly three domains are considered. Two use the same setting with a shared family of hyperparameters. A third one uses a different setting.\n", "questions": "", "limitations": "", "rating": 7, "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": "I am confused by the wording of the contributions. Therefore, let me summarize them using the same numbers as in the paper. \n\n1. Subgoal Search using transformer + search algorithm is strong.\n2. Same transformer per se is strong.\n3. The value functions used in the paper are weak.\n\nThe 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 \n\n* Using different setup in Sokoban vs the other two domains.\n* The lack of comparison with search algorithms.\n\nA minor weakness is\n\n* Given the effort devoted to tuning the algorithms, it becomes relevant to try planning algorithms suitable for this deterministic setting.\n\nThis is NeurIPS, so this illustration might be pertinent for this setting, deterministic and where the model is known.\n\n* If the states are atomic, then both search and goal-conditioned RL solves the problem of finding a sequence of actions.\n* 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.  \n\nThe evaluation is done in three benchmarks:\n\n* Rubik's cube. Well studied in the search community. \n* Sokoban. Well studied in the search and planning communities.\n\nA 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.\n\nREQUIRED: in a related work section, please comment on these two lines of work:\n\n* 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.\n* 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.\n\nHowever, 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?\"\n\n\n\n\nREQUIRED: \n* Please clarify what if BestFS is and what it shares with BF-kSubs. \n* Is BestFS equivalent to \"k=1\"?\n\nREQUIRED: 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).\n\n1. 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 \\}$\". \n2. When possible, report complete results using Dijkstra. (Sect 4.5 implies part of the work is done)\n3. $k=1$\n4. $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.\n\nThis possible lack of information on the points 3 and 4 is the weakest aspect of the paper, as that's the main research question.\n\nREQUIRED:\n* Please focus 3rd contribution on the observation about value errors. The importance of subgoal search is covered in the other two contributions.\n\n---- \n\nThank you for your comments. I let my comments in the discussion. Just updating the scores.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

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)