Addressing Long-Horizon Tasks by Integrating Program Synthesis and State Machines

It seems the method does not perform very ideally in the INF-DOORKEY and INF-HARVESTER, could authors provide additional explanations on this? Including more analysis of the failure modes would also help readers understand the limitations of the work.

We thank the reviewer for raising this question.

Inf-Harvester: We noted that in the Inf-Harvester task, there is a drastic difference between retrieving programs and learning the transition function. Specifically, when retrieving mode programs, it seldom starts executing program candidates from a state with a small number of markers, and therefore, the retrieved programs modes mainly are specialized in collecting “dense” markers; however, when learning the transition function, after executing a few programs, the state contains only a small number of markers, and no program mode is specialized in such a scenario.

Inf-DoorKey: Our proposed POMP achieves the second-best performance in the Inf-DoorKey task, with an average reward of 0.91, outperforming HPRL (0.15) and LEAPS (0.1) by a large margin. DRL achieves the best performance (0.97). The Inf-DoorKey environment consists of four small chambers (i.e., one 3x3, two 2x3, and one 2x2) connected to each other. Therefore, each stage of Inf-Doorkey requires only moderate exploration, allowing DRL to achieve good performance.

Some related works also explore state machines for high-level transition abstraction in RL, e.g., integrating symbolic planning and skill policies [1][2][3], please consider discussing or comparing. Reference:

[1] LEAGUE: Guided Skill Learning and Abstraction for Long-Horizon Manipulation, RA-L 2023;

[2] Leveraging approximate symbolic models for reinforcement learning via skill diversity, ICML 2022;

[3] PEORL: Integrating Symbolic Planning and Hierarchical Reinforcement Learning for Robust Decision-Making, IJCAI 2018.

We thank the reviewer for pointing out these relevant works on symbolic planning, and we have revised the paper to discuss them. The major difference between POMP and Cheng and Xu, 2023 and Lin et al., 2022 is the interpretability of the skill or option. In POMP, each learned skill is represented by a human-readable program. On the other hand, neural networks used by Cheng and Xu, 2023 and tabular approaches used by Lin et al., 2022 are used to learn the skill policies. In Yang et al., 2018, the option set is assumed as input without learning and cannot be directly compared with Cheng and Xu, 2023, Lin et al., 2022 and POMP.

Another difference between the proposed POMP framework and Cheng and Xu, 2023, Lin et al., 2022, and Yang et al., 2018 is whether the high-level transition abstraction is provided as input. In Cheng and Xu, 2023, a library of skill operators is taken as input and serves as the basis for skill learning. In Lin et al., 2022, the set of “landmarks” is taken as input to decompose the task into different combinations of subgoals. In PEORL, the option set is taken as input, and each option has a 1-1 mapping with each transition in the high-level planning. On the other hand, the proposed POMP framework utilized the set of retrieved programs as modes, which is conducted based on the reward from the target task without any guidance from framework input.

References

• Liu et al. “Hierarchical Programmatic Reinforcement Learning via Learning to Compose Programs” ICML 2023
• Inala et al. ”Synthesizing Programmatic Policies that Inductively Generalize” ICLR 2020
• Trivedi et al. “Learning to Synthesize Programs as Interpretable and Generalizable Policies” NeurIPS 2021
• Koul et al. "Learning Finite State Representations of Recurrent Policy Networks" in ICLR 2019
• Kempka et al. "Vizdoom: A doom-based ai research platform for visual reinforcement learning" IEEE Conference on Computational Intelligence and Games 2016
• Sun et al. ‘Program Guided Agent” in ICLR 2020
• Chevalier-Boisvert, et al. “Minigrid & Miniworld: Modular & Customizable Reinforcement Learning Environments for Goal-Oriented Tasks’” arxiv 2023
• Liang et al. “Code as Policies: Language Model Programs for Embodied Control” ICRA 2023
• Wang et al. “Demo2Code: From Summarizing Demonstrations to Synthesizing Code via Extended Chain-of-Thought” arxiv 2023
• Cheng and Xu "LEAGUE: Guided Skill Learning and Abstraction for Long-Horizon Manipulation" RA-L 2023
• Lin et al. "Leveraging Approximate Symbolic Models for Reinforcement Learning via Skill Diversity" ICML 2022
• Yang et al. "PEORL: Integrating Symbolic Planning and Hierarchical Reinforcement Learning for Robust Decision-Making" IJCAI 2018

