Hierarchical Programmatic Option Framework
Authors: Yu-An Lin
Chen-Tao Lee
Chih-Han Yang
Guan-Ting Liu
Shao-Hua Sun
Venue: NeurIPS 2024 poster (2024)
Keywords: Reinforcement Learning
Programmatic Reinforcement Learning
Hierarchical Reinforcement Learning
Program Synthesis
Primary area: reinforcement_learning

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.

Hierarchical Programmatic Option Framework
Yu-An Lin" Chen-Tao Lee"
Chih-Han Yang"
Guan-Ting Liu" Shao-Hua Sun
National Taiwan University
{b06204039, b06703027, b10902069, f07944014, shachuas Snttu edu. tw
Abstract
Deep reinforcement learning aims to learn deep neural network policies to solve large-scale decision-making making problems. However, approximating policies using deep neural networks makes it difficult interpret the learned decision-makinn process. To address this issue, prior works [10 readable programs policies to increase the interpretability of the decision-makinn pipeline. Nevertheless, programmatic policies generated by these methods struggle effectively solve long and repetitive RL tasks and cannot generalize even longer horizons during testing. To solve these problems, we propose the Hierar- chical Programmatic Option framework (HIPO), which aims to solve long and repetitive RL problems with human-readable programs as options (low-level poli- cies). Specifically, we propose method that retrieves set of effective, diverse, and compatible programs 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 RI. baselines various tasks. Ablation studies justify the effectiveness of our proposed search algorithm for retrieving a set of programmatic options.
46 74) proposed to use human-
Introduction
Deep reinforcement learning (deep RL) has recently achieved tremendous success various domains, such as controlling robots [26 31,, playing strategy board games [67 688, and mastering video games 778 82 However, neural network policies learned by deep RL methods are not human- interpretable, 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 limiting their applicability in the context of most real-world applications.
To address these issues, programmatic RI. frameworks 10
were proposed represent policies as programs that detail task-solving procedures 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.
46 74
Despite encouraging results, prior programmatic RL frameworks are limited to generating concise programs that can only tackle short-horizon tasks. Particularly for long- long-horizon RL problems like robotic manipulation (2 8 and autonomous driving (55) 58], these tasks consist of reoccurring subtasks and sparse rewards, necessitating significant number of actions to be fully resolved. Therefore, the RL. agent needs to learn diverse and reusable set of skills to solve such tasks effectively.
"Equal contribution.
Correspondence to: Shao-Hua Sun <shaohuasentu, edu. ty>
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Aiming to solve long and repetitive tasks with better policy interpretability, we borrow ideas from the option frameworks 51 66 72] and latent-space-basee 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- long-horizon tasks with arbitrary number of repeating subroutines.
Our framework contains three stages. (1) Constructing 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 searching algorithm to retrieve set of programmatic options from the learned program embedding space. Fach programmatic option can be executed in the MDP and achieve satisfactory performance: more importantly, these programs are compatible and can sequentially executed in any order. (3) Learning a high-level policy: To alter between 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 grid world and interacts with objects. HIPO outperforms prior programmatic reinforcement learning and deep RL baselines on existing benchmarks [46] [7]. To further evaluate the performance and generalization ability to even longer horizons, we design 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.
2 Related work
Program synthesis. Program synthesis techniques revolve around program generation convert given inputs into desired outputs. These methods have demonstrated notable successes across diverse domains such as array and tensor manipulation computer commands describing agent behaviors 9
string transformation (20
29
85
generating
and code [1
42 graphics and 3D shape modeling
48 73
81), and
[3
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 readbble 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 33
state machines
[32], symbolic expressions [19] 33
39
49
50
g3 and programs [1 75 76
Liu
al. [46). Medeiros et al. [52), Moraes and Lelis
[53 Trivedi et al. (74), and Carvalho et al.
[T]
attempted to produce policies described by domain -specfi language programs to solve simple RL
tasks. We aim take step toward addressing complex, long- hogg-horizon. repetitive tasks.
Hierarchical reinforcement learning. Hicrarchical Reinforeement Learning (HRL) frame- works 4 40 72 (77 focus 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 lowelevel policies, our framework aims 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 Nomain-specinfe language (DSL) of the Karel domain (9 [3 74]. as illustrated in Figure 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 ear 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 consid- ered in this work can be formulated as mmite-horizon discounted Markov Decision Processes (MDPs). The performance of HIPO evaluated based on the exe- cution traces of a series of programs (programmatic options) selected by high-level policy. The roll- out of program P consists of a Ttep sequence of state-action pairs {s,, (;) )==1. ...... obtained from a
Prugram p DEF run mn 8 m)
Repetition n = Number of repetitions
Perception h frontIsClear leftlsClear rightssClear
markerPresent noMarkerPresent
Condition = perception | not perception h
Action
turneeft turnRight
putMarker pickMarker
Statement
while 6c) w| $1::82 |a]
program executor EXEC(.) that executes program p to interact with an environment, resulting in the dis-
repeat R=n r( sx) (T((be)i(xi))
ifelse ol (bc) else ol #2
counted return > (((r)). where re = R(s,, az) denotes the reward function. We aim maximize the total rewards by executing series of programs following the high-level policy.
Figure 1:
Karel domain-specific language (DSL), designed for describing the Karel agent's behaviors.
Hierarchical Programmatic Option Framework. The proposed hierarchical framework consists of set of programmatic options M fo that sequentially chooses one option at a time. Each option m, encapsulates a -eadablee program Pm; that will be executed if selected by the high-level policy f On the other hand, the high-level policy fmm',, s/x+) outputs the probability distribution over all programmatic options M, given the last selected programmatic option m² at timestep T and the current MDP state si.. If the next option m sampled from the distribution is the termination mode Merm. the rollout will be terminated. Otherwise, the corresponding programmatic option Pm++1 will be executed and generates a sequence state-action pairs {s{ (st+1 aq ) ) Ti+1 before the high-level policy fo selects the next programmatic option +22
M low-level policies and high-level policy
(+1)
4 Approach
We design a three-stage framework search programmatic options and train high-level policy represented by neural networks. The main goal is to maximize the return given a task described by an MDP. Firstly, introduced Section 4.1 we construct program embedding space parameterizing programs smoothly and continuously with diverse behaviors. Then, Section 4.2 presents a method that retrieves 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 Figure
4.1 Constructing program embedding space
We follow the approach and the program dataset specified Trivedi et al. 77 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 pe to map any program embedding = to program Pz = po(2) consisting of a sequence of program tokens. Details on the program dataset generation and the encoder-decoder training be found in Section E.I.I
4.2 Retrieving programmatic options
With a program embedding space, we aim to retrieve a set of programs (programmatic options) given task. This set of programs should have the following properties.
3

---

Cornett Option cucumennt
Learning Hight Palky
Search Center
Piggam Cancidates
Decoder
800
High f
Progran Erioodoing 4
Enwirmmet
Papa-
Eaf
Option
term
Sample Nost Program
Resioved
Distarts Each Candiaaie
Envroemeett
Prggrammntc
Fou ExECruglal
Optione
Excoute Perud
Pxy
Shemiy T3lE
(a) Retrieving Programmatic Options
Learning Hightl evel Policy with Programmatic Options
Figure 2: Hierarchical Programmatic Option Framework. (a): Retrieving programmatic options. After learning the program embedding space, we propose an advanced search scheme built upon the Cross-Entee Entrr-y Method (CEM) to search programs Pm...... ..... Pmg Pma++ of different skills. While searching for the next program Pmg.11 consider its compatibility with predetermined programs Pm...... Pm,, by randomly sampling sequence of programs. We also consider the diversity among all programs using the diversity multiplier. (b): Learning the high-level policy, Given current environment state and the current programmatic option m.. the high-level policy outputs a probability distribution over all programmatic options, aiming to maximize the total accumulative reward from the environment.
Effectiveness: Each program can solve the task to some extent.
Diversity: The more behaviorally diverse the programs are, the richer behaviors can be captured.
Sequentially executing some programs with specific orders can potentially lead to improved task performance.
Compatibility:
4.2.1 Retrieving effective programs
To obtain solving program, we can apply the Cross-Entre Entroop Method [59] iteratively searching in learned program embedding space 77 in the following procedure:
(1) Randomly initialize a program embedding vector the search center.
Add random noises 2, generate population of program embeddings Z = {24 (zi)i=l,.. where denotes the population size.
(3) Evaluate every program embedding Z with the evaluation function G to get a list of
fitness score [G(z))]==1....
(4) Average the top program embeddings Z according to fitness scores [G(z;)] I.... I. and assign it to the search center 2r-
(5) Repeat (2) to (4) until the fitness score G(z,) of z, 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 pro- gram execution return of decoded program embedding, i.e., G(=) Σ'n (. ExEc((x)) [ra] To retrieve set of J programmatic options for high-level policy, we deploy this CEM search N times, take M best program embeddings, and obtain the decoded program set {Pz., po(2,)))==.... Please refer to Section A.1 for more details and the CEM search pseudo-code.
4.2.2 Retrieving effective, diverse programs
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 -dmianiil- 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 is evaluated by G(z, 2x) = (Ei= -xXECC
diversily(2, Zạ), where 2:2,
diversity(2. 7 is the proposed diversity multiplier defined as Sigmoid(- - max |||||
Thus, the program execution return is scaled down by sity(2 Zx) based on the maximum cosine similarity between and the retrieved program embeddings Z = { l= from the previous k CEM searches, diverging the current program embedding from previously retrieved programs.
To retrieve a set of JM] 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 Section A.2
4.2.3 Retrieving effective, diverse, compatible programs
The proposed HIPO executes a sequence of programmatic options determined by high-level policy, Therefore, these programs shall be compatible with each other, i.e., executing 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, CEMM-ddiversttyycomaatbbbbi
To evaluate the program embedding we take the decoded program P3 as the (A: + st option. Then, lists of programs V Vi,=i..... are sampled with replacements from determined & options and the (k + 1)st option. Each program list V contains at least one (A + 1)st option to consider the compatibility between the (k + 1)st and previously determined options. The return is computed by sequentially executing these D sequences of programs and multiply the result with the diversity multiplier proposed Section 4.2.2 As the result, the evaluation function is G(z, Zx) 1 Ei= Rv, diversity(2, Zk), where R.g, is the normalized reward obtained from executing all programs in the specified program sequence Vr
10.1 29
1
Rv:
TE
j=1
t=
with | being the number of programs in the program sequence M,, Mi[i] being the j-th program, and y as the discount factor.
The search method with the specified evaluation is deployed |M times to obtain 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.
4.3 Learning high-level policy with programmatic options
Given set of programmatic options M {mL bonn)k=in k=1, |M]j [M]- we formulate learning high-level policy So 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' and the current environment state s, the high-level policy fo outputs the probability distribution of programmatic options for the next option m+1 E Murm U (m4)h= [M] where Them denotes the termination option that ends the episode once selected. Otherwise, the corresponding program
Pm++1 is executed, yielding the next state 8T4., and the cumulative reward y++1 Et=1 r rft1 Note i+1 that the last state +1 the state sequence is returned by EXEC 1), with 1 denoting the horizon of the + 1-th program execution. Also, the cumulative reward r++ obtained within a single
T'
program execution not discounted.
Note that single program execution EXEC(p) will terminate after complete execution or the number of function calls emitted during EXEC(p) reaches 220, which aligns to the setting Trivedi et al.
5

---

(a) SEESAW
(b) UP-N-DoWN
(c) FARMER
(d) INP-DOORKEY
(c) INF-HARVESTER
Figure 3: KAREL-LONG problem set: This work introduces new set of tasks in the Karel domain. These tasks necessitate learning diverse, repetitive, and spec-ipe skills. For example, in our designed INF- SNF-HARVESTER, the agent needs to traverse the whole map and pick nearly 400 markers solve the tasks since the environment randomly generates markers; contrast, the HARVESTER from the KAREL problem set [4 can be solved by picking merely 36 markers.
74]. This iterative process stops once the termination option is sampled the maximum number of the option-selectin 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. [3) 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
5
Experiments
We aim to answer the following questions with the experiments and ablation studies. (1) Can our proposed diversity multiplier introduced in Section 4.2.2 enhance CEM and yield programs with improved performance? (2) Can our proposed
introduced in Section 4.2.3 retrieve set of programs that are diverse yet compatible with each other? (3) Can the proposed framework outperforms existing methods on long-horizon tasks?
Please refer to Section B for hyperparameter settings for the following experiments.
5.1
Karel problem sets
To this end, consider the Karel domain [66 which is widely adopted in program synthesis 9 65 70] and programmatic reinforcement learning 46 74]. Specifically, we utilize the KAREL problem set [74] and the MAREL-HARD problem set 466] The KAREL problem set includes basic tasks, each of which can be solved by short program (less than 45 tokens), with 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 provided in Section FJand Section G
13
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 not suitable for evaluating long-hone long-horizon task-solving ability (i.e., tasks requiring more than 3000 timesteps to finish). Hence, we introduce newly designed KAREL-LONS problem set as the benchmark to evaluate the capability of HIPO.
As illustrated in Figure 3 the tasks require the agent to fulfiil 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|Hi
5.2 Cross-entropy method with diversity multiplier
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

---

Table 1: Evaluation KAREL and KAREL-HARD tasks. Mean return and standard deviation of all methods across the KAREL and KAREL-HARD problem set, evaluated over five random seeds. CEM+diversity outperforms CEM with significantly smaller standard deviations across 8 out of 10 tasks, highlighting the effectiveness and stability of CEM+diversity. In addition, HIPO outperforms LEAPS and HPRL on out of 10 tasks.
Method
Foun CORNER
Top OFF
CLEAN
HouSE
STAIR CLIMBER
HARVESTER
DnOk KEY
STROKE
ONT
SEEDER
CFM
0.18
0.14
1.00
0:45-0.2 0.28
0.50 0.00
0,65
0.5 +
0.21 +.115
CEMedivesiity
0.80
1,00
0.05
0.07
0.50 0.00
0.09 +
0.02
8:05
0.00
0.48 0.03
0.96
LEAPS
0:45
0:40
0.81 0.07
0.18 0.14
1.00 1:000
0.65 0.28
1.00
0.00
0.50 0.00
0.65 0.19
0.51 1:021
0.21 1.0.5
HPRL
1.00 =: 0.00
1.00 0.00
1.00
1: 0.00
1.00 2: 0.00
1.00
0.00
1.09
0.00
0.50 4: 0.00
0.80 0.02
0.58 2: 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,89
12:00
1.00 :: 0.00
0.62 0.01
0.97 0.02
0,36 0.02
CEM+diversity to find 10 programs. Then, for each task, we evaluate all the programs and report the best performance in Table [ 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 CBM+diversity can be found in Section A.2
5.3
Ablation study
We propose hetad-diiensity-ommaatbbib matic options for our high-level policy. In this section, we compare a variety of implementations regarding the diversity and the compatibility of programs.
retrieve set of effective, diverse, compatible program-
CEM x X|M Conduct the CEM search described in Section 4.2.1 M times and take the resulting M programs as the set of programmatic options.
CEM+diversity top k, in Section 4.2.2 N = 10 times and take the top |M results as the set of programmatic options.
|M Conduct the CEM search with the diversity multiplier described
CiM+divyrsity x MM Conduct the CEM search with the diversity multiplier described in Section 4.2.2 N 10 times and select the best program as the it option. Repeat this process |M] times to extract M programs as the set of programmatic options.
CEM MM]: Conduct the CEM search by executing programs in the specified program sequence V. described in Section 4.2.3 excluding the diversity multiplier. Iteratively perform this search [M] times and take the resulting |M programs as the set of programmatic
options.
HIPO (ours): Conduct commpibts (i.e., CEM with the diversity multiplier and Ry as described in Section 4.2.3) for N = 10 times and select the best result as the jth 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-Dow and INF- HARVESTERR and 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 iindicate that our proposed framework, HIPO, outperforms its variants that ignore diversity or compatibility among programmatic options on all the tasks. This justifies our proposed effective, diverse, compatible programs options for the high-level policy.
ccompatiiyyy method for retrieving a set of
5.4 Comparing with deep RL and programmatic RL Methods
We compare proposed framework and its variant state-of-the-ane 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.
7

---

Table 2: KAREL-LONG performance. Mean return and standard deviation of all methods across the KAREL- problem set, evaluated over five random seeds. Our proposed framework achieves the best mean reward across most of the tasks by learning high-level policy with set of effective, diverse, and compatible programs.
Method
SRESAW
UP-N-DOWN
FARMER
INF. DOORKEY
INI-HARVESTER
CEM
M)
0.06 0.10
0.39 + 0.36
0.03 0.00
0.14
0.41+ 0.17
CEMediversity top R, k [M]
0.15 0.211
0.25 + 0.35
0.03 = 0.00
0.13 0.16
0.42+ 0.19
CEM--divenity x [M]
0.28 0.23
0.31
0.03
0.36 0.26
0.471
CEM#compaiiiiity x|a[]
0.23 0.332
0.43 0.34
0.14 = 0.22
0.57 1 0.3
0.66 1: 0.08
Random Transition
0.01 0.00
0.01 0.00
0.01 0.01
0.15+
PAO
0.01 0.00
0.00 + 0.00
0.43 113=0.22 0.23
0.34 0.45
0.60 + 0.04
0.00
0.38
0.17 0.36
0.74+
Option Critic
0,00-10.00 0.00
0.00 1. 0.00
0.00 1 0.00
0,00 1 0.00
0.47 1 0.01
LEAPS
0.01 0:01
0.01
0,03
0.01 0.00
0.12
HPRL
0,00 0.00
0.00 0.00
0.01 = 0.00
0.00 0.00
0.45 + 0.03
HC
0.08
0.31 + 0.38
0.19 0.03
0.14:00.16
0.88 0.00
HIPO (Ours)
0.53 0.10
0,76 + 0.02
0.62 = 0.02
0.66 0.07
0.79 0.02
Inf-Hareester
Option Searchingg
Dotton Searcitng
Petormenc Dre- (M))
-22
HIFO
IIFO
-40
.20
XLC
Expected Herizon Jargi
(a) Program Sample Efficiency
(b) Inductive Generalization
Figure 4: (a) Program sample efficiency. The training curves of HIPO and other programmatic RL approaches, 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.
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, pi cicMarkee).
DRL represents a policy as a neural network and is learned using PPO 61
Option-Criti represents policy that both high-level and low-level policies are neural networks and is learned using the option-criti 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, pi ckMarker)
Learning Embeddings for Latent Program Synthesis (LEAPS) 74 searches for single
sosk-no program using the vanilla CEM learned program embedding space.
Hierarchical Programmatic Reinforcement Learning (HPRL) learns a meta-policy, whose action space is learned program embedding space, to compose 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 set of neighboring candidates. The program that performs best among these neighbors is selected as the next candidate for exploration.
As Table T shows, HIPO outperforms LEAPS and HPRI. 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
8

---

tasks (i.e., less than 500 actions). For long- horizon tasks that require more than 3000 actions to solve, Table 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 extended traverse collect markers, leading to a sparser reward distribution. During the searching phase of programmatic options, emphasizing compatibility enables HIPOO secure 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
5.5 Program sample efficiency
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 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-space- based programmatic RL frameworks, More details and the action sample efficiency can be found in Section B and Figure
5.6 Inductive generalization
We aim to compare the inductive generalization ability among all the methods, generalizing to of-iiistribtioonaly (i.e., unseen during training) long task instances [32]. To this end, we increase the expected horizons of FARMER and HAR-ETRE by 2x, 4x, 8x, and 16x. 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
The results show that HIPO suffers a fewer decline in performance in testing environments with sig- nificantly 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.
5.7 Interpretabilityy
In the proposed framework, we retrieve a set of programmatic options that can be reused by the high- level policy to solve long and repetitive tasks. For example, in ONF-DOORKE KEY (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 guide the agent traverse all four chambers with the following sequence of programmatic options: T. = (m,, M3, Mys My, m,, m4, M4, M2, My, Ma, my).
INF-DOORKEY requires three different skills to solve: picking 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 I 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, the control flows, perceptions, and actions specified the program. On the other hand, the high-level policy is neural network by itself, making it hard to interpret the option transition dynamic learned by the high-level policy.
could fully interpret the agent policy with
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

---

6
Conclusion
This work aims to construct reinforcement learning policies that are human- interpeetttreeeeeeeeee and general- izable, bridging from hierarchical reinforcement learning to programmatic options. Consequently, we propose the Hierarchical Programmatic Option framework (HIPO) to represent complex behaviors and address aag-hooizon 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 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 RI. and programmatic RI. meth- ods on various tasks. addition, HIPO demonstrates good performance 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.
Acknowledgement
Shao-Hua Sun was supported by the Yushan Fellow Program by the Ministry of Education, Taiwan.
References
[1] David Aleixo and Levi HS Lelis. Show me the way! bilevel search for synthesizing programmatic strategies. In Association for the Advancement of Artificial Intelligence, 2023.
[2] Mihai Anca, Mark F. Hansen, and Matthew Studley. Modular hierarchical reinforcement learning for robotics: Improving scalability and generalizability. In ICML Workshop on New Frontiers in Learning, Control, and Dynamical Systems, 2023.
[3] Jacob Andreas, Dan Klein, and Sergey Levine. Modular multitask reinforcement learning with policy sketches. In International Conference on Machine Learning, 2017.
[4] Pierre-Luc Bacon, Jean Harb, and Doina Precup. The option-critic architecture. In Association for the Advancement of Artificial Intelligence, 2017.
[5] Matej Balog, Alexander I. Gaunt, Mare Brockschmidr, Sebastian Nowozin, and Daniel Tarlow. Deepcoder: Learning to write programs. In International Conference on Learning Representa- tions, 2017.
[6] Andrew G Barto and Sridhar Mahadevan. Recent advances in hierarchical reinforcement learning. Discrete Event Dynamic Systems, 2003.
[7] Osbert Bastani, Yewen Pu, and Armando Solar-Lezama. Verifiable reinforcement learning via policy extraction. In Neural Information Processing Systems, 2018
[8] Benjamin Beyret, Ali Shafti, and A. Aldo Faisal. Dot-to-dot: Explainable hierarchical rein- forcement learning for robotic manipulation. In 2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 5014-5019, 2019.
[9] Rudy R Bunel, Matthew Hausknecht, Jacob Devlin. Rishabh Singh, and Pushmeet Kohli. Leveraging grammar and reinforcement learning for neural program synthesis. In International Conference on Learning Representations, 2018.
[10] Tales Henrique Carvalho, Kenneth Tjhia, and Levi Lelis, Reclaiming the source of programmatic policies: Programmatic versus latent spaces. In The Twelfth International Conference on Learning Representations, 2024.
[11] Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards. Yuri Burda, Nicholas Joseph, Greg Brockman, Alex Ray, Raul Puri, Gretchen Krueger, Michael Petrov, Heidy Khlaaf, Girish Sastry, Pamela Mishkin, Brooke Chan, Scott Gray, Nick Ryder, Mikhail Pavlov, Alethea Power, Lukasz Kaiser, Mohammad Bavarian, Clemens Winter, Philippe Tillet, Felipe Petroski Such, Dave Cummings, Matthias Plappert, Fotios Chantzis, Elizabeth Barnes, Ariel Herbert- Voss, William Hebgen Guss, Alex
10

---

Nichol, Alex Paino, Nikolas Tezak, Jie Tang, Igor Babuschkin, Suchir Balaji, Shantanu Jain, William Saunders, Christopher Hesse, Andrew N. Carr, Jan Leike, Josh Achiam, Vedant Misra, Evan Morikawa, Alec Radford, Matthew Knight, Miles Brundage, Mira Murati, Katie Mayer, Peter Welinder, Bob McCirew Dario Amodei, Sam McCandlish, Ilya Sutskever, and Wojeiech Zaremba. Evaluating large language models trained on code. arXiv preprint arXiv:2107.03377, 2021.
[12] Shang-Fu Chen, Hsiang-Chun Wang, Ming-Hao Hsu, Chun-Mao Lai, and Shao-Hua Sun. Diffusion model-augmmened behavioral cloning. In International Conference on Machine Learning 2024.
[13] Xinyun Chen, Chang Liu, and Dawn Song. Execution-guided neural program synthesis. In International Conference Learning Representations, 2019.
[14] Maxime Chevalier-Boisvert,, Bolun Dai, Mark Towers, Rodrigo de Lazcano, Lucas Willems, Salem Lahlou, Suman Pal, Pablo Samuel Castro, and Jordan Terry Minigrid & miniworld: Modular & customizable reinforcement learning environments for goal-oriented tasks. arXiv preprint arXiv: 13831, 2023.
[15] Kyunghyun Cho, Bart van Merrienboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. Learning phrase representations using encoder- decoder for statistical machine translation. arXiv, 2014.
[16] Dongkyu Choi and Pat Langley. Learning teleoreactive logic programs from problem solving. In International Conference Inductive Logic Programming. 2005.
[17] Karl Cobbe, Oleg Klimov, Chris Hesse, Tachoon Kim, and John Schulman. Quantifying generalization in reinforcement learning. In International Conference on Machine Learning, 2019.
[18] Christian Daniel, Gerhard Neumann, and Jan Peters. Hierarchical relative entropy policy search. In Neil D. Lawrence and Mark Girolami, editors, Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, volume 22 of Proceedings of Machine Learning Research, pages 273-281, La Palma, Canary Islands, 21-23 Apr 2012. PMLR.
[19] Quentin Delfosse, Hikaru Shindo, Devendra Dhami, and Kristian Kersting. Interpretable and explainable logical policies via neurally guided symbolic abstraction. arXiv, 2023.
[20] Jacob Devlin, Jonathan Uesato, Surya Bhupatiraju, Rishabh Singh, Abdel-rahman Mohamed, and Pushmeet Kohli. Robustfill: Neural program learning under noisy i/o. In International Conference on Machine Learning, 2017.
[21] Fan Ding and Fei Zhu. Hliferl: hierarchical lifelong reinforcement learning framework. Journal of King Saud University Computer and Information Sciences, 34(7):411244211 2022. ISSN 1319-1578.
[22] Kevin Ellis. Catherine Wong, Maxwell Nye, Mathias Sable-Meyer, Luc Cary, Lucas Morales, Luke Hewitt, Armando generalizable, interpretable knowledge with wake-sleep bayesian program learning. arXiv preprint arXiv:2006. 08381, 2020.
and Joshua B Tenenbaum. Dreamcoder: Growing
[23] Kunihiko Fukushima and Sei Miyake. Neocognitron: A celf-organizing neural network model for mechanism of visual pattern recognition. Competition and Cooperation Neural Nets: Proceedings of the US-Japan Joint Seminar, 1982.
[24] Daniel Graves, Jun Jin, and Jun Luo. Lispr: An options framework for policy reuse with reinforcement learning. arXiv, 2020.
[25] Karol Gregor, Danilo Jimenez Rezende, and Daan Wierstra. Variational intrinsic control. arXiv, 2016.
[26] Shixiang Gu, Ethan Holly, Timothy Lillicrap, and Sergey Levine. Deep reinforcement learn- ing for robotic manipulation with asynchronous off-policy updates. IEEE International Conference Robotics and Automation, 2017.

---

[27] Irina Higgins, Loic Matthey, Arka Pal, Christopher Burgess, Xavier Glorot, Matthew Botvinick, Shakir Mohamed, and Alexander Lerehner. beta-vae: Learning basic visual concepts with constrained variational framework, In International Conference on Learning Representations, 2016.
[28] Jonathan Ho and Stefano Ermon. Generative adversarial imitation learning. In Advances in Neural Information Processing Systems, 2016.
(29] Joey Hong, David Dohan, Rishabh Singh, Charles Sutton, and Manzil Zaheer. Latent program- mer: Discrete latent codes for program synthesis. In International Conference Machine Learning, 2021.
[30] Bo-Ruei Huang, Chun-Kai Yang. Chun-Mao Lai,, and Shao-Hua Sun. Diffusion imitation from observation. In Neural Information Processing Systems, 2024.
[31] Julian Ibarz, Jie Tan, Chelsea Finn, Mrinal Kalakrishman, Peter Pastor, and Sergey Levine. How train your robot with deep reinforcement learning: lessons we have learned. The International Journal of Robotics Research, 2021.
[32] Jeevana Priya Inala, Osbert Bastani, Zenna Tavares, and Armando Solar-Lezama, Synthesizing programmatic policies that inductively generalize. In International Conference on Learning Representations, 2020.
[33] Zhengyao Jiang and Shan Luo. Neural logic reinforcement learning. arXiv, 2019.
[34] Michal Kempka, Marek Wydmuch, Grzegorz Runc, Jakub Toczek, and Wojciech Jaškowski. Vizdoom: A doom-based ai research platform for visual reinforcement learning. In IEEE Conference on Computational Intelligence and Games, 2016.
[35] Hector Kohler, Quentin Delfosse, Riad Akrour, Kristian Kersting, and Philippe Preux. Inter- pretable and editable programmatic tree policies for reinforcement learning. arXiv preprint arXiv:2405. /4956, 2024.
[36] Anurag Koul, Alan Fern, and Sam Greydanus. Learning finite state representations of recurrent policy networks. In International Conference on Learning Representations, 2019.
[37] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. Communications of the ACM, 2017.
[38] Chun-Mao Lai, Hsiang-Chur Wang, Ping-Chun Hsieh, Yu-Chiang Frank Wang, Min-Hung Chen, and Shao-Hua Sun. Diffusion-reward adversarial imitation learning. In Neural Informa- tion Processing Systems, 2024.
[39] Mikel Landajuela, Brenden K Petersen, Sookyung Kim, Claudio P Santiago, Ruben Glatt, Nathan Mundhenk, Jacob Pettit, and Daniel Faissol. Discovering symbolic policies with deep reinforcement learning. In International Conference on Machine Learning, 2021.
[40] Youngwoon Lee, Shao-Hua Sun, Sriram Somasundaram, Edward Hu, and Joseph J. Lim. Composing complex skills by learning transition policies. In International Conference on Learning Representations, 2019.
[41] Youngwoon Lee, Andrew Szot, Shao-Hua Sun, and Joseph J. Lim. Generalizable imitation learning from observation via inferring goal proximity. In Neural Information Processing Systems, 2021.
[42] Yujia Li, David Choi, Junyoung Chung, Nate Kushman, Julian Schrittwieser, Rémi Leblond, Tom Eccles, James Keeling, Felix Gimeno, Agustin Dal Lago, Thomas Hubert, Peter Choy, Cyprien de Masson d' Autume, Igor Babuschkin, Xinyun Chen, Po-Sen Huang. Johannes Welbl, Sven Gowal, Alexey Cherepanov, James Molloy, Daniel J. Mankowitz, Esme Sutherland Robson, Pushmeet Kohli, Nando de Freitas, Koray Kavukcuoglu, and Oriol Vinyals. Competition-level code generation with alphacode. Science, 2022.
[43] Jacky Liang, Wenlong Huang, Fei Xia, Peng Xu, Karol Hausman, Brian Ichter, Pete Florence, and Andy Zeng. Code as policies: Language model programs for embodied control. In International Conference on Robotics and Automation, 2023.
12

---

[44] Xi Victoria Lin, Chenglong Wang, Luke Zettlemoyer, and Michael D Emsst NI2bash: A corpus and semantic parser for natural language interface to the linux operating system. In International Conference on Language Resources and Evaluation, 2018.
[45] Zachary C Lipton. The mythos of model interpretability. In ICML Workshop on Human Interpretability in Machine Learning, 2016.
[46] Guan-Ting Ting Liu, En-Pei Hu, Pu-Jen Cheng, Hung- Yi Lee, and Shao-Hua Sun. Hierarchical programmatic reinforcement learning via learning to compose programs. In International Conference Machine Learning. 2023.
[47] Max Liu, Chan-Hung Yu, Wei-Hsu Lee, Cheng-We Hung, Yen-Chun Chen, and Shao-Hua Sun. Synthesizing programmatic reinforcement learning policies with large language model guided search. arXiv preprint urXiv:2405. 16450, 2024.
[48] Yunchao Liu, Jiajun Wu, Zheng Wu, Daniel Ritchie, William T. Freeman, and Joshua B. Tenenbaum. Learning to describe scenes with programs. In International Conference on Learning Representations, 2019.
[49] Lirui Luo, Guoxi Zhang. Hongming Xu, Yaodong Yang. Cong Fang, and Qing Li. End-to-end neuro-symbolic reinforcement learning with textual explanations. arXiv, 2024.
[50] Zhihao Ma. Yuzheng Zhuang, Paul Weng, Hankz Hankui Zhuo, Dong Li, Wulong Liu, and Jianye Hao. Learning symbolic rules for interpretable deep reinforcement learning. arXiv, 2021.
[51] Timothy Mann and Shie Mannor. Scaling up approximate value iteration with options: Better policies with fewer iterations. In Eric Xing and Tony Jebara, editors, Proceedings of the s International Conference Machine Learning, volume 32 of P Proceedings of Machine Learning Research, pages 127-135, Bejing, China, 22-24 Jun 2014. PMLR.
[52] Leandro C Medeiros, David S Aleixo, and Levi HS Lelis. What can we learn even from the weakest? learning sketches for programmatic strategies. In Association for the Advancement of Artificial Intelligence, 2022.
[53] Rubens O Moraes and Levi HS Lelis. Searching for programmatic policies in semantic spaces. arXiv preprint arXiv:2405.0543/ 2024.
[54] Taewook Nam, Shao-Hua Sun, Karl Pertsch, Sung Ju Hwang, and Joseph J. Lim. Skill-based meta-reinforcemen learning. In International Conference on Learning Representations, 2022.
[55] Kaleb Ben Naveed, Zhiqian Qiao, and John M. Dolan. Trajectory planning for autonomous vehicles using hierarchical reinforcement learning. In 2021 IEEE International Intelligent Transportation Systems Conference (ITSC), pages 601-606 2021.
[56] Richard E Pattis. Karel the robot: gentle introduction to the art of programming. John Wiley & Sons, Inc., 1981.
[57] Karl Pertsch, Youngwoon Lee, and Joseph Lim. Accelcrating reinforcement learning with learned skill priors. In Conference on Robot Learning, 2021.
[58) Zhiqian Qiao, Zachariah Tyree, Priyantha Mudalige, Jeff Schneider, and John M. Dolan. Hierarchical reinforcement learning method for autonomous vehicle behavior planning. In 2020 JEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 6084-6089, 2020.
[59] Reuven Y Rubinstein. Optimization of computer simulation models with rare events. European Journal of Operational Research, 1997.
[60] Stefan Schaal. Learning from demonstration. In Advances in Neural Information Processing Systems, 1997.
[61] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint 17X1v:1707.06347. 2017.
13

---

[62] Tanmay Shankar and Abhinav Gupta. Learning robot skills with temporal variational inference. In Hal Daumé III and Aarti Singh, editors. Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 6624-8633, PMLR, 13-18 Jul 2020.
[63] Archit Sharma, Shixiang Gu, Sergey Levine, Vikash Kumar, and Karol Hausman. Dynamics- aware unsupervised discovery of skills. In International Conference on Learning Representa- tions, 2020.
[64] Owen Shen. Interpretability ML: A broad overview, 2020.
[65] Eui Chul Shin, Illia Polosukhin, and Dawn Song. Improving neural program synthesis with inferred execution traces. In Neural Information Processing Systems, 2018.
[66] David Silver and Kamil Ciosek. Compositional planning using optimal option models. In International Conference Machine Learning, 2012.
[67] David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driess- che, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Mare Lanctot, et al. Mastering the game of go with deep neural networks and tree search. Nature, 2016.
[68] David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, Yutian Chen, Timothy Lillicrap. Fan Hui. Laurent Sifre,, George Hassabis. Mastering the game of go without human knowledge. Nature, 2017.
den Driessche, Thore Graepel, and Demis
[69] Tom Silver, Kelsey R Allen, Alex K Lew, Leslie Pack Kaelbling, and Josh Tenenbaum. Few-shot bayesian imitation learning with logical program policies. In Association for the Advancement of Artificcaa Intelligence, 2020.
[70] Shao-Hua Sun, Hyeonwoo Noh, Sriram Somasundaram, and Joseph Lim. Neural program synthesis from diverse demonstration videos. In International Conference Machine Learning, 2018.
[71] Shao-Hua Sun, Te-Lin Wu, and Joseph J. Lim. Program guided agent. International Conference on Learning Representations, 2020.
[72] Richard S Sutton, Doina Precup, and Satinder Singh. Between mdps and semi-mdps: A framework for temporal abstraction in reinforcement learning. Artificial intelligence, 1999.
[73] Yonglong Tian, Andrew Luo, Xingyuan Sun, Kevin Ellis, William T. Freeman, Joshua B. Tenenbaum, and Jiajun Wu. Learning to infer and execute 3d shape programs. In International Conference on Learning Representations, 2019.
[74] Dweep Trivedi, Jesse Zhang, Shao-Hua Sun, and Joseph J Lim. Learning to synthesize programs as interpretable and generalizable policies. In Neural Information Processing Systems, 2021.
[75] Abhinay Verma, Vijayaraghavan Murali, Rishabh Singh, Pushmeet Kohli, and Swarat Chaudhuri. Programmatically interpretable reinforcement learning. In International Conference on Machine Learning, 2018
[76] Abhinav Verma, Hoang Le, Yisong Yue, and Swarat Chaudhuri. cmiitationpproecee program- matic reinforcement learning. In Neural Information Processing Systems, 2019.
[77] Alexander Sasha Vezhnevets, Simon Osindero, Tom Schaul, Nicolas Heess, Max Jaderberg, David Silver, and Koray Kavukcuoglu. Feudal networks for hierarchical reinforcement learning. In International Conference Machine Learning, 2017.
[78] Oriol Vinyals, Igor Babuschkin, Wojciech M Czarnecki, Michaël Mathieu, Andrew Dudzik, Jun- young Chung, David Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature, 2019.
[79] Huaxiaoyue Wang, Gonzalo Konzalez-Pumariees Yash Sharma, and Sanjiban Choudhury. Demo2code: From summarizing demonstrations to synthesizing code via extended chain-of- thought. arXiv preprint 230.:v3335.16444 2023.
14

---

[80] Elly Winner and Manuela Veloso. Distill: International Conference on Machine Learning. 2003.
Learning domain-specifie planners by example. In
[81] Jiajun Wu, Joshua B Tenenbaum, and Pushmeet Kohli. Neural scene de-rendering. In IEEE Conference Computer Vision and Pattern Recognition, 2017.
[82] Peter R Wurman, Samuel Barrett, Kenta Kawamoto, James MacGlashan, Kaushik Subramanian, Thomas Walsh, Roberto Capobianco, Alisa Devlic, Franziska Eckert, Florian Fuchs, et al. Outracing champion gran turismo drivers with deep reinforcement learning. Nature, 2022.
[83] Duo Xu and Faramarz Fekri. Interpretable model-based hierarchical reinforcement learning using inductive logic programming, arXiv, 2021.
[84] Chiyuan Zhang, Oriol Vinyals, Remi Munos, and Samy Bengio. A study on overfitting in deep reinforcement learning. arXiv preprint arXiv: 06893, 2018.
[85] Linghan Zhong, Ryan Lindeborg, Jesse Zhang, Joseph Lim, and Shao-Hua Sun. Hierarchical neural program synthesis. arXiv preprint arXiv:2303.06011 2023.
15

---

Appendix
Table of Contents
A Cross entropy method details
17
A.1 CEM
17
A.2 CEMediversity
17
A.3 Cemmaabbrs
19
B Program sample efficiency
20
B.I HIPO
................................
20
LEAPS
20
B.3 HPRL
21
B.4 HC
21
C Inductive generalization
21
FARMER
21
C.2 INF-HARVESTER
22
C.3 INF-DOORKEY
22
D State machine extraction
22
E
Hyperparameters and experimental settings
22
E.1 HIPO
22
PAO
25
E.3 DRL
25
E.4 Option-Critic
25
E.S LEAPS
26
E.6 HPRL
26
E.7
F Details of KAREL problem set
27
F.I STAIRCLIMBER
27
F2 FOURCORNER
27
F3
TOPÓFF
27
F4 MAZE
27
F55 CLEANHOUSE
27
HARVESTER
27
G Details of KAREL-HARD problem set
27
G.1 DOORKEY
28
G.2 ONESTROKE
29
G.3 SEEDER
................................
29
G.4 SNAKE
29
Details of KAREL-LONG problem set
H.1 SEESAW
31
H.2 UP-N-DOWN
................................
31
H.3 FARMER
31
H.4 INF-DOORKEY
31
16

---

H.5 INF-HARVESTER
31
Designing domain-specific languages
31
Limitations
K Computational resources
33
L Impact statements
33
Cross entropy method details
A.1
CEM
Figure iillustrates the workflow of the cross entropy method (CEM). The corresponding pseudo-code available in Algorithm T
Hyperparameters list:
Population size n: 64
Standard Deviation of Noise a: 0.5
Percent of the Population Elites et 0.05
Exponential a decay: True
Maximum Iteration N,: 1000
A.2 CEM+diversity
The procedure of running CEM+diversity N times is as follows:
(1) Search the program embedding z1 by CEM (Zx: (H)
Search the 2nd program embedding 22 by CEM(G, (Zx (21)))
(N) Search the Nthh program embedding nN by CEM(G, g = (Zx {z1.... zN
Z is the set of retrieved program embeddings fzi)i=1,.., from the previous (k: - 1) CEM searches.
The evaluation function is G(z, Z+) (Ei (e )xxEC())= diversily(s, Zz), where diversity(:: 7x) = Sigmoid(- - m || Searching trajectories shown Figure
2.8,
exemplifies the influence of the diversity factor.
Noise
Sampling
Program Embedding N.
TopK Candidate Combination
For Each
iteration
Ti
Program Evaluation Function
R
R
G(-)
Figure Using the Cross-Entropy Method to search for a program with high execution reward the leamedd program embedding space.
17

---

Algorithm Cross Entropy Method
Input: Evaluation Function G, Function Input g, Maximum Iteration N,, Population Size n, Standard Deviation of Noise Percent of the Population Elites e.
2: Latent Program Search Center 2, +- [ ž1; .... 8255]: 2i ~ (0,1))
3: slep < 0
4: while slep < N₂
5: Candidate Latent Programs Z t-1 []
6: Fitness Scores LG []
7:
for + to do
8:
~ (((,o) E + [ E.,, Ei... E258 E
9:
Z.append 2, +
10: Le.append( (G((z, + E).
11: end for
12:
Elite Latent Programs Z f- Latent Programs in top e percent of ranked by Lg.
13:
f- -mean(2 (7 14:
slep 4- slep +
end while
CEM
2_0
CEM
Z,1
20
CEM 2
2_2
10
0-
-10
-20
-10
20
30
Figure CEM+diversity searching trajectories. demonstration of searching trajectories CEM+diversity procedure in the latent space. The CFM-acquired program embeddings are reduced into 2-dimensional representation with PCA. Given the diversity factor, the 2nd CEM-search exploration is ushered the opposite direction of the searching trajectory of the isl CEM-search, and the 3rd CEM-seard trajectory perpendicular to 1sl and 2nd searching paths.
18

---

A.3
CEMi-ivverityy-comaabbllll
A.3.1 Sample program sequence
In the subsequent section, we outline the procedure for sampling a program sequence V from previously determined programs Pi,iml,..,k during the search of the (k 1)st program Pk++1
(1) Uniformly sample program Pj from all programs (p1,.., Pk. Pk+1), and add Pj to
V.
(2) Repeat (1) until the (k + 1)st program Pk+1 is sampled.
(3) Uniformly sample program Pj from {pr,-.. - Pk, Pk++1 1 Premm) where Atem represents the termination program, then append Pj to V.
(4) Repeat (3) until Pemm is sampled.
(5) Return V with length greater equal to Limins where Linin is hyperparameter that indicates the minimum length of sampled sequence. Re-sample Y otherwise.
A.3.2 The score function
The score function G(2, 7x) for CEM-divvrsityycoomatblll:::
((2 D
Rv, diversitylz, Zx)
(2)
Rv.
(3)
V.
| denotes the number of programs in the program list M, V.[i] represents the j-th program in the program list V,, and is the discount factor.
A.3.3 CEM-diivesiiyyy+ooppiibblllll procedure The procedure of running CEM-diivesityy+oomaiibllyy |M| times in order retrieve |M| programs:
(1) Retrieve 1st program 21-
a. Sample a program sequence V==1 with k 0
b. Deploy CEM+diversity N times with Z4 = } to acquire N program embeddings.
Select the program embedding with the highest score G(z, 7 ()) 21, among the N program embeddings.
(2) Retrieve 2nd program 22-
Sample program sequence 1,2 with k previously determined program.
b. Deploy CEM+diversity N times with Z₁. = {21} J. to acquire N program embeddings.
Select the program embedding with the highest score G(z, Zu {z1 }) among the N program embeddings.
(M Retrieve |M th program Z|M--
a. Sample program sequence W V,.i=I..... MI-1 with h: = |M| previously determined programs.
b. Deploy CEM+diversity N times with Zi = {21, 22, 2 M - to acquire N program embeddings.
c. Select the program embedding with the highest score G(z, Zx = {21, 22, -[M)-1)) 2jM), among the N program embeddings.
19

---

Farmer
Inf Doorley
Inf Harveseer
84
HPRL
HPAL
HPRL
0.
Option Searching
Option Searching
Option Searching
HIPO
HIPO
HPQ
TAMAT
14
83
02
0.2
03
11
00
Eicecated Rogroms
Figure 7: Program sample efficiency. Results different programmatic RL approaches in FARMER, INF- DOORKEY, HNE-HARVESTER.
Inf-Harvester
LEAPS Option Searching
LEAPS
LEAPS
Option Searching
Option Searching
HIPO
MEam
Figure 8: Sample efficiency. Results of different programmatic RL approaches in FARMER, NN--DORKKEY. INF-HARVESTER.
B Program sample efficiency
Generally speaking. programmatic RL approaches incorporate three-step training procedure, in which program will be first synthesized, exectued, then evaluated with respect given task. The three-step procedure is iteratively applied until the return converges or the maximum training step is reached. "Program Sample Efficiency" "eariency"-refeerrin to how effectively the method achieves desired return using an efficient number of the three-stey step procedure is crucial for analyzing and comparing efficiency of our approaches against the baselines. As Figure illustrates, HIPO (our method) obtains the best program sampling efficiency in FARMER and INF-DOOR KEY. Details of the program sample efficiency calculation for each baseline are elaborated the subsequent sections.
B.1 HIPO
the program searching phase HIPO, up to 50 CEM-searches are conducted to fetch programmatic options. Each CFM-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 Figure 7 the return is counted as the highest return obtained from sequential execution of the programmatic options, based the order indicated by the sampled random sequence.
Afterward, during the high-level policy training phase (indicated by the red curve Figure 77. the three-step procedure is executed once per PPO training step. The return is recorded as the maximum validation return achieved the HIPO manner, where the high-level policy continuously selects and deploys a program to solve long-horizon task.
B.2 LEAPS
In the program searching process of LEAPS, 216 CEM-searches are performed to obtain the targeted program, accordance with the settings in [74. In each CFM-search, up to 1000 iterations are performed, in which the three-step procedure is executed times, where is the population size of
20

---

Inf-Doorkey
Inf-Harvester
Pur Terfeemance Diop DS1
-22
223
-42
-42
1100
310
P1C
PHG
DEL
D3L
42
HPRL
HC
Expected Horizn Langos
Figure 9: Inductive generalization. Experiment results different baselines in FARMER, DOORKEY, and INE-HARVESTER.
the CEM-search. The return for certain number exccuted programs is recorded as the maximum return obtained from executing the previously searched programs only.
B.3 HPRL
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 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.
B.4 HC
In the program searching progress of HC, 250 neighbors are sampled and executed to obtain the targeted program for each iteration. Up 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.
C Inductive generalization
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 alllngaand-oollecting rounds that we expect the agent to accomplish (please refer to Section 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-es and-collecting process. In other words, all policies among baselines are trained to terminate after 10 placing and- picking iterations. Nevertheless, the upper limit numher 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 DI-NN-DWN (i.e., more than half of baseline approaches have mean return close to 0.0 these tasks), conduct experiments mainly on FARMER, -N--DOOR,EY, and INT-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 I. The detailed settings and experimental results for each of these three tasks presented below.
C.1 FARMER
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 Figure as the expected horizon length increases, the performance of all baselines except HIPO declines significantly. This
21

---

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
C.2 INF-HARVESTER
During the training phase of all baslines, the emerging probability 15 and 32 in the testing phase. As shown in Figure as the expected modified this number to 2. g. T6 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 provided in Section
2.2 Following this, we
C.3 INF-
During the training phase of all baselines, the upper limit number of marker-picking and marker- placing is 16. Then, modified this number to 32, 64, 128, and 256 in the testing phase. As shown in Figure as the expected horizon length grows, the performance of all the baselines drop significantly. Nevertheless, HIPO has minor performance drop compared other baselines. Further details on the definition of the upper limit number are provided in Section H
D State machine extraction
In approach, since the high-level neural network policy is incorporated, the proposed HIPOO is only partially or locally interpretable once the the high-level policy selects a programmatic option, human can recognize the following execution of the program.
To further increase the interpretability of the trained high-level policy Se. we extracted 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 x 32 vector, which is then quantized into a hyperparameter h balances between the simplicity of the finite state machine and performance drop. Using these quantized vectors, we can construct a taate-transiton 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 TO Figure 11 and Figure 12
vector. The
E
Hyperparameters and experimental settings
E.1
HIPO
E.1.1
Encoder & decoder
We follow the training procedure and the model structure proposed in (74, which uses the GRU [5 network to implement both the encoder qu and the decoder pe with hidden dimensions of 256. The encoder qy and decoder are trained on programs randomly sampled from the Karel DSL. The
Figure 10: Example of extracted state machine on FARMER. O1 to O31 represent the unique guantized
vectors encoded from observations. The corresponding programs of M1 to M5 are displayed in Figure 23
22

---

01, OR,
011
0l. 01.03,00 011
01,00, O8, OR
XOL
0:0
04 on
Os OS On
M5
Pa Os
02
Figure 11: Example extracted machine on INF-DOORKEY. OL O11 represent unique
quantized vectors encoded from ohservations. The corresponding programs of to M5 are displayed in Figure 24
04
M2
02
01, 02, 03, 04
MI
01, 02, 03
04
cnd
Figure 12: Example of extracted state machine INF-HARVESTER. O1 to O4 represent the unique quantized vectors encoded from observations. The corresponding programs of M1 to A/3 are displayed in Figure 25
23

---

State
High-level Palicy fs
Next Option
m i-1
Current Option
m
Termination
Meeem
Reward
while hontisClear) meve()
roMaarkaaPPosset) putMarker))
putMonkert)
movel]
Pm::
Pm.
run frantlsCleen)): move() turnLeft)
rundl:
FresemF piciMarieen]
[r]
Pma
Pma
Environment
State of
Exacution
Action of
Figure 13: High-level policy execution.
loss function for training the encoder-decoder model integrates the 3- V-V 27 loss, the program behavior reconstruction loss (74). and the latent behavior reconstruction loss 74
The program dataset used to train Qg and Po consists of 35,000 programs for training and 7,500 programs for validation and testing. Program tokens sequentially sampled for each program based on defined probabilities until an ending token is reached or the maximum program length of 40 is attained. Defined probabilities of each type of token listed below:
WHILE: 0.15
REPEAT: 0.03
STMT_STHH 0.5
ACTION: 0.2
IF: 0.08
IFELSE: 0.04
Note: the token STNT_STиT represents 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 's length, as well as the quantity and complexity of nested loops and statements.
E.1.2 Programmatic options
We conduct the procedure described in Section A.3.3 search programmatic options for each high- level policy. For tasks only involving skills of marker-picking and traversal, i.e., INE-HARVESTER, SEESAW, and UP-N-DOWN, designate the number of programmatic options as [M] 3, while for the remaining tasks, |M| = 5.
E.1.3 High-level policy
The high-level policy far whose training process is illustrated in Figure K comprises convolutional layers 22 37 to extract features from the Karel states and fully connected layers to determine the next program for execution. Mcanwhile, 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 adopted optimize the high-level policy fa. Hyperparameters are listed below:
Maximum program number: 1000
Batch size: 32
Clipping: 0.05
24

---

a: 0.99
y. 0.99
GAE lambda: 0.95
Value function coefficient: 0.5
Entropy coefficient: 0.1
Number of updates per training iteration:
Number of environment steps per set of training iterations: 32
Number of parallel actors: 32
Optimizer: Adam
Learning rate: (0.1, 0.01, 0.001, 0.0001, 0.00001)
E.2
PAO
The implemented PAO resembles the setting in Section E. The input, output, and structure of the high-level policy f& remain the same. However, the low-level programs are replaced by primitive actions (move, turnLeft, turnRight, putMarker, ciMMakeer)
E.3 DRL
DRL training on the Karel environment implemented with the PPO 61 algorithm with 20 million timesteps. Both the policy and value networks share a convolutional encoder interpreting the state of the grid world. This encoder comprises two layers. The first layer comprises 32-filters, a size-4 kernel, and stride of 1. The following layer has 32 filters, size-2 kernel, and the same stride of The high-level policy neural network yields the probability distribution among primitive actions (move, turnleft, turnRight, putMarker, pickMarker) and termination, given the current environmental state as input. our experiments with DRL on Karel-Long tasks, all hyperparameters are fixed as listed below, except for learning rates tuned in grid-search manner.
Maximum horizon: 50000
Batch size 32
Clipping: 0.05
a: 0.99
y: 0.99
GAE lambda: 0.95
Value function coefficient: 0.5
Entropy coefficient: 0.1
Number of updates per training iteration:
Number of environment steps per set of training iterations: 128
Number of parallel actors: 32
Optimizer: Adam
Learning rate: (0.1, 0.01, 0.001, 0.0001, 0.00001)
E,4
Option-Critic
Option-Critic training on the Karel environment is implemented with the option-critic architecture A. algorithm with 20 million timesteps. The state inputs 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, size-2 kernel, and the same stride of 1. In our experiments with Option-Critt Critic on Karel-Long tasks, all hyperparameters are listed below.
Maximum horizon: {2000, 4000, 6000. 8000, 10000)
Number of options: [2, 3, 4. 5)
25

---

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
E.5 LEAPS
Following the setup detailed in [74], we conducted experiments with various CEM-related hyperpa- rameters listed below, in order to optimize rewards for LEAPS.
Population size (n): (8, 16, 32, 64)
a: {0.1, 0.25, 0.5}
e: [0.05, 0.1, 0.2)
Exponential a decay: (True, False)
Initial distribution P:
E.6 HPRL
Aligned with the approach described in [46], we trained the meta-policy for each task to predict program sequence, with hyperparameters listed below.
Max subprogram: 5
Max subprogram Length: 40
Batch size: 128
Clipping: 0.05
o: 0.99
7: 0.99
GAE lambda: 0.95
Value function coefficient: 0.5
Entropy coefficient: 0.1
Number of updates per training iteration: 4
Number of environment steps per set of training iterations: 32
Number of parallel actors: 32
Optimizer: : Adam
Learning rate: 0.00001
Training steps: 25M
E.7 HC
According [10.
performed the stochastic hill climbing search to find the resulting program. Hyperparameters are listed below.
Number of neighbor candidate programs: 250
Number of parallel actors: 16
Total number of evaluated programs: 1000000
Maximum function calls: 10000
26

---

Details of KAREL problem set
Introduced in Trivedi et al. (74), the KAREL problem set includes 6 tasks: STAIRCLIMBER, FOUR- CORNER, TOPÔFF, MAZE, CLEANHOUSE and HARVESTER. Figure 14 and Figure T3 depict randomly generated initial states, legit sampled internal states, and desired final states for each task. The experimental results in Table avveaage 32 rewards obtained across 32 randomly generated initial states of the environment.
F1 STAIRCLIMBIR
In 12 12 grid environment, the agent's task is climb the stairs and reach designated marked grid. Both the agent's '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 for reaching the goal, -1 1 for moving off the stairs, and otherwise.
FOURCORNER
In 12 12 grid environment, the agent is tasked with placing a marker each of the four corners. The agent receives no reward for placing marker anywhere on the grid other than the four corners. Each successful marker placement unmarked corner earns reward of 0.25.
F.3 TOPÓFF
In 12 x 12 grid environment, the agent's objective to place a marker on every grid cell columns where the bottom row has 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 it places marker on an empty cell in the bottom row or marked cell.
F.4 MAZE
In 8 x 8 grid environment, the agent is tasked to find marker by navigating the grid environment. The marker's 's location, the initial agent position, and the maze layout configuration are randomly initialized. The agent receives sparse reward of 1 for successfully finding the marker in the environment, and otherwise.
F.5 CLEANHOUSE
In 14 x 22 grid environment, the agent's target is to collect scattered markers as many possible. The initial location of the agent is fixed, whereas the scattered markers are randomly placed within the environment, adjacent walls. The return is calculated as the ratio of the number of collected markers to the total number of initially designated markers.
F.6 HARVESTER
In x 8 grid environment, initially populated with markers in all grid cells, the agent's objective to pick up a marker from each location within. The return calculated as ratio of the number of picked markers to the total number of initially placed markers.
G Details of KAREL-HARD problem set
The KAREL-HARD problem set proposed by Liu et al. 466 involves 5 tasks: DOORKEY, ONE- STROKE, SEEDER and SNAKE. Each task in this benchmark is designed to 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 I average 32 rewards obtained across 32 randomly generated initial states of the environment.
27

---

(a) STAIRCLIMBER
(b) FOURCORNER
(c) TOPOFF
T
-
-
(d) MAZE
Figure 14: Visualization of STAIRCLIMBER FOURCORNER, TOPOFF, and MAZE in the KAREL problem set presented in Trivedi et al. 74. For each task, random initial state, a legitimate internal state, and the ideal end state shown. In most tasks, the position of markers and the initial location of the Karel agent are randomized, More details of the KAREL problem set can be found in Section F
G.1 DOORKEY
In an 8 grid environment, partitioned into left room and 6 right room by column of walls, the agent's objective is to collect key (represented by 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 the target.
28

---

(a) CLEANHOUSE
(b) HARVESTER
Figure 15: Visualization of CLEANHOUSE and HARVESTER in the KAREL problem set presented in Trivedi al. (74) For each task, a random initial state, a legitimate internal state, and the ideal end state are shown. More details of the KAREL problem set can be found in Section
G.2 ONESTROKE
In 8 x 8 grid environment, the agent is tasked to navigate through all grid cells without revisiting any them. An empty grid cell replaced with a wall once visited. The episode ends once the agent collides with any of these walls. The return is calculated the ratio of visited grids to the total number empty grids in the initial environment.
G.3 SEEDER
In an 8 x 8 grid environment, the agent's task is to place one marker 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.
G.4 SNAKE
In 8 x grid environment, the agent operates the snake's head and seeks to consume (pass- through) as much food (markers) as possible without colliding with own body. The snake's body grows by 1 grid cell for each marker consumption, and new marker appears at different location.
29

---

Throughout the episode, only one marker exists in the environment. The reward is defined as 20 which is the reciprocal of the targeted number of marker consumption, for each marker consumption.
(c)
6/1
Figure 16: Visualization of SEESAW in the KAREL-LONG problem set. This figure partially illustrates typical trajectory of the Karel agent during the task SEESAW. (a): Once the Karel agent collects a marker in the left chamber, new marker appears in the right chamber. (b): The agent must navigate through the central corridor to collect the marker the right chamber. (c): Once the Karel agent collects a marker in the right chamber, new marker further appears in the left chamber. (d): Once again, the agent is traversing through the corridor the left chamber. (e): new marker appears in the right chamber again after the agent picks up the marker in the left chamber. (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 have set the number 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
randomized. Also, note that
H Details of KAREL-LONG problem set
We introduce the novel KAREL-LONG problem set a benchmark evaluate the capability of HIPO. Each task in our KAREL-LONG benchmark is crafted to exhibit long-horizon characteristies derived from Karel states. Additionally, we ensure that these tasks maintain constant per-action cost, set at 0.0001. Figure 16 Figure 17 Figure [8] Figure 19 and Figure 20 depict the tasks within the K KARFI-LLONG problem set, exhibiting randomly generated initial states and several internal states sampled from legitimate trajectories.
30

---

H.1 SEESAW
In 16 16 grid environment, the agent's 's objective is to traverse back and forth between two x 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 x corridor. Initially, one marker is positioned in the left chamber, awaiting collection by the agent. Upon picking marker in chamber, another is randomly generated in the opposite chamber, continuing the agent's s task of collecting markers. Consequently, the agent must navigate between the two chambers 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."
H.2 UP-N-DOWN
In 8 x 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 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."
The agent would receive an additional constant penalty (i.e., -0.005) for being
H.3 FARMER
In am 8 8 grid environment, the agent's objective is twofold: initially, 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 farmer collecting crops. Following this, the agent is prompted to refill the environment again, and the cycle repeats. We've imposed maximum iteration limit to represent the anticipated number of alling-and-collettng rounds. The return is calculated as the ratio of the number of seieeddand-plaeeee markers to the total theoretical capacity of termed as "max markers." "
markers,
H.4 INF-DOORKEY
In an 8 x grid environment, partitioned into chambers, the agent tasked to pick up markers in certain chambers, place markers in others, and continuously traverse between chambers until predetermined upper limit number of marker-picking and marker-placing is reached. As mentioned earlier, the environment partitioned into 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 advance and perform another action. The return is calculated as the ratio of the number of bocked-and-plae the total number of markers that the agent can theoretically pick and place, referred as "max keys."
markers to
H.S INF-HARVESTER
In 16 x 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 a probability, termed the "emerging probability." that a new marker will appear in 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 specific emerging probability.
I Designing domain-specifie languages
Our program policies are designed to describe high-level solkiso procedures or decision- maainn logics of an agent. Therefore, our principle of designing Nomain-specine 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 donain-indeependent perceptions and actions can be designed based on the domain of interest, requiring specific expertise and domain knowledge.
31

---

Table 3: Performance of programmatic policies KAREL-LOON across thirty-two random seeds. Mean return and standard deviation of all methods across the KAREL-LONNG problem set, evaluated over thirty-two random seeds.
Method
SEESAW
Up-N-Down
FARMER
INF-DOORKEY
INF-HARVESTER
LEAPS
0.00 + 0.01
0.01 = 0.01
0.02 + 0.00
0.00 0.01
0.11 = 0.00
HPRL
0.00 1 0.00
0.00 1 0.00
0.02 1 0.00
0.01 1 0.01
0.49 1 0.07
HC
0.23 + 0.10
0.14 = 0.27
0.24 + 0.06
0.21 + 0.13
0.89 = 0.00
HIPO (Ours)
0.50 + 0.14
0.72 + 0.07
0.51 + 0.22
0.65 0.08
0.76 + 0.04
Such DSLs are proposed and utilized in various domains, including ViZDoom [3]. 2D MineCraft [ 71]. and sym-minigrid [14). Recent works [43 [79] also explored describing agents' behaviors using programs with function-taking arguments.
Limitations
While the Hierarchical Programmatic Option (HIPO) Framework provides notable advantages includ- ing 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 33 LLM-based interpretation [4]. and decision tree
policies 7 351 are also specifically designed to create interpretable, explainable, and generalizable
agents for solving MDPs.
In environments with large state or action spaces, neuro-symbolic methods adopting symbolic policies 19 33
33 are generally less computationally intensive and more feasible for training compared to programmatic approaches like this work and [10 46 (4), However, symbolic policies
50
[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 inter- pretability. 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 the environment and the quality 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 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 plausible training scheme. 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 basclines, including DRL, where deep neural networks were used as expert policies in 7 learning decision trees. This suggests that decision- methods 7 35 are unable to surpass our HIPO framework due the limitations of the underperforming DNN expert. In [7]. the authors propose methods for verifying decision-tree tree policies. The structure of decision trees contributes to efficient verification, allowing for quantitative assessment of the policy's '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 quantitatively verify programmatic policy remains significant challenge.
35 demonstrate trajectories for
32

---

Finally, while HIPO retrieves set of effective and compatible programs through search method, exploring approaches that leverage prior knowledge, e.g., large language models [47] offline
datasets in imitation learning [12 28 30
38
41
60 or skill-based reinforcement learning 40 54 57
to efficiently retrieve programs is promising research direction.
K Computational resources
For our experiments, utilized the following workstation: 20-core Intel(R) Xeon(R) W-2255 CPU 3. 3.70GHz, with 2X NVIDIA GeForce RTX 4070 Ti GPU
The rough computation time for the main experiments of our framework and baselines are follows:
SEESAW
(a) DRL: 24 hours
(b) LEAPS: hours
(c) HPRL: 48 hours
(d) HIPO: 48 hours
2. UP-N-DoWN:
(a) DRL: 24 hours
(b) LEAPS: 48 hours
(c) HPRL: 48 hours
(d) HIPO: 48 hours
3. FARMER:
(a) DRL: 24 hours
(b) LEAPS: 48 hours
(c) HPRL: 48 hours
(d) HIPO: 72 hours
4. NNF-DOORKEY:
(a) DRL: 24 hours
(b) LEAPS: 48 hours
(c) HPRL: 48 hours
(d) HIPO: 72 hours
5. INF-HARVESTER:
(a) DRL: 24 hours
(b) LEAPS: 48 hours
(c) HPRL: 48 hours
(d) HIPO: 48 hours
L Impact statements
Our work introduces Hierarchical Programmatic Option framework (HIPO), 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, 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 acknowledge the importance of continuous efforts to ensure that Al systems, including HIPO, adhere to ethical standards and contribute positively to society.
33

---

(c)
(f)
g
Figure 17: Visualization of UP-N-DoWN in the KAREL-LONG problem set. This figure partially illustrates typical trajectory of the Karel agent during the task UP-N-Dow (a): The Karel agent ascending the stairs collect load located above the stairs. Note that the agent can theoretically collect the load without directly climbing up the stairs, but will receive some penalties for doing so. (b): Once the agent collects the load, new load appears below the stairs. (c): The agent then descends the stairs to collect a load located below. Note that the agent can theoretically collect the load without directly climbing down the stairs, but will receive some penalties doing so. (d): Upon the agent collecting the load, new load appears above the stairs. (e): The agent once again ascends the stairs collect a load. (f): A new load appears below the stairs again after the agent collects the load located above. (g): The agent would continue to collect the emerging loads in descend-ascent cycles repeatedly on the stairs. Note that the locations of all the emerging loads are randomly initiated right next to the stairs. The load must appears below/above the stairs after the agent just finished ascending/descending. Also, we have fixed the number of emerging loads to 100 during the training phase (i.e., the agent shall collect 100 loads to complete the task). More details of the task UP-N-DOWN can be found Section
34

---

(e)
(a)
(d)
(b)
Figure 18: Visualization of FARMER the KAREL-LONG problem set. This figure partially illustrates typical trajectory of the Karel agent during the task FARMER. (a): The Karel agent is filling (placing) the entire environment layout with markers. In the initial state, there exists a single marker located in the upper-right corner. The marker is purposed to prompt the agent to start filling the environment layout. (b): The agent successfully populates the entire environment. (c): The agent is then asked to pick up markers much possible. (d): The agent successfully picks all markers up, leaving the environment empty. (e): there is another fillig--add-collectnn round, a marker will appear in the upper-right corner indicate that the agent should start the filling process again. 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 720 during the training phase (i.e., the agent has to fill the entire environment layout with markers and pick all markers each 10 times fully complete the task.) More details of the task FAR FARMER can be found in Section
35

---

Figure Visualization of INF-DOORKEY the KAREL-LONG problem set. This figure partially illustrates a typical trajectory of the Karel agent during the task INF-DOORKEY. (a): The Karel agent picks up marker the upper-left chamber. Then, a passage to the upper-right chamber opens, allowing the agent to traverse through. (b): The agent successfully places marker at marked grid located in the upper-right chamber. Subsequently, passage to the lower-right chamber opens, allowing the agent traverse through. (c): After the agent collects a marker in the lower-right chamber, a passage to the lower-left chamber opens, allowing the agent to traverse through. (d): The agent properly places marker at marked grid located in the lower-left chamber. After that, passage to the leper-left chamber opens, and a new marker appears in the upper-left chamber. (e): Upon the agent picking up 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 marker at marked grid located in the upper-right chamber. Afterward, the passage the lower-right chamber opens again, and 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 pick and place 100 markers in total fully complete the task.) More details of the task INF-DOORKEY KEY can be found in Section
36

---

(c)
$1
(f)
rigure 20: Visualizaali of INT-HARVESTER the KAREL-LONG problem set. This figure partially illustrates legitimate trajectory of the Karel agent during the task INF HARVESTER. (a): The Karel agent picks up markers in the last row. Meanwhile, no new markers are popped out the last row. (b): The agent turns left and picks up 6 markers in the 7th column while 3 markers appear in previously empty grids in the last row. (c): The agent collects markers in the 8th row while marker appears in previously empty grid in the 7th column. (d): The agent picks up 6 markers in the 5th column while 2 markers appear in 2 previously empty grids in the 7th column. (e): The agent picks up more markers in the last row while markers appeared in previously empty grids in the 5th 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 new markers appear in the environment. The emerging probability has been fixed to 2 during the training phase.
More details of the task INF-HARE HA--HAREESS ESTER ESTER can be found in Section
H
37

---

H
-H
(a) DOORKEY
(b) ONESTROKE
(c) SEEDER
(d) SNAKE
Figure 21: Visualization of each task in the LAREL-HARD problem set proposed by Liu et al. (46).
For each task, random initial state, some legitimate internal state(s), and the ideal end state are shown. More details of the KAREL-HAR problem can be found in Section G
38

---

Karel Programs
SEESAW
Option
Option 2
Option 3
run c( frontlatlenr c) turnlaft
xove
WHILE c( markorsPrenent
rove pickHarker
c) w( pickKarker terakigat
NHILE frentiscicar c)
pichMarker turnlett
7(
WHILE o( narkorsPreeent
c) u(
IF c( frontinClear
pickkarzor
pickBarker
8) WHILE ot frontInclear c)
nove pickNarker
WHILE of markeraPreeant
<) R( packHarker
pickMarker
pickKarker
1) nove
4)
frontIsClear pichNarzer nove PickNarker
noye pickMarker
UP-N-DOWN
Option
Option 2
Option 3
n(
DEF
DEP =
fronsleClear nove nove
zore
moye
suraRight
tarnBight
aes leftIeClear
tarnLeft
e) c) 1(
nove
UaraRight
turnLert
aove
tarnBight
turaleft
nove
turaRight
turnLert
move
tarnBight
turateft
move
tarnBight
turnLeft
move
CuraRight
move
turnBight
turnleft
move
CaruRight
turnCwft.
move
tarnRight
Figure 22: Example programs on Karel-Long tasks: SEESAW and UP-N-DOWN, The programs with best rewards out of five random seeds are shown. |M 3 for SEESAW and Jp-N-DowN.
39

---

Karel Programs
FARMER
Option
Option 2
Option
DEF run n(
DEF ron suraRight
DEP run m
pickMarker
taraRight
REPEAT R-0
PickNarker
putMarker
tarnkiggs gbt
D070
turaRighs
patHarker
tureRight
Booe
pickMarker
pickMarker
putNarker
p PickMarker PatHarker
turaLett
zore
DoVe
pickMarker
noye
putNarker
PickMarkor
buxeRight
Patkakker
PickMarkor
Bove
turnleit
putNarker
P PickMarkor
patkakker
PickMarkor
pickMarker
PutMarker
p PickMarker
KutMarkez
tuxuteit
pickMarker
PutNarker
P PickMarker
zove
PatMacken kez
pickMarkox
aoye
LurntaCt
80ye
pickMarker
nove
r)
Option 4
Option 5
rua n( REPEAT R-1? r( IF c( not of rightlsGlear
putharker
PiczMarker
turaRight
zove
putHarzer nove 4)
PickMarker
turallghh ght
pickMarker
patMaakkrr
zoVe
pickMarker
putMarker
ZoYe
pickMarker
putMarkor
zove
PickHarker
PutNazkor
PickMarker
PutMarker
zove
Figure 23: Example programs on Karel-Long tasks: FARMER. The programs with best rewards out of five random seeds are shown. [M] = 5 for FARMER.
40

---

Karel Programs
INE-DOORKEY
Option
Option 2
Option 3
DEP
soMarkaraPreeant
MatMarker p pickMarker IP c( not ot parkeraPrezent. > 1( nove i) soMarkaraPraamnt w( IPELSR e( markeraPrazent
noNarkeraPresont c)
putMarker
nove TF ct
ELSE
coMarkers
pickFarker putMarker
nave REPEAT R-1 x(
corslaft r
1)
turnlets
1)
i)
2ofarkorePreeent
move
nove
turniight gh
AEPEAT R-1 r(
8)
r(
zove
n)
Option
Option 5
a( putNarker
turnRight.
turaleft
IF e( luftIaClens c) 1 turnteft
piekMarker
turnleft
putMazker
IFELSR et parkersPrezent e) L(
IP ol leftIaClanr c) 1( tarnlatt
turnlaft
pickMarker
i) ELSE o
sove
IF c lefeIaCiear c) 1(
1)
m)
putNarker
InfcIaClear e) i(
turnlett
()
pickMarker
Figure 24: Example programs on Karel-Long tasks: INF-DOORKEY. The programs with best rewards out of five seeds are shown. |M] 5 for INF-DOORKEY.
41

---

Karel Programs
INT-HARVESTER
Option
Option 2
Option
DEF zus a(
DEF ren
DEP run =t REPEAT RH5 x( turnLeft
REPEAT R 2( turnLact
SHILE o( frontIsClear c)
Bove
frontIaClear
REPEAT R-B r(
3 it
pickMarker
Lurnleft
IF c(
VHILE
frontIaClear c) 4( PickMarker zove
turnleft
pickMarker
B) o plekMazker
nove
pickMarker
e( trontlaClesr c) 5( PiekMarker
pickMurker
T) turnlaft
BoYe
pickMarker
REPEAT R-3 pickMarker +)
p1 DickMarker
i) fronsInclear
pickMarker
pickNarker
pickMarker 810 V1
pickMarker
pickMarieer
pickMarker ROYe
pickMarker
pickMarker
nOVe pickNarieer
PickNarker
noye
pickMarker
pickMarker
+)
n)
Figure 25: Example programs Karel-Long tasks: INF-HARVESTES The programs with best rewards out five random seeds are shown. [M] = 3 for INF- HARVESTER.
42

---

NeurIPS paper checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The abstract and introduction clearly state the claims made.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The details are shown Section J
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [NA]
43

---

Justification:
The paper does not include theoretical results.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
The details shown in Section
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
44

---

Answer:
[No]
Justification:
We will release the code as soon as possible.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ cpippi.ccppulli//uuuii wwwtii/gguie///eeeeceoocc CoodeSubeiiieeee ssi wsionnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The details are shown Section Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: The paper reports the means and variances of the experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
45

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The compute resources are shown in Section K
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http://eerrrp.ppeee http:/ps...//llll/chhccccciaanno
Question:
Answer: [Yes]
Justification: The research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations their jurisdiction..
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
The statements are shown in Section
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
46

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is 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 being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there 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 monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have 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 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 best faith effort.
12. Lieenses for existing assets
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?
Question:
Answer: [Yes]
Justification: The original publications that produced the assets are cited.
Guidelines:
The answer NA means that the paper does 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 URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.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, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of 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.
47

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/mooel as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
48


Reviews:
[{"review_id": "AFqMAMRzWS", "reviewer": "Reviewer_x8GU", "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.", "questions": "Please feel free to comment on the points listed under weaknesses. In addition to them, I will add the following questions and comments.\n\n1. 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?\n\n2. 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.\n\n3. 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?\n\n4. 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.\n\n5. 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": "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.", "rating": 7, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "The idea of using programmatic representations to learn options is interesting and valuable. The authors correctly state that using programmatic policies as options as opposed to policies means that one sacrifices, to some extent, the interpretability of the policies in favor of performance.\n\nAnother strength of HIPO is its natural combination of programmatic and neural representations -- this is not mentioned in the paper and perhaps it should! The repetitive behavior required to solve the tasks is given by the programmatic options, which can achieve this through the strong inductive bias the Karel language offers. The neural policy is then responsible for orchestrating these different components, which would clearly be difficult through program synthesis.\n\nI am particularly impressed by the results on the DoorKey domain. This is such a difficult domain for program synthesis and DRL. HIPO managed to achieve a really high score in that domain. I do have some clarifying questions about this result (please see them in the Questions section of this review).\n\nI also appreciated the extra effort the authors put into translating the neural model that orchestrates the options into automata for interpretability. Since the automata can also be seen as programs, it would be interesting to see their performance or even their translation into the Karel language.", "weaknesses": "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.\n\n1. HIPO represents a method for learning programmatic options, but it includes no option-learning baseline.\n2. 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.\n3. 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.\n4. 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.\n\nOverall, 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the thorough and constructive comments. Please find the response to your questions below.\n\n> Option-learning baselines\n\nAs suggested by the reviewer, we additionally experimented with the option-critic architecture [1] and reported the comparison to our method below.\n\n| Method | Seesaw | UP-N-Down | Farmer | Inf-DoorKey | Inf-Harvester |\n|-|-|-|-|-|-|\n| Option-critic | 0.00 $\\pm$ 0.00 | 0.00 $\\pm$ 0.00 | 0.00 $\\pm$ 0.00 | 0.00 $\\pm$ 0.00 | 0.47 $\\pm$ 0.01 |\n| HIPO (Ours) | **0.53** $\\pm$ 0.10 | **0.76** $\\pm$ 0.02 | **0.62** $\\pm$ 0.02 | **0.66** $\\pm$ 0.07 | **0.79** $\\pm$ 0.02 |\n\nThe 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.\n\n> Search in the programmatic space\n\nAs 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].\n\n| Method | Seesaw | UP-N-Down | Farmer | Inf-DoorKey | Inf-Harvester |\n|-|-|-|-|-|-|\n| HC | 0.22 $\\pm$ 0.08 | 0.63 $\\pm$ 0.26 | 0.19 $\\pm$ 0.03 | 0.14 $\\pm$ 0.16 | **0.88** $\\pm$ 0.00 |\n| HIPO (Ours) | **0.53** $\\pm$ 0.10 | **0.76** $\\pm$ 0.02 | **0.62** $\\pm$ 0.02 | **0.66** $\\pm$ 0.07 | 0.79 $\\pm$ 0.02 |\n\nThe 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.\n\n> Environment-step sample efficiency\n\nWe thank the reviewer for the suggestion. We will add this plot to the revised paper.\n\n> More runs of the experiments >30 and confidence intervals\n\nWe 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.\n\n> Performance of HIPO in DoorKey\n\nThe 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.\n\nDue 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.\n\n> Best order used in the composability step\n\nAs 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.\n\n| Method | DoorKey | Seesaw | UP-N-Down | Farmer | Inf-DoorKey | Inf-Harvester |\n|-|-|-|-|-|-|-|\n| Best Random Sequence | **1.00** $\\pm$ 0.00 | 0.04 $\\pm$ 0.02 | 0.17 $\\pm$ 0.08 | 0.05 $\\pm$ 0.03 | 0.06 $\\pm$ 0.06 | 0.60 $\\pm$ 0.02 |\n| HIPO (Ours) | **1.00** $\\pm$ 0.00 | **0.53** $\\pm$ 0.10 | **0.76** $\\pm$ 0.02 | **0.62** $\\pm$ 0.02 | **0.66** $\\pm$ 0.07 | **0.79** $\\pm$ 0.02 |\n\nThe 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.\n\n> Termination option\n\nWe 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.\n\n> A short program that is able to collect an arbitrary number of markers\n\nYes, 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.\n\n> I would like to challenge the desiderata of the options (lines 136-139).\n\nWe thank the reviewer for the insight. We will remove “(i.e., obtain some task rewards)” from the definition of effectiveness.\n\n> Diversity score for programmatic spaces\n\nWe 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.\n\n---\n\nReferences:\n\n[1] Pierre-Luc Bacon, Jean Harb, and Doina Precup. The option-critic architecture. In Association for the Advancement of Artificial Intelligence, 2017.\n\n[2] Tales Henrique Carvalho, Kenneth Tjhia, and Levi Lelis. Reclaiming the source of programmatic policies: Programmatic versus latent spaces. In ICLR, 2024.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nRixGzSabp", "reviewer": "Reviewer_ukMP", "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.", "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).\n* 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. \n* What's the percentage of retrieved program (based on your effectiveness and diversity criterion) ?", "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.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper is sound and clear. The structure is clear, the contributions easily identifiable, the figures, table are easily understandable. \nI am not a deep expert of option or program synthesis, but the paper is so clear that it brought me sufficient insight to situate it and understand its method. The KAREL-LONG test-bench is well motivated, as one can see that the original framework is not enough to differentiate its existing SOTA methods. \nTheir evaluation shows that HIPO helps with long and repetitive tasks, while being the strongest competitor on the existing KAREL domain. \nI'm already giving an accept, but might further raise based on the other reviews and the rebuttal.", "weaknesses": "The only main weakness I was able to identify is the:\n\n**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. \n\nFurther smaller concerns are: \n\n**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. \n\n**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. \n\n-------------------------------\n[1] Jiang, Zhengyao, and Shan Luo. \"Neural logic reinforcement learning.\" International conference on machine learning. PMLR, 2019.\n\n[2] Xu, Duo, and Faramarz Fekri. \"Interpretable model-based hierarchical reinforcement learning using inductive logic programming.\" arXiv preprint arXiv:2106.11417 (2021).\n\n[3] Luo, Lirui, et al. \"INSIGHT: End-to-End Neuro-Symbolic Visual Reinforcement Learning with Language Explanations.\" arXiv preprint arXiv:2403.12451 (2024).\n\n[4] Di Langosco, Lauro Langosco, et al. \"Goal misgeneralization in deep reinforcement learning.\" International Conference on Machine Learning. PMLR, 2022.\n\n[5] Delfosse, Quentin, et al. \"Interpretable concept bottlenecks to align reinforcement learning agents.\" arXiv preprint arXiv:2401.05821 (2024).\n\n[6] Kohler, Hector, et al. \"Interpretable and Editable Programmatic Tree Policies for Reinforcement Learning.\" arXiv preprint arXiv:2405.14956 (2024).\n\n[7] Delfosse, Quentin, et al. \"HackAtari: Atari Learning Environments for Robust and Continual Reinforcement Learning.\" arXiv preprint arXiv:2406.03997 (2024).\n\n[8] Bastani, Osbert, Yewen Pu, and Armando Solar-Lezama. \"Verifiable reinforcement learning via policy extraction.\" Advances in neural information processing systems 31 (2018).\n\n[9] Delfosse, Quentin, et al. \"Interpretable and explainable logical policies via neurally guided symbolic abstraction.\" Advances in Neural Information Processing Systems 36 (2024).\n\n[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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the thorough and constructive comments. Please find the response to your questions below.\n\n>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.\n\nWe 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.\n\n\n>Interpretability allows to detect invisible suboptimal behaviors\n\nWe 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.\n\n>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.\n\nWe thank the reviewer for the suggestion. We will try to adjust the name of our method to avoid potential confusion.\n\n>It might be insightful to test the generalizability of the different methods (by varying size, of the environment).\n\nIn 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.\n\nWe will add other different generalization settings (e.g., varying size of the environment) to further testify the proposed framework in the  revision.\n\n>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.\n\nAs 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.\n\n>What's the percentage of retrieved program (based on your effectiveness and diversity criterion)?\n\nThe 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8x48BUo8hD", "reviewer": "Reviewer_p5Z4", "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.", "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?\n\n2. 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": "The authors adequately addressed the limitations of their work.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The authors proposed novel reward functions that can enhance the diversity and compatibility of the program skill set obtained by CEM. The experimental results show that HiPO performs better on average compared to existing baselines, and every part of HiPO plays a significant role.", "weaknesses": "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.\n\n2. 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.\n\n3. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the thorough and constructive comments. Please find the response to your questions below.\n\n>The execution time will differ from program to program, but HiPO does not consider this factor while incorporating a discount factor 𝛾 of 0.99.\n\nDuring 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.\n\n>HiPO does not discount the cumulative reward of low-level actions\n\nAfter 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].\n\n>The difference between the two settings, CEM+diversity top k and CEM+diversity x |M|, is unclear.\n\nIn 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. \n\nNote 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.\n\n>The authors did not conduct experiments on the CEM + compatibility setting.\n\nAs suggested by the reviewer, we conduct additional experiments of CEM+compatibility ×|M|.\n\n| Method | Seesaw | UP-N-Down | Farmer | Inf-DoorKey | Inf-Harvester |\n|-|-|-|-|-|-|\n| CEM × \\|M\\| | 0.06 $\\pm$ 0.10 | 0.39 $\\pm$ 0.36 | 0.03 $\\pm$ 0.00 | 0.11 $\\pm$ 0.14  | 0.41$\\pm$ 0.17 |\n| CEM+diversity top k, k=\\|M\\|| 0.15 $\\pm$ 0.21 | 0.25 $\\pm$ 0.35 | 0.03 $\\pm$ 0.00 | 0.13 $\\pm$ 0.16 | 0.42$\\pm$ 0.19 |\n| CEM+diversity × \\|M\\|| **0.28** $\\pm$ 0.23 | **0.58** $\\pm$ 0.31 | 0.03 $\\pm$ 0.00 | 0.36 $\\pm$ 0.26 | 0.47$\\pm$ 0.23 |\n| CEM+compatibility × \\|M\\| | 0.23 $\\pm$ 0.32 | 0.43 $\\pm$ 0.34 | **0.14** $\\pm$ 0.22 | **0.57** $\\pm$ 0.3 | **0.66** $\\pm$ 0.08 |\n\nAcross 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.\n\n>The diversity of the embedding vectors does not necessarily guarantee the diversity in the actual behaviour.\n\nWe 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. \n\n>How different are the programs' actual behaviors in the final skill set?\n\nFigures 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:\n- 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.\n- 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.\n- 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. \n\n>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?\n\nThe 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.\n\n---\n\nReferences:\n\n[1] Ofir Nachum, Shixiang Gu, Honglak Lee, and Sergey Levine. Data-efficient hierarchical reinforcement learning. In NeurIPS, 2018.\n\n[2] Kevin Frans, Jonathan Ho, Xi Chen, Pieter Abbeel, and John Schulman. Meta learning shared hierarchies. In ICLR, 2018.\n\n[3] Youngwoon Lee, Jingyun Yang, and Joseph J. Lim. Learning to coordinate manipulation skills via skill behavior diversification. In ICLR, 2020.\n\n[4] Dweep Trivedi, Jesse Zhang, Shao-Hua Sun, and Joseph J Lim. Learning to synthesize programs as interpretable and generalizable policies. In NeurIPS, 2021.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "byj57TUijf", "reviewer": "Reviewer_4qWN", "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.", "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.\n2) 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": "Yes.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1) Effective approach: This work tackles an intuitively challenging problem and proposes a practically effective solution. Particularly on long-horizon tasks, as shown by the results in Karel-long in Table 2, demonstrates the effectiveness of the proposed method.\n2) Thorough ablation studies: the paper conducts various ablation studies, and show the optimal performance of the proposed approach among other variants.", "weaknesses": "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?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the thorough and constructive comments. Please find the response to your questions below.\n\n>Is there any empirical evidence to show that the designed modules do improve the effectiveness, diversity, and compatibility of programs? \n\nWe thank the reviewer for this insight. We discuss the evaluation of effectiveness, diversity, and compatibility below.\n\n- 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.\n- 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.\n- 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.\n\n| Method | Seesaw | UP-N-Down | Farmer | Inf-DoorKey | Inf-Harvester |\n|-|-|-|-|-|-|\n| CEM × \\|M\\| | 0.06 $\\pm$ 0.10 | 0.39 $\\pm$ 0.36 | 0.03 $\\pm$ 0.00 | 0.11 $\\pm$ 0.14  | 0.41$\\pm$ 0.17 |\n| CEM+compatibility × \\|M\\| | **0.23** $\\pm$ 0.32 | **0.43** $\\pm$ 0.34 | **0.14** $\\pm$ 0.22 | **0.57** $\\pm$ 0.3 | **0.66** $\\pm$ 0.08 |\n\nThe results show that, across every task listed above, CEM+compatibility × |M| outperforms CEM × |M|, demonstrating the effectiveness of employing the proposed compatibility measure. \n\nWe thank the reviewer for inspiring us to conduct this experiment, and we will include the results in the revised paper.\n\n>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.\n\nWe 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.\n- 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.\n- 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.\n- 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. \n\nBy 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.\n\n>Does the choice of DSL affect the performance of the proposed process? Would a less well-designed DSL cause the method to be ineffective?\n\nAs 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: 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.
Decision: Accept (poster)