Hierarchical Programmatic Option Framework

Authors: yu-an  lin
chen-tao  lee
chih-han  yang
guan-ting  liu
shao-hua  sun
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-12 19:44:09

Abstract: Deep reinforcement learning aims to learn deep neural network policies to solve large-scale decision-making problems. However, approximating policies using deep neural networks makes it difficult to interpret the learned decision-making process. To address this issue, prior works (Trivedi et al., 2021; Liu et al., 2023; Carvalho et al., 2024) proposed to use human-readable programs as policies to increase the interpretability of the decision-making pipeline. Nevertheless, programmatic policies generated by these methods struggle to effectively solve long and repetitive RL tasks and cannot generalize to even longer horizons during testing. To solve these problems, we propose the Hierarchical Programmatic Option framework (HIPO), which aims to solve long and repetitive RL problems with human-readable programs as options (low-level policies). Specifically, we propose a method that retrieves a set of effective, diverse, and compatible programs as options. Then, we learn a high-level policy to effectively reuse these programmatic options to solve reoccurring subtasks. Our proposed framework outperforms programmatic RL and deep RL baselines on various tasks. Ablation studies justify the effectiveness of our proposed search algorithm for retrieving a set of programmatic options.

Main paper: 
 introduction: 
 Deep reinforcement learning (deep RL) has recently achieved tremendous success in various domains, such as controlling robots [26, 31] , playing strategy board games [67, 68] , and mastering video games [78, 82] . However, neural network policies learned by deep RL methods are not humaninterpretable, and their black-box nature poses challenges in scrutinizing model decisions and establishing user trust [45, 64] . Moreover, deep RL policies often suffer from overfitting and struggle to generalize to novel scenarios [17, 84] , limiting their applicability in the context of most real-world applications.To address these issues, programmatic RL frameworks [10, 46, 74] were proposed to represent policies as programs that detail task-solving procedures in a formal programming language. Particularly, Trivedi et al. [74] and Liu et al. [46] synthesize programs from continuous latent spaces, whereas Carvalho et al. [10] search programs directly from discrete programmatic spaces. Such program policies are human-readable and demonstrate significantly improved zero-shot generalizability from smaller state spaces to larger ones. Despite encouraging results, prior programmatic RL frameworks are limited to generating concise programs that can only tackle short-horizon tasks. Particularly for long-horizon RL problems like robotic manipulation [2, 8] and autonomous driving [55, 58] , these tasks consist of reoccurring subtasks and sparse rewards, necessitating a significant number of actions to be fully resolved. Therefore, the RL agent needs to learn a diverse and reusable set of skills to solve such tasks effectively.Aiming to solve long and repetitive tasks with better policy interpretability, we borrow ideas from the option frameworks [4, 51, 66, 72] and latent-space-based programmatic RL frameworks [46, 74] . With that in mind, we propose the Hierarchical Programmatic Option framework (HIPO), which utilizes a set of programs with diverse skills as options (programmatic options) and learn a high-level policy to determine which programmatic option to be used based on the current state and the current option. By switching between these programmatic options, HIPO can reuse the skills encapsulated in these options to tackle long-horizon tasks with an arbitrary number of repeating subroutines.Our framework contains three stages. (1) Constructing a program embedding space: To establish a program embedding space that smoothly and continuously parameterizes programs with diverse behaviors, we adopt the method proposed by Trivedi et al. [74] . (2) Retrieving a diverse set of effective and reusable programmatic options: We introduce a searching algorithm to retrieve a set of programmatic options from the learned program embedding space. Each programmatic option can be executed in the MDP and achieve satisfactory performance; more importantly, these programs are compatible and can be sequentially executed in any order. (3) Learning a high-level policy: To alter between a set of programmatic options, the high-level policy represented by neural networks takes the current environment state and the current programmatic option as input to predict the next programmatic option. This high-level policy can be learned using RL algorithms with the goal of maximizing the task return from the MDP.To evaluate our proposed HIPO framework, we adopt the Karel domain [56] , which characterizes an agent that navigates a grid world and interacts with objects. HIPO outperforms prior programmatic reinforcement learning and deep RL baselines on existing benchmarks [46, 74] . To further evaluate the performance and generalization ability to even longer horizons, we design a new set of tasks consisting of an arbitrary number of subtasks. Our framework shows better generalization in testing environments of different lengths. Ablation studies are also conducted to demonstrate the effectiveness of the proposed programmatic options retrieving process. 
related work: 
 Program synthesis. Program synthesis techniques revolve around program generation to convert given inputs into desired outputs. These methods have demonstrated notable successes across diverse domains such as array and tensor manipulation [5, 22] , string transformation [20, 29, 85] , generating computer commands [44] and code [11, 42] , graphics and 3D shape modeling [48, 73, 81] , and describing agent behaviors [9, 13, 43, 69, 70] . Most program synthesis methods focus on task specifications such as input/output pairs, demonstrations, or language descriptions; in contrast, this work aims to synthesize human-readable programs as options to solve reinforcement learning tasks.Programmatic reinforcement learning. Programmatic reinforcement learning methods [16, 80] explore structured representations for representing RL policies, including decision trees [7, 35] , state machines [32] , symbolic expressions [19, 33, 39, 49, 50, 83] , and programs [1, 75, 76] . Liu et al. [46] , Medeiros et al. [52] , Moraes and Lelis [53] , Trivedi et al. [74] , and Carvalho et al. [10] attempted to produce policies described by domain-specific language programs to solve simple RL tasks. We aim to take a step toward addressing complex, long-horizon, repetitive tasks.Hierarchical reinforcement learning. Hierarchical Reinforcement Learning (HRL) frameworks [4, 6, 40, 72, 77] focus on learning and operating across different levels of temporal abstraction, enhancing the efficiency of learning and exploration, particularly in sparse-reward environments. In this work, our proposed HIPO shares the same spirit with HRL frameworks [18, 21, 24, 25, 62, 63] that learn reusable skills as options. Instead of learning uninterpretable options as low-level policies, our framework aims to retrieve reusable and interpretable programs as options. 
problem formulation: 
 Our goal is to devise a framework that generates a set of programs as options (low-level policies) and integrates them with high-level policies to tackle complex, long-term tasks defined by Markov Decision Processes (MDPs). To this end, we first synthesize a set of task-solving, diverse, compatible programs, then train a high-level policy to iteratively select and execute programs. Domain specific language. This work adopts the domain-specific language (DSL) of the Karel domain [9, 13, 74] , as illustrated in Figure 1 . This DSL describes the control flows as well as the perception and actions of the Karel agent. Actions including move, turnRight, and putMarker define how the agent can interact with the environment. Perceptions, such as frontIsClear and markerPresent, formulate how the agent observes the environment. Control flows, e.g., if, else, while, enable representing divergent and repetitive behaviors. Furthermore, Boolean and logical operators like and, or, and not allow for composing more intricate conditions. This work uses programs structured in this DSL to construct programmatic options. Markov Decision Process (MDP). The tasks considered in this work can be formulated as finite-horizon discounted Markov Decision Processes (MDPs). The performance of HIPO is evaluated based on the execution traces of a series of programs (programmatic options) selected by its high-level policy. The rollout of a program ρ consists of a T -step sequence of state-action pairs {(s t , a t )} t=1, ..., T obtained from a program executor EXEC(•) that executes program ρ to interact with an environment, resulting in the discounted return T t=0 γ t (r t ), where r t = R(s t , a t ) denotes the reward function. We aim to maximize the total rewards by executing a series of programs following the high-level policy.Hierarchical Programmatic Option Framework. The proposed hierarchical framework consists of a set of programmatic options M = {m k } k=1, ...,|M | as low-level policies and a high-level policy f ϕ that sequentially chooses one option at a time. Each option m i encapsulates a human-readable program ρ mi that will be executed if selected by the high-level policy f ϕ . On the other hand, the high-level policy f ϕ (m i , s i T i ) outputs the probability distribution over all programmatic options M , given the last selected programmatic option m i at timestep T i and the current MDP state s i T i . If the next option m i+1 sampled from the distribution is the termination mode m term , the rollout will be terminated. Otherwise, the corresponding programmatic option ρ m i+1 will be executed and generates a sequence of state-action pairs {(s i+1 t , a i+1 t )} t=1, ..., T i+1 before the high-level policy f ϕ selects the next programmatic option m i+2 . 
