Subgoal-Guided Policy Heuristic Search with Learned Subgoals

Thank you for your helpful comments and feedback.

Concern 1

Each 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).

Consider 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.

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. 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.

We then tested the resulting models on a separate test set of 100 problems to match the procedure done for Table 1.

Concern 2

Yes, 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.

Concern 3

We 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.

Concern 4

A 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).

While 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.

Concern 5

We 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.

• 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.
• 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.

Concern 6

We did not tune hyperparameters specifically for each domain for our method. For any hyperparameter 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.

Thank you for your helpful comments and feedback.

Weakness 1

We 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.

Our 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.

We 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.

While 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.

In 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.

Weakness 2

This 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.

We 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.

To 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.

Thanks for your helpful comments and feedback.

Question 1.

The 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.

We 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.

Our 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.

We 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.

Question 3.

We 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.

[1] Culberson, J. Sokoban is PSPACE-complete. IEICE Technical Report, 1997

[2] Viglietta, Giovanni. "Gaming is a hard job, but someone has to do it!." Theory of Computing Systems 54 (2014): 595-621.

[3] Kujanpää, Kalle, Joni Pajarinen, and Alexander Ilin. "Hierarchical imitation learning with vector quantized models." International Conference on Machine Learning. PMLR, 2023.

Thank you for your helpful comments and feedback.

Question 1

Thank 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.

Our 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.

We then tested the resulting models on a separate test set of 100 problems to match the procedure done for Table 1.

Question 2

The 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.

What 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.

The following addresses your points from the Weaknesses section.

• 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
• 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]
• 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.
• 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.
• 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.

[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.