Conclusion

We are incredibly grateful to the reviewer for the detailed and constructive review. We believe our responses address the concerns raised by the reviewer. Please kindly let us know if there are any further concerns or missing experimental results that potentially prevent you from accepting this submission. We would be more than happy to address them if time allows. Thank you very much for all your detailed feedback and the time you put into helping us to improve our submission.

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

Responses to Questions

The framework utilizes 3 stage design where the learning of the program embeddings and the mode transition function are separated, which could lead to cascading errors.

We thank the reviewer for raising this concern. In the following, we discuss how error propagation may happen from Stage 1 (i.e., learning a program embedding space) to Stage 2 (i.e., retrieving mode programs), and from Stage 2 to Stage 3 (i.e., constructing the policy by learning a transition function with the mode programs).

Stage 1 $\rightarrow$ Stage 2: Stage 1 learns a program embedding space that continuously parameterizes diverse programs. Once the reconstruction loss is optimized, the program decoder can ideally decode all the training programs given corresponding program embeddings. In fact, the experiments show that with a sufficient embedding size, we can achieve 100% reconstruction accuracy on the entire training program set. Moreover, it can generate novel programs by interpolating in the learned program embedding space, as demonstrated in Trivedi et al., 2021. We believe the cascading error issue would not happen between Stage 1 and Stage 2, i.e., the training programs would not be "dropped/lost" in Stage 1.

Stage 2 $\rightarrow$ Stage 3: Stage 2 retrieves a set of programs as modes of a state machine, and Stage 3 learns a transition function based on the retrieved mode programs. Therefore, as pointed out by the reviewer, if none of the programs retrieved from Stage 2 can solve a part of a task, Stage 3 cannot recover from such failure. To maximally avoid this issue of missing programs in Stage 2, this work focuses on designing search methods that can reliably retrieve all the essential programs in Stage 2. Specifically, we propose a CEM-based search method considering a set of programs' effectiveness, diversity, and compatibility. The ablation studies compare various methods for program retrieval and verify the superior performance of our proposed search method.

The absence of strict constraints to guarantee compatibility between generated programs could result in execution incompatibilities. In Sec. 4.2.3, the most compatible program is selected by inserting the newly generated program into a randomly chosen program sequence and ranking the returns of the execution, would this design guarantee compatibility? If not, what’s the failure ratio of the case that the generated program cannot be executed due to the compatibility issue?

We thank the reviewer for raising this question. Each decoded program is guaranteed to be executable because a syntax mask is applied to the decoder during the program decoding process proposed by Trivedi et al., 2021 to ensure syntactic correctness. That said, we can safely (i.e., it does not “fail”) execute any programs in any order.

We would like to clarify that we introduced the compatibility bonus to account for task performance instead of executability. For example, given a set of retrieved programs $p_1$ and $p_2$, the compatibility bonus tends to retrieve the third mode program $p_3$ if executing some orders (e.g., $p_1 \rightarrow p_3 \rightarrow p_2$, $p_2 \rightarrow p_3$) of these three programs yields satisfactory rewards.

The experiments only consider simple tabular tasks, and only a few baselines are compared. Demonstrating the effectiveness of the framework on more complex tasks would strengthen the paper.