approach: 
 We design a three-stage framework to search programmatic options and train a high-level policy represented by neural networks. The main goal is to maximize the return given a task described by an MDP. Firstly, as introduced in Section 4.1, we construct a program embedding space parameterizing programs smoothly and continuously with diverse behaviors. Then, Section 4.2 presents a method that retrieves a set of effective, diverse, and compatible programmatic options. Given retrieved programmatic options, Section 4.3 describes learning the high-level policy to determine probability distributions for options sampling. An overview of the proposed framework is illustrated in Figure 2 .We follow the approach and the program dataset specified in Trivedi et al. [74] to learn a program embedding space that smoothly and continuously parameterizes programs with diverse behaviors. The training objectives include a VAE loss and two losses that encourage learning a behaviorally smooth program embedding space. Once trained, we can use the learned decoder p θ to map any program embedding z to a program ρ z = p θ (z) consisting of a sequence of program tokens. Details on the program dataset generation and the encoder-decoder training can be found in Section E.1.1.With a program embedding space, we aim to retrieve a set of programs (programmatic options) given a task. This set of programs should have the following properties. Learning the high-level policy. Given the current environment state s and the current programmatic option mi, the high-level policy outputs a probability distribution over all programmatic options, aiming to maximize the total accumulative reward from the environment.zi∈Zk z ⋅ z i ∥z∥∥z i ∥ ) R Ψi = 1 | Ψ i | |Ψi| ∑ j=1 T j ∑ t=0 γ t 𝔼 (st,at)∼EXEC(Ψi[ j]) [r t ] × Evaluate Each Candidate Program High-level Policy f ϕ Environment s i+1 r i+1 s i t a i t [s i 1 , . . . , s i T i ] [r i 1 , . . . , r i T i ] [-1] ⋅ Σ• Effectiveness: Each program can solve the task to some extent.• Diversity: The more behaviorally diverse the programs are, the richer behaviors can be captured.• Compatibility: Sequentially executing some programs with specific orders can potentially lead to improved task performance.To obtain a task-solving program, we can apply the Cross-Entropy Method [59] , iteratively searching in a learned program embedding space [74] in the following procedure:(1) Randomly initialize a program embedding vector z r as the search center.(2) Add random noises to z r to generate a population of program embeddings Z = {z i } i=1,...,n , where n denotes the population size.(3) Evaluate every program embedding z ∈ Z with the evaluation function G to get a list of fitness score [G(z i )] i=1,...,n .(4) Average the top k program embeddings in Z according to fitness scores [G(z i )] i=1,...,n and assign it to the search center z r .(5) Repeat ( 2) to (4) until the fitness score G(z r ) of z r converges or the maximum number of steps is reached.Since we aim to retrieve a set of effective programs, we can define the evaluation function as the program execution return of a decoded program embedding, i.e., G(z)= T t=0 γ t E (st,at)∼EXEC(ρz) [r t ].To retrieve a set of |M | programmatic options for a high-level policy, we deploy this CEM search N times, take |M | best program embeddings, and obtain the decoded program set {ρ zr i = p θ (z ri )} i=1,...,|M | . Please refer to Section A.1 for more details and the CEM search pseudo-code.In our proposal, we retrieve a set of programmatic options for a high-level policy. Hence, the diversity of behaviors of the retreived program set endow HIPO with versatility. However, by running the CEM search for |M | times, the obtained program set can have low diversity, making the multiskill-demanding tasks unsolvable.To address this issue, we propose the diversity multiplier that accounts previous search results to encourage diversity among the retrieved programs. The evaluation of program employing the diversity multiplier is illustrated in Figure 2 . Specifically, during the (k + 1)st CEM search, each program embedding z is evaluated by G(z, Z k ) = ( T t=0 γ t E (st,at)∼EXEC(ρz) [r t ]) • diversity(z, Z k ), where diversity(z, Z k ) is the proposed diversity multiplier defined as Sigmoid(-max zi∈Z k z•zi ∥z∥∥zi∥ ). Thus, the program execution return is scaled down by diversity(z, Z k ) based on the maximum cosine similarity between z and the retrieved program embeddings Z k = {z i } i=1,...,k from the previous k CEM searches, diverging the current program embedding from previously retrieved programs.To retrieve a set of |M | programmatic options for our high-level policy, we deploy this CEM+diversity search N times, take |M | best program embeddings, and obtain the decoded program set. The procedure and the search trajectory visualization can be found in Section A.2.The proposed HIPO executes a sequence of programmatic options determined by a high-level policy. Therefore, these programs shall be compatible with each other, i.e., executing a program following the execution of other programs could improve task performance. Yet, CEM+diversity discussed in Section 4.2.2 searches every program independently.Accounting for the compatibility among programs while searching, we propose an evaluation method, CEM+diversity+compatibility. To evaluate the program embedding z, we take the decoded program ρ z as the (k + 1)st option. Then, lists of programs Ψ i,i=1,...,D are sampled with replacements from determined k options and the (k + 1)st option. Each program list Ψ i contains at least one (k + 1)st option to consider the compatibility between the (k + 1)st and previously determined k options. The return is computed by sequentially executing these D sequences of programs and multiply the result with the diversity multiplier proposed in Section 4.2.2. As the result, the evaluation function isG(z, Z k ) = 1 D D i=1 R Ψi • diversity(z, Z k ), where R Ψi is the normalized reward obtained from executing all programs in the specified program sequence Ψ i :EQUATIONwith |Ψ i | being the number of programs in the program sequence Ψ i , Ψ i [j] being the j-th program, and γ as the discount factor.The search method with the specified evaluation is deployed |M | times to obtain a set of programs that are effective, diverse, and compatible with each other, adopted by the high-level policy as programmatic options. Please refer to Section A.3 for more details and the thorough procedure.Given a set of programmatic options M = {m k } k=1, ..., |M | , we formulate learning a high-level policy f ϕ represented by neural networks, as a reinforcement learning problem aiming to maximize the task return. At the i-th high-level step, given the latest selected programmatic option m i and the current environment state s, the high-level policy f ϕ (m i , s) outputs the probability distribution of programmatic options for the next option m i+1 ∈ m term ∪ {m k } k=1, ..., |M | , where m term denotes the termination option that ends the episode once selected. Otherwise, the corresponding program ρ m i+1 is executed, yielding the next state s i+1 T i+1 and the cumulative reward r i+1 = T i+1 t=1 r i+1 t . Note that the last state s i+1 T i+1 of the state sequence is returned by EXEC(ρ m i+1 ), with T i+1 denoting the horizon of the i + 1-th program execution. Also, the cumulative reward r i+1 obtained within a single program execution is not discounted.Note that a single program execution EXEC(ρ) will terminate after complete execution or the number of function calls emitted during EXEC(ρ) reaches 220, which aligns to the setting in Trivedi et al. These tasks necessitate learning diverse, repetitive, and task-specific skills. For example, in our designed INF-HARVESTER, the agent needs to traverse the whole map and pick nearly 400 markers to solve the tasks since the environment randomly generates markers; in contrast, the HARVESTER from the KAREL problem set [74] can be solved by picking merely 36 markers.[74]. This iterative process stops once the termination option is sampled or the maximum number of the option-selection steps is reached. Please refer to Section E.1.3 for training details.To further enhance the explainability of the high-level policy, we apply the approach proposed by Koul et al. [36] to extract the state machine structure from the learned high-level policy. Combining the retrieved set of programmatic options and the extracted state machine structure, our framework is capable of solving long-horizon tasks while being self-explanatory. Examples of extracted state machines are illustrated in Section D. 
