Hierarchical Programmatic Option Framework

We sincerely thank the reviewer for the thorough and constructive comments. Please find the response to your questions below.

Is there any empirical evidence to show that the designed modules do improve the effectiveness, diversity, and compatibility of programs?

We thank the reviewer for this insight. We discuss the evaluation of effectiveness, diversity, and compatibility below.

• Effectiveness: The ablation study in Section 5.3 and the experimental results presented in Table 1 serve as empirical evidences that demonstrate the efficacy of the proposed CEM+diversity searching paradigm.
• Diversity: Section 5.7 (Figures 21, 22, 23, and 24) provides multiple examples of the retrieved option program sets that cover diverse skills and subroutines for each given task.
• Compatibility: As suggested by the reviewer, to further investigate and quantify the compatibility among the retrieved programs, we conduct additional experiments of CEM+compatibility ×|M| (i.e., CEM with the evaluation function $G(z) = \frac{1}{D} \sum_{i=1}^{D} R_{\Psi_i}$, where the number of programs sequences $D$, the specified program sequence $\Psi_i$ and the normalized reward $R_{\Psi_i}$ are defined similarly as in Section 4.2.3 and Equation 1) for N = 1 time and select each of the result as the i-th option. Repeat the above process |M| times and take all |M| results as the set of programmatic options.

The results show that, across every task listed above, CEM+compatibility × |M| outperforms CEM × |M|, demonstrating the effectiveness of employing the proposed compatibility measure.

We thank the reviewer for inspiring us to conduct this experiment, and we will include the results in the revised paper.

While generating reusable subroutines is intuitive, there are no examples on how these low-level policies look like throughout the paper, making it a bit harder to concretely visualize how the policies look like. Adding a few examples, even in appendix, would make the process more interpretable.

We provide multiple examples in Figures 21, 22, 23, 24 in the appendix. These examples serve as concrete examples that explain what the agent will do by following these programmatic options. Taking Inf-DoorKey as an example, this task requires iterating between three different skills.

• The first skill is picking up the key in a chamber to open the door. Option 1 of this task, shown in Figure 23, is suitable for acquiring this skill since this program will check whether a key exists in the agent position and pick it up to open the door.
• The second skill is navigating inside and between chambers. Option 2 of this task, shown in Figure 23, is suitable for acquiring this skill since this program contains numerous tokens about moving and turning directions.
• The third skill is locating and placing the key in a specific position to open the door. Option 3 of this task, shown in Figure 23, is suitable for acquiring this skill since this program will first place the key and then pick it up.

By combining these skills with the help of the high-level policy controller, the agent can pick up or place keys in the correct places and navigate inside and between chambers.

Does the choice of DSL affect the performance of the proposed process? Would a less well-designed DSL cause the method to be ineffective?

As pointed out by the reviewer, the choice of DSL plays a vital role in the proposed framework. In this work, we choose Karel DSL because its semantics are designed to describe an agent’s behavior and how agents can observe and interact with the environment. Suboptimal DSLs (e.g., inaccurate tokens to indicate state or behavior) could lead to suboptimal programmatic policies. We will incorporate this discussion into the limitation section (Section J) in the paper revision.

We sincerely thank the reviewer for the thorough and constructive comments. Please find the response to your questions below.

The execution time will differ from program to program, but HiPO does not consider this factor while incorporating a discount factor 𝛾 of 0.99.

During the option retrieval process, the normalized reward defined in Equation 1 explicitly considers the execution time of each program in the sampled option sequence through the discount factor 𝛾 (i.e., distant reward will be discounted more than instant reward in each program execution). Therefore, the evaluation function $G$ introduced in Section 4.2.3 not only assesses the diversity and compatibility among different options, but also considers the variance of execution time of each option across lists of options sampled by the evaluation function. We will revise the paper to make it clear.

HiPO does not discount the cumulative reward of low-level actions

After retrieving a set of options, each option can be viewed as a “macro action” by the high-level policy, and executing each macro action takes a “macro timestep” (i.e., the beginning of the episode or after fully executing the selected option), as depicted in Figure 2(b). Since these options are fixed and deterministic sub-policies in sMDP, we use the cumulative reward of all the low-level actions from a program execution as the return of each macro action. This aligns with existing hierarchical RL literature [1,2,3].

The difference between the two settings, CEM+diversity top k and CEM+diversity x |M|, is unclear.

In CEM+diversity top k (k=|M|), we select the top k=|M| programs out of a total of N=10 CEM searches. On the other hand, CEM+diversity x |M| conducts |M| rounds of N=10 CEM search (a total of 10 x |M| CEM searches) and selects the best program in each round to get a total of |M| programs.

Note that when conducting the j-th CEM during the i-th CEM+diversity of CEM+diversity x |M|, the diversity multiplier is calculated based on the previous (i-1) retrieved programs and the current j programs. In comparison, the j-th CEM during CEM+diversity top k only considers the diversity among these j programs. We will revise the paper to make it clear.