Baselines: We believe that our comparisons to the baselines are sufficient. HPRL (Liu et al., 2023) is the current state-of-the-art method published at ICML 2023 (July 2023). We have revised the paper to include comparisons to the Moore machine network framework proposed by Koul et al., 2019, and state machine policies inspired by Inala et al., 2020. We would appreciate it if the reviewer could be specific about which methods we should compare against.

Tasks: We would like to emphasize that the tasks in the Karel domain characterize various properties that resemble hard RL problems, such as long horizons (up to tens of thousands of time steps), sparse rewards, deceptive rewards, etc. Nevertheless, we agree with the reviewer that extending our work to a variety of domains, e.g., ViZDoom (Kempka et al., 2016), 2D Minecraft (Sun et al., 2020), gym-minigrid (Chevalier-Boisvert et al., 2023), robot arm manipulation (Liang et al., 2023, Wang et al., 2023), is a promising research direction.

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

Responses to Questions

An extremely minor point, in Figure 6a marker ticks aren't used but in Figure 6b they are. Consistency on this would be nice and if possible adding the ticks to 6a would be useful.

We thank the reviewer for this suggestion. We have fixed it in the revised paper.

I think that the pipeline is not challenged or considered fully. For example, the compatibility regulariser ensures that programs are compatible to the previous and subsequent programs. This does not seem to ensure compatibility across multiple programs.

We would like to emphasize that our proposed compatibility regulariser ensures compatibility across the entire program sequence. For example, say during the search phase, we have found 3 mode programs, $p_1$, $p_2$, $p_3$, and we are evaluating a candidate for the 4th program, $p_4$. At this iteration, if the program sequence $[p_2, p_1, p_4, p_3]$ was sampled, we will compute the execution reward by executing this entire program sequence, resulting in the compatibility score considering all $p_1$, $p_2$, $p_3$, not just the program executed right before and after $p_4$. We revised the paper to make this clear.

As shown in Table 2, by taking this compatibility that considers entire program sequences described in Section 4.2.3 into consideration, CEM+diversity+compatibility outperforms other baselines that ignore the compatibility issues. This result highlights the effectiveness of the designed compatibility regulariser.

There is almost a markov assumption being implicitly used at the level of the programs. If this is true, it should be stated explicitly as it is an important point. It makes the comparison to Skill Machines less valid and also makes the pipeline resemble an Options framework far more.

We would like to emphasize that we explicitly discuss this in the problem formulation section (Section 3) in the original paper. Specifically, it is stated that “the tasks considered in this work can be formulated as finite-horizon discounted Markov Decision Processes (MDPs).”

We fully agree with the reviewer that our proposed Program Machine Policy shares the same spirit and some ideas with hierarchical reinforcement learning frameworks and semi-markov decision processes (SMDPs) if we view the transition function as a “high-level” policy and the set of mode programs as “low-level” policies or skills.

While most HRL frameworks either pre-define and pre-learned low-level policies, or jointly learn the high-level and low-level policies from scratch, our proposed framework first retrieves a set of effective, diverse, and compatible modes, and then learns the mode transition function.

We have revised the paper and included a discussion on HRL (Section A). We would appreciate it if the reviewer could suggest more related HRL and SMDP papers if our discussion misses anything.

Moreover, skill machine are primarily used to encode long-horizon tasks where transitions between FSM states corresponds to a meaningful (usually semantic) change in the environment. However, since all all programs here are being sampled from a pre-trained embedding space which is not conditioned on the state or context of the environment, it seems all programs are only usable in the same environment, making them more monolithic in their own right.

We thank the reviewer for raising this question. Following Trivedi et al., 2021 and Liu et al., 2023, we learn the pre-trained program embedding space using randomly generated task-agnostic programs. Once a program embedding space of a domain (e.g., the Karel domain) has been learned, it can be used for solving any tasks in this domain. In fact, we used the precisely same program embedding space to produce policies for all the tasks in the Karel, Karel-Hard, and Karel-Long problem sets.