experiments: 
 We aim to answer the following questions with the experiments and ablation studies. ( Please refer to Section E for hyperparameter settings for the following experiments.To this end, we consider the Karel domain [56] , which is widely adopted in program synthesis [9, 13, 65, 70] and programmatic reinforcement learning [46, 74] . Specifically, we utilize the KAREL problem set [74] and the KAREL-HARD problem set [46] . The KAREL problem set includes six basic tasks, each of which can be solved by a short program (less than 45 tokens), with a horizon shorter than 200 steps per episode. On the other hand, the four tasks introduced in the KAREL-HARD problem require longer, more complex programs (i.e., 45 to 120 tokens) in longer execution horizons (i.e., up to 500 actions). Details on two problem sets is provided in Section F and Section G.KAREL-LONG problem set. Since most of the tasks in the KAREL and KAREL-HARD problem sets are short-horizon tasks (i.e., can be finished in less than 500 timesteps), they are not suitable for evaluating long-horizon task-solving ability (i.e., tasks requiring more than 3000 timesteps to finish). Hence, we introduce a newly designed KAREL-LONG problem set as the benchmark to evaluate the capability of HIPO.As illustrated in Figure 3 , the tasks require the agent to fulfill extra constraints (e.g., not placing multiple markers on the same spot in FARMER, receiving penalties imposed for not moving along the stairs in UP-N-DOWN) and conduct extended exploration (e.g., repetitively locating and collecting markers in SEESAW, INF-DOORKEY, and INF-HARVESTER). More details on the KAREL-LONG tasks can be found in Section H.We aim to investigate whether our proposed diversity multiplier can enhance CEM and yield programs with improved performance. To this end, for each KAREL or KAREL-HARD task, we use CEM and CEM 0.45 ± 0.40 0.81 ± 0.07 0.18 ± 0.14 1.00 ± 0.00 0.45 ± 0.28 1.00 ± 0.00 0.50 ± 0.00 0.65 ± 0.19 0.51 ± 0.21 0.21 ± 0.15 CEM+diversity 1.00 ± 0.00 1.00 ± 0.00 0.37 ± 0.06 1.00 ± 0.00 0.80 ± 0.07 1.00 ± 0.00 0.50 ± 0.00 0.62 ± 0.01 0.69 ± 0.07 0.36 ± 0.02 DRL 0.29 ± 0.05 0.32 ± 0.07 0.00 ± 0.00 1.00 ± 0.00 0.90 ± 0.10 1.00 ± 0.00 0.48 ± 0.03 0.89 ± 0.04 0.96 ± 0.02 0.67 ± 0.17 LEAPS 0.45 ± 0.40 0.81 ± 0.07 0.18 ± 0.14 1.00 ± 0.00 0.45 ± 0.28 1.00 ± 0.00 0.50 ± 0.00 0.65 ± 0.19 0.51 ± 0.21 0.21 ± 0.15 HPRL 1.00 ± 0.00 1.00 ± 0.00 1.00 ± 0.00 1.00 ± 0.00 1.00 ± 0.00 1.00 ± 0.00 0.50 ± 0.00 0.80 ± 0.02 0.58 ± 0.07 0.28 ± 0.11 HIPO (Ours) 1.00 ± 0.00 1.00 ± 0.00 1.00 ± 0.00 1.00 ± 0.00 1.00 ± 0.00 1.00 ± 0.00 1.00 ± 0.00 0.62 ± 0.01 0.97 ± 0.02 0.36 ± 0.02CEM+diversity to find 10 programs. Then, for each task, we evaluate all the programs and report the best performance in Table 1 . The results suggest that our proposed CEM+diversity achieves better performance on most of the tasks, highlighting the improved search quality induced by covering wider regions in the search space with the diversity multiplier. Visualized search trajectories of CEM+diversity can be found in Section A.2.We propose CEM+diversity+compatibility to retrieve a set of effective, diverse, compatible programmatic options for our high-level policy. In this section, we compare a variety of implementations regarding the diversity and the compatibility of programs.• CEM ×|M |: Conduct the CEM search described in Section 4. • HIPO (ours): Conduct CEM+diversity+compatibility (i.e., CEM with the diversity multiplier and R Ψ as described in Section 4.2.3) for N = 10 times and select the best result as the i th option. Repeat the above process |M | times and take all |M | results as the set of programmatic options.The number of programmatic options |M | is 3 for SEESAW, UP-N-DOWN, and INF-HARVESTER and 5 for FARMER and INF-DOORKEY. We assess the quality of the retrieved programmatic options by evaluating the performance of the high-level policy learned with these option sets on the KAREL-LONG tasks. The results presented in Table 2 indicate that our proposed framework, HIPO, outperforms its variants that ignore diversity or compatibility among programmatic options on all the tasks. This justifies our proposed CEM+diversity+compatibility method for retrieving a set of effective, diverse, compatible programs as options for the high-level policy.We compare our proposed framework and its variant to state-of-the-art deep RL and programmatic RL methods on the KAREL-LONG tasks.• Random transition uses the same set of programmatic options as our method but with a random high-level policy (i.e., uniformly randomly select the next option at each step). The performance of this method examines the necessity of learning a high-level policy. where the x-axis is the total number of executed programs for interacting with the environment, and the y-axis is the maximum validation return. This demonstrates that our proposed framework has better program sample efficiency and converges to better performance. (b) Inductive generalization performance. We evaluate and report the performance drop in the testing environments with an extended horizon, where the x-axis is the extended horizon length compared to the horizon of the training environments, and the y-axis is the performance drop in percentage. Our proposed framework can inductively generalize to longer horizons without any fine-tuning.• Primitive actions as options (PAO) learns a high-level policy similar to HIPO, which takes the current option and environment state as input and predicts the next option. However, it utilizes primitive actions (e.g., move, pickMarker) as options. This baseline highlights the necessity of retrieving programs with higher-level behaviors as options.• DRL represents a policy as a neural network and is learned using PPO [61] . The policy takes raw states (i.e., Karel grids) as input and predicts the probability distribution over the set of primitive actions, (e.g., move, pickMarker).• Option-Critic represents a policy that both high-level and low-level policies are neural networks and is learned using the option-critic architecture [4] . The policy takes raw states (i.e., Karel grids) as input, and each option predicts the probability distribution over the set of primitive actions (e.g., move, pickMarker).• Learning Embeddings for Latent Program Synthesis (LEAPS) [74] searches for a single task-solving program using the vanilla CEM in a learned program embedding space.• Hierarchical Programmatic Reinforcement Learning (HPRL) [46] learns a meta-policy, whose action space is a learned program embedding space, to compose a series of programs as the policy.• Hill Climbing (HC) [10] is a stochastic search technique that operates directly within the program space. The process begins by randomly modifying portions of the current program to generate a set of neighboring candidates. The program that performs best among these neighbors is selected as the next candidate for exploration.As Table 1 shows, HIPO outperforms LEAPS and HPRL on 8 out of 10 tasks from the KAREL and KAREL-HARD tasks, indicating that the retrieved programs are truly effective at solving short horizon tasks (i.e., less than 500 actions). For long-horizon tasks that require more than 3000 actions to solve, Table 2 shows that HIPO excels on four tasks, with better performance on FARMER and particular prowess in SEESAW, UP-N-DOWN, and INF-DOORKEY.Two of these tasks require distinct skills (e.g., pick and put markers in FARMER; go up and downstairs in UP-N-DOWN) and the capability to persistently execute one skill for an extended period before transitioning to another. HIPO adeptly addresses this challenge due to the consideration of diversity while seeking programmatic options, ensuring the acquisition of both skills concurrently.Unlike the other tasks, SEESAW and INF-DOORKEY require an extended traverse to collect markers, leading to a sparser reward distribution. During the searching phase of programmatic options, emphasizing compatibility enables HIPO to secure a set of mutually compatible options that work together effectively to accomplish the extended traversal.Retrieved programs are provided in Appendix (Figure 22 , Figure 23 , Figure 24 , and Figure 25 ). Experimental results on programmatic policy baselines over 32 seeds are provided in Table 3 .To accurately evaluate the sample efficiency of programmatic RL methods, we propose the program sample efficiency metric, measuring the total number of program executions required to learn a program policy. We report the program sample efficiency of LEAPS, HPRL, HC, and HIPO on FARMER and INF-HARVESTER in Figure 4a . As the results show, HIPO demonstrates program sample efficiency than LEAPS and HPRL, indicating that our framework requires fewer program interactions with the environment and lower computational costs compared to existing latent-spacebased programmatic RL frameworks. More details and the action sample efficiency can be found in Section B and Figure 8 .We aim to compare the inductive generalization ability among all the methods, generalizing to out-of-distributionally (i.e., unseen during training) long task instances [32] . To this end, we increase the expected horizons of FARMER and INF-HARVESTER by 2×, 4×, 8×, and 16×. Then, we report the performance drop compared to the original task performance of selected baselines in Figure 4b . More details on extending task horizons are provided in Section C.The results show that HIPO suffers a fewer decline in performance in testing environments with significantly extended horizons than LEAPS and HPRL, suggesting that HIPO exhibits better inductive generalization in these tasks. The longest execution of HIPO ran up to 48k environment steps.In the proposed framework, we retrieve a set of programmatic options that can be reused by the highlevel policy to solve long and repetitive tasks. For example, in INF-DOORKEY (detailed in Section H), the retrieved programmatic options are presented in Figure 24 . Based on these programmatic options, the high-level policy can reuse them to guide the agent to traverse all four chambers with the following sequence of programmatic options:τ m = {m 5 , m 3 , m 5 , m 3 , m 1 , m 4 , m 4 , m 2 , m 5 , m 4 , m 5 }.INF-DOORKEY requires three different skills to solve: picking a marker to open the door in some chambers, placing a marker to open the door in some other chambers, and navigating between the chambers. Specifically, the programs provided in Figure 24 show that Option 1 and Option 5 fulfill the first skill, while Option 3, Option 4, and Option 5 meet the requirements for the second, and Option 2 satisfy the third. Along with the observation, we could fully interpret the agent policy with the control flows, perceptions, and actions specified in the program. On the other hand, the high-level policy is a neural network by itself, making it hard to interpret the option transition dynamic learned by the high-level policy.To improve the interpretability of our high-level policy, we extract state machine structures from the high-level policy to visualize the option transition dynamics. More details and examples of extracted state machines can be found in Section D. 
conclusion: 
 This work aims to construct reinforcement learning policies that are human-interpretable and generalizable, bridging from hierarchical reinforcement learning to programmatic options. Consequently, we propose the Hierarchical Programmatic Option framework (HIPO) to represent complex behaviors and address long-horizon tasks. Specifically, we introduce a method that can retrieve a set of effective, diverse, compatible programs by modifying the Cross Entropy Method (CEM). Following this, these programs are applied as options by the high-level policy learned with reinforcement learning. To evaluate HIPO's ability in extended horizons, we design a set of tasks that require thousands of steps in the Karel domain. Our framework HIPO outperforms various deep RL and programmatic RL methods on various tasks. In addition, HIPO demonstrates good performance in inductive generalization to even longer horizons without fine-tuning. Last but not least, extensive ablation studies justify the effectiveness of our proposed search algorithm in retrieving programmatic options. The procedure of running CEM+diversity N times is as follows:(1) Search the 1st program embedding z 1 by CEM (G, g = (Z k : {}))(2) Search the 2nd program embedding z 2 by CEM (G, g = (Z k :{z 1 })) ... (N) Search the N th program embedding z N by CEM (G, g = (Z k : {z 1 , ..., z N -1 })) Z k is the set of retrieved program embeddings {z i } i=1,...,k-1 from the previous (k -1) CEM searches. The evaluation function is G(z, Z k ) = ( T t=0 γ t E (st,at)∼EXEC(ρz) [r t ]) • diversity(z, Z k ), where diversity(z, Z k ) = Sigmoid(-max zi∈Z k z•zi ∥z∥∥zi∥ ).Searching trajectories shown in Figure 6 exemplifies the influence of the diversity factor. for i ← 1 to n do 8: ε ← [ε 0 , ε 1 , ..., ε i , ..., ε 255 ], ε i ∼ N (0, σ) 9:Z.append(z r + ε)  
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: The paper poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes] Justification: The original publications that produced the assets are cited.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. 
 
 Appendix: In the subsequent section, we outline the procedure for sampling a program sequence Ψ from k previously determined programs ρ i,i=1,...,k during the search of the (k + 1)st program ρ k+1 .(1) Uniformly sample a program ρ j from all k + 1 programs {ρ 1 , ..., ρ k , ρ k+1 }, and add ρ j to Ψ.(2) Repeat (1) until the (k + 1)st program ρ k+1 is sampled.(3) Uniformly sample a program ρ j from {ρ 1 , ..., ρ k , ρ k+1 , ρ term }, where ρ term represents the termination program, then append ρ j to Ψ.(4) Repeat (3) until ρ term is sampled.(5) Return Ψ with length greater or equal to L min , where L min is a hyperparameter that indicates the minimum length of a sampled sequence. Re-sample Ψ otherwise.The score function G(z, Z k ) for CEM+diversity+compatibility: EQUATIONEQUATIONGenerally speaking, programmatic RL approaches incorporate a three-step training procedure, in which a program will be first synthesized, exectued, then evaluated with respect to a given task. The three-step procedure is iteratively applied until the return converges or the maximum training step is reached. "Program Sample Efficiency"-referring to how effectively the method achieves a desired return using an efficient number of the three-step procedure-is crucial for analyzing and comparing the efficiency of our approaches against the baselines. As Figure 7 illustrates, HIPO (our method) obtains the best program sampling efficiency in FARMER and INF-DOORKEY. Details of the program sample efficiency calculation for each baseline are elaborated in the subsequent sections.In the program searching phase of HIPO, up to 50 CEM-searches are conducted to fetch programmatic options. Each CEM-search involves a maximum of 1000 search iterations, in which the three-step procedure (synthesis, execution, and evaluation) is executed n times, where n is the population size of the CEM-search. In the first phase of the efficiency curve of our method (indicated by the yellow curve in Figure 7 ), the return is counted as the highest return obtained from a sequential execution of the programmatic options, based on the order indicated by the sampled random sequence.Afterward, during the high-level policy training phase (indicated by the red curve in Figure 7 ), the three-step procedure is executed once per PPO training step. The return is recorded as the maximum validation return achieved in the HIPO manner, where the high-level policy continuously selects and deploys a program to solve a long-horizon task.In the program searching process of LEAPS, 216 CEM-searches are performed to obtain the targeted program, in accordance with the settings in [74] . In each CEM-search, up to 1000 iterations are performed, in which the three-step procedure is executed n times, where n is the population size of the CEM-search. The return for a certain number of executed programs is recorded as the maximum return obtained from executing the previously searched programs only.During the meta-policy training process of HPRL, the three-step procedure is performed once per PPO training step. Therefore, with the exact experiment settings described in Section E.6, the three-step procedure would be executed 25M times at the end of the training process. The return for a certain number of executed programs is recorded as the maximum return achieved in the cascaded execution of 5 programs, decoded from the latent program embeddings output by the meta-policy.In the program searching progress of HC, 250 neighbors are sampled and executed to obtain the targeted program for each iteration. Up to 1000000 evaluations would be performed in the searching process, with 16 parallel execution of a program involved in one evaluation. The return for a certain number of executed programs is recorded as the maximum return obtained from executing the previously searched programs only.To compare baselines with our proposal regarding inductive generalization, the expected horizon of the environment is scaled up by increasing the upper limit of the target for each KAREL-LONG task during the testing phase. For instance, in the FARMER task, the upper limit number is essentially the maximum iteration number of the filling-and-collecting rounds that we expect the agent to accomplish (please refer to Section H for more details). In the original task setting, the agent is tasked to continuously placing and picking markers in a total of 10 rounds of the filling-and-collecting process. In other words, all policies among baselines are trained to terminate after 10 placing-andpicking iterations. Nevertheless, the upper limit number is set to 20, 40, etc, in the testing environment regarding the inductive generalization ability of each policy.Since most of the baselines obtain a poor peformance on SEESAW and UP-N-DOWN (i.e., more than half of baseline approaches have mean return close to 0.0 on these tasks), we conduct experiments mainly on FARMER, INF-DOORKEY, and INF-HARVESTER. The testing environments will have expected horizon lengths that are 2, 4, 8, and 16 times longer than those of the training environments. Additionally, the rewards for picking or placing markers, as well as the penalties for actions, will be scaled down by factors of 2, 4, 8, and 16, respectively, ensuring that the maximum accumulated reward for each task is normalized to 1. The detailed settings and experimental results for each of these three tasks are presented below.During the training phase of all baselines, the maximum iteration number is set to 10. Afterward, we modified this number to 20, 40, 80, and 160 in the testing phase. As shown in Figure 9 , as the expected horizon length increases, the performance of all baselines except HIPO declines significantly. This indicates that our method has a much better inductive generalization property for this task. Further details on the definition of the maximum iteration number are provided in Section H.During the training phase of all baslines, the emerging probability is set to 1 2 . Following this, we modified this number to 3 4 , 7 8 , 15 16 and 31 32 in the testing phase. As shown in Figure 9 , as the expected horizon length grows, the performances of HIPO, PAO, and DRL drop slightly, but the performances of LEAPS and HPRL drop extensively. Also, HC performs better when the scale increases, but drops when the scale grows further. More details on the definition of the emerging probability are provided in Section H.During the training phase of all baselines, the upper limit number of marker-picking and markerplacing is set to 16. Then, we modified this number to 32, 64, 128, and 256 in the testing phase. As shown in Figure 9 , as the expected horizon length grows, the performance of all the baselines drop significantly. Nevertheless, HIPO has a minor performance drop compared to other baselines. Further details on the definition of the upper limit number are provided in Section H.In our approach, since the high-level neural network policy is incorporated, the proposed HIPO is only partially or locally interpretable -once the the high-level policy selects a programmatic option, human users can recognize the following execution of the program.To further increase the interpretability of the trained high-level policy f ϕ , we extracted a state machine structure by the approach proposed in [36] . In this setup, since HIPO utilizes the previous programmatic option as input and predicts the following option, we focus only on encoding the environment state observations. Each state observation is processed by convolutional neural networks and fully connected layers into a 1 × 32 vector, which is then quantized into a 1 × h vector. The hyperparameter h balances between the simplicity of the finite state machine and performance drop. Using these quantized vectors, we can construct a state-transition table. The final step involves minimizing these quantized vectors to effectively represent the state machine's structure. Examples of the extracted state machines are shown in Figure 10 , Figure 11 , and Figure 12 .We follow the training procedure and the model structure proposed in [74] , which uses the GRU [15] network to implement both the encoder q ψ and the decoder p θ with hidden dimensions of 256. The encoder q ψ and decoder p θ are trained on programs randomly sampled from the Karel DSL. The Note: the token STMT_STMT represents a division operation that splits the current token into two separate tokens, which are then sampled following the above probability list. This token primarily dictates the program's length, as well as the quantity and complexity of nested loops and statements.We conduct the procedure described in Section A.3.3 to search programmatic options for each highlevel policy. For tasks only involving skills of marker-picking and traversal, i.e., INF-HARVESTER, SEESAW, and UP-N-DOWN, we designate the number of programmatic options as |M | = 3, while for the remaining tasks, |M | = 5.The high-level policy f ϕ , whose training process is illustrated in Figure 13 , comprises convolutional layers [23, 37] to extract features from the Karel states and fully connected layers to determine the next program for execution. Meanwhile, one-hot encodings are used by the high-level policy to represent the indices of programmatic options. The detailed setting of the convolutional layers accords with the description in Section E.3. PPO [61] algorithm is adopted to optimize the high-level policy f ϕ . Hyperparameters are listed below: Option-Critic training on the Karel environment is implemented with the option-critic architecture [4] . algorithm with 20 million timesteps. The raw state inputs are extracted by an encoder comprised of two layers. The first layer comprises 32 filters, a size-4 kernel, and a stride of 1. The following layer has 32 filters, a size-2 kernel, and the same stride of 1. In our experiments with Option-Critic on Karel-Long tasks, all hyperparameters are listed below.• Maximum horizon: {2000, 4000, 6000, 8000, 10000}• Number of options: {2, 3, 4, 5}• Batch size : {32, 64, 128}• γ: 0.99• Termination Regularization: {0.1, 0.01}• Freeze interval: {128, 256, 512, 1024}• Update frequency: {32, 64, 128}• Entropy regularization: {0.1, 0.01}• Learning rate: {0.1, 0.01, 0.001, 0.0001, 0.00001}Following the setup detailed in [74] , we conducted experiments with various CEM-related hyperparameters as listed below, in order to optimize rewards for LEAPS.• Population size (n): {8, 16, 32, 64}• σ: {0.1, 0.25, 0.5}• e: {0.05, 0.1, 0.2}• Exponential σ decay: {True, False}• Initial distribution P : {N (1, 0), N (0, σ), N (0, 0.1σ)}Aligned with the approach described in [46] , we trained the meta-policy for each task to predict a program sequence, with hyperparameters listed below.• Introduced in Trivedi et al. [74] , the KAREL problem set includes 6 tasks: STAIRCLIMBER, FOUR-CORNER, TOPOFF, MAZE, CLEANHOUSE and HARVESTER. Figure 14 and Figure 15 depict randomly generated initial states, legit sampled internal states, and desired final states for each task.The experimental results in Table 1 average 32 rewards obtained across 32 randomly generated initial states of the environment.In a 12 × 12 grid environment, the agent's task is to climb the stairs and reach designated marked grid. Both the agent's starting position and the marked grid's position are randomly initialized on the stairs, with the marked grid always placed at the higher end. The reward is sparsely defined as: the agent receives a reward of 1 for reaching the goal, -1 for moving off the stairs, and 0 otherwise.In a 12 × 12 grid environment, the agent is tasked with placing a marker at each of the four corners. The agent receives no reward for placing a marker anywhere on the grid other than the four corners. Each successful marker placement at an unmarked corner earns a reward of 0.25.In a 12 × 12 grid environment, the agent's objective is to place a marker on every grid cell in columns where the bottom row has a marker in presence. Moreover, the agent should end up in the rightmost square of the row at the end of the episode. The agent receives rewards for consecutively and correctly placing markers until a mistake, which occurs if it places a marker on an empty cell in the bottom row or a marked cell.In an 8 × 8 grid environment, the agent is tasked to find a marker by navigating the grid environment. The marker's location, the initial agent position, and the maze layout configuration are randomly initialized. The agent receives a sparse reward of 1 for successfully finding the marker in the environment, and 0 otherwise.In a 14 × 22 grid environment, the agent's target is to collect scattered markers as many as possible.The initial location of the agent is fixed, whereas the scattered markers are randomly placed within the environment, adjacent to walls. The return is calculated as the ratio of the number of collected markers to the total number of initially designated markers.In an 8 × 8 grid environment, initially populated with markers in all grid cells, the agent's objective is to pick up a marker from each location within. The return is calculated as ratio of the number of picked markers to the total number of initially placed markers.The KAREL-HARD problem set proposed by Liu et al. [46] involves 5 tasks: DOORKEY, ONE-STROKE, SEEDER and SNAKE. Each task in this benchmark is designed to be more constrained and structurally complex than those in the KAREL problem set. Figure 21 depicts randomly generated initial states, legit sampled internal states, and final states for each task. The experimental results in Table 1 average 32 rewards obtained across 32 randomly generated initial states of the environment. In an 8 × 8 grid environment, partitioned into a 6 × 3 left room and a 6 × 2 right room by a column of walls, the agent's objective is to collect a key (represented by a marker) in the left room to unlock a door (an empty grid cell subsequently occurs in that wall column) and place the key on a marked grid cell in the right room. The agent's initial location, the key's location, and the target's location are randomly initialized. The agent receives a reward of 0.5 for collecting the key and another 0.5 for placing the key on the target. In an 8 × 8 grid environment, the agent is tasked to navigate through all grid cells without revisiting any of them. An empty grid cell is replaced with a wall once visited. The episode ends once the agent collides with any of these walls. The return is calculated as the ratio of visited grids to the total number of empty grids in the initial environment.In an 8 × 8 grid environment, the agent's task is to place one marker on every grid cell. The episode terminates immediately whenever the agent places multiple markers on one grid cell. The return is calculated as the ratio of the number of successfully placed markers to the total number of empty grids in the initial environment.In an 8 × 8 grid environment, the agent operates as the snake's head and seeks to consume (passthrough) as much food (markers) as possible without colliding with its own body. The snake's body grows by 1 grid cell for each marker consumption, and a new marker appears at a different location.Throughout the episode, only one marker exists in the environment. The reward is defined as 1 20 , which is the reciprocal of the targeted number of marker consumption, for each marker consumption. (f): The agent will move back and forth between the two chambers to collect the emerging markers continuously. Note that the locations of all the emerging markers are randomized. Also, note that we have set the number of emerging markers to 64 during the training phase (i.e., the agent has to pick up 64 markers to fully complete the task.) More details of the task SEESAW can be found in Section H.We introduce the novel KAREL-LONG problem set as a benchmark to evaluate the capability of HIPO. Each task in our KAREL-LONG benchmark is crafted to exhibit long-horizon characteristics derived from Karel states. Additionally, we ensure that these tasks maintain a constant per-action cost, set at 0.0001. Figure 16 , Figure 17 , Figure 18 , Figure 19 , and Figure 20 depict the tasks within the KAREL-LONG problem set, exhibiting randomly generated initial states and several internal states sampled from legitimate trajectories.In a 16 × 16 grid environment, the agent's objective is to traverse back and forth between two 4 × 4 chambers (the left chamber and the right chamber), continuously collecting markers. To facilitate movement between the left and right chambers, the agent must traverse through a central 2 × 6 corridor. Initially, one marker is positioned in the left chamber, awaiting collection by the agent. Upon picking a marker in a chamber, another is randomly generated in the opposite chamber, continuing the agent's task of collecting markers. Consequently, the agent must navigate between the two chambers to collect markers continuously. The return is defined as the ratio of the number of picked markers to the total number of markers generated by the environment, termed as "emerging markers."In an 8 × 8 grid, the agent's objective is to ascend and dscend the stairs repeatedly to collect markers (loads). Once a marker below/above the stairs is picked up, the next marker will appear above/below the stairs, and so on. The agent would receive an additional constant penalty (i.e., -0.005) for being out of contact with the stair. The return is defined as the ratio of the number of picked markers to the total number of markers generated by the environment, termed as "emerging loads."In an 8 × 8 grid environment, the agent's objective is twofold: initially, to fill the entire layout with markers, and subsequently, to collect them. In the initial state, all girds, except for the one in the upper-right corner, are empty, signaling the agent to proceed to populating the layout with markers, akin to farmer sowing seeds. After most grids are marked, the agent deploys the harvesting phase, analogous to a farmer collecting crops. Following this, the agent is prompted to refill the environment again, and the cycle repeats. We've imposed a maximum iteration limit to represent the anticipated number of filling-and-collecting rounds. The return is calculated as the ratio of the number of picked-and-placed markers to the total theoretical capacity of picked-and-placed markers, termed as "max markers."In an 8 × 8 grid environment, partitioned into 4 chambers, the agent is tasked to pick up markers in certain chambers, place markers in others, and continuously traverse between chambers until a predetermined upper limit number of marker-picking and marker-placing is reached. As mentioned earlier, the environment is partitioned into 4 chambers, restricting the agent's placement (or pick-up) actions to one chamber at a time. Upon completing a placement (or pick-up) action in a chamber, the passage to the next chamber opens (an emptied grid cell), allowing the agent to advance and perform another action. The return is calculated as the ratio of the number of picked-and-placed markers to the total number of markers that the agent can theoretically pick and place, referred to as "max keys."In a 16 × 16 grid environment, the agent's goal is to continuously pick up markers until none remain and no further markers emerge. Initially, the environment is fully stocked with markers. Each time the agent picks up a marker, there is a probability, termed the "emerging probability," that a new marker will appear in an empty grid cell, granting the agent to collect markers continuously and indefinitely. The return is calculated as the ratio of the number of picked markers to the expected total number of markers the environment can generate given a specific emerging probability.Our program policies are designed to describe high-level task-solving procedures or decision-making logics of an agent. Therefore, our principle of designing domain-specific languages (DSLs) considers a general setting where an agent can perceive and interact with the environment to solve specific tasks. DSLs integrate control flows, perceptions, and actions. While control flows are domain-independent, perceptions and actions can be designed based on the domain of interest, requiring specific expertise and domain knowledge. Such DSLs are proposed and utilized in various domains, including ViZDoom [34] , 2D MineCraft [3, 71] , and gym-minigrid [14] . Recent works [43, 79] also explored describing agents' behaviors using programs with function-taking arguments.While the Hierarchical Programmatic Option (HIPO) Framework provides notable advantages including interpretability, long-horizon task solving, inductive generalizability, and sample efficiency, it also has limitations that merit consideration in comparison to other methods. Techniques utilizing first-order logic programming [19, 33, 50, 83] , LLM-based interpretation [49] , and decision tree policies [7, 35] are also specifically designed to create interpretable, explainable, and generalizable agents for solving MDPs.In environments with a large state or action spaces, neuro-symbolic methods adopting symbolic policies [19, 33, 50, 83] are generally less computationally intensive and more feasible for training compared to programmatic approaches like this work and [10, 46, 74] . However, symbolic policies [19, 33, 50, 83] are inherently less intepretable, whereas programmatic policies, which could convey the logical flow of reasoning, are more intuitive to general users.While these symbolic policies are often complex for the average user, INSIGHT [49] uses LLMs to explain symbolic policies (i.e. polynomials with trainable parameters), thereby enhancing interpretability. This is something we could consider for future improvements, like using LLMs to explain programmatic options for better interpretability. Nonetheless, LLM prompting requires detailed environment and task descriptions, where the generated explanation is dependent on the LLM's understanding of the environment and the quality of the descriptions. In contrast, HIPO directly derives an interpretable programmatic policy through interaction with the environment, avoiding the aforementioned issue.Other proposals for enhancing interpretability involve decision trees. Both [7, 35] focus on learning decision trees within the imitation learning framework, which includes a DNN oracle for expert demonstration. In [35] , learned decision trees are further converted into if-else Python programs. However, the interpretability and performance of these methods depend heavily on the tree learning algorithm. Overly complex or brute-force programs become less interpretable and meaningful. Moreover, these methods generally require specific state information (e.g. object coordinates) for predetermined training, making it challenging to identify the necessary symbolic features for optimal performance or to develop a plausible training scheme. In contrast, LEAPS and its successors search only within the embedding space and perceive the state space partially and consistently, operating with fewer assumptions and achieving good performance.Besides, in our experiments detailed in Section 5, HIPO outperforms other baselines, including DRL, where deep neural networks were used as expert policies in [7, 35] to demonstrate trajectories for learning decision trees. This suggests that decision-tree methods [7, 35] are unable to surpass our HIPO framework due to the limitations of the underperforming DNN expert. In [7] , the authors propose methods for verifying decision-tree policies. The structure of decision trees contributes to efficient verification, allowing for quantitative assessment of the policy's correctness, stability, and robustness. This process aims to evaluate the effectiveness of the policy, including its performance in various scenarios and the presence of other desirable properties. Developing a method to quantitatively verify a programmatic policy remains a significant challenge.Finally, while HIPO retrieves a set of effective and compatible programs through a search method, exploring approaches that leverage prior knowledge, e.g., large language models [47] or offline datasets in imitation learning [12, 28, 30, 38, 41, 60] or skill-based reinforcement learning [40, 54, 57] , to efficiently retrieve programs is a promising research direction.For our experiments, we utilized the following workstation: 20-core Intel(R) Xeon(R) W-2255 CPU @ 3.70GHz, with 2X NVIDIA GeForce RTX 4070 Ti GPUThe rough computation time for the main experiments of our framework and baselines are as follows:1 Our work introduces Hierarchical Programmatic Option framework (HIPO), a novel framework that combines programmatic RL and HRL, enabling autonomous agents to represent complex behaviors and address long-term tasks. HIPO demonstrates significant potential in automating laborious or risky tasks, enhancing the efficiency and safety of autonomous systems. While offering promising societal benefits, we acknowledge the importance of addressing ethical considerations, including potential biases inherited from training data or adversarial attacks. Ongoing research in the field of responsible AI and fairness in machine learning aims to mitigate these biases, and we acknowledge the importance of continuous efforts to ensure that AI systems, including HIPO, adhere to ethical standards and contribute positively to society. Otherwise, the agent completes the entire task, and no further marker will appear. For simplicity, we only show the former case here. We have fixed the number of max markers to 720 during the training phase (i.e., the agent has to fill the entire environment layout with markers and pick up all markers each 10 times to fully complete the task.) More details of the task FARMER can be found in Section H. The agent properly places a marker at a marked grid located in the lower-left chamber. After that, a passage to the upper-left chamber opens, and a new marker appears in the upper-left chamber. (e): Upon the agent picking up a marker in the upper-left chamber, the passage to the upper-right chamber opens again, and a grid is marked randomly in the upper-right chamber. (f): The agent accurately places a marker at a marked grid located in the upper-right chamber. Afterward, the passage to the lower-right chamber opens again, and a new marker emerges in the lower-right chamber. (g): The agent will repeatedly pick up and place markers in this fashion until the number of max keys is reached. We have fixed the number of max keys to 100 during the training phase (i.e., the agent has to pick and place 100 markers in total to fully complete the task.) More details of the task INF-DOORKEY can be found in Section H. The agent picks up 6 markers in the 5 th column while 2 markers appear in 2 previously empty grids in the 7 th column. (e): The agent picks up 2 more markers in the last row while 2 markers appeared in 2 previously empty grids in the 5 th column. (f): Since markers appear in previously empty grids based on the emerging probability, the agent will continuously and indefinitely collect markers until none remain and no new markers appear in the environment. The emerging probability has been fixed to 1 2 during the training phase. More details of the task INF-HARVESTER can be found in Section H. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 


