Integrating Planning and Deep Reinforcement Learning via Automatic Induction of Task Substructures
Authors: Jung-Chun Liu
Chi-Hsien Chang
Shao-Hua Sun
Tian-Li Yu
Venue: ICLR 2024 poster (2024)
Keywords: Deep Reinforcement Learning
Classical Planning
Genetic Programming
Symbolic AI
Learning from Demonstration
Primary area: reinforcement learning
TL;DR: The work integrates planning and deep reinforcement learning to discover critical action schemata and build hierarchical networks. The framework induces symbolic knowledge of task substructures via genetic programming.

Abstract: Despite recent advancements, deep reinforcement learning (DRL) still struggles at learning sparse-reward goal-directed tasks. Classical planning excels at addressing hierarchical tasks by employing symbolic knowledge, yet most of the methods rely on assumptions about pre-defined subtasks. To bridge the best of both worlds, we propose a framework that integrates DRL with classical planning by automatically inducing task structures and substructures from a few demonstrations. Specifically, genetic programming is used for substructure induction where the program model reflects prior domain knowledge of effect rules. We compare the proposed framework to state-of-the-art DRL algorithms, imitation learning methods, and an exploration approach in various domains. Experimental results show that our proposed framework outperforms all the abovementioned algorithms in terms of sample efficiency and task performance. Moreover, our framework achieves strong generalization performance by effectively inducing new rules and composing task structures. Ablation studies justify the design of our induction module and the proposed genetic programming procedure.

Published as a conference paper at ICLR 2024
INTEGRATING PLANNING AND DEEP REINFORCE- MENT LEARNING VIA AUTOMATIC INDUCTION OF TASK SUBSTRUCTURES
Jung-Chun Liu, Chi-Hsien Chang, Shao-Hua Sun, Tian-Li Yu Department of Electrical Engineering
National Taiwan University
[x10921043, (0 407921004, shaohuas, saabbaas,ttanllyygeauu......
ABSTRACT
Despite recent advancements, deep reinforcement learning (DRL) still struggles at learning sparse-reward goal-directed tasks. Classical planning excels at ad- dressing hierarchical tasks by employing symbolic knowledge, yet most of the methods rely on assumptions about pre-defined subtasks. To bridge the best of both worlds, we propose a framework that integrates DRL with classical planning by automatically inducing task structures and substructures from few demon- strations. Specifically, genetic programming is used for substructure induction where the program model reflects prior domain knowledge of effect rules. We compare the proposed framework to state-of-the-ar DRL algorithms, imitation learning methods, and exploration approach in various domains. Experimen- tal results show that our proposed framework outperforms all the abovementioned algorithms in terms of sample efficiency and task performance. Moreover, framework achieves strong generalization performance by effectively inducing new rules and composing task structures. Ablation studies justify the design of our induction module and the proposed genetic programming procedure.
INTRODUCTION
Deep reinforcement learning (DRL) as an inductive learning method allows agents to deal with high-dimensional decision-maaing problems considered intractable in the past (Arulkumaran et al.) 2017). DRL has applied to various fields, including robotics (Nguyen el al.) 2020), autonomous driving (Kiran et al. 2022), and video games (Mnih al. (013). However, exploring complex tasks with sparse and delayed rewards still remains challenging, leading to inapplicability many real-world problems comprising multiple subtasks, e.g., cooking and furniture assembly.
In contrast, classical planning is a deductive learning method which aims to solve planning and scheduling problems. Particularly, classical planning is adept at finding the sequence of actions in deterministic and known environments. Researchers in classical planning have developed effective planners that handle large-scale problems (Vallati al.) 2015). Yet, classical planning agents face difficulties exploring environments due to limitations in model and domain-specific representa- tion in unknown environments where action models are undiscovered.
Several methods work on combining planning and DRL address hierarchical tasks with high-level abstraction. Konidaris et al. (2018) develop a skill-up approach to build a planning representation from skill abstraction. while they do not encompass skill acquisition from low-level execution. Mao et al, 2022) introduce an extension of planning domain definition language (Ghallab et al. 1998] to model the skill, and [Silver et al. (2022) propose method for learning parameterized poli- cies integrated with symbolic operators and neural samplers. However, they consider object-centric representations, which require fully observable environments and carefully designed predicates.
In this paper, we combine classical planning and DRL to augment agents effectively to adapt to environments by inducing underlying prior knowledge from expert demonstrations, Specifically, we devise a method that induces symbolic knowledge using genetic programming (Koza) 1994). an evolutionary computation approach, to discover task substructures that accurately capture the under- lying patterns within the data. The compositional property of the programs enables generalizability that adapts new environments by discovering new substructures from known ones.

---