Since we construct such a program embedding space from randomly generating a program dataset, the majority of the generated programs do not capture meaningful behaviors. Therefore, devising efficient search methods that can quickly identify effective programs is critical, which is the main focus of LEAPS and HRPL. The search method proposed in our work, on the other hand, not only aims to obtain effective programs but is also designed to retrieve a set of effective, diverse, and compatible programs. For example, Figure 7 illustrates how the proposed CEM+diversity can avoid searching over paths similar to those previously explored, which drastically increases the searching efficiency.

DEF run m( IF c( frontIsClear c) i( move i) turnRight WHILE c( frontIsClear c) w( pickMarker move w) m)

DEF run m(WHILE c( leftIsClear c) w( turnRight move putMarker pickMarker move w) m)

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

Responses to Questions

The paper specifically cites the work of Inala et al. as being difficult to be interpreted by human users. Similarly to how I can accept that programs in the Karel language can be interpretable, I can also accept that the FSM learned with Inala et al.'s system to also be interpretable. As far as I know, no paper has actually evaluated the interpretability of these systems, so the argument that FSM aren't interpretable is wrong to me.

We thank the reviewer for pointing that out. We agree with the reviewer that symbolic programs used in Inala et al., 2020's systems are more interpretable than neural network policies. However, we still believe that such symbolic mode programs describing the relationship among variables, which are presented in Figure 16 to Figure 21 in Inala et al., 2020 paper, are less interpretable than our programs written in a formal language. Trivedi et al., 2021 demonstrated that users with basic programming skills can interpret, edit, and improve the programs synthesized by LEAPS, which highlights the interpretability of DSL programs.

As suggested by the reviewer, we have revised the paper and toned down our statement. Instead of stating that the FSMs used in Inala et al., 2020 are "difficult to be interpreted by human users," we now argue such FSMs "are less interpretable (compared to DSL programs)."

Even if we accept that the policies the system of Inala et al. generates aren't interpretable and the programs in the Karel language are, I still find it hard to accept that the policies POMP encodes are interpretable. The choices of which mode to execute next are provided by a neural network, which arguably is hard to interpret. While it is easy to accept that the modes are interpretable (although no evidence for it was provided), I would accept that the POMP policies are interpretable only after seeing some strong evidence of the fact.

We agree with the reviewer that employing the neural network transition function makes our proposed program machine policies not entirely interpretably. However, the program machine policies still enjoy "local interpretibility." That said, once the transition function chooses each mode program, human users can read and understand the following execution of the program. To reflect this point raised by the reviewer, we have revised the paper to emphasize that the policies produced by our proposed framework are "locally interpretable." We appreciate the reviewer for helping us clarify this.

To further improve the interpretability of the proposed program machine policies, we have conducted additional experiments to extract Moore machines from learned transition functions using the Moore machine network framework proposed by Koul et al., 2019. By synthesizing the corresponding Moore machine from a learned transition function, we can explicitly display the learned mode transition mechanism as a state machine and thus make the overall framework more interpretable. The extracted results on "Farmer," "Inf-Doorkey," and "Inf-Harvester" are shown in Section E of the revised paper.

Is the process of learning modes accounted for in the curves shown in Figure 6a and in the numbers shown in Table 2? And is the learning of modes performed in the target task? I ask this question because, due to the compatible constrain, learning modes is essentially learning a solution to the problem because it already tries to combine programs such that they can maximize the expected reward. I might have also missed this information, but it isn't clear the number of steps used to train each system.

We thank the reviewer for raising the questions.

• Yes, timesteps of learning modes are accounted for in the curves shown in Figure 6a. The detail about how returns in Figure 6a are calculated is addressed in Section C of the revised paper.
• Yes, the mode program retrieving process introduced in Section 4.2.3 is performed on each target task to ensure that the retrieved mode programs are diverse and compatible for solving the given task.

DEF run m(WHILE c( leftIsClear c) w( turnRight move putMarker pickMarker move w) m)

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