Decision: This paper presents a method for learning options as programs for repetitive, long-horizon tasks. We all agreed the work is well-written and clear, the method well-motivated and well-defined, and the empirical evaluations convincing enough to recommend an acceptance.

Reviews: review: paper_summary: paper_summary: The paper presents HIPO, a method for learning programmatic options for solving problems with long-horizon and repetitive tasks. First, HIPO searches in the space defined by a domain-specific language for a set of diverse programs. This set of programs is generated while accounting for the diversity and composability of the programs. Finally, these programs are used as options for a neural policy. HIPO was evaluated on instances of Karel the Robot, where it was shown to be more sample efficient than Deep RL and other programmatic methods. The paper also includes a carefully designed ablation study on HIPO's components.
strength_weakness: strength_weakness: The paper has a few weaknesses too. It would be helpful if the authors managed to fix the following for the camera ready, if the paper is accepted.

1. HIPO represents a method for learning programmatic options, but it includes no option-learning baseline.
2. Searching directly in the programmatic space was recently shown to outperform the latent search used in HIPO. It would be valuable to include this type of search as a baseline too.
3. It would be interesting to measure sample efficiency in terms of samples instead of programs. Intuitively, some programs could run much longer and be more costly in real settings. This would also allow for a comparison with DRL in terms of sample complexity. In general, I find learning curves more informative than the tables presented in the paper, which show only asymptotic performance.
4. It would be valuable to have more runs of the experiments >30 and show confidence intervals instead of standard deviation, as CI is easier to draw conclusions from without statistical tests.

