Hybrid Search for Efficient Planning with Completeness Guarantees
Authors: Kalle Kujanpää
Joni Pajarinen
Alexander Ilin
Venue: NeurIPS 2023 poster (2023)
Keywords: Planning
Subgoal search
Reinforcement learning
Hierarchical Imitation Learning
Hierarchical planning
Hierarchical reinforcement learning
TL;DR: We propose and analyze hybrid search, an extension of subgoal search with completeness guarantees and improved performance

Abstract: Solving complex planning problems has been a long-standing challenge in computer science. Learning-based subgoal search methods have shown promise in tackling these problems, but they often suffer from a lack of completeness guarantees, meaning that they may fail to find a solution even if one exists. In this paper, we propose an efficient approach to augment a subgoal search method to achieve completeness in discrete action spaces. Specifically, we augment the high-level search with low-level actions to execute a multi-level (hybrid) search, which we call complete subgoal search. This solution achieves the best of both worlds: the practical efficiency of high-level search and the completeness of low-level search. We apply the proposed search method to a recently proposed subgoal search algorithm and evaluate the algorithm trained on offline data on complex planning problems. We demonstrate that our complete subgoal search not only guarantees completeness but can even improve performance in terms of search expansions for instances that the high-level could solve without low-level augmentations. Our approach makes it possible to apply subgoal-level planning for systems where completeness is a critical requirement.

Hybrid Search for Efficient Planning with Completeness Guarantees
Kalle Kujanpää!3, Joni Pajarinen* Alexander Ilin
'Department of Computer Science, Aalto University
Department of Electrical Engincering and Automation, Aalto University Finnishh Center for Artificial Intelligence FCAI *System 2 AI
(kalle. kujanpaa, joni pojaiinan,,,,n alexander il ilin>Baalto.Fs
Abstract
Solving complex planning problems has been long-standing challenge in com- puter science. Learning-based subgoal search methods have shown promise in tackling these problems, but they often suffer from lack completeness guaran- tees, meaning that they may fail to find a solution even if one exists. In this paper, we propose an efficient approach to augment subgoal search method to achieve completeness in discrete action spaces. Specifically, we augment the high-level search with low-level actions execute a multi-level (hybrid) search, which we call complete subgoal search. This solution achieves the best of both worlds: the practical efficiency of high-level search and the completeness low-level search. We apply the proposed search method to recently proposed subgoal search al- gorithm and evaluate the algorithm trained on offline data on complex planning problems. We demonstrate that our complete subgoal search not only guarantees completeness but can even improve performance in terms of search expansions for instances that the high-level could solve without low-level augmentations. Our approach makes possible to apply subgoal-leve planning for systems where completeness is critical requirement.
Introduction
Combining planning with deep learning has led to significant advances in many fields, such as automated theorem proving [33], classical board games [39], puzzles [1], Atari games [38], video compression [24], robotics (5), and autonomous driving [43]. However, deep learning-based methods often plan in terms of low-level actions, such individual moves in chess commands in Atari games, whereas humans tend to plan by decomposing problems into smaller subproblems [11]. This observation has inspired lot of recent research into methods that solve complex tasks by performing hicrarchical planning and search. In the continuous setting, hierarchical planning has been applied to, for instance, robotic manipulation and navigation [31, 25, 12, 15]. Discrete hierarchical planning methods, when trained entirely on offline data, can solve complex problems with high combinatorial complexity. These methods are efficient at long-term planning thanks the hierarchy reducing the effective planning horizon [4, 18, 45]. Furthermore, they reduce the impact of noise on planning [4] and show promising generalization ability diverse multi-task offline data has been shown scale and generalize broadly to new tasks, and being compatible with training without any environment interaction can seen an additional strength of these methods [20, 5, 42).
df-distribttionn tasks [45]. Training RL agents on
Corresponding author
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

(a) low-level search
(b) high-level search
(c) high-level search
(d) complete search
(a): Low-level search systematically visits all states reachable from the root node and, therefore, is guaranteed to find path to the terminal state (shown in red). (b): High-level search can find solution with much fewer steps due to its ability to operate with high-level actions that span several time steps. (c): High-level search may fail to find a solution due to an imperfect subgoal generation model. (d): Complete subgoal search can find a solution with few steps thanks to high-leve actions, and it has completeness guarantees due to also considering low-level actions.
Figure 1:
Despite their excellent performance, the discrete subgoal search methods share weakness: neither AdaSubS [45], kSubS [4], nor HIPS [18] are guaranteed to find a solution even if it exists. All these methods rely on a learned subgoal generator that proposes new subgoals be used with some classical search algorithms for planning. If the generator fails to perform adequately, the result can be a failure to discover solutions to solvable problems. We call this property the lack of completeness. The guarantee of the algorithm finding solution is critical for both theoretical science and practical algorithms. In the context of subgoal search, completeness guarantees discovering the solution, even if the generative model is imperfect. Completeness allows extensions and new incremental algorithms that require building on top of exact solutions. One example of that could be curriculum learning. Furthermore, we show that completeness significantly improves the of-distribution generalization of subgoal search. Achieving completeness also makes applying high-level search as an alternative to low-level search possible in safety-critical real-world systems. Zawalski et al. [45] mentioned that AdaSubS can be made complete by adding an exhaustive one-step subgoal generator that only utilized when the search would otherwise fail, whereas Kujanpää et al. [18] proposed combining high- and low-level actions to attain completeness of HIPS. However, to the best of our knowledge, this idea has not been formalized, analyzed, or evaluated in prior work.
We present a multi-level (hybrid) search method, complete subgoal search, that combines hierarchical planning and classical exhaustive low-level search. The idea is illustrated in Figure 1. We apply our complete search approach to HIPS [18] which 1) has been shown to outperform several other subgoal search algorithms in challenging discrete problem domains, 2) does not require training multiple subgoal generators in parallel to perform adaptive-length planning, and 3) particularly suited for being combined with low-level actions due to using Policy-guided Heuristic Search (PHS) as the main search algorithm [18, 27]. We use the name HIPS-c for the proposed enhancement of HIPS with complete subgoal search. We argue that the idea suggested in [45] can be seen as a specific case of our search method that works well in some environments but can be improved upon in others. We evaluate HIPS-S challenging, long-term discrete reasoning problems and show that it outperforms HIPS, other subgoal search methods, and strong offline reinforcement learning (RL) baselines. Not only does HIPS-E attain completeness, but complete subgoal search also demonstrates improved performance on problem instances that subgoal search alone was sufficient for solving.
2 Related Work
We propose augment the high-level search used in learning-based hierarchical planning with low-level actions to achieve completeness while even improving the search performance in terms of node expansions. First, we discuss our work in the general context of hierarchical planning and then focus on the closest methods in discrete subgoal search, to which we compare the proposed approach.
Continuous Hierarchical Planning Hierarchical planning has been widely applied in the contin- uous setting. The Cross-Entropp Method (CEM) [34] is often used as the planning algorithm for different hierarchical planning methods [22, 25, 12, 32). However, the cross-entropy method is numerical optimization method, unsuitable for addressing discrete planning problems. There is also prior work on hierarchical planning for continuous and visual tasks, including control and navigation,

---

where CEM is not used as the optimization algorithm [21, 26, 6, 31, 36, 46]. Kim et al. [14] plan how to select landmarks and use them to train a high-level policy for generating subgoals. Planning with search is common approach in classical Al research [35]. Combining search with hierarchical planning has been proposed [23, 8], but these approaches are generally inapplicable to complex, discrete reasoning domains, where precise subgoal generation and planning are necessary [45].
Recursive Babbool-Baseed Planning In this work, we focus on search algorithms where subgoals are generated sequentially from the previous subgoal. Recursive subgoal generation is an orthogonal alternative to our approach. In certain domains, given start and a goal state, it is possible to hierarchically partition the tasks into simpler ones, for instance, by generating subgoals that are approximately halfway between the start and the end state. This idea can be applied repeatedly for an efficient planning algorithm [30, 31, 13). However, the recursive approach can be difficult to combine with search and limits the class of problems that can be solved.
Discrete Subgoal Search Discrete subgoal search methods can solve complex reasoning problems efficiently with limited search node expansions. S-MCTS [7] is method for MCTS- subgoal search with predefined subgoal generators and heuristics, which significantly limits its usability to novel problems. Allen et al. [2] improve the efficiency of search through temporal abstraction by learning macro-actions, which are sequences of low-level actions. Methods that learn subgoal generators, on the other hand, generally suffer from lack of completeness guarantees. kSubS [4] learns subgoal generator and performs planning in the subgoal space to solve demanding reasoning tasks. AdaSubS [45] builds on top of kSubS and proposes learning multiple subgoal generators for different distances and performing adaptive planning. HIPS [18] learns to segment trajectories using RL and trains one generator that can propose multiple-length subgoals for adaptive planning.
3 Method
We present HIPS-a, an extension of Hierarchical Imitation Planning with Search (HIPS), a search- based hierarchical imitation learning algorithm for solving difficult condiiondt reasoning problems [18]. We use the Markov decision process (MDP) formalism, and the agent's 's objective is to enter terminal state in the MDP. However, we deviate from the reward maximization objective. Instead, the objective is to minimize the total search loss, that is, the number of search nodes expanded before solution is found. A similar objective has been adopted in prior work on subgoal search and, in practice, the solutions found are efficient (4, 45].
We assume the MDPs to be deterministic and fully observable with discrete state space S and action space A. We also assume the standard offline setting: the agent cannot interact with the environment during training, and it learns to solve tasks only from D, an existing dataset of expert demonstrations. These trajectories may be heavily suboptimal, but all lead to a goal state. Therefore, the agent should be capable of performing stitching to discover the solutions efficiently [40].
3.1 Preliminaries
HIPS learns to segment trajectories into subgoals using RL and nubgoal-conditionel low-level policy : [[a]s, [s, sy). The segmented trajectories are used to train a generative model p(sgls) over subgoals 8, that is implemented as a VQVAE with discrete latent codes [41], strategy inspired by Ozair et al. [29]. The VQVAE learns a state-conditioned prior distribution p(els) over latent codes e from a codebook IE and a decoder (8yyle, s) acting as a generator that outputs a subgoal Sg given the latent code e and state s deterministically as sy = g(e, s). Each code E E E can be considered a state-dependent high-level action that induces a sequence of low-level actions As(s) (at..... any). a, E A, that takes the environment from state s to Sg. The low-level action sequence is generated deterministically by the subgoal-conee conditoooo policy x(a|s, sy)) when the most likely action is used at each step. The prior p(c 8) can be interpreted as a high-level policy (e)(E that assigns a probability to each latent code. HIPS also learns a heuristic that predicts the number of low-level actions a E A needed to reach a terminal state from s and a single-step dynamics model fayn ($14 la,, 8,). The heuristic is denoted by Vss) in [18], but we denote it by h in this paper.
HIPS performs high-level planning in the subgoal space with PHS [27], although other search methods can be used well. PHS is variant of best-first search in which the algorithm maintains
3