The authors did not conduct experiments on the CEM + compatibility setting.

As suggested by the reviewer, we conduct additional experiments of CEM+compatibility ×|M|.

Across tasks listed above, CEM+compatibility × |M| performs better than CEM × |M|, showing the effectiveness of the compatibility measure on its own. For multi-stage tasks like Farmer and Inf-DoorKey, CEM+compatibility × |M| performs better than CEM+diversity top $k$ and CEM+diversity × |M|, indicating that the compatibility measure can help CEM more easily find skills suitable for multi-stages compared to the diversity measure. We will revise the paper to include this experiment.

The diversity of the embedding vectors does not necessarily guarantee the diversity in the actual behaviour.

We learn a program embedding space following Trivedi et al. [4]. The objective function features a latent behavior reconstruction loss, which aims to ensure that in the learned embedding space, similar behaviors are encoded closer and drastically different behaviors are encoded far from each other.

How different are the programs' actual behaviors in the final skill set?

Figures 21, 22, 23, and 24 present the retrieved options using our method. Taking Inf-DoorKey as an example, this task requires iterating between three skills:

• Picking up the key in a chamber to open the door. Option 1 in Figure 23 is suitable for acquiring the skill since this program will check whether a key exists in the agent position and pick it up to open the door.
• Navigating inside and between chambers. Option 2 in Figure 23 is suitable for acquiring the skill since this program contains numerous tokens about moving and turning directions.
• Locating and placing the key in a specific position to open the door. Option 3 in Figure 23 is suitable for acquiring the skill since this program will first place the key and then pick it up.

From Section A.2, it seems like at every step, the procedure selects one program through CEM. Wouldn't this approach cause the programs selected in the earlier stages to be sub-optimal?

The programs retrieved in the earlier stages could be suboptimal, which motivates us to design the diversity and compatibility rewards to ensure the performance of the retrieved programs as a whole. Despite the potential suboptimal retrieved programs, the experimental results in Sections 5.2, 5.3, and 5.4 show that the high-level policy can effectively reuse programmatic options selected by the proposed procedure, outperforming the baselines.

---

References:

[1] Ofir Nachum, Shixiang Gu, Honglak Lee, and Sergey Levine. Data-efficient hierarchical reinforcement learning. In NeurIPS, 2018.

[2] Kevin Frans, Jonathan Ho, Xi Chen, Pieter Abbeel, and John Schulman. Meta learning shared hierarchies. In ICLR, 2018.

[3] Youngwoon Lee, Jingyun Yang, and Joseph J. Lim. Learning to coordinate manipulation skills via skill behavior diversification. In ICLR, 2020.

[4] Dweep Trivedi, Jesse Zhang, Shao-Hua Sun, and Joseph J Lim. Learning to synthesize programs as interpretable and generalizable policies. In NeurIPS, 2021.

We would like to express our sincere gratitude to the reviewer for the thorough and constructive feedback. We are confident that our responses adequately address the concerns raised by the reviewer, including the following points.

• A discussion of discount factors in our hierarchical RL setup
• A clarification of the two settings, CEM+diversity top k and CEM+diversity x |M|
• Additional results of CEM + compatibility
• An explanation of diversity in program embeddings and behaviors
• A discussion of suboptimal retrieved programs

Please kindly let us know if the reviewer has any additional concerns or if further experimental results are required. We are fully committed to resolving any potential issues, should time permit. Again, we thank the reviewer for all the detailed review and the time the reviewer put into helping us to improve our submission.

1) (0, 1, 0, 1, 0, 1), (0, 1)
2) (0, 1), (0, 1), (0, 1), (0, 1.01) 

We sincerely thank the reviewer for the thorough and constructive comments. Please find the response to your questions below.

A dedicated Limitation section could clearly help situate the advantages and drawback of HIPO, and compare it to other methods. Authors could step a little bit outside programmatic and look into e.g. interpretable logic-based RL [1, 2, 9, 10], interpretable RL methods that use LLM [3], tree-based policies [8, 5, 6, 7], ... etc.

We thank the reviewer for providing the references and suggestions. We will revise the paper to discuss these works by adding a dedicated section or merging it with Section J, which points out the challenges of DSL design and the interpretability-performance tradeoff.

Interpretability allows to detect invisible suboptimal behaviors

We thank the reviewer for this insight. We totally agree that interpretability can help detect misaligned policies. We will revise the paper to incorporate this discussion.

Authors could slightly modify your method name (if they wish). Your methods' name might collide with Hierarchical Proximal Policy Optimization (HIPPO), an existing known option learning framework.

We thank the reviewer for the suggestion. We will try to adjust the name of our method to avoid potential confusion.

It might be insightful to test the generalizability of the different methods (by varying size, of the environment).