Overall, in my opinion, the strengths of the paper outweigh its weaknesses. This is because the paper shows a different way of using programmatic representations that the community should further explore.
questions: questions: Please feel free to comment on the points listed under weaknesses. In addition to them, I will add the following questions and comments.

1. I am puzzled by the outstanding performance of HIPO in DoorKey. The way that the options are selected is that they have to be diverse and they have to maximize the agent's return. Since the options are selected as a pre-processing step, before orchestrating them, the programs must be collecting the key and receiving a positive reward, all of them. Once they are orchestrated, they happen to contain the behavior needed to find the door and collect the marker after the key is found. Is it because the composability step is already finding a solution that stitches together options that are able to solve the problem? If that is the case, would it be valuable to add a baseline that performs diversity+composability and returns the best order used in the composability step?

2. Why does HIPO use an option that terminates the episode? This doesn't make sense to me. The episode finishes whenever it finishes. That is, it is not up to the agent to decide when the episode finishes. This is a property of the MDP.

3. The caption of Figure 3 says that the Harvester goes from 36 to 400 markers as we move from Harvester to Inf-Harvester. Due to the structure of the problem, isn't it possible to find a short program that is able to collect an arbitrary number of markers?

4. I would like to challenge the desiderata of the options (lines 136-139). First, an option doesn't have to be effective in the sense that it needs to "obtain some task reward." It just needs to be part of the solution. For example, in the DoorKey problem, if the agent only received a positive reward once the problem was solved, an option that collects the key would still be helpful. Second, I suspect that the property of compatibility is only needed because the neural agent doesn't have access to the primitive actions while orchestrating the options. If the agent had access to them, it would be able to combine any "helpful option" by using primitive actions in between them. However, I understand that even if the agent had access to primitive actions, it could still find value in compatibility. In this case, compatibility would be playing the effectiveness property, and it would be looking at ways of how different programs can be combined to maximize the agent's return.

