Subgoal-Guided Policy Heuristic Search with Learned Subgoals
Authors: Jake Tuero
Michael Buro
Levi Lelis
Venue: ICML 2025 poster (2025)
Keywords: Tree search
heuristic search
policy tree search
planning
Primary area: reinforcement_learning->planning

Abstract: Policy tree search is a family of tree search algorithms that use a policy to guide the search. These algorithms provide guarantees on the number of expansions required to solve a given problem that are based on the quality of the policy. While these algorithms have shown promising results, the process in which they are trained requires complete solution trajectories to train the policy. Search trajectories are obtained during a trial-and-error search process. When the training problem instances are hard, learning can be prohibitively costly, especially when starting from a randomly initialized policy. As a result, search samples are wasted in failed attempts to solve these hard instances. This paper introduces a novel method for learning subgoal-based policies for policy tree search algorithms. The subgoals and policies conditioned on subgoals are learned from the trees that the search expands while attempting to solve problems, including the search trees of failed attempts. We empirically show that our policy formulation and training method improve the sample efficiency of learning a policy and heuristic function in this online setting.

Subgoal-Guided Policy Heuristic Search with Learned Subgoals
Jake Tuero 12
Michael Buro'
Levi H. S. Lelis 12
Abstract
2018; Orseau & Lelis, 2021), which use a learned policy to guide the search, i.e., a probability distribution over the set of actions available to the agent. Orseau et al. (2018) showed that a benefit of using policy tree search methods over traditional heuristic search methods that they provide upper bound on the number of node expansions required to find a solution that depends on the quality of the policy, and Orseau & Lelis (2021) showed that policy can be learned while minimizing such an upper bound.
Policy tree search is family of tree search algo- rithms that use a policy to guide the search. These algorithms provide guarantees on the number of expansions required to solve a given problem that are based on the quality of the policy. While these algorithms have shown promising results, the pro- cess in which they are trained requires complete solution trajectories train the policy. Search trajectories are obtained during trial-and-erron search process. When the training problem in- stances are hard, learning can be prohibitively costly, especially when starting from a randomly initialized policy. As a result, search samples are wasted in failed attempts to solve these hard in- stances. This paper introduces a novel method for learning subgoal-based policies for policy tree search algorithms. The subgoals and policies con- ditioned on subgoals are learned from the trees that the search expands while attempting to solve problems, including the search trees of failed at- tempts. We empirically show that our policy for- mulation and training method improve the sample efficiency of learning a policy and heuristic func- tion in this online setting.
Policy-Guide Heuristic Search (PHS*) (Orseau & Lelis, 2021) a policy-guided search algorithm that combines a learned policy and a heuristic function. While there have been previous approaches to combining policy and heuris- tic/value function, such as the PUCT-based search algo- rithms (Rosin, 2011; Kocsis & Szepesvári, 2006) like Alp- haZero (Silver et al., 2017) and MuZero (Schrittwieser et al., 2020) in adversarial search domains like Go and Chess, Orseau & Lelis (2021) show that PHS* is better suited for the single-agent search problems we consider in this work.
Policy tree search methods, including PHS* are usually trained online using the Bootstrap search-and-learn process (Arfaee et al., 201 The Bootstrap process initially uses randomly initialized neural models encoding the heuristic and the policy to iteratively solve subset of the problems. If the search cannot solve problems within a search budget, the resulting trees are discarded; if at least one problem is solved, the models are optimized the solution trajectories found. A problem with this approach is that much of the search effort is wasted on failed attempts, especially in the early iterations of learning, with untrained neural models.
1. Introduction and Overview
This work focuses on solving single-agent deterministic search problems, using minimal domain knowledge. In particular, we are interested in sneedle-in-hysstenn lems, where finding any solution can be challenging. Many important problems can be represented as deterministic single-agent search problem, such as robotic navigation (Tan et al., 2021) and network routing (Liu & Ramakrish- nan, 2001). A recent line of research to address this class of problems is policy tree search algorithms (Orseau et al.,
prob-
A key innovation of our approach is that we use these failed search attempts to learn subgoals, which can shorten the planning horizon and ease the learning process. These failed attempts allow subgoals. Using subgoals to break down the search horizon into smaller pieces has shown success in complex domains, as demonstrated in kSubS (Czechowski et al., 2021), Ada- SubS (Zawalski et al., 2022), and HIPS (Kujanpää et al., 2023). An issue with some of these approaches that they lack completeness, i.e., they might fail to return solution even if one exists. HIPS-E (Kujanpää et al., 2024) is vari- ant of HIPS that is complete. However, HIPS-s, as well as kSubS, AdaSubS, and HIPS, require precomputed datasets
learn policies that navigate between
'Department of Computing Science, University of Al- berta, Edmonton, Canada Alberta Machine Intelligence Insti- tute (Amii), Edmonton, Canada. Correspondence to: Jake Tuero <tucro uabreraabberta.c.....
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Subgoal-Guided Policy Heuristic Search with Learned Subgoals
of solution trajectories, which may be prohibitively costly in complex environments.
of children is denoted as ((n), its parent as par(n), and its set of ancestors excluding n is ane(n) and also define anc- (n) = anc(n) U {n). The process in which search algorithm generates the set of children for a node n is called expansion, and we say that the node was expanded. The first node to be expanded is the root Ro. and all nodes n can only be expanded its parent par(n) has been expanded. The search ends when there are no more nodes to expand or the search finds node representing an 8 in Sg. The set Sg is not known a priori, but can be checked with a Boolean test.
We propose hierarchical policy for policy-guided tree search algorithms that is complete and does not require precomputed solution trajectories. This is achieved by learn- ing Sabgoal-guided low-level policies from the Bootstrap data. In our approach, a subgoal generator produces a set of subgoals for a given state encountered in the search. The low-level policy is then conditioned on each of these sub- goals and on the current state, thus providing one probabil- ity distribution over actions for each subgoal. A high-level policy produces a distribution over the generated subgoals, which gives an importance weighting for each of the low- level policies. The low-level policies are then mixed, based on the weighting given by the high-level policy, to produce a final policy that guides the search. In addition, we propose method to learn these subgoals and policies using the data provided by the tree search, even in contexts where a budget for the search causes early termination without a solution.
The search algorithm incurs a loss of L : N + (0, oc] every time a node is expanded. The path loss g(n) of a node is the sum of losses from the root node to n, given by g()) = Enneame(n) E(n'). If {(m) = for all nodes, then (n) is equal to the depth of the node, denoted d(n).
A policy a N + [0, 1] assigns probabilities to se- quences of actions which represents each node. It is de- fined recursively for child n' of node n by T(n') T (n)) In), where the conditional probability x x [n) in [0, 11. Evre(n)) =<n' [m) S 1 (the inequality can occur due to state pruning during the search), and ((o)) 1. Thus, T (n) is the product of probabilities along the path from the root to n: (n) II n (m))) T(n' par(n')).
In experiments, we demonstrate the sample efficiency our method enables in that requires substantially fewer node expansions to learn effective policies than other search al- gorithms trained with the Bootstrap algorithm in variety of problem domains. We also show that policy tree search algorithms using our subgoal- based policy can learn how to solve problems from domains that HIPS-S cannot solve.
2.1. Background
Best-First Search. Best-First Search (BFS) algorithms (Pearl, 1984), expand nodes with increasing cost. The root node is added to a priority queue sorted by a cost function. In every iteration, the cheapest node in the queue is removed and expanded; the nodes thus generated are added into the queue. A node will not be expanded if its underlying state has already been expanded. In the context of poliey-guided search, the search terminates when node representing state in NV is encountered (see Appendix A for details).
Our contributions can be summarized as follows. We pro- vide a novel subgoal discovery method for policy-guided tree search algorithm that learns from data collected dur- ing search. Our method for learning policies automatically reduces complex problems into easier sub-problems, by au- tomatically learning subgoals. Moreover, it can train neural policies from both successful and failed searches, unlike other algorithms that learn with the Bootstrap process.
Policy Tree Search. LevinTS (Orseau et al., 2018) is a BFS algorithm using the evaluation function
2. Preliminaries
We define single-agent deterministic search problem as the tuple (S, A, T, 8o, Sy), where S is the set of states, A is the finite set of actions available to the agent, T : S x A S is a deterministic transition function, 8u is the initial state, Sy is the set of goal states. The state reached after applying a sequence of actions dg:t ag .1,..., ag is denoted as T( The underlying state space of the search problem is modeled as a graph G = (S, A). This graph has one edge (s, s') in A for each in A such that T(s, a) = s''
LevinTS (n) d(n) +1
(1)
(n)
Policy-Guided Heuristic Search (PHS*) (Orseau & Lelis, 2021) generalized LevinTS by using both a policy and heuristic function to guide the search, which can be defined as BFS using the evaluation function
sPes (n) = (1(12) g(n)
(2)
T(n)
The algorithms we consider search over the state space by generating a tree. Let W be the set of nodes of the tree, with no E A being the root node corresponding to the initial state sg- Any node in the tree can be defined as sequence of actions from the initial state so, with the root node being the empty sequence of actions, For any node n in N,, its set
where 77nn is the heuristic factor for node n defined as
n()) = 1 (((n///(()) [nn)MM)/a(M))
with is(n) being a heuristic, which estimates the cost-to-go
2

---

Subgoal-Guided Policy Heuristic Search with Learned Subgoals
goal state. For g()) 0, we define ry(n) 1. LevinTTS and PHS* are shown in Appendix B, Algorithms 2 and 3.
ate subgoals and trajectories between them for the subgoal generator and low-level policy to learn from, respectively (Section 3.3). Finally, Figure I.c shows how we use solution trajectories to train the heuristic model, low-level policy, high-level policy, and subgoal generator (Section 3.4).
The Bootstrap Process. The Bootstrap algorithm (Arfaee et al., 2011) learns a neural policy and/or heuristic functions from search. The initial policy//euristie is represented by randomly initialized neural network, and are improved in each iteration as follows. A search algorithm using the current neural model runs on subset of the training problem instances with bound on the number of node expansions allowed for each problem. Problems that are solved have their solution trajectory used to update the models, and the process continues. After every sweep through a set of training problems, a separate validation set is used to determine when to stop. If the search can solve all problems from the validation set, then the training is complete and the neural model is returned. If the search cannot solve any new problems after sweep of the training set, the expansion budget is increased. See Appendix C for its pseudocode.
3.1. Subgoal- Policy Search
Instead of single policy x--) that produces a probabil- ity distribution over actions, we employ several subgoal- conditioned low-level policies together with a high-level policy over subgoals. The low-level policy soo (als, 8,.) is conditioned on a state and subgoal sy., and represents probability distribution over actions achieve 8g. from s. For k subgoals, we generate a set of k probability distri- butions by conditioning low on each of the l subgoals $g. The high-level policy ( (s) gives a distribution over the l subgoals. These low-level and high-level policies are implemented as neural networks parameterized by 0 and vi respectively.
2.2. Problem Statement
The resulting policy (a which we will refer to the mubbool-guidee policy, is formulated by using weighted ge- ometric mixing of the low-level policies, in which the weight given to policy -/oo (als, Sy.) is the probability for the ith subgoal given by the high-level subgoal policy ($ Is):
Given set of problem instances K, the objective is to solve them while minimizing the total search loss. Concretely, we use the formulation provided by Orseau & Lelis (2021): For a search algorithm S. a loss of E(n) > 0 is incurred by S expanding node n, and the search loss T.SS, n) is the sum of individual losses E(n') for all nodes n' that have been expanded by algorithm S up and including The total search loss is then given by ΣKEK L(S, ni)), where L(S, n²)) is the search loss of algorithm S while finding solution node ni on the k-th problem in K. For example, if {(n) = for all nodes n. then the objective is to solve the problem instances using as few node expansions as possible.
Th
E m (8g.ls) The (als, Sy.)
π (als)) =
(4)
Σ.E. hi (8g. (8) m low (al 88 8g.))
The search algorithm then works by calling BFS with the corresponding evaluation function (PLevinTS or (PHs), but uses n 5G instead of (T-).
3. Method
3.2. VQVAE Subgoal Generator
We use a Vector Quantized Variational Autoencoder (Van Den Oord et al., 2017) (VQVAF), represented by a neural network parameterized by o, as a subgoal generator. Our design is similar to the one used in HIPS- (Kujanpää et al., 2023). The Encoder takes as input a pair of states (Neur: Sta)) and and produces continuous latent code ze. The latent code is quantized by finding the nearest entry in the code- book e., which is table of k vectors. The decoder takes as input the pair (Seur; ee) and produces a reconstructed target Sun. The intuition behind the pair of current and target states given to the encoder is that the encoder learns to capture the difference between the two states into the encoding code- book vector. When the current state is given the decoder at runtime during search, the encoding codebook vector can be used to recover the changes required to be made from the current state to reconstruct the target state.
We propose learning a subgoal-guided policy for policy search algorithms, which uses learned subgoals from sub- goal generator to guide the search through the use of policies conditioned on subgoals. In this work, we define subgoals as states from the underlying state space that the search attempts to achieve. Unlike previous policy search methods, our policy uses data from mudget-bounded searches that fail to find solution to train its neural policy.
Our method is given in Figure 1. Figure 1.a shows how the low-level policy, high-level policy, heuristic, and subgoal generator models interact when expanding node during the search (Sections 3.1 and 3.2). During the Bootstrap pro- cess used to train the policy, the heuristic, and the subgoal generator models, the budgeted search will either termi- nate without a solution or with solution trajectory. When the budgeted search terminates without solution found, Figure b shows how the search tree can be used to gener-
To generate the i-th subgoal during search, the node's 's state 8 and the i-th codebook entry e; of the VQVAE are given
3

---

Bubgoal-Guides Policy Heuristic Search with Learned Subgoals
(a) Policy Search Algorithm
(b) Training (Non-Solution)
Expansion
Loussin Algurithen
Vrns
Go
(Gp
* (a) (3,
VQVAE
(a/s)
Go
G1
(((s)
Codebbook Entries
Policy Heuriesic Inference
Gonrate Sulagouls
(ii) Sample texining dhia for VQVAE
Led (Co. Gr... .Gx)
oulput Loavain alguril
(c) Training (Solution)
2. Select graph Gy (Va, Ar) for a given chuster level in J0, N) from (Go, (Go.U2.1 C2..11 .Gr).
3. Sumple wegg m). in from As-
4. Sumpph Yeer and Mar from the sod vi respectivily such that and are in Vo-
Update heuristic model
(BB) Update subgoal generator
Generate training set t-))oo
given sos lo. Ai Ac- Me-
2. Update f., with !
(ii)) Recemndract puih
Mears
VIVVE Farnnde
VQVAE Daooeer
Update subgos! generator
policy
(11) Segneett solution trajectory
1. Calculate ronning mean and variance of sampled trajectation from (b.is)
trajectory length from (biii)
On
O+
varisnce the trajettry lengthe
((v) Up-late high-lwoel and low level policy
from (b.ll)
Sumple segamett length
Ni
Codebook Entry e,
3. Segment solution tsojectory lnto subitijjuctccion of longth
VQYAE
VQVAR
Twender
Ayr outy Aorti far
Codebook Eatries
Figure 1: (a) Tree Search. Policy tree search generates subgoals to use with T- (b) Training (Non-Solution). (i) The underlying graph that induced the tree search is generated from the parent-child relationships found during search, which is used to create a hierarchy of cluster graphs using the Louvain algorithm. (ii) States 8eur and Star are sampled from neighbouring states in G; from the graphs created by the Louvain Algorithm.
(iv) The resulting trajectory from 8eur to Star used update the subgoal generator and low-level policy. (c) Training (Solution). (i) The heuristic is updated using the solution trajectory. (ii) The solution trajectory is segmented. (iii) The subgoal generator is updated using the partial trajectory. (iv) The high-level and low-level policies are updated using the segmented trajectories.
as input to the VQVAE's decoder, which produces a tar- get subgoal state 9g.- The is generated subgoals are then used as inputs to the low-level and high-level policies, then combined to produce SG ,.S(()). (.), as described in Section 3.1.
to condition the low-level policies. We further hypothesize that, in this n x.) scheme, even imperfect reconstructions of subgoal states can be helpful in guiding the search.
To train the VQVAE subgoal generator to generate candidate subgoal states, (Seur: Star) are encoded into the continuous la- tent code ze, quantized to the nearest entry in the codebook ee, then given to the decoder along with Scur to produce a reconstructed target Star- A reconstruction loss Cree (Stur S is used to encourage the reconstructed target subgoal state to match the given target state, along with a penalty to en- courage the encoding vector to become closer to a trainable codebook entry. The full loss is denoted as LvQ, and this procedure is used to train the VQVAE in scenarios where the search terminates without solution found (Section 3.3) and when the search returns a solution trajectory (Section 3.4), with the only difference being how Seur and 8ur are selected. For full details of the loss function used, see Appendix D.
The difference between our work and HIPS-E is how the VQVAE subgoal generator is used. We condition low-level policies on the generated subgoal states to guide the search to reach these subgoals, but search is performed at the search problem's 's action level. HIPS-E performs search at the subgoal-level, where the resulting state-transition from node expansion comes from the generated state of the VQ- VAE. This can be problematic if the generated subgoal states not accurate reconstructions of actual states because the reconstructed states might not be reachable by the search trying to find the subgoals. We hypothesize that HIPS-s will not be able to effectively guide the search in complex environments for which state reconstruction is hard. By con- trast, our policy (.)) uses the reconstructed states only
4

---

Subgoal-Guided Policy Heuristic Search with Learned Subgoals
3.3. Training From Non-Solution Search Trees
the current state along the solution path the goal state (Figure I.c.i). Similarly to previous work, the heuristic function is learned by minimizing the mean squared error between the model's ' predicted value and the actual cost to go for the states along the solution path (Arfaee et al., 201 1).
We leverage data from search trees that during the online Bootstrap training process would normally be discarded. This allows the conditiood low-level policy and subgoal generator networks to be trained on problem in- stances where Levin'TS and PHS* cannot find solutions. This process is shown in Figure 1.b, and in the empirical section, we show how this can lead to significant savings in the total search loss incurred during the Bootstrap training process.
Instead of clustering, we segment the solution trajec- tory (S0, .1....,st)) .s) into sub-trajectories of length at most t' t of the form (st, Si+1......... Smin(i+t',))) .)). Here, {0, t', ."',... - , (') distribution, with mean and variance calculated from the lengths of sampled trajectories from the non-solution trees (Figure I.c.ii). Sampling t' ensures that the average number of state transitions between the 8; and $i+e' states is close to Scur and fur sampled in the non-solution case.
and t' is sampled from a Normal
Different BFS algorithms potentially expand different trees, which form different subgraphs of the underlying state space. We denote the subgraph containing the states represented by the nodes expanded in the tree as Go. If the search cannot solve a problem instance during the online training process, we use this subgraph as the initial graph Go for the Louvain clustering algorithm (Blondel et al., 2008). The Louvain algorithm iteratively creates hierarchy of graphs (Go.... Gx) ) through clustering (Figure I.b.i). Each itera- tion of the Louvain algorithm consists of creating hierar- chical graph Gi+1 = 14+1) from the current graph G. = Ac), where Vi+1 represents a partition of V,, where each in Vi+1 represents a part in this partition. The set A4+1 contains edges (1++1, 2/41) for 1/+1 and 1/411 in V4+1 only if there are a 02 in 0141 (1/ is in the part u++1) and a on in 2/41 (vf is in the part 1 such that (1i, vf) in A, This process continues until graph consisting of a single node is produced, or if G++1= = G,. The pseudocode of this algorithm is given in Appendix E, Algorithm 5.
For each sub-trajectory, Scur and Star are represented by s; and Syt'' respectively. Similarly to Section 3.3, the VQ- VAE subgoal generator is trained using (8t, 8i+e) as input to generate the reconstructed target subgoal state &64er (Fig- ure I.c.ii). The low-level policy Jlo is trained using the sequence of states and actions (8t, 91+1,.... ((4r)) while conditioned on the subgoal & The high-level policy n is trained by generating the k subgoals following the process outlined in Section 3.2 for the state st, of which 8,-0 is one of them, and uses &.40' as the target for training the policy Th (Figure I.c.iv). All policies are trained while minimizing the Levin loss (Orseau & Lelis, 2021).
3.5. Analysis of S
Policy-guided search algorithms can be implemented as BFS, but using our policy definition given in Equation 4. As a result, any policy-guided search algorithm using our policy SG comes with all the guarantees which PHS* provides with completeness being one of them. Specifically, the requirement for completeness is that the loss incurred for each expansion step is non-negative, and that no infinite path has finite path loss (Orseau & Lelis, 2021). This is unlike other subgoal tree search algorithms such as kSubS, AdaSubS, and HIPS, with the exception of HIPS-s.
We use the Louvain algorithm because Evans & Şimşek (2023) showed it to find meaningful structure in other state spaces. The difference between our method and that of Evans & Şimşek is that we learn to generalize subgoals across instances, where they assumed the state-transition graph for each individual problem was known a priori.
For a given clustering level kt the graph G1 produced by the Louvain algorithm is selected. Two states Seur and Sua are sampled from Ek and v/ respectively such that (rk, o() E As (Figure 1.2. If the graph is directed, then a graph traversal is performed in Gu between the two sampled states to determine the order of Scur and Sur such that 8ur can be reached from Scur through a sequence of actions. The VQVAE subgoal generator is then trained using (Seur, Star) as imput to generate the reconstructed target subgoal state 6 of Sur, described in Section 3.2. The low-level slw policy is trained using the sequence of states and actions between Scur and Sar in Go, while conditioned on &g (Figure I.b.ii).
4. Experiments
The goal of our experiments is to test hypothesis that our learning process of 7G is more sample efficient than ex- isting approaches to learning policies for search algorithms. In the extreme case, our method's s sample efficiency enables policies to be learned on complex environment domains in which the existing approaches require a search budget (both in terms of the number of node expansions and in time) which are prohibitively expensive to the point where those methods cannot make any progress. We also evaluate the quality of the learned policies in terms of expansions and solution cost on a separate test set.
3.4. Training From Solution Search Trees
If the search finds solution, then the solution trajectory is used to train the heuristic model hn using the costs of
5

---

Subgoal-Guided Policy Heuristic Search with Learned Subgoals
Boulderbash (Standard)
Box-World (Standard)
CraftWorld (Standard)
Sokoban (Standard)
Outstanding Problems
8000
6000
4000
2000
0.0
0.5
1.5
0.0
0.5
1.0
1.5 0.0
0.5 Expansions
1.0
Expansions
le8
Expansions
le7
Expansions
1e8
1e8
LevinTS(n)
(Ours) LevinTS(r
PHS
(Ours) (H
WA (1.5)
(a) Standard problem instances.
BoulderDash (Hard)
CraftWorld (Hard)
TSP (Hard)
10000
Outstanding Problems
8000
6000
2000
0
0.00
0.25
0.50
0.75
1.00
Expansions
1eB
Expansions
168
Expansions
1c9
LevinTS(n)
(Ours) LevinTS(n='9)
PHS*(N)
(Ours) PHS*(1??)
WA- (1.5)
(b) Hard problem instances.
Figure 2: The line is the average number outstanding problems for the respective number expansions accumulated during training. Shaded regions show maximum and minimum outstanding problems across all seeds.
4.1. Environment Domains
grid. Sokoban is PSPACE-hard (Culberson, 1999). We the Boxoban training and test problems (Guez et al., 2018).
Box-Worid 20 20 room with colored keys and locked boxes (Zambaldi et al., 2018). Keys consumed when used lock of the matching color, with the agent receiv- ing a new key matching the color of the box. The objective is to open the designated goal box by opening the correct se- quence locks. If the agent opens a corresponding lock on the wrong box, the resulting scenario can become dead-end.
Traveling Salesman Problem (TSP): A 10 x 10 grid-based environment where the agent must visit all of the cities before returning back to the first city it visited. The TSP NP-hard (Garey Johnson, 1979).
4.2. Algorithms Evaluated
World A 14 14 room with various materials and workbenches (Andreas et al., 2017). The agent can collect raw materials to create tools. We generate prob- lems with the open-source level generator' of the procedure detailed by Andreas et al. (2017).
A Algorithms with SSG We evaluate our subgoal-guided policy SS on both PHS* and LevinTS, which we denote PHS*(1 and LevinTS(x*S)) respectively. Both *HS* and LevinTS were shown to perform well in single-agent deterministic search problems (Orseau & Lelis, 2021).
BoulderDash: A 14 x room where the agent must gather number of diamonds unlock the exit door, and proceed enter it. Diamonds which the corresponding key must be gathered first. Various dirt elements exist, which disappear once the agent walks over them, and can significantly increase the state-space size. We generate problems by randomly placing the keys, diamonds, and an exit door.
Baselines. To evaluate the training sample efficiency our subgoal-guided policy and data generation method provides from the trees when search terminates prematurely, we compare PHS*(x to PHS* and LevinTS(7>SC) to Lev- inTS using their original single policy formulation, denoted ( and LevinTS(z)), respectively. Following Orseau also evaluate policy formulation
be inside locked sub-rooms in
& Lelis (2021), against Weighted A (Pohl, 1970) with 1.5, which was shown to be more sample efficient than PHS* in some envi- ronments. We also test our method against HIPS-s, which is another complete subgoal- subgoal-guided tree search method.
Sokoban: 10 10 room where the agent must push boxes onto specified goal locations. The box can only be pushed; not pulled, so boxes can get stuck walls of the
6

---

Subgoal-Guided Policy Heuristic Search with Learned Subgoals
4.3. Experimentation Procedure
Table I: Results on the hard environments. "Expansions"
represents the sum over all problems, time is measured in hours, and the maximum value for "Solved" 10,000.
For evaluating the sample efficiency of different methods to learn effective policy, we use the setup of Orseau & Lelis (2021). A loss of E(+) 1 is used, which corre- sponds to the search L(S, mn) being the number of node expansions that an algorithm S requires to solve problem instance k. (*)*(*), (Tv) and WA* are trained using the Bootstrap process (Section 2.1 and Appendix C). (HS) and (=) are trained using the pro- cess outlined in Section 3 (with full pseudocode given in Appendix F). The Bootstrap process starts with budget of 4000 expansions and use a budgeting update schedule noted in Appendix F. During the online training Bootstrap process, we record the number of outstanding training prob- lems which have yet to be solved, and the total accumulated loss (expansions) incurred after every iteration.
ALGORITHM
EXPANSIONS
TIME
SoLVED
CRAFTWORLD (HARD)
WA (1.5)
350.169.632
16.01
1,850
LEVINTS(TT) PH)*(T)
360,454,214
16.02
73
324.718,860
16.04
54
LEVINTS(7 PHS*(**0)
172,188,799
16.02
9
125,089,420
13.74
9,985
BOULDERDASHI (HARD)
WA* (1.5)
599,818,595
16.01
18
LEVINTS(T) (*)*(*)
636,718,68 6338
16.04
16
591,135,427
16.02
19
LEVINTS(7T) )
284,044, 949
16.02
31
85,470,564
6.25
10,000
The training procedure outlined for HIPS-E requires pre- computed dataset of solution trajectories. Since it is not clear how to train HIPS-= online using the Bootstrap pro- cess, we do not include HIPS-s in our training efficiency results. The policy, heuristic, and subgoal generator mod- els used in HIPS-s are trained following the procedure of Kujanpää et al. (2024). For Sokoban, we use the offline datasets provided by Kujanpää et al. (2024). For Box-Worli CraftWorld, and Boulderdash, we use trajectories found by domain-specine solvers over the same training set used to train the other systems with the Bootstrap process.
TSP (HARD)
WA (1.5)
1,019,840,000
16.01
0
LEVINTS(T) PHS*(T)
1,107,904 40000
16.02
0
980,928, ,000
16.02
0
LEVINTS( (T5)
105,838.613
4.55
10,000
20,593,798
1.23
10,000
sions than PHS*(T) and LevinTS respectively, to solve all 10,000 training instances. Sokoban is the only environ- ment where PHS*(T) initially can solve more problems using fewer expansions, but both PHS*(T) and PHS*(7*SU) converge towards the end of training when only the harder problems remain to be solved. We hypothesize that our method performs worse in Sokoban than in the other prob- lems due to the training data that the clustering algorithm generates. While clustering finds important structures in the other problems, it fails to find helpful structures in Sokoban.
Every domain has a disjoint set of 10,000 problem instances to train, 1,000 as validation, and 100 in the test set. Each algorithm is trained on 5 separate seeds, which determine the model initialization, the train and validate problem in- stances partitions, and how the problems are shuffled when batched. For the training efficiency experiment, we report the maximum, minimum, and average number of outstand- ing problems in our plot of results. For testing, we record the number of problem instances each algorithm was able to solve, the average number of expansions required to solve those instances, and the average solution length. We report the version of the trained network which allowed it to solve the highest number of problems, with tie breaks going to the one whose total solution lengths were the shortest (Orseau & Lelis, 2021). Due to the large runtime costs of HIPS-e, we limit the budget during testing to 8,000.
The next set of experiments is similar to the above, but in- stead, it showcases how the sample efficiency of our method enables policies to be learned in more challenging prob- lems. For the domain environments with access to level- generators, problem instances were generated to be suffi- ciently hard, such adding more diamonds for the agent to collect in BoulderDash. All methods were given a maxi- mum of 16 hours for the online bootstrap training process, with the training loss curves given in Figure 2.b and summa- rized Table 1. The baseline algorithms were not able to solve many of the training instances within the time budget, and incurred a large training loss. PHS* (TSG) was able to complete the training process well under the time allocated on all problems evaluated. Despite our method requiring a higher computational cost per node expansion due to the use of several networks, its sample efficiency allows it to solve challenging problems while incurring a substantially smaller cost in terms of both node expansions and computation time.
4.4. Results
The first set of training loss experiments focuses on domains that all the baseline methods can solve. The total search loss incurred over the course of training, as measured by the number of node expansions, is shown in Figure 2.a. In the World, CraftWorld, and BoulderDash environ- ments, the subgoal-guided policy formulation (HS*() and LevinTS(7 (G) require substantially fewer node expan-
7

---

Subgoal-Guidet Policy Heuristic Search with Learned Subgoals
Table 2: Results on the test set for each of the standard domain environments. Expansions and solution length are averaged over solved problems. (f) Expansions reported for HIIPS-E are only for the latent-level space, and thus are not directly comparable the other algorithms.
10000
Pe55 iSolation Onlyl
Problems
8000
6000
ALGORITHM
SOLVED
EXPANSIONS
LENGTH
Box- MOX-WORL.D (STANDARD)
2000
WA (1.5)
100
2,398.68
66.19
(E)
100
605
67.91
(*)
100
767.06
68.07
HIPS-E
100
467.79(1)
67.39
1.00 1.25
1.50
1.75
Expansions
168
LEVINTS(>>0)
100
411.38
66.73
PHS (x
100
378.58
66.75
Figure 3: Reduction in search loss during training when using data from non-solution trees. The line represents the average and the shaded regions show maximum, minimum, and average outstanding problems across all seeds.
CRAFTWORLD (STANDARD)
WA (1.5)
100
2,318.22
90.01
LEVINTS(TT)
100
262.76
93.93
(M)*(()
100
172.04
93.49
HIPS-E
19
116.11(f)
92.47
The results the easier and more difficult domains support hypothesis that our subgoal-gun -ogiddd policies can improve the sampling efficiency of policy-guided search algorithms.
LEVINTS( SG
100
208.28
93.93
PHS PHS"(x
100
103.23
94.54
BOULDERDASH (STANDARD)
WA (1.5)
100
1,193.60
51.44
Search Loss Efficiency from Non-Solution Trees.
LEVINTS(*T)
100
61.33
52.90
(IIS((m)
100
53.65
52.74
One of the main contributions of our method for learning policies is that it can use data from failed searches to train low-level policy and subgoal generator. While the previous experiment evaluated the training efficiency that the com- bination of aubgoal-guided -gudedd policy and the training method provides, this experiment aims to analyze the contribution of each. In Figure 3, we show the search loss during train- ing for PHS*(x$0) in the BoulderDash environment when we limit it to only using solution trajectories update the models. These results show that learning ,0 from solution trajectories already substantially improves the sample ef- ficiency of * We see another improvement when the system learns π SG from both successful and failed searches.
HIPS-E
0
LEVINTS(**
100
488
53.30
(x)
100
53.34
52.68
SokOBAN (STANDARD)
WA (1.5)
100
1,091
32.81
LEVINTS(*))
100
1,177.26
41.04
PH)*(*)
100
1.523.38
39.40
HIPS-
100
80.55(t)
45.24
LEVINTS(**))
100
496.87
41.85
PHIS*("3G)
100
808.42
39.61
constraints. HIPS- performs poorly in these domains be- cause its search performed at the learned subgoal level. In domains whose observations are complex to represent, such as BoulderDash and Cralt HIPSS requires the VQVAE subgoal generator to be very accurate and not miss important features, such as the agent, goal, key object locations. In environments where the VQVAE can reliably reconstruct the states, such as Sokoban, HIPS- performed well and solved all problem instances. Note that expansions being reported by HIPS-E are not directly comparable to the other algorithms, as it only counts the expansions performed in the learned subgoal space, which does not include the costs such as grounding and verifying the actual paths in the original state space. Since PHS*(>S0) and Levin (1: perform the search in the original space, it is more forgiving with reconstruction errors from the subgoal generator.
Test Results. To test the quality of the learned policies, Table 2 reports the average number of expansions and av- erage solution length of each algorithm on the test set of the standard problems. On all domains except for Sokoban, PHS* (HSG) solved the test problems using the least number of expansions on average. WA* is able to find solutions that are the closest on average to the optimal cost, but it requires considerably more node expansions. With the exception of Dash,erDash, LevinTS(<=*5) and (H**( can solve the test problems using fewer node expansions than LevinTS(m)) and PHS*(*) ()), respectively. Taken together, Table and Fig- ure 2 show that learning SG can be more sample efficient than learning non-subgoal-based policies (Figure 2). while asympiotically producing policies of similar quality in terms of expansions and solution cost (Table 2).
HIPS- was unable to solve any problem in BoulderDush, and the majority of problems in CrrldWorld within budget
Table 3 reports similar metrics for each algorithm on the test set of the hard problems. Each problem instance was given a
8

---

Babbgoal-Guide Policy Heuristic Search with Learned Subgoals
Table 3: Results on the test set for each of the hard domain environments. Expansions and solution length are averaged over solved problems.
Goal-Conditioned Reinforcement Learning: Identifying useful subgoal states for policies to navigate between has shown promising results for solving long-horizon tasks, There are many different approaches to how these subgoal states are generated from the history of states the agent has visited. HIGL (Kim et al., 2021) builds a graph of landmark states, from which a goal is selected. HILL (Zhang et al., 2023) and HESS (Li et al., 2021) sample goal states from learned embedding using distance metrics. L.3P (Zhang et al., 2021) learns a latent space and then learns latent land- marks through clustering, and finally decodes the cluster centroids as goals. DisTop (Aubret et al., 2023) clusters an embedding of the state space and samples a goal from one of the selected clusters. Our method is different in that it sub- goals are found using only the underlying properties of the state-space graph, without relying on additional metrics to select subgoals such as novelty and reachability measures.
ALGORITHM
SOLVED
EXPANSIONS
LENGTH
CRAFTWORLD (HARD)
WA+ (1.5) (EVINTS(T)
100
313,572,52
117.03
(*)
LEVINTS
100
395.557.94
123.29
100
3,071.83
120.77
BOULDERDASH (HARD)
WA (1.5)
16
271.636.94
$8.19
(EVINTS(E)
(*)
LEVINTS(=>9) (*5*(
22
315.807.99 91
69.5
100
172.32
84.5
TSP (HARD)
WA (1.5) (EVINTS(*) (*)
502,624.0
45.0
VQ as Subgoal Generators: Vector Quantized Vari- ational Autoencoders (Van Den Oord et al., 2017) have become a popular model to use as subgoal generator. DGRL (Islam et al., 2022), Choreographer (Mazzaglia et al., 2022), and QPHIL (Canesse et al., 2024) use VQVAEs gener- ate target subgoal observation, which is used with the current state input to policies. VQVAEs are generally trained on an offline dataset, separate from the reinforcement learning task. CQM (Lee et al., 2023) trains a VQVAE to discretize continuous observations, which is used to create a curriculum over landmarks. Our method trains a VQVAE to generate subgoal observations, but does so online, while learning the policy. This allows our method to be used in scenarios where generating quality training trajectories is too costly.
LEVINTS( PHS*(x"50) 59)
100
570.09
40.89
100
41.93
41.73
maximum budget of 512.000 node expansions. (*S*) was able solve all test problems, while the other compar- ison methods struggled to solve majority of them. The exception is WA* on World, but it required over 100 times more node expansions as compared to PHS*(x Due to the complexity of the problem instances, HIPS- is omitted from these results as it requires a dataset of solution trajectories to train its policies and subgoal generator.
5. Related Work
6. Conclusion
Subgoal Search. Our work is primarily related to other works that use subgoals in search. kSubS (Czechowski et al., 2021) Iearns a subgoal generator to predict resulting states that are & steps ahead of the current state. AdaSubS (Zawalski et al., 2022) extends kSubS by learning multiple subgoal generators, each for a different look-ahead depth k. Since both kSubS and AdaSubS search at the subgoal level, they are not complete. HIPS (Kujanpää et al., 2023) learns to segment trajectories through reinforcement learning, then trains a subgoal generator using these trajectories and a low-level policy to reach the generated subgoals. HIPS also searches at the subgoal level, and thus is not complete. HIPS- (Kujanpää al.,, 2024) augments the subgoal search by combining the subgoals and the actions of the environ- ment. These approaches require a precomputed dataset of solution trajectories, which our approach does not require. Also, we showed empirically that HIPS-E might fail to solve problems when reconstructing the state is challenging, while our approach is robust to reconstruction inaccuracies.
In this paper, we presented a novel way to combine subgoal discovery with subgoal-guided policies, which can be used as a drop-in replacement to policies used in existing policy tree search algorithms, such as LevinTS and PHS* The neural network models in our method can be trained online without needing an offline solution dataset. Moreover, it can be trained from both successful and failed searches, which we showed to improve the sampling efficiency of tree search algorithms substantially. This is due to the fact that a sub- goal conditioned policy can be trained using non-solution trajectories from the search tree. In the domains evaluated, our experiments showed that the large reduction in environ- ment interactions does not reduce the quality of the solutions found, while requiring fewer expansions at test time. As we increased the problem's 's difficulty, the gap between our subgoal- approach and other approaches increased while our learned policies solved all test problems, previous approaches failed to learn effective ones.
9

---

Subgoal-Guided Policy Heuristic Search with Learned Subgoals
Acknowledgements
Subgoal search for complex reasoning tasks. Advances in Neural Information Processing Systems, 34:624-638 2021.
This research was supported by Canada's NSERC and the CIFAR AI Chairs program. This research was enabled in part by support provided by the Digital Research Alliance of Canada. The authors thank the anonymous reviewers for valuable feedback on this work.
Evans, J. B. and Şimşek, Ö. Creating multi-level skill hi- erarchies in reinforcement learning. Advances in Neural Information Processing Systems, (8648872-484444 2023,
Impact Statement
Garey, M. R. and Johnson, D. S. Computers and Intractabil- ity: A Guide to the Theory of JPP-Completeness. W. H. Freeman, 1979.
This paper advances the field of Machine Learning by demonstrating how to improve existing tree search ap- proaches to solve difficult "heedle-in-thh-hhysttac single- agent problems. While the primary impact of our work is technical and our evaluated domains are game-like, this re- search direction could have broader applications in the long run. We do not see immediate societal risks, but as with any research in this field, ethical considerations should be taken into account when deploying these methods in real-world settings.
Guez, A., Mirza, M., Gregor, K., Kabra, R., Racaniere, S., Weber, T., Raposo, D., Santoro, A., Orseau, L.,, Eccles, T., Wayne, G., Silver, D., Lillicrap, T., and Valdes, V. An investigation of model-free planning: boxoban levels. 2018.
He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learn- ing for image recognition. Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778. 2016.
References
Andreas, J., Klein, D., and Levine, S. Modular multitask reinforcement learning with policy sketches. In Inter- national conference machine learning, pp. 166-175. PMLR. 2017.
Islam, R., Zang, H., Goyal, A., Lamb, A., Kawaguchi, K., Li, X., Laroche, R., Bengio, Y., and Combes, R. T. D. Discrete factorial representations goal conditioned reinforcement learning. arXiv preprint arXi::2211.00247 2022.
abstraction for
Arface, S. J., Zilles, S., and Holte, R. C. Learning heuristic functions for large state spaces. Artificial Intelligence, 175(16-17):2075-2))) -2908 2011.
Kim. J., Seo, Y., and Shin, J. Landmark-guided subgoal generation in hierarchical reinforcement learning. Ad- vances in neural information processing systems, 34: 28336-28349, 2021.
Aubret, A., Matignon, L.,, and Hassas, S. Distop: Discov- ering a topological representation to learn diverse and rewarding skills. IEEE Transactions on Cognitive and Developmental Systems, 15(4):1905-1915, 2023.
Kingma, D. Adam: A method for stochastic optimization. arXiv preprint 1412 128600 2014.
Blondel, V. D., Guillaume, J.-L., Lambiotte, R., and Lefeb- vre, E. Fast unfolding of communities in large networks. Journal of statistical mechanics: theory and experiment, 2008(10):P1000S 2008.
Kocsis, L. and Szepesvári, C. Bandit based monte-carlo planning. In European conference on machine learning, pp. 282-293. Springer, 2006.
Kujanpää, K., Pajarinen, J., and Ilin, A. Hierarchical im- itation learning with vector quantized models. In Inter- national Conference Machine Learning, pp. 17896 17919. PMLR, 2023.
Brandes, U., Delling, D., Gaertler, M., Görke, R., Hoefer, M., Nikoloski, Z., and Wagner, D. Maximizing modular- ity is hard. arXiv preprint physics/0608255, 2006.
Canesse, A., Petitbois, M., Denoyer, L., Lamprier, S., and Portelas, R. Navigation with qphil: Quantizing plan- ner for hierarchical implicit q-learning. arXiv preprint arXiv:2411.07766) 2024.
Kujanpää, K., Pajarinen, J., and Ilin, A. Hybrid search for ef- ficient planning with completeness guarantees. Advances in Neural Information Processing Systems, 36, 2024.
Lee, S., Cho, D., Park, J., and Kim, H. J. Cqm: Curriculum reinforcement learning with a quantized world model. In Oh, A., Naumann, T., Globerson, A., Saenko, K., Hardt, M., and Levine, S. (eds.), Advances in Neural Informa- tion Processing Systems, volume 36, pp. 78824-78845. Curran Associates, Inc., 2023.
Culberson, C. Sokoban PSPACE-complete. In Inter- national Conference Fun with Algorithms (FUN), pp. 65-76, 1999.
Czechowski, K., Odrzygóżdž, T., Zbysiński, M., Zawal- ski, M., Olejnik, K., Wu, Y., Kucinski, L.., and Mitos,
10

---

Subgoal-Guided Policy Heuristic Search with Learned Subgoals
Leicht, E. A. and Newman, M. E. Community structure in directed networks. Physical review letters, 100(11): 118703, 2008.
Schrittwieser, J., Antonoglou, I., Hubert, T., Simonyan, K., Sifre, I.., Schmitt, S., Guez, A., Lockhart, E., Hassabis, D., Graepel, T., et al. Mastering atari, go, chess and shogi by planning with learned model. Nature, 588(7839): 604-609, 2020.
Li, S., Zhang, J., Wang, J., Yu, Y., and Zhang, C. Active hi- erarchical exploration with stable subgoal representation learning. arXiv preprint arXiv:2105. 14750, 2021.
Silver, D., Hubert, T., Schrittwieser, J., Antonoglou, I., Lai, M.. Guez, A., Lanctot, M., Sifre. L., Kumaran, D., Grae- pel, T., et al. Mastering chess and shogi by self-play with general reinforcement learning algorithm. arXiv preprint arXiv:1712.01815, 2017.
Liu, G. and Ramakrishnan, K. prune: an algorithm for finding k shortest paths subject to multiple constraints. In Proceedings IEEE INFOCOM 2001. Conference Computer Communications, Twentieth Annual Joint Con- ference of the IEEE Computer and Communications Soci- ery (Cat. No.01CH37213), volume 2, pp. 143-749 vol.2, 2001. doi: 10.1109/NFCOM.200 .166263.
Tan, C. S., Mohd-Mokhtar, R., and Arshad, M. R. A com- prehensive review of coverage path planning in robotics using classical and heuristic algorithms. IEEE Access, 9: 1 119310-1199 119342, 2021.
Mazzaglia, Verbelen, T., Dhoedt, B., Lacoste, A., and Rajeswar, S. Choreographer: Learning and adapting skills in imagination. arXiv preprini urXiv:2211.13350. 2022.
Van Den Oord, A., Vinyals, O., al. Neural discrete rep- resentation learning. Advances in neural information processing systems, 30, 2017.
Zambaldi, V., Raposo, D., Santoro, A., Bapst, V., Li, Y.. Babuschkin, I., Tuyls, K., Reichert, D., Lillicrap, T., Lockhart, E., et al. Relational deep reinforcement learn- ing. arXiv preprint arXiv:1806 1806.01830 2018.
Newman, M. E. and Girvan, M. Finding and evaluating community structure networks. Physical review E, (2):026113 13, 2004.
Orseau, L. and Lelis, L. H. Policy-guided heuristic search with guarantees. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 12382-12320 2021.
Zawalski, M., Tyrolski, M.. Czechowski, K., Odrzygóżdž, T., Stachura, D., Piękos, P., Wu, Y., Kuciński, E., and Mitoš, P. Fast and precise: Adjusting planning horizon with adaptive subgoal search. arXiv preprint arXi::2206.00702 2022.
Orseau, L., Lelis, L., Lattimore, T., and Weber, T. Single- agent policy tree search with guarantees. Advances in Neural Information Processing Systems, 31, 2018.
Zhang, L.,, Yang, G., and Stadie, B. C. World model as graph: Learning latent landmarks for planning. In International conference on machine learning, pp. 12611- 12620. PMIR, 2021.
Orseau, L., Hutter, M., and Lelis, L. H. Levin tree search with context models. arXiv preprint 2.XX::2305.1694. 2023.
Zhang, Q. Yang, Y., Ruan, J., Xiong, X., Xing, D., and Xu, B. Balancing exploration and exploitation in hierarchical reinforcement learning via latent landmark graphs. In 2023 International Joint Conference on Neural Networks (IJCNN), pp. 1-8. IEFE, 2023.
Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., Desmaison, A., Kopf. A., Yang, E., Veto,, Z., Raison, M., Tejani, A., Chilamkurthy, S., Steiner, B., Fang, I.., Bai, J., and Chintala, S. Pytorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems 32, pp. 8024- 8035. Curran Associates, Inc., 2019.
Pearl, J. Heuristics: intelligent search strategies for com- puter problem solving. Addison Addison-Wesley Longman Pub- lishing Co., Inc., 1984.
Pohl, I. Heuristic search viewed path finding in graph. Artificial intelligence, 1(3-4):193-2044 1970.
Rosin, C. D. aumdi- bandits with episode context.
Annals of Mathematics and Artificial Intelligence, 61(3): 203-230, 2011.

---

Subgoal-Guided Policy Heuristic Search with Learned Subgoals
A. Best-First Search
Algorithm I Best-Firrt Search (BFS)
1: Input: Initial state S0, evaluation function budget
2: Output: Solution node, or status failed search
3: struct Node (state 8, float g}
4: q - prioritt__qeeuerrrer__..
4p)
5: <- set()
(Set of visited states. {Root node.)
6: Node 0)
7: insert(g no. ((mo))
8: b +-0 0
9: while not empty and b < B do
n + extract_minng)
s state(n)
b b+b+1
13: if then continue
14:
(Previously expanded state.)
15: end if
16: insert(u,s)
17: for each E expand(n) do
+ state(n')
if is then
20: return n'
21: end if
22:
Ansert(q. n', (((()) 23: end for
24:
end while
return timeout i B else no no_solution
B. Policy Tree Search
Algorithm and Algorithm depict the policy tree search algorithms Levin Tree Search (Levin'SS) and Policy-Guidae Heuristic Search (PHS*) respectively.
Algorithm 2 Levin Tree Search (Levin'TS)
1: Input: Initial state sp, budget b
2: Output: Solution node, or status of failed search
3: return (FS (PLevinTS,
Algorithm 3 Policy-Guided Heuristic Tree Search (PHS*)
1: Input: Initial state 8p, budget
2: Output: Solution node, or status of failed search
3: return BFS(so, spuss, b)
12

---

Subgoal-Guided Policy Heuristic Search with Learned Subgoals
C. The Bootstrap Training Process
Algorithm 4 depicts the Bootstrap Process. After each iteration of the algorithm, new budget needs to selected. Arfaee al. (2011) unconditionally double the budget every iteration. Orseau & Lelis (2021) double the budget only if new problems are solved in the current iteration.
Algorithm 4 The Bootstrap Process
Input: Initial budget Bo, root states 8 (training problems), search algorithm S, neural policy/heuristic models +
2: sclved <- set()
3: for (= 0, 1.. do
4: for each E S do
5: result + S,
6: # timeout and result * co_soluuionn then
7: insert(solved, nn)
8: update θ using solution trajectory from result
9: end if
10: end for
11: if [ssol vedl [ then
12: break
13: end if
14: choose budget B++1
end for
D. Vector Quantized Variational Autoencoders
VQVAEs utilize a codebook containing trainable D-dimensional embedding vectors e, E IR, i l...., Inputs æ are encoded by the encoder, resulting in an encoded vector ze. The encoding vector is then mapped quantized encoding vector 2g which is the nearest embedding vector using Euclidean distance:
Zg
Ect
where c arg min ||= e:ll2-
The discretized encoding vector is then passed through the decoder which produces reconstructed output ž. The loss function used to optimize the encoder, decoder, and codebook is given by
Lvq Liee x) + [[=) -..12 + B sg
(6)
where Leee is the reconstruction loss, and sg(.) is the stop gradient operation. The stop gradient is required that independently update the codebook to converge to the encoding vector, and the encoding vector to converge the codebook.
13

---

Subgoal-Guided Policy Heuristic Search with Learned Subgoals
E. Louvain Algorithm
partition of graph is grouping of its nodes into mutually exclusive groups called clusters. The modularity (Newman Girvan, 2004; Leicht & Newman, 2008) of a graph measures the relative density of edges inside the clusters to outgoing edges. The modularity of cluster Qe is given by
>C Q
DC 2 2m
P
2m
where Eng is the total edge weight between nodes in cluster c, E is the total edge weight within the cluster (which includes edges leading out to other clusters), m is the sum of all edge weights in the graph, and p > 0 is balancing parameter. The modularity of a graph G is then given by the sum of all cluster modularities: Q = Ec Qe- A clustering that maximizes the modularity of the graph is one that has dense connections between nodes in the same clusters, with sparse connections between each of the clusters.
has been shown that finding partition of a graph that maximizes the modularity is NP-hard (Brandes al., 2006), so approximation algorithms generally used. The Louvain algorithm (Blondel al., 2008) is an iterative hierarchical graph clustering algorithm. It works by first placing every node of the given graph Go into its own cluster. Nodes are then moved into neighbouring cluster iteratively if it increases the overall modularity of the graph. This process stops once no additional progress can be made. The result is clustering over the graph, which can then be used to create new aggregate graph G1 as follows: clusters of Go become nodes in graph G1, and two nodes in G1 have an edge joining them if there exists an edge that connects neighbouring clusters in Go- The resulting graph G1 can then be used this process again, which will produce another aggregate graph G2, and so on until either final graph has single node or the returned graph G++1 is the same graph as G2 (i.e., no nodes were able be moved a different cluster). The result from this process hierarchy of graph clusterings, in which earlier graphs contain many smaller clusters which are then merged into fewer larger clusters.
The Louvain algorithm is given as pseudocode in Algorithm 5, which is adapted from Evans & Şimşek (2023).
Algorithm 5 The Louvain Algorithm
1: Input: Base graph Go = (Vo, Ea)
2: Output: Hierarchy of graph clusterings
3: for = 1,.. do
4: C. + [u1}
Vij
(initialize singleton cluster over each node.) [Modularity of C₁, Equation 7.}
5: Qoi + E, DC /2m - P(E(C)) (2mm))
6: repeat
7: for each u E do
8:
Find cluster E C, node belongs to Find neighbouring clusters N, of
9:
10:
Remove u from cluster e
11:
Compute modularity gains by moving u into each neighbouring cluster N, Move u into neighbouring cluster maximizing modularity, gain > end for
12:
14:
until no change in C.
15:
Qnew E. (CC /2m pl (2 ((2m)))
[Modularity of updated C, Equation 7.)
16:
if Quew Qold then
17:
V4+ + {cICE C.}.
(Parent graph G where nodes are clusters from G..)
E+1 ((c,,c) cj E Ct cs and ej are neighbours in C.}
19: G (V,-1, Fet1)
20: else
21:
break
No further gain.)
22:
end if
23:
end for
24: return (Go....,Gay GN)
14

---

Subgoal-Guided Policy Heuristic Search with Learned Subgoals
F. Complete Training Procedure
Algorithm 6 depicts our modified Bootstrap training algorithm which we use for PHS*(T50) and LevinTS(77SC), After each iteration of the algorithm, a new budget needs be selected. our experiments, we follow budget selection method which follows Orseau et al. (2023): If more than factor (1 + b) of problems are solved in the current iteration & than was the previous iteration t the next budget reduced to B++1 max Bu, B2) Otherwise, the budget is increased to B++1 2B; + T,/ Tr/st, where T, is the total number of expansions used for the solved problems, and is the number of remaining unsolved problems.
Algorithm Sabgoal-Guides Policy Search Training Procedure
1: Input: Initial budget Bo, root nodes Ao (training problems), low-level conditional policy nbw high-level subgoal policy T heuristic model thw Subgoal Generator VQg, Louvain sampling level k, Policy Search algorithm S
2: so solved < -et()
3: lengths < []
4:
1.... do
5: for each no Vo do
6: result S(n,. |=b T A vQol: B.)
7:
if result # timeout and result # no_solution then insert(solved,nu) mu)
8:
9:
T= (s0, 00, ,1..,...., 8t) + reconstructed path from initial state state(no) to goal state state(n") Optimize h. for each state s, E T by minimizing the mean-squared error with respect to the distance to 8t. + partition 7 into sub-trajectories lengths sampled from Normal distribution parameterized by the mean and variance of lengths
10:
11:
12:
for each PT = (8i, Oi; 8141,-... ..t..)......)))))... E T do
13:
8141' f- VQ (s, $i4r')
14:
89 + 18 C quantized codebook index from VQo ((:e)
(VQa(e,,s) s
15:
16:
Optimize VQ by minimizing the loss LvQ( (8ittr, 81++)
17:
Optimize n/wo n (ajlsj, (8j, 8145) for each 8j, aj PT by minimizing the cross-entropy loss with respect to a,
Optimize Th ($gls)) (5) for each s, PT by minimizing the cross-entropy loss with respect to $g.
19:
end for
20:
else
21:
Go + underlying graph from search tree
22:
Ge < kth cluster graph from Louvain(C (Go)
23:
C, Cj t sampled neighbour clusters from G
24:
Seur f sampled state from C
Sur + sampled state from C₁
T (so, ag, s1,..., 8t) < reconstructed path from Seur Star
27:
insert(lengths.t)
28:
Sur + VQ Star)
29:
Optimize VQ by minimizing the loss LvQ (S Sta)
30:
(as(si, Star for each 8;, E T by minimizing the cross-entropy loss with respect to Optimize TiB
low
31:
end
32:
end for
33: if solved | then
34: break
35: endie if
36: choose budget B
37: end for
15

---

Subgoal-Guided Policy Heuristic Search with Learned Subgoals
G. Implementation and Machine Details
The algorithms and environment are implemented in C++, adhering to the C++20 standard. The codebase 2 compiled using the GNU Compiler Collection version 13.3.0, and uses the PyTorch 2.4 C++ frontend (Paszke al., 2019). Where available, the official implementation of comparison methods are used. All experiments were conducted on an Intel i9-7960X and Nvidia 3090, with 128GB of system memory running Ubuntu 24.04.
H. Additional Environment Details
Most the problem instances used in this paper are based off of existing open source implementations. Box- World uses an open source problem generator with a goal length of and several distractor paths of length 3. distractor path is a sequence of key and locks which can be used by the agent, but does not progress to the goal. Craft uses custom problem generator based off of (Andreas et al., 2017), which has various levels of difficulty for the generated problems. BoulderDash also uses a custom problem generator which randomly places coloured keys, doors, diamonds, and the exit in different rooms. Sokoban uses the Boxban problems. Finally, TSP uses a custom level generator to randomly place the agent starting location and the cities.
Box-World
CraftWorld
BoulderDash
Sokoban
TSP
Figure 4: The environment domains used in the experiments. Box- World: The agent in black needs to open colored locks (right pixel) to receive colored key (left pixel) until it gets to the goal (white). CraftWorld: The agent must create an iron pickaxe to get the gem that they can craft a ring. BoulderDash: The agent must get the green key to unlock the room containing the diamond. Once the diamond is collect, the exit in the bottom-right room will open. Sokoban: The agent must push boxes to the goal locations without getting boxes stuck in corners. TSP: The agent (black) must visit each city (red) then return back to the first city (blue). The gray boxes are traversable obstacles.
I. Additional Experimental Details
In experiments, PHS*(x55) (ev"nTS(=>99), (HS*(m), LevinTS(Tr). and WA* all use ResNet-based (He al., 2016) networks. (HS*(T) uses single network with two heads, one for the policy and one for the heuristic. For )=S)( we use separate networks for the conditional low policy, and two-headed network for the subgoal policy and global heuristic. LevinTS(=7SG) follows the same network structure, without the heuristic head. We use the Adam optimizer (Kingma, 2014), with learning rate of 3E-4 and L2-regularization of IE-4, The policy and heuristic networks for PHS*(T). (m)), (HS*), and (T) both use 128 ResNet channels, with PHS*(;;S)) and LevinTS (=) using half the number blocks (4 versus 8) due to the fact that they both have both a low-level and high-level policy. The VQVAE subgoal generator a codebook size of 4, codebook dimension of size 128, and 0.25. We use the open source implementation for HIPS- in our experiments". We use IE-3 for all environments, and use for version of HIPS-a which assumes access to an environment dynamics model. All other hyperparameter follows the authors choice in their Box- World experiments (Kujanpää et al., 2024).
"https://gituub.com http::/hhhbbboomuuuuoou/uuaaaaap
hheps://gthu...oo/maatii http:/hwww....m/cacaaaannnnnnnnn World
"http://github.. "henps//gituhh.oom/llleeee com.kalleekk//HISS
16

---

Subgoal-Guided Policy Heuristic Search with Learned Subgoals
J. Ablation: Impact of Codebook Size
The size the codebook the VQVAE determines the number how many subgoals are parameterized by the model. In Figure 5, we show the search loss during training for various codebook sizes on the CraftWorld environment. The chosen codebook size of incurs the smallest search loss, but note that there is fair amount of overlap between the curves. Table 4 shows how each of these models performs the test set. While the solution length is relatively the same, there is quite large difference in the number of expansions required to solve the problems. If too few subgoals are used, then the codebook becomes overburdened in trying to represent single subgoal state. Interestingly, if too many subgoals are used, we also see an increase in the number of expansions required. One possible reason for this could be that a large number of codebook entries are not being used, then the resulting mixture policy will look more like uniform policy, which will increase the number of node expansions required. One avenue for future work is to dynamically remove unused codebook entries from being used in the final policy.
10000
k
16
8000
Outstanding Problems
4000
2000
0.0
0.2
0.4
0.6
0.8
1.0
Expansions
1e8
Figure 5: Learning curves during training using the Bootstrap process for varying codebook sizes. The line is the average outstanding problems for the respective number of expansions accumulated during training. All training runs lie within the shaded regions.
Table 4: Results on CraftWorld test set using various codebook sizes. Expansions and solution length are averaged over solved problems.
ALGORITHM
SOLVED
EXPANSIONS
LENGTH
100
263.92
92.52
K =
100
103.23
94.54
K = 16
100
305.17
94.16
17

---

Subgoal-Guided Policy Heuristic Search with Learned Subgoals
K. Ablation: Impact of Cluster Graph Level when Sampling Subgoals
From the base graph Go. the Louvain algorithm produces a hierarchy of cluster graphs [GI....,Gy, Gr3 where earlier graphs contain many smaller clusters with later graphs merging them into fewer clusters. One decision make when sampling subgoals which of these cluster graphs the hierarchy choose from. Smaller abstraction levels will generally result in pairs of states being sampled which are close in space/time, and larger abstraction levels will generally result in pairs of states further apart, which is depicted in Table 5.
Table Average trajectory length between subgoals for each cluster level on the CraftWorld environment.
CLUSTER GRAPH LEVEL
SUBGOAL DISTANCE
1.66
4.93
5
17.29
Figure shows the search loss during training when sampling subgoals from various cluster graph levels, and Table 6 shows the test results the World environment. From the search loss during training and test time, it appears that one must be careful in that they do not sample subgoals which are too close together from G1, the subgoals will not be as meaningful. Sampling subgoals from Gs which were far apart as compared to G3 did lead to a slight loss in performance, both in terms of number of node expansions and solution length.
10000
8000
Outstanding Problems
6000
4000
2000
0.0
0.2
0.4
0.6
0.8
1.0
Expansions
1e8
Figure 6: Learning curves during training using the Bootstrap process for varying cluster graph levels from which subgoal states were sampled from. The line the average outstanding problems for the respective number of expansions accumulated during training. All training runs lie within the shaded regions.
Table 6: Results on Cralt test set using models which were trained using various cluster graph levels. Expansions and solution length are averaged over solved problems.
ALGORITHM
SOLVED
EXPANSIONS
LENGTH
G1
100.00
287.24
93.88
G3
100.00
103.23
94.54
G5
100.00
110.10
95.05
18

---

Subgoal-Guided Policy Heuristic Search with Learned Subgoals
L. Robustness to Out-of-Distribution Scenarios
Table 7 represents the results of an experiment that evaluates the algorithms on BoulderDash problems which require two keys unlock two consecutive doors before reaching the diamond, whereas the neural policy and heuristic models were trained on problems where only a single key was required. PHS*(T) and PHS*(=*0) perform similarly, using a number of expansions close to the solution length which means that the policies learned problems. LevinTS((=S0) can handle out-of-distribution problems much better than LevinTS(rr) in terms of the number of expansions required, while finding solutions slightly longer. WA* could not solve all problems, possibly for having to rely only on the guidance of a heuristic function. The heuristic WA* uses was trained to estimate the cost-to-go in a smaller interval than the longer out-of distiriiibtt problems. Note that HIPSS-E is not present here as was unable to solve any BoulderDash problems in the original test set, due the subgoal generator having difficulty reproduce the complex state representation.
almost deterministically solve these
Table 7: Results on an out-of-distributtion test set for BoulderDash. Expansions and solution length are averaged over solved problems.
ALGORITHM
SOLVED
EXPANSIONS
LENGTH
WA (1.S)
73
9.712.64
68.29
LEVINTS(T)
100
131.41
70.15
PHS*(T)
100
72.45
70.37
LEVINTS(+
100
72.30
72.09
PHS*(T50)
71.35
70.25
19


Reviews:
[{"review_id": "RqGPeQk36L", "reviewer": "Reviewer_WUJG", "summary": "- The paper proposes an algorithmic framework for best-first search intended to solve deterministic search problems. The primary contributions of the paper are algorithmic and empirical. The main algorithmic idea is to learn control knowledge to speedup search. Subgoals here refer to state abstractions represented by a VQVAE, with the size of the subgoal \"space\" parameterized by the size of the VQVAE codebook. The resulting control knowledge takes the form of a pair of policies, one generating subgoals and one conditioned on them. These can now be used to guide the search towards states more likely to lead to solutions (based on previously solved problem instances).\n\n- The training algorithm consists of alternating between generating search control knowledge with the current policy and updating the policies and heuristic function in a loop. Key implementation choices include using the Louvain clustering algorithm to generate training data for the subgoal generator (VQVAE) as well as scaling training data for the VQVAE subgoal generator by augmenting the supervised solution sub-trajectories with additional data generated via a clustering-based approach.\n\n- Results on four deterministic search domains show that the proposed algorithm is more sample efficient than the baselines (which do not use the learned control knowledge) without any deterioration in solution quality.\n\n---\n\n## update after rebuttal\n\n  - I thank the authors for their detailed responses to the reviewers. These have addressed my main concerns about the paper. I'm now more positively inclined towards the paper and have revised my score upwards.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "Thank you for your helpful comments and feedback.\n\n**Question 1**\n\nThank you for your suggestion to run on more difficult instances. We ran additional experiments on a much larger version of BoulderDash, following the same procedure from **Section 4.3**. We also tried increasing the network size used in PHS*($\\pi$) (denoted LARGE) to match the number of parameters used in PHS*($\\pi^{SG}$) to show that simply using more parameters does not help.\n\nOur results are summarized in the tables below. Our proposed approach, PHS*($\\pi^{SG}$), learned how to solve the difficult set of BoulderDash within 6.25 hours. The baselines did not learn to solve the problems even when granted 4x more expansions and 2x more time. \n\n|Algorithm | Total Loss (Expansions) | Total Time (Hours) | Training Instances Solved | Nodes Generated per Second |\n|---|---:|---:|---:|--:|\n| WA* | 606,000,000 | 15.58 | 16 |1,872.31 |\n| LevinTS($\\pi$) | 636,718,638 | 16.69 | 16 | 1,828.51 |\n| PHS*($\\pi$) | 599,849,865 | 15.61 | 16 | 1,765.00 |\n| PHS*($\\pi$) LARGE | 344,512,985 | 33.04 | 1 | 496.45 |\n| PHS*($\\pi^{SG}$) [Ours] | 85,470,564 | 6.25 | 10,000 | 791.69 |\n\nWe then tested the resulting models on a separate test set of 100 problems to match the procedure done for Table 1. \n| Algorithm | Solved | Expansions |\n| --- | --: | --: |\n| WA* | 14 | 272,872.28 |\n| LevinTS($\\pi$) | 14 | 280,407.36 | \n| PHS*($\\pi$) | 14 | 288,045.64 |\n| PHS*($\\pi$) LARGE | 4 | 110,805.75 |\n| PHS*($\\pi^{SG}$) [Ours] | 100 | 1,291.37 |\n\n**Question 2**\n\nThe results on the more difficult instances of BoulderDash we presented above highlight that PHS*($\\pi^{SG}$) can be substantially faster than the baselines, to the point where PHS*($\\pi^{SG}$) learns how to solve the problems while the baselines do not.  Next, we present the runtime statistics for the methods listed in Table 1, on the easier problem instances, for a representative example; the tables for the other domains are similar and were omitted for space. \n\nWhat the table below shows is that, from a practical perspective, all algorithms tested, once they learn a policy and/or heuristic, are able to solve the test problems within a reasonable amount of time. The key difference between the method we propose and the baselines is the time that it might take them to learn the policy and heuristic. As demonstrated in the more difficult BoulderDash instances, the difference between our approach and baselines can be the same as solving all instances versus solving none of the instances.\n\n| Algorithm | Solved | Expansions | Length | Total Time (Seconds) |\n| --- | ---: | ---: | ---: | ---: |\n|  | | **BoulderDash** | | |\n| WA* (1.5) | 100 | 1,193.60 | 51.44 | 31.93 |\n| LevinTS($\\pi$) | 100 | 61.33 | 52.90 | 4.82 | \n| PHS*($\\pi$) | 100 | 53.65 | 52.74 | 5.60 | \n| LevinTS($\\pi^{SG}$) | 100 | 65.48 | 53.30 | 16.18 | \n| PHS*($\\pi^{SG}$) | 100 | 53.34 | 52.68 | 10.89 | \n\nThe following addresses your points from the Weaknesses section.\n- **Formal definition of a subgoal**: Subgoals are states from the underlying state space that the search attempts to achieve.  We will clarify this in the paper\n- **Restricting to deterministic problems**: Deterministic problems are an important and active area of research. There is also a body of work which looks at how transformations can be applied to non-classical planning problems (e.g., non-determinism/incomplete information) from the classical planning setting we consider in our work [5]\n- **Is the proposed method is better than existing technique**: WA*, LevinTS, and PHS* are the current state of the art methods for the problems we consider. [1] and [4] consider two-player games and Orseau & Lelis showed that PUCT performs quite poorly on this type of problem. [3] solves MDPs, whereas we consider the classical planning setting. [2] requires a dataset of structured input/outputs, whereas we focus on needle-in-a-haystack problems. The suggested references, [1-4], are only related to our work in a broad sense.\n- **Intuition for Equation (4)**: We provide the intuition of Equation 4 with an example. Consider the case where one subgoal could be \"go to the door on left\", while another could be \"go to the door on the right\". Mixing these two subgoals would result in a uniform (and ineffective) policy. The high-level policy decides which subgoal to attain next by providing a weight to the probability distribution given by the low-level policies. This way, the high-level policy decides whether the agent will go right or left. \n- **Baselines do not use the learned control knowledge**: All baselines learn a policy and/or heuristic. In particular, LevinTS/PHS* use the same Bootstrap pipeline that our method uses.\n\n[5] Geffner, Hector. \"Non-classical planning with a classical planner: The power of transformations.\" European Workshop on Logics in Artificial Intelligence. Cham: Springer International Publishing, 2014.", "claims_and_evidence": "- The claims are reasonably well supported.", "methods_and_evaluation_criteria": "- Table 1 shows nearly all baselines and the proposed methods solve all test problem instances. This suggests that the problem domains might be a bit too \"easy\". It is currently unclear how the method might perform on harder problems.\n\n- The experimental section is somewhat thin. Since search quality is not shown to be improved, it would have been good to see a conclusive empirical demonstration of search speedup. This does not happen in the paper. While number of node expansions is a reasonable metric, I'd suggest a more detailed investigation into runtimes and computational overhead is warranted.", "theoretical_claims": "- The paper does not focus on theoretical aspects. The properties of the search seem fine to me.", "experimental_designs_or_analyses": "- Yes. The experimental setup described in Section 4 and the appendices seems fine to me.", "relation_to_broader_scientific_literature": "- The main algorithmic contribution is a good combination of ideas from prior work (Louvain clustering, VQVAE-based subgoal generation, k-step data generation as shown in kSubS and AdaSubS).", "essential_references_not_discussed": "- None that I can spot. The paper's related work section needs some improvement though to make it more complete.", "other_strengths_and_weaknesses": "Strengths\n\n  - The paper tackles an interesting and important problem. The ability to learn search control knowledge for improving search quality and speed, without the need for manual domain engineering, has large utility.\n  - The overall approach is intuitively clear.\n  - The paper seems to be an interesting and novel combination of prior ideas (Louvain clustering, VQVAE as subgoal generator, best-first search, differentiable policies).\n  - The experimental results show that the proposed algorithm needs fewer node expansions to find solutions of similar quality.\n\n\nWeaknesses\n  \n  - The paper mentions its approach in detail but does not offer much motivation or justification for its algorithmic choices. Examples below.\n    - What's a formal definition of a subgoal as used in the paper?\n    - Why restrict to deterministic problems? What doesn't work if there's randomness or noise in the transition function?\n    - What's the intuition for choosing the particular form of $\\pi^{SG}$ described in Equation 4? What other forms were considered? Why was this one preferred over those?\n\n  - Considering the large body of work on learning search control knowledge to improve search quality and speed [1,2,3,4], the experimental section needs improvement. It is unclear to me if the proposed method is better than existing techniques. Details follow.\n    - All considered domains are solved at test time by all methods including baselines without any improvement in solution quality. This suggests all the domains are \"easy\" for the baselines. How might the method do in harder domains? The choice of domains needs to be improved in order to answer these questions.\n    - The proposed method is an algorithmic framework, with many hyperparameters and choices. Appendix J demonstrates the potential impact of a single poorly chosen hyper-parameter. In my opinion, the paper needs a much more careful empirical investigation with key insights discussed in the main paper.\n    - Reporting results in terms of node expansions is not wrong but does mask the overhead of using the control knowledge during search. Does the proposed algorithm actually run faster than the simpler baselines (LevinTS, PHS*)? Please discuss and / or report time-based results. If solution quality was better, this would be less of a concern.\n    - [1] Combining Online and Offline Knowledge in UCT (Silver 2007)\n    - [2] HC-Search: Learning Heuristics and Cost Functions for Structured Prediction (Doppa 2013)\n    - [3] Guided search for task and motion plans using learned heuristics (Chitnis 2016)\n    - [4] Learning Simulation Control in General Game-Playing Agents (Finnsson 2010)\n\n  - The related work section could be significantly improved. For example, the kSubS paper contains a more complete discussion of related work. Specifically, the discussion on goal-conditioned RL could be improved with a discussion of hierarchical RL methods (e.g., MAXQ [1], ALISP, options, etc.) and state abstraction [1,2] in particular, given the Louvain algorithm and the k-step training mechanism.\n      - [1] Dietterich 1999: https://proceedings.neurips.cc/paper/1999/hash/e5a4d6bf330f23a8707bb0d6001dfbe8-Abstract.html\n      - [2] Andre 2002 ; https://cdn.aaai.org/AAAI/2002/AAAI02-019.pdf\n\n  - Overall, due to the lack of improvement in solution quality and limited empirical evaluation, I'm not sure if the paper represents an actual algorithmic improvement over existing methods. While an interesting combination of existing ideas, the overall novelty seems low. As a result, I'm inclined to reject. That said, I do like the overall approach and don't see any major technical issues with the paper, so I'm happy to revise my score upwards based on author feedback.", "other_comments_or_suggestions": "- None at this time.", "questions_for_authors": "- (Q1) Based on Table 1, it seems nearly all baselines and proposed methods solve all test problem instances. Might this suggest that the selected domains are too \"easy\"? What might be more challenging domains and how might the results change on these domains?\n\n- (Q2) Is LevinTS($\\pi^{SG}$) actually faster than LevinTS in wall-clock time? Please provide details about actual runtime at test time for all the methods considered. I'm looking to better understand how much search speedup is achieved by using the VQVAE and hierarchical policy.", "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": "", "extra_scores": {}}, {"review_id": "YZIMFjRVI0", "reviewer": "Reviewer_nFhe", "summary": "The authors propose a new way to generate policies for deterministic tree search algorithms. Their method to do so is by learning to generate sub-goals using a VQVAE where the subgoals are recognized , learning to reach these subgoals with a low level policy and a high level policy over subgoals.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "Thanks for your helpful comments and feedback.\n\n**Question 1.**\n\nThe environment domains chosen are common amongst related works. In terms of complexity, Sokoban is PSPACE-complete [1], CraftWorld and Box-World are NP-hard [2]. BoulderDash requires collecting multiple diamonds before reaching the exit, which is equivalent to the NP-Hard Hamiltonian path problem between the diamonds and the exit of the puzzle. The domains have important differences that make them a good benchmark for search algorithms. Both Sokoban and Box-World have deadlocks (pushing a box into a corner for Sokoban and using a key on the wrong box for Box-World). BoulderDash has a unique property with its dirt elements, where the agent when moving over a dirt tile removes it. This can greatly increase the size of the state-space, and the agent needs to learn that dirt elements can be ignored.\n\nWe ran additional experiments on a much larger version of BoulderDash. As before, we use the bootstrap process to train through search WA*, PHS*($\\pi$), and our method PHS*($\\pi^{SG}$) over 10,000 problems where an initial budget of 4000 is used. The neural networks used for the policy/heuristics in WA* and PHS*($\\pi$) have ~2.5M parameters, whereas the total number of parameters for all policies/subgoal generators in PHS*($\\pi^{SG}$) is ~10M. We also tried increasing the network size used in PHS*($\\pi$) (denoted LARGE) to match the number of parameters used in PHS*($\\pi^{SG}$) to show that simply using more parameters does not help.\n\nOur results are summarized in the tables below. Our proposed approach, PHS*($\\pi^{SG}$), learned how to solve the difficult set of BoulderDash within 6.25 hours. WA*,PHS*($\\pi$), and PHS*($\\pi$) LARGE did not learn to solve the problems even when granted 4x more expansions and 2x more time. Increasing the size of the neural network of PHS*($\\pi$) does not help either.\n\n|Algorithm | Total Loss (Expansions) | Total Time (Hours) | Training Instances Solved | Nodes Generated per Second |\n|---|---:|---:|---:|--:|\n| WA* | 606,000,000 | 15.58 | 16 |1,872.31 |\n| LevinTS($\\pi$) | 636,718,638 | 16.69 | 16 | 1,828.51 |\n| PHS*($\\pi$) | 599,849,865 | 15.61 | 16 | 1,765.00 |\n| PHS*($\\pi$) LARGE | 344,512,985 | 33.04 | 1 | 496.45 |\n| PHS*($\\pi^{SG}$) [Ours] | 85,470,564 | 6.25 | 10,000 | 791.69 |\n\nWe then tested the resulting models on a separate test set of 100 problems to match the procedure done for Table 1. A maximum budget of 512,000 was given for each problem instance. PHS*($\\pi^{SG}$) can solve all 100 problems with a bit more than 1000 expansions. The baselines can solve a small fraction of the 100 problems even when granted 100x more expansions.\n\n| Algorithm | Solved | Expansions |\n| --- | --: | --: |\n| WA* | 14 | 272,872.28 |\n| LevinTS($\\pi$) | 14 | 280,407.36 | \n| PHS*($\\pi$) | 14 | 288,045.64 |\n| PHS*($\\pi$) LARGE | 4 | 110,805.75 |\n| PHS*($\\pi^{SG}$) [Ours] | 100 | 1,291.37 |\n\n**Question 3.**\n\nWe are happy to give more details in the paper, but as part of our implementation details we do not use the fully grounded reconstructed observation from the VQVAE decoder. This results in it being difficult to gaininsights to potential semantic meaning of the subgoals produced. HIPS [3] which uses the fully reconstructed observations as their subgoal targets do provide visualizations of the subgoals generated. We do think that this would be an interesting research direction, to see if any semantic meaning can be learned and/or used in downstream tasks.\n\n[1] Culberson, J. Sokoban is PSPACE-complete. IEICE Technical Report, 1997\n\n[2] Viglietta, Giovanni. \"Gaming is a hard job, but someone has to do it!.\" Theory of Computing Systems 54 (2014): 595-621.\n\n[3] Kujanpää, Kalle, Joni Pajarinen, and Alexander Ilin. \"Hierarchical imitation learning with vector quantized models.\" International Conference on Machine Learning. PMLR, 2023.", "claims_and_evidence": "The experimental results are over 4 domains and looks promising. But the domains looks very similar, and not very large. I wonder how challenging they are, and if the proposed approach is scalable to harder domains and problems.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "No theoretical claims in the paper.", "experimental_designs_or_analyses": "The experimental results in Figure 2 looks sound as far as I can tell.", "relation_to_broader_scientific_literature": "The paper seems to consider related scientific literature appropriately.", "essential_references_not_discussed": "None that I know of.", "other_strengths_and_weaknesses": "The motivation is good and I think deterministic tree search problems are very common in real world. \n\nThe improvements over previous works are substantial and novel.\n\nThe paper is a bit complicated and hard to follow with many parts, some text simplication or simpler diagrams of specific components like the Louvain algorithm or the search part would have helped with understanding). \n\nEven though the overall algorithm seems pretty complex, the experiments are done on problems that look pretty small and easy so either an explanation on how hard these problems are, or tackling problems that look harder, would have been a great help to assess the quality of the work.", "other_comments_or_suggestions": "Perhaps you can consider optimization problems as another test-bed (for example TSP and extensions). There are numerous benchmarks there and it should be easy to see if the proposed approach is \"competitive\".", "questions_for_authors": "1. How complex are the domains you've experimented on? \n\n2. How well will the method work on much bigger problems?\n\n3. Does the learned sub-tasks in the experiments reach some semantic meaning?", "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": "", "extra_scores": {}}, {"review_id": "fvz0VUsHdc", "reviewer": "Reviewer_ocyY", "summary": "The paper proposes a new approach for utilizing policy tree search by the inclusion of learned sub-goals. The subgoals are learned online as the tree search expands during a Bootstrap process while attempting to solve problems. One key innovation is the utilization of failed solution trees as data as well (similar to many modern RL algorithms like HER) but by expertly partioning the graph by exploiting the Louvain algorithm. The policy search is hierarchical with the subgoal policy guided by a weighted sample of the high-level subgoal and the low-level subgoal policy. This forms the evaluation function for policy tree search. The subgoal generator uses the VQVAE ( (Vector Quantized Variational Autoencoder). One key distinction is that the search still operates using the problems operator set while the low-level policy guides the search to read the subgoals. Thus, sub-goal representations that do not map to any high-level state are less susceptible to cause problems. \n\nThe authors then perform an empirical analysis on 4 domains using the new evaluation function and perform an ablation that showcases the strengths of exploiting failed attempts.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "Thank you for your helpful comments and feedback.\n\n\n**Weakness 1**\n\n\nWe understand the reviewer's concern with running time as some of the gains we have in terms of expansions disappear when solving easier problems. To address this, we ran experiments on a much more difficult version of BoulderDash to highlight the difference in inference speed is not an issue when the problems are too difficult for the baselines. We also increased the network size used in PHS*($\\pi$) (denoted LARGE) to match the number of parameters used in PHS*($\\pi^{SG}$) to show that simply using more parameters does not help.\n\n\nOur results are summarized in the tables below. Our proposed approach, PHS*($\\pi^{SG}$), learned how to solve the difficult set of BoulderDash within 6.25 hours. WA*,PHS*($\\pi$), and PHS*($\\pi$) LARGE did not learn to solve the problems even when granted 4x more expansions and 2x more time. Increasing the size of the neural network of PHS*($\\pi$) does not help either.\n\n\n|Algorithm | Total Loss (Expansions) | Total Time (Hours) | Training Instances Solved | Nodes Generated per Second |\n|---|---:|---:|---:|--:|\n| WA* | 606,000,000 | 15.58 | 16 |1,872.31 |\n| LevinTS($\\pi$) | 636,718,638 | 16.69 | 16 | 1,828.51 |\n| PHS*($\\pi$) | 599,849,865 | 15.61 | 16 | 1,765.00 |\n| PHS*($\\pi$) LARGE | 344,512,985 | 33.04 | 1 | 496.45 |\n| PHS*($\\pi^{SG}$) [Ours] | 85,470,564 | 6.25 | 10,000 | 791.69 |\n\n\nWe then tested the resulting models on a separate test set of 100 problems to match the procedure done for Table 1. A maximum budget of 512,000 was given for each problem instance. PHS*($\\pi^{SG}$) can solve all 100 problems with a bit more than 1000 expansions. The baselines can solve a small fraction of the 100 problems even when granted 100x more expansions.\n\n| Algorithm | Solved | Expansions |\n| --- | --: | --: |\n| WA* | 14 | 272,872.28 |\n| LevinTS($\\pi$) | 14 | 280,407.36 | \n| PHS*($\\pi$) | 14 | 288,045.64 |\n| PHS*($\\pi$) LARGE | 4 | 110,805.75 |\n| PHS*($\\pi^{SG}$) [Ours] | 100 | 1,291.37 |\n\nWhile we can provide the runtime cost of HIPS-e, it would still not be meaningful. We used the open source HIPS-e implementation from the authors, which is implemented in Python. Our experiments and all other baselines are implemented in C++. If we were to compare running time, we would show our approach being substantially faster than HIPS-e, but due to the mismatch in programming languages, this comparison is not meaningful. Note that our comparison to HIPS-e is still meaningful in the sense that while our approach can learn to solve instances of BoulderDash, HIPS-e fails to do so.\n\nIn summary, while our proposed approach might not be faster on easier problems, due to the cost of querying more expensive neural models, it can allow us to solve problems we would not be able to solve with the baseline systems considered in our experiments. \n\n\n**Weakness 2**\n\nThis is a great point and we are happy we have the chance to address it in our rebuttal. To avoid confusion with the argument that will follow, let us start by saying that our Sokoban results are by no means weak. The method was able to learn how to solve all training instances and performed best in terms of expansions on the test instances. We just did not see the clear advantage in our favor that we see in the other domains. We conjecture that the reason our method performs worse in Sokoban in comparison to the other three problems is due to the training data the clustering algorithm generates. While clustering finds important structures in the other three problems, it did not find helpful structures in Sokoban. For example, in BoulderDash, once the agent unlocks a door, it opens a region of the state space that was not available before. This is the type of structure the clustering algorithm might be capturing. With that, the structure of the underlying state space could be offering subgoals that are helpful in solving these problems. Sokoban might not have such a helpful underlying structure. Note that it is not trivial to verify our conjecture because we do not attempt to reconstruct the subgoals; we use them to condition the policies.\n\nWe see the Sokoban results as a demonstration that our approach is robust. Even if the clustering algorithm does not find helpful structures in the state space, we are still able to learn how to solve the problems.\n\nTo illustrate that our approach can undo reached subgoals when needed, we collected statistics of when we need to remove boxes from the goal in Sokoban. For the solution paths our method finds, we tracked the statistics of how often a box was pushed onto a goal, then undone (for example, to shuffle around for another box to get through). The table below shows the results. The table shows that in 66% (37+17+9+4) of the problems solved our system had to move at least one box from a goal location. \n\n| Number of times a solved box was undone | Percentage of paths found |\n| --- | ---: |\n| 0 | 33% |\n| 1 | 37% |\n| 2 | 17% | \n| 3 | 9% |\n| 4 | 4%|", "claims_and_evidence": "The claims are supported by convincing evidence. Their empirical evaluation showcases that their approach can reduce the computational effort in problems on several domains compared to SOTA baselines.", "methods_and_evaluation_criteria": "Using subgoals to guide search in sparse, binary reward type problems has been a well-known and well-researched topic. The application to policy search in an online fashion and in the hierarchical setting is reasonable.", "theoretical_claims": "The theoretical claims that their method enjoys the same guarantees that PHS* provides (Sec 3.5) seems okay to me.", "experimental_designs_or_analyses": "The choice of domains is good, baselines are suitable and evaluation metrics are reasonable for the most part although some additional evaluation metrics could be added.", "relation_to_broader_scientific_literature": "This work advances the state-of-art in policy guided search algorithms by introducing a method of learning and utilizing learned subgoals online while also exploiting failed attempts.", "essential_references_not_discussed": "Not applicable", "other_strengths_and_weaknesses": "1. I think one weakness is the lack of other evaluation metrics like time in seconds on the x-axis. It is quite important to add data with such results especially due to the added computational effort from learning the subgoals is involved.\n\nThis also solves the problem of \"incomparable\" comparisons with HIPS-e since if the node expansions are not directly comparable certainly time is.\n\n2. Another issue is that the analysis of failures is a bit lacking. I would have rather preferred some more detailed analysis on why sokoban seems to perform worse using this approach. Subgoals needing to be undone is pretty common among many problems (eg. Sussmans anomaly) so if your approach cannot be expected to work here then I would question its overall utility. Please expand on why your approach is outperformed by the vanilla methods on Sokoban. It might also make sense to run a quick experiment on Blocksworld (the domain in sussmans anomaly) and analyse whether similar observations can be made.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "Overall I have a very positive view of this paper. My negative score is due to the lack of clarity regarding W2. I hope the authors can appropriately resolve my questions in weaknesses before I can revise my score.", "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": "", "extra_scores": {}}, {"review_id": "eTkLODxRDC", "reviewer": "Reviewer_yx2F", "summary": "The paper proposes a new approach to training policies for search. The authors leverage subgoal guidance and this way they show how to get the training signal even from unsolved episodes. By experiments in 4 environments, they show that the proposed approach improves sample efficiency of the training procedure.\n\n## Update after rebuttal\n\nThank you for the answer. Although I'm still on the fence about this paper, I will raise my rating to 3. That said, I still encourage the authors to make the proposed adjustments to strengthen the paper.\n\n> Indeed, if the problems are on the easier end, then our method will not offer gains in terms of running time. [...] These results will be added to the paper.\n\nI cannot give credit for results that are not shown. If that is indeed the case, then please include evaluations on harder instances in the paper. Otherwise, the paper will have limited impact, even if published. The results show currently are somewhat misleading as they rely only on the expansions metric that is not equally handled by methods; taking into account other metrics, such as running time currently makes the advantage rather small.\n\n> Why We Prefer to Not Use the Trick of Filtering Out Actions\n\nNo, I am proposing a very simple baseline: fix k=2, $\\varepsilon=0$, i=0, and j=$\\infty$. To be honest, I expect that running such an experiment would take less time than writing the justification for not running it. All you have to do is to add `action_probs = action_probs * (action_probs >= torch.topk(action_probs, k).values.min())` after `action_probs = pi(s)` in the implementation of the baseline.\n\n> is orthogonal to our subgoal-based policies\n\nYes, I agree. However, this is not exactly about improving speed. The point is to understand why your approach is beneficial. One advantage is that using the high-level policy for additional weighting makes the policy more focused on actions that matter. The question is whether this is the main benefit? If you show that naively focusing the search on top actions is still inferior to your approach, it would significantly strengthen your results.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "Thank you for your helpful comments and feedback.\n\n**Concern 1**\n\nEach node generation for LevinTS/PHS requires a single policy call (plus heuristic for PHS). Each node generation for our approach requires K VQ-VAE calls to generate the K subgoal observations, K policy calls for the low-level policy (over each of the K generated subgoal target observations), and a single policy call for the high-level policy mixture. We make the K calls faster by batching them. Due to batching, the slowdown is not linear with the size of K, (see **Concern 3**).\n\nConsider the results of the following experiment on a much more difficult version of BoulderDash, following the same procedure from **Section 4.3**. We also increased the network size used in PHS*($\\pi$) (denoted LARGE) to match the number of parameters used in PHS*($\\pi^{SG}$) to show that simply using more parameters does not help.\n\nPHS*($\\pi^{SG}$) learned how to solve the difficult set of BoulderDash within 6.25 hours. The baselines did not learn to solve the problems even when granted 4x more expansions and 2x more time. We also report the number of nodes generated per second of each model. We only have a factor of 2 slowdown while using 4 times more parameters and K subgoals.\n\n|Algorithm | Total Loss (Expansions) | Total Time (Hours) | Training Instances Solved | Nodes Generated per Second |\n|---|---:|---:|---:|--:|\n| WA* | 606,000,000 | 15.58 | 16 |1,872.31 |\n| LevinTS($\\pi$) | 636,718,638 | 16.69 | 16 | 1,828.51 |\n| PHS*($\\pi$) | 599,849,865 | 15.61 | 16 | 1,765.00 |\n| PHS*($\\pi$) LARGE | 344,512,985 | 33.04 | 1 | 496.45 |\n| PHS*($\\pi^{SG}$) [Ours] | 85,470,564 | 6.25 | 10,000 | 791.69 |\n\nWe then tested the resulting models on a separate test set of 100 problems to match the procedure done for Table 1. \n\n| Algorithm | Solved | Expansions |\n| --- | --: | --: |\n| WA* | 14 | 272,872.28 |\n| LevinTS($\\pi$) | 14 | 280,407.36 | \n| PHS*($\\pi$) | 14 | 288,045.64 |\n| PHS*($\\pi$) LARGE | 4 | 110,805.75 |\n| PHS*($\\pi^{SG}$) [Ours] | 100 | 1,291.37 |\n\n**Concern 2**\n\nYes, we equip the learning agent with the ability of learning from experiences that previous methods could not use for learning. We update our method more often because we learn how to reach the subgoals the clustering algorithm generates. The baselines cannot learn from such experience because they do not learn and exploit subgoals. \n\n**Concern 3**\n\nWe make a single call of batch size K for a faster query. The time information was indeed missing in our ablation, which we include below. Due to batching, the number of generations per second does not decrease linearly with the number of subgoals. \n\n| Codebook Size (Number of Subgoals) | Nodes Generated per Second |\n| --- | ---: |\n| 1 | 266.85 |\n| 4 | 261.74 |\n| 16 | 208.44 | \n\n**Concern 4**\n\nA key difference between our approach and the baselines is that we can learn from problems we have yet to solve. As an example from BoulderDash, if many diamonds are required to solve a problem, it may be difficult to find a solution, but sampled paths may contain the agent collecting a single diamond. The low-level policy learns to collect diamonds even before the method can solve any problems (see Figure 3 of the paper). \n\nWhile we find the suggestion of performing roll-outs to simulate subgoal guidance interesting, we don’t see how it would be competitive with our method. Our method learns helpful subgoals because it uses the information contained in the CLOSED list of the search, which stores the entire search tree. The roll-out approach contains a single path. While the CLOSED list contains helpful information such as how to collect a key and open a door, it is unlikely a roll-out will capture this type of information. \n\n**Concern 5**\n\nWe could apply the suggestion of using the top-k (e.g., k = 2) actions during search with the baselines in two moments: (1) during training and (2) during testing. \n- **Training**: Once the neural model is randomly initialized, the policy is nearly uniform. So choosing the top-k would be an arbitrary choice, as we would choose the two actions that happen to have a slightly higher probability at initialization.\n- **Testing**: Once these models manage to solve all training instances, their policies almost deterministically choose their actions. So choosing k > 1 would increase the number of expansions because we would be forcing the algorithm to explore when it can almost deterministically solve the problem. \n\n**Concern 6**\n\nWe did not tune hyperparameters specifically for each domain for our method. For any \nhyperparameter specific to HIPS-e, we used their listed ones. For WA*, we followed LevinTS and PHS* which used a weight of 1.5. WA* tends to be quite robust to the weight value as it learns its heuristic function.", "claims_and_evidence": "The main claim of the paper is that the proposed training pipeline improves sample efficiency of the training. More spcifically -- less node expansions are required until the search algorithm can solve all instances. I am mostly convinced with that. However, a few concerns remain:\n\n1. A single expansion of LevinTS/PHS requires one policy call and 0-k heuristic calls. On the other hand, a single expansion of your approaches require k VQ-VAE calls, 2k policy calls, and 0-k heuristic calls. This is a considerable difference, especially given that the VQ-VAE model likely has considerably more parameters than policies. Please discuss the difference in expansion cost and make it explicit in the paper. What is the magnitude of that difference in practice?\n\n2. Given that your method requires training 3 policy-like models instead of a single one for baselines, is it not the case that it trains faster simply because in practice it receives more training updates? Please discuss that.\n\n3. The cost of expansion is highly dependent on the number of generated subgoals. However, I found no specification of such hyperparameters (except few in appendices J,K). It makes a huge difference whether you use 4 or 40 subgoals. Please discuss that.\n\n4. While I understand the proposed method, I am missing an intuition why it works. The key step lies in extracting the training signal from non-solution data. The pipeline you proposed uses those to train subgoal generator and low-level policy. This data is sufficient to train a goal-reaching low-level policy. The subgoals learned this way are not targetted toward the solution, hence the generator learns to output _any_ valid subgoals. While it makes sense that it should considerably improve the sample efficiency of the subgoal search, I don't see immediate reasons for why we should expect it to outperform plain low-level search. As far as I understand, the main role of subgoals in your pipeline is that they provide additional lookahead-driven weighting for actions. What would happen if you would augment baselines by \"simulating\" this subgoal guidance (e.g. during expansion, for each action make a single few-step policy rollout, treat the final state as a subgoal and the product of policy predictions on the path as subgoal probabilities)? Would it be sufficient to close the gap between methods?\n\n5. There is also another difference: subgoals can be seen as a way to select more promising action from the full set. How would the performance of low-level methods change if you limited the number of actions used for each expansion to only top 2 according to the policy (or use weighting [0.45, 0.45, 0.05, 0.05] if you wish to preserve completeness)?\n\n6. Were the key hyperparameters of each method tuned separately for each domain? From my experience, the weight of 1.5 for A* seems quite high, did you check other values as well?\n\nI'm happy to accept the paper if my concerns are addressed.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "There are no theoretical claims that need to be checked.", "experimental_designs_or_analyses": "Yes, I checked all experiments in the main text.", "relation_to_broader_scientific_literature": "The proposed approach is mostly a combination of existing tools (LevinTS/PHS search, HIPS-inspired subgoal model, Louvain algorithm for subgoal discovery), but the proposed combination and additional training details are novel to my best knowledge.", "essential_references_not_discussed": "I'm not aware of any essential references that have to be added.", "other_strengths_and_weaknesses": "While the proposed pipeline mostly rely on existing parts, the proposed combination is novel and as such can be a good contribution.", "other_comments_or_suggestions": "- The running title is missing.\n- typos: (90L \"subgoals\"), (74R \"represent\"), (238L \"a hierarchy\"), (251R \"using\")\n- Figure 1.c.ii: there is a problem with indexing, all sequences have the same indices.\n- Why using the Louvain algorithm is helpful? Is it much better than sampling subgoal pairs from unsolved trajectories in the same way as from solved trajectories?", "questions_for_authors": "Please answer my questions from the Claims and Evidence section.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper proposes a subgoal-guided policy tree search with learned subgoals. Unlike previous approaches where subgoals are learned from trajectories, the proposed method learns subgoals online using a VQVAE based on the search tree. Experiments show that the proposed method improves sample efficiency in online settings.

The paper provides a new perspective on incorporating subgoal planning, which is an important topic. The experimental results support the claims and are promising. All reviewers agree it is a good paper. Overall, I recommend acceptance.
Decision: Accept (poster)