In Section 5.6, we evaluate the ability to inductive generalization in testing Karel-Long environments with longer horizons than training environments. Table 4(b) indicates that HIPO generalizes better to the testing environments with significantly extended horizons compared to the baselines.

We will add other different generalization settings (e.g., varying size of the environment) to further testify the proposed framework in the revision.

I am not sure if the option is returning a terminal token or if the high level controller is reselecting an option at each timestep.

As detailed in Figure 2 and Section 4.3, the high-level controller will reselect an option after the previously selected programmatic option is executed and terminated. After executing the selected programmatic option, the high-level policy will receive the execution trace (i.e., a series of (state, action, reward) tuples) collected during the program execution. Based on the final state in the execution trace and the current selected programmatic option, the high-level policy will choose the next programmatic option. We will revise the paper to make this clear.

What's the percentage of retrieved program (based on your effectiveness and diversity criterion)?

The theoretical search space of each programmatic option is about $30^{40}$, i.e., the token space size to the power of program length. Throughout the experiments conducted in this paper, we sample approximately 50000 unique programs according to our effectiveness and diversity criteria to solve a given task, which only takes up a small fraction of the total program space; therefore, an effective retrieval method is essential.

We sincerely thank the reviewer for the thorough and constructive comments. Please find the response to your questions below.

Option-learning baselines

As suggested by the reviewer, we additionally experimented with the option-critic architecture [1] and reported the comparison to our method below.

The results show that our method outperforms option-critic on all the Karel-Long tasks. Option-critic performs poorly on all tasks except for Inf-Harvester, likely because of the sparse rewards nature of these tasks and the environment's per-action cost, possibly forcing the options to be trained to terminate quickly. We will revise the paper to include this result.

Search in the programmatic space

As suggested by the reviewer, we conduct additional experiments that search directly in the programmatic space using the hill climbing (HC) approach proposed by Carvalho et al. [2].

The results show that searching directly in the programmatic space can achieve better performance on tasks with denser rewards, e.g., Inf-Harvester. On the other hand, HIPO performs better on sparse-reward tasks requiring diverse skills. We will revise the paper to include this baseline.

Environment-step sample efficiency

We thank the reviewer for the suggestion. We will add this plot to the revised paper.

More runs of the experiments >30 and confidence intervals

We thank the reviewer for the suggestion. We presented standard deviations with five random seeds following the standard practice in RL literature. We will add more runs and show confidence intervals in the revision.

Performance of HIPO in DoorKey

The diversity multiplier encourages exploring programs of different behaviors during the search process. Therefore, after retrieving the program that "find the key" as the first option, other behaviors like "navigating" or "put maker" will be more likely to be retrieved as the second option.

Due to the consideration among the options, it is possible to sample some option execution orders that are able to solve the problem following the evaluation function defined in Section 4.2.3. If one program can be stitched together with retrieved options in some specific order to solve the program, then the evaluation function will return a high score for this new option.

Best order used in the composability step

As suggested by the reviewer, we report the return obtained by executing the best random sequence order found in the compatibility step during the search of CEM+diversity+compatibility.

The results show that, without the high-level policy, executing options with a specific sequence can already achieve a good performance on tasks with short-horizon or denser reward tasks requiring fewer skills, e.g., DoorKey and Inf-Harvester. On the other hand, HIPO performs better on long-horizon and sparse-reward tasks, indicating the necessity of integrating the high-level policy with the option searching process when solving repetitive and long tasks.

Termination option

We implement the termination option as a “do nothing” low-level policy, i.e., an empty program, that triggers null action to avoid the per-action cost as described in Section H, which urges the agent to solve the tasks as efficiently as possible by reducing redundant actions. That said, as pointed out by the reviewer, the MDP decides when to terminate, and the agent can learn to take null action to avoid action costs.

A short program that is able to collect an arbitrary number of markers

Yes, it is possible to find a short program that collects an arbitrary number of markers in the Inf-Harvester task. Despite the long-horizon nature of this task, it only requires repeatedly traversing and picking markers, which can be easily encapsulated by short programs with a small number of primitive actions inside an outer WHILE control statement.

I would like to challenge the desiderata of the options (lines 136-139).

We thank the reviewer for the insight. We will remove “(i.e., obtain some task rewards)” from the definition of effectiveness.

Diversity score for programmatic spaces

We think it is not trivial to define the diversity score in a programmatic space. Specifically, taking the programmatic space defined by abstract syntax trees (ASTs) proposed in Carvalho et al. [2] as an example, it is not clear how we can compute the distance between a pair of ASTs. Exploring how the diversity score can be defined in programmatic spaces is an interesting future direction.

---

References:

[1] Pierre-Luc Bacon, Jean Harb, and Doina Precup. The option-critic architecture. In Association for the Advancement of Artificial Intelligence, 2017.

[2] Tales Henrique Carvalho, Kenneth Tjhia, and Levi Lelis. Reclaiming the source of programmatic policies: Programmatic versus latent spaces. In ICLR, 2024.