5. How can the diversity score be defined for searching directly in the programmatic space? Could one use the losses used to train the latent space to define diversity? Or is the diversity score only possible because of the properties of the latent space?
limitations: limitations: The paper has a limitations section in the appendix that addresses some important limitations, such as the trade-off between interpretability and performance. I would also add the points raised in the Weaknesses section of this review and the use of a single domain in the experiments.
paper_summary: paper_summary: The authors present HIPO, a method that use a Program embedding space to create options. Some are retrieve if diverse and efficient to create a set of option, later used by a learned high level policy. To evaluate their framework, as the KAREL benchmark does not include long and repetitive tasks, they introduce KAREL-LONG and evaluate their method on both benchmarks. Their result show that HIPO is a viable hierarchical RL method.
strength_weakness: strength_weakness: The only main weakness I was able to identify is the:

**Lack of limitation section**. 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], which can be useful for programs synthesis, tree-based policies (convertible to tree programs)[8, 5, 6, 7], ... etc. I think the "background" part of current related work section could be included in the *Introduction*, and that a dedicated *Limitation and related work* section could include such a discussion. It would situate the method in the broader literature, and bring attention to the nice HIPO method to these communities as well. I give some pointers references, but some more could be searched. 

Further smaller concerns are: 

**Interpretability allows to detect invisible suboptimal behaviors.** It has been shown that non-interpretable (e.g. deep) RL methods often learn misaligned policies [4, 5, 6], without this problem being spotted, on tasks as simple as Pong [5]. This is a much stronger argument to directly place in the introduction than the lack of transparency and trust. I would start off using such an argument, highlighting the need of e.g. readable, interpretable programs. 

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

