Unveiling Options with Neural Network Decomposition

Small Neural Networks

Dec-Options do not have to be restricted to small neural networks. Please see our answer to this question in the answer to all reviewers.

Baseline with Random Policies

Thank you for suggesting this baseline! In this baseline, we ignore steps 1 and 2 and randomly select an option that performs a fixed set of actions of length $M$. We then add $K$ of such options to the agent's action set. Note that this approach requires domain knowledge, as the values of $M$ and $K$ are not known a priori. By contrast, Dec-Options discovers them automatically.

We ran experiments on the Combo domain where we chose $M$ to be $6$, which is the average number of options Dec-Option chooses and $K$ to be $4$, which is the number of directions the agent can move. Despite having more information than Dec-Options, the latter performs much better as shown in Figure 10 of the Appendix E of the revised version. Even when we manually set the values of $M$ and $K$, there are many options to choose from and it is unlikely that helpful options would be selected this way.

Another interpretation of the reviewer's suggestion is to use the selection step (step 3) without steps 1 and 2. We note that step 3 cannot be used without step 1. This is because step 3 requires the data generated in step 1 to compute the Levin loss for selection.

Argmax in Section 4.2

Well spotted! Thank you! It should be $a_t = \arg\max_a \pi(s_t, a)$ instead of $a_t = \arg\max_a p(s_t, a)$. The use of the $\arg\max$ operator over $\pi$ reduces the noise in the selection process of the Dec-Options because the options also act greedily according to the sub-policies extracted from $\pi$. The added a sentence to explain this in the paper.

Suggestion Related to Figure 1

Thank you for your suggestion! We replaced Figure 1 with a smaller example where we can show the entire neural tree. This change also allowed us to get rid of the equations from the figure. Please see the new example on Page 4 of the revised version of the paper.

Thank you for your quick response. We are happy to hear you like our new Figure 1. We will add paragraphs explaining Option-Critic, DCEO, and $\epsilon$z-greedy to the appendix.

In the meantime, we would like to ask a couple of clarifying questions about your suggested baseline. There is a chance we will also answer your question "why is not possible to compute the Levin loss with randomly generated policies" while asking our questions.

Our Question: By randomly generated policies do you mean neural networks with their weights randomly generated or policies that execute a fixed and repeated random set of actions as we used in our baseline Random in Appendix E?

Re: "you randomly generate the policies, sample their trajectories and use Alg. 1"

There are a few ways of how the randomly generated policies $R$ can be used in Algorithm 1. Recall that Algorithm 1 requires a trajectory $\mathcal{T}$ and a set of options $\Omega$.

1. Interpretation (a): We can use $R$ to generate a trajectory $\mathcal{T}$ that is used in Algorithm 1.
2. Interpretation (b): We can use a set of policies $R$ to be used as the set of options $\Omega$ in Algorithm 1.
3. Interpretation (c): We can use policies $R$ to replace both $\mathcal{T}$ and $\Omega$ in Algorithm 1.

Interpretation (a) still requires us to define the set of options $\Omega$ used in Algorithm 1. In Dec-Options, $\Omega$ is defined as the sub-policies of trained neural networks. If we use with the baseline the same set of options $\Omega$ used with Dec-Options, then we cannot skip steps 1 and 2 of Dec-Options because $\Omega$ is generated in those two steps.

Interpretation (b) still requires us to define the trajectories $\mathcal{T}$ of Algorithms 1. In Dec-Options, $\mathcal{T}$ is given by trajectories sampled from fully trained neural networks, which are given in step 1 of our algorithm. This means we cannot skip step 1 of Dec-Options with interpretation (b).

Interpretation (c) allows us to skip steps 1 and 2 of Dec-Options and it offers a baseline that is somewhat similar to the baseline Random we added to Appendix E. If $R$ is given by a fixed and repeated random set of actions, then the trajectory $\mathcal{T}$ will be given by such a random sequence. In this case, the Levin loss will be minimized by a selection of policies $R$ that choose trajectories similar to those in $\mathcal{T}$. This is similar to randomly choosing some of these policies $R$ to be used as options, as we did in Appendix E.

Please let us know whether we answered your question. If not, please let us know which interpretation you had in mind: (a), (b), or (c), and we will get back to you.

Answer to Q1: Wonderful question! We chose the uniform policy because it is the only safe choice to be made. Since randomly initialized neural networks represent near-uniform policies, we know that at least in the first steps of training our choice of policy will be correct. Any other choice could be harmful. For example, if we consider a policy that favors one of the options, then this could hurt exploration in a target task if the favored option is not actually helpful.