Responses to Questions

Unclear presentation and missing details

We sincerely thank the reviewer for pointing these out. We have thoroughly revised the paper to include the missing details and make the existing information easier to find.

How are the programs over which the embedding space is learned generated? Are they simply randomly sampled from the Karel DSL? These programs form such a crucial building block for the method that it's worth discussing how they're generated here, and how they might be generated in other domains.

As described in Section 4.1, we follow the training procedure proposed by LEAPS (Trivedi et al., 2021), which generates 50000 programs that are randomly sampled according to the Karel DSL to train the encoder-decoder model. Further details about the program dataset generation and the training of the encoder-decoder model can be found in Section F.1 of the revised paper.

To generate programs in another domain, we can simply randomly sample programs according to the DSL in that domain "for free" and then learn a program embedding space.

How are the rewards defined in the CEM optimization in the retrieval stage? It seems like one would need many different reward functions to ensure good diversity and coverage in the selected modes. Is it task-specific? This crucial information does not appear to be clearly explained anywhere.

The reward used by POMP for CEM optimization, as shown in Equation 1 and Figure 3, is defined as:

$R\_{\rho} = \sum\_{i=1}^{|\Psi\_{\text{before}}|} \gamma ^ {i-1} \sum\_{t=0}^{T^i} \gamma^t \mathbb{E}\_{(s\_t,a\_t) \sim \text{EXEC} (\Psi\_{\text{before}}[i])}[r\_{t}] + \gamma^{|\Psi\_{\text{before}}|}\sum\_{t=0}^{T} \gamma^t \mathbb{E}\_{(s\_t,a\_t) \sim \text{EXEC} (\rho\_z)}[r\_{t}] + \gamma^{|\Psi\_{\text{before}}|+1}\sum\_{i=1}^{|\Psi\_{\text{after}}|} \gamma^{i-1} \sum\_{t=0}^{T^i} \gamma^t \mathbb{E}\_{(s\_t,a\_t) \sim \text{EXEC} (\Psi\_{\text{after}}[i])}[r\_{t}].$

Note that this reward function is not task-specific, and we use this reward to retrieve the set of mode programs for POMP across all tasks discussed in Section 5.1.

How is the transition function f learned? Is this learned via standard RL, where choosing the modes is the action?

As stated in Section 4.3 and Section F, the learning process of transition function $f$ is formulated as a standard RL problem. A state includes the current Karel grid and the previously executed mode represented by a one-hot vector, while an action chooses the next mode program, as correctly understood by the reviewer. We use the PPO algorithm to optimize the transition function $f$.

How do state machine policies differ from other notions of hierarchical reinforcement learning? It seems like the modes can simply be interpreted as "skills" or formally options in a SMDP framework.

We fully agree with the reviewer that our proposed Program Machine Policy shares the same spirit and some ideas with HRL frameworks and SMDP if we view the transition function as a “high-level” policy and the set of mode programs as “low-level” policies or skills.

While most HRL frameworks either pre-define and pre-learned low-level policies, or jointly learn the high-level and low-level policies from scratch, our proposed framework first retrieves a set of effective, diverse, and compatible modes, and then learns the mode transition function.

We have revised the paper and included a discussion on HRL (Section A). We would appreciate it if the reviewer could suggest more related HRL and SMDP papers if our discussion misses anything.

Details about the state are missing from the main body of the work, which makes it difficult to understand the task. From what I gather from the Appendix, a N x M array is used as the state for a N x M grid world for the deep RL baseline -- is this the same state that the proposed approach uses for selecting which mode to switch to?

We thank the reviewer for bringing up this issue. Yes, as described in Section 4.3 and Section F of the revised paper, both the DRL baseline and the mode transition function of POMP use a CNN to encode an input state of an N x M array, describing the current Karel grid, as shown in Figure 5 and Section H of the revised paper.