-------------------------------
[1] Jiang, Zhengyao, and Shan Luo. "Neural logic reinforcement learning." International conference on machine learning. PMLR, 2019.

[2] Xu, Duo, and Faramarz Fekri. "Interpretable model-based hierarchical reinforcement learning using inductive logic programming." arXiv preprint arXiv:2106.11417 (2021).

[3] Luo, Lirui, et al. "INSIGHT: End-to-End Neuro-Symbolic Visual Reinforcement Learning with Language Explanations." arXiv preprint arXiv:2403.12451 (2024).

[4] Di Langosco, Lauro Langosco, et al. "Goal misgeneralization in deep reinforcement learning." International Conference on Machine Learning. PMLR, 2022.

[5] Delfosse, Quentin, et al. "Interpretable concept bottlenecks to align reinforcement learning agents." arXiv preprint arXiv:2401.05821 (2024).

[6] Kohler, Hector, et al. "Interpretable and Editable Programmatic Tree Policies for Reinforcement Learning." arXiv preprint arXiv:2405.14956 (2024).

[7] Delfosse, Quentin, et al. "HackAtari: Atari Learning Environments for Robust and Continual Reinforcement Learning." arXiv preprint arXiv:2406.03997 (2024).

[8] Bastani, Osbert, Yewen Pu, and Armando Solar-Lezama. "Verifiable reinforcement learning via policy extraction." Advances in neural information processing systems 31 (2018).