Published as a conference paper at ICLR 2024
To evaluate the proposed framework, we design three gridworld environments where agents can move on and interact with objects. The result shows the improvement of DRL agents and outperfor- mance compared to other imitation learning and exploration- methods. Also, our framework demonstrates generalizability by inducing variant substructures and recomposing task structures. Finally, we show the ablation studies about the accuracy of induction.
RELATED WORK
Learning abstraction from demonstrations. State abstraction facilitates the agent's reason- ing capabilities in high-level planning by extracting symbolic representations from low-level states (Abel et al. 2018 Guan et al.) (022). Agents can learn the abstraction from demonstrations since demonstrations encompass valuable information regarding task composition and relevant fea- tures (Byrne & Russon 1998). Some methods were developed extract task decomposition and abstraction from demonstrations (Hayes & Scassellati] 22016] Cobo el al. 2011). Our work extends these approaches infer knowledge from demonstrations.
Learning planning action models. Some works have focused on integrating learning and plan- ning to enhance capabilities in complex environments (Danesh el al., [023] Velooo et al. 1995). To leverage the strategies of classical planning, many works have developed building planning action models, including skill acquisition and action schema learning (Arora et al. 2018; Stern & Juba
2017
Pasula al.) 2007 Callanan al. 2022; Silver et al. 2022 Mao et al. [222]] Yang et al.
2007
However, these works mainly focus on the existing planning benchmark and less focus on
general Markov decision process (MDP) problems. On the other hand, to address the issue of sample efficiency in DRL,, several techniques explored the integration of symbolic knowledge with DRL by learning planning action models (Jin et al. 2022 Lyu al. 2019). In this work, we aim to bridge this gap by extending these approaches to incorporate inferred knowledge into DRL, enhancing its applicability complex decision- makiing scenarios.
Hierarchical task learning. A proper hierarchical structure is crucial for task decomposition and abstraction. Various methods have been proposed for constructing hierarchical task representation
PPateria al. (2022), including graphs (Svetlik et al. (017), automata (Furelos-Blande Blanco et al.
1021
Icarte et al. [2019] 2022; Xu et al. 2021). programs (Sun et al.) 2018, 2020; Trivedi et al. 2021
Liu er al. [223]]Li
al. [2023), , and hierarchical task networks (Hayes & Scassellati 2016 Sohn
el al. (220) Lee el al. (019). Some approaches utilize the capabilities of deep learning with intrinsic
rewards (Kulkarni el al. 2016 Florensa el al. 2017). In addition, some of these works specifically
address leveraging knowledge to deal with multiple compositional tasks via task decomposition (Andreas et al. 2017 Sohn al. 2022 Liu al. [022] Sun et al. [2020] [Sonn et al. 2018 Furelos- Blanco et al. (222)) Despite the success in building hierarchical models shown in previous works, these works put less emphasis on inducing subtask rules and substructure. Therefore, we develop a method to induce symbolic knowledge and leverage it for hierarchical task representation.
3 PROBLEM FORMULATION
We address the sparse-reward goal-directed problems which can be formulated as MDPs denoted as (S, A, T, R, 7), where S denotes state space, A denotes action space, T S A + S denotes transition function, R : S x A + R denotes reward function, and E (0. 1] denotes a discount- ing factor. DRL agents often struggle at solving sparse-reward, hierarchical tasks, while classical planning techniques excel in such scenarios. On the other hand, unlike classical planning, DRL, as a generic model-free framework, does not require pre-defined models. This motivates us to bridge the best of both worlds by integrating these two paradigms.
However, while DRL directly learns from interacting with MDPs, classical planning operates on literal conjunctions. To address this gap, we integrate planning and DRL methods by annotating the specific MDP actions in the form of action schemata. Specifically, we consider the problem of inducing the action schemata from demonstrations. The objective is to induce the action schemata which can be leveraged for task structure deduction. After the action schemata are discovered, the framework deduces task structures from the action model and aims to offer guidance for the training of DRL. agents based on the task structures.
2

---

Published as a conference paper at ICLR 2024
Name
Symbol
Example
workDench
Critical action
t Be (ieef
make stick
MDP action
nake jake_atick nakel
Effect variables
(wood, stick)
Effect
e0' (1)) V(pre(e)) pre(v)
(ooo - 2, stick +
Precondition variables
(at workbench, wood]
Precondition
(at at..worbbench 1, wood 2
(a) Critical action
(b) Symbols examples of an action schema make_stee .skic..
sbick
x right råght down pickup pickup
down
pickupppppp. Nood
woode [Lx3]
Wood
Bl_woEXbanch
MDP actions
MDP
paice stick
actions
Inventory
Inventory
Inventory
wood
BLiCK
empty
wood
x
stick
stick
(c) Critical action network
(d) Example of making a stick in MINECRAFT
Figure 1:
Critical action. (a)-(b) The illustration, symbols, and examples of critical action. A critical action is an essential action in environments with preconditions and effects. (c) Critical action network. If an action model is discovered by the induction module, it builds critical action networks. (d) Example of making stick in MINECRAFT. Actions highlighted by red rectangles are critical, i.e., picking up wood twice and making a stick (makel).
4 INTEGRATION OF MDP IN DRL AND PLANNING WITH CRITICAL ACTION
To bridge the gap between DRL and planning, introduce the concept of critical actions in this section. Specifically, we formulate our problems as mapping tasks described by MDPs to planning domain definition language (PDDL) (Ghallab al. 1998 Silver Chitnis 2020) and
SAS* (Bäckström & Nebel 1995), where the preliminary notation is elaborated in Appendix A To express numeric variables, we adopt the configuration of PDDL 2.1 includes arithmetic operators for specification.
(Fox & Long 2003 which
Mapping between MDP and classical planning. Lee et al. (022) has developed the abstraction mapping between planning and MDP problems. A planning task II = (V, O, s.))) where a set of variables, is set of operators in the domain, and / is partial state describing the goal. The transition graph of the planning task is a tuple T' = (S', S where T is set of transitions goo! is set goal states. Let C + be a mapping from the MDP state space to high-level planning state space S'. Given an MDP problem, the abstraction (C, I1) is proper iff there exists a mapping L 11 such that (C(s), v. L(T(s, ag))) E T if some d is admissible in the MDP state S or ((s) = C(T(s, az)), where T' is a set of all possible transitions in II. this work, we focus on the MDP problems with proper abstraction in which mapping to planning domain exists, and action models can be induced by the proposed framework.
(s', o, (s))) for all s' in S', and S
Critical action. Critical actions are the actions that lead to the transitions in T'. That is, these actions critical for progress the planning level and must be executed in specific order. A state E S' in the planning domain is an assignment to V, and s E is the value assigned to the variable planning task as an MDP-like tuple (S', O, I",, transition (s, ag T(s, ax)) in an MDP problem can be directly transferred the transition (L(s), b. L(T(s, ag))) in planning domain.
V. We map each 8, in MDP problems with distinct 8y in planning, considering
MDP action Og E A denotes the MDP action mapping to t/.
Precondition pre( set conditions requires satisfaction before executing vh.
Effect eff (1) is of functions which indicates the state change after executing v/.
state E S', where S' denotes planning state space, is an assignment to V, where V(p) denotes the variables of the assignment p. Given an effect eff (1/) and one of its variables ((el(()))
3

---

Published as a conference paper at ICLR 2024
Environment
Collecting
Demonstrations
Agent
State
Demonstrations
Action
Reward
Extracting
Action-Erfact Linkage
Demonstrations
DRL Module
Action-Effect
V(+0(-))
Intrinsic
Determining Effect Symbolic Rules
Goal
Reward
Effect Rules
Induction Module
Knowledge Base
Training Module
eff-) (a. ((
Determining
Precondition Rules
Critical Action Graph
Precondition Rules
Training Data
pre(-) V(a, eff(-))
Critical Action Schemata (a, pre()),pe(()
(a) Framework overview
(b) Induction module
(a) Framework overview. The proposed framework is two-stage. In the induction stage, critical action schemata induced from demonstrations. In the training stage, the training module deduces the critical action network from the goal by backward-chaining and offers intrinsic rewards to the DRL module according to the network. (b) Induction module. The induction module induces the critical action schemata from demonstrations through three steps. First, it finds the linkage between actions and effect variables transitions. Then, given the transitions with action-effect linkage, the induction module induces the effect rules via symbolic regression. Finally, it determines the precondition given the specific action and the effect.
Figure 2:
R is function which transfers the specific feature value s', in s' to another value eff (s) the transition, and a precondition rule pre( is a logical formula pre()). R - f0, }} that determines whether the variable is satisfied to execute th. Given a state s', two critical action & and á (1), satisfy pre()), in state s' iff a variable v in both ((eff( (x)) and (prr( and pre())u[s(. false while (re()))(ef(()) That is, executing vi makes & become admissible.
an effect rule eff (v))
true in transition with th
To efficiently induce the model, we assume that the properties of the features in state are known. (u v E Veeff (v)) & O} contains the variables that will change in
Effect variable space transitions and related to the progress of the tasks.
Critical action network. This work represents symbolic knowledge structures as critical action networks illustrated in Figure Ic Given set of critical actions O and desired goal specification Poont, a critical action network & = (V, E)) is an in-tree structure where the root the critical action that can satisfy the goal specification directly. For each edge (1b, Φ) E E, there exists eff (v), for some u that satisfy pre( Once the action schemata are known, we can construct the network using planners backward chaining.
5 METHOD
We introduce the induction module that determines the critical actions from demonstrations and extracts symbolic rules in Sec Then, Section Secttoo|552]dessrrieee the training module that deduces task structures to build critical action networks online from the given goal. The network contains subtask dependencies, providing guidance through intrinsic rewards and augmenting the training efficiency of DRL agents. An overview of our proposed framework is illustrated in Figure 2a
5.1 INDUCTION MODULE
The procedure of the induction module is illustrated in Figure 2b The module first extracts action- effect linkages (a, V(eff (v))) from demonstrations. Second, the module induces effect rules eff (e) given (a, Veel (1))). Finally, the module leverages the rules determine the precondition rules
4

---

Published as a conference paper at ICLR 2024
Start
makel -- (wood, stick)
Population Intialization
action
effect variable
state
next state
wood wood 0, wood 4, ...
make1
wood
wood 2, ...
Evaluation
wood 3, ...
wood 1,
Terminate?
True
Salaction
Reproduction
Crossover
Mutation
Duplication
wood wood,-2 -2 WoodL "wood,
wood #wood_*1
fitness
fitness 0.33
fitness
End
(a) Procedure of genetic programming
(b) Example of fitness evaluation
Figure 3: Symbolic regression using genetic programming. Given a pair of an MDP action and effect variables, symbolic regression is used to determine the rules when executing the action. (a) Procedure of genetic programming. The programs iteratively evolve through fitmess evaluation, selection, and reproduction. (b) Example of fitness evaluation. The algorithm evaluates the accu- racy of programs to induce the rule between makel and wood.
pr)( for each (a, (+))). After these steps, the components of critical action schemata are all determined. Note that we name the critical action t for the convenience of reference, which is not known when inducing action schemata. We use "," to represent an undefined critical action. The following paragraphs will elaborate on the details of the induction methods.
Action-effect linkages. Based on the outcome assumption that one action only impacts specific state features, we can detect co-oceurrence of what effects often occur after executing by calcu- lating mutual information (Shannon, 1948) between actions and effect variables. Let & be set of possible effect variable combinations V(ef(())) in the transitions of demonstrations. The mutual information ((.)Veef()) is defined follows:
(as (()) log Pas(a V(eff()) (+)) aEA V(efT(-))EE
Mave<M-) = Σ Σ
(1)
(V(e)))((((e((()))
where (a(a) is the count of transitions with action Pa(V(eff (-))) is the count of transitions that include variables in V(eff())): PAe(a, V-))(()))) the count of transitions that include changed variables in (-))((-)) with action a. To determine the linkage, the pairs are divided into two clusters with the threshold of a maximum gap, and the cluster with higher values are selected. The detailed algorithm is shown in Appendix B.1
Effect symbolic rules. Given action-effect pair (a, (-)), the induction module proceeds to search for the effect e.f( which can be formulated as a symbolic regression. To accomplish this, we employ genetic programming for symbolic regression to discover each effect rule e-]((), for all v in ((eff(() (-)), aiming to discover programs that can accurately predict the effects.
In genetic programming, each program is represented as an expression tree, taking and ay in each transition as input and yielding the predicted value of v after the transition as output. The algorithm consists of three key steps: initialization, evaluation, selection, and reproduction. Initially, a population of programs is randomly generated. The fitness of each program evaluated based on its prediction accuracy, and the programs with the highest fitness values are selected, serving as parents to reproduce offspring through crossover, mutation, and duplication mechanisms. The procedures and the example of genetic programming are illustrated in Figure
The model of symbolic rules is regarded the substructures of the subtasks, and selecting the proper operators for the symbolic model compatible with the effects plays a crucial role facilitating effec- tive inference. For instance, in the context of general DRL task with numerical variable representa- tion configuration, arithmetic operation set F {+, -, X, + inc, dec} is used as the function set in genetic programming, where inc denotes increment operator and dec denotes decrement oper-
5

---

Published as a conference paper at ICLR 2024
ator. This choice of function set is consistent with the numerical variable representation commonly employed in DRL tasks. The underlying assumption guiding our approach is that the effects can be expressed through these programs, serving prior knowledge of the problem. This allows method to induce task substructures and generalize the knowledge across domains that share iden- tical operation configurations. This distinguishing feature sets approach apart from alternative model-free methodologies. Additional implementation details can be found in Appendix B.2
Precondition rules. After the relation between and e-f found, determining precondition rules (-) can be formulated as a classification problem, as the objective is to identify whether e+)(+) occurs given the action and the state. The process involves minimal consistent determina- tion (MCD) and the decision tree method. The model of pre(.) decides what preconditions leading desired effects after executing a. Additional details can be found in Appendix B.3
5.2 TRAINING MODULE
After the induction process, the critical action schemata serve as the components of knowledge base that guides the agent in the training stage. During the training stage, the training module deduces critical action network given the initial state and goal specification and provides intrinsic reward if the agent successfully performs action that meets the critical effects in the network.
Inferring critical action network. Once the critical actions schemata are defined, we can infer task structures from the model. Given goal and an initial state, the proposed framework deduces the critical action networks by backward chaining. Starting from the goal, the module searches for the critical action to find the desired effect for unconnected precondition rules pre(-), where E. Maximum operation steps are set to terminate the search. Once the critical action found, the critical action will be considered the predecessor of previous critical actions.
DRL agent. In the training stage, we aim to train a DRL agent that can learn the subtask by leveraging the feature-extracting power of neural networks. The induction module only specifies the coarse-grained critical action to express temporal order. Therefore, the framework deploys DRL to complete the fine-grained decision-making tasks, which utilizes deep learning to approximate the optimal policy with neuron networks. DRL uses the policy gradient method to update the policy. In the proposed method, we use the action-critic method (Mnih er al. 2016 Raflin er al. (021) as the DRL agent. The implementation details are described in Appendix B.4
Intrinsic rewards. During the training stage. if the agent successfully executes the critical effects, it will receive an intrinsic reward when the preconditions of critical action & are satisfied. Con- versely, if the agent takes an action that leads to undesired effects, such as violating effect rules, will receive a penalty. However, note that our model only specifies positive critical actions and does not explicitly identify actions that have possible negative consequences. Therefore, the implemen- tation of a penalty depends on the specific domain.
6 EXPERIMENTS
We evaluate our framework and provide ablation studies in this section. Section 6.1 lists the algo- rithms we use for comparison. Section 6.2 provides the description of the environments and tasks. Section (.3) presents the results of training efficiency and performance. Section c.ciionno.4eeeee demonstrtss the generalizability in different levels.
6.1 BASELINES
We extensively compare our framework to various DRL algorithms (DQN and PPO) learning from rewards, imitation learning methods (BC and GAIL) learning from demonstrations, advanced ap- proaches (DQN-RBS and BC-PPO) that leverage both rewards and demonstrations, and explo- ration method (RIDE) that maximizes intrinsic and extrinsic rewards.
DQN (Mnih et al. 2015) is off-policy deep Q-learing algorithm.
PPO (Schulman al. 2017 state-of-the-art on-policy DRL algorithm.

---

Published as a conference paper at ICLR 2024
Behavior cloning (BC; Ross et al. 2011) imitates an expert by learning from demonstra-
tions in a supervised manner.
Generative adversarial imitation learning (GAIL; Ho & Ermon 2016) mimics expert
behaviors via learning a generative adversarial network whose generator is policy.
DQN-RBS initializes the replay buffer of DQN with demonstrations, allowing for a perfor- mance boost. This is inspired by the replay buffer spiking technique (Lipton et al.) 2016))
BC-PPO pre-trains a BC policy using demonstrations and then fine-tunes the policy with PPO using rewards, similar to Video Pre'rraining (VPT: Baker et al. 2022)
Rewarding impact-driven exploration (RIDE; Raileanu Rocktäschel, 2020 an RI.
exploration method inspired by the intrinsic curiosity module (Pathak et al. 2017).
6.2 ENVIRONMENTS & TASKS
To evaluate the proposed framework and the baselines, we design three groups tasks in a 8 x gridworld environment, where agent move along four directions {up, down, 1eft, right) and interact with objects. The tasks are described as follows. See Appendix C for more details.
SwItcH requires an agent to turn on the switches in sequential order. it toggles the wrong switch, the progress will regress, which makes it challenging for DRL agents solve the task through solely exploration. We design four tasks 4-SWITCH, 8-SWITCH, D-DISRRACTORS and 4-RooMS, where 4-SWITCH and 8-S G-TCH evaluate the performance between different difficulties of tasks. 4- DISTRACTORS consist of four target switches and four distractor switches, and 4- 4-ROOMS combines the configuration Minigrid four-rooms tasks Shevalier-Boiseert et al. 2023).
DOORKEY features hierarchical task similar the Minigrid door-key tasks, where the agent needs to open door with a key and turn on a switch behind the door.
MINECRAFT is inspired by the computer game Minecraft and is similar to the environment in previous works (Sohn al. 2018 (nnreas al.) 20177] [Sun al.) [2200] Brooks et al.) 2021). The environment is designed for evaluation using muluille-tak demonstrations. We select simple task IRON, a difficult task ENHANCETABLE, and a multiple-gor task MULTIPLE.
For the methods that require demonstrations, we collect 20 demonstrations from corresponding tasks in SWITCH and DOORKEY and collect 64 multiple-tas statiple-tskkk demonstrations from MULTIPLE for all tasks MINECRAFT.
6.3 RESULTS
The experimental results in Figure show that our framework outperforms all the baselines on chal- lenging tasks (e.g., 8-SWITCH, AICTTRRS ENHANCETABLE, MULTIPLE) and performs competitively simpler tasks (e.g., DOORKEY, 4-SWITCHES, IRON). The imitation learning ap- proaches, BC and GAIL, fail to learn all the tasks due to insufficient demonstrations and lack of exploration, while RIDE, BC-PPO, and DQN-RBS, which consider rewards online, fail on advanced tasks that require long-term planning. In contrast, our framework can leverage the knowledge from the same number of demonstrations and efficiently explore the environment, especially on the tasks 8-SwITCHIE where all the baselines completely fail, as shown in Figure 4b] Moreover, our pro- posed framework is the most sample-efficient method in learning the DOORKEY task.
6.4 GENERALIZABILITTY
Our framework employs the critical action model to achieve task-level generalizability. enabling the construction of novel task structures based on familiar critical actions. Additionally, we introduce genetic programming, renowned for its adaptability in reasoning symbolic rules as task substruc- tures, thereby enhancing generalizability at the rule level. To define the domain gap, we denote the original domain as the domain where demonstrations are collected and the variant domain as the domain where agents learn. For rule-level generalizability, we define a variant critical action é from v where V(eff (Ø)) V(eff (+)) and V(pre()) ((pre()) while (Ø) + eff (++) or pre( + pre( a critical action & varies, the induced symbolic programs and the popu- lation can evolve and adapt new substructures. Since (prre())) and V(eff (Ø)) are known, the procedure starts from inducing effect rules eff (Ø) + eff( Thus, the proposed framework can potentially achieve task generalization.
7

---

Published as a conference paper at ICLR 2024
DON P9O
BC
GAIL
DON-RBS
BC-PPO
RIDE
Ours
1.0
0.2
02
00
SkpstMi
Suparhii
Suputhi
(a) 4-SWITCHES
(b) 8-SWITCHES
(c) 4- 4-DISTRACTORS
(d) 4-ROOMS
1.0
0.2
Supelii
(e) DOORKEY
(1) IRON
(g) ENHANCETABLE
(h) MULTIPLE
Figure 4: Task performance. We report the mean (line) and the standard deviation (shaded regions)
of the training curves over 5M steps out of three runs. Our approach outperforms other methods, especially in advanced tasks.
Setup. To evaluate the generalizability of our framework and baselines, consider 4- S-SWITCHES- (N+1) as the original domain and its variant domains, 8-SWITCHES-(N++) 1), 4-DISTRACTONE In 8-SWITCHES-(N+1 we extend the number of switches from 4 to 8 to evaluate the generalization of task structures. In 4-DISTRACTORS--N++ switches are added 4-SWITCHES-(N+11 and in 4-DISTRACTORS- changes to 2n + (e.g., + 3 5 + 7), while the order of switches in N- D-DISTRACTORS-(N) + 4). This series of settings evaluates if a method can generalize to different effect rules. We collect 200 demonstrations in 4-SWITCHES-(N+: steps for all methods. for all methods, and our framework leverages the previous populations of genetic programming to re-induce the rules, which only require few-shot demonstrations.
(N+1), and 4-DISTRACTORS--(2M
4 distractor the order of switches
+ 1 (e.g.
and and run 5M we collect only 4 additional demonstrations
AIIITRACTORS-(2N::
Baselines. We compare our framework with the best-performing basclines (BC- PPO) and the most widely used baseline (GAIL) for the generalization experiments.
Table 1 Generalization performance in the original domain 4-SWITCHES and variant domains.
Task
GAIL.
BC-PPO
Ours
Results. The results in Table demonstrate that the performance of GAIL and BC-PPO drops in the variant domains, whereas our framework able to generalize, highlight- ing its ability construct novel rules and structures in the variant domains.
4-SWITCHES-(N-1)
30%-s8%
97%+0%
96%s %
3-SWITCHRS-(N+11 +-DISTRACTORS-(NHII] 10%=27%
10%:
00%:40%
90%:42%
41%:24
95%+2%
(-DISTRACTORS-(NNI))
11%:66
335:+2%
95%x11
6.5 ABLATION STUDY
Effect
This section presents the ablation studies of induction modules. Section 66.51] quali- tatively examines the mutual information and Section 66.52 shows the accuracy of symbolic regression using genetic programming.
+ Bb
Mutual Information (log)
3
I
(g)
(+)
len
right
up
down
Action make?
mate!
make?
6.5.1 ACTION-EFFECT LINKAGE
2
maked
we introduce action-effect link- ages to discover the co-occurred effect vari- ables and actions. Figure presents presents the exper- imental results in MINECRAFT and shows the relationship between the logarithm of mutual information and action-effect linkages. The heat map visualizes the values of all action-effect pairs, with darker colors indicating higher val-
In Section 5.1
Pickum
Figure 5: Action-effect mutual information in MINECRAFT inferred by our framework.
8

---

Published as a conference paper at ICLR 2024
and stronger associations, highlighting the linkages. For instance, { O wood, / stick) is the effect variables of make-stick as mentioned in Figure la and lb discovered by our framework from exccuting make1.
6.5.2 SYMBOLIC REGRESSION
The proposed framework necessitates robust symbolic regression module generate the symbolic rules. In Section[5.1 we introduce ge- netic programming symbolic regression for induction. Since genetic programming is ran- domized search method, empirical results are shown to discuss the success rate of finding cor- rect rules and how much demonstrations are re- quired to capture the symbolic rules.
100
Accuracy (%)
Polulation
500
1000
2000
30
100
175
Demonstrations
The experiment setting is described as follows. In MINECRAFT environment, there are 27 ef- fect rules listed in T We sample different numbers of demonstrations from random subtasks, and the number of population are 500, 1000, and 2000. Other parameters genetic programming the same as the setting in Table 2 We calculate the number of programs which is equivalent to the ground truth after simplification. The result is the average accuracy out of five runs shown in Figure 6 We claim that the effect rules can be induced via genetic programming when sufficient number of demonstrations and programs in the population are available. Noting that the results related to the diversity of the data. In theoretically, each n-polynomial rule requires more than ++ points for regression. In addition, critical action networks can still be built when some rules inequivalent the ground truth due the bias of the data, long the rules match with the precondition of succeeding critical actions.
Figure 6: Symbolic regression accuracy.
7 DISCUSSION
We present a framework to address sparse-reward, goal-directed MDP tasks by integrating DRL and classical planning techniques. Our proposed framework represents symbolic knowledge as critical actions and employs procedure to automatically extract knowledge from demonstrations. This combination of inductive learning (i.e., DRL) and deductive learning (i.e., classical planning) en- ables framework to perform explicit high-level planning and accurate low-level execution, al- lowing for robust task performance and generalizing to unseen domains. Additionally, evolutionary computation provides adaptability at the rule level by inducing the task substructures.
Specifically, by representing knowledge critical actions and employing critical action networks, we provide a structured and organized mechanism for capturing and utilizing symbolic knowledge within DRL. The proposed procedures of subtask decomposition combine planning and DRL, lead- ing to effective and efficient learning in goal-directed tasks. Furthermore, the compositionality of the critical action model allows for different levels of generalization, highlighting its potential address a wide range of general problems. In sum, our work offers a holistic perspective to effec- tively handle general goal-directed decision- decision-making problems with the integration of inductive and deductive learning.
This work extensively evaluates our proposed framework on deterministic, fully observable environ- ments within the integer domain. To extend our proposed framework to complex domains, such as continuous input, we can potentially leverage recent studies that have developed genetic program- ming for different variable types (Virgolin et al. 2017 2021). When facing stochastic or partially observable environments, the induction module the uncertainty. a worst-case scenario, when the induction module produces no rule, the proposed framework simply reduces to the backbone DRL algorithm (i.e., PPO) without any intrinsic reward. One potential direction to address this issue is to extend the induction module to recognize and infer probabilistic rules (Pasula et al. 2007
fail to induce some critical actions because of
Arora al. 2018), which is left for future work.

---

Published as a conference paper at ICLR 2024
8 ACKNOWLEDGEMENT
The authors would like thank the support of the National Science and Technology Council in Taiwan under grant No. NSTC 111-2221-E-002-188 and National Taiwan University under grant No. 1121891 103. Shao-Hua Sun was partially supported by the Yushan Fellow Program by the Ministry of Education, Taiwan.
10

---

Published as a conference paper at ICLR 2024
REFERENCES
David Abel, Dilip Arumugam, Lucas Lehnert, and Michael Littman. State abstractions for lifelong reinforcement learning. International Conference on Machine Learning, 2018.
Jacob Andreas, Dan Klein, and Sergey Levine. Modular multitask reinforcement learning with policy sketches. International Conference on Machine Learning. 2017.
Ankuj Arora, Humbert Fiorino, Damien Pellier, Mare Métivier, and Sylvie Pesty. review of learning planning action models. The Knowledge Engineering Review, 2018.
Kai Arulkumaran, Mare Peter Deisenroth, Miles Brundage, and Anil Anthony Bharath. Deep rein- forcement learning: A brief survey. IEEE Signal Processing Magazine, 2017.
Bowen Baker, Ilge Akkaya, Peter Zhokov, Joost Huizinga, Jie Tang, Adrien Ecoffet, Brandon Houghton, Raul Sampedro, and Jeff Clune. Video pretraining (VPT): Learning to act by watching unlabeled online videos. Neural Information Processing Systems, 2022.
Ethan Brooks, Janarthanan Rajendran, Richard Lewis, and Satinder Singh. Reinforcement learning of implicit and explicit control flow in instructions. In International Conference on Machine Learning. 2021.
Richard Byrne and Anne Russon. Learning by imitation: hierarchical approach. Behavioral and Brain Sciences, 1998.
Christer Bäckström and Bernhard Nebel. Complexity results for SAS* planning. Computational Intelligence, 1995.
Ethan Callanan, Rebecca De Venezia, Victoria Armstrong, Alison Paredes, Tathagata Chakraborti, and Christian Muise. MACQ: A holistic view of model acquisition techniques. In The ICAPS Workshop on Knowledge Engineering for Planning and Scheduling. 2022.
Maxime Chevelier-Boisvertt, 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. CoRR, hBss2306613831, 2023.
Luis Cobo, Peng Zang, Charles Isbell, and Andrea Thomaz. Automatic state abstraction from demonstration. In International Joint Conference Artificial Intelligence, 2011.
Mohamad Hosein Danesh, Panpan Cai, and David Hsu. Leader: Learning attention over driving behaviors for planning under uncertainty. In Conference Robot Learning, 2023.
Carlos Florensa, Yan Duan, and Pieter Abbeel. Stochastic neural networks for hierarchical rein- forcement learning. In International Conference Learning Representations, 2017.
Maria Fox and Derek Long. PDDL2.1: An extension PDDL for expressing temporal planning domains. Journal of Artificial Intelligence Research, 2003.
Daniel Furelos- Hurelos-Blanco, Mark Law, Anders Jonsson, Krysia Broda, and Alessandra Russo. Induction and exploitation of subgoal automata for reinforcement learning. Journal of Artificial Intelligence Research. 2021.
Malik Ghallab, Craig Knoblock, David Wilkins, Anthony Barrett, Dave Christianson, Marc Fried- man, Chung Kwok, Keith Golden, Scott Penberthy. David Smith, Ying Sun, and Daniel Weld. PDDL the planning domain definition language. 1998.
Lin Guan, Sarath Sreedharan, and Subbarao Kambhampati. Leveraging approximate symbolic mod- els for reinforcement learning via skill diversity. arXiv preprint arXiv:2202.02880 2022.
Bradley Hayes and Brian Scassellati. Autonomously constructing hierarchical task networks for planning and human-robot collaboration. In IEEE International Conference on Robotics and Automation, 2016.
11

---

Published as a conference paper at ICLR 2024
Jonathan Ho and Stefano Ermon. Generative adversarial imitation learning. Advances in Neural Information Processing Systems, 2016.
Rodrigo Toro Icarte, Ethan Waldie, Toryn Klassen, Rick Valenzano, Margarita Castro, and Sheila Mcllraith. Learning reward machines for partially observable reinforcement learning. Neural Information Processing Systems, 2019.
Rodrigo Toro Icarte, Toryn Klassen, Richard Valenzano, and Sheila A. Mcllraith. Reward machines: exploiting reward function structure in reinforcement learning. Journal of Artificial Intelligence Research, 2022.
Mu Jin, Zhihao Ma, Kebing Jin, Hankz Hankui Zhuo, Chen Chen, and Chao Yu. Creativity of ai: Automatic symbolic option discovery for facilitating deep reinforcement learning. In AAAI Conference on Artificial Intelligence, 2022.
B Ravi Kiran, Ibrahim Sobh, Victor Talpaert, Patrick Mannion, Ahmad A. Al Sallab, Senthil Yoga- mani, and Patrick Pérez. Deep reinforcement learning for autonomous driving: survey. IEEE Transactions Intelligent Transportation Systems, 2022.
George Konidaris, Leslie Pack Kaelbling, and Tomas Pizano-Perez, From skills to symbols: Learn- ing symbolic representations for abstract high-level planning. Journal of Artificial Intelligence Research, 2018.
John Koza. Genetic programming: On the programming of computers by means of natural selection. Statistics and computing, 1994.
Tejas Kulkarni, Karthik Narasimhan, Ardavan Saeedi, and Joshua B. Tenenbaum. Hierarchical deep reinforcement learning: Integrating temporal abstraction and intrinsic motivation. Advances in Neural Information Processing Systems, 2016.
Junkyu Lee, Michael Katz, Don Joven Agravante, Miao Liu, Tim Klinger, Murray Campbell, Shirin Sohrabi, and Gerald Tesauro. Al planning annotation in reinforcement learning: Options and beyond. In Planning and Reinforcement Learning Workshop at International Conference on Au- tomated Planning and Scheduling, 2021.
Youngwoon Lee, Shao-Hur Sun, Sriram Somasundaram, Edward Hu, and Joseph Lim. Com- posing complex skills by learning transition policies. In International Conference on Learning Representations, 2019.
Yu-An Lin, Chen-Tao Lee, Guan-Ting Liu, Pu-Jen Cheng, and Shao-Hua Sun. Addressing long- horizon tasks by integrating program synthesis and state machines. arXiv:2311.15960 2023.
Zachary C Lipton, Jianfeng Gao, Lihong Li, Xiujun Li, Faisal Ahmed, and Li Deng. Efficient exploration for dialogue policy learning with bbq networks & replay buffer spiking. arXiv preprint arXiv: (60:::60800000 05081, 2016.
Anthony Liu, Sungryull Sohn, Mahdi Qazwini, and Honglak Lee. Learning parameterized task structure for generalization to unseen entities. In AAAI Conference on Artificial Intelligence, 2022.
Guan-Ting Liu, En-Pei Hu, Pu-Jen Cheng, Hung-Yi Yi Lee, and Shao-Hua Sun. Hierarchical program- matic reinforcement learning via learning to compose programs. In International Conference on Machine Learning. 2023.
Wei- Loh. Classification and regression trees. Wiley interdisciplinary reviews: data mining and knowledge discovery, 2011.
Daoming Lyu, Fangkai Yang, Bo Liu, and Steven Gustafson. Sdrl: Interpretable and data-efficient deep reinforcement learning leveraging symbolic planning. In AAAI Conference on Artificial Intelligence, 2019.
Jiayuan Mao, Tomás Serano-Pérezz Joshua B. Tenenbaum, and Leslie Pack Kaelbling. PDSketch: Integrated domain programming, learning, and planning. In Neural Information Processing Sys- fems, 2022.
12

---

Published as a conference paper at ICLR 2024
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, loannis Antonoglou, Daan Wier- stra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint arXiv:1312.5602, 2013.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wier- stra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. Nature, 2015.
Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuogiu. Asynchronous methods for deep reinforcement learning. International Conference on Machine Learning, 2016.
Thanh Thi Nguyen, Ngoc Duy Nguyen, and Saeid Nahavandi. Deep reinforcement learning for multiagent systems: A review of challenges, solutions, and applications. IEEE Transactions on Cybernetics, 2020.
Hanna Pasula, Luke Zettlemoyer, and Leslie Kaelbling. Learning symbolic models of stochastic domains. Journal of Artificial Intelligence Research, 2007.
Shubham Pateria, Budhitama Subagdja, Ah-hwee Tan, and Chai Quek. Hierarchical reinforcement learning: A comprehensive survey. ACM Computing Surveys, 2022.
Deepak Pathak, Pulkit Agrawal, Alexei A. Efros, and Trevor Darrell. Curiosity-driven exploration by self-supervised prediction. In International Conference on Machine Learning, 2017.
Antonin Raffin, Ashley Hill, Adam Gleave, Anssi Kanervisto, Maximilian Ernestus, and Noah Dor- mann. Baslle-bsselinss:: Reliable reinforcement learning implementations. Journal of Machine Learning Research, 2021.
Roberta Raileanu and Tim Rocktäschel.
RIDE: Rewarding impact-driven exploration for procedurally-geneeeee environments. In International Conference on Learning Representattons, 2020.
Stéphane Ross, Geoffrey Gordon, and Drew Bagnell. A reduction of imitation learning and struc- tured prediction to no-regret online learning. In International Conference on Artificial Intelligence and Statistics, 2011.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017.
Claude Elwood Shannon. A mathematical theory of communication. The Bell system technical journal, 1948.
Tom Silver and Rohan Chitnis. PDDLGym: Gym environments from PDDL problems. Planning and Reinforcement Learning Workshop at International Conference Automated Planning and Scheduling, 2020.
Tom Silver, Ashay Athalye, Joshua B. Tenenbaum, Tomás Lozano-Pérez, and Leslie Pack Kaelbling. Learning neuro-symbolic skills for bilevel planning. In Conference Robot Learning, 2022.
Sungryull Sohn, Junhyuk Oh, and Honglak Lee. Hierarchical reinforcement learning for zero-shot generalization with subtask dependencies. Neural Information Processing Systems, 2018. 8.
Sungryull Sohn, Hyunjae Woo, Jongwook Choi, and Honglak Lee. Meta Reinforcement Learning with Autonomous Inference of Subtask Dependencies. arXiv preprint arXiv:2001.00220 2020.
Sungryull Sohn, Hyunjae Woo, Jongwook Choi, lyubing qiang, Izzeddin Gur, Aleksandra Faust, and Honglak Lec. Fast inference and transfer of compositional task structures for few-shot task generalization. In Uncertainty in Artificial Intelligence, 2022.
Roni Stern and Brendan Juba. Efficient, safe, and probably approximately complete learning of action models. In International Joint Conference on Artificial Intelligence, 2017.
13

---

Published as a conference paper at ICLR 2024
Shao-Hua Sun, Hyeonwoo Noh, Sriram Somasundaram, and Joseph Lim. Neural program synthesis from diverse demonstration videos. In International Conference on Machine Learning, 2018.
Shao-Hua Sun, Te-Lin Wu, and Joseph Lim. Program guided agent. In International Conference on Learning Representations, 2020.
Maxwell Svetlik, Matteo Leonetti, Jivko Sinapov, Rishi Shah, Nick Walker, and Peter Stone. Au- tomatic curriculum graph generation for reinforcement learning agents. AAAI Conference on Artificial Intelligence, 2017.
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.
Mauro Vallati, Lukas Chrpa, Marek Grzeš, Thomas Leo McCluskey, Mark Roberts, Scott Sanner, et al. The 2014 international planning competition: Progress and trends. Al Magazine, 2015.
Manuela Veloso, Jaime Carbonell, Alicia Perez, Daniel Borrajo, Eugene Fink, and Jim Blythe. Inte- grating planning and learning: The prodigy architecture. Journal of Experimental Theoretical Artificial Intelligence, 1995.
Marco Virgolin, Tanja Alderliesten, Cees Witteveen, and Peter A. N. Bosman. Scalable genetic pro- gramming by gene-pool optimal mixing and input-space catropy-based building-blee block learning. In Genetic and Evolutionary Computation Conference, 2017.
Marco Virgolin, Tanja Alderliesten, Cees Witteveen, and Peter AN Bosman. Improving model-based
genetic programming for symbolic regression of small expressions. Evolutionary computation, 29(2):211-255 2021.
Lucas Willems. PyTorch Actor-Critic deep reinforcement learning algorithms: A2C and PPO.
https://qithube wow/:/caiwweemm///oooooooeoeeoe ac 2022.
Zhe Xu, Bo Wu, Aditya Ojha, Daniel Neider, and Ufuk Topeu. Active finite reward automaton inference and reinforcement learning using queries and counterexamples. In Machine Learning and Knowledge Extraction, 2021.
Qiang Yang, Kangheng Wu, and Yunfei Jiang. Learning action models from plan examples using weighted max-sat. Artificial Intelligence, 2007.
14

---

Published as a conference paper at ICLR 2024
APPENDIX
A PRELIMINARY DEFINITION
This section provides the annotations of the Markov decision process (MDP) and planning specifi- cation discussed Sectino Section A.1 gives the formulation of MDP problems and Section A.2 explains the definition and the annotation of planning domain definition language (PDDL).
A.1 MARKOV DECISION PROCESS
A decision-making problem is formulated as Markov decision process (MDP). MDP consists of a five-tuple AS T, R, 7), where S denotes state space, A denotes action space, T x A S denotes a transition function, R S x A + IR denotes a reward function, and (0, 1] denotes discounting factor.
In contrast with classical planning. problems in reinforcement learning represent the actions and the states with vectors of numeric values instead of literal conjunctions. A state in S is re-dimension vector 8, where each entry 8i, i E (1, 2.., n... represents the value of numeric variable. this work, focus goal-directed sparse-rewart problems. That is, given an initial state, the objective to find policy to reach a desired goal state, and the agent only receives rewards when reaching the goal state.
A.2 PLANNING DOMAIN DEFINITION LANGUAGE
PDDL is a language in first-order logic to describe the domains and the problems. domain de- scription includes the specification of objects, variables, and action models with preconditions and effects. A problem description includes an initial state and goal specification. These standard lan- guage specifications allow off-the-shelf planners to deduce the optimal action sequence of the goal.
For theory formalism, we follow the representation of SASt To distinguish with MDP state space S, the state space in the planning domain are denoted as S'. A SAS* task II can be represented as a tuple (V, O, s' Pgoul) where V is set of variables, and O set of operators in the domain. A state s' E S' the planning domain is an assignment to V, and s' E R is the value assigned to the variable Specifically, s'ii E S' is the initial state, and Pgoat is a partial state of the goal specification.
V in s'. p' C. <'' is partial state of s', where p' is the assignment to V(p') C. V.
A logical condition ly describes the relation between the variable and an distinct value (e.g. wood 1, stick 2 2). Each operator E O can be described as an action schema in a pair (pre(o), elf (o)), where pre(o) is conjunction of logical conditions denoted the precondi- tion needed to be satisfied before executing o, eff (o) is a set of functions denoted the change toward the state variables after executing The prevail condition is a subset of pre(o) which holds during the action and does not affect by the effect, denoted as pro(o) = (lp h E pre(o), v g (o)) An operator is admissible in state s' iff pre(o) s' and (rv(o) s'
B IMPLEMENTATION DETAIL
In this section, we elaborate on the implementation detail of the proposed framework that was used in the experiments, We implement several modules using off-the-shelf packages and approaches, including genetic programming symbolic regression with gplearn, the agents with PPO, and the intrinsic reward function we use in the experiments.
B. ALGORITHM IN EXTRACTING ACTION EFFECT LINKAGES
In Algorithm|] 1 for each MDP action, we calculate the mutual information between the action and all combinations of effect variables in demonstrations. Then, apply the two-center clustering method to determine the threshold shown in Algorithm?? 2 Two-center clustering finds a threshold value that separates given data into two clusters, which minimizes the sum of distances of data points from their respective cluster centers. We take the logarithm of mutual information as the metric to avoid incorrect thresholds caused by extremely high mutual information.
15

---

Published as a conference paper at ICLR 2024
Algorithm Extracting Action-Effect Linkages
Input: Demonstrations, action set A, effect set 3 Output: Action-effect pairs with linkages L 4-00 0
for a in AAdo
No +- 0 for (.) in E do Na < Na U (ef((e
end for t 4- CwooCCenter-Clusteeing(Aaa for (-) in & do if M(tt 2 then I. LU (a, (())(()))
end if' end for end for
Algorithm 2 Two-Center- Cio--Center-Clustering
Input: Data D with length Output: Threshold of two clusters dusterr,cuuster, < 0
C12 C2 - min(D), max (D)
if c1 02 then
return C1
end if
terminaled + False
while not lerminaled do: for i = to n do
if D c1 [Dii] 02 then
cluster < D[i]
else
clusters < D[i] end if end for d' c2 + mean(clusterr., neen(cduster).mmmnn((sstt)))) mean(cluster))
if ci oi and C2 c₂ then
terminated <- True
end if
C1, 02 + c, c end while
return (cI + 02)
B.2 GENETIC PROGRAMMING
Genetic programming is employed as symbolic regressor for determining symbolic effect rules in the proposed methods, illustrated in Figure 3al We use the gplearn package for implementation and the parameter settings of are shown in Table 2 Given the action-effect linkage (a. ((eff( (-))), the transitions with action are selected as the training data. For each effect variable (eeff (-)). the algorithm's is objective is to find the program eff (.), that predicts after executing the action with the highest accuracy.
Each program is represented as an expression tree where input is the current state in the transition and output is the predicted value. The algorithm comprises several steps: initialization, evaluation, selection, crossover, and mutation. Initially, the population, which is a set of programs, is randomly generated. Fimess evaluation is then performed on all programs; subset of programs with the highest fitness values selected. These programs serve as parents to produce offspring through crossover and mutation mechanisms. Through iterative selection and production, the evolution of
16

---

Published as a conference paper at ICLR 2024
Table 2:
The parameter setting of gplearn. The parameter with two values indicates that the settings are different in two phases.
Parameters
Value (first/sccond phase)
population_sin _iize
2000/2000
tournamen_siize
40/40
generations
20/10
p_crossover
0.6/0.6
mutaatin
0.2/0.2
hoist mutation
0.1/0.1
point mutation
0.05/0.05
max_ samples
0.95/0.95
init_depth
(2,6)(2,6)
parsimony_coe ccoffficient
0.0001/0.005
function set
{+, {+,-,X, inc, detc//tt++ x, inc, dec}
the population to discover the programs that best fit the given data. The evaluation metric used in genetic programming is the percentage of correct effect prediction shown below:
fitness(efi) (+)) # of transitions with (a, ((eef(()) consistent with eff eff
# of transitions with (a, ((eff(-))
where a transition consistent with (-)x means that the predicted effect value eff (-)) is consis- tent with the actual one ('s. a) given the transition (s, a, ((,, a)). To prevent bloat issues which the program grows extremely large to fit the data, the algorithm contains two phases: exploring and pruning. The best programs with the highest accuracy are determined in the exploring phase. Subsequently, in the pruning phase, we set high parsimony to prune the program.
B.3 DECISION TREE METHOD
The proposed framework uses classification and regression tree (CART) (Loh 2011 build deci- sion trees. CART is supervised learning algorithm that generates binary trees by recursive parti- tioning, where each internal node represents a decision based on specific variable, and each leaf node represents prediction. Let data partitioned at the internal node m denoted as Dm with n.m samples. The algorithm aims find decision with a variable and threshold to partition D, into two subsets Do and D m. with ni and n!! samples. The loss function of the partition is defined
as follows:
nh Tm
Th H(D!.) Thm
G(D m: 9,t)
H(D
where H(Di..) the entropy of D each partition, the algorithm's objective is to find the (q, t) that minimizes G(D,,, q, t) at node This process is repeated until stopping criterion is met.
In the given transition (s, T(s, with in demonstrations, the current states are taken inputs to a decision tree, and the outcome of the decision tree a true value that whether T(s. a) consistent with the rules in eff' (-). After generating decision tree by CART, the model of this decision tree is then transferred into a conjunction of rules by logical simplification and set as the precondition rules pre(.), while (-pre(-)) is the of variables mentioned in pre(-). (-). Considering the precondition is the conjunction of the precondition rules while the formula of the decision tree may involve disjunction, the decision tree model is transferred into the disjunctive normal form. Each clause in the disjunctive normal form is considered the precondition for different critical actions.
B.4 DEEP REINFORCEMEN" LEARNING MODULE
In our research, adopt the Proximal Policy Optimization (PPO) the foundation for our frame- work and the baseline in this work, utilizing the torch-ac ac library (Willems) 2022) for implementation. The architecture of our model is designed to encode 8x8 gridworld and state information.
17

---

Published as a conference paper at ICLR 2024
The gridworld is handled by convolutional neural network (CNN) comprising four layers. The network effectively processes the imput images, which are formatted in a three-channel setup, repre- senting the object, color, and status respectively. The first convolutional layer utilizes 32 filters with a kernel size of 3x3 and a stride of 2x2. Subsequent layers employ 2x2 kernels, with channel sizes incrementing through 64, 96, to 128. Each layer integrates the ReLU activation function.
Parallelly, the state representation, converted into PDDL., is encoded through two-layer fully- connected network. Each of these layers contains 64 neurons and leverages the ReLU activation function for non-linear transformation.
Two types of encoded observation are concatenated and encoded by another two-layer 64 64 fully- connected network. The output-encoded observation is then used as the input of the actor network and the critic network. Both the encoding networks and the actor-critic networks are trained.
B.5 REWARD FUNCTION
During the training stage, we train an agent with intrinsic rewards generated from the critical action network. The modified rewards function is illustrated as follows:
{ if execute a critical action,
Rint (s) = 0
(4)
otherwise.
Given the original reward function R as extrinsic rewards, the overall reward of the MDP problem (omo(s) = R(s) (sne(s). In the experiment, the reward function is defined
stepmez slepmar
if the episode terminated,
R =
(5)
otherwise,
where stePmar is the maximum number of steps in the environment, and step is where step is the current number of steps the agent has done. The setting of the maximum number of steps in each environment is described in Appendix C
C TEST ENVIRONMENTS
We use three MDP environments: SWITCH, DOORKEY, and MINECRAFT for evaluation. The first environment SWITCH tests the ability to achieve sequential tasks. The second environment DOORKEY is similar to door-key in Minigrid which is a bascline environment with hicrarchical tasks. The third environment MINECRAFT is designed to evaluate the ability to construct various task structures with multiple subtasks for compositional tasks. The following sections provide a description of the environments. The maximum number of steps in DOORKEY is 1600, while in SWITCH and MINECRAFT is 25600.
C.1 SWITCH
The environment SWITCH is designed to evaluate the ability solve hierarchical tasks. In SWITCH, several switches are placed on the grid. The objective of the agent in SWITCH is to sequentially turn on switches pre-determined order.
We define the state variables as V fat_switch, next switth, goal_switch). at_switch indicates the switch the agent stays at. If the agent does not stay at any switch, this variable is zero. next switch indicates which switch should be activated in the following actions. goal switch denotes the last switch and also implies how many switches should be turned on. The action space contains five actions: {left, up, down, toggle). toggle enables the agent to activate or deactivate switch.
The switches have three states, including available, on and off The agent can turn the available switch to on. If the agent executes the action toggle at the switch, it will be deactivated and turned to available. The agent can not change the status of the off switch until the predecessor switch is a on switch is turned to available, all subsequent switches will also be deactivated. This makes challenging for RL agents to solve the task through random walks exploration alone.
For various evaluations, design several situations, including the number of switches, sequential order, and distractors. In the following sections, the settings of the tasks are listed and the illustra- tions can be found in Figure
18

---

Published as a conference paper at ICLR 2024
(a) 4-SWITCHES
(b) 8-SWITCHES
(c) 4-DISTRACTORS
(d) 4-RoOMS
Visualization of SWITCH environments. N-SWITCHES in (a) and (b) shows the tasks which consist of and 8 switches in incremental order. (c) N-DISTRACTORS the variant N- SWITHES with other distractor switches (the circle with dotted line). (d) combines four-room environment in Minigird, testing the navigation ability the agent.
Figure 7:
When the number of switches increases, the tasks become more difficult as it has more chance to turn off the switch. This setting evaluates the performance of different difficulties of tasks.
N-SWITCHES.
N-DISTRACTORS. Available switches are added as distractors the environment. The agent can turn on and off the distractor switches, but it does not help to achieve the tasks. In n-switch ineremental-order tasks, the switches labeled n tors, while in n-switch incremental-orde tasks, the switches labeled 2, ..... 2n are set as distractors. This setting evaluates whether the agent acquires the ability to select correct switches and neglects the incorrect ones.
are set as distrac-
4- 4-RooMs. Two lines of walls divide the gridworld into four rooms according to the four- room configuration Minigrid. Every two rooms are interconnected by a gap in the walls. In this scenario, the agent must navigate through the rooms considering the walls to activate the switches. This setting evaluates the efficacy of DRL involving navigating obstacles at low-level execution.
Order of the switches. To evaluate generalizability, we define two types of orders in- cluding (N+1) and (2N+1). (N+1) indicates that the switches should be turned on in incremental order (i.e., indicates that the switches should be turned on odd order (i.e., + - 5 - 7...) where (goal switch 2n + 1). The order labeled after the task name (e.g.. 4- (ISTRACTORS-((+1). and by default the order (N+1).
2 + 3 + 4...) where (goal_switch n). and (2N+1)
C.2 DOORKEY
The enviromment DOORKEY presents a task where an agent must collect a key to unlock door and turn on the switch behind the door. It is basic setting which can be used evaluate the ability to solve hierarchical tasks.
We define the state variables as = fagent_dil _irr has key, door statt, at st_switch, at at_door, next. pext_switch). agent dir indicates the agent direction, has key indicates whether the agent holds the key, and door_state indicates the state of the door, including open, closed, and locked. The action space A contains seven actions: (left, right, up, down, toggle, pickup, drop). toggle enables the agent to activate switch open the door.
C.3 MINECRAFT
MINECRAFT is inspired by the computer game Minecraft and is similar to the environment in previ- ous works (Sonn et al. 2018 Andreas et al. 2017 Sun et al.) 2020 Brooks et al.) 2021 illustrated in Figure 8a The agent can pick up the primary materials on the map and make different tools in specific places consuming the materials. The goal of each task is to acquire the desired materials or tools. The state variables include {x, denotes whether the agent is at the place, and inventory > denotes the number of materials or tools the agent holds.
at at_
place
inventory >> where at. place >
19

---

Published as a conference paper at ICLR 2024
at wood
Mike, Btick
at_stone
wite Atone piakaze
at_iron
at at_gem
pielipp Iron
at wor.keebeechh
pickets
at toohhed
at_ sheep
Inventory
wood 2, 8tone
Juksbox
(a) Visualization of MINECRAFT environment.
(b) Dependency of subtasks in MINECRAFT.
Figure 8: Illustration of configuration and subtask dependencies MINECRAFT environment. (a) There are 7 locations in MINECRAFT environment, and the agent needs collect materials and craft tools at specific location. (b) illustrate the dependencies of the critical actions. For instance, to execute pi pickup_iron, the agent needs make stone pickaxe. The graph ignores preconditions, effects, and the number of executions required.
In our experiments, thirteen types of items designed in the inventory: wood, stone, stick, iron, gen, stone pickaxe, iron pi sicaxxe, wool, paper, scissors, bed, jukebox, enhance table, and there seven places the gird world: at wood, stone, iron, at gem, at sheep, at_workbench, at_toolshed.
The action space A contains eight actions: (left, right, up, down, make1, make2, make3, make4). The agent crafts different items when executing different make actions (make1, make2, make3, make4) and at different places (workbench or toolshed). The formulas of the items are listed in Table 3 and the dependency of the subtasks is illustrated the materials to create desired items. We test two single tasks with different difficulties IRON and ENHANCETABLE and multiple task MULTIPLE that sample the goal random.
Figure 88b The agent needs to get
20

---

Published as a conference paper at ICLR 2024
Table Formulas in MINECRAFT environment. The MDP actions, precondtions and effects are the same as their corresponding critical actions.
Inventory
MDP Action
Preconditions Effects
at_wood wood +
wood
pickup
at_stone 1 stone +
stone
pickup
at_iron iron +
stone.pickaxe 2
iron
pickup
at.gem gem+1
iron_pickaxe 2
gem
pickup
at_sheep wool +1
scissors
wool
pickup
at_workbench =1 stick +
stick
make1
wood
at at.toolshed stone picckee
stone pickaxe
make1
stone 3
stick
at.toolshed iron pickaxe +
iron pickaxe
make2
iron - 3 stick 2
at-workbench =
iscissors
make2
scissors +1
iron -
at_workbench
scissors 2
paper
make3
paper -
wood
at_toolshed bed
bed
make3
wood 3
wool 3
at.workbench =1 jukebox +
jukebox
make4
wood
gem 1
at.toolshed = enhance table
enhance.table
make4
stone
paper
gem
D CRITICAL ACTION
The critical action and its graph are shown in this section. Tables 4 and 5 show the critical actions in DOORKEY and SWITCH environments. The rules of critical actions MINECRAFI AFT environment are already listed in Table 3 and are omitted in this section. Figures 2 critical action networks of N- N-SWITCHES, DOORKEY, IRON and TABLNC respectively.
IO II and 12 illustrate the
Table 4: Critical actions in SWITCH environment.
Action Name
MDP Action
Preconditions
Effects
at_switch next_switch next_switch
turn_on
toggle
21

---

Published as a conference paper at ICLR 2024
Table 5: Critical actions in DOORKEY environment.
Action Name
MDP Action
Preconditions Effects
at at_key = at_key
pickup_key
pickup
has_key
door state 0 at at.door =
agent dir = 1
open door
toggle
door_state 2
switch door state
turn
toggle
next switch +
next cert_switch11
at at__switch next sww. next_switch
turn toggle
x goal C
next www.switttt. switch+(1xgga]]
next next_ 1tt__sstthhhhg-11111
Figure 9: Critical action network of SWITCH
next swi next_swi tch=1
at key=1
pickup key pickup
dir=1
at door=1
has key=1
at It_key=0
open door
toggle
door door_statee state=0
at stisticch=1
turn on toggle
next_s$i text_switch+
next sext__swicch=11
Figure 10: Critical action network of DOORKEY
22

---

Published as a conference paper at ICLR 2024
iron
wood
pick_wood wood
pickup
wood+ (1x4)
1ood>(2x2)
at workbench
at stone 1
make stick
pick stone pickup
2
make1
wood- (2x2)
stick+ ( (1x2)
stone+ + ( (1x3)
stick 2
stone 3
at at_toolshed
make_stone stone pickaxe
make1
stone pickaxe
stick 2
stone 3
stone pickaxe 2
pick iron pickup
iron
iron
Figure 11: Critical action network of IRON
23

---

Published as a conference paper at ICLR 2024
table
at wood 1
pick pickup
wood wood=(1xg) (1*8)
at stone
4x2)
workbench
pick_ator _tton
make stick
pickup
make1
(1x3)
(1x2k-(1x2)
at toolsbed
Stone 3
stick 2
x make stone pickaxe
stone_pickaxe pickaxe stone
stick
stone 3
stone pickaxe 2
iron
pickup
(ron+(1w2)
Iron=(1x3) (1x3)
stickt(1x2)
workbench
at
x make scissors
make iron pickaxe
make2
x
makel
Wood+(1x2) (1x2)
scissors
iron
iron pickaxe
stick
iron
st workbenchh wood? 1x2) (1x2)(1x2)
scissors 2
iron pickaxe 1
paper
pick gem pickup
make?
wood (1 (1x2)
papert (1x2)
stone+
gam
paper 2
at_ boolshed
stone 3
gem
make enhance table
makes
paper
gest
enhance table
Figure 12: Critical action network of ENHANCETABLE
24


Reviews:
[{"review_id": "LWecIX845B", "reviewer": "Reviewer_hQ37", "summary": "This paper presents a method that integrates automated planning and deep reinforcement learning for solving sequential decision-making problems, such as grid navigation problems. \nThis paper assumes that the state of an RL environment is annotated with symbolic representations, such that the agent can obtain a trace of symbolic states given an RL trajectory. \nThe main idea is that the agent first learns an action model, which is called critical action in this paper, that specifies how the state changes due to the application of the action, given human demonstrations. After obtaining an action model in which a symbolic action is associated with a single RL action, the agent performs planning with backward chaining to find a plan and use it to train an RL policy with PPO.", "questions": "### General questions\n\n1. In the experiments, can you show the number of action operators learned to solve each problem? What is the length of the plans? For generating demonstrations given a problem environment, what are the prior knowledge required for an expert?\n\n2. Do you assume that you have a symbolic state annotation for an RL state and grounded action operators in the environment?\n\n\n### Learning action models from traces\n3. In the action-effect linkages, is $a$ an RL action (for example, make1 in Figure 3(b))?  How do we know that make1 maps to make_stick ? For computing mutual information, how many cases need to be considered? Is it |A| * \\sum_{r=1^n} nCr for n being the number of variables? nCr is the number of selecting r variables from n variables. What is the typical number of variables considered in the experiment?\n\n4. Precondition is found by learning a decision tree. I think it will be meaningful to compare this approach of learning action model (effect and precondition) with papers mentioned above [1,2] or other methods in automated planning [3, 4].\n\n5. In the Minecraft example, make_stick fits well with the presented approach. make_stick only changes features to make a stick by consuming wood and stick in the inventory, and there is a unique MDP action make1 that corresponds to this action. Minecraft environment will generate a sequence of actions that transform objects to a particular object and it will be given by human demonstration. What aspect of this example can be generalized such that the agent doesn't need to see the demonstration?\n\n6. What are the critical actions in mini-grid environments?\n\n### Planning\n7. What if some of the critical actions had incorrect preconditions and effects learned? Figure 6 shows that the accuracy cannot reach 100% and it implies it may miss some effect variable. Or it may skip some states that some critical action is applicable due to incorrect precondition. Is there any guarantee that the presented approach solves the problem?\n\n8. What is the length of the plans for solving each problem?\n\n### Reinforcement Learning\n\n9. DoorKey or 4-Rooms environments are too small-scale. Did you try on larger scale problems in mini-grid or BabyAI? \n\n10. Did you train a single RL agent for low-level policy?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "* Originality: The originality of this work is the notion of action-effect linkage that finds effect variables for an action. For finding symbolic expression of action models, this paper proposes a method using genetic programming to find effects with numeric expressions.\n* Quality: The paper shows ideas in words and figures to help to understand the basic concepts.\n* Significance: This paper shows that the proposed method outperforms several baselines in grid-world environments.", "weaknesses": "Originality:\n\nRegarding action model acquisition from RL environments, there are related works, such as [1, 2]. Learning action models from symbolic traces is also a widely studied topic in automated planning [3, 4]. The papers such as [1, 2] have similar problem settings, so it is worth mentioning in the paper. \n\n[1] Jin, M., Ma, Z., Jin, K., Zhuo, H. H., Chen, C., & Yu, C. (2022, June). Creativity of ai: Automatic symbolic option discovery for facilitating deep reinforcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 36, No. 6, pp. 7042-7050).\n\n[2] Lyu, D., Yang, F., Liu, B., & Gustafson, S. (2019). SDRL: Interpretable and Data-Efficient Deep Reinforcement Learning Leveraging Symbolic Planning.\n\n[3] Arora, A., Fiorino, H., Pellier, D., Métivier, M., & Pesty, S. (2018). A review of learning planning action models. The Knowledge Engineering Review, 33, e20.\n\n[4] Yang, Q., Wu, K., & Jiang, Y. (2007). Learning action models from plan examples using weighted MAX-SAT. Artificial Intelligence, 171(2-3), 107-143.\n\nClarity: \n* There are very strong assumptions made in the paper that can be easily overlooked. \nFor example, action precondition is defined over all variables, one action impacts specific features, and critical action maps to exactly one MDP action. It needs clarification on why those assumptions are needed.\n\nSignificance: \n\nEnvironments tested in the experiment section are small-scale.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "UdILI0DyeX", "reviewer": "Reviewer_Yjtd", "summary": "- The proposed work automatically infers substructures from demonstrations that enable generalization to adapt to new environments. \n\n- Induction stage: The approach uses genetic programming to infer action schemata and extracts symbolic knowledge in the form of critical actions from it.\n\n- Training stage: The approach uses the inferred model of symbolic rules that represent task substructures to build a critical action network online from the goal by backward-chaining. Whenever critical actions are achieved instrinsic rewards are provided.\n\n- The work considers deterministic, fully observable but unknown environments.", "questions": "Included with the limitations.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The idea of using genetic programming to learn symbolic action schema and extracting the relevant substructures for a specific goal is interesting.\n\n- The paper is well-written and clear. The results are convincing.", "weaknesses": "- There is much work on learning action models from demonstrations or trajectories as also mentioned in the related work section. How is the induction stage different from that line of research?\n\n- In the experimental section, it will help to report the critical actions inferred by the approach for different domains. \n\n- How does the proposed approach favor in comparison with option discovery approaches that directly learn useful substructures? What are your thoughts on the comparison of their sample efficiency?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "rVk9wDTHMr", "reviewer": "Reviewer_9Jkh", "summary": "This paper introduces a framework that combines deep reinforcement learning with classical planning techniques to tackle sparse-reward, goal-directed tasks. The framework utilizes genetic programming to automatically induce task structures from expert demonstrations, enabling efficient and robust learning in various domains. Experimental results demonstrate the framework's superior performance in terms of sample efficiency, task performance, and generalization. The paper also discusses the potential for future enhancements, particularly in addressing stochastic or partially observable environments.", "questions": "See above.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper presents an innovative approach that integrates deep reinforcement learning with classical planning techniques, offering a unique solution to address sparse-reward, goal-directed tasks. This integration leverages the strengths of both paradigms. The paper provides empirical evidence through experiments in gridworld environments, demonstrating the superior performance of the proposed framework in terms of sample efficiency and task performance compared to other methods, including DRL and imitation learning. Finally, the paper offers a clear and comprehensive discussion of the proposed framework, including its components and the potential for future enhancements, such as handling probabilistic rules in uncertain environments.", "weaknesses": "- There is a plethora of works on integrating learning and planning, [1,2,3] to name a few. Missing them in the related work section devalues the overall presentation of the work. I strongly suggest having this line of work included and compared against.   \n- In section 3, the MDP tuple is not explained. By convention, one could understand what `S` , `A`, and others stand for, but it would be better if authors could include their formal definitions.   \n- How critical states and actions are recognized? I see that it is discussed in section 4, but there are no verifications for such assumptions in the paper.   \n- Most recent method used as a baseline was introduced in 2020, which would neglect the progress made in the literature since then. I would suggest to include more recent approaches as baselines as well.\n- With the use of genetic algorithms, since it is one the most important integral parts of the proposed method, how would it affect the scalability of the overall approach?\n    \n\n[1] Veloso, Manuela, et al. \"Integrating planning and learning: The PRODIGY architecture.\" Journal of Experimental & Theoretical Artificial Intelligence 7.1 (1995): 81-120.\n[2] Danesh, Mohamad Hosein, Panpan Cai, and David Hsu. \"LEADER: Learning Attention over Driving Behaviors for Planning under Uncertainty.\" *Conference on Robot Learning*. PMLR, 2023.\n[3] Zhao, Luyang, et al. \"PLRC\\*: A piecewise linear regression complex for approximating optimal robot motion.\" *2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)*. IEEE, 2020.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "zyndXqyulW", "reviewer": "Reviewer_n4PR", "summary": "In this paper, the authors seek to speed up deep reinforcement learning by inferring a classical planning model from expert demonstrations. Specifically, they infer PDDL-style preconditions and effects of \"critical actions\" (actions that are crucial for success and must be executed in a particular order) via genetic programming. Later, when training an RL agent to perform the granular actions required to complete the task, they use backward-chaining to infer the next critical action that should be taken, and provide an intrinsic reward to the RL for completing that action. Experiments in three gridworld domains show that this approach learns faster than several competing methods (vanilla RL, behavioural cloning, and an alternative intrinsic reward approach), and further show that the inferred knowledge can be readily applied to new task instances.", "questions": "Have you considered extending the approach to work without expert demonstrations? It seems to me that the induction module should still work, although it probably wouldn't be able to infer as many rules at the start of training (because certain types of transition wouldn't have been seen yet). However, rather than backward chaining from the goal, you could potentially backward chain from novel states, so as to encourage the agent to explore.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "RL algorithms would have far more practical value if they could solve sparse-reward, goal-directed tasks quickly, since it's generally easier to specify tasks in these terms, especially for non-experts. Humans clearly do use some form of planning to solve such tasks, and intuitively we do learn high-level rules akin to action schemas, so this line of work is natural and well-motivated.\n\nI'm familiar with much of the related work on hierarchical task learning, and while I'm not 100% sure about the authors' claim that \"induc(ing) the required subtasks has not been addressed\" (for example, Icarte et al., 2019 arguably do this to some degree), their approach to the problem is novel. I certainly haven't seen genetic programming applied in this context before, and it's an interesting idea!", "weaknesses": "The main issue I have with the paper is that the limitations/assumptions aren't sufficiently discussed. In particular:\n- Deep reinforcement learning applications often involve learning from high dimensional input (e.g., pixels) or dealing with continuous controls (e.g., MuJoCo, real-word robotics). However, it's hard to see how the proposed approach would extend beyond discrete, gridworld-style tasks. At the top of page 6 it's claimed: \"This choice of function set is consistent with the numerical variable representation commonly employed in DRL tasks\", but seemingly the true assumption here is that the state can be encoded as a vector of *integers*. If true, this should be acknowledged, and either way I'd like to see a discussion of how the approach could be extended to more complex domains.\n- The assumptions around \"critical actions\" aren't clear. It seems that the approach requires a human expert to deem which state variables are important (e.g., those corresponding to the inventory in Minecraft) and which are non-critical (e.g., the player's position). Again, this ought to be discussed.\n\nA secondary concern is that there doesn't appear to be any source code included with the submission (correct me if I'm wrong) and the reinforcement learning setup isn't clear. For example:\n- How is the 8x8 gridworld represented to the agent? Do you use different channels to represent different types of object, or just a single channel with different numerical values?\n- Why is the agent paid a decaying reward based on the current step number (Appendix B.5)? Is this meant to be paid only at episode termination, or at every step? (The former would make more sense to me, but it's not expressed like this.)\n- The gridworld and the PDDL state are encoded via a convolutional neural net and a fully-connected network, respectively. Are these encoders trained or fixed? What are kernel sizes of the CNN?\n- I found the generalizability experiments quite confusing. Is the \"ours\" agent retrained in the variant domains after re-inducing the rules? (I can't see how it would generalize otherwise.) Are the original demonstrations for GAIL and BC-PPO discarded? Is BC-PPO retrained in the variant domain?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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:

Decision: Accept (poster)