Answer to Q2: Well spotted! Our implementation actually uses the linear version you mention. We decided to explain the quadratic because we felt it is easier to understand. In the revised version, we have added the linear version in Appendix A and added a sentence about it in the main text, after we explain the algorithm's complexity.

Answer to Q3: Thank you for pointing this out about Dec-Options-Whole. We have a few ideas of how to move forward with the selection process with very large neural networks. The activation pattern of the network in the early tasks provides valuable information. For example, if a neuron is always active or always inactive, then we can "prune" this neuron from consideration and that would represent a three-fold reduction in the size of the space. Also, the number of activation patterns is bounded by the number of samples in the tasks, so even if we have a very large neural network, the number of patterns that matter will always be bounded by how much data we have. All this information can potentially be used to guide local search algorithms in the activation pattern space. Also, following your observation about Dec-Options-Whole, we could try to bias the selection to consider sub-policies more similar to them. We think this is an exciting research direction.

Comments on Presentation

Thank you for the suggestions related to the presentation of the paper. We believe we made major improvements to the original version. Namely, the example from Figure 1 is much simpler and complete now. Instead of using a neural network with 3 neurons in the hidden layer, now we have a network with 2 neurons in the hidden layer. This allowed us to draw the entire neural tree and get rid of the formulas and of the $Z'$ notation, as you had suggested.

Also aiming at improving readability, we added an example of how the Levin loss is computed with our dynamic programming procedure in Appendix A.

Suggestion of Using Klissarov and Machado's DCEO as a Baseline

Thank you for suggesting us to include the work of Klissarov and Machado (2023) as a baseline. We ran experiments with their codebase and added the results to our plots (see Figures 3 and 4 in the revised version of the paper). You will notice from the plots that we also included another recent baseline, $\epsilon$z-greedy [1].

However, note that DCEO (the same goes to Option-Critic and $\epsilon$z-greedy) is not a direct competitor to the method we propose. DCEO learns options while learning a policy for a given problem. By contrast, Dec-Options are extracted from "legacy policies" and re-used in downstream problems; the options are learned even before the agent sees the target task. In some ways, Dec-Options have more information than DCEO because they use legacy policies. In other ways, DCEO has more information than Dec-Options because the options are learned for the target task, while Dec-Options relies on how well the options generalize across similar, but different tasks. Both methods make their unique and valuable contributions.

More Qualitative Results

Our way of visualizing what the options are doing is through the sequence of actions with the curly upper and lower brackets as shown at the end of Section 5.2. We also added more of such sequences in Appendix D, following your suggestion.

Question: What would be required to scale the method to larger neural networks?

Answer: This is a great question! We need to be able to search in the space of sub-programs and we have a few ideas of how this could be done, but we did not want to conflate the problem of searching in the space of sub-policies with the experiments that evaluate whether the sub-policies of existing networks could encode good options. We believe that the activation pattern of networks can offer valuable information on which sub-policies encode valuable information that could be transformed into options. This is a research question that needs to be addressed.

Question: Why investigate the ComboGrid environment? What is interesting about this task?

Answer: The Combo domain is a hard exploration problem that allows us to easily understand the sub-policies extracted from the neural networks. Moreover, the domain has clear dynamics where options could be helpful. Human designers would possibly design one option for each movement the agent can perform (up, down, left, and right). We wanted to see whether Dec-Options would be able to find something similar without having any prior information of the problem. We were pleased to see that our method discovered options similar to what we would have designed.

Comment: "we consider small neural networks with one hidden layer, so we can evaluate all sub-policies of a neural policy." This should be highlighted more.

Answer: Good point! We added a sentence in the last paragraph of the Introduction highlighting this methodological choice.

Reference

[1] Dabney, W., Ostrovski, G., and Barreto, A. Temporally-extended ϵ-greedy exploration. In International Conference on Learning Representations, 2021.

Short answer: No.

Long answer: We performed all our experiments on small neural networks so we would be able to evaluate all sub-policies of a given network. This way, we would not conflate a possible lack of helpful sub-policies with our potential inability to search for helpful options.

However, this does not mean that our method is restricted to small neural networks. Reviewer i5GW correctly pointed out that the variant Dec-Options-Whole, which only considers one sub-tree of the neural tree and does not pose constraints on the size of the neural network, already provides strong results.

Moreover, now that we know that it is possible to extract helpful policies with network decomposition, future research will investigate search algorithms for the space of sub-policies.