[9] Delfosse, Quentin, et al. "Interpretable and explainable logical policies via neurally guided symbolic abstraction." Advances in Neural Information Processing Systems 36 (2024).

[10] Ma, Z., Zhuang, Y., Weng, P., Zhuo, H. H., Li, D., Liu, W., & Hao, J. (2021). Learning symbolic rules for interpretable deep reinforcement learning. arXiv preprint arXiv:2103.08228.
questions: questions: * Are the KAREL-LONG environment containing training and testing environments ? As programs are compared, it might be insightful to test the generalizability of the different methods (by varying size, of the environment).
* 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. This could be made clearer. 
* What's the percentage of retrieved program (based on your effectiveness and diversity criterion) ?
limitations: limitations: This constitutes my main concern, I have not been able to clearly situate a (broader discussion) on the limitations. Again, I would create such a section, bringing most of the related work in it, as an opportunity to criticize (both positively and negatively) HIPO, and other approaches.
paper_summary: paper_summary: Utilizing human-readable programs as policies has been recently proposed to enhance interpretability in reinforcement learning. This work introduces the Hierarchical Programmatic Option Framework (HiPO) that first embeds the programs into a smooth and continuously parametrized space, obtains a diverse and compatible skill set by applying the cross entropy method on the embedding space with respect to novel diversity and compatibility metrics, and finally learning a high-level policy upon the skill set. Experimental analysis of HiPO on the Karel problem sets manifests its effectiveness and zero-shot generalizability.
strength_weakness: strength_weakness: 1. The execution time will differ from program to program, but HiPO does not consider this factor while incorporating a discount factor $\gamma$ of 0.99. The adoption of SMDP should be considered to deal with the variance in execution time appropriately. Also, HiPO does not discount the cumulative reward of low-level actions, further deepening the inconsistency between the theoretical objective and the actual loss function. The authors should justify such design choices.

2. In Section 5.3, the difference between the two settings, CEM+diversity top k and CEM+diversity x |M|, is unclear. Further explanation would be helpful for the readers.

3. The authors did not conduct experiments on the CEM + compatibility setting. In the Karel-Long environments, most of the improvement seems to come from the compatibility heuristic.
questions: questions: 1. Figure 6 shows how the adoption of the diversity factor spreads the skill set over the embedding space. However, the diversity of the embedding vectors does not necessarily guarantee the diversity in the actual behaviour. How different are the programs' actual behaviors in the final skill set?

2. 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?
limitations: limitations: The authors adequately addressed the limitations of their work.
paper_summary: paper_summary: This work builds off of deep reinforcement learning generating programmatic policies, and adapts it to solve long-horizon, repetitive tasks. Concretely, this work proposes HIPO, short for hierarchical programmatic option framework, which retrieves history programs by its neural embeddings, and uses these programs as reusable options to solve reoccurring tasks.
strength_weakness: strength_weakness: 1) Lack of retrieval evaluation: The paper proposes special techniques to improve the effectiveness, diversity, and compatibility of retrieved programs, however, is there any empirical evidence to show that the designed modules do improve the effectiveness, diversity, and compatibility of programs?
questions: questions: 1) 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.
2) This work chooses a particular DSL (as introduced in Section 3), does the choice of DSL affect the performance of the proposed process? Would a less well-designed DSL cause the method to be ineffective?
limitations: limitations: Yes.

Comments: title: Re: Official Comment by Reviewer p5Z4
Re: Thank you for the clarifications
Thank you for the clarifications
Reminder: The reviewer-author discussion period ends in three days
comment: My point was to suggest discounting more after long macro-actions, e.g. $(\gamma+\gamma^3+\gamma^5)+\gamma^6\times\gamma$ for the first sequence and $\gamma+\gamma^2\times\gamma+\gamma^4\times\gamma+\gamma^6\times 1.01\gamma$ for the second one. Anyway, my other concerns are resolved, and I have updated my score. Please add the explanations to the camera-ready version.
Thank you for answering all my questions, I appreciate the effort.
We thank the reviewer for the question with further clarification. 

> Unlike [1, 2, 3], where the length of a high-level action is fixed, HIPO deals with variable-length high-level actions. This can be problematic in certain situations. Consider the following two sequences of rewards ...

Due to the temporal abstraction brought by the hierarchical structure, the high-level policy evaluates the effectiveness (i.e., cumulative reward) of each macro action no matter how long or short each macro action is. That said, we consider learning the high-level policy to be a standard RL problem. As pointed out by the reviewer, with a discount factor $\gamma<1$, the high-level policy prefers immediate rewards to delayed rewards. This has been proven to be effective and lead to better convergence, and is widely adopted in most RL algorithms [1-4] with or without a hierarchical policy structure. Note that such a setting is also adopted by [5], whose low-level policy (transition policy) also has varying horizons.

On the other hand, the preference of the high-level policy can be adjusted under different values of $\gamma$. For example, if the value of $\gamma$ is raised from $0.99$ to $0.999$, the discounted return of sequence 1 in the example above is $3 + 0.999 \times 1 = 3.999$, and the discounted return of sequence 2 is $1 + 0.999 \times 1 + 0.999^2 \times 1 + 0.999^3 \times 1.01 \approx 4.003974$. With this adjustment, the high-level policy prefers sequence 2. Hence, the desired value of the discount factor can vary from one task to another.

We thank the reviewer for the fruitful discussion and will revise the paper to include it. Also, we hope our initial rebuttal sufficiently addresses other questions raised in your initial review. 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. 

[1] Nachum et al., "Data-efficient hierarchical reinforcement learning." In NeurIPS, 2018.

[2] Frans et al., "Meta learning shared hierarchies." In ICLR, 2018.

[3] Lee et al., "Learning to coordinate manipulation skills via skill behavior diversification." In ICLR, 2020.

[4] Schulman et al., "Proximal policy optimization algorithms." 2017.

[5] Lee et al., "Composing Complex Skills by Learning Transition Policies." In ICLR, 2019.
I'm very sorry for the late reply. Here are some clarifications I want to make.

Unlike [1, 2, 3], where the length of a high-level action is fixed, HIPO deals with variable-length high-level actions. This can be problematic in certain situations. Consider the following two sequences of rewards:

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

where rewards from the same macro-action are grouped by parentheses. Under the return computation scheme used by HIPO, sequence 1 results in $4+0.99\times 1=4.99$ and sequence 2 results in $1+0.99\times 1+0.99^2\times 1+0+0.99^3\times 1.01\approx 3.95$. Even though sequence 2 is better, HIPO will prefer the first one.
Thank the authors for the detailed response and additional experiments. The discussions and potential adjustments sound reasonable to me. I will keep my score.
We would like to express our sincere gratitude to the reviewer for the thorough and constructive feedback. We will definitely revise the paper to incorporate all the modifications that were promised.
I want to thank the authors for their clarifications. 
I want to insist on the fact that they do not have to change their method name, I just gave an advice, but the choice is theirs.

If the last point above has not been discussed in the paper, I would advise adding it as well.
 
Overall, I hope that the promised modifications will be incorporated in the manuscript, and hope to see this paper presented at the conference.
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.