---

priority queue and always expands the node with the lowest evaluation function value. There a non-negative loss function L, and when the search expands node n, it incurs loss L(n). The objective of PHS is to minimize the total search loss. The evaluation function of PHS is
(nn) = (n) g()) x(n)'
(I)
where (T(1)) 2. 1 is heuristic factor that depends on the heuristic function lt(r). g(n) is the path loss, the sum of the losses from the root no to n. T()) S 1 the probability of node n that is defined recursively: TTn²)) = (n))))((n) (mo) = 1, is the parent of n' and E drsc..no), that is, is a descendant of the root node ngg- When HTPS plans, each search node n corresponds to a state s, g(n) to the number of low-level steps needed to reach from the root no. and h(n) to the output of the value function Vs)). The children ((n) of node n are the valid subgoals generated by the VQVAE decoder g s) for all eg E E. The search policy π (nx) is induced by the conditional policy a (n') [n), which is represented by the state-conditioned prior p(cls).
3.2 Complete Subgoal Search
HIPS performs search solely in the space of subgoals proposed by the trained generator network. which may cause failures to discover solutions to solvable problems due to possible imperfections of the subgoal generation model (see Fig. lc). This problem augmenting the search with low-level actions (see Fig. ld). In this work, we apply this idea to HIPS to guarantee solution discovery when the solution exists while still utilizing the subgoal generator for temporally abstracted efficient search.
be tackled in discrete-action MDPs by
Formally, we propose modifying the search procedure of HIPS such that in addition to the subgoals {sy = g(e, s), Ve E }} produced by the HIPS generator, the search also considers states {sl = T(s, a). Va E A} that result from the agent taking every low-level action E A in state s, where T(s, a) is the environment transition function. We assume that T' is known but we also evaluate the method with Iearned T. The augmented action space is then A+ AUE. E. We use PHS as the search algorithm and compute the node probabilities used for the evaluation function (1) as
T (n)
II a (()((1)))))((1))
where sa(n) the state that corresponds to node n at depth d, sa- (n), (n)) so(n) are the states of the ancestor nodes of and TTs (n)))))1(n) is the search policy. We propose compute the probabilities (Ts (8))) in the following way:
=))so((els))-) if sj o(ck: is proposed by HIPS (8518551) & (Bc(als)-1)
if sy T(5 a) proposed by low-level search
where Tsa(eulsj-1) (nc(alsj-1) is low-level policy that train from available expert demonstrations with BC. We use hyperparameter s to balance the probabilities computed with the high and low-level policies: higher values of prioritize more lowelevel exploration. We call this complete search HIPS-s.
p(ex/(/s (1)-)) is the prior over the high-level actions learned by HIPS and
The proposed complete search approach can be combined with any policy-guided search algorithm, but we focus PHS due to its of-te-of-the-at performance. Complete search can also be used with policyless search algorithms, but in that case, E cannot directly control the frequency of low and high-level actions.
Zawalski et al. [45] suggested using low-level actions only when the high-level search would otherwise fail. In the context of PHS, this can be interpreted as having an infinitesimal E such that every high- level action has lower evaluation function value (1) and, therefore, a higher priority than every low-level action. With some abuse of notation, we refer to this approach + 0.
3.3 Complete Subgoal Search Heuristic
The objective of PHS is to minimize the search loss, and Orseau and Lelis [27] propose using heuristic to estimate the g-cost of the least costly solution node n² that is descendant of the current

---

search node n. They propose to approximate the probability x(n") for node n" that contains found solution as
x (n")
(3)
72n)66 to be used in (I). PHS* is the variant of PHS that uses this heuristic factor. The derivation of the heuristic factor in (n) assumes that gnn). the path loss of node n, and h()), the heuristic function approximating the distance to the least-cost descendant goal node n² are expressed in the same scale. This does not hold for the proposed search algorithm. The search objective of HIPS-E is to minimize the number of node expansions, which implies that g(n) is equal to the depth of node n, whereas the heuristic h(n) trained predict the number of low-level actions to the goal. One solution to the number of low-level steps to node n. However, this would distort the search objective. The cost of expanding node corresponding to a subgoal would equal the length of the corresponding low-level action sequence, whereas the loss of low-level actions would be one. However, the cost should be the same for every node, as the objective is to minimize the number of node expansions.
and use this approximation to arrive at heuristic factor im (n) 1+ 1+n(n)/o(n)
let g(n) be equal
Instead, we propose re-scaling the heuristic factor h to be equal to the estimated number of search nodes the path from n. to the goal node n" by dividing the expected number of low-level actions from node n to the terminal node by the average low-level distance between the nodes on the path from To to node n. Let (1z) be equal to d(n). the depth of the node, and let ((n)) be the number of low-level actions from the root node. Then, we define a scaled heuristic h(m) = M(nlg(n) and by
I(n)
using it instead of i(n) in (3), we get a new approximation T(n*) = πt (1++(x0)/(0)) which yields the following heuristic factor and evaluation function:
+ h(n)/(()) (m)))m))((
(n( = gn)) (1 + ((m)((m))
(4)
( +h(m)/(m))))))
For the full derivation, please see Appendix C. Note that fA may not be PHS- PHS-admissible, even if h(n) were admissible. In HIPS, there are no guarantees of the learned heuristic f((1)) being admissible.
3.4 Analysis of HIPS-&
Orseau and Lelis [27] showed that the search loss of PHS has an upper bound:
g(n")
T(n)
L(PHS, n²)= & LP(SS n²) = m((n)) 17 (n")
(5)
n (n))
(EC
where n" is the solution node returned by PHS, (nn) is the path loss from the root to n, x the search policy, and t the modified heuristic factor corresponding to the monotone non-decreasing evaluation function e (n). and C.p (n²) the set of nodes that have been expanded before n², but the children of which have not been expanded. Now, given the recursively defined policy π (n) that depends on TBC and TsG as outlined in Subsection 3.2, the upper bound derived (5) is unchanged.
However, the upper bound of (5) can be seen as uninformative in the context of complete search, as it depends on the high-level policy SSG. In general, we cannot make any assumptions about the behavior of the high-level policy as it depends on the subgoals proposed by the generator network. However, we can derive the following upper bound, where the probability of the terminal node n² is independent of the behavior of the generator, and consequently, the high-level policy TSG:
Corollary (Subgoal-P PHS upper bound without TSG in the denominator). For any non-negutive loss function L, non-empty set of solution nodes Ng C descc (no), low-level policy TBC. high-level policy TsG, E (0, 1), policy x (n' n) as defined in (2), and heuristic factor n(()) 2 1, Subgoul-PHS returns solution node n" E arg eNg +pt(re (n*), ). Then, there exists terminal node ñ E Ng such that (iate(ñ) = state(n"), ),
where â corresponds to low-level trajectory (so, ao...., ........ aN - state(n") )) and
the search loss is bounded by
L(PHS-h,, L(PHS-h, 5
g(n) N-1 T==0 (a,ss) REC, (N)
" (n)
Σ
T(n)
(6)
N
(7(m))
Proof. Subgoal- PHS does not change the underlying search algorithm, so the assumption of Subgoal- PHS returning the minimum score solution node follows from Theorem in [27]. The first inequality
5

---

3
9
13
12
5
7
16
18
14
11
15
10
19
17
20
21
22
23
24
Sokoban
Sliding Tile Puzzle
Box-World
Travelling Salesman
We evaluate our complete search approach, HIPS-E, in Sokoban, Sliding Tile Puzzle (STP), Box-We World (BW), and Travelling Salesman Problem (TSP). Sokoban, the agent must push the yellow boxes onto the red target locations. In the Sliding Tile Puzzle, the agent must slide the tiles sort them from locks with keys of the corresponding color. In Travelling Salesman, the agent (marked with a circle) must visit all unvisited cities (red squares) before returning to the start (black square).
Figure 2:
24. In Box-World, the task collect the gem (marked with $) by opening
follows from the fact that the loss function 7. is always non-negative and the node n will be expanded before any other node n with o (n) 1 (n*). In particular, note that it is possible that n'
The second inequality follows from the Theorem 1 in [27] and (f) = e I TBC (ac(a,)8;) (8)). O
Now, suppose that we have problem where there is only one terminal state and sequence of low- level actions that reaches this terminal state, and the search space is infinite. Let us denote this trajectory as T (Su, ag $1, dl,..... SN-1, (N))).8). Additionally, assume that the high-level policy asa never guides the search towards a solution, that is, for each state s E T, the low-level action sequence for every subgoal 8y proposed by the generator network contains an incorrect action. Furthermore, assume that the generator network can always generate new, reachable subgoals for all states E Hence, only actions selected by the low-level policy lead the solution, and thus (n") = eN - (Bc(oa)s:) bound in (5) approaches infinity.
= 0 or & + 0, the search does not converge, and the upper
Czechowski et al. [4] argue that low-level search suffers more from local noise than subgoal search and using subgoals improves the signal-to-noise ratio of the search, and the results of Kujanpää et al. [18] support this. For complete search, lower & can increase the use of high-level policy relation to the low-level actions, thereby shortening the effective planning horizon and making the search more effective. Hence, we hypothesize that low value of æ is generally preferred. However, (6) shows that the worst-case performance of the search deteriorates when the value of decreases.
there no heuristic, the bound can be simplified similarly as in Orseau and Lelis [27]. This following corollary shows that removing the heuristic factor does not affect the inverse dependence of the worst-case search loss on E, and fact, the worst case of (6), that the search failing for E + 0, is possible even given perfect heuristic function.
Corollary 2. (Subgoal- upper bound without heuristic). If there no heuristic, that is, Vnn (n)) = 1, the upper bound simplifies
g(
L(PHS-h,, & L(PHS-h,
II TBC(a:)84)
Proof. The first inequality follows in Corollary 1, and the second inequality follows from the assumptions and Eneey(o) (nn') S for all n, see Orseau et al. [28].
4
Experiments
The main objective of our experiments is to evaluate whether the proposed complete search algorithm HIPS-g can be combined with an existing subgoal search algorithm, HIPS [18], to improve its performance in environments that require long-term planning and complex, object-based relational reasoning. We also analyze the sensitivity of HIPS- to the hyperparameter and the impact of the

---

Table 1: The success rates (%) after performing N node expansions for different subgoal search algorithms with access to environment dynamics. For HIPS-e, we use the value of ε that yields the best performance: - 0 for Sokoban, and + 0 for Travelling Salesman Problem. HIPS corresponds to HIPS-env in [18] and uses PHS* the search algorithm in all environments.
10-5 for Sliding Tile Puzzle, 10 for
Sokoban
Sliding Tile Puzzle
N
50
100
200
50
100
200
PHS" (low-level search)
0.2
2.4
16.2
100
0.0
0.0
0.0
100
HIPS (high-level search)
82.0
87.8
91.6
97.9
8.7
56.8
86.3
95.0
AdaSubS (high-level search)
76.4
82.2
85.7
91.3
0.0
0.0
0.0
0.0
kSubS (high-level search)
69.1
73.1
76.3
90.5
0.7
79.9
89.8
93.3
HIPS-s (complete search)
84.3
89.5
93.1
100
18.5
69.5
93.8
100
Box- World
Travelling Salesman Problem
30
00
20
50
100
00
PHS* (low-level search)
0.0
0.1
2.2
100
0.0
0.0
0.0
100
HIPS (high-level search)
86.3
97.9
99.9
99.9
19.6
88.1
97.7
100
AdaSubS (high-level search)
0.0
0.0
0.6
21.2
kSubS (high-level search)
0.0
1.5
40.4
87.9
HIPS-E (complete search)
89.7
98.9
100
100
17.9
87.4
97.9
100
novel heuristic factor and the corresponding PHS* evaluation function (4). The DOD-generalizattin abilities of HIPS-s are also discussed. We use the four environments considered in [18]: Box-World [44], Sliding Tile Puzzle [17], Gym-Sokoban [37] and Travelling Salesman (see Fig. 2).
We implement HIPS-E as proposed in (2) and the policy (Bc(a)s) (a)s) as a ResNet-based network [10] and train it using Adam [16]. We use the implementation of HIPS from the original paper and use PHS* (or complete variant thereof) as the search algorithm for HIPS and HIPS--. In [18], HIPS was evaluated with GBFS and A on some environments. HIPS- experiments with these search algorithms can be found in Appendix F. We use the versions of HIPS- and HIPS that have access to the environment dynamics (named HIPS-env in [18]) unless stated otherwise.
In Table I, we report the proportion of solved puzzles function of the number of expanded nodes for the low-level search PHS* high-level search algorithms HIPS [18], kSubS [4], and AdaSubS [45], and our HIPS-s, which is HIPS enhanced with the proposed complete subgoal search. We used the kSubS and AdaSubS results from [18] where they were not evaluated on Box- Gox-World. The results show that high-level search alone does not guarantee completeness, which means that for some puzzles the solution is not found even without limit on the number of cxpanded nodes (N = oo) due to the generator failing to propose subgoals that lead to a valid terminal state, phenomenon observed in prior work [4, 18, 45]. As expected, HIPS-s achieves a 100% success rate in all environments thanks to augmenting the subgoals with low-level actions. In addition to the number of search node expansions, we analyzed the search cost in terms of wall-clock time and environment steps. HIPS- generally outperforms the baselines also using these metries. The results of these experiments can be found in Appendices and K.
We also evaluated HIPS-e on Sokoban, STP, and TSP with learned transition models and compared it to HIPS with learned models, behavioral cloning (BC), Conservative Q-learning [CQL, 19], and Decision Transformer [DT, 3]. We omitted Box-World due to HIPS struggling with the learned dynamics [18]. The results are shown Table 2. HIPS-s outperforms the baselines but can fail to find solution to solvable problem instance due to the learned dynamics model sometimes outputting incorrect transitions. Completeness can be attained by using the true dynamics for validating solutions and simulating low-level actions, while still minimizing the number of environment steps (see Appendix E). For complete results with confidence intervals, please see Appendix G.
Interestingly, the results in Table show that augmenting the high-level search with low-level actions may have a positive impact on the performance for the same budget of node expansions N: we observe statistically significantly increased success rates for the same N in all environments except
7

---

Table 2: The success rates (%) of different algorithms without access to environment dynamics in Sokoban, Sliding Tile Puzzle, and TSP. HIPS-E outperforms the baselines and can solve 100% of the puzzles when the environment dynamics easy to learn.
HIPS
HIPS-E
BC
CQL
DT
Sokoban
97.5
100.0
18.7
3.3
36.7
Sliding Tile Puzzle
94.7
100.0
82.5
11.7
0.0
Travelling Salesman
100.0
100.0
28.8
33.6
0.0
Table 3: The success rates (%) after N node expansions Sliding Tile Puzzle computed only on
problem instances solvable by HIPS. (N) is the mean number of expansions needed to find a solution.
N
50
75
100
200
500
(N)
HIPS
9.2
38.2
59.8
90.8
99.7
108.9
HIPS-S, 10-5
17.3
48.4
68.2
93.5
99.9
95.6
in the Travelling Salesman, where the results are approximately equal. Next, we analyze whether the increased number of solved puzzles is only because of the high-level search failing to find solution some puzzles. In Table 3, we consider the Sliding Tile Puzzle problem and report the same results as in Table 1 considering only the puzzles solvable by HIPS. The results suggest that the complete search can speed up finding correct solution.
In Fig. 3, we analyze the effect of the hyperparameter e on the number of solved puzzles. We report the ratio of the number of unsolved puzzles by HIPS-s the number of unsolved puzzles by HIPS as a function of N, the number of node expansions. We observe that HIPS-s outperforms HIPS in all environments except TSP, and extensive hyperparameter tuning select good value of is rarely necessary. The plots also support our hypothesis about small value of æ being often better despite the worse worst-case performance, as E 10 is often superior strategy suggested by Zawalski et al. [45] (which we denote as E + 0) is sometimes but not always the best strategy. We analyze the impact of the value of E in Appendix I.
0.1. The augmented search
Generalization to Out-of-Distribution Distribution Puzzles In the following experiment, we demonstrate one of the most attractive properties of complete search: its ability enhance the high-level search policy to transfer to new (potentially more complex) search problems. We evaluate HIPS-- on Box- World in which the following changes have been made comparison to the trajectories in D: the number of distractor keys has been increased from three to four, and the colors of distractors changed such that there are longer distractor trajectories that lead into dead-end states, making it more difficult to detect distractor keys. After these changes to the environment, the share of puzzles HIPS can solve drops from over 99% to approximately 66% (see Fig. 4). However, the 100% solution rate can be retained by performing complete search. Note here that higher values of & seem superior to lower values when the generator is worse, which is aligned with our analysis in Section 3.4.
Role of the Heuristic Factor Orseau and Lelis [27] observed that for pure low-level search, using learned heuristic in addition to search policy т can lead to significantly improved search performance. We evaluated the performance of HIPS-s with different heuristic factors and corresponding PHS evaluation functions. We compared the heuristic factor and evaluation function (4) proposed by us, the Levin-Tr TS inspired evaluation function PLeviinS
g(n) (n) that does not heuristic, and
Table 4: The success rates (%) of HIPS-E with different PHS evaluation functions. For all environ- ments, = 1 Search without heuristic fails in TSP due running out of memory.
Sokoban
Sliding Tile Puzzle
Box- Box-World
TSP
N
50
100
200
50
100
200
10
20
50
100
S (ours)
82.5
88.8
92.9
16.3
68.6
93.7
89.0
99.1
18.3
82.4
96.1
PLeiinSS
66.4
80.1
88.8
0.0
0.0
0.5
27.4
66.3
N/A
N/A
N/A
Pdepth
71.8
83.6
91.5
0.0
0.2
1.2
37.3
75.8
0.0
0.0
0.0
Paist
68.6
81.3
88.7
0.0
0.1
0.7
30.4
70.0
0.0
0.0
0.0
8

---

Box World
Siiding Tile Puzzie
10-
0.6
0.6
10
6-0
H15
23
50
7.3
10.0
25.0
20.0
167
Sokoban
Travelling Sa esman Problem
2.4
1.-
14-
1.0
94 107 207
121
Figure 3: The ratio of the number of unsolved puzzles to the number of unsolved puzzles by HIPS as function of the number of node expansions N (x-axis). Values below indicate that the complete search is superior to the high-level search. HIPS-- outperforms HIPS in every environment except TSP, where high-level actions are sufficient for solving every problem instance.
10%
04
1-10
1.20
2000
2000
(a) Percentage of unsolved puzzles
(b) Ratio unsolved puzzles (cf. HIPS)
Figure 4: The percentage of puzzles remaining unsolved (y-axis) depending the number of node expansions (x-axis) for complete search with different values of e and only high-level search (left), and the ratio of unsolved puzzles in comparison with HIPS depending the number of node expansions (right), when the methods have been evaluated on an aatoo--distribution variant of Box-World.
naive A **iinspired evaluation functions [9] which correspond to the variant PHS, in [27]:
Pdapph (g(n)) + h(n)))/((n)
Paaist = (I(m) ((m))/(())
The results in Table 4 show that a heuristic function is crucial for reaching a competitive search performance most environments. In particular, on TSP, where it was observed that training good VQVAE prior (which we use TsG) is very difficult [18], the search heavily relies the learned heuristic, and the search fails due to running out of memory. Furthermore, naively using A in-isiireed evaluation functions fails to be competitive.

---

5 Conclusions
Subgoal search algorithms can effectively address complex reasoning problems that require long-term planning. However, these algorithms may fail to find a solution to solvable problems. We have presented and analyzed HIPS-s, an extension a recently proposed subgoal search algorithm HIPS. We achieve this by augmenting the subgoal-level search with low-level actions. As a result, HIPS-E is guaranteed to discover a solution if solution exists and has access to an accurate environment model. HIPS-E outperforms HIPS and other baseline methods in terms of search loss and solution rate. Furthermore, the results demonstrate that augmenting the search with low-level actions can improve the planning performance even if the subgoal search could solve the puzzle without them, and the proposed algorithm not byperparameter-sensee sensitive.. HIPS-s enables using subgoal search in discrete settings where search completeness is critical.
In the future, we would like tackle some of the limitations of our work. Our search paradigm could be applied to other subgoal search methods than HIPS and search algorithms than PHS. Combining HIPS-E with recursive search methods that split the problem into smaller segments could enable scaling to even longer problem horizons. Our analysis of the complete subgoal search assumes deterministic environments and access transition dynamics. HIPS- can also function without access to the transition dynamics, but the completeness guarantee is lost. Many real-world problems are partially or fully continuous. There are also problems with infinite discrete action spaces that HIPS-g is not particularly suited for, and we assume discrete state representations. HIPS-g also assumes that a solution exists. Modifying HIPS-c for the continuous setting could enable solving real-world robotics tasks. HIPS-s also showed potential at transfer learning by efficiently solving more complex Box-World tasks than those seen during training. Applying curriculum learning by learning the initial model offline and then learning to progressively solve harder problem instances with online teeettunng is a promising direction for future research.
Acknowledgments and Disclosure of Funding
We acknowledge the computational resources provided by the Aalto Science-IT project and CSC, Finnish IT Center for Science. The work was funded by Research Council of Finland (aka Academy of Finland) within the Flagship Programme, Finnish Center for Artificial Intelligence (FCAI). J. Pa- jarinen was partly supported by Research Council of Finland (aka Academy of Finland) (345521).
References
[1] Forest Agostinelli, Stephen McAleer, Alexander Shmakov, and Pierre Baldi. Solving the Rubik's 's Cube with Deep Reinforcement Learning and Search. Nature Machine Intelligence, 1 (8):356-363, 2019.
[2] Cameron Allen, Michael Katz, Tim Klinger, George Konidaris, Matthew Riemer, and Gerald Tesauro. Efficient Black-Box Planning Using Macro-Actions with Focused Effects. ArXiv preprint, htss/2004.13443 2020. URL /tapps:///axxv..///// orggoog/// abs//0/4. 13242.
[3] Lili Chen, Kevin Lu, Aravind Rajeswaran, Kimin Lee, Aditya Grover, Michael Laskin, Pieter Abbeel, Aravind Srinivas, and Igor Mordatch. Decision Transformer: Rein- forcement Learning via Sequence Modeling. In Mare' Aurelio Ranzato, Alina Beygelz- imer, Yann N. Dauphin, Percy Liang. and Jennifer Wortman Vaughan, editors, Ad- vances Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages 15084 2021. URL https::////oooceeeeee wtw.oooeedniinn.u.enr..e..eeee.e neurinsu.ccomm cc. pppppr/222//aaa/// 7
http://60066---bbbaacca Abstract.. html.
[4] Konrad Czechowski, Tomasz Odrzygózdz. Marek Zbysinski, Michal Zawalski, Krzysztof Ole- jnik, Yuhuai Wu, Lukasz Kucinski, and Piotr Milos. Subgoal Search for Complex Reasoning Tasks. In Mare" Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurlPS 2021, Decem- ber 6-14, 2021, virtual, pages 624 638, 2021. URL https: htwp://dding.......oo/oo.p/ paper/ paper/2021// http:///seccccctteeeeetttttoeoo. htt.saassr.tttetaaaaaaattt...... Abstract. html.
www.inuu.p.... cc/
10

---

[5] Danny Driess, Fei Xia, Mehdi SM Sajjadi, Corey Lynch, Aakanksha Chowdhery, Brian Ichter, Ayzaan Wahid, Jonathan Tompson, Quan Vuong, Tianhe Yu, et al. PaLM-E: An Embodied Multimodal I Language Model. ArXiv preprint, a 2023. URL https://arxiv 033778
[6] Kuan Fang, Yuke Zhu, Animesh Garg, Silvio Savarese, and Li Fei-Fei. Dynamics Learning with Cascaded Variational Inference for Multi-Step Manipulation. ArXiv preprint, 1tts/1900.13995, 2019. URL https: /tt////axvvv.//// http//aawvv.//aaa///////// herg/bbs/191 13395.
[7] Thomas Gabor, Jan Peter, Thomy Phan, Christian Meyer, and Claudia Linnhoff- Subgoal- Based Temporal Abstraction Monte-Carlo Tree Search. In Sarit Kraus, editor, Proceedings of the Eerenty-Eightt International Joint Conference China, August 10-16, 2019, pages 5562- 5568. ijcai.org. 2019. doi: 10.24963/fjeai.2119977 URL https://doot org/ 10. 24963 wtcp:///jjaa../// htt.:/aaaaa2111//7/1 2019/772.
Artificial Intelligence, IJCAI 2019, Macao,
[8] Wei Gao, David Hsu, Wee Sun Lee, Shengmei Shen, and Karthikk Subramanian. Intention- Net: Integrating Planning and Deep Learning for Goal- Direeiiee Autonomous Navigation. In Conference on robot learning, pages 185-194. PMLR, 2017.
[9] Peter E Hart, Nils J Nilsson, and Bertram Raphael. A Formal Basis for the Heuristic Determina- tion of Minimum Cost Paths. IEEE Transactions Systems Science and Cybernetics, 4(2): 100-107, 1968.
[10] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep Residual Learning for Image Recognition, In 2016 IEFE Conference on Computer Vision and Pattern Recognition, CVPR 2016, Las Vegas, NV, USA, June 27-30, 2016, pages 770-778. IEEE Computer Society, 2016. doi: 10. 109/CVPR.2016
URL. https: /doii org/10 10. 1109/CVPR. 2016.90.
[11] Jeffrey R Hollerman, Leon Tremblay, and Wolfram Schultz. Involvement of Basal Ganglia and Orbitofrontal Cortex in Goal-Directed Behavior. Progress in brain research, 126:193-215, 2000.
[12] Dinesh Jayaraman, Frederik Ebert, Alexei A. Efros, and Sergey Levine. Time-Agnostic Prediction: Predicting Predictable Video Frames. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
URL
[13] Tom Jurgenson, Or Avner, Edward Groshev, and Aviv Tamar. Sub-Goal Trees a Framework for Goal- Boal-B Reinforcement Learning. Proceedings of the 37th International Conference on Machine Learning, ICMI. 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 5020-5030 PMLR, 2020. URL http: /ttp:::///ooceeings.... mlr. wwwps//eee/e///eepeeppepppssseee jurgensonung htmm.
[14] Junsu Kim, Younggyo Seo, and Jinwoo Shin. Landmark-Cuided Subgoal Genera- tion in Hierarchical Reinforcement Learning. In Marc' Aurelio Ranzato, Alina Beygelz- imer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Ad- vances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages 28336-28349, 2021. URL https httpp//pooeee..eeeeeee www.eees..cppapeeeeeeeeeeeeeeeee cctppppe////21/////eccc 9c98550bbiiedffcc8333383 www.aa8c8888888aaaaaaaa
Bateeeaaca-Abbtraacao Abstract htmml
[15] Taesup Kim, Sungjin Ahn, and Yoshua Bengio. Variational Temporal Abstraction. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Bus Buc, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 11566-11575 2019. URL https: /ttpc::://rroo/eeee ptwp//diiceee.eeeeeeeeeeeco...ee neur cc/paper/ Abstract. htmml. html.
2019 /aaaaa/5555aa0010111000100000000
[16] Diederik Kingma and Jimmy Ba. Adam: A Method for Stochastic Optimization. In Yoshua Bengio and Yann LeCun, editors, 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015. URL. http:/ /ttp:///xxii /aaxiiiiiiva//aa///aaa/aaaaaavva org/abs/ 1480.6980......

---

[17] Richard E Korf. Depth-First Seerative-Deepenne an Optimal Admissible Tree Search. Artificial Intelligence, 27 1985.
[18] Kalle Kujanpää, Joni Pajarinen, and Alexander Ilin. Hierarchical Imitation Learning with Vector Quantized Models. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 17896-17919. PMLR, 2023. URL htteps://proceedinne mlr.
html.
[19] Aviral Kumar, Aurick Zhou, George Tucker, and Sergey Levine. Conservative Q-Learning for Offline Reinforcement Learning. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, viriual, 2020. URL https: http//ppooeddnneeeee/eeeeeee neurips.co paper saper/2020/hasta) 201220//aah/000
https::/procceeeeee Attt-Artttttaatttmmma
[20] Aviral Kumar, Rishabh Agarwal, Xinyang Geng, George Tucker, and Sergey Levine. Of- fline Q-Learning on Diverse Multi-Task Data Both Scales And Generalizes. ArXiv preprint, abs/2211.15144 2022. URL https: /
wwt//tgg/////////////.///eee//// abs//211...... 15144.
[21] Thanard Kurutach, Aviv Tamar, Ge Yang, Stuart J. Russell, and Pieter Abbeel. Learning Plannable Representations with Causal InfoGAN. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett, editors, Ad- vances in Neural Information Processing Systems 31: Annual Conference on Neural Infor- mation Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pages 8747-8758, 2018. URL htpp://prrocesenng neurips httpp/pppp/////a///eee CBaccacc886565333951111117777553 http://ssttttttttttttta. html.
[22] Jinning Li, Chen Tang. Masayoshi Tomizuka, and Wei Zhan. Hierarchical Planning Through Conditond Offline Reinforcement Learning. ArXiv preprint, abs/2205.11790, 2022.
URL https://arxixi http://////ax..ooo//aaa/////////
[23] Kara Liu, Thanard Kurutach, Christine Tung, Pieter Abbeel, and Aviv Tamar. Hallucinative Topological Memory for Zero-Shot Visual Planning. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 6259-6270. PMLR, 2020. URL http: // //ppoceedings.iii mlr. press http///119/lii// .html.
[24] Amol Mandhane, Anton Zhernov, Maribeth Rauh, Chenjie Gu, Miaosen Wang, Flora Xue, Wendy Shang, Derek Pang, Rene Claus, Ching-Han Chiang, et al. MuZero with Self- Competition for Rate Control in VP9 Video Compression. ArXiv preprint, abs/2202.06626, 2022. URL https: attps://arxivv wtw.a.iwo...a...oaooooooooooolll perg//bs///a abs//202..66e222
[25] Suraj Nair and Chelsea Finn. Hierarchical Foresight: Self-Supervised Learning of Long- Horizon Tasks via Visual Subgoal Generation. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL https://
[26] Soroush Nasiriany, Vitchyr Pong. Steven Lin, and Sergey Levine. Planning with Goal- Conditioned Policies. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-BBu,, Emily B. Fox, and Roman Garnett, editors, Advances in Neu- ral Information Processing Systems 32: Annual Conference
Neural Information Pro- cessing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 14814-14825, 2019. URL https: http:///wceeeee...e/////// UtLpttps://prrceednne 4Bcc6990ccbE144440ee22661111
pepooeedinggeneurips... www.ips..ccpapprr//// wwtpc//pppe///////eeeea abbsraact.hmm
[27] Laurent Orseau and Levi H. S. Lelis. Policy-Guided Heuristic Search with Guarantees. In Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty- Thirty-Third Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, FAAI 2021, Viriual Event, February 2-9, 2021, pages 12382-12390. AAAI Press, 2021, URL https: / /ojs aaai, .rgg frrg/ine ///ddxddxx/// www..pppppAa.. AAAT/ article/view/14g0
12

---

[28] Laurent Orseau, Levi Lelis, Tor Lattimore, and Theophane Weber. Single-Agent Policy Tree Search with Guarantees. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Biancht and Roman Garnett, editors, Advances Neural Information Processing Systems 31: Annual Conference on Neural Informa- tion Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada. pages 3205-3213, 2018. URL https: ppooee/eiogccc......... neuripu-..... cctppaper///////a//eeee www.rratt.tttteeeeeeeeeee
[29] Sherjil Ozair, Yazhe Li, Ali Razavi, Ioannis Antonoglou, Aäron van den Oord, and Oriol Vinyals. Vector Quantized Models for Planning. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 3302-83153 PMLR, 2021. URL http:: httpt:://ppooceinngs....m mlr. www.ppeeessseee 2ttess/v139//zarr1111 www.oraaaaaaaa.e..eeee.a html.
[30] Giambattista Parascandolo, Lars Buesing, Josh Merel, Leonard Hasenclever, John Aslanides, Jessica B Hamrick, Nicolas Heess, Alexander Neitz, and Theophane Weber. Divide-and- Conquer Monte Carlo Tree Search for Goal-Directed Planning. ArXiv preprint, abs/2004.11410, 2020. URL https: / / /arxiv.ivvv htte:/b//20000 /204. 11410.
[31] Karl Pertsch, Oleh Rybkin, Frederik Ebert, Shenghao Zhou, Dinesh Jayaraman, Chelsea Finn, and Sergey Levine. Long-Horizon Visual Planning with Condi-Condii Hierarchical Predictors. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Floring Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6- 12, 2020, virtual, 2020. URL https: httttpss//prroceednggg httpeeeeddinnnnnn.iii.ss.. wwwrips.cc/paapeeee (papee//020//ash//// Boddaa70eeaab31155566668886666
Abstraatttttttaaaee...eeaaa.. html.
[32] Karl Pertsch, Oleh Rybkin, Jingyun Yang, Shenghao Zhou, Kosta Derpanis, Joseph Lim, Kostas Danilidiss, and Andrew Jaegle. KeyIn: Keyframing for Visual Planning. Conference on Learning for Dynamics and Control, 2020.
[33] Stanislas Polu and Ilya Sutskever. Generative Language Modeling for Automated Theorem Proving. ArXiv preprint, 0bs/2009.033993 2020. URL https://arxiv https:///xxvvvo///aaaee arg/abs/2009. 03393.
[34] Reuven Y Rubinstein and Dirk P Kroese. The Cross-Entrop Method: Unified Approach to Combinatorial Optimization, Monte- Carlo Simulation, and Machine Learning, volume 133. Springer, 2004.
[35] Stuart Russell. Artificial Intelligence: A Modern Approach. Pearson Education, Inc., 2010.
[36] Nikolay Savinov, Alexey Dosovitskiy, and Vladlen Koltun. Semi-Parametric Topological Mem- ory for Navigation. In 6th International Conference Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30- May 3, 2018, Conference Track Proceedings. OpenRe- view.net, 2018. URL
[37] Max-Philipp B. Schrader. gym- sokoban, 2018.
gom-sokoban.
[38] Julian Schritwweserr, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Si- mon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, et al. Mastering Atari, Go, Chess and Shogi by Planning with Learned Model. Nature, 588(7839):004-699, 2020.
[39] David Silver, Thomas Hubert. Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. A General Reinforcement Learning Algorithm that Masters Chess, Shogi, and Go Through Self-Play. Science, 362(6419): 140-1 144, 2018
[40] Avi Singh, Albert Yu, Jonathan Yang, Jesse Zhang, Aviral Kumar, and Sergey Levine. COG: Connecting New Skills to Past Experience with Offline Reinforcement Learning. ArXiv preprini, abs/2010.14500 2020. URL https: ptttps://arxiie http///axvvvv///////a org/ abs/ 14500.
13

---

[41] Aäron van den Oord, Oriol Vinyals, and Koray Kavukcuoglu. Neural Discrete Representation Learning. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett, editors, Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9 2017, Long Beach, CA, USA, pages cc http:////////.../.....00000000e/ Abstract.................. html.
2017. URL httpp//tttttttteeereeeeaaaae iet.reerpdinnss.nu.i....... neurips.
[42] Homer Rich Walke, Jonathan Heewon Yang, Albert Yu, Aviral Kumar, Jędrzej Orbik, Avi Singh, and Sergey Levine. Don't Start from Scratch: Leveraging Prior Data to Automate Robotic Reinforcement Learning. In Conference on Robot Learning, pages 1652-1662. PMLR, 2023.
[43] Ekim Yurtsever, Jacob Lambert, Alexander Carballo, and Kazuya Takeda. A Survey of Au- tonomous Driving: Common Practices and Emerging Technologies. IEEE access, 8:58443- 58469, 2020.
[44] Vinicius Zambaldi, David Raposo, Adam Santoro, Victor Bapst, Yujia Li, Igor Babuschkin, Karl Tuyls, David Reichert, Timothy Lillicrap, Edward Lockhart, et Relational Deep Reinforcement Learning. ArXiv preprint, 1806.80618000 2018. URL https::/arxxi...o
abs/1806. 01830.
[45] Michat Zawalski, Michat Tyrolski, Konrad Czechowski, Damian Stachura, Piotr Piękos, Tomasz Odrzygózdć, Yuhuai Wu, Lukasz Kuciñski, and Piotr Mitoš. Fast and Precise: Adjusting Planning Horizon with Adaptive Subgoal Search. ArXiv preprint, abs/2206.00702, 2022. URL https: attps://arxiv> org/ abs/ 00702.
[46] Lunjun Zhang, Ge Yang, and Bradly C. Stadie. World Model as a Graph: Learning Latent Landmarks for Planning. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning. ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 16611-1660. PMLR, 2021. html. html..
URL http: httpp:///occeedngg..mmm mlr, wwwppppsssse....... /aess//v/////v 2119//hhag21x1
14


Reviews:
[{"review_id": "x8QyoyEvKw", "reviewer": "Reviewer_nqzu", "summary": "The paper considers solving complex planning problems with discrete action spaces and develops a novel hybrid search scheme that combines high-level sub-goal oriented search (aka hierarchical planning) with a complete low-level search scheme. The latter embodies a classical exhaustive search scheme that only considers low-level actions. The proposed approach is applied to an existing sub-goal oriented planning system called HIPS (Hierarchical Imitation Planning with Search). In contrast to the existing approaches, including HIPS, the new system is guaranteed to be complete, namely it will find a solution if one exists. Furthermore, the proposed enhanced HIPS is evaluated on four planning benchmarks which were also considered in previous work. The results demonstrate clearly the performance of the proposed approach compared with the baseline HIPS system as well as with strong existing offline reinforcement learning algorithms.\n", "questions": "1. The sliding puzzle and to some extent the box-world problems are considered to be fairly easy to solve by classical AI planners using some version of A* search. I was wondering how does the proposed HIPS enhancement compare with classical planners on this domain.\n\n", "limitations": "I think the limitations of the proposed method are discussed fairly clearly in the paper.\n", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is fairly well written and organised. The quality of the presentation is overall fairly good. The results are presented in a relatively clear manner so it's fairly easy to grasp the big picture.\n", "weaknesses": "My only concern is that the proposed approach looks fairly incremental compared with the existing work on HIPS. The main novelty seems to consist in adding the behaviour cloning policy to select low-level actions.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their insightful comments and observations.\n\n> The main novelty seems to consist in adding the behaviour cloning policy to select low-level actions.\n\nWe want to emphasize that not only do we add a new behavior cloning policy to efficiently solve a known problem of subgoal search methods, but we also analyze the impact it will have on the results, derive a new heuristic rule for efficiently using it in search (which is particularly important, see Table 4) and confirm that the empirical results match the expected ones. High-level search has been recognized as a promising research direction, as kSubS was published at NeurIPS 2021, AdaSubS at ICLR 2023 (Notable top-5 % = Oral), and HIPS at ICML 2023, so improving on these methods is relevant. Furthermore, we show that using the low-level actions not only guarantees completeness but can also improve the search performance on instances solvable by high-level search, which is a non-trivial result. Although we evaluated our approach on HIPS due to its strong performance, our framework can also be applied to other subgoal search methods such as kSubS and AdaSubS. Finally, we show promising OOD generalization capabilities, which are missing in many learning algorithms. The promising OOD results also open doors for new applications such as curriculum learning and the multi-task setting.\n\n> The sliding puzzle and to some extent the box-world problems are considered to be fairly easy to solve by classical AI planners using some version of A* search. I was wondering how does the proposed HIPS enhancement compare with classical planners on this domain.\n\nDefining a suitable heuristic for the Box-World problem (without prior knowledge about the solution path) is a highly non-trivial problem, which hampers our ability to apply the A* algorithm. If we naively apply Dijkstra's algorithm to it, we're bottlenecked by RAM before a solution is discovered (happens at ~700k node expansions). If we assume access to prior knowledge, a reasonable heuristic is to count the number of collected keys (which does not separate between distractors and correct ones) and subtract that from the goal length (requiring prior knowledge). This heuristic does not help us to reliably discover solutions (see Table 12 in the global rebuttal pdf) even if we perform WA* with W=10, and in most of the failure cases, we run out of RAM before a solution is discovered.\n\nFor STP, note that the prior work in the planning domain has focused on the easier 4x4 variant, whereas we work on the 5x5 problem, which is considered significantly harder (see [1], pp. 71). Nevertheless, we can still use the Manhattan distance as a heuristic for A*. We experimented with a limit of 100,000 expansions (note that HIPS-$\\varepsilon$ had a 69.5 % solution rate with 100 expansions and 93.8 % at 200). A* had a solution percentage of 0. With WA* and W=2, the solution % at 100,000 expansions was 10.2 %, which is significantly worse with 10^3 times more node expansions. For W=5, where the heuristic is used very greedily, the solution rate is 91.0 % at 100,000 expansions (see Table 12 in the rebuttal pdf). Even then, it is significantly inferior to HIPS-$\\varepsilon$ in terms of expansions and requires applying prior knowledge for defining the heuristic, whereas HIPS-$\\varepsilon$ does not assume any prior knowledge except the ability to recognize terminal states upon entering them. Finally, note that, for example, the HIPS paper [2] specifically used subgoal-based A* to generate the demonstrations for STP and Box-World because of how expensive the demonstration generation was with standard A*.\n\n[1] Russell, S. & Norvig, P. Artificial Intelligence: A Modern Approach. 3rd edition.\n\n[2] Kujanpää, K., Pajarinen, J., & Ilin, A. (2023). Hierarchical Imitation Learning with Vector Quantized Models. ICML 2023. "}, {"review_id": "MieErcJVFm", "reviewer": "Reviewer_v7TG", "summary": "The authors present an idea of enriching a classical hierarchical search pipeline with an exhaustive low-level search. This approach guarantees the completeness of the search and offers practical advantages, including slightly better success rates in the tested environments and stronger out-of-distribution evaluation properties. The method is built on top of the HIPS algorithm. The paper provides technical adjustments to the theory of the original HIPS that cover the hybrid approach.", "questions": "In general, I think that the paper is solid and well-presented. The novelty is limited, as the main idea is a formalized study of ideas hinted in some previous papers, which is an extension of known algorithms. Nevertheless, I think it may be a good contribution since the described approach is simple, yet offers some clear advantages. That said, I would like a few clarifications. See my comments below.\n\nl.15: You claim that your approach guarantees completeness, which is clear. However, it is not clear to me why should we care so much about completeness. I suggest adding to the paper (introduction perhaps) a short justification of the necessity of having the completeness property, as you claim it to be your main advantage.\n\nl.92 How much data do you use for training in a single environment? How long do you train each of the networks?\n\nl.141: I understand that the value of $\\varepsilon$ corresponds to the density of using low-level actions. But I would like to understand how the specific values (importantly, those used in experiments) correspond to the number of low-level expansions performed during the search. For instance, does setting $\\varepsilon=10^{-5}$ correspond to roughly one expansion every $10^5$ steps? I don't think so, because it would have quite a negligible impact on performance. In l.212 you claim that a low value of $\\varepsilon$ is generally preferred, but I don't know how it exactly relates to the search itself.\n\nl.173: Please refer to the exact place in the appendix.\n\nTable 1: Is the $\\infty$ budget a theoretical bound (like we're sure that given $10^{20}$ iterations low-level search would solve TSP optimally), or did you simply run the methods for a very large number of steps? Please state it clearly.\n\nTable 1: Since setting $\\varepsilon\\to 0$ essentially means that you perform exhaustive expansion in case the search would otherwise fail, why does your HIPS-e achieve (a little) worse results than HIPS in TSP?\n\nTable 1: Please provide the values of the main hyperparameters used for evaluating all the approaches presented in Table 1. Did you tune any values yourself? The results of the AdaSubS baseline on Sliding Tile Puzzle and TSP seem quite low compared to kSubS. As far as I understand, it is a generalization of kSubS, so why is it so much worse?\n\nl.259: Arguably the simplest approach to improving the completeness is to increase the number of subgoals generated at each node expansion. I wonder how do your empirical results relate to tuning that parameter? In particular, please specify the values that you use.\n\nl.266 I really like the OOD idea. Intuitively, it seems clear that augmenting the search with reliable low-level expansions is helpful in case the generator struggle in unknown domains. I think it deserves analyzing it in more detail. Did you observe similar patterns in other environments? What budget did you use for the reported results? Or are these results _theoretical_ (i.e. HIPS-e is _guaranteed_ to solve everything eventually) (in which case you should also remark it)?", "limitations": "The limitations are discussed. The negative societal impact is not a concern here.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is mostly clear and well-written. The main idea is intuitive and the reported experiments support it. The OOD application seems very promising to me.", "weaknesses": "The novelty of the approach is limited, although the paper may still be a good contribution. I am not convinced that the completeness is a major concern itself, the paper lacks a clear justification for that. The impact of tuning the most important parameter $\\varepsilon$ on the number of low-level expansions should be discussed. The key parameters used for evaluating presented methods should be provided.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their insightful comments and questions.\n\n>I am not convinced that the completeness is a major concern itself.\n>\n> l.15 Why should we care so much about completeness\n\nWe see completeness as a worthwhile problem to tackle due to four main reasons:\n1. Without completeness, we do not know whether a solution will be found when the algorithm is executed. This is critical for both theoretical science but also for practical algorithms.\n2. Completeness is the key to the promising OOD capabilities shown by our agent, as completeness guarantees that the solution to the tasks will be found, even if the generative model or low-level policy is imperfect. Completeness allows extensions and new incremental algorithms that require building on top of exact solutions. One example of that could be curriculum learning. \n3. Achieving completeness makes applying high-level search as an alternative to low-level search possible in safety-critical real-world systems.\n4. Without completeness, comparing different high-level search algorithms requires a somewhat arbitrary balancing of efficiency and solution percentage.\n\nWe will include this discussion in the final version.\n\n> The impact of tuning epsilon\n>\n> l.141: How the specific values [of epsilon] correspond to the number of low-level expansions\n\nWe performed an additional study on STP and analyzed the impact of $\\varepsilon$ on the number of low-level expansions performed during the search and low-level actions included in the discovered solutions. Please see Figure 7 in the global response PDF for the results. As expected, the relative share of low-level expansions and actions decreases as we decrease epsilon, and the function is monotone. Note that $\\varepsilon$ only affects the probability assigned to the node ($\\pi(n)$ in Eq 4 of the paper), but the node evaluation function also depends on the node’s depth and low-level distance from the root, and the value of the learned heuristic function. Hence, there is no deterministic correspondence between the value of epsilon and the share of low-level expansions. Nevertheless, we observe that for $\\varepsilon = 0.5$, the share of low-level expansions is slightly over 40 %, so there is a rough correspondence for larger values of $\\varepsilon$. In line 212, we hypothesize that a low value of $\\varepsilon$ should, in most cases, lead to a more efficient search due to high-level actions being used more often, but it has a worse worst case-performance.\n\n> Key parameters used for evaluating presented methods.\n\nWe will add the hyperparameters used for evaluating HIPS and HIPS-epsilon to the final version. Note that for AdaSubS, kSubS, and other baselines, we copied the results from [1] (lines 238-239 in the submission) to save computational resources. We used the same hyperparameters for HIPS as in [1]. The only hyperparameter that we tuned for HIPS-$\\varepsilon$ was the value of $\\varepsilon$. AdaSubS has a learned low-level policy, whereas kSubS uses a low-level search. Therefore, AdaSubS solves a more difficult problem than kSubS (and equally difficult as HIPS-$\\varepsilon$). The authors of [1] report that AdaSubS struggles to reliably reach the generated subgoals with the learned low-level policy, which would explain the results.\n\n> l.92 Training data and procedure\n\nWe use the same dataset as in [1], that is, 10340 trajectories in Sokoban, 5100 in STP, 22100 in BW, and unlimited but extremely low-quality trajectories in TSP. The datasets used in [1] also contain a validation set. We used the validation loss for early stopping.\n\n> l.173: Exact place in the appendix.\n\nAppendix B, we will add it to the text.\n \n> Table 1. Is the budget a theoretical bound\n\nFor HIPS-$\\varepsilon$, a budget of 10,000 expansions was sufficient to solve all the problem instances in our experiments in Table 1. For Sokoban and STP, we ran a PHS* low-level search for all problems until all solutions were discovered. For BW and TSP, we had a computation budget of 128,000 expansions, and we needed to interrupt the PHS* evaluation runs before a 100 % solution rate was attained.\n\n>Table 1: Why does your HIPS-e achieve (a little) worse results than HIPS in TSP?\n\nThe difference between HIPS and HIPS-$\\varepsilon$ in TSP is just noise (please check the complete results in Appendix E, Table 7). Thank you for raising this question, we will clarify it in the main text.\n\n> l. 259. Number of subgoals\n\nUnfortunately, we did not have the computational resources for an in-depth analysis of how the number of subgoals generated at each node expansion affects the completeness. However, looking at Figures 6b, 7b, 8b, and 9b in the Appendix J of [1], it seems that the VQVAE is already \"saturated\" and increasing the number of VQVAE codes does not increase the number of generated subgoals. For instance, in Figure 7b, it appears as if the VQVAE generated 4, 4, and 7 valid subgoals for the given states, even though the requested number of subgoals was 64. Hence, given a VQVAE generative model, increasing the number of subgoals is very unlikely to lead to completeness. For the autoregressive network used in kSubS and AdaSubS, that could be verified separately in the future.\n\n> l.266 OOD idea\n\nWe observed a similar pattern in Sokoban, although the advantage of HIPS-$\\varepsilon$ is slightly smaller due to HIPS generalizing better than in Box-World. Please see Figure 6 in the common PDF for the results. In STP, generating OOD puzzles is impossible without increasing the board resolution, which would require re-training the networks, and in our preliminary experiments, we found that HIPS already generalizes well to increasing the number of cities in TSP, so the benefits of hybrid search are limited there. The budget for HIPS-$\\varepsilon$ was 20,000 expansions, which was sufficient for solving all the evaluated problems.\n\n[1] Kujanpää, K., Pajarinen, J., & Ilin, A. (2023). Hierarchical Imitation Learning with Vector Quantized Models. ICML 2023. "}, {"review_id": "RTsZVdhE8i", "reviewer": "Reviewer_jgQs", "summary": "The paper introduces a method, called hybrid search (or HIPS-\\epsilon) that combines high-level planning (with subgoals generated by a learned model) with low-level search. Subgoals allow for more efficient search, but existing subgoal-based methods are prone to errors, which can lead to failures in finding solutions, even if the solution exists. Low-level search gives the completeness guarantee but is usually much less efficient. Hybrid search is a novel and efficient way of combining the advantages of both approaches. The method was tested on 4 different tasks, and various analyses show its excellent performance. ", "questions": "Questions:\n1. Why the error estimates for the success rate on the TSP problem are so high compared to the other tasks?\n2. How sample-efficient is the training of hybrid search? Is there any way to estimate the number of samples needed to train the method in a new env? \n3. How the performance of hybrid search depends on the size of the training dataset?\n4. Clearly TSP is an outlier: the results on this task look different (I mean: Figure 3, Table 7 in supplementary materials or lines 261-262). Do you know why it is so? What is so specific about TSP?\n5. Do you have results similar to Table 3 but for other problems? The most interesting here is the average number of nodes of expansion.\n6. A typical solution produced by HIPS-epsilon was constructed from some number of high-level actions and some number of low-level actions. What is the ratio of those? How is depends on epsilon? \n7. What happens if you run HIPS-epsilon on a problem with no solution (e.g. unsolvable Sokoban board)? For example, the state space in Sokoban is finite. Could HIPS be used to classify if the solution exists? Sokoban is an interesting example since deciding if a given board is solvable is NP-hard problem.\n8. Was AdaSubS tuned for the experiments? Its performance strongly depends on the chosen hyperparameters.\n\nlines: 269-272: was any component of HIPS or HIPS-epsilon trained after modification of the dataset? I suppose that no, just want to be sure.\n\nSuggestions:\nI think you should mention the tasks on which the method is evaluated both in the abstract and introduction. It is important for the reader.\n\nIn Section 3.1 some comment about the meaning of the heuristic factor is missing. For a reader who is not familiar with PHS it may be hard to quickly get how it depends on h(n) and we need the heuristic factor at all. I know that this can be found in the cited papers. I only suggest adding a footnote or comment with some motivation or explanation.\n", "limitations": "Some limitations were mentioned in Section 5, but in my opinion not all. All problems used for testing HIPS-epsilon have compact state representation, finite action space (there are problems with discrete yet infinite action space). Also, HIPS-epsilon is useful only on problems for which the solution exists (it is not a problem, but should be mentioned).", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The motivation for this paper is very clear and it precisely formulates the problem it is going to solve. The introduction section is well written with clear references to other works in the field. Baselines are chosen accurately. There are also a lot of insightful comments about the comparison of hybrid search to baselines. There is a broad evaluation of the method: success rate across all envs, epsilon-hyperparameter analysis, unsolved puzzles ratio, etc. Figure 3 is very insightful. I agree with the authors that OOD generalization is a very attractive property of the method. Hybrid search is explained in a clear way and, most importantly, the meaning of epsilon is easy to understand. The technical improvement over HIPS is simple, it mainly consists of two contributions: modification of policy, and modification of search heuristics. I consider it a huge advantage that a simple technique gives excellent results. The quality of the text is high, also I really liked all the comments. The main result, that is, achieving completeness without loss of efficiency, is excellent.", "weaknesses": "Table 1: there is no information on how many problem instances the method was tested. Are all results statistically significant? I know that there is no place in this table to put all error bars, but in the table caption, at least the average error (or maximum error) should be mentioned. I have looked into the supplementary materials to check the error estimates and I am not convinced by the results for TSP. For n=20, 50, and 100 the difference between HIPS and HIPS-epsilon is much smaller than the error estimates. Could you run the test on more instances to reduce the error or provide some argument why the results for TSP are meaningful?\n\nFigure 1. does not serve its role in illustrating the method. A reader wants to look at the image and quickly see the difference between the hybrid search and the other methods. The whole figure does not help in it. It illustrates only some flaws of other methods. I was unable to get any idea what a hybrid search is about just by looking at Figure 1. I think that a much better Figure can be created instead.\n\nFigure 3. Lines for epsilon=1e-5 are missing. You use that value in two problems, so we would like to see how it behaves on this graph.\n\nThere is no information about the size of the dataset used for offline training. \n\nOOD Generalization should be more elaborated. It is a very interesting result. I would like to see more results, for example, a table similar to  Table 1, Table 2, or Figure 3. Please consider this a minor weakness, I don't see any flaw in the part of the paper about OOD, I just want to say that the paper could benefit much from getting more results like this. \n\nThe success rate is clearly greate\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their insightful comments and questions.\n\n>Are all results statistically significant?\n>Could you run the test on more instances to reduce the error or provide some argument why the results for TSP are meaningful?\n\nWe will incorporate the information about statistical significance in the main text. At the moment, the statistical significance of the results has been computed in the supplementary material. The results are statistically significant in almost all cases except for TSP. Note that for TSP, we expect HIPS-$\\varepsilon$ and HIPS to be equal given that HIPS already attains a 100 % success rate and low-level expansions are never performed. The difference is not expected to be statistically significant. \n\n>Figure 1. does not serve its role in illustrating the method. \n\nWe will do our best to improve the figure for the final version of the paper by clearly marking and annotating the figure, illustrating the search queue, and reducing the number of nodes, in case the paper is accepted.\n\n> Figure 3. Lines for epsilon=1e-5 are missing. You use that value in two problems, so we would like to see how it behaves on this graph.\n\nThe results for epsilon = 10^-5 are very close to those of epsilon = 10^-3, so we chose to omit 10^-5 for clarity. We will include a figure with epsilon = 10^-5 in the final version of the paper if accepted.\n\n> There is no information about the size of the dataset used for offline training.\n\nWe use the same dataset as in [1], that is, 10340 trajectories in Sokoban, 5100 in STP, 22100 in BW, and unlimited but extremely low-quality trajectories in TSP.\n\n>OOD Generalization should be more elaborated. \n\nWe added a similar experiment on Sokoban (see Figure 6 in the common PDF), and add numerical results in the appendixes (due to lack of space).\n\n> Why the error estimates for the success rate on the TSP problem are so high compared to the other tasks?\n\nThe performance of HIPS-$\\varepsilon$ in TSP is more variable than in other environments. We hypothesize that it is due to the environment being particularly sensitive to the successfulness of the segmentation (does the detector agent always learn to take every city visit as a subgoal). \n\n>Sample efficiency\n\nIn this work, we used datasets of fixed sizes, and HIPS-epsilon outperformed the baselines for all sizes, but we do not unfortunately have any general estimates. However, note that the sample efficiency of the overall method depends on the chosen subgoal search approach, and in particular, the generative model (in this case, HIPS, and VQVAE). Generally, our results indicate that the hybrid search proposed by us will improve the sample efficiency of the underlying subgoal search (that is, HIPS-$\\varepsilon$ will be better in this respect than HIPS), as it will enable the agent to deal with the imprecisions of the low-level policy and generative model, similarly as in the OOD experiments. Table 3 in our submission indicates that the sample efficiency can improve even if the problem is solvable with subgoal search.\n\n>What is so specific about TSP?\n\nThe main difference is that HIPS already solves 100 % of the environments, so there is no room for improvement. In general, as mentioned above, we think that the environment makes successful segmentation particularly important, and there is some variance in terms of the performance of the detector agent trained with REINFORCE.\n\n> Do you have results similar to Table 3 but for other problems? The most interesting here is the average number of nodes of expansion.\n\nWe do not unfortunately have the same results for other problems, as we sampled the evaluation environments in the environments. However, in Box-World, the average number of expansions is 3.56 vs 3.82 in favor of HIPS-$\\varepsilon$ (p<0.001) for all solved problems. In Sokoban and TSP, we would expect the averages to be approximately equal for problems solved by both methods (given that $\\varepsilon \\to 0$ seems to work the best).\n\n> A typical solution produced by HIPS-epsilon was constructed from some number of high-level actions and some number of low-level actions. What is the ratio of those? How is depends on epsilon?\n\nPlease see Figure 7 in the common pdf. High-level actions dominate the solutions, with individual low-level actions being used (between 15 % and 0.2 % in our experiments), and their share depends on the value of epsilon such that higher epsilon gives more low-level actions, as expected.\n\n>What happens if you run HIPS-epsilon on a problem with no solution (e.g. unsolvable Sokoban board)? For example, the state space in Sokoban is finite. Could HIPS be used to classify if the solution exists? Sokoban is an interesting example since deciding if a given board is solvable is NP-hard problem.\n\nUnfortunately not by any other way except by running the search until the search queue empties. This is an interesting topic for further work.\n\n>Was AdaSubS tuned for the experiments?\n\nTo save computational resources, we copied the results for AdaSubS from [1], who did not elaborate in their paper on how the AdaSubS hyperparameters were chosen. In this paper, we incorporated our search approach into HIPS yielding HIPS-$\\varepsilon$. A further interesting evaluation could be incorporating hybrid search into AdaSubS yielding AdaSubS-$\\varepsilon$. In this case, we could also check hyperparameter optimization for AdaSubS.\n\n>lines: 269-272: was any component of HIPS or HIPS-epsilon trained after modification of the dataset? I suppose that no, just want to be sure.\n\nNo, no retraining was performed.\n\n>Suggestions: \n>Some limitations were mentioned in Section 5, but in my opinion not all. \n\nThank you for the suggestions and pointing out limitations, we will try to make them fit in the main text while staying within the constraints of the page limits.\n\n[1] Kujanpää, K., Pajarinen, J., & Ilin, A. (2023). Hierarchical Imitation Learning with Vector Quantized Models. ICML 2023. \n\n"}, {"review_id": "P2eFpsEoMj", "reviewer": "Reviewer_i9rx", "summary": "In this paper, the authors propose a hybrid technique to speed up the planning tasks. The novelty is that the completeness is guaranteed. I agree that guaranteeing completeness is a good property for a learning-based algorithm. ", "questions": "Please see my comments in the \"weakness\" block. ", "limitations": "I think the paper has presented the limitation and future works properly. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-written. \n2. The novelty of the contribution is moderate. \n3. It seems that the algorithm tried to find a balance between classic algorithms (complete but slow) and learning-based algorithms (fast but non-complete). The simulated results look good. ", "weaknesses": "1. I would say that the words \"hybrid search\" is not a suitable expression for the proposed algorithm. There have been too many \"hybrid\" algorithms. Currently I haven't come up with a suggestion, but the authors can think about it. \n2. Can the author present the problem to be solved in a formal environment? I mean \"Problem 1: (xxx) ...\". Currently the presentation is only friendly to expert. (Fig.1 does a good job.)\n3. I suggest the authors implement classic algorithms and show their performance. In my opinion, they are complete and optimal, but slow. By doing this the author can show the quality of the solution generated by the proposed algorithm. \n4. The algorithms should be tested in larger simulated environments. \n5. I think the related work section can be re-structured. Currently it just listed three kinds of searching algorithms, without mentioning their connection to this paper. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their insightful comments and questions.\n\n>I would say that the words \"hybrid search\" is not a suitable expression for the proposed algorithm. There have been too many \"hybrid\" algorithms. Currently I haven't come up with a suggestion, but the authors can think about it.\n\nThank you for the comment. A more concrete alternative to hybrid search is a high-level search augmented with low-level actions. To make it easy for the potential reader, we introduce our main idea and present the name hybrid search already in the abstract.\n\n>Can the author present the problem to be solved in a formal environment? I mean \"Problem 1: (xxx) ...\". Currently the presentation is only friendly to expert. (Fig.1 does a good job.)\n\nWe will add a more formal presentation of the problem, preferably at the beginning of Section 3, depending on the page limit constraints.\n\n>I suggest the authors implement classic algorithms and show their performance. In my opinion, they are complete and optimal, but slow. By doing this the author can show the quality of the solution generated by the proposed algorithm.\n\nWe performed this analysis. Please see Table 12 in the common response pdf. Generally, we indeed note that HIPS-$\\varepsilon$ greatly outperforms the classical planning algorithms in terms of node expansions, even if we allow classical planning algorithms to use heuristics defined using prior knowledge, which HIPS-$\\varepsilon$ does not have access to.\n\n>The algorithms should be tested in larger simulated environments.\n\nWe think that the environments used are already challenging and require significant computing power, as evidenced by the relative failure of classical planning methods at solving the problems (see Table 12 in the common response pdf). To further increase the difficulty, we perform the OOD experiments with Box-World (in the paper) and Sokoban (Figure 6 in the common response pdf). Also, the 5x5 sliding tile puzzle environment is considered challenging in the classical planning literature [1] (page 71).\n\n>I think the related work section can be re-structured. Currently it just listed three kinds of searching algorithms, without mentioning their connection to this paper.\n\nThank you for this comment. The first class of algorithms is hierarchical planning methods, but they rely on numerical optimization or are not suited to solving difficult discrete problems as used for evaluation in this work due to lack of search, capability to generate exact subgoals, or ability to plan. The second class of algorithms represents an orthogonal direction for improving hierarchical planning algorithms, and successfully combining these algorithms with our work could lead to even stronger agents, which is a subject for further work. The third class of algorithms is the ones most closely related to our work that our work builds on and that we use as baselines for evaluating our method. We will incorporate this information in the related work section to clarify the connection to prior work.\n\n[1] Russell, S. & Norvig, P. Artificial Intelligence: A Modern Approach. 3rd edition.\n"}]

Author rebuttal:
We want to thank all reviewers for taking the time to review our work and give feedback. Your insightful comments and observations are vital for improving the paper. We are grateful to the reviewers for appreciating the empirical results (all reviewers), the intuitive main idea (v7TG), clear motivation (jgQs), the broad evaluation and insightful comments (jgQs), the OOD application (v7TG, jgQs), and the presentation and writing (all reviewers).

To address the questions of the reviewers, we attached a pdf with results from the following additional experiments:
1. OOD experiments on Sokoban with six boxes, when the model has been trained on Sokoban with four boxes (Figure 6).
2. Demonstrating how the number of low-level expansions made by the search and the number of low-level actions in the returned solutions are affected by the value of $\varepsilon$ in STP (Figure 7).
3. Comparing HIPS-$\varepsilon$ to classical planning algorithms in terms of node expansions, highlighting the difficulty of the problems HIPS-$\varepsilon$ is capable of solving (Table 12).

We plan to add these to the final version to strengthen the paper even further. Furthermore, in the final version, we want to motivate why the completeness property is relevant (v7TG), improve the related work section to clarify the relation of our work to the prior work (i9rx), and make other adjustments based on the reviewer feedback.

Meta-review: The reviewers were in general agreement that the paper made a solid contribution. Please take the critical feedback into account when preparing the camera ready paper.
Decision: